1 for for循环的最差时间复杂度(Big O)

Question

所以我理解大多数复杂问题; 然而,这让我很困惑.

当for循环中的第二个语句如下(i*i <n)时,循环的Big O是什么？怎么计算？

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

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

Answer 2

i*i<n

可以转化为

i<sqrt(n)

所以它的实际 O(sqrt(n))