Notes: Mathematical Analysis of Algorithms

date

May 18, 2021

slug

knuth-paper

status

Published

Introduction

算法分析领域的核心目标是研究如何量化分析各个不同算法的好坏，主要的两类问题如下：

Analysis of a particular algorithm. 分析某些特定算法的基本特征。

Frequency analysis. 分析算法的各部分的执行次数情况，实际上是分析时间复杂度。

Storage analysis. 分析算法占用的内存资源情况，实际上是分析空间复杂度。

Analysis of a class of algorithms. 分析解决一类问题的所有算法，尝试找到最优的算法。本文指出这类问题的两点弊端：

对技术性调整敏感。某些微小改变可能对最优算法的选取产生巨大的影响，因此研究往往被局限在一个有限范围内；

难以控制模型的拟合性。第 2 类问题的分析往往过于复杂，而简化模型可能与现实相悖，导致算法分析出现失误。

正因此，尽管第 1 类问题没有第 2 类问题有趣，但在实际应用中也可以发挥出巨大作用。在接下来的核心篇幅中，Knuth 便借助两个实例来具体阐述算法分析的基本思路。

In Situ Permutation

问题提出

给定一个一维数组，以及一个函数，使得是对的一个排列，同时有序。附加要求如下：

算法的空间复杂度为；

不能修改存储排列的空间。

算法设计

由数学知识，我们认识到这样的事实：在任意一个排列，我们总会存在若干个“环”，这个环形如。

以如下排列为例：

我们可以发现这个排列中有四个“环”：

我们定义某一环中最小的值为这个环的头元素，那么每当我们发现了一个环的头元素，我们便将的值填入处，将的值填入处……最终将填入环的尾元素对应的位置即可。

for j = 1 to n
   # 从 p(j) 开始遍历这个环
   k = p(j)
   # 如果 j 不是环的头元素，那么就会存在一个环上点 k < j
   while k > j: # --> a
      k = p(k)
   if k == j: # --> b
      # k 是环的头元素
      y = x[j], l = p(k)
      while l != j:
         x[k] = x[l], k = l, l = p(k)
      x[k] = y

算法分析

由基尔霍夫定律，我们了解到所有进入某节点的电流的总和等于所有离开这节点的电流的总和，在这里，我们可以有效的衡量某部分程序的执行情况。具体地，判断 k > j 的总次数等于 k = p(j) 以及 k = p(k) 的执行次数之和。

为了便于分析，在伪代码注释中标记出两个部分 a 和 b。而对于算法的正确性分析，算法的设计过程已清晰的展现，而要给出一个严谨的证明则十分麻烦，作者在此选择略去繁琐的证明部分。

极端情况

若记当前环的长度为 n，易知当时即对应 a 的最坏情况，此时取到最大值，值得注意的是，此时正好对应着 b 的最好情况。

而相类似的，当时即对应 b 的最坏情况，此时正好对应着 a 的最好情况。

平均情况

考虑 n 个元素的全排列的种可能情况是等可能的，即对应着平均情况。

重新回顾此前的例子排列，可以这个排列的环表述为，然而若不加限制，对其中每个环的表述方式会存在多种，难以统一，因此给予以下限制：

每个环从其头元素开始；

每个环的头元素递减排列。

在这样的条件下，环的表述可以固定为。

而此时我们发现括号的存在已无实际意义，因此可以直接去掉。那么，我们可以将每一个的排列映射为符合题意的。

这时，我们可以对 b 的意义进行描述：中的环的个数，也即中的 “left-to-right minima”（可以被表示为第一类斯特林数），由数学知识，记 b 的平均值为，b 的方差为，则有：

接下来我们同样可以对 a 的值进行分析。当循环变量 j = q(i) 时，k 一直往后执行到，满足抑或为环的头元素，因此会从到执行运算，于是，令：

那么

具体地，在以上实例中，，此时代入公式可得时，其余情形下。

记的平均值为，容易发现它便是所有个排列中的排列个数，我们有：

记调和级数为，对上式进行展开：

由数学知识易证，因此 a 的平均执行次数为。

接下来我们对 a 的方差进行求解，我们需要计算下面式子的平均值：

接下来便是一系列繁杂的数学运算过程：

其中，

将代入可得：

相对应地，

令，代入可得：

最终带入整理可以得到：

对 a 的方差的讨论证明了的最坏情况是非常罕见的。最后再进行一些近似，可以得到如下的结论：

可以得出结论：这个算法的平均时间复杂度为 ，在极少数情况下可能达到 。

进一步分析

对于外循环遍历到的一个，同时搜索，其中为的反函数，则可以对算法进行优化。

设最坏情况为，此时整个排列只有一个长度为 n 的环，我们可以得到如下递推式：

记为的二进制表示中 1 的个数。对于这个看起来很难下手的问题，Knuth 给出了答案：

若，则有

经过以上分析，我们了解到这种解法在最坏的情况下的时间复杂度为，实现了进一步的优化。

Selecting the largest

问题提出

给定一个一维数组，在比较次数尽可能少的前提下找到数组中第 t 大的值。

算法设计

对于这种问题，一个时间复杂度为的排序算法便可以解决，因此，我们需要考虑的是有没有时间复杂度低于的算法。

回忆我们已了解的算法以及刚学过的分治策略，根据快速排序的启发，我们可以采取如下思路：

对于数组，首先调用 Partition() 方法对的位置进行移动，记移动后的位置为 k，使它左边元素都比其小、右边元素都比其大。此时我们根据 k 和 t 的大小关系，就可以分别讨论接下来的搜索是在 k 的左侧还是右侧进行，抑或是此时 k 位置的元素正好是第 k 大的元素。

FindtthNumber(a, i, j, t):
   key = a[i]
   # Partition()的实现参考快速排序的相关原理
   # Partition()返回的是分割后的数组下标
   # 减去数组开头的位置得到a[k]是a[i]-a[j]里第几大的数
   k = Partition(key, a, i, j) - i + 1 
   if k == t:
      return a[k]
   else if k < t:
      return FindtthNumber(a, k + 1, j, t - k)
   else:
      return FindtthNumber(a, i, k - 1, t)