MIT算法导论

写在前面

学习《算法导论》是导师留给我的第一个任务,磨磨蹭蹭躺尸了国庆假期后才开始慢慢进入学习状态。按照知乎高赞回答的建议,准备首先学习 MIT算法导论课程 ,之后边刷leetcode边翻阅《算法导论》积累更多算法知识。
本文记录了 MIT算法导论 课程上的一些知识点与想法。

Lesson 1 - 课程简介及算法分析

算法课程分为

  • 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
2
3
4
5
6
7
8
INSERTION-SORT(A, n) //Sort A[1...n]
for j <- 2 to n
do key <- A[j]
i <- j-1
while i > 0 and A[i]>key
do A[i+1] <- A[i]
i <- i-1
A[i+1] <- key

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]

  1. If n=1, done
  2. Recursively sort A[1..n/2(上界)] and A[n/2(上界)+1..n]
  3. 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左右之和,归并排序比插入排序要快