Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
608 views
in Technique[技术] by (71.8m points)

python - Does insert at the end of a list have O(1) time complexity?

Is there a difference between append and insert at the end of a list? Is insert at the end of a list a constant time operation?

nums = [1, 2, 3]
nums.append(4)  # Time complexity: O(1)
nums.insert(len(nums), 5)  # Time complexity: O(?)

According to the TimeComplexity article in the Python Wiki, the average case for append is O(1), while the average case for insert is O(n). However, in the Python tutorial, it is mentioned that:

... and a.insert(len(a), x) is equivalent to a.append(x).

I'm unsure if "equivalent" there means "equivalent in functionality" or "equivalent in time complexity". Does anyone know?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Worst time complexity for inserting into list is O(n-i), where n is the length of the list and i is the index at which you are inserting.

So in case if you are inserting at the last index, that makes it O(1).

Here is an article that might help you understand better :

https://yourbasic.org/algorithms/time-complexity-arrays/.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...