Độ phức tạp tiệm cận của List.Add là gì?

Question

Tôi thấy rằng có rất nhiều tranh cãi về sự phức tạp tiệm cận của List.Add(). Nguồn của nó tôi nghi ngờ là trường hợp xấu nhất kịch bản that causes underlying array to resize và sẽ hợp lý là hoạt động O(n). Tuy nhiên, array grows twice in size mỗi danh sách thời gian hết dung lượng. Điều đó làm cho số lượng thay đổi kích thước cần thiết cho các yếu tố n tỷ lệ thuận với log(n).

Điều đó không có nghĩa là sự phức tạp tiệm cận của hoạt động Add trong trường hợp trung bình sẽ là O(n/log(n))?

Điểm chuẩn thực sự cho List.Add() ở bên dưới. Tuy nhiên, điểm chuẩn không thực sự biểu cảm cho hoạt động như vậy - chúng tôi có thể hết bộ nhớ trước khi bất kỳ độ lệch nào từ đường thẳng (trong thang logarit) trở nên hiển thị.

Answer 1

Điều này có nghĩa rằng amortized complexity của List.Add() thể được tính toán bằng cách tổng hợp các hoạt động thay đổi kích thước và sau đó nhân cho tổng số lượng bổ sung được thực hiện vào danh sách.

T(n) = (2 + 4 + 8 + ... + n/2 + n)/n 

Nhưng lưu ý rằng tổng là một geometric series, và chúng tôi có thể làm tốt hơn so với giả định đó là (tổng) n*log(n):

T(n) < 2n/n = 2 -> T(n) is in O(1) 

---

Lưu ý: Ở đây tôi giả sử bạn có nghĩa là add() như phụ thêm . Chèn một phần tử vào một vị trí tùy ý mất O(n) thời gian, và bạn cũng sẽ phải tính đến điều đó, điều này sẽ thay đổi kết quả cuối cùng từ O(1) phức tạp phân bổ thành O(n) phức tạp phân bổ.