分治算法
用于設計算法的另一種常用技巧為分治算法(divide and conquer)。分治算法由兩部分組成：
- 分(divide)：遞歸解決較小的問題(當然，基準情況除外)
- 治(conquer)：然後，從子問題的解建構原問題的解。
傳統上，在其代碼中至少含有兩個遞歸調用的例程叫作分治算法，且一般認為子問題是不相交的(即基本上不重疊)。例如，最大子序列和問題的一個 O(N logN) 的解法，以及分治算法的經典例子：歸并排序 和 快速排序，它們分别有 O(N logN) 的最壞情形以及平均時間的時間界。
分治算法的運作時間
有效的分治算法都是把問題分成一些子問題，每個子問題都是原問題的一部分，然後進行某些附加的工作以算出最後的答案。例如，歸并排序對兩個問題進行運算，每個問題均為原問題大小的一半，然後用到 O(N) 的附加工作。由此得到運作時間方程(帶有合适初始條件)：
T(N) = 2T(N/2) + O(N)
該方程的解為 O(N logN)。下面的定理可以用來确定大部分分治算法的運作時間。
方程 T(N) = aT(N/b) + O(Nk) 的解為
其中 a ≥ 1 以及 b ＞1。
最近點問題
問題的輸入是平面上的點集 P。如果 p1 = (x1, y1) 和 p2 = (x2, y2)，那麼 p1 和 p2 間的歐幾裡得距離為 [ (x1 - x2)2 + (y1 - y2)2 ]1/2 。需要找出一對最近的點。這其中有可能兩個點位于相同的位置，在這種情況下它們的距離為 0。
如果存在 N 個點，那麼就存在 N(N-1)/2 對點間的距離。
第一種方法是檢查所有這些距離，能夠得到一個很短的程式，但卻是花費 O(N2) 的算法，也就是窮舉搜尋的算法。
//計算點對間最小距離的蠻力算法
//計算點對間最小距離的蠻力算法
for (i = 0; i < numPointsInStrip; ++i)
for (j = i + 1; j < numPointsInStrip; ++j)
if (dist(pi, pj) < δ)
δ = dist(pi, pj);
假設平面上這些點已經按照 x 的坐标排過序，這隻不過頂多在最後的時間界上僅加了 O(N logN) 而已，因為整個算法都将是 O(N logN) 的，是以排序基本上沒增加運作時間消耗級别。
圖1 畫出了一個小的樣本點集 P。若這些點已按 x 坐标排序，那我們可以畫一條想象的垂線，把 P 分成兩半：PL 和 PR 。
最近的一對點或者都在 PL 中，或者都在 PR 中，或者一個點在 PL 中而另一個在 PR 中。這三個距離在圖2 中标出。
我們可以遞歸地計算 dL 和 dR。由于想要一個 O(N logN) 的解，是以必須能夠隻用 O(N) 的附加工作計算出 dC 。即，如果一個過程由兩個一半大小的遞歸調用和附加的 O(N) 工作組成，那麼總的時間将是 O(N logN)。
令 δ = min (dL, dR)。如果 dC 對 δ 有所改進，那麼隻需計算 dC 。如果 dC 是這樣一個距離，則決定 dC 的兩個點必然在分割線的 δ 距離之内，把這個條形局域叫作帶(strip)。如圖3 所示，這個觀察結果消減了需要考慮的點的個數(此例中的 δ = dR)。
有兩種方法可以用來計算 dC，由于平均隻有 O(N1/2) 個點在這個帶中，是以第一種方法可以以 O(N2) 時間對這些點進行蠻力計算。但在最壞情況下，所有的點可能都在這條帶狀區域内，是以這種算法不總能以線性時間運作。
改進算法：确定 dC 的兩個點的 y 坐标之間相差最多是 δ，否則就會有 dC ＞ δ。設帶中的點按照它們的 y 坐标排序。是以，如果 pi 和 pj 的 y 坐标相差大于 δ，則可以再去繼續處理 pi+1。
//最小距離的精化計算
for (i = 0; i < numPointsInStrip; ++i)
for (j = i + 1; j < numPointsInStrip; ++j)
if(pi and pj 's y-coordinates differ by more than δ)
break; //轉向下一個pi
else
if (dist(pi, pj) < δ)
δ = dist(pi, pj);
選擇問題
選擇問題要求我們找出 N 個元素集合 S 中的第 k 個最小的元素。
基本的算法是簡單的遞歸政策。設 N 大于截止點(cutoff point)，元素将從截止點開始進行簡單的排序，v 是選出的一個元素，叫作樞紐元(pivot)。其餘元素被放在兩個集合 S1 和 S2 中，S1 含有那些保證不大于 v 的元素，而 S2 包含那些不小于 v 的元素。最後，如果 k ≤ |S1|，那麼 S 中的第 k 個最小的元素就可以通過遞歸地計算 S1 中第 k 個最小的元素而找到。如果 k = |S1| +1，則樞紐元就是第 k 個最小的元素。否則，在 S 中的第 k 個最小的元素是 S2 中的第 (k - |S1| - 1) 個最小元素。這個算法和快速排序之間的主要差別在于，這裡隻有一個子問題而不是兩個子問題要被求解。
五元中值組取中值分割法
對于快速排序，樞紐元一種好的選擇是選取 3 個元素并取它們的中位數。但它并不提供一種好的保證。為得到一個好的最壞情形，關鍵想法是再用一個間接層。不是從随機元素的樣本中找出中值，而是從一些中值的樣本中找出中值。
基本的樞紐元選擇算法如下：
- 把 N 個元素分成 ⌊N/5⌋ 組，每組5個元素，忽略剩餘的（最多4個）元素。
- 找出每組的中值，得到 ⌊N/5⌋ 個中值的表M。
- 再求出 M 的中值，将其作為樞紐元 v 傳回。
使用五元中值組取中值分割法的快速選擇算法的運作時間為 O(N)。
整數相乘
設要将兩個 N 位數字的數 X 和 Y 相乘，并假設它們都是正的。幾乎人在手算時用的算法都需要 O(N2) 次運算，這是因為 X 中的每一位數字都要被 Y 的每一位數字去乘。
如果 X = 61 438 521 而 Y = 94 736 407，那麼 XY = 5 820 464 730 934 047。将 X 和 Y 拆成兩半，分别由最高幾位和最低幾位數字組成。此時，XL = 6143，XR = 8521，YL = 9473，YR = 6407。則有 X = XL104 + XR 以及 Y = YL104 +YR，由此得
XY = XLYL108 + (XLYR + XRYL)104 + XRYR。
這個方程由4次乘法組成，即XLYL、XLYR、 XRYL 和 XRYR。它們每一個都是原問題大小的一半(N/2位數字)。若遞歸地使用該算法進行這4項運算，則得到遞歸
T(N)=4T(N/2) +O(N)
可知T(N) = O(N2)，為得到一個亞二次的算法，必須使用少于4次的遞歸調用，有
XLYR + XRYL = (XL - XR) (YR - YL) + XLYL +XRYR
此時的遞歸方程
T(N)=3T(N/2) +O(N)
進而得到 T(N) = O(N1.59)。