algorithm - 我如何将我对 O(log N) 的理解应用到这个特定函数中？

Question

所以，我对 O(log n) 的理解是时间线性增加，而 n 呈指数增加。我正在尝试将这种理解应用于 interviewbit 的以下功能:

int a = 0, i = N;
    while (i > 0) {
        a += i;
        i /= 2;
    }

我似乎无法理解为什么时间复杂度是 O(log n)。任何人都可以对此进行分解并解释原因吗？

Answer 1

在此示例中，您需要计算循环迭代次数，因为这些迭代次数决定了算法所需的总时间。

由于 i 在每次迭代中除以 2，我们有 log N 循环迭代(使用 log base 2 更容易理解，但这实际上并不事)。

示例:对于 N=64，您有 7 次迭代，第一次使用 i=64，第二次使用 i=32，然后是 16、8、4、2、1，最后循环在 i= 1/2 给出 0(整数算术)。如果将 N 加倍到 128，则有 8 次迭代。如果将 N 再次加倍到 256，则有 9 次迭代。在这里，您可以看到 N 呈指数增长，而循环迭代次数(即时间)呈线性增长。