MIT 算法导论

算法课程分为

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 伪代码

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]

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左右之和，归并排序比插入排序要快