具有已知子任务复杂度的算法的复杂性

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。