algorithm - 当我无穷大接近零时循环结束？

Question

所以我想知道下面这个问题的时间复杂度。正确的解决方案是 O(logN)；如果此循环终止，我会理解这一点。但是因为我们只有一半，所以理论上 i 可以非常接近 0，但永远不会结束？!

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

Answer 1

重要的是要记住，您是在除以 int，而不是浮点值，因此没有小数部分。相反，任何剩余部分都将被简单地丢弃。所以一旦你降到 1，一半是 0.5，因为你只取整数部分，你将得到 0。因此，这最终会结束。

例如，如果您从 10 开始:

10/2 是 5

5/2是2加上1的余数——余数被丢弃——i是2

2/2 是 1

1/2是0加上1的余数——余数被丢弃——i是0