如何比 O(N^3) 更快地优化这个 for 循环？

Question

我的 for 循环打印列表的所有连续子序列。例如，假设一个列表包含 [0, 1,2,3,4,5,6,7,8,9]。它打印，

• 0
• 0,1
• 0,1,2
• 0,1,2,3
• .......
• 0,1,2,3,4,5,6,7,8,9
• 1
• 1,2
• 1,2,3
• 1,2,3,4,5,6,7,8,9
• .......
• 8
• 8,9
• 9

for i in range(10)
    for j in range(i, 10):
        subseq = []
            for k in range(i, j+1):
                subseq.append(k)
        print(subseq)

目前这个for循环的算法复杂度是O(N^3)。有什么方法可以让这个算法更快吗？

Answer 1

我不知道 Python（这是 Python，对吧？），但是像这样的东西会是 O(N^3) 的一个更快的版本（见下面的评论）：

for i in range(10):
    subseq = []
    for j in range(i, 10):
        subseq.append(j)
        print(subseq)

是的，行得通：

[0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1]
[1, 2] 
...
[7, 8]
[7, 8, 9]
[8]
[8, 9]
[9]

Answer 2

不可能在少于 O(n³) 的时间内完成此操作，因为您总共要打印 O(n³) 项。具体来说，把数组分成四分之一，看中间的四分之二的数组。选择那里的任何元素 - 例如，位置 k 的那个。这将打印在至少 n² / 4 个不同的子数组中：选择第一季度的任何元素，最后四分之一的任何元素，这些元素之间的子数组将包含元素位置 k.

这意味着中间两个季度的 n / 2 项中的任何一项至少打印 n² / 4 次，因此您至少打印 n³ / 8 个总值。没有比 O(n³) 时间更好的方法了。