如何优化输出列表连续子序列的O(N^3)三重for循环，获得更低时间复杂度

原代码问题分析 #

原代码使用三层嵌套循环，第三层循环每次从头遍历区间[i,j]构建子序列，是时间复杂度达到O(N³)的核心原因，同时原代码存在语法问题：第一层for语句末尾缺失冒号、第三层循环缩进错误。

优化方案 #

我们可以通过复用子序列的构建过程直接砍掉第三层循环，将时间复杂度降低到理论最优的O(N²)：

• 每次启动以第i个元素为起点的子序列遍历时，初始化一次空子序列
• 内层遍历终点j时，直接将当前j位置的元素追加到已有子序列末尾，即可得到以i为起点、j为终点的连续子序列，无需重新遍历构建

优化后代码 #

arr = [0,1,2,3,4,5,6,7,8,9]
n = len(arr)
for i in range(n):
    subseq = []
    for j in range(i, n):
        subseq.append(arr[j])
        print(subseq)

进一步优化（降低常数耗时） #

如果只需要输出逗号分隔的字符串格式，不需要保留列表类型的子序列，可以直接做字符串拼接，避免列表转字符串的额外开销：

arr = [0,1,2,3,4,5,6,7,8,9]
n = len(arr)
for i in range(n):
    current_output = ""
    for j in range(i, n):
        if j > i:
            current_output += ","
        current_output += str(arr[j])
        print(current_output)

复杂度说明 #

长度为N的列表，连续子序列的总数量为N*(N+1)/2，所有子序列的元素总个数为O(N²)，这是输出所有连续子序列的理论最低时间复杂度，上述优化方案已经达到了这个下限。 #

内容的提问来源于stack exchange，提问作者Fernando Swenson