Sort

父之齒隨行,兄之齒鴈行,朋友不相踰。《禮記.王制》

Sort

「排序」。把一群數字由小到大排好。

排序演算法類型

一、使用循序資料結構,例如Array、List,將數字依序放進去,執行排序演算法。

二、使用具備排序功效的資料結構,例如Binary Search Tree、Binary Heap,將數字整個倒進去、整個倒出來,完成排序。

本文討論第一種類型。第二種類型請見本站文件「Binary Search Tree」。

排序原理

一、對調(比較)。二、放置(索引)。

對調式排序,將小數字往前挪、大數字往後挪。基礎的對調式排序是Selection Sort。當前最快的對調式排序是Pdqsort。

放置式排序,需要額外的記憶體空間來放置數字,但是計算時間遠少於對調式排序。基礎的放置式排序是Counting Sort。當前最快的放置式排序是Radix Sort。

英文說法:一、比較式排序演算法Comparison-based Sorting Algorithm、交換排序Exchange Sort。二、非比較式排序演算法Non-comparison-based Sorting Algorithm、分布排序Distribution Sort。

等價於數字的東西也可以排序

字元也可以排序。字元就是ASCII碼、就是數字。

指標也可以排序。指標就是記憶體位址、就是數字。

資料也可以排序。只要資料的某個特定欄位是數字,這個欄位稱作鍵值(key)。

等價於數組的東西也可以排序

數組(tuple)也可以排序。其中一種方式:先比較第一維度;如果平手,再比較第二維度;如果又平手,再比較第三維度;以此類推。這個比較方式稱作字典序(lexicographical order)。

字串也可以排序。字串就是一串ASCII碼、就是數組。

英文單字也可以排序。英文單字就是一串字母、字母可以編號、整體宛如數組。英文字典,採用了字典序,排序所有英文單字。

UVa 482

能夠建立全序的東西也可以排序

所有東西均可兩兩比較大小,而且沒有矛盾,稱作全序(total order)。

排序對象沒必要是數字。沒有數字,只有比較;沒有絕對大小,只有相對大小;無法使用放置式排序,只能使用對調式排序。

間接排序

排序會搬動資料,但是大多數時候我們不希望搬動資料。此時可以取出資料的記憶體位址,另外建立指標,對指標進行排序,但是比較對象是指標所指的資料鍵值大小。

也有人使用陣列索引值,道理跟指標相同。

Stable

鍵值相同的資料們,原本排在前頭的,排序後仍在前頭;原本排在後頭的,排序後仍在後頭。這稱作「穩定的」排序演算法,鍵值相同、順序不變。

只要是放在陣列的資料,任何一種排序演算法,都可以擴展成穩定的排序演算法。你想到解決方法了嗎?

Comparison Function(Comparator)

對調式排序必須使用「比較函數」。

C標準函式庫的qsort(),其參數cmp就是比較函數。意義是小於,回傳值是int變數,正零負代表< = >。

C++標準函式庫的sort(),其參數cmp就是比較函數。意義是小於,回傳值是bool變數,true false代表< ≮。

C++標準函式庫也有比較函數less(),以便作為參數預設值。

Sorting Network

「排序網路」。兩兩比較的先後次序圖。

每一種對調式排序演算法,都可以畫出排序網路。但是也有例外,例如Quicksort的加速技巧:三個中位數的中位數,必須知道數字多寡,才能決定比較對象,此時就無法畫出排序網路。

事情也可以反過來。設計一個新的排序網路,就得到一種新的對調式排序演算法。

排序網路的深度,即是排序演算法的步驟數量。深度下限,已被證明是Ω(NlogN),不可能更少了。深度最小值,則是NP-complete問題。換句話說,找到一個深度盡量小的排序網路,目前沒有(以後大概也不會有)快速的演算法。

設計排序網路演算法,製造排序演算法,以演算法產生演算法,這件事簡直超酷的。但是很不幸的,這條路很難走。

UVa 1117

排序演算法

               | average   worst     | extra | stable
               | case      case      | space | sort
---------------+---------------------+-------+----
searching sort | O(NR)     O(NR)     | O(N)  | ✓  → my favorite
selection sort | O(NN)     O(NN)     | O(1)  | ✓
---------------+---------------------+-------+----
bubble sort    | O(NN)     O(NN)     | O(1)  | ✓
gnome sort     | O(NN)     O(NN)     | O(1)  | ✓    best
insertion sort | O(NN)     O(NN)     | O(1)  | ✓    stable
Shell sort     | O(NN)     O(NN)     | O(1)  |      comparison-
merge sort     | O(NlogN)  O(NlogN)  | O(N)  | ✓    based
Timsort        | O(NlogN)  O(NlogN)  | O(N)  | ✓  → sort
---------------+---------------------+-------+----
heapsort       | O(NlogN)  O(NlogN)  | O(1)  |
splaysort      | O(NlogN)  O(NlogN)  | O(1)  |
---------------+---------------------+-------+----
quicksort      | O(NlogN)  O(NN)     | O(N)  |      best
introsort      | O(NlogN)  O(NlogN)  | O(N)  |      comparison-
blockquicksort | O(NlogN)  O(NlogN)  | O(N)  |      based
pdqsort        | O(NlogN)  O(NlogN)  | O(N)  |    → sort
---------------+---------------------+-------+---- 
counting sort  | O(N+R)    O(N+R)    | O(R)  | ✓    best
radix sort     | O((N+β)D) O((N+β)D) | O(β)  | ✓  → sort
---------------+---------------------+-------+----
bucket sort    | O(N+β)    O((N+β)D) | O(βD) | ✓
flashsort      | O(N+β)    O((N+β)D) | O(βD) | ✓    best
samplesort     | O(NlogN)  O(NN)     | O(N)  | ✓    parallel
IPS⁴o          | O(NlogN)  O(NN)     | O(N)  | ✓  → sort
---------------+---------------------+-------+----
sleep sort     | O(N+R)    O(N+R)    | O(N)  | ✓  → best of
                                                    the best
N: input size
R: input range
β: radix / bucket count       (β = 2, generally speaking)
D: digits / recursion depth   (D = logᵦR) (R = βᴰ)

Searching Sort

搜尋排序。依序枚舉每一個整數,看看陣列裡頭有沒有。

令最小值是A,最大值是B,從最小值到最大值有R = B-A+1個整數。時間複雜度O(RN)。

Selection Sort

選擇排序。掃描一遍所有數字,找到最小值,挪至陣列左端。遞迴處理尚未排序的N-1個數字。

Bubble Sort

氣泡排序。由左到右,相鄰兩兩比較,較大者往右挪,最後最大值會出現在陣列右端。遞迴處理尚未排序的N-1個數字。

Gnome Sort

地精排序。Bubble Sort加強版。調整兩兩比較的先後次序。

特色是程式碼只有一個迴圈,結構簡單。

Insertion Sort

插入排序。由左到右,逐一把數字插入到目前已排序的陣列當中。將大量數字往右挪,以騰出空間插入數字。

資料結構如果是Array,可以使用Binary Search快速找到插入點;但是很不幸的,插入時還是要挪動整塊記憶體。

資料結構如果是List,就無法使用Binary Search得到插入點;但是很幸運地,插入時不必挪動整塊記憶體。

UVa 10107

Shell Sort

Shell是作者姓名。Insertion Sort加強版。

Scaling Method。固定間隔取得數字作為一組,各組各自做Insertion Sort;間隔大小減半,重複上述動作。

特色是往右挪的總次數變少了。

Merge Sort

合併排序。Divide-and-Conquer Method。分兩半、分別排序、合併。

可以直接使用C++標準函式庫的stable_sort()。

UVa 10810

Timsort

Tim是作者姓名。Merge Sort加強版。

合併時,若數字大小順序交錯,則適合原本方式,步步前進;若數字大小順序連貫,則適合Binary Search,大步邁進。

對於短區間,交錯機會少,連貫機會大,於是改成大步邁進。

分水嶺通常設定成64,沒有科學根據。

實務上速度最快的stable的對調式排序演算法。

Heapsort

堆積排序。陣列可以當作二元樹。陣列可以當作Binary Heap。逐一把數字放入Binary Heap,達到排序功效。

Splaysort

伸展排序。陣列可以當作二元樹。陣列可以當作Splay Tree。逐一把數字放入Splay Tree,達到排序功效。

Quicksort

快速排序。Divide-and-Conquer Method。選定pivot,挪到陣列邊緣,然後把陣列分成大的一邊和小的一邊,兩邊分別排序。

任選一個數字當作pivot,排序結果皆正確。想讓Quicksort達到最佳效率,就讓每次選中的pivot,每次都把陣列分成兩等份,如此一來時間複雜度是O(NlogN)。幸運的是,即便把陣列分成數量懸殊的兩半,即便是1000000:1,只要是固定比例,時間複雜度還是O(NlogN)。但是這種事帶點運氣成份。

固定選擇最後一個數字當作pivot,也有機會把陣列分成兩等份。然而這卻產生一個古怪現象:遇到已經排序的陣列,每次都把陣列分成(N-1):1,時間複雜度變成O(N²),超級慢。Quicksort有時快、有時慢;遇到幾乎排序好的陣列,更是慢到吐血。

為了避免這種情況,可以每次都用亂數選擇pivot,如此一來比較不容易出現上述古怪現象。然而這又衍生一個難纏問題:只是做個排序,卻還得載入亂數模組,耗損系統資源、拖慢系統速度,帶來了新的壞處。

最後大家捨棄亂數,轉而構思一些小技巧,讓pivot儘可能把陣列分成兩等分。例如Java的Quicksort,把陣列切成前中後三段,拿這三段中央的數字,三個數字的中位數當作pivot。這便是一個簡單實用的小技巧。

UVa 755

© 2010 tkcn. All rights reserved.

Introsort

內排序。Quicksort加強版。遞迴分割陣列,區間越來越短,數字也幾乎排序好了。對於幾乎已經排序好的短區間,Quicksort慢到吐血。此時改用Heapsort,強硬地壓低最差時間複雜度。

分水嶺通常設定成logN² = 2logN,N是陣列長度。

可以直接使用C++標準函式庫的sort()。

BlockQuicksort

分塊快速排序。Quicksort加強版。比較大小,避免branch misprediction,改用整數運算。對調數字,避免cache miss,改用分塊搬運。

Pattern-defeating Quicksort(Pdqsort)

破格快速排序。Introsort暨BlockQuicksort加強版。比較大小、對調數字,進行細部改良。盡量避免使用緩慢的Heapsort。

實務上速度最快的對調式排序演算法。

Counting Sort

計數排序。全部數字,依其數值,放到相符位置。由小到大讀取各個位置的數字。只能處理整數。

UVa 484 11462

Radix Sort

基數排序。Scaling Method。低位數到高位數,每個位數依序作為鍵值,總共做D回合Counting Sort,D為位數大小。

二進位數字,基數β = 2,位數D = logᵦR。實務上取基數β = 256 = 2⁸,記憶體剛好是1 byte = 8 bit。

也能處理二補數。仔細判讀正負號位置。

也能處理浮點數。仔細判讀正負號位置、次方值位置。

實務上速度最快的排序演算法。

Bucket Sort

桶排序。Divide-and-Conquer Method。自訂桶子數量β、自訂桶子區間[a₀,a₁)到[aᵦ₋₁,aᵦ)。每個數字放到相符桶子。各個桶子各自排序。由小到大讀取各個桶子的數字。可以處理非整數。

桶子區間,習慣遞迴等分。數字範圍,除以桶子數量,作為桶子區間寬度。每個數字經由除法運算、取整運算,求得相符桶子編號。

Flashsort

閃排序。Bucket Sort加強版。預先求得最小值、最大值,作為數字範圍。最大值減最小值,除以桶子數量,作為桶子區間寬度。

Samplesort

抽樣排序。Bucket Sort加強版。隨機抽樣,作為桶子區間。

可以視作Quicksort的通例。大量pivot,將陣列分成多段。

In-place Parallel Super Scalar Samplesort(IPS⁴o)

原地平行超純量抽樣排序。Samplesort平行化版本。

in-place:額外記憶體空間為O(1),甚至不需要額外記憶體空間。
parallel:多個中央處理器。此處是指,各桶各自排序。
superscalar:中央處理器,整合處理多個指令。此處是指,整合處理比較與交換。
cache-efficient:記憶體區塊,鮮少反覆載入。此處是指,比較集中在同一區塊。
branch-prediction:if判斷結果,經常預測成功。此處是指,比較結果經常一致。

平行計算的情況下,實務上速度最快的對調式排序演算法。

Sleep Sort

睡眠排序。源自網路論壇4chan。

延遲輸出,延遲時間是數字大小。數字越小,輸出越早。

實務上最適合拿來裝逼的排序演算法。

Search

眾裏尋他千百度,驀然回首,那人卻在,燈火闌珊處。《辛棄疾.青玉案》

Search

「搜尋」。找出一個數字的位置。

Search in Array: Sequential Search

循序搜尋。依序看一遍。時間複雜度O(N)。

Search in Sorted Array: Binary Search

二元搜尋。Divide-and-Conquer Method。已排序陣列,對半分成兩邊,遞迴搜尋其中一邊。時間複雜度O(logN)。

經典應用:資料恰有兩種性質,明顯地分做兩邊,可用Binary Search找到分界之處。

UVa 10611 10077

Search in Sorted Array: Interpolation Search

內插搜尋。Binary Search加強版。根據陣列左右兩端數字大小,一次內插,作為分割位置。

Search in Sorted Unbound Array: Doubling Search

倍增搜尋。主持人心中有一正整數,我們可以一直猜他心中的正整數,但是他只會回答「太高」或「太低」或「正確」。請問要怎麼猜可以最快猜到他心中的正整數呢?

有個類似的團康遊戲叫做「終極密碼」,常常在綜藝節目出現。「終極密碼」的規則比較不一樣,數字範圍通常只有1到100,而且是很多個人輪流猜,越晚猜出來越好。這裡的猜數字遊戲,數字範圍是1到無限大,只有一個人猜,越早猜出來越好。

言歸正傳。從1開始一個一個往上猜,實在太慢了。比較快的猜法,是將問題分成兩個步驟,第一個步驟是先確定範圍,第二個步驟再來縮小範圍。

確定範圍:可以從1、2、4、8、……這個順序去猜。如果主持人不斷回答太低,我們就不斷往大數字猜,一直到主持人回答太高為止。如果主持人心中的正整數為N,則可以用O(logN)的時間得到一個合理的範圍,N會落在(2ᵏ⁻¹, 2ᵏ]之間。

縮小範圍:可以使用Binary Search!從(2ᵏ⁻¹, 2ᵏ]之間找出正確的正整數,只需O(logN)時間。

二元搜尋和倍增搜尋相互對立,前者除以二、後者乘以二。

Search in Sorted Arrays: Fractional Cascading

Search in Sorted Matrix: Saddleback Search

鞍背搜尋。二維矩陣裡的數字經過排序,往右、往下都呈現嚴格遞增,此時有個很巧妙的搜尋方式,時間複雜度O(X+Y),X與Y分別為矩陣的長與寬。

首先在腦中將矩陣的數字切割為大於n的一邊(右下)與不大於n的一邊(左上)。現在我們所要作的,便是遊走於大與小的邊緣來尋找n!從矩陣的右上角開始,嘗試走到左下角,若走到了大於n的一邊,就立即往不大於n的另一邊移動,反之亦同。

各位可以想想當找到目標數字時,應該往左還是往下走好?當矩陣數字是非嚴格遞增的時候會產生什麼問題?

UVa 12192

Select

羽望見良麾蓋,策馬刺良於萬眾之中,斬其首還。《三國志》

Select

「選擇」。找到特定名次的數字,例如第k小的數字。

最簡單的方式就是先排序、再搜尋。以下探討更快的方法。

UVa 10041 10107 11875

Select in Array: Quickselect

Quicksort只遞迴其中一邊。平均時間複雜度O(N),最差時間複雜度O(N²)。

可以進化成Introselect、Pdqselect。最差時間複雜度O(N)。

可以直接使用C++標準函式庫的nth_element(),但是細節不盡相同。

Select in Array: Median-of-Medians Algorithm

找到中位數們的中位數(中中數),將數字分成大的一邊和小的一邊,遞迴找其中一邊。時間複雜度O(N),但是不實用。

1. 五個五個分堆,最後一堆可以沒有滿。

   第一堆 ● ● ● ● ●
   第二堆 ● ● ● ● ●
   第三堆 ● ● ● ● ●
   第四堆 ● ● ● ● ●
   第五堆 ● ● ● ● ●
   第六堆 ● ● ●

2. 每堆各自排序。然後求出每堆的中位數 ○。

      小  →  大
   ↑  ● ● ○ ● ●
   沒 ● ● ○ ● ●
   有 ● ● ○ ● ●
   順 ● ● ○ ● ●
   序 ● ● ○ ● ●
   ↓    ● ○ ●     ← 最後一堆對齊一下比較好看

3. 求出中位數們的中位數 x。遞迴套用此演算法求得 x。

      小  →  大
   ↑  ● ● ○ ● ●
   沒 ● ● ○ ● ●
   有 ● ● ○ ● ●
   順 ● ● ○ ● ●
   序 ● ● x ● ●   ← 中位數可能在任何一個地方
   ↓    ● ○ ●

4. 將全部的數字分成兩邊,一邊小於 x ,一邊大於等於 x。

         小於 x ←|   |→ 大於等於 x
   ... ● ● ● ● ● ● x ● ● ● ● ● ● ● ● ...

5. 看看 k 是在哪一邊。遞迴下去找出答案。
時間複雜度証明

          小  →  大
   第一堆 ● ● ○ ● ●
   第二堆 ● ● ○ ● ●
   第三堆 ● ● ○ ● ●
   第四堆 ● ● ○ ● ●
   第五堆 ● ● x ● ●
   第六堆   ● ○ ●

依照中位數們的大小,重新排列每一堆。

              小  →  大
   第四堆  中 ● ● ○ ● ●
   第二堆  位 ● ● ○ ● ●
   第五堆  數 ● ● x ● ●   ← 中位數 x 變成排在中間
   第一堆  小 ● ● ○ ● ●
   第三堆  ↓  ● ● ○ ● ●
   第六堆  大   ● ○ ●

觀察一定小於等於x的數、一定大於等於x的數。

   一定小於    一定大於
   等於x的數   等於x的數
   ◊ ◊ ◊ ● ●   ● ● ○ ● ●
   ◊ ◊ ◊ ● ●   ● ● ○ ● ●
   ◊ ◊ x ● ●   ● ● x ◊ ◊
   ● ● ○ ● ●   ● ● ◊ ◊ ◊
   ● ● ○ ● ●   ● ● ◊ ◊ ◊
     ● ○ ●       ● ◊ ◊

推得「小於等於 x 的數至少有 3n/10 - 6 個。大於 x 的數至多有 7n/10 + 6 個。」
推得「大於等於 x 的數至少有 3n/10 - 6 個。小於 x 的數至多有 7n/10 + 6 個。」

  至多7n/10 + 6         差不多至多7n/10 + 6
         小於 x ←|   |→ 大於等於 x
   ... ● ● ● ● ● ● x ● ● ● ● ● ● ● ● ...

分兩邊後,
小於的那一邊至多有 7n/10 + 6 個,
大於等於的那一邊差不多至多有 7n/10 + 6 個。
遞迴下去,總時間複雜度 O(n)。

Select in Array: Floyd–Rivest Algorithm

據說是實務上速度最快的選擇演算法。

Select in Sorted Array

O(1)。

Select in Sorted Arrays

找到中中數,然後每列皆實施Binary Search,最後所有數字分為大的一邊和小的一邊,遞迴找其中一邊。每回合至少削減一半的列的一半。每列各自建立首尾索引值,記錄剩下的數字。

每回合需時O(XlogY),總共O(logY)回合,時間複雜度O(XlogYlogY)。X是陣列數量,Y是陣列長度。

簡單來說,此演算法是搜尋中中數、分兩邊、遞迴一邊。

Select in Sorted Arrays

找到X個中位數,然後找到最大中位數、最小中位數。每回合削減最大中位數的右半或最小中位數的左半。每回合刪除一列的一半,總共O(XlogY)回合。

以二元搜尋樹儲存X個中位數,每回合可以快速找到最大中位數、最小中位數。總共操作O(XlogY)次,每次操作O(logX),時間複雜度O(XlogXlogY)。X是陣列數量,Y是陣列長度。

Select in Sorted Matrix

切成一列一列,找到中中數。利用Saddleback Search將矩陣分為大的一邊和小的一邊,遞迴找其中一邊。

每回合需時O(N),總共O(logN)回合,時間複雜度O(NlogN)。

Select in Sorted Matrix

Divide-and-Conquer Method。O(N)。

Statistic

Extremum

「極值」。細分為最大值maximum、最小值minimum。

找到極值本身,甚至找到出現次數、出現位置。

循序搜尋。時間複雜度O(N),額外的空間複雜度O(1)。

Mode

「眾數」。出現最多次的數字。

先排序再搜尋。採用對調式排序,例如Merge Sort,時間複雜度O(NlogN),額外的空間複雜度O(1)。採用放置式排序,例如Counting Sort,時間複雜度O(N+R),額外的空間複雜度O(R)。

Longest Plateau

一串數字當中,連續出現最多次的數字,找到出現次數。

已排序陣列,有更簡單的做法。

Majority

「過半數」。過半的數字。

找到其中一個過半數。時間複雜度O(N),額外的空間複雜度O(1)。

Distinct Count

相異數字個數。

先排序再搜尋。時間複雜度O(NlogN)或O(N+R)。

近似演算法是「Flajolet–Martin Sketch」和「HyperLogLog」。

Maximum Gap

一串數字,排序之後,相鄰兩數的差值,其中最大的差值稱作「最大間隔」。可能同時有許多個「最大間隔」。

Flashsort可以找出所有最大間隔。時間複雜度O(N)。

一、找到最大值max、最小值min。
二、建立N-1個桶,每個桶的範圍大小是 D = (max-min)/(N-1)。
三、除了最大值、最小值,
  剩下的N-2個數字通通塞入桶,
  數字 x 塞到 floor[(x-min)/D]。
四、N-1個桶,N-2個數字,必有空桶。
  最大間隔的兩數必定跨過空桶,最大間隔大於D。
  最大間隔的兩數不在同一個桶。
五、找到每個桶的最大值bucket[i].max、最小值bucket[i].min。
六、刪除空桶,重新編號。
  max { bucket[i+1].min - bucket[i].max } 即是最大間隔。

Minimum Gap

先排序再搜尋。時間複雜度O(NlogN)或O(N+R)。【尚待確認】

Pairwise Sum

X+Y

窮舉法。O(N²)。

Fourier Transform。O(N + RlogR)。

Sort in X+Y

先窮舉,再排序。O(N²logN²) = O(N²logN)。

先排序,再N-way Merge。O(N²logN)。

Fourier Transform。O(N + RlogR)。

Search in X+Y

先排序。想像矩陣add[i][j] = a[i] + b[j],已排序矩陣的搜尋。O(NlogN)。

Select in X+Y

先排序。想像矩陣add[i][j] = a[i] + b[j],已排序矩陣的選擇。O(NlogN)。

Search in 2D X+Y

找y/x。最差O(Nlog²N),平均Θ(NlogN)。

Select in 2D X+Y

找y/x。Θ(NlogN)。

Extremum in 2D X+Y

找y/x。必在凸包上。Θ(NlogN)。

Pairwise Distance

All Row Minimums

以下介紹三個特殊矩陣,以及其「每一個橫條(直條)的最小值」的演算法。

Monge Matrix ⇒ Totally Monotone Matrix ⇒ Monotone Matrix。從特例到通例,限制從強到弱,數量從少到多,演算法從快到慢。

Monge Matrix (concave)
[standard form] ↖ + ↘ ≤ ↗ + ↙      主對角線和,小於等於次對角線和
     [row form] ↘ - ↙ ≤ ↗ - ↖      橫條各處斜率,往上遞增
  [column form] ↘ - ↗ ≤ ↙ - ↖      直條各處斜率,往左遞增

Totally Monotone Matrix
   [row type] if ↙ ≤ ↘ then ↖ ≤ ↗  橫條小於等於關係,往上遞增
[column type] if ↗ ≤ ↘ then ↖ ≤ ↙  直條小於等於關係,往左遞增

Monotone Matrix
   [row type] argmin ⤷             橫條最小值位置,往下遞增
[column type] argmin ⤵             直條最小值位置,往右遞增

Monge Matrix

矩陣當中所有田字四個格子皆滿足不等式:↖ + ↘ ≤ ↗ + ↙。

不等式分成凹凸兩種,大小相反、性質顛倒。以下以凹為主。

Concave Monge Matrix: a[i][j] + a[i+1][j+1] ≤ a[i][j+1] + a[i+1][j]
 Convex Monge Matrix: a[i][j] + a[i+1][j+1] ≥ a[i][j+1] + a[i+1][j]

另一種等價的寫法:所有子矩形的四個端點皆滿足不等式。

a[i₁][j₁] + a[i₂][j₂] ≤ a[i₁][j₂] + a[i₂][j₁] when i₁ < i₂ and j₁ < j₂

移項一下,得到橫條(直條)斜率遞減的形式。彷彿凹函數。

Monge Matrix乘以非負倍率,仍是Monge Matrix。

Monge Matrix相加,仍是Monge Matrix。

Monge Matrix has "non-negative linearity":
(1) X is Monge Matrix, k ≥ 0   ⇒ kX is Monge Matrix
(2) X and Y are Monge Matrices ⇒ X+Y is Monge Matrix

Monge Matrix刪除橫條(直條),仍是Monge Matrix。

Monge Matrix橫條(直條)加上同一數,仍是Monge Matrix。

Symmetric Monge Matrix = Supnick Matrix。恰好沿著主對角線對稱。

Convex/Concave Monge Matrix = Submodular/Supermodular Function。矩陣行列索引值,視作區間左右邊界。

舉個實際範例。例如二維平面上,凸四邊形上下邊相加 ≤ 兩條對角線相加,距離雙向均等,符合Supnick Matrix不等式。

Supnick Matrix的延伸意義是:不交換最好。例如尋找最佳排列的問題Travelling Salesman Problem、Assignment Problem,若滿足Supnick Matrix,則有高速演算法。

Totally Monotone Matrix

分成凹凸兩種,又細分成橫直兩種,共四種。以下以凹為主。

橫條(直條)一旦出現≤,上方(左方)也都是≤。

concave row version:    if ↙ ≤ ↘ then ↖ ≤ ↗
concave column version: if ↗ ≤ ↘ then ↖ ≤ ↙

自然界難以見到Totally Monotone Matrix,其定義是計算學家故意設計的,是從Monge Matrix的不等式所推導出來的性質。

Monge Matrix ⇒ Totally Monotone Matrix的證明:橫條(直條)斜率遞減的形式當中,若左式非負,則右式也非負。

Monotone Matrix

分成凹凸兩種,又細分成橫直兩種,共四種。以下以凹為主。

每個橫條(直條)的第一個最小值位置,往右(往下)遞增。最小值可能有許多個,所謂的第一個是指索引值最小者。

row version:    argmin r₀ ≤ argmin r₁ ≤ argmin r₂ ≤ ... 
column version: argmin c₀ ≤ argmin c₁ ≤ argmin c₂ ≤ ... 

自然界難以見到Monotone Matrix,其定義是計算學家故意設計的,是從Totally Monotone Matrix的不等式所推導出來的性質。

Totally Monotone Matrix ⇒ Monotone Matrix的證明:因為上方橫條(左方直條)小於等於關係不變,所以最小值位置只可能一樣、或者更往左(更往上)。

尋找Monotone Matrix的每個橫條(直條)的第一個最小值

分治法。找到中央橫條的最小值,然後左上矩陣與右下矩陣,分別遞迴求解。時間複雜度O(YlogX)。

尋找Totally Monotone Matrix的每個橫條(直條)的第一個最小值

限制更強了,擁有更快的演算法。分治法,三個步驟。

一、刪除多餘直條,將X×Y矩陣變成X×X方陣:

把矩陣裡面每一個橫條的第一個最小值圈出來。目標是:砍掉不含第一個最小值的直條。砍到變成方陣即可,不必趕盡殺絕。

任意橫條上面,任取兩個數字a[i][j₁] a[i][j₂],比較大小。如果a[i][j₁] ≤ a[i][j₂],表示右邊數字以上,皆不含第一個最小值。如果a[i][j₁] > a[i][j₂],表示左邊數字以下,皆不含第一個最小值。

沿對角線前進,與右邊數字比較大小。如果a[i][i] ≤ a[i][i+1],那麼姑且繼續前進,累積無效區域,使得上三角矩陣都是無效區域。如果a[i][i] > a[i][i+1],那麼對角線當前數字以下是無效區域,恰好跟先前的無效區域,湊出一整個直條,得以刪除。

二、遞迴求解,以找到偶數橫條的最小值:

偶數橫條合併成一個X/2×X矩陣,遞迴求解。

三、內插夾擠,以找到奇數橫條的最小值:

把矩陣裡面每一個橫條的第一個最小值圈出來,從上往下看,第一個最小值的位置從左往右遞增。用偶數橫條的最小值位置,夾擠出奇數橫條最小值的可能位置,然後窮舉搜尋就行了。

此演算法稱作SMAWK Algorithm。時間複雜度O(X+Y)。

尋找Monge Matrix的每個橫條(直條)的第一個最小值

限制更強了,理應有更簡易的演算法,但是似乎沒人研究?

可以直接使用上述兩個演算法。

UVa 12311