41
tôi đang viết một hàm python mà nhìn một cái gì đó như thế nàyĐộ phức tạp thời gian chạy của các hàm danh sách python là gì?
def foo(some_list):
for i in range(0, len(some_list)):
bar(some_list[i], i)
để nó được gọi với
x = [0, 1, 2, 3, ... ]
foo(x)
tôi đã giả định rằng truy cập chỉ mục của danh sách là O(1), nhưng rất ngạc nhiên khi thấy rằng cho các danh sách lớn, điều này chậm hơn đáng kể so với dự kiến của tôi.
Câu hỏi của tôi, sau đó, là như thế nào là danh sách python được thực hiện, và mức độ phức tạp thời gian chạy các nội dung sau
- Indexing là gì:
list[x] - Popping từ cuối cùng:
list.pop() - Popping từ bắt đầu:
list.pop(0) - Mở rộng danh sách:
list.append(x)
Để có thêm tín dụng, ghép nối hoặc tùy ý bật lên.
Tha thứ cho sự thiếu hiểu biết của tôi, nhưng đâu là sự phức tạp của 'pop()' trên trang đó? – Zaz
@Zaz, pop() không có chỉ mục là O (1), với chỉ mục, ví dụ: đầu tiên trong danh sách, nó là O (n). vì bạn cần lấy mục O (1) và sau đó xóa nó. Sau đó có thời gian O (n) để sắp xếp tất cả các mục khác trong danh sách. Thêm thông tin về điều đó tại đây: https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt –