演算法/分治法

頂部, 章節: 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