Va bene, quindi, la complessità computazionale. Solo un po 'di un avvertimento Prima di tuffarci in troppo far-- questo sarà probabilmente tra le cose più matematica pesante parliamo in CS50. Speriamo che non sarà troppo schiacciante e cercheremo di guidarvi attraverso il processo, ma solo un po 'di un avvertimento fiera. C'è un po ' di matematica coinvolta qui. Va bene, così al fine di rendere utilizzo delle nostre risorse di calcolo nel vero world-- è davvero importante capire algoritmi e il modo in cui trattano dati. Se abbiamo una veramente algoritmo efficiente, abbiamo può minimizzare la quantità di risorse abbiamo a disposizione a che fare con esso. Se abbiamo un algoritmo che sta andando a prendere un sacco di lavoro per elaborare un veramente grande insieme di dati, è andando a richiedere più e più risorse, che è il denaro, la RAM, tutto questo genere di cose. 

Quindi, essendo in grado di analizzare un Algoritmo utilizzando questo set di strumenti, fondamentalmente, chiede al interrogo come fa questa scala algoritmo come gettiamo sempre più dati a esso? Nel CS50, la quantità di dati che siamo lavorando è piuttosto piccolo. In generale, i nostri programmi sono in corso per l'esecuzione in un secondo o less-- probabilmente molto meno soprattutto nella fase iniziale. 

Ma pensare a una società che si occupa con centinaia di milioni di clienti. E hanno bisogno di elaborare i dati dei clienti. Poiché il numero di clienti che avere diventa sempre più grande, sta andando a richiedere sempre più risorse. Quanti altri mezzi? Beh, questo dipende da come analizziamo l'algoritmo, utilizzando gli strumenti di questa casella. Quando si parla della complessità del un algorithm-- che a volte si ascoltano indicato come il tempo complessità o spazio complessità ma stiamo solo andando chiamare complexity-- stiamo generalmente parlando la peggiore delle ipotesi. Dato il peggiore in assoluto di palo dati che potremmo buttare a lui, come è questo algoritmo sta per elaborare o trattare tali dati? In genere chiamiamo il caso peggiore tempo di esecuzione di un algoritmo O-grande. Quindi un algoritmo può essere detto di eseguito in O di n o n O di quadrato. E di più su ciò quelli significa in un secondo. 

A volte, però, facciamo cura circa la migliore delle ipotesi. Se i dati sono tutto quello che volevamo che sia ed era assolutamente perfetto e siamo stati l'invio di questo perfetto set di dati attraverso il nostro algoritmo. Come sarebbe gestire in quella situazione? Ci riferiamo a volte che, come big-Omega, così in contrasto con O-grande, abbiamo grande-Omega. Big-Omega per la migliore delle ipotesi. Big-O per la peggiore delle ipotesi. In generale, quando si parla di la complessità di un algoritmo, stiamo parlando della nella peggiore delle ipotesi. Modo da tenere a mente. 

E in questa classe, stiamo andando in genere di lasciare la rigorosa analisi da parte. Ci sono scienze e campi dedicato a questo genere di cose. Quando si parla di ragionamento tramite algoritmi, che faremo pezzo per pezzo per molti Algoritmi parliamo della classe. Stiamo davvero parlando solo ragionamento attraverso di essa con il senso comune, non con formule, o prove, o qualcosa di simile. Quindi non preoccupatevi, Non saremo si trasforma in una grande classe di matematica. 

Così ho detto ci preoccupiamo per la complessità perché pone la domanda, come non i nostri algoritmi gestiscono più grande e set di dati più grandi essere gettato contro di loro. Beh, quello che è un insieme di dati? Che cosa voglio dire quando ho detto che? Significa ciò che rende la maggior parte senso nel contesto, ad essere onesti. Se abbiamo un algoritmo, il Processi Strings-- probabilmente siamo parlando della dimensione della stringa. Ecco i dati set-- la dimensione, il numero di caratteri che compongono la stringa. Se stiamo parlando di un algoritmo che elabora i file, potremmo parlare di come molti kilobyte comprendono quel file. E questo è il set di dati. Se stiamo parlando di un algoritmo che gestisce array più in generale, quali algoritmi di ordinamento o la ricerca di algoritmi, probabilmente stiamo parlando del numero di di elementi che compongono un array. 

Ora, siamo in grado di misurare una algorithm-- in particolare, quando dico che possiamo misurare un algoritmo, I significa che possiamo misurare come molte risorse che occupa. Se tali risorse sono, quanti byte di RAM-- o megabyte di RAM Usa. O quanto tempo necessario per l'esecuzione. E possiamo chiamare questo misura, arbitrariamente, f n. Dove n è il numero di elementi del set di dati. E f n è il numero di quarantina. Quante unità di risorse fa si richiede di elaborare tali dati. 

Ora, in realtà non ci interessa su ciò che f n è esattamente. In effetti, abbiamo will-- molto raramente certamente non sarà mai in questo io class-- tuffarsi in qualsiasi veramente profondo analisi di ciò che f n è. Stiamo solo andando a parlare di ciò che di f n è approssimativamente o ciò tende a. E la tendenza di un algoritmo dettata dal suo termine di ordine più alto. E possiamo vedere quello che ho dire con che prendendo uno sguardo ad un esempio più concreto. 

Quindi cerchiamo di dire che abbiamo tre diversi algoritmi. Il primo dei quali prende n cubetti, alcune unità di risorse per elaborare un insieme di dati di dimensione n. Abbiamo un secondo algoritmo che prende n cubetti più risorse n quadrati per elaborare un insieme di dati di dimensione n. E abbiamo un terzo algoritmo che esegue dentro-- che riprende n meno cubetti 8n quadrato più 20 n unità di risorse di elaborare un algoritmo l'insieme di dati di dimensione n. 

Ora di nuovo, noi non stiamo andando per entrare in questo livello di dettaglio. Sono davvero ho solo questi in su qui come un esempio di un punto che ho intenzione di essere facendo in un secondo, è che abbiamo solo veramente a cuore per la tendenza delle cose come i set di dati diventano più grandi. Quindi, se il set di dati è piccolo, non c'è in realtà una bella differenza in questi algoritmi. Il terzo algoritmo di lì prende 13 volte più a lungo, 13 volte la quantità di risorse eseguire rispetto al primo. 

Se il nostro set di dati è la dimensione 10, che è più grande, ma non necessariamente enorme, possiamo vedere che non c'è in realtà un po 'di differenza. Il terzo algoritmo diventa più efficiente. Si tratta di realtà il 40% - o il 60% più efficiente. Prende 40% la quantità di tempo. Può run-- si può prendere 400 unità di risorse di elaborare un insieme di dati di dimensioni 10. Considerando che la prima algoritmo, per contrasto, prende 1.000 unità di risorse di elaborare un insieme di dati di dimensioni 10. Ma guardate cosa succede come i nostri numeri diventano ancora più grande. 

Ora, la differenza tra questi algoritmi iniziare a diventare un po 'meno evidente. E il fatto che ci sono di ordine inferiore terms-- o meglio, patti con bassa exponents-- iniziare a diventare irrilevante. Se un insieme di dati è di dimensioni 1.000 e il primo algoritmo viene eseguito in un miliardo di passi. E il secondo algoritmo viene eseguito in un miliardo e un milione di passi. E il terzo algoritmo funziona in poco meno di un miliardo di punti. E 'più o meno un miliardo di passi. Questi termini di ordine inferiore iniziano per diventare davvero irrilevante. E proprio per davvero martello a casa il Point-- se l'input dei dati è di dimensioni un million-- tutti e tre di questi più o meno prendere uno quintillion-- se la mia matematica è a pochi passi correct-- per elaborare un ingresso dati di dimensioni un milione. Questo è un sacco di passi. E il fatto che uno di essi potrebbe prendere un paio di 100.000, o una coppia di 100 milioni di ancor meno quando stiamo parlando di un numero che big-- è una specie di irrilevante. Tutti tendono a prendere circa n cubetti, e così ci sarebbe in realtà riferirsi a tutti questi algoritmi come essendo dell'ordine di n a cubetti o O-grande di n cubetti. 

Ecco un elenco di alcuni dei più classi comuni di complessità computazionale che ci incontriamo nella algoritmi, generalmente. E anche specificamente in CS50. Questi sono ordinati da generalmente più veloce in alto, a generalmente più lenta in basso. Così algoritmi costante di tempo tendono essere il più veloce, indipendentemente della dimensione del inserimento dei dati si passa. Prendono sempre una operazione o una unità di risorse per far fronte. Potrebbe essere 2, potrebbe essere di 3, potrebbe essere 4. Ma è un numero costante. Esso non varia. 

Algoritmi tempo logaritmico sono un po 'meglio. E davvero un buon esempio di un algoritmo di tempo logaritmico avete sicuramente visto ormai è il lacerazione della rubrica trovare Mike Smith nella rubrica. Abbiamo tagliato il problema a metà. E così quando n diventa più grande e più grande e larger-- infatti, ogni volta che si raddoppia n, ci vuole solo un altro passo. Ecco, questo è molto meglio rispetto, ad esempio, il tempo lineare. Quale è se si raddoppia n, esso prende il doppio del numero di passi. Se triplicare n, ci vuole triplicare il numero di passi. Un passo per unità. 

Poi le cose si fanno un po more-- poco meno grande da lì. Avete tempo ritmico lineare, a volte chiamato registro tempo lineare o solo n log n. E faremo un esempio di un algoritmo che viene eseguito in n log n, che è ancora meglio di tempo-- quadratica n al quadrato. Oppure tempo polinomiale, n due qualsiasi numero maggiore di due. Oppure tempo esponenziale, che è anche peggio-- C al n. Così alcuni numero costante elevato a il potere della dimensione dell'input. Quindi, se c'è 1,000-- se la immissione dei dati è di dimensioni 1.000, ci vorrebbe C al potere 1000. E 'molto peggio di un tempo polinomiale. 

Tempo fattoriale è ancora peggio. E in effetti, c'è davvero fare Esistono algoritmi tempo infinito, come ad esempio, i cosiddetti sort-- stupido cui compito è quello di mescolare in modo casuale un array e quindi verificare se è ordinato. E se non lo è, in modo casuale mescolare di nuovo l'array e verificare se è ordinato. E come si può probabilmente imagine-- si può immaginare una situazione dove nel caso peggiore, che la volontà mai effettivamente iniziare con l'array. Questo algoritmo funzionerebbe per sempre. E così che sarebbe un algoritmo di tempo infinito. Speriamo che non sarà la scrittura qualsiasi momento fattoriale o infinito algoritmi in CS50. 

Allora, facciamo un po 'di più sguardo concreto ad alcune semplici classi di complessità computazionale. Quindi abbiamo un example-- o due esempi qui-- algoritmi di tempo costante, che sempre prendere una singola operazione nel caso peggiore. Quindi la prima example-- abbiamo una funzione chiamato 4 per te, che accetta un array di dimensioni 1.000. Ma poi a quanto pare in realtà non guardare a it-- in realtà non importa ciò che è all'interno di esso, di tale matrice. Sempre restituisce solo quattro. Quindi, tale algoritmo, nonostante il fatto che prende 1.000 elementi non fare qualcosa con loro. Proprio restituisce quattro. E 'sempre un solo passo. 

In realtà, aggiungere 2 nums-- che abbiamo visto prima come well-- appena due interi processi. Non è un solo passo. In realtà è un paio di passi. Si ottiene un, si ottiene b, vengono aggiunti insieme, e voi di uscita dei risultati. Quindi è di 84 gradini. Ma è sempre costante, indipendentemente a o b. Dovete ottenere un, ottenere b, aggiungere insieme, uscita il risultato. Quindi questo è un algoritmo di tempo costante. 

Ecco un esempio di un tempo algorithm-- lineari un algoritmo che gets-- che prende un passo ulteriore, eventualmente, come ingresso cresce di 1. Quindi, diciamo che stiamo cercando il numero 5 all'interno di una matrice. Si potrebbe avere una situazione in cui si può trovare abbastanza presto. Ma si potrebbe anche avere una situazione in cui potrebbe essere l'ultimo elemento dell'array. In un array di dimensioni 5, se stiamo cercando il numero 5. Ci vorrebbero 5 passi. E infatti, immaginare che ci sia non 5 ovunque in questo array. Abbiamo ancora in realtà dobbiamo guardare ogni singolo elemento dell'array per determinare o meno 5 è lì. 

Quindi nel caso peggiore, che è quella l'elemento è ultima nell'array o non esiste affatto. Dobbiamo ancora guardare tutti gli n elementi. E così questo algoritmo viene eseguito in tempo lineare. È possibile confermare che, estrapolando un po 'dicendo: se avessimo un array di 6 elementi e stavamo cercando per il numero 5, si potrebbe prendere 6 punti. Se abbiamo un array di 7 elementi e stiamo cercando il numero 5. Si potrebbe prendere 7 passi. Come si aggiunge un ulteriore elemento per il nostro array, ci vuole un passo in più. Questo è un algoritmo lineare nel caso peggiore. 

Coppia brevi domande per voi. Qual è la cosa è runtime-- il caso peggiore runtime di questo particolare frammento di codice? Così ho un ciclo 4 qui che corre da j è uguale a 0, tutta la strada fino a m. E quello che sto vedendo qui, è che il corpo del ciclo viene eseguito in tempo costante. Quindi, utilizzando la terminologia che abbiamo già parlato about-- cosa sarebbe il caso peggiore tempo di esecuzione di questo algoritmo? Prendete un secondo. La parte interna del loop viene eseguito in tempo costante. E la parte esterna del ciclo è andare a correre m volte. Allora qual è il tempo di esecuzione nel caso peggiore qui? Avete indovinato O-grande di m? Avreste ragione. 

Che ne dite di un altro? Questa volta abbiamo una ciclo all'interno di un ciclo. Abbiamo un ciclo esterno che va da zero a p. E abbiamo un ciclo interno che gira da zero a p, e all'interno di questo, Premetto che il corpo ciclo viene eseguito in tempo costante. Allora qual è il tempo di esecuzione nel caso peggiore di questo particolare frammento di codice? Bene, ancora una volta, abbiamo un anello esterno che corre p volte. E ogni iterazione tempo-- di quel ciclo, piuttosto. Abbiamo un ciclo interno che corre anche p volte. E poi dentro di questo, c'è il costante piccolo frammento tempo-- lì. 

Quindi, se abbiamo un ciclo esterno che gestisce p volte all'interno del quale è un ciclo interno che gestisce p times-- ciò che è il caso peggiore runtime di questo frammento di codice? Avete indovinato O-grande di p quadrato? 

Sono Doug Lloyd. Questo è CS50.