Qui il professore ha detto che, per ordinare i tornei occorrono (n-1) + 2 (n-1) logn confronti.
{Dove (n-1) per calcolare Massimo o dire creare una struttura Torneo e 2 (n-1) logn per altri elementi da ordinare}
Perché il professore ha omesso il numero di confronti necessari per trovare il minimo? Perché per calcolare gli elementi minimi abbiamo bisogno di confronti (n / 2 - 1) .
Qui logn significa log n alla base 2
Sto guardando la conferenza di NPTEL link (Tempo video - 25:50)
A causa di "ordinamento" e "abbandono", penso che tu faccia riferimento alla notazione O grande .
Citando :
If the function f can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n).
In (n-1) + 2(n-1)logn , n cresce non veloce come n*log(n) .
Sembra che trovare il minimo non sia uno dei passaggi dell'algoritmo. Quindi il numero di confronti necessari per trovare il minimo è irrilevante, poiché quel passaggio non viene mai nemmeno eseguito.
Leggi altre domande sui tag algorithms complexity comparison sorting algorithm-analysis