首页 > 代码库 > 分治算法

分治算法

1、折半搜索算法

(1)算法代码:

(2)复杂性分析

 任何一种以比较为基础的搜索算法, 在最坏情况下所用的时间都不可能低于 (log ) n  ,因此,也就不可能存在最坏情况下所需时间比折半搜索数量级还低的算法。
 

2、排序问题

2.1归并排序算法
(1)归并排序算法思想
该算法采用分治方法, 将要排序的数组分成两部分, 先对每部分进行排序,然后将两部分的元素按不降顺序放在一个新数组中。这一过程可能需要多次分解和合并,因此是一个递归过程。
(2)合并两个有序组

(3)归并排序主程序


 该算法的最好、 最坏和平均时间复杂性都是 双界nlog n。

2.2 快速排序算法
(1)划分程序
(2)算法主程序

(3)复杂性分析
  

 快速排序与归并排序具有相同的平均时间复杂性。但实际表现有所不同,快速排序一般要比归并排序用时少。
注: 在快速排序中, 如果划分元素是随机选取的, 则几乎可以保证不会出现最坏情况,几乎都在平均时间内完成。 

几种排序算法的时间复杂性比较



分治算法