需要解释算法的时间复杂性解决方案

Question

我的软件工程类介绍刚刚达到时间复杂度并学习如何分析某些算法。我很难看到他们如何得到解决方案，并希望有人能够解释它，希望有一些合理的证据？

void foo(int N) { 
    int k = 1; 
    while (k < N * N) { 
     k = k * 2; 
    } 
} 

他们的解决方案是，这个功能的大澳是O（logN）的 [我明白这里提到日志基地2]

我试图通过思考来解决这个多少次会通过将随机值分配给N进行迭代，我无法找到模式，有什么帮助？

Answer 1

k每次增加因子2的事实是使得算法logN的原因。实际上，它是log(N^2)，但使用对数属性我们可以将其简化为2log(N)，然后通过将极限作为N接近无穷大以获得log(N)来删除2。

因此，时间复杂度为O(logN)。

编辑：此外，可以看出，k开始于1和程序结束时k大于或等于N * N。如果我们采用log(N^2)，我们将知道程序将运行多少次迭代。在这样做的情况下，我们也可以通过获取log(N^2)的上限来确定k的结束值。

编辑：一个例子是N = 10：N的正方形是100。因此，k将增加，直到两个以上的幂或等于100，即128。

Answer 2

使用你的高中代数。在p迭代之后，k的值是2^p。 （这很容易检查。）当k >= N^2时，循环将停止执行。代替，循环停止时

2^p >= N^2 

现在解决：

log_2(2^p) >= log(N^2) 
p >= 2 log(N) 

所以循环将在非常接近2 log(N)迭代停止。这是O（log（N））。

只有在操作数大小存在固定限制的情况下，您可能需要指出乘法是恒定时间才能完成任务。没有这样的限制，问题也取决于乘法的渐近行为。

顺便说一下，O（log N）对于所有对数底数都是相同的。 base只是通过一个常数来改变日志的值，big-O忽略了常量因素。