算法公开课 1 课程简介及插入排序算法分析

2019-09-27

视频来自B站，以下笔记记录视频学习点及不懂点。原创By bellaSun

---

1. Insertion Sort ：short， 插入排序

Math : 数学解析

---

Merge sort  A[1...n]

 1.If n=1 ,done  -----------Theta(1) 

 2.Recursively sort A[1....[1/n] ] and A[ [n/2] +1 ...+n] -----------2T(n/2) 

3.Merge subroutine 归并子程序    -------Theta(n)

Key subroutine -Merge :

Time = theta(n) on n total time 

Recursion tree 递归树方法：