时间复杂度计算


O(1)

1.不包含循环、递归,也不调用其他非固定时间的函数

2.如果循环、递归花费的时间是固定的,时间复杂度也为O(1),比如下面

// Here c is a constant   
for (int i = 1; i <= c; i++) {  
    // some O(1) expressions
}

O(n)

下面代码时间复杂度为 O(n)

   // c为正整数常量 
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

   for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
   }

O(nᶜ)

下面时间复杂度为O(n²)

for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
   }

   for (int i = n; i > 0; i -= c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
   }

O(logn)

循环变量除以或者乘以固定的常数

for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
   }
   for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
   }

O(loglogn)

循环变量常数指数级增加或者减少

// Here c is a constant greater than 1   
   for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
   }
   //Here fun is sqrt or cuberoot or any other constant root
   for (int i = n; i > 1; i = fun(i)) { 
       // some O(1) expressions
   }


多个时间复杂度一起计算

   for (int i = 1; i <=m; i += c) {  
        // some O(1) expressions
   }
   for (int i = 1; i <=n; i += c) {
        // some O(1) expressions
   }
   Time complexity of above code is O(m) + O(n) which is O(m+n)
   If m == n, the time complexity becomes O(2n) which is O(n)


例子1

void fun(int n, int k) 
{ 
    for (int i=1; i<=n; i++) 
    { 
      int p = pow(i, k);  
      for (int j=1; j<=p; j++) 
      { 
          // Some O(1) work 
      } 
    } 
}
k=1
Sum = 1 + 2 + 3 ... n 
    = n(n+1)/2 
    = n2 + n/2

k=2
Sum = 12 + 22 + 32 + ... n12.
    = n(n+1)(2n+1)/6
    = n3/3 + n2/2 + n/6

k=3
Sum = 13 + 23 + 33 + ... n13.
    = n2(n+1)2/4
    = n4/4 + n3/2 + n2/4

所以时间复杂度为 Θ(nᵏ⁺¹ / (k+1))


参考:

AnalysisofAlgorithms

上一篇: 渐进记法
下一篇: 搜索算法
作者邮箱: 203328517@qq.com