n 个数字数组的插入排序的时间复杂度，以及附加信息

Question

设一个由n个数字组成的数组A。 让我们定义一个反转：有两个索引，i < j, such that A[i] > A[j]。 如果我的数组 A 有 K 次反转，那么用插入排序对数组进行排序的时间复杂度是多少？

我知道反转越少，我们的数组就越接近其排序数组。如果只有一个反转，则意味着只有 2 个元素未排序（如果有更多，那么我们会有更多反转）。但是，我不确定如何分析一般情况。 如果有任何提示，我将不胜感激。

Answer 1

下面提供的插入代码也注明了其操作次数，计算的是数组 A 与排序完全相反的最坏情况。在每种情况下都需要交换数组 A 的所有元素。

for ( i = 1 ; i < n ; i++ )                     // 1(initialization) + n(check)
{
     j = i;                                     // n-1(initialization)
     while ( ( j > 0 ) && ( A[j-1] > A[j] ) )   // 2(∑ᵢ₌₁^{n} i) - 1 (checks)
     {
          temp = A[j];                          // ∑ᵢ₌₁^{n-1} i (operation)
          A[j] = A[j-1];                        // ∑ᵢ₌₁^{n-1} i (operation)
          A[j-1] = temp;                        // ∑ᵢ₌₁^{n-1} i (operation)
          j = j – 1;                            // ∑ᵢ₌₁^{n-1} i (operation)
     }
}                                               // n-1(incrementation)

注意到 Σᵢ₌₁^{n} i 表示从 1 开始的 n 个自然数之和。

Σᵢ₌₁^{n} i = n(n+1)/2

操作次数（最坏情况）

= 1 + n + (n-1) + 2(n(n+1)/2) - 1 + 4(n(n-1)/2) + (n-1)

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

= 2n + n^2 + n - 1 + 2n^2 + n -1

= 3n^2 + 2n - 2

最坏情况的运算次数为 f(n) = 3n^2 + 2n - 2。通常，我们考虑最好情况（数组完美排序）、最坏情况和平均情况（（最坏 + 最好）/ 2 ).

分析算法复杂度的另一种方法是渐近符号。在这种情况下，f(n) = O(n^2) 的上限。