循环的时间复杂度

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)？

谢谢

Answer 1

I am aware that loops whose counter gets increased by a constant amount every iteration generally have a complexity of O(sqrt(n))

这是错误的。每次迭代计数器增加一个常数的循环是 O(N)。

一个循环，其计数器增加的量在每次迭代中线性增加是 O(sqrt(N))。

在这种情况下，N 这里是 n * n，因为这就是你的循环要循环到的地方，所以这个简单的替换告诉你，是的，操作是 O(sqrt(n^ 2)) 或 O(n).

Answer 2

I am aware that loops whose counter gets increased by a constant amount every iteration generally have a complexity of 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)

Answer 3

它是 O(n)，因为循环将精确迭代 n 次。

关于交互 1：i 的值将是 1 * 1 - 1 即 0

关于交互 2：i 的值将是 2 * 2 - 1 即 3

关于交互 3：i 的值将是 3 * 3 - 1 即 8

...

在交互 n 上：i 的值将是 n * n - 1。这会导致循环终止。

总而言之，i 增长速度足以在 n 次迭代中达到 n * n - 1。

Time complexity of loop