所以，我对 O(log n) 的理解是时间线性增加，而 n 呈指数增加。我试图将这种理解应用到 Interviewbit 的以下函数中:
int a = 0, i = N;
while (i > 0) {
a += i;
i /= 2;
}
我似乎无法理解为什么时间复杂度是 O(log n)。任何人都可以分解这个并解释原因吗？
最佳答案
在此示例中，您需要计算循环迭代次数，因为这些迭代的次数决定了算法所需的总时间。
如i在每次迭代中除以 2，我们有 log N循环的迭代(使用以 2 为底的对数更容易理解，但这并不重要)。
示例:对于 N=64，您有 7 次迭代，第一次迭代 i=64，第二次迭代 i=32，然后是 16,8,4,2,1，最后循环在除 i=1/2 后停止。给出 0(整数算术)。如果将 N 加倍到 128，则有 8 次迭代。如果将 N 再次加倍到 256，则有 9 次迭代。在这里，您可以看到 N 呈指数增长，同时循环迭代次数(即时间)呈线性增长。
关于algorithm - 我如何将我对 O(log N) 的理解应用于这个特定函数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37970486/