数据结构时间复杂度例子

时间复杂度例子

常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n²)、立方阶O(n³)、k次方阶O(n^k)、指数阶O(2ⁿ)

常数阶O(1)

int a = 1;
int b = 1;
int c = a + b;

对数阶O(log2n)

int a = 1;
while(a <= n) {
    a *= 2;
}

线性阶O(n)

for(int a = 1; a <= n; a ++) {

}

线性对数阶O(nlog2n)

int b;
for(int a = 1; a <= n; a ++) {
    b = 1;
    while(b <= n) {
        b *= 2;
    }
}

平方阶O(n²)

for(int a = 1; a <= n; a ++) {
   for(int b = 1; b <= n; b ++) {
       
   }
}

立方阶O(n³)

for(int a = 1; a <= n; a ++) {
   for(int b = 1; b <= n; b ++) {
       for(int c = 1; c <= n; c ++) {

       }
   }
}

k次方阶O(n^k)

for(int a = 1; a <= n; a ++) {
   for(int b = 1; b <= n; b ++) {
       for(int c = 1; c <= n; c ++) {
            // ...k层循环
       }
   }
}

指数阶O(2ⁿ)

int fun(int a) {    
   if(a <= 1) {
       return 1;
   } else {
       return fun(a - 1) + fun(a - 2);
   }
}