Share
Presumo che tu sia un programmatore di computer. Forse sei un nuovo studente di informatica o forse sei un ingegnere del software con esperienza. Indipendentemente da dove ti trovi su quello spettro, gli algoritmi e le strutture dati sono importanti. Non solo come concetti teorici, ma come elementi costitutivi utilizzati per creare soluzioni ai problemi aziendali.
Certo, potresti sapere come usare il C # Elenco o Pila classe, ma capisci cosa sta succedendo sotto le coperte? In caso contrario, stai davvero prendendo le decisioni migliori su quali algoritmi e strutture di dati stai usando?
La comprensione significativa degli algoritmi e delle strutture dati inizia con il modo di esprimere e confrontare i relativi costi.
Quando parliamo di misurare il costo o la complessità di un algoritmo, ciò di cui stiamo realmente parlando sta eseguendo un'analisi dell'algoritmo quando i set di input sono molto grandi. L'analisi di ciò che accade quando il numero di input diventa molto grande viene definito analisi asintotica. Come cambia la complessità dell'algoritmo se applicata a dieci, o mille o dieci milioni di elementi? Se un algoritmo viene eseguito in cinque millisecondi con un migliaio di elementi, cosa possiamo dire su ciò che accadrà quando viene eseguito con un milione? Ci vorranno cinque o cinque anni? Non preferiresti capirlo prima del tuo cliente?
Questa roba conta!
Il tasso di crescita descrive il modo in cui la complessità di un algoritmo cambia al crescere delle dimensioni dell'input. Questo è comunemente rappresentato usando la notazione Big-O. La notazione Big-O utilizza una O maiuscola ("ordine") e una formula che esprime la complessità dell'algoritmo. La formula può avere una variabile, n, che rappresenta la dimensione dell'input. Le seguenti sono alcune funzioni di ordine comuni che vedremo in questo libro ma questa lista non è completa.
Un algoritmo O (1) è uno la cui complessità è costante indipendentemente dall'ampiezza della dimensione dell'input. Il "1" non significa che ci sia solo una operazione o che l'operazione richieda una piccola quantità di tempo. Potrebbe richiedere un microsecondo o potrebbe richiedere un'ora. Il punto è che la dimensione dell'ingresso non influenza il tempo richiesto dall'operazione.
public int GetCount (int [] items) return items.Length;
Un algoritmo O (n) è un algoritmo la cui complessità cresce linearmente con la dimensione dell'input. È ragionevole aspettarsi che se una dimensione di input di uno impiega cinque millisecondi, un input di mille elementi richiederà cinque secondi.
Spesso è possibile riconoscere un algoritmo O (n) cercando un meccanismo di loop che accede a ciascun membro.
GetSum pubblico lungo (int [] items) long sum = 0; foreach (int i in items) sum + = i; return sum;
Un algoritmo O (log n) è un algoritmo la cui complessità è logaritmica rispetto alle sue dimensioni. Molti algoritmi di divisione e conquista rientrano in questo bucket. L'albero di ricerca binario contiene il metodo implementa un algoritmo O (log n).
Un algoritmo linearithmic, o loglinear, è un algoritmo che ha una complessità di O (n log n). Alcuni algoritmi di divisione e conquista rientrano in questo bucket. Vedremo due esempi quando guardiamo l'unire sort e l'ordinamento rapido.
Un algoritmo O (n ^ 2) è uno la cui complessità è quadratica rispetto alla sua dimensione. Anche se non sempre è evitabile, l'uso di un algoritmo quadratico è un segno potenziale che è necessario riconsiderare l'algoritmo o la scelta della struttura dei dati. Gli algoritmi quadratici non si adattano bene all'aumentare delle dimensioni di input. Ad esempio, un array con 1000 interi richiederebbe il completamento di 1.000.000 di operazioni. Un'input con un milione di articoli richiederebbe un trilione (1.000.000.000.000) di operazioni. Per mettere questo in prospettiva, se ogni operazione richiede un millisecondo per essere completata, un algoritmo O (n ^ 2) che riceve un input di un milione di elementi richiederà circa 32 anni per essere completato. Realizzare quell'algoritmo 100 volte più velocemente richiederebbe ancora 84 giorni.
Vedremo un esempio di un algoritmo quadratico quando osserveremo l'ordinamento delle bolle.
Quando diciamo che un algoritmo è O (n), cosa stiamo realmente dicendo? Stiamo dicendo che l'algoritmo è O (n) in media? O stiamo descrivendo lo scenario migliore o peggiore?
Generalmente intendiamo lo scenario peggiore a meno che il caso comune e il caso peggiore siano molto diversi. Ad esempio, vedremo esempi in questo libro in cui un algoritmo è O (1) in media, ma periodicamente diventa O (n) (vedere ArrayList.Add). In questi casi descriverò l'algoritmo come O (1) in media e poi spiegherò quando la complessità cambia.
Il punto chiave è che dire O (n) non significa che sono sempre n operazioni. Potrebbe essere di meno, ma non dovrebbe essere più.
Quando misuriamo algoritmi e strutture dati, di solito parliamo di una di queste due cose: la quantità di tempo necessario per completare l'operazione (complessità operativa) o la quantità di risorse (memoria) utilizzate da un algoritmo (complessità delle risorse).
Un algoritmo che funziona dieci volte più velocemente ma utilizza una memoria dieci volte maggiore potrebbe essere perfettamente accettabile in un ambiente server con una grande quantità di memoria disponibile, ma potrebbe non essere appropriato in un ambiente embedded in cui la memoria disponibile è seriamente limitata.
In questo libro mi concentrerò principalmente sulla complessità operativa, ma nella sezione Algoritmi di ordinamento vedremo alcuni esempi di complessità delle risorse.
Alcuni esempi specifici di cose che potremmo misurare includono:
Il contesto dell'operazione eseguita tipicamente ti dirà che tipo di misurazione viene eseguita.
Ad esempio, discutendo la complessità di un algoritmo che cerca un elemento all'interno di una struttura dati, stiamo quasi certamente parlando di operazioni di confronto. La ricerca è generalmente un'operazione di sola lettura, quindi non dovrebbe esserci alcuna necessità di eseguire assegnazioni o allocare memoria.
Tuttavia, quando parliamo di ordinamento dei dati, potrebbe essere logico supporre che potremmo parlare di confronti, assegnazioni o allocazioni. Nei casi in cui ci può essere ambiguità, indico il tipo di misura a cui la complessità si riferisce effettivamente.
Questo completa la prima parte su algoritmi e strutture dati. Successivamente, passeremo all'elenco collegato.
Accentsconagua