《数据结构 上》一共六章,41小节,一天一节,再给20天缓冲,大概两个月可以看完。不着急,慢慢来。
  • 计算机科学--计算科学
  • 绳索计算机:十二等分绳索求直角,这里的计算机是绳索。
  • 尺规计算机:三等分一条线段,相似三角形,这里的计算机是尺规。

算法

  • 计算 = 信息处理

借助某种工具,遵照一定规则,以明确而机械的形式进行

  • 计算模型 = 计算机 = 信息处理工具

  • 所谓算法,即特定计算模型下,旨在解决特定问题的指令序列

    输入
    输出
    正确性: 的确可以解决指定的问题
    确定性: 任一算法都可以描述为一个由基本操作组成的序列
    可行性: 每一基本操作都可实现,且在常数时间内完成
    有穷性

算法:有穷性

                {1}  n<=1
Hailstone(n)   {n} U Hailstone(n/2)  n偶
                {n} U Hailstone(3n+1) n奇

注: Hailstone 冰雹
int hailstone(int n) {
    int length = 1;
    while(1<n) {
               (n%2) ? n = 3*n+1 : n/=2; length++;
    }
    return length;
}

对于任意的n,总有|Hailstone(n)| < oo ?
结论待定->程序未必是一个算法,死循环或者栈溢出。
关注点:如何设计、优化算法? 如何评判、比较?

好算法

正确性:能处理简单、大规模、一般性、退化、任意合法的输入
健壮性:能辨别不合法的输入并适当处理,而不导致非正常退出
可读性:结构化+准确命名+注释+...
效率:速度尽可能快;存储空间尽可能少;

Algorithms + Data Structures = Programs // N. Wirth, 1976
(Algorithms + Data Structures) × Efficiency = Computation // Deng

性能测度

To measure is to know.
If you can not measure it, you can not improve it.
- Lord Kelvin

算法分析

  • 正确性
  • 成本: 运行时间 + 所需存储空间(本节课先忽略空间)

考察:T(P) = 算法A求解问题实例P的计算成本

意义不大,可能出现的问题的实例太多

  • 归纳概括:划分等价类

观察:问题实例的规模,往往是决定计算成本的主要因素

  • 通常: 规模接近,计算成本也接近;规模扩大计算成本扩大。

特定算法 + 不同实例

令T(n) = 用算法A求解某一问题规模为n的实例,所需的计算成本,然而,同一问题等规模的不同实例,计算成本不尽相同,甚至有实质差别。
如Hailstone,枚举三角形面积最小三个点等

  • T(n) = max {T(p) | |P| = n}
    在规模为n的所有实例中,只关注最坏者。

  • 实验统计也不足以准确反映算法的真正效率。

规模、类型,程序员、语言、编译器、体系结构、操作系统等都会导致区别。

  • 抽象出一个理想的平台,不依赖于上述的具体因素,从而直接准确地描述、测量并评价算法,得出客观的评判。
    如伽利略的物理实验方法。

图灵机 Turing Machine, TM

Tape 依次均匀地划分为单元格 各注有某一字符,默认为‘#’
Alphabet 字符种类有限
Head 对准某一单元格,可读写字符。每过一节拍,转左侧或右侧的邻格。
State TM总是处于有限种状态中的某一种,每过一个节拍,可换状态。
Transition Function:(q,c;d,L/R,p)
// 状态、字符;新字符、左移/右移,新状态
// 一旦进入状态‘h’,则停机

  • 规范 ~ 接口

RAM: Random Access Machine

可计算方面与图灵机对等,都是一般工具的简化与抽象
独立于具体的平台,对算法的效率作出可信的比较与评判

算法的运行时间 -> 算法需要执行的基本操作次数
T(n) = 算法为求解规模为n的问题,所需执行的基本操作次数

  • 寄存器顺序编号,总数没有限制

基本操作:
R[i] <- c
R[i] <- R[j]
R[i] <- R[R[j]] // 间接存取
R[R[i]] <- R[j]
R[i] <- R[j] + R[k]
IF R[i] = 0 GOTO 1
GOTO 1 // 绝对转向
STOP // 停止语句 -- 图灵机中的‘h’

RAM:Floor

向下取整的除法,0 <= c, 0 < d

算法:反复从R[0] = 1+c 中减去R[1] = d,统计下溢之前,所做减法的次数x

  • RAM模型仅支持加减运算

0 R[3] <- 1 //increment 1 R[0] <- R[0] + R[3] // c++ 2 R[0] <- R[0] - R[1] // c -= d 3 R[2] <- R[2] + R[3] // x++ 4 IF R[0] > 0 GOTO 2 // if c>0 goto 2
5 R[0] <- R[2] - R[3] // else x-- and
6 STOP // return R[0] = x = floor(c/d)

大O记号

Mathematics is more in need of good notations than of new theorems -- Alan Turing

  • 渐进分析 Asymptotic analysis 规模足够大 n >> 2