Time complexity for a sublist in Python

2019-06-21 04:32发布

问题:

In Python, what is the time complexity when we create a sublist from an existing list?

For example, here data is the name of our existing list and list1 is our sublist created by slicing data.

data = [1,2,3,4,5,6..100,...1000....,10^6] 
list1 = data[101:10^6]

What is the running time for creating list1?

Is it O(10^6) i.e.O(N), or O(1)?

回答1:

Getting a list slice in python is O(M - N) / O(10^6 - 101)

Here you can check python list operations time complexity

By underneath, python lists are represented like arrays. So, you can iterate starting on some index(N) and stopping in another one(M)