Qual è la complessità del metodo addAll di PriorityQueue. Aggiunge un elemento alla volta risultante in O (n log n) o utilizza un processo di heap di build che crea un heap di elementi non ordinati nel tempo O (n)?Complessità di PriorityQueue addAll()
Javadoc sembra implicare che addAll ereditato da AbstractQueue dove è implementato come una sequenza di aggiunge.
Questo mi porta a credere che la complessità sia O(mlogn) dove m è la dimensione della collezione che si sta inserendo.
Guardando OpenJDK, sembra che PriorityQueue erediti l'implementazione addAll da AbstractQueue che itera sulla raccolta e chiama le aggiunte su ciascun elemento.
... questa implementazione fornisce O (log (n)) per l'Enqueing e metodi dequeing ...
Così si può solo assumere n log(n).
Tuttavia, ovviamente, questo è solo ciò che si può assumere. A seconda dell'implementazione specifica che intendi utilizzare, potresti trovare alcuni trucchi che potrebbero migliorare le tue esigenze.
...? _O (m log n) _, non _O (m n log n) _. –
@LouisWasserman hai corretto grazie! –
Penso che sarebbe 'O (m log (n + m))'. Pensa al caso in cui 'n = 0' –