1 00:00:00,000 --> 00:00:11,100 >> [Mūzikas atskaņošanas] 2 00:00:11,100 --> 00:00:11,490 >> DAVID J. Malan: Nu labi. 3 00:00:11,490 --> 00:00:12,170 Tik laipni atpakaļ. 4 00:00:12,170 --> 00:00:15,180 Tas ir CS50, un ir beigām, trīs nedēļas. 5 00:00:15,180 --> 00:00:17,770 >> Tātad atgādināt vairāku pēdējo nedēļu laikā, mēs esam izdevumu diezgan daudz 6 00:00:17,770 --> 00:00:20,820 laiks C, uz plānošanu, par sintaksi. 7 00:00:20,820 --> 00:00:24,680 Un tas ir pavisam normāli, ja jūs joprojām cīnās ar problēmu Set 2, lai būtu 8 00:00:24,680 --> 00:00:25,950 banging galvu pret sienu. 9 00:00:25,950 --> 00:00:28,310 Tas ir mistisks vērstu kļūdu ziņojumi un bugs, ka jūs 10 00:00:28,310 --> 00:00:29,220 nevar gluži tramdīt leju. 11 00:00:29,220 --> 00:00:32,310 Jo, drošs, ka tikai Dažu nedēļu laikā jūs varēsiet atskatīties uz 12 00:00:32,310 --> 00:00:35,930 lietas, piemēram, Cēzara, un [? V-genair,?] varbūt pat kreka, un 13 00:00:35,930 --> 00:00:40,050 saprast, cik tālu Jūs esat nonācis īsā laika periodā. 14 00:00:40,050 --> 00:00:43,670 Tātad, ja tas ir kāds mierinājums, karājas tur tagad. 15 00:00:43,670 --> 00:00:46,610 >> Šodien, lai gan, mēs sākam pāreju līdz lietas augstākā līmenī. 16 00:00:46,610 --> 00:00:49,820 Un mēs sākam pieņemt par pašsaprotamu, ka jūs guys zināt, kā programma, vai 17 00:00:49,820 --> 00:00:52,090 vismaz iesākums ka komforta līmeni. 18 00:00:52,090 --> 00:00:56,520 Un mēs sākam apsvērt, kā mēs varam iet par projektēšana programmu vairāk 19 00:00:56,520 --> 00:00:57,440 efektīvi. 20 00:00:57,440 --> 00:01:01,090 Kā mēs varam iet par optimizēt efektivitāti mūsu algoritmiem, un 21 00:01:01,090 --> 00:01:03,110 parasti risināšanā vairāk interesanti problēmas. 22 00:01:03,110 --> 00:01:06,850 Un sāk pieņemt par pašsaprotamu, ka, ja mēs vēlējāmies, mēs varētu kodēt nekādus 23 00:01:06,850 --> 00:01:08,350 no piemēriem ir prātā. 24 00:01:08,350 --> 00:01:11,430 Tātad šodien, mums nav pieskarties tastatūru jebkura veida kodu. 25 00:01:11,430 --> 00:01:15,150 Tas būs daudz augstākā līmenī, un galu galā, par problēmu risināšanas. 26 00:01:15,150 --> 00:01:20,490 >> Tātad, lai saņemtu uz šo jautājumu, ļaujiet man piedāvāt ka šādi septiņi 27 00:01:20,490 --> 00:01:24,290 taisnstūri veido septiņas durvis, aiz kas ir visai ķekars 28 00:01:24,290 --> 00:01:26,340 numuri, starp kuriem ir skaitlis 50. 29 00:01:26,340 --> 00:01:30,470 Ļaujiet man projekts šo par šo Ekrāns arī šeit. 30 00:01:30,470 --> 00:01:36,770 Un ierosina, ka mums ir nepieciešams brīvprātīgo palīdzēt atrast man numuru priekšā 31 00:01:36,770 --> 00:01:38,140 internets šeit, lai aplūkotu. 32 00:01:38,140 --> 00:01:40,755 Nāciet uz augšu, rozā. 33 00:01:40,755 --> 00:01:43,050 Labi. 34 00:01:43,050 --> 00:01:43,930 Kāds ir Jūsu vārds? 35 00:01:43,930 --> 00:01:44,850 >> Jennifer: [dzirdams] 36 00:01:44,850 --> 00:01:45,170 >> DAVID J. Malan: Atvaino? 37 00:01:45,170 --> 00:01:45,860 >> Jennifer: Jennifer. 38 00:01:45,860 --> 00:01:46,390 >> DAVID J. Malan: Jennifer. 39 00:01:46,390 --> 00:01:46,980 Visas tiesības, Jennifer. 40 00:01:46,980 --> 00:01:47,630 Priecājos ar jums iepazīties. 41 00:01:47,630 --> 00:01:48,370 Nāciet uz augšu. 42 00:01:48,370 --> 00:01:52,430 Tātad, tie šeit ir septiņi durvis, un kādi Es gribētu, lai jūs darīt mums šeit, 43 00:01:52,430 --> 00:01:56,560 priekšā visiem saviem klasesbiedriem, ir mūs atrast numuru, 50. 44 00:01:56,560 --> 00:02:00,860 Lai atrastu numuru, jūs varat palūrēt aiz kāda no šīm durvīm, vienkārši pieskaroties 45 00:02:00,860 --> 00:02:03,030 uz vienas no durvīm, un atklās savu numuru. 46 00:02:03,030 --> 00:02:06,080 Un pieņemsim redzēt, cik ātri jūs var atrast mums numuru, 50. 47 00:02:06,080 --> 00:02:09,979 48 00:02:09,979 --> 00:02:11,229 >> 15. 49 00:02:11,229 --> 00:02:13,110 50 00:02:13,110 --> 00:02:14,360 16. 51 00:02:14,360 --> 00:02:16,270 52 00:02:16,270 --> 00:02:16,530 50. 53 00:02:16,530 --> 00:02:17,350 Labi darīts. 54 00:02:17,350 --> 00:02:18,040 Labi. 55 00:02:18,040 --> 00:02:19,906 Kārta aplausi par Jennifer. 56 00:02:19,906 --> 00:02:21,530 >> [Aplausi] 57 00:02:21,530 --> 00:02:22,320 >> Labi. 58 00:02:22,320 --> 00:02:25,254 Tātad, kādi bija jūsu stratēģija atrast numuru, 50? 59 00:02:25,254 --> 00:02:27,222 >> Jennifer: Um, es domāju, varbūt, ja - 60 00:02:27,222 --> 00:02:27,714 [Dzirdams] 61 00:02:27,714 --> 00:02:28,206 >> DAVID J. Malan: Ak. 62 00:02:28,206 --> 00:02:29,630 Piešķiriet vienu sekundi. 63 00:02:29,630 --> 00:02:32,420 Tātad bija jūsu stratēģija atrast numuru, 50? 64 00:02:32,420 --> 00:02:34,760 >> Jennifer: Tāpēc es tikai sākas sāk redzēt to, ko pirmais numurs 65 00:02:34,760 --> 00:02:38,590 bija, un tad es domāju, varbūt, ja viņi sakārtoti, es ņemšu tikai glabāt 66 00:02:38,590 --> 00:02:39,970 pieskaroties augstāk? 67 00:02:39,970 --> 00:02:40,140 >> DAVID J. Malan: OK. 68 00:02:40,140 --> 00:02:42,910 Un mēs, šķiet, esam atraduši kas ir gadījums. 69 00:02:42,910 --> 00:02:45,670 Lai gan, pieņemsim mizu atpakaļ slāņi tikai mazliet, un jūs vēlaties doties 70 00:02:45,670 --> 00:02:47,640 priekšu un atklāt citas durvis jūs varētu izvēlēties? 71 00:02:47,640 --> 00:02:50,400 72 00:02:50,400 --> 00:02:51,712 >> Jennifer: Ak, mīļais. 73 00:02:51,712 --> 00:02:53,128 >> DAVID J. Malan: Ah. 74 00:02:53,128 --> 00:02:54,280 >> Jennifer: Tāpēc es tikko saņēmu laimīgs. 75 00:02:54,280 --> 00:02:55,270 >> DAVID J. Malan: Tātad jums laimīgs. 76 00:02:55,270 --> 00:02:55,710 Labi. 77 00:02:55,710 --> 00:02:56,795 Tātad nav slikti. 78 00:02:56,795 --> 00:02:58,750 Bet tas ir interesanti ieskatu, vai ne? 79 00:02:58,750 --> 00:03:01,870 Ja jūs pieņemts, un jūs saņemsiet, tiešām, mazliet laimīgs tur. 80 00:03:01,870 --> 00:03:05,350 Bet, ja tu pieņem, ka to skaits bija sakārtoti, jūs varat būt precīzāks 81 00:03:05,350 --> 00:03:08,750 par to, kā tas ietekmē jūsu uzvedība? 82 00:03:08,750 --> 00:03:11,715 >> Jennifer: Tātad, ja tie sakārtoti, es domāju, varbūt mazākā līdz lielākajam. 83 00:03:11,715 --> 00:03:11,970 >> DAVID J. Malan: OK. 84 00:03:11,970 --> 00:03:15,260 >> Jennifer: Vai, ja tas beidzās ar to, tiešām liels, tad vislielākā uz vismazāko. 85 00:03:15,260 --> 00:03:15,540 >> DAVID J. Malan: OK. 86 00:03:15,540 --> 00:03:18,170 Tātad vislielākā uz vismazāko, vai vismazākās līdz lielākais. 87 00:03:18,170 --> 00:03:21,990 Bet ļaujiet man piedāvāt, pieņemsim, ka jums bija gotten nelaimīgs, un pieņemsim, ka viņi 88 00:03:21,990 --> 00:03:26,840 nebija, patiesībā, šķiroti, cik no šīs durvis varētu jums bija palūrēt 89 00:03:26,840 --> 00:03:28,590 aiz ka sliktākajā gadījumā? 90 00:03:28,590 --> 00:03:29,860 >> Jennifer: Visi no tiem. 91 00:03:29,860 --> 00:03:30,420 >> DAVID J. Malan: Visi no tiem. 92 00:03:30,420 --> 00:03:31,740 Tā ļauj vispārināt, ka n. 93 00:03:31,740 --> 00:03:34,790 Tur notiek, ir 7, bet pieņemsim vairāk Parasti saka, tur ir n durvis 94 00:03:34,790 --> 00:03:35,650 ekrāns šeit. 95 00:03:35,650 --> 00:03:40,110 Tātad, sliktākajā gadījumā, jums būtu meklēt aiz 7 durvīm, vai n durvīm. 96 00:03:40,110 --> 00:03:44,140 Un tā tas tiešām ir, tas ir mazliet veiksmi šodien, bet tas tiešām lineārs 97 00:03:44,140 --> 00:03:46,440 algoritms par veidu, pat ja jūs bija sava veida izlaižot apkārt. 98 00:03:46,440 --> 00:03:47,080 Vai tas ir godīgi? 99 00:03:47,080 --> 00:03:47,500 >> Jennifer: Jā. 100 00:03:47,500 --> 00:03:50,000 >> DAVID J. Malan: Nu, ļaujiet man redzēt, ja jūsu stratēģija izmaiņas, ja es pārceļos mūs uz 101 00:03:50,000 --> 00:03:52,190 Mūsu Otrs piemērs šeit ar 7 dažādas durvis. 102 00:03:52,190 --> 00:03:55,240 Paši skaitļi, bet šī reizi, kad tie ir sakārtoti. 103 00:03:55,240 --> 00:03:58,350 Kāds ir jūsu stratēģija šeit būs, mēģinot nodot no sava prāta, kas 104 00:03:58,350 --> 00:03:59,310 pārējie skaitļi bija - 105 00:03:59,310 --> 00:03:59,930 >> Jennifer: OK. 106 00:03:59,930 --> 00:04:02,290 >> DAVID J. Malan: - agrāk? 107 00:04:02,290 --> 00:04:03,180 >> Jennifer: Sāksim ar pirmo. 108 00:04:03,180 --> 00:04:03,540 >> DAVID J. Malan: Nu labi. 109 00:04:03,540 --> 00:04:05,190 Sākt ar pirmo. 110 00:04:05,190 --> 00:04:05,960 4. 111 00:04:05,960 --> 00:04:08,810 Tagad, ja jūs plānojat doties, un kāpēc? 112 00:04:08,810 --> 00:04:10,040 >> Jennifer: 4, ir ļoti mazs. 113 00:04:10,040 --> 00:04:12,500 Tātad, ja viņi veida varbūt mazākā uz lielāko, tas būtu 114 00:04:12,500 --> 00:04:13,290 būt divreiz, ka, un -. 115 00:04:13,290 --> 00:04:13,670 >> DAVID J. Malan: OK. 116 00:04:13,670 --> 00:04:15,990 Let 's redzēt, ko jūs domājat? 117 00:04:15,990 --> 00:04:19,050 >> Jennifer: Mēģiniet pēdējais. 118 00:04:19,050 --> 00:04:19,500 Nice. 119 00:04:19,500 --> 00:04:20,880 >> DAVID J. Malan: Ļoti labi darīts. 120 00:04:20,880 --> 00:04:21,860 Labi. 121 00:04:21,860 --> 00:04:23,010 >> [Aplausi] 122 00:04:23,010 --> 00:04:24,310 >> DAVID J. Malan: OK. 123 00:04:24,310 --> 00:04:26,790 Tātad jūs faktiski dara to briesmīgi, jo tu esi 124 00:04:26,790 --> 00:04:27,700 dara to ļoti labi. 125 00:04:27,700 --> 00:04:31,150 Kas atstāj mūs nespēj veikt konkrētus punktus. 126 00:04:31,150 --> 00:04:32,565 Tātad, pieņemsim mēģināt roll atpakaļ šeit. 127 00:04:32,565 --> 00:04:34,560 >> Jennifer: OK. 128 00:04:34,560 --> 00:04:35,980 >> DAVID J. Malan: Ļoti labi darīts, tomēr. 129 00:04:35,980 --> 00:04:39,060 Tātad jums sākās sākumā, redzējāt, ka tas bija 4, tad jūs 130 00:04:39,060 --> 00:04:40,240 pārvietots uz beigām. 131 00:04:40,240 --> 00:04:42,320 Bet pieņemsim, ka jums nav get laimīgs tur, un pieņemsim, 50 132 00:04:42,320 --> 00:04:42,890 bija kaut kur citur. 133 00:04:42,890 --> 00:04:46,190 Kādas ir jūsu Trešais solis ir bijis? 134 00:04:46,190 --> 00:04:47,680 >> Jennifer: Iet atpakaļ uz sākumu. 135 00:04:47,680 --> 00:04:48,320 >> DAVID J. Malan: Iet atpakaļ līdz sākumā. 136 00:04:48,320 --> 00:04:51,320 Labi, lai jūs esat pieskāries šīs durvis, kas bija 8. 137 00:04:51,320 --> 00:04:51,660 Labi. 138 00:04:51,660 --> 00:04:52,650 Tātad, tas nav 50. 139 00:04:52,650 --> 00:04:55,380 Kur jūs esat izskatījās tālāk? 140 00:04:55,380 --> 00:04:56,720 >> Jennifer: Ja man nav zināt, tie sakārtoti. 141 00:04:56,720 --> 00:04:57,005 >> DAVID J. Malan: Pareizi. 142 00:04:57,005 --> 00:04:58,490 Nu, ja jūs zināt, tie sakārtoti - 143 00:04:58,490 --> 00:04:58,700 >> Jennifer: Ak, zinu, jā. 144 00:04:58,700 --> 00:05:00,910 >> DAVID J. Malan - bet jums nav zināt, kur 50 bija vēl? 145 00:05:00,910 --> 00:05:01,785 >> Jennifer: Just glabāt turpinās. 146 00:05:01,785 --> 00:05:02,130 >> DAVID J. Malan: Nu labi. 147 00:05:02,130 --> 00:05:02,520 Labi. 148 00:05:02,520 --> 00:05:03,800 Uzglabāt iet. 149 00:05:03,800 --> 00:05:05,270 Labi, ka es varu strādāt. 150 00:05:05,270 --> 00:05:05,610 >> Jennifer: OK. 151 00:05:05,610 --> 00:05:07,210 >> DAVID J. Malan: Tagad, ja jūs tikai dodas, lai saglabātu turpinās, kas ir jūsu 152 00:05:07,210 --> 00:05:09,680 algoritms pārgājuši atbalstīja into. 153 00:05:09,680 --> 00:05:10,740 >> Jennifer: lineāra -. 154 00:05:10,740 --> 00:05:11,820 >> DAVID J. Malan: Tā ir sava veida lineāra. 155 00:05:11,820 --> 00:05:13,480 Bet ļaujiet man piedāvāt, lai man likt uz vietas. 156 00:05:13,480 --> 00:05:14,900 Ļaujiet man atsvaidzināt lapā. 157 00:05:14,900 --> 00:05:17,120 pats numurs, pašu vienošanos, pašas durvis. 158 00:05:17,120 --> 00:05:21,350 Bet domāju, ka atpakaļ uz šo pirmo dienu klasē, kad mēs saplēsa tālruņa grāmatu 159 00:05:21,350 --> 00:05:25,480 puse, veida, un to, kas bija mūsu stratēģija tur? 160 00:05:25,480 --> 00:05:26,450 >> Jennifer: Sāciet vidū. 161 00:05:26,450 --> 00:05:26,690 >> DAVID J. Malan: OK. 162 00:05:26,690 --> 00:05:27,610 Tātad, sākt pa vidu. 163 00:05:27,610 --> 00:05:28,790 Tāpēc iesim uz priekšu un simulēt to. 164 00:05:28,790 --> 00:05:30,720 Sākt pa vidu ar atklājot, ka durvis. 165 00:05:30,720 --> 00:05:31,660 Tātad skaitlis 16. 166 00:05:31,660 --> 00:05:35,290 Tātad, kas būtu spēcīgs puisis ir izdarīts, kurš saplēsa telefona grāmatu pusē, 167 00:05:35,290 --> 00:05:38,450 nokļūt uz nākamo guess? 168 00:05:38,450 --> 00:05:39,400 >> Jennifer: Go šajā pusē. 169 00:05:39,400 --> 00:05:41,700 >> DAVID J. Malan: Un kāpēc uz labo pusi? 170 00:05:41,700 --> 00:05:43,900 >> Jennifer: Ja tie bija sava veida mazākā uz lielāko, tad 50 būtu 171 00:05:43,900 --> 00:05:44,720 šajā sakarā. 172 00:05:44,720 --> 00:05:44,920 >> DAVID J. Malan: Labi. 173 00:05:44,920 --> 00:05:45,390 Pilnīgi pamatoti. 174 00:05:45,390 --> 00:05:48,380 Tātad, piemēram, tālruņa grāmatu, jūs doties uz pa labi, nevis pa kreisi, bet šeit 175 00:05:48,380 --> 00:05:49,500 ir galvenais takeaway. 176 00:05:49,500 --> 00:05:53,930 Jūs tagad varat mest prom, vai noplēst, puse no šīs problēmas, atstājot jūs ne 177 00:05:53,930 --> 00:05:55,970 ar 7 durvīm, bet tiešām ar 3 tikai. 178 00:05:55,970 --> 00:05:57,870 Kas ir aptuveni puse no lielums problēmu. 179 00:05:57,870 --> 00:05:58,350 Labi. 180 00:05:58,350 --> 00:06:01,890 Tātad tagad, ko jūs būtu izdarīts pēc tam, kad iet labi? 181 00:06:01,890 --> 00:06:05,870 >> Jennifer: Tātad 16 joprojām ir diezgan mazs, salīdzinot ar 50, tāpēc varbūt es mēģināšu, 182 00:06:05,870 --> 00:06:06,700 piemēram, šo vienu. 183 00:06:06,700 --> 00:06:07,890 >> DAVID J. Malan: Nu labi. 184 00:06:07,890 --> 00:06:08,720 42. 185 00:06:08,720 --> 00:06:10,830 Labi, tāpēc tagad to, kas ir jūsu instinkts stāsta jums? 186 00:06:10,830 --> 00:06:12,100 >> Jennifer: Es varu mest prom šo un tad tikai - 187 00:06:12,100 --> 00:06:12,360 >> DAVID J. Malan: OK. 188 00:06:12,360 --> 00:06:14,212 Labi, jūs varat mest prom kreiso pusi tur. 189 00:06:14,212 --> 00:06:14,890 >> Jennifer: - izvēlēties šo vienu. 190 00:06:14,890 --> 00:06:15,530 >> DAVID J. Malan: Un labi. 191 00:06:15,530 --> 00:06:15,760 >> Jennifer: Jā. 192 00:06:15,760 --> 00:06:17,820 >> DAVID J. Malan: Tātad, pat ja tas ir grūti redzēt, varbūt, ja tur ir tikai 193 00:06:17,820 --> 00:06:21,320 7 durvis, domā par to, kas tagad, konsekvence 194 00:06:21,320 --> 00:06:22,620 algoritms, jūs vienkārši piemērot. 195 00:06:22,620 --> 00:06:24,510 Iepriekšējā gadījumā, jūs paveiksies, kas bija lieliski. 196 00:06:24,510 --> 00:06:26,540 Bet jūs izmantojat heiristisko, Es teiktu. 197 00:06:26,540 --> 00:06:29,150 Tu izmanto veida savu instinktu, un zinot to sakārtoti, ja tas ir diezgan 198 00:06:29,150 --> 00:06:31,600 mazs sākumā, protams, mēs esam got iet vairāk uz labo pusi. 199 00:06:31,600 --> 00:06:34,990 Bet zināmā mērā, jums laimīgs, jo varbūt tas bija skaitlis 100, 200 00:06:34,990 --> 00:06:36,220 un varbūt 50 bija pa vidu. 201 00:06:36,220 --> 00:06:37,910 Varbūt 50 bija pat vairāk nekā šeit. 202 00:06:37,910 --> 00:06:40,960 >> Bet ko jūs nedaudz savādāk šoreiz bija, jūs pats 203 00:06:40,960 --> 00:06:42,150 atkal un atkal. 204 00:06:42,150 --> 00:06:45,310 Un es teiktu, ka tas, ko jūs tikko tomēr, lai gan ietekmē tālruni 205 00:06:45,310 --> 00:06:48,100 grāmata, piemēram, ir kaut kas daudz vairāk algoritmiskās, un daudz 206 00:06:48,100 --> 00:06:49,930 mazāk īpašu cased. 207 00:06:49,930 --> 00:06:51,620 Daudz mazāk instinktīvs. 208 00:06:51,620 --> 00:06:57,160 Tātad, kas galu galā, kā būtu Jūs raksturotu efektivitātes 209 00:06:57,160 --> 00:07:00,530 Pirmais algoritms, kur jums gāja kreisās uz labo pusi, salīdzinot 210 00:07:00,530 --> 00:07:03,430 Otrais algoritms šeit? 211 00:07:03,430 --> 00:07:06,460 >> Jennifer: Tas viens ir, piemēram, varbūt uz pusi samazināt laiku, vai pat vairāk, jā. 212 00:07:06,460 --> 00:07:07,320 >> DAVID J. Malan: Labi, varbūt pat vairāk. 213 00:07:07,320 --> 00:07:10,150 Let 's push nedaudz grūtāk par to. 214 00:07:10,150 --> 00:07:13,030 Kas īsti, ja mēs turpināsim šo loģika, mēs noteikti uz pusi 215 00:07:13,030 --> 00:07:15,830 darba laiku, ar šo otro algoritmu metot prom pusi 216 00:07:15,830 --> 00:07:18,470 numurus, bet to, ko mēs izdarījām par nākamo atkārtojuma, kad Jennifer atklāja 217 00:07:18,470 --> 00:07:20,615 otrais numurs? 218 00:07:20,615 --> 00:07:22,830 >> Mēs pusi skaitu durvis atkal. 219 00:07:22,830 --> 00:07:25,270 Un tad ko mēs izdarījām pēc tam, ja tur bija vairāk durvis, lai spēlēt ar? 220 00:07:25,270 --> 00:07:27,520 Mēs vēlētos pusi samazināt tos, un atkal, un atkal, un atkal. 221 00:07:27,520 --> 00:07:30,420 Un tas bija tāpat kā jums, puiši visu stāv augšā pirmajā nedēļā 222 00:07:30,420 --> 00:07:33,000 klasē, puse no jums sēžot, puse no jums sēžot, pusi no jums 223 00:07:33,000 --> 00:07:35,440 sēžot, kamēr viens vientuļš dvēsele stāvēja. 224 00:07:35,440 --> 00:07:39,050 Un mēs teicām, ka darbības laiks ka, pakāpienu skaits, kas bija bija 225 00:07:39,050 --> 00:07:40,430 uz rīkojumu, ko? 226 00:07:40,430 --> 00:07:41,230 >> SPEAKER 1: [dzirdams] 227 00:07:41,230 --> 00:07:43,970 >> DAVID J. Malan: Tātad log bāze 2 no n, vai tikai vēl vienkāršāk, log n. 228 00:07:43,970 --> 00:07:45,060 Lai kaut logaritmiska. 229 00:07:45,060 --> 00:07:48,380 Un grafikā nav taisna līnija ka tikko ieguva arvien sliktāk un sliktāk, tas bija 230 00:07:48,380 --> 00:07:52,490 tas interesanti līkne, kas nav saņemt tik slikti laika gaitā. 231 00:07:52,490 --> 00:07:53,910 Tātad, pieņemsim turēt uz šo ideju. 232 00:07:53,910 --> 00:07:54,690 Let 's paldies Jennifer. 233 00:07:54,690 --> 00:07:56,150 Paldies tik daudz, lai nāk uz augšu. 234 00:07:56,150 --> 00:07:57,400 Un, viens sek. 235 00:07:57,400 --> 00:08:00,170 236 00:08:00,170 --> 00:08:02,925 Nav galda lampas šodien, bet mēs Vai ir CS50 stresa bumbas. 237 00:08:02,925 --> 00:08:03,420 >> Jennifer: Yay. 238 00:08:03,420 --> 00:08:04,410 >> DAVID J. Malan: Nu labi, šeit. 239 00:08:04,410 --> 00:08:06,545 Paldies, uzņemoties stress šeit. 240 00:08:06,545 --> 00:08:07,350 Labi. 241 00:08:07,350 --> 00:08:10,620 Tātad, pieņemsim redzēt, ja mēs varam ne tagad formalizēt šo mazliet vairāk. 242 00:08:10,620 --> 00:08:14,820 Tātad vēlreiz, ko mēs tikko izdarījām, bija būtībā tas pats, kā mēs to darījām 243 00:08:14,820 --> 00:08:16,660 šajā pirmajā nedēļā. 244 00:08:16,660 --> 00:08:23,780 Bet nevis beigās tikai ar lineāru algoritms, ko mēs attēlota 245 00:08:23,780 --> 00:08:27,210 agrāk kā šīs taisnu līniju, saskaņā ar kuru, ja mēs ieliekam vēl vienu durvis 246 00:08:27,210 --> 00:08:29,610 ekrāns, tad Jennifer būtu nācās meklēt, iespējams, 247 00:08:29,610 --> 00:08:30,600 Aiz vēl vienu durvīm. 248 00:08:30,600 --> 00:08:33,490 Ja mēs uzdodam vēl divas durvis, viņa varētu būt meklēt aiz vēl divas durvis. 249 00:08:33,490 --> 00:08:35,990 >> Un tā, tur bija šī lineārā attiecības starp lielumu 250 00:08:35,990 --> 00:08:39,059 problēma, teiksim, x-ass, un laika daudzums, kas nepieciešams, lai 251 00:08:39,059 --> 00:08:40,440 atrisināt uz y. 252 00:08:40,440 --> 00:08:43,330 Bet bilde man bija atsaucoties uz agrāk bija šī zaļo līniju. 253 00:08:43,330 --> 00:08:45,970 Zaļš apzināti, jo tas vienkārši jutās labāk. 254 00:08:45,970 --> 00:08:49,790 Teorētiski, algoritms, kad mēs to paveicām ar telefona grāmatu, kad mēs to paveicām 255 00:08:49,790 --> 00:08:52,420 ar jums puiši skaitīšanas viens otru, un Otrajā gadījumā, kad Jennifer vienkārši 256 00:08:52,420 --> 00:08:55,250 to darīja šeit, tas bija sava veida fundamentāli labāk. 257 00:08:55,250 --> 00:08:57,180 Jo tas bija ne tikai divreiz ātrāk. 258 00:08:57,180 --> 00:08:58,870 Tas nebija pat četras reizes ātrāk. 259 00:08:58,870 --> 00:09:03,290 Tas bija pilnīgi atkarīgs no kāda izmērs no ieejas ir, kā uz cik daudz 260 00:09:03,290 --> 00:09:05,220 pasākumiem, ko tā galu galā bija. 261 00:09:05,220 --> 00:09:08,040 >> Un tā tas vienkārši ideja, ka mēs visi ņēma par pašsaprotamu ar tālruņu grāmatu, 262 00:09:08,040 --> 00:09:10,200 var līdzīgi piemērot lai kaut kas līdzīgs šim. 263 00:09:10,200 --> 00:09:12,380 Un tas varētu būt vairāk pagadās pazīstams kā, kā jūs varētu 264 00:09:12,380 --> 00:09:13,940 iedomāties, skaldi un valdi. 265 00:09:13,940 --> 00:09:16,390 Ne atšķirībā no to, ko mēs darījām, protams, ar tālruņu grāmatu. 266 00:09:16,390 --> 00:09:18,300 >> Bet pseudocode, atsaukšana, bija šī. 267 00:09:18,300 --> 00:09:21,800 Tāpēc mēs nevarēsim darīt atkal, bet atcerēties ka pirmo nedēļu, mums visiem piecēlās 268 00:09:21,800 --> 00:09:25,140 un tad puse no jums apsēdās, puse tu apsēdies, puse no jums apsēdās. 269 00:09:25,140 --> 00:09:29,280 Šis algoritms tika realizēts mazliet par krāpšanos veidā, ar to, ka, tā 270 00:09:29,280 --> 00:09:32,870 bija ne tikai viena no manis skaitīšana, būtiski, efektīvāk. 271 00:09:32,870 --> 00:09:35,830 Tādā gadījumā, man bija piesaistot sekundārā resurss. 272 00:09:35,830 --> 00:09:39,470 Kārtot, vairāku CPU, vairākas smadzenes, vairākas smart cilvēki 273 00:09:39,470 --> 00:09:42,740 istaba bija palīdzēt man iegūt no kaut lineārs kaut 274 00:09:42,740 --> 00:09:45,190 logaritmiska, no kaut kā sarkanas līdz kaut zaļu. 275 00:09:45,190 --> 00:09:48,650 >> Bet šajā gadījumā, Jennifer vien var būtiski uzlabo 276 00:09:48,650 --> 00:09:52,370 sniegums savu pirmo algoritmu, ko, atkal, tikai domāju nedaudz grūtāk. 277 00:09:52,370 --> 00:09:56,650 Un tagad, kad runa ir laiks, lai īstenotu šīs lietas, norādītas 278 00:09:56,650 --> 00:10:00,670 kāda rindiņas kodu, jūs varat rakstīt tādas ka jūs varat atkārtot tos atkal, un 279 00:10:00,670 --> 00:10:03,350 atkal, un atkal, sava veida kas looping veidā. 280 00:10:03,350 --> 00:10:06,370 Tāpēc, ka jūs neesat nāksies luksusa, piemēram, Jennifer darīja sākumā, lai 281 00:10:06,370 --> 00:10:10,460 vienkārši ir visai ķekars IF un teikt, hmm, ja šis pirmais skaitlis ir 4, 282 00:10:10,460 --> 00:10:11,800 ļaujiet man lēkt visu ceļu līdz beigām. 283 00:10:11,800 --> 00:10:14,180 Ooh, ja šis skaits ir pārāk liels, ļaujiet man pārvietoties patvaļīgi atpakaļ 284 00:10:14,180 --> 00:10:15,220 līdz otrā elementa. 285 00:10:15,220 --> 00:10:18,210 Jūs atradīsiet, ka tas būs daudz grūtāk noformēt to, ko mēs cilvēki 286 00:10:18,210 --> 00:10:21,270 pieņemt par pašsaprotamu, jo ļoti saprātīgs heiristikas, bet dators ir tikai 287 00:10:21,270 --> 00:10:23,260 gatavojas darīt to, kas jums pateiks to darīt. 288 00:10:23,260 --> 00:10:25,280 >> Tagad tas ir ļoti interesanti ietekme. 289 00:10:25,280 --> 00:10:29,950 Šajā grafikā ir sava veida domāts, lai sakārtotu ar apbērt vizuāli, bet paziņojums, kurā 290 00:10:29,950 --> 00:10:32,230 ir taisna līnija šajā grafikā? 291 00:10:32,230 --> 00:10:35,330 Kur ir lineāra diagramma ka mēs saucam n? 292 00:10:35,330 --> 00:10:37,580 Nu, tas ir sava veida virzienā no apakšas ar šo attēlu, vai ne? 293 00:10:37,580 --> 00:10:40,500 Tātad, visi mēs esam darījuši, ir, mēs esam sava veida attālināt līdz x-ass un 294 00:10:40,500 --> 00:10:44,780 y-ass, lai mēģinātu iegūt sajūtu par to, kas cita veida līknes izskatās. 295 00:10:44,780 --> 00:10:47,760 >> Un specifiku matemātisko izteiksmes šodien nav svarīgi tik 296 00:10:47,760 --> 00:10:52,440 daudz, bet paziņo, ka tur ir daudz algoritmi, kas ir daudz sliktāk, nekā 297 00:10:52,440 --> 00:10:53,470 kaut kas ir lineāra. 298 00:10:53,470 --> 00:10:55,410 Patiešām, kubā n izskatās diezgan slikti. 299 00:10:55,410 --> 00:10:58,400 2 līdz n izskatās diezgan slikti. n kvadrātā izskatās diezgan slikti. 300 00:10:58,400 --> 00:11:01,630 Un mēs redzēsim, ko daži no tiem, varētu būt patiesībā šodien. 301 00:11:01,630 --> 00:11:05,430 Un log n nejūtas tik slikti, bet labāk nekā n ir log bāze 2 no n. 302 00:11:05,430 --> 00:11:08,080 Bet jūs zināt, tas būtu bijis vēl vairāk pārsteidzoša, ja Jennifer, vai ja mēs, 303 00:11:08,080 --> 00:11:12,910 ka pirmajā nedēļā, bija jānāk klajā ar kaut kas ir log log n. 304 00:11:12,910 --> 00:11:15,880 >> Tātad, citiem vārdiem sakot, tas viss virkne iespējamo risinājumu 305 00:11:15,880 --> 00:11:18,570 problēmas, bet pat šeit, paziņojums to, kas notiks. 306 00:11:18,570 --> 00:11:22,910 Kad es zoom out, kura no šīm līknēm gatavojas izrādīties absolūti 307 00:11:22,910 --> 00:11:26,630 sliktākais no uz ekrāna tiem tagad? 308 00:11:26,630 --> 00:11:28,680 Tātad n kubā izskatas slikti brīdī. 309 00:11:28,680 --> 00:11:32,470 Bet, ja mēs tālināt un redzēt vairāk x un y asi, kas dodas uz 310 00:11:32,470 --> 00:11:34,550 dominē galu galā? 311 00:11:34,550 --> 00:11:37,120 Tātad tas faktiski izrādās, ka 2 līdz n, un jūs varat skaitlis šo out, vienkārši 312 00:11:37,120 --> 00:11:39,990 tapām dažās arvien lielāku numuru, un jūs redzēsiet, ka 2 313 00:11:39,990 --> 00:11:42,070 n, protams, kļūst lielāka daudz ātrāk. 314 00:11:42,070 --> 00:11:45,530 Ja mēs patiešām tālināt, ar 2, lai n algoritms absolūti sūkā. 315 00:11:45,530 --> 00:11:48,170 Es domāju tas ir gatavojas veikt pavisam nedaudz laika, lai 316 00:11:48,170 --> 00:11:49,460 datoru, lai kannu cauri. 317 00:11:49,460 --> 00:11:52,500 >> Bet jūs redzēsiet laika gaitā, jo īpaši ar nākotnes problēmu kopas, un pat 318 00:11:52,500 --> 00:11:55,600 galīgie projekti ir jūsu dati kas izpaužas liels, labi? 319 00:11:55,600 --> 00:11:58,300 Pat pirmajā versijas Facebook, cik draugu, un 320 00:11:58,300 --> 00:12:01,840 Reģistrēto lietotāju skaits got liels, Jūs varat kārtot par telefonu tas ir, un 321 00:12:01,840 --> 00:12:05,530 ieviest kaut ko ar lineāro meklēšanu, vai arī ļoti vienkāršs šķirošana 322 00:12:05,530 --> 00:12:07,030 algoritmu, kā mēs redzam šodien. 323 00:12:07,030 --> 00:12:09,280 Jums ir jāsāk domāt grūtāk un grūtāk par šīm problēmām. 324 00:12:09,280 --> 00:12:12,070 Un veida problēmām vietās, piemēram, Facebook un Google un Microsoft, 325 00:12:12,070 --> 00:12:16,350 un citi strādā pie tieši šiem kārtot lielo datu veida jautājumiem 326 00:12:16,350 --> 00:12:18,530 arvien vairāk šajās dienās. 327 00:12:18,530 --> 00:12:18,900 >> Labi. 328 00:12:18,900 --> 00:12:23,800 Tātad Dženiferas panākumiem, ka otrais algoritms, atklāti sakot, viņa bija pārsteidzoši 329 00:12:23,800 --> 00:12:26,110 arī pirmo reizi, bet, pieņemsim rakstīt to kā veiksmi, lai mēs 330 00:12:26,110 --> 00:12:27,000 var padarīt šo jautājumu. 331 00:12:27,000 --> 00:12:30,970 Otrajā gadījumā, viņa parādi algoritms, kas atkārtojas atkal un 332 00:12:30,970 --> 00:12:34,670 atkal, bet viņa ņēma par pašsaprotamu drošs pieņēmums, ka mēs atļāvām 333 00:12:34,670 --> 00:12:39,370 viņai, bet viņa izmanto daži dati otrā reize, kad viņai nebija 334 00:12:39,370 --> 00:12:39,840 pirmo reizi. 335 00:12:39,840 --> 00:12:41,800 Kas bija tas, ko? 336 00:12:41,800 --> 00:12:43,050 >> Šis saraksts tika sakārtots. 337 00:12:43,050 --> 00:12:46,350 Tātad, tiklīdz saraksts tika sakārtoti, mēs apgalvo, ka Jennifer varēja izdarīt 338 00:12:46,350 --> 00:12:47,480 fundamentāli labāk. 339 00:12:47,480 --> 00:12:51,450 7 durvis, jā, nav tik interesanti, bet pieņemsim, ka to mēs esam 7 miljoni durvis. 340 00:12:51,450 --> 00:12:54,080 Log n ir noteikti gatavojas , lai veiktu daudz, daudz 341 00:12:54,080 --> 00:12:55,610 ātrāk ilgtermiņā. 342 00:12:55,610 --> 00:12:58,880 Bet viņa bija jābūt durvis sakārtoti viņai. 343 00:12:58,880 --> 00:13:02,320 Tagad, man bija atļaušos darām iepriekš uz datora ekrāna 344 00:13:02,320 --> 00:13:05,160 šeit, bet pieņemsim, ka Jennifer nācās darīt sev? 345 00:13:05,160 --> 00:13:10,120 Pieņemsim, ka durvis attiecīgie pārstāvēti datus datu bāzē, vai 346 00:13:10,120 --> 00:13:14,260 draugi reģistrējušies Facebook, vai visi mājas lapas internetā, kas 347 00:13:14,260 --> 00:13:16,880 dažādās tīmekļa vietnēs varētu būt vajadzīga indeksēt vai meklēt vairāk. 348 00:13:16,880 --> 00:13:20,940 >> Pieņemsim, ka jūs tikko bija izejas dati noteikt un tas tika atstāts, lai jūs, vai 349 00:13:20,940 --> 00:13:23,010 Jennifer to darīt šķirošanu? 350 00:13:23,010 --> 00:13:26,950 Tas drīzāk prasa, lai mēs atbildētu jautājums, labi, cik daudz laika 351 00:13:26,950 --> 00:13:31,080 būtu jāņem Jennifer, vai pat mani, kārtot šos numurus iepriekš, lai 352 00:13:31,080 --> 00:13:32,680 ka viņa varētu gūt labumu no tā? 353 00:13:32,680 --> 00:13:32,880 Labi? 354 00:13:32,880 --> 00:13:36,620 Jo Ietekme, protams, ir ja tas notiek man diezgan, bet, lai sakārtotu 355 00:13:36,620 --> 00:13:40,800 numuri, kas heck rūpējas, ka jums varat atrast vairākas, piemēram, 50 tik ātri, 356 00:13:40,800 --> 00:13:44,850 kā arī Dženiferas gadījumā, ja mēs vairāk nekā nomākti apjomu kopējā laika 357 00:13:44,850 --> 00:13:46,920 tas notika pēc šķirošanas lietas iepriekš? 358 00:13:46,920 --> 00:13:49,320 >> Tātad, pieņemsim redzēt, ja mēs nevaram krāsu attēlu šeit. 359 00:13:49,320 --> 00:13:51,370 Man ir visai ķekars vairāk uzsvērt bumbiņas, ja tas palīdz 360 00:13:51,370 --> 00:13:52,270 lauzt ledu šeit. 361 00:13:52,270 --> 00:13:55,690 Un, ja jūs neiebilstat, mēs nepieciešams septiņi brīvprātīgie - 362 00:13:55,690 --> 00:13:57,060 gada, OK. 363 00:13:57,060 --> 00:13:57,240 Wow. 364 00:13:57,240 --> 00:13:59,250 Tāpēc mums nav jātērē uz galda lampas, šķiet. 365 00:13:59,250 --> 00:13:59,690 Labi. 366 00:13:59,690 --> 00:14:01,530 Tā kā par tevi divi priekšā. 367 00:14:01,530 --> 00:14:04,160 Kā par jums divi puiši, kas aizmugurē. 368 00:14:04,160 --> 00:14:04,870 Tāpēc, ka ir četri. 369 00:14:04,870 --> 00:14:09,890 Kā par jums priekšā pieci, seši un septiņi. 370 00:14:09,890 --> 00:14:10,320 Labi tur. 371 00:14:10,320 --> 00:14:13,260 Jūsu drauga norādot tevi, lai jūs iegūtu balvu. 372 00:14:13,260 --> 00:14:13,700 >> Labi. 373 00:14:13,700 --> 00:14:14,410 Nāciet uz augšu. 374 00:14:14,410 --> 00:14:17,120 Un kāpēc nav mēs esam jums puiši nāk vairāk nekā šeit. 375 00:14:17,120 --> 00:14:18,960 Es esmu gatavojas sniegt jums katru numuru. 376 00:14:18,960 --> 00:14:22,150 Un iet uz priekšu, un sakārtot sevi vienāds ar to, kas ir 377 00:14:22,150 --> 00:14:25,180 attēlots uz ekrāna. 378 00:14:25,180 --> 00:14:26,530 >> [Interposing Voices] 379 00:14:26,530 --> 00:14:28,160 >> DAVID J. Malan: OOP, sorry. 380 00:14:28,160 --> 00:14:30,210 Bug. 381 00:14:30,210 --> 00:14:32,180 Labi. 382 00:14:32,180 --> 00:14:32,750 Nu, šeit mēs iet. 383 00:14:32,750 --> 00:14:34,180 Numuru pieci. 384 00:14:34,180 --> 00:14:35,136 Seši numurs. 385 00:14:35,136 --> 00:14:37,770 Viens, divi, trīs, četru, piecu, sešu, septiņu. 386 00:14:37,770 --> 00:14:39,410 Ak, tas ir neērts. 387 00:14:39,410 --> 00:14:41,210 >> SPEAKER 2: Es ņemšu tikai iegūt -. 388 00:14:41,210 --> 00:14:41,900 >> DAVID J. Malan: Labi darījumu. 389 00:14:41,900 --> 00:14:43,130 Labi. 390 00:14:43,130 --> 00:14:44,611 Paldies par dalību. 391 00:14:44,611 --> 00:14:47,200 >> [Aplausi] 392 00:14:47,200 --> 00:14:48,580 >> Labi. 393 00:14:48,580 --> 00:14:48,860 Labi. 394 00:14:48,860 --> 00:14:51,970 Tātad mums ir četri, divi, seši, viens, trīs, septiņi, pieci. 395 00:14:51,970 --> 00:14:56,010 Perfect tāpēc mums ir septiņi brīvprātīgie šeit, kas ir vienāds ar platumu, lai 396 00:14:56,010 --> 00:14:57,430 masīvs, ka mēs esam spēlē ar agrāk. 397 00:14:57,430 --> 00:14:59,470 Un es izvēlējos septiņus iemeslu dēļ ka būs tikai 398 00:14:59,470 --> 00:15:00,840 ērts mazliet. 399 00:15:00,840 --> 00:15:04,400 Un es esmu gatavojas ierosināt ka, pirmkārt, mēs šķirot šos septiņus brīvprātīgos. 400 00:15:04,400 --> 00:15:06,786 Ja vēlaties, pirmkārt, teikt hello, lai gan. 401 00:15:06,786 --> 00:15:08,970 Tā kā šī būs neērts vairākas minūtes. 402 00:15:08,970 --> 00:15:10,370 Ieviest sevi. 403 00:15:10,370 --> 00:15:10,980 >> GRACE: Sveiki, es esmu Grace. 404 00:15:10,980 --> 00:15:14,190 Es esmu otrā kursa students, kas Leverett namā. 405 00:15:14,190 --> 00:15:14,620 >> BRANSON: Hi. 406 00:15:14,620 --> 00:15:15,620 Es esmu Branson. 407 00:15:15,620 --> 00:15:16,920 Es esmu pirmkursnieks metināt. 408 00:15:16,920 --> 00:15:19,755 409 00:15:19,755 --> 00:15:20,230 >> Gabe: Hi. 410 00:15:20,230 --> 00:15:21,040 Es esmu Gabe. 411 00:15:21,040 --> 00:15:22,300 Es esmu junioru Cabot. 412 00:15:22,300 --> 00:15:24,826 413 00:15:24,826 --> 00:15:25,980 >> Neil: Es esmu Neil. 414 00:15:25,980 --> 00:15:29,090 Es esmu pirmkursnieks Matthews. 415 00:15:29,090 --> 00:15:29,550 >> Jason: Es esmu Jason. 416 00:15:29,550 --> 00:15:32,816 Es esmu pirmkursnieks Greenough. 417 00:15:32,816 --> 00:15:33,700 >> MIKE: Es esmu Mike. 418 00:15:33,700 --> 00:15:37,360 Es esmu pirmkursnieks Grays. 419 00:15:37,360 --> 00:15:37,990 >> JESS: Es esmu Jess. 420 00:15:37,990 --> 00:15:40,313 Es esmu otrā kursa students, kas Leverett. 421 00:15:40,313 --> 00:15:41,300 >> DAVID J. Malan: Excellent. 422 00:15:41,300 --> 00:15:41,850 Labi. 423 00:15:41,850 --> 00:15:44,190 Nu, paldies visiem mūsu brīvprātīgie šeit līdz šim. 424 00:15:44,190 --> 00:15:47,110 Un pie rokas uzdevums šobrīd notiek jābūt, lai sakārtotu šos puiši, bet pēc tam 425 00:15:47,110 --> 00:15:50,250 mēs esam nāksies domāt nedaudz grūti par to, cik efektīvi mēs patiesībā 426 00:15:50,250 --> 00:15:51,110 sakārtoti tos. 427 00:15:51,110 --> 00:15:52,580 Tātad, pieņemsim vispirms izmēģināt šo. 428 00:15:52,580 --> 00:15:55,970 Jūs guys var redzēt viens otra numuru vienkārši ievietojot ap stūri. 429 00:15:55,970 --> 00:15:59,380 Iet uz priekšu un veikt dažas sekundes, un kārtot paši no mazākais 430 00:15:59,380 --> 00:16:01,240 pa kreisi, lai lielākā labajā pusē. 431 00:16:01,240 --> 00:16:02,490 Iet. 432 00:16:02,490 --> 00:16:07,010 433 00:16:07,010 --> 00:16:07,530 >> Labi. 434 00:16:07,530 --> 00:16:08,030 Labs. 435 00:16:08,030 --> 00:16:09,370 Tas bija tiešām darn ātri. 436 00:16:09,370 --> 00:16:14,040 Tagad kāds šeit, kas bija algoritms ka šie puiši piemērots? 437 00:16:14,040 --> 00:16:14,900 >> SPEAKER 1: vismaz uz lielāko. 438 00:16:14,900 --> 00:16:15,000 >> DAVID J. Malan: OK. 439 00:16:15,000 --> 00:16:18,070 Vismaz uz lielāko tiešām ir sava veida mērķis, bet es neesmu pārliecināts, ka ir 440 00:16:18,070 --> 00:16:18,890 tiešām algoritms. 441 00:16:18,890 --> 00:16:21,810 Vismaz uz lielāko nestāsta man soli pa solim, ko darīt. 442 00:16:21,810 --> 00:16:22,833 Yeah? 443 00:16:22,833 --> 00:16:24,083 >> SPEAKER 1: [dzirdams] 444 00:16:24,083 --> 00:16:26,010 445 00:16:26,010 --> 00:16:26,280 >> DAVID J. Malan: OK. 446 00:16:26,280 --> 00:16:28,920 Tātad, ja jūs redzat persona mazāks nekā jūsu numurs, tad pāriet uz 447 00:16:28,920 --> 00:16:29,680 tiesības uz tiem. 448 00:16:29,680 --> 00:16:32,800 Tātad, kas ir tagad kļūst daudz izteiksmīgāku, vairāk kā algoritms, jo jūs 449 00:16:32,800 --> 00:16:35,410 var teikt, ja tā, tad tā. 450 00:16:35,410 --> 00:16:37,050 Tāpēc mums ir sava veida nosacīta konstrukcija. 451 00:16:37,050 --> 00:16:39,700 Un šie puiši, šķiet, darīt, ka daži reizes, jo daži no jums pārcēlās mazliet 452 00:16:39,700 --> 00:16:40,420 no attāluma. 453 00:16:40,420 --> 00:16:43,410 Tātad bija iespējams, sava veida looping notiek viņu prātos. 454 00:16:43,410 --> 00:16:44,610 >> Bet pieņemsim mēģināt formalizēt to. 455 00:16:44,610 --> 00:16:47,540 Ja jūs puiši varētu nomainīt atpakaļ ar šo vienošanos. 456 00:16:47,540 --> 00:16:50,650 Redzēsim, vai mēs nevaram noformēt šo bit, un pēc tam uzdot jautājumu, vienkārši 457 00:16:50,650 --> 00:16:51,580 cik efektīvi tas ir? 458 00:16:51,580 --> 00:16:54,220 Protams, tad, kad mēs to darām lēnāk, tas notiek, lai justos tik laba 459 00:16:54,220 --> 00:16:57,210 algoritms, bet pieņemsim redzēt, ja mēs varam nodot mūsu pirkstiem uz konkrētiem soļiem. 460 00:16:57,210 --> 00:16:58,670 >> Tātad jūs abi puiši ir četri un divi. 461 00:16:58,670 --> 00:17:01,020 Vai jūs pareizi vai nepareizi pasūtīt? 462 00:17:01,020 --> 00:17:01,900 Acīmredzami nepareizs. 463 00:17:01,900 --> 00:17:02,710 Tāpēc mēs nomainīju. 464 00:17:02,710 --> 00:17:05,170 Tagad es esmu gatavojas pārcelties malā šeit un teikt, 05:56. 465 00:17:05,170 --> 00:17:06,240 Vai jūs pareizi vai nepareizi? 466 00:17:06,240 --> 00:17:06,599 >> Gabe: Pareizi. 467 00:17:06,599 --> 00:17:07,180 >> DAVID J. Malan: Pareizi. 468 00:17:07,180 --> 00:17:08,300 Seši un viens? 469 00:17:08,300 --> 00:17:08,609 Nē. 470 00:17:08,609 --> 00:17:09,630 Swap. 471 00:17:09,630 --> 00:17:10,490 Tātad tas ir divas mijmaiņas. 472 00:17:10,490 --> 00:17:11,710 Seši un trīs? 473 00:17:11,710 --> 00:17:11,980 Nē. 474 00:17:11,980 --> 00:17:13,000 Swap. 475 00:17:13,000 --> 00:17:13,930 Seši un septiņi? 476 00:17:13,930 --> 00:17:14,630 Izskatās labi. 477 00:17:14,630 --> 00:17:15,396 Septiņi un pieci? 478 00:17:15,396 --> 00:17:16,150 >> JESS: [dzirdams] 479 00:17:16,150 --> 00:17:17,089 >> DAVID J. Malan: Labi, swap. 480 00:17:17,089 --> 00:17:19,770 Un sakārtoti. 481 00:17:19,770 --> 00:17:19,980 Labi. 482 00:17:19,980 --> 00:17:21,440 Tātad acīmredzot ne, labi? 483 00:17:21,440 --> 00:17:22,470 Tātad, tur bija vairāk notiek. 484 00:17:22,470 --> 00:17:24,920 Bet, protams, šie puiši, pat vienkārši instinktīvi. 485 00:17:24,920 --> 00:17:25,450 tur pārvietojas. 486 00:17:25,450 --> 00:17:27,710 Tās nav tikai pārtraukt, kad viņi labota viena problēma. 487 00:17:27,710 --> 00:17:27,839 Tātad. 488 00:17:27,839 --> 00:17:29,390 Patiešām, es esmu nāksies darīt to pašu. 489 00:17:29,390 --> 00:17:32,720 Es esmu nāksies kārtot no attīt atpakaļ līdz sākumā šīs problēmas, 490 00:17:32,720 --> 00:17:35,630 vai sākumā šī masīva cilvēki, sāksim aicinot viņus. 491 00:17:35,630 --> 00:17:38,366 >> Un tagad kāds būtu mans algoritms uz otro pass būt? 492 00:17:38,366 --> 00:17:39,220 >> SPEAKER 1: Same lieta. 493 00:17:39,220 --> 00:17:39,940 >> DAVID J. Malan: Same lieta. 494 00:17:39,940 --> 00:17:41,460 Un tas, es esmu sāk patīk, vai ne? 495 00:17:41,460 --> 00:17:44,720 Tiklīdz jūs varat atrast sev dara pats atkal un atkal, tas ir 496 00:17:44,720 --> 00:17:47,890 kļūst vairāk, piemēram, algoritmu, un mazāk cilvēka instinkts. 497 00:17:47,890 --> 00:17:48,680 >> Tāpēc tagad, šeit mēs aiziet vēlreiz. 498 00:17:48,680 --> 00:17:49,870 Divi un četri? 499 00:17:49,870 --> 00:17:50,220 Nē. 500 00:17:50,220 --> 00:17:51,050 Četri un viens? 501 00:17:51,050 --> 00:17:53,380 Ah, tur tiešām bija daži darba vēl jāpaveic. 502 00:17:53,380 --> 00:17:53,620 Par un trīs? 503 00:17:53,620 --> 00:17:54,572 Labs. 504 00:17:54,572 --> 00:17:56,000 Četras līdz sešas? 505 00:17:56,000 --> 00:17:58,380 Seši un pieci? 506 00:17:58,380 --> 00:17:59,470 Seši un septiņi? 507 00:17:59,470 --> 00:18:00,970 Labi, tagad, darīts. 508 00:18:00,970 --> 00:18:01,550 Labi, nē. 509 00:18:01,550 --> 00:18:02,710 Man ir jāiet atpakaļ. 510 00:18:02,710 --> 00:18:05,130 >> Tāpēc tagad, atkal, mēs darām to nedaudz vairāk apzināti. 511 00:18:05,130 --> 00:18:08,700 Un tagad, tur ir tikai viena smadzeņu izpildot šo algoritmu. 512 00:18:08,700 --> 00:18:10,290 Viens CPU, ja Jums gribas. 513 00:18:10,290 --> 00:18:13,090 Un, atklāti sakot, tas ir vienīgais resurss mēs ejam, lai būtu pieejami. 514 00:18:13,090 --> 00:18:16,280 Un, kad mēs iet atpakaļ uz klaviatūras un ir kaut kas līdzīgs C pie mūsu 515 00:18:16,280 --> 00:18:19,600 iznīcināšana, mēs esam tikai rakstot programmu ka var darīt viena lieta laikā. 516 00:18:19,600 --> 00:18:22,900 Tā kā šie puiši pirms brīža, mēs parādi to kolektīvās intelektuālo potenciālu 517 00:18:22,900 --> 00:18:24,180 kā jūs puiši darīja nedēļu nulles. 518 00:18:24,180 --> 00:18:24,980 Tā ļauj saglabāt to izdarīt. 519 00:18:24,980 --> 00:18:26,260 >> Divi un viens. 520 00:18:26,260 --> 00:18:26,945 Divi un trīs. 521 00:18:26,945 --> 00:18:27,460 Trīs un četras. 522 00:18:27,460 --> 00:18:28,310 Četri un pieci. 523 00:18:28,310 --> 00:18:28,620 Piecus un sešus. 524 00:18:28,620 --> 00:18:30,510 Seši un septiņi. 525 00:18:30,510 --> 00:18:31,880 Gatavs? 526 00:18:31,880 --> 00:18:34,560 Tāpēc es esmu, bet ļaujiet man spēlēt Velna advokāts. 527 00:18:34,560 --> 00:18:37,950 Vai man, veida datora, kurš tikko sniedza piespēli šo masīvu 528 00:18:37,950 --> 00:18:40,225 cilvēki, zina, ka es esmu darīts? 529 00:18:40,225 --> 00:18:40,670 >> SPEAKER 1: Nē. 530 00:18:40,670 --> 00:18:41,050 >> DAVID J. Malan: Tad kāpēc? 531 00:18:41,050 --> 00:18:46,900 Kas man jādara, lai secināt, izlēmīgi, ka es esmu darīts? 532 00:18:46,900 --> 00:18:48,230 Iespējams, vēl viens pass. 533 00:18:48,230 --> 00:18:48,430 Labi? 534 00:18:48,430 --> 00:18:51,760 Jo viss, ko es zinu no ka iepriekšējais caurlaide ir, ka man jālabo kļūda. 535 00:18:51,760 --> 00:18:53,920 Un tas nozīmē, varbūt tur ir vēl viena kļūda 536 00:18:53,920 --> 00:18:54,840 ka man ir nepieciešams labot. 537 00:18:54,840 --> 00:18:58,680 Tāpēc es varu tikai būt pārliecināts, ka līdz pārtīšana, un pēc tam pārbaudot, 1-2, divi un 538 00:18:58,680 --> 00:19:00,940 trīs, trīs un četri, četri un pieci, pieci un seši, seši un septiņi. 539 00:19:00,940 --> 00:19:02,510 Labi, tagad man nebija nekādu darbu. 540 00:19:02,510 --> 00:19:05,990 >> Es, protams, atceros, ka man nebija neviena strādāt ar kaut ko, piemēram, mainīgo, 541 00:19:05,990 --> 00:19:06,975 piemēram, int. 542 00:19:06,975 --> 00:19:12,490 Call to mijmaiņas līgumus, un, ja mijmaiņas ir 0, kad I iegūt šeit, un tas sākās ar 0, tad 543 00:19:12,490 --> 00:19:15,520 Es būtu vienkārši muļķīgi, lai saglabātu turpinās uz priekšu un atpakaļ, pārbaudot atkal, un 544 00:19:15,520 --> 00:19:16,450 atkal, un atkal, vai ne? 545 00:19:16,450 --> 00:19:18,450 Tāpēc, ka jums iestrēdzis dažos veida bezgalīga cilpa. 546 00:19:18,450 --> 00:19:21,250 Tātad, tiklīdz tur ir 0 mijmaiņas darījumi, mēs varam apgalvot, ka šis 547 00:19:21,250 --> 00:19:23,810 algoritms ir patiešām pilnīgs. 548 00:19:23,810 --> 00:19:25,400 >> Tagad, pieņemsim likt vārdu par to. 549 00:19:25,400 --> 00:19:28,930 Algoritms, ka es ierosinu mēs tikko īstenota, ir kaut kas ko sauc burbulis 550 00:19:28,930 --> 00:19:32,800 kārtot, kas pazīstams kā tāds nozīmē, ka skaitļi, kas ir lielāki veida 551 00:19:32,800 --> 00:19:37,990 burbulis savu ceļu uz augšu uz augšu, vai uz augšu līdz beigām masīva numuriem. 552 00:19:37,990 --> 00:19:40,270 Bet cik efektīva bija šis algoritms? 553 00:19:40,270 --> 00:19:44,600 Cik soļus gan es fiziski ir veikt, piemēram, lai sakārtotu šos 554 00:19:44,600 --> 00:19:45,850 septiņi cilvēki? 555 00:19:45,850 --> 00:19:48,560 556 00:19:48,560 --> 00:19:49,550 >> Četriem līdz pieciem? 557 00:19:49,550 --> 00:19:51,420 Labi, pārāk daudz galu galā būs atbilde. 558 00:19:51,420 --> 00:19:54,960 Bet pat tad, konkrētu skaitu nav tik interesanti. 559 00:19:54,960 --> 00:19:56,670 Pieņemsim vispārināt to kā n. 560 00:19:56,670 --> 00:20:00,520 Tātad, ja man bija n cilvēkus šeit, un viņi bija sava veida, nejaušā secībā pēc 561 00:20:00,520 --> 00:20:02,180 sākumā, jo šajā sākotnējā secībā. 562 00:20:02,180 --> 00:20:04,910 Nu, cik soļus bija man uzņemties pirmā loka? 563 00:20:04,910 --> 00:20:09,810 Tas bija viens, divi, trīs, četru, piecu, seši, un viņi ir septiņi cilvēki, tāpēc 564 00:20:09,810 --> 00:20:13,670 kas ir septiņi, seši -, tā ka ir n mīnus viens soļi pirmo reizi. 565 00:20:13,670 --> 00:20:16,280 >> Tagad, cik soļus bija man lai tad, kad es jāpārtin? 566 00:20:16,280 --> 00:20:19,310 Nu, mēs patiešām varētu dubultot, ka, ja mēs patiešām vēlējāmies, bet tagad, es esmu 567 00:20:19,310 --> 00:20:22,300 tikai gatavojas teikt, labi, vēl viens n mīnus 1. 568 00:20:22,300 --> 00:20:25,240 Tātad n mīnus 1 ir gatavojas iegūt kaitinošas, lai sekotu, tāpēc pieņemsim 569 00:20:25,240 --> 00:20:26,400 tikai noapaļot uz augšu mazliet. 570 00:20:26,400 --> 00:20:27,770 Tātad 2n soļi. 571 00:20:27,770 --> 00:20:29,310 Tātad 14 soļi, sniegt vai pieņemt. 572 00:20:29,310 --> 00:20:31,930 >> Cik reizes es solis nākamreiz? 573 00:20:31,930 --> 00:20:33,740 Nu, tas ir 3n. 574 00:20:33,740 --> 00:20:34,510 tiešām. 575 00:20:34,510 --> 00:20:37,920 Un tagad, sliktākajā gadījumā, attiecībā Piemēram, cik reizes man ir 576 00:20:37,920 --> 00:20:41,730 gājusi uz priekšu un atpakaļ, uz priekšu un atpakaļ, izpildot šo algoritmu, pārnešana 577 00:20:41,730 --> 00:20:44,620 cilvēki uz katra brauciena, aptuveni? 578 00:20:44,620 --> 00:20:47,720 579 00:20:47,720 --> 00:20:50,010 Tas ir patiešām n rūtiņām, vai ne? 580 00:20:50,010 --> 00:20:53,000 >> Jo sliktākajā gadījumā, jūs varat veida gada domā par to intuitīvi, 581 00:20:53,000 --> 00:20:54,800 kaut gan tas var aizņemt nedaudz mazliet laika, lai izlietne collas 582 00:20:54,800 --> 00:20:57,590 Sliktākajā gadījumā, kādi būtu šie septiņi cilvēki izskatījās, it 583 00:20:57,590 --> 00:21:00,230 vienošanās noteikumi par to skaitu? 584 00:21:00,230 --> 00:21:01,460 Pilnīgi atpakaļ, labi? 585 00:21:01,460 --> 00:21:02,815 Un tikai, lai modelētu, ka, kāda bija jūsu vārds atkal? 586 00:21:02,815 --> 00:21:03,360 >> MIKE: Mike. 587 00:21:03,360 --> 00:21:03,640 >> DAVID J. Malan: Mike? 588 00:21:03,640 --> 00:21:08,100 Labi, Mike, jūs varat vienkārši pievienoties man vairāk šeit tikai par vienu sekundi? 589 00:21:08,100 --> 00:21:08,880 Patiesībā, nē. 590 00:21:08,880 --> 00:21:10,150 Atvainojiet Mike, pieņemsim atpakaļ. 591 00:21:10,150 --> 00:21:10,910 Kāds ir Jūsu vārds atkal? 592 00:21:10,910 --> 00:21:11,180 >> Neil: Neil. 593 00:21:11,180 --> 00:21:11,640 >> DAVID J. Malan: Neil. 594 00:21:11,640 --> 00:21:13,750 Labi, Neil, jūs nākt ar man, ja jums nav prātā. 595 00:21:13,750 --> 00:21:17,150 Tāpēc es esmu gatavojas ierosināt, tikai vienkāršība, ka Neil tagad viņa 596 00:21:17,150 --> 00:21:18,510 vissliktākais iespējamais gadījums. 597 00:21:18,510 --> 00:21:20,720 Bet atceros, kā es īstenoti mans algoritms. 598 00:21:20,720 --> 00:21:24,530 Es esmu salīdzinot, salīdzinot, salīdzinot, Salīdzinot, salīdzinot, oh. 599 00:21:24,530 --> 00:21:26,640 Tagad šie puiši ir out kārtības, tāpēc es noteikt. 600 00:21:26,640 --> 00:21:27,980 Tātad jūs guys swap. 601 00:21:27,980 --> 00:21:31,630 Bet uzskatu, tagad, cik daudz tālāk nav Neil jāiet? 602 00:21:31,630 --> 00:21:32,690 Tas ir aptuveni n. 603 00:21:32,690 --> 00:21:33,570 Jūs zināt, tas nav reāli n. 604 00:21:33,570 --> 00:21:36,040 Tas ir tāpat, n mīnus 1, bet es saņemu kaitina sekotu maz 605 00:21:36,040 --> 00:21:37,550 numuru, tāpēc pieņemsim tikai sauc to n. 606 00:21:37,550 --> 00:21:42,860 >> Tātad, ja Neil kustas viens solis maksimāli katras laiku, un, lai pārvietotu Neil vienu soli, 607 00:21:42,860 --> 00:21:46,580 Man ir, lai padarītu šo patiesi nogurdinošs caurlaide uz priekšu un atpakaļ, tas ir aptuveni 608 00:21:46,580 --> 00:21:52,080 darot, n posmi, no n reizes kopā, tāpēc, ka tas notiek, lai mani 609 00:21:52,080 --> 00:21:55,820 ka daudzi soļi, lai saņemtu Neil visiem veids, kur viņš pieder. 610 00:21:55,820 --> 00:21:58,620 Nemaz nerunājot visi pārējie, ja jūs guys visi bija nepareizi lika, kā arī. 611 00:21:58,620 --> 00:22:01,100 >> Tāpēc sauksim burbulis veida n brusas. 612 00:22:01,100 --> 00:22:04,860 Darbības laiks šo algoritmu, izpilde šī algoritma, 613 00:22:04,860 --> 00:22:07,120 efektivitāte šo algoritmu, mēs vienkārši aprakstīt vairāk 614 00:22:07,120 --> 00:22:08,800 , kā parasti n rūtiņām. 615 00:22:08,800 --> 00:22:11,650 Kas ir jauki, jo es varētu darīt pats piemērs ar astoņiem cilvēkiem, deviņas 616 00:22:11,650 --> 00:22:15,450 cilvēki, miljons cilvēku, un ka Atbilde nav gatavojas mainīt. 617 00:22:15,450 --> 00:22:18,870 >> Tātad, ja jūs guys nebūtu prātā, pieņemsim reset jums, kur jums sākusies. 618 00:22:18,870 --> 00:22:22,510 Un pamēģināsim divas citas pieejas un redzēt, ja mēs nevaram darīt fundamentāli 619 00:22:22,510 --> 00:22:23,820 labāk nekā šis. 620 00:22:23,820 --> 00:22:27,130 Tātad šajā laikā, es esmu gatavojas ierosināt veida dažādu algoritmu. 621 00:22:27,130 --> 00:22:29,950 Tas bija ļoti gudrs no mums pēdējo reizi, un jūs puiši bija tiesības uz 622 00:22:29,950 --> 00:22:32,470 tiesības instinkti tikko veida pārnešana pāru. 623 00:22:32,470 --> 00:22:36,500 Bet, ja es tiešām gribēju, lai pieeja šo vienkārši, un mans mērķis ir, lai pārvietotos 624 00:22:36,500 --> 00:22:39,800 visas maz numuriem šādā veidā, un push visi lielie numuriem, 625 00:22:39,800 --> 00:22:43,030 veidā, kāpēc ne es tikai darīt, ka visvairāk naivs veidā iespējams, un redzēt, ja es 626 00:22:43,030 --> 00:22:45,730 var darīt labāk, nekā to, kas bija diezgan sarežģītu algoritmu? 627 00:22:45,730 --> 00:22:46,620 >> Tātad, pieņemsim redzēt. 628 00:22:46,620 --> 00:22:48,940 Četri ir diezgan maz, tāpēc es esmu gatavojas atstāt jūs tur brīdi. 629 00:22:48,940 --> 00:22:50,610 Ooh, numur divi ir pat labāk. 630 00:22:50,610 --> 00:22:52,230 Tātad, jūs varat vienkārši soli uz priekšu uz brīdi? 631 00:22:52,230 --> 00:22:55,670 Tas pašlaik ir mans mazākais numurētas kandidāts, un es esmu gatavojas atcerēties 632 00:22:55,670 --> 00:22:57,000 ka ar, piemēram, mainīgo. 633 00:22:57,000 --> 00:22:57,930 Bet es esmu gatavojas, lai saglabātu pārbaudot. 634 00:22:57,930 --> 00:22:59,890 Vai ir kāds, kuru skaits ir mazāks? 635 00:22:59,890 --> 00:23:00,460 Seši, nē. 636 00:23:00,460 --> 00:23:01,390 Ak, tur ir Neil vēlreiz. 637 00:23:01,390 --> 00:23:04,050 >> Tāpēc es esmu gatavojas push jums atpakaļ veida konceptuāli. 638 00:23:04,050 --> 00:23:05,120 Neil nāks klajā. 639 00:23:05,120 --> 00:23:08,440 Un tagad, mainīgo, ka es esmu, izmantojot to sekot līdzi, kas ir mazākais 640 00:23:08,440 --> 00:23:11,390 numurs tiek atjaunināts, lai apturētu Neil atrašanās vietu. 641 00:23:11,390 --> 00:23:12,110 Nu, paskatīsimies. 642 00:23:12,110 --> 00:23:13,960 Trīs, septiņi, pieci. 643 00:23:13,960 --> 00:23:15,590 Labi, es zinu, Neil bija vismazākā. 644 00:23:15,590 --> 00:23:18,110 Kas ir vienkāršākais lieta man tagad darīt? 645 00:23:18,110 --> 00:23:21,410 Es netaisos tērēt savu laiku, tikai burbuļošana Neil vienas vietas pa kreisi. 646 00:23:21,410 --> 00:23:25,350 Kāpēc es tikai izvirzīti Neil kur viņš pieder, kas ir, protams, kur? 647 00:23:25,350 --> 00:23:26,160 >> Visu ceļu sākumā. 648 00:23:26,160 --> 00:23:27,720 Tātad Neil, nāc ar mani. 649 00:23:27,720 --> 00:23:28,910 Un kāda bija jūsu vārds atkal? 650 00:23:28,910 --> 00:23:29,310 >> GRACE: Grace. 651 00:23:29,310 --> 00:23:29,710 >> DAVID J. Malan: Grace. 652 00:23:29,710 --> 00:23:29,920 Labi. 653 00:23:29,920 --> 00:23:32,490 Tātad Grace, diemžēl, tu esi veida ceļā. 654 00:23:32,490 --> 00:23:34,290 Tātad, kā mēs atrisināt šo problēmu? 655 00:23:34,290 --> 00:23:34,490 Labi? 656 00:23:34,490 --> 00:23:37,500 Ja tas ir masīvs, tur ir tikai septiņas vietas. 657 00:23:37,500 --> 00:23:40,830 Atgādināt, ka, ar Rob, mēs runājām deklarē vecumu, un mums bija tikai 658 00:23:40,830 --> 00:23:41,740 ierobežots skaits vecumu? 659 00:23:41,740 --> 00:23:42,535 Pati ideja šeit. 660 00:23:42,535 --> 00:23:44,300 Mums ir tikai ierobežots skaits ints. 661 00:23:44,300 --> 00:23:47,590 Grace ir sava veida mūsu veidā, tad kā mēs varam noteikt? 662 00:23:47,590 --> 00:23:49,555 >> Vienkāršākais veids ir, piemēram, Žēlastība, sorry. 663 00:23:49,555 --> 00:23:51,870 Jūs esat nāksies iet pa tur, lai mēs varētu padarīt telpu. 664 00:23:51,870 --> 00:23:55,290 Tagad, ja jūs domājat par to, varbūt mēs tikko veikts problēma sliktāka. 665 00:23:55,290 --> 00:23:58,510 Un varbūt mēs darījām, jo ​​kas notiks, ja Grace bija īstajā vietā? 666 00:23:58,510 --> 00:24:01,730 Bet mēs zinām, viņa nav, jo citādi, viņai būtu bijis 667 00:24:01,730 --> 00:24:03,980 stāvot uz priekšu, nevis Neil šajā laikā, vai ne? 668 00:24:03,980 --> 00:24:05,550 Mēs jau paņemts viņas numuru out. 669 00:24:05,550 --> 00:24:05,770 >> Labi. 670 00:24:05,770 --> 00:24:09,110 Tāpēc tagad, Neil ir pareizajā vietā, un Es varu darīt nelielu optimizāciju. 671 00:24:09,110 --> 00:24:11,740 Attiecībā uz nākamo minūti, es esmu gatavojas ignorēt Neil visi kopā, tā, lai 672 00:24:11,740 --> 00:24:15,280 atkritumu savu laiku, vai nejauši swap viņu nepareizā vietā. 673 00:24:15,280 --> 00:24:17,805 Tāpēc tagad, kā es varu atrast nākamo elements, kas ir mazākais? 674 00:24:17,805 --> 00:24:18,480 Divi. 675 00:24:18,480 --> 00:24:20,225 Tas ir diezgan labs numurs, ja Jūs vēlaties, lai soli uz priekšu un 676 00:24:20,225 --> 00:24:21,100 Es atceros tevi. 677 00:24:21,100 --> 00:24:21,980 Seši, nav labi. 678 00:24:21,980 --> 00:24:24,820 Četri, trīs, septiņi, pieci, nav labi. 679 00:24:24,820 --> 00:24:26,800 Tātad, ļaujiet man pāriet jums Jūsu īstā vieta. 680 00:24:26,800 --> 00:24:28,470 Un mēs vienkārši palaimējies šoreiz. 681 00:24:28,470 --> 00:24:31,350 >> Tagad es esmu gatavojas ignorēt šos divi puiši, bet tagad vēl viena 682 00:24:31,350 --> 00:24:32,260 iet caur šo. 683 00:24:32,260 --> 00:24:33,490 Seši, ka diezgan neliels skaits. 684 00:24:33,490 --> 00:24:34,300 Nāc uz priekšu. 685 00:24:34,300 --> 00:24:35,220 Ak, piedodiet. 686 00:24:35,220 --> 00:24:37,640 Grace numurs ir labāk, tā solis uz priekšu. 687 00:24:37,640 --> 00:24:38,260 Četri. 688 00:24:38,260 --> 00:24:39,120 Atvainojiet, Grace. 689 00:24:39,120 --> 00:24:39,950 Iet atpakaļ. 690 00:24:39,950 --> 00:24:41,550 Numurs trīs ir labāk. 691 00:24:41,550 --> 00:24:42,290 Septiņi. 692 00:24:42,290 --> 00:24:42,720 Pieci. 693 00:24:42,720 --> 00:24:43,550 Un tagad kāds ir tavs vārds atkal? 694 00:24:43,550 --> 00:24:44,000 >> Jason: Jason. 695 00:24:44,000 --> 00:24:44,420 >> DAVID J. Malan: Jason. 696 00:24:44,420 --> 00:24:47,050 Tātad Jason tagad mazākais elements, es esmu izvēlēts. 697 00:24:47,050 --> 00:24:49,160 Gadījumos, kad viņš gatavojas doties? 698 00:24:49,160 --> 00:24:50,380 Tātad, kur seši ir. 699 00:24:50,380 --> 00:24:51,210 Un jūsu vārds atkal? 700 00:24:51,210 --> 00:24:51,710 >> Gabe: Gabe. 701 00:24:51,710 --> 00:24:52,340 >> DAVID J. Malan: Gabe. 702 00:24:52,340 --> 00:24:53,220 Gabe ir ceļā. 703 00:24:53,220 --> 00:24:54,640 Kas ir vieglākais lieta darīt? 704 00:24:54,640 --> 00:24:58,390 Swap šie divi puiši un turpināt. 705 00:24:58,390 --> 00:24:59,020 Tātad tagad pieņemsim redzēt. 706 00:24:59,020 --> 00:25:00,170 Kurš ir mazākais? 707 00:25:00,170 --> 00:25:01,030 Četri. 708 00:25:01,030 --> 00:25:01,990 Ļaujiet man tikai veida pievilt. 709 00:25:01,990 --> 00:25:03,090 Pieci būs vismazākā. 710 00:25:03,090 --> 00:25:05,220 Es atrast nākamo, ja jūs vēlaties, lai soli priekšu, kas man ir jādara ar 711 00:25:05,220 --> 00:25:06,820 šie puiši, ar Gabe? 712 00:25:06,820 --> 00:25:08,450 Swap vēlreiz. 713 00:25:08,450 --> 00:25:10,740 Tāpēc tagad, vēl nedaudz bojātas. 714 00:25:10,740 --> 00:25:14,140 Es konstatēts Gabe būt mazākais, tā Es pop viņu ārā, pārvietot jūs puiši vairāk. 715 00:25:14,140 --> 00:25:15,190 Un darīts. 716 00:25:15,190 --> 00:25:17,200 >> Tātad atbilde ir tas pats. 717 00:25:17,200 --> 00:25:18,600 Gala rezultāts ir tāds pats. 718 00:25:18,600 --> 00:25:22,730 Kurš no šiem diviem algoritmu ir labāks? 719 00:25:22,730 --> 00:25:23,500 Otrs, es dzirdēju. 720 00:25:23,500 --> 00:25:24,252 Kāpēc? 721 00:25:24,252 --> 00:25:25,900 >> SPEAKER 3: Tas ir n soļi [nedzirdama]. 722 00:25:25,900 --> 00:25:27,600 >> DAVID J. Malan: Tas ir n soļi pie visvairāk. 723 00:25:27,600 --> 00:25:28,490 Interesanti. 724 00:25:28,490 --> 00:25:30,610 Tātad, tas ir gan? 725 00:25:30,610 --> 00:25:33,630 Tātad, kā es varu atrast mazākais elements? 726 00:25:33,630 --> 00:25:37,060 Cik soļus did I ir jāņem atrast mazāko elementu? 727 00:25:37,060 --> 00:25:39,220 Man bija skatīties visu ceļu gada beigās, vai ne? 728 00:25:39,220 --> 00:25:41,530 Jo šajā sliktākajā gadījumā, kas ja Neil bija vairāk nekā šeit? 729 00:25:41,530 --> 00:25:45,700 Tik vienkārši atrast mazāko elementu ņem mani n soļi, vai n mīnus 1. 730 00:25:45,700 --> 00:25:46,100 Bet, OK. 731 00:25:46,100 --> 00:25:46,980 Tātad noteikt Neil. 732 00:25:46,980 --> 00:25:48,740 Atcerieties, ka, minūti, vai arī tā atpakaļ. 733 00:25:48,740 --> 00:25:51,680 >> Bet kā es varu atrast nākamo mazākais elements? 734 00:25:51,680 --> 00:25:54,830 Tas ir n mīnus 1, vai n mīnus 2 tiešām, no to darbību skaitu. 735 00:25:54,830 --> 00:25:55,440 Tātad OK. 736 00:25:55,440 --> 00:25:57,390 Tāpēc man nebija n mīnus 2. 737 00:25:57,390 --> 00:25:57,600 Labi. 738 00:25:57,600 --> 00:25:59,130 Tāpēc, ka jūtas mazliet labāk. 739 00:25:59,130 --> 00:25:59,730 Labi. 740 00:25:59,730 --> 00:26:03,270 Cik soļus nākamreiz lai atrastu numuru trīs? 741 00:26:03,270 --> 00:26:04,420 Tā n mīnus 4. 742 00:26:04,420 --> 00:26:07,670 Tātad tas samazinās, viens mazāk soli uz katra atkārtojuma. 743 00:26:07,670 --> 00:26:08,740 Tātad tas justies labāk, vai ne? 744 00:26:08,740 --> 00:26:13,450 Ja pēdējā laikā, tas ir aptuveni n reizes, n, šoreiz tas ir n mīnus 1, plus n mīnus 745 00:26:13,450 --> 00:26:16,500 2, plus n mīnus 3, plus n mīnus 4, dot, dot, dot. 746 00:26:16,500 --> 00:26:18,750 Bet, ja jūs atceraties no jūsu vidusskolā mācību grāmatas, maz apkrāptu 747 00:26:18,750 --> 00:26:24,380 loksnes pie muguras, kas ir formulas, ja Saskaitot šīs sērijas numuru, 748 00:26:24,380 --> 00:26:31,280 kāds ir kopējais skaits soļiem būs, ka es šeit? 749 00:26:31,280 --> 00:26:36,580 >> Šis ir viens no tiem, piemēram, n mīnus 1 reizes n, dalot ar 2. 750 00:26:36,580 --> 00:26:39,040 Tātad, ļaujiet man redzēt, ja es varētu pull šo up tikai brīdi. 751 00:26:39,040 --> 00:26:42,230 Un atkal, es esmu veida noapaļošanas dažu numurus tikai, lai saglabātu mūsu dzīvi vienkāršu, 752 00:26:42,230 --> 00:26:47,830 bet, cik es atceros, tas ir kaut kas līdzīgs, ja Man n mīnus 1 lietas, tad n mīnus 753 00:26:47,830 --> 00:26:53,570 2, tad n mīnus 3, tas ir aptuveni kaut kas līdzīgs šim vairāk nekā 2, un, ja es 754 00:26:53,570 --> 00:26:55,510 reizināt šo out, tas ir faktiski n kvadrātu. 755 00:26:55,510 --> 00:26:58,940 Tas nav slikta pārāk labi. n mīnus n vairāk nekā 2. 756 00:26:58,940 --> 00:27:00,350 >> Bet šeit ir lieta. 757 00:27:00,350 --> 00:27:03,720 Datorzinātnēs, kad problēmas sāk iegūt interesantu, ir tad, kad n 758 00:27:03,720 --> 00:27:04,700 izpaužas patiešām liels. 759 00:27:04,700 --> 00:27:08,110 Un, ja n kļūst patiešām liels, kas no šīs vērtības gatavojas dominēt visu 760 00:27:08,110 --> 00:27:09,750 par citiem? 761 00:27:09,750 --> 00:27:10,990 Tas ir sava veida n brusas, vai ne? 762 00:27:10,990 --> 00:27:13,340 Jā, dalot ar 2, ir diezgan laba. 763 00:27:13,340 --> 00:27:16,740 Bet, ja jūs runājat par miljardu gabalu datu vai triljoniem 764 00:27:16,740 --> 00:27:18,700 gabalu datiem, OK, tāpēc tu esi divreiz ātrāk. 765 00:27:18,700 --> 00:27:22,440 Bet kas tiešām rūpējas, ja šo lielo skaitu, ja šis faktors ir tas, kas izpaužas 766 00:27:22,440 --> 00:27:23,040 lielāka un lielāka. 767 00:27:23,040 --> 00:27:25,990 Un, protams, tas padara vairāk atšķirība par šo puisis. 768 00:27:25,990 --> 00:27:29,120 Tātad, pat ja jūs guys ir taisnība, otrkārt algoritms, mēs to saucam 769 00:27:29,120 --> 00:27:32,970 izvēle kārtot, ir reālajā pasaulē, mazliet ātrāk iespējams, jo es esmu 770 00:27:32,970 --> 00:27:35,360 ņemot mazāk un mazāk soļus katru reizi. 771 00:27:35,360 --> 00:27:37,340 >> Tas nav īsti būtiski ātrāk. 772 00:27:37,340 --> 00:27:41,430 Jo, ja mēs faktiski spēlēt šo out lielas vērtības no N, beigās 773 00:27:41,430 --> 00:27:44,750 diena, lieliem pietiekami n, tas joprojām ir gatavojas justies diezgan lēns. 774 00:27:44,750 --> 00:27:46,770 Nu, ļaujiet man izmantot vienu pēdējo reizi iet tajā. 775 00:27:46,770 --> 00:27:48,920 Tas ir tas, ko es sauktu atlase kārtošanas. 776 00:27:48,920 --> 00:27:51,040 Vai jūs guys reset sevi pēdējo reizi? 777 00:27:51,040 --> 00:27:53,550 Un šajā pēdējā gadījumā, es esmu gatavojas ierosināt kaut ko 778 00:27:53,550 --> 00:27:54,970 sauc ievietošanas veida. 779 00:27:54,970 --> 00:27:57,470 Ievietošanas šķirot ir konceptuāli nedaudz savādāka. 780 00:27:57,470 --> 00:28:00,980 >> Nevis iet uz priekšu un atpakaļ, un izvēloties mazāko elementu, es esmu 781 00:28:00,980 --> 00:28:05,030 tikai gatavojas, lai risinātu ar katru no šiem puiši kā es saskaras viņiem, un ievietojiet 782 00:28:05,030 --> 00:28:06,850 tos savā pareizajā vietā. 783 00:28:06,850 --> 00:28:10,160 Tāpēc es esmu tikai gatavojas sākt ar Grace, un es redzu, ka viņa ir numur četri. 784 00:28:10,160 --> 00:28:11,720 Kur numur četri pieder? 785 00:28:11,720 --> 00:28:14,940 Man nav sākusies šķirošana neko, tāpēc Grace izpaužas palikt turpat. 786 00:28:14,940 --> 00:28:18,355 Un tagad es esmu gatavojas pieprasīt, ja jūs varētu spert soli, lai jūsu tiesības, tas 787 00:28:18,355 --> 00:28:21,650 mans sakārtoti sarakstā, tas ir mans nešķiroti atlikušo sarakstu. 788 00:28:21,650 --> 00:28:23,260 Tāpēc tagad es esmu gatavojas sākt nākamo, un kāds ir tavs vārds atkal? 789 00:28:23,260 --> 00:28:23,700 >> BRANSON: Branson. 790 00:28:23,700 --> 00:28:24,150 >> DAVID J. Malan: Branson. 791 00:28:24,150 --> 00:28:25,375 Tātad Branson ir numur divi. 792 00:28:25,375 --> 00:28:27,490 Tāpēc es esmu gatavojas pieņemt jums kas uz brīdi. 793 00:28:27,490 --> 00:28:30,940 Un tagad, kad jūs piederat Šajā masīva? 794 00:28:30,940 --> 00:28:32,360 Tātad, pa labi no Grace. 795 00:28:32,360 --> 00:28:35,670 Tātad vēlreiz, mēs esam sava veida padarīt Grace darīt daudz darba šeit. 796 00:28:35,670 --> 00:28:37,290 Kur mēs nodot jums? 797 00:28:37,290 --> 00:28:40,120 Tātad, mēs ejam, lai slīdētu jums pa kreisi, un ievietojiet Branson tur. 798 00:28:40,120 --> 00:28:41,680 Bet tagad man apgalvot, ka jūs guys ir darīts. 799 00:28:41,680 --> 00:28:43,240 Bet paziņojums, es neesmu, izmantojot papildu telpas. 800 00:28:43,240 --> 00:28:45,130 Tas joprojām ir 2 elementi Šeit, 5 vairāk nekā šeit. 801 00:28:45,130 --> 00:28:47,910 Kopējais masīva izmērs ir 7, tāpēc es esmu nekrāpj, labi? 802 00:28:47,910 --> 00:28:51,950 >> Tāpēc tagad mums ir, ar Gabe šeit, numuru seši, ja jūs piederat? 803 00:28:51,950 --> 00:28:52,650 Tev laimīgs atkal. 804 00:28:52,650 --> 00:28:53,820 Tātad jums palikt turpat. 805 00:28:53,820 --> 00:28:57,210 Just veikt nelielu soli, lai labi tikai, lai būtu skaidrs, ka jūs esat sakārtoti. 806 00:28:57,210 --> 00:29:00,520 Un tagad mums ir Neil atkal, skaits viens, kur jūs iet? 807 00:29:00,520 --> 00:29:03,540 Un tagad ir, ja mēs sāksim redzēt, ka tas algoritms, lai gan par pirmo 808 00:29:03,540 --> 00:29:05,950 skatienu, jūtas diezgan gudri, skatīties kas ir aptuveni notikt. 809 00:29:05,950 --> 00:29:07,370 Ja jūs varētu soli uz priekšu. 810 00:29:07,370 --> 00:29:09,260 >> Kur mēs vēlamies, lai Neil? 811 00:29:09,260 --> 00:29:11,830 Tātad acīmredzot šeit, tad kā Vai mēs Neil tur? 812 00:29:11,830 --> 00:29:12,970 Darīsim to soli pa solim. 813 00:29:12,970 --> 00:29:15,620 Gabe, kur jums jāiet? 814 00:29:15,620 --> 00:29:19,590 Yep, tā veic vienu lielu soli, vai divu pusi-soļi, lai padarītu 815 00:29:19,590 --> 00:29:20,820 viens solis tur. 816 00:29:20,820 --> 00:29:21,750 Grace, kur jums iet? 817 00:29:21,750 --> 00:29:22,510 Labs. 818 00:29:22,510 --> 00:29:23,500 Tātad vēl viens solis. 819 00:29:23,500 --> 00:29:24,960 Un, visbeidzot, Branson? 820 00:29:24,960 --> 00:29:25,460 Vēl viens solis. 821 00:29:25,460 --> 00:29:27,190 Un tagad mēs varam nodot Neil vietā. 822 00:29:27,190 --> 00:29:28,440 >> Tāpēc tagad, turpināt šo loģiku. 823 00:29:28,440 --> 00:29:32,420 Pat ja mēs neesam novirzot Neil vairāk un vairāk, un vairāk, lai viņu 824 00:29:32,420 --> 00:29:36,420 kur viņš dodas, sliktākajā gadījumā, nākamais skaitlis mēs varētu saskarties varētu 825 00:29:36,420 --> 00:29:42,220 ir skaitlis, teiksim, tur bija vairāki nulle, tad mēs ejam, lai novirzīt visus 826 00:29:42,220 --> 00:29:42,730 šie puiši. 827 00:29:42,730 --> 00:29:44,950 Pieņemsim, ka tur ir vairāki, negatīvs viens, tad mums ir novirzīt 828 00:29:44,950 --> 00:29:46,080 visiem šiem puišiem. 829 00:29:46,080 --> 00:29:48,500 Tāpēc mēs esam tiešām tikai veida flipping problēma apkārt, piemēram, ka mēs esam 830 00:29:48,500 --> 00:29:52,620 pārceļot rēķina no atlases process tāpēc ievietošanas 831 00:29:52,620 --> 00:29:56,930 procesā, piemēram, ka jūs puiši tikko bija pārvietot aptuveni n mīnus kaut ko 832 00:29:56,930 --> 00:29:57,940 virkne pasākumu. 833 00:29:57,940 --> 00:30:01,200 Un, ka vairāki pasākumi ir tikai gatavojas palielināties, jo es izvēlētos citus numurus, 834 00:30:01,200 --> 00:30:04,730 ja man ir, lai saglabātu shoving jums guys atpakaļ, un atpakaļ, un atpakaļ. 835 00:30:04,730 --> 00:30:08,320 >> Tik skumji lieta tagad ir visi šie algoritmi ir n rūtiņām. 836 00:30:08,320 --> 00:30:10,570 Iesim uz priekšu, un, pateicoties šiem puiši, un vizualizēt šos mazliet 837 00:30:10,570 --> 00:30:11,090 savādāk. 838 00:30:11,090 --> 00:30:12,312 Ļoti labi darīts. 839 00:30:12,312 --> 00:30:14,120 >> [Aplausi] 840 00:30:14,120 --> 00:30:15,030 >> Labi. 841 00:30:15,030 --> 00:30:16,280 Tur jums iet. 842 00:30:16,280 --> 00:30:18,390 843 00:30:18,390 --> 00:30:18,470 Paldies par - 844 00:30:18,470 --> 00:30:19,190 >> BRANSON: [dzirdams] saglabāt numurus. 845 00:30:19,190 --> 00:30:21,990 >> DAVID J. Malan: Nē, jūs varat saglabāt numurus, kā arī. 846 00:30:21,990 --> 00:30:23,440 Labi. 847 00:30:23,440 --> 00:30:24,100 Labi darīts. 848 00:30:24,100 --> 00:30:25,300 Labi. 849 00:30:25,300 --> 00:30:30,510 Tātad, pieņemsim redzēt, ja mēs nevaram tagad apkopot ātrāk, un vairāk vizuāli, 850 00:30:30,510 --> 00:30:33,410 tieši to, kas tikko notika Šeit šādi. 851 00:30:33,410 --> 00:30:36,510 852 00:30:36,510 --> 00:30:38,770 Es iešu uz priekšu un uzvilkt Firefox. 853 00:30:38,770 --> 00:30:41,310 Mēs saistīt šo demonstrāciju par kursu tīmekļa vietnē. 854 00:30:41,310 --> 00:30:43,870 Java ir mazliet kaitinošas, lai saņemtu darbu dažās pārlūkprogrammās šajās dienās. 855 00:30:43,870 --> 00:30:46,760 Tātad, ja jūs spēlēt ar šo mājās, saproti, jums var būt nepieciešams izmantot Firefox 856 00:30:46,760 --> 00:30:47,990 lai saņemtu to strādāt. 857 00:30:47,990 --> 00:30:50,440 Un ko es esmu gatavojas darīt ar to demonstrācija ir šādi. 858 00:30:50,440 --> 00:30:54,875 >> Apakšā, man ir visai ķekars izvēlnes iespējas, tostarp sākuma un 859 00:30:54,875 --> 00:30:55,840 stop pogu. 860 00:30:55,840 --> 00:30:59,450 Tāpat kā malā, šķiet, bug šajās programmās, kuru jūs 861 00:30:59,450 --> 00:31:03,720 nevarat patiešām redzēt sākuma vai beigu pogu, ja jūs turiet Command vai Alt 862 00:31:03,720 --> 00:31:06,560 plus un zoom in, kas savādi rāda vairāk pogu. 863 00:31:06,560 --> 00:31:09,090 Tik vienkārši FYI, ja jūs spēlēt ar šo mājās. 864 00:31:09,090 --> 00:31:12,870 Tagad es esmu gatavojas noklikšķiniet uz Sākt, kas tikko Mirklī, kad norādot kavēšanās, 865 00:31:12,870 --> 00:31:16,810 piemēram, 200 milisekundes šeit, vienkārši lai mēs varētu redzēt, kas notiek. 866 00:31:16,810 --> 00:31:20,180 >> Tāpēc es apgalvo, ka tas ir vizualizācija Pirmā algoritma 867 00:31:20,180 --> 00:31:23,730 šie puiši darīja, burbulis kārtot, kuru mēs nomainīju cilvēkus pa pāriem. 868 00:31:23,730 --> 00:31:27,490 Galvenais ieskatu šajā vizualizācijas ir tas, ka augstums stieņiem 869 00:31:27,490 --> 00:31:30,510 apzīmē lielumu skaitu. 870 00:31:30,510 --> 00:31:32,210 Tātad garāki josla, lielāks skaits. 871 00:31:32,210 --> 00:31:33,680 Īsāks bārs, mazāku skaitu. 872 00:31:33,680 --> 00:31:38,630 Un, ja pamanāt, mēs ejam cauri Pirmo atkārtojumu šo algoritmu, 873 00:31:38,630 --> 00:31:42,620 pārnešana lielos un mazos numurus, lai neliels skaits ir pirmajā vietā, un 874 00:31:42,620 --> 00:31:44,280 liels skaitlis iet uz labo pusi. 875 00:31:44,280 --> 00:31:48,770 >> Un, tiklīdz mēs saņemam beigām masīva Daudzu vairāk skaits nekā septiņiem, mēs esam 876 00:31:48,770 --> 00:31:49,900 gatavojas doties atpakaļ uz sākumu. 877 00:31:49,900 --> 00:31:51,140 Un paredzēt šo. 878 00:31:51,140 --> 00:31:54,860 Par tālu pa kreisi, ka maz puisis notiek apmainīt uz pusi, un šis 879 00:31:54,860 --> 00:31:56,010 process atkārtojas. 880 00:31:56,010 --> 00:31:59,450 Tagad šis vizualizācija ātri kļūst garlaicīgi, tāpēc ļaujiet man iet uz priekšu un apstāties 881 00:31:59,450 --> 00:32:04,170 tas, izmainīt aiztures kaut kas daudz ātrāk, tikai, lai iegūtu tagad justies par 882 00:32:04,170 --> 00:32:05,060 tas algoritms. 883 00:32:05,060 --> 00:32:07,840 >> Tātad, pat ja es esmu jāpaātrina to uz augšu, tas ir kā uzlabot manu procesoru, pērkot 884 00:32:07,840 --> 00:32:08,580 jaunu datoru. 885 00:32:08,580 --> 00:32:12,980 Man nav būtiski mainīja manu algoritms, bet jūs tiešām var redzēt vairāk 886 00:32:12,980 --> 00:32:16,800 skaidrāk nekā ar cilvēkiem, ka liela skaits ir burbuļo uz augšu, 887 00:32:16,800 --> 00:32:20,900 un mazie skaitļi ir burbuļošana uz leju, lai apakšā. 888 00:32:20,900 --> 00:32:22,390 Un tagad šī lieta šeit sakārtoti. 889 00:32:22,390 --> 00:32:25,260 Un kā malā, ar kvadrātu, tur ir tikai daži grāmatvedības tur 890 00:32:25,260 --> 00:32:28,010 palīdzēs jums saskaitīt, cik daudz salīdzinājumus, vai cik atvasinātie 891 00:32:28,010 --> 00:32:28,950 faktiski veikts. 892 00:32:28,950 --> 00:32:30,750 >> Nu, pieņemsim, mēģiniet vienu no citi mēs redzējām. 893 00:32:30,750 --> 00:32:37,116 Ļaujiet man noklikšķiniet uz burbulis kārtot šeit, un ļaujiet man izvēlēties, un visa šī mājas lapa 894 00:32:37,116 --> 00:32:38,936 ir nedaudz buggy. 895 00:32:38,936 --> 00:32:41,155 Let 's pieņemt risku un palaist to no jauna. 896 00:32:41,155 --> 00:32:44,560 897 00:32:44,560 --> 00:32:45,030 Tur mēs ejam. 898 00:32:45,030 --> 00:32:47,180 Tātad, pieņemsim do atlases veida. 899 00:32:47,180 --> 00:32:49,140 Es nezinu, kāpēc izvēlne Šķiet tur. 900 00:32:49,140 --> 00:32:54,070 Let 's tālummaiņu, lai noteiktu, ka bug, mainīt līdz 50. 901 00:32:54,070 --> 00:32:56,020 Ah, pieņemsim faktiski darīt ka daudz ātrāk. 902 00:32:56,020 --> 00:32:59,160 Piecas milisekundes, vai arī tā, un sākt. 903 00:32:59,160 --> 00:33:00,470 >> Tātad šī ir izvēle veida. 904 00:33:00,470 --> 00:33:03,070 Tātad vēlreiz, domāju par to, ko mēs darīja ar cilvēkiem šeit. 905 00:33:03,070 --> 00:33:08,490 Mēs gājām cauri masīva un izvēlēto mazākais elements atkal, 906 00:33:08,490 --> 00:33:09,250 un atkal, un atkal. 907 00:33:09,250 --> 00:33:11,110 Tagad es apgalvo, ka vēl bija diezgan slikti. 908 00:33:11,110 --> 00:33:15,010 Tas vēl bija n rūtiņām, sniegt vai pieņemt, bet tas bija, reālajā pasaulē, nedaudz 909 00:33:15,010 --> 00:33:18,280 ātrāk, jo man tiešām bija, ņemot Nedaudz mazāk soļus katru reizi. 910 00:33:18,280 --> 00:33:19,800 Bet mēs esam tikai runājam, ko? 911 00:33:19,800 --> 00:33:21,830 Varbūt 40 vai tik bāri šeit? 912 00:33:21,830 --> 00:33:23,200 Mēs nerunājam 40 miljonus. 913 00:33:23,200 --> 00:33:27,430 Tātad, tas nav pilnīgi skaidrs, man, ka tiešām bija nozīmīgs ieguvums. 914 00:33:27,430 --> 00:33:32,530 >> Ļaujiet man tagad iet atpakaļ un mainīt, lai mūsu trešais algoritmu, kas tika atlasīt 915 00:33:32,530 --> 00:33:33,180 ievietošanas kārtošanas. 916 00:33:33,180 --> 00:33:36,380 Un tagad tas ir patiešām buggy, jo izvēlne tiešām nevajadzētu būt tur lejā. 917 00:33:36,380 --> 00:33:40,840 Tāpēc tagad mēs ritināt atpakaļ uz augšu šeit un sākt šo algoritmu. 918 00:33:40,840 --> 00:33:43,270 Bļāviens, sākt un pārtraukt. 919 00:33:43,270 --> 00:33:47,160 Tātad šī viena veida ir diezgan modelis uz to, kur mēs esam atkal 920 00:33:47,160 --> 00:33:50,240 Ievietojot cilvēkus, vai arī Šajā gadījumā, bāri vērā 921 00:33:50,240 --> 00:33:52,620 to piemērotu vietu. 922 00:33:52,620 --> 00:33:55,430 Un tas jau ir izdarīts pirms Es pagriezos. 923 00:33:55,430 --> 00:33:58,940 Bet tas viens, arī teorētiski, ir vēl n rūtiņām. 924 00:33:58,940 --> 00:34:01,430 >> Tātad, pieņemsim redzēt, ja mēs nevaram apkopot tie ir šādi. 925 00:34:01,430 --> 00:34:04,750 Es iešu uz priekšu un tikai, lai dotu mums sava veida kopīgu ceļu, kā runāt 926 00:34:04,750 --> 00:34:08,489 par šīm lietām, ļaujiet man iepazīstināt tikai mazliet notācijas šeit. 927 00:34:08,489 --> 00:34:12,480 Jūs gatavojaties, lai redzētu kaut ko sauc liels O, jo tas ir burtiski liels 928 00:34:12,480 --> 00:34:16,320 O. Un tas ir tā, ka dators zinātnieks vai matemātiķis pat izmanto 929 00:34:16,320 --> 00:34:19,230 lai aprakstītu darbības laiku par kādu algoritmu. 930 00:34:19,230 --> 00:34:21,400 Cik soļus tas tiešām nepieciešams? 931 00:34:21,400 --> 00:34:25,080 >> Tagad es esmu gatavojas apgrūtināt sevi ar mans rokraksts šeit tikai brīdi. 932 00:34:25,080 --> 00:34:29,020 Bet ļaujiet man iet uz priekšu un teikt, ka tas būs liels O nekā šeit. 933 00:34:29,020 --> 00:34:33,610 Un ļaujiet man iepazīstināt vienam otru simbols, kapitāla omega. 934 00:34:33,610 --> 00:34:37,080 Omega būs pretējs, būtībā, lielo O. tā lielā O 935 00:34:37,080 --> 00:34:40,790 nozīmē, sliktākajā gadījumā, cik daudz laika varētu kādu algoritms veikt, 936 00:34:40,790 --> 00:34:43,480 noteikumi n, omega gatavojas ir, cik daudz laika tas varētu 937 00:34:43,480 --> 00:34:45,409 veikt labākajā gadījumā. 938 00:34:45,409 --> 00:34:48,090 Un mēs redzēsim, ko mēs saprotam ar labākajā gadījumā tikai brīdi. 939 00:34:48,090 --> 00:34:49,940 >> Tāpēc sāksim kaut ko vienkāršu. 940 00:34:49,940 --> 00:34:54,719 Ļaujiet man sākt ar lineāru meklēšanu. 941 00:34:54,719 --> 00:34:55,679 Tāpēc ne šķirošana. 942 00:34:55,679 --> 00:34:58,000 Mēs to saucam par lineāru meklēšanu. 943 00:34:58,000 --> 00:35:01,140 Un tagad, padara nedaudz tabulu no šīs. 944 00:35:01,140 --> 00:35:06,600 Un tagad, ja lineāro meklēšanu, sliktākajā gadījumā, cik soļus ir 945 00:35:06,600 --> 00:35:11,770 tas notiek, lai mani atrast skaits patvaļīgas izvēles? 946 00:35:11,770 --> 00:35:14,540 Un tur ir n kopējais durvis vai n kopējais skaits. 947 00:35:14,540 --> 00:35:15,940 Sliktākajā gadījumā. 948 00:35:15,940 --> 00:35:18,800 Cik soļus man nāksies veikt, lai atrastu skaitli 50 masīvā 949 00:35:18,800 --> 00:35:20,830 no n durvīm? 950 00:35:20,830 --> 00:35:21,410 Un kāpēc? 951 00:35:21,410 --> 00:35:23,680 Tāpēc, ka tas varētu būt visu kā vairāk uz beigām. 952 00:35:23,680 --> 00:35:27,120 Tik daudz, piemēram, Jennifer radušās, numuru 50 bija visu ceļu pāri, tāpēc 953 00:35:27,120 --> 00:35:30,760 sliktākajā gadījumā lineāra meklēšana ir liels O n, mēs teikt. 954 00:35:30,760 --> 00:35:33,430 >> Kas par labākajā gadījumā, ja jums patiesi laimīgs? 955 00:35:33,430 --> 00:35:36,200 Tas ir tikai gatavojas veikt vienu soli, vai konstante skaits no soļiem. 956 00:35:36,200 --> 00:35:37,830 Tāpēc mēs aprakstīt, ka 1. 957 00:35:37,830 --> 00:35:39,010 Tātad tas ir diezgan laba. 958 00:35:39,010 --> 00:35:41,210 Tagad, kas notiks, ja mēs kaut ko patīk bināro meklēšanu? 959 00:35:41,210 --> 00:35:43,860 960 00:35:43,860 --> 00:35:47,846 Tātad bināro meklēšanu, jo sliktākajā gadījumu, ņēma cik daudz laika? 961 00:35:47,846 --> 00:35:49,250 >> [Interposing Voices] 962 00:35:49,250 --> 00:35:51,310 >> DAVID J. Malan: Tik tiešām, es dzirdēja to pāris vietās. 963 00:35:51,310 --> 00:35:56,390 Tātad, tas ir faktiski log n, sniegt vai pieņemt, jo, kā mēs sadalīt sarakstu pusi 964 00:35:56,390 --> 00:36:00,730 atkal, un atkal, un atkal, mēs esam spējīgi atrast, galu galā, vērtību, 965 00:36:00,730 --> 00:36:04,750 ja tas ir tur, bet tur ir nozvejas. 966 00:36:04,750 --> 00:36:08,590 Kas ir pieņēmums, ka mums ir par pašsaprotamu bināro meklēšanu? 967 00:36:08,590 --> 00:36:09,700 Tā ir jābūt sakārtoti. 968 00:36:09,700 --> 00:36:12,770 Tas nav sakārtots, jūs varat sadalīt lieta uz pusi atkal un atkal, un jūs 969 00:36:12,770 --> 00:36:15,490 var iet pa kreisi, un jūs varat iet labi, un jūs varat iet pa kreisi un pa labi, bet jūs esat 970 00:36:15,490 --> 00:36:18,070 nav dodas, lai atrastu elementu, ja saraksts nav sakārtots, jo 971 00:36:18,070 --> 00:36:18,790 jūs varat palaist garām to. 972 00:36:18,790 --> 00:36:22,120 Tāpēc, ka jūsu heiristisko, lai dotos pa kreisi vai pa labi, būs kļūdaina, ja tas ir 973 00:36:22,120 --> 00:36:23,420 tiešām nav sakārtoti. 974 00:36:23,420 --> 00:36:26,110 Tātad tur ir sava veida slēptās izmaksas lai, izmantojot kaut kas līdzīgs šim. 975 00:36:26,110 --> 00:36:29,250 >> Tagad, iesim uz mūsu šķirošanu algoritmi nav meklē - 976 00:36:29,250 --> 00:36:31,140 ak, tiešām iesim šajā tukšu. 977 00:36:31,140 --> 00:36:33,190 Bināro meklēšanu labākajā gadījumā? 978 00:36:33,190 --> 00:36:36,290 Tas ir arī 1, ja tas vienkārši notiek, ir in pašā vidū masīva, vai 979 00:36:36,290 --> 00:36:37,810 vidū tālruņu grāmatu. 980 00:36:37,810 --> 00:36:39,710 Tagad pieņemsim do burbulis veida. 981 00:36:39,710 --> 00:36:42,570 Tātad vēlreiz, tagad mēs esam ienāk sakārto, nevis meklē. 982 00:36:42,570 --> 00:36:47,220 >> Sliktākajā gadījumā, cik soļus vai mēs prasība burbulis kārtot gatavojas veikt? 983 00:36:47,220 --> 00:36:48,410 n rūtiņām. 984 00:36:48,410 --> 00:36:49,200 Tāpēc es esmu gatavojas izdarīt to. 985 00:36:49,200 --> 00:36:51,710 Ooh, mans rokraksts izskatās vēl sliktāk kad tas ir prognozēts, ka liels. 986 00:36:51,710 --> 00:36:52,510 Labi. 987 00:36:52,510 --> 00:36:53,570 Tātad, kas ir n rūtiņām. 988 00:36:53,570 --> 00:36:59,460 Un labākajā gadījumā uz burbuļa veida, cik soļus tā gatavojas veikt? 989 00:36:59,460 --> 00:37:00,980 1, es dzirdēju. 990 00:37:00,980 --> 00:37:01,760 >> SPEAKER 1: n. 991 00:37:01,760 --> 00:37:03,286 >> DAVID J. Malan: n, es dzirdēju. 992 00:37:03,286 --> 00:37:04,200 >> SPEAKER 1: 2. 993 00:37:04,200 --> 00:37:05,010 >> DAVID J. Malan: 2, es dzirdēju. 994 00:37:05,010 --> 00:37:06,670 Vai es dzirdu 3? 995 00:37:06,670 --> 00:37:07,080 Labi. 996 00:37:07,080 --> 00:37:11,390 Tāpēc es esmu dzirdējis 1, n, 2, bet pieņemsim izvēlēties Apart vismaz pirmais no tiem 997 00:37:11,390 --> 00:37:12,330 ieteikumi, 1. 998 00:37:12,330 --> 00:37:15,370 Tas nav slikti instinkts, jo tas veida seko rakstu šeit. 999 00:37:15,370 --> 00:37:19,670 Bet, ja tas aizņem tikai 1 solis, kā in pasaule es varētu apgalvot, ka saraksts 1000 00:37:19,670 --> 00:37:22,900 ir sakārtots, jo, ja es esmu tikai atļauts veikt 1 soli, cik elementi 1001 00:37:22,900 --> 00:37:25,230 es varētu faktiski pārbaudīt, lai pārliecinātos? 1002 00:37:25,230 --> 00:37:28,270 Nu, tikai 1, kas nozīmē, ka ir n mīnus 1 elementi, kas varētu būt no 1003 00:37:28,270 --> 00:37:31,310 kārtība, un es esmu tikai gatavojas uz ticību pēc Aplūkojot 1 elements, kas 1004 00:37:31,310 --> 00:37:31,850 lieta ir sakārtots. 1005 00:37:31,850 --> 00:37:33,930 Līdz 1 Tas nav pareizi šeit. 1006 00:37:33,930 --> 00:37:35,710 Tātad minimāli, cik man apskatīt? 1007 00:37:35,710 --> 00:37:36,680 >> [Interposing Voices] 1008 00:37:36,680 --> 00:37:40,160 >> DAVID J. Malan: n mīnus 1, vai tiešām, n, jo man ir nepieciešams, lai apskatīt katru 1009 00:37:40,160 --> 00:37:42,190 elements, lai pārliecinātos, ka tas nav bojātas. 1010 00:37:42,190 --> 00:37:44,750 Bet atkal, mēs sava veida vilnis mūsu rokas pie mazākā skaitā un 1011 00:37:44,750 --> 00:37:47,100 pieņemu, ka n kļūst liels, viņi neinteresanti anyway. 1012 00:37:47,100 --> 00:37:48,380 Tātad, tas ir burbulis šķirot. 1013 00:37:48,380 --> 00:37:49,830 Un tagad, pieņemsim do pēdējiem diviem. 1014 00:37:49,830 --> 00:37:53,520 Atlase kārtot, un tad mēs do ievietošanas veida. 1015 00:37:53,520 --> 00:37:57,160 Un tad mums būs trieciens jūsu prāts ar kaut ko daudz 1016 00:37:57,160 --> 00:37:58,926 labāk nekā visi no tiem. 1017 00:37:58,926 --> 00:38:00,410 Labi. 1018 00:38:00,410 --> 00:38:04,700 >> Kas ir sliktākajā gadījumā darbojas laiks atlases veida? 1019 00:38:04,700 --> 00:38:05,680 >> SPEAKER 4: n rūtiņām. 1020 00:38:05,680 --> 00:38:06,710 >> DAVID J. Malan: n kvadrātveida, es esmu dzirde. 1021 00:38:06,710 --> 00:38:09,790 Bet kāpēc n rūtiņām, intuitīvi? 1022 00:38:09,790 --> 00:38:11,170 >> SPEAKER 4: Jo mēs vienkārši to darīja. 1023 00:38:11,170 --> 00:38:12,260 >> DAVID J. Malan: Tāpēc, ka mēs vienkārši to darīja. 1024 00:38:12,260 --> 00:38:12,550 Labi. 1025 00:38:12,550 --> 00:38:13,380 Laba atbilde. 1026 00:38:13,380 --> 00:38:16,660 Bet intuitīvi, kāpēc ir izvēle kārtot n kvadrātā? 1027 00:38:16,660 --> 00:38:18,980 Ko mums jādara atkal un atkal? 1028 00:38:18,980 --> 00:38:22,570 Mums bija, lai saglabātu skenēšana, izmantojot, ir Jūs mazākais, jūs 1029 00:38:22,570 --> 00:38:24,020 mazākais, jūs mazākais. 1030 00:38:24,020 --> 00:38:27,480 Un piešķirts, mēs varējām veikt n soļi, tad n mīnus 1, tad n mīnus 2. 1031 00:38:27,480 --> 00:38:30,700 Bet, ja jūs veida pievienot tos visus uz augšu, vai ņemt to uz ticību, ka es esmu pievienojusi 1032 00:38:30,700 --> 00:38:34,810 viņiem jau iepriekš, mēs iegūstam aptuveni n kvadrātā mīnus dažiem mazākiem skaitļiem. 1033 00:38:34,810 --> 00:38:36,730 Tāpēc es esmu gatavojas nosaukt šo n rūtiņām. 1034 00:38:36,730 --> 00:38:39,530 Bet ar atlases veida, kas vislabāk gadījumā, cik soļus ir tas, 1035 00:38:39,530 --> 00:38:40,632 gatavojas pieņemt mani? 1036 00:38:40,632 --> 00:38:41,840 >> SPEAKER 5: [dzirdams] 1037 00:38:41,840 --> 00:38:44,350 >> DAVID J. Malan: Tas diemžēl vēl n kvadrātā, vai ne? 1038 00:38:44,350 --> 00:38:49,590 Jo, ja es esmu izvēloties mazāko elements, un mums bija septiņi cilvēki šeit, 1039 00:38:49,590 --> 00:38:53,280 Es tikai zinu, kad es nokļūt ļoti end, ka es esmu atradis mazākais 1040 00:38:53,280 --> 00:38:55,670 numuru, kur viņš vai viņa var būt. 1041 00:38:55,670 --> 00:38:58,820 Bet kā es varu atrast nākamo Vismazāk? 1042 00:38:58,820 --> 00:39:00,160 Man ir jādara citas caurlaide. 1043 00:39:00,160 --> 00:39:04,810 Tātad labākajā gadījumā, kāds ir ieguldījums atlases veida? 1044 00:39:04,810 --> 00:39:07,830 Tas ir jau sava saraksta, numur viens, numurs divi, trīs numurs, numurs četri. 1045 00:39:07,830 --> 00:39:08,600 Bet es esmu datoru. 1046 00:39:08,600 --> 00:39:10,190 Es varu tikai apskatīt vienu lieta laikā. 1047 00:39:10,190 --> 00:39:12,465 Es nevaru sava veida spert soli atpakaļ, piemēram, cilvēku un saka: 1048 00:39:12,465 --> 00:39:14,030 ooh, tas izskatās pareizi. 1049 00:39:14,030 --> 00:39:17,580 >> Es varu tikai spriest pareizību, kas atlase kārtot, izvēloties 1050 00:39:17,580 --> 00:39:18,370 Vismazāk. 1051 00:39:18,370 --> 00:39:21,390 Bet, pat ja es uzskatu, numur viens, pirmkārt, ja es nezinu neko citu par 1052 00:39:21,390 --> 00:39:24,460 pārējie skaitļi, kas man nav, viss, ko es zina, ka es esmu bijis nodots masīvs 1053 00:39:24,460 --> 00:39:27,930 vai kopums, durvis, aiz kuriem ir numurus, vienīgais veids, kā es zinu, ka viens 1054 00:39:27,930 --> 00:39:28,680 bija mazākais? 1055 00:39:28,680 --> 00:39:32,440 Ja man visu ceļu šeit un saprast, damn, viens bija patiešām mazākais. 1056 00:39:32,440 --> 00:39:34,870 >> Bet kā es varu, tad nosaka, ka divi ir nākamais mazākais? 1057 00:39:34,870 --> 00:39:38,350 Darot to pašu neefektivitāti atkal un atkal. 1058 00:39:38,350 --> 00:39:42,210 Tātad beidzot, ar ievietošanas veida, kā, sliktākajā gadījumā, 1059 00:39:42,210 --> 00:39:44,990 tomēr mēs sakām tā veic? 1060 00:39:44,990 --> 00:39:49,100 Tas arī ir n rūtiņām. 1061 00:39:49,100 --> 00:39:53,020 Un kā ar to labākajā gadījumā? 1062 00:39:53,020 --> 00:39:56,282 Mēs ņemšu atvaļinājumu, ka cliffhanger. 1063 00:39:56,282 --> 00:40:00,090 Mēs aizpildīt šo tukšo nākamreiz, bet vispirms ļaujiet man ieteikt, ka mēs 1064 00:40:00,090 --> 00:40:02,620 būtiski darīt labāk nekā visi šie, labi? 1065 00:40:02,620 --> 00:40:05,220 >> Tāpēc domāju, ka sev ko ievietošanas kārtot būs. 1066 00:40:05,220 --> 00:40:06,910 Labi, ka nebija ļoti dramatiska, tāpēc, ka es esmu tikai viens 1067 00:40:06,910 --> 00:40:08,970 kas redzēja izmaiņas. 1068 00:40:08,970 --> 00:40:09,620 Wow. 1069 00:40:09,620 --> 00:40:10,420 Labi. 1070 00:40:10,420 --> 00:40:12,615 Tātad, šeit mums ir nedaudz atšķirīgs demonstrācija. 1071 00:40:12,615 --> 00:40:16,580 Ja es tuvinātu šeit, jūs redzēsiet, ka kreisi mums ir burbulis veida, kas 1072 00:40:16,580 --> 00:40:20,740 vidū mums ir atlases veida, un cik labi, mums ir kaut kas, mēs 1073 00:40:20,740 --> 00:40:23,380 nav paskatījās vēl aicināja apvienot kārtot. 1074 00:40:23,380 --> 00:40:26,080 Bet uzskatu, ko mēs esam bijuši te dari līdz šim šodien. 1075 00:40:26,080 --> 00:40:29,200 Kad Jennifer pirmo reizi nāca uz skatuves, mēs gājām cauri masīva numuru 1076 00:40:29,200 --> 00:40:33,750 atkal, un atkal, ar lineāro meklēšanu, un mēs saņēmām lineāru darba laiku, big O 1077 00:40:33,750 --> 00:40:35,100 no n, tā sakot. 1078 00:40:35,100 --> 00:40:41,000 >> Kad mēs tagad uzskata, ka pirmajā nedēļā klasē, kad mums bija skaldi un valdi, 1079 00:40:41,000 --> 00:40:43,740 un mums bija telefona grāmatu plīsumi, un Jennifer, un mēs kopīgi 1080 00:40:43,740 --> 00:40:47,500 parādi, ka atslēgu ieskatu, kas bija atkārtot sevi atkal un atkal 1081 00:40:47,500 --> 00:40:50,930 kaut kā throwing prom, throwing prom, throwing prom, no problēmas puse, vai 1082 00:40:50,930 --> 00:40:55,320 parasti, dalot problēma pusi, un pēc tam apstrādājot mazāku gabalu 1083 00:40:55,320 --> 00:40:59,630 problēma, jo konceptuāli ekvivalents uz otru, mēs kaut kā bija 1084 00:40:59,630 --> 00:41:00,910 fundamentāli labāk. 1085 00:41:00,910 --> 00:41:04,720 Bet ar burbuļu veida, ar atlases kārtot, ar ievietošanas veida, mēs esam var 1086 00:41:04,720 --> 00:41:06,560 nav tādas atziņas, ka Dženifera darīja. 1087 00:41:06,560 --> 00:41:10,220 Mēs diezgan daudz tikai gāja atpakaļ un tālāk viss ķekars reizes, un mēs 1088 00:41:10,220 --> 00:41:12,650 tweaked lietas mazliet, pārnešana šādā secībā, varbūt 1089 00:41:12,650 --> 00:41:13,730 Ievietojot vai izvēloties. 1090 00:41:13,730 --> 00:41:16,950 Bet beigās, dienā, es did daudz no neērtā kājām un atpakaļ. 1091 00:41:16,950 --> 00:41:21,160 Mums nav īsti sviras kaut ko smart piemēram, Jennifer darīja, piemēram, dalot 1092 00:41:21,160 --> 00:41:22,040 un iekarošana. 1093 00:41:22,040 --> 00:41:25,620 >> Tātad apvienot kārtot, gluži pretēji, kuru mēs nebūs redzēt tikai nākamajā nedēļā, tas notiek 1094 00:41:25,620 --> 00:41:29,540 lai piesaistītu ka galvenais ideja dalot ievadi, un pēc tam uz pusi, un pēc tam 1095 00:41:29,540 --> 00:41:30,580 pusi, un pēc tam pusi. 1096 00:41:30,580 --> 00:41:34,590 Un uz katra atkārtojuma šīs cilpas, šķirošana kreiso pusi, un labais 1097 00:41:34,590 --> 00:41:38,200 puse, tad kreiso pusi no kreisās puses, un labajā pusē no kreisās puses, tad 1098 00:41:38,200 --> 00:41:40,990 kreiso pusi no labās puses, un tiesības puse no labajā pusē. 1099 00:41:40,990 --> 00:41:42,840 Un atkārtojot atkal un atkal. 1100 00:41:42,840 --> 00:41:46,170 >> Tātad, jūs redzēsiet to vizuāli, bet tas ir tas, kas mūs sagaida nākamajā nedēļā. 1101 00:41:46,170 --> 00:41:49,760 Un vispār, kad mēs domājam, nedaudz mazliet grūtāk par šādu problēmu. 1102 00:41:49,760 --> 00:41:52,435 1103 00:41:52,435 --> 00:41:57,970 Mums ir n rūtiņām pa kreisi, n kvadrātā vidū, un n 1104 00:41:57,970 --> 00:41:59,400 log n labajā pusē. 1105 00:41:59,400 --> 00:42:00,590 Tātad tur ir jūsu reālā cliffhanger. 1106 00:42:00,590 --> 00:42:02,040 Mēs tiksimies pirmdien. 1107 00:42:02,040 --> 00:42:05,163 >> [Aplausi]