Độ phức tạp về thời gian của pop từ một danh sách trong Python là gì?

Các cấu trúc dữ liệu tích hợp trong ngôn ngữ lập trình Python như danh sách, bộ và từ điển cung cấp nhiều thao tác giúp viết mã ngắn gọn dễ dàng hơn

Tuy nhiên, không nhận thức được sự phức tạp của chúng trong khi viết logic nghiệp vụ hoặc thuật toán có thể dẫn đến hành vi chậm không mong muốn của mã python của bạn

Trong bài học này, bạn sẽ tìm hiểu về các Độ phức tạp thời gian Big O khác nhau của các cấu trúc dữ liệu trong ngôn ngữ lập trình Python như Từ điển, Danh sách và Tập hợp cũng như các phương thức của chúng

Độ phức tạp thời gian lớn của danh sách Python và bộ dữ liệu và các phương thức của nó

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

Danh sách tương tự như mảng, có khả năng thêm và xóa hai chiều. Bên trong, một danh sách được biểu diễn dưới dạng một mảng

Chi phí lớn nhất đến từ việc kéo dài vượt quá kích thước phân bổ hiện tại [vì mọi thứ phải di chuyển] hoặc từ việc chèn hoặc xóa một nơi nào đó gần đầu [vì mọi thứ sau đó phải di chuyển]

Nếu bạn cần thêm hoặc xóa ở cả hai đầu, hãy cân nhắc sử dụng bộ sưu tập của Python. deque thay vì

Các bộ dữ liệu có các thao tác và độ phức tạp giống như danh sách ngoại trừ các thao tác làm thay đổi danh sách vì các bộ dữ liệu là bất biến

Dưới đây là những phức tạp thời gian Big O quan trọng nhất cần lưu ý trong danh sách Python

• Đối với Lập chỉ mục & Chỉ định, bất kể danh sách 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]
• Đối với Nối và Nối, có nhiều cách để thực hiện việc này, nhưng chúng tôi sẽ chỉ tập trung vào hai cách để thực hiện việc này. Chúng ta có thể sử dụng phương thức append, là O[1] hoặc toán tử nối [+], O[k], trong đó k là kích thước của danh sách nối vì phải xảy ra k phép toán gán tuần tự
• Đối với Popping, Shifting & Delete, popping từ danh sách Python theo mặc định được thực hiện từ cuối hoặc từ một vị trí cụ thể bằng cách chuyển một chỉ mục. Khi pop được gọi từ cuối, thao tác là O[1], trong khi gọi pop từ bất kỳ nơi nào khác là O[n]
• Đối với Phép lặp, nó là O[n] vì phép lặp qua n phần tử cần n bước
• Toán tử in trong Python để xác định xem một phần tử có trong danh sách hay không là O[n] vì chúng ta phải lặp qua mọi phần tử
• Đối với Cắt lát, truy cập lát cắt là O[k], trong đó k là kích thước của lát cắt. Xóa một lát là O[n] vì lý do tương tự như xóa một phần tử là O[n] i. e n phần tử tiếp theo phải được chuyển về đầu danh sách
• Đối với Phép nhân, phép nhân một danh sách là O[nk], vì nhân một danh sách cỡ k n lần sẽ yêu cầu k[n−1] nối thêm
• Đối với Đảo ngược, đó là O[n] vì chúng ta phải định vị lại từng phần tử
• Đối với Sắp xếp, nó là O[nlogn]

Đây là bảng 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

Hoạt động Độ phức tạp của Big OTrường hợp xấu nhấtVí dụbản saoO[n]O[n]mục. sao chép[] nối thêmO[1]O[1]mục. nối thêm[mục]mở rộngO[k]O[k]mục. mở rộng[…]pop cuối cùng với các mục pop[]O[1]O[1]. pop[]pop trung gian với các mục pop[index]O[n]O[n]. pop[index]get itemO[1]O[1]items[index]set itemO[1]O[1]items[index]=iteminsert itemO[n]O[n]items[index, item]xóa itemO[n . xóa[…]xóa danh sáchO[1]O[1]mục. clear[]IterationO[n]O[n]for item in itemsGet sliceO[k]O[k]items[i. j]Del sliceO[n]O[n]del items[i. j]Đặt lát cắtO[k+n]O[k+n]sắp xếpO[nlogn]O[nlogn]mục. sắp xếp[]ChứaO[n]O[n]mục trong/không có trong lmin[mục], tối đa[mục]O[n]O[n]min[mục], tối đa[mục]Nhận độ dàiO[1]O[ . đảo ngược[]Nối O[k]O[k]items1+items2multiplyO[nk]O[nk]items1*items2So sánh danh sáchO[n]O[n]items1==items2 hoặc item1. =mục2

Sự phức tạp về thời gian của Big O của Từ điển Python và các phương thức của nó

Từ điển sử dụng Bảng băm cho các thao tác chèn/xóa và tra cứu

Defaultdict trong Python có các hoạt động tương tự như dict với cùng độ phức tạp về thời gian khi nó kế thừa từ dict

Dưới đây là những phức tạp thời gian Big O quan trọng nhất cần lưu ý trong từ điển Python

1. Truy cập và thêm một mục trong từ điển đều là thao tác O[1]

2. Việc kiểm tra xem một khóa có trong từ điển hay không cũng là O[1] bởi vì việc kiểm tra một khóa đã cho có nghĩa là lấy một mục từ từ điển, chính nó là O[1].
   Một thao tác tra từ điển đơn giản có thể được thực hiện bởi một trong hai.

if key in d:

# Time complexity of O[N] for Python2, O[1] for Python3

hoặc

if dict.get[key]

1. Lặp lại từ điển là O[n] cũng như sao chép từ điển vì n cặp khóa/giá trị phải được sao chép

Đây là bảng 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

Thao tác Big O Độ phức tạp Trường hợp xấu nhất Ví dụ xây dựng dictO[len[d]]O[len[d]]dict[] mới kiểm tra sizeO[1]O[1]len[d]copyO[n]O[n]d. sao chép[] lấy mụcO[1]O[n]d. get[]set itemO[1]O[n]d[key]=itemxóa mục bằng keyO[1]O[n]del d[key]xóa mục bằng pop[]O[1]O[n]d. pop[item]xóa mục với popitem[]O[1]O[n]d. popitem[]clear[]O[1]O[1]d. rõ ràng[] chứa [trong]O[1]O[n]mục trong/không có trong vị tríO[n]O[n]cho mục trong d. giá trị trả vềO[1]O[1]d. các giá trị[] trả về các phímO[1]O[1]d. keys[] from keysO[len[seq]]O[len[seq]]d. fromkeys[seq]

Độ phức tạp thời gian của Big O của Python Set và Frozen Set và các phương thức của nó

Đặt sử dụng Bảng băm cho các hoạt động chèn/xóa và tra cứu

Frozen Set có các thao tác và độ phức tạp giống như các set ngoại trừ các thao tác làm thay đổi danh sách vì các set cố định là bất biến

Đây là bảng 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 ComplexityWorst CaseExampleadd itemO[1]O[n]s.add[item]pop itemO[1]O[n]s.pop[]clear[]O[1]O[1]s.clear[]copyO[n]O[n]s.copy[]contains[in]O[1]O[n]item in/not in sconstruct new setO[len[s]]O[len[s]]set[]discard itemO[1]O[n]s.discard[item]Set ComparisonO[min[len[s1], len[s2]]]O[min[len[s1], len[s2]]]s1==s2, s1!=s2iterationO[n]O[n]for item in s:check subsetO[len[s1]]O[len[s1]]s1=s2UnionO[len[s1]+len[s2]]-s1+s2IntersectionO[min[len[s1], len[s2]]]O[len[s] * len[t]]s1 & s2DifferenceO[len[s]]O[len[s]]s1 -s2Difference UpdateO[len[s2]]–s1.difference_update[s2]Symmetric DifferenceO[len[s1]]O[len[s1] * len[s2]]s1 ^ s2Symmetric Difference UpdateO[len[s2]]O[len[s2] * len[s1]]s1.symmetric_difference_update[s2]

kết thúc

Ngôn ngữ lập trình Python vẫn đang phát triển, điều đó có nghĩa là những phức tạp 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

Nếu bạn đã học được từ hướng dẫn này hoặc nó đã giúp bạn theo bất kỳ cách nào, vui lòng xem xét chia sẻ và đăng ký nhận bản tin của chúng tôi

Vui lòng chia sẻ bài đăng này và để biết thêm các bài viết sâu sắc về kinh doanh, công nghệ, kỹ thuật, lịch sử và tiếp thị, hãy đăng ký nhận bản tin của chúng tôi

Pop 0 có phức tạp về thời gian trong Python không?

Thời gian chạy của pop trong Python là gì?

Tại sao pop[] O 1?

Danh sách Python có bật chậm không?