一个for循环的最坏时间复杂度（大O表示法）为什么？

Question

我理解大多数复杂性问题，但这个问题让我感到困惑。

当for循环中的第二个语句是如下形式时（i * i < n），那么循环的大O值会是什么？该如何计算？

for ( i = 1 ; i * i < n ; i++)

- mbksr

Answer 1

假设n是输入大小的代理（并且您的代码将仅为可处理的每个成员执行一次循环体，并且没有其他输入元素选择器逻辑）。

i * i < n
  i^2 < n
    i < Sqrt(n)

因此，时间复杂度为O(Floor(Sqrt(n)))。

让我们以n = 10为例（表格显示了在每次迭代结束时变量的状态，在评估i++并执行i * i < n测试之前的确切时刻）。

Iteration,   i,   i * i,  n
        1,   1,       1, 10
        2,   2,       4, 10
        3,   3,       9, 10
        4,   4,      16, 10 -- 16 > 10, abort loop
        5,   5,      25, 10 -- for illustrative purposes

（注意，由于在循环执行之前进行 i ^ 2＜10 检查，因此不会执行第4次迭代，因此循环将执行3次。 10的确切平方根为3.1622 ...，但迭代计数是基于0的自然数，因此请使用Floor 。）

- Dai

---

很好的解释了 i * i < n 如何等同于 i < sqrt(n)。 - Nick Zuber

Answer 2

i*i<n

可以转换为

i<sqrt(n)

所以它实际上是O(sqrt(n))。

- h8red

---

哦，我从未遇到过那种形式，只有各种指数的O(n)，O(logn)或(n logn)，当然还有常数。所以它真的可以写成"O(√n)"吗？这是一种被接受的"语法"吗？ - mbksr

@mbksr 正确。在 O() 中可以使用任何代数表达式（和符号）。请注意，O() 不一定是 n 的函数，例如，如果您正在处理一个二维数组（在这种情况下，它是宽度和高度的函数 m 和 n）。 - Dai

@mbksr O() 可以与任何类型的函数一起使用。它只是一种表达两个函数增长之间关系的方式：关于符号的维基百科文章。 - h8red