算法/分治法

顶部, 章节: 1, 2, 3, 4, 5, 6, 7, 8, 9, A

我们涵盖的第一个主要算法技术是分治法。设计一个好的分治算法的关键之一是确定如何将一个给定的问题分解成两个或多个相同类型但规模更小的子问题。更一般地说，当我们创建分治算法时，我们将遵循以下步骤

分治法方法

给定一个问题，识别出数量很少、规模明显更小的同类型子问题
递归地解决每个子问题（子问题的最小规模是一个基本情况）
将这些解决方案组合成主问题的解决方案

我们将要介绍的第一个使用这种方法的算法是归并排序。

归并排序

归并排序解决的问题是通用排序：给定一个具有全序关系的无序元素数组，创建一个包含相同元素的已排序数组。更准确地说，对于索引为 1 到 n 的数组 a，如果条件

对于所有 i、j，使得 1 ≤ i < j ≤ n 那么 a[i] ≤ a[j]

成立，那么 a 被认为是已排序的。以下是接口

// sort -- returns a sorted copy of array a
function sort(array a): array

遵循分治法方法，如何将 a 分解成更小的子问题？因为 a 是一个包含 n 个元素的数组，所以我们可能想要首先将数组分解成两个大小为 n/2 的数组。这些更小的数组也将是无序的，对这些更小的数组进行排序是有意义的；因此我们可以将这些更小的数组视为“类似”。暂时忽略基本情况，这将问题简化为一个不同的问题：给定两个已排序数组，如何将它们合并以形成一个包含两个给定数组中所有元素的单个已排序数组

// merge—given a and b (assumed to be sorted) returns a merged array that
// preserves order
function merge(array a, array b): array

到目前为止，遵循该方法已将我们引导到这一点，但是基本情况呢？基本情况是算法关注当问题无法分解成更小的子问题时发生的情况。在这里，基本情况是当数组只有一个元素时。以下是一个忠实地对只有零个或一个元素的数组进行排序的排序算法

// base-sort -- given an array of one element (or empty), return a copy of the
// array sorted
function base-sort(array a[1..n]): array
  assert (n <= 1)
  return a.copy()
end

将这些放在一起，以下是我们迄今为止通过该方法告诉我们编写的代码

// sort -- returns a sorted copy of array a
function sort(array a[1..n]): array
  if n <= 1: return a.copy()
  else:
    let sub_size := n / 2
    let first_half := sort(a[1,..,sub_size])
    let second_half := sort(a[sub_size + 1,..,n])
    
    return merge(first_half, second_half)
  fi
end

除了未实现的合并子例程之外，这个排序算法已经完成！在我们介绍这个算法如何工作之前，以下是如何编写合并操作

// merge -- given a and b (assumed to be sorted) returns a merged array that
// preserves order
function merge(array a[1..n], array b[1..m]): array
  let result := new array[n + m]
  let i, j := 1
  
  for k := 1 to n + m:
    if i >= n: result[k] := b[j]; j += 1
    else-if j >= m: result[k] := a[i]; i += 1
    else:
      if a[i] < b[j]:
        result[k] := a[i]; i += 1
      else:
        result[k] := b[j]; j += 1
      fi
    fi
  repeat
end

[待办：如何运作；包括正确性证明] 该算法利用了这样一个事实，即给定两个已排序数组，最小元素总是出现在两个位置之一。它要么在第一个数组的头部，要么在第二个数组的头部。

分析

令 $T(n)$ 为算法在大小为 $n$ 的输入上运行所需的时间步数。

合并需要线性时间，每次我们在两个大小为原始大小一半的子问题上递归，因此

T(n)=2\cdot T\left({\frac {n}{2}}\right)+O(n).

根据主定理，我们可以看到此递推关系具有“稳态”树。因此，运行时间为

T(n)=O(n\cdot \log n).

这可以通过询问 n 需要除以 2 多少次才能使排序数组的大小变为 1 来直观地理解？当然，m 次！

更直接地，2^m = n，相当于 log 2^m = log n，相当于 m × log₂2 = log ₂ n，而 log₂ 2 = 1，相当于 m = log₂n。

由于 m 是在数组被分割成 1 个元素的块之前数组被减半的次数，然后将需要 m 级合并子数组及其相邻数组，其中子数组的总大小在每一级都将是 n，因此在每一级合并中将进行 n ÷ 2 次比较，m（log₂n）级，因此 O(n ÷ 2 × log n) <=> O ( n log n) 。

迭代版本

这个归并排序算法可以通过迭代地合并每个后续的配对，然后合并每组四个，依此类推，来转换为迭代算法。由于缺乏函数开销，迭代算法在实践中往往更快。但是，由于递归版本的调用树的深度是对数的，因此它不需要太多运行时堆栈空间：即使对 4 千兆字节的项目进行排序，也只需要堆栈上的 32 个调用条目，考虑到即使每个调用都需要堆栈上的 256 字节，这也是非常小的，它只需要 8 千字节。

归并排序的迭代版本是对递归版本的一个小修改——实际上我们可以重复使用先前的合并函数。该算法通过合并原始数组中小的已排序子部分来工作，以创建更大的已排序数组子部分。为此，我们使用越来越大的“步长”遍历数组。

// sort -- returns a sorted copy of array a
function sort_iterative(array a[1,.n]): array
   let result := a.copy()
   for power := 0 to log2(n-1)
     let unit := 2^power
     for i := 1 to n by unit*2
       if i+unit-1 < n: 
         let a1[1..unit] := result[i..i+unit-1]
         let a2[1.unit] := result[i+unit..min(i+unit*2-1, n)]
         result[i..i+unit*2-1] := merge(a1,a2)
       fi
     repeat
   repeat
   
   return result
end

这是有效的，因为数组中长度为 1 的每个子列表都定义为已排序的。每次遍历数组（使用计数变量 i）都会通过将相邻的子列表合并成已排序的较大版本来使已排序子列表的大小加倍。算法中已排序子列表的当前大小由 unit 变量表示。

空间效率低

直接的归并排序需要 2 × n 的空间，n 用于存储两个排序后的较小数组，n 用于存储合并后的最终结果。但归并排序仍然适合用于合并批处理。

二分查找

一旦数组排序，我们就可以通过二分查找快速定位数组中的元素。二分查找与其他分治算法不同，它主要基于分治（不需要征服）。二分查找背后的概念将有助于理解将在随机化章节介绍的划分和快速排序算法。

在已经排序的数组中查找元素类似于在电话簿中查找姓名：你可以从打开书的中间部分开始。如果你要找的姓名在那页上，你就可以停止了。如果你翻得太远了，你可以从书的前半部分重新开始。如果你要查找的姓名出现在该页之后的页码上，你可以从书的后半部分开始。你重复这个过程，每次将搜索空间缩小一半，直到你找到你要找的内容（或者，或者找到你正在查找的内容应该在的地方，如果它存在）。

以下算法精确地描述了这个过程

// binary-search -- returns the index of value in the given array, or
// -1 if value cannot be found. Assumes array is sorted in ascending order
function binary-search(value, array A[1..n]): integer
  return search-inner(value, A, 1, n + 1)
end

// search-inner -- search subparts of the array; end is one past the
// last element 
function search-inner(value, array A, start, end): integer
  if start == end: 
     return -1                   // not found
  fi

  let length := end - start
  if length == 1:
    if value == A[start]:
      return start
    else:
      return -1 
    fi
  fi
  
  let mid := start + (length / 2)
  if value == A[mid]:
    return mid
  else-if value > A[mid]:
    return search-inner(value, A, mid + 1, end)
  else:
    return search-inner(value, A, start, mid)
  fi
end

注意，所有发出的递归调用都是尾调用，因此该算法是迭代的。如果我们的编程语言还没有为我们完成这些工作，我们可以通过将传递给递归调用的参数值变成赋值，然后循环到函数体顶部来显式地删除尾调用。

// binary-search -- returns the index of value in the given array, or
// -1 if value cannot be found. Assumes array is sorted in ascending order
function binary-search(value, array A[1,..n]): integer
  let start := 1
  let end := n + 1
  
  loop:
    if start == end: return -1 fi                 // not found
  
    let length := end - start
    if length == 1:
      if value == A[start]: return start
      else: return -1 fi
    fi
  
    let mid := start + (length / 2)
    if value == A[mid]:
      return mid
    else-if value > A[mid]:
      start := mid + 1
    else:
      end := mid
    fi
  repeat
end

即使我们有一个迭代算法，但理解递归版本更容易。如果算法执行的步骤数为 $T(n)$ ，那么我们有以下定义 $T(n)$ 的递归关系

T(n)=1\cdot T\left({\frac {n}{2}}\right)+O(1).

每次发出的递归调用的规模都是输入规模的一半 ( $n$ )，并且在递归之外花费了恒定时间（即，计算 length 和 mid 所需的时间将相同，无论数组中有多少元素）。根据主定理，该递归关系的值为 $a=1,b=2,k=0$ ，这是一个“稳态”树，因此我们使用稳态情况来告诉我们

T(n)=\Theta (n^{k}\cdot \log n)=\Theta (\log n).

因此，该算法需要对数时间。通常，即使当 n 很大时，也可以让堆栈通过递归调用增长 $\log n$ 个激活记录。

最初正确的二分查找实现的困难

维基百科上关于二分查找的文章也提到了编写正确的二分查找算法的困难：例如，java Arrays.binarySearch(..) 重载函数实现做了一个迭代二分查找，当大的整数溢出一个简单的中间值计算表达式 mid = ( end + start) / 2 时，它不起作用，即 end + start > max_positive_integer。因此，以上算法在使用长度 = end - start 并将一半长度加到开始时更正确。java 二分查找算法给出了一个返回值，该返回值对于找到最接近搜索键的键的位置很有用，即搜索键可以插入的位置。

即，如果未完全找到搜索键，但需要为搜索键插入点 (插入点 = -返回值 - 1)，则返回 - (keypos+1) 。查看边界值，插入点可以在列表的前面（ip = 0，返回值 = -1），也可以在最后一个元素之后的那个位置（ip = length(A)，返回值 = - length(A) - 1）。

作为一个练习，尝试在上面的迭代二分查找中实现此功能对于进一步理解可能会有所帮助。

整数乘法

如果要对小整数执行算术运算，可以简单地使用机器的内置算术硬件。但是，如果你想将大于计算机标准“字”整数大小的整数相乘，则必须在软件中实现一个乘法算法，或者使用其他人编写的软件实现。例如，RSA 加密需要使用非常大的整数（相对于许多机器的 64 位字大小而言）并且使用特殊的乘法算法。^[1]

小学乘法

如何表示一个大的多字整数？我们可以使用一个单词数组（或一块分配的内存）来表示大整数的位，从而得到二进制表示。假设我们现在有两个整数， $X$ 和 $Y$ ，我们想要将它们相乘。为简化起见，我们假设 $X$ 和 $Y$ 都有 $n$ 位（如果其中一个比另一个短，我们总是可以在开头填充零）。最基本的方法是用小学乘法算法来相乘。在二进制中，这甚至更容易，因为我们只乘以 1 或 0

         x6 x5 x4 x3 x2 x1 x0
      ×  y6 y5 y4 y3 y2 y1 y0
      -----------------------
         x6 x5 x4 x3 x2 x1 x0 (when y0 is 1; 0 otherwise)
      x6 x5 x4 x3 x2 x1 x0  0 (when y1 is 1; 0 otherwise)
   x6 x5 x4 x3 x2 x1 x0  0  0 (when y2 is 1; 0 otherwise)
x6 x5 x4 x3 x2 x1 x0  0  0  0 (when y3 is 1; 0 otherwise)
  ... et cetera

作为一个算法，以下是乘法的示例

// multiply -- return the product of two binary integers, both of length n
function multiply(bitarray x[1,..n], bitarray y[1,..n]): bitarray
  bitarray p = 0
  for i:=1 to n:
    if y[i] == 1:
      p := add(p, x)
    fi
    x := pad(x, 0)         // add another zero to the end of x
  repeat
  return p
end

子例程 add 会将两个二进制整数相加并返回结果，子例程 pad 会在数字末尾添加一个额外的数字（填充零与将数字左移相同，与将其乘以二相同）。在这里，我们循环 n 次，在最坏的情况下，我们对 add 进行了 n 次调用。传递给 add 的数字最多为 $2n$ 长。此外，我们可以预期 add 子例程可以在线性时间内完成。因此，如果对一个 $O(n)$ 子例程进行了 n 次调用，则该算法需要 $O(n^{2})$ 时间。

分治乘法

你可能已经猜到，这还不是故事的结尾。我们已经介绍了乘法的“明显”算法；所以让我们看看分治策略是否能给我们带来更好的结果。我们可能想尝试的一条路线是将整数分成两部分。例如，整数 x 可以分成两部分， $x_{h}$ 和 $x_{l}$ ，表示 $x$ 的高位和低位一半。例如，如果 $x$ 有 n 位，我们有

x=x_{h}\cdot 2^{n/2}+x_{l}

我们可以对 $y$ 做同样的事情

y=y_{h}\cdot 2^{n/2}+y_{l}

但是从这种分成较小部分的划分来看，不清楚我们如何相乘这些部分，从而使我们能够组合结果以解决主问题。首先，让我们写出 $x\times y$ 在这种系统中的表示

x\times y=x_{h}\times y_{h}\cdot (2^{n/2})^{2}+(x_{h}\times y_{l}+x_{l}\times y_{h})\cdot (2^{n/2})+x_{l}\times y_{l}

这来自简单地将 × 和 $y$ 的新高/低表示形式相乘。较小部分的乘法由 “ $\times$ ” 符号标记。请注意，乘以 $2^{n/2}$ 和 $(2^{n/2})^{2}=2^{n}$ 不需要真正的乘法：我们只需在右侧添加相应的零即可。这表明了以下分治算法

// multiply -- return the product of two binary integers, both of length n
function multiply(bitarray x[1,..n], bitarray y[1,..n]): bitarray
  if n == 1: return x[1] * y[1] fi          // multiply single digits: O(1)
  
  let xh := x[n/2 + 1, .., n]               // array slicing, O(n)
  let xl := x[0, .., n / 2]                 // array slicing, O(n)
  let yh := y[n/2 + 1, .., n]               // array slicing, O(n)
  let yl := y[0, .., n / 2]                 // array slicing, O(n)
  
  let a := multiply(xh, yh)                 // recursive call; T(n/2)
  let b := multiply(xh, yl)                 // recursive call; T(n/2)
  let c := multiply(xl, yh)                 // recursive call; T(n/2)
  let d := multiply(xl, yl)                 // recursive call; T(n/2)
  
  b := add(b, c)                            // regular addition; O(n)
  a := shift(a, n)                          // pad on zeros; O(n)
  b := shift(b, n/2)                        // pad on zeros; O(n)
  return add(a, b, d)                       // regular addition; O(n)
end

我们可以使用主定理来分析该算法的运行时间。假设算法的运行时间为 $T(n)$ ，注释显示了每一步需要多少时间。由于有四个递归调用，每个调用的输入大小为 $n/2$ ，我们有

T(n)=4T(n/2)+O(n)

这里， $a=4,b=2,k=1$ ，并且鉴于 $4>2^{1}$ ，我们处于“底部重”情况，因此将这些值代入主定理的“底部重”情况，我们得到

T(n)=O(n^{\log _{2}4})=O(n^{2}).

因此，经过所有这些努力，我们仍然没有比小学算法好！幸运的是，数字和多项式是我们已知其附加信息的数据集。事实上，我们可以通过一些数学技巧来减少运行时间。

首先，让我们用一个变量 *z* 替换 $2^{n/2}$

x\times y=x_{h}*y_{h}z^{2}+(x_{h}*y_{l}+x_{l}*y_{h})z+x_{l}*y_{l}

这看起来像是一个二次方程，我们知道你只需要三个系数或图形上的点来唯一地描述一个二次方程。然而，在我们上面的算法中，我们总共使用了四个乘法。让我们尝试将 × 和 $y$ 重铸为线性函数

P_{x}(z)=x_{h}\cdot z+x_{l}

P_{y}(z)=y_{h}\cdot z+y_{l}

现在，对于 $x\times y$ 我们只需要计算 $(P_{x}\cdot P_{y})(2^{n/2})$ 。我们将评估 $P_{x}(z)$ 和 $P_{y}(z)$ 在三个点上。评估函数的三个方便的点将是 $(P_{x}\cdot P_{y})(1),(P_{x}\cdot P_{y})(0),(P_{x}\cdot P_{y})(-1)$

[待办事项：展示如何使两部分分解更有效；然后提到最佳乘法使用 FFT，但不要实际涵盖该主题（该主题保存在高级书籍中）]

进制转换

[待办事项：使用 DnC 快速将数字从十进制转换为二进制。]

除了二进制之外，计算机科学还使用 8 进制和 16 进制，因为在使用 8 进制和 16 进制时，这三种进制之间的转换非常容易，并且 8 进制和 16 进制显着缩短了数字表示。

为了表示二进制系统中的前 8 个数字，我们需要 3 位。因此，我们有，0=000、1=001、2=010、3=011、4=100、5=101、6=110、7=111。假设 M=(2065)₈。为了获得其二进制表示，用相应的三个位替换四个数字中的每一个：010 000 110 101。删除前导零后，二进制表示立即得到：M=(10000110101)₂。（对于十六进制系统的转换非常类似，只是现在应该使用 16 以下数字的 4 位表示。）这一事实源于一般的转换算法，以及观察 8= $2^{3}$ （当然，16= $2^{4}$ ）。因此，似乎将数字转换为二进制系统的最短方法是先将它们转换为八进制或十六进制表示。现在让我们看看如何以编程方式实现一般算法。

为了参考，以基数（基数）N 表示的数字只能包含小于 N 的数字。

更准确地说，如果

(1)M=a_{k}N^{k}+a_{k-1}N^{k-1}+...+a_{1}N^{1}+a_{0}

如果 $0<=a_{i}<N$ ，那么我们有 M 在 N 进制下的表示，可以写成

M=(a_{k}a_{k-1}...a_{0})N

如果我们将 (1) 重写为

(2)M=a_{0}+N*(a_{1}+N*(a_{2}+N*...))

那么获取系数 ai 的算法就更加明显。例如， $a_{0}=M\ modulo\ n$ 以及 $a_{1}=(M/N)\ modulo\ n$ ，等等。

递归实现

让我们用记忆的方式来表示算法：(结果是一个字符串或字符变量，我将一个一个地累积结果的数字)

result = "" 
if M < N, result = 'M' + result. Stop. 
S = M mod N, result = 'S' + result
M = M/N 
goto 2

解释一下。

"" 是一个空字符串。您可能还记得它是字符串连接的零元素。在这里我们检查转换过程是否结束。如果 M 小于 N，则 M 就是一个数字（对于 N>10 有一些限定），并且没有额外的操作需要执行。只需将其预置在之前获得的所有其他数字前面。'+' 加号代表字符串连接。如果我们走到这里，M 不小于 N。首先我们提取其被 N 除的余数，将其预置到结果中，如前所述，并将 M 重新赋值为 M/N。这意味着整个过程应该从步骤 2 开始重复。我想有一个函数，比如称为 Conversion，它接受两个参数 M 和 N，并返回数字 M 在 N 进制下的表示。函数可能看起来像这样

1 String Conversion(int M, int N) // return string, accept two integers 
2 {  
3     if (M < N) // see if it's time to return 
4         return new String(""+M); // ""+M makes a string out of a digit 
5     else // the time is not yet ripe 
6         return Conversion(M/N, N) +
           new String(""+(M mod N)); // continue 
7 }

这实际上是一个有效的 Java 函数，它在 C++ 中看起来非常相似，并且只需要对 C 进行微小的修改。如您所见，在某些时候，函数会使用不同的第一个参数调用自身。有人可能会说该函数是根据自身定义的。这样的函数称为递归函数。（最著名的递归函数是阶乘：n!=n*(n-1)!。）该函数会将其参数调用（应用）于自身，然后（自然地）将参数应用于自身，然后...等等。我们可以确定该过程最终会停止，因为参数序列（第一个参数）正在递减。因此，迟早第一个参数将小于第二个参数，并且该过程将开始从递归中退出，一次一步。

迭代实现

并非所有编程语言都允许函数递归调用自身。如果出于任何原因可能会出现进程中断，递归函数也可能不可取。例如，在汉诺塔难题中，用户可能希望中断演示，因为他们急于测试自己对解决方案的理解。由于计算机执行程序的方式，当用户希望退出多个级别的递归调用时，会出现复杂情况。

但是请注意，转换算法产生的字符串是以错误的顺序获得的：所有数字都首先计算，然后将最后一个数字放在最前面写入字符串。递归实现很容易解决这个问题。每次调用 Conversion 函数时，计算机都会创建一个新的环境，其中存储了 M、N 和新计算的 S 的传递值。完成函数调用，即从函数返回后，我们会发现环境与调用之前一样。递归函数隐式地存储了一系列计算。消除递归调用意味着我们必须设法显式地存储计算出的数字，然后以相反的顺序检索它们。

在计算机科学中，这种机制被称为 LIFO - 后进先出。它最好用堆栈数据结构实现。堆栈只允许两种操作：push 和 pop。直观地说，堆栈可以被可视化为一个堆栈对象。对象一个一个地堆叠在彼此上面，因此要检索一个对象，必须删除上面所有需要的对象。显然，唯一可以立即删除的对象是顶部的对象，即最后进入堆栈的对象。

然后，Conversion 函数的迭代实现可能如下所示。

 1 String Conversion(int M, int N) // return string, accept two integers 
 2 {  
 3     Stack stack = new Stack(); // create a stack 
 4     while (M >= N) // now the repetitive loop is clearly seen 
 5     {  
 6         stack.push(M mod N); // store a digit 
 7         M = M/N; // find new M 
 8     }  
 9     // now it's time to collect the digits together  
10     String str = new String(""+M); // create a string with a single digit M 
11     while (stack.NotEmpty())  
12         str = str+stack.pop() // get from the stack next digit 
13     return str;  
14 }

该函数比它的递归对应函数长得多；但是，正如我所说，有时它是您想要使用的函数，有时它是您实际上唯一可以使用的函数。

最接近的点对

对于二维平面上的点集，如果要找到最接近的两个点，可以将它们全部相互比较，时间复杂度为 $O(n^{2})$ ，或者使用分治算法。

[待办事项：解释算法，并显示 n^2 算法]

[待办事项：编写算法，包括直觉、正确性证明和运行时间分析]

使用此链接查看原始文档。

http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

最接近点对：分治法

介绍

最接近点对问题的蛮力法（即检查所有可能的点对）需要二次时间。我们现在想介绍一种更快的分治算法来解决最接近点对问题。给定平面 S 上的点集，我们的方法是将该集合分成两个大致相等的半部分（S1 和 S2），我们已经拥有了这两个半部分的解，然后以线性时间合并这两个半部分，从而得到一个 O(nlogn) 算法。但是，实际的解决方案远非显而易见。目标对可能有一个点在 S1 中，另一个点在 S2 中，这难道不会强迫我们再次检查所有可能的点对吗？这里介绍的分治方法直接从我们在上一节中介绍的一维算法中推广而来。

平面上的最接近点对

好的，我们将尽可能直接地推广我们的一维算法（参见图 3.2）。给定平面上的点集 S，我们通过一条垂直线 l 将其划分为两个子集 S1 和 S2，使得 S1 中的点在 l 的左侧，S2 中的点在 l 的右侧。

我们现在递归地在这两个集合上求解问题，得到最小距离 d1（对于 S1）和 d2（对于 S2）。我们令 d 为这两个距离中的最小值。

现在，与一维情况相同，如果整个集合的最接近对包含来自每个子集的一个点，那么这两个点必须在 l 的 d 范围内。这个区域表示为 l 两侧的两个条带 P1 和 P2。

到目前为止，我们完全与一维情况一致。然而，此时，额外的维度造成了一些问题。我们希望确定 P1 中的某个点是否距离 P2 中的另一个点不到 d。然而，在平面上，我们没有在直线上观察到的奢侈条件，即每个集合中只有一个点可以处于中值的 d 范围内。实际上，在二维中，所有点都可能在条带中！这是灾难性的，因为我们将不得不比较 n2 对点以合并集合，因此我们的分治算法在效率方面不会给我们带来任何优势。值得庆幸的是，我们可以在此处进行另一个拯救生命的观察。对于条带中的任何特定点 p，只需要检查另一个条带中满足以下约束的点：

距离 p 不到 d 的点，并且位于另一个条带的方向上
距离 p 不到 d 的点，并且位于正负 y 方向上

仅仅因为在这个边界框之外的点不可能距离 p 小于 d 个单位（参见图 3.3）。碰巧的是，因为这个框中的每个点至少相距 d，所以框内最多可以有六个点。

现在，我们不需要检查所有 n2 个点。我们所要做的就是按 y 坐标对条带中的点进行排序，并按顺序扫描这些点，检查每个点与其最多 6 个邻居的距离。这意味着检查所有候选对最多需要 6*n 次比较。但是，由于我们按 y 坐标对条带中的点进行了排序，因此合并两个子集的过程不是线性的，实际上需要 O(nlogn) 时间。因此，我们的完整算法还没有达到 O(nlogn)，但它仍然比蛮力方法的二次性能有所改进（我们将在下一节中看到）。在第 3.4 节中，我们将演示如何通过加强递归子解来使该算法更有效。

二维算法的摘要和分析

我们在此提供上一节中介绍的算法的逐步摘要，以及性能分析。该算法只是以列表形式编写，因为我发现伪代码在试图理解算法时很繁琐且不必要。请注意，我们根据点的 x 坐标预先对点进行排序，并维护另一个结构，该结构按点的 y 值对点进行排序（用于步骤 4），这本身需要 O(nlogn) 时间。

点集的最接近对

通过直线 l 将集合划分为两个大小相等的子集，并递归地计算每个子集中的最小距离。
令 d 为这两个最小距离中的最小值。
消除距离 l 超过 d 的点。
根据它们的 y 坐标考虑剩余的点，我们已经预先计算了这些坐标。
按 y 顺序扫描剩余的点，并计算每个点与其所有邻居的距离，这些邻居的距离不超过 d（这就是为什么我们需要按 y 进行排序）。请注意，这样的点不超过 5 个（没有图 3.3，因此没有图的话，这 5 或 6 毫无意义。请将其包含在内）。
如果这些距离中的任何一个小于 d，则更新 d。

分析

让我们将 T(n) 视为我们算法的效率
步骤 1 需要 2T(n/2)（我们将算法应用于两个部分）
步骤 3 需要 O(n) 时间
步骤 5 需要 O(n) 时间（正如我们在上一节中看到的那样）

所以，

$T(n)=2T(n/2)+O(n)$

根据主定理，结果是

$T(n)\in O(nlogn)$

因此，子解的合并由步骤 4 中的排序控制，因此需要 O(nlogn) 时间。

这必须在分治算法的每个递归级别重复一次。

因此，整个 ClosestPair 算法需要 O(logn*nlogn) = O(nlog2n) 时间。

改进算法

我们可以通过减少步骤 4 中实现 y 坐标排序所需的时间来稍微改进该算法。这是通过要求步骤 1 中计算的递归解以 y 坐标的排序顺序返回点来完成的。这将产生两个排序的点列表，只需要在步骤 4 中合并它们（线性时间操作）即可生成完整的排序列表。因此，修改后的算法包括进行以下更改：步骤 1：将集合划分为...，并递归地计算每个部分的距离，以 y 坐标排序的顺序返回每个集合中的点。步骤 4：将两个排序列表以 O(n) 时间合并成一个排序列表。因此，合并过程现在由线性时间步骤控制，从而为在平面上查找点集的最接近对产生了 O(nlogn) 算法。

汉诺塔问题

[TODO: 写关于汉诺塔算法及其程序]

有 n 个不同大小的圆盘和三个柱子，圆盘按其大小的顺序放置在左侧柱子上。最小的圆盘在最上面，最大的圆盘在最下面。这个游戏是将所有圆盘从左侧柱子移动

规则

1) 每次只能移动一个圆盘。

2) 只能移动最上面的圆盘。

3) 任何圆盘只能放在更大圆盘的顶部。

解决方案

直观的想法

为了将最大的圆盘从左侧柱子移动到中间柱子，首先必须将最小的圆盘移动到右侧柱子。移动最大的圆盘后。然后将较小的圆盘从右侧柱子移动到中间柱子。

递归关系

假设 n 是圆盘的数量。

要将 n 个圆盘从柱子 a 移动到柱子 b，

1) 如果 n>1，则将 n-1 个圆盘从柱子 a 移动到柱子 c

2) 将第 n 个圆盘从柱子 a 移动到柱子 b

3) 如果 n>1，则将 n-1 个圆盘从柱子 c 移动到柱子 a

伪代码

void hanoi(n,src,dst){
  if (n>1)
    hanoi(n-1,src,pegs-{src,dst});
  print "move n-th disc from src to dst";
  if (n>1)
    hanoi(n-1,pegs-{src,dst},dst);
}

分析

分析很简单。 $T(n)=2T(n-1)+O(1)=O(2^{n})$

脚注

↑
超过计算机硬件直接支持的最大 "int" 的（数学）整数通常被称为 "BigInt"。处理如此大的数字通常被称为 "多精度算术"。有很多关于处理此类数字的各种算法的书籍，例如：
- 现代计算机算术，理查德·布伦特和保罗·齐默曼，剑桥大学出版社，2010 年。
- 唐纳德·E·克努特，《计算机程序设计艺术》，第 2 卷：半数值算法（第 3 版），1997 年。
实现这些算法的人可能会
- 为一个特定应用程序编写一次性实现
- 编写一个可用于许多应用程序的库，例如 GMP，GNU 多精度算术库或 McCutchen 的大整数库或者各种库 [1] [2] [3] [4] [5] 用于演示 RSA 加密
- 将这些算法放入你可以使用的编程语言的编译器中（例如 Python 和 Lisp），这些语言会在需要时自动从标准整数切换到 BigInt

顶部, 章节: 1, 2, 3, 4, 5, 6, 7, 8, 9, A

[1] 超过计算机硬件直接支持的最大 "int" 的（数学）整数通常被称为 "BigInt"。处理如此大的数字通常被称为 "多精度算术"。有很多关于处理此类数字的各种算法的书籍，例如：
现代计算机算术，理查德·布伦特和保罗·齐默曼，剑桥大学出版社，2010 年。

唐纳德·E·克努特，《计算机程序设计艺术》，第 2 卷：半数值算法（第 3 版），1997 年。
实现这些算法的人可能会
为一个特定应用程序编写一次性实现

编写一个可用于许多应用程序的库，例如 GMP，GNU 多精度算术库或 McCutchen 的大整数库或者各种库 [1] [2] [3] [4] [5] 用于演示 RSA 加密

将这些算法放入你可以使用的编程语言的编译器中（例如 Python 和 Lisp），这些语言会在需要时自动从标准整数切换到 BigInt

[2] 现代计算机算术，理查德·布伦特和保罗·齐默曼，剑桥大学出版社，2010 年。

[3] 唐纳德·E·克努特，《计算机程序设计艺术》，第 2 卷：半数值算法（第 3 版），1997 年。

[4] 为一个特定应用程序编写一次性实现

[5] 编写一个可用于许多应用程序的库，例如 GMP，GNU 多精度算术库或 McCutchen 的大整数库或者各种库 [1] [2] [3] [4] [5] 用于演示 RSA 加密

[6] 将这些算法放入你可以使用的编程语言的编译器中（例如 Python 和 Lisp），这些语言会在需要时自动从标准整数切换到 BigInt