如何根据操作次数计算出时间复杂度

Question

所以我想知道如何根据操作次数计算出一段代码的时间复杂度（T（n）），例如下面的代码。

for( int i = n; i > 0; i /= 2 ) {
    for( int j = 1; j < n; j *= 2 ) {
        for( int k = 0; k < n; k += 2 ) {
            ... // constant number of operations
        }
    }
}

我确信它很简单，但我的讲师没有很好地教授这个概念，我真的想知道如何计算时间的复杂性！

先感谢您！

Answer 1

为了解决这个问题，一种方法是单独分解三个循环的复杂性。

我们可以做的一个重要观察是：

（P）：每个循环中的步数不依赖于其父循环的“索引”的值。

我们打电话吧

• f(n)外循环中聚合的操作数（1）
• g(n)在中间内环（2）
• h(n)在最内圈（3）。

  for( int i = n; i > 0; i /= 2 ) {            // (1): f(n)
      for( int j = 1; j < n; j *= 2 ) {        // (2): g(n)
          for( int k = 0; k < n; k += 2 ) {    // (3): h(n)
             // constant number of operations  // => (P)
          }
      }
  }

循环（1）

步数 i得到值n，n/2，n/4，......等到达n/2^k，其中2^k大于n（2^k > n），这样n/2^k = 0，此时你退出循环。

另一种说法是你有步骤1（i = n），步骤2（i = n/2），步骤3（i = n/4），...步骤k - 1（i = n/2^(k-1)），然后你退出循环。这些是k步骤。

现在k的价值是多少？观察n - 1 <= 2^k < n <=> log2(n - 1) <= k < log2(n) <= INT(log2(n - 1)) <= k <= INT(log2(n))。这使得k = INT(log2(n))或松散地说k = log2(n)。

每一步的成本 现在每个步骤有多少次操作？

在步骤i，根据我们选择的符号和属性（P），它是g(i) = g(n)。

循环（2）

步数 你有步骤（1）（j = 1），步骤（2）（j = 2），步骤（3）（j = 4）等，直到你到达步骤（p）（j = 2^p），其中p被定义为2^p > n这样的最小整数，或者松散地说log2(n)。

每一步的成本 根据我们选择的符号和属性（P），步骤j的成本是h(j) = h(n)。

循环（3）

步数 再次，让我们计算步骤：（1）：k = 0，（1）：k = 2，（2）：k = 4，...，k = n - 1 or k = n - 2。这相当于n / 2步骤。

每一步的成本 因为（P），它是恒定的。让我们称之为常数K。

所有循环都是一样的

聚合操作的数量是

T(n) = f(n) = sum(i = 0, i < log2(n), g(i))
            = sum(i = 0, i < log2(n), g(n))
            = log2(n).g(n)
            = log2(n).sum(j = 0, j < log2(n), h(j))
            = log2(n).log2(n).h(n)
            = log2(n).log2(n).(n/2).K

所以T(n) = (K/2).(log2(n))^2.n

Answer 2

写一个方法，添加一个计数器，返回结果：

int nIterator (int n) {
    int counter = 0;
    for( int i = n; i > 0; i /= 2 ) {
        for( int j = 1; j < n; j *= 2 ) {
            for( int k = 0; k < n; k += 2 ) {
                ++counter;
            }
        }
    }
    return counter;
}

快速增加N的协议和以可读方式记录结果：

int old = 0;
for (int i = 0, j=1; i < 18; ++i, j*=2) {
    int res = nIterator (j);
    double quote = (old == 0) ? 0.0 : (res*1.0)/old;
    System.out.printf ("%6d %10d %3f\n", j, res, quote);    
    old=res;
}

结果：

     1          0 0,000000
     2          2 0,000000
     4         12 6,000000
     8         48 4,000000
    16        160 3,333333
    32        480 3,000000
    64       1344 2,800000
   128       3584 2,666667
   256       9216 2,571429
   512      23040 2,500000
  1024      56320 2,444444
  2048     135168 2,400000
  4096     319488 2,363636
  8192     745472 2,333333
 16384    1720320 2,307692
 32768    3932160 2,285714
 65536    8912896 2,266667
131072   20054016 2,250000

因此n增加了2倍，计数器在开始时增加超过2²，但随后迅速减少到某个东西，不会高于2.这应该可以帮助你找到方法。