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 次迭代结束后循环才会停止。

希望这对您有所帮助!