[Powered by Google Translate] Probabilmente avete sentito parlare di un algoritmo veloce o efficace per l'esecuzione di vostro compito particolare, ma che cosa significa per un algoritmo di essere veloce o efficiente? Beh, non si sta parlando di una misura in tempo reale, come secondi o minuti. Questo perché hardware e software variano drasticamente. Il mio programma potrebbe funzionare più lento del tuo, perché io sono in esecuzione su un vecchio computer, o perché mi capita di giocare un gioco online video allo stesso tempo, che è hogging tutta la memoria, o potrei essere in esecuzione il mio programma attraverso diversi software che comunica con la macchina in modo diverso a un livello basso. E 'come paragonare mele e arance. Solo perché il mio computer più lento impiega più tempo della tua di restituire una risposta non significa che si ha l'algoritmo più efficiente. 

Quindi, dal momento che non è possibile confrontare direttamente i tempi di esecuzione dei programmi in pochi secondi o minuti, come si fa a confrontare due diversi algoritmi indipendentemente dal loro ambiente hardware o software? Per creare un modo più uniforme di misurazione dell'efficienza algoritmica, gli informatici e matematici hanno inventato concetti per misurare la complessità asintotica di un programma e una notazione chiamata 'Ohnotation Big' per descrivere questo. La definizione formale è che una funzione f (x) corre dell'ordine di g (x) se esiste un po 'di (x) il valore, x ₀ e una costante, C, per cui f (x) è minore o uguale a che costante volte g (x) per ogni x maggiore di x ₀. 

Ma non abbiate paura di distanza dalla definizione formale. Che cosa significa questo in realtà significa in termini meno teorici? Be ', è fondamentalmente un modo di analizzare la velocità di esecuzione di un programma cresce asintoticamente. Cioè, come la dimensione dei fattori aumenta verso l'infinito, dire, si sta ordinamento di un array di dimensioni 1000 rispetto ad un array di dimensione 10. In che modo il tempo di esecuzione del programma di crescere? Per esempio, immaginate contando il numero di caratteri in una stringa il modo più semplice  a piedi attraverso l'intera stringa lettera per lettera e l'aggiunta di 1 a un contatore per ogni personaggio. Questo algoritmo è detto per l'esecuzione in tempo lineare rispetto al numero di caratteri, 'N' nella stringa. In breve, viene eseguito in O (n). Perché questo? Ebbene, utilizzando questo approccio, il tempo richiesto per attraversare l'intera stringa è proporzionale al numero di caratteri. Contare il numero di caratteri di una stringa di 20 caratteri sta per il doppio del tempo necessario per contare i caratteri di una stringa di 10 caratteri, perché si deve guardare a tutti i personaggi e ogni personaggio ha la stessa quantità di tempo per guardare. Come si aumenta il numero di caratteri, il runtime aumenta linearmente con la lunghezza dell'input. 

Ora, immaginate se si decide che il tempo lineare, O (n), non era abbastanza veloce per te? Forse stai memorizzare stringhe enormi, e non può permettersi il tempo in più ci sarebbe voluto attraversare tutti i loro conteggio caratteri uno ad uno. Così, si decide di provare qualcosa di diverso. E se ne sarebbe già memorizzare il numero di caratteri nella stringa, ad esempio, in una variabile chiamata 'len,' nelle prime fasi del programma, prima ancora memorizzato il primo carattere nella stringa? Quindi, tutto ciò che avrebbe dovuto fare ora per trovare la lunghezza della stringa, è verificare quale sia il valore della variabile è. Lei non avrebbe dovuto guardare la stringa stessa a tutti, e accedere al valore di una variabile come len è considerata un'operazione di tempo asintoticamente costante, o O (1). Perché questo? Bene, ricordate che cosa significa complessità asintotica. Come cambia il runtime come la dimensione degli input cresce? 

Diciamo che stavano cercando di ottenere il numero di caratteri di una stringa più grande. Beh, non importa quanto grande a fare la stringa, anche un milione di caratteri, tutto quello che avrei dovuto fare per trovare la lunghezza della corda con questo approccio, è leggere il valore della variabile len, che hai già fatto. La lunghezza di input, cioè la lunghezza della stringa che si sta cercando di trovare, non influisce affatto quanto velocemente il vostro programma viene eseguito. Questa parte del programma sarebbe altrettanto veloce su una stringa di un carattere e mille-stringa di caratteri, ed è per questo che questo programma dovrebbe essere indicato come l'esecuzione in tempo costante rispetto alla dimensione dell'input. 

Naturalmente, c'è un inconveniente. Si spende più spazio di memoria sul vostro computer memorizzare la variabile e il tempo in più che ti porta per fare il deposito effettivo della variabile, ma il punto si ferma, scoprire quanto tempo la stringa è stata non dipende dalla lunghezza della stringa a tutti. Quindi, viene eseguito in O (1) o costante di tempo. Questo certamente non significa necessariamente che il codice viene eseguito in 1 passo, ma non importa quanti passi è, se non cambia con le dimensioni degli ingressi, è ancora asintoticamente costante che noi rappresentiamo come O (1). 

Come si può intuire, ci sono molti diversi tempi di esecuzione O grandi per misurare con gli algoritmi. O (n) ² algoritmi sono asintoticamente più lento di O (n) algoritmi. Cioè, il numero di elementi (n) cresce, alla fine O (n) ² algoritmi ci vorrà più tempo di O (n) gli algoritmi per l'esecuzione. Questo non significa che O (n) algoritmi sempre più veloci di O (n) ² algoritmi, anche nello stesso ambiente, sullo stesso hardware. Forse per le dimensioni di ingresso di piccole dimensioni,  O (n) ² algoritmo potrebbe effettivamente lavorare più velocemente, ma, alla fine, come la dimensione ingresso aumenta verso l'infinito, la O (n) algoritmo ² di runtime finirà per eclissare il runtime del (n) algoritmo O. Proprio come qualsiasi funzione quadratica matematica  finirà per superare qualsiasi funzione lineare, non importa quanto di una testa di avviare la funzione lineare inizia con. Se si lavora con grandi quantità di dati, algoritmi che vengono eseguiti in O (n) ² può davvero finire per rallentare il programma, ma per piccole dimensioni di ingresso, probabilmente non si accorgono neppure. 

Un altro è la complessità asintotica, tempo logaritmico, O (log n). Un esempio di un algoritmo che esegue questo rapidamente è il classico algoritmo di ricerca binaria, per trovare un elemento in un elenco già ordinato di elementi. 

Se non sai cosa fa la ricerca binaria, Te lo spiego per voi molto velocemente. Diciamo che stai cercando il numero 3 in questo array di interi. Si guarda l'elemento centrale della matrice e chiede, "è l'elemento che voglio maggiore, uguale o inferiore a questo?" Se è uguale, allora grande. Hai trovato l'elemento, e il gioco è fatto. Se è maggiore, poi si sa l'elemento deve essere nel lato destro della matrice, e si può solo osservare che, in futuro, e se è più piccolo, poi si sa che deve essere sul lato sinistro. Questo processo viene ripetuto con la minore dimensione della matrice finché l'elemento esatto. 

Questo potente algoritmo riduce la dimensione della matrice a metà con ogni operazione. Così, per trovare un elemento in un array ordinato di dimensione 8, al massimo (log ₂ 8), o tre di queste operazioni, controllando l'elemento centrale, poi tagliando la matrice in mezzo sarà richiesto, considerando che un array di dimensione 16 si (log ₂ 16), o 4 operazioni. Questo è solo 1 operazione di più per un doppio-dimensione dell'array. Raddoppiando la dimensione della matrice aumenta il tempo di esecuzione di solo 1 pezzo di questo codice. Nuovo, controllando l'elemento centrale dell'elenco, quindi splitting. Così, si dice di operare in tempo logaritmico, O (log n). Ma aspetta, tu dici, questo non dipende il punto in cui l'elemento che stai cercando è? Che cosa succede se il primo elemento si guarda sembra essere quella giusta? Poi, ci vuole solo 1 operazione, non importa quanto grande è la lista. 

Beh, è ​​per questo che gli informatici hanno termini più per la complessità asintotica che riflettono il caso migliore e nel caso peggiore performance di un algoritmo. Più propriamente, i limiti superiore e inferiore sul runtime. Nel migliore dei casi per la ricerca binaria, è il nostro elemento proprio lì in mezzo, e si ottiene in tempo costante, non importa quanto grande il resto della matrice è. Il simbolo utilizzato per questo è Ω. Quindi, questo algoritmo è detto per l'esecuzione in Ω (1). Nel migliore dei casi, si trova l'elemento in modo rapido, non importa quanto grande sia la matrice, ma nel caso peggiore, che deve eseguire (log n) controlli parziali della matrice per trovare l'elemento giusto. Limiti del caso peggiore superiori sono indicati con la grande "O" che già conoscete. Quindi, è O (log n), ma Ω (1). 

Una ricerca lineare, per contrasto, in cui si cammina attraverso ogni elemento della matrice per trovare quello che si desidera, è al meglio Ω (1). Anche in questo caso, il primo elemento che si desidera. Quindi, non importa quanto grande sia la matrice è. Nel peggiore dei casi, è l'ultimo elemento dell'array. Quindi, bisogna camminare attraverso tutti gli elementi della matrice n per trovarlo, come se si stesse cercando un 3. Quindi, viene eseguito in O (n) perché è proporzionale al numero di elementi nella matrice. 

Un simbolo più utilizzato è Θ. Questo può essere usato per descrivere algoritmi Qualora i casi migliori e peggiori sono uguali. Questo è il caso nella stringa di lunghezza algoritmi di cui abbiamo parlato in precedenza. Cioè, se lo memorizzare in una variabile prima abbiamo memorizzare la stringa e accedervi in ​​seguito in tempo costante. Non importa quale sia il numero stiamo memorizzare in quella variabile, dovremo guardare. Il caso migliore è, lo guardiamo e trovare la lunghezza della stringa. Quindi Ω (1) o nel caso migliore costante di tempo. Il caso peggiore è, lo guardiamo e trovare la lunghezza della stringa. Quindi, O (1) o costante di tempo nel caso peggiore. Quindi, poiché il caso migliore e peggiore dei casi sono gli stessi, questo può essere detto per funzionare in Θ (1) tempo. 

In sintesi, ci sono buoni modi per ragionare su efficienza codici senza sapere nulla del mondo reale tempo che impiegano per l'esecuzione, che è influenzata da molti fattori esterni, incluso l'hardware differenti, il software, o le specifiche del codice. Inoltre, ci permette di ragionare bene su cosa accadrà quando la dimensione degli aumenti ingressi. 

Se si esegue in O (n) ² algoritmo, o peggio, una O (2 ⁿ) algoritmo, uno dei più rapida crescita tipi, si davvero iniziare a notare il rallentamento quando si inizia a lavorare con grandi quantità di dati. 

E 'la complessità asintotica. Grazie.