loops - 有趣的嵌套循环的大哦 - 如何计算它？

Question

我知道关于 Big Oh 符号有很多类似的问题，但是这个例子很有趣，而且不是微不足道的：

int sum = 0;
for (int i = 1; i <= N; i = i*2)
    for (int j = 0; j < i; j++)
        sum++;

外循环将迭代 lg(N) 次，但是内循环呢？所有操作的 T(N) 是多少？我只能看到 3 个可能性：

我的意见 - T(N) = N - 但这只是我从 sum 变量的观察值得出的直觉，当 N 被多次相乘时 - sum 几乎等于 2N，这给了我们 N。

基本上我不知道怎么算。请帮助我完成这项任务并解释解决方案 - 这对我来说非常重要。

谢谢

score 0 · Accepted Answer

内部循环迭代最后一次最大值。N. 在最后一次运行之前，它迭代 N/2。如果你把它加起来 N + N/2 + N/4 + N/8 这加起来是 2*N。这就是你计算所有运行的全部内容。T(N) = N

1 回答 1