[Powered by Google Translate] [Sezione 3 - più confortevole]
[Rob Bowden - Harvard University]
>> [Questo è CS50. - CS50.TV]
>> Quindi la prima domanda è stranamente formulata.
GDB permette di "debug", un programma, ma, più in particolare, che cosa ti permette di fare?
Ti risponderò che uno, e io non so cosa stia esattamente previsto,
così Sto indovinando che è qualcosa lungo le linee di esso permette di passo dopo passo
a piedi attraverso il programma, interagire con esso, le variabili del cambiamento, fare tutte queste cose -
sostanzialmente completamente controllare l'esecuzione di un programma
e ispezionare qualsiasi data parte della esecuzione del programma.
Quindi, le caratteristiche consentono di eseguire il debug di cose.
Va bene.
Perché la ricerca binaria richiede che un array da ordinare?
Chi ha voglia di rispondere?
[Studente] Perché non funziona se non è ordinato. Sì >>. [Risate]
Se non è risolto, allora è impossibile dividere a metà
e sapere che tutto a sinistra è meno e tutto a destra
è maggiore del valore centrale.
Quindi ha bisogno di essere ordinati.
Va bene.
Perché è una sorta di bolla in O quadrato n?
Qualcuno vuole prima di dare una molto veloce panoramica di alto livello di che tipo bolla è?
[Studente] Che, fondamentalmente, passare attraverso ogni elemento e di controllare gli elementi primi.
Se sono su dove li scambiare, poi di controllare gli elementi successivi e così via.
Quando si raggiunge la fine, poi si sa che l'elemento più grande è posto alla fine,
in modo da ignorare che uno poi si continua a passare attraverso,
e ogni volta che si controlla un elemento meno fino a quando non si apportano modifiche. Sì >>.
Si chiama bubble sort, perché se si capovolgere la matrice su un lato in modo che sia alto e in basso, verticale,
quindi i valori di grandi dimensioni si depositano sul fondo ed i valori piccola bolla fino alla cima.
È così che ha preso il nome.
E sì, basta andare attraverso.
Continui a passare attraverso la matrice, scambiando il valore maggiore
per ottenere valori più grandi sul fondo.
>> Perché è O di quadrato n?
In primo luogo, nessuno vuole dire perché è O di n al quadrato?
[Studente] Perché per ogni corsa va n volte.
Si può solo essere sicuro che hai preso il più grande elemento fino in fondo,
poi si deve ripetere che a molti elementi. Sì >>.
Quindi, tenere a mente che cosa grande O significa e che cosa significa Omega grandi.
The Big O è come il limite superiore per quanto lento possa effettivamente funzionare.
Così dicendo che è O del quadrato n, non è O di n altrimenti sarebbe in grado di eseguire
in tempo lineare, ma è O di n cubo
perché è delimitata da O di n cubo.
Se è delimitata da O quadrato di n, allora è anche delimitata da n cubo.
Così è n quadrato, e nel caso peggiore assoluta non può fare meglio squared n,
ed è per questo che è O di n quadrato.
Quindi, per vedere la matematica lieve come risulta essere n quadrato,
se abbiamo cinque cose nella nostra lista, la prima volta il numero di operazioni di swap potremmo potenzialmente bisogno di fare
per ottenere questo? Facciamo in realtà solo -
Quanti swap stiamo andando ad avere per fare nella prima prova del Bubble sort attraverso l'array?
[Studente] n - 1. Sì >>.
>> Se ci sono 5 elementi, avremo bisogno di fare n - 1.
Poi, il secondo il numero di swap stiamo andando ad avere per fare?
[Studente] n - 2. Sì >>.
E il terzo sarà n - 3, e poi per comodità scriverò le ultime due
come allora stiamo andando ad avere bisogno di fare 2 swap e 1 di swap.
Credo che l'ultimo può o non può effettivamente bisogno per accadere.
E 'uno swap? Non lo so.
Quindi questi sono gli importi totali delle operazioni di swap o almeno confronti si devono fare.
Anche se non scambiare, hai ancora bisogno di confrontare i valori.
Quindi ci sono n - 1 confronti della prima esecuzione tramite la matrice.
Se riorganizzare queste cose, cerchiamo di fare sei in realtà le cose e quindi le cose stack up bene,
e poi farò 3, 2, 1.
Quindi, solo riordinando queste somme, vogliamo vedere quanti confronti facciamo
nel intero algoritmo.
Quindi, se portiamo questi ragazzi qui,
allora siamo ancora solo sommando i confronti però ci sono stati molti.
Ma se sommiamo questi e sommiamo questi e sommiamo questi,
è ancora lo stesso problema. Abbiamo appena riassumere quei gruppi particolari.
>> Così ora stiamo sommando le 3 n. Non si tratta solo di 3 n.
E 'sempre sarà n / 2 di n.
Così qui ci capita di avere 6.
Se avessimo 10 cose, allora potremmo fare questo gruppo per 5 diverse coppie di cose
e finire con n + n + n + n + n.
Quindi, si sta andando sempre di ottenere n / 2 n, e quindi questo te lo butto fuori a n quadrato / 2.
E quindi, anche se è il fattore di mezzo, che avviene a venire in
a causa del fatto che ogni iterazione attraverso la matrice confrontiamo 1 meno
è così che si ottiene il più del 2, ma è ancora n quadrato.
Non ci interessa il fattore costante di un mezzo.
Quindi un sacco di grandi cose O come questa si basa su un solo tipo di fare questo tipo di matematica,
facendo le somme aritmetiche e cose serie geometriche,
ma la maggior parte di loro in questo corso sono piuttosto semplici.
Va bene.
Perché è una sorta di inserimento in Omega di n? Che cosa significa omega?
[Due studenti di lingua in una sola volta - incomprensibili] >> Si '.
Omega si può pensare come il limite inferiore.
>> Quindi, non importa quanto sia efficiente il vostro algoritmo di ordinamento per inserimento è,
indipendentemente dalla lista che è passato in, ha sempre confrontare almeno n cose
o deve scorrere le cose n.
Perché è così?
[Studente] Perché se la lista è già ordinato, poi attraverso la prima iterazione
si può solo garantire che il primo elemento è il meno,
e la seconda iterazione si può garantire solo le prime due sono
perché non si sa che il resto della lista è ordinata. Sì >>.
Se si passa in un elenco completamente ordinato, per lo meno si deve andare su tutti gli elementi
per vedere che non ha bisogno di essere spostati.
Quindi, passando sopra l'elenco e dire oh, questo è già ordinato,
è impossibile per voi sapere che è risolto solo dopo aver verificato ogni elemento
per vedere che sono in modo ordinato.
Quindi il limite inferiore per inserzione è Omega di n.
Che cosa è il caso peggiore tempo di esecuzione di merge sort,
peggiore dei casi, essendo O grandi di nuovo?
Così, nel peggiore dei casi, come si merge sort esegue?
[Studente] N log n. Sì >>.
I più veloci algoritmi di ordinamento generale sono n log n. Non si può fare di meglio.
>> Ci sono casi particolari, e se abbiamo tempo di oggi - ma probabilmente won't -
abbiamo potuto vedere quello che fa meglio di n log n.
Ma, nel caso generale, non si può fare meglio di n log n.
E merge sort sembra essere quello che si deve sapere per questo corso che è n log n.
E così saremo effettivamente attuazione di tale oggi.
E, infine, in non più di tre frasi, come funziona sorta lavoro di selezione?
Qualcuno vuole rispondere, e io conto le frasi
perché se si va oltre 3 -
Qualcuno ricorda per selezione?
Sorta di selezione di solito è abbastanza facile da ricordare solo dal nome.
Basta scorrere l'array, trovare qualunque sia il valore più grande è o più piccolo -
qualunque ordine si sta ordinamento trovi
Quindi diciamo che stiamo ordinamento dal più piccolo al più grande.
È scorrere l'array, alla ricerca di tutto ciò che è l'elemento minimo,
selezionarlo, e poi semplicemente scambiare tutto ciò che è in primo luogo.
E poi al secondo passaggio la matrice, cercare l'elemento minimo di nuovo,
selezionarlo, e poi scambiarlo con ciò che è in seconda posizione.
Quindi, ci sono solo la raccolta e scegliendo i valori minimi
e inserendoli nella prima parte dell'array finché non viene risolto.
Domande su questo?
>> Questi inevitabilmente appaiono nelle forme che devono compilare quando si elaborano il pset.
Queste sono fondamentalmente le risposte a quelli.
Bene, ora i problemi di codifica.
Ho già inviato tramite e-mail - Non avere nessuno che la posta elettronica? Va bene.
Ho già inviato tramite e-mail lo spazio che abbiamo intenzione di utilizzare,
e se si fa clic sul mio nome - quindi penso che ho intenzione di essere in fondo
a causa della r indietro - ma se cliccate sul mio nome vedrai 2 revisioni.
Revisione 1 sta per essere ho già copiato e incollato il codice in spazi
ricerca per la cosa si sta andando ad avere per implementare.
E Revisione 2 sarà la cosa tipo che implementiamo dopo.
Quindi, è possibile fare clic sul mio Revisione 1 e lavorare da lì.
E ora vogliamo implementare la ricerca binaria.
>> Qualcuno ha voglia di fare solo un pseudocodice di alto livello spiegazione
di quello che stiamo andando ad avere a che fare per la ricerca? Gia '.
[Studente] Devi solo prendere il centro della matrice e vedere se quello che stai cercando
sia inferiore o superiore a quella.
E se è meno, si va alla metà che è meno,
e se è di più, si va a metà che è più e che si ripete fino a che non solo ottenere una cosa.
[Bowden] Si '.
Si noti che la nostra matrice di numeri è già ordinato,
e in modo che significa che siamo in grado di approfittare di questo e abbiamo potuto verificare prima,
ok, sto cercando il numero 50.
Così posso andare al centro.
Oriente è difficile da definire quando si tratta di un numero pari di cose,
ma diciamo solo che saremo sempre troncare al centro.
Quindi qui abbiamo 8 cose, in modo che il centro sarebbe 16.
Sto cercando per il 50, quindi 50 è maggiore di 16.
Così ora posso trattare praticamente la mia matrice come questi elementi.
Posso buttare via tutto, a partire dal 16 oltre.
Ora il mio array è solo questi 4 elementi, e lo ripeto.
Allora io voglio trovare il mezzo nuovo, che sta per essere 42.
42 è inferiore a 50, in modo da poter buttare via questi due elementi.
Questa è la mia matrice rimanente.
Vado a trovare il mezzo nuovo.
Credo che 50 era un cattivo esempio perché ero sempre buttare via le cose a sinistra,
ma per la stessa misura, se sto cercando qualcosa
ed è meno l'elemento Attualmente sto guardando,
allora ho intenzione di buttare via tutto a destra.
Così ora abbiamo bisogno di attuare tale.
Si noti che abbiamo bisogno di passare di dimensione.
Si può anche non essere necessario a livello di codice dimensioni.
Quindi, se ci liberiamo di quel # define -
Va bene.
Come posso ben capire che la dimensione della matrice di numeri è attualmente?
>> Quanti elementi sono nella matrice numeri?
[Studenti] Numeri, staffe,. Lunghezza?
[Bowden] Che non esiste in C.
Bisogno. Lunghezza.
Gli array non hanno proprietà, quindi non c'è alcuna proprietà lunghezza di array
che sarà solo darvi tutto il tempo capita di essere.
[Studente] Cfr. la quantità di memoria che ha e dividere per quanto - >> Si '.
Quindi, come possiamo vedere quanta memoria ha? >> [Studente] sizeof. >> Si ', sizeof.
Sizeof è l'operatore che sta per restituire la dimensione della matrice numeri.
E che sta per essere numeri interi ma ci sono molte volte più grande di un numero intero
dato che è la quantità di memoria che in realtà è occupare.
Quindi, se voglio il numero di cose nella matrice,
allora ho intenzione di voler dividere per le dimensioni di un intero.
Va bene. In modo che mi permette di passare in formato qui.
Perché ho bisogno di passare in dimensioni a tutti?
Perché non posso semplicemente fare qui int size = sizeof (pagliaio) / sizeof (int)?
Perché questo non funziona?
[Studente] Non è una variabile globale.
[Bowden] Haystack esiste e stiamo passando a numeri come pagliaio,
e questo è una sorta di prefigurazione di quello che verrà. Gia '.
[Studente] Haystack è solo il riferimento ad esso, in modo che sarebbe tornato quanto grande che sia di riferimento.
Gia '.
Dubito in conferenza aver visto la pila ancora veramente, giusto?
Abbiamo appena parlato.
Quindi lo stack è dove tutte le variabili stanno per essere memorizzati.
>> Ogni memoria è allocata per le variabili locali sta nello stack,
e ogni funzione prende il suo spazio nello stack, il suo stack frame è ciò che si chiama.
Così ha il suo principale stack frame, e all'interno di esso sta per esistere questa matrice di numeri,
e sta andando ad essere di dimensione sizeof (numeri).
E 'intenzione di avere dimensioni di numeri divisi da dimensione degli elementi,
ma che tutte le vite all'interno dello stack frame principale.
Quando chiamiamo ricerca, la ricerca prende il telaio proprio stack,
proprio spazio per archiviare tutte le sue variabili locali.
Ma questi argomenti - in modo da pagliaio non è una copia di questo intero array.
Non passare l'intero array come una copia in ricerca.
Passa solo un riferimento a tale matrice.
Così ricerca può accedere a questi numeri attraverso questo riferimento.
E 'ancora l'accesso alle cose che vivono dentro di stack frame principale,
ma in fondo, quando si arriva a puntatori, che dovrebbe essere presto,
questo è ciò che i puntatori sono.
I puntatori sono solo riferimenti a cose, ed è possibile utilizzare i puntatori per accedere a cose
che sono in stack frame altre cose ».
Così, anche se i numeri è locale principale, possiamo ancora accedere attraverso questo puntatore.
Ma dal momento che è solo un puntatore ed è solo un punto di riferimento,
sizeof (pagliaio) restituisce solo la dimensione del riferimento stesso.
Non restituire la dimensione della cosa sta indicando.
Essa non restituisce la dimensione effettiva dei numeri.
E quindi questo non è andare a lavorare come vogliamo che.
>> Domande su questo?
Puntatori sarà andato in in dettaglio molto più cruento nelle settimane a venire.
Ed è per questo che un sacco di cose che si vedono, la maggior parte delle cose di ricerca o cose di ordinamento,
sono quasi tutti bisogno di andare a prendere la dimensione effettiva della matrice,
perché in C, non abbiamo idea di quale sia la dimensione della matrice è.
È necessario passare manualmente trovi
E non si può passare manualmente l'intero array perché sei solo di passaggio nel riferimento
e non può ottenere la dimensione di riferimento.
Va bene.
Quindi ora vogliamo attuare ciò che è stato spiegato in precedenza.
È possibile lavorare su di esso per un minuto,
e non dovete preoccuparvi di ottenere tutto perfettamente funzionante al 100%.
Basta scrivere il pseudocodice metà per come si pensa che dovrebbe funzionare.
Va bene.
Non c'è bisogno di essere completamente fatto con questo ancora.
Ma qualcuno sentirsi a proprio agio con quello che hanno fino ad ora,
come qualcosa che possiamo lavorare con insieme?
Qualcuno vuole fare volontariato? Oppure scegliere in modo casuale.
Non deve essere proprio di ogni misura, ma qualcosa che si può modificare in uno stato di lavoro.
[Studente] Certo. Va bene >>.
Così si può salvare la revisione facendo clic sulla piccola icona Salva.
Hai Ramya, giusto? >> [Studente] Si '. >> [Bowden] Ok.
Così ora posso visualizzare la revisione e tutti possono tirare su la revisione.
E qui abbiamo - Va bene.
Così Ramya andato con la soluzione ricorsiva, che è sicuramente una valida soluzione.
Ci sono due modi per fare questo problema.
È possibile fare in modo ricorsivo o iterativo.
La maggior parte dei problemi che si verificano che può essere fatto in modo ricorsivo può essere fatto anche iterativamente.
Quindi qui abbiamo fatto in modo ricorsivo.
>> Qualcuno vuole definire che cosa significa fare una funzione ricorsiva?
[Studente] Quando si dispone di una funzione di chiamare se stesso
e poi si chiama fino a quando non esce con vero e vero. Sì >>.
Una funzione ricorsiva è solo una funzione che si chiama.
Ci sono tre grandi cose che una funzione ricorsiva deve avere.
Il primo è, ovviamente, che si chiama.
Il secondo è il caso base.
Quindi, ad un certo punto la funzione deve smettere di chiamare se stesso,
ed è quello che il caso base è per.
Ecco allora sappiamo che dovremmo smettere, dovremmo rinunciare nella nostra ricerca
quando inizio è uguale a fine - e andremo su ciò che significa.
Ma alla fine, l'ultima cosa che è importante per le funzioni ricorsive:
le funzioni deve in qualche modo avvicinarsi al caso base.
Come se non si è in realtà l'aggiornamento nulla quando si effettua la seconda chiamata ricorsiva,
se si sta letteralmente chiamando la funzione di nuovo con gli stessi argomenti
e non le variabili globali sono cambiati o altro,
che non potrà mai raggiungere il caso base, in questo caso non va bene.
Sarà una ricorsione infinita e un overflow dello stack.
Ma qui vediamo che l'aggiornamento è in corso in quanto stiamo aggiornando start + end / 2,
stiamo aggiornando l'argomento fin qui, stiamo aggiornando l'argomento start qui.
Così in tutte le chiamate ricorsive stiamo aggiornando qualcosa. Va bene.
Vuoi camminare noi tramite la tua soluzione? Certo >>.
Sto utilizzando SearchHelp in modo che ogni volta che faccio questa chiamata di funzione
Ho l'inizio di dove sto cercando nella matrice e la fine
di dove sto cercando la matrice.
>> Ad ogni passo dove sta dicendo che è l'elemento centrale, che è inizio + fine / 2,
che è uguale a quello che stiamo cercando?
E se lo è, allora lo abbiamo trovato, e credo che viene superato i livelli di ricorsione.
E se questo non è vero, allora verificare se tale valore medio della matrice è troppo grande,
nel qual caso guardiamo la metà sinistra della matrice andando dall'inizio all'indice medio.
E altrimenti facciamo la metà fine.
[Bowden] Ok.
Ottima idea.
Ok, quindi un paio di cose, e in realtà, questa è una cosa di altissimo livello
che non avrai mai bisogno di sapere per questo corso, ma è vero.
Funzioni ricorsive, è sempre sentito che sono un cattivo affare
perché se in modo ricorsivo chiamarti troppe volte, si ottiene un overflow dello stack
dal momento che, come ho detto prima, ogni funzione prende il telaio proprio stack.
Così ogni chiamata della funzione ricorsiva prende il telaio proprio stack.
Quindi, se si fanno 1.000 chiamate ricorsive, si ottiene 1.000 stack frame,
e rapidamente vi porterà ad avere stack frame troppe cose e solo rompere.
Allora è per questo che le funzioni ricorsive sono generalmente male.
Ma vi è un sottoinsieme piacevole di funzioni ricorsive chiamato coda funzioni ricorsive,
e questo sembra essere un esempio di quella in cui il compilatore se ne accorge
e dovrebbe, credo - in Clang se gli viene passato il flag-O2
poi si noterà questo è tail ricorsiva e fare le cose bene.
>> Si riutilizzare lo stesso telaio dello stack più e più volte per ogni chiamata ricorsiva.
E così dal momento che si sta utilizzando lo stesso telaio dello stack, non è necessario preoccuparsi di
impilare mai traboccante, e al tempo stesso, come hai detto prima,
dove una volta si torna vero, allora deve restituire il backup di tutti questi stack frame
e la chiamata 10 al SearchHelp deve tornare al 9, è tenuto a restituire al 8.
In modo che non ha bisogno di accadere quando le funzioni sono coda ricorsiva.
E così ciò che rende questa coda funzione ricorsiva è notare che per ogni invito a searchHelp
la chiamata ricorsiva che si sta facendo è quello che sta tornando.
Così nella prima chiamata a SearchHelp, si sia immediatamente restituire false,
immediatamente restituire true, oppure effettuare una chiamata ricorsiva a SearchHelp
dove quello che stiamo tornando è ciò che la chiamata sta tornando.
E non abbiamo potuto fare questo se abbiamo fatto qualcosa di simile int x = SearchHelp, return x * 2,
solo un po 'di cambiamento casuale.
>> Così ora questa chiamata ricorsiva, questo int x = chiamata SearchHelp ricorsiva,
non è più la coda ricorsiva, perché in realtà ha bisogno di tornare
di nuovo ad un stack frame precedente in modo che la chiamata precedente alla funzione
È quindi possibile fare qualcosa con il valore di ritorno.
Quindi questo non è tail ricorsiva, ma quello che avevamo prima è ben coda ricorsiva. Gia '.
[Studente] non dovrebbe seconda base caso essere controllato per primo
perché ci potrebbe essere una situazione in cui quando si passa l'argomento
aver inizio = fine, ma sono il valore ago.
La questione è stata non possiamo correre nel caso in cui il valore finale è dell'ago
o avviare = fine, opportunamente, inizio fine =
e non si è effettivamente verificato che il valore particolare ancora,
quindi avviare + finale / 2 è solo andare a essere lo stesso valore.
Ma abbiamo già restituito false e non abbiamo mai effettivamente controllato il valore.
Così per lo meno, in prima convocazione, se la dimensione è 0, allora vogliamo restituire false.
Ma se la dimensione è 1, allora inizio non sta per finire pari,
e noi provvederemo a verificare almeno l'unico elemento.
Ma credo che tu abbia ragione nel senso che possiamo finire in un caso in cui inizio + fine / 2,
start finisce per essere la stessa di inizio + fine / 2,
ma in realtà non abbiamo mai verificato tale elemento.
>> Quindi, se per prima cosa controllare è l'elemento centrale il valore che stiamo cercando,
allora possiamo immediatamente restituire true.
Altrimenti se sono uguali, allora non c'è ragione di continuare
dal momento che stiamo solo andando a l'aggiornamento a un caso in cui siamo su un singolo elemento di un array.
Se questo elemento non è quello che stiamo cercando,
allora tutto è sbagliato. Gia '.
[Studente] Il fatto è che, poiché la dimensione è in realtà maggiore del numero di elementi nella matrice,
c'è già un offset - >> Così sarà formato -
[Studente] Dire se la matrice era di dimensioni 0, il SearchHelp effettivamente verificare pagliaio di 0
in prima convocazione.
La matrice ha dimensione 0, in modo che il 0 è - >> Si '.
C'è un'altra cosa che - che potrebbe essere buono. Pensiamo.
Quindi, se l'array ha 10 elementi e quella centrale che andremo a controllare è indice 5,
quindi stiamo controllando 5, e diciamo che il valore è inferiore.
Quindi stiamo buttando via tutto da 5 in poi.
Così inizia + finale / 2 sarà la nostra fine nuovo,
Quindi sì, è sempre intenzione di rimanere oltre la fine della matrice.
Se si tratta di un caso se era pari o dispari, allora dovremmo controllare, per esempio, 4,
ma stiamo ancora buttando via -
Quindi sì, la fine sta andando sempre di essere al di là della fine effettiva della matrice.
Quindi gli elementi che si stanno concentrando su, fine sta andando sempre essere quello dopo.
E così se all'inizio fa mai fine uguali, siamo in un array di dimensione 0.
>> L'altra cosa che ho pensato è che stiamo aggiornando start per avviare da fine + / 2,
quindi questo è il caso che io sto avendo problemi con, dove partono + finale / 2
è l'elemento che stiamo controllando.
Diciamo che abbiamo avuto questo 10-elemento di matrice. Qualunque cosa.
Così inizia + finale / 2 sta per essere qualcosa come questo,
e se questo non è il valore, diciamo che vogliamo aggiornare.
Il valore è maggiore, quindi vogliamo guardare a questa metà della matrice.
Così come stiamo aggiornando inizio, stiamo aggiornando inizio ad essere ora questo elemento.
Ma questo può ancora funzionare, o per lo meno, si può fare di inizio + fine / 2 + 1.
[Studente] Non è necessario iniziare da fine + [incomprensibile] >> Si '.
Abbiamo già verificato questo elemento e so che non è quello che stiamo cercando.
Quindi non c'è bisogno di aggiornare dall'inizio per essere questo elemento.
Possiamo basta saltare e aggiornare iniziano ad essere questo elemento.
E c'è sempre un caso, diciamo, che questo fosse fine,
così poi iniziare è questo, start + finale / 2 sarebbe questo,
inizio fine + - Si ', penso che possa finire in una ricorsione infinita.
Diciamo che è solo un array di dimensione 2 o un array di dimensione 1. Penso che questo possa funzionare.
Quindi al momento, è l'elemento di inizio e fine è 1 di là di esso.
Quindi, l'elemento che stiamo andando a controllare è questo,
e poi quando si aggiorna inizio, stiamo aggiornando dall'inizio per essere 0 + 1/2,
che sta per finire ci riporta con partenza essendo questo elemento.
>> Quindi stiamo controllando lo stesso elemento più e più volte.
Quindi questo è il caso in cui ogni chiamata ricorsiva deve essere effettivamente aggiornare qualcosa.
Quindi abbiamo bisogno di fare start + end / 2 + 1, oppure c'è un caso
dove non è in realtà l'aggiornamento iniziale.
Ognuno vede che?
Va bene.
Qualcuno ha domande su questa soluzione o commenti più?
Va bene. Qualcuno ha una soluzione iterativa che tutti noi possiamo guardare?
Abbiamo tutti lo fanno in modo ricorsivo?
O anche Credo che se lei ha aperto, allora si potrebbe avere sovrascritto a quello precedente.
Ha salva automaticamente? Io non sono positive.
Qualcuno ha iterativo?
Siamo in grado di camminare attraverso di essa, se non insieme.
L'idea sarà lo stesso.
Iterativo soluzione.
Stiamo andando a voler fare sostanzialmente la stessa idea
dove vogliamo tenere traccia della nuova fine della matrice e il nuovo inizio della matrice
e farlo più e più volte.
E se quello che stiamo tenendo traccia di come l'inizio e la fine sempre si intersecano,
allora non lo abbiamo trovato e siamo in grado di restituire false.
Allora, come faccio a farlo? Qualcuno ha suggerimenti o codice per me per tirare su?
[Studente] fare un ciclo while. Sì >>.
Stai andando a voler fare un ciclo.
>> Lo si dispone di codice potrei tirare su, o quello che volevi suggerire?
[Studente] Penso di sì. Va bene >>. Questo rende le cose più facili. Qual era il suo nome?
[Studente] Lucas.
Revisione 1. Va bene.
Basso è quello che abbiamo chiamato prima di iniziare.
Up non è proprio quello che abbiamo chiamato prima della fine.
In realtà, alla fine è ora all'interno della matrice. E 'un elemento che dovrebbe prendere in considerazione.
Così basso è 0, è la dimensione della matrice - 1,
e ora stiamo looping, e stiamo verificando -
Credo che si può raggiungere a piedi attraverso di essa.
Qual è stato il vostro pensiero attraverso questo? Cammina con noi attraverso il vostro codice.
[Studente] Certo. Guarda il valore pagliaio in mezzo e confrontarlo con l'ago.
Quindi, se è più grande del tuo ago, poi si vuole - oh, in realtà, che dovrebbe essere al contrario.
Stai andando a voler buttare via la metà destra, e quindi si, che dovrebbe essere la strada.
[Bowden] Quindi questo dovrebbe essere meno? È che quello che hai detto? >> [Studente] Si '.
[Bowden] Ok. Di meno.
Quindi, se ciò che stiamo guardando è più piccolo di quello che vogliamo,
allora sì, si vuole buttare via la metà sinistra,
il che significa che stiamo aggiornando tutto quello che stiamo considerando
spostando basso a destra della matrice.
Questo sembra buono.
Io penso che abbia lo stesso problema che abbiamo detto su quello precedente,
dove se bassa è 0 ed è alto 1, quindi a basso + up / 2 sta per impostare fino a essere la stessa cosa di nuovo.
>> E anche se non è questo il caso, è ancora più efficiente per lo meno
sbarazzarvi l'elemento che abbiamo appena visto che sappiamo essere sbagliato.
Così basso + alto / 2 + 1 - >> [studente] Questo dovrebbe essere il contrario.
[Bowden] O questo dovrebbe essere - uno e l'altro deve essere + 1.
[Studente] E ci dovrebbe essere un doppio segno di uguale. >> [Bowden] Si '.
[Studente] Si '.
Va bene.
E, infine, ora che abbiamo questo + 1 - 1 cosa,
è - non può essere - è mai possibile che da basso a finire con un valore maggiore di up?
Penso che l'unico modo che può accadere - E 'possibile? >> [Studente] Non lo so.
Ma se si tronca e poi si fa meno che 1 e poi - >> Si '.
[Studente] Sarebbe forse avere incasinato.
Penso che dovrebbe essere buona solo perché
per farlo finire inferiore avrebbero dovuto essere uguali, credo.
Ma se sono uguali, allora non avrebbe fatto il ciclo while per cominciare
e abbiamo appena avrebbe restituito il valore. Quindi penso che siamo a posto ora.
Si noti che anche se questo problema non è più ricorsiva,
lo stesso tipo di idee si applicano dove possiamo vedere come questo così facilmente si presta
ad una soluzione ricorsiva dal fatto che stiamo solo aggiornando gli indici più e più volte,
stiamo rendendo il problema più piccolo, ci stiamo concentrando su un sottoinsieme della matrice.
[Studente] Se basso è 0 e fino a 1, che sarebbero entrambi 0 + 1/2, che sarebbe andato a 0,
e poi uno sarebbe + 1, uno sarebbe - 1.
[Studente] Dove stiamo verificando l'uguaglianza?
Come se quello centrale è in realtà l'ago?
Non stiamo facendo attualmente che? Oh!
Se E'-
Sì. Non possiamo fare la prova qui, perché diciamo la prima metà -
[Studente] In realtà è come non buttare via il limite.
Quindi, se buttare via il limite, è necessario verificare in primo luogo o qualsiasi altra cosa.
Ah. Gia '. >> [Studente] Si '.
Così ora abbiamo buttato via quella che abbiamo attualmente esaminato,
il che significa che ora abbiamo bisogno di avere anche
if (pagliaio [(basso + alto) / 2] == ago), allora possiamo restituire true.
E se ho messo altro o solo se, letteralmente significa la stessa cosa
perché questo avrebbe restituito true.
Così mi metterò altro se, ma non importa.
>> Quindi, se questo altro, altrimenti questo, e questa è una cosa comune che faccio
dove anche se è il caso in cui tutto è buono qui,
come il basso non può mai essere superiore in su, non è un ragionamento un valore di circa se questo è vero.
Così si può anche dire che, mentre bassa è inferiore o uguale a
o mentre bassa è inferiore
quindi se sono mai uguali o bassa succede a passare in su,
allora possiamo uscire da questo ciclo.
Domande, dubbi, commenti?
Va bene. Questo sembra buono.
Ora vogliamo fare di ordinamento.
Se andiamo alla mia seconda revisione, vediamo questi stessi numeri,
ma ora non sono più in modo ordinato.
E vogliamo implementare l'ordinamento utilizzando qualsiasi algoritmo in O di n log n.
Quindi l'algoritmo pensi che dovrebbe attuare qui? >> [Studente] merge sort.
[Bowden] Si '. Merge sort è O (n log n), ed è quello che stiamo per fare.
E il problema sta per essere abbastanza simili,
dove si presta facilmente ad una soluzione ricorsiva.
Possiamo anche trovare una soluzione iterativa, se vogliamo,
ricorsione, ma sarà più facile qui e dobbiamo fare la ricorsione.
Credo che ci guiderà attraverso merge sort in primo luogo,
anche se vi è un video lovely di merge sort già. [Risate]
Quindi merge sort ci sono - sto sprecando così tanto di questo lavoro.
Oh, c'è solo una sinistra.
Così si fondono.
Oh, 1, 3, 5.
Va bene.
Merge prende due array separati.
Individualmente i due array sono entrambi ordinati.
Quindi questo array, 1, 3, 5, ordinato. Questo array, 0, 2, 4, ordinato.
Ora che cosa unione dovrebbe fare è combinare in un singolo array che è esso stesso ordinati.
Quindi vogliamo un array di dimensione 6 che sta per avere questi elementi all'interno di esso
in modo ordinato.
>> E così siamo in grado di approfittare del fatto che questi due array sono ordinati
per fare questo in tempo lineare,
significato tempo lineare se questo array è x dimensioni e questo è y dimensioni,
allora l'algoritmo totale dovrebbe essere O (x + y). Va bene.
Così suggerimenti.
[Studente] Si potrebbe ricominciare da sinistra?
Quindi metto giù lo 0 e poi il 1 e poi qui siete al 2.
Quindi è un po 'come si dispone di una scheda che si muove verso destra. >> [Bowden] Si '.
Per entrambi questi array, se solo concentrarsi sull'elemento più a sinistra.
Dato che entrambi gli array sono ordinati, si sa che questi 2 elementi
sono i più piccoli elementi o matrice.
In modo che significa che 1 di questi 2 elementi deve essere il più piccolo elemento nel nostro array fuso.
Si dà il caso che il più piccolo è quello sulla destra questa volta.
Quindi prendiamo 0, inserirla sulla sinistra perché 0 è minore di 1,
in modo da prendere 0, inserirlo nella nostra prima posizione, e poi aggiornare questa
a concentrarsi ora sul primo elemento.
E ora ripetiamo.
Così ora mettiamo a confronto 2 e 1. 1 è più piccolo, quindi dovremo inserire 1.
Aggiorniamo questo puntatore per puntare a questo ragazzo.
Ora lo facciamo di nuovo, in modo 2. Questo aggiornerà, confrontare questi 2, 3.
Questo aggiornamento, poi 4 e 5.
Così che è unione.
>> Dovrebbe essere abbastanza evidente che si tratta di tempo lineare dato che basta andare su ogni elemento di una volta.
E questo è il più grande passo per l'attuazione merge sort sta facendo questo.
E non è così difficile.
Un paio di cose di cui preoccuparsi è diciamo eravamo fusione 1, 2, 3, 4, 5, 6.
In questo caso si finisce nello scenario in cui questo sta andando essere più piccoli,
allora aggiorniamo questo puntatore, questo sta andando essere più piccole, aggiornare questo,
questo è più piccolo, e ora si deve riconoscere
quando hai effettivamente eseguito su elementi da confrontare con.
Dal momento che abbiamo già utilizzato questo array,
tutto in questo array è ora appena inserito in questa sede.
Quindi, se mai eseguito nel punto in cui uno dei nostri array è completamente fusa già,
poi basta prendere tutti gli elementi della matrice altro e inserirle nella fine della matrice.
Quindi possiamo solo inserire 4, 5, 6. Va bene.
Questa è una cosa a cui prestare attenzione.
Attuazione che dovrebbe essere il punto 1.
Merge sort poi in base a questo, è a 2 passi, 2 passi stupidi.
Diciamo solo dare questo array.
Così merge sort, punto 1 è quello di rompere ricorsivamente l'array in due metà.
Quindi dividere questo array in due metà.
Ora abbiamo 4, 15, 16, 50 e 8, 23, 42, 108.
E ora lo facciamo di nuovo e abbiamo diviso questi a metà.
Ho appena faro 'da questa parte.
Quindi 4, 15 e 16, 50.
Vorremmo fare la stessa cosa qui.
E ora ci si divise in due parti di nuovo.
E abbiamo 4, 15, 16, 50.
Quindi, questo è il nostro caso base.
Una volta che le matrici sono di dimensione 1, quindi ci fermiamo con la scissione in due parti.
>> Ora che cosa facciamo con questo?
Finiamo questo inoltre si suddividono in 8, 23, 42, e 108.
Quindi, ora che siamo a questo punto, ora passo due di merge sort è solo la fusione coppie alle liste.
Quindi vogliamo unire questi. Ci basta chiamare unione.
Sappiamo unione torneremo questi in modo ordinato.
4, 15.
Ora vogliamo unire questi, e che restituirà una lista con quelli in modo ordinato,
16, 50.
Siamo quelli che si fondono - Non riesco a scrivere - 8, 23 e 42, 108.
Così abbiamo coppie unite una volta.
Ora dobbiamo solo unire di nuovo.
Si noti che ciascuna di queste liste è ordinato in sé,
e poi si può solo unire queste liste per ottenere un elenco di dimensioni 4 che è ordinato
e unione di queste due liste per ottenere un elenco di dimensioni 4 che è ordinato.
E, infine, siamo in grado di unire i due elenchi di dimensione 4 per ottenere una lista di dimensione 8 che è ordinato.
Quindi, per vedere che questo è nel complesso n log n, abbiamo già visto che la fusione è lineare,
così quando abbiamo a che fare con la fusione questi, così come il costo complessivo della fusione
per queste due liste è solo 2 perché -
O beh, e 'O di n, ma n qui è solo questi 2 elementi, in modo che sia 2.
E questi 2 sarà 2 e questi 2 sarà 2 e questi 2 sarà 2,
così su tutte le fusioni che dobbiamo fare, si finisce per fare n.
Come 2 + 2 + 2 + 2 è 8, che è n,
quindi il costo della fusione in questa serie è n.
E poi la stessa cosa qui.
Ci unire questi 2, quindi questi 2, e individualmente questa unione avrà quattro operazioni,
questa unione avrà quattro operazioni, ma ancora una volta, tra tutti questi,
si finisce per unire n cose totali, e così questa operazione richiederà n.
E così ogni livello ha n elementi alla fusione.
>> E quanti livelli ci sono?
Ad ogni livello, la serie cresce taglia 2.
Ecco le nostre matrici sono di dimensione 1, qui sono di dimensione 2, qui sono di dimensione 4,
e, infine, sono di dimensione 8.
Quindi, dal momento che è il raddoppio, ci saranno un totale di n log di questi livelli.
Quindi, con log n livelli, ogni singolo livello di assunzione n operazioni totali,
otteniamo un log n n algoritmo.
Domande?
Sono persone già compiuto progressi sulle modalità di attuazione del presente?
C'è qualcuno che è già in uno stato in cui posso solo tirare su il loro codice?
Posso dare un minuto.
Questo sta andando essere più lungo.
Consiglio vivamente recidiva -
Non è necessario fare la ricorsione per unione
perché per fare la ricorsione per unione, si sta andando ad avere per passare un po 'di diverse dimensioni.
È possibile, ma è fastidioso.
Ma ricorsione per l'ordinamento in sé è abbastanza facile.
Basta chiamare letteralmente ordinamento metà sinistra, sorta a metà destra. Va bene.
Qualcuno ha qualcosa che posso tirare ancora registrato?
Oppure darò un minuto.
Va bene.
Qualcuno ha qualcosa che possiamo lavorare?
Oppure dobbiamo solo lavorare con questo e quindi espandere da lì.
>> Qualcuno ha più di questo che posso tirare su?
[Studente] Si '. Si può tirare la mia. Va bene >>.
Sì!
[Studente] Ci sono stati un sacco di condizioni. >> Oh, cavolo. Can you -
[Studente] devo salvarlo. Sì >>.
Così abbiamo fatto fare l'unione separatamente.
Oh, ma non è così male.
Va bene.
Così sorta in sé è semplicemente chiamando mergeSortHelp.
Spiegaci cosa mergeSortHelp fa.
[Studente] MergeSortHelp praticamente fa molto le due fasi principali,
che è di ordinare ogni metà della matrice e poi unire entrambi.
[Bowden] Ok, allora dammi un secondo.
Penso che questo - >> [studente] Ho bisogno di -
Gia '. Mi manca qualcosa.
In unione, mi rendo conto che ho bisogno di creare un nuovo array
perché non potrei farlo al suo posto. Sì >>. Non è possibile. Correggi.
[Studente] Così ho creato un nuovo array.
Ho dimenticato alla fine di unione per ri-cambiare.
Va bene. Abbiamo bisogno di un nuovo array.
In merge sort, questo è quasi sempre vero.
Parte del costo di un algoritmo migliore tempo-saggio
è quasi sempre la necessità di utilizzare la memoria un po 'di più.
Quindi, ecco, non importa come si fa merge sort,
si sarebbe inevitabilmente necessario utilizzare un po 'di memoria aggiuntiva.
Lui o lei ha creato un nuovo array.
E poi dire alla fine abbiamo solo bisogno di copiare nuova matrice nella matrice originale.
[Studente] Penso di sì, sì.
Non so se funziona, in termini di conteggio di riferimento o qualsiasi altra cosa -
Sì, funzionerà. >> [Studente] Ok.
Hai provato l'esecuzione di questo? >> [Studente] No, non ancora. Va bene >>.
Provare a eseguire, e poi ne parlerò per un secondo.
[Studente] Ho bisogno di avere tutti i prototipi di funzione e tutto il resto, pero ', vero?
I prototipi di funzione. Oh, vuoi dire come - Sì.
Ordina chiama mergeSortHelp.
>> Quindi, al fine di ordinamento chiamare mergeSortHelp, mergeSortHelp deve essere stata definita
prima di ordinare o ci serve solo il prototipo. Basta copiare e incollare questo.
E allo stesso modo, mergeSortHelp chiama unione,
ma unione non è stata ancora definita, in modo che possiamo lasciare che mergeSortHelp sapere
che questo è ciò che si fondono è andare a guardare come, e questo è tutto.
Così mergeSortHelp.
Abbiamo un problema qui dove non abbiamo alcun caso base.
MergeSortHelp è ricorsiva, in modo che qualsiasi funzione ricorsiva
avrà bisogno di un qualche tipo di scenario di base per sapere quando smettere di chiamare sé stesso ricorsivamente.
Qual è il nostro scenario di base sarà qui? Gia '.
[Studente] Se la dimensione è di 1? >> [Bowden] Sì.
Così come abbiamo visto proprio lì, ci siamo fermati array scissione
una volta arrivati ​​in un array di dimensione 1, che inevitabilmente sono a loro volta ordinati.
Quindi, se la dimensione è uguale a 1, sappiamo che l'array è già ordinato,
in modo che possiamo semplicemente restituire.
>> Si noti che è vuoto, in modo da non restituiscono niente di particolare, abbiamo appena ritorno.
Va bene. Ecco, questo è il nostro caso base.
Credo che il nostro scenario di base potrebbe essere anche se ci capita di essere la fusione un array di dimensione 0,
probabilmente vuole fermare a un certo punto,
quindi possiamo dire dimensione inferiore a 2 o inferiore o uguale a 1
in modo che questo funziona per qualsiasi matrice ora.
Va bene.
Ecco, questo è il nostro caso base.
Ora vuoi camminare noi attraverso unione?
Che cosa significano tutti questi casi?
Quassù, stiamo solo facendo la stessa idea, la -
[Studente] Ho bisogno di essere di passaggio dimensioni, con tutte le chiamate mergeSortHelp.
Ho aggiunto dimensioni come primario aggiuntivo e non è lì, come dimensioni / 2.
[Bowden] Oh, taglia / 2, superficie / 2. >> [Studente] Sì, e anche nella funzione di cui sopra pure.
[Bowden] qui? >> [Studente] Proprio dimensioni. >> [Bowden] Oh. Taglia, taglia? >> [Studente] Si '.
[Bowden] Ok.
Fammi pensare per un secondo.
Non ci si imbatte in un problema?
Siamo sempre trattare il sinistro come 0. >> [Studente] No.
Questo è sbagliato troppo. Scusi. Dovrebbe essere inizio. Gia '.
[Bowden] Ok. Mi piace che meglio.
E fine. Va bene.
Quindi ora vuoi camminare noi attraverso unione? >> [Studente] Ok.
Sto solo a piedi attraverso questa nuova matrice che ho creato.
La sua dimensione è la dimensione della porzione di matrice che vogliamo essere ordinati
e cercando di trovare l'elemento che dovrei mettere nel passaggio nuovo array.
Quindi, per fare questo, in primo luogo sto controllando se la metà sinistra della matrice continua ad avere elementi più,
e se non lo fa, allora si scende a condizione che gli altri, che dice basta
va bene, deve essere nel campo di destra, e metteremo che nell'indice corrente di newArray.
>> E poi altrimenti, sto controllando se il lato destro della matrice è terminata,
nel qual caso ho appena messo nella sinistra.
Questo non potrebbe in realtà essere necessario. Non ne sono sicuro.
Ma in ogni caso, gli altri due verifica quale delle due sono più piccoli in sinistra o destra.
E anche in ogni caso, sto incrementando qualsiasi segnaposto che incrementare.
[Bowden] Ok.
Questo sembra buono.
Qualcuno ha commenti o dubbi o domande?
Così i quattro casi che dobbiamo portare le cose in solo di essere - o sembra che cinque -
ma dobbiamo considerare se la matrice di sinistra è a corto di cose che dobbiamo unire,
se il campo di destra è a corto di cose che dobbiamo unire -
Io sto puntando a nulla.
Quindi, se la matrice di sinistra è a corto di cose o di campo di destra è a corto di cose.
Questi sono due casi.
Abbiamo anche bisogno il caso banale di se la cosa a sinistra è minore la cosa giusta.
Poi vogliamo scegliere la cosa di sinistra.
Questi sono i casi.
Quindi questo era giusto, in modo che è così.
Matrice sinistra. È 1, 2, 3. Va bene. Quindi sì, queste sono le quattro cose che potremmo voler fare.
E non andrà oltre una soluzione iterativa.
Non lo consiglio -
Merge sort è un esempio di una funzione che è sia non tail ricorsiva,
non è facile fare la coda ricorsiva,
ma non è molto facile da fare è iterativo.
Questo è molto facile.
Questa implementazione di merge sort,
unire, non importa quello che fai, che stai andando a costruire unione.
>> Così merge sort costruito sulla cima di unione è ricorsivamente solo queste tre righe.
Iterativo, è più fastidioso e più difficile da pensare.
Ma si noti che non è la coda ricorsiva dal mergeSortHelp - quando si chiama -
ha ancora bisogno di fare le cose dopo questo ritorno della chiamata ricorsiva.
Quindi questo stack frame deve continuare ad esistere anche dopo la chiamata a questo.
E poi quando si chiama questo, lo stack frame deve continuare ad esistere
perché anche dopo la chiamata, abbiamo ancora bisogno di unire.
Ed è banale per rendere questa coda ricorsiva.
Domande?
Bene.
Quindi, tornando a ordinare - oh, ci sono due cose che voglio mostrare. Va bene.
Tornando al tipo, faremo in fretta.
Oppure cerca. In ordine? Ordina. Gia '.
Tornando agli inizi del genere.
Vogliamo creare un algoritmo che ordina l'array usando un algoritmo
in O di n.
Così come è possibile? Qualcuno ha qualche tipo di -
Ho accennato prima al -
Se stiamo per migliorare, passando da n log n a O di n,
abbiamo migliorato il nostro algoritmo di time-saggio,
il che significa che ciò che abbiamo intenzione di bisogno di fare per compensare questo?
[Studente] Spazio. Sì >>. Abbiamo intenzione di utilizzare più spazio.
E non anche solo più spazio, è lo spazio esponenzialmente più.
Quindi penso che questo tipo di algoritmo è qualcosa di pseudo, polinomio pseudo -
pseudo - non ricordo. Pseudo qualcosa.
Ma è perché abbiamo bisogno di usare tanto spazio
che questo è possibile, ma non è realistico.
>> E come si fa a raggiungere questo obiettivo?
Siamo in grado di farlo, nel caso vi possiamo garantire che un particolare elemento della matrice
è al di sotto di una certa dimensione.
Quindi, diciamo solo che la dimensione è di 200,
qualsiasi elemento di un array è inferiore a grandezza 200.
E questo è in realtà molto realistico.
Si può facilmente avere una matrice che tu sai tutto in esso
sarà inferiore a un certo numero.
Come se avete qualche vettore assolutamente enormi o qualcosa del genere
ma tu sai tutto quello che sta per essere tra 0 e 5,
allora sarà significativamente più veloce per fare questo.
E il limite su qualsiasi degli elementi è 5,
così questo limite, che è la quantità di memoria che si vuole utilizzare.
Quindi, il limite è 200.
In teoria c'è sempre un limite dal momento che un numero intero può essere fino a 4 miliardi di euro,
ma questo è realistica in quanto si verrebbe così ad utilizzare lo spazio
dell'ordine di 4 miliardi. Ecco, questo è irrealistico.
Ma qui diremo la nostra associazione è di 200.
Il trucco per farlo in O di n è che facciamo un altro array chiamato conta di dimensioni BOUND.
Quindi, in realtà, questa è una scorciatoia per - Io in realtà non so se Clang fa questo.
Ma nel GCC almeno - Sto Clang ammesso che fa anche -
questo sarà solo inizializzare l'intero array di essere 0s.
Quindi, se io non voglio farlo, quindi ho potuto fare a parte for (int i = 0;
i <BOUND, i + +) e conta [i] = 0;
Così ora tutto è inizializzato a 0.
Ho iterazioni su mia matrice,
e quello che sto facendo è che sto contando il numero di ciascun - Andiamo qui.
Abbiamo 4, 15, 16, 50, 8, 23, 42, 108.
Quello che sto contando il numero di occorrenze di ciascuna di tali elementi.
Facciamo in realtà aggiungere un paio più in là con alcune ripetizioni.
Quindi il valore che abbiamo qui, il valore di tale sarà array [i].
Quindi val potrebbero essere 4 o 8 o qualsiasi altra cosa.
E ora sto contando quanti di quel valore che ho visto,
quindi conta [val] + +;
Dopo aver fatto questo, conta è andare a guardare qualcosa come 0001.
Facciamo conta [val] - VINCOLATO + 1.
>> Ora che è solo per tenere conto del fatto che stiamo a partire da 0.
Quindi, se 200 è sarà il nostro più grande numero,
quindi 0 per 200 è 201 cose.
Quindi conta, sarà simile a 00.001, dato che disponiamo 4.
Poi avremo 0001 dove avremo un 1 nell'indice 8 conteggio.
Avremo un 2 nell'indice 23 count.
Avremo un 2 nell'indice 42 ° numero.
Così possiamo usare count.
Così num_of_item = conta [i].
E quindi se num_of_item è 2, che significa che vogliamo inserire i 2 del numero
nel nostro array ordinato.
Quindi abbiamo bisogno di tenere traccia di quanto siamo lontani nella matrice.
Così index = 0.
Array - mi limiterò a scrivere.
Conti -
array [index + +] = i;
E 'questo quello che voglio? Penso che sia quello che voglio.
Sì, questo sembra buono. Va bene.
Così fa capire a tutti quale sia lo scopo della mia matrice conta è?
Si conta il numero di occorrenze di ciascuno di questi numeri.
Poi io sono l'iterazione di tale matrice conta,
e la posizione esima dell'array conta
è il numero di i è che dovrebbe apparire nel mio array ordinato.
È per questo che conta di 4 sta per essere 1
e conta di 8 sta per essere 1, conta di 23 sta per essere 2.
È così che molti di loro voglio inserire nel mio array ordinato.
Poi ho solo farlo.
Sto inserendo num_of_item mi e 'nel mio array ordinato.
>> Domande?
E così ancora una volta, questo è il tempo lineare, dal momento che sono solo l'iterazione di una volta,
ma è anche lineare in quanto questo numero sembra essere,
e quindi dipende in larga misura ciò che la vostra associazione è.
Con un balzo di 200, che non è poi così male.
Se la vostra associazione sta per essere 10.000, allora questo è un po 'peggio,
ma se la vostra associazione sta per essere 4 miliardi di euro, che è completamente irrealistico
e questo array sta andando ad avere per essere di dimensione 4 miliardi di euro, che non è realistico.
Quindi, questo è tutto. Domande?
[Risposta degli studenti incomprensibile] >> Ok.
Ho capito un'altra cosa, quando stavamo attraversando.
Penso che il problema era in Lucas e probabilmente ognuno che abbiamo visto.
Ho completamente dimenticato.
L'unica cosa che volevo commentare è che quando hai a che fare con cose come gli indici,
non si è mai davvero vedere questo quando si scrive un ciclo for,
ma tecnicamente, ogni volta che hai a che fare con questi indici,
si dovrebbe quasi sempre a che fare con i numeri interi senza segno.
La ragione di questo è quando hai a che fare con i numeri interi con segno,
quindi se si dispone di 2 interi con segno e li sommano
e finiscono troppo grande, allora si finisce con un numero negativo.
Ecco, questo è quello che è integer overflow.
>> Se posso aggiungere 2 miliardi e 1 miliardo, io alla fine con negativo 1 miliardo.
Ecco come numeri interi funziona su computer.
Quindi il problema con l'utilizzo -
Questo è bene, tranne se basso sembra essere 2 miliardi e capita fino a 1 miliardo,
allora questo sarà negativo 1 miliardo e poi andremo a dividere che per 2
e finire con negativo 500 milioni.
Quindi, questo è solo un problema se vi capita di essere alla ricerca attraverso un array
di miliardi di cose.
Ma se succede + basso fino a traboccare, allora questo è un problema.
Non appena li facciamo senza segno, quindi 2 miliardi di dollari più 1 miliardo 3 miliardi.
3000000000 diviso 2 è di 1,5 miliardi di euro.
Così, non appena sono unsigned, tutto è perfetto.
E così che è anche un problema quando si scrive un ciclo FOR,
e in realtà, probabilmente lo fa automaticamente.
Essa in realtà solo urlare contro di voi.
Quindi, se questo numero è troppo grande per essere solo in un numero intero, ma si adatterebbe in un intero senza segno,
sarà urlare contro di voi, è per questo che non hai mai veramente incontrato il problema.
Si può vedere che un indice non sta per essere negativo,
e così quando si è l'iterazione di un array,
si può quasi sempre dire unsigned int i, ma non si ha realmente bisogno.
Le cose stanno andando a lavorare più o meno altrettanto bene.
Va bene. [Sussurra] Che ora è?
L'ultima cosa che volevo mostrare - e mi limiterò a farlo davvero veloce.
Tu sai come abbiamo # define in modo che possiamo # define MAX come 5 o qualcosa del genere?
Cerchiamo di non fare MAX. # Define BOUND come 200. Questo è quello che abbiamo fatto prima.
Questo definisce una costante, che è solo andare a essere copiato e incollato
ovunque ci capita di scrivere BOUND.
>> Così possiamo davvero fare di più con # define.
Siamo in grado di definire le funzioni #.
Non sono in realtà funzioni, ma che chiameremo funzioni.
Un esempio potrebbe essere qualcosa di simile a MAX (x, y) è definito come (x <y y: x). Va bene.
Così si dovrebbe abituarsi alla sintassi operatore ternario,
ma è inferiore a x y? Ritorno y, else return x.
Così si può vedere è possibile rendere questo una funzione separata,
e la funzione potrebbe essere come bool MAX prende 2 argomenti, restituire questo.
Questo è uno di quelli più comuni che vedo fatto così. Noi li chiamiamo macro.
Si tratta di una macro.
Questo è solo la sintassi per questo.
È possibile scrivere una macro per fare quello che vuoi.
È frequente vedere Macro per il debug printfs e roba del genere.
Quindi un tipo di printf, ci sono costanti speciali in C, come sottolineano LINE sottolineatura,
2 sottolinea LINE sottolineatura,
e c'è anche penso due sottolineatura FUNC. Questo potrebbe essere. Qualcosa del genere.
Quelle cose verrà sostituito con il nome della funzione
o il numero della riga che si è in.
Spesso si scrive printfs debug che qui avrei potuto poi basta scrivere
DEBUG e sarà il numero della linea e la funzione che mi capita di essere in
che ha rilevato che la dichiarazione DEBUG.
E si può anche stampare altre cose.
Quindi, una cosa che si dovrebbe guardare fuori per è che se mi capita di definire # DOUBLE_MAX
come qualcosa come 2 * y e 2 * x.
Quindi, per qualsiasi motivo, vi capita di fare un sacco.
Così ne fanno un macro.
Questo è effettivamente rotto.
Io lo definirei facendo qualcosa di simile DOUBLE_MAX (3, 6).
Che cosa si deve essere restituito?
[Studente] 12.
Sì, 12 deve essere restituito, e 12 viene restituito.
3 viene sostituito per x, 6 viene sostituito per y, e ci restituisce 2 * 6, che è 12.
Ora, che dire di questo? Quali devono essere restituite?
[Studente] 14. >> Idealmente, 14.
Il problema è che come hash definisce il lavoro, ricordatevi che è una copia letterale e incolla
di praticamente tutto, quindi ciò che questo sta per essere interpretato nel senso che
è 3 meno di 1 + 6, 2 volte 1 più 6, 2 volte 3.
>> Quindi, per questo motivo è quasi sempre avvolgere tutto tra parentesi.
Ogni variabile è quasi sempre avvolgere tra parentesi.
Ci sono casi in cui non si devono, come so che non ho bisogno di farlo qui
perché meno è praticamente sempre e solo andare a lavorare,
anche se questo potrebbe anche non essere vero.
Se c'è qualcosa di ridicolo come DOUBLE_MAX (1 == 2),
allora che si fara 'sostituito con 3 è uguale a meno di 1 è uguale a 2,
e così poi è andare a fare 3 minore di 1, vuol uguale a 2,
che non è quello che vogliamo.
Quindi, al fine di prevenire eventuali problemi di precedenza degli operatori,
avvolgere sempre tra parentesi.
Va bene. E questo è tutto, 5:30.
Se avete domande sul pset, fatecelo sapere.
Dovrebbe essere divertente, e l'edizione hacker è anche molto più realistico
rispetto all'edizione hacker lo scorso anno, quindi speriamo che molti di voi provare.
L'anno scorso è stato molto travolgente.
>> [CS50.TV]