排序/查找模型及其最优时间复杂度,stable分析

排序/排序模型

• 比较模型

  • 二分查找
    • T(N) = O(lgN)
  • insertion sort
    • T(N) = O(N^2)
    • stable = true,在排序的过程中相同的元素彼此不回调换位置
  • merge sort
    • T(N) = O(N*lgN)
    • stable = true/false,取决于当left == right的时候是先归并left还是right
  • heap sort
    • T(N) = O(N*lgN)
    • stable = true/false,取决于从extract的时候是将元素放在数组最后还是另外用一个数组存储
    • https://www.geeksforgeeks.org/stability-in-sorting-algorithms/
    • https://stackoverflow.com/questions/31805235/why-heap-sort-is-not-considered-as-a-stable-sorting-algorithm?lq=1

• 比较查找模型的最优时间复杂度为Omega(lgN),原因:

  • 比较查找模型就像一颗决策树(比如二分查找),每次比较的时间复杂度都是O(1),结果都是树上的叶子结点,那么执行比较的次数就是树的根节点到叶子结点的路径长度,就是lgN

• 比较排序模型的最优时间复杂度为Omega(N * lgN),原因:

  • 把比较排序模型看成一颗决策树，结果同样存储在叶子结点上，所有叶子结点的数量(可能的比较结果)其实是N的排列组合(采用这种模型必须将给出数组中的元素两两全部比较,虽然可以用数学的传递性优化掉一部分,但是in general)=N!,则跟节点->叶子结点的路径长度=lgN!,根据Stirling公式可以推算出Omega(N * lgN)

• RAM模型

  • counting sort
    • T(N) = O(N + K)
    • stable = true
  • radix sort
    • T(N) = O(N)
    • stable = true