Lezioni del corso di Harvard sui fondamenti della programmazione CS50 Compiti CS50, settimana 3, parte 1 Compiti CS50, settimana 3, parte 2
Notazione asintotica
Misurare la velocità di un algoritmo in tempo reale, in secondi e minuti, non è facile. Un programma può funzionare più lentamente di un altro non a causa della sua inefficienza, ma a causa della lentezza del sistema operativo, dell'incompatibilità con l'hardware, della memoria del computer occupata da altri processi... Per misurare l'efficacia degli algoritmi, sono stati inventati concetti universali , indipendentemente dall'ambiente in cui viene eseguito il programma. La complessità asintotica di un problema viene misurata utilizzando la notazione Big O. Siano f(x) e g(x) funzioni definite in un certo intorno di x0, e lì g non si annulla. Allora f è “O” maggiore di g per (x -> x0) se esiste una costante C> 0 , che per tutti gli x da qualche intorno del punto x0 vale la disuguaglianza|f(x)| <= C |g(x)|
Leggermente meno stringente: f è “O” maggiore di g se esiste una costante C>0, che per tutti x > x0 f(x) <= C*g(x)
Non aver paura di la definizione formale! In sostanza, determina l'aumento asintotico del tempo di esecuzione del programma quando la quantità di dati di input cresce verso l'infinito. Ad esempio, stai confrontando l'ordinamento di un array di 1000 elementi e 10 elementi e devi capire come aumenterà il tempo di esecuzione del programma. Oppure devi calcolare la lunghezza di una stringa di caratteri procedendo carattere per carattere e aggiungendo 1 per ogni carattere: c - 1 a - 2 t - 3
la sua velocità asintotica = O(n), dove n è il numero di lettere nella parola. Se conti secondo questo principio, il tempo necessario per contare l'intera riga è proporzionale al numero di caratteri. Il conteggio del numero di caratteri in una stringa di 20 caratteri richiede il doppio del tempo rispetto al conteggio del numero di caratteri in una stringa di dieci caratteri. Immagina che nella variabile length tu abbia memorizzato un valore pari al numero di caratteri nella stringa. Ad esempio, lunghezza = 1000. Per ottenere la lunghezza di una stringa, devi solo accedere a questa variabile e non devi nemmeno guardare la stringa stessa. E non importa come modifichiamo la lunghezza, possiamo sempre accedere a questa variabile. In questo caso, velocità asintotica = O(1). La modifica dei dati di input non cambia la velocità di tale attività; la ricerca viene completata in un tempo costante. In questo caso il programma è asintoticamente costante. Svantaggio: si spreca memoria del computer memorizzando una variabile aggiuntiva e tempo aggiuntivo per aggiornarne il valore. Se pensi che il tempo lineare sia negativo, possiamo assicurarti che può essere molto peggio. Ad esempio, O(n2 ) . Questa notazione significa che man mano che n cresce, il tempo richiesto per scorrere gli elementi (o un'altra azione) aumenterà sempre di più. Ma per n piccoli, gli algoritmi con velocità asintotica O(n 2 ) possono funzionare più velocemente degli algoritmi con velocità asintotica O(n). Ma ad un certo punto la funzione quadratica supererà quella lineare, non c'è modo di aggirarla. Un'altra complessità asintotica è il tempo logaritmico o O(log n). All'aumentare di n, questa funzione aumenta molto lentamente. O(log n) è il tempo di esecuzione del classico algoritmo di ricerca binaria in un array ordinato (ricordate l'elenco telefonico strappato nella lezione?). L'array viene diviso in due, quindi viene selezionata la metà in cui si trova l'elemento e così, riducendo ogni volta della metà l'area di ricerca, si cerca l'elemento. Cosa succede se ci imbattiamo immediatamente in ciò che stiamo cercando, dividendo per la prima volta il nostro array di dati a metà? Esiste un termine per indicare il momento migliore: Omega-grande o Ω(n). Nel caso della ricerca binaria = Ω(1) (trova in tempo costante, indipendentemente dalla dimensione dell'array). La ricerca lineare viene eseguita in tempo O(n) e Ω(1) se l'elemento da cercare è il primo. Un altro simbolo è theta (Θ(n)). Viene utilizzato quando le opzioni migliori e peggiori coincidono. Questo è adatto per un esempio in cui abbiamo memorizzato la lunghezza di una stringa in una variabile separata, quindi per qualsiasi lunghezza è sufficiente fare riferimento a questa variabile. Per questo algoritmo, il caso migliore e quello peggiore sono rispettivamente Ω(1) e O(1). Ciò significa che l'algoritmo viene eseguito nel tempo Θ(1).
Ricerca lineare
Quando apri un browser web, cerchi una pagina, informazioni, amici sui social network, stai facendo una ricerca, proprio come quando cerchi di trovare il paio di scarpe giusto in un negozio. Probabilmente hai notato che l'ordine ha un grande impatto sul modo in cui effettui le ricerche. Se hai tutte le camicie nell'armadio, solitamente è più facile trovare quella che ti serve tra queste piuttosto che tra quelle sparse senza sistema per la stanza. La ricerca lineare è un metodo di ricerca sequenziale, uno per uno. Quando esamini i risultati di ricerca di Google dall'alto verso il basso, stai utilizzando una ricerca lineare. Esempio . Diciamo di avere una lista di numeri:2 4 0 5 3 7 8 1
e dobbiamo trovare lo 0. Lo vediamo subito, ma un programma per computer non funziona in questo modo. Comincia dall'inizio dell'elenco e vede il numero 2. Poi controlla, 2=0? Non lo è, quindi continua e passa al secondo personaggio. Anche lì l'attende il fallimento e solo nella terza posizione l'algoritmo trova il numero richiesto. Pseudocodice per la ricerca lineare: La funzione linearSearch riceve due argomenti come input: la chiave key e l'array array[]. La chiave è il valore desiderato, nell'esempio precedente key = 0. L'array è un elenco di numeri che noi guarderò attraverso. Se non troviamo nulla, la funzione restituirà -1 (una posizione che non esiste nell'array). Se la ricerca lineare trova l'elemento desiderato, la funzione restituirà la posizione in cui si trova l'elemento desiderato nell'array. L'aspetto positivo della ricerca lineare è che funzionerà per qualsiasi array, indipendentemente dall'ordine degli elementi: esamineremo comunque l'intero array. Questa è anche la sua debolezza. Se devi trovare il numero 198 in un array di 200 numeri ordinati, il ciclo for eseguirà 198 passaggi. Probabilmente hai già indovinato quale metodo funziona meglio per un array ordinato?
Ricerca binaria e alberi
Immagina di avere un elenco di personaggi Disney in ordine alfabetico e di dover trovare Topolino. Linearmente ci vorrebbe molto tempo. E se usiamo il "metodo di dividere la directory a metà", arriviamo direttamente a Jasmine e possiamo tranquillamente scartare la prima metà dell'elenco, rendendoci conto che Topolino non può essere lì. Utilizzando lo stesso principio, scartiamo la seconda colonna. Proseguendo questa strategia troveremo Topolino in un paio di passaggi. Troviamo il numero 144. Dividiamo la lista a metà e arriviamo al numero 13. Valutiamo se il numero che cerchiamo è maggiore o minore di 13. 13 < 144, quindi possiamo ignorare tutto ciò che si trova a sinistra di 13 e questo numero stesso. Ora il nostro elenco di ricerca si presenta così: C'è un numero pari di elementi, quindi scegliamo il principio in base al quale selezioniamo il "centro" (più vicino all'inizio o alla fine). Diciamo che abbiamo scelto fin dall'inizio la strategia della prossimità. In questo caso, il nostro "centro" = 55. 55 < 144. Scartiamo nuovamente la metà sinistra della lista. Fortunatamente per noi, il numero medio successivo è 144. Abbiamo trovato 144 in un array di 13 elementi utilizzando la ricerca binaria in soli tre passaggi. Una ricerca lineare gestirebbe la stessa situazione in un massimo di 12 passaggi. Poiché questo algoritmo riduce della metà il numero di elementi nell'array ad ogni passaggio, troverà quello richiesto in tempo asintotico O(log n), dove n è il numero di elementi nell'elenco. Cioè, nel nostro caso, il tempo asintotico = O(log 13) (questo è poco più di tre). Pseudocodice della funzione di ricerca binaria: La funzione accetta 4 argomenti come input: la chiave desiderata, l'array di dati array [], in cui si trova quello desiderato, min e max sono puntatori al numero massimo e minimo nell'array, che stiamo esaminando questo passaggio dell'algoritmo. Per il nostro esempio inizialmente è stata fornita la seguente immagine: Analizziamo ulteriormente il codice. il punto medio è il nostro centro dell'array. Dipende dai punti estremi ed è centrato tra loro. Dopo aver trovato la metà, controlliamo se è inferiore al nostro numero di chiave. Se è così, allora anche la chiave è maggiore di qualsiasi numero a sinistra del centro e possiamo chiamare di nuovo la funzione binaria, solo che ora il nostro min = punto medio + 1. Se risulta che chiave < punto medio, possiamo scartare quel numero stesso e tutti i numeri, che giacciono alla sua destra. E chiamiamo una ricerca binaria attraverso l'array dal numero min fino al valore (punto medio – 1). Infine, il terzo ramo: se il valore nel punto medio non è né maggiore né minore della chiave, non ha altra scelta che essere il numero desiderato. In questo caso, lo restituiamo e terminiamo il programma. Infine, può succedere che il numero che stai cercando non sia affatto nell'array. Per tenere conto di questo caso, eseguiamo il seguente controllo: E restituiamo (-1) per indicare che non abbiamo trovato nulla. Sai già che la ricerca binaria richiede l'ordinamento dell'array. Pertanto, se abbiamo un array non ordinato in cui dobbiamo trovare un determinato elemento, abbiamo due opzioni:- Ordina l'elenco e applica la ricerca binaria
- Mantieni l'elenco sempre ordinato aggiungendo e rimuovendo contemporaneamente elementi da esso.
- È un albero (una struttura dati che emula una struttura ad albero - ha una radice e altri nodi (foglie) collegati da "rami" o bordi senza cicli)
- Ogni nodo ha 0, 1 o 2 figli
- Entrambi i sottoalberi sinistro e destro sono alberi di ricerca binari.
- Tutti i nodi del sottoalbero sinistro di un nodo X arbitrario hanno valori della chiave dati inferiori al valore della chiave dati del nodo X stesso.
- Tutti i nodi nel sottoalbero destro di un nodo X arbitrario hanno valori della chiave dati maggiori o uguali al valore della chiave dati del nodo X stesso.
- L'opzione più semplice: dobbiamo eliminare un vertice che non ha figli. Ad esempio, il numero 7 che abbiamo appena aggiunto. In questo caso seguiamo semplicemente il percorso fino al vertice con questo numero e lo cancelliamo.
- Un vertice ha un vertice figlio. In questo caso è possibile eliminare il vertice desiderato, ma il suo discendente deve essere collegato al “nonno”, cioè al vertice da cui è cresciuto il suo immediato antenato. Ad esempio, dallo stesso albero dobbiamo rimuovere il numero 3. In questo caso uniamo il suo discendente, uno, insieme all'intero sottoalbero a 5. Questo viene fatto semplicemente, poiché tutti i vertici a sinistra di 5 saranno inferiore a questo numero (e inferiore alla tripla remota).
- Il caso più difficile è quando il vertice da eliminare ha due figli. Ora la prima cosa che dobbiamo fare è trovare il vertice in cui è nascosto il valore successivo più grande, dobbiamo scambiarli e quindi eliminare il vertice desiderato. Si noti che il successivo vertice con il valore più alto non può avere due figli, quindi il figlio sinistro sarà il miglior candidato per il valore successivo. Rimuoviamo dal nostro albero il nodo radice 13. Per prima cosa cerchiamo il numero più vicino a 13, che è maggiore di esso. Questo è 21. Scambia 21 e 13 ed elimina 13.
Algoritmi di ordinamento
C'è una serie di numeri. Dobbiamo sistemarlo. Per semplicità, supponiamo di ordinare i numeri interi in ordine crescente (dal più piccolo al più grande). Esistono diversi modi noti per eseguire questo processo. Inoltre, puoi sempre inventare l'argomento e inventare una modifica dell'algoritmo.Ordinamento per selezione
L'idea principale è dividere la nostra lista in due parti, ordinate e non ordinate. Ad ogni passo dell'algoritmo, un nuovo numero viene spostato dalla parte non ordinata a quella ordinata, e così via finché tutti i numeri non si trovano nella parte ordinata.- Trova il valore minimo non ordinato.
- Scambiamo questo valore con il primo valore non ordinato, posizionandolo così alla fine dell'array ordinato.
- Se sono rimasti valori non ordinati, tornare al passaggio 1.
Ordinamento delle bolle
L'algoritmo di bubble sort è uno dei più semplici. Percorriamo l'intero array e confrontiamo 2 elementi vicini. Se sono nell'ordine sbagliato, li scambiamo. Al primo passaggio, alla fine apparirà l'elemento più piccolo (“float”) (se ordiniamo in ordine decrescente). Ripetere il primo passaggio se nel passaggio precedente è stato completato almeno uno scambio. Ordiniamo l'array. Passaggio 1: esaminare l'array. L'algoritmo inizia con i primi due elementi, 8 e 6, e controlla se sono nell'ordine corretto. 8 > 6, quindi li invertiamo. Successivamente guardiamo il secondo e il terzo elemento, ora questi sono 8 e 4. Per gli stessi motivi, li scambiamo. Per la terza volta confrontiamo 8 e 2. In totale facciamo tre scambi (8, 6), (8, 4), (8, 2). Il valore 8 "fluttua" alla fine dell'elenco nella posizione corretta. Passaggio 2: scambiare (6,4) e (6,2). 6 è ora in penultima posizione e non c'è bisogno di confrontarlo con la “coda” già ordinata della lista. Passaggio 3: scambia 4 e 2. I quattro "galleggiano" al posto giusto. Passaggio 4: esaminiamo l'array, ma non abbiamo nulla da modificare. Ciò segnala che l'array è completamente ordinato. E questo è il codice dell'algoritmo. Prova a implementarlo in C! Il bubble sort richiede un tempo O(n 2 ) nel caso peggiore (tutti i numeri sono sbagliati), poiché dobbiamo fare n passi ad ogni iterazione, di cui ci sono anche n. Infatti, come nel caso dell'algoritmo di ordinamento per selezione, il tempo sarà leggermente inferiore (n 2 /2 – n/2), ma questo può essere trascurato. Nel migliore dei casi (se tutti gli elementi sono già presenti), possiamo farlo in n passaggi, ovvero Ω(n), poiché dovremo solo scorrere l'array una volta e assicurarci che tutti gli elementi siano al loro posto (cioè anche n-1 elementi).Ordinamento di inserimento
L'idea principale di questo algoritmo è dividere il nostro array in due parti, ordinate e non ordinate. Ad ogni passo dell'algoritmo, il numero si sposta dalla parte non ordinata a quella ordinata. Diamo un'occhiata a come funziona l'ordinamento per inserzione utilizzando l'esempio seguente. Prima di iniziare, tutti gli elementi sono considerati non ordinati. Passaggio 1: prendi il primo valore non ordinato (3) e inseriscilo nel sottoarray ordinato. A questo punto, l'intero sottoarray ordinato, il suo inizio e la sua fine saranno proprio questi tre. Passaggio 2: poiché 3 > 5, inseriremo 5 nel sottoarray ordinato a destra di 3. Passaggio 3: ora lavoriamo sull'inserimento del numero 2 nel nostro array ordinato. Confrontiamo 2 con valori da destra a sinistra per trovare la posizione corretta. Dato che 2 < 5 e 2 < 3 abbiamo raggiunto l'inizio del sottoarray ordinato. Dobbiamo quindi inserire 2 a sinistra di 3. Per fare ciò, sposta 3 e 5 a destra in modo che ci sia spazio per il 2 e inseriscilo all'inizio dell'array. Passaggio 4. Siamo fortunati: 6 > 5, quindi possiamo inserire quel numero subito dopo il numero 5. Passaggio 5. 4 < 6 e 4 < 5, ma 4 > 3. Pertanto, sappiamo che 4 deve essere inserito per a destra di 3. Ancora una volta, siamo costretti a spostare 5 e 6 a destra per creare uno spazio per 4. Fatto! Algoritmo generalizzato: prendi ogni elemento non ordinato di n e confrontalo con i valori nel sottoarray ordinato da destra a sinistra finché non troviamo una posizione adatta per n (ovvero nel momento in cui troviamo il primo numero inferiore a n) . Quindi spostiamo tutti gli elementi ordinati che si trovano a destra di questo numero a destra per fare spazio al nostro n, e lo inseriamo lì, espandendo così la parte ordinata dell'array. Per ogni elemento non ordinato n è necessario:- Determina la posizione nella parte ordinata dell'array in cui deve essere inserito n
- Sposta gli elementi ordinati a destra per creare uno spazio per n
- Inserisci n nello spazio risultante nella parte ordinata dell'array.
GO TO FULL VERSION