如果一个内部循环通过对变量求平方而递增，那么它的运行时间是什么?如何

Question

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

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

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

因此，如果Theta(n log(log(n)))。