快速排序时间复杂度分析

目录

快速排序是非常经典和实用的算法,也是学习算法复杂度分析的一个很好的入门例子,下面我们就分析一下这个算法的时间复杂度。

算法复杂度

   算法复杂度的定义网上到处都可以搜索得到,但是我这里给出一个自己的理解,算法复杂度=每次处理数据规模*迭代次数。
举例说,比如有 n 个数据,你的算法只需要对这个数据进行 1 次处理这个算法复杂度就是 n,如果需要进行 2 次处理就是 2n。
但是往往我们只需要关注算法随着规模的增长度所以可以忽略掉复杂度中的常数。
   我们对任何一个算法的优化都可以从两方面入手:1.减少每次处理数据的规模。2.减少迭代的次数。

quicksort_time_complexity_analysis_1.png

分治法

  上面提到了优化算法的两种途径,那么分治法就是通过减少迭代次数来达到优化算法的目的。任何算法问题只要能通过分治法处理,那么就可能可以减少处理问题所需的迭代次数。
  简单的说分治法就是把一个问题分解为 n 个规模更小的类似(类似是指处理的复杂度相同或更小)的问题。如果分治法是把问题每次分解为 2 个规模更小的问题,那么对于规模为 n 的数据,只需要 lg(n)次迭代就可以处理完。快速排序就是经典的利用分治法优化的算法。

快排时间复杂度分析

算法过程

1. 从 n 个元素中选出一个元素 k。
2. 把小于 k 的元素放在 k 的左边,把大于 k 的元素放在 k 的右边。
3. 对 k 左边和右边的元素进行相同的操作。

最坏情况

  如果我们每次都选择的是 n 个元素中最大的那个元素,那么这个就是最坏的情况。
迭代次数 处理数据
1 n
2 n-1
3 n-2
n 1
  很明显这时我们的算法复杂度是 n + (n-1) + (n-2) + ... + 1 = O(n^2)

最好情况

  最好的情况是我们每次选的数恰好是 n 个元素的中位数,把 n 分成两半处理。
迭代次数 处理数据
1 n
2 n
3 n
lg(n) n
  这时的算法复杂度就是 n*lg(n)

平均情况

  平均情况我还没弄明白,以后补上 

目录