确定循环的时间复杂度

Question

我希望在确定下面的 while 循环的时间复杂度方面得到一些帮助。我正在尝试解决一个 o(n) 时间复杂度的问题，但不确定这个循环是否满足这个条件。

如果循环不是 o(n) 的时间复杂度，它会是 o(n^2) 吗？

谢谢:)

int a = 0;
int b = a + 1;
while (a < n) {
    b++;
    if (b == n) {
        a++;
        b = a + 1;
    }
}

Answer 1

（我这里假设if分支中的赋值是b = a;而不是b = a + 1;，否则死循环。）

您的算法生成了所有 (a, b) 对 a < n、b < n 和 b > a。正好有 (n - 1) + (n - 2) + ... + 1 对夫妇满足此限制条件。 (n - 1) + (n - 2) + ... + 1 = (n - 1) * (n - 2) / 2 给出了 O(n²).

的复杂性

您可能会被程序中的单个循环误导，这可能会给人一种复杂度为 O(n) 的印象，但您的算法可以重写如下：

int a = 0;
int b;
while (a < n) {
    b = a + 1;
    while (b < n) {
       b ++;
    }
    a++;
}

这样更容易看出复杂度确实是O(n²)。

Answer 2

(n-1) + (n-2) + ... + 1 = n*(n-1)/2

所以你有一个 O(n^2) 循环。

Answer 3

这是 [1, infinity) 范围内所有 n 值的无限循环，因为当 a++ 将导致 a 的值等于 n - 1 ， b 的值将重置为 a + 1 ，这只不过是 n [a + 1 => n - 1 + 1 => n] 并且在下一次迭代中 b 将递增 1 然后，理论上，b == n 永远不会是 true.

I am trying to solve a problem in o(n) time complexity....

如果您能分享一些有关您尝试实施以解决问题的算法的详细信息，那就更好了。

确定循环的时间复杂度

Identifying time complexity for a loop

c

time-complexity

while-loop