具有已知子任務複雜度的算法的複雜性

Question

動態規劃算法的輸入是單個n長的序列。算法考慮序列的所有可能的子串，並且對於k長子串，它計算O（k）時間中的值。

我在想如果有人告訴我怎麼估計這個算法的運行時間。

Answer 1

好吧，讓我們在挖。

7  abcdefg 
6  abcdef 
6  bcdefg 
5  abcde 
5  bcdef 
5  cdefg 
. 
. 
. 

OK，所以對於長度n的字符串，我們有2子長度n-1的，長度n-2的3，...，長度1的n。