算法课程分为
- Analysis of Algorithms
- Design of Algorithms
算法分析是理论研究(The theoretical study of computer program performance and resource usage)
我们关注 Performance
Q1:软件领域什么比 Performance 更重要呢?
Correctness, Maintainability, Features, Functionality, Modularity, Security, Scalability, User-friendliness…
Q2:这么多比 Performance 重要的内容为什么我们还关注 Performance?
- 通常,性能的好坏直接决定着是否可行
- 算法是一种描述程序行为的语言,他就像钱一样,需要性能作为支付其他东西的“货币”(例如为了 Functionality 愿意牺牲2倍性能),这决定了 Performance 是处于最底层的,他是衡量一般性的标准
- 这里充满了乐趣,速度总是让人激动
Insertion Sort 插入排序
Pseudocode 伪代码
1 | INSERTION-SORT(A, n) //Sort A[1...n] |
Running Time 运行时间
取决于“输入本身(是否有序)”和“输入规模”
将时间T与输入规模n函数化关联
Worst-case(usually)
运行时间的上界:是对用户的一个承诺T(n) = max time on any input of size n
Average-case(sometimes)
T(n) = expected time over all inputs of size n
expectation: 数学概念: 每种输入的运行时间乘以那种输入出现的概率(这里假设每种输入情形出现的概率是等可能性的,均匀分布)
Best-case(bogus 假象(没啥用))
Cheat~
Q3:插入排序的运行时间分析?
运行时间与机器有关
- relative speed(on same machine)
- absolute speed(on diff machine)
引出了算法的大局观
BIG IDEA
Asymptotic Analysis
- Ignore machine dependant constants
- Look at growth of T(n) as n -> ♾
渐进分析
- 忽略掉依赖于机器的常量
- 不是去检查实际的运行时间,而是关注运行时间的增长
渐进符号
θ-notation: drop lowerder terms, ignore leading constants
Ex: 3n3-90n2-5n+6046 = θ(n3)
算法分析要求我们既有对待数学的严谨,又有对待工程那样富有直觉
渐进符号可以满足我们对相对速度和绝对速度的要求,随着n的增大,渐进结果一般而言不会改变
从工程的角度还有一件事情需要处理,就是有时候需要n足够大某个算法的优势才可以被显现,这时我们经常会使用一些低速算法,在合理的范围内满足我们对速度的要求。因此,我们就必须在我们的数学理解和工程直觉之间做好平衡。
插入排序的Worst-case T(n): θ(n2)
Merge Sort 归并排序
Merge sort A[1..n]
- If n=1, done
- Recursively sort A[1..n/2(上界)] and A[n/2(上界)+1..n]
- Merge 2 sorted lists
我们会用到一个归并子程序 Key subroutine-Merge
T(n) = θ(1) if n = 1 (通常省略)
= 2T(n/2) + θ(n) if n > 1
Recursion tree: T(n) = 2T(n/2) + cn (const c > 0)
使用递归树分析,归并排序的时间复杂度T(n)=θ(nlgn)
树的高度是lgn,叶节点层之和为θ(n),其他层每层为cn
在n大于30左右之和,归并排序比插入排序要快