有人可以解釋爲什麼以下LIS算法不是O（n）？

以下代碼遍歷列表一次並找到LIS。我不明白爲什麼DP算法應該採用O（n2）。有人可以解釋爲什麼以下LIS算法不是O（n）？

//C 
int lis(int *a, int l){ 
    if(l == 0) return 1; 
    else if(a[l] > a[l - 1]) return 1 + lis(a, l - 1); 
    else return lis(a, l - 1); 
} 

int main(){ 
    int a[] = { 10, 22, 9, 33, 21, 50, 41, 60 }; 
    cout << lis(a, sizeof(a)/sizeof(a[0]) - 1); 
} 

% erlang 
lis([_H]) -> 1; 
lis([H1, H2 |T]) when H1 > H2 -> 1 + lis([H2|T]); 
lis([_H|T]) -> lis(T). 

main() -> lis(lists:reverse([ 10, 22, 9, 33, 21, 50, 41, 60 ])).

來源

2014-11-21 functional_overflow

也許我誤解了一些東西，但爲什麼你認爲你的erlang實現不是O（n）？ – 2014-11-21 10:42:40

我的c和erlang代碼的複雜性不一樣嗎？根據維基百科和http://goo.gl/R1WHrP，這個問題需要O（n2），它可以改進爲O（n logn）。 – 2014-11-21 10:59:34

您目前的lis/1函數的實現是O（n），我沒有看到任何理由懷疑。但是有一些問題。你的實現並不實際計算有效的LIS。嘗試

lis(lists:reverse([1,2,3,4,1,2]))

錯誤的例子。最長的序列是[1,2,3,4]，對嗎？但是你的算法返回結果6。在你的算法

第一個錯誤，你每次增加result，當你遇到元素比以前大於。但是隻有當前元素大於當前LIS的最大元素時，才應該增加result。因此（根據上面的示例），您應該記住4並且在檢測到之後不會增加result，然後2大於1。
但這不僅僅是你必須要做的事情。考慮序列1 2 3 6 4 5。對於5個第一個元素，LIS的長度爲4.但是有兩個可能的選項 - 1 2 3 4或1 2 3 6。你應該把它當做實際的LIS？
等等，等等...

又如直接來自wiki page.

序列[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]具有LIS [0, 2, 6, 9, 13, 15]（例如，6元素），但你的algorythm說：9。

而且（糾正我，如果我錯了），LIS實現必須返回子序列本身，但不僅僅是它的長度。

來源

2014-11-21 11:04:13

謝謝Viacheslav Kovalev和@Roberto Aloi！你能指出爲什麼它適用於我的例子，而不是所有情況？我認爲，使用上述算法返回子序列以及長度只需要額外的空間而不需要額外的時間。 – 2014-11-21 12:35:19

@functional_overflow，我已更新（實際上，已更正）示例，它可以說明您的算法不當行爲。 – 2014-11-21 12:59:31

謝謝，我明白我的算法是錯誤的。我不明白如何/在哪裏出錯。我希望你能指出我解決方案中的錯誤。 – 2014-11-21 13:43:13

好消息：上面的實現不是二次的。

壞消息：上述函數不計算增加元素的最長子序列（定義爲LIS）。

爲了迴應你的問題，實際的LIS問題具有二次複雜性，而不是DP算法本身，這只是朝着最終解決方案邁出的一步。實際上，對於列表中的所有元素都要重複DP算法（您需要計算所有DP [i]），這就是爲什麼將完整算法歸類爲O（n^2）的原因。

來源

2014-11-21 11:07:42

有人可以解釋爲什麼以下LIS算法不是O（n）？

回答

相關問題