如何找到下面提到的 Big-O 复杂性

java big-o

2022-09-02 03:21:36

你们能帮助理解以下代码的时间复杂度吗？

int count = 0;
for (int i = N; i > 0; i /= 2) {
    for (int j = 0; j < i; j++) {
        count += 1;
    }
}

我低估了这应该是O（nlogn），但这是错误的。只是为了更新为什么我认为它会是O（nlogn），因为在第一个循环中，我们将i除以2，这意味着我们将它切成两半，所以这将是log n，在内部循环中，我们一直运行它直到i，所以它将是N，所以复杂性将是O（nlogn）提前感谢

答案 1

内部循环很容易 - 每次从0到j.，所以现在我们只需要了解每次迭代中的j是什么。
外循环从N开始，每次切成两半，这意味着第一轮将是N，第二轮是N/2，第三轮是N/4，依此类推。

所以我们有N + N / 2 + N / 4 + N / 8 ....这总结了2N操作。所以复杂度是o（N）

答案 2

正如其他人所指出的，每次外部循环迭代时，内部循环都会执行一半的迭代，从N开始：

N + N/2 + N/4 + N/8 ...

这将持续到除以 0 为止。然而，就上限复杂性而言，考虑无穷大的情况是典型的，这意味着，想象这个系列会继续下去......但是我们可以找到一个收敛值。

在这种特殊情况下，我们发现，提取共同因素，我们剩下：

N * (1 + 1/2 + 1/4 + 1/8 ...)

第一个因素只是N，第二个因子是几何级数，这些项的形式为1/2^n（公式和进一步的解释在这里)

在短期内，第二个因素，无限和，收敛于2。因此，我们总共有2N，就复杂性而言，它相当于N。