L23 排序与分治

Posted on Edited on In Views:
  • 数学归纳法
  • QuickSort
  • 堆

Ref:

  • 算法设计与分析(Algorithm design and analysis) by 黄宇

数学归纳法

证明

  • 逆否命题 + 良序公理

形式

例子

  • “所有马都是同色”
    • 数学归纳法要求\(P(1)\)成立， 并且\(P(1)\) 到 \(P(2)\), \(P(2)\) 到 \(P(3)\)等全部成立。 这里\(P(1)\) 到\(P(2)\)不成立

公理化

  • 算法中遇到的输入是“可数无穷多”的（ 《离散》 ）
  • 自然数的定义
    • 可以用集合定义自然数
    • 可以用Lambda演算定义自然数

QuickSort

分析（指标随机变量）

Input：\(a_1,a_2,\dots,a_n\), 它必定有一个唯一的排列 \(z_1,z_2,\dots,z_n\)满足\(z_1 < z_2 < \dots < z_n\)​

  • 指标随机变量\(x_{ij}:\quad \{z_i 比 z_j\}\)​
  • 一共有\(\sum\limits_{1\leq i\leq j\leq n}x_{ij}\)次比较， 若两元素没有比较，则 \(x_{ij} = 0\)
  • 平均情况时间复杂度： \(E[\sum\limits_{1\leq i\leq j\leq n}x_{ij}] \in \Theta(nlogn)\)​​
    • \(E[x_{ij}] = \frac{2}{j-i+1}\)
      • 对于\(z_i,z_{i+1},\dots, z_{j-1},z_j\)，只有\(z_i\)或\(z_j\)被选为pivot时，\(z_i\)和\(z_j\)才会发生比较

堆

  • 堆的前k大元素：
    • 只需搜索堆的前k层（规模从n缩小为k），而且堆的前k层还是堆
  • \(\sum h \leq n-1\)​
    • \(\sum h_L + \sum h_R\) 用归纳法和堆的性质（左右子树必定有一棵是完美二叉树）