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

比如這個問題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了


推薦閱讀:

遺傳演算法相對於窮舉演算法可以減少多少計算量?
圍棋有沒有必勝策略?
怎樣判斷平面上一個矩形和一個圓形是否有重疊?

TAG:演算法 | 演算法設計 | 演算法複雜度 | ACM競賽 | 子序列問題 |