Tại sao độ phức tạp của phương thức list.append() của python là O (1)?

Question

Như đã thấy trong tài liệu cho TimeComplexity, loại list của Python được triển khai đang sử dụng một mảng.

Vì vậy, nếu một mảng đang được sử dụng và chúng tôi thực hiện một vài phụ, cuối cùng bạn sẽ phải phân bổ lại không gian và sao chép tất cả thông tin vào không gian mới.
Sau tất cả, làm thế nào nó có thể là O (1) trường hợp xấu nhất?

Answer 1

Nếu bạn nhìn vào chú thích trong tài liệu bạn liên kết, bạn có thể thấy rằng chúng bao gồm một caveat:

Các hoạt động này dựa trên "khấu hao" một phần của "khấu hao tệ nhất Case". Các hành động riêng lẻ có thể mất nhiều thời gian, tùy thuộc vào lịch sử của vùng chứa.

Sử dụng amortized analysis, ngay cả khi chúng tôi thỉnh thoảng thực hiện các hoạt động đắt tiền, chúng tôi có thể bị ràng buộc thấp hơn về chi phí hoạt động 'trung bình' khi bạn coi chúng là một chuỗi thay vì riêng lẻ. Vì vậy, bất kỳ hoạt động cá nhân có thể rất tốn kém - O (n) hoặc O (n^2) hoặc một cái gì đó lớn hơn - nhưng vì chúng ta biết các hoạt động này rất hiếm, chúng tôi đảm bảo rằng một chuỗi các hoạt động O (n) có thể được thực hiện trong thời gian O (n).

Answer 2

Nó được phân bổ O (1), không phải O (1).

Giả sử kích thước dành riêng cho danh sách là 8 phần tử và kích thước tăng gấp đôi khi không gian hết. Bạn muốn đẩy 50 phần tử.

8 yếu tố đầu tiên đẩy vào O (1). Các nineth gây ra tái phân bổ và 8 bản sao, tiếp theo là một O (1) đẩy. Tiếp theo 7 đẩy trong O (1). Thứ mười bảy gây ra tái phân bổ và 16 bản sao, tiếp theo là một O (1) đẩy. 15 lần đẩy tiếp theo trong O (1). Trình kích hoạt lại ba mươi ba và 32 bản sao, tiếp theo là một cú đẩy O (1). Tiếp theo 17 đẩy trong O (1).

Vì vậy, tất cả các cú đẩy có độ phức tạp O (1), chúng tôi có 56 bản sao tại O (1) và 3 đường dẫn tại O (n), với n = 8, 16 và 32. Lưu ý rằng đây là chuỗi hình học và asymptotically bằng O (n) với n = kích thước cuối cùng của danh sách. Điều đó có nghĩa là toàn bộ hoạt động của việc đẩy các đối tượng n vào danh sách là O (n). Nếu chúng tôi khấu hao cho mỗi phần tử, đó là O (n)/n = O (1).

Answer 3

Thời gian chi phí phụ thêm vào một danh sách

Các nhà thiết kế của Python sử dụng một ý tưởng rất thông minh để đảm bảo rằng đây trường hợp xấu nhất thời gian chạy cho phụ thêm vào danh sách xảy ra thường xuyên. Chúng ta vừa thấy rằng khi Python gắn thêm vào một danh sách hiện có và hết dung lượng, nó phải yêu cầu một bộ nhớ mới, nơi nó sẽ di chuyển danh sách.

Giả sử độ dài danh sách là n. Nhưng thay vì yêu cầu đủ không gian cho danh sách size n + 1, Python sắp xếp để có chỗ cho danh sách mới phát triển và yêu cầu không gian cho danh sách size 2n. Việc phân bổ theo cách này có vẻ như là nó lãng phí rất nhiều không gian — Python phân bổ tối đa twice lượng bộ nhớ mà danh sách thực sự cần. Nhưng lợi thế là nếu bạn nối thêm các mục vào danh sách lặp đi lặp lại, danh sách sẽ được di chuyển không thường xuyên.