1 00:00:00,000 --> 00:00:00,488 2 00:00:00,488 --> 00:00:10,800 >> [Muusika mängib] 3 00:00:10,800 --> 00:00:13,500 DAVID Malan: Olgu. 4 00:00:13,500 --> 00:00:14,670 Olgu, tere tulemast tagasi. 5 00:00:14,670 --> 00:00:18,120 Nii et see on 4. nädalal alguses arvestades, et juba. 6 00:00:18,120 --> 00:00:21,320 Ja sa meenutada, et eelmisel nädalal paneme koodi kõrvale natuke 7 00:00:21,320 --> 00:00:24,240 ja me hakkasime rääkima natuke rohkem kõrgetasemelised asju nagu 8 00:00:24,240 --> 00:00:28,130 otsimine ja sorteerimine, mis on küll mõnevõrra lihtsad ideed, on 9 00:00:28,130 --> 00:00:31,840 esindaja klass probleeme hakkate lahendada eriti 10 00:00:31,840 --> 00:00:34,820 kui hakkate mõtlema lõplik projekte ja huvitavaid lahendusi 11 00:00:34,820 --> 00:00:36,760 võib-olla reaalse maailma probleeme. 12 00:00:36,760 --> 00:00:39,490 Nüüd mull sort oli üks lihtsamaid selline algoritme, ja see 13 00:00:39,490 --> 00:00:42,900 töötas omades väikest arvu nimekirja või massiivi omamoodi 14 00:00:42,900 --> 00:00:46,530 mull oma teed kuni ülemise ja big numbrid liikuda oma tee alla 15 00:00:46,530 --> 00:00:47,930 aasta lõpuks, et nimekirja. 16 00:00:47,930 --> 00:00:50,650 >> Ja meenutada, et me võiks visualiseerida mull omamoodi väike 17 00:00:50,650 --> 00:00:52,310 midagi sellist. 18 00:00:52,310 --> 00:00:53,640 Nii et lubage mul minna ja klõpsake nuppu Start. 19 00:00:53,640 --> 00:00:55,350 Olen valmis valitud mull omamoodi. 20 00:00:55,350 --> 00:00:58,920 Ja kui te mäletate, et pikem sinine Jooned tähistavad suured numbrid, väike 21 00:00:58,920 --> 00:01:03,300 sinised jooned kujutavad vähe, kui me minna läbi see uuesti ja uuesti ja 22 00:01:03,300 --> 00:01:07,680 jälle, võrreldes kaks baari kõrval iga teine ​​punane, me ei kavatse vahetada 23 00:01:07,680 --> 00:01:11,010 suurima ja väikseima kui nad on rikkis. 24 00:01:11,010 --> 00:01:14,150 >> Nii see läheb ja edasi minna ja minna kohta, ja te näete, et suurem 25 00:01:14,150 --> 00:01:16,700 elemendid teevad oma tee õige, ja väiksemad elemendid on 26 00:01:16,700 --> 00:01:17,900 tegemise teel vasakule. 27 00:01:17,900 --> 00:01:21,380 Aga meil hakkas kvantifitseerida Tõhususe 28 00:01:21,380 --> 00:01:22,970 kvaliteet selle algoritmi. 29 00:01:22,970 --> 00:01:25,200 Ja me ütlesime, et halvimal juhul on see algoritm võttis 30 00:01:25,200 --> 00:01:27,940 ligikaudu, mitu sammu? 31 00:01:27,940 --> 00:01:28,980 >> Nii n ruudus. 32 00:01:28,980 --> 00:01:30,402 Ja mis oli n? 33 00:01:30,402 --> 00:01:31,650 >> Publik: elementide arv. 34 00:01:31,650 --> 00:01:32,790 >> DAVID Malan: So n oli mitmeid elemente. 35 00:01:32,790 --> 00:01:33,730 Ja nii me teeme seda sageli. 36 00:01:33,730 --> 00:01:36,650 Iga kord, kui me tahame rääkida suurus probleem või suuruse 37 00:01:36,650 --> 00:01:39,140 sisend, või kui palju aega kulub toota toodangut, me lihtsalt 38 00:01:39,140 --> 00:01:41,610 üldistatud iganes sisend on n. 39 00:01:41,610 --> 00:01:45,970 Nii tagasi nädal 0, number lehekülge aastal telefoniraamat oli n. 40 00:01:45,970 --> 00:01:47,550 Õpilaste arv ruumis oli n. 41 00:01:47,550 --> 00:01:49,630 Nii ka siin, me pärast et muster. 42 00:01:49,630 --> 00:01:52,800 >> Nüüd n ruudus ei ole eriti kiire, nii oleme püüdnud teha paremini. 43 00:01:52,800 --> 00:01:55,970 Ja nii me vaatasime paar teiste algoritme, mille hulgas 44 00:01:55,970 --> 00:01:57,690 olid valiku sort. 45 00:01:57,690 --> 00:01:59,180 Seega valik sort oli veidi erinev. 46 00:01:59,180 --> 00:02:03,130 See oli peaaegu lihtsam, ma julgen öelda, kusjuures ma hakkasin alguses 47 00:02:03,130 --> 00:02:06,740 nimekiri meie vabatahtlikele ja ma lihtsalt uuesti ja jälle läks läbi 48 00:02:06,740 --> 00:02:10,060 nimekiri, kitkumise välja väikseim element korraga ja paneb teda või 49 00:02:10,060 --> 00:02:13,040 teda alguses nimekirja. 50 00:02:13,040 --> 00:02:16,410 >> Aga ka see, kui me hakkasime mõtlema läbi matemaatika ja suurem 51 00:02:16,410 --> 00:02:19,860 pilt, mõelnud mitu korda Ma läksin edasi ja tagasi ja tagasi 52 00:02:19,860 --> 00:02:24,090 edasi ja me ütlesime halvimal juhul valik sort oli ka see, mida? 53 00:02:24,090 --> 00:02:24,960 n ruudus. 54 00:02:24,960 --> 00:02:27,490 Nüüd reaalses maailmas, see võib tegelikult ainult natuke kiiremini. 55 00:02:27,490 --> 00:02:30,620 Kuna uuesti, ma ei pea hoidma tagurdusmeetod kord olin järjestatud 56 00:02:30,620 --> 00:02:31,880 väikseim elemente. 57 00:02:31,880 --> 00:02:35,090 Aga kui me mõtleme väga suur n ja kui sa omamoodi tegema läbi matemaatika kui 58 00:02:35,090 --> 00:02:39,170 Tegin laual, koos n ruudus miinus midagi, kõik muu 59 00:02:39,170 --> 00:02:41,850 peale n ruudus, kui n saab tõesti suur, ei 60 00:02:41,850 --> 00:02:42,850 tegelikult küsimus, kui palju. 61 00:02:42,850 --> 00:02:45,470 Nii nagu arvuti teadlased, oleme omamoodi silmi kinni pigistama, et väiksemate 62 00:02:45,470 --> 00:02:49,220 teguritest ja keskenduda ainult tegur mõiste, mis läheb teha 63 00:02:49,220 --> 00:02:50,330 suurim erinevus. 64 00:02:50,330 --> 00:02:52,840 >> Noh, lõpuks, me vaatasime kell sisestamise sort. 65 00:02:52,840 --> 00:02:56,620 Ja see oli sarnase sisuga, kuid mitte läbida korduvalt ja 66 00:02:56,620 --> 00:03:01,250 valida väikseim element ükshaaval aega, ma selle asemel võttis kätte, et ma 67 00:03:01,250 --> 00:03:04,070 arutati, ja ma otsustasin, kõik õige, sa kuulud siia. 68 00:03:04,070 --> 00:03:06,160 Siis kolisin järgmisele element ja otsustas, et ta või 69 00:03:06,160 --> 00:03:07,470 ta kuulus siin. 70 00:03:07,470 --> 00:03:08,810 Ja siis kolisin edasi ja edasi. 71 00:03:08,810 --> 00:03:11,780 Ja ma võiks üles, mööda teed, suunata need kutid, et 72 00:03:11,780 --> 00:03:13,030 teha ruumi neile. 73 00:03:13,030 --> 00:03:16,880 Nii et oli omamoodi vaimne pöördumise Valiku sort, et meil 74 00:03:16,880 --> 00:03:18,630 nimetatakse sisestamise sort. 75 00:03:18,630 --> 00:03:20,810 >> Nii et need teemad tekivad reaalses maailmas. 76 00:03:20,810 --> 00:03:23,640 Paar aastat tagasi, kui teatud senaator presidendiks kandideerida, 77 00:03:23,640 --> 00:03:27,160 Eric Schmidt ajal tegevjuht Google, tegelikult oli võimalus 78 00:03:27,160 --> 00:03:28,040 küsitleda teda. 79 00:03:28,040 --> 00:03:32,010 Ja me arvasime me tahaks jagada seda YouTube'is Videoklipp sa siin, kui me võiks omakorda üles 80 00:03:32,010 --> 00:03:32,950 helitugevust. 81 00:03:32,950 --> 00:03:39,360 >> [VIDEO PLAYBACK] 82 00:03:39,360 --> 00:03:44,620 >> -Senaator, et sa siin oled Google, ja mulle meeldib mõelda eesistujariigi 83 00:03:44,620 --> 00:03:46,042 nagu tööintervjuu. 84 00:03:46,042 --> 00:03:47,770 >> [Naer] 85 00:03:47,770 --> 00:03:50,800 >> -Nüüd on raske saada töö kui president. 86 00:03:50,800 --> 00:03:52,480 Ja sa lähed läbi külmavärinad nüüd. 87 00:03:52,480 --> 00:03:54,330 Samuti on raske saada tööd Google. 88 00:03:54,330 --> 00:03:59,610 Meil on küsimused ja palume Meie kandidaadid küsimusi. 89 00:03:59,610 --> 00:04:02,250 Ja see on Larry Schwimmer. 90 00:04:02,250 --> 00:04:05,325 >> [Naer] 91 00:04:05,325 --> 00:04:06,400 -Te vist teen nalja? 92 00:04:06,400 --> 00:04:08,750 See on siinsamas. 93 00:04:08,750 --> 00:04:12,110 Mis on kõige tõhusam viis Kuvatud miljonit kaks-bit täisarvud? 94 00:04:12,110 --> 00:04:15,810 >> [Naer] 95 00:04:15,810 --> 00:04:18,260 >> -Noh, uh - 96 00:04:18,260 --> 00:04:19,029 >> Anna andeks. 97 00:04:19,029 --> 00:04:19,745 Võib-olla me peaks - 98 00:04:19,745 --> 00:04:21,000 >> -Ei, ei, ei, ei, ei. 99 00:04:21,000 --> 00:04:21,470 >> -See ei ole - 100 00:04:21,470 --> 00:04:22,185 OK. 101 00:04:22,185 --> 00:04:25,328 >> -Ma arvan, et mull sort oleks olla vale tee. 102 00:04:25,328 --> 00:04:26,792 >> [Naer] 103 00:04:26,792 --> 00:04:28,510 >> [Cheering JA APLAUS] 104 00:04:28,510 --> 00:04:31,211 >> Tule, kes rääkis talle seda? 105 00:04:31,211 --> 00:04:32,155 OK. 106 00:04:32,155 --> 00:04:33,350 >> [END VIDEO PLAYBACK] 107 00:04:33,350 --> 00:04:35,070 >> DAVID Malan: Nii et teil on see. 108 00:04:35,070 --> 00:04:39,600 Niisiis hakkasime arvuliselt töötab korda, nii et rääkida, millegi 109 00:04:39,600 --> 00:04:43,480 nimetatakse asümptootiliseks märke, mis on lihtsalt viidates meie omamoodi keerates 110 00:04:43,480 --> 00:04:47,420 silma need väiksemad tegurid ja ainult vaadates sõiduaega, 111 00:04:47,420 --> 00:04:51,250 täidaksid neid algoritme, kui n saab tõesti suur ajas. 112 00:04:51,250 --> 00:04:55,110 Ja nii me kasutusele suur O. Ja suur O esindab midagi, mida me arvasime 113 00:04:55,110 --> 00:04:57,000 AS ülemise. 114 00:04:57,000 --> 00:04:59,570 Ja tegelikult, Barry, saame alandada kui mic natuke? 115 00:04:59,570 --> 00:05:01,040 >> Me arvasime, et sellest on ülemise. 116 00:05:01,040 --> 00:05:04,710 Nii suur O n ruudus tähendab, et halvimal juhul midagi 117 00:05:04,710 --> 00:05:07,780 valik omamoodi võtaks n ruudus samme. 118 00:05:07,780 --> 00:05:10,310 Või midagi sellist sisestamise sort oleks n ruudus samme. 119 00:05:10,310 --> 00:05:15,150 Nüüd midagi sisestamise sort, mis oli halvim? 120 00:05:15,150 --> 00:05:18,200 Arvestades massiiv, mis on kõige hullem võimalik stsenaarium, et te võite leida 121 00:05:18,200 --> 00:05:20,650 ise silmitsi? 122 00:05:20,650 --> 00:05:21,860 >> See on täiesti tagurpidi, eks? 123 00:05:21,860 --> 00:05:24,530 Sest kui see on täiesti tagurpidi, mida sa pead tegema palju tööd. 124 00:05:24,530 --> 00:05:26,420 Sest kui sa oled täiesti tagurpidi, sa lähed leida 125 00:05:26,420 --> 00:05:28,840 suurim element siin, kuigi see kuulub sinna alla. 126 00:05:28,840 --> 00:05:31,140 Nii et sa lähed öelda, olgu, kell Praegusel ajahetkel, sa kuulud siia, 127 00:05:31,140 --> 00:05:32,310 nii et jäta ta rahule. 128 00:05:32,310 --> 00:05:35,425 >> Siis sa mõistad, oh, neetud, ma pean liiguta see veidi väiksem element 129 00:05:35,425 --> 00:05:36,470 vasakul teile. 130 00:05:36,470 --> 00:05:38,770 Siis ma pean tegema, et uuesti ja uuesti ja uuesti. 131 00:05:38,770 --> 00:05:41,410 Ja kui ma kõndis edasi-tagasi, siis oleks omamoodi tunne tulemuslikkust 132 00:05:41,410 --> 00:05:45,540 et algoritm, sest pidevalt ma olen lohistades kõik teisedki alla 133 00:05:45,540 --> 00:05:46,510 massiivi teha ruumi. 134 00:05:46,510 --> 00:05:47,750 Nii et halvim. 135 00:05:47,750 --> 00:05:48,570 >> Seevastu - 136 00:05:48,570 --> 00:05:50,320 ja see oli pinge viimast korda - 137 00:05:50,320 --> 00:05:54,065 me öelda, et sisestamise sort oli omega mida? 138 00:05:54,065 --> 00:05:57,530 Milline on parim puhul töötab on asetatud sort? 139 00:05:57,530 --> 00:05:58,520 Nii et see on tegelikult n. 140 00:05:58,520 --> 00:06:00,980 See oli tühi, et jätsime laual viimast korda. 141 00:06:00,980 --> 00:06:03,160 >> Ja see on omega n sest miks? 142 00:06:03,160 --> 00:06:06,630 Noh, väga parim, siis millised on sisestamise omamoodi kavatse antakse? 143 00:06:06,630 --> 00:06:09,830 Noh, nimekiri, mis on täielikult järjestatud juba, minimaalne tööd teha. 144 00:06:09,830 --> 00:06:12,460 Aga mis on puhas umbes sisestamise sorteeri on see, et kuna see algab siin ja 145 00:06:12,460 --> 00:06:15,340 otsustab, oh, sa oled number üks, sa kuulud siia. 146 00:06:15,340 --> 00:06:16,970 Oh, mis õnn. 147 00:06:16,970 --> 00:06:17,740 >> Sa oled number kaks. 148 00:06:17,740 --> 00:06:19,030 Samuti kuuluvad siia. 149 00:06:19,030 --> 00:06:21,010 Number kolm, isegi parem, sa kuulud siia. 150 00:06:21,010 --> 00:06:25,210 Niipea, kui ta saab lõpuks nimekirja kohta sisestamise sort on pseudokoodi 151 00:06:25,210 --> 00:06:28,010 et me kõndinud läbi suuliselt viimane kord, see on tehtud. 152 00:06:28,010 --> 00:06:32,790 Aga valiku sorteerida, seevastu hoida seda, mida? 153 00:06:32,790 --> 00:06:35,260 >> Hoitud läbimas nimekiri uuesti ja uuesti ja uuesti. 154 00:06:35,260 --> 00:06:39,160 Sest Võtmeküsimuseks oli ainult kui olete otsinud kõik viis 155 00:06:39,160 --> 00:06:42,500 nimekirja lõppu sa saad olla kindel et element valisite oli 156 00:06:42,500 --> 00:06:45,560 tõepoolest praegu väikseim element. 157 00:06:45,560 --> 00:06:48,920 Nii et need erinevad vaimse mudelid lõppu üles saades mõned väga reaalse 158 00:06:48,920 --> 00:06:53,130 erinevused meile, samuti nende teoreetiline asümptootiliseks erinevusi. 159 00:06:53,130 --> 00:06:56,910 >> Nii lihtsalt sulgege siis suur O n ruudus, me oleme näinud vähe selliseid 160 00:06:56,910 --> 00:06:58,350 algoritme siiani. 161 00:06:58,350 --> 00:06:59,580 Big O n? 162 00:06:59,580 --> 00:07:02,870 Mis on algoritm, mis võiks pidada suur O n? 163 00:07:02,870 --> 00:07:06,930 Halvimal juhul kulub lineaarne arvu. 164 00:07:06,930 --> 00:07:07,810 >> OK, lineaarne otsing. 165 00:07:07,810 --> 00:07:10,470 Ja halvimal juhul, kui see on element otsite kui 166 00:07:10,470 --> 00:07:12,950 lineaarse otsing? 167 00:07:12,950 --> 00:07:14,680 >> OK, halvimal juhul see ei ole isegi seal. 168 00:07:14,680 --> 00:07:17,000 Või teine ​​halvim, see on kõik viis lõpuks, mis on 169 00:07:17,000 --> 00:07:18,880 pluss-või-miinus üks samm vahe. 170 00:07:18,880 --> 00:07:21,180 Nii et lõpuks, võime öelda, et see on lineaarne. 171 00:07:21,180 --> 00:07:23,910 Big O n oleks lineaarne otsing, sest halvimal juhul, 172 00:07:23,910 --> 00:07:26,610 element ei ole isegi seal või see on kogu tee lõpus. 173 00:07:26,610 --> 00:07:29,370 >> Noh, suur O log n. 174 00:07:29,370 --> 00:07:32,760 Me ei saa rääkida väga üksikasjalikult seda, kuid me oleme seda varem näinud. 175 00:07:32,760 --> 00:07:36,840 Mis töötab nn logaritmiline aega, halvimal juhul? 176 00:07:36,840 --> 00:07:38,500 >> Jah, nii binaarne otsing. 177 00:07:38,500 --> 00:07:42,930 Ja binaarne otsing halvimal juhul võib olla element kuskil 178 00:07:42,930 --> 00:07:45,640 keskel või kuskil sees massiiv. 179 00:07:45,640 --> 00:07:48,040 Aga te ainult leida see, kui olete Jaga nimekirja pooleks, in 180 00:07:48,040 --> 00:07:48,940 pool, poole, pooleks. 181 00:07:48,940 --> 00:07:50,200 Ja siis voila, see on seal. 182 00:07:50,200 --> 00:07:52,500 Või veel, halvimal juhul see ei ole isegi seal. 183 00:07:52,500 --> 00:07:56,770 Aga te ei tea, et see ei ole seal kuni sa omamoodi jõuda, et viimane 184 00:07:56,770 --> 00:08:00,470 kõige alumine elementide poole võrra ja poole võrra ja vähendada poole võrra. 185 00:08:00,470 --> 00:08:01,400 >> Big O 1. 186 00:08:01,400 --> 00:08:03,540 Et me saaksime suur O 2, suur O 3. 187 00:08:03,540 --> 00:08:06,260 Anytime soovite lihtsalt konstant, me lihtsalt sorteerida just lihtsamaks 188 00:08:06,260 --> 00:08:07,280 et kui suur O 1. 189 00:08:07,280 --> 00:08:10,440 Isegi kui reaalselt kulub 2 või isegi 100 sammu, kui see on 190 00:08:10,440 --> 00:08:13,680 pidev mitmeid samme, me lihtsalt öelda suur O 1. 191 00:08:13,680 --> 00:08:15,930 Mis on algoritm, mis on aastal suur O 1? 192 00:08:15,930 --> 00:08:18,350 >> Publik: Leida pikkus muutuv. 193 00:08:18,350 --> 00:08:21,090 >> DAVID Malan: Leida pikkus muutuv? 194 00:08:21,090 --> 00:08:23,870 >> Publik: Ei, pikkus kui see on juba järjestatud. 195 00:08:23,870 --> 00:08:24,160 >> DAVID Malan: Hea. 196 00:08:24,160 --> 00:08:27,850 OK, nii leida pikkust midagi kui pikkus, et midagi nagu 197 00:08:27,850 --> 00:08:30,020 massiiv, on salvestatud mõned muutuja. 198 00:08:30,020 --> 00:08:33,380 Sest sa võid lugeda muutuja, või printida muutuja või 199 00:08:33,380 --> 00:08:34,960 lihtsalt tavaliselt juurdepääs, et muutuja. 200 00:08:34,960 --> 00:08:37,299 Ja voila, mis võtab pidevalt aega. 201 00:08:37,299 --> 00:08:38,909 >> Seevastu arvan, et tagasi tühjalt. 202 00:08:38,909 --> 00:08:42,460 Mõtle tagasi esimesel nädalal C, kutsudes lihtsalt printf ja trükkimine 203 00:08:42,460 --> 00:08:46,240 midagi ekraanil on väidetavalt pidev ajal, sest see lihtsalt võtab 204 00:08:46,240 --> 00:08:50,880 mõned mitmeid protsessori näidata et teksti ekraanil. 205 00:08:50,880 --> 00:08:52,720 Või oodake - kas pole? 206 00:08:52,720 --> 00:08:56,430 Kuidas muidu võiks me modelleerida täitmise printf? 207 00:08:56,430 --> 00:09:00,420 Kas keegi meeldib nõus, et võibolla see ei ole tõesti pidev ajal? 208 00:09:00,420 --> 00:09:03,600 Mis mõttes võib printf jookseb ajal tegelikult trükkimine string 209 00:09:03,600 --> 00:09:05,580 ekraanil olema midagi peale pidevalt. 210 00:09:05,580 --> 00:09:07,860 >> Publik: [kuuldamatu]. 211 00:09:07,860 --> 00:09:08,230 >> DAVID Malan: Jah. 212 00:09:08,230 --> 00:09:09,300 Seega sõltub meie vaatenurgast. 213 00:09:09,300 --> 00:09:13,390 Kui me tegelikult mõtleme sisendi printf olevaks string, ja 214 00:09:13,390 --> 00:09:16,380 Seetõttu me suuruse mõõtmiseks, mis sisend selle pikkus - nii kutsume 215 00:09:16,380 --> 00:09:17,780 et pikkus n samuti - 216 00:09:17,780 --> 00:09:21,990 Väidetavalt printf on ise suur O n sest see läheb teid n samme 217 00:09:21,990 --> 00:09:24,750 välja trükkida kõik need n tähemärki, kõige tõenäolisem. 218 00:09:24,750 --> 00:09:27,730 Vähemalt sel määral, et me eeldame, et äkki ta kasutab silmus 219 00:09:27,730 --> 00:09:28,560 all kapuuts. 220 00:09:28,560 --> 00:09:30,860 >> Aga me peame vaatama, et koodi seda paremini mõista. 221 00:09:30,860 --> 00:09:33,650 Ja tõepoolest, kui te alustada analüüsida oma algoritme, saate 222 00:09:33,650 --> 00:09:34,900 sõna otseses mõttes teha just seda. 223 00:09:34,900 --> 00:09:37,765 Omamoodi silmamuna oma kood ja mõelda kohta - kõik õige, mul on see ahel 224 00:09:37,765 --> 00:09:41,870 siin või ma pean nested silmuseid siin et kavatseb teha n asjad n korda, 225 00:09:41,870 --> 00:09:46,050 ja saate sortida mõistuse teed läbi koodi, isegi kui see on 226 00:09:46,050 --> 00:09:47,980 pseudokoodi ja mitte tegelikku koodi. 227 00:09:47,980 --> 00:09:49,730 >> Nii kuidas omega n ruudus? 228 00:09:49,730 --> 00:09:53,582 Mis oli algoritm, et parimal juhul ikka võttis n ruudus sammud? 229 00:09:53,582 --> 00:09:54,014 Jah? 230 00:09:54,014 --> 00:09:54,880 >> Publik: [kuuldamatu]. 231 00:09:54,880 --> 00:09:55,900 >> DAVID Malan: Nii valiku sort. 232 00:09:55,900 --> 00:09:59,150 Sest, et probleem on tõesti vähenenud asjaolust, et jälle, ma ei tea, 233 00:09:59,150 --> 00:10:02,600 Olen märganud, praegune väikseim kuni Olen vaadanud kõik darn elemente. 234 00:10:02,600 --> 00:10:08,050 Nii omega, ütleme, n, me lihtsalt tulid üks. 235 00:10:08,050 --> 00:10:09,300 Insertion sorti. 236 00:10:09,300 --> 00:10:12,370 Kui loend juhtub olema järjestatud juba, parimal juhul me lihtsalt 237 00:10:12,370 --> 00:10:15,090 teha üks läbib see, sel hetkel oleme kindlad. 238 00:10:15,090 --> 00:10:17,890 Ja siis, et võiks öelda, olema lineaarne, kindlasti. 239 00:10:17,890 --> 00:10:20,570 >> Aga omega 1? 240 00:10:20,570 --> 00:10:23,790 Millised on parimal juhul võiks võtta pidev sammude arv? 241 00:10:23,790 --> 00:10:27,220 Nii lineaarne otsing, kui sa lihtsalt veab ja element, mida otsid 242 00:10:27,220 --> 00:10:31,000 on õige alguses nimekirja kui see, kui sa oled hakanud oma 243 00:10:31,000 --> 00:10:33,070 lineaarne läbipääsusüsteemid selles nimekirjas. 244 00:10:33,070 --> 00:10:35,180 >> Ja see on tõsi mitmeid asju. 245 00:10:35,180 --> 00:10:37,660 Näiteks isegi binaarne otsing on omega 1. 246 00:10:37,660 --> 00:10:40,310 Sest kui sa saad tõesti darn õnnelik ja Ihan keset 247 00:10:40,310 --> 00:10:42,950 oma massiiv on number otsite? 248 00:10:42,950 --> 00:10:45,730 Nii saad õnnelik seal samuti. 249 00:10:45,730 --> 00:10:49,190 >> See üks lõpuks omega n log n. 250 00:10:49,190 --> 00:10:52,573 Nii n log n, me tegelikult ei rääkida, aga - 251 00:10:52,573 --> 00:10:53,300 >> Publik: Merge sort? 252 00:10:53,300 --> 00:10:53,960 >> DAVID Malan: Merge sort. 253 00:10:53,960 --> 00:10:56,920 See oli pinge on viimane kord, kui tegime ettepaneku, ja me näitasime 254 00:10:56,920 --> 00:10:58,600 visuaalselt, et on olemas algoritme. 255 00:10:58,600 --> 00:11:02,470 Ja liita omamoodi lihtsalt üks selline algoritm, mis on põhimõtteliselt kiiremini 256 00:11:02,470 --> 00:11:03,450 kui mõned neist teised poisid. 257 00:11:03,450 --> 00:11:07,800 Tegelikult ühendada lühike on mitte ainult Parimal juhul n log n, halvimal 258 00:11:07,800 --> 00:11:09,460 juhul n log n. 259 00:11:09,460 --> 00:11:14,540 Ja kui teil on see kokkusattumus omega ja suur O on sama asi? 260 00:11:14,540 --> 00:11:17,310 Me saame tegelikult kirjeldada, et mis nimega beta, kuigi see on 261 00:11:17,310 --> 00:11:18,220 veidi vähem levinud. 262 00:11:18,220 --> 00:11:21,730 Aga see tähendab lihtsalt kaks piire, sel juhul on samad. 263 00:11:21,730 --> 00:11:25,770 >> Nii ühendab sort, mida see tegelikult taandub meie jaoks? 264 00:11:25,770 --> 00:11:27,000 Noh, meenutada motivatsiooni. 265 00:11:27,000 --> 00:11:30,340 Las ma tõmba teine ​​animatsioon me ei vaata viimast korda. 266 00:11:30,340 --> 00:11:33,390 See üks, sama idee, kuid see on veidi suurem. 267 00:11:33,390 --> 00:11:36,160 Ja ma lähen edasi minna ja rõhutada esimene - meil sisestamise sorteerida 268 00:11:36,160 --> 00:11:39,410 top vasakule, siis valiku sorteerida, mull sorteerida, paar teist liiki - 269 00:11:39,410 --> 00:11:42,670 kest ja kiire - et me ei rääkinud kohta, ja hunnik ja ühendada sort. 270 00:11:42,670 --> 00:11:47,090 >> Nii vähemalt proovida keskenduda oma silmad esikolmikusse vasakul ja seejärel 271 00:11:47,090 --> 00:11:49,120 Tarkvaraprojekteerimise Napsautan see roheline nool. 272 00:11:49,120 --> 00:11:51,900 Aga ma lasen nad kõik kulgema, lihtsalt annab teile tunde mitmekesisust 273 00:11:51,900 --> 00:11:53,980 algoritme, mis on olemas kogu maailmas. 274 00:11:53,980 --> 00:11:56,180 Ma lasen selle run vaid paar sekundit. 275 00:11:56,180 --> 00:11:59,640 Ja kui teil keskenduda oma silmi - vali algoritm, keskendub ta vaid 276 00:11:59,640 --> 00:12:02,970 sekundit - saate hakata näha muster, et see rakendatakse. 277 00:12:02,970 --> 00:12:04,530 >> Merge sort, teate, on tehtud. 278 00:12:04,530 --> 00:12:06,430 Heap sort, kiire sort, koorimata - 279 00:12:06,430 --> 00:12:09,480 nii tundub tutvustasime kolm halvim algoritme eelmisel nädalal. 280 00:12:09,480 --> 00:12:12,960 Aga see on hea, et me oleme täna siin, et vaata Tarkvaraprojekteerimise, mis on üks 281 00:12:12,960 --> 00:12:16,500 lihtsam ones on vaadata, isegi kuigi see ilmselt painutada meelt 282 00:12:16,500 --> 00:12:17,490 natuke. 283 00:12:17,490 --> 00:12:21,130 Siin näeme, kui palju valik omamoodi jama. 284 00:12:21,130 --> 00:12:24,600 >> Aga Tagakülg, see on tõesti lihtne rakendada. 285 00:12:24,600 --> 00:12:28,160 Ja võibolla P Set 3, mis on üks algoritme valisid rakendada 286 00:12:28,160 --> 00:12:28,960 jaoks standard edition. 287 00:12:28,960 --> 00:12:30,970 Täiesti korras, täiesti õige. 288 00:12:30,970 --> 00:12:35,210 >> Aga jälle, kui n saab suur, kui te soovi korral rakendada kiiremini algoritm 289 00:12:35,210 --> 00:12:39,020 meeldib liita sort, koefitsiendid on suurem ja suurem sisendite teie kood on lihtsalt 290 00:12:39,020 --> 00:12:39,800 läheb kiiremini töötada. 291 00:12:39,800 --> 00:12:41,090 Teie koduleheküljel läheb paremini. 292 00:12:41,090 --> 00:12:42,650 Kasutajad saavad olema õnnelikumad. 293 00:12:42,650 --> 00:12:45,280 Ja nii on nende mõjude tegelikult annab 294 00:12:45,280 --> 00:12:47,350 meile mõned sügavamad arvasin. 295 00:12:47,350 --> 00:12:49,990 >> Võtame pilk liita sort on tegelikult kõike. 296 00:12:49,990 --> 00:12:52,992 Lahe asi on see, et ühendada sort on just see. 297 00:12:52,992 --> 00:12:56,300 See on jällegi see, mida me oleme kutsutud pseudokoodi, pseudokoodi olend 298 00:12:56,300 --> 00:12:57,720 Inglise-like süntaks. 299 00:12:57,720 --> 00:12:59,890 Ja lihtsus on omamoodi põnev. 300 00:12:59,890 --> 00:13:02,840 >> Nii on sisend n elemente - nii et tähendab lihtsalt, siin on massiiv. 301 00:13:02,840 --> 00:13:04,000 See sai n asju ta. 302 00:13:04,000 --> 00:13:05,370 See on kõik, mida me ütleme seal. 303 00:13:05,370 --> 00:13:07,560 >> Kui n on väiksem kui 2 tagasi. 304 00:13:07,560 --> 00:13:08,640 Nii et lihtsalt triviaalne puhul. 305 00:13:08,640 --> 00:13:12,580 Kui n on väiksem kui 2, siis ilmselt on see 1 või 0, mille puhul asi 306 00:13:12,580 --> 00:13:14,780 on juba järjestatud või olematu, nii lihtsalt tagasi. 307 00:13:14,780 --> 00:13:15,900 Ei ole midagi teha. 308 00:13:15,900 --> 00:13:18,360 Nii et see on lihtne asi kisu maha. 309 00:13:18,360 --> 00:13:20,110 >> Else, meil on kolm etappi. 310 00:13:20,110 --> 00:13:23,650 Sorteeri vasakul poolel elemente, sorteerida paremal pool elemendid, 311 00:13:23,650 --> 00:13:26,650 ja siis liita järjestatud pooleks. 312 00:13:26,650 --> 00:13:29,400 Huvitav on see, et Ma olen selline punting, eks? 313 00:13:29,400 --> 00:13:32,300 Seal on selline ümmargune definitsioon Selle algoritmi. 314 00:13:32,300 --> 00:13:35,986 Mis mõttes on see algoritm on määratlus ümmargune? 315 00:13:35,986 --> 00:13:37,850 >> Publik: [kuuldamatu]. 316 00:13:37,850 --> 00:13:41,670 >> DAVID Malan: Jah, minu sorteerimise algoritm, kaks tema sammud on "omamoodi 317 00:13:41,670 --> 00:13:44,640 midagi. "Ja nii see tekitab küsimus, noh, mida ma ei kavatse kasutada 318 00:13:44,640 --> 00:13:46,460 sorteerida vasakul pool ja paremal pool? 319 00:13:46,460 --> 00:13:49,600 Ja ilu on selles, et kuigi Jällegi, see on Hallutsinatsioone 320 00:13:49,600 --> 00:13:54,030 osa potentsiaalselt võid kasutada sama algoritm sorteerida vasakul pool. 321 00:13:54,030 --> 00:13:54,700 >> Kuid oodake minut. 322 00:13:54,700 --> 00:13:57,070 Kui sulle öeldakse, et järjestada vasakul pool, mis on kaks 323 00:13:57,070 --> 00:13:58,240 samme saab olema järgmine? 324 00:13:58,240 --> 00:14:00,550 Me sorteerida vasakul poolel vasakul pool ja paremal 325 00:14:00,550 --> 00:14:01,420 pool vasakul pool. 326 00:14:01,420 --> 00:14:04,430 Kurat, kuidas ma sorteeri need kaks pooleks, või kvartalite nüüd? 327 00:14:04,430 --> 00:14:05,260 >> Aga see on OK. 328 00:14:05,260 --> 00:14:07,830 Meil on sorteerimise algoritm siin. 329 00:14:07,830 --> 00:14:10,660 Ja kuigi võite muretsema juures esimene see on selline lõputu 330 00:14:10,660 --> 00:14:12,780 loop, see on tsükkel, mis kunagi läheb lõpuks - see läheb 331 00:14:12,780 --> 00:14:15,770 lõpeb siis, kui see, mis juhtub? 332 00:14:15,770 --> 00:14:16,970 Kui n on väiksem kui 2. 333 00:14:16,970 --> 00:14:19,180 Mis lõpuks juhtub, sest kui te ei hoia poole võrra ja 334 00:14:19,180 --> 00:14:23,020 vähendamine poole võrra on poole võrra nende pooleks, kindlasti lõpuks sa lähed lõpuni 335 00:14:23,020 --> 00:14:25,350 koos vaid 1 või 0 elemente. 336 00:14:25,350 --> 00:14:28,500 Sel hetkel, see algoritm ütleb, et sa oled teinud. 337 00:14:28,500 --> 00:14:31,020 >> Nii et tegelik võlu selles algoritm tundub olevat 338 00:14:31,020 --> 00:14:33,470 et viimane samm, ühinevad. 339 00:14:33,470 --> 00:14:37,190 See lihtne mõte lihtsalt ühendada kaks asjad, mis on see, mida on lõppkokkuvõttes läheb 340 00:14:37,190 --> 00:14:40,920 et võimaldada meil sorteerida massiivi, ütleme, kaheksa elemente. 341 00:14:40,920 --> 00:14:44,410 Nii et mul on veel kaheksa stress pallid üles Siin kaheksa paberitükke ja üks 342 00:14:44,410 --> 00:14:45,500 Google Glass - 343 00:14:45,500 --> 00:14:46,140 mis ma saan hoida. 344 00:14:46,140 --> 00:14:46,960 >> [Naer] 345 00:14:46,960 --> 00:14:48,970 >> DAVID Malan: Kui me võiksime võtta kaheksa vabatahtlike, ja vaatame, kas me saame 346 00:14:48,970 --> 00:14:51,430 mängida seda välja, nii et. 347 00:14:51,430 --> 00:14:52,500 Wow, OK. 348 00:14:52,500 --> 00:14:53,565 Arvutiteadus muutub lõbus. 349 00:14:53,565 --> 00:14:54,320 Hea küll. 350 00:14:54,320 --> 00:14:57,770 Niisiis, kuidas te kolm, Suurim käsi seal. 351 00:14:57,770 --> 00:14:58,580 Neli taga. 352 00:14:58,580 --> 00:15:02,220 Ja kuidas me teeme teile kolm selles reas? 353 00:15:02,220 --> 00:15:03,390 Ja neli ees. 354 00:15:03,390 --> 00:15:04,920 Nii et sa kaheksa, tulge siia. 355 00:15:04,920 --> 00:15:12,060 >> [Naer] 356 00:15:12,060 --> 00:15:13,450 >> DAVID Malan: ma olen tegelikult ei ole kindel, mis see on. 357 00:15:13,450 --> 00:15:14,810 Kas see stress pallid? 358 00:15:14,810 --> 00:15:16,510 Laualambid? 359 00:15:16,510 --> 00:15:18,650 Materjal? 360 00:15:18,650 --> 00:15:19,680 Internet? 361 00:15:19,680 --> 00:15:20,160 >> OK. 362 00:15:20,160 --> 00:15:21,310 Nii et tulge siia. 363 00:15:21,310 --> 00:15:22,310 Kes soovib - 364 00:15:22,310 --> 00:15:23,570 hoida tulemas. 365 00:15:23,570 --> 00:15:24,240 Vaatame. 366 00:15:24,240 --> 00:15:26,460 Ja see paneb sind asukoht - 367 00:15:26,460 --> 00:15:27,940 sa oled kohas üks. 368 00:15:27,940 --> 00:15:28,670 Uh-oh, oota natuke. 369 00:15:28,670 --> 00:15:30,760 1, 2, 3, 4, 5, 6, 7 - oh, hea. 370 00:15:30,760 --> 00:15:31,310 Olgu, me oleme head. 371 00:15:31,310 --> 00:15:35,130 Olgu, nii et igaüks istet, kuid mitte Google Klaas. 372 00:15:35,130 --> 00:15:36,475 Lubage mul sabas need üles. 373 00:15:36,475 --> 00:15:37,115 Mis su nimi on? 374 00:15:37,115 --> 00:15:37,440 >> MICHELLE: Michelle. 375 00:15:37,440 --> 00:15:38,090 >> DAVID Malan: Michelle? 376 00:15:38,090 --> 00:15:42,000 Olgu, sa saad nägema geek, kui see on OK. 377 00:15:42,000 --> 00:15:44,625 Noh, mina ka, ma arvan, hetkeks. 378 00:15:44,625 --> 00:15:45,875 Olgu, ooterežiimis. 379 00:15:45,875 --> 00:15:48,510 380 00:15:48,510 --> 00:15:50,950 Oleme püüdnud tulla kasutada juhul Google Klaas ja me 381 00:15:50,950 --> 00:15:53,750 arvasin, et see oleks tore lihtsalt teha see, kui inimesed on laval. 382 00:15:53,750 --> 00:15:57,120 Me salvestame maailma vaatenurgast. 383 00:15:57,120 --> 00:15:58,410 Hea küll. 384 00:15:58,410 --> 00:15:59,830 Pole ilmselt mida Google ette. 385 00:15:59,830 --> 00:16:02,260 Olgu, kui sa ei pahanda seljas see järgmiseks ebamugav minuti 386 00:16:02,260 --> 00:16:03,150 et oleks tore. 387 00:16:03,150 --> 00:16:08,620 >> Olgu, meil on siin hulgaliselt elemente ja et massiivi kohta 388 00:16:08,620 --> 00:16:11,480 paberitükid need inimesed " käed, praegu sortimata. 389 00:16:11,480 --> 00:16:12,050 >> MICHELLE: Oh, see on nii imelik. 390 00:16:12,050 --> 00:16:12,810 >> DAVID Malan: See on päris palju juhuslikult. 391 00:16:12,810 --> 00:16:15,760 Ja üks hetk, me ei kavatse proovida rakendada Tarkvaraprojekteerimise kokku 392 00:16:15,760 --> 00:16:17,950 ja vaata, kui see Võtmeküsimuseks on. 393 00:16:17,950 --> 00:16:21,970 Ja trikk siin Tarkvaraprojekteerimise on midagi, mida me ei ole endale veel. 394 00:16:21,970 --> 00:16:24,030 Me tegelikult vajan lisaruumi. 395 00:16:24,030 --> 00:16:26,650 Mis siis saab olema eriti Huvitav on see, et need 396 00:16:26,650 --> 00:16:29,270 poisid hakkavad liikuda vähe natuke, sest ma lähen eeldada, et 397 00:16:29,270 --> 00:16:31,880 seal on ekstra massiivi ruumi öelda, eks nende taga. 398 00:16:31,880 --> 00:16:34,570 >> Nii et kui nad on jäänud oma tool, see on sekundaarne massiivi. 399 00:16:34,570 --> 00:16:36,960 Kui nad istuvad siin, see on esmane massiivi. 400 00:16:36,960 --> 00:16:40,170 Aga see on ressurss, mis meil on ole võimendatud seni mulli 401 00:16:40,170 --> 00:16:42,040 sort ja valida sort, koos nende sort. 402 00:16:42,040 --> 00:16:44,600 Meenuta eelmisel nädalal kõigile lihtsalt liiki segatud paigas. 403 00:16:44,600 --> 00:16:46,840 Nad ei kasuta ühtegi täiendavat mälu. 404 00:16:46,840 --> 00:16:49,310 Tegime ruumi inimesi liikuvad inimesed ümber. 405 00:16:49,310 --> 00:16:50,580 >> Nii et see on oluline mõista ka. 406 00:16:50,580 --> 00:16:53,410 Seal on see kompromiss, üldiselt infotehnoloogia vahendeid. 407 00:16:53,410 --> 00:16:55,800 Kui soovite, et kiirendada midagi nagu aeg, sa lähed 408 00:16:55,800 --> 00:16:56,900 peavad maksma hinda. 409 00:16:56,900 --> 00:17:00,750 Ja üks neist, hinnad on väga sageli ruum, mälu või kõva 410 00:17:00,750 --> 00:17:01,700 kettaruumi, et te kasutate. 411 00:17:01,700 --> 00:17:03,640 Või ausalt, summa programmeerija aega. 412 00:17:03,640 --> 00:17:06,700 Kui palju aega kulub teil, inimese, tegelikult rakendada veidi rohkem 413 00:17:06,700 --> 00:17:07,829 keeruline algoritm. 414 00:17:07,829 --> 00:17:09,760 Aga täna, kaubandus-off on ajas ja ruumis. 415 00:17:09,760 --> 00:17:11,930 >> Nii et kui te poisid võiks lihtsalt hoida oma numbrid, et me näeme, et sa oled 416 00:17:11,930 --> 00:17:15,839 tõepoolest sobitamine 4, 2, 6, 1, 3, 7, 8. 417 00:17:15,839 --> 00:17:16,599 Suurepärane. 418 00:17:16,599 --> 00:17:19,520 Nii et ma lähen püüta asjad, siis kui sa suudad lihtsalt 419 00:17:19,520 --> 00:17:21,800 jälgi mind siin. 420 00:17:21,800 --> 00:17:26,650 >> Nii ma rakendada esiteks Esimene samm pseudokoodi, mis on 421 00:17:26,650 --> 00:17:29,440 on sisend n elementi, kui n on vähem kui 2, siis tagasi. 422 00:17:29,440 --> 00:17:31,370 Ilmselt see ei sätteid, et me liigume edasi. 423 00:17:31,370 --> 00:17:33,340 Nii sorteerida vasakul poolel elemente. 424 00:17:33,340 --> 00:17:36,220 See tähendab, et ma lähen keskenduda oma tähelepanu hetkeks nendel 425 00:17:36,220 --> 00:17:37,310 neli poisid siin. 426 00:17:37,310 --> 00:17:39,774 Olgu, mida ma järgmisena teha? 427 00:17:39,774 --> 00:17:40,570 >> Publik: Sorteeri vasakul pool. 428 00:17:40,570 --> 00:17:42,780 >> DAVID Malan: Nüüd pean sortida vasakul pool need kutid. 429 00:17:42,780 --> 00:17:45,580 Sest jällegi oletada, et ise eesmärk on sorteerida vasakul pool. 430 00:17:45,580 --> 00:17:46,440 Kuidas sa seda tegid? 431 00:17:46,440 --> 00:17:49,140 Jälgi juhiseid, isegi kuigi me teeme seda jälle. 432 00:17:49,140 --> 00:17:50,160 Nii sorteerida vasakul pool. 433 00:17:50,160 --> 00:17:52,030 Nüüd ma sorteerimine need kaks venda. 434 00:17:52,030 --> 00:17:53,563 Mis saab edasi? 435 00:17:53,563 --> 00:17:54,510 >> Publik: Sorteeri vasakul pool. 436 00:17:54,510 --> 00:17:55,460 >> DAVID Malan: Sorteeri vasakul pool. 437 00:17:55,460 --> 00:18:00,680 Nüüd need, see koht on siin, on nimekiri suurus 1. 438 00:18:00,680 --> 00:18:01,365 Ja mis su nimi oligi? 439 00:18:01,365 --> 00:18:02,390 >> PRINCESS DAISY: Princess Daisy. 440 00:18:02,390 --> 00:18:03,690 >> DAVID Malan: Princess Daisy on siin. 441 00:18:03,690 --> 00:18:07,470 Ja nii ta on juba järjestatud, sest nimekiri on suurus 1. 442 00:18:07,470 --> 00:18:09,490 Mida ma järgmisena teha? 443 00:18:09,490 --> 00:18:13,680 OK, tagasi, sest see nimekiri on suurus 1, mis on väiksem kui 2. 444 00:18:13,680 --> 00:18:14,320 Siis milline on järgmine samm? 445 00:18:14,320 --> 00:18:17,490 Ja nüüd on selline Taganeda meelt. 446 00:18:17,490 --> 00:18:19,340 >> Sorteeri paremal pool, mis on - 447 00:18:19,340 --> 00:18:19,570 Mis su nimi on? 448 00:18:19,570 --> 00:18:20,220 >> LINDA: Linda. 449 00:18:20,220 --> 00:18:20,980 >> DAVID Malan: Linda. 450 00:18:20,980 --> 00:18:23,210 Ja mis me nüüd teeme, et Meil on nimekiri suurus 1? 451 00:18:23,210 --> 00:18:24,440 >> Publik: Return. 452 00:18:24,440 --> 00:18:24,760 >> DAVID Malan: Ettevaatust. 453 00:18:24,760 --> 00:18:29,540 Me naaseme esimene ja nüüd kolmas samm - ja kui ma mingi kujutada seda 454 00:18:29,540 --> 00:18:33,490 omaks kaks istet nüüd, nüüd ma on ühendada need kaks elementi. 455 00:18:33,490 --> 00:18:35,530 Nüüd kahjuks elemendid on rikkis. 456 00:18:35,530 --> 00:18:39,920 Aga see, kui ühinevad protsessi hakkab saama veenvad. 457 00:18:39,920 --> 00:18:42,410 >> Nii et kui te ei seisa lihtsalt Hetkeks ma vajan sind, et 458 00:18:42,410 --> 00:18:44,170 Praegu sammu taga oma tool. 459 00:18:44,170 --> 00:18:46,480 Ja kui Linda, sest 2 on väiksem kui 4, siis miks mitte 460 00:18:46,480 --> 00:18:48,130 sa tuled ümber esimesena? 461 00:18:48,130 --> 00:18:48,690 Seal viibida. 462 00:18:48,690 --> 00:18:50,520 Nii Linda, tule ümber esimese. 463 00:18:50,520 --> 00:18:53,820 >> Nüüd tegelikult kui see on lihtsalt massiivi me võiks lihtsalt liikuda oma reaalajas 464 00:18:53,820 --> 00:18:55,360 selle tooli selle koha. 465 00:18:55,360 --> 00:18:57,770 Nii kujutan ette, et võttis mõned pidev mitmeid samme 1. 466 00:18:57,770 --> 00:18:58,480 Ja nüüd - 467 00:18:58,480 --> 00:19:01,490 kuid me peame teile Esimene asukoha. 468 00:19:01,490 --> 00:19:03,930 >> Ja nüüd, kui te võiks tulla ringi, samuti me läheme 469 00:19:03,930 --> 00:19:06,300 olema asukoha kaks. 470 00:19:06,300 --> 00:19:09,120 Ja kuigi see tundub nii võttes samal ajal, mis on tore praegu 471 00:19:09,120 --> 00:19:14,710 et vasakul poolel vasakul pool on nüüd järjestatud. 472 00:19:14,710 --> 00:19:18,010 Mis siis oli järgmine samm, kui me nüüd kerida edasi lugu? 473 00:19:18,010 --> 00:19:18,980 >> Publik: Parem pool. 474 00:19:18,980 --> 00:19:19,900 >> DAVID Malan: Sorteeri paremal pool. 475 00:19:19,900 --> 00:19:21,320 Nii et te ei pea seda tegema, samuti. 476 00:19:21,320 --> 00:19:23,510 Nii et kui sa võiksid seista hetkeks? 477 00:19:23,510 --> 00:19:25,192 Ja mis sinu nimi on? 478 00:19:25,192 --> 00:19:25,540 >> JESS: Jess. 479 00:19:25,540 --> 00:19:25,870 >> DAVID Malan: Jess. 480 00:19:25,870 --> 00:19:29,720 OK, nii et Jess on nüüd vasakul poole paremal poolel. 481 00:19:29,720 --> 00:19:31,400 Ja nii ta on nimekiri suurus 1. 482 00:19:31,400 --> 00:19:32,380 Ta ilmselt sorteerida. 483 00:19:32,380 --> 00:19:33,070 Ja su nimi oligi? 484 00:19:33,070 --> 00:19:33,630 >> MICHELLE: Michelle. 485 00:19:33,630 --> 00:19:35,340 >> DAVID Malan: Michelle on ilmselt nimekirja suurus 1. 486 00:19:35,340 --> 00:19:36,050 Ta on juba järjestatud. 487 00:19:36,050 --> 00:19:38,690 Nüüd magic juhtub, ühinevate protsessi. 488 00:19:38,690 --> 00:19:39,790 Nii et kes tulemas esimene? 489 00:19:39,790 --> 00:19:41,560 Ilmselt Michelle. 490 00:19:41,560 --> 00:19:43,280 Nii et kui sa võiks tulla umbes tagasi. 491 00:19:43,280 --> 00:19:47,090 Ruumi on meil olemas oma nüüd on õigus selle taga tool siin. 492 00:19:47,090 --> 00:19:51,580 Ja nüüd, kui te saaksite tagasi tulla ka, meil on nüüd, et oleks selge, kaks 493 00:19:51,580 --> 00:19:53,810 pooleks, kusjuures suurus 2 - 494 00:19:53,810 --> 00:19:57,090 ja lihtsalt kirjeldus pärast, kui te võiks teha natuke ruumi - 495 00:19:57,090 --> 00:19:59,780 üks vasakul pool siin, üks paremale poole siin. 496 00:19:59,780 --> 00:20:01,160 >> Keri edasi lugu. 497 00:20:01,160 --> 00:20:02,270 Mis samm on järgmine? 498 00:20:02,270 --> 00:20:03,030 >> Publik: Merge. 499 00:20:03,030 --> 00:20:04,160 >> DAVID Malan: Nüüd on meil ühineda. 500 00:20:04,160 --> 00:20:07,490 Nii OK, nüüd õnneks me lihtsalt vabanenud neli tooli. 501 00:20:07,490 --> 00:20:11,480 Nii et me oleme kasutatakse kaks korda rohkem mälu, kuid saame anda flip-flopping vahel 502 00:20:11,480 --> 00:20:12,330 kaks massiivid. 503 00:20:12,330 --> 00:20:14,190 Nii et mis number on esikohal? 504 00:20:14,190 --> 00:20:14,850 Nii Michelle ilmselt. 505 00:20:14,850 --> 00:20:16,680 Nii tulevad ümber ja võtma oma kohale siin. 506 00:20:16,680 --> 00:20:19,120 Ja siis number 2 on ilmselt Järgmine, siis tule siia. 507 00:20:19,120 --> 00:20:21,520 Number 4, number 6. 508 00:20:21,520 --> 00:20:23,390 Ja veel, kuigi seal on natuke jalgsi kaasatud 509 00:20:23,390 --> 00:20:26,010 tõesti, need võib juhtuda koheselt, liigutades üks - 510 00:20:26,010 --> 00:20:26,880 OK, hästi mängitud. 511 00:20:26,880 --> 00:20:28,350 >> [Naer] 512 00:20:28,350 --> 00:20:29,680 >> DAVID Malan: Ja nüüd me oleme päris heas seisus. 513 00:20:29,680 --> 00:20:34,910 Vasakul pool kogu sisend on nüüd järjestatud. 514 00:20:34,910 --> 00:20:37,370 Olgu, need kutid olid ära mu - 515 00:20:37,370 --> 00:20:40,340 kuidas see lõpuks kõik tüdrukud vasakule ja kõik poisid paremal? 516 00:20:40,340 --> 00:20:42,450 >> OK, nii poisid "kord nüüd. 517 00:20:42,450 --> 00:20:44,680 Nii et ma ei sõelub neid samme. 518 00:20:44,680 --> 00:20:46,550 Eks me näe, kas me saame uuesti Samal pseudokoodi. 519 00:20:46,550 --> 00:20:50,050 Kui soovite minna ja seista, ja teid, lubage mul anda teile mic. 520 00:20:50,050 --> 00:20:52,990 Vaata, kas sa ei saa dubleerida seda, mida me tegime siin 521 00:20:52,990 --> 00:20:53,880 muu loendi lõppu. 522 00:20:53,880 --> 00:20:59,530 Kes peab rääkima kõigepealt, põhineb algoritm? 523 00:20:59,530 --> 00:21:03,210 Nii selgitab, mida sa teed enne Te teete suu liigutusi. 524 00:21:03,210 --> 00:21:05,930 >> SPEAKER 1: Olgu, kuna Ma olen vasakul pool 525 00:21:05,930 --> 00:21:07,790 vasakul pool, ma tagasi. 526 00:21:07,790 --> 00:21:08,730 Õigus? 527 00:21:08,730 --> 00:21:09,250 >> DAVID Malan: Hea. 528 00:21:09,250 --> 00:21:10,350 >> SPEAKER 1: Ja siis - 529 00:21:10,350 --> 00:21:11,800 >> DAVID Malan: Kes mic minna edasi? 530 00:21:11,800 --> 00:21:12,920 >> SPEAKER 1: Järgmine number. 531 00:21:12,920 --> 00:21:14,720 >> SPEAKER 2: Nii et ma olen parem pool on vasakul pool 532 00:21:14,720 --> 00:21:17,830 vasakul pool, ja ma tagasi. 533 00:21:17,830 --> 00:21:18,050 >> DAVID Malan: Hea. 534 00:21:18,050 --> 00:21:18,550 Naasete. 535 00:21:18,550 --> 00:21:21,855 Nüüd mis on järgmine kuni teile kaks? 536 00:21:21,855 --> 00:21:23,740 >> SPEAKER 2: Me tahame näha, kes on väiksem. 537 00:21:23,740 --> 00:21:24,200 >> DAVID Malan: Täpselt. 538 00:21:24,200 --> 00:21:24,940 Me tahame ühendada. 539 00:21:24,940 --> 00:21:27,590 Ruumi me ei kavatse kasutada ühendada teid, kuigi need on 540 00:21:27,590 --> 00:21:30,250 ilmselt järjestatud juba, me ei kavatse järgima sama algoritmi. 541 00:21:30,250 --> 00:21:31,560 Niisiis, kes läheb tagasi esimene? 542 00:21:31,560 --> 00:21:35,720 Nii 3 ja siis 7. 543 00:21:35,720 --> 00:21:38,570 Ja nüüd mic läheb et need kutid, OK? 544 00:21:38,570 --> 00:21:43,590 >> SPEAKER 3: Nii et ma olen paremal pool vasakul pool ja minu n on väiksem kui 545 00:21:43,590 --> 00:21:45,048 1, nii et ma olen lihtsalt läheb edasi - 546 00:21:45,048 --> 00:21:46,380 >> DAVID Malan: Hea. 547 00:21:46,380 --> 00:21:49,450 >> SPEAKER 4: Ma olen paremal pool paremale poole paremal poolel, ja ma olen 548 00:21:49,450 --> 00:21:51,740 ka üks inimene, nii et ma olen läheb tagasi. 549 00:21:51,740 --> 00:21:52,990 Nüüd me ühinevad. 550 00:21:52,990 --> 00:21:55,140 551 00:21:55,140 --> 00:21:56,150 >> SPEAKER 3: Nii et me tagasi minna. 552 00:21:56,150 --> 00:21:57,160 >> DAVID Malan: Nii et te lähete tagasi. 553 00:21:57,160 --> 00:21:59,200 Nii 5 läheb esimesena, seejärel 8. 554 00:21:59,200 --> 00:22:01,240 Ja nüüd publik, mis on astuma peame nüüd tagasi kerida 555 00:22:01,240 --> 00:22:02,200 tagasi meie mõtetes? 556 00:22:02,200 --> 00:22:02,940 >> Publik: Merge. 557 00:22:02,940 --> 00:22:07,270 >> DAVID Malan: Ühinevad vasakul pool ja paremal pool esialgsest vasakul pool. 558 00:22:07,270 --> 00:22:08,840 Nüüd - 559 00:22:08,840 --> 00:22:10,520 ja lihtsalt selgeks teha, teha natuke ruumi 560 00:22:10,520 --> 00:22:11,690 teie kahe vahel kutid. 561 00:22:11,690 --> 00:22:13,800 Nüüd, et on kaks nimekirja, vasakule ja paremale. 562 00:22:13,800 --> 00:22:18,320 Niisiis, kuidas me nüüd ühendada te poisid ees istmerida jälle? 563 00:22:18,320 --> 00:22:19,600 >> 3 läheb esimesena. 564 00:22:19,600 --> 00:22:20,850 Siis 5, ilmselt. 565 00:22:20,850 --> 00:22:23,110 566 00:22:23,110 --> 00:22:27,330 Siis 7 ja nüüd 8. 567 00:22:27,330 --> 00:22:28,710 OK, ja nüüd me oleme? 568 00:22:28,710 --> 00:22:29,650 >> Publik: Ei kärbita. 569 00:22:29,650 --> 00:22:32,440 >> DAVID Malan: Ei ole tehtud, kuna Ilmselt seal on üks samm jäänud. 570 00:22:32,440 --> 00:22:35,720 Aga jälle, miks ma olen, kasutades seda kõnepruugis nagu "tagasikerimine meelt," 571 00:22:35,720 --> 00:22:37,160 see on, sest see on tõesti mis toimub. 572 00:22:37,160 --> 00:22:39,610 Me läheme läbi kõik need sammud, aga me oleme omamoodi tõmbamata 573 00:22:39,610 --> 00:22:42,480 hetk, sukeldumine sügavamale algoritm, peatades hetkeks 574 00:22:42,480 --> 00:22:45,840 sukeldumine sügavamale algoritm, ja nüüd peame omamoodi tagurpidi meie 575 00:22:45,840 --> 00:22:49,430 mõtetes ja tühistada kõik need kihid et me oleme justkui ootele. 576 00:22:49,430 --> 00:22:51,790 >> Nüüd on meil kaks nimekirjad suurus 4. 577 00:22:51,790 --> 00:22:54,790 Kui te võiks püsti viimast korda ja teha natuke ruumi siia 578 00:22:54,790 --> 00:22:57,230 selgeks teha, et see on vasakul pool originaal, 579 00:22:57,230 --> 00:22:58,620 paremale poole originaal. 580 00:22:58,620 --> 00:23:01,060 Kes on esimene number, et me pead tõmba tagasi? 581 00:23:01,060 --> 00:23:01,870 Michelle, muidugi. 582 00:23:01,870 --> 00:23:03,230 >> Nii paneme Michelle siin. 583 00:23:03,230 --> 00:23:05,080 Ja kes on number 2? 584 00:23:05,080 --> 00:23:06,440 Number 2 süttib tagasi samuti. 585 00:23:06,440 --> 00:23:07,800 Number 3? 586 00:23:07,800 --> 00:23:08,510 Suurepärane. 587 00:23:08,510 --> 00:23:16,570 Number 4, number 5, number 6, number 7 ja number 8. 588 00:23:16,570 --> 00:23:18,850 >> OK, nii see tundus palju samme, kindlasti. 589 00:23:18,850 --> 00:23:22,390 Aga nüüd vaatame, kui me ei saa kinnitada, omamoodi intuitiivselt, et see 590 00:23:22,390 --> 00:23:26,190 algoritm põhimõtteliselt, eriti n saab tõesti suur, sest me oleme näinud 591 00:23:26,190 --> 00:23:29,170 koos animatsioonid, on põhimõtteliselt kiiremini. 592 00:23:29,170 --> 00:23:33,400 Nii et ma väita seda algoritmi, halvimal juhul ja isegi parimal juhul 593 00:23:33,400 --> 00:23:36,160 on suur O n korda log n. 594 00:23:36,160 --> 00:23:39,160 See tähendab, et seal on mõned aspekt algoritm, mis võtab n samme, kuid 595 00:23:39,160 --> 00:23:43,110 seal on teine ​​aspekt kusagil et iteratsiooni et silmukoiminen, et 596 00:23:43,110 --> 00:23:44,410 võtab log n samme. 597 00:23:44,410 --> 00:23:49,154 Kas me paneme oma sõrme, millised need kaks numbrit viitavad? 598 00:23:49,154 --> 00:23:51,320 Noh, kus - 599 00:23:51,320 --> 00:23:54,160 Kust mic minna? 600 00:23:54,160 --> 00:23:58,660 >> SPEAKER 1: kas sisse n purustamine meid kaheks - 601 00:23:58,660 --> 00:23:59,630 jagades kaks sisuliselt. 602 00:23:59,630 --> 00:24:00,120 >> DAVID Malan: Täpselt. 603 00:24:00,120 --> 00:24:03,000 Iga kord, kui me näeme iga algoritm seega kaugele, et siin on see muster 604 00:24:03,000 --> 00:24:04,200 jagamisel, vahesein, jagades. 605 00:24:04,200 --> 00:24:05,700 Ja see on tavaliselt vähendada midagi, mis on 606 00:24:05,700 --> 00:24:07,100 logaritmiline, logaritm alusel 2. 607 00:24:07,100 --> 00:24:10,180 Aga see võib tõesti olla midagi, kuid sisse alus 2. 608 00:24:10,180 --> 00:24:11,330 >> Mida aga n? 609 00:24:11,330 --> 00:24:14,550 Ma näen, et meil selline jagatud sa poisid - jagatud teid jagada teile, 610 00:24:14,550 --> 00:24:15,910 jagatud teile jagatud teile. 611 00:24:15,910 --> 00:24:18,760 Kuhu see lõpuks tuli? 612 00:24:18,760 --> 00:24:19,810 >> Nii et see on ühinevate. 613 00:24:19,810 --> 00:24:20,610 Sest mõelda. 614 00:24:20,610 --> 00:24:25,420 Kui liita kaheksa inimest koos, kusjuures pooled neist on komplekt neljast 615 00:24:25,420 --> 00:24:27,770 ja teine ​​pool on teise komplekt neli, kuidas sa minna 616 00:24:27,770 --> 00:24:28,820 seda teed ühinevad? 617 00:24:28,820 --> 00:24:30,830 Noh, te tegite seda üsna intuitiivselt. 618 00:24:30,830 --> 00:24:34,140 >> Aga kui ma selle asemel tegi seda veidi metoodiliselt, ma oleks osutanud 619 00:24:34,140 --> 00:24:38,090 vasakpoolsema inimene kõigepealt mu vasak Samas osutas vasakpoolsema inimene 620 00:24:38,090 --> 00:24:42,080 selle poole minu paremal käel, ja lihtsalt hiljem kõndis läbi 621 00:24:42,080 --> 00:24:46,990 nimekiri, osutades väikseim element iga kord, liigub mu sõrmi ja 622 00:24:46,990 --> 00:24:48,970 üle kui vaja kogu nimekiri. 623 00:24:48,970 --> 00:24:51,890 Aga mis on võti selle ühinevad protsessi ma võrrelda neid paari 624 00:24:51,890 --> 00:24:53,460 elemente. 625 00:24:53,460 --> 00:24:57,270 Paremalt pool ja vasak pool, ma ei ole kunagi üks samm tagasi võrreldes. 626 00:24:57,270 --> 00:25:00,570 >> Nii ühendamise ise võtab mitte rohkem kui n samme. 627 00:25:00,570 --> 00:25:03,250 Ja mitu korda tegin ma mida teha, et ühinevad? 628 00:25:03,250 --> 00:25:07,150 Noh, mitte rohkem kui n, ja me lihtsalt nägin, et selle lõpliku ühendamisega. 629 00:25:07,150 --> 00:25:13,120 Ja kui te teete midagi, mis võtab logi n sammud n korda, või vastupidi, 630 00:25:13,120 --> 00:25:15,210 see läheb meile n korda log n. 631 00:25:15,210 --> 00:25:16,310 >> Ja miks see nii on parem? 632 00:25:16,310 --> 00:25:19,600 Noh, kui me juba teame, et register n on parem kui n - eks? 633 00:25:19,600 --> 00:25:22,590 Nägime binaarne otsing, telefoniraamat Näiteks log n oli kindlasti 634 00:25:22,590 --> 00:25:23,760 parem kui lineaarne. 635 00:25:23,760 --> 00:25:28,420 Nii et see tähendab n korda log n on kindlasti parem kui n korda teine 636 00:25:28,420 --> 00:25:30,390 n, AKA n ruudus. 637 00:25:30,390 --> 00:25:32,400 Ja see, mida me lõpuks tunne. 638 00:25:32,400 --> 00:25:34,928 >> Nii suur aplaus, kui Võiksime need kutid. 639 00:25:34,928 --> 00:25:38,920 >> [APLAUS] 640 00:25:38,920 --> 00:25:41,550 >> DAVID Malan: Ja teie lahkuminek kingitused - võite hoida numbrid 641 00:25:41,550 --> 00:25:44,010 kui soovite. 642 00:25:44,010 --> 00:25:45,620 Ja teie peokink, nagu tavaliselt. 643 00:25:45,620 --> 00:25:47,290 Oh, ja me saadame sulle footage, Michelle. 644 00:25:47,290 --> 00:25:48,343 Aitäh. 645 00:25:48,343 --> 00:25:49,250 Hea küll. 646 00:25:49,250 --> 00:25:50,400 Aita ennast stressi pall. 647 00:25:50,400 --> 00:25:54,110 >> Ja las ma tõmba vahepeal, Meie sõber Rob Bowden pakkuda 648 00:25:54,110 --> 00:25:59,520 veidi erineva vaatenurga see, sest sa ei mõtle neid 649 00:25:59,520 --> 00:26:01,280 samme toimub mõnevõrra teistmoodi. 650 00:26:01,280 --> 00:26:04,750 Tegelikult ülesseadmist mida Rob on umbes et näidata meile, eeldab, et me oleme 651 00:26:04,750 --> 00:26:09,030 juba teinud jagamise kohta suur nimekiri kaheksaks väike nimekirjade 652 00:26:09,030 --> 00:26:10,570 Iga suurus 1. 653 00:26:10,570 --> 00:26:13,350 >> Nii et me muutuvad pseudokoodi natuke lihtsalt omamoodi nöökima 654 00:26:13,350 --> 00:26:15,320 põhiidee kuidas ühinevate töötab. 655 00:26:15,320 --> 00:26:17,600 Aga sõiduaega, mida ta on umbes, mida teha on veel 656 00:26:17,600 --> 00:26:19,110 saab olema sama. 657 00:26:19,110 --> 00:26:23,540 Ja jälle, set-up on see, et ta on alustatud kaheksa nimekirjad suurus 1. 658 00:26:23,540 --> 00:26:27,730 Nii et olete jäänud osa, kus ta on tegelikult tehtud log n log n log n 659 00:26:27,730 --> 00:26:31,205 lõhestab sisend. 660 00:26:31,205 --> 00:26:32,120 >> [VIDEO PLAYBACK] 661 00:26:32,120 --> 00:26:33,615 >> -Ongi esimene etapp. 662 00:26:33,615 --> 00:26:38,270 Sest samm kaks, korduvalt ühendada paari nimekirju. 663 00:26:38,270 --> 00:26:39,210 >> DAVID Malan: Hm. 664 00:26:39,210 --> 00:26:41,270 Ainult heli on tulemas välja minu arvuti. 665 00:26:41,270 --> 00:26:42,520 Proovime uuesti. 666 00:26:42,520 --> 00:26:45,330 667 00:26:45,330 --> 00:26:48,310 >> -Just suvaliselt valida mis - Nüüd on meil neli nimekirja. 668 00:26:48,310 --> 00:26:51,590 669 00:26:51,590 --> 00:26:52,120 Lugege enne. 670 00:26:52,120 --> 00:26:53,040 >> DAVID Malan: Vot nii. 671 00:26:53,040 --> 00:27:00,510 >> -Ühinevad 108 ja 15, me lõpetame välja nimekiri 15 108. 672 00:27:00,510 --> 00:27:07,170 Ühinevad 50 ja 4, me lõpetame 4, 50. 673 00:27:07,170 --> 00:27:12,990 Ühinevad 8 ja 42, me lõpetame 8, 42. 674 00:27:12,990 --> 00:27:19,970 Ja ühinevate 23 ja 16, siis lõpetame 16, 23. 675 00:27:19,970 --> 00:27:23,270 >> Nüüd on kõik meie nimekirjad on suurus 2. 676 00:27:23,270 --> 00:27:26,690 Pange tähele, et iga neli nimekirja sorteeritakse. 677 00:27:26,690 --> 00:27:29,450 Nii saame alustada ühinevad paari nimekirjad uuesti. 678 00:27:29,450 --> 00:27:38,420 Ühinevad 15 ja 108 ning 4 ja 50, siis kõigepealt 4, siis 15, siis 679 00:27:38,420 --> 00:27:41,500 50, siis 108. 680 00:27:41,500 --> 00:27:50,610 Ühinevad 8, 42 ja 16, 23, me kõigepealt 8, siis 16, siis 23, 681 00:27:50,610 --> 00:27:52,700 siis 42. 682 00:27:52,700 --> 00:27:57,600 >> Nüüd on meil vaid kaks nimekirjad suurus 4, millest igaüks on järjestatud. 683 00:27:57,600 --> 00:28:01,170 Nüüd me ühinevad need kaks nimekirja. 684 00:28:01,170 --> 00:28:11,835 Esiteks, me 4, siis me võtame 8, siis me võtame 15, siis 16, siis 685 00:28:11,835 --> 00:28:19,456 23, siis 42, siis 50, siis 108. 686 00:28:19,456 --> 00:28:19,872 >> [END VIDEO PLAYBACK] 687 00:28:19,872 --> 00:28:23,430 >> DAVID Malan: Jällegi, teate, ta ei ole kunagi puudutanud antud tass rohkem kui üks kord 688 00:28:23,430 --> 00:28:24,860 pärast edeneb väljaspool. 689 00:28:24,860 --> 00:28:26,200 Nii ta on kunagi korrata. 690 00:28:26,200 --> 00:28:29,850 Nii ta on alati liigub küljele, ja see on, kus me saime oma n. 691 00:28:29,850 --> 00:28:33,290 >> Miks ei lase mul tõmba üks animatsioon et me nägime, kuid seekord 692 00:28:33,290 --> 00:28:35,110 keskendudes ainult Tarkvaraprojekteerimise. 693 00:28:35,110 --> 00:28:38,030 Lubage mul minna ja suurendamiseks aastal selle siin. 694 00:28:38,030 --> 00:28:42,530 Esiteks lubage mul valida juhuslik sisend, võimendada ja saate sortida ja vaata 695 00:28:42,530 --> 00:28:46,600 mida me pidasin enesestmõistetavaks, varem liita omamoodi tegelikult teeb. 696 00:28:46,600 --> 00:28:50,330 >> Nii teate, et saad need pooleks või Nende kvartalite või nende kaheksandikku 697 00:28:50,330 --> 00:28:53,140 probleem, et äkki hakkamist heas korras. 698 00:28:53,140 --> 00:28:57,070 Ja siis lõpuks, näed kell Päris lõpus, et BAM 699 00:28:57,070 --> 00:28:58,860 kõik on ühendatud kokku. 700 00:28:58,860 --> 00:29:01,690 >> Nii et need on vaid kolm erinevat võtab sama mõte. 701 00:29:01,690 --> 00:29:05,980 Aga võti teadmisi, nagu lõhe ja vallutada väga esimese klassi 702 00:29:05,980 --> 00:29:10,640 oli see, et me otsustasime, et kuidagi jagada probleem millekski suur sisseveo 703 00:29:10,640 --> 00:29:14,760 midagi omamoodi identne vaimu aga väiksemaid ja väiksemaid 704 00:29:14,760 --> 00:29:15,660 ja väiksem. 705 00:29:15,660 --> 00:29:18,420 >> Nüüd teine ​​lõbus viis omamoodi mõelda nendest, kuigi see ei ole 706 00:29:18,420 --> 00:29:20,520 annan sulle sama intuitiivne mõistmist, on 707 00:29:20,520 --> 00:29:21,640 järgmine animatsioon. 708 00:29:21,640 --> 00:29:25,400 Nii et see on video keegi kokku panna mis on seotud erinevate 709 00:29:25,400 --> 00:29:29,970 kõlab erinevate toimingute eest sisestamise sort, sest Tarkvaraprojekteerimise ja 710 00:29:29,970 --> 00:29:31,150 paariks teised. 711 00:29:31,150 --> 00:29:32,330 Nii et hetkel, ma lähen lüüa Play. 712 00:29:32,330 --> 00:29:33,600 See on umbes ühe minuti pikkune. 713 00:29:33,600 --> 00:29:37,410 Ja kuigi võite veel näha mustrid juhtub, sel ajal võite 714 00:29:37,410 --> 00:29:41,420 ka kuulata, kuidas need algoritmid täidab erinevalt ja 715 00:29:41,420 --> 00:29:43,950 mõnevõrra erinevad mustrid. 716 00:29:43,950 --> 00:29:45,830 >> See on sisestamise sort. 717 00:29:45,830 --> 00:29:50,400 >> [Toonid MÄNGIB] 718 00:29:50,400 --> 00:29:52,400 >> DAVID Malan: See jälle üritab sisestada iga element 719 00:29:52,400 --> 00:29:52,900 arvesse, kui ta kuulub. 720 00:29:52,900 --> 00:29:54,628 See on mull omamoodi. 721 00:29:54,628 --> 00:30:10,097 >> [Toonid MÄNGIB] 722 00:30:10,097 --> 00:30:13,630 >> DAVID Malan: Ja saab omamoodi tunne kuidas suhteliselt vähe tööd ta teeb 723 00:30:13,630 --> 00:30:15,834 iga samm. 724 00:30:15,834 --> 00:30:20,470 See on see, mida igavus kõlab. 725 00:30:20,470 --> 00:30:21,472 >> [Toonid MÄNGIB] 726 00:30:21,472 --> 00:30:25,222 >> DAVID Malan: See on valiku sorteerida, kus valime elemendi tahame poolt 727 00:30:25,222 --> 00:30:28,845 läbimas uuesti ja uuesti ja uuesti ja paneb selle alguses. 728 00:30:28,845 --> 00:30:37,674 >> [Toonid MÄNGIB] 729 00:30:37,674 --> 00:30:43,970 >> DAVID Malan: See on ühendada sort, mis saab tõesti hakata end. 730 00:30:43,970 --> 00:30:51,810 >> [Toonid MÄNGIB] 731 00:30:51,810 --> 00:30:54,770 >> [Naer] 732 00:30:54,770 --> 00:30:58,395 >> DAVID Malan: midagi, mida nimetatakse gnome sort, mida me ei ole vaadanud. 733 00:30:58,395 --> 00:31:13,630 >> [Toonid MÄNGIB] 734 00:31:13,630 --> 00:31:17,910 >> DAVID Malan: Nii et lubage mul näha, et nüüd, segane nagu te loodetavasti on poolt 735 00:31:17,910 --> 00:31:21,110 muusika, kui ma ei libise vähe natuke matemaatikat siin. 736 00:31:21,110 --> 00:31:24,850 Nii et seal on neljas võimalus, et me ei mõelda, mida see tähendab, need 737 00:31:24,850 --> 00:31:29,210 funktsioonid olla kiirem kui need et me oleme näinud. 738 00:31:29,210 --> 00:31:32,470 Ja kui sa oled tulemas kursuse matemaatika taust, siis 739 00:31:32,470 --> 00:31:36,030 tegelikult teavad ehk juba, et sa saab laksu perspektiivis seda tehnikat - 740 00:31:36,030 --> 00:31:40,400 nimelt rekursioon, funktsioon et kuidagi nimetab ennast. 741 00:31:40,400 --> 00:31:44,780 >> Ja jälle meenutada, et Tarkvaraprojekteerimise pseudokoodi oli rekursiivne mõttes 742 00:31:44,780 --> 00:31:48,460 et üks Tarkvaraprojekteerimise sammudest oli helistada sort - 743 00:31:48,460 --> 00:31:49,740 mis on iseenesest. 744 00:31:49,740 --> 00:31:52,480 Aga õnneks, sest me hoida kutsudes sort, või ühendada sorteerida, 745 00:31:52,480 --> 00:31:55,880 Konkreetsemalt on väiksemaid ja väiksem nimekirja, me lõpuks 746 00:31:55,880 --> 00:32:00,005 põhja tänu mida me kutsume tugipunkti, kodeeritud nii, et 747 00:32:00,005 --> 00:32:04,270 ütles, et kui nimekiri on väike, vähem kui 2 sel juhul lihtsalt kohe tagasi. 748 00:32:04,270 --> 00:32:07,550 Kui me ei ole, et erijuhul, algoritm oleks kunagi alt välja, 749 00:32:07,550 --> 00:32:11,010 ja sa tõesti sattuda lõputu silmuse tõesti igavesti. 750 00:32:11,010 --> 00:32:14,330 >> Aga oletame, et tahame nüüd panna mõned numbrid selle taas kasutades n 751 00:32:14,330 --> 00:32:15,660 nagu suurus sisend. 752 00:32:15,660 --> 00:32:18,680 Ja ma tahtsin teilt küsida, millised on kogu aeg kaasatud 753 00:32:18,680 --> 00:32:19,800 töötab Tarkvaraprojekteerimise? 754 00:32:19,800 --> 00:32:22,960 Või üldisemalt mis kulu see aeg? 755 00:32:22,960 --> 00:32:24,730 >> Noh see on üsna lihtne mõõta seda. 756 00:32:24,730 --> 00:32:29,010 Kui n on väiksem kui 2 korda kaasatud sorteerimine n elementi, 757 00:32:29,010 --> 00:32:30,480 kus n on 2, on 0. 758 00:32:30,480 --> 00:32:31,410 Sest me lihtsalt tagasi. 759 00:32:31,410 --> 00:32:32,510 Pole mingit tööd teha. 760 00:32:32,510 --> 00:32:35,660 Nüüd väidetavalt äkki see on üks samm või kaks samme nuputada summa 761 00:32:35,660 --> 00:32:38,420 töö, kuid see on piisavalt lähedal, et 0, et Ma lihtsalt ütlen tööd ei 762 00:32:38,420 --> 00:32:40,940 nõutav, kui loetelu on nii väike, tuleb ebahuvitav. 763 00:32:40,940 --> 00:32:42,580 >> Aga sel juhul on huvitav. 764 00:32:42,580 --> 00:32:47,320 Rekursiivne juhul oli filiaal pseudokoodi et ütles veel, sorteerida 765 00:32:47,320 --> 00:32:52,000 vasakul pool, sorteerida õigus poole, liita kaks poolt. 766 00:32:52,000 --> 00:32:55,530 Nüüd miks see väljend Kinnitan, et kulu? 767 00:32:55,530 --> 00:32:58,690 Noh, T n tähendab lihtsalt aega, et sortida n elemente. 768 00:32:58,690 --> 00:33:03,070 Ja siis paremal pool võrdusmärk seal, T n jagatud 769 00:33:03,070 --> 00:33:06,600 2 viitab kulud, mida? 770 00:33:06,600 --> 00:33:07,570 Sorteerimine vasakul pool. 771 00:33:07,570 --> 00:33:10,990 Teine T n jagatud 2 on arvatavasti viidates kulusid 772 00:33:10,990 --> 00:33:12,390 Kuvatud paremale poole. 773 00:33:12,390 --> 00:33:14,590 >> Ja siis pluss n? 774 00:33:14,590 --> 00:33:15,420 Kas ühinevad. 775 00:33:15,420 --> 00:33:19,120 Sest kui sul on kaks nimekirja, mis on üks suurus n üle 2 ja teise suurus n 776 00:33:19,120 --> 00:33:22,580 üle 2, siis pead sisuliselt puudutada kõik need elemendid, nagu Rob 777 00:33:22,580 --> 00:33:24,990 puudutanud iga tassi ja lihtsalt nagu me märkisime igal 778 00:33:24,990 --> 00:33:26,310 vabatahtlike laval. 779 00:33:26,310 --> 00:33:28,790 Nii n on arvel ühinevad. 780 00:33:28,790 --> 00:33:31,780 >> Nüüd kahjuks see valem on ka ise kirjutan. 781 00:33:31,780 --> 00:33:36,390 Seega, kui küsis, kui n on, ütleme, 16, kui seal on 16 inimest laval 782 00:33:36,390 --> 00:33:40,670 või 16 tassi video, kui palju kokku samme see võtta neid sorteerida 783 00:33:40,670 --> 00:33:41,550 koos Tarkvaraprojekteerimise? 784 00:33:41,550 --> 00:33:45,790 See on tegelikult mitte selge vastus, sest nüüd on mingisugune 785 00:33:45,790 --> 00:33:48,500 rekursiivselt vastata selle valemi. 786 00:33:48,500 --> 00:33:51,190 >> Aga see on OK, sest lubage mul pakkuda et me teeme järgmine. 787 00:33:51,190 --> 00:33:56,670 Ajakulu sortida 16 inimest või 16 tassi läheb esindatud 788 00:33:56,670 --> 00:33:58,020 üldiselt kui T 16. 789 00:33:58,020 --> 00:34:01,400 Aga mis võrdub vastavalt meie eelmine valem, 2 korda suurem 790 00:34:01,400 --> 00:34:04,780 aeg, mis kulub, et järjestada 8 tassi pluss 16. 791 00:34:04,780 --> 00:34:08,590 Ja veel, pluss 16 on aeg ühineda, ja kaks korda T 8. on 792 00:34:08,590 --> 00:34:10,790 aega, et sortida vasakul pool ja paremal pool. 793 00:34:10,790 --> 00:34:11,989 >> Aga jälle, see ei ole piisav. 794 00:34:11,989 --> 00:34:13,210 Meil on sukelduda sügavamale. 795 00:34:13,210 --> 00:34:16,409 See tähendab, et me peame vastama küsimus, mis on T 8? 796 00:34:16,409 --> 00:34:19,610 Noh T 8. on vaid 2 korda T 4 pluss 8. 797 00:34:19,610 --> 00:34:20,520 Nii, mis on T 4? 798 00:34:20,520 --> 00:34:23,780 T 4 on lihtsalt 2 korda T 2 pluss 4. 799 00:34:23,780 --> 00:34:25,489 Nii, mis on T 2? 800 00:34:25,489 --> 00:34:29,030 T 2 on vaid 2 korda T 1 pluss 2. 801 00:34:29,030 --> 00:34:31,940 >> Ja veel, me oleme omamoodi saada kinni selles tsüklis. 802 00:34:31,940 --> 00:34:34,790 Aga see on umbes lüüa, et niinimetatud tugipunkti. 803 00:34:34,790 --> 00:34:37,310 Sest see, mis on T 1, me väita? 804 00:34:37,310 --> 00:34:37,810 0. 805 00:34:37,810 --> 00:34:39,730 Nüüd lõpuks saame teha tagurpidi. 806 00:34:39,730 --> 00:34:44,290 >> Kui T 1 on 0, võin nüüd minna tagasi kuni üks rida see kutt siin, ja ma ei saa 807 00:34:44,290 --> 00:34:46,330 pistik 0 T 1. 808 00:34:46,330 --> 00:34:51,770 See tähendab, see on võrdne 2 korda null, muidu tuntud 0, pluss 2. 809 00:34:51,770 --> 00:34:53,739 Ja nii, et kogu avaldis on 2. 810 00:34:53,739 --> 00:34:58,740 >> Nüüd, kui ma võtan T 2, kelle vastus on 2, ühendage see keset rida, T 811 00:34:58,740 --> 00:35:02,740 4, mis annab mulle 2 korda 2 pluss 4, seega 8. 812 00:35:02,740 --> 00:35:07,080 Kui ma siis ühendan 8 eelmise line, et annab mulle 2 korda 8, 16. 813 00:35:07,080 --> 00:35:12,470 Ja kui me siis jätkama, et koos 24, lisades 16, me lõpuks saada 814 00:35:12,470 --> 00:35:13,820 väärtus 64. 815 00:35:13,820 --> 00:35:18,480 >> Nüüd, ja iseenesest justkui räägib midagi n märke, 816 00:35:18,480 --> 00:35:20,700 suur O, omega, mida me oleme rääkinud. 817 00:35:20,700 --> 00:35:24,890 Aga selgub, et 64 on tõepoolest 16 suurus sisend, 818 00:35:24,890 --> 00:35:27,110 logaritm alusel 2 16. 819 00:35:27,110 --> 00:35:30,200 Ja kui see on veidi harjumatu, vaid arvan, et tagasi, ja ta tulen tagasi 820 00:35:30,200 --> 00:35:30,700 et sa lõpuks. 821 00:35:30,700 --> 00:35:33,775 Kui see on samamoodi baasi 2, see on nagu 2 tõsteti mis annab sulle 16? 822 00:35:33,775 --> 00:35:36,380 Oh, see on 4, nii et see on 16 korda 4. 823 00:35:36,380 --> 00:35:39,380 >> Ja veel, see ei ole suur asi, kui see on omamoodi udune mälu nüüd. 824 00:35:39,380 --> 00:35:43,720 Aga nüüd, võtta usk et 16 log 16 on 64. 825 00:35:43,720 --> 00:35:46,590 Ja nii tõesti, selle lihtsa meelerahu vaadake, me oleme kinnitanud - 826 00:35:46,590 --> 00:35:48,250 kuid ei osutunud ametlikult - 827 00:35:48,250 --> 00:35:52,800 et sõiduaega ühendamist sort on tõepoolest n log n. 828 00:35:52,800 --> 00:35:53,790 >> Nii ei ole halb. 829 00:35:53,790 --> 00:35:57,260 See on kindlasti parem kui algoritme oleme näinud siiani, ja 830 00:35:57,260 --> 00:36:00,710 see on sellepärast, et me oleme võimendatud, üks, tehnikat nimega rekursiooni. 831 00:36:00,710 --> 00:36:03,880 Aga huvitavam kui see, mis mõiste jagades ja vallutavad. 832 00:36:03,880 --> 00:36:07,460 Jällegi tõeliselt nädal 0 kraami, isegi nüüd on taasteket 833 00:36:07,460 --> 00:36:08,740 selgem viis. 834 00:36:08,740 --> 00:36:11,750 >> Nüüd lõbus väike harjutus, kui olete kunagi seda teinud - ja siis ilmselt 835 00:36:11,750 --> 00:36:14,660 ei oleks, sest omamoodi normaalne inimesed ei usu, et seda teha. 836 00:36:14,660 --> 00:36:20,650 Aga kui ma lähen google.com ja kui Ma tahan õppida midagi 837 00:36:20,650 --> 00:36:22,356 rekursioon, Enter. 838 00:36:22,356 --> 00:36:25,106 839 00:36:25,106 --> 00:36:29,058 >> [Naer] 840 00:36:29,058 --> 00:36:32,030 [MORE naer] 841 00:36:32,030 --> 00:36:33,385 DAVID Malan: Bad joke aeglaselt levib. 842 00:36:33,385 --> 00:36:34,450 [Naer] 843 00:36:34,450 --> 00:36:36,970 DAVID Malan: Igaks juhuks, et see on olemas. 844 00:36:36,970 --> 00:36:38,710 Ma ei saa kirjutada seda valesti, ja seal on nali. 845 00:36:38,710 --> 00:36:40,810 Hea küll. 846 00:36:40,810 --> 00:36:42,950 Selgitage see inimestele sinu kõrval, kui see ei ole päris klõpsanud veel. 847 00:36:42,950 --> 00:36:47,650 Aga recursion üldisemalt viitab et protsessi funktsioon helistades 848 00:36:47,650 --> 00:36:51,430 ise, või üldisemalt, jagades probleem millekski, mis võib olla 849 00:36:51,430 --> 00:36:56,220 lahendada tükkhaaval lahendades identne esindaja probleeme. 850 00:36:56,220 --> 00:36:58,400 >> Noh, olgem käiku vahetada hetkeks. 851 00:36:58,400 --> 00:37:00,840 Meile meeldib end teatud cliffhangers, Alustame seada 852 00:37:00,840 --> 00:37:05,870 etapp, mitu minutit, on väga lihtne idee - 853 00:37:05,870 --> 00:37:07,620 et Vahetatakse kahe elemendi, eks? 854 00:37:07,620 --> 00:37:10,040 Kõik need algoritmid me oleme räägi paari viimase 855 00:37:10,040 --> 00:37:12,420 loengud hõlmata omamoodi vahetada. 856 00:37:12,420 --> 00:37:14,630 Täna oli visualiseeritud neid saada üles välja oma toolid ja 857 00:37:14,630 --> 00:37:18,570 jalutamas, kuid kood, oleksime lihtsalt võtta osa ühest array 858 00:37:18,570 --> 00:37:20,370 ja sulpsti see teise. 859 00:37:20,370 --> 00:37:21,880 >> Niisiis, kuidas me minna seda teed? 860 00:37:21,880 --> 00:37:24,850 Noh, lubage mul minna ja kirjutada kiire programm siin. 861 00:37:24,850 --> 00:37:31,600 Ma lähen edasi minna ja teha see on järgmine. 862 00:37:31,600 --> 00:37:33,910 Kutsume seda - 863 00:37:33,910 --> 00:37:38,070 Mida me tahame helistada see üks? 864 00:37:38,070 --> 00:37:38,650 >> Tegelikult, ei. 865 00:37:38,650 --> 00:37:39,420 Lubage mul kerida. 866 00:37:39,420 --> 00:37:41,220 Ma ei taha seda teha, pinge veel. 867 00:37:41,220 --> 00:37:42,270 See on sõjasaak lõbus. 868 00:37:42,270 --> 00:37:43,600 Teeme seda mitte. 869 00:37:43,600 --> 00:37:47,430 >> Oletame, et ma tahan kirjutada vähe programm ning nüüd hõlmab see 870 00:37:47,430 --> 00:37:48,700 Idee rekursiooni. 871 00:37:48,700 --> 00:37:50,370 Ma nagu sain enne ise seal. 872 00:37:50,370 --> 00:37:51,420 Ma lähen tegema järgmist. 873 00:37:51,420 --> 00:38:00,220 >> Esiteks, kiire sisaldavad standardi io.h, samuti nagu on cs50.h. 874 00:38:00,220 --> 00:38:03,200 Ja siis ma lähen edasi minna ja deklareerima int main void 875 00:38:03,200 --> 00:38:04,360 tavalisel viisil. 876 00:38:04,360 --> 00:38:07,920 Mul tuli misnamed faili, nii et Lubage mul lisada. c pikendamine siin nii 877 00:38:07,920 --> 00:38:09,510 et saaksime koostada seda korralikult. 878 00:38:09,510 --> 00:38:10,970 Alusta seda funktsiooni välja lülitada. 879 00:38:10,970 --> 00:38:13,290 >> Ja funktsioon ma tahan kirjutada, üsna lihtsalt, on üks, mis palub 880 00:38:13,290 --> 00:38:16,210 kasutaja number ja siis lisab kõik numbrid vahel, et 881 00:38:16,210 --> 00:38:19,920 number ja, ütleme, 0. 882 00:38:19,920 --> 00:38:22,510 Nii et kõigepealt ma lähen edasi minna ja deklareerima int n. 883 00:38:22,510 --> 00:38:24,760 Siis ma saan kopeerida mõned kood, mis Me kasutasime mõnda aega. 884 00:38:24,760 --> 00:38:26,660 Kuigi midagi on tõsi. 885 00:38:26,660 --> 00:38:28,000 Ma tulen tagasi, et hetkel. 886 00:38:28,000 --> 00:38:29,010 >> Mida ma tahan teha? 887 00:38:29,010 --> 00:38:33,460 Ma tahan öelda printf positiivne täisarv palun. 888 00:38:33,460 --> 00:38:36,130 Ja siis ma lähen öelda n saab saada int. 889 00:38:36,130 --> 00:38:38,800 Nii et taas, mõned stereotüüp kood et me oleme varem kasutanud. 890 00:38:38,800 --> 00:38:40,810 Ja ma kavatsen seda teha kui n on väiksem kui 1. 891 00:38:40,810 --> 00:38:44,120 Nii, et see tagab, et kasutaja annab mulle positiivne täisarv. 892 00:38:44,120 --> 00:38:45,490 >> Ja nüüd ma lähen tegema järgmist. 893 00:38:45,490 --> 00:38:51,020 Tahan lisada kuni kõik numbrid vahemikus 1 ja n või 0 ja n, 894 00:38:51,020 --> 00:38:52,570 võrreldavalt saada kogu summa. 895 00:38:52,570 --> 00:38:55,100 Nii suur sigma sümbol et te võiks meenutada. 896 00:38:55,100 --> 00:38:59,050 Nii et ma lähen tegema seda esimene helistaja funktsiooni nimetatakse sigma, 897 00:38:59,050 --> 00:39:06,030 kulgeb seda n, ja siis ma lähen öelda printf, vastus on siin. 898 00:39:06,030 --> 00:39:08,180 >> Nii lühike, saan ja int kasutaja. 899 00:39:08,180 --> 00:39:09,280 Ma veenduge, et see on positiivne. 900 00:39:09,280 --> 00:39:12,700 Kinnitan muutuja nimega vastus tüüpi int ja kaupluse see tagasi 901 00:39:12,700 --> 00:39:15,610 väärtus sigma, läbides n sisendiks. 902 00:39:15,610 --> 00:39:17,060 Ja siis ma välja printida, et vastata. 903 00:39:17,060 --> 00:39:19,550 >> Kahjuks, kuigi sigma kõlab nagu midagi, mis võiks olla 904 00:39:19,550 --> 00:39:24,040 math.h fail oma avalduses, see on tegelikult mitte. 905 00:39:24,040 --> 00:39:24,690 Nii et pole midagi. 906 00:39:24,690 --> 00:39:26,170 Võin rakendada seda ise. 907 00:39:26,170 --> 00:39:29,160 Ma lähen, et rakendada funktsioon nimega sigma ja see vőtab 908 00:39:29,160 --> 00:39:29,900 parameeter - 909 00:39:29,900 --> 00:39:32,100 Ütleme nii, et m, lihtsalt nii et see on teistsugune. 910 00:39:32,100 --> 00:39:35,910 Ja siis siin, ma lähen öelda, Noh, kui m on alla 1 - see on 911 00:39:35,910 --> 00:39:38,180 väga ebahuvitav programm. 912 00:39:38,180 --> 00:39:41,700 Nii et ma lähen edasi minna ja kohe tagasi 0. 913 00:39:41,700 --> 00:39:45,920 See lihtsalt ei ole mõtet lisada kuni kõik numbrid vahemikus 1 m, kui m 914 00:39:45,920 --> 00:39:48,470 ise 0 või negatiivne. 915 00:39:48,470 --> 00:39:50,900 >> Ja siis ma lähen edasi minna ja seda väga korduvalt. 916 00:39:50,900 --> 00:39:53,090 Ma teen seda omamoodi vana kooli, ja ma lähen edasi minna 917 00:39:53,090 --> 00:39:57,150 ja öelda, et ma lähen kuulutada summa olema 0. 918 00:39:57,150 --> 00:39:59,630 Siis ma lähen on jaoks silmus int - 919 00:39:59,630 --> 00:40:02,820 ja las ma teen seda, mis vastavad meie jaotus kood, nii et teil on koopia 920 00:40:02,820 --> 00:40:07,500 kodus. int i saab 1 kuni i on väiksem või võrdne m. 921 00:40:07,500 --> 00:40:09,430 i pluss pluss. 922 00:40:09,430 --> 00:40:11,430 Ja siis seestpoolt seda loop - 923 00:40:11,430 --> 00:40:12,440 me oleme peaaegu kohal - 924 00:40:12,440 --> 00:40:15,810 summa muutub summa pluss 1. 925 00:40:15,810 --> 00:40:17,670 Ja siis ma lähen tagasi summa. 926 00:40:17,670 --> 00:40:19,420 >> Nii et ma tegin seda kiiresti, päris tõsi. 927 00:40:19,420 --> 00:40:22,775 Aga jälle, mille peamine ülesanne on päris arusaadav, mis põhineb kood oleme 928 00:40:22,775 --> 00:40:23,190 kirjaliku siiani. 929 00:40:23,190 --> 00:40:25,610 Kasutab dual loop saada positiivne int kasutaja. 930 00:40:25,610 --> 00:40:29,870 Ma siis edasi, et int uue funktsiooni nimetatakse sigma, nimetades seda jällegi n. 931 00:40:29,870 --> 00:40:33,100 Ja ma salvestada tagastatav väärtus, vastus alates musta kasti praegu 932 00:40:33,100 --> 00:40:35,460 tuntud Sigma, muutuv kutsutud vastus. 933 00:40:35,460 --> 00:40:36,580 Siis ma printida. 934 00:40:36,580 --> 00:40:39,090 >> Kui nüüd jätkata lugu, kuidas on sigma rakendada? 935 00:40:39,090 --> 00:40:40,840 Teen ettepaneku rakendada järgmised. 936 00:40:40,840 --> 00:40:43,560 Esiteks natuke Tõrkekontroll veenduda, et kasutaja ei 937 00:40:43,560 --> 00:40:46,480 mulle jama ja kulgeb mõned negatiivsed või 0 väärtust. 938 00:40:46,480 --> 00:40:49,710 Siis ma kuulutada muutuja nimega Kokkuvõttes ja sisesta 0.. 939 00:40:49,710 --> 00:40:55,910 >> Ja nüüd ma hakkan liikuma i võrdub 1. kõik viis kuni m, 940 00:40:55,910 --> 00:41:00,130 sest ma tahan, et see hõlmaks kõiki numbrid ühest kuni m, kaasa arvatud. 941 00:41:00,130 --> 00:41:04,350 Ja sees selle jaoks silmus, ma lihtsalt teha summa muutub mis iganes see on nüüd, pluss 942 00:41:04,350 --> 00:41:08,900 väärtus i. 943 00:41:08,900 --> 00:41:10,370 Plus väärtus i. 944 00:41:10,370 --> 00:41:14,090 >> Nagu kõrvale, kui sul ei ole seda näinud enne, seal on mõned süntaktiline suhkur 945 00:41:14,090 --> 00:41:14,870 Selle liini. 946 00:41:14,870 --> 00:41:21,120 Võin selle uuesti kirjutada pluss võrdub i, lihtsalt säästa ennast mõne klahvivajutusega 947 00:41:21,120 --> 00:41:22,570 ja vaatama natuke jahedam. 948 00:41:22,570 --> 00:41:23,140 Aga see on kõik. 949 00:41:23,140 --> 00:41:24,660 See on funktsionaalselt sama asi. 950 00:41:24,660 --> 00:41:26,710 >> Kahjuks on see kood on ei kavatse koostada veel. 951 00:41:26,710 --> 00:41:31,600 Kui ma saan teha sigma 0, kui olen Ma hakka karjus? 952 00:41:31,600 --> 00:41:33,473 Kuidas see läheb ei meeldi? 953 00:41:33,473 --> 00:41:35,740 >> Publik: [kuuldamatu]. 954 00:41:35,740 --> 00:41:37,800 >> DAVID Malan: Jah, ma ei tunnistanud funktsioon üleval, eks? 955 00:41:37,800 --> 00:41:40,590 C on tobe, sest see ainult teeb mida sa öelda tahad, ja sa 956 00:41:40,590 --> 00:41:41,880 on seda teha selles järjekorras. 957 00:41:41,880 --> 00:41:45,910 Ja nii kui ma Enter siin, ma lähen saada hoiatuse sigma kaudne 958 00:41:45,910 --> 00:41:46,860 deklaratsioon. 959 00:41:46,860 --> 00:41:48,120 >> Oh, ei ole probleem. 960 00:41:48,120 --> 00:41:50,370 Ma ei saa minna kuni top, ja ma ei öelda, olgu, oota natuke. 961 00:41:50,370 --> 00:41:54,240 Sigma on funktsioon, mis tagastab int ja see eeldab 962 00:41:54,240 --> 00:41:56,620 int sisend, semikoolon. 963 00:41:56,620 --> 00:41:59,550 Või ma võiksin panna kogu funktsioon eespool peamine, kuid üldiselt, ma 964 00:41:59,550 --> 00:42:02,260 soovitan vastu, et kuna see on tore on alati peamine tipus nii 965 00:42:02,260 --> 00:42:06,310 saate sukelduda paremale ja teavad, mida Programm teeb lugedes peamine esimene. 966 00:42:06,310 --> 00:42:07,930 >> Nüüd lubage mul selge ekraan. 967 00:42:07,930 --> 00:42:09,330 Uusversiooni sigma 0. 968 00:42:09,330 --> 00:42:10,340 Kõik tundub, et kontrollida. 969 00:42:10,340 --> 00:42:11,970 Lubage mul joosta sigma 0. 970 00:42:11,970 --> 00:42:12,770 Positiivne muu. 971 00:42:12,770 --> 00:42:15,580 Ma annan see number 3. hoida lihtsa. 972 00:42:15,580 --> 00:42:18,710 Nii et peaks mulle 3 pluss 2 pluss 1, seega 6. 973 00:42:18,710 --> 00:42:20,750 Sisesta ning tõepoolest saan 6. 974 00:42:20,750 --> 00:42:21,820 >> Ma ei tee midagi suuremat - 975 00:42:21,820 --> 00:42:24,080 50, 12, 75. 976 00:42:24,080 --> 00:42:27,690 Just nagu puutuja, ma lähen tegema midagi naeruväärne nagu tõesti suur 977 00:42:27,690 --> 00:42:30,375 number, Oh, mis tegelikult välja töötatud - 978 00:42:30,375 --> 00:42:31,600 eh, ma ei usu, et see on õige. 979 00:42:31,600 --> 00:42:32,810 Vaatame. 980 00:42:32,810 --> 00:42:34,060 Olgem tõesti jama see. 981 00:42:34,060 --> 00:42:37,150 982 00:42:37,150 --> 00:42:38,400 >> See on probleem. 983 00:42:38,400 --> 00:42:43,180 984 00:42:43,180 --> 00:42:44,970 Mis toimub? 985 00:42:44,970 --> 00:42:46,050 Kood ei ole nii halb. 986 00:42:46,050 --> 00:42:48,470 See on ikka lineaarne. 987 00:42:48,470 --> 00:42:50,810 Vilistamine on hea mõju, kuigi. 988 00:42:50,810 --> 00:42:52,060 Mis toimub? 989 00:42:52,060 --> 00:42:54,700 990 00:42:54,700 --> 00:42:55,620 >> Ei ole kindel, kui ma kuulsin seda. 991 00:42:55,620 --> 00:42:57,620 Nii selgub - ja see on nagu kõrvale. 992 00:42:57,620 --> 00:42:59,400 See ei ole tuum Idee rekursiooni. 993 00:42:59,400 --> 00:43:02,480 Selgub, sest ma üritan esindab nii suur number, kõige 994 00:43:02,480 --> 00:43:06,980 tõenäoliselt see kuramuse valesti poolt C, ei positiivne arv, 995 00:43:06,980 --> 00:43:09,980 kuid negatiivne number. 996 00:43:09,980 --> 00:43:12,690 >> Me ei ole sellest rääkinud, kuid see Selgub, on negatiivsed arvud 997 00:43:12,690 --> 00:43:14,210 maailmas lisaks positiivseid numbreid. 998 00:43:14,210 --> 00:43:16,290 Ja vahendid, mille abil saab esindama negatiivne arv 999 00:43:16,290 --> 00:43:19,530 sisuliselt on, siis kasutage ühte eriline natuke näidata 1000 00:43:19,530 --> 00:43:20,400 positiivne jooksul negatiivne. 1001 00:43:20,400 --> 00:43:22,950 See on natuke keerulisem kui see, aga see on põhiidee. 1002 00:43:22,950 --> 00:43:26,740 >> Nii kahjuks kui C ajab üks need bitti kui tegelikult tähendab, 1003 00:43:26,740 --> 00:43:30,790 oh, see on negatiivne arv, mu loop siin näiteks on tegelikult kunagi 1004 00:43:30,790 --> 00:43:31,740 kavatse lõpetada. 1005 00:43:31,740 --> 00:43:33,850 Nii et kui ma tegelikult trükkimine midagi ikka ja jälle, oleksime 1006 00:43:33,850 --> 00:43:34,650 vaata palju. 1007 00:43:34,650 --> 00:43:36,220 Aga jälle, see on peale punkti. 1008 00:43:36,220 --> 00:43:38,590 See on tõesti lihtsalt omamoodi intellektuaalne uudishimu, et me tuleme 1009 00:43:38,590 --> 00:43:39,550 Tagasi lõpuks. 1010 00:43:39,550 --> 00:43:43,400 Aga nüüd, et see on õige rakendamist, kui me eeldame, et 1011 00:43:43,400 --> 00:43:45,970 kasutaja annab ints mis mahuvad ints. 1012 00:43:45,970 --> 00:43:49,370 >> Aga ma väita, et see kood, ausalt, võiks teha nii palju lihtsalt. 1013 00:43:49,370 --> 00:43:54,060 Kui eesmärk käepärast on võtta mitmeid nagu m ja liita kõik 1014 00:43:54,060 --> 00:43:59,510 numbrite vahel see ja 1 või vastupidi vahel 1 ja see, ma väita, 1015 00:43:59,510 --> 00:44:03,380 et võin seda laenata idee, et ühendada sort oli, mis oli võttes probleem 1016 00:44:03,380 --> 00:44:05,660 Selle suurus ja jagades selle millekski väiksem. 1017 00:44:05,660 --> 00:44:09,875 Võib-olla mitte pool, aga väiksem, kuid esindavad sama. 1018 00:44:09,875 --> 00:44:12,130 Sama mõte, kuid väiksem probleem. 1019 00:44:12,130 --> 00:44:15,470 >> Nii et ma olen tegelikult - las ma salvestan selle faili erineva versiooni number. 1020 00:44:15,470 --> 00:44:17,670 Me nimetame seda versiooni 0 asemel 1. 1021 00:44:17,670 --> 00:44:20,790 Ja ma väita, et ma ei saa tegelikult implementeerid seda selline 1022 00:44:20,790 --> 00:44:22,160 Raske tee. 1023 00:44:22,160 --> 00:44:23,710 >> Ma jätan selle osa üksi. 1024 00:44:23,710 --> 00:44:27,710 Ma ütlen, kui m on vähem kui või isegi võrdne 0 - 1025 00:44:27,710 --> 00:44:29,280 Ma lihtsalt olema natuke rohkem anal seekord 1026 00:44:29,280 --> 00:44:30,520 minu viga kontroll - 1027 00:44:30,520 --> 00:44:33,190 Ma lähen edasi minna ja tagasi 0. 1028 00:44:33,190 --> 00:44:34,490 See on meelevaldne. 1029 00:44:34,490 --> 00:44:37,500 Ma lihtsalt lihtsalt otsustada, kas kasutaja annab mulle negatiivne number, ma olen 1030 00:44:37,500 --> 00:44:41,490 tagasi 0 ja nad oleks pidanud lugema dokumentatsioon tihedamalt. 1031 00:44:41,490 --> 00:44:42,170 >> Muu - 1032 00:44:42,170 --> 00:44:44,070 teate, mida ma teen. 1033 00:44:44,070 --> 00:44:49,260 Else ma tagasi m pluss - 1034 00:44:49,260 --> 00:44:51,010 mis on sigma m? 1035 00:44:51,010 --> 00:44:56,710 Noh, sigma m pluss m miinus 1, pluss m miinus 2, pluss m miinus 3. 1036 00:44:56,710 --> 00:44:58,030 Ma ei taha, et kirjutada kõik, et välja. 1037 00:44:58,030 --> 00:44:59,120 Miks ma ei lihtsalt punt? 1038 00:44:59,120 --> 00:45:05,080 Rekursiivselt kutsuvad ennast veidi väiksem probleem, semikoolon, 1039 00:45:05,080 --> 00:45:06,840 ja nimetavad seda päeva? 1040 00:45:06,840 --> 00:45:07,040 >> Õigus? 1041 00:45:07,040 --> 00:45:10,980 Nüüd ka siin, võite tunda või muretsema et see on lõputu silmuse, et ma olen 1042 00:45:10,980 --> 00:45:15,450 tekitavaid, mille ma olen rakendamisel sigma väljakutsel sigma. 1043 00:45:15,450 --> 00:45:20,342 Aga see on täiesti OK, sest ma arvasin enne lisatud, mis read? 1044 00:45:20,342 --> 00:45:22,600 >> Publik: [kuuldamatu]. 1045 00:45:22,600 --> 00:45:25,430 >> DAVID Malan: 23-26, mis on minu kui seisukorras. 1046 00:45:25,430 --> 00:45:28,390 Sest see, mis on ilus umbes lahutamine siin, sest ma hoida 1047 00:45:28,390 --> 00:45:31,180 teisaldus sigma väiksemad probleemid, väiksem probleeme, väiksem - see ei ole 1048 00:45:31,180 --> 00:45:31,870 poole väiksem. 1049 00:45:31,870 --> 00:45:34,380 See on ainus laps samm väiksem, kuid see on OK. 1050 00:45:34,380 --> 00:45:38,050 Sest lõpuks, me töö meie tee alla 1 või 0. 1051 00:45:38,050 --> 00:45:41,630 Ja kui me tabanud 0, Sigma ei läheb kutsuvad ennast enam. 1052 00:45:41,630 --> 00:45:43,590 See läheb kohe tagasi 0. 1053 00:45:43,590 --> 00:45:47,960 >> Seega mõju, kui sa omamoodi tuul see üles meelt, on lisada m pluss 1054 00:45:47,960 --> 00:45:52,740 m miinus 1 pluss m miinus 2, pluss m miinus 3, pluss dot, dot, dot, m miinus 1055 00:45:52,740 --> 00:45:57,820 m, lõpuks annab teile 0, ja mõju on lõpuks lisada kõik 1056 00:45:57,820 --> 00:45:59,070 need asjad kokku. 1057 00:45:59,070 --> 00:46:02,380 Nii et me ei ole, kus rekursioon, lahendada probleemi, et me 1058 00:46:02,380 --> 00:46:03,470 ei suudetud lahendada enne. 1059 00:46:03,470 --> 00:46:06,840 Tõepoolest, versioon 0 sellest ja iga probleem siiani olnud lahendatav 1060 00:46:06,840 --> 00:46:09,980 vaid kasutades silmuseid või kui silmuseid vms konstrueerib. 1061 00:46:09,980 --> 00:46:13,150 >> Aga rekursioon, Julgen öelda, annab meile teistmoodi mõtlema 1062 00:46:13,150 --> 00:46:17,010 probleeme, mille kohaselt juhul saame probleem, jagada see midagi 1063 00:46:17,010 --> 00:46:22,340 mõnevõrra suur millekski mõnevõrra väiksem, ma väita, et me saame seda lahendada 1064 00:46:22,340 --> 00:46:26,040 võibolla veidi rohkem elegantselt poolest disain, kus on vähem koodi, 1065 00:46:26,040 --> 00:46:30,980 ja võib-olla isegi lahendada probleeme, mis olla raskem, kui paneme lõpuks 1066 00:46:30,980 --> 00:46:33,280 vaata, lahendades puhtalt korduvalt. 1067 00:46:33,280 --> 00:46:35,980 >> Aga pinge, mis ma tegin, taha jätta meid oli see. 1068 00:46:35,980 --> 00:46:40,720 Lubage mul minna ja avada üles faili - 1069 00:46:40,720 --> 00:46:44,300 tegelikult, lase mul minna ja seda päris kiiresti. 1070 00:46:44,300 --> 00:46:46,875 Lubage mul minna ja ettepanekuid järgmised. 1071 00:46:46,875 --> 00:46:51,160 1072 00:46:51,160 --> 00:46:54,785 Seas tänane kood on see pilt siin. 1073 00:46:54,785 --> 00:47:01,090 1074 00:47:01,090 --> 00:47:03,050 See üks siin, noswap. 1075 00:47:03,050 --> 00:47:06,260 >> Nii et see on rumal väike programm, mis Ma vahustatud up et väited, mida teha 1076 00:47:06,260 --> 00:47:06,940 järgmised. 1077 00:47:06,940 --> 00:47:10,140 In peamine, see esimene deklareerib int nimetatakse x ja annab see 1078 00:47:10,140 --> 00:47:11,100 väärtus 1. 1079 00:47:11,100 --> 00:47:13,520 Siis ta teatab, int y ja määrab see väärtus 2. 1080 00:47:13,520 --> 00:47:15,310 Siis ta prindib välja, mis x ja y on. 1081 00:47:15,310 --> 00:47:17,781 Siis ta ütleb, vahetada, dot dot dot. 1082 00:47:17,781 --> 00:47:21,670 >> Seejärel väidab ta, et kutsudes funktsioon kutsutakse swap, läbides x ja 1083 00:47:21,670 --> 00:47:24,290 y, idee, mis on see, et loodetavasti x ja y tulevad tagasi 1084 00:47:24,290 --> 00:47:25,620 erinevad, vastupidine. 1085 00:47:25,620 --> 00:47:27,110 Siis väidavad vahetasid! 1086 00:47:27,110 --> 00:47:28,420 hüüumärk. 1087 00:47:28,420 --> 00:47:30,190 Siis ta prindib välja x ja y. 1088 00:47:30,190 --> 00:47:33,480 >> Aga selgub, et see väga lihtne tutvustamise alla 1089 00:47:33,480 --> 00:47:35,570 siin on tegelikult lollakas. 1090 00:47:35,570 --> 00:47:38,870 Kuigi ma kuulutab ajutine muutuv ja ajutiselt panna sisse 1091 00:47:38,870 --> 00:47:42,010 , siis ma ümberjagamise väärtus b - 1092 00:47:42,010 --> 00:47:45,080 mis tundub mõistlik, sest ma olen salvestatud koopia ka temp. 1093 00:47:45,080 --> 00:47:48,410 Siis ma uuendada b võrdsele mis iganes oli temp. 1094 00:47:48,410 --> 00:47:51,610 Selline kest mäng liigub arvesse B ja b ümber, kasutades seda 1095 00:47:51,610 --> 00:47:54,360 Lähis-nimeline mees temp tunneb täiesti mõistlik. 1096 00:47:54,360 --> 00:47:57,270 >> Aga ma väita, et kui ma saan seda kood, nagu ma teen nüüd - 1097 00:47:57,270 --> 00:47:59,490 lase mul minna ja kleebi see siin. 1098 00:47:59,490 --> 00:48:01,995 Ma nimetan seda noswap.c. 1099 00:48:01,995 --> 00:48:05,630 Ja nagu nimigi ütleb, ei ole see kavatse olla õige programm. 1100 00:48:05,630 --> 00:48:09,460 Tee noswap. / Ei swap. 1101 00:48:09,460 --> 00:48:12,110 x on 1, y on 2, vahetada, vahetada. 1102 00:48:12,110 --> 00:48:14,220 x on 1, y 2. 1103 00:48:14,220 --> 00:48:16,920 See on põhimõtteliselt vale, isegi kuigi see tundub täiesti 1104 00:48:16,920 --> 00:48:17,730 mõistlik mulle. 1105 00:48:17,730 --> 00:48:21,330 Ja seal on põhjus, kuid me ei ole kavatse paljastada põhjus veel. 1106 00:48:21,330 --> 00:48:24,610 >> Nüüd teine ​​pinge tahtsin lahkuda teile on see, 1107 00:48:24,610 --> 00:48:27,120 teadaanne kehvasti edasi Kupongi koodid. 1108 00:48:27,120 --> 00:48:31,590 Meie innovatsiooni hilinenud päeva tänavu on tekitanud mitte-triviaalne number 1109 00:48:31,590 --> 00:48:33,830 küsimusi, mis on mitte meie eesmärk. 1110 00:48:33,830 --> 00:48:36,590 Kavatsusega need Kupongi koodid, kusjuures, kui sa osa probleemist 1111 00:48:36,590 --> 00:48:39,850 seada varakult, seeläbi muutub lisapäev, oli tõesti aidata teid aidata 1112 00:48:39,850 --> 00:48:42,420 ise alustada varakult, sorteerida teel Lisatasusid lubavad sulle. 1113 00:48:42,420 --> 00:48:44,880 Aitab meil levitada lasti üle tööaega paremini, et 1114 00:48:44,880 --> 00:48:45,740 see on omamoodi võidavad. 1115 00:48:45,740 --> 00:48:48,860 >> Kahjuks ma arvan, et minu juhiseid ei ole olnud siiani väga selge, et 1116 00:48:48,860 --> 00:48:52,230 Läksin tagasi sel nädalavahetusel ja ajakohastatud spec suurem, julgem teksti 1117 00:48:52,230 --> 00:48:53,600 selgitada täppe nagu need. 1118 00:48:53,600 --> 00:48:56,900 Ja just seda öelda veel avalikult, mida Vaikimisi probleem komplekti on tingitud neljapäev 1119 00:48:56,900 --> 00:48:58,400 Keskpäeval kohta ainekava. 1120 00:48:58,400 --> 00:49:02,030 Kui alustate varakult, viimistlus osa probleem kehtestatud kolmapäeval kell 12:00 1121 00:49:02,030 --> 00:49:05,170 PM, see osa, mis on seotud kupong kood, idee on see, et saate laiendada 1122 00:49:05,170 --> 00:49:07,710 oma tähtpäeva P seada kuni reede. 1123 00:49:07,710 --> 00:49:10,890 See on natuke off tilluke osa P määrata suhteline, mida tavaliselt on 1124 00:49:10,890 --> 00:49:13,200 suurem probleem, ja kui osta ise lisapäev. 1125 00:49:13,200 --> 00:49:15,190 Jällegi, see läheb sa mõtled Ülesanded, saab teil 1126 00:49:15,190 --> 00:49:16,380 tööajal varem. 1127 00:49:16,380 --> 00:49:20,670 Aga kuponkikoodi probleem on endiselt nõutav, isegi kui sa ei esita see. 1128 00:49:20,670 --> 00:49:23,340 >> Aga rohkem compellingly on see. 1129 00:49:23,340 --> 00:49:26,520 (Lavasosin) Ja need inimesed lahkuvad vara on veel kahetsed seda. 1130 00:49:26,520 --> 00:49:28,620 Nagu on inimesed rõdul. 1131 00:49:28,620 --> 00:49:32,510 Vabandan ette, et inimesed on rõdu põhjustel, mis on 1132 00:49:32,510 --> 00:49:33,920 selge hetk. 1133 00:49:33,920 --> 00:49:37,050 >> Nii et meil on õnnelik, et on üks CS50 endine juht õpetamise stipendiaatide kell 1134 00:49:37,050 --> 00:49:39,302 firma nimega dropbox.com. 1135 00:49:39,302 --> 00:49:45,500 Nad on väga heldelt annetatud kuponkikoodi siin nii palju ruumi, 1136 00:49:45,500 --> 00:49:48,180 mis on üles tavaliselt 2 gigabaiti. 1137 00:49:48,180 --> 00:49:51,740 Niisiis, mida ma arvasin, et me teeks seda Lõpetuseks on teha natuke give 1138 00:49:51,740 --> 00:49:55,380 kusjuures vaid hetk, me paljastada võitja ja kes on kupong 1139 00:49:55,380 --> 00:49:57,980 kood, mis saab siis minna oma kodulehel, kirjuta see ja voila, saada 1140 00:49:57,980 --> 00:50:01,370 palju rohkem Dropbox ruumi oma seadme ja oma isiklikke faile. 1141 00:50:01,370 --> 00:50:05,690 >> Ja esimene, kes sooviksid osaleda Selles joonisel? 1142 00:50:05,690 --> 00:50:09,630 OK, nüüd, mis muudab ta isegi lõbusam. 1143 00:50:09,630 --> 00:50:14,010 Isik, kes saab see 25 GB kuponkikoodi - mis on palju 1144 00:50:14,010 --> 00:50:16,150 ahvatlevamaks kui hilja päeva nüüd, ehk - 1145 00:50:16,150 --> 00:50:20,620 on see, kes istub peal istmepadja all, mis on 1146 00:50:20,620 --> 00:50:21,620 et kuponkikoodi. 1147 00:50:21,620 --> 00:50:23,480 Nüüd võite vaadata all oma istmepadja. 1148 00:50:23,480 --> 00:50:28,710 1149 00:50:28,710 --> 00:50:29,680 >> [VIDEO PLAYBACK] 1150 00:50:29,680 --> 00:50:31,620 >> -Üks, kaks, kolm. 1151 00:50:31,620 --> 00:50:35,015 >> [Karjuvad] 1152 00:50:35,015 --> 00:50:35,985 >> -Sa saad auto! 1153 00:50:35,985 --> 00:50:36,670 Sa saad auto! 1154 00:50:36,670 --> 00:50:37,970 >> DAVID Malan: Me näeme, sa kolmapäeval. 1155 00:50:37,970 --> 00:50:38,904 >> -Sa saad auto! 1156 00:50:38,904 --> 00:50:39,371 Sa saad auto! 1157 00:50:39,371 --> 00:50:40,305 Sa saad auto! 1158 00:50:40,305 --> 00:50:41,706 Sa saad auto! 1159 00:50:41,706 --> 00:50:43,107 Sa saad auto! 1160 00:50:43,107 --> 00:50:45,530 >> DAVID Malan: Rõdu inimesed, tulge siia alla ees, 1161 00:50:45,530 --> 00:50:46,866 kus meil on lisad. 1162 00:50:46,866 --> 00:50:50,282 >> -Kőik saab auto! 1163 00:50:50,282 --> 00:50:52,234 Igaüks saab auto! 1164 00:50:52,234 --> 00:50:52,722 >> [END VIDEO PLAYBACK] 1165 00:50:52,722 --> 00:50:54,590 >> Jutustaja: Järgmisel CS50 - 1166 00:50:54,590 --> 00:51:00,374 >> SPEAKER 5: Issake jumal jumal jumal issand jumal jumal jumal jumal jumal - 1167 00:51:00,374 --> 00:51:02,106 >> [Ukelele PLAYS]