我试图找出下面代码块的运行时间 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复杂度运行时间。这个案例有什么意义？
蒂亚。
最佳答案
假设你的 n 是 15，那么你的循环如下 -
1, 3, 9 = 3 次 迭代次数是一个log_3(15)
通常的思考方式是，如果您将输入减半或除以三分之一(或任何分数)并上升到 0，那么它将是您除以的那个因子的对数底数。
如果你减半，它将是 log_2(n)，如果你除以三分之一，它将是 log_3(n) 等等。希望总体思路有所帮助
关于algorithm - 循环迭代分析，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11111706/