MIT 算法导论

Posted on | In |

算法课程分为

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