algorithm - 如果通过对变量进行平方来增加内部循环，它的运行时间将是多少以及如何？

Question

假设这里的 n 是小于 256 的任何数字，则内循环将 4 次为真，现在随着 n 的增加，内循环遵循什么样的序列。

for ( int i=1; i<=n; i++){
    for ( int j=2;j<=n; j=j*j){

    }
}

标签： algorithmtime-complexityruntime

Answer 1

外部循环将被迭代n次数。内部循环每次都将前一个值平方，即2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k}. 因此，时间复杂度为n * k。为了计算k，我们需要找到k这样的n = 2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k}：

2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k} = sum_{t=0}^{k} 2^{2^t} = n 
=>  k = \theta(log(log(n)) 

因此，时间复杂度 if Theta(n log(log(n)))。