algorithm - 循环迭代分析

Question

我正在尝试找到以下代码块的运行时间 O(n)：

int z=0;
int x=0; 
for (int i=1; i<=n; i=i*3){ //runs from 1->n, 1, 3, 9, 27... <- fcn that defines this?
   //constant running times below
   z = z+5;
   z++;
   x = 2*x;
}

如果是 i=i*2，那么就是 logn 复杂度运行时间。这个案子有什么用？

蒂亚。

Answer 1

假设你的 n 是 15，这种情况下你的循环如下 -

1, 3, 9 = 3次迭代次数为log_3 (15)

一般来说，考虑它的方法是，如果您将输入减半或除以三分之一（或任何分数）并达到 0，那么它将是您除以该因子的对数基数。

如果减半，则为 log_2(n)，如果除以三分之一，则为 log_3(n)，依此类推。希望总体思路有所帮助

Answer 2

请注意 log_3 (n) = log_2 (n) / log_2 (3) 。这里 log_2 表示以 2 为底的对数，log_3 表示以 3 为底的对数。因此，log_2(n) 只是 log_3(n) 乘以一个常数。

因此，根据大 O 定义，任何运行时间为 O(log_3(n)) 的代码也是 O(log(n))。