algorithm - 如何找到此块的 theta 符号？

Question

该块是：

    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 ^{2 k}。这意味着迭代次数将（大致）对应于 k 的最小值，使得

2 ^{2 k} ≥ n

两边取对数两次，我们得到

2 ^{2 k} ≥ n

2 ^k ≥ 对数₂ n

k ≥ log ₂ log ₂ n

所以循环迭代的次数大致是log ₂ log ₂ n。因此，循环运行 O(log log n) 次。更准确地说，循环运行 Θ(log log n) 次，因为循环在 k 次迭代结束之前不会停止。

希望这可以帮助！