大 O N^2 (Log N)

Question

我是 Big O 的新手，对此我有点难过。 我有：

for (int i = 1; i < n*n; i *= 2)

在我看来，这等同于

我说得对吗？还是可以将其简化为 N，因为您将 n*n 的输入加倍并用 i *= 2 减半？

Answer 1

在这种情况下你有

O(log2(n ^ 2))

这是

O(2 * log2(n))

或者只是

O(ln N)

请注意，如果 n * n > (1 << 30) 您将遇到无限循环。