Độ phức tạp của từ điển Python ✅ Đã Test

Kinh Nghiệm về Độ phức tạp của từ điển Python Chi Tiết

Hà Văn Thắng đang tìm kiếm từ khóa Độ phức tạp của từ điển Python được Update vào lúc : 2022-12-17 16:25:08 . Với phương châm chia sẻ Thủ Thuật Hướng dẫn trong nội dung bài viết một cách Chi Tiết Mới Nhất. Nếu sau khi đọc Post vẫn ko hiểu thì hoàn toàn có thể lại Comments ở cuối bài để Admin lý giải và hướng dẫn lại nha.

Chúng ta đã thảo luận rất rõ ràng về phương thức get() của từ điển Python ở đây (bạn hoàn toàn có thể muốn đi và kiểm tra điều đó trước). Trong hướng dẫn này, tất cả chúng ta sẽ chỉ tập trung vào ngân sách thời gian chạy của phương thức

Nội dung chính Show

Độ phức tạp thời gian lớn của list Python và bộ tài liệu và những phương thức của nóSự phức tạp về thời gian của Big O của Từ điển Python và những phương thức của nóĐộ phức tạp thời gian của Big O của Python Set và Frozen Set và những phương thức của nókết thúcĐộ phức tạp về thời gian cho những phím dict() là gì?Từ điển ra làm sao là O 1?Độ phức tạp không khí của một từ điển là gì?Tại sao từ điển nhanh hơn list?

Trước khi tiếp tục, tất cả chúng ta hãy xem nhanh hiệu suất cao củaget() làm gì

được()

dictionary.get(key,default_value) lấy  giá trị  được link với khóa  khóa . Nếu khóa không còn trong từ điển, thì get() trả về  default_value  nếu chúng tôi đáp ứng cho nó giá trị mặc định, nếu chúng tôi không đáp ứng 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 phương pháp sử dụng hashmap, do đó, ngân sách chèn, xóa và tra cứu của từ điển sẽ in như ngân sách của hashmap. Trong hướng dẫn này, tất cả chúng ta sẽ chỉ nói về ngân sách 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òn 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ả những mục trong cùng một nhóm băm (e. g. nếu tất cả những 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à vì những 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 phía dưới đã cho tất cả chúng ta biết sự va chạm trong HashMap

nguồn hình ảnh. tin tặc

Như bạn hoàn toà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 tất cả chúng ta cần tra cứu một phần tử có mã băm 2 hoặc 5, thì tất cả chúng ta sẽ cần lặp lại những mục được link .

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ả những phần tử N để tra cứu bất kỳ giá trị nào (tương tự như tra cứu trong list được link).

Kịch bản này rất khó xảy ra vì những hàm băm thường được thiết kế khá thông minh

Bây giờ tất cả chúng ta đã thấy va chạm trong một hashmap trông ra làm sao, hãy xem hashmap lý tưởng với một hàm băm lý tưởng trông ra làm sao,

Nguồn. hướng dẫn. com

Như bạn hoàn toà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 link với những 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 nhất

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

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

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

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

Trong list Python, những giá trị được gán và truy xuất từ ​​những vị trí bộ nhớ rõ ràng, đã biết

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

Chi phí lớn số 1 đến từ việc kéo dãn vượt quá kích thước phân bổ hiện tại (vì mọi thứ phải di tá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 tán)

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

Các bộ tài liệu có những thao tác và độ phức tạp in như list ngoại trừ những thao tác làm thay đổi list vì những bộ tài liệu là không bao giờ thay đổi

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 list Python

Đối với Lập chỉ mục & Chỉ định, bất kể list 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 phương pháp để thực hiện việc này, nhưng chúng tôi sẽ chỉ tập trung vào hai phương pháp để thực hiện việc này. Chúng ta hoàn toàn 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 list 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ừ list Python theo mặc định được thực hiện từ cuối hoặc từ một vị trí rõ ràng bằng phương pháp 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ướcToán tử if dict.get(key) 3 trong Python để xác định xem một phần tử có trong list hay là không là O(n) vì tất cả 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ì nguyên 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 list là O(nk), vì nhân một list 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ì tất cả 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 suất cao của tất cả những hoạt động và sinh hoạt giải trí sinh hoạt từ điển trong bảng phía 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 ở đầu cuối với những mục pop()O(1)O(1). pop()pop trung gian với những 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òn 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à những phương thức của nó

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

Defaultdict trong Python có những hoạt động và sinh hoạt giải trí sinh hoạt tương tự như dict với cùng độ phức tạp về thời gian khi nó thừa kế 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

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

Việc kiểm tra xem một khóa có trong từ điển hay là không cũng là O(1) vì việc kiểm tra một khóa đã cho 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 hoàn toà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ấuLặ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 suất cao của tất cả những hoạt động và sinh hoạt giải trí sinh hoạt từ điển trong bảng phía 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òn trong vị tríO(n)O(n)cho mục trong d. giá trị trả vềO(1)O(1)d. những giá trị() trả về những 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à những phương thức của nó

Đặt sử dụng Bảng băm cho những hoạt động và sinh hoạt giải trí chèn/xóa và tra cứu

Frozen Set có những thao tác và độ phức tạp in như những set ngoại trừ những thao tác làm thay đổi list vì những set cố định và thắt chặt là không bao giờ thay đổi

Đây là bảng tóm tắt hiệu suất cao của tất cả những hoạt động và sinh hoạt giải trí sinh hoạt từ điển trong bảng phía 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 đó nghĩa là những phức tạp trên hoàn toàn có thể thay đổi

tin tức tiên tiến nhất về hiệu suất của nhiều chủng loại tài liệu Python hoàn toàn 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 hoàn toàn 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 những nội dung bài viết sâu sắc về marketing thương mại, công nghệ tiên tiến, 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 những 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 list nên việc điền vào list đó hoặc thực hiện một số trong những tra cứu trên đó sẽ mất 0(n).

Từ điển ra làm sao là O 1?

O(1) nghĩa là hằng số bất kể kích thước của tài liệu . Hàm băm mất một khoảng chừ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 cục sưu tập.

Độ phức tạp không khí của một từ điển là gì?

Từ điển sử dụng cấu trúc tài liệu mảng phối hợp có độ phức tạp về không khí O(N) .

Tại sao từ điển nhanh hơn list?

Danh sách là một tập hợp tài liệu được sắp xếp theo thứ tự, trong khi những từ điển tàng trữ tài liệu dưới dạng những cặp khóa-giá trị bằng phương pháp sử dụng cấu trúc hashtable. Do đó, việc tìm nạp những phần tử từ cấu trúc tài liệu list khá phức tạp so với từ điển trong Python . Do đó, từ điển nhanh hơn list trong Python. Tải thêm tài liệu liên quan đến nội dung bài viết Độ phức tạp của từ điển Python programming python

Video Độ phức tạp của từ điển Python ?

Bạn vừa Read nội dung bài viết Với Một số hướng dẫn một cách rõ ràng hơn về Video Độ phức tạp của từ điển Python tiên tiến nhất

Chia Sẻ Link Download Độ phức tạp của từ điển Python miễn phí

Heros đang tìm một số trong những Chia Sẻ Link Down Độ phức tạp của từ điển Python Free.

Hỏi đáp thắc mắc về Độ phức tạp của từ điển Python

Nếu sau khi đọc nội dung bài viết Độ phức tạp của từ điển Python vẫn chưa hiểu thì hoàn toàn có thể lại Comments ở cuối bài để Ad lý giải và hướng dẫn lại nha #Độ #phức #tạp #của #từ #điển #Python - 2022-12-17 16:25:08