[Mūzikas atskaņošanai] 

ANDI PENG: Aicinām sadaļas 3 nedēļas. Paldies, jūs puiši, visiem nāk uz šo agrāko sākuma laiku šodien. Mēs esam ieguvuši jauku, nedaudz intīms grupa šodien. Tik cerams, mēs sāksim apdare, iespējams, agri, mazliet agri šodien. Tik ātri, tikai daži paziņojumi par darba kārtībā šodien. Pirms sākam, mēs esam gatavojas tikai iet pa dažas īsas loģistikas jautājumiem, PSET jautājumi, debrief, lietas, piemēram, ka. Un tad mēs nirt tiesības. Mēs izmantosim atkļūdotājs sauc GDB līdz sākt atmaskot mūsu kodu, kas David izskaidrots lekciju citu dienu. Mēs iet pār četru veidu veidu. Mēs iet pār viņiem diezgan ātri jo viņi diezgan intensīva. Bet zinu, ka visi slaidi un pirmkods vienmēr tiešsaistē. Lai justies brīvi, pēc jūsu pārlasīšana, lai atgriezties un apskatīt to. 

Mēs iet cauri asimptotiskās notācija, kas ir tikai iedomātā veids kā pateikt "runtimes," kur mums ir Big O, kas David paskaidrots lekciju. Un mums ir arī Omega, kas ir zemākā robeža runtime. Un mēs runājam mazliet vairāk padziļināti par to, kā šos darbus. Un visbeidzot, mēs iet pār bināro meklēšanu, jo daudz no jums, kas ir jau paskatījās jūsu psets droši vien zināt, ka tas ir jautājums, kas ir jūsu PSET. Tātad jūs visi būtu laimīgi ka mēs uz šo šodien. 

Un visbeidzot, par savu sadaļa atsauksmes, es tiešām atstāja aptuveni 15 minūtes pēc beigām, lai tikai iet pa loģistika pset3, kādi jautājumi, varbūt mazliet vadlīnijas, ja jūs, Pirms mēs sākam programmēšanu. Tātad pieņemsim mēģināt tikt cauri materiāls diezgan ātri. Un tad mēs varam pavadīt kādu laiku ņemot vairākus jautājumus par PSET. LABI. 

Ātri, lai tikai daži paziņojumi, pirms mēs sākam jau šodien. Pirmkārt, welcome to padarot tas caur diviem no jūsu psets. Paņēmu apskatīt your-- yeah, pieņemsim iegūt kārta aplausi par šo vienu. Patiesībā, es biju patiesi, patiešām iespaidu. Es sašķirotas pirmo PSET jums puiši Pagājušajā nedēļā un jums puiši izdarīja neticami. 

Stils bija brīdī Bez dažiem komentāriem. Pārliecinieties, ka jūs esat vienmēr Komentējot savu kodu. Bet jūsu psets bija punktu. Un glabā to uz augšu. Un tas ir labi, lai greiders uz redzu, ka jūs guys ir liekot tik daudz pūļu, savu stilu un jūsu dizains savu kodu ka mēs vēlētos, lai jūs varētu redzēt. Tāpēc es esmu iet gar manu pateicību par pārējiem Tehniskās vienošanās. 

Tomēr pastāv daži debrief jautājumi Es tikai gribu, lai iet pār būtu gan manu dzīvi un daudz otra Tehniskās vienošanās "dzīvo mazliet vieglāk. Pirmkārt, es esmu ievērojis, šis pagātne week-- cik daudzi no jums ir darboties check50 uz Jūsu kods, pirms jūs iesniedzat? LABI. Tāpēc ikvienam vajadzētu darīt check50, because-- secret-- mēs faktiski palaist check50 kā daļu no mūsu pareizību skripti testēšana savu kodu. Tātad, ja jūsu kods nepilda check50, visticamāk, tas ir iespējams, gatavojas neizdoties mūsu pārbaudi, kā arī. Dažreiz jūs guys ir pareizās atbildes. Līdzīgi, jo mantkārīgs, daži Jums ir tiesības numurus, jūs vienkārši izdrukāt dažas papildu sīkumi. Un ka papildu sīkumi faktiski neiztur pārbaudi, jo dators nav tiešām zināt, ko tas meklē. Un tā tas būs vienkārši palaist cauri, redzēt, ka jūsu izejas nav saskaņot to, ko mēs sagaidām atbildi būt, un atzīmējiet tas ir nepareizi. 

Un es zinu, ka notika daži no jūsu gadījumu šonedēļ. Tāpēc es devos atpakaļ un manuāli pāršķiro ikviena kodu. Nākotnē gan, lūdzu, lūdzu, pārliecinieties, ka ka jūs strādājat pārbaudīt 50 uz jūsu kodu. Jo tas ir sava veida sāpes par TA lai iet atpakaļ un manuāli pāršķirošanu katru PSET par katru single, mazliet garām instance. Tāpēc es neņēma nost nekādus punktus. Es domāju, ka es novilka varbūt viens vai divi projektēšanai. Nākotnē, lai gan, ja jūs nedarot check50, punkti tiks ņemti off pareizību. 

Turklāt psets ir dēļ piektdienās plkst. Es domāju, ka tur ir septiņu minūšu vēlu labvēlības periods, kas mums dos jums. Per Hārvardas laiku, viņi ļāva būt septiņas minūtes, vēlu, lai viss. Tātad šeit at Yale, mēs ievērot, ka labi. Bet diezgan daudz, pie 12:07, Ja jūsu PSET nav, tas būs jāmarķē kā vēlu. Un tā, kamēr tas tiek atzīmēts kā vēlu, tad TA-- es esmu joprojām būs šķirošanas jūsu psets. Tātad jūs joprojām redzēt parādīsies pakāpes. Tomēr zinu, ka beigas semestrī, visi vēlu psets būs tikai automātiski noregulē uz nulli ar datoru. 

Mēs to darām, divu iemeslu dēļ. Viens, dažreiz mēs attaisnojama, tāpat prāvesta attaisnojumus, vēlāk, ka es nezinu par vēl. Tāpēc mēs gribētu, lai pārliecinātos, mēs klasificēšanai viss tikai gadījumā, piemēram, es esmu trūkst dekāna attaisnojums. Un, otrkārt, paturiet prāta, jūs joprojām varat piliens vienu PSET, ka ir pilnā apjomā punktus. Un tā mēs vēlētos grade visiem jūsu psets tikko lai pārliecinātos, ka jūsu darbības joma ir tur un jūs cenšaties viņus. Tātad, pat ja tas ir vēlu, jūs joprojām saņemt kredītu jomas jautājumiem, es domāju. 

Tātad morālā no stāsts ir, padarīt ka jūsu psets ir uz laiku. Un, ja tie nav uz laiku, zinu, ka tas nav liels. Jā, pirms es virzīties tālāk, vai kāds ir kādi jautājumi par PSET atsauksmes? Jā. 

Mērķauditorija: Vai jūs teiktu, mēs var nomest kādu no psets? 

ANDI PENG: Jā. Tātad tur ir deviņi psets kopumā gaitā semestra. Un, ja jums ir joma points-- tā darbības joma ir tikai, diezgan daudz, jūs mēģināt veikt problēma, jūs liekot laikā, Jūs parādot, ka jūs esat demonstrēja esat izlasījis spec. Tas ir diezgan plašas. Un, ja jūs pilda joma punkti, mēs var nomest zemākais viens no pilnā apjomā. Tātad tas ir jūsu priekšrocības pabeigt un izmēģināt visu PSET. 

Pat upload-- ja neviena no viņiem strādāt, augšupielādēt tos visus. Un tad mēs, cerams, varēs sniegt jums dažus no šiem punktiem atpakaļ. Cool. Jebkuri citi jautājumi? Liels. 

Otrkārt, biroja hours-- daži ātri piezīmes par darba laika. Tātad, pirmkārt, nāk agri nedēļā. Neviens nekad at Darba laiks pirmdienās. Christabel ieradās Darba laiks pēdējā naktī. Jā, Christabel. Un ko mums birojā stundas vakar vakarā, Christabel? 

Mērķauditorija: Mums bija saldējumu. 

ANDI PENG: Tāpēc, ka ir labi, mums bija saldējums pie darba laika pēdējā naktī. Lai gan es nevaru apsolīt, ka mums būs saldējums pie darba laika katru nedēļu, ko es varu jums apsolīt ir tā, ka tur būs daudz labāk studentam TA attiecību. Tāpat legit, tas ir tāpat kā trīs pret vienu. Tā kā, kontrasts, ka ar Ceturtdiena, tev par 150 tiešām uzsvēra, bērni un nav saldējumu. Un tas ir tikai nav produktīvs ikvienam. Tātad stāsts morāles ir, nāk agri uz darba laika un labas lietas notiks. 

Arī nāk gatava uzdot jautājumus. Tu zini? Neatkarīgi no tā, TAS, es domāju, ir teikts, mēs esam iegūt pāris studentus kas nonāk ceturtdien, piemēram, 10:50 ne izlasot spec ir līdzīgi man palīdzēt, palīdziet man. Diemžēl šajā brīdī, tur ir nav daudz mēs varam darīt, lai palīdzētu jums. Tāpēc, lūdzu, nāk agri nedēļā. Nāciet agri darba laika. Nāciet gatavi uzdot jautājumus. Pārliecinieties, ka jūs, kā students, esam tur, kur Jums ir nepieciešams, lai būtu tā, ka Tehniskās vienošanās var jums kopā, kas ir tas, ko darba laiks vajadzētu tikt atvēlēts. 

Otrkārt, tāpēc es zinu, profesori patīk pārsteigt mūs ar testiem. Man bija profesors šos piemēram, yo, starp citu, atcerieties, ka vidēja termiņa Jums ir nākamajā pirmdienā. Jā, es nezināju par šo vidusposma. Tāpēc es esmu gatavojas būt, ka TA kas atgādina jums visu šo viktorīnu 0-- jo jūs zināt, mēs esam CS. Tagad, ka mēs esam darījuši bloki, jūs saņemsiet kāpēc tas ir viktorīna 0, ne viktorīna 1, vai nē? LABI. Ak, es saņēmu dažas chuckles par šo vienu. LABI. 

Tātad viktorīna 0 būs 14 oktobrim, ja tu esi no pirmdienas līdz trešdienas sadaļu un 15. oktobrī, ja tu esi otrdiena līdz ceturtdienai sadaļā. Tas neattiecas uz Tiem no jums, Harvard who-- Es domāju, ka jums viss būs ņemot jūsu viktorīnas par 14. 

Tātad yeah, nākamnedēļ, ja David, lekciju, iet, yeah, tāpēc par to, ka viktorīna nākamnedēļ, jūs visi netiks šokēts, jo jums nāca uz sadaļu un jūs zināt, ka jūsu viktorīna 0 ir divas nedēļas. Un mums būs atsauksmi sesijas un viss. Līdz ar to nav rūpes par ir bail par to. Visus jautājumus before-- kādi jautājumi visu par loģistikas jautājumiem, šķirošana, darba laiks, sekcijas? Jā. 

Mērķauditorija: Tātad viktorīna ir būs lekciju laikā? 

ANDI PENG: Jā. Tātad viktorīnas, es domāju, ir 60 minutes atvēlēts šajā laika slots ka jūs vienkārši ņemt ar lekciju zālē. Tātad jums nav nonākt par, piemēram, izlases 7:00 PM. Tas viss ir labi. Jā. Cool. 

Viss kārtībā. Tātad mēs ejam ieviest koncepciju, lai jums šonedēļ, ka Deivids ir jau sava veida no pieskārās lekciju pagājušajā nedēļā. To sauc GDB. Un cik daudzi no jums, bet Par rakstot savu psets Protams, ir pamanījuši lielu pogu, kas saka "Debug" uz augšu jūsu IDE? LABI. Tāpēc tagad mēs faktiski nokļūt atklāt noslēpums, kas tas patiesībā pogas dara. Un es garantija jums, tas ir skaista, skaista lieta. 

Tātad līdz šim, es domāju, ka tur ir bijis divas lietas studenti bijuši parasti darot, kad debugging psets. Viens, viņi vai nu pievienot printf () - tā ik pēc dažām līnijām, viņi pievienot ar printf () - Ak, kas tas ir mainīgs? Ak, kas tas ir mainīgs now-- un jūs veida redzēt progresēšanu Jūsu kodu, kā tas darbojas. Vai otrā metode bērniem darīt, ir ka viņi vienkārši uzrakstīt visa lieta un pēc tam iet, piemēram, tas beigās. Cerams, ka tas darbojas. I garantija jums, GDB ir labāk nekā abas šīs metodes. Jā. Tātad tas būs jūsu jaunais labākais draugs. Jo tas ir skaista lieta kas vizuāli parāda gan kādas ir jūsu kods dara kādā konkrētā kā arī to, ko visas jūsu mainīgie ir uzskaites, piemēram, kādi ir viņu vērtības, šajā konkrētajā brīdī. Un šādā veidā, jūs varat patiešām kas kontrolpunkti jūsu kodu. Jūs varat palaist caur pozīcijai. Un GDB vienkārši ir par Jūs, redzams jums, ko visi jūsu mainīgo ir, ko viņi dara, kas notiek ar kodu. Un tādā veidā, tas ir tik daudz vieglāk, lai redzētu kas notiek, nevis printf-ing vai rakstot uz leju savus paziņojumus. 

Tāpēc mēs darīsim piemēru šo vēlāk. Tātad tas šķiet mazliet abstrakts. Neraizējieties, mēs darīsim piemērus. Un tā būtībā, trīs lielākās, visbiežāk izmanto funkcijas jums būs nepieciešams GDB ir nākamais, Soli pa, un Solis pogām. Es esmu gatavojas dodies tur, faktiski, tieši tagad. 

Tātad jūs varat guys visu redzēt, ka vai man tuvinātu mazliet? Uz muguras, jūs varat redzēt, ka? Ja es tuvinātu? Tikai mazliet? OK, atdzesē. Tur mēs ejam. LABI. 

Tāpēc man ir, šeit, Mani ieviešana mantkārīgs. Un, lai gan daudzi no jums guys rakstīja mantkārīgs in kamēr cilpa form-- ka ir pilnīgi pieņemams veids, kā to izdarīt it-- vēl viens veids, kā to darīt, ir vienkārši sadalīt ar Modulo. Jo tad jums var būt jūsu vērtība un tad ir jūsu atlikušo daļu. Un tad jūs varat vienkārši pievienojiet to visu kopā. Vai loģiku, ko es daru šeit jēgas ikvienam, Pirms mēs sākam? IT kā? Cool. Liels. Tas ir diezgan sexy gabals koda, es teiktu. Tāpat kā es teicu, David, jo lekciju, pēc brītiņa, jūs visi sākat redzēt kodu kā kaut ko, kas ir skaists. Un dažreiz, kad jūs redzat skaista kods, tas ir tik brīnišķīga sajūta. 

Tātad tomēr, kamēr šis kods ir ļoti skaisti, tas nedarbojas pareizi. Tātad, pieņemsim palaist check50 par šo. Pārbaudiet 50 20-- OOP. 2? Vai tas pset2? Jā. Ak, pset1. LABI. Tātad mēs palaist check50. 

Un kā jūs guys var redzēt šeit, tas ja pāris gadījumos. Un daži no jums, jo Protams, kā to savu problēmu kopas, jūs, piemēram, ah, kāpēc nav tā strādā. Kāpēc tas strādā daži vērtības, bet ne citiem? Nu, GDB notiek, lai palīdzētu jums saprast , kāpēc šie dati nebija darba. 

LABI. Tātad, pieņemsim redzēt, kas ir viens no Pārbaudes Es biju nepildīšanu check50 bija ieejas vērtību 0.41. Tātad pareizā atbilde, ka Jums vajadzētu iegūt ir 4. Bet tā vietā, ko es esmu izdrukāšana ir 3-n, kas ir nepareiza. Tātad pieņemsim tikai palaist manuāli, tikai pārliecinieties, ka check50 strādā. Darīsim ./greedy. Hmm, man ir veikt mantkārīgs. Tur mēs ejam. Tagad ./greedy. 

Cik daudz ir parādā? Darīsim 0,41. Un Yep, mēs redzam šeit ka tas izvada 3 kad pareizā atbilde, patiesībā, vajadzētu būt 4. Tātad pieņemsim ieiet GDB un redzēt, kā mēs var iet par nosakot šo problēmu. 

Tātad pirmais solis vienmēr atkļūdošana savu kodu ir noteikt pārtraukumpunkts, vai punkts, kurā Jūs vēlaties datora vai atkļūdotājs lai sāktu meklē. Tātad, ja jums nav īsti zināt, kādas ir jūsu problēma ir, parasti, tipisks lieta, ko mēs gribam darīt, ir noteikt mūsu koncentrācija ir galvenais. Tātad, ja jūs guys var redzēt šo sarkano pogu turpat, Yep, kas bija mani a; koncentrācija par galveno funkciju. Es noklikšķiniet uz tā. 

Un tad es varu iet uz augšu uz manu Debug pogu. Es hit šīs pogas. Ļaujiet man tālinātu, ja es varu. Tur mēs ejam. Tāpēc mums ir, šeit, paneli labajā pusē. Man žēl, puiši uz muguras, jūs nevar īsti redzēt patiešām labi. Bet būtībā, visi šīs tiesības panelis dara ir sekot gan uzsvēra līnija, kas ir rindā kodu ka dators pašlaik darbojas, kā arī visiem saviem mainīgajiem leju šeit. 

Tātad jūs esat ieguvuši centiem, monētas, n, visi deklarēti dažādām lietām šajā brīdī. Neraizējieties, jo mums nav reāli inicializēts tos visus mainīgajiem vēl. Tātad jūsu datorā, jūsu dators ir tikai redzēt, oh, 32767 bija pēdējais lietotais funkcija Šīs atmiņas vietu manā datorā. Un tā tas ir, ja centi šobrīd ir. Bet nē, ka tad, kad jūs palaist kodu, tai jākļūst inicializēts. 

So iesim cauri, līniju ar līnija, kas notiek šeit. LABI. Tātad, šeit ir trīs pogas, ka es tikko paskaidroja. Jums ir spēlēt, vai Run funkciju, poga, jums ir soli pa pogu, un jums ir arī solis uz pogas. Un būtībā, visas trīs viņiem vienkārši iet caur savu kodu un darīt dažādas lietas. 

Tātad parasti, kad jūs atkļūdošana, mēs nevēlamies, lai tikai sasniegtu Atskaņot, jo spēlē būs vienkārši palaist Jūsu kods līdz gada beigām tā. Un tad jums nebūs faktiski zināt, kādas ir jūsu problēma ir, ja jūs noteikti vairāki kontrolpunkti. Ja jūs noteikti vairāki kontrolpunkti, tas vienkārši automātiski palaist no viena pārtraukumpunkts, uz nākamo, uz nākamo. Bet šajā gadījumā mēs esam tikai, ka viens, jo mēs vēlos strādāt mūsu ceļu no augšas uz leju uz leju. Tātad mēs ejam, lai ignorēt šo pogu tagad nolūkā šo programmu. 

Tātad soli pa funkciju tikai soļi nekā katru līniju un stāsta jums to, ko dators dara. Solis uz funkciju iet vērā faktisko funkciju tas ir jūsu koda rindu. Tā, piemēram, piemēram, printf (), kas ir funkcija, vai ne? Ja es gribēju fiziski solis uz printf () funkciju, Es tiešām iedziļināties gabals kodu, kur printf () bija rakstīts un redzēt kas notiek tur. 

Bet parasti, mēs pieņemam, ka kods, kas mums dos jums darbojas. Mēs pieņemam, ka printf () strādā. Mēs pieņemam, ka GetInt () strādā. Tāpēc nav nepieciešams soli šīm funkcijām. Bet, ja tur ir funkcijas ka jums rakstīt pats ka jūs vēlaties, lai pārbaudītu to, kas notiek, Jūs vēlaties, lai soli par šo funkciju. 

Tāpēc tagad mēs esam tikai gatavojas soli pa šo gabalu kodu. Tātad, pieņemsim redzēt. Ak, print, "Ak hai, kā daudz pārmaiņas parādā? " Mums nav vienalga. Mēs zinām, ka strādā, tāpēc mēs soli pār to. 

Tātad, n, kas ir mūsu pludiņš kas mēs esam initialized-- vai declared-- augšā, mēs esam tagad vienāds, ka, lai GetFloat (). Tātad pieņemsim soli pār to. Un mēs redzam pie bottom šeit, programma ir pamudinot mani ievadi vērtība. So let ieguldījuma vērtību mēs gribam pārbaudīt šeit, kas ir 0.41. Liels. 

Tāpēc tagad N- do you guys redzēt šeit, pie bottom-- tas ir stored-- jo mēs vēl nav noapaļotas, tas ir glabājas šajā līdzīgu milzu pludiņš, kas ir 0,4099999996, kas ir pietiekami tuvu, lai mūsu mērķiem, tieši tagad, lai 0.41. Un tad mēs redzēsim vēlāk, kā mēs turpināt pastiprināšanu pār programmu, pēc šeit, n ir kļuvusi noapaļoti un centiem kļuvis 41. Liels. Tātad mēs zinām, ka mūsu noapaļošanas strādā. Mēs zinām, ka mums ir pareizs skaits centiem, tāpēc mēs zinām, ka tas ir nav īsti problēma. 

Tātad mēs turpinām pastiprināšanu par šajā programmā. Mēs ejam šeit. Un tā pēc šīs līnijas kodu, mēs vajadzētu zināt, cik daudz ceturtdaļas mums ir. Mēs soli pa. Un jūs redzat mēs, patiesībā, ir viens ceturtdaļa jo mēs esam atņemti 25 no mūsu sākotnējās vērtības 41. Un mums ir 16 aizbrauca uz mūsu centiem. 

Vai visi saprotam, cik programma ir pastiprināšanu caur un kāpēc centi ir kļuvis 16 un kāpēc tagad, monētas ir kļuvis 1? Vai visi šādu loģiku? Cool. Tā kā šo punktu, tad Programmas darba, vai ne? Mēs zinām, tas dara tieši tā ko mēs gribam to. Un mēs neesam reāli ir izdrukāt, ak, ko ir centi šajā brīdī, kas ir monētas šajā brīdī. 

Mēs turpinām iet caur programmu. Pārkāpt pāri. Cool. Mēs ejam pa dimes. Liels. Mēs redzam, ka tas ir pieņemts off $ 0,10 par dimetānnaftalīns. Un tagad mums ir divas monētas. Tas ir pareizi. 

Mēs ejam pār pennies un mēs redzam ka mēs esam ieguvuši palikuši pāri centiem. Hmm, tas ir dīvaini. Šurp pie programmas, man vajadzēja to ir jāatņem savu pennies. Varbūt es vienkārši nebija dara, ka līnija tiesības. Un diemžēl, jūs varat redzēt šeit, jo mēs zinām, ka mēs pastiprināšanu caur un līnijām 32 33, tas ir, ja mūsu programma nepareizi bija mainīgie darboties. Tātad, mēs varam skatīties un redzēt, ak, Es esmu atņemot centiem šeit, bet es neesmu faktiski pievienojot manu monētu vērtību. Es esmu pievienojot centiem. Un es negribu, lai pievienotu centiem, es gribu pievienot monētām. Tātad, ja mēs mainīt, ka uz monētām, mēs esam ieguvuši darba programmu. Es varu palaist check50. Jūs varat vienkārši iziet ārā no GDB tiesības šeit un pēc tam palaist check50 vēlreiz. Es varētu vienkārši darīt. Man ir veikt mantkārīgs. 0.41. Un šeit, tas ir apdruka out pareizo atbildi. 

Tātad, kā jūs guys var redzēt, GDB ir ļoti spēcīgs instruments , kad mums ir tik daudz kodu notiek, un tik daudz mainīgo ka tas ir grūti par mums, jo cilvēka, lai sekotu. Dators, kas GDB atkļūdotājs, ir spēja sekot visam. Es zinu, kas Visionaire, jūs puiši, iespējams, varētu būt hit dažas segmentācijas kļūdas jo tu darbojās no robežas jūsu masīvs. Piemērā par ķeizaru, kas ir tieši tas, ko es esmu ieviesta šeit. 

Tāpēc es aizmirsu, lai pārbaudītu kas notiktu, ja es nebija divas komandrindas argumentus. Man vienkārši nav laidis šajā pārbaudē. Un tāpēc, ja es palaist Debug-- es noteikti mans robežvērtība, lai turpat. Es palaist Debug. 

LABI. Jā. Tātad faktiski, GDB bija paredzēts to ir teicis man tur bija segmentācija vaina tur. Es nezinu, kas notiek labi tur, bet, kad es ilga to, tas strādāja. Palaižot rindas koda cauri un GDB varētu vienkārši pēkšņi atmest par jums, iet uz augšu un meklēt to, ko sarkanā kļūda. Tas jums pateiks, hey, jūs bija segmentāciju vaina, kas nozīmē, ka jūs mēģinājis piekļūt telpa masīva ka nepastāvēja. Jā. 

Tātad, nākamajā problēmu Uzlikt šo nedēļu, jums puiši iespējams, būs daudz mainīgie peldošs apkārt. Jūs neesat gatavojas, lai pārliecinātos, ko tie visi nozīmē kādā noteiktā brīdī. Tātad GDB būs tiešām palīdzēs jums norādītas , ko viņi visi līdzinoties un to var redzēt, ka vizuāli. Vai kāds sajaukt par to, kā jebkuru, kas strādā? Cool. Viss kārtībā. Tātad, pēc tam, mēs esam gatavojas nirt tiesības vērā ir četras dažādas veidu veidu šajā nedēļā. Cik daudzi no jums, pirmkārt no visiem, pirms mēs sākam, esmu izlasījis visu spec par pset3? LABI. Es esmu lepns par jums puiši. Tas ir tāpat kā pusei no klases, kurā ir ievērojami vairāk nekā pēdējo reizi. 

Tātad tas ir lieliski, jo, kad mēs runājam par saturu in lecture-- vai žēl, in section-- man patīk saistīt daudz kas atpakaļ uz to, ko PSET ir un kā jūs vēlaties īsteno ka jūsu PSET. Tātad, ja jūs nākt ar lasīt spec, tas būs būt daudz vieglāk, lai jūs varētu saprast ko es runāju par to, kad es saku, oh hey, tas varētu būt patiešām laba vieta, lai īstenotu šāda veida. Tātad tiem no jums, kas ir izlasījis spec zina, ka, kā daļu no jūsu PSET, jūs nāksies uzrakstīt veida veida. Tātad tas var būt ļoti noderīga par šodien daudzi no jums. 

Tātad mēs sāktu ar, būtībā, visvienkāršākā veids no veida, izvēle kārtošanas. Tipisks algoritms kā mēs gribētu iet par šo is-- David gāja cauri šiem visiem lekcija, tāpēc es ņemšu ātri pārvietoties pa here-- būtībā, jūs ir masīvs vērtībām. Un tad jūs atrast mazākais nešķiroti vērtība un jūs mijmaiņas šo vērtību ar pirmais nešķiroti vērtība. Un tad jūs vienkārši turēt atkārtojot ar pārējo savu sarakstu. 

Un šeit ir vizuāls paskaidrojums par to, kā tas varētu strādāt. Tā, piemēram, ja mēs, lai sāktu ar masīvu pieciem elementiem, indeksa 0 līdz 4, ar 3, 5, 2, 6, un 4 vērtības ievietots array-- tāpēc tieši tagad, mēs esam tikai gatavojas pieņemt ka viņi visi nešķiroti jo mēs neesam pārbaudītas citādi. 

Tātad, kā atlases veida būtu darbs ir, ka tas būtu pirmais palaist cauri kopumā no nešķirotu masīva. Tas izlasīt mazāko vērtību. Šajā gadījumā, 3, pa labi Tagad, ir mazākais. Tas izpaužas 5. Nē, 5 ir ne lielāks than-- vai sorry, ne mazāk than-- 3. Tātad minimālā vērtība ir vēl 3. Un tad jūs saņemsiet 2. Dators redz, ak, 2 ir mazāk nekā 3. Tagad 2 jābūt minimālā vērtība. Un tā 2 Mijmaiņu ar šo pirmo vērtību. 

Tātad, pēc vienas piespēles, mēs tiešām redzētu ka 2 un 3 tiek pārnestas. Un mēs esam tikai gatavojas turpināt darīt Tas atkal ar pārējo masīva. Tātad mēs ejam, lai vienkārši palaist caur pēdējie četri indeksi masīva. Mēs redzam, ka 3 ir nākamais minimālā vērtība. Tātad mēs ejam, lai mijmaiņas kas ar 4. Un tad mēs esam tikai gatavojas glabāt braucot cauri līdz, galu galā, jūs nokļūt šķiroto masīvu, kurā 2, 3, 4, 5, un 6 tiek visi sakārtoti. Vai visi saprast loģiku par to, kā atlases veida darbojas? 

Jums vienkārši ir kaut kāda minimālo vērtību. Jūs esat sekotu, kas tas ir. Un, kad jūs atradīsiet to, jūs mijmaiņas to ar pirmo vērtību array-- vai, nav pirmais value-- nākamais vērtību masīvā. Cool. 

Tātad, kā jūs puiši veida redzēja no īsu ieskatu, mēs spēsim pseudocode šo out. Tātad, ja jūs guys aizmugurē vēlaties veido grupu, visi pie galda var veidot mazliet partneris, es eju lai dotu jums puiši, piemēram, trīs minūtes tikai runāt caur loģika, angļu, par to, kā mēs varētu īstenot pseudocode uzrakstīt atlases veida. Un tur ir konfektes. Lūdzu, nāciet un saņemt konfektes. Ja tu esi atpakaļ, un jūs vēlaties konfektes, es varētu mest Candy pie jums. Patiesībā, do you-- atdzist. Ak, piedod. LABI. 

Tātad, ja mēs vēlētos, lai klases, rakstīt pseudocode par to, kā viens varētu tuvoties šī problēma, vienkārši justies brīvi. Es ņemšu tikai iet apkārt un, lai, jautājiet grupas nākamajam līniju Ko mums vajadzētu darīt. Tātad, ja jūs puiši vēlas uzsākt off, kas ir pirmā lieta, ko darīt, ja jūs mēģināt īstenot veidu, kā atrisināt šo programmu selektīvi kārtotu sarakstu? Pieņemsim tikai pieņemt, mēs ir masīvs, labi? 

Mērķauditorija: Jūs vēlaties, lai radītu dažus kārtot [dzirdams], ka tu esi braucot cauri jūsu visai masīvs. 

ANDI PENG: Right. Tātad jūs esat gatavojas vēlaties atkārtot ar katru telpu, labi? Tātad, lieliski. Ja jūs puiši vēlas dot man Nākamais line-- yeah, uz muguras. 

Mērķauditorija: Pārbaudiet tos visi par vismazāko. 

ANDI PENG: Tur mēs ejam. Tāpēc mēs gribam iet cauri un pārbaudīt, lai redzētu minimālā vērtība ir, vai ne? Es esmu gatavojas saīsināt, ka, lai "min." Ko jūs guys vēlaties darīt pēc esat atradis minimālo vērtību? 

Mērķauditorija: [dzirdams] ANDI PENG: Tātad jūs gatavojas vēlaties ieslēdziet to ar pirmo šī masīva, labi? Tas ir sākums, es esmu gatavojas teikt. Viss kārtībā. Tāpēc tagad, ka jūs esat aizstāja pirmais viens, ko jūs vēlaties darīt pēc tam? Tāpēc tagad mēs zinām, ka šeit tas viens jābūt vismazākā vērtība, vai ne? Tad jums ir papildu atpūta masīva, kas ir nešķiroti. Tātad, ko jūs vēlaties darīt šeit, ja jūs puiši vēlas dot man nākamo līniju? Mērķauditorija: Tātad jūs vēlaties atkārtot visu atlikušo masīva. ANDI PENG: Jā. Un tā, ko tas atkārtojot cauri veida nozīmē mums, iespējams, ir nepieciešama? Kāda veida of-- 

Mērķauditorija: Ak, papildu mainīgo? ANDI PENG: Iespējams Vēl viens cilpa, vai ne? Tāpēc mēs, iespējams, gatavojas vēlaties atkārtot through-- lieliski. Un tad jūs gatavojas doties atpakaļ un iespējams pārbaudīt minimums atkal, labi? Un jūs gatavojas glabāt atkārtojot tas, ka cilpas tikai iet lai saglabātu darboties, vai ne? 

Tātad, kā jūs guys var redzēt, mēs vienkārši ir vispārējs pseudocode par to, kā mēs vēlamies, lai šī programma izskatīties. Tas atkārtot šeit, ko mēs parasti nepieciešams uzrakstīt mūsu kodu ja mēs vēlamies atkārtot, izmantojot masīvs, kāda modeļa struktūra? Es domāju, ka Christabel jau teicu pirms tam. 

Mērķauditorija: A cilpa. 

ANDI PENG: A cilpa? Tieši tā. Tātad tas ir iespējams būs cilpas. Kas ir pārbaude šeit gatavojas nozīmēt? Parasti, ja jūs vēlaties, lai pārbaudītu ja kaut kas ir kaut else-- 

Mērķauditorija: Ja. 

ANDI PENG: An ja, vai ne? Un tad swap šeit, mēs iet pāri vēlāk, jo Dāvida pārdzīvoja, ka lekciju, kā arī. Un tad otrā atkārtot implies-- 

Mērķauditorija: Vēl viens cilpa. 

ANDI PENG: --another cilpas, precīzi. Tātad, ja mēs meklējam šajā pareizi, mēs var redzēt, ka mēs, iespējams, būs nepieciešama ligzdotu cilpas ar nosacītu paziņojumu tur un tad faktiskā gabals kodu, kas ir gatavojas apmainīt vērtības. Tāpēc es esmu tikai parasti rakstīts pseudocode kodu šeit. Un tad mēs tiešām dodas fiziski, kā klasi, izmēģināt šo šodien īstenot. Iesim atpakaļ uz šo IDE. 

Uh-oh. Kāpēc ir tā, ka not-- tur tas ir. LABI. Atvainojiet, ļaujiet man mēģināt, lai tuvinātu mazliet vairāk. Tur mēs ejam. Viss, ko es daru šeit es esmu izveidojis programma, ko sauc "atlase / sort.c." Esmu izveidojis masīvs deviņu vērtībām, 4, 8, 2, 1, 6, 9, 7, 5, 3. Šobrīd, kā jūs varat Redzi, tie ir Nekārtots. n būs skaits, kas stāsta jums summu vērtību jums ir jūsu masīvs. Šajā gadījumā, mums ir deviņas vērtības. Un es esmu tikko ieguvuši cilpa šeit kas izdrukā uz nešķirotu masīvs. 

Un beigās, es esmu arī ieguva par cilpa, kas vienkārši izdrukā to no jauna. Tātad teorētiski, ja šīs programmas darbojas pareizi, beigās, Jums vajadzētu redzēt iespiesti cilpu , kurā 1, 2, 3, 4, 5, 6, 7, 8, 9 ir visu pareizi, lai. 

Tātad mēs esam ieguvuši mūsu pseudocode šeit. Vai kāds vēlas kuri paredzēti, es esmu tikai gatavojas iet lūgt volunteers-- man pateikt, tieši to, ko rakstīt, ja Mēs vēlamies, lai, pirmkārt, vienkārši atkārtot caur sākumā šo masīva? Kas ir līnija koda es esmu iespējams, būs nepieciešams šeit? 

Mērķauditorija: [dzirdams] 

ANDI PENG: Jā, jūtos bezmaksas kuri paredzēti, piedodiet, jūs nav stāvēt up-- justies brīvi paaugstināt savu balsi mazliet. 

Mērķauditorija: Par int i vienāds 0-- 

ANDI PENG: Jā, labi. 

AUDITORIJA: i ir mazāks nekā masīva garumu. 

ANDI PENG: Tātad paturiet prātā šeit, jo mēs nav funkciju, kas stāsta mums garums masīva, mums jau ir vērtība, kas saglabā to. Tiesības? Vēl viena lieta, kas jāpatur in mind-- masīvā Deviņu vērtībām, kādas ir indeksi? Pieņemsim tikai teikt masīvs bija 0: 3. Jūs redzēsiet, ka pēdējā indekss ir faktiski 3. Tas nav 4, lai gan tur ir četras vērtības masīvā. 

Tātad šeit, mums ir jābūt ļoti uzmanīgiem par to, kas mūsu stāvoklī garumu būs. 

Mērķauditorija: Vai tas ir n mīnus 1? ANDI PENG: Tas būs n mīnus 1, tieši tā. Vai, ka jēga, kāpēc tas ir n mīnus 1, visi? Tas ir tāpēc, ka masīvi ir nulle indeksētas. Viņi sāk ar 0 un palaist līdz n mīnus 1. Jā, tas ir mazliet viltīgs. LABI. Un tad-- Mērķauditorija: Isnt'1 ka jau rūpēsies, lai gan, ko tikai ne sakot "ir mazāks vai vienāds ar "un vienkārši pasakot" mazāk nekā? " 

ANDI PENG: Tas ir tiešām labs jautājums. Tātad, jā. Bet arī, tā, ka mēs esam Īstenojot pārbaudes tiesības, Jums ir nepieciešams, lai salīdzinātu divas vērtības. Tātad jūs tiešām vēlaties atstāt "uz" tukšs. Jo, ja jūs salīdzināt Tas viens, jūs nebrauksim ir kaut kas pēc tam salīdzināt ar, vai ne? Jā. Tāpēc es ++. Pieņemsim pievienot mūsu iekavās. Whoops. Liels. Tāpēc mums ir sākums Mūsu ārējā kontūra. Tāpēc tagad mēs, iespējams, vēlas izveidot mainīgo, lai uzturētu dziesmu par mazāko vērtību, vai ne? Vai kāds vēlas dot man rindā kodu, kas varētu darīt? Kas mums ir nepieciešams, ja mēs ejam vēlas saglabāt kaut ko? 

Tiesības. Varbūt labāks nosaukums, kas būtu be-- "temp" pilnīgi works-- varbūt vairāk trāpīgi nosaukts būtu, ja mēs gribam mazāko value-- 

Mērķauditorija: Min. ANDI PENG: min, tur mēs ejam. min būtu labi. Un tā šeit, ko mēs vēlas, lai sāktu to? Tas ir mazliet viltīgs. Jo tieši tagad pie sākumā šo masīva, Jūs neesat paskatījās kaut ko, vai ne? Tātad, ko, automātiski, ja mēs esam tikai uz i ir vienāds ar 0, ko mēs gribam, lai sāktu mūsu pirmais minimālā vērtība? Mērķauditorija: i. ANDI PENG: i, tieši tā. Christabel, kāpēc mēs gribam inicializēt to i? 

Mērķauditorija: Tā, labi, mēs sākam ar 0. Tāpēc, ka mums nav ko salīdzināt to, minimālā galu galā ir 0. 

ANDI PENG: Tieši tā. Tātad viņa ir tieši labi. Jo mums ir faktiski nav paskatījās kaut ko vēl, mēs nezinām, ko mūsu minimālā vērtība ir. Mēs vēlamies, lai tikai sāktu to i, kas pašlaik ir tepat. Un kā mēs turpinām pārvietot pa šo masīvu, mēs redzēsim, ka ar katru papildu caurlaide, i pieaugumu. Un tā šajā brīdī, i, iespējams, gatavojas vēlas būt minimālā, jo tas būs būt jebkas ir sākums nešķirotu masīva. Cool. 

Tāpēc tagad mēs vēlamies, lai pievienotu A cilpu šeit tas ir gatavojas atkārtot cauri nešķiroti, vai pārējo šī masīva. Vai kāds vēlas sniegt man rindā kodu, kas varētu darīt? Hint-- Ko mums vajag noteikti šeit? Kas notiek, lai iet šajā cilpas? Jā. Mērķauditorija: Tātad mēs gribētu vēlamies ir atšķirīgs skaitli, jo mēs esam darbojas ar pārējo masīva nevis i, tāpēc varbūt j. 

ANDI PENG: Jā, j skan labi man. Vienāds? 

Mērķauditorija: Tātad būtu i plus 1, jo jūs, sākot ar nākamo vērtību. Un pēc tam uz end-- tā atkal, j ir mazāk nekā n mīnus 1, un pēc tam j ++. ANDI PENG: Great. 

Un tad šeit, mēs esam gatavojas vēlaties pārbaudīt, lai redzētu, vai mūsu nosacījums ir izpildīts, labi? Tāpēc, ka jūs vēlaties, lai mainītu minimālo vērtību ja tas ir tiešām mazāks nekā tas, ko jūs salīdzināt to ar, vai ne? Tātad, ko mēs gatavojamies vēlamies šeit? Pārbaudiet, lai redzētu. Kāda no paziņojuma veids mēs droši vien ti vēlas izmantot, ja mēs vēlaties pārbaudīt kaut ko? 

Mērķauditorija: ja paziņojums. 

ANDI PENG: An ja paziņojums. Tātad if-- un kādi būs nosacījums, ka mēs gribam iekšā Mūsu ja paziņojums? 

Mērķauditorija: Ja vērtība j ir mazāka nekā vērtība, i-- 

ANDI PENG: Tieši tā. Tātad if-- tāpēc šis masīvs tiek saukta par "masīvs." Liels. Tātad, ja array-- Kas tas bija? Pasaki to vēlreiz. 

AUDITORIJA: Ja masīvs-j ir mazāks nekā masīvs-i, tad mēs varētu mainīt min. Tātad min būtu j. 

ANDI PENG: tas, kas padara jēga? LABI. Un tagad uz leju šeit, mēs faktiski vēlas, lai īstenotu mijmaiņas, vai ne? Tātad atgādināt, lekciju, ka Dāvids, kad viņš mēģina apmainīt the-- Kas bija it-- apelsīnu sula un milk-- 

Mērķauditorija: Tas bija bruto. 

ANDI PENG: Jā, tas bija sava veida bruto. Bet tas bija diezgan labs jēdziens demonstrējot laiku. Tāpēc domāju, ka par jūsu vērtībām šeit. Tev masīvs min, masīvs i, vai kāds mēs cenšamies apmainīt šeit. Un jūs, iespējams, nevar ieliet tos viens otru tajā pašā laikā, pa labi? Tātad, ko mēs gatavojamies nepieciešams, lai izveidotu šeit lai mijmaiņas vērtības pareizi? 

Mērķauditorija: pagaidu mainīgs. 

ANDI PENG: pagaidu mainīgs. Tātad, pieņemsim darīt int temp. Skat, tas būtu labāk laiks kuri paredzēti, paga, kāda bija, ka? LABI. Tātad tas būtu bijis labāks laiks nosaukt mainīgais "temp." Tātad, pieņemsim darīt int temp. Ko mēs gatavojamies noteikts temp vienāds ar šeit? Mērķauditorija: Min? ANDI PENG: Tas ir mazliet viltīgs. Tas tiešām nav svarīgi beigās. Tas nav svarīgi, ko Lai jūs izvēlaties mijmaiņas tik ilgi, cik jūs gūstat pārliecināts, ka jūs esat sekotu ko jūs pārnešana. 

Mērķauditorija: Tas varētu būt masīvs-i. 

ANDI PENG: Jā, pieņemsim darīt masīva-i. Un tad kāds ir nākamais rindā kodu mēs vēlamies, lai būtu šeit? Mērķauditorija: masīvs-i ir vienāds ar masīvu-J. ANDI PENG: Un visbeidzot? Mērķauditorija: masīvs-j vienāds masīvs-i. Mērķauditorija: Vai masīvs-j Vienāds masīvs-temp-- vai, temp. 

ANDI PENG: OK. Tātad pieņemsim palaist šo un redzēt ja tas notiek uz darbu. Ja ir, kas notiek? Ak, tas ir problēma. Skat, 40. līniju, mēs esam mēģina izmantot masīvu-J? Bet kur j pastāv tikai? 

Mērķauditorija: In uz cilpas. ANDI PENG: Right. Tātad, ko mēs gatavojamies jādara? 

Mērķauditorija: Noteikt to ārpus the-- Mērķauditorija: Jā, es domāju, jums ir izmantot citu, ja apgalvojums, vai ne? Tātad, piemēram, ja minimum-- labi, ļaujiet man domāt. 

ANDI Peng: Puiši, mēģiniet paskatīties Let 's skat, kāda ir kaut ko mēs varam darīt šeit? 

Mērķauditorija: OK. Tātad, ja minimālais nav vienāds j-- tādēļ, ja minimālais joprojām i-- tad mēs nebūtu swap. 

ANDI PENG: Vai, ka vienāda i? Ko jūs vēlaties pateikt šeit? 

Mērķauditorija: Vai yeah, ja Minimālā nav vienāds i, jā. ANDI PENG: OK. Nu, kas atrisina, veida, mūsu problēmas. Bet tas joprojām neatrisina problēma par to, kas notiek, ja j-- kopš j neeksistē ārpus tā, ko tu mēs gribam darīt ar to? Pieteikt to ārpus? Mēģināsim rādīt šo. Uh-oh. Mūsu kārtot nedarbojas. 

Kā jūs varat redzēt, mūsu sākotnējo masīvs bija šīs vērtības. Un pēc tam tā vajadzētu būt ir 1, 2, 3, 4, 5, 6, 7, 8, 9. Tas nestrādā. Ahh. Ko mēs darām? Mērķauditorija: Debug. ANDI PENG: Nu labi, mēs varam mēģināt to. Mēs varam atkļūdot. Zoom out mazliet. Pieņemsim, kas mūsu koncentrācija. Iesim like-- OK. 

Tāpēc, ka mēs jau zinām, ka Šīs līnijas, 15 līdz 22, ir working-- jo viss, ko es daru, ir tikai atkārtojot cauri un printing-- Es varu iet uz priekšu un izlaist to. Sāksim līniju 25. OOP, ļaujiet man atbrīvoties no tā. 

Mērķauditorija: Tātad robežvērtība s kur atkļūdošanas sākas? ANDI PENG: vai aptur. Mērķauditorija: vai aptur. ANDI PENG: Jā. Jūs varat iestatīt vairākus kontrolpunkti un tā var vienkārši pāriet no viena uz otru. Bet šajā gadījumā mēs nezinām kur kļūda notiek. Tātad mēs vienkārši vēlamies, lai sākt no augšas uz leju. Yep. LABI. 

Tātad šī līnija šeit, mēs varam soli. Jūs varat redzēt šeit lejā, mēs esam ieguvuši masīvu. Tās ir vērtības, kas ir masīva. Vai redzat, ka, cik indekss 0, tas atbilst value-- oh, Es esmu gatavojas izmēģināt, lai tuvinātu. Atvainojiet, tas ir tiešām grūti līdz see-- pie masīva indekss 0, mums ir vērtība 4 un pēc tam tā tālāk, un tā tālāk. Mums ir mūsu vietējās mainīgie. Tieši tagad i ir vienāds ar 0, ko mēs gribam, lai to. 

Un tāpēc pieņemsim saglabātu pastiprināšanu caur. Mūsu minimālais ir vienāds ar 0, ko mēs arī vēlamies, lai to. Un tad mēs ieejam mūsu sekundē cilpa, ja masīvs-j ir mazāks nekā masīvs-i, kas tā nebija. Tātad jūs redzēt, kā ka izlaidis vairāk nekā, ka? 

Mērķauditorija: Tātad ja ja minimums, visi that-- nevajadzētu ka būt iekšā pirmā cilpa? ANDI PENG: Nē, jo jūs joprojām vēlaties, lai pārbaudītu. Jūs vēlaties darīt salīdzinājumu ik laiks, pat pēc tam, kad jūs darbināt caur to. Jums nav vienkārši vēlaties to darīt uz pirmā transmisiju. Jūs vēlaties darīt to ar katram papildu pass atkal. Tātad jūs vēlaties, lai pārbaudītu Jūsu stāvoklis iekšā. Tātad mēs esam tikai gatavojas skriet cauri šeit. Es došu jums puiši mājienu. Tas ir saistīts ar to, ka tad, kad jūs pārbaudīt savu nosacīta, Jūs neesat pārbaude par pareizu indekss. Tātad tagad jūs pārbaudot masīvs indekss j ir mazāks nekā masīva indekss i. Bet ko jūs darāt augšā sākums cilpa? Vai tu nosakot j ir vienāds ar i? 

Jā, tāpēc mēs faktiski var izietu atkļūdotājs šeit. Tātad, pieņemsim to apskatīt mūsu pseudocode. For-- mēs ejam sākas i ir vienāds ar 0. Mēs ejam, lai iet līdz n mīnus 1. Let 's pārbaudīt, tomēr mums ir šādas tiesības? Yep, tas bija taisnība. 

Tātad iekšā šeit, mēs esam notiek, lai radītu minimālo vērtību un noteikt, ka vienāds ar i. Vai mēs to darām? Yep, to izdarīja. Tagad mūsu iekšējās cilpas, mēs esam darīsim j vienāds i n 1 mīnus. Vai mēs to darām? Patiesi, mēs to izdarīja. 

Tātad tomēr, ko mēs salīdzinot šeit? 

Mērķauditorija: j plus 1. ANDI PENG: Tieši tā. Un tad jūs gatavojas vēlaties iestatīt Jūsu minimums ir vienāds ar j plus 1, kā arī. Tāpēc es devos cauri, ka tiešām ātri. Vai jūs guys saprast kāpēc tas ir j plus 1? LABI. 

Tātad jūsu masīvs, it savu pirmo iet caur, Jūsu cilpas, lai int i ir vienāds ar 0, pieņemsim tikai pieņemu, tas vēl nav mainīta. Mums ir masīvs, pilnīgi, tikai četras nešķirotas elementi, vai ne? Tāpēc mēs vēlamies, lai sāktu i vienāda ar 0. Un es gatavojas tikai palaist caur šo cilpu. Un tā pirmajā caurlaide, mēs ejam inicializēt mainīgo sauc par "min" ka arī vienāds i, jo mēs nav minimālo vērtību. Tātad tas ir pašlaik ir vienāds ar 0, kā arī. Un tad mēs ejam, lai iet cauri. Un mēs gribam atkārtot vēlreiz. Tagad, ka mēs esam atraduši to, ko mūsu minimālais ir, mēs vēlamies atkārtot, izmantojot vēlreiz, lai redzētu, vai tas ir, salīdzinot, vai ne? Tātad j, šeit, notiek uz vienāda i, kas ir 0. Un tad, ja masīvs j plus i, kas ir viens, kas ir nākamais vairāk, jo mazāk nekā to, ko jūsu pašreizējo minimumam vērtība ir, jūs vēlaties apmainīt. 

Tātad pieņemsim tikai teikt, ka mēs esam ieguva, piemēram, 2, 5, 1, 8. Tieši tagad, i ir vienāds ar 0 un j ir vienāds ar 0. Un tas ir mūsu minimālā vērtība. Ja masīvu-j plus i-- tādēļ, ja viens tas ir pēc tam, kad viens mēs esam meklē ir lielāks nekā tas, pirms tā, tas notiek, lai kļūtu par minimālo. 

Tātad, šeit mēs redzam, ka 5 ir ne mazāks par to. Tātad, tas notiek, lai nav 5. Mēs redzam, ka 1 ir mazāks par 2, vai ne? Tāpēc tagad mēs zinām, ka mūsu minimums ir būs indekss ir 0, 1, 2. Yeah? Un tad, kad jums uz leju šeit, Jūs varat mijmaiņas pareizās vērtības. 

Tātad, ja jūs guys bija tikai, kam j pirms, jums nav apskatot vienu pēc tā. Jūs meklējāt at pati vērtība, kas Tāpēc tas vienkārši bija nedara neko. Vai tas ir jēga, lai visiem, kāpēc mums vajadzēja, ka plus 1 tur? LABI. Tagad pieņemsim tikai palaist caur to izdarīt pārliecināts pārējā kods ir pareizs. Kāpēc ir tā, ka notiek? Ah, tas ir min tieši šeit. Mēs bijām salīdzinot nepareizu vērtību. Ak, nē. 

Ak jā, noteikti šeit mēs bijām pārnešana nepareizas vērtības, kā arī. Tāpēc, ka mēs meklējām pie i un j. Tie ir tie, mums bija pārbaudes. Mēs tiešām vēlamies, lai mijmaiņas minimums, pašreizējais minimālais, ar kāda viena ārā ir. Un kā jūs guys var redzēt uz leju šeit, mums ir sakārtoti masīvs. Tas vienkārši bija jādara ar fakts, ka tad, kad mēs pārbaudot vērtībām mēs salīdzināšanas, mēs nebijām meklē pareizos vērtībām. Mēs meklējām tajā pašā vienā šeit, faktiski nav pārnešana to. Jums ir jāskatās uz vienu nākamo uz to, un tad jūs varat mijmaiņas. Tātad tas, kas bija sava veida pirms bugging mūsu kodu. Un ko es darīju šeit ir viss atkļūdotājs varēja darīt, lai jūs Es vienkārši darīju to uz kuģa, jo tas ir vieglāk redzēt, nevis mēģināt lai tuvinātu atkļūdotājs. Vai tas ir jēga, lai visiem? Cool. 

Viss kārtībā. Mēs varam pāriet uz runāt par asimptotiskās notācija, kas ir tikai iedomātā veids, kā sakot runtimes Visu šo veidu. Tāpēc es zinu, Dāvidu, lekciju, pieskārās runtimes. Un viņš gāja cauri visai formulu par to, kā aprēķināt runtimes. Neraizējieties par to. Ja jūs patiešām ziņkārīgs par to, kā tas darbojas, justies brīvi runāt ar mani pēc iedaļas. Mēs varam iet cauri formulas kopā. Bet viss, kas jums puiši ir patiešām zina, ir tas, ka n brusas vairāk nekā 2 ir tas pats, kas n brusas. Jo lielākā numuru, eksponents, aug visvairāk. Un tā mūsu vajadzībām, viss, kas mums rūp ir tas, ka milzu skaits, kas ir pieaug. 

Tātad, kas ir labākais gadījums runtime atlases veida? Ja jūs nāksies atkārtot, izmantojot sarakstu un tad atkārtot, izmantojot pārējā šo sarakstu, cik reizes ir jūs gatavojas, iespējams, sliktākajā case-- iekļaušanu labākajā gadījumā, sorry-- palaist cauri? Varbūt labāk jautājums ir jautāt, kāda ir sliktākajā gadījumā runtime atlases veida. Mērķauditorija: n brusas. ANDI PENG: Tas n brusas, pa labi. Tik viegls veids, kā domāt par tas ir kā, jebkurā laikā jums ir divas ligzdotas uz cilpas, tas būs n brusas. Jo ne tikai jūs braucot cauri vēlreiz, Jums jādodas atpakaļ ap un palaist caur to atkal iekšā katrai vērtībai. Tātad šajā gadījumā, jūs darbojas n reizes n brusas, kas is-- sorry, n reizes n, kas ir vienāds ar n brusas. 

Un veida ir arī nedaudz unikāls tādā ziņā, ka tas nav svarīgi, ja tie vērtības ir jau kārtībā. Tas joprojām turpinās, lai palaistu cauri anyways. Let tikai teikt, tas bija 1, 2, 3, 4. Neatkarīgi no tā, vai tas bija rīkojums, tas joprojām būtu skrēja cauri un joprojām pārbauda minimālo vērtību. Tas būtu padarījuši pats pārbaužu skaits katru reizi, pat ja tā faktiski nav nekam pieskarties. 

Tātad šādā gadījumā, labākais un sliktākais runtimes ir faktiski līdzvērtīgi. Tātad sagaidāmais runtime atlases veida, ko mēs iecelt ar simbolu no teta, teta, šajā gadījumā, būtu arī n brusas. Visi trīs šie būtu n brusas. Vai ikvienam skaidrs, kāpēc Runtime ir n kvadrātā? 

Viss kārtībā. Tāpēc es esmu tikai gatavojas ātri palaist ar pārējo veidu. Par algoritms burbulis sort-- atcerēties, šī bija pirmā Dāvids piegāja lekciju. Būtībā, jums soli caur visu sarakstu un jūs swap-- jūs tikko salīdzināt divu laikā. Un, ja kāds ir lielāks, par tevi tikai mijmaiņas tiem. Tātad, ja tie ir lielāki, jūs mijmaiņas. Man amatpersona tieši šeit. 

Tātad pieņemsim tikai teikt, jums bija 8, 6, 4, 2. Tu gribētu salīdzināt 8 un 6. Jūs nepieciešams, lai mijmaiņas tiem. Tu gribētu salīdzināt 8 un 4. Jūs nepieciešams, lai mijmaiņas tiem. Ja jums ir swap 8 un Vai 2, mainās arī tās. Tātad tādā ziņā, jūs varat redzēt, izspēlēta ilgā laika periodā, kā vērtības veida burbulis gali, tāpēc mēs to saucam burbulis šķirot. 

Mēs vienkārši palaist cauri atkal mūsu otrais caurlaide, un mūsu trešās caurlaide, un mūsu ceturtais caurlaide. Būtībā, burbulis šķirot vienkārši iet kamēr jums nav nekādas vairāk mijmaiņas darījumus. Tātad šajā ziņā, tas ir tikai vispārējais pseudocode par to. Neraizējieties, tie visi būs tiešsaistē. Mums nav faktiski iet pār to. 

Mēs tikko inicializēt skaitītājs mainīgais, kas sākas ar 0. Un mēs atkārtot cauri visam blokam. Un, ja kāds vērtība is-- ja tas vērtība ir lielāka nekā vērtība, jūs gatavojas, lai mijmaiņas tiem. Un tad tu esi vienkārši gatavojas, lai saglabātu turpinās. Un jūs gatavojas rēķināties. Un jūs tikai gatavojas, lai saglabātu darot šis kamēr skaitītājs ir lielāks par 0, kas nozīmē, ka Katru reizi, kad jums ir swap, jūs zināt, jūs vēlaties, lai iet atpakaļ un pārbaudīt vēlreiz. Jūs vēlaties, lai saglabātu pārbaudot, kamēr jūs zināt ka jums nav swap vairs. 

Tātad, kas ir labākais un sliktākais Lieta runtimes burbulis kārtot? Un tas hint-- ir faktiski atšķiras no atlases veida tādā ziņā ka šie divi atbildes nav vienādi. Padomājiet par to, kas notiktu lietā, ja tā jau bija sakārtoti. Un domāt par to, ko notiktu, ja tas bija gadījumā, kad tas bija nav sakārtoti. Un jūs varat veida palaist cauri, kāpēc tas notiek. Es došu jums puiši, piemēram, 30 sekundes, lai padomātu par to. 

LABI. Vai kāds ir minējums pie kāda sliktākajā gadījumā runtime burbuļiem veida ir? Jā. 

Mērķauditorija: Vai tas būtu, piemēram, n reizes n mīnus 1 vai kaut kas tamlīdzīgs? Tāpat, katru reizi, kad tā darbojas, tas ir tāpat, kā, piemēram, viens swap mazāk ka neatkarīgi no tā bija. 

ANDI PENG: Jā, tā tu esi pilnīgi taisnība. Un šis ir gadījums, kad jūsu Atbilde bija faktiski sarežģītāka nekā tā mums ir nepieciešams, lai dotu. Tātad, tas notiek, lai run-- es esmu gatavojas dzēst visu šo šeit. Vai visi labi? Vai es varu izdzēst šo? LABI. Jūs esat gatavojas palaist cauri n reizes pirmo reizi, vai ne? Un viņi gatavojas palaist cauri n mīnus 1 otro reizi, vai ne? Un tad jūs gatavojas glabāt iet, n raktuves 2, un tā tālāk. Dāvids darīja to lekciju, ja, ja jūs saskaita visas šīs vērtības, jums kaut kas ir like-- yeah-- vairāk nekā 2, kas būtībā ir tikai samazina līdz n brusas. Jūs esat gatavojas iegūt dīvaini frakcija tur. Un tā tikai zinu, ka n brusas vienmēr prevalē pār frakciju. Un tā šajā gadījumā, sliktākajā runtime būtu n brusas. Ja tas bija dilstošā rīkojums, domāju, jūs ir padarīt swap katru reizi. 

Kas varētu būt, iespējams, labākajā gadījumā izpildlaika? Pieņemsim tikai teikt, ja saraksts jau bija kārtībā, kāda būtu Runtime būt? 

Mērķauditorija: n. ANDI PENG: Tas ir n, tieši tā. Un kāpēc tas ir n? Mērķauditorija: jo jūs vienkārši ir pārbaudīt katru reizi. ANDI PENG: Tieši tā. Tātad vislabākajā runtime, ja šis saraksts jau bija sorted-- teiksim 1, 2, 3, 4-- jums vienkārši iet cauri, jūs varētu pārbaudīt, jūs varētu redzēt, ak, viņi visi pan out. Man nav swap. Esmu pabeidzis. Tātad šajā gadījumā, tas ir tikai n vai vairāki soļi jūs vienkārši bija pārbaudīt pirmajā sarakstā. 

Un pēc tam, mēs tagad hit ievietošanas kārtot, kur algoritms ir būtiski sadalīt tas par šķiroto un nešķirotiem porciju. Un tad pa vienam, nešķirotajiem vērtības ievietota to lietderīgi pozīcijas, kas saraksta sākumā. 

Tā, piemēram, mums ir saraksts, 3, 5, 2, 6, 4 atkal. Mēs zinām, ka tas ir šobrīd nešķiroti jo mēs esam tikai sākās skatoties uz to. Mēs to apskatīt, un mēs zinām, ka Pirmā vērtība ir sakārtots, labi? Ja jūs tikai apskatot masīvs izmērs viens, jūs zināt, ka tas ir sakārtoti. 

Tātad mēs zinām, ka Pārējie četri ir nešķiroti. Mēs ejam cauri, un mēs redzam, ka vērtību. Iesim atpakaļ. Redzēt, ka vērtība ir 5? Mēs varam doties apskatīt to. Mēs salīdzinām to ar 3. Mēs zinām, ka tas ir lielāks nekā 3, tāpēc mēs zinām, ka tas ir sakārtoti. Tātad, mēs tagad zinām, ka pirmās divas ir sakārtoti un pēdējās trīs nav. 

Mēs varam doties apskatīt 2. Mēs vispirms pārbaudiet to ar 5. Vai tas ir mazāk nekā 5? Tas nav. Tātad mums ir, lai saglabātu meklējat leju. Tad jūs pārbaudīt 2 off 3. Vai tas ir mazāk nekā? Nē. Tātad, jūs zināt, 2 ir jāievieto priekšpuses un 3 un 5 abiem jābūt izstumti. Vai tas atkal ar 6 un 4. Un mēs tikai saglabātu pārbaudot būtībā, kur mēs vienkārši pārbaudīt, pārbaudīt, pārbaudīt. Un, kamēr tas ir labi amats, mēs veida tikai ievietojiet to pareizā stāvoklī, kas ir, ja nosaukums no tā nāca no. 

Tātad tas ir tikai algoritms, pseudocode per se, veida, par to, kā mēs varētu īstenot ienesto veida. Pseudocode ir šeit. Tas viss ir tiešsaistē. Neraizējieties, ja jūs guys ir mēģina kopēt šo leju. Tātad vēlreiz, tas pats question-- ko būtu labākais un sliktākais runtimes ievadīšanai veida? Tas ir ļoti līdzīgs pēdējo jautājumu. Es došu jums puiši, piemēram, 30 sekundes, lai padomātu par to kā labi. 

OK Vai kāds vēlas iedodiet man sliktākais runtime? Jā. 

Mērķauditorija: n brusas. 

ANDI PENG: Tas n brusas. Un kāpēc tas ir n kvadrātā? 

Mērķauditorija: Jo apgrieztā secībā, jums ir iet cauri n reizes n, kas is-- ANDI PENG: Jā, tieši tā. Tātad pats kā burbulis šķirot. Ja šis saraksts ir dilstošā secībā, jūs esat nāksies pārbaudīt vispirms vienu reizi. Un tad ar katru papildu vērtību, jūs esat nāksies pārbaudīt to pret katru vērtību, vai ne? Un tā kopā, jūs gatavojas darīt an n caurlaide reizes cits n caurlaide, kas ir n brusas. Kas par labākajā gadījumā? Jā. 

AUDITORIJA: n mīnus 1, jo Pirmais ir jau brusas. 

ANDI PENG: Tātad, tuvu. Atbilde ir faktiski n. Jo, kamēr pirmā no tām ir sakārtots, tā nedrīkst actually-- to mēs vienkārši lucked, jo šis piemērs, ka 2 gadījās būt mazākais skaitlis. Bet tas ne vienmēr tā ir. Ja 2 ir jau sakārtoti sākumā bet jums izskatīties un tur ir 1 šeit, gada 1. gatavojas kliegt to. Un tas notiek, lai beigtu up to bumped anyways. 

Tātad labākajā gadījumā, tas ir tiešām tikai būs n. Ja jums ir 1, 2, 3, 4, 5, 6, 7, 8, jūs gatavojas palaist cauri ka viss saraksts reiz pārbaudīt, lai redzētu, vai viss ir labi. Vai visi skaidrs darbojas laiki izvēles, kā arī? Es zinu, es esmu iet cauri tie ļoti ātri. Bet tikai zinu, ka, ja jūs zināt vispārīgie jēdzieni, jums vajadzētu būt labi. LABI. Tāpēc es ņemšu tikai sniegt jums puiši varbūt, piemēram, minūtes runāt ar saviem kaimiņiem par to, kas ir tikai daži no galvenajām atšķirībām starp šiem veidu veidiem. Mēs iet pār ka drīz. Mērķauditorija: Ak, OK. ANDI PENG: Jā. LABI. Atdzesē, pieņemsim jaunā sanāksmē kā klasē. LABI. Tātad tas bija sava veida beztermiņa jautājums tādā ziņā ka tur ir daudz atbildes uz tiem. Un mēs iet pār daži no tiem īsi. Es tikai gribēju, lai jūs guys domājot par to, kas diferencē visi trīs veidu veidu. Un es dzirdēju, arī, lielisks question-- Kāda apvienot veida darīt? Liels jautājums, jo tas ir ko mēs aptver nākamo. 

Tātad apvienot kārtot ir viena veida, kas darbojas ļoti atšķirīgi no citiem veidu. Kā jūs guys var see-- Dāvids darīt, ka demo kur viņš bija visu atdzist trokšņi redzēt, kā apvienot kārtot skrēja, piemēram, bezgalīgi straujāk nekā pārējo divu veidu? LABI. Tātad, tas ir tāpēc, ka sapludināšanas Kārtot īsteno šo plaisu un iekarot koncepciju, ka mēs esam runāja par daudz lekciju. Tādā nozīmē, ka mēs vēlētos strādāt viedāku, ne grūtāk, ja jūs sadalīt un iekarot problēmas, un izjauktu tiem uz leju, un pēc tam nodot tos kopā, labas lietas vienmēr notiek. 

Tātad tā, ka apvienot kārtot pēc būtības darbi ir tas, ka tā dala nešķirotu masīvs pusi. Un tad tas ir ieguvuši divas pusītes masīvi. Un tas tikai sakārto šīs divas pusītes. Tas tikai tur dalot uz pusēm, jo pusi, uz pusēm, līdz viss ir sakārtots un pēc tam rekursīvi liek to visu kopā. 

Tātad tas ir patiešām abstrakts. Tātad tas ir tikai mazliet pseudocode. Vai tas jēgas veids, kā tas darbojas? Tātad pieņemsim tikai teikt, jums ir masīvs n elementiem, vai ne? Ja n ir mazāks par 2, jūs varat atgriezties. Jo jūs zināt, ka, ja tur ir tikai viena lieta, tā ir sakārtoti. Else, jūs kārtot kreiso pusi, un tad jūs kārtot pareizo pusi, un tad jūs apvienot. 

Tāpēc, kamēr tas izskatās tiešām viegli, realitātē, domājot par to ir veida grūti. Jo jūs esat līdzīgi, Nu, tas ir sava veida darbojas uz sevi. Tiesības? Tas darbojas uz sevi. Tātad šajā ziņā, David pieskārās pēc recursion klasē. Un tas ir jēdziens mēs runājam par daudz. Tas, ka šis, šīs divas līnijas šeit, patiesībā ir tikai programma stāstīt to, lai palaistu sevi ar atšķirīgu ieejas. Tātad, nevis darboties pati ar tad viss n elementiem, Jūs varat sadalīt minēto kreiso pusi un labajā pusē un tad palaist to no jauna. 

Un tad mēs skatāmies uz to vizuāli, jo es esmu vizuālo skolēns. Tas darbojas labāk par mani. Tātad mēs apskatīt vizuālo piemēru šeit. 

Pieņemsim, ka mums ir masīvs, seši elementus, 3, 5, 2, 6, 4, 1, nav sakārtoti. Labi, tur ir daudz šajā lapā. Tātad, ja jūs guys var apskatīt pirmais solis šeit, 3, 5, 2, 6, 4, 1, Jūs varat sadalīt to pusi. Jums ir 3, 5, 2, 6, 4, 1. Jūs zināt, ka tie aren't-- tevi nezinu, vai viņi šķiro vai ne, lai jūs saglabātu pārkāpj tos, uz pusēm, pusi, uz pusēm, līdz beidzot, jums ir tikai viens elements. Un viens elements vienmēr ir sakārtots, labi? 

Tātad mēs zinām, ka 3, 5, 2, 4, 6, 1, kas pašas par sevi ir sakārtoti. Un tagad mēs varam nodot tos atpakaļ kopā. Tātad mēs zinām 3, 5. Mēs ieliekam tos kopā. Mēs zinām, ka ir sakārtoti. 2 joprojām. Mēs varam nodot 4 un 6 kopā. Mēs zinām, ka tas ir sakārtots, tāpēc mēs nodot, ka kopā. Un 1 ir tur. 

Un tad jūs vienkārši apskatīt šīs divas pusītes tieši šeit. Jums ir 3, 5, 2, 2, 3, 5. Jūs varat vienkārši salīdzināt sākumā viss. Jo jūs zināt, ka tas ir sakārtots un jūs zināt, ka tas ir sakārtoti. Tātad jums nav pat ir salīdzināt 5, jūs vienkārši salīdzināt 3. Un 2, ir mazāks par 3, tā jūs zināt, 2 jāiet beigās. 

Pats tur. 1 ir jāiet šeit. Un tad, kad jūs iet nodot šie divi lielumi kopā, jūs zināt, ka tas ir sakārtots un jūs zināt, ka tas ir sakārtots. Tā tad 1 un 2, 1 ir mazāks par 2. Tas stāsta, ka 1 vajadzētu iet uz beigām, tas pat nepaskatoties uz 3 vai 5. Un tad uz 4, jūs varat vienkārši pārbaudīt, tā iet tieši šeit. Jums nav jāskatās uz 5. Pats ar 6. Jūs zināt, ka 6-- tas vienkārši nav nepieciešams izskatījās. 

Un tā šādā veidā, jūs esat tikai ietaupot sevi daudz soļu, kad jūs salīdzināt. Jums nav, lai salīdzinātu katru elements pret citiem elementiem. Jūs vienkārši salīdzināt pret tiem, kas jums ir nepieciešams, lai salīdzinātu to pret. Tātad tas ir sava veida abstraktu jēdzienu. Neraizējieties, ja tas nav gluži hitting jums taisnība vēl. Bet vispār, tas ir kā apvienot veida darbi. Jautājumi, ātrie jautājumi, pirms es virzīties tālāk? Jā. 

Mērķauditorija: Tātad jūs teicāt, ka esat lietojis ar 1, un pēc tam 4, un 6 un nodot tos. Tātad nav those-- netiek Jūs skatoties uz viņiem kā atsevišķi elementi, nevis kā kopumā? ANDI PENG: Jā. Tātad, kas notiek ir tas, ka jūs būtībā rada pavisam jaunu masīvu. Tātad, jūs zināt, ka šeit, man ir divi bloki no lieluma 3, vai ne? Tātad, jūs zināt, ka mans šķiroto masīvs ir jābūt seši elementi. Tātad jūs vienkārši izveidot Jaunā summa atmiņas. Tātad jūs esat veida, piemēram, ir izšķērdīgs atmiņas, bet tas nav svarīgi jo tas ir tik mazs. Tātad paskatās 1 un paskatās 2. Un jūs zināt, ka 1 ir mazāks par 2. Tātad, jūs zināt, ka 1 būtu jāiet sākums visiem tiem. 

Jums pat nav nepieciešams apskatīt 3 un 5. Tātad, jūs zināt 1 iet tur. Tad jūs būtībā karbonāde off 1. Tas ir, piemēram, miris pie mums. Tad mēs vienkārši ir 2, 3, 5, un pēc tam 4 un 6. Un tad jūs zināt, ka jūs salīdzināt 4, 2, Ak, 2 vajadzētu iet tur. Tātad jūs plunkšķis no 2 uz leju, jūs karbonāde to off. Tātad, tad jums vienkārši ir 3 un 5 uz 4 un 6. Un jūs vienkārši glabāt kapāšanas to off kamēr jūs nodot tos masīvā. 

Mērķauditorija: Tātad tu esi tikai vienmēr Salīdzinot [dzirdams]? 

ANDI PENG: Tieši tā. Tātad šajā ziņā, tu esi vienkārši salīdzinot, būtībā, viens numurs pret citu numuru. Un tāpēc, ka jūs zināt ka tas ir sakārtots, jūs nav jāmeklē caur visus numurus. Jums tikai apskatīt pirmo. Un tad jūs varat vienkārši plunkšķis tos, jo jūs zināt tie pieder, ja tie ir piederīgi. Jā. Labs jautājums. 

Un tad, ja kāds no jums ir mazliet ambiciozs, justies brīvi apskatīt šo kodu. Tas ir faktiski fiziskā īstenošana par to, kā mēs varētu rakstīt sapludināšanas veida. Un jūs varat redzēt, tas ir ļoti īss. Bet idejas aiz tas ir diezgan sarežģīti. Tātad, ja jūs jūtaties kā zīmēšanas šo out jūsu mājasdarbu šovakar, justies brīvi. 

LABI. Tātad Dāvids arī gāja pāri šo lekciju. Kāds ir labākais lieta runtimes, vissliktākie runtimes, un paredzamās runtimes no sapludināšanas veida? Pāris sekundes domāt. Tas ir diezgan grūti, bet sava veida intuitīvs, ja jūs domājat par to. Viss kārtībā. 

Mērķauditorija: Vai sliktākajā gadījumā n log n? ANDI PENG: Tieši tā. Un kāpēc tas ir n log n. 

Mērķauditorija: Vai nav tā, jo tas kļūst eksponenciāli ātrāk, tāpēc tas ir, piemēram, atkarībā no ka nevis tikai vienkārši ir n brusas vai kaut kas? ANDI PENG: Tieši tā. Tātad iemesls, kāpēc runtime par šo ir n log n ir because-- Ko jūs dara visu no šiem pasākumiem? Tu esi tikai kapāšanas to pusi, vai ne? Un tad, kad mēs darām log, visu, ko tā dara ir dalot problēma pusi, pusi, uz pusēm, jo ​​vairāk daļās. Un šajā ziņā, jūs varat veida no likvidēt lineārais modelis ka mēs esam izmantojuši. Jo, kad jūs karbonāde lietas pusi, tas ir žurnāls. Tas ir tikai matemātisks veids, kā to pārstāv. 

Un tad beidzot, beigās, jūs esat tikai veicot vienu pēdējo iziet cauri likt tiem visiem kārtībā, vai ne? Un tādēļ, ja jums vienkārši ir pārbaudīt viena lieta, kas ir n. Un tā jūs esat veida reizinot abas kopā. Tātad, tas ir tāpat kā tev, ka galīgais pārbaudīt n leju šeit ar log n šeit. Un, ja jūs reizināt tos, kas ir n log n. 

Un tāpēc labākais gadījums, un sliktākajā lieta un paredzams, ka visi ir n log n. Tas ir arī, piemēram, cita veida. Tas ir tāpat kā atlases veida kas nozīmē, ka tā nav svarīgi, kādas ir jūsu saraksts ir, tas ir tikai gatavojas darīt to pašu katru reizi. LABI. Tātad, kā jūs guys var redzēt, kaut arī par veidu, ka mēs esam izgājuši through-- n brusas, tas nav ļoti efektīva. Un pat tas n log n ir nav efektīvākais. Ja jūs guys ir interese, tur ir kārtot mehānismi kas ir tik efektīva, ka viņi gandrīz būtībā dzīvoklis runtime. 

Jūs esat ieguvuši dažas žurnālu n s. Jūs esat ieguvuši dažas log log n s. Mums nav pieskarties uz tiem šajā klasē tieši tagad. Bet, ja jūs guys ir ziņkārīgs, justies brīvi google, kas ir visefektīvākie šķirošanas mehānismi. Es nezinu, ir daži patiešām smieklīgi tiem, like-- tur ir daži patiešām smieklīgi tie, ka cilvēki dara. Un jūs brīnums, kā viņi kādreiz domājuši par to. Tātad google, ja jums ir dažas rezerves laiks, uz, kādi ir daži smieklīgi veidi ka people-- kā arī Efektīvākās ways-- cilvēki spējuši īstenot veidu. LABI. Un šeit ir tikai ērts maz diagramma. Es zinu, jūs visus, pirms šī viktorīnu 0, būs savā istabā, iespējams, mēģina iegaumēt, ka. Tātad tas ir jauki, jo tur jums puiši. Tikai neaizmirstiet loģiku, ka made-- kāpēc šie skaitļi bija noticis. Ja jūs vienmēr zaudēja, tikai padara pārliecināts, ka jūs zināt, kas ir veida. Un jūs varat palaist caur tos savā prātā saprast, kāpēc tiem, atbildes ir šīs atbildes. 

Viss kārtībā. Tātad mēs ejam, lai pārvietotos gada, visbeidzot, meklēšanu. Jo, kā tiem no jums, kurš ir izlasījis PSET, meklēšana ir arī daļa no šīs nedēļas problēma komplekti. Jums tiks lūgts, lai īstenotu divu veidu meklēšanu. Viens no tiem ir lineāra meklēšanas un viens ir bināro meklēšanu. 

Tātad lineārā meklēšana ir diezgan viegli. Jūs vienkārši vēlaties meklēt elements no saraksta, lai redzētu, vai jums to. Jums tikai atkārtot, izmantojot. Un, ja tas ir vienāds ar kaut ko, Jūs varat atgriezties to, vai ne? Bet viens, ka mēs esam visvairāk ieinteresēti runāt par ir bināro meklēšanu, tiesības, kas ir skaldi un valdi mehānismu, kas David demonstrēja lekciju. 

Atcerieties tālruņu grāmatas piemēru ka viņš tur audzina, viens, ka viņš veida cīnījās mazliet par šo pagājušajā gadā, kur jūs sadalīt problēmu uz pusēm, pusi, uz pusēm, atkal un atkal, līdz jūs atradīsiet to, ko jūs meklējat? Un jūs esat ieguvuši runtime no tā, kā labi. Un jūs varat redzēt, tas ir ievērojami efektīvāki nekā jebkura cita veida meklēšanu. 

Tātad tā, ka mēs varētu iet par Īstenojot bināro meklēšanu ir, ja mums bija masīvs, indekss 0 līdz 6, septiņi elementi, mēs varam skatīties vidū, right-- sorry, ja mūsu jautājumu first-- ja mēs vēlamies uzdot jautājumu, vai masīvs satur no 7 elementu, protams, ir cilvēki, un, ņemot tik maza masīvs, tas ir viegli mums teikt jā. Bet veids, kā īstenot bināro meklēšana būtu meklēt vidū. 

Mēs zinām, ka indekss ir 3 vidū, jo mēs zinu, ka ir septiņi elementi. Ko 7 dalīts ar 2? Jūs varat karbonāde off ka papildus 1. Jūs esat ieguvuši 3 vidū. Tātad ir masīvs 3 vienāds ar 7? Tā nav, vai ne? Bet mēs varam darīt pāris pārbaudes. Vai masīvs 3 mazāk nekā 7 vai ir masīvs no 3 lielāks par 7? 

Un mēs zinām, ka tas ir mazāk nekā 7. Tātad mēs zinām, ka, ak, tai nav būt kreisajā pusē. Mēs zinām, ka tai ir jābūt pareizajā pusē, vai ne? Tātad, mēs varam tikai karbonāde off pusi masīvs. Mums nav pat ir apskatīt to vairs. Jo mēs zinām, ka puse no mūsu problem-- mēs zinām, ka atbilde ir labajā pusē mūsu problēmas. Tātad mēs vienkārši apskatīt, ka tagad. 

Tāpēc tagad mēs skatāmies vidū to, ​​kas ir pa kreisi. Šis indekss 5. Mēs darām to pašu pārbaudi vēlreiz un mēs redzam, ka tas ir mazāks. Tātad mēs skatāmies pa kreisi no tā. Un tad mēs redzam, ka pārbaudi. Vai masīvs vērtība indekss 4 vienāda ar 7? Tas ir. Tātad, mēs varam atgriezties taisnība, jo mēs atradām vērtību mūsu sarakstā. Vai, kā es gāju cauri ka jēgas visiem? LABI. Es došu jums puiši varbūt, piemēram, trīs, četras minūtes, lai noskaidrotu Kā pseudocode to. 

Tik iedomāties es lūdzu jūs rakstīt funkcija sauc meklēšana (), kas atgriezās vērtība, Būla vērtība, tas bija patiess vai false--, piemēram, taisnība, ja jūs atradis vērtība, false, ja jums nav. Un tad tu biji nodots vērtības jums meklējām uz vērtībām, kas ir array-- oh, es noteikti likts ka nepareizā vietā. LABI. Anyways, ka ir jābūt bijis pa labi no vērtībām. Un tad int n ir skaitlis Elementu šajā masīvā. Kā jūs iet par mēģina lai pseudocode šo problēmu? Es došu jums puiši, piemēram, trīs minūtes, lai to izdarītu. Nē, es domāju, ka tur ir only-- yeah, tur ir viena taisnība šeit. Mērķauditorija: Vai es varu? ANDI PENG: Jā, es saņēmu tevi. Vai tas darbojas? OK, atdzesē. 

LABI. Visas tiesības puiši, mēs esam gatavojas iegrožot to. LABI. Tātad pieņemu, mēs esam ieguvuši šo skaisto maz masīvs ar n vērtībām tajā. Man nebija zīmēt līnijas. Bet kā būtu mēs iet par cenšos rakstīt šo? Vai kāds vēlas iedodiet man pirmajā rindā? Ja jūs vēlaties, lai dotu man Pirmajā rindā no šīs pseudocode. 

Mērķauditorija: [dzirdams] Mērķauditorija: Jūs vēlaties, atkārtot through-- Mērķauditorija: Just another cilpas? Mērķauditorija: --for. 

ANDI PENG: Tātad šis viens ir mazliet viltīgs. Padomā about-- vēlaties lai saglabātu darboties šo cilpa atkal un atkal, līdz, ja? 

Mērķauditorija: Līdz [nedzirdama] vērtība ir vienāda ar minēto vērtību. ANDI PENG: Tieši tā. Tātad jūs varat faktiski tikai write-- mēs pat varam vienkāršot to vairāk. Mēs varam tikai darīt, kamēr cilpa, vai ne? Tātad, jūs varat vienkārši ir loop-- mēs zinām, ka tā ir, bet. Bet tagad labi, es eju teikt "cilpu" - ar ko? Loop until-- kas ir Mūsu beidzas stāvoklis? Es domāju, ka es dzirdēju to. Es dzirdēju kādu sakām to. 

Mērķauditorija: Vērtības ir vienāds vidū. ANDI PENG: Pasaki to vēlreiz. Mērķauditorija: Vai, kamēr vērtība jūs meklējat , ir vienāda ar vidējo vērtību. 

ANDI PENG: Ko darīt, ja tas nav tur? Ko darīt, ja vērtība jūs meklējat jo faktiski nav šajā masīvā? Mērķauditorija: Tu atgriezīsies 1. 

ANDI PENG: Bet ko mēs gribam cilpa, kamēr, ja mums ir stāvoklī? Jā. 

Mērķauditorija: Līdz tur ir tikai viena vērtība? ANDI PENG: Jūs varat cilpa until-- lai jūs zināt, ka jūs esat nāksies max vērtība, vai ne? Un jūs zināt, ka jūs gatavojas lai būtu min vērtība, vai ne? Jo arī, tas ir kaut kas Es aizmirsu pirms teikt, ka kaut kas ir kritiska par bināro meklēšanu ir tas, ka jūsu masīva jau ir sakārtoti. Jo tur nav veids, kā to tas ja viņi tikai izlases vērtībām. Jūs nezināt, ja viens ir lielāks nekā otru, labi? 

Tātad, jūs zināt, ka jūsu max un Jūsu mins ir šeit, vai ne? Ja jūs esat būs pielāgojot Jūsu max jūsu min un mid-- pieņemsim tikai uzņemties savu mid vērtība ir taisnība here-- jūs gatavojas būtībā cilpa, kamēr jūsu minimums ir apmēram tāds pats kā jūsu max, pa labi, vai ja jūsu max ir tas pats kā jūsu min. Tiesības? Jo tad, kad tas notiks, jūs zināt, ka jūs esat beidzot hit pašu vērtību. Tātad jūs vēlaties, lai cilpa, kamēr jūsu min ir mazāks par vai vienāds kuri paredzēti, Ups, ne mazāks par vai vienāds ar, Otrs veids around-- maks ir. 

Vai, ka jēga? Paņēmu dažas mēģina iegūt šīs tiesības. Bet cilpa līdz Jūsu max vērtības būtībā gandrīz mazāk par vai vienāds ar savu minimumu, vai ne? Tas ir, kad jūs zināt ka jūs esat izlīdzinājušās. Mērķauditorija: Kad būtu jūsu maksimālā vērtība ir mazāka par minimālo? ANDI PENG: Ja jūs paturiet pielāgojot to, kas ir tas, ko mēs gatavojamies lai dara to. Vai tas ir jēga? Minimālā un max ir tikai veseli skaitļi, kas mums ir, iespējams, gatavojas vēlaties, lai izveidotu, lai saglabātu trase, kur mēs meklējam. Jo masīvs eksistē neatkarīgi no tā, ko mēs darām. Tāpat, mēs esam faktiski nav fiziski kapāšanas pie masīva, vai ne? Mēs esam tikai pielāgojot kur mēs meklējam. Vai tas ir jēga? 

Mērķauditorija: Jā. 

ANDI PENG: OK. Tātad, ja tas ir nosacījums mūsu cilpas, Ko mēs gribam iekšā šīs cilpas? Ko mēs gribam būt vēlas darīt? Tāpēc tieši tagad, mēs esam ieguvuši max un min, pa labi, droši vien radīja šeit kaut kur. Mēs ejam, lai, iespējams, vēlas atrast vidū, labi? Kā mēs gribam būt iespēja atrast vidū? Kas ir mathematical-- Mērķauditorija: Max plus min dalīts ar 2. ANDI PENG: Tieši tā. Vai tas ir jēga? Un jūs guys redzēt, kāpēc mēs nebija tikai use-- kāpēc mēs to darījām nevis dara tikai n dalot ar 2? Tas ir tāpēc, ka n ir vērtība kas notiek, lai palikt tāds pats. Tiesības? Bet kā mēs pielāgot mūsu minimumu un maksimālās vērtības, viņi gatavojas mainīt. Un kā rezultātā, mūsu vidējā gatavojas mainīt too. Tātad, tāpēc mēs vēlamies darīt šīs tiesības šeit. LABI. 

Un tad tagad, mēs esam noskaidrojuši our-- yeah. 

Mērķauditorija: Just a quick question-- kad jūs sakāt min un max, mēs pieņemot, ka tas jau sakārtoti? 

ANDI PENG: Jā, tas tiešām ir priekšnoteikums bināro meklēšanu, kas jums ir jāzina, tas ir sakārtoti. Kurš ir iemesls, kāpēc kārtot, jūs rakstīt savu Problēma noteikti pirms jūsu bināro meklēšanu. LABI. Tāpēc tagad, ka mēs zinām, kur mūsu viduspunktā ir, ko jūs vēlaties darīt šeit? 

Mērķauditorija: Mēs vēlamies, lai salīdzinātu ka uz otru. ANDI PENG: Tieši tā. Tātad jūs gatavojas, lai salīdzinātu vidus līdz vērtībai, vai ne? Un ko tas pateiks mums, kad mēs salīdzinām? Ko mēs vēlamies darīt pēc tam? 

Mērķauditorija: Ja vērtība ir lielāka nekā vidū, mēs vēlamies samazināt to off. ANDI PENG: Tieši tā. Tātad, ja vērtība ir lielāka nekā vidū, mēs esam gatavojas vēlaties mainīt šos Minimālā un maxes, labi? Ko mēs gribam mainīt? Tātad, ja mēs zinām, vērtība ir kaut kur šeit, ko jūs mums jāmaina? Mēs vēlamies mainīt mūsu minimums būt vidus, labi? Un tad vēl, ja tas ir šajā puse, ko mēs gribam mainīt? 

Mērķauditorija: Jūsu maksimums. ANDI PENG: Jā. Un tad jūs tikai gatavojas saglabāt looping, vai ne? Jo tagad, pēc viena atkārtojuma izmantojot, jūs esat ieguvuši max šeit. Un tad jūs varat pārrēķināt mid. Un tad jūs varat salīdzināt. Un jūs gatavojas, lai saglabātu turpinās līdz min un maxes būtībā izlīdzinājušās. Un tas ir tad, kad jūs zināt, ka jūs esat hit beigām tā. Un nu jūs esat atradis vai jums ir ne tajā brīdī. 

Vai tas ir jēga, lai visiem? LABI. Tas ir diezgan svarīgi, jo jums ir rakstīt šo jūsu kodu šovakar. Bet jums puiši ir diezgan labs sajūtu, ko jums vajadzētu darīt, kas ir labs. LABI. Tātad, mēs esam ieguvuši apmēram septiņi minūtes atstāja nodaļu. Tāpēc mēs esam gatavojas runāt par Tas PSET, ka mums būs darīt. Tātad PSET ir sadalīta divās daļās. Pirmajā pusē ir saistīta Īstenojot Find kurā jūs rakstīt lineāra meklēšana, bināro meklēšanu, kā arī šķirošanas algoritmu. 

Tātad šis ir pirmais reizi pēc PSET kur mēs būsim sniedzot jums puiši, ko sauc sadales kods, kas ir kodu ka mēs esam iepriekš rakstīts, bet tikai pa kreisi dažus gabalus off lai jūs varētu pabeigt rakstīšanu. Tātad jums puiši, ja jūs apskatīt šo kods, jūs varētu saņemt patiešām nobijies. Ja jūs vienkārši vēlaties, Ahh, es nezinu, ko tas dara, Es nezinu, kā, piemēram, tas, šķiet, tik sarežģīti, ahh, atpūsties. Ir labi. Lasīt spec. Spec izskaidros jums tieši Ko visas šīs programmas dara. 

Piemēram, generate.c ir programma kas nāks ar savu PSET. Jums nav tiešām ir pieskarties, bet Jums vajadzētu saprast, ko tas dara. Un generate.c, visi tā dara, ir nu radot izlases skaitu vai jūs varat dot to sēklas, piemēram, iepriekš sagatavots numurs ka tas notiek, un tas rada vairāk numuru. Tātad tur ir īpašs veids, kā īstenot generate.c kurā Jūs varat vienkārši veikt ķekars numuriem lai jūs varētu pārbaudīt jūsu citas metodes on. 

Tātad, ja jūs vēlaties, lai, Piemēram, pārbaudīt savas Atrast, jūs vēlaties, lai palaistu generate.c, radīt ķekars numuriem, un pēc tam palaist jūsu palīgiem funkciju. Jūsu palīgi funkcija ir, ja tu esi faktiski fiziski rakstot kodu. Un domā par palīgiem, kā bibliotēkas failu jūs esat rakstiski, ka atradums zvana. Un tā laikā helpers.c, jūs do meklēšanu un šķirošana. 

Un tad jūs gatavojas būtībā vienkārši viņus visus kopā. Spec jums pateiks, kā to likt ka uz komandrindas. Un jūs varēsiet pārbaudīt, vai nav jūsu kārtot un meklēt strādā. Cool. Vai kāds jau ir sākusies, un radušās problēmas vai jautājumi tie ir tieši tagad ar šo? LABI. 

Mērķauditorija: Pagaidiet. Man ir jautājums. 

ANDI PENG: Jā. 

Mērķauditorija: Tātad es sāku darīt lineārais sektorā helpers.c un tas nebija īsti strādāt. Bet tad vēlāk, es uzzināju mēs vienkārši ir izdzēst to un darīt bināro meklēšanu. Tātad tas jautājums, ja tas nedarbojas? 

ANDI PENG: Īsā atbilde ir nē. Bet, tā kā mēs esam not-- Mērķauditorija: Bet neviens s faktiski pārbaudot. ANDI PENG: Mēs esam nekad gatavojas redzēt, ka. Bet jūs, iespējams, vēlaties, lai Pārliecinieties, ka jūsu meklēšanas strādā. Jo, ja jūsu lineārs meklēšana nedarbojas, tad izredzes ir jūsu bināro meklēšana nav dodas uz darbu, kā arī. Jo jums ir līdzīga loģika viņiem abiem. Un nē, tas nav īsti jautājums. Tātad vienīgie, jūs savukārt jo ir kārtot un bināro meklēšanu. Jā. 

Un arī, daudz bērniem bija mēģinot apkopot helpers.c. Jūs neesat faktiski atļauta to darīt, jo helpers.c nav galvenā funkcija. Un lai jūs būtu tikai būt faktiski apkopojot radīt un atrast, jo atrast zvani helpers.c un funkcijas tajā. Tātad, kas padara atkļūdošanu sāpes muca. Bet tas, kas mums ir jādara. Mērķauditorija: Jums tikai darīt visu, vai ne? ANDI PENG: jūs varat vienkārši darīt visu, kā arī, jā. LABI. Tāpēc, ka tas arī viss par to, ko PSET lūdz jūs visi darīt. Ja jums ir kādi jautājumi, droši brīvi uzdot man pēc iedaļas. Es būšu šeit, piemēram, 20 minūtes. 

Un jā, tad PSET s tiešām nav tik slikti. Jūs puiši būtu OK. Tie, vienkārši izpildiet norādījumus. Veida ir sajūta, loģiski, ko vajadzētu būt noticis, un jums būs labi. Vai nav pārāk nobijies. Tur ir daudz koda jau rakstīts tur. Vai nav pārāk nobijies, ja jums nav saprast, ko tas viss nozīmē. Ja tas ir daudz, tas ir pilnīgi naudas sodu. Un nāk uz darba laika. Mēs palīdzēsim jums to apskatīt. 

Mērķauditorija: Ar papildu funkcijas, mēs skatīties tos uz augšu? 

ANDI PENG: Jā, tie ir kodu. Šajā spēlē 15, puse no tas jau rakstīts jums. Tātad šīs funkcijas ir jau kodu. Yep. Viss kārtībā. Nu, veiksmi. Tas ir pretīgi diena. Tik cerams, jūs guys nejūtos pārāk slikti par uzturas iekšā un kodēšanas.