time complexity时间复杂度

The time complexity of an algorithm is denoted O(…) where the three dots represent some function. Usually, the variable n denotes the input size.

//O(n)
for (int i = 1; i <= n; i++) {
    // code
}

//O(n^2)
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
    // code
    } 
}

A time complexity does not tell us the exact number of times the code inside a loop is executed, but it only shows the order of magnitude.

//这些都是O(n)
for (int i = 1; i <= 3*n; i++) {
    // code
}
for (int i = 1; i <= n+5; i++) {
    // code
}
  for (int i = 1; i <= n; i += 2) {
    // code
}

//这就是O(n^2)的
for (int i = 1; i <= n; i++) {
    for (int j = i+1; j <= n; j++) {
    // code
    } 
}

一段程序中，有多个程序段落，整个程序的时间复杂度跟 时间复杂度最大的段落走

for (int i = 1; i <= n; i++) {
    // code
}
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
    // code
    }
}
for (int i = 1; i <= n; i++) {
    // code
}
//这段代码，是O(n^2)的

还有O(nm)

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
    // code
    } 
}