Analisi degli algoritmi (complessità)

Question

Come vengono analizzati gli algoritmi? Che cosa rende quicksort avere una prestazione peggiore nel O(n^2) mentre l'ordinamento di unione ha una prestazione nel caso peggiore O(n log(n))?

Answer 1

Questo è un argomento per un intero semestre. In definitiva, stiamo parlando del limite superiore del numero di operazioni che devono essere completate prima che l'algoritmo termini in base alla dimensione dell'input. Non includiamo i coeffecients (cioè 10N vs 4N^2) perché per N abbastanza grande, non ha più importanza.

Come dimostrare che il big-oh di un algoritmo può essere abbastanza difficile. Richiede una prova formale e ci sono molte tecniche. Spesso un buon modo ad hoc è quello di contare quanti passaggi sui dati l'algoritmo fa. Ad esempio, se il tuo algoritmo ha annidato per cicli, allora per ognuno di N elementi devi operare N volte. Quello sarebbe generalmente O (N^2).

Per unire l'ordinamento, si suddividono i dati a metà ancora e ancora. Ciò richiede log2 (n). E per ogni divisione fai un passaggio sui dati, che fornisce N log (n).

L'ordinamento rapido è un po 'più complicato perché nel caso medio è anche n log (n). Devi immaginare cosa succede se la tua partizione divide i dati in modo tale che ogni volta che ottieni un solo elemento su un lato della partizione. Quindi dovrai dividere i dati n volte invece che log (n) volte che lo rende N^2. Il vantaggio di quicksort è che può essere eseguito sul posto e che di solito ci si avvicina al rendimento N log (n).

Answer 2

Entrambi quicksort e merge sort dividono l'array in due, ordina ogni parte in modo ricorsivo, quindi combina il risultato. Quicksort si divide scegliendo un elemento "pivot" e partizionando l'array in più piccolo o più grande del pivot. Unisci ordina suddivide in modo arbitrario e quindi unisce i risultati in tempo lineare. In entrambi i casi, un singolo passaggio è O (n), e se la dimensione dell'array dimezza ogni volta questo darebbe un numero logaritmico di passi. Quindi ci aspetteremmo O (n log (n)).

Tuttavia, il quicksort ha il peggiore dei casi in cui la divisione è sempre disomogenea, quindi non si ottiene un numero di passi proporzionale alla logaritmica di n, ma un numero di passi proporzionale a n. Unisci ordina suddivide esattamente in due metà (o il più vicino possibile) in modo che non abbia questo problema.

Answer 3

• quick sort ha molte varianti a seconda della selezione perno
• Supponiamo abbiamo sempre selezioniamo primo elemento dell'array come perno

Se la matrice di ingresso è ordinato quindi ordinare rapida sarà solo un tipo di selezione sort! Poiché non si sta realmente dividendo l'array .. si sta selezionando solo il primo elemento in ogni ciclo

D'altro canto l'unire l'ordinamento dividerà sempre l'array di input nello stesso modo, indipendentemente dal suo contenuto!

Nota: la migliore prestazione in divisione e conquista quando la lunghezza delle divisioni è pari -nearly!

Answer 4

1. Questa è un'analisi introduttiva del materiale del corso degli algoritmi.

2. Un'operazione è definita (vale a dire, moltiplicazione) e l'analisi viene eseguita in termini di spazio o tempo.

3. Questa operazione viene conteggiata in termini di spazio o tempo.Tipicamente le analisi vengono eseguite come Tempo che è la variabile dipendente sulla dimensione di input.

Esempio pseudocodice:

foreach $elem in @list 

    op(); 

endfor 

Ci sarà n operazioni eseguite, dove n è la dimensione di @list. Contattalo da solo se non mi credi.

Per analizzare Quicksort e Mergesort richiede un livello decente di ciò che è noto come sofisticazione matematica. In modo approssimativo, risolvete un'equazione differenziale discreta derivata dalla relazione ricorsiva.