Kiểu dữ liệu python độ phức tạp o lớn

Bây giờ bạn đã hiểu chung về ký hiệu O lớn, chúng ta sẽ dành thời gian thảo luận về hiệu suất O lớn cho các hoạt động được sử dụng phổ biến nhất được hỗ trợ bởi danh sách và từ điển Python. Hiệu quả của những kiểu dữ liệu này rất quan trọng vì chúng ta sẽ sử dụng chúng để triển khai các cấu trúc dữ liệu trừu tượng khác trong phần còn lại của cuốn sách này

Phần này nhằm cung cấp cho bạn một số hiểu biết trực quan về lý do tại sao các màn trình diễn lại như vậy, nhưng bạn sẽ không đánh giá đầy đủ những lý do này cho đến sau này, khi chúng ta khám phá cách các danh sách và từ điển có thể được triển khai

Hãy nhớ rằng có sự khác biệt giữa ngôn ngữ Python và triển khai Python. Cuộc thảo luận của chúng tôi dưới đây giả định việc sử dụng triển khai CPython

danh sách

Các nhà thiết kế kiểu dữ liệu danh sách Python có nhiều lựa chọn để thực hiện trong quá trình triển khai. Mỗi lựa chọn ảnh hưởng đến tốc độ danh sách có thể thực hiện các thao tác. Một quyết định mà họ đưa ra là tối ưu hóa việc triển khai danh sách cho các hoạt động chung

Lập chỉ mục & Chỉ định

Hai hoạt động phổ biến là lập chỉ mục và gán cho một vị trí chỉ mục. Trong danh sách Python, các giá trị được gán và truy xuất từ ​​các vị trí bộ nhớ cụ thể, đã biết. Cho dù danh sách có lớn đến đâu, việc tra cứu chỉ mục và chỉ định sẽ mất một lượng thời gian không đổi và do đó O(1)O(1)O(1)

Một nhu cầu lập trình phổ biến khác là phát triển một danh sách. Có hai cách để làm điều này. you can use the append method or the concatenation operator (+)

Phương pháp append được “khấu hao” O(1)O(1)O(1). Trong hầu hết các trường hợp, bộ nhớ cần thiết để nối thêm một giá trị mới đã được cấp phát, đúng là O(1)O(1)O(1). Khi mảng C bên dưới danh sách đã hết, nó phải được mở rộng để chứa thêm các append. Quá trình mở rộng định kỳ này là tuyến tính so với kích thước của mảng mới, điều này dường như mâu thuẫn với tuyên bố của chúng tôi rằng appending là O(1)O(1)O(1)

Tuy nhiên, tỷ lệ mở rộng được chọn khéo léo là gấp ba lần kích thước trước đó của mảng;

Mặt khác, phép nối là O(k)O(k)O(k), trong đó kkk là kích thước của danh sách được nối, vì các hoạt động gán tuần tự kkk phải xảy ra

Bật, dịch chuyển và xóa

Xuất hiện từ danh sách Python thường được thực hiện từ cuối, nhưng bằng cách chuyển một chỉ mục, bạn có thể xuất hiện từ một vị trí cụ thể. Khi pop được gọi từ cuối, thao tác là O(1)O(1)O(1), trong khi gọi pop từ bất kỳ nơi nào khác là O(n)O(n)O(n). Tại sao sự khác biệt?

Khi một mục được lấy từ phía trước danh sách Python, tất cả các phần tử khác trong danh sách sẽ được dịch chuyển một vị trí gần đầu hơn. Đây là chi phí không thể tránh khỏi để cho phép tra cứu chỉ mục O(1)O(1)O(1), đây là thao tác phổ biến hơn

Vì những lý do tương tự, việc chèn vào một chỉ mục là O(n)O(n)O(n); . Không có gì đáng ngạc nhiên, việc xóa hoạt động theo cùng một cách

lặp lại

Phép lặp là O(n)O(n)O(n) vì phép lặp qua nnn phần tử yêu cầu nnn bước. Điều này cũng giải thích tại sao toán tử in trong Python là O(n)O(n)O(n). để xác định xem một phần tử có trong danh sách hay không, chúng ta phải lặp qua từng phần tử

cắt lát

Thao tác cắt lát đòi hỏi nhiều suy nghĩ hơn. Để truy cập lát cắt +0 của danh sách, chúng ta phải lặp qua mọi phần tử giữa các chỉ số +1 và +2. Vì vậy, truy cập lát cắt là O(k)O(k)O(k), trong đó kkk là kích thước của lát cắt. Xóa một lát là O(n)O(n)O(n) vì lý do tương tự như xóa một phần tử là O(n)O(n)O(n). nnn phần tử tiếp theo phải được chuyển về đầu danh sách

nhân

Để hiểu phép nhân danh sách, hãy nhớ rằng nối là O(k)O(k)O(k), trong đó kkk là độ dài của danh sách nối. Theo đó, phép nhân một danh sách là O(nk)O(nk)O(nk), vì phép nhân một danh sách có kích thước kkk nnn lần sẽ cần thêm k(n−1)k(n - 1)k(n−1)

đảo chiều

Đảo ngược danh sách là O(n)O(n)O(n) vì chúng ta phải định vị lại từng phần tử

Sắp xếp

Cuối cùng (và ít trực quan nhất), sắp xếp trong Python là O(nlogn)O(n\log{n})O(nlogn) và nằm ngoài phạm vi của cuốn sách này để chứng minh

Để tham khảo, chúng tôi đã tóm tắt các đặc điểm hiệu suất của các thao tác danh sách của Python trong bảng bên dưới

OperationBig O Efficiencyindex []O(1)O(1)O(1)index assignmentO(1)O(1)O(1)appendO(1)O(1)O(1)pop()O(1)O(1)O(1)pop(i)O(n)O(n)O(n)insert(i, item)O(n)O(n)O(n)del operatorO(n)O(n)O(n)iterationO(n)O(n)O(n)contains (in)O(n)O(n)O(n)get slice [x. y]O(k)O(k)O(k)del sliceO(n)O(n)O(n)đảo ngượcO(n)O(n)O(n)nối (k)O(k)O(k)

từ điển

Kiểu dữ liệu Python chính thứ hai là từ điển. Như bạn có thể nhớ lại, từ điển khác với danh sách ở khả năng truy cập các mục theo khóa thay vì vị trí. Hiện tại, đặc điểm quan trọng nhất cần lưu ý là việc “lấy” và “đặt” một mục trong từ điển đều là thao tác O(1)O(1)O(1)

Chúng tôi sẽ không cố gắng đưa ra lời giải thích trực quan cho điều này ngay bây giờ, nhưng hãy yên tâm rằng chúng tôi sẽ thảo luận về việc triển khai từ điển sau. Hiện tại, chỉ cần nhớ rằng từ điển được tạo riêng để nhận và đặt giá trị theo khóa nhanh nhất có thể

+3

Một thao tác từ điển quan trọng khác là kiểm tra xem một khóa có trong từ điển hay không. Thao tác “chứa” này cũng là O(1)O(1)O(1) vì việc kiểm tra một khóa đã cho ẩn chứa trong việc lấy một mục từ từ điển, chính nó là O(1)O(1)O(1)

Lặp lại và sao chép

Việc lặp qua một từ điển là O(n)O(n)O(n), giống như sao chép từ điển, vì các cặp khóa/giá trị nnn phải được sao chép

Chúng tôi đã tóm tắt hiệu quả của tất cả các hoạt động từ điển trong bảng bên dưới

OperationBig O EfficiencycopyO(n)O(n)O(n)get itemO(1)O(1)O(1)set itemO(1)O(1)O(1)delete itemO(1)O(1)O(1)contains (in)O(1)O(1)O(1)iterationO(n)O(n)O(n)

“Trường hợp trung bình”

Hiệu quả được cung cấp trong các bảng trên là hiệu suất trong trường hợp trung bình. Trong một số ít trường hợp, “contains”, “get item” và “set item” có thể suy biến thành hiệu suất O(n)O(n)O(n) nhưng, một lần nữa, chúng ta sẽ thảo luận về điều đó khi nói về các cách triển khai khác nhau

---

Python vẫn là một ngôn ngữ đang phát triển, có nghĩa là các bảng trên có thể thay đổi. Thông tin mới nhất về hiệu suất của các loại dữ liệu Python có thể được tìm thấy trên trang web Python. Khi viết bài này, wiki Python có một trang về độ phức tạp thời gian đẹp có thể tìm thấy tại Wiki Độ phức tạp thời gian

Python phức tạp Big O là gì?

Từ điển Python có phải là số 1 không?

Độ phức tạp Big O là gì?

Có sự phức tạp về thời gian trong Python không?