Hướng dẫn what is the time complexity of pop () in python? - độ phức tạp về thời gian của pop () trong python là gì?

Nội dung chính Show

Một nghiên cứu thực nghiệm trên danh sách Python.POP Độ phức tạp
Liệt kê là hàng đợi
Một nghiên cứu thực nghiệm thông qua hồ sơ
Sự phức tạp về thời gian của Python Pop là gì?
Thời gian phức tạp pop là gì?
Pop có chậm trong Python không?
Python pop 0 có phải là thời gian không đổi không?

Một nghiên cứu thực nghiệm trên danh sách Python.POP Độ phức tạp

Đây là lý do tại sao bạn nên sử dụng Collection.deque làm hàng đợi, nhưng không phải liệt kê.

TL;DR

Python list.pop (k) có độ phức tạp về thời gian của O (k).
Hãy thận trọng khi sử dụng Python list làm cấu trúc hàng đợi. Sử dụng deque thay thế.
Luôn hồ sơ mã của bạn để tối ưu hóa.

Liệt kê là hàng đợi

Hàng đợi là cấu trúc dữ liệu đầu tiên (FIFO) đầu tiên. Thuộc tính cơ bản này làm cho hàng đợi hữu ích trong một loạt các ứng dụng, chẳng hạn như tổ chức các đối tượng theo thứ tự và phục vụ như là bộ đệm giao tiếp giữa các luồng.

Hàng đợi chỉ là một loại dữ liệu trừu tượng và các ngôn ngữ khác nhau có các dụng cụ riêng. Trong Python, hàng đợi FIFO thích hợp là deque, cung cấp các hàm append và

a = [1, 2, 3, 4, 5, 6]

0 để đẩy một phần tử cuối cùng và bật phần tử lâu đời nhất từ phía trước, tương ứng. Tuy nhiên, vì Python

a = [1, 2, 3, 4, 5, 6]

1 có phơi nhiễm tốt hơn nhiều và cũng cung cấp các hàm

a = [1, 2, 3, 4, 5, 6]

2 và

a = [1, 2, 3, 4, 5, 6]

a = [1, 2, 3, 4, 5, 6]

1 có lẽ thường được sử dụng như một hàng đợi.However, since the Python

a = [1, 2, 3, 4, 5, 6]

1 has a much better exposures and also provides

a = [1, 2, 3, 4, 5, 6]

2 and

a = [1, 2, 3, 4, 5, 6]

3 functions,

a = [1, 2, 3, 4, 5, 6]

1 is probably more frequently used as a Queue.

Vì vậy, mối quan tâm với việc sử dụng list làm hàng đợi là gì? Đặc biệt, chúng ta có nên sử dụng

a = [1, 2, 3, 4, 5, 6]

6 để bật yếu tố lâu đời nhất từ hàng đợi không?

Đây là giao diện của

a = [1, 2, 3, 4, 5, 6]

7 được xác định trong Python

a = [1, 2, 3, 4, 5, 6]
8([i])
Loại bỏ mục tại vị trí đã cho trong danh sách và trả về nó. Nếu không có chỉ mục được chỉ định,
a = [1, 2, 3, 4, 5, 6]
9 sẽ xóa và trả về mục cuối cùng trong danh sách.

Cơ chế cơ bản và độ phức tạp thời gian không được đề cập. Nhưng tài liệu thực sự ủng hộ việc sử dụng list làm hàng đợi

Để thực hiện hàng đợi, hãy sử dụng
a.pop(k)
1 được thiết kế để có sự thay đổi nhanh chóng và bật từ cả hai đầu.

Về cơ bản, một Python list được triển khai như một loạt các con trỏ.

a.pop(k)

3 đầu tiên loại bỏ và trả về phần tử tại

a.pop(k)

4, sau đó di chuyển tất cả các phần tử ngoài

a.pop(k)

4 một vị trí lên.

Một nghiên cứu thực nghiệm thông qua hồ sơ

Dưới đây là một ví dụ demo về việc sử dụng hàng đợi để theo thứ tự ngang hàng (tạo) một cây. Chúng tôi tạo ra một cây nhị phân ngẫu nhiên với tối đa 10.000 nút.

Mã mẫu để tạo cây nhị phân với hàng đợi.

Ở dòng 19 và 21, chúng tôi đang sử dụng deque để thực hiện các đường truyền theo cấp độ của cây nhị phân ngẫu nhiên của chúng tôi. Các kết quả hồ sơ được hiển thị trong hình khi bắt đầu bài viết này.

Bạn có thể hình ảnh những gì xảy ra nếu chúng ta sử dụng danh sách thay thế không? Thay đổi dòng 19 và 21 thành:

line 19:    queue = list([root])
line 21:    cur = queue.pop(0)

Và đây là kết quả hồ sơ. Hoạt động

a.pop(k)

7 chậm hơn gần 1000 lần so với

a.pop(k)

8. Do đó, toàn bộ chương trình kết thúc với hai lần thời gian. Đây là sự khác biệt giữa hàm phức tạp thời gian O (1) V.S. O (n) một.

Python danh sách.pop (0) cực kỳ chậm cho một danh sách lớn.

Nếu bạn đang học Python sau JavaScript là ngôn ngữ đầu tiên của bạn. Bạn có thể sẽ bị khóa bởi các chức năng sẵn có mà chúng ta có trong Python.

Trong khi xóa bất kỳ yếu tố nào khỏi danh sách, chúng tôi nên quan tâm đến sự phức tạp và chúng tôi có chức năng pop () bật phần tử từ danh sách trên chỉ mục được cung cấp. Nó có quan tâm đến sự phức tạp về thời gian không?

Hãy xem xét chúng tôi có danh sách sau.

a = [1, 2, 3, 4, 5, 6]

Bằng cách thực hiện

a = [1, 2, 3, 4, 5, 6]

9 không có đối số, nó sẽ xóa và trả về phần tử cuối cùng có độ phức tạp thời gian O (1). Bởi vì nó chỉ loại bỏ phần tử cuối cùng và không cần phải sắp xếp lại các phần tử.

Danh sách Python được thực hiện như một mảng của con trỏ. Nếu chúng ta thực hiện xóa và trả lại

O(N-k)

1 và sau đó di chuyển tất cả các yếu tố sau khi

a.pop(k)

4 lên một vị trí. Để chúng tôi không có giá trị

O(N-k)

3 ở vị trí

O(N-k)

Vì vậy, điều gì sẽ là sự phức tạp về thời gian khi chúng ta vượt qua một cuộc tranh luận? Hãy xem xét độ dài của danh sách là

O(N-k)

5 và chúng ta cần loại bỏ một phần tử ở mức độ ____36 như sau.

a.pop(k)

Công thức chung cho độ phức tạp thời gian này sẽ là:general formula for this time complexity will be:

O(N-k)

Độ phức tạp thời gian tồi tệ nhất sẽ là: time complexity will be:


# when we have to remove the first element
O(N)# if we consider list we have above
a = [1, 2, 3, 4, 5, 6]
O(6-0) = O(6) = O(N)

Độ phức tạp thời gian trường hợp trung bình sẽ là: time complexity will be:

O(k) or O(N/2)

Vì chúng tôi có sáu yếu tố trong danh sách và loại bỏ phần tử giữa của danh sách là

O(N-k)

7 sẽ có các hoạt động

a.pop(k)

4. Vì vậy, đơn giản là chúng ta sẽ có độ phức tạp thời gian

O(N-k)

9average.

Nhìn vào sự phức tạp, chúng ta không nên sử dụng


# when we have to remove the first element
O(N)# if we consider list we have above
a = [1, 2, 3, 4, 5, 6]
O(6-0) = O(6) = O(N)

0 để quản lý hàng đợi. Thay vào đó chúng tôi có


# when we have to remove the first element
O(N)# if we consider list we have above
a = [1, 2, 3, 4, 5, 6]
O(6-0) = O(6) = O(N)

1in Python.

Hạnh phúc mã hóa cho đến lúc đó!

Sự phức tạp về thời gian của Python Pop là gì?

danh sách

Hoạt động	Trường hợp trung bình	Đã khấu hao trường hợp xấu nhất
Pop cuối cùng	O(1)	O(1)
Trung cấp pop [2]	O(n)	O(n)
Chèn	O(n)	O(n)
Nhận mục	O(1)	O(1)

Timecomplexity - Python wikiwiki.python.org