循环的时间复杂度

Question

我不确定下面这段C代码的复杂性：

int i = 0, j = 1;
for ( i = 0; i < n * n; i += j )
{
    O1();
    j += 2;
}

O1是一个显然需要恒定时间执行的函数。我知道，循环计数器每次迭代增加一个常量的循环通常具有复杂度为O(sqrt(n))，但这里也是这种情况吗？还是O(sqrt(n^2))，即O(n)？

谢谢

- w.kovacs

---

你的变量i遵循算术级数：https://zh.wikipedia.org/wiki/等差数列 - vdolez

实际上，这是一个等差数列或二次序列。 - Ian Abbott

Answer 1

我知道每次迭代计数器都会增加一个常量的循环通常具有O(sqrt(n))的复杂度，但这是错误的。每次迭代计数器增加一个常量的循环是O(N)。计数器按每次迭代线性增加的循环为O(sqrt(N))。在这种情况下，N等于n * n，因为这是你的循环循环到的位置，所以简单地替换告诉你，是的，操作是O(sqrt(n^2))或O(n)。

- Servy

---

谢谢您的更正和确认我的猜想。如果计数器呈几何级数增加会怎么样？ - w.kovacs

请包含证明！i = S(n) = n*(n+1) / 2 - vdolez

@w.kovacs 那么你执行的操作次数就是一个反比几何数。 - Servy

@Servy 你如何用大O符号表示这个？ - w.kovacs

@w.kovacs 那就是对数。 - Servy

Answer 2

我知道每次迭代计数器增加固定值的循环通常具有O(sqrt(n))的复杂度。 不对！这个说法不正确。例如考虑以下循环：

for(i = 0; i < n; i++)

变量i的值每次增加一个常数，即1。但是循环的复杂度为O(n)。

---

如果你仔细观察这个序列，会发现值i所得到的是：

0, 3, 8, 15, 24, 35, ...

这是一个等差数列。它还可以写成

0^2 - 1, 1^2 - 1, 2^2 - 1, 3^2 - 1, 4^2 - 1, 5^2 - 1, 6^2 - 1, ...

---

现在循环将一直运行，直到i达到n^2，（i < n*n）

因此，您可以推断出循环将运行O(n)次。

因此，复杂度为O(n)

- Haris

Answer 3

这是O(n)的，因为循环将恰好迭代n次。

在第一次迭代中：i的值将为1 * 1 - 1，即0

在第二次迭代中：i的值将为2 * 2 - 1，即3

在第三次迭代中：i的值将为3 * 3 - 1，即8

...

在第n次迭代中：i的值将为n * n - 1。这导致循环终止。

总之，i增长得足够快，可以在n次迭代中达到n * n - 1。

- Yacoub Massad

---

它不会恰好迭代n次。它是O(n)，但有一个系数在那里。 - Servy

@Servy，它将精确迭代n次，您可以验证。 - Yacoub Massad