Ký sự phỏng vấn đầu đời và có suy nghĩ mông lung tương lai

[Killua]

Bạn có biết stack là gì, queue là gì ko, mình thấy câu đó rất rõ ràng mà

[rogp10]

O(1) amortized (trung bình)

[htwap (lu___va_sa__)]

O(1) amortized

nói rõ hơn chỗ này đc không rogp10 ơi, mình hơi yếu phần này

[hungaya (Hung)]

Nếu Stack được hiện thực bằng Linked List thì có thể tận dụng thao tác insert phần tử head, remove phần tử head để làm push(), pop() cho Stack. Nên thao tác trên Stack chỉ chạy trong O(1).

enqueue() sử dụng push() của Stack, nên nó cũng chạy O(1).

Còn dequeue(), thời gian chạy phụ thuộc vào condition outbox.isEmpty(). Nếu là true, thời gian là O(n), nếu là false thì thời gian chỉ là O(1). Do đó việc tính runtime time cho dequeue() rắc rối hơn, vì phải xem xét với từng outbox thì condition trả về như thế nào.

Tuy nhiên, cũng có cách đơn giản, nếu xét tất cả outbox phân phối theo uniform distribution. Trong tất cả outbox có thể có, chỉ có duy nhất 1 trường hợp “outbox chứa 0 phần tử” làm cho outbox.isEmpty() trả về true. Do đó xác suất cho condition trả về true gần bằng 0, false gần bằng 1. Vì thế, tổng thời gian runtime time của dequeue() tính xấp xỉ như sau:

0 . O(n) + 1 . O(1) = O(1)

[Erin_A_James]

Update tình hình hiện tại: Rất cảm ơn lời khuyên mọi người, e vừa tốt nghiệp đầu năm vừa rồi, hiện tại mức lương của e cũng được 1k rồi ạ. Cảm ơn mọi người ạ