Ho una matrice con 1,000,000 di elementi non ordinati. Ho bisogno di calcolare il numero previsto di operazioni che devono essere eseguite per ordinare l'array usando l'algoritmo Quicksort in situazioni comuni (non il caso peggiore n ^ 2).
Non sono sicuro di come viene calcolato (n log n) - ha senso calcolare questo?
Se (n log n) = (n*log(some base)n) quale base sarebbe per Quicksort ?
Prima di continuare e continuare i tuoi calcoli, ti consiglio di provare a capire la notazione O grande. La notazione ti aiuta ad avere un'idea della evoluzione dei costi di calcolo quando cambia la dimensione dell'input. La base del log è irrilevante qui poiché influenza solo il fattore costante
Se è necessario fornire un numero preciso di operazioni, è necessario analizzare l'algoritmo e la struttura dati utilizzata per la sua implementazione e non solo utilizzare una formula.
L'articolo su quicksort su Wikipedia spiega cos'è l'algoritmo.
Mostra un'animazione di come viene eseguito l'ordinamento.
La base è "2".
il log qui è nella base 2, la semplice notazione O dice semplicemente che se si aumenta il valore del numero di elementi, che è n in questo caso, come sarebbe il tempo di calcolare l'output dipende da esso.
Leggi altre domande sui tag algorithms complexity optimization
