邓俊辉<<数据结构>>-公开课-01-D

发表于

我把邓老师课上对自己有需要的笔记写下来，并在看完视频后补充教材和课后习题的内容.

算法分析

运用DSA

算法分析的两个任务

  • 正确性(不变性 * 单调性)
  • 复杂度增长速度表格

C++等高级语言的基本指令，等效于常数条RAM的基本指令；渐进意义下，相当
分支转向：goto // 算法灵魂；出于结构考虑，被隐藏
迭代循环:for(), while().. // 本质上 “if+goto”
调用+递归 // 本质上也是 “goto”

复杂度分析方法:

  1. 迭代: 级数求和
  2. 递归: 递归跟踪 + 递推方程
    猜测 + 验证

级数

算术级数：与末项平方同阶

幂方级数：比幂次高出一阶

几何级数（a > 1）:与末项同阶

收敛级数:O(1)

未必收敛，但长度有限

h(n) = 1 + 1/2 + 1/3 + … + 1/n = O(logn) // 调和级数
log1 + log2 + log3 + … + logn = log(n!) = O(nlogn) // 对数级数

推荐书籍

<<Concrete Math>> 具体数学

循环 vs 级数

没有耦合的二层循环

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
    O1Operation(i, j);

算术级数: n * n = O(n^2)
等效：矩形被填充的过程，时间复杂度等于矩形面积。

耦合的二层循环

for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++)
    O1Operation(i, j);

算术级数: n(n-1) / 2 = O(n^2)
等效：三角形被填充，复杂度等于矩形面积。

递增不为1的二层循环

for (int i = 0; i < n; i++)
for (int j = 0; j < i; j += 2013)
    O1Operation(i, j);

算术级数：O(n^2)

外循环左移一位(加倍)

for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < i; j++)
    O1peration(i, j);

几何级数：O(n) // ??

更复杂的实例

for (int i = 0; i <= n; i++)
for (int j = 1; j <  i; j += j)
    O1peration(i, j);

习题解析

取非极端元素、冒泡排序

取非极端元素

算法：

1, 从S中取出三个元素{x, y, z}
2, 确定并排除其中的最小值和最大值
3, 输出剩下的元素z

int ordinaryElements(int A[], int n) {
  // 从n >= 3个互异整数中,除最大、最小者以外,任取一个“常规元素”
  // 先比较a,b;再确定c对于(a,b)区间的关系
  int a = A[0], b = A[1], c = A[2];    // 从特定单元读取元素O(3)
  // 统一成区间(a, b), 用于c对其判断
  if (a < b) { } else {
    swap(&a, &b);
  }
  if (c < a) return a;
  else if (c > b) return b;
  else
    return c;
  // return 输出非极端数O(1)

  // =======================================
  // T(n) = O(3) + O(3) + O(1) = O(7) = O(1)
}

结论:无论输入规模有多大，所需执行该算法的执行时间都不变。

起泡排序问题

void bubblesort(int A[], int n) {
  for (bool sorted = false; sorted = !sorted; n--)
    for (int i = 1; i < n+1; i++) {  // 自左向右逐对检查[0,n)各相邻元素
      if (A[i-1] > A[i]) {         // 若逆序,则
        swap(&A[i-1], &A[i]);      // 令其交换位置
        sorted = false;            // 消除全局有序标记
      }
    }
}

算法分析

不变性：经k轮扫描交换后，最大的k个元素必然就位
单调性：经k轮扫描交换后，问题的规模缩减至n-k
正确性：经至多k轮扫描后，算法必然终止，且能给出正确答案

基本且重要的技巧：通过挖掘不变性和单调性，证明算法的正确性

封底估计 Back-Of-The-Envelope Calculation

不需要工具

787km 占据整个周长的1/50 => 整个周长4wkm

抓住问题的主要方面，简洁得出总体规律

在复杂度分析中，对象是时间。

封底估计实例

  • 一天: = 24hr 60min 60sec = 25 * 4000 = 10^5 sec
  • 一生: = 1世纪 = 100yr 365 = 3 10^4 = 3 * 10^9 sec
  • “50年” = 1.6 * 10^9 sec
  • 三生三世: 300yr = 10^10 = (1 googel)^(1/10) sec
  • 宇宙大爆炸至今: 10^21 = 10^(10^10)^2 sec
    三生三世是10^10s
    三生三世中的一天，相当于在一天中的1s
    整个宇宙中的三生三世，就是在三生三世中的0.1s

1亿 = 10^9

复杂度和浮点运算能力flops相除，能得到某算法的时间。

人口普查 n = 10^9
\=====================
普通PC 1Ghz 10^9 flops
Bullesort: O(n^2) ==> (10^9)^2 = 10^18

时间: 10^18 / 10^9 = 10^9
310^9 = 100yr, 10^9 = 30年
\=====================
普通PC 10^9 flops
Mergesort: O(n\logn) => (10^9)*log(10^9) = 30 * 10^9

时间; 30 * 10^9 / 10^9 = 30s
\=====================
天河1A 10^15 flops
Bullesort:

时间:20min: 10^3s
\=====================