java - 基本算法的复杂性？

Question

我有这个示例算法:

int sum = 0;
int j = 1;
while (j <= n) {
    sum++;
    j = j * 2;
}

我正在读的书《Building Java Programs - a Back to the Basics Approach》告诉我，我需要找到这个:

以 n 为单位估算以下代码片段的运行时间:以 O(N^2) 等格式写下您的答案或O(N log N) 。

我似乎不明白如何从a点到达b点。我想出了两个语句= O(2) ，以及包含两个语句的循环 = O(2N)所以应该是O(2N + 2) 。我哪里出错了？

Answer 1

在确定复杂性时，我们不包括常数或系数。它应该是 O(n)，而不是 O(2N + 2)。我们只关心指数数字，即 2^n 或 n^2、log2(n) 等。

抛开这一点，你确定这是 O(n) 吗？ O(n) 意味着它运行 n 次，但看起来 j 会在 n 之前 catch n 次。明白我在说什么吗？

编辑:好的，这就是发生的事情。

看看 j 会发生什么。 j = j * 2。 j 每次都会加倍。换句话说，j 和 n 之间的差异减半。当每次迭代时剩余迭代次数减半时，这称为 log(n) 算法。 log(n) 算法非常出色，因为即使 n 非常大，log(n) 却出人意料地小。代入一些数字就可以明白我的意思。