递归树以及时间复杂度
在数据结构中我们经常被问到某某排序算法的时间复杂度是多少，虽然我们能答的上来时间复杂度是多少。但是却不明白这个时间复杂度是怎么得到的，下面就让我们来搞清楚时间复杂度的由来！（我们以归并算法为例来说明）
1.什么是归并排序？
归并排序（Merge Sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。
归并操作（Merge），也叫归并算法，指的是将两个已排好序的序列合并成一个序列的操作。归并算法依赖归并操作。归并排序有多路归并排序、两路归并排序，可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。算法的主要思想：
- 1、把n个记录看成n个长度为
1的有序子表；
- 2、进行两两归并是记录关键字有序，得到
n/2个长度为2的有序子表；
- 3、重复第2步直到所有记录归并成一个长度为n的有序表为止。
现在下面图描述了数组序列为[7,9,8]，然后就是将这个数组分为两个数组子序列合并为一个有序的数组序列。
文章图片
image.png
文章图片
image.png 归并算法代码如下：
package com.zhoujian.solutions.dataStructure.sort;
/**
* @author zhoujian123@hotmail.com 2018/5/7 10:08
* 归并排序的算法思想：它是将待排列的元素分成大小大致相同的两个子集合，并分别对两个子集合排序，然后将排好的子集合合并。
* https://www.geeksforgeeks.org/merge-sort/
* 空间复杂度：O(n)
* 稳定：是的
* 时间复杂度： O(nlogn)
* 根据递推式画出递推公式
* T（n）= 2T（n / 2）+ C(n)
*
*/
public class MergeSort {
/**
* merge()的功能是将前后相邻的两个有序表归并为一个有序表的算法。
*/
void merge(int arr[],int low,int mid,int high){
int[] temp = new int[arr.length+1];
//将arr中的数据复制到temp，比较temp中的值，最后将比较后的序列复制到arr中
for (int k=low;
k <=high;
k++) {
temp[k]=arr[k];
}
int i,j,k;
//两个序列开始排序
for (i=low,j=mid+1,k=i;
i<=mid&&j<=high;
k++){
if (temp[i] <=temp[j]){
arr[k]=temp[i++];
}else {
arr[k]=temp[j++];
}
}
//当两个序列中的一个比较完了之后，另外一个直接复制到arr的结尾处
while (i<=mid) arr[k++]=temp[i++];
//当第一个表未检测完
while (j<=high) arr[k++]=temp[j++];
//当第二个表未检测完
}/**
* 采用2路归并排序
*/
void mergeSort(int arr[],int low,int high ){
if (low
文章图片
image.png 2.递推式是如何产生的？
我们来仔细分析一下归并算法，我们会注意到运行一个大小为n的数组的时间复杂度计算过程如下：
- 第一步，计算n需要花
O(1)；
- 第二步，我们做了两个递归归并排序，两个数组的长度为：
?(n ? 1)/2? and ?(n ? 1)/2?；
- 最后，我们调用
Merge算法，遍历两个子序列，然后分别增加i和j，这个过程需要花费的时间为O(n)。
通过上面的分析可以知道：
文章图片
image.png T(?(n ? 1)/2?) + T(?(n ? 1)/2?)代表是的归并过程的时间复杂度，Θ(n)代表排序过程中时间复杂度。
可以将上面的式子简化为下面的表达式：
文章图片
image.png 然后我们来关注这个式子就可以了。
3.通过递推式计算时间复杂度
第一次递归划分：
文章图片
img 第二次递归划分：
文章图片
img 第三次递归划分：
文章图片
img 第n次递归划分：
文章图片
img 这棵树的高度为：
2^t=n===>t=log2(n)
每层所花费是时间为cn，总的时间cn * lgn + θ(n) ，计算时间复杂度可以将c和θ(n)忽略，所以归并排序的时间复杂度为O(nlgn)
参考资料
https://www.hackerearth.com/zh/practice/algorithms/sorting/merge-sort/tutorial/
https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/analysis-of-merge-sort
http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L08-AnalysisMergeSort.htm
【递归树以及时间复杂度】http://www-bcf.usc.edu/~dkempe/CS104/11-07.pdf
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- java中如何实现重建二叉树
- 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
- 种树郭橐驼传（文言句式+古今异义+词类活用+通假字）
- 白杨树
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会
- ［原创］能见沂山一棵树，胜读十年无用书！
- 涵养字外功
- 2018.07.07《刺杀骑士团长》村上春树
- 二叉树路径节点关键值和等于目标值（LeetCode--112&LeetCode--113）