最長公共子序列是否存在低於 O(n^2) 的演算法？

12-29

比如這個問題Problem - 2253，O(n^2)的解法會超時
-----------------------分割線-----------------------
問了下學長，那個題因為字符集比較小可以用位壓縮的技術來優化，不過這個是常數優化，漸進複雜度還是n^2的

起床怒答一發。低於 O(n^2) 的通用方法好像是沒有的（起碼我不知道），雖然大家都是 O(n^2) 的複雜度，但是演算法和演算法之間也是有差距的。普通的DP方法，無論是時間還是空間上，都是非常不優秀的，都是 O(n^2)。

實際上LCS在日常生活中是非常常見的，比如說 diff 本質上就是一個 LCS，只不過 diff 可能會允許近似解。如果真的 LCS 的實現大多是DP（或者某些可能的變種），那麼想想當你 git diff 一個近萬行的程序的時候，那畫面不得太美了？（10000^2 的計算量，得跑一會兒了，並且想想你的內存……）

順著這個思路，注意到就算是你 git diff 了一個近萬行的程序，但是實際上你可能只修改了不到一百行。讀到這裡，細心的讀者一定發現了，衡量一個 diff 演算法的優劣指標不應該僅僅由長度 n 決定，還應該由差異數量 d 決定！

現在廣泛採用的 diff 演算法，也就是題注問的 LCS 演算法，基本上採用的是 Eugene Myers 的論文 An O(ND) Difference Algorithm and its Variations (http://www.xmailserver.org/diff2.pdf) 上面寫的方法的變種，在論文中提到的方法在時間上是很好的，在空間上不知比DP厲害到哪裡去了：

期望的時間複雜度是 O(N + M + D^2)
最壞的時間複雜度是 O((N+M) * D)
可優化成 O((N+M)log(N+M) + D^2)
空間複雜度是 O(N + M)

論文寫得還是很清楚的，跟著看就行了。

另外，如果你真的拿兩個差異很大的文件去 diff ，你會發現它仍然跑得飛快，這就牽扯到很多近似解的方法了，不過這些近似解的方法也都是從這篇論文的方法衍生出去的。因為我沒有去了解，而且也不符合題主的需求，所以就不多提了。有興趣的可以去看看 diffutils 和 libxdiff 的代碼，裡面有寫注釋（其實也只標註了說這是一個 heuristic method ，沒有仔細講為什麼）

我上個學期因為在實現一個 simplified git 所以接觸到了這個東西，看了上面兩個庫的代碼，發現看不懂 T_T 於是只好自己對著論文寫了，有需要的可以看：sit/Diff.cc at master · abcdabcd987/sit · GitHub 只包含了這篇論文裡面的演算法，不包括各種啟發式的近似解，不過實測 O(ND) 的複雜度已經很優秀了。

====== 廣告時間 ======

當時我們有做了個 benchmark 發現我們的 simplified git 的效率稍稍比 git 更高了點，這是我們當時演講的 slides: https://github.com/abcdabcd987/sit/blob/master/report/Presentation.pdf 。

其實我只是來求 star 的：

abcdabcd987/sit · GitHub

====== 2015-12-01 Update ======

剛剛看到@馬融馬老師點了一下贊，瞬間得到了一大堆贊，受寵若驚。

雖然樓主提問是為了刷題，還是來安利一下這類問題的理論結果

「某個P問題是否存在低於某個給定複雜度的演算法」這個問題是目前理論cs領域前沿也很熱門的問題之一，其研究動機也來源於「為什麼我們找不到某些字元串問題的低於O(n^2)的演算法」。

論證「沒有低於xxx的演算法」這方面的進展主要基於SETH（Strong Exponential Time Hypothesis），方法和NP問題的規約相似，即先假設某個問題沒有低於某個多項式時間的演算法（SETH中是k-SAT)，然後把問題規約到它。最近在這個方面做的比較突出的是斯坦福的Virginia Vassilevska Williams和MIT的Arturs Backurs，編輯距離問題和樓主問的LCS都是有一些結果的了。樓主提的LCS的問題相關結論：對於任意?&>0, LCS不存在O(n^(2??))的演算法（注意不是不存在「低於O(n^2) 」的演算法），除非SETH不成立。論文：https://arxiv.org/abs/1501.07053

至於SETH成不成立呢，類似於P?=NP問題，你要是證明了SETH不成立，即使得不了圖靈獎，或許也可以一拼哥德爾獎？

另一方面，也有人在做找某些問題的低於某個多項式時間複雜度的演算法，同樣是斯坦福的Ryan Williams和他的學生－－大家都知道的oi選手俞華程－－最近在這方面有不少結果，給出了許多看似沒有低於O(n^3)演算法的問題的低於O(n^3)的演算法，比如一類所有點對路徑問題的O(n^3/((log n)^k))的演算法，思路是從電路複雜性Circuit Complexity裡面的結論開始，得到矩陣問題相關的低複雜度的演算法，然後把原問題轉化為操作矩陣的問題。

所以對於LCS，目前的結論是除非SETH不成立，否則不存在n的冪次上更低的演算法（比如nlogn這種）－－當然這和刷題有沒有更快的演算法毫無關係－－但也歡迎搞oi出身的小朋友加入理論研究。

若字符集為常數，則可低於O(MN)

設字符集為C, 將動態規劃中n*n的矩陣拆分（n/t）^2個t＊t的小矩陣,其中t為1/2*log以c為底n，在預處理中小矩陣有c^2t種，每個小矩陣需要t^2時間計算，所以預處理需要o(n(logn)^2)，這樣每個可能的小矩陣的結果都已經計算完

最後針對n＊n大矩陣中的每個t＊t小矩陣填入返回值（由於小矩陣的返回值僅與它上面和左面邊上的值有關，因此檢查每個小矩陣的時候僅需要輸入上面和左面邊上的值，也只需要返回下面後右面邊上的值，這四條邊都是O(t），因此檢查一個小矩陣也需要O(t）)

因為總共需要檢查（n/t）^2個小矩陣,檢查一個小矩陣需要O(t）,最後得到右下角的值就需要（n/t）^2＊t=(n^2)/t = O((n^2)/logn)，小於O(MN)

似乎沒聽說過嚴格小於 O(n^2) 的演算法，但是存在一般情況下 O(n log n) 的演算法。

對於 A，B 兩個串，將 A 中每個字元替換成在 B 中間出現的位置的逆序列，例如原串為

A="abacd"

B="cabbab"

字元 "a" 在 B 中出現的位置為 2, 5，字元 "b" 在 B 中出現的位置為 3, 4, 6，字元 "c" 出現的位置為 1，字元 "d" 沒有出現。那麼 A 序列將被替換成為

(5, 2), (6, 4, 3), (5, 2), (1), (?)

每一個括弧代表原來的 A、B 兩串相同字元的匹配，如下圖：

但是匹配必須是遞增的，也就是每個括弧里選一個數，選出的數必須遞增。將括弧里的數反序排列是為了方便限制「每個括弧里選一個數」的條件。

這是 LCS（最長公共子序列）到 LIS（最長遞增子序列）的經典轉化。只需要找到「(5, 2), (6, 4, 3), (5, 2), (1), (?)」裡面的遞增子序列即可。

對於長度為 n 的最長遞增子序列，存在基於動態規劃的嚴格 O(n log n) 演算法，這個可以自己搜索。

但是 A → (5, 2), (6, 4, 3), (5, 2), (1), (?) 這一步，序列變長了，一般來說不會退化，整個演算法還是約為 O(n log n) 的。

但是 A="aaaaa" B="aaaaaa" 這樣的數據就會退化成 O(n^2 log n)。

一般採用動態規劃的時間複雜度為O(MN)，沒有見過比這個效果更好的。

謝邀，lcs問題O(mn)是下界了，如果數據特殊，可以有針對性的優化，同樣推薦這個帖子。

=@noticeHeader =@@answer.user.name 關於 =@@answer.question.title 的回答

我記得可以壓位

但是還是n ^ 2 / 32的

試試這個100000的兩個串，求最長公共子序列，時限1s，求教

非特殊情況的話n^2基本是理論最好了，頂多差一些log項

最長公共子序列(nlogn)

(1) 對序列B排序

(2) 計算A中每個元素在B中的序號，並構成新序列

(3) 使用LIS的方法計算最長嚴格遞增子序列

(4) 獲取最長公共子序列

這種演算法怎麼樣？

我試過用於計算兩個01組成的字元串，發現結果不太對。求知友一起探討下

預處理一下，將A中的元素換為B中的對應下標，然後求LIS，複雜度就是NlogN了