7. 快速排序

快速排序是一种最坏情况时间复杂度为$\Theta(n^2)$的排序算法，虽然最坏情况的时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，它的期望时间复杂度是$\Theta(n\lg n)$，而且$\Theta(n\lg n)$中隐含的常数因子非常小。另外它是原址排序。

快速排序

快速排序也用了分治的思想。对子数组A[p…r]进行快速排序的过程如下：
分解 将A[p…r]划分为两个数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]的每一个元素小于等于A[q]，而A[q+1…r]的每一个元素大于等于A[q]。
解决 递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序。
合并 因为是原址操作，所以无需合并，这时A[p…r]已经有序。

伪代码和分解过程如下：

性能

最坏情况

若每次分解时，都分解为一个空数组和一个n-1大小的数组,则为最坏情况。
递归式为$T(n) = T(n-1) + T(0) + \Theta(n)$
$T(n)$的解为$\Theta(n^2)$

最好情况

若每次分解时，都分解为两个一样大的子问题，这时为最好情况。
递归式为$T(n) = 2 T(n/2) + \Theta(n)$
$T(n)$的解为$\Theta(n\lg n)$

平衡的划分

若每次分解时，都按照一定比例分割，比如按照9:1划分。
递归式为$T(n) = T(9n/10) + T(n/10) + \Theta(n)$
$T(n)$的解为$\Theta(n\lg n)$

可用代入法证明按照任何比例划分，$T(n)$的解都为$\Theta(n\lg n)$

平均情况

若每次分解时，最好情况和最坏情况交替出现。
$T(n)$的解为$\Theta(n\lg n)$

可以将最好情况和最坏情况合并，时间复杂度并没变

随机快速排序

随机快速排序可以避免特定输入（已排序的队列或逆序列）时运行时间较长的情况。
分解时，随机的挑选数组中的一个元素来分解。

TODO: 证明随机快速排序的期望运行时间

涉及算法

点击查看实现

• 快速排序
• 随机快速排序

留言與分享

6. 堆排序

堆排序也是一种时间复杂度为$\Omicron (n\lg n)$的排序算法，但是与归并排序不同的是堆排序是一种原址排序，也就是说排序过程只是交换数据的位置。

最大堆

堆是一个数组，存储一个近似完全二叉树，树上的每个结点对应数组中的一个元素，数组第一个元素存储根节点，第i个元素的左孩子在数组的2i位置，右孩子在数组的2i+1位置，父结点在数组的i/2位置。

最大堆指一种父节点必然大于等于子节点的堆。下图为一个最大堆的存储情况：

MAX-HEAPIFY（维护最大堆）

MAX-HEAPIFY是维护最大堆性质的重要方法。MAX-HEAPIFY的输入为数组A和下标i，当调用MAX-HEAPIFY时，假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，但是A[i]可能比它的子节点要小。MAX-HEAPIFY通过让A[i]的值在最大堆中逐级下降，从而使得以下标i为根节点的树符合最大堆的性质。以下是MAX-HEAPIFY的伪代码以及MAX-HEAPIFY(A, 2)的处理过程：

因为堆的高度为$\lg n$，所以该过程的时间复杂度是$\Omicron (\lg n)$.

建堆

自下而上的调用MAX-HEAPIFY可以把一个数组转换为最大堆。
叶子节点不需要调用，所以从下标为n/2的的元素开始，一直到根节点。
伪代码和建堆过程如下：

堆排序

1. 利用BUILD-MAX-HEAP方法构建最大堆
2. 接着循环的堆的根节点和最后一个元素交换
3. 堆的大小减一
4. 调用MAX-HEAPIFY(A, 1)
5. 循环2-4步，直到堆中只剩根节点

伪代码，以及2-5步过程如下：

优先队列

堆除了堆排序还有很多应用，比如优先队列。优先队列也有两种最大优先队列和最小优先队列。
一个最大优先队列支持以下操作：

1
2
3
4

INSERT(S, x)
MAXIMUM(S)
EXTRACT-MAX(S)
INCREASE-KEY(S, x, k)

最大优先队列的应用有很多，其中一个是在共享计算机系统的作业调度。最大优先队列记录将要执行的各个作业及他们之间的相对优先级。
最小优先队列可以被用于基于事件驱动的模拟器。队列中保存要模拟的事件，每个事件都有一个发生时间作为其关键字。

涉及算法

点击查看实现

• 堆排序

习题答案

思考题

• 6-43 Young氏矩阵

留言與分享

5. 概率分析和随机算法

当算法的时间和输入的数据有关时，往往我们需要使用概率分析得到算法运行时间的期望值（平均值）。
雇用问题这种答案不唯一的问题，也需要概率分析来分析算法的期望值，从而评估算法的有效性。

随机算法也有很广的应用，比如随机快速排序可以避免特定输入（已排序的队列或逆序列）时运行时间较长的情况。

留言與分享

4. 分治策略

本着涉及更多的分治法相关的算法，以及分治法运行时间的分析方法。

递归式

递归式可以很自然的刻画分支算法的运行时间。
递归式通过更小的输入上的函数值来藐视一个函数。
下图为归并排序的递归式：

$T(n)=\left\{ \begin{aligned} & \Theta(1) & if \quad n=1, \\ & 2T(n/2) + \Theta(n) & if \quad n>1, \end{aligned} \right.$

求解递归式的方法

• 代入法
  猜测一个界，然后用数学归纳法证明这个界的正确性
• 递归树法
  将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
• 主方法 可求解形式如 $T(n) = aT(n/b) + f(n)$的递归式的界

涉及算法

点击查看实现

• 最大子数组
• 矩阵乘法

练习

4.1-1

1

返回最大的一个数组成的数组

4.1-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

FIND-MAXIMUM-SUBARRAY(A, n)
    low = 1
    high = 1
    sum = A[1]
    for i = 1 to n
        max_sum = A[i]
        tmp_sum = A[i]
        for j = i+1 to n
            tmp_sum += A[j]
            if tmp_sum > max_sum
                max_sum = tmp_sum
                tmp_low = i
                tmp_high = j
        if max_sum > sum
            sum = max_sum
            low = tmp_low
            high = tmp_high
    return (low, high, sum)

4.1-4

1

在比较left-sum, right-sum, cross-sum时，增加对0的比较，当0最大时，返回空数组

留言與分享

3. 函数的增长

本章给出集中标准方法来简化算法的渐进分析。

渐进符号

Θ 渐进紧确界

   $f(n)=\Theta(g(n))$ 类似于 a = b
   当n>n0时，存在常数c₁和c₂使得c₁·g(n) <= f(n) <= c₂·g(n)

Ο 渐进上界

   $f(n)=O(g(n))$ 类似于 a ≤ b
   当n>n₀时，存在一个常数c使得 f(n) <= c·g(n)

Ω 渐进下界

   $f(n)=\Omega(g(n))$ 类似于 a ≥ b
   当n>n₀时，存在一个常数c使得 f(n) >= c·g(n)

ο

   $f(n)=\omicron(g(n))$ 类似于 a < b

ω

   $f(n)=\omega(g(n))$ 类似于 a > b

此图为书中截图，很好的说明了Θ Ο Ω 的含义

留言與分享

2. 算法基础

本章介绍了一个证明算法正确性的方法——循环不变式，对算法运行时间的简单分析，以及分治法。

循环不变式

类似于数学归纳法的一种证明算法正确性的方法。
需要证明以下三步：

• 初始化
  循环的第一次迭代前，它为真。
• 保持
  如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真。
• 终止
  再循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的。

分治法

将原问题分解为几个规模较小但类似于原问题的子问题，递归求解这些子问题，然后合并这些子问题的解来建立原问题的解。
每层递归时，都有如下三个步骤：

• 分解
  将原问题分解为几个规模较小但类似于原问题的子问题
• 解决
  递归求解各个子问题，当子问题规模够小可以直接求解时，则直接求解
• 合并
  合并这些子问题的解来建立原问题的解

涉及算法

点击查看实现

• 插入排序
• 归并排序

习题答案

思考题

• 2-4 逆序对

留言與分享

1. 算法在计算中的作用

算法应用广泛，包括解决一些问题，以及让解决一个问题更快速，更省空间。硬件（CPU，内存）总是有限的，所以算法是非常有必要的。不论是当今流行的互联网还是人工智能都和算法息息相关。

算法解决哪些问题

• 基因工程

  DNA中有十万个基因，30亿个化学基对，数据量很大

• 互联网

  管理和处理海量数据（路由，搜索引擎）

• 电子商务

  加密（公钥密码和数字签名）

• 资源分配

  最大利益（线性规划）

• 交通

  导航（最短路径）

• 基因匹配

  最长公共子序列

• 依据部件库的机械设计

  拓扑排序

• 凸壳
• …

难题

NP 完全问题

1. 迄今找不到一个有效算法，但是也没人能证明不存在有效算法
2. 如果任何一个NP 完全问题存在有效算法，那么所有NP 完全问题都存在有效算法
3. 有几个NP 完全问题类似于一些已知有效算法的问题

本书内容

• 算法
• 数据结构
• 算法分析/算法设计

留言與分享