为什么这段代码的大 O 表示法不是 log(log(n))

Question

明天我们有期中考试，我们不能解决这段代码的大O符号：

for(int i =1; i<n;i=i*2)
{
   for(int j=1; j<i; j = j*2)
   {
     cout << "hello";
   }
} 

我们认为它可以是“log(log(n))”，但事实并非如此。

Answer 1

如果我们做一个图形table，我们可以看到答案是O(n^2):

Answer 2

这个循环：

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

将在 1、2、4、8、... 中以 i 执行其主体，直到（但不包括）i = n。所以它将执行它的主体 O(log n) 次。

这个循环：

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

将在 1、2、4、8、... 中以 j 执行其主体，直到（但不包括）i = j。所以它会执行它的主体 O(log(j)) 次。因为 j < n, O(log j) < O(log n), 所以我们也可以说 j 循环是 O(log n).

我们已经确定 i 循环执行了 j 循环的 O(log n) 次执行，而 j 循环执行了 O(log n) 执行其主体。因此，我们乘以因子得到 O(log n) * O(log n) = O(log n * log n) = O(log² n) j循环体。

注意log² n是数学家的写法(log n)²。 与log log n不同。