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

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

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

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。这应该能帮你找到路。

Answer 2

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

我们可以做的一个关键观察是：

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

我们打电话吧

>

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)
        }
    }
}

步骤数
i获取值n，n/2，n/4。。。等等，直到达到n/2^k，其中2^k大于n（2^k

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

现在k的值是多少？观察n-1

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

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

步骤数
你有步骤（1）（j=1）、步骤（2）（j=2）、步骤（3）（j=4）等，直到你到达步骤（p）（j=2^p）其中p被定义为最小的整数，这样2^p

每个步骤的代价
根据我们选择的符号和属性（P），步骤j的代价是h（j）=h（n）。

步骤数再次，让我们计算步骤：（1）：k=0，（1）：k=2，（2）：k=4<代码>k=n-1或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