Jaka jest złożoność sposobu AddAll z kolejka priorytetowa. Czy dodaje on jeden element naraz, powodując O (n log n), czy też używa procesu budowania sterty, który tworzy stertę z nieuporządkowanych elementów w czasie O (n)?Złożoność kolejka priorytetowa AddAll()
Javadoc wydaje się sugerować, że addAll jest dziedziczona z AbstractQueue gdzie jest realizowane jako sekwencja dodaje.
To prowadzi mnie do przekonania, że złożoność to O(mlogn) gdzie m jest wielkością wstawianej kolekcji.
Patrząc na OpenJDK, wygląda kolejka priorytetowa dziedziczy realizację AddAll z AbstractQueue który wykonuje iteracje nad zbierania i wzywa dodać na każdym elemencie.
... ta implementacja zapewnia O (log (n)) czas na enqueing i metod dequeing ...
Więc można tylko załóżmy n log(n).
jednak - oczywiście - to jest tylko to, co można założyć. W zależności od konkretnej implementacji, której zamierzasz użyć, możesz znaleźć kilka sztuczek, które mogą poprawić sytuację.
...? _O (m log n) _, nie _O (m n log n) _. –
@LouisWasserman yup naprawione dzięki! –
Myślę, że byłby to "O (m log (n + m))". Pomyśl o przypadku, gdy 'n = 0' –