Ciao! La conferenza di oggi sarà un po' diversa dalle altre. Differirà in quanto è correlato solo indirettamente a Java. Tuttavia, questo argomento è molto importante per ogni programmatore. Parleremo di algoritmi . Cos'è un algoritmo? In termini semplici, questa è una determinata sequenza di azioni che devono essere eseguite per ottenere il risultato desiderato . Usiamo spesso algoritmi nella vita di tutti i giorni. Ad esempio, ogni mattina ti trovi di fronte a un compito: venire a scuola o al lavoro e allo stesso tempo essere:
Vestito
Pulito
Ben nutriti
Quale algoritmo ti permetterà di ottenere questo risultato?
Svegliati con la sveglia.
Fatti una doccia, lavati la faccia.
Preparare la colazione, preparare il caffè/tè.
Mangiare.
Se non hai stirato i tuoi vestiti dalla sera, stirali.
Vestirsi.
Uscire di casa.
Questa sequenza di azioni ti consentirà sicuramente di ottenere il risultato desiderato. Nella programmazione, il punto centrale del nostro lavoro è risolvere costantemente i problemi. Una parte significativa di questi compiti può essere eseguita utilizzando algoritmi già noti. Ad esempio, ti trovi di fronte a un compito: ordinare un elenco di 100 nomi in un array . Questo compito è abbastanza semplice, ma può essere risolto in diversi modi. Ecco una soluzione: Algoritmo per ordinare i nomi in ordine alfabetico:
Acquista o scarica su Internet l'edizione 1966 del "Dizionario dei nomi personali russi".
Trova tutti i nomi del nostro elenco in questo dizionario.
Annota su un foglio di carta in quale pagina del dizionario si trova il nome.
Metti in ordine i nomi utilizzando le note su un pezzo di carta.
Una tale sequenza di azioni ci consentirà di risolvere il nostro problema? Sì, lo consentirà completamente. Questa soluzione sarà efficace ? Difficilmente. Qui arriviamo ad un'altra proprietà molto importante degli algoritmi: la loro efficienza . Il problema può essere risolto in diversi modi. Ma sia nella programmazione che nella vita di tutti i giorni scegliamo il metodo che sarà più efficace. Se il tuo compito è preparare un panino con il burro, puoi ovviamente iniziare seminando il grano e mungendo una mucca. Ma questa sarà una soluzione inefficace: richiederà molto tempo e costerà molti soldi. Per risolvere il tuo semplice problema, puoi semplicemente acquistare pane e burro. E l’algoritmo con grano e mucca, sebbene permetta di risolvere il problema, è troppo complesso per essere applicato nella pratica. Per valutare la complessità degli algoritmi nella programmazione, è stata creata una notazione speciale chiamata Big-O (“big O”) . Big-O permette di stimare quanto il tempo di esecuzione di un algoritmo dipende dai dati che vi vengono passati . Diamo un'occhiata all'esempio più semplice: il trasferimento dei dati. Immagina di dover trasmettere alcune informazioni sotto forma di file su una lunga distanza (ad esempio 5000 chilometri). Quale algoritmo sarà il più efficiente? Dipende dai dati con cui deve lavorare. Ad esempio, abbiamo un file audio di 10 megabyte. In questo caso, l'algoritmo più efficiente sarebbe trasferire il file su Internet. Ci vorranno solo un paio di minuti! Quindi, diamo nuovamente voce al nostro algoritmo: "Se è necessario trasferire informazioni sotto forma di file su una distanza di 5000 chilometri, è necessario utilizzare la trasmissione dei dati su Internet". Grande. Ora analizziamolo. Risolve il nostro problema? In generale sì, lo risolve completamente. Ma cosa si può dire della sua complessità? Hmm, ora è qui che le cose si fanno interessanti. Il fatto è che il nostro algoritmo dipende molto dai dati in arrivo, ovvero dalla dimensione dei file. Ora abbiamo 10 megabyte e va tutto bene. Cosa succede se dobbiamo trasferire 500 megabyte? 20 gigabyte? 500 terabyte? 30 petabyte? Il nostro algoritmo smetterà di funzionare? No, tutte queste quantità di dati possono ancora essere trasferite. Ci vorrà più tempo per completarlo? Si lo farà! Ora conosciamo una caratteristica importante del nostro algoritmo: maggiore è la dimensione dei dati da trasferire, più tempo impiegherà l'algoritmo per completarsi . Ma vorremmo capire più precisamente in cosa consiste questa relazione (tra la dimensione dei dati e il tempo necessario per trasferirli). Nel nostro caso, la complessità dell’algoritmo sarà lineare. “Lineare” significa che all'aumentare del volume dei dati, il tempo per la loro trasmissione aumenterà in modo approssimativamente proporzionale. Se sono presenti 2 volte più dati, il trasferimento richiederà 2 volte più tempo. Se sono presenti 10 volte più dati, il tempo di trasferimento aumenterà di 10 volte. Usando la notazione Big-O, la complessità del nostro algoritmo è definita come O(N) . Questa notazione è meglio ricordarla per riferimento futuro; viene sempre utilizzata per algoritmi con complessità lineare. Nota: qui non stiamo affatto parlando di varie cose "variabili": la velocità di Internet, la potenza del nostro computer e così via. Quando si valuta la complessità di un algoritmo, ciò semplicemente non ha senso: non abbiamo comunque alcun controllo su di esso. Big-O valuta l’algoritmo stesso, indipendentemente dall’“ambiente” in cui dovrà operare. Continuiamo con il nostro esempio. Diciamo che alla fine risulta che la dimensione dei file da trasferire è di 800 terabyte. Se li trasmettiamo via Internet, il problema, ovviamente, sarà risolto. C'è solo un problema: la trasmissione su un collegamento moderno standard (a 100 megabit al secondo) che la maggior parte di noi utilizza nelle nostre case richiederà circa 708 giorni. Quasi 2 anni! :O Quindi, il nostro algoritmo chiaramente non è adatto qui. Abbiamo bisogno di qualche altra soluzione! All’improvviso arriva in nostro aiuto il colosso informatico Amazon! Il suo servizio Amazon Snowmobile ti consente di caricare grandi quantità di dati in unità di archiviazione mobili e di consegnarli all'indirizzo desiderato tramite camion! Quindi abbiamo un nuovo algoritmo! "Se è necessario trasferire informazioni sotto forma di file su una distanza di 5.000 chilometri e il processo richiederà più di 14 giorni se trasferito tramite Internet, è necessario utilizzare il trasporto su camion di Amazon." La cifra di 14 giorni è stata qui scelta a caso: diciamo che è il periodo massimo che possiamo permetterci. Analizziamo il nostro algoritmo. E la velocità? Anche se il camion viaggia a soli 50 km/h, in sole 100 ore percorrerà 5.000 chilometri. Sono poco più di quattro giorni! Questo è molto meglio dell'opzione di trasmissione Internet. Che dire della complessità di questo algoritmo? Sarà anch'esso lineare, O(N)? No, non lo farà. Dopotutto, al camion non importa quanto lo carichi: guiderà comunque all'incirca alla stessa velocità e arriverà in orario. Sia che abbiamo 800 terabyte, o 10 volte più dati, il camion arriverà comunque in 5 giorni. In altre parole, l’algoritmo per la consegna dei dati tramite camion ha una complessità costante . “Costante” significa che non dipende dai dati passati all’algoritmo. Metti una chiavetta da 1 GB nel camion e arriverà in 5 giorni. Metti lì i dischi con 800 terabyte di dati e arriverà in 5 giorni. Quando si utilizza Big-O, la complessità costante è indicata come O(1) . Dato che abbiamo conosciuto O(N) eO(1) , diamo ora un'occhiata ad altri esempi da "programmatore" :) Diciamo che ti viene dato un array di 100 numeri e il compito è stampare ciascuno di essi sulla console. Scrivi un ciclo regolare forche esegue questa attività
Qual è la complessità dell'algoritmo scritto? Lineare, O(N). Il numero di azioni che il programma deve eseguire dipende esattamente da quanti numeri gli sono stati passati. Se nella matrice sono presenti 100 numeri, le azioni (output sullo schermo) saranno 100. Se nella matrice sono presenti 10.000 numeri, sarà necessario eseguire 10.000 azioni. Il nostro algoritmo può essere migliorato? NO. In ogni caso dovremo effettuare N passaggi attraverso l'array ed eseguire N output sulla console. Diamo un'occhiata a un altro esempio.
Ne abbiamo uno vuoto LinkedListin cui inseriamo diversi numeri. Dobbiamo stimare la complessità dell'algoritmo per inserire un singolo numero nel LinkedListnostro esempio e come dipende dal numero di elementi nell'elenco. La risposta è O(1) - complessità costante . Perché? Nota: ogni volta inseriamo un numero all'inizio della lista. Inoltre, come ricordi, quando inserisci numeri negli LinkedListelementi, non vengono spostati da nessuna parte: i collegamenti vengono ridefiniti (se all'improvviso hai dimenticato come funziona LinkedList, dai un'occhiata a una delle nostre vecchie lezioni ). Se ora il primo numero della nostra lista è il numero х, e inseriamo il numero y all'inizio della lista, basterà:
x.previous = y;
y.previous =null;
y.next = x;
Per questa ridefinizione dei riferimenti, non ci importa quanti numeri ci siano adessoLinkedList : almeno uno, almeno un miliardo. La complessità dell'algoritmo sarà costante - O(1).
Complessità logaritmica
Niente panico! :) Se la parola “logaritmico” ti fa venire voglia di chiudere la lezione e non continuare a leggere, aspetta un paio di minuti. Non ci saranno difficoltà matematiche qui (ci sono molte spiegazioni simili in altri posti) e analizzeremo tutti gli esempi “sulle dita”. Immagina che il tuo compito sia trovare un numero specifico in una matrice di 100 numeri. Più precisamente, controlla se è presente. Non appena viene trovato il numero richiesto, la ricerca deve essere interrotta e nella console deve essere visualizzata la voce "Il numero richiesto è stato trovato!". Il suo indice nell'array = ...." Come risolveresti un problema del genere? Qui la soluzione è ovvia: è necessario scorrere gli elementi dell'array uno per uno, iniziando dal primo (o dall'ultimo) e verificare se il numero corrente coincide con quello desiderato. Di conseguenza, il numero di azioni dipende direttamente dal numero di elementi nell'array. Se abbiamo 100 numeri, dobbiamo passare all'elemento successivo 100 volte e controllare il numero per una corrispondenza 100 volte. Se ci sono 1000 numeri, i passaggi di controllo saranno 1000. Questa è ovviamente complessità lineare, O(N) . Ora aggiungeremo una precisazione al nostro esempio: l'array in cui devi trovare un numero è ordinato in ordine crescente . Questo cambia qualcosa per il nostro compito? Possiamo ancora cercare il numero desiderato con la forza bruta. Ma possiamo usare invece il noto algoritmo di ricerca binaria . Nella riga superiore dell'immagine vediamo un array ordinato. In esso dobbiamo trovare il numero 23. Invece di ripetere i numeri, dividiamo semplicemente l'array in 2 parti e controlliamo il numero medio nell'array. Troviamo il numero che si trova nella cella 4 e lo controlliamo (seconda riga nella foto). Questo numero è 16 e stiamo cercando 23. Il numero attuale è inferiore. Cosa significa questo? Che non è necessario controllare tutti i numeri precedenti (che si trovano fino al numero 16) : saranno sicuramente inferiori a quello che stiamo cercando, perché il nostro array è ordinato! Continuiamo la ricerca tra i restanti 5 elementi. Fai attenzione:Abbiamo fatto solo un controllo, ma abbiamo già eliminato la metà delle opzioni possibili. Ci restano solo 5 elementi. Ripeteremo il nostro passaggio: dividiamo nuovamente l'array rimanente per 2 e prendiamo nuovamente l'elemento centrale (riga 3 nella figura). Questo numero è 56 ed è più grande di quello che stiamo cercando. Cosa significa questo? Che scartiamo altre 3 opzioni: il numero 56 stesso e due numeri successivi (sono decisamente maggiori di 23, perché l'array è ordinato). Ci restano solo 2 numeri da controllare (l'ultima riga nella figura): numeri con indici di array 5 e 6. Controlliamo il primo, ed è quello che stavamo cercando: il numero 23! Il suo indice = 5! Diamo un'occhiata ai risultati del nostro algoritmo e poi ne capiremo la complessità. (A proposito, ora capisci perché si chiama binario: la sua essenza è dividere costantemente i dati per 2). Il risultato è impressionante! Se cercassimo il numero desiderato utilizzando la ricerca lineare avremmo bisogno di 10 controlli, ma con la ricerca binaria ce la faremo in 3! Nel peggiore dei casi, ce ne sarebbero 4, se nell'ultimo passaggio il numero di cui avevamo bisogno risultasse essere il secondo e non il primo. E la sua complessità? Questo è un punto molto interessante :) L'algoritmo di ricerca binaria dipende molto meno dal numero di elementi nell'array rispetto all'algoritmo di ricerca lineare (ovvero l'enumerazione semplice). Con 10 elementi nell'array, la ricerca lineare richiederà un massimo di 10 controlli e la ricerca binaria richiederà un massimo di 4 controlli. La differenza è 2,5 volte. Ma per un array di 1000 elementi, la ricerca lineare avrà bisogno di 1000 controlli e la ricerca binaria ne richiederà solo 10 ! La differenza è già 100 volte! Fai attenzione:il numero di elementi nell'array è aumentato di 100 volte (da 10 a 1000) e il numero di controlli necessari per la ricerca binaria è aumentato solo di 2,5 volte, da 4 a 10. Se raggiungiamo 10.000 elementi , la differenza è ancora più impressionante: 10.000 controlli per la ricerca lineare e un totale di 14 controlli per il binario. E ancora: il numero degli elementi è aumentato di 1000 volte (da 10 a 10000), ma il numero di controlli è aumentato solo di 3,5 volte (da 4 a 14). La complessità dell'algoritmo di ricerca binaria è logaritmica o, nella notazione Big-O, O(log n) . Perché si chiama così? Un logaritmo è l'inverso dell'elevamento a potenza. Il logaritmo binario viene utilizzato per calcolare la potenza di 2. Ad esempio, abbiamo 10.000 elementi che dobbiamo esaminare utilizzando una ricerca binaria. Adesso hai una foto davanti ai tuoi occhi e sai che per realizzarla sono necessarie al massimo 14 verifiche. Ma cosa succede se non hai alcuna immagine davanti ai tuoi occhi e devi contare il numero esatto di controlli necessari? Basta rispondere ad una semplice domanda: a quale potenza bisogna elevare il numero 2 affinché il risultato ottenuto sia >= al numero di elementi da controllare? Per 10000 sarà la 14a potenza. 2 alla 13a potenza è troppo piccolo (8192) Ma 2 alla 14a potenza = 16384 , questo numero soddisfa la nostra condizione (è >= il numero di elementi nell'array). Abbiamo trovato il logaritmo - 14. Ecco quanti controlli abbiamo bisogno! :) Gli algoritmi e la loro complessità sono un argomento troppo vasto per essere incluso in una lezione. Ma saperlo è molto importante: in molte interviste riceverai problemi algoritmici. Per quanto riguarda la teoria, posso consigliarti diversi libri. Un buon punto di partenza è “ Grocking Algorithms ”: sebbene gli esempi nel libro siano scritti in Python, il linguaggio e gli esempi del libro sono molto semplici. L'opzione migliore per un principiante ed è anche di volume ridotto. Lettura più seria: libri di Robert Laforet e Robert Sedgwick . Entrambi sono scritti in Java, il che ti renderà l'apprendimento un po' più semplice. Dopotutto, hai abbastanza familiarità con questa lingua! :) Per gli studenti con un buon background matematico, l'opzione migliore sarebbe il libro di Thomas Corman . Ma non ti accontenterai solo della teoria! “Conoscere”!= “essere capace” Puoi esercitarti a risolvere problemi di algoritmo su HackerRank e Leetcode . I problemi da lì vengono spesso utilizzati anche durante le interviste su Google e Facebook, quindi sicuramente non ti annoierai :) Per rafforzare il materiale delle lezioni, ti consiglio di guardare un eccellente video su Big-O su YouTube. Ci vediamo alle prossime lezioni! :)
In questo caso, l'algoritmo più efficiente sarebbe trasferire il file su Internet. Ci vorranno solo un paio di minuti! Quindi, diamo nuovamente voce al nostro algoritmo: "Se è necessario trasferire informazioni sotto forma di file su una distanza di 5000 chilometri, è necessario utilizzare la trasmissione dei dati su Internet". Grande. Ora analizziamolo. Risolve il nostro problema? In generale sì, lo risolve completamente. Ma cosa si può dire della sua complessità? Hmm, ora è qui che le cose si fanno interessanti. Il fatto è che il nostro algoritmo dipende molto dai dati in arrivo, ovvero dalla dimensione dei file. Ora abbiamo 10 megabyte e va tutto bene. Cosa succede se dobbiamo trasferire 500 megabyte? 20 gigabyte? 500 terabyte? 30 petabyte? Il nostro algoritmo smetterà di funzionare? No, tutte queste quantità di dati possono ancora essere trasferite. Ci vorrà più tempo per completarlo? Si lo farà! Ora conosciamo una caratteristica importante del nostro algoritmo: maggiore è la dimensione dei dati da trasferire, più tempo impiegherà l'algoritmo per completarsi . Ma vorremmo capire più precisamente in cosa consiste questa relazione (tra la dimensione dei dati e il tempo necessario per trasferirli). Nel nostro caso, la complessità dell’algoritmo sarà lineare. “Lineare” significa che all'aumentare del volume dei dati, il tempo per la loro trasmissione aumenterà in modo approssimativamente proporzionale. Se sono presenti 2 volte più dati, il trasferimento richiederà 2 volte più tempo. Se sono presenti 10 volte più dati, il tempo di trasferimento aumenterà di 10 volte. Usando la notazione Big-O, la complessità del nostro algoritmo è definita come O(N) . Questa notazione è meglio ricordarla per riferimento futuro; viene sempre utilizzata per algoritmi con complessità lineare. Nota: qui non stiamo affatto parlando di varie cose "variabili": la velocità di Internet, la potenza del nostro computer e così via. Quando si valuta la complessità di un algoritmo, ciò semplicemente non ha senso: non abbiamo comunque alcun controllo su di esso. Big-O valuta l’algoritmo stesso, indipendentemente dall’“ambiente” in cui dovrà operare. Continuiamo con il nostro esempio. Diciamo che alla fine risulta che la dimensione dei file da trasferire è di 800 terabyte. Se li trasmettiamo via Internet, il problema, ovviamente, sarà risolto. C'è solo un problema: la trasmissione su un collegamento moderno standard (a 100 megabit al secondo) che la maggior parte di noi utilizza nelle nostre case richiederà circa 708 giorni. Quasi 2 anni! :O Quindi, il nostro algoritmo chiaramente non è adatto qui. Abbiamo bisogno di qualche altra soluzione! All’improvviso arriva in nostro aiuto il colosso informatico Amazon! Il suo servizio Amazon Snowmobile ti consente di caricare grandi quantità di dati in unità di archiviazione mobili e di consegnarli all'indirizzo desiderato tramite camion! 
Quindi abbiamo un nuovo algoritmo! "Se è necessario trasferire informazioni sotto forma di file su una distanza di 5.000 chilometri e il processo richiederà più di 14 giorni se trasferito tramite Internet, è necessario utilizzare il trasporto su camion di Amazon." La cifra di 14 giorni è stata qui scelta a caso: diciamo che è il periodo massimo che possiamo permetterci. Analizziamo il nostro algoritmo. E la velocità? Anche se il camion viaggia a soli 50 km/h, in sole 100 ore percorrerà 5.000 chilometri. Sono poco più di quattro giorni! Questo è molto meglio dell'opzione di trasmissione Internet. Che dire della complessità di questo algoritmo? Sarà anch'esso lineare, O(N)? No, non lo farà. Dopotutto, al camion non importa quanto lo carichi: guiderà comunque all'incirca alla stessa velocità e arriverà in orario. Sia che abbiamo 800 terabyte, o 10 volte più dati, il camion arriverà comunque in 5 giorni. In altre parole, l’algoritmo per la consegna dei dati tramite camion ha una complessità costante . “Costante” significa che non dipende dai dati passati all’algoritmo. Metti una chiavetta da 1 GB nel camion e arriverà in 5 giorni. Metti lì i dischi con 800 terabyte di dati e arriverà in 5 giorni. Quando si utilizza Big-O, la complessità costante è indicata come O(1) . Dato che abbiamo conosciuto O(N) eO(1) , diamo ora un'occhiata ad altri esempi da "programmatore" :) Diciamo che ti viene dato un array di 100 numeri e il compito è stampare ciascuno di essi sulla console. Scrivi un ciclo regolare 
Nella riga superiore dell'immagine vediamo un array ordinato. In esso dobbiamo trovare il numero 23. Invece di ripetere i numeri, dividiamo semplicemente l'array in 2 parti e controlliamo il numero medio nell'array. Troviamo il numero che si trova nella cella 4 e lo controlliamo (seconda riga nella foto). Questo numero è 16 e stiamo cercando 23. Il numero attuale è inferiore. Cosa significa questo? Che non è necessario controllare tutti i numeri precedenti (che si trovano fino al numero 16) : saranno sicuramente inferiori a quello che stiamo cercando, perché il nostro array è ordinato! Continuiamo la ricerca tra i restanti 5 elementi. Fai attenzione:Abbiamo fatto solo un controllo, ma abbiamo già eliminato la metà delle opzioni possibili. Ci restano solo 5 elementi. Ripeteremo il nostro passaggio: dividiamo nuovamente l'array rimanente per 2 e prendiamo nuovamente l'elemento centrale (riga 3 nella figura). Questo numero è 56 ed è più grande di quello che stiamo cercando. Cosa significa questo? Che scartiamo altre 3 opzioni: il numero 56 stesso e due numeri successivi (sono decisamente maggiori di 23, perché l'array è ordinato). Ci restano solo 2 numeri da controllare (l'ultima riga nella figura): numeri con indici di array 5 e 6. Controlliamo il primo, ed è quello che stavamo cercando: il numero 23! Il suo indice = 5! Diamo un'occhiata ai risultati del nostro algoritmo e poi ne capiremo la complessità. (A proposito, ora capisci perché si chiama binario: la sua essenza è dividere costantemente i dati per 2). Il risultato è impressionante! Se cercassimo il numero desiderato utilizzando la ricerca lineare avremmo bisogno di 10 controlli, ma con la ricerca binaria ce la faremo in 3! Nel peggiore dei casi, ce ne sarebbero 4, se nell'ultimo passaggio il numero di cui avevamo bisogno risultasse essere il secondo e non il primo. E la sua complessità? Questo è un punto molto interessante :) L'algoritmo di ricerca binaria dipende molto meno dal numero di elementi nell'array rispetto all'algoritmo di ricerca lineare (ovvero l'enumerazione semplice). Con 10 elementi nell'array, la ricerca lineare richiederà un massimo di 10 controlli e la ricerca binaria richiederà un massimo di 4 controlli. La differenza è 2,5 volte. Ma per un array di 1000 elementi, la ricerca lineare avrà bisogno di 1000 controlli e la ricerca binaria ne richiederà solo 10 ! La differenza è già 100 volte! Fai attenzione:il numero di elementi nell'array è aumentato di 100 volte (da 10 a 1000) e il numero di controlli necessari per la ricerca binaria è aumentato solo di 2,5 volte, da 4 a 10. Se raggiungiamo 10.000 elementi , la differenza è ancora più impressionante: 10.000 controlli per la ricerca lineare e un totale di 14 controlli per il binario. E ancora: il numero degli elementi è aumentato di 1000 volte (da 10 a 10000), ma il numero di controlli è aumentato solo di 3,5 volte (da 4 a 14). La complessità dell'algoritmo di ricerca binaria è logaritmica o, nella notazione Big-O, O(log n) . Perché si chiama così? Un logaritmo è l'inverso dell'elevamento a potenza. Il logaritmo binario viene utilizzato per calcolare la potenza di 2. Ad esempio, abbiamo 10.000 elementi che dobbiamo esaminare utilizzando una ricerca binaria. 
Adesso hai una foto davanti ai tuoi occhi e sai che per realizzarla sono necessarie al massimo 14 verifiche. Ma cosa succede se non hai alcuna immagine davanti ai tuoi occhi e devi contare il numero esatto di controlli necessari? Basta rispondere ad una semplice domanda: a quale potenza bisogna elevare il numero 2 affinché il risultato ottenuto sia >= al numero di elementi da controllare? Per 10000 sarà la 14a potenza. 2 alla 13a potenza è troppo piccolo (8192) Ma 2 alla 14a potenza = 16384 , questo numero soddisfa la nostra condizione (è >= il numero di elementi nell'array). Abbiamo trovato il logaritmo - 14. Ecco quanti controlli abbiamo bisogno! :) Gli algoritmi e la loro complessità sono un argomento troppo vasto per essere incluso in una lezione. Ma saperlo è molto importante: in molte interviste riceverai problemi algoritmici. Per quanto riguarda la teoria, posso consigliarti diversi libri. Un buon punto di partenza è “ Grocking Algorithms ”: sebbene gli esempi nel libro siano scritti in Python, il linguaggio e gli esempi del libro sono molto semplici. L'opzione migliore per un principiante ed è anche di volume ridotto. Lettura più seria: libri di Robert Laforet e Robert Sedgwick . Entrambi sono scritti in Java, il che ti renderà l'apprendimento un po' più semplice. Dopotutto, hai abbastanza familiarità con questa lingua! :) Per gli studenti con un buon background matematico, l'opzione migliore sarebbe il libro di Thomas Corman . Ma non ti accontenterai solo della teoria! “Conoscere”!= “essere capace” Puoi esercitarti a risolvere problemi di algoritmo su HackerRank e Leetcode . I problemi da lì vengono spesso utilizzati anche durante le interviste su Google e Facebook, quindi sicuramente non ti annoierai :) Per rafforzare il materiale delle lezioni, ti consiglio di guardare un eccellente video su Big-O su YouTube. Ci vediamo alle prossime lezioni! :)
GO TO FULL VERSION