algorithm - 确定时间复杂度

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