Hướng dẫn python deque insert time complexity - python và chèn thời gian phức tạp

Nhận cuốn sách này -> Vấn đề về Array: Đối với các cuộc phỏng vấn và lập trình cạnh tranh

Deque (Hàng đợi kết thúc kép) là một cấu trúc dữ liệu có thể được sử dụng để chèn hoặc xóa các phần tử dữ liệu ở cả hai kết thúc. Nó được hỗ trợ trực tiếp trong Python thông qua mô -đun bộ sưu tập.

• "Bộ sưu tập", là một mô -đun Python xác định Deque.Collections", is a Python Module that defines Deque.
• Để bắt đầu sử dụng Deque trong chương trình Python của bạn, hãy sử dụng mã được đưa ra dưới đây.

import collections
de = collections.deque([1,2,3])

• Deque yêu cầu thời gian O (1) để thực hiện các hoạt động của phụ lục và POP. Trong khi đó, một danh sách yêu cầu độ phức tạp O (n). Để tham khảo, máy mất 1S để thực hiện 10^6 hoạt động.
  For reference a machine takes 1s to perform 10^6 operations.
• Các yếu tố có thể được truy cập tại bất kỳ chỉ mục. Giống như một mảng. Nếu trong một trường hợp ví dụ bạn cần truy cập (giả sử) Phần tử thứ 4, bạn có thể có thể truy cập chỉ bằng chỉ mục.

Câu hỏi

Độ phức tạp về thời gian cho các hoạt động phụ lục và pop?

Tham khảo phần giới thiệu ở trên.

Hoạt động trên Deque

Các hoạt động được hỗ trợ bởi Deque là:

• nối
• Phụ lục
• Pop và Popleft
• mục lục
• chèn
• gỡ bỏ
• đếm
• gia hạn
• mở rộng
• đảo ngược
• quay
• Len

1. append ():- Hàm này được sử dụng để chèn giá trị vào đối số của nó vào đầu bên phải của deque. Nối đơn giản là nối lại phần tử bạn nhập vào đầu bên phải của deque. :- This function is used to insert the value in its argument to the right end of deque. Append simply appends the element you enter to the right end of the deque.

import collections
de = collections.deque([1,2,3])
de.append(4)
de

2. Phụ lục ():- Hàm này được sử dụng để chèn giá trị vào đối số của nó vào đầu bên trái của deque. :- This function is used to insert the value in its argument to the left end of deque.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de

3. pop () & popleft ():- Các phương pháp này được sử dụng để xóa một đối số từ đầu bên phải và cũng từ đầu bên trái của deque tương ứng. :- These methods are used to delete an argument from the right end and also from the left end of the deque respectively.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de
de.popleft()
de

Câu hỏi

Độ phức tạp về thời gian cho các hoạt động phụ lục và pop?

Tham khảo phần giới thiệu ở trên.

Hoạt động trên Deque :- This function returns the first index of the value mentioned in arguments, starting searching from beg till end index. This simply searches the occurence for the 'ele'and returns it.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)

Các hoạt động được hỗ trợ bởi Deque là: :- This function inserts the value mentioned in arguments(a) at index(i) specified in arguments. This is similar to in array. It overrides the value, if the value is present in prior to the insertion at the given index.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de

nối

Phụ lục

Pop và Popleft

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.remove(2)
de.insert(-5,10)
de

mục lục :- This function removes the first occurrence of value mentioned in arguments. Searches, for the occurence of the element and deletes whenever, it finds the required element.

gỡ bỏ :- This function counts the number of occurrences of value mentioned in arguments. Increements to the value of the number of times a number is present.

import collections
de = collections.deque([1,2,3])
de.append(4)
de.appendleft(0)
de.pop()
de.popleft()
de.index(2,0,2)
de.insert(1,5)
de.remove(2)
de.append(1)
de.count(1)

Câu hỏi

Độ phức tạp về thời gian cho các hoạt động phụ lục và pop?

Phụ lục

Pop và Popleft :- This function is used to add multiple values at the right end of deque. The argument passed is an iterable. Iteratively, it just inserts the values into the deque.

import collections
de = collections.deque([1,2,3])

mục lục :- This function is used to add multiple values at the left end of deque. The argument passed is an iterable. Order is reversed as a result of left appends.

import collections
de = collections.deque([1,2,3])

chèn :- This function is used to reverse order of deque elements. Just as in other cases for other data-structures.

import collections
de = collections.deque([1,2,3])

gỡ bỏ :- This function rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to left. By default the rotation is to right.

import collections
de = collections.deque([1,2,3])

đếm

import collections
de = collections.deque([1,2,3])

gia hạn :- Gives out the length of the Deque.

Câu hỏi

Độ phức tạp về thời gian cho các hoạt động phụ lục và pop?

Phụ lục

Pop và Popleft