My for loop prints all the consecutive subsequence of a list. For example, suppose a list contains [0, 1,2,3,4,5,6,7,8,9]. It prints,

• 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)

The current algorithmic complexity of this for loop is O(N^3). Is there any way to make this algorithm any faster?

CodePudding user response：

I don't know Python (this is Python, right?), but something like this will be O(N^2):

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

Yes, that works:

[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]

CodePudding user response：

It’s not possible to do this in less than O(n³) time because you’re printing a total of O(n³) items. Specifically, split the array in quarters and look at the middle two quarters of the array. Pick any element there - say, the one at position k. That will be printed in at least n² / 4 different subarrays: pick any element in the first quarter, any element in the last quarter, and the subarray between those elements will contain the element at position k.

This means that any of the n / 2 items in the middle two quarters gets printed at least n² / 4 times, so you print at least n³ / 8 total values. There’s no way to do that in better than O(n³) time.