Độ phức tạp của từ điển Python
Chúng ta đã thảo luận rất chi tiết về phương thức Show
Trước khi tiếp tục, chúng ta hãy xem nhanh chức năng của được()
Chi phí thời gian chạy của phương thức get() tl;dr Từ điển Python Chi phí tra cứu trong một hashmap là O(1) trong trường hợp trung bình – khi hàm băm khá và không có xung đột giữa . Trong trường hợp xấu nhất, một O(1) tra cứu không được đảm bảo trong hashmap nhưng nó hầu như luôn đạt được. Điều này là do các hàm băm tốt giúp phân phối mã băm đồng đều trên phạm vi. Hình ảnh bên dưới cho thấy sự va chạm trong HashMap nguồn hình ảnh. tin tặcNhư bạn có thể thấy, đối với mã băm 2 và 5 có nhiều phần tử, vì vậy, nếu chúng ta cần tra cứu một phần tử có mã băm 2 hoặc 5, thì chúng ta sẽ cần lặp lại các mục được liên kết . Kịch bản này rất khó xảy ra vì các hàm băm thường được thiết kế khá thông minh Bây giờ chúng ta đã thấy va chạm trong một hashmap trông như thế nào, hãy xem hashmap lý tưởng với một hàm băm lý tưởng trông như thế nào, Nguồn. hướng dẫn. comNhư bạn có thể thấy, key_1, key_2 và key_3 đi qua Hàm băm và tạo mã băm (Chỉ mục trong ví dụ trên) sau đó được liên kết với các giá trị. Không, hai khóa chia sẻ cùng một mã băm, điều này làm cho quá trình băm trở nên hoàn hảo 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
Đâ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
Mẫu mã được đánh dấuhoặc Mẫu mã được đánh dấu
Đâ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<=s2check supersetO(len(s2))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úcNgô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 Độ phức tạp về thời gian cho các phím dict() là gì?Độ phức tạp của nó là 0(1) trong Python 3. x. Trong Python 2. x, nó trả về một danh sách nên việc điền vào danh sách đó hoặc thực hiện một số tra cứu trên đó sẽ mất 0(n).
Từ điển như thế nào là O 1?O(1) có nghĩa là hằng số bất kể kích thước của dữ liệu . Hàm băm mất một khoảng thời gian nhất định, nhưng lượng thời gian đó không tỷ lệ với kích thước của bộ sưu tập.
Độ phức tạp không gian của một từ điển là gì?Từ điển sử dụng cấu trúc dữ liệu mảng kết hợp có độ phức tạp về không gian O(N) .
Tại sao từ điển nhanh hơn danh sách?Danh sách là một tập hợp dữ liệu được sắp xếp theo thứ tự, trong khi các từ điển lưu trữ dữ liệu dưới dạng các cặp khóa-giá trị bằng cách sử dụng cấu trúc hashtable. Do đó, việc tìm nạp các phần tử từ cấu trúc dữ liệu danh sách khá phức tạp so với từ điển trong Python . Do đó, từ điển nhanh hơn danh sách trong Python. |