Sort

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

Sort

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

實際要做排序,有兩個方向,一是將數字放入循序性資料結構(例如array與list),然後執行下述其中一種排序演算法。二是使用有排序功效的資料結構,例如binary heap、binary search tree,將數字整個倒進去、整個倒出來即排序完畢。

               | best     average  worst    | extra | stable
               | case     case     case     | space |
---------------+----------------------------+-------+--------
brute force    | O(NR)    O(NR)    O(NR)    | O(N)  | O
selection sort | O(NN)    O(NN)    O(NN)    | O(1)  | X
bubble sort    | O(N)     O(NN)    O(NN)    | O(1)  | O
gnome sort     | O(N)     O(NN)    O(NN)    | O(1)  | O
insertion sort | O(N)     O(NN)    O(NN)    | O(1)  | O
Shell sort     | O(NN)    O(NN)    O(NN)    | O(1)  | X
merge sort     | O(NlogN) O(NlogN) O(NlogN) | O(N)  | O
quicksort      | O(NlogN) O(NlogN) O(NN)    | O(N)  | X
heapsort       | O(NlogN) O(NlogN) O(NlogN) | O(1)  | X
counting sort  | O(N+R)   O(N+R)   O(N+R)   | O(R)  | O
bucket sort    | O(N+B+?) O(N+B+?) O(N+B+?) | O(B)  | X
radix sort     | O(ND)    O(ND)    O(ND)    | O(D)  | O

除了數字可以排序之外,事實上字元也可以排序,因為電腦中的字元就是數字(請參照ASCII表)。指標也可以排序,因為指標就是記憶體位址也就是數字。一般資料也可以排序,只要資料裡的某個特定欄位是數字,這個欄位被稱作鍵值(key)。

排序原理

排序的基本原理,當今只有兩種,一是對調(數字是實數),二是放置(數字必須是整數)。

純粹透過對調來排序,已證明出數字兩兩比較的次數是Ω(NlogN),不可能更少了,當今也已經有了到達下限的排序演算法,例如merge sort。同時透過對調與放置來排序,則可以打破方才的下限,例如flashsort。

純粹透過放置來排序,需要額外的記憶體空間來放置數字。時間複雜度通常是數字數量加上記憶體用量,效率相當好,只可惜只能處理整數,例如counting sort。

暴力搜尋

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

令陣列最小值為A,最大值為B。令A和B之間的整數有R個,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是一個人名,是發明這個演算法的人,不是殼的意思。

運用Scaling Method:以固定間隔取得數字做為一組,各組各自做Insertion Sort;然後減少間隔大小,重複上述動作。

Merge Sort

運用Divide and Conquer:Divide是陣列分兩半;Conquer是兩半分別排序;Combine是兩半各自排序好的陣列,弄成一條排序好的陣列。

可以直接使用STL的stable_sort()。

UVa 10810

Quicksort

運用Divide and Conquer:Divide是選定pivot,把pivot挪到陣列邊緣,然後把陣列分成大的一邊和小的一邊;Conquer是兩邊分別排序;Combine不做任何事。

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

固定選擇最後一個數字當作pivot,也有機會把陣列分成兩等份。但是這卻產生一個古怪的現象:遇到已經排序的陣列,卻會變成每次都沒有分到,時間複雜度變成O(N²),超級慢。

結果導致Quicksort有時快、有時卻很慢,遇到幾乎排序好的陣列,更是慢到吐血。時快時慢,該快不快,那不是很莫名其妙嗎?

為了避免這種情況,可以每次都用亂數指定pivot,這樣不管給定陣列是有排序的或是沒排序的,兩等份的機會都一樣多,如此就比較不會出現前述的古怪情形。不過這又衍生出一個問題,只是想做個排序,卻還得載入亂數模組,耗損系統資源、拖慢系統速度,帶來了新的壞處。

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

Quicksort演算法的陷阱相當多,須考慮數字全都相等、判斷式是小於還是小於等於、分割點恰好選到最大值或者最小值、遞迴的區段範圍、遞迴的區段很短、……等等問題。編寫Quicksort的程式碼時,最好是寫一支窮舉所有排列的程式,一一排序、一一驗證。如果擔心自己寫的程式碼用在正事上不妥當,也可以採用程式語言函式庫內建的Quicksort。

UVa 755

© 2010 tkcn. All rights reserved.

Heapsort

陣列可以做為二元樹資料結構。把陣列本身當作是heap,逐一把數字加入heap,達到排序功效。

Introsort

Quicksort的加強版。遞迴分割陣列,區間越來越短,數字也幾乎排序好了。對於幾乎已經排序好的區間,Quicksort效率非常差,所以改用Heapsort。

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

可以直接使用STL的sort()。

Counting Sort

全部數字依其數值大小,放到相符位置。接著由小到大讀取各個位置的數字。

UVa 484 11462

Bucket Sort

全部數字依其數值區間,放到相符桶子。接著各個桶子各自排序之後,再由小到大讀取各個桶子的數字。

Radix Sort

由低位數到高位數,每個位數依序做為鍵值,做D次counting sort,D為位數大小。

資料是數字,數字表示成二進位,D = logR。

Flash Sort

http://www.cnblogs.com/kkun/archive/2011/11/24/2261529.html

延伸閱讀:以指標排序

排序會搬動資料,但是大多數時候我們不希望搬動資料。此時可以取出資料的記憶體位址,存入指標,對指標進行排序。

也有人以索引值排序,道理跟指標相同。

UVa 482

延伸閱讀:stable

兩筆相同資料,原本排在前頭的,排序後仍在前頭;原本排在後頭的,排序後仍在後頭。這稱作stable的排序演算法,相同資料、順序不變。

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

延伸閱讀:lexicographical order

當資料是高維度數據,如何比較大小呢?其中一種方式叫做字典順序,先比較第一維度;如果平手,再比較第二維度;如果又平手,再比較第三維度;以此類推。

英文字典,即採用了字典順序,排序所有英文單字。英文字典當中,兩個英文單字比較大小的方式,就是字典順序。

延伸閱讀:Sorting Network

UVa 1117

Search

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

Search

搜尋。在資料結構當中,找出一個東西的位置。

常與Search相提並論的有Sort:在資料結構當中,把所有東西排好順序,放在正確位置。另外還有Select:在資料結構當中,找到特定順位的資料。

資料結構千變萬化,各有其獨特的Search、Sort、Select演算法。在陣列中,便有Binary Search、Bubble Sort、Quickselect這些演算法;在圖論中,則有Depth-first Search這樣的演算法。

甚至也有專為Search、Sort、Select而設計的資料結構,如各種Priority Queue、各種Search Tree、Hash Table、……等等。

Search in Array: Sequential Search

循序搜尋。依序看一遍,無一遺漏。時間複雜度是O(N)。

Search in Sorted Array: Binary Search

二元搜尋。相信各位耳熟能詳。這裡只作重點歸納。

Binary Search的功用,是在一個排序過的數列(遞增數列、遞減數列)當中,找出某個數字的索引值(index)。

基本原理是Divide and Conquer。當資料存放在陣列──Binary Search是將一個將排序好的陣列,分為大的一邊和小的一邊,再看看我們要找的元素會在哪一邊。如此下去直到找到為止。分割的時候,也是採用對半分,時間複雜度是O(logN),以2為底的logN。

我想大家最好自己重新寫一份,並且驗證它在任何情形下,結果都是正確無誤的,而不會有超出陣列範圍的結果。另外也請看看這篇文章:Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

上面這支程式亦可改用遞迴寫出來,不妨試試。

資料往往都是排序整齊的,也因此,Binary Search常被用來加速程式。一旦看到數據資料有排序、遞增遞減、成正比反比的時候,便要想到Binary Search。

還有一種常見的應用是:資料恰有兩種性質,明顯地分做兩邊──想找到分界之處,便可以用Binary Search。

很多問題其實都隱含著上述這種性質,只是不容易發現。嘗試從問題當中發掘這種性質,並且寫程式解決問題,這便是程式設計深奧且有趣之處。

UVa 10611 10077

Search in Sorted Array

Interpolation Search」、「Fibonacci 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

http://en.wikipedia.org/wiki/Fractional_cascading

Search in Sorted Matrix: Saddleback Search

一個排序過的陣列可以用Binary Search來搜尋數字,那麼一個排序過的二維矩陣呢?當一個二維矩陣裡的元素經過排序,任一位置往右、往下都呈現嚴格遞增時(嚴格遞減也行),此時有個很巧妙的搜尋方式,時間複雜度為O(X+Y),X與Y分別為矩陣的長與寬。

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

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

UVa 12192

Search in Sorted Matrix: 2D Binary Search

只有特殊情況能派上用場。

一個排序過的陣列可以用Binary Search來搜尋數字,那麼一個排序過的二維矩陣呢?

搜尋已排序陣列,都是切對半、從中位數切成兩半。搜尋已排序矩陣,亦可如法炮製,從中位數們的中位數(中中數)切成兩半。

矩陣切成一條一條陣列,找到中中數;實施Saddleback Search,以中中數將矩陣分為大的一邊和小的一邊,遞迴找其中一邊。

時間複雜度分析:

一、每一條陣列(已排序),各自找到中位數,總共O(Y)。

二、中位數們(未排序),找到中位數,使用後面章節的演算法,O(X)。

三、Saddleback Search,O(X+Y)。

四、小於等於中中數的數字們,至少佔1/4。大於等於亦如是。遞迴找其中一邊,至少刪1/4、至多剩3/4。總共O(logXY)回合。

每回合的時間複雜度為O(X+Y),總共O(logXY)回合,總時間複雜度為O((X+Y)logXY)。

時間複雜度難以記憶。簡易的方式,是把X和Y視作相等,等於N。每回合需時O(N),總共O(logN²) = O(2logN) = O(logN)回合,總時間複雜度為O(NlogN)。

此演算法沒有實務上的價值,只有理論上的價值,而且只有特殊情況能派上用場:資料恰有兩種性質,明顯地分做兩邊──想找到分界之處。Saddleback Search每一步都要判斷在哪一邊,總共判斷O(N)次。2D Binary Search每一回合只需判斷中中數在哪一邊,總共判斷O(logN)次。

Select

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

Select

選擇。找到特定名次的數字,例如第k小、第k大的數字。或者,找到特定數字的名次。

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

UVa 10041 10107 11875

Select in Array: Quickselect

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

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)。

可以直接使用STL的nth_element()。

Select in Sorted Array

O(1)。

Select in Sorted Arrays

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

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

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

Select in Sorted Arrays

找到中位數們的中位數,找到最大中位數、最小中位數。最小中位數至少小於一半的數字,最大中位數亦如是。判斷第K大是小於一半或大於一半,每回合削減最大中位數的右半或最小中位數的左半。每次刪除一列的一半,總共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

http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf

Divide and Conquer。O(N)。

Count

選出牡丹第一枝,勸君折取莫遲疑,世間若問相知處,萬事逢春正及時。《六十甲子籤》

Longest Plateau

一條數列,找到連續出現最多次的數字暨次數。

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

Mode

一條數列,找到出現最多次的數字暨次數。

先排序再搜尋。採用交換式排序,例如quicksort或者merge sort,時間複雜度O(NlogN),額外的空間複雜度O(1)。採用索引式排序,例如counting sort或者hash table,時間複雜度O(N+R),額外的空間複雜度O(R)。

Majority Vote

一條數列,找到出現過半的數字暨次數。時間複雜度O(N),額外的空間複雜度O(1)。

Maximum Gap

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

時間複雜度O(N),不必排序,就能找出所有最大間隔。但是前提是floor運算是O(1)。

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

Minimum Gap

一串數列當中,找到相差最小的兩個數字。

給定一串未排序數列,排序之後,考慮相鄰兩數的差值,其中最小的差值稱作「最小間隔」。一條數列可能同時有許多個「最小間隔」。

時間複雜度O(NlogN)。

【待補文字】

Count Distinct

一串數列當中,找到相異數字個數。

http://ravi-bhide.blogspot.tw/2011/04/flajolet-martin-algorithm.html

https://chenjiehua.me/database/hyperloglog-bigdata.html

末一位可能是0/1,如果都出現,答案至少2
末二位可能是00/01/10/11,如果都出現,答案至少4

【待補文字】

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

http://arxiv.org/abs/0809.1171

找y/x。最差O(NlogNlogN),平均Θ(NlogN)。

Select in 2D X+Y

http://arxiv.org/abs/0809.1171

找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、Bipartite Matching,若滿足Supnick Matrix,則有快速演算法。

Totally Monotone Matrix

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

橫條往左(直條往上),<與=的總數量遞增。只會增加或不變、不會減少。

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

還有另一種更嚴格的定義:≤的數量遞增。

concave row version:    (if ↙ < ↘ then ↖ < ↗) and
                        (if ↙ = ↘ then ↖ ≤ ↗)
concave column version: (if ↗ < ↘ then ↖ < ↙) and
                        (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