Độ 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 get() của từ điển Python ở đây (bạn có thể muốn đi và kiểm tra điều đó trước). Trong hướng dẫn này, chúng ta sẽ chỉ tập trung vào chi phí thời gian chạy của phương thức


Trước khi tiếp tục, chúng ta hãy xem nhanh chức năng củaget() làm gì

được()

dictionary.get(key,default_value) lấy  giá trị  được liên kết với khóa  khóa . Nếu khóa không có trong từ điển, thì get() trả về  default_value  nếu chúng tôi cung cấp cho nó giá trị mặc định, nếu chúng tôi không cung cấp bất kỳ giá trị nào < . default_value, then it returns None.


Chi phí thời gian chạy của phương thức get()

tl;dr
Độ phức tạp của trường hợp thời gian trung bình. O(1)
Độ phức tạp thời gian trong trường hợp xấu nhất. O(N)

Từ điển Python dict được triển khai nội bộ bằng cách sử dụng hashmap, do đó, chi phí chèn, xóa và tra cứu của từ điển sẽ giống như chi phí của hashmap. Trong hướng dẫn này, chúng ta sẽ chỉ nói về chi phí tra cứu trong từ điển vì get() là một thao tác tra cứu

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 HashMap có O(N) tra cứu do đi qua tất cả các mục trong cùng một nhóm băm (e. g. nếu tất cả các giá trị chia sẻ cùng một mã băm).

May mắn thay, tình huống xấu nhất đó không thường xuyên xảy ra trong đời thực.

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

Độ phức tạp của từ điển Python
nguồn hình ảnh. tin tặc

Như 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 .

Trong trường hợp xấu nhất, tất cả N phần tử chia sẻ cùng một mã băm. Sau đó, chúng tôi sẽ cần lặp lại tất cả các phần tử N để tra cứu bất kỳ giá trị nào (tương tự như tra cứu trong danh sách đượ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,

Độ phức tạp của từ điển Python
Nguồn. hướng dẫn. com

Như 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

  • Đố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 (
    if dict.get(key)
    
    0), O(k), trong đó k là kích thước của danh sách nối vì k phép toán gán tuần tự phải xảy ra
  • Đố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
    if dict.get(key)
    
    1 được gọi từ cuối, thao tác là O(1), trong khi gọi
    if dict.get(key)
    
    1 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ử
    if dict.get(key)
    
    3 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) 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
Mẫu mã được đánh dấu

hoặc

if dict.get(key)
Mẫu mã được đánh dấu
  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<=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ú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

Độ 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.