排序算法的证明和运行时间

Question

水文排序是一种排序算法。下面是伪码。

*/A is arrary to sort, i = start index, j = end index */

    Hydrosort(A, i, j):                 // Let T(n) be the time to find where n = j-1+1

      n = j – i + 1                              O(1)
      if (n < 10) {                              O(1)
        sort A[i…j] by insertion-sort            O(n^2) //insertion sort = O(n^2) worst-case
        return                                   O(1)
      }
      m1 = i + 3 * n / 4                         O(1)
      m2 = i + n / 4                             O(1)
      Hydrosort(A, i, m1)                        T(n/2)
      Hydrosort(A, m2, j)                        T(n/2)
      Hydrosort(A, i, m1)                        T(n/2)

T(n) = O(n^2) + 3T(n/2)，因此T(n)是O(n^2)。我用主定理的第三个例子来解决这个递推。

我有两个问题：

1. 我算出了这里最坏的运行时间吗？
2. 如何证明流体排序(A，1，n)正确地排列n个元素的数组A？

Answer 1

我算出了这里最坏的运行时间吗？

恐怕不行。复杂性函数是：

T(n) = 3T(3n/4) + CONST

这是因为：

1. 对于一个大小为3n/4的问题，有三个递归调用
2. 这里的常量修饰符是O(1)，因为所有非递归调用操作都有一个固定大小的限制(具体来说，n<=10的插入排序是O(1))。

如果你继续计算它，你会变得比O(n^2)更复杂

如何证明流体排序(A，1，n)正确地排列n个元素的数组A？

通过归纳。假设您的算法适用于大小n的问题，那么让我们来研究一个大小n+1的问题。对于n+1<10来说，这是微不足道的，因此我们忽略了这种情况。

• 在第一次递归调用之后，可以保证对数组的前3/4进行排序，特别是保证第一个n/4的元素是本部分中最小的元素。这意味着，它们不能在数组的最后n/4中，因为至少有n/2元素大于它们。这意味着，n/4最大元素介于m2和j之间。
• 在第二次递归调用之后，由于保证在n/4最大元素上调用它，它将将这些元素放在数组的末尾。这意味着m1和j之间的部分现在得到了正确的排序。这也意味着，3n/4最小元素介于i和m1之间。
• 第三，递归调用正确地对3n/4元素进行排序，并且n/4最大元素已经就位，因此现在对数组进行排序。