Câu hỏi:
13/07/2024 118
Hãy giải thích vì sao lệnh dequeue(Q) lại có độ phức tạp thời gian là O(n), với n là độ dài của hàng đợi hiện thời.
Hãy giải thích vì sao lệnh dequeue(Q) lại có độ phức tạp thời gian là O(n), với n là độ dài của hàng đợi hiện thời.
Câu hỏi trong đề:
Giải chuyên đề Tin 12 KNTT Bài 4: Kiểu dữ liệu hàng đợi có đáp án !!
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Nếu biểu diễn hàng đợi (queue) bằng một danh sách (list), lệnh dequeue(Q) thường được thực hiện bằng cách sử dụng phương thức pop(0), tức là lấy và loại bỏ phần tử đầu tiên của danh sách. Độ phức tạp thời gian của lệnh này là O(n)O(n)O(n), với nnn là số phần tử trong hàng đợi hiện thời. Để hiểu rõ tại sao lại như vậy, ta cần xem xét cách thức hoạt động của danh sách trong Python.
Hoạt động của lệnh pop(0)
1. Truy cập phần tử đầu tiên:
Truy cập phần tử đầu tiên của danh sách (phần tử có chỉ số 0) là O(1)O(1)O(1), vì Python có thể truy cập bất kỳ phần tử nào của danh sách theo chỉ số trong thời gian hằng số.
2. Loại bỏ phần tử đầu tiên:
- Khi phần tử đầu tiên bị loại bỏ, tất cả các phần tử còn lại trong danh sách phải được di chuyển về phía trước một vị trí để lấp chỗ trống. Cụ thể, phần tử thứ hai trở thành phần tử thứ nhất, phần tử thứ ba trở thành phần tử thứ hai, và cứ thế tiếp tục.
- Quá trình di chuyển tất cả các phần tử này có độ phức tạp là O(n)O(n)O(n), vì cần phải di chuyển n−1n-1n−1 phần tử trong danh sách (với nnn là tổng số phần tử ban đầu).
Độ phức tạp thời gian
- Việc di chuyển tất cả các phần tử về phía trước một vị trí có độ phức tạp thời gian là O(n−1)O(n-1)O(n−1), nhưng về mặt phân tích độ phức tạp, chúng ta bỏ qua hằng số và bậc thấp, do đó kết quả là O(n)O(n)O(n).
Vì lý do này, lệnh dequeue(Q) thực hiện bằng Q.pop(0) có độ phức tạp thời gian là O(n)O(n)O(n).
Lựa chọn thay thế
Để cải thiện hiệu suất có thể sử dụng collections.deque trong Python, một cấu trúc dữ liệu được thiết kế cho việc thêm và loại bỏ phần tử ở cả hai đầu với độ phức tạp thời gian là O(1)O(1)O(1):
from collections import deque
Q = deque([1, 2, 3, 4, 5])
Q.popleft() # Loại bỏ phần tử đầu tiên, độ phức tạp là O(1)
Với deque , lệnh dequeue(Q) sẽ có độ phức tạp thời gian là O(1)O(1)O(1), hiệu quả hơn rất nhiều so với việc sử dụng danh sách.
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Em hãy nêu sự giống nhau và khác nhau giữa các hàm của ngăn xếp và hàng đợi được cài đặt bằng danh sách (kiểu list của Python).
Em hãy nêu sự giống nhau và khác nhau giữa các hàm của ngăn xếp và hàng đợi được cài đặt bằng danh sách (kiểu list của Python).
Xem đáp án »
13/07/2024
142
Câu 2:
Khi hàng đợi Q được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết chỉ số của các phản tử tại đầu (front) và đuôi (rear). So sánh các chỉ số này với chỉ số của các phần tử tại đáy (bottom) và đỉnh (top) của ngăn xếp (cũng được cài đặt bằng danh sách).
Khi hàng đợi Q được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết chỉ số của các phản tử tại đầu (front) và đuôi (rear). So sánh các chỉ số này với chỉ số của các phần tử tại đáy (bottom) và đỉnh (top) của ngăn xếp (cũng được cài đặt bằng danh sách).
Xem đáp án »
13/07/2024
108
Câu 3:
Quan sát, trao đổi, thảo luận để tìm hiểu cách biểu diễn hàng đợi bằng mảng một chiều. Em hãy trả lời các câu hỏi sau:
1. Có thể biểu diễn hàng đợi bằng mảng một chiều được không?
2. Cần có các biến nào để thực hiện các phép toán thêm vào và lấy ra?
Quan sát, trao đổi, thảo luận để tìm hiểu cách biểu diễn hàng đợi bằng mảng một chiều. Em hãy trả lời các câu hỏi sau:
1. Có thể biểu diễn hàng đợi bằng mảng một chiều được không?
2. Cần có các biến nào để thực hiện các phép toán thêm vào và lấy ra?
Xem đáp án »
13/07/2024
102
Câu 4:
Khi hàng đợi được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết cách tính số phần tử của hàng đợi này.
Khi hàng đợi được cài đặt bằng danh sách (kiểu list của Python), em hãy cho biết cách tính số phần tử của hàng đợi này.
Xem đáp án »
13/07/2024
92
Câu 5:
Từ các bài học trước, em đã biết viết chương trình đơn giản để sử dụng các hàm cơ bản của ngăn xếp được cài đặt bằng danh sách (kiểu list của Python). Em hãy trả lời các câu hỏi sau:
a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?
b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện phép toán thêm vảo và lấy ra?
Từ các bài học trước, em đã biết viết chương trình đơn giản để sử dụng các hàm cơ bản của ngăn xếp được cài đặt bằng danh sách (kiểu list của Python). Em hãy trả lời các câu hỏi sau:
a) Có thể cài đặt hàng đợi bằng mảng một chiều tương tự như ngăn xếp được không?
b) Khi cài đặt hàng đợi bằng mảng một chiều, cần có thông tin nào để thực hiện phép toán thêm vảo và lấy ra?
Xem đáp án »
13/07/2024
91
Câu 6:
Ban đầu, hàng đợi là rỗng. Em hãy cho biết giá trị của phần tử ở đầu (front) và đuôi (rear) sau khi thực hiện tuần tự các phép toán enqueue(Q,2); enqueue(Q,19); dequeue(Q), enaqueue (Q, 6); dequeue(Q); enqueue(Q, 9); enqueue(Q,1).
Ban đầu, hàng đợi là rỗng. Em hãy cho biết giá trị của phần tử ở đầu (front) và đuôi (rear) sau khi thực hiện tuần tự các phép toán enqueue(Q,2); enqueue(Q,19); dequeue(Q), enaqueue (Q, 6); dequeue(Q); enqueue(Q, 9); enqueue(Q,1).
Xem đáp án »
13/07/2024
91
về câu hỏi!