Ho familiarità con le basi dell'analisi run-time, ad esempio ciò che rende certi tipi di codice O (n) e O (n ^ 2). Ma ho davvero dei problemi nell'apprendere, comprendere e ricordare davvero come analizzare pezzi di codice che girano in altre complessità come O (n log n) o O (2 ^ n). Sto cercando risorse che spieghino in termini semplici come funzionano queste altre complessità e alcuni problemi pratici per forzare davvero la mia comprensione.
Penso che il problema più profondo qui sia l'analisi dell'algoritmo. È facile capire quale sia la complessità del runtime di un algoritmo se si sa cosa sta effettivamente succedendo nell'algoritmo.
Un libro come Introduzione agli algoritmi ti fornirà tutti gli strumenti necessari e più che sufficienti problemi pratici e dovresti vedere la prima risposta qui per ottenere una grande panoramica del diversi runtime.
Nel complesso, tuttavia, la pratica rende perfetti. Quando si moltiplicano due numeri, non si "ricorda" come funziona la moltiplicazione, ma li si moltiplica perché è la seconda natura. Dopo aver analizzato abbastanza algoritmi, stai per capire cosa sta realmente accadendo. Non è necessario "ricordare" come funziona l'analisi dell'algoritmo: basta osservare l'algoritmo, vedere cosa sta succedendo e capire cosa sta succedendo.
Ciò che funziona per me è conoscere un po 'di teoria dell'informazione. Nello specifico, quando un programma esegue un'istruzione IF come questa:
if (test){
... code A ...
} else {
... code B ...
}
test ha una certa probabilità P di essere true , e 1-P di essere false , e le informazioni acquisite (nel contatore del programma) quando si effettua quel ramo è I = log (1 / P) (base 2).
Se P è 0.5 (è altrettanto probabile che sia vero come falso), allora I = log (2) = 1 non importa quale ramo è preso. Questa è la quantità che il contatore del programma "impara" nel fare questa scelta.
Ora Entropy (parola spaventosa, lo so) è solo informazione media acquisita su tutti i rami, che è 1, giusto? Quindi potresti dire che il ramo fa 1 bit di lavoro quando viene eseguito.
Supponiamo che P non sia 0,5. Supponiamo che tu stia facendo una ricerca lineare in una tabella di 1024 voci. Il primo test che fai dice "La voce 0 è quella che sto cercando?". Se la risposta potrebbe essere ovunque, allora P = 1/1024 e 1-P = 1023/1024.
Quindi se l'elemento che stai cercando è il primo, ottieni log (1024) = dieci bit , ma se non lo è, ottieni solo il log (1024 / 1023) o essenzialmente zero bit . Qual è l'entropia? È la somma delle informazioni che ottieni su ciascun ramo moltiplicato per la probabilità di quel ramo. È 1/1024 * 10 + 1023/1024 * 0, che è circa 1 / 102,4. Quel test "impara" meno di un centesimo di bit in media.
Poiché per trovare un elemento in una tabella di immissione 1024, devi imparare 10 bit, puoi vedere perché la ricerca lineare è lenta. Infatti, se N è il numero di bit che devi imparare, è esponenziale!
Ecco perché le ricerche basate su punti decisionali binari altrettanto probabili sono O (logN). Un modo per fare una ricerca più veloce è indexing . Ecco dove hai un indice e usalo per localizzare un elemento di un array. Se la matrice è lunga 1024 elementi, è come un punto di decisione con 1024 risultati. Se sono tutti ugualmente probabili, qual è l'entropia? È 1/1024 * log (1024) + 1/1024 * log (1024) ... per 1024 termini, che esce a - dieci bit . Impari tutti e dieci i bit in una singola operazione!
OK, che ne dici di ordinare? Se hai N elementi, devi cercare dove ognuno appartiene all'array, quindi costa sostanzialmente N volte il costo della ricerca. Non potrebbe essere più semplice.
L'analisi di algoritmi complessi richiede molto background matematico. Per un aggiornamento sull'analisi degli algoritmi standard puoi fare riferimento ai libri.
Se hai bisogno di un punto di partenza per l'analisi degli algoritmi suggerisco di leggere alcuni libri sugli algoritmi. Il miglior libro che posso consultare per analizzare gli algoritmi è Introduzione agli algoritmi .
Se ti piacerebbe frequentare le lezioni piuttosto che leggere ci sono molti video su questo argomento. Ad esempio conferenze del MIT .
Quello che puoi provare è trovare l'espressione analitica che è uguale al costo dell'algoritmo con cui stai lavorando.
In molti casi, questa espressione potrebbe essere una somma (di solito per cicli annidati). Tuttavia, per un algoritmo ricorsivo, potresti esprimere il suo costo con una formula ricorsiva che dovrai risolvere. Ad esempio, il costo di una ricerca binaria può essere espresso con la formula T (n) = floor (T (n / 2)) + 1 (worst case). Risolvendo la formula scopriamo che la risposta è Θ (log (n)).
Per gli algoritmi di ordinamento, avremo solitamente il caso medio Θ (n ^ 2) o Θ (n log (n)) (il quicksort è Θ (n log (n)) nel caso medio ma Θ (n ^ 2) nel caso peggiore !!). A volte il costo trovato risolvendo una formula ricorsiva potrebbe anche essere esponenziale (vedi il problema Torre di Hanoi), e questo è qualcosa di cui preoccuparsi.
Infine, usando il Teorema Master quando è possibile, puoi stimare la complessità del tempo di esecuzione senza risolvere esplicitamente la ricorsione, che è molto utile.
Leggi altre domande sui tag self-improvement performance algorithms complexity