algorithm - 如何找到该 block 的 theta 表示法？

Question

该 block 是:

    i=2  
    while(i<n){  
        i=i*i;  
        x=x+1;  
    }  

我需要找到 x=x+1 执行次数的 theta 表示法。我创建了一个包含一些示例值的表，但我不知道如何从那里继续。这是我的示例值:

(n) - (# times looped)  
  3 - 1  
  5 - 2  
 20 - 3  
400 - 4

Answer 1

考虑这个问题的一种方法是跟踪循环中 i 的值。在第一次迭代之前，该值为 2 = 2¹。第二次迭代后，结果为 4 = 2²。第三次迭代后，结果为 16 = 2⁴。第四次迭代后，结果为 256 = 2⁸。第五次之后，为 65,536 = 2¹⁶。

如您所见，经过 k 次循环迭代后，i 的值为 2^2k。这意味着迭代次数将(大致)对应于 k 的最低值，使得

2^2k ≥ n

两边取对数两次，得

2^2k ≥ n

2^k ≥ log₂ n

k ≥ log₂ log₂ n

因此循环迭代次数大致为 log₂ log₂ n。因此，循环运行 O(log log n) 次。更准确地说，循环运行 θ(log log n) 次，因为循环直到 k 次迭代结束后才会停止。

希望这有帮助!