分析这个短代码的时间复杂度

Question

我正在尝试评估这几行代码的运行时复杂性，这是一个冒泡排序代码。现在我知道它是O（n ^ 2），但我想做一个准确的分析。而且我不确定我是否正确

for i ← 1 to n-1
    for j ← n downto i+1
      if A[j-1] > A[j]
          temp ← A[j-1]
          A[j-1] ← A[j]
          A[j] ← temp

我做的是：第一行执行n次，所以（c1）* n第二行依赖于i，但它将是n，然后是n-1，...，1，这就是我的问题所在，应该我使用求和而不是？似乎很奇怪运行时依赖于我的第三行也依赖于我们得到的数组，并且下一行依赖于此。

有人可以帮助进行适当的分析吗？谢谢你。

Answer 1

对于i的每个值，代码执行许多依赖于i的操作，比如c(i)。所以操作的总量将是

total := sum_{i=1}^{n-1} c(i)

现在让我们为一般的c(i)计算i。在最坏的情况下，if语句的真正分支总是被执行并且例如C操作，这是一个独立于j，i和n的数量。所以

c(i) <= sum_{j=n}^{i+1} C
      = C*(n - (i+1) + 1)
      = C*(n - i)

从而

total <= sum_{i=1}^{n-1} C*(n-i)
       = C * sum_{i=1}{n-1} (n-i)
       = C * n(n-1)/2
       = O(n^2)

请注意，在最好的情况下，if的真正分支将永远不会发生，您只需要计算计算不等式所需的操作数，例如D。因此，您可以重复与C和D用<=替换>=之前相同的计算

total >= O(n^2)