Độ phức tạp của phương thức addAll của PriorityQueue là gì. Liệu nó thêm một phần tử tại một thời điểm dẫn đến O (n log n) hay nó sử dụng một quá trình heap xây dựng mà tạo ra một đống ra khỏi các yếu tố không có thứ tự trong thời gian O (n)?Độ phức tạp của ưu tiênQueue addAll()
Javadoc dường như ngụ ý rằng addAll được thừa hưởng từ AbstractQueue nó ở đâu thực hiện như một chuỗi các thêm.
Điều này dẫn tôi tin rằng độ phức tạp là O(mlogn) trong đó m là kích thước của bộ sưu tập được chèn vào.
Nhìn vào OpenJDK, có vẻ như PriorityQueue kế thừa việc thực hiện addAll từ AbstractQueue lặp qua bộ sưu tập và các cuộc gọi thêm vào mỗi phần tử.
... thực hiện này cung cấp O (log (n)) thời gian cho các enqueing và phương pháp dequeing ...
Vì vậy, bạn chỉ có thể giả sử n log(n).
Tuy nhiên - hiển nhiên - đây chỉ là những gì bạn có thể giả định. Tùy thuộc vào việc triển khai cụ thể mà bạn định sử dụng, bạn có thể tìm thấy một số thủ thuật có thể cải thiện vấn đề cho bạn.
...? _O (m log n) _, không _O (m n log n) _. –
@LouisWasserman yup cố gắng cảm ơn! –
Tôi nghĩ nó sẽ là 'O (m log (n + m))'. Hãy suy nghĩ về trường hợp khi 'n = 0' –