已知子任务复杂度的算法复杂度

Question

动态规划算法的输入是单个，n长序列。该算法考虑了序列所有可能的子串，对于第k个长子串，在O(k)时间内计算出一个值。

我想知道是否有人告诉我如何估计这个算法的运行时间。

Answer 1

好的，让我们开始吧。

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

好的，所以对于长度为 n 的字符串，我们有 2 个长度为 n-1、3 长度为 n-2 的子字符串，.. ., n 长度 1.

Complexity of the algorithm with known complexity of the subtasks