确定时间复杂度

Question

给定数组 A 的以下伪代码

x = 0
  for i = 0 to n - 1
    for j = i to n - 1
       if A[i] > A[j]:
          x = x + 1
  return x

如何确定运行时间？ 我会说它是 (n - 1)*(n - 1) = n^2 - 2n - 1 = O(n^2).

虽然我不太确定如何使用 if 循环。

Answer 1

是的O(n^2)，只是对内循环的迭代次数求和：

n + (n - 1) + (n - 2) + ... 1 = [ n x (n + 1) ] / 2

而且if不是循环，是控制结构。通常你只计算条件被检查的次数而不考虑条件。如果 if 主体中有另一个循环，则该条件可能很重要。

如何计算内循环的迭代次数：

• 当i = 0内循环运行n次，然后结束
• 然后 i = 1 内部循环运行 n - 1 次，然后结束
• 然后 i = 2 内部循环运行 n - 2 次，然后结束
• .....
• 当 i = n - 2 内循环运行 1 次时
• 当 i = n - 1 内循环运行 0 次时

所以我们需要做的就是加上内循环的迭代次数：

n + (n - 1) + (n - 2) + ... 1 = [ n x (n + 1) ] / 2

Answer 2

实际上，说 "this algorithm has a O(n^2)time complexity" 暗示它是 最坏情况 的复杂性。

用一种天真的方式，你可以只计算每条指令在最坏情况下执行的次数。 if A[i] > A[j]: 也可能被视为指令，因此您不必首先问自己条件何时为真。

2*(n-1)*(n-1)是最内层循环中执行的指令数的一个主要部分，更准确地说：

2(n + (n-1) + ... + 1) = n(n+1) = O(n^2)

即使 O 符号不重要，也有几个数组的条件始终为真（因此这些是该算法的最坏情况）。例如：

n n-1 n-2 ... 2 1

Answer 3

@perreal 的顺序完全正确：

n*(n+1)/2 => O(n^2)

关于 "if" 部分，这并不重要。 （我写这个是为了回答这部分）

假设检查 if 需要 c1 时间，而执行 x=x+1 需要 c2 时间。你将拥有

(c1 | c1+c2)* n*(n+1)/2 

并且由于您可以忽略订单中的常量，因此它来自

O(n^2)