1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> SPEAKER: Nu labi, tas ir CS50. 3 00:00:14,910 --> 00:00:19,020 Tas ir beigu trīs nedēļas, un, ja jums nav izmantojuši jau, 4 00:00:19,020 --> 00:00:21,790 zinu, ka būs pusdienas šo piektdien, kā ierasts, kur 5 00:00:21,790 --> 00:00:25,430 Jūs varat baudīt laba saruna un ēdiens Uguns un ledus 6 00:00:25,430 --> 00:00:27,980 ar dažiem no CS50 s personāls un klasesbiedru. 7 00:00:27,980 --> 00:00:30,170 Dodies uz šo URL šeit. 8 00:00:30,170 --> 00:00:33,420 >> Tagad jūs varat atgādināt, vai arī jūs drīz var iepazīties ar, 9 00:00:33,420 --> 00:00:35,970 šīs lietas šeit, kas tiek dots beigās 10 00:00:35,970 --> 00:00:37,850 semestra daudziem klasēm. 11 00:00:37,850 --> 00:00:40,870 Tā sauktais eksāmenu zilas grāmatas, kurās jums rakstīt jūsu atbildes uz eksāmeniem. 12 00:00:40,870 --> 00:00:44,240 Tagad man ir šeit 26 tādas zilā grāmatas, par katru no tām 13 00:00:44,240 --> 00:00:47,580 ir rakstīts nosaukumu, A caur Z. Un patiesi vārdi ir tik vienkārši, 14 00:00:47,580 --> 00:00:50,490 līdz Z. Un viens no mērķi pie rokas šodien 15 00:00:50,490 --> 00:00:53,910 būs arī turpmāk, ko mēs sākām pirmdien, kas nav 16 00:00:53,910 --> 00:00:57,830 tik daudz meklē kodu, bet tiešām meklē idejas un problēmu risināšanu. 17 00:00:57,830 --> 00:01:00,170 Viens no mērķiem, un solījumi šajā kursā 18 00:01:00,170 --> 00:01:02,985 ir mācīt jūs domāt vairāk uzmanīgi, vairāk metodiski, 19 00:01:02,985 --> 00:01:05,400 un risināt problēmas efektīvāk. 20 00:01:05,400 --> 00:01:09,526 Un tiešām, mēs varam darīt, ka patiešām , pat nepieskaroties līnijas kodu. 21 00:01:09,526 --> 00:01:12,150 Tāpēc man ir pāris ziloņi šeit šodien, oranžā un zilā krāsā, 22 00:01:12,150 --> 00:01:15,780 ja mēs varētu saņemt viens brīvprātīgais, varbūt no tālāk atpakaļ nekā parasti. 23 00:01:15,780 --> 00:01:18,070 Kā par turpat, nāk uz leju. 24 00:01:18,070 --> 00:01:24,180 Kura mērķis būs līdz palīdzēt plus administrēt šo eksāmenu šeit. 25 00:01:24,180 --> 00:01:24,935 Kāds ir tavs vārds? 26 00:01:24,935 --> 00:01:25,768 >> AUDITORIJA: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 SPEAKER: Mary Beth, nākt uz augšu. 28 00:01:27,560 --> 00:01:29,560 Ļaujiet man iegūt mikrofonu šeit jums. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Prieks iepazīties. 31 00:01:32,880 --> 00:01:34,005 >> AUDITORIJA: Prieks iepazīties. 32 00:01:34,005 --> 00:01:36,790 SPEAKER: Nu labi, tāpēc man ir Šeit zila grāmatas līdz Z, 33 00:01:36,790 --> 00:01:41,680 un es esmu gatavojas izlikties, ka Man ir viens no skolēniem, 34 00:01:41,680 --> 00:01:45,770 un viņi nāk nedaudz nejauši beigās trīs stundu Exam bloku, 35 00:01:45,770 --> 00:01:49,400 lai viņi beidzot dažās daļēji izlases kārtība, kā šis. 36 00:01:49,400 --> 00:01:54,510 Tagad jūsu uzdevums tikai brīdi notiek to be-- tas ir faktiski, kā viņi saņem 37 00:01:54,510 --> 00:01:56,820 griezt beigās klasē, visticamāk. 38 00:01:56,820 --> 00:02:01,120 Jūsu darbs tagad būs diezgan vienkārši, lai kārtotu šos zilos grāmatas mums 39 00:02:01,120 --> 00:02:05,220 no A līdz Z. 40 00:02:05,220 --> 00:02:08,400 >> AUDITORIJA: Ak, tas ir gatavojas veikt uz visiem laikiem. 41 00:02:08,400 --> 00:02:13,747 >> SPEAKER: Un mēs skatīties kā jūs to izdarītu, nav spiediena. 42 00:02:13,747 --> 00:02:15,330 AUDITORIJA: Nē, nav spiediena vai neko. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> SPEAKER: Un jautri, pieņemsim safasēti taimeri. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> AUDITORIJA: Tik daudz jautrības, tik jautri. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> SPEAKER: Es varu turēt mic jums. 49 00:02:38,574 --> 00:02:40,240 Labi, mēs esam tikai dubultojies mūsu ātrumu. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Tātad to laiku, ļaujiet man uzdot to, kas ir būs jautājums Mary Beth 52 00:02:49,060 --> 00:02:51,540 ir to, kas ir viņa dara, cik ir viņa iet par risināšanas šo? 53 00:02:51,540 --> 00:02:54,040 Un patiesībā, iespējams, jums nav kādreiz domājuši par kaut ko 54 00:02:54,040 --> 00:02:57,440 tik vienkārši, kā tad, kad jūs izvēlaties līdz 26 grāmatas, piemēram, tas, 55 00:02:57,440 --> 00:02:59,350 kam ir dabisks pasūtot uz tiem. 56 00:02:59,350 --> 00:03:01,335 Kas ir process ka jūs faktiski izmantot? 57 00:03:01,335 --> 00:03:03,770 Vai tas ir diezgan nejauši tikko picking pirmo redzat 58 00:03:03,770 --> 00:03:05,250 un ievietojot to savā vietā? 59 00:03:05,250 --> 00:03:09,680 Vai jums vispirms pārvietoties rokas apkārt meklē, tad meklē B? 60 00:03:09,680 --> 00:03:11,722 Vai jūs to apskatīt No tiem blakus pāris 61 00:03:11,722 --> 00:03:14,680 un tikai teikt, pagaidiet minūti, šis nav pareizi, un tad ielieciet pasūtījumu? 62 00:03:14,680 --> 00:03:16,960 Mēs jau redzējām pirmdien ka tur ir vairāki veidi 63 00:03:16,960 --> 00:03:22,140 kurā mēs varam izdarīt, un tiešām, kā mēs pie beigām šeit 64 00:03:22,140 --> 00:03:26,360 Es varētu ņemt vērā varbūt par ko Mary Beth dara. 65 00:03:26,360 --> 00:03:30,040 Mums ir daži pāļi šķiet, lielāks par vienu, trīs mazākie. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> AUDITORIJA: Es esmu pasūtot tos kad es atrast divus burtus 68 00:03:36,415 --> 00:03:39,540 , ka es zinu, ir kopā secībā, Es viņus kopā tā, ka man nav 69 00:03:39,540 --> 00:03:42,915 jāuztraucas par saglabājot līdzi veselu rindu grāmatas. 70 00:03:42,915 --> 00:03:45,706 Tas ir tikai, ak, ir pirmais, Man šī kaudze šeit. 71 00:03:45,706 --> 00:03:47,580 SPEAKER: Tātad, gandrīz kā puzzle gabalus, ka 72 00:03:47,580 --> 00:03:49,860 ir pareizo formu sakrīt ar otru. 73 00:03:49,860 --> 00:03:51,026 AUDITORIJA: Diezgan daudz, jā. 74 00:03:51,026 --> 00:03:55,320 SPEAKER: OK, lielisks. 75 00:03:55,320 --> 00:03:59,850 Un tagad katru no šiem pāļi, ir iespējams, sakārtoti? 76 00:03:59,850 --> 00:04:00,990 >> AUDITORIJA: Jā. 77 00:04:00,990 --> 00:04:09,900 >> SPEAKER: Labi, izmantojot Z. All labi, apsveicu, jūs to darīja. 78 00:04:09,900 --> 00:04:11,461 Jums ir jūsu izvēle. 79 00:04:11,461 --> 00:04:11,960 Blue? 80 00:04:11,960 --> 00:04:13,530 Nu labi, paldies par to. 81 00:04:13,530 --> 00:04:16,679 Tātad Mary Beth nebija ierosināt ko viņas pieeja bija, 82 00:04:16,679 --> 00:04:19,720 bet to, kas ir cita pieeja, kā jums varētu iet par šķirošanas šīs lietas? 83 00:04:19,720 --> 00:04:21,130 Ko jūs esat darījuši? 84 00:04:21,130 --> 00:04:24,060 Ieraksts pārspēt būtu bijis vienu minūti un 50 vai tik sekundes, 85 00:04:24,060 --> 00:04:26,039 plus tie, es aizmirsu skaitīt. 86 00:04:26,039 --> 00:04:27,080 Ko jūs esat darījuši? 87 00:04:27,080 --> 00:04:27,579 Yeah? 88 00:04:27,579 --> 00:04:28,735 AUDITORIJA: Veikt kaudze. 89 00:04:28,735 --> 00:04:29,776 Sākt no sākuma. 90 00:04:29,776 --> 00:04:32,284 Pārbaudiet savus dokumentus. 91 00:04:32,284 --> 00:04:36,586 Un, ja top viens ir augstāks nekā, varbūt, tie ir, 92 00:04:36,586 --> 00:04:38,980 apakšā viens ir augstāka, tad pāriet tos. 93 00:04:38,980 --> 00:04:41,300 >> SPEAKER: Labi, tāpēc sākot augšā un apakšā, 94 00:04:41,300 --> 00:04:43,716 un tad strādā savu ceļu ievešana, piemēram, ka, pārnešana viņiem? 95 00:04:43,716 --> 00:04:46,580 Labi, tāpēc mazliet līdzīgs garā uz burbulis kārtot, 96 00:04:46,580 --> 00:04:49,160 bet izvēloties galējībām nav blakus pāri. 97 00:04:49,160 --> 00:04:52,080 Bet īss ir tas, ka tur ir protams ķekars dažādos veidos 98 00:04:52,080 --> 00:04:54,210 mēs varētu darīt, un godīgi sakot, es domāju, ka jūs veida 99 00:04:54,210 --> 00:04:55,700 pieņēma pāris pieejas, labi? 100 00:04:55,700 --> 00:05:00,567 Jūs, kas veida četri Šķirotu pāļi, un Tad faktiski apvienojās kopā. 101 00:05:00,567 --> 00:05:02,650 Un tas ir, daresay, cits tehniku ​​vispār. 102 00:05:02,650 --> 00:05:06,950 Jums nav pret to, kā vienu lielu kaudzi, Jums sadalīja problēmu četrās kvadrociklu, 103 00:05:06,950 --> 00:05:09,820 ja jūs, un tad kaut apvienoti tos beigās. 104 00:05:09,820 --> 00:05:13,410 >> Tātad, pieņemsim apsvērt, galu galā, kā gan citādi mēs varētu darīt. 105 00:05:13,410 --> 00:05:15,860 Mēs oficiāli jēdzienu burbuļiem kārtošanas pēdējo reizi, 106 00:05:15,860 --> 00:05:18,780 un burbulis kārtot atsaukšana bija algoritms, kas mēs vizualizēta 107 00:05:18,780 --> 00:05:22,640 ar astoņiem jūsu klasesbiedriem up šeit, šķietami nejauši sakārtoti sākumā. 108 00:05:22,640 --> 00:05:26,110 Un mēs pēc tam nolēma pairwise, ja divi elementi ir no rīkojuma, 109 00:05:26,110 --> 00:05:26,950 vienkārši mijmaiņas tiem. 110 00:05:26,950 --> 00:05:28,930 Tātad četri un divi acīmredzot nedarbojas, 111 00:05:28,930 --> 00:05:31,080 tāpēc šie divi klasesbiedru pārgāja pozīcijas. 112 00:05:31,080 --> 00:05:35,390 Un tad mēs atkārto ar četriem un sešiem, Pēc tam sešas un astoņas, par katru atkārtojuma, 113 00:05:35,390 --> 00:05:36,980 pārvietojas pa labi. 114 00:05:36,980 --> 00:05:42,590 >> Tāpēc, astoņi cilvēki, cik pairwise salīdzinājumi man darīt ejot no 115 00:05:42,590 --> 00:05:45,220 kreisās uz labo vienu šādu atkārtojuma? 116 00:05:45,220 --> 00:05:48,410 Cik salīdzinājumi? 117 00:05:48,410 --> 00:05:49,197 Septiņi, labi? 118 00:05:49,197 --> 00:05:51,405 Jo, ja tur ir astoņi cilvēki, bet jums ir pāri 119 00:05:51,405 --> 00:05:53,880 viņiem un jūs pastāvīgi pārvietojas viens hop pa labi, 120 00:05:53,880 --> 00:05:56,060 jūs neesat nāksies astoņi salīdzinājumus, jo jūs nevarat salīdzināt 121 00:05:56,060 --> 00:05:59,226 elements pret sevi, vai tas būtu vienkārši bezjēdzīgi, tāpēc jums ir septiņi. 122 00:05:59,226 --> 00:06:01,290 Vai biežāk, ja mums ir n cilvēki, mēs 123 00:06:01,290 --> 00:06:04,300 do n mīnus 1 salīdzinājumus ar burbulis veida. 124 00:06:04,300 --> 00:06:08,150 >> Tātad, pieņemsim apsvērt, tagad, cik labi vai slikts burbulis kārtot patiesībā bija, un mēģiniet 125 00:06:08,150 --> 00:06:13,570 dot sev vārdu krājumu ar kuras kritikas algoritmus, piemēram, tas, 126 00:06:13,570 --> 00:06:14,430 un drīz mūsu pašu. 127 00:06:14,430 --> 00:06:16,970 Tātad pirmā loka caur burbulis kārtot, pirmo reizi 128 00:06:16,970 --> 00:06:20,909 Es aizgāju no kreisās uz labo pusi pāri posms, paņēma mani n mīnus 1 salīdzinājumus. 129 00:06:20,909 --> 00:06:22,950 Un kas notiek, lai būtu mans mērvienība, labi? 130 00:06:22,950 --> 00:06:26,170 Es biju veida runā un pastaigām, nedaudz ātrs, nedaudz lēns, 131 00:06:26,170 --> 00:06:29,300 tāpēc skaitot manu numuru sekundes nav īpaši spēcīgi, 132 00:06:29,300 --> 00:06:32,260 bet, saskaitot operācijām, ka man pirmdien, 133 00:06:32,260 --> 00:06:35,900 Salīdzinot divus cilvēkus, kas jūtas kā jauku mērvienības. 134 00:06:35,900 --> 00:06:40,980 >> Tātad n mīnus 1 soļus pirmo reizi, bet tad to, kas notika pēc tam? 135 00:06:40,980 --> 00:06:46,610 Kas ir viens otrādi viena caurlaide caur citādi nešķirotiem sarakstā? 136 00:06:46,610 --> 00:06:49,840 Ko jūs varat man pastāstīt par elementu kurš bija visu ceļu tur? 137 00:06:49,840 --> 00:06:51,300 Yeah? 138 00:06:51,300 --> 00:06:52,870 Tas bija lielākais elements, vai ne? 139 00:06:52,870 --> 00:06:55,710 Numurs astoņi, kaut gan viņa sākās šeit, katru reizi, kad es 140 00:06:55,710 --> 00:06:57,860 salīdzinot viņu pret kaimiņš, viņa tur 141 00:06:57,860 --> 00:07:00,480 burbuļo uz labo pusē no saraksta. 142 00:07:00,480 --> 00:07:02,710 Un tiešām, tas ir, ja algoritms iegūst savu nosaukumu. 143 00:07:02,710 --> 00:07:07,630 >> Tagad ar šo loģiku, cik daudz salīdzinājumi vajag Es veicu uz otro reizi 144 00:07:07,630 --> 00:07:09,800 Es veicu šo piespēli no kreisās uz labo pusi? 145 00:07:09,800 --> 00:07:10,730 n mīnus 2, vai ne? 146 00:07:10,730 --> 00:07:14,297 Tas būtu vienkārši izšķērdēt manu laiku, ja I saglabāt salīdzinot astoņi pret kādu 147 00:07:14,297 --> 00:07:16,630 citur, jo mēs jau zinām viņa bija savā vietā. 148 00:07:16,630 --> 00:07:19,760 Tā ka ir mazliet optimizācija, tāpēc nākamais pass 149 00:07:19,760 --> 00:07:23,899 būs plus n mīnus divi soļi, kur n ir cilvēku skaits. 150 00:07:23,899 --> 00:07:26,940 Tagad jūs varat veida ekstrapolēt, pat Ja jūs neesat datorzinātnieks, 151 00:07:26,940 --> 00:07:27,680 kā tas beidzas. 152 00:07:27,680 --> 00:07:31,259 Beigās šo algoritmu, iespējams tev tikai viens salīdzinājums pa kreisi. 153 00:07:31,259 --> 00:07:33,800 Jums ir sava veida noteikt sākums saraksta gadījumā divām 154 00:07:33,800 --> 00:07:36,540 un viens ir no rīkojuma un būtu viens un divi, 155 00:07:36,540 --> 00:07:40,330 tāpēc šis dibeni veic plus 1 final salīdzinājums. 156 00:07:40,330 --> 00:07:44,500 >> Tagad dot, dot, dot veida viļņi, tas ir rokas pie dažas juicier detaļas, 157 00:07:44,500 --> 00:07:46,452 bet pieņemsim tikai iet uz priekšu un vienkāršot. 158 00:07:46,452 --> 00:07:48,660 Ja jūs atceraties no augstas skola, atklāti sakot, daudzi no jums 159 00:07:48,660 --> 00:07:50,340 bija matemātikas grāmatas, kas bija mazliet apkrāptu lapa 160 00:07:50,340 --> 00:07:52,550 uz priekšējā vāka, vai aizmugurējais vāciņš, kas parādīja, jums 161 00:07:52,550 --> 00:07:56,400 kādi sērijas summations piemēram Tas galu galā saskaita. 162 00:07:56,400 --> 00:07:59,600 Vispārīgā gadījumā, ja jums ir mainīgs, piemēram n, un patiesībā tas viens, 163 00:07:59,600 --> 00:08:01,634 ja jūs paskatījās jūsu vecās skolas matemātikas grāmata, 164 00:08:01,634 --> 00:08:04,050 jūs varētu redzēt, ka tas patiesībā piebilst, līdz šīs summas šeit 165 00:08:04,050 --> 00:08:07,970 n reizes n mīnus 1 viss dalīts ar 2. 166 00:08:07,970 --> 00:08:11,172 Tātad tagad ļaujiet man tikai noteikt, tā ir taisnība, tāpēc uz lēciens ticības, 167 00:08:11,172 --> 00:08:12,880 ka tas, ko šis rezumē līdz, un mēs varētu 168 00:08:12,880 --> 00:08:14,341 pierāda, ka daudz vispārējā gadījumā. 169 00:08:14,341 --> 00:08:15,590 Bet tagad pieņemsim paplašināt šo out. 170 00:08:15,590 --> 00:08:19,920 Tāpēc pieņemsim reizināt šo, tā ka ir n brusas, mīnus n, viss dalīts ar 2. 171 00:08:19,920 --> 00:08:23,200 Tas tiešām n rūtiņām, dalīts ar 2, mīnus n nekā 2, 172 00:08:23,200 --> 00:08:25,010 tā, ka viss ir jauki un interesanti. 173 00:08:25,010 --> 00:08:27,060 Bet kas notiek, ja mēs Tagad plug-in vērtību? 174 00:08:27,060 --> 00:08:29,724 Pieņemsim, ka man nebija astoņi cilvēki, bet saka miljons. 175 00:08:29,724 --> 00:08:31,890 Un miljonus tikai tāpēc, ka tas ir diezgan liels skaits, 176 00:08:31,890 --> 00:08:34,039 pieņemsim plug ka, un redzēt, kas notiek. 177 00:08:34,039 --> 00:08:39,039 Tātad, ja es plug miljons minētajā formulā Es esmu gatavojas saņemt miljonus rūtiņām, 178 00:08:39,039 --> 00:08:42,868 dalīts ar 2, mīnus miljoni, dalīts ar 2. 179 00:08:42,868 --> 00:08:44,159 Tagad to, kas ir, kas notiek, lai ir vienādi? 180 00:08:44,159 --> 00:08:47,354 Tātad 500 miljardi, mīnus 500,000. 181 00:08:47,354 --> 00:08:49,270 Un, ja es tiešām ka math out, ka līdzekļi 182 00:08:49,270 --> 00:08:53,920 ka šķirošana miljons cilvēki ar burbuļa kārtošanas 183 00:08:53,920 --> 00:09:01,800 var aizņemt man 499999500000 soļi vai salīdzinājumi beigās, 184 00:09:01,800 --> 00:09:02,900 mēs esam tikai ekstrapolējot. 185 00:09:02,900 --> 00:09:06,860 >> Ka jūtas diezgan lēns, bet atklāti sakot mērot vienu konkrētu ieguldījumu 186 00:09:06,860 --> 00:09:09,160 , piemēram, tas, nav viss, kas stāsta. 187 00:09:09,160 --> 00:09:14,050 Bet tiešām tas liecina, ka, tā kā n saņem lielāku un lielāku, šo algoritmu 188 00:09:14,050 --> 00:09:16,280 veida jūtas sliktāk un sliktāk, vai jūs tiešām 189 00:09:16,280 --> 00:09:20,450 sāk izjust sāpes, ka exponentiation, ka n rūtiņām, 190 00:09:20,450 --> 00:09:21,770 kas iznāk diezgan ātri. 191 00:09:21,770 --> 00:09:25,340 Un šī informācija nav zaudēja uz cilvēkiem, patiesībā 192 00:09:25,340 --> 00:09:29,640 Pirms dažiem gadiem zināma senators, kurš bija kampaņas, apsēdās uz interviju 193 00:09:29,640 --> 00:09:32,180 ar Google Eric Schmidt, CEO tajā laikā, 194 00:09:32,180 --> 00:09:36,380 un apstrīdēja ar jautājumu daudz, piemēram, mēs pētām šodien. 195 00:09:36,380 --> 00:09:38,468 Pieņemsim to apskatīt. 196 00:09:38,468 --> 00:09:45,280 >> [Video atskaņošana] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Tu esi šeit Google, un man patīk 198 00:09:48,560 --> 00:09:53,382 domāt par prezidentūras kā darba interviju. 199 00:09:53,382 --> 00:09:56,434 Tagad, tas ir grūti iegūt darbu kā prezidents, 200 00:09:56,434 --> 00:09:58,100 un jūs iet cauri drebuļi tagad. 201 00:09:58,100 --> 00:10:01,860 Tas ir arī grūti iegūt darbu pie Google. 202 00:10:01,860 --> 00:10:05,490 Mums ir jautājumi, un mēs uzdot mūsu kandidātiem jautājumus, 203 00:10:05,490 --> 00:10:09,770 un tas viens no Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- jūs puiši domājat, ka es esmu kidding, tas ir tepat. 205 00:10:14,760 --> 00:10:17,930 Kas ir visefektīvākais veids, kā šķirot miljons 32-bitu integers? 206 00:10:17,930 --> 00:10:21,800 207 00:10:21,800 --> 00:10:24,350 >> -Well-- 208 00:10:24,350 --> 00:10:25,200 >> -Es Žēl, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> -Nē, Nē, nē. 210 00:10:27,400 --> 00:10:30,700 Es domāju, ka burbulis šķirot būtu nepareizs ceļš. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> -Nāc, Kas viņam šo stāstīja? 213 00:10:38,180 --> 00:10:40,590 Es neredzēju datoru zinātne jūsu fona. 214 00:10:40,590 --> 00:10:42,130 >> -We've Ieguva mūsu spiegu tur. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> -OK, Pieņemsim uzdot atšķirīgs intervija jautājums. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO PLAYBACK] 218 00:10:49,300 --> 00:10:52,290 >> SPEAKER: Tātad runājam konkrēti skaitļi, lai gan, 219 00:10:52,290 --> 00:10:53,890 nav būs viss, kas noderīgs. 220 00:10:53,890 --> 00:10:56,810 Tas nav dzīves mācība, ka burbulis kārtot, ņemot miljons ieejas, 221 00:10:56,810 --> 00:10:58,590 varētu veikt tik daudz kā 500 miljardi soļus. 222 00:10:58,590 --> 00:11:01,120 Jūs nevarat īsti vispārināt Arī faktiski no tā 223 00:11:01,120 --> 00:11:03,560 un darīt labus dizains lēmumus rakstot programmas. 224 00:11:03,560 --> 00:11:07,070 Tātad, pieņemsim koncentrēties gan uz to, kā mēs varētu vienkāršot šo rezultātu. 225 00:11:07,070 --> 00:11:11,780 >> Tāpēc es esmu iezīmēts dzeltenā šeit rezultāts n kvadrātā dalīts ar 2, 226 00:11:11,780 --> 00:11:14,330 tāpēc miljons kvadrātā dalot ar 2, un pēc tam 227 00:11:14,330 --> 00:11:16,710 Es esmu uzsvērusi to, ko galīgā atbilde bija 228 00:11:16,710 --> 00:11:20,180 kad mēs jāatņem off n dalīts ar 2. 229 00:11:20,180 --> 00:11:24,850 Un apgalvojums es esmu gatavojas darīt tagad, kurš heck cares, ja tu atņem off 230 00:11:24,850 --> 00:11:30,060 mazliet vecs n vairāk nekā 2, kad pirmais daļa no šīs formulas ir tik daudz lielāks? 231 00:11:30,060 --> 00:11:33,910 Tā dominē otru termins, n kvadrātā dalīts ar 2 232 00:11:33,910 --> 00:11:37,510 ir tik daudz lielāks, nepārprotami, jo n izpaužas liels, piemēram, miljons, 233 00:11:37,510 --> 00:11:41,450 ka ir tiešām liela atšķirība pie dienas beigās no 500 miljardu 234 00:11:41,450 --> 00:11:45,730 un 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Nav īsti. 236 00:11:46,349 --> 00:11:48,640 Un tā, ko mēs gatavojamies darīt, kā datoru zinātnieki ir 237 00:11:48,640 --> 00:11:53,270 ignorēt šos zemākas kārtības noteikumus un veikt kaut kas līdzīgs šim, un patiešām 238 00:11:53,270 --> 00:11:56,050 tikai vienkāršot to termins, kas notiek, lai jautājums. 239 00:11:56,050 --> 00:12:00,315 Lielāki mūsu datu kopas nokļūt, lielāks Mūsu datu bāzes iegūt, jo vairāk interneta lapas 240 00:12:00,315 --> 00:12:02,690 mums ir jāmeklē, vairāk draugi jums ir uz Facebook. 241 00:12:02,690 --> 00:12:07,340 >> Kā n kļūst lielāka, mēs patiešām gatavojas rūpēties par lielāko 242 00:12:07,340 --> 00:12:11,560 jēdziens jebkurā šādā analīzē mūsu algoritmi sniegumu. 243 00:12:11,560 --> 00:12:16,230 Un es esmu gatavojas teikt, jūs zināt, ko, burbulis veida ir par lielo O rīkojumu, 244 00:12:16,230 --> 00:12:18,060 par n secībā brusas. 245 00:12:18,060 --> 00:12:20,090 Tas nav tieši n brusas, kā mēs esam redzējuši, 246 00:12:20,090 --> 00:12:22,060 bet kurš tiešām rūpējas par šiem mazākiem nosacījumiem, 247 00:12:22,060 --> 00:12:24,390 un godīgi sakot, kas tiešām cares, ja mēs sadalīt pa 2? 248 00:12:24,390 --> 00:12:25,870 Tas ir tikai nemainīgs faktors. 249 00:12:25,870 --> 00:12:29,480 Un ir 500 miljardi pret 250 miljardiem tiešām tik liels ir galā? 250 00:12:29,480 --> 00:12:32,190 Es varētu vienkārši gaidīt vienu gadu, let manu klēpjdators burtiski 251 00:12:32,190 --> 00:12:34,810 saņemt divreiz ātrāk aparatūru, un kas veida starpības 252 00:12:34,810 --> 00:12:36,650 vienkārši iet prom dabiski laika gaitā. 253 00:12:36,650 --> 00:12:39,300 >> Ko mēs rūpējamies par to ir izteiksme, daļa 254 00:12:39,300 --> 00:12:42,489 Izteiksmes, kas notiek variēt kā mūsu ieguldījums kļūst lielāka un lielāka. 255 00:12:42,489 --> 00:12:45,280 Un tiešām, reālajā pasaulē, tas, kas notiek arvien biežāk 256 00:12:45,280 --> 00:12:48,330 ir ieejas uz mūsu problēmām un algoritmi kļūst lielāki. 257 00:12:48,330 --> 00:12:53,470 Tik liels O būs atzīme, asimptotiskās apzīmējums, ka mēs vienkārši 258 00:12:53,470 --> 00:12:57,160 izmantot kā datoru zinātnieki, lai aprakstītu stāvokli, vai darbības laiks, 259 00:12:57,160 --> 00:12:58,130 algoritma. 260 00:12:58,130 --> 00:13:00,800 Tāpēc, ka mēs varam salīdzināt algoritmus uz dažādiem datoriem rakstveida 261 00:13:00,800 --> 00:13:04,170 dažādi cilvēki, izmantojot daži fundamentāli līdzīgs metrisko 262 00:13:04,170 --> 00:13:07,557 tāpat skaita salīdzinājumu tu esi pieņemšanā, vai varbūt skaitu mijmaiņas darījumu 263 00:13:07,557 --> 00:13:08,140 jūs gūstat. 264 00:13:08,140 --> 00:13:11,910 >> Ko mēs nebrauksim skaits ir laika daudzums 265 00:13:11,910 --> 00:13:13,981 kas iet uz pulksteni uz sienas tipisku. 266 00:13:13,981 --> 00:13:16,230 Ko mēs nebrauksim jāuztraucas par to ir, cik daudz atmiņas 267 00:13:16,230 --> 00:13:17,820 jūs izmantojat šodien at Vismaz, lai gan tas ir 268 00:13:17,820 --> 00:13:19,370 vēl viens resurss, mēs varētu izmērīt. 269 00:13:19,370 --> 00:13:23,610 Mēs ejam, lai mēģinātu pamatot savu analīzi par tikai no pamatdarbības, tie, 270 00:13:23,610 --> 00:13:25,930 atklāti sakot, ka jūs varat redzēt, lielākā daļa vizuāli. 271 00:13:25,930 --> 00:13:30,700 Tātad ar kaut ko līdzīgu lielo O n brusas, es apgalvot, ka O n kvadrātā 272 00:13:30,700 --> 00:13:35,820 ir augšējā robeža tā saukto darbības laiks burbulis veida. 273 00:13:35,820 --> 00:13:38,820 Citiem vārdiem sakot, ja jums gribēja apgalvot, ka tur ir 274 00:13:38,820 --> 00:13:41,370 šī augšējā robeža, cik daudz soļi algoritms varētu veikt, 275 00:13:41,370 --> 00:13:46,240 tas būs lielā O n brusas šajā gadījumā, augšējo robežu. 276 00:13:46,240 --> 00:13:49,710 >> Ko darīt, ja es tā vietā mainās stāsts ir ne par burbulis kārtot, 277 00:13:49,710 --> 00:13:50,910 bet par šo augšējo robežu. 278 00:13:50,910 --> 00:13:54,030 Vai jūs varat iedomāties algoritmu ka mēs esam paskatījās jau 279 00:13:54,030 --> 00:13:59,530 kuru augšējo robežu, maksimālais izmērīt laika vai darbībām, 280 00:13:59,530 --> 00:14:04,300 būtu teikt, ka ierobežo ar n, lineāra funkcija, 281 00:14:04,300 --> 00:14:07,260 nav kvadrāta viens, kas ir izliekta? 282 00:14:07,260 --> 00:14:10,780 Kas ir algoritms, kas vienmēr aizņem ne vairāk 283 00:14:10,780 --> 00:14:12,860 nekā, piemēram, n soļus, vai 2n pakāpieni, vai 3n soļi? 284 00:14:12,860 --> 00:14:13,360 Yeah? 285 00:14:13,360 --> 00:14:15,030 >> AUDITORIJA: Meklējot Visvairāk sarakstā? 286 00:14:15,030 --> 00:14:16,930 >> SPEAKER: Perfect, konstatējot Visvairāk sarakstā. 287 00:14:16,930 --> 00:14:18,940 Ja es esmu dota sarakstu cilvēki piemēram, 288 00:14:18,940 --> 00:14:21,440 katrs no kuriem ir saimniecības numuru, kas ir maksimālais skaits 289 00:14:21,440 --> 00:14:23,770 par pasākumiem, ko tā būtu jāņem mani, samērā gudrs cilvēks, 290 00:14:23,770 --> 00:14:27,530 lai atrastu lielāko personu šajā sarakstā? 291 00:14:27,530 --> 00:14:28,100 n, vai ne? 292 00:14:28,100 --> 00:14:31,320 Jo sliktākajā gadījumā, kad varētu lielākā vērtība būt? 293 00:14:31,320 --> 00:14:32,700 Labi, visu ceļu beigās. 294 00:14:32,700 --> 00:14:34,575 Tātad sliktākajā gadījumā augšējā robeža, es varētu 295 00:14:34,575 --> 00:14:36,450 ir iet visu ceļu šurp un būt, piemēram, 296 00:14:36,450 --> 00:14:39,170 oh, šeit ir vairāki astoņi, vai kāds, ka vērtība ir. 297 00:14:39,170 --> 00:14:41,330 Tagad tas būtu vienkārši stulbi ja es tur iet, vai ne? 298 00:14:41,330 --> 00:14:43,840 Meklē vairāk un vairāk elementiem ja pēdējais no tiem ir tur? 299 00:14:43,840 --> 00:14:45,340 Tātad, protams, n ir augšējo robežu. 300 00:14:45,340 --> 00:14:47,420 Man nav nepieciešams veikt vairāk soļi nekā. 301 00:14:47,420 --> 00:14:51,580 >> Tātad, ko tad, ja tā vietā, es ierosināju, ka ir algoritmi šajā pasaulē, kas 302 00:14:51,580 --> 00:14:57,750 ir darbības laiku, kas ir robežojas ar lielo O log n log n? 303 00:14:57,750 --> 00:15:00,390 Kur mēs esam redzējuši šo pirms? 304 00:15:00,390 --> 00:15:00,890 Yeah? 305 00:15:00,890 --> 00:15:03,309 >> AUDITORIJA: In tālruņa grāmatu problēmu? 306 00:15:03,309 --> 00:15:04,850 SPEAKER: Tāpat tālruņa grāmatu problēmu. 307 00:15:04,850 --> 00:15:07,754 Kāds bija pasākums, cik daudz laika vai cik asaras IT 308 00:15:07,754 --> 00:15:10,170 aizveda mani atrast kādu, piemēram, Mike Smith tālruņu katalogā? 309 00:15:10,170 --> 00:15:13,212 Mums apgalvoja, ka tas bija log n, un pat ja svešs, vai tas tā ir 310 00:15:13,212 --> 00:15:15,170 mazliet dūmakains, ko logaritms vai eksponents bija 311 00:15:15,170 --> 00:15:17,650 tikai atcerieties, ka log n parasti attiecas uz procesu, 312 00:15:17,650 --> 00:15:20,790 Šajā gadījumā, dalot kaut pusi atkal, un atkal, 313 00:15:20,790 --> 00:15:25,790 un atkal, un atkal, tā, ka tā kļūst arvien mazs, kā jūs darīt. 314 00:15:25,790 --> 00:15:28,470 >> Tātad log of n atsaucas, pārliecināts, uz tālruņa grāmatu, piemēram, 315 00:15:28,470 --> 00:15:32,662 uz bināro meklēšanu teoriju, kad mēs bija virtuālās durvis uz kuģa, 316 00:15:32,662 --> 00:15:34,370 vai tad, kad Sean bija meklē kaut ko. 317 00:15:34,370 --> 00:15:37,374 Ja viņš ir izmantojis bināro meklēšanu, log n būtu augšējo robežu, cik daudz 318 00:15:37,374 --> 00:15:38,040 laiks, kas notiek. 319 00:15:38,040 --> 00:15:44,027 Bet tie algoritmi, kas skrēja log n pieņemts kāda atslēgu detaļu? 320 00:15:44,027 --> 00:15:45,360 Šis saraksts ir sakārtots, labi? 321 00:15:45,360 --> 00:15:47,789 Tavs algoritms ir nepareizi, ja jūsu ieguldījums nav sakārtots, 322 00:15:47,789 --> 00:15:49,830 un tomēr jūs izmantojat kaut kā bināro meklēšanu 323 00:15:49,830 --> 00:15:51,704 tāpēc, ka jūs varētu lēkt tiesības pār elementu 324 00:15:51,704 --> 00:15:53,600 neapzinoties tā ir patiešām tur. 325 00:15:53,600 --> 00:15:55,600 >> Tagad, ko tas varētu nozīmēt, Big O vienu? 326 00:15:55,600 --> 00:15:59,117 Tas nenozīmē, ka jūsu algoritmu aizņem viens un tikai viens solis, 327 00:15:59,117 --> 00:16:01,200 tas tikai nozīmē, ka tas notiek konstante vairāki soļi. 328 00:16:01,200 --> 00:16:04,060 Varbūt tas ir 1, varbūt tā ir 10, varbūt tas ir 1000, 329 00:16:04,060 --> 00:16:07,750 bet tas ir neatkarīgs no problēmas apmēri. 330 00:16:07,750 --> 00:16:10,850 Nav svarīgi, cik liels n ir, pastāvīgs laiks algoritms 331 00:16:10,850 --> 00:16:12,747 vienmēr ir tāds pats vairākus pasākumus. 332 00:16:12,747 --> 00:16:15,080 Tātad, kādi varētu būt algoritms mēs esam runājuši par to, vai vienkārši 333 00:16:15,080 --> 00:16:20,418 intuitīvi, kas nāk pie jums, ka vienmēr darbojas tā sauktajā pastāvīgu laiku? 334 00:16:20,418 --> 00:16:20,918 Yeah? 335 00:16:20,918 --> 00:16:22,001 >> AUDITORIJA: Pievienot divus numurus. 336 00:16:22,001 --> 00:16:25,320 SPEAKER: Pievienot divus numurus, 2 plus 2 ir vienāds ar 4, darīts. 337 00:16:25,320 --> 00:16:27,227 Lai varētu strādāt, ko vēl? 338 00:16:27,227 --> 00:16:28,560 Kā par vairāk reālajā pasaulē, jā? 339 00:16:28,560 --> 00:16:30,686 >> AUDITORIJA: Meklējot pirmā lieta sarakstā. 340 00:16:30,686 --> 00:16:32,810 SPEAKER: Meklējot pirmais elements sarakstā, pārliecināts. 341 00:16:32,810 --> 00:16:34,540 Mēs esam patiešām ir runāt par masīviem jau 342 00:16:34,540 --> 00:16:36,540 kā jūs saņemsiet pie pirmais elements masīvā, 343 00:16:36,540 --> 00:16:40,465 vienalga, cik ilgi masīvs ir C kodu? 344 00:16:40,465 --> 00:16:43,090 Jūs vienkārši izmantot kā kronšteinu nulle apzīmējums, bam, tu esi tur. 345 00:16:43,090 --> 00:16:46,120 Un patiešām bloki, kā malā, atbalsts kaut vispārzināma 346 00:16:46,120 --> 00:16:49,240 kā brīvpiekļuves, brīvpieejas atmiņa, jo jūs varat burtiski 347 00:16:49,240 --> 00:16:50,284 pāriet uz jebkuru vienā vietā. 348 00:16:50,284 --> 00:16:52,700 Mēs varam izdarīt vēl vienkāršāk mēs varam attīt uz nedēļu nulles 349 00:16:52,700 --> 00:16:53,900 kad mēs darījām Scratch. 350 00:16:53,900 --> 00:16:59,707 Cik daudz laika tas veic, lai saka bloks Scratch izpildīt? 351 00:16:59,707 --> 00:17:00,790 Tikai nemainīgs laiks, vai ne? 352 00:17:00,790 --> 00:17:03,960 Pateikt kaut ko, teiksim kaut ko, tas nav svarīgi 353 00:17:03,960 --> 00:17:07,359 cik liels Skrāpējumi pasaule ir, tas vienmēr ir gatavojas pieņemt tādu pašu laiku 354 00:17:07,359 --> 00:17:08,490 vienkārši pateikt kaut ko. 355 00:17:08,490 --> 00:17:11,089 >> Tā ka ir nemainīgs laiks, bet to, kas ir otra puse? 356 00:17:11,089 --> 00:17:13,030 Ja tas bija augšējais robežas, kas notiks, ja mēs gribam 357 00:17:13,030 --> 00:17:17,089 aprakstīt zemākas robežas mūsu algoritmu darbības laiks? 358 00:17:17,089 --> 00:17:19,852 Gandrīz labākajā gadījumā potenciāli, ja jūs, 359 00:17:19,852 --> 00:17:23,060 gan šie noteikumi varētu attiekties uz labāko lietas, sliktākajā lietas, vidējās gadījumi vairāk 360 00:17:23,060 --> 00:17:26,359 vispār, bet pieņemsim tikai koncentrēties uz apakšējā robeža kopumā. 361 00:17:26,359 --> 00:17:31,920 Kas ir algoritms, kas ir zemākā robeža n soļiem, 362 00:17:31,920 --> 00:17:33,350 vai 2n pakāpieni, vai 3n soļi? 363 00:17:33,350 --> 00:17:36,241 Daži no n soļiem faktors, tas tā apakšējo robežu. 364 00:17:36,241 --> 00:17:36,740 Yeah? 365 00:17:36,740 --> 00:17:37,910 >> AUDITORIJA: Bubble kārtošanas? 366 00:17:37,910 --> 00:17:41,610 >> SPEAKER: Bubble kārtošanas notiek Jūs minimāli n soļi, kāpēc? 367 00:17:41,610 --> 00:17:42,279 Kāpēc tā? 368 00:17:42,279 --> 00:17:45,320 Kāpēc, ka sākums nākt pie jums intuitīvi, pat ja tas ne tikai 369 00:17:45,320 --> 00:17:46,530 vēl? 370 00:17:46,530 --> 00:17:47,030 Yeah? 371 00:17:47,030 --> 00:17:47,990 >> AUDITORIJA: [nedzirdama]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 SPEAKER: Tieši tā. 374 00:17:52,360 --> 00:17:55,810 Vislabākajā iespējamajā scenārijā burbulis kārtot, un daudz algoritmu, 375 00:17:55,810 --> 00:17:58,769 ja es roku jums astoņi cilvēki kuri jau ir sakārtoti, 376 00:17:58,769 --> 00:18:00,560 tas būtu muļķīgi jums, algoritms, 377 00:18:00,560 --> 00:18:02,202 iet uz priekšu un atpakaļ vairāk nekā vienu reizi, vai ne? 378 00:18:02,202 --> 00:18:04,285 Jo, tiklīdz jūs iet cauri sarakstam vienu reizi, 379 00:18:04,285 --> 00:18:08,090 Jums vajadzētu saprast, ak, es nē mijmaiņas līgumi, šis saraksts ir sakārtots, izeju. 380 00:18:08,090 --> 00:18:09,700 Bet kas notiek, lai tevi n soļus. 381 00:18:09,700 --> 00:18:12,033 >> Un otrādi, kas ir vēl viens veids, kā domāt par to? 382 00:18:12,033 --> 00:18:15,240 Bubble kārtošanas ir omega, tā sakot, no n, 383 00:18:15,240 --> 00:18:19,050 jo, ja paskatās mazāk nekā n elementi, ko 384 00:18:19,050 --> 00:18:23,009 ir būtisks jautājums tur? 385 00:18:23,009 --> 00:18:24,550 Jūs nezināt, ja tas ir sakārtots, labi. 386 00:18:24,550 --> 00:18:26,800 Mēs cilvēki varētu skatienu pulksten astoņos cilvēki un būt, piemēram, ak, tas ir sakārtoti, 387 00:18:26,800 --> 00:18:28,430 ka neņēma mani n soļus, bet tas notika. 388 00:18:28,430 --> 00:18:30,810 Tavas acis, lai gan jums veida gada ir liels redzeslauku, 389 00:18:30,810 --> 00:18:33,184 Jūs paskatījās astoņiem elementiem, Jūs paskatījās astoņiem cilvēkiem, 390 00:18:33,184 --> 00:18:34,610 tas ir astoņi soļi efektīvi. 391 00:18:34,610 --> 00:18:38,612 Un tikai tad, ja es staigāju visa saraksts darīt es saprotu, jā, sakārtoti. 392 00:18:38,612 --> 00:18:41,320 Ja man apstāties pusceļā domāt, viss labi, tas ir diezgan sakārtoti līdz šim, 393 00:18:41,320 --> 00:18:42,520 kādas ir izredzes, tas nav šķirotas? 394 00:18:42,520 --> 00:18:44,186 Ka algoritmi nebūs pareizs. 395 00:18:44,186 --> 00:18:46,250 Varētu būt ātrāks, bet nepareizi. 396 00:18:46,250 --> 00:18:48,500 >> Tāpēc tagad mums ir veids, kā Aprakstot zemākas robežas, 397 00:18:48,500 --> 00:18:49,710 un ko par pastāvīgu laiku? 398 00:18:49,710 --> 00:18:54,565 Kas ir algoritms, kas ir zemāka saista tās darba laika viena? 399 00:18:54,565 --> 00:18:58,350 1 solis, 2 soļi, 10 soļi, bet nemainīgs, neatkarīgi no N, 400 00:18:58,350 --> 00:18:59,310 lielums ievadi? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Jā, aizmugurē. 403 00:19:04,600 --> 00:19:05,309 >> AUDITORIJA: Printf? 404 00:19:05,309 --> 00:19:06,183 SPEAKER: Kas tas tāds? 405 00:19:06,183 --> 00:19:07,184 AUDITORIJA: Printf? 406 00:19:07,184 --> 00:19:07,850 SPEAKER: Printf. 407 00:19:07,850 --> 00:19:08,400 Labi, protams. 408 00:19:08,400 --> 00:19:10,720 Tātad tas aizņem fiksētu vairākus pasākumus. 409 00:19:10,720 --> 00:19:13,170 Un es būtu now-- tagad, ka mēs runājam par C kodu 410 00:19:13,170 --> 00:19:16,040 un nevis Scratch, kaut piemēram, teiksim, ar printf, 411 00:19:16,040 --> 00:19:17,710 mums vajadzētu sākt saņemt uzmanīgiem. 412 00:19:17,710 --> 00:19:21,090 Jo printf nav jāveic ievadi, tas ir string, 413 00:19:21,090 --> 00:19:23,220 un auklas tie tehniski ir garums. 414 00:19:23,220 --> 00:19:25,530 Tātad, ja mēs tagad gribam uzņemt par jums, ja jums nav prātā, 415 00:19:25,530 --> 00:19:29,430 tehniski mēs varētu apgalvot, ka printf tas ņem mainīga garuma ievadi, 416 00:19:29,430 --> 00:19:32,270 un, protams, tas var aizņemt vairāk laiks drukāt virkni šo ilgi, 417 00:19:32,270 --> 00:19:33,560 par šo ilgi. 418 00:19:33,560 --> 00:19:36,570 >> Tātad, ko tad mēs uzskatām tikai šķirošanas un meklēšanas piemērus? 419 00:19:36,570 --> 00:19:40,450 Kas par Mike Smith tālrunī grāmatu, vai binārā meklēšana plašāk? 420 00:19:40,450 --> 00:19:42,220 Labākajā gadījumā, kas varētu notikt? 421 00:19:42,220 --> 00:19:45,577 Es atvērt telefona grāmatu un, bam, tur ir Maika Smita numurs. 422 00:19:45,577 --> 00:19:46,660 Es varu zvanīt viņam uzreiz. 423 00:19:46,660 --> 00:19:49,390 >> Spēra vienu soli, varbūt divos posmos, bet pastāvīga vairākus pasākumus 424 00:19:49,390 --> 00:19:50,230 ja es saņēmu laimīgs. 425 00:19:50,230 --> 00:19:52,570 Un godīgi sakot, mēs redzējām Pirmdiena Jūsu klasesbiedrs 426 00:19:52,570 --> 00:19:54,710 iegūt diezgan laimīgs divas reizes pēc kārtas. 427 00:19:54,710 --> 00:19:57,050 Un tas patiešām bija nemainīgs laiks zemāku robežas 428 00:19:57,050 --> 00:20:01,280 par algoritma jautājumu, lai atrastu numurs 50 aiz tiem slēgts 429 00:20:01,280 --> 00:20:01,830 durvis. 430 00:20:01,830 --> 00:20:06,400 >> Tagad, kā malā, ja jūs atklāsiet ka gan liels O, augšējo robežu, 431 00:20:06,400 --> 00:20:09,310 un omega, zemākā robeža, ir viena un tā pati, kas 432 00:20:09,310 --> 00:20:11,830 ir tāda pati formula iekavas, varat arī 433 00:20:11,830 --> 00:20:15,170 teikt, tikai, lai būtu iedomātā, ka kaut kas ir teta 434 00:20:15,170 --> 00:20:18,270 n vai teta kādas citas vērtības. 435 00:20:18,270 --> 00:20:20,661 Tas tikai nozīmē, kad liels O un omega ir vienādi. 436 00:20:20,661 --> 00:20:21,910 Tagad, ko par atlases veida? 437 00:20:21,910 --> 00:20:23,400 Pieņemsim izmantot šo jauno vārdu krājumu. 438 00:20:23,400 --> 00:20:27,407 Šajā atlases veida, kādi bija mēs dara atkal, un atkal, un atkal? 439 00:20:27,407 --> 00:20:29,990 Man bija iet uz priekšu un atpakaļ, izmantojot sarakstu, meklē kam? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Mazākais numurs. 442 00:20:34,730 --> 00:20:37,560 >> Tik, cik daudzi soļi, kā daudzi salīdzinājumi did I 443 00:20:37,560 --> 00:20:43,250 ir jāveic, lai noskaidrotu, kurš mazākais elements sarakstā bija? 444 00:20:43,250 --> 00:20:44,437 n mīnus 1, vai ne? 445 00:20:44,437 --> 00:20:47,770 Jo, ja es vienkārši sākt ar vienu es esmu dota, un es sāku salīdzināt viņu, 446 00:20:47,770 --> 00:20:49,519 tad viņam vai viņai, viņam vai viņas, viņam vai viņai, es 447 00:20:49,519 --> 00:20:52,010 var tikai pārī elementus kopā n mīnus 1 reizes. 448 00:20:52,010 --> 00:20:55,630 Tātad izvēle veida līdzīgi notiek n mīnus 1 soļus pirmo reizi. 449 00:20:55,630 --> 00:20:59,540 >> Cik soļus tas veic mani atrast otro mazāko elementu? 450 00:20:59,540 --> 00:21:02,920 n mīnus 2, jo es esmu mēms ja es turpinu meklē paši cilvēki 451 00:21:02,920 --> 00:21:06,280 atkal, ja es esmu jau izvēlējies viņam vai viņas un nodot tos savā vietā. 452 00:21:06,280 --> 00:21:09,270 Un trešais solis, n mīnus 3, tad n mīnus 4. 453 00:21:09,270 --> 00:21:11,020 Mēs esam redzējuši šo modeli pirms, un patiešām 454 00:21:11,020 --> 00:21:13,460 atlase veida līdzīgi ir augšējo robežu 455 00:21:13,460 --> 00:21:16,210 no n kvadrātā, ja mēs uz augšu, ka summēšanas. 456 00:21:16,210 --> 00:21:19,790 Kas ir tās apakšējo robežu, atlase kārtošanas? 457 00:21:19,790 --> 00:21:25,350 Minimāli, cik daudz laika must atlase kārtot veikt, kā mēs to definēja pirmdien? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Ierosinās divas iespējas. 460 00:21:30,490 --> 00:21:32,360 Varbūt tas ir n, kā iepriekš. 461 00:21:32,360 --> 00:21:35,040 Varbūt tas ir n brusas, kā tas ir tagad, jo augšējo robežu. 462 00:21:35,040 --> 00:21:35,874 >> AUDITORIJA: n brusas. 463 00:21:35,874 --> 00:21:36,664 SPEAKER: n brusas. 464 00:21:36,664 --> 00:21:37,368 Kāpēc? 465 00:21:37,368 --> 00:21:40,060 >> AUDITORIJA: Jo jums ir definēt [nedzirdama]. 466 00:21:40,060 --> 00:21:41,510 >> SPEAKER: Tieši tā. 467 00:21:41,510 --> 00:21:45,077 Vismaz kā es noteikti atlases veida tas bija diezgan naivi, turpiniet, 468 00:21:45,077 --> 00:21:46,160 atrast mazāko elementu. 469 00:21:46,160 --> 00:21:47,770 Iet atkal, atrast mazāko elementu. 470 00:21:47,770 --> 00:21:49,490 Iet atkal, atrast mazāko elementu. 471 00:21:49,490 --> 00:21:51,700 Nav veida optimizācija tur, ka 472 00:21:51,700 --> 00:21:54,350 varētu man pārtraukt pēc tikai n vai tik soļi. 473 00:21:54,350 --> 00:21:57,080 Tik tiešām, atlase kārtot, omega n brusas. 474 00:21:57,080 --> 00:22:00,667 >> Kas par ievietošanas veida, kur es ņēma kas man tika dots, un tad es viņam plopped 475 00:22:00,667 --> 00:22:01,750 vai viņai īstajā vietā? 476 00:22:01,750 --> 00:22:04,958 Tad es turpināja otrajā personā, plopped viņam vai viņai īstajā vietā. 477 00:22:04,958 --> 00:22:07,910 Tad nākamais cilvēks, plopped viņam vai viņai īstajā vietā. 478 00:22:07,910 --> 00:22:10,537 Ievērojiet, ka tas ir ļoti lineāra, lai runāt. 479 00:22:10,537 --> 00:22:12,620 Es esmu taisne, es esmu nebrauksim uz priekšu un atpakaļ, 480 00:22:12,620 --> 00:22:16,080 Es nekad neesmu atskatoties īsti, bet kas notiek, kad es ievietot viņu 481 00:22:16,080 --> 00:22:20,302 vai viņas uz sākumu sarakstu, kā mēs to darījām pirmdien? 482 00:22:20,302 --> 00:22:21,010 Kas notiek? 483 00:22:21,010 --> 00:22:21,510 Yeah? 484 00:22:21,510 --> 00:22:23,122 AUDITORIJA: [nedzirdama]. 485 00:22:23,122 --> 00:22:24,830 SPEAKER: Jā, ka bija nozvejas, vai ne? 486 00:22:24,830 --> 00:22:26,746 Jūs varētu atsaukt no savu klasesbiedru, ja tie 487 00:22:26,746 --> 00:22:29,670 Tika jebkādu kustību ar kājām, kas bija operācija. 488 00:22:29,670 --> 00:22:33,610 Tātad, ja tur bija trīs cilvēki šeit un jauna persona piederēja ceļu tur, 489 00:22:33,610 --> 00:22:37,360 uz ilgu skatuves kā šis, protams, viņš vai viņa varētu vienkārši doties uz pašām beigām. 490 00:22:37,360 --> 00:22:40,074 Bet, ja mēs, domājot par dators un masīvs atmiņas, 491 00:22:40,074 --> 00:22:41,990 šie cilvēki dodas lai būtu, lai sajauktu vairāk 492 00:22:41,990 --> 00:22:43,260 lai atbrīvotu vietu šai personai. 493 00:22:43,260 --> 00:22:46,930 Un tā, ka n mīnus 1 shufflings, n mīnus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 mīnus 3 shufflings ir tikai sava veida notiek aiz manis, nevis man priekšā 495 00:22:50,660 --> 00:22:52,710 kā iepriekš, savā ziņā. 499 00:22:52,557 --> 00:22:54,640 Tagad, kā malā, un kā Jums varētu būt reizi manīts 500 00:22:54,640 --> 00:22:57,699 Ja jūs sākat papētījis par veidu, tur ir tik daudz dažādas tie 501 00:22:57,699 --> 00:22:59,490 tur, daži no tiem labāk nekā citi. 502 00:22:59,490 --> 00:23:02,200 Patiešām, bogosort ir viens tas ir sava veida jautrības uzmeklēt. 503 00:23:02,200 --> 00:23:06,650 Bogosort aizņem kopumu numuri vai teikt kārtis, 504 00:23:06,650 --> 00:23:09,870 nejauši sajauks viņiem, un pārbaudes, ja viņi sakārtoti. 505 00:23:09,870 --> 00:23:12,130 Un, ja nav, to dara atkārtoti. 506 00:23:12,130 --> 00:23:14,140 Un, ja nav, to dara atkārtoti. 507 00:23:14,140 --> 00:23:15,440 Ja tā nav, to dara atkārtoti. 508 00:23:15,440 --> 00:23:17,060 Neticami stulba. 509 00:23:17,060 --> 00:23:19,520 >> Un tiešām, ja jūs lasīt piemēram, Wikipedia rakstu, 510 00:23:19,520 --> 00:23:21,200 tā segvārds ir stulba kārtošanas. 511 00:23:21,200 --> 00:23:25,180 Tas būs iespējams strādāt, cerams, dots pietiekami daudz laika, 512 00:23:25,180 --> 00:23:28,240 bet, ka daudz laika varētu veikt diezgan kādu laiku. 513 00:23:28,240 --> 00:23:31,650 Tātad, ja es varētu, pieņemsim ātruma lietām up no Mary Beth piemēru agrāk, 514 00:23:31,650 --> 00:23:35,150 , ņemot vēl dažus elementus, bet vēl divi procesori. 515 00:23:35,150 --> 00:23:37,100 Divi cilvēki, ja jums neiebilstu savieno mani. 516 00:23:37,100 --> 00:23:40,972 Kā par 1 vairāk nekā šeit, un pieņemsim go-- nevienu pār tur? 517 00:23:40,972 --> 00:23:41,722 Neviens tur? 518 00:23:41,722 --> 00:23:42,221 OK. 519 00:23:42,221 --> 00:23:44,190 Tu ar melnu krekls, jā, nāk uz leju. 520 00:23:44,190 --> 00:23:45,000 Nu labi, kāds ir tavs vārds? 521 00:23:45,000 --> 00:23:45,720 >> AUDITORIJA: Peter. 522 00:23:45,720 --> 00:23:46,100 >> SPEAKER: Kas tas tāds? 523 00:23:46,100 --> 00:23:46,766 >> AUDITORIJA: Peter. 524 00:23:46,766 --> 00:23:49,450 SPEAKER: Pēteris, Dāvids, nice to meet you. 525 00:23:49,450 --> 00:23:53,670 Nu labi, mums ir Pēteris šeit, ja jums vēlaties nākt uz galda nekā šeit. 526 00:23:53,670 --> 00:23:54,550 Un kāds ir tavs vārds? 527 00:23:54,550 --> 00:23:55,216 >> AUDITORIJA: Elena. 528 00:23:55,216 --> 00:23:55,970 SPEAKER: Elena. 529 00:23:55,970 --> 00:23:57,030 OK, nice to meet you. 530 00:23:57,030 --> 00:23:58,060 Elena tiekas Pēteris. 531 00:23:58,060 --> 00:23:59,170 Pēteris, Elena. 532 00:23:59,170 --> 00:24:02,290 Un mums būs nepieciešams Andrew šeit, kā arī, lūdzu. 533 00:24:02,290 --> 00:24:06,107 Un jūsu uzdevums ir iet jābūt, lai kārtotu kārtis. 534 00:24:06,107 --> 00:24:08,190 Un, ja svešs, klāja Karšu vajadzētu galu galā 535 00:24:08,190 --> 00:24:11,064 sakārtoti nedaudz kaut kas līdzīgs tas, kur mēs darīsim klubiem, tad 536 00:24:11,064 --> 00:24:13,660 tad lāpstas, tad sirdis un dimanti, no dūzi kā viens, 537 00:24:13,660 --> 00:24:15,570 visu ceļu līdz pat karalim. 538 00:24:15,570 --> 00:24:20,890 >> Kārtis Es esmu gatavojas sniegt jums ir būs 52 daudzuma. 539 00:24:20,890 --> 00:24:23,160 Mēs ejam, lai līdzīgi laiks jums, tikai brīdi. 540 00:24:23,160 --> 00:24:26,410 Mēs ejam, lai mest Andrew uz ekrāna šeit 541 00:24:26,410 --> 00:24:28,170 lai skatīties, kā jūs to izdarītu. 542 00:24:28,170 --> 00:24:31,070 Un tā, ka tas viss ir viss vairāk redzams, 543 00:24:31,070 --> 00:24:33,490 šie ir kārtis es saņēmu par Amazon. 544 00:24:33,490 --> 00:24:42,861 Tātad tie jau nejauši sakārtoti, un mēs braucam pa laikam jums. 545 00:24:42,861 --> 00:24:44,610 Un mēs ejam saglabāt to reālu šoreiz, 546 00:24:44,610 --> 00:24:47,820 tāpēc mēs esam gatavojas izmēģināt, lai piespiestu tevi , jo pretējā gadījumā tas kļūs garlaicīgs 547 00:24:47,820 --> 00:24:48,460 ātri. 548 00:24:48,460 --> 00:24:53,860 Ja jūs varētu turpināt kārtot 52 elementus kopā caur kādu līdzekļiem, tagad. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Un atkal, kā mēs skatīties šos guys darīt ko, kas beigās 551 00:25:07,180 --> 00:25:10,200 gatavojas ražot acīmredzama Rezultāts, domāju par patiešām 552 00:25:10,200 --> 00:25:12,962 cik viņi katrs dara to, kā jūs varētu aprakstīt to. 553 00:25:12,962 --> 00:25:15,045 Jo atkal, tie ir visi procesi, algoritmi 554 00:25:15,045 --> 00:25:17,090 ka mēs uztveram par pašsaprotamu, jo cilvēkam. 555 00:25:17,090 --> 00:25:22,349 Bet jūs esat droši vien sen bija intuīcija, ilgi pirms jums pat 556 00:25:22,349 --> 00:25:24,390 domāja par ņemot datorzinātnes jums klase 557 00:25:24,390 --> 00:25:27,223 varētu būt bijusi intuīcija ar kas, lai atrisinātu problēmas, kā šis. 558 00:25:27,223 --> 00:25:29,560 Bet tad, kad jūs apzināties modeļus un sākt 559 00:25:29,560 --> 00:25:32,407 formalizēt pasākumus, ar kuriem jūs atrisināt šīs problēmas, 560 00:25:32,407 --> 00:25:35,490 Jūs atradīsiet, ka jūs varat atrisināt daudz vairāk interesantu un daudz sarežģītāka 561 00:25:35,490 --> 00:25:39,190 problēmas ātri. 562 00:25:39,190 --> 00:25:42,351 Lai kāds no skatītājiem, kas ir vismaz viens elements algoritmu 563 00:25:42,351 --> 00:25:43,350 ka viņi, izmantojot šeit? 564 00:25:43,350 --> 00:25:44,275 >> Mērķauditorija: [dzirdams] 565 00:25:44,275 --> 00:25:45,150 SPEAKER: Kas tas tāds? 566 00:25:45,150 --> 00:25:47,062 AUDITORIJA: Pēc uzvalks. 567 00:25:47,062 --> 00:25:47,770 SPEAKER: Pēc uzvalks. 568 00:25:47,770 --> 00:25:50,630 Tātad vispirms tie, sagrupējot visas dimantu kopā 569 00:25:50,630 --> 00:25:52,560 šķiet, visi sirdis kopā, šķiet, 570 00:25:52,560 --> 00:25:56,520 un tā tālāk, neievērojot par cipariem uz kartes. 571 00:25:56,520 --> 00:26:00,900 Un tagad tie parādās, piemēram, kas šķirojot tos pēc skaita. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Ļoti labs. 574 00:26:08,910 --> 00:26:12,370 >> Labi, lai to, kas notiek, lai būs pēdējais solis, tad šeit? 575 00:26:12,370 --> 00:26:16,950 Tiklīdz mums ir četri sakārtotās kostīmi, ko vai mums vajag darīt, lai četriem pāļu 576 00:26:16,950 --> 00:26:20,059 lai sasniegtu vienu sakārtoti klāja, gluži vienkārši? 577 00:26:20,059 --> 00:26:21,350 Tāpēc mums ir nepieciešams apvienot tos vēlreiz. 578 00:26:21,350 --> 00:26:25,160 >> Tātad tur ir interesanta ideja, ka atkal, daresay, ir ļoti intuitīva, pat 579 00:26:25,160 --> 00:26:28,140 ja jūs varētu nekad cirta šāda veida etiķetes par to. 580 00:26:28,140 --> 00:26:31,900 Šis būtisks jēdziens dalot problēma ne pusi šajā laikā, 581 00:26:31,900 --> 00:26:33,410 bet vismaz četrās daļās. 582 00:26:33,410 --> 00:26:36,810 Risināšana diezgan daudz fundamentāli identiskas problēmas 583 00:26:36,810 --> 00:26:40,480 ir izolēti viens no otra, un pēc tam apvienojot rezultātus. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Un, lielisks, darīts. 586 00:26:50,140 --> 00:26:52,140 Labi, liels apaļš aplausu, ja mēs varētu. 587 00:26:52,140 --> 00:26:56,480 >> [Aplausi] 588 00:26:56,480 --> 00:26:59,740 >> SPEAKER: Man nav ne jausmas, ko jūs darīt ar tiem, bet šeit jums iet. 589 00:26:59,740 --> 00:27:01,690 Thank you so much. 590 00:27:01,690 --> 00:27:04,660 Tātad, pieņemsim redzēt, divas minūtes un astoņas sekundes, 591 00:27:04,660 --> 00:27:07,490 Ja vēlaties, lai apstrīdētu draugus. 592 00:27:07,490 --> 00:27:12,160 Kas tad ir gatavojas ir prom no šīs 593 00:27:12,160 --> 00:27:13,830 ka mēs varam piesaistīt vairāk vispār? 594 00:27:13,830 --> 00:27:16,080 Nu, domāju, ka atpakaļ uz šis masīvs numuru, 595 00:27:16,080 --> 00:27:19,060 un domāju, ka atpakaļ tagad dažus pseudocode mēs esam rakstīts pagātnē, 596 00:27:19,060 --> 00:27:22,080 un tas bija pseudocode par risināšanā tālruņu grāmatas problēmu. 597 00:27:22,080 --> 00:27:25,150 Kuru in pseudocode I uzskaitītas vairāk metodisku ceļu 598 00:27:25,150 --> 00:27:28,400 aprakstīt, kā es darīju ļoti intuitīvs cilvēka algoritms dalot tālruni 599 00:27:28,400 --> 00:27:31,650 grāmata uz pusēm, atkārtot, atkārtot, atkārtot, līdz es atrast kāds, piemēram, Mike Smith, 600 00:27:31,650 --> 00:27:33,790 ja viņš ir patiešām tālruņu grāmatā. 601 00:27:33,790 --> 00:27:37,610 >> Bet es veida izmanto to, ko es saukšu ļoti iteratīvs pieeja šeit, 602 00:27:37,610 --> 00:27:42,160 jo īpaši paziņojumā līnija 8 un pozīcija 11. 603 00:27:42,160 --> 00:27:46,750 Tie ir pierādījums iteratīvs pieeja, looping pieeja, 604 00:27:46,750 --> 00:27:49,040 tāpēc, ka tas ir tieši uzvedība tie liek. 605 00:27:49,040 --> 00:27:52,910 Šie līnijas abas saku iet uz veida līniju trīs, un jūs varat no 606 00:27:52,910 --> 00:27:55,140 domāju, ka jūsu prāta acs kā cilpa. 607 00:27:55,140 --> 00:27:59,080 Tā stāsta jums iet atpakaļ uz augšu soli trīs un atkārtot atkal un atkal, 608 00:27:59,080 --> 00:28:00,010 un atkal. 609 00:28:00,010 --> 00:28:04,410 >> Bet ja mēs sviras galvenā ideja šeit, ka mēs neesam pēdējā reize, 610 00:28:04,410 --> 00:28:10,280 un vienkāršot līniju 8 un pozīcija 11 un viņu kaimiņi 611 00:28:10,280 --> 00:28:12,840 , jo tikai tas, dzeltenā krāsā. 612 00:28:12,840 --> 00:28:16,480 Tas nav būtiski saīsinot pseudocode ļoti daudz, 613 00:28:16,480 --> 00:28:20,530 bet tas ir būtiski mainās raksturs manas algoritmu. 614 00:28:20,530 --> 00:28:24,220 Kas es esmu tagad saka 7 soli, 10 solis 615 00:28:24,220 --> 00:28:29,140 ir meklēt Mike tieši tādā pašā veidā, 616 00:28:29,140 --> 00:28:31,580 bet tikai pa kreisi puse vai labi pusi. 617 00:28:31,580 --> 00:28:33,420 >> Tātad, citiem vārdiem sakot, ja Es sāku no viena soļa, 618 00:28:33,420 --> 00:28:36,150 uzņemt tālruņa grāmatu, atvērta vidu no tālruņu grāmatas, apskatīt vārdiem, 619 00:28:36,150 --> 00:28:39,010 ja Smith ir viena vārds ir, zvaniet Mike, cits 620 00:28:39,010 --> 00:28:44,340 ja Smits ir agrāk grāmatā, septiņi soli meklēt Mike kreisajā pusē grāmatas. 621 00:28:44,340 --> 00:28:47,130 Bet šāda veida jūtas kā tas ir atstājot mani karājas, labi? 622 00:28:47,130 --> 00:28:49,240 Dzeltenā krāsā, ir instrukcija, bet kā es varu 623 00:28:49,240 --> 00:28:51,870 meklēt Mike kreisi puse no tālruņa grāmatu? 624 00:28:51,870 --> 00:28:54,210 Kur man ir algoritms, ar kuru es 625 00:28:54,210 --> 00:28:57,100 var meklēt kādu, piemēram, Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Nu, tas skatās mums sejā. 627 00:28:58,980 --> 00:29:03,090 Es varu burtiski izmantot tieši tādu pašu programma faktiski iet uz augšu uz augšu 628 00:29:03,090 --> 00:29:06,490 atkal un atkal darbojas tās pašas līnijas kodu. 629 00:29:06,490 --> 00:29:10,610 >> Tātad, pat ja tas būtu justies kā mazliet cikliskas definīcijas 630 00:29:10,610 --> 00:29:13,480 kur jūs atbildētu kāds ir jautājums, ko tikai veida jautā 631 00:29:13,480 --> 00:29:15,990 pats jautājums atkal, piemēram, kāpēc, kāpēc, kāpēc? 632 00:29:15,990 --> 00:29:21,580 Realitāte ir tāda, ka mēs esam smagi kodēta pāris īpašas līnijas, 4 soli, 633 00:29:21,580 --> 00:29:25,320 kas ir, ja, un 12 soli, kas ir efektīvi cits filiāle, 634 00:29:25,320 --> 00:29:30,120 jo mums ir šie spunde pasākumus, tas algoritms beigsies, ja mēs 635 00:29:30,120 --> 00:29:32,050 atrast Mike, vai arī, ja mums nav. 636 00:29:32,050 --> 00:29:36,810 Bet 7 un soli 10 tagad, mums ir tas, ko mēs saucam rekursīvo algoritmu. 637 00:29:36,810 --> 00:29:40,420 Un rekursijas ir patiešām spēcīgs ideja ka ir maz prāta saliekuma sākumā, 638 00:29:40,420 --> 00:29:42,500 , ka mēs tagad varam piemēro šādi. 639 00:29:42,500 --> 00:29:46,600 >> Apvienot kārtot būs pēdējais kārtošanas, ka mēs skatāmies, vismaz klasē formāli. 640 00:29:46,600 --> 00:29:50,040 Un tas ir būtiski atšķiras no tiem pēdējiem trīs, un, protams, 641 00:29:50,040 --> 00:29:52,140 pēdējo četru ja mēs iekļaujam bogosort. 642 00:29:52,140 --> 00:29:54,810 Lūk pseudocode par sapludināšanas kārtošanas. 643 00:29:54,810 --> 00:30:00,170 Kad par ieejas n elementiem, tā, ņemot vērā masīva izmērs N, ja n ir mazāks par 2, 644 00:30:00,170 --> 00:30:01,040 atgriezties. 645 00:30:01,040 --> 00:30:03,610 Tātad, kāpēc man ir, ka vesels saprāts pārbaudīt vispirms? 646 00:30:03,610 --> 00:30:09,477 Kāda ir saistība, ja es roku tevi masīvs, kura garums n ir mazāks par 2? 647 00:30:09,477 --> 00:30:11,060 Tas jau ir sakārtoti, protams, labi? 648 00:30:11,060 --> 00:30:13,640 Jo saraksts nu ir viens elements, kas ir trivially 649 00:30:13,640 --> 00:30:15,180 sakārtoti, jo tas ir Vienīgais, kas tur. 650 00:30:15,180 --> 00:30:18,138 Vai tas ir no lieluma nulles, kas nozīmē, nekas, lai kārtotu, tāpēc pēc būtības 651 00:30:18,138 --> 00:30:18,720 tas ir sakārtots. 652 00:30:18,720 --> 00:30:20,410 Tur ir tikai nekas nepareizs tur. 653 00:30:20,410 --> 00:30:22,310 Tātad tas ir mūsu tā saucamā bāzes gadījums. 654 00:30:22,310 --> 00:30:24,440 >> Tas ir līdzīgs garā to, ko mēs darījām ar Mike. 655 00:30:24,440 --> 00:30:26,023 Ja Mike s tālruņu grāmatā, zvanu viņam. 656 00:30:26,023 --> 00:30:27,740 Ja viņš tur nav, atmest. 657 00:30:27,740 --> 00:30:31,240 Tas ir tā sauktais bāzes scenārijs, lai pārliecinātos, ka Šis algoritms beigās dienā 658 00:30:31,240 --> 00:30:33,540 apstāsies noteiktos apstākļos. 659 00:30:33,540 --> 00:30:37,890 >> Bet šeit ir lēciens ticības tagad, cits, kārtot kreiso pusi elementiem, 660 00:30:37,890 --> 00:30:39,740 tad šķirot tiesības puse no elementiem, 661 00:30:39,740 --> 00:30:41,189 un pēc tam apvienot sakārtoti pusītes. 662 00:30:41,189 --> 00:30:43,230 Un šeit ir, ja tā uzskata, kā mēs esam copping out. 663 00:30:43,230 --> 00:30:46,900 Esmu lūdza, lai sakārtotu n elementi, un es esmu 664 00:30:46,900 --> 00:30:50,712 sacīdams, OK, es to ar šķirošanu kreisi un šķirošanas tiesības. 665 00:30:50,712 --> 00:30:52,420 Bet es saku vienu Otra lieta, un šī 666 00:30:52,420 --> 00:30:55,530 ir galvenais temats šķiet uz intuīciju līdz šim, 667 00:30:55,530 --> 00:30:57,380 tur ir šis trešais solis apvienošanu. 668 00:30:57,380 --> 00:31:00,430 Kas, kaut arī tā šķiet tik mēms garā, 669 00:31:00,430 --> 00:31:02,320 tāpat vienkārši apvienot lietas kopā, šķiet, 670 00:31:02,320 --> 00:31:05,380 būt svarīgs solis pārbūves divas problēmas, kas 671 00:31:05,380 --> 00:31:07,330 tika sadalītas galu galā uz pusēm. 672 00:31:07,330 --> 00:31:12,090 >> Tātad apvienot kārtot, pieņemsim darīt, ja jūs humors mani, ar vēl vienu demonstrāciju, 673 00:31:12,090 --> 00:31:14,730 tikai tāpēc, ka mums ir daži numuri strādāt. 674 00:31:14,730 --> 00:31:19,470 Es varu apmainīties astoņi stresu bumbas astoņu cilvēku? 675 00:31:19,470 --> 00:31:29,320 Nu labi, kā par jums trīs, jūs četri šajā sadaļā, pieci, seši, un pieņemsim 676 00:31:29,320 --> 00:31:30,720 do 7, 8, nākt uz augšu. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 OK, jā OK. 679 00:31:36,520 --> 00:31:38,640 Mīnus 8, tur mēs ejam, plus 1. 680 00:31:38,640 --> 00:31:39,150 Excellent. 681 00:31:39,150 --> 00:31:42,000 Visas tiesības nākt uz augšu, pieņemsim ātri sniegt jums numurus. 682 00:31:42,000 --> 00:31:50,800 Numurs divi, numurs trīs, numurs četri, numuru pieci, seši, septiņi un astoņi. 683 00:31:50,800 --> 00:31:52,140 I did astoņi pareizi šo laiku. 684 00:31:52,140 --> 00:31:56,390 >> Labi, tā iet uz priekšu, ja jūs varētu, un pieņemsim sakārtotu sākotnējā kārtībā 685 00:31:56,390 --> 00:31:59,810 ka mums bija vakar, kas izskatījās , piemēram, tas, ja jūs neiebilstat. 686 00:31:59,810 --> 00:32:03,620 Un pieņemsim to darīt pie galda. 687 00:32:03,620 --> 00:32:06,510 Labi, tāpēc apvienot kārtošanas. 688 00:32:06,510 --> 00:32:08,820 Tas ir, ja tas notiek nokļūt veida interesants, 689 00:32:08,820 --> 00:32:12,800 jo man šķiet, kas sevi tik daudz mazāk informācijas šodien. 690 00:32:12,800 --> 00:32:15,149 >> Tātad apvienot kārtot vispirms par ieejas n elementiem, 691 00:32:15,149 --> 00:32:18,440 un, protams, nav mazāks par diviem, tas ir astoņi, tāpēc man ir dažas vairāk jāstrādā. 692 00:32:18,440 --> 00:32:21,140 Tāpēc tagad garīgi mēs kā klasē šobrīd ir cits filiālē, 693 00:32:21,140 --> 00:32:22,540 kas nozīmē trīs soļus. 694 00:32:22,540 --> 00:32:25,017 Pirmkārt, man ir, lai kārtotu kreiso pusi no elementiem. 695 00:32:25,017 --> 00:32:26,350 Tātad, kā es varu iet par to izdarīt? 696 00:32:26,350 --> 00:32:28,950 Nu, es esmu gatavojas veida garīgi sadalīt sarakstu šeit, 697 00:32:28,950 --> 00:32:30,700 jums nav fiziski kustēties, un es esmu 698 00:32:30,700 --> 00:32:33,180 gatavojas koncentrēties tikai uz kreisā puse no elementiem šeit. 699 00:32:33,180 --> 00:32:36,770 Tātad, kā es varu iet par šķirošanu Piedāvājuma saraksts izmēra četriem? 700 00:32:36,770 --> 00:32:38,730 Kas ir mans algoritms? 701 00:32:38,730 --> 00:32:42,580 Vispirms es pārbaudītu, ir n mazāks nekā divi, nē, tāpēc es pārietu uz citu bloku vēlreiz. 702 00:32:42,580 --> 00:32:43,900 Kārtot atstājis pusi no elementu. 703 00:32:43,900 --> 00:32:45,608 >> Tāpēc tagad atkal, garīgi, un tas ir, ja 704 00:32:45,608 --> 00:32:49,550 Jums ir uzkrāt daudz garīgo vēsturi, ja Jums gribas. 705 00:32:49,550 --> 00:32:51,940 Tagad es esmu šķirošanu kreiso puse no kreisās puses. 706 00:32:51,940 --> 00:32:57,000 Labi, tāpēc tagad es aicinu manu pašu sapludināšanu šķirošana algoritms, ir n mazāk nekā divas? 707 00:32:57,000 --> 00:33:00,590 Nē, tas ir divi, tāpēc man ir, lai sakārtotu kreiso pusi, un labajā pusē. 708 00:33:00,590 --> 00:33:02,042 Tātad šeit mēs ejam, sakārtot pa kreisi pusi. 709 00:33:02,042 --> 00:33:03,750 Kāpēc ne jūs vienkārši veikt vienu soli uz priekšu. 710 00:33:03,750 --> 00:33:04,415 Kāds ir tavs vārds? 711 00:33:04,415 --> 00:33:04,860 >> AUDITORIJA: Darren. 712 00:33:04,860 --> 00:33:05,260 >> SPEAKER: Dan. 713 00:33:05,260 --> 00:33:06,040 Dan ir pastiprināts priekšu. 714 00:33:06,040 --> 00:33:06,748 >> AUDITORIJA: Darren. 715 00:33:06,748 --> 00:33:09,000 SPEAKER: Darren, darīts. 716 00:33:09,000 --> 00:33:10,090 Tu teici Darren vai Dan? 717 00:33:10,090 --> 00:33:10,550 >> AUDITORIJA: Darren. 718 00:33:10,550 --> 00:33:11,216 >> SPEAKER: Darren. 719 00:33:11,216 --> 00:33:14,422 OK, Darren ir pastiprināts priekšu, un viņš tagad sakārtots. 720 00:33:14,422 --> 00:33:16,130 Un tas ir gandrīz muļķīgs apgalvojums, vai ne? 721 00:33:16,130 --> 00:33:18,862 Man nav īsti, šķiet, ir sasniegt kaut kas, bet pieņemsim turpināt. 722 00:33:18,862 --> 00:33:20,820 Tagad ļaujiet man sakārtot tiesības puse no elementiem. 723 00:33:20,820 --> 00:33:21,200 Kāds ir tavs vārds? 724 00:33:21,200 --> 00:33:21,690 >> AUDITORIJA: Luke. 725 00:33:21,690 --> 00:33:22,273 >> SPEAKER: Luke. 726 00:33:22,273 --> 00:33:23,400 Come on, soli uz priekšu. 727 00:33:23,400 --> 00:33:25,640 Darīts, man ir sakārtoti Luke. 728 00:33:25,640 --> 00:33:28,570 Kreisā puse tagad ir sakārtoti un tiesības puse tagad ir sakārtoti, 729 00:33:28,570 --> 00:33:30,770 bet atkal, tur ir svarīgs solis šeit. 730 00:33:30,770 --> 00:33:32,940 Kas man blakus vajag darīt? 731 00:33:32,940 --> 00:33:33,941 Apvienot sakārtoti pusītes. 732 00:33:33,941 --> 00:33:36,648 Tagad mēs ejam, lai vienkārši ir katrs uz priekšu un atpakaļ šādā veidā, 733 00:33:36,648 --> 00:33:38,620 jo man veida vajag daži scratch telpa. 734 00:33:38,620 --> 00:33:40,411 Tas ir gandrīz kā šos puiši ir uz galda, 735 00:33:40,411 --> 00:33:42,460 un man vajag dažas telpas , lai tos tālāk. 736 00:33:42,460 --> 00:33:44,170 Tāpēc es esmu gatavojas apvienoties jūs puiši, apskatot 737 00:33:44,170 --> 00:33:45,960 kreisajā pusē un labajā pusē. 738 00:33:45,960 --> 00:33:48,740 Un kurš acīmredzot ir pirmajā vietā, kreisi puse jeb labi pusi? 739 00:33:48,740 --> 00:33:52,710 Tik labi pusi, tāpēc pāriesim Luke vairāk šeit, lai Darren sākotnējā stāvoklī. 740 00:33:52,710 --> 00:33:57,640 Un tagad apvienot savu kreiso pusi, kas, Darren gatavojas pārcelties turpat. 741 00:33:57,640 --> 00:33:59,750 >> Tāpēc jūtas kā gandrīz burbulis veida efekts, 742 00:33:59,750 --> 00:34:02,482 bet mans galvenais algoritms, ļoti atšķirīgs šoreiz. 743 00:34:02,482 --> 00:34:04,815 Bet tagad ir, ja lietas iegūt mazliet kaitinošas, jo jums 744 00:34:04,815 --> 00:34:06,810 jāgriež atpakaļ garīgi kurienes es mitēties. 745 00:34:06,810 --> 00:34:09,893 Esmu tikko apvienoja sakārtotos pusītes, kas nozīmē, ka es esmu, kur manā algoritmu? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Man ir, lai sakārtotu labo pusi, vai ne? 748 00:34:13,770 --> 00:34:15,910 >> Ja jūs attīt, burtiski uz video, jūs 749 00:34:15,910 --> 00:34:18,339 redz, ka mēs saņēmām šo punkts Lūkas un Darren 750 00:34:18,339 --> 00:34:21,370 šķirošanas kreiso puse no kreisās puses. 751 00:34:21,370 --> 00:34:23,430 Tad mēs apvienojām tiem šķirotas pusītes, kas 752 00:34:23,430 --> 00:34:27,941 nozīmē, nākamais solis ir sava labo pusi kreisajā pusē. 753 00:34:27,941 --> 00:34:29,649 Labi, tāpēc pieņemsim izdarīt ātrāk. 754 00:34:29,649 --> 00:34:33,282 Nu labi, seši, es esmu gatavojas pieprasīt jūs tagad sakārtoti, nāc uz priekšu. 755 00:34:33,282 --> 00:34:33,990 Kāds ir tavs vārds? 756 00:34:33,990 --> 00:34:34,589 >> AUDITORIJA: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> SPEAKER: Adriano. 758 00:34:35,200 --> 00:34:36,010 Tagad Adriano ir sakārtots. 759 00:34:36,010 --> 00:34:36,450 Un kāds ir tavs vārds? 760 00:34:36,450 --> 00:34:37,080 >> AUDITORIJA: Alex. 761 00:34:37,080 --> 00:34:38,379 >> SPEAKER: tagad Alex ir sakārtots. 762 00:34:38,379 --> 00:34:40,750 Kreisās puse, labi pusi, kas ir pēdējais solis? 763 00:34:40,750 --> 00:34:41,250 Apvienoties. 764 00:34:41,250 --> 00:34:44,310 Diezgan niecīgs, tāpēc es esmu gatavojas apvienot sešās, 765 00:34:44,310 --> 00:34:46,930 spert soli atpakaļ, astoņi, veikt soli atpakaļ. 766 00:34:46,930 --> 00:34:49,530 Un tagad paziņojums tas ir noderīgs takeaway, ko 767 00:34:49,530 --> 00:34:53,930 tagad ir taisnība par kreisajā pusē saraksts, neatkarīgi no tā, kā mēs sākām? 768 00:34:53,930 --> 00:34:55,090 Tas ir sakārtots. 769 00:34:55,090 --> 00:34:57,750 >> Tagad tas nav sakārtoti liels shēma lietām, 770 00:34:57,750 --> 00:35:00,250 bet tas ir sakārtots patstāvīgi no otras puses. 771 00:35:00,250 --> 00:35:04,100 Tagad to solis es esmu par, ja es turpinu pārtīšana kā stāsts sākās? 772 00:35:04,100 --> 00:35:05,680 Tagad man ir, lai sakārtotu pareizo pusi. 773 00:35:05,680 --> 00:35:07,630 Tāpēc tagad mēs esam ceļu atpakaļ sākums stāsts, 774 00:35:07,630 --> 00:35:08,921 un pieņemsim darīt ātrāk. 775 00:35:08,921 --> 00:35:11,320 Tāpēc es esmu gatavojas, lai sakārtotu labo pusi no visu sarakstu. 776 00:35:11,320 --> 00:35:13,060 Kāds ir nākamais solis? 777 00:35:13,060 --> 00:35:15,840 Kārtot kreiso pusi labajā pusē. 778 00:35:15,840 --> 00:35:18,715 Kārtot kreiso pusi kreisā puse no labajā pusē. 779 00:35:18,715 --> 00:35:19,590 Un kāds ir tavs vārds? 780 00:35:19,590 --> 00:35:20,230 >> AUDITORIJA: Omar. 781 00:35:20,230 --> 00:35:21,970 >> SPEAKER: Omar, soli uz priekšu, darīts. 782 00:35:21,970 --> 00:35:22,860 Kreisā puse ir sakārtots. 783 00:35:22,860 --> 00:35:23,330 Un kāds ir tavs vārds? 784 00:35:23,330 --> 00:35:23,820 >> AUDITORIJA: Chris. 785 00:35:23,820 --> 00:35:25,620 >> SPEAKER: Chris, veikt soli uz priekšu, jūs tagad sakārtoti. 786 00:35:25,620 --> 00:35:27,010 Kas ir galvenais solis tagad? 787 00:35:27,010 --> 00:35:27,510 Apvienoties. 788 00:35:27,510 --> 00:35:30,509 Tik viens gatavojas apvienot savā vietā Šeit, ja jūs varētu veikt soli atpakaļ, 789 00:35:30,509 --> 00:35:32,930 un trīs gatavojas spert soli atpakaļ, apvienot. 790 00:35:32,930 --> 00:35:38,080 Tātad kreisā puse labajā pusē, tagad ir sakārtots. 791 00:35:38,080 --> 00:35:41,747 Atklāti sakot, šis algoritms jūtas kā mēs ir izšķērdēt veids vairāk laika nekā agrāk, 792 00:35:41,747 --> 00:35:44,830 bet, ja mēs to darījām reālā laikā, mēs ņemšu redzētu takeaways būs. 793 00:35:44,830 --> 00:35:47,970 Tagad šeit es esmu, vai ne puse labajā pusē, 794 00:35:47,970 --> 00:35:50,170 ļaujiet man iet uz priekšu un kārtot kreiso pusi. 795 00:35:50,170 --> 00:35:51,482 Solis uz priekšu, kāds ir tavs vārds? 796 00:35:51,482 --> 00:35:52,190 AUDITORIJA: Ramsey. 797 00:35:52,190 --> 00:35:53,210 SPEAKER: tagad Ramsey ir sakārtots. 798 00:35:53,210 --> 00:35:53,570 Kāds ir tavs vārds? 799 00:35:53,570 --> 00:35:54,200 >> AUDITORIJA: Marina. 800 00:35:54,200 --> 00:35:57,033 >> SPEAKER: tagad Marina ir sakārtots kā labi, ja jūs veikt vienu soli uz priekšu. 801 00:35:57,033 --> 00:36:00,690 Būtisks šeit tagad apvienot, es esmu gatavojas raut no maniem diviem sarakstiem, 802 00:36:00,690 --> 00:36:01,720 pa kreisi un pa labi. 803 00:36:01,720 --> 00:36:05,150 Five gatavojas nākt pirmkārt, un septiņi gatavojas nākt nākamais. 804 00:36:05,150 --> 00:36:06,410 Un atkal, tas ir apzināta. 805 00:36:06,410 --> 00:36:08,535 Fakts, ka viņi lieto soļi uz priekšu un atpakaļ 806 00:36:08,535 --> 00:36:12,997 ir domāts, lai pārstāvētu, ka mēs nevaram darīt šo algoritmu vietā tik viegli 807 00:36:12,997 --> 00:36:15,830 kā burbulis veida, un atlases veida, un ievietošanas kārtošanas, kur mēs vienkārši 808 00:36:15,830 --> 00:36:16,960 tur pārnešana cilvēkus. 809 00:36:16,960 --> 00:36:19,940 Es burtiski vajag veida no skrāpējumiem papīra, kurā 810 00:36:19,940 --> 00:36:21,827 likt šiem ļaudīm kamēr es to apvienošanu, 811 00:36:21,827 --> 00:36:23,410 un tad es varu nodot tos atpakaļ vietā. 812 00:36:23,410 --> 00:36:27,260 Un tas ir galvenais, jo es esmu, izmantojot jaunu resursu, telpu, ne tikai laiks. 813 00:36:27,260 --> 00:36:28,270 >> OK, tas ir pārsteidzošs. 814 00:36:28,270 --> 00:36:32,050 Atstājis pusi ir sakārtots, labi puse sakārtots, tagad, ka galvenais apvienojas solis. 815 00:36:32,050 --> 00:36:33,450 Kā es gatavojas apvienot šo? 816 00:36:33,450 --> 00:36:35,470 Tātad, ja jums sekot manu kreisā un labā roka, 817 00:36:35,470 --> 00:36:38,930 Es esmu gatavojas atzīmēt manu kreiso roku kreisajā pusē, mana labā roka 818 00:36:38,930 --> 00:36:42,680 īstajā pusē, un tagad man ir izlemt soli pa solim, kam apvienoties in. 819 00:36:42,680 --> 00:36:44,650 Kurš acīmredzot nāk vispirms? 820 00:36:44,650 --> 00:36:45,150 Numur viens. 821 00:36:45,150 --> 00:36:47,327 Tā nāk vairāk nekā šeit, šeit ir mūsu scratch pad. 822 00:36:47,327 --> 00:36:49,910 Tātad tagad numur viens, un paziņojums Ko es darīšu ar savu labo roku, 823 00:36:49,910 --> 00:36:54,152 Es esmu gatavojas pārvietot savu labo roku vienu soli pa norādīt numuru trīs, 824 00:36:54,152 --> 00:36:55,860 un tagad man ir, lai pats lēmums. 825 00:36:55,860 --> 00:36:58,387 Un faktiski stāvēt tiesības priekšpuse Lūkas šeit, ja jūs varētu, 826 00:36:58,387 --> 00:36:59,720 tāpēc, ka tas ir mūsu scratch pad. 827 00:36:59,720 --> 00:37:00,610 Tātad, kas būs tālāk? 828 00:37:00,610 --> 00:37:05,000 Mums ir Lūkas ar divām skaits vai Chris ar numuru trīs. 829 00:37:05,000 --> 00:37:07,460 Acīmredzot Luke, numurs divi, lai jūs nākt šeit. 830 00:37:07,460 --> 00:37:11,270 >> Bet mana kreisā roka tagad gatavojas palielina norādīt uz Darren, 831 00:37:11,270 --> 00:37:15,160 un šeit ir atslēga atņemt ar apvienošana, es esmu gatavojas, lai saglabātu darot to, 832 00:37:15,160 --> 00:37:17,340 protams, ja jūs veida no sekot loģikai. 833 00:37:17,340 --> 00:37:19,670 Bet manas rokas nekad gatavojas doties atpakaļ, 834 00:37:19,670 --> 00:37:23,861 kas nozīmē, ka es esmu tikai kādreiz pārvietojas uz kreisi ar manu apvienošanu procesu, 835 00:37:23,861 --> 00:37:26,360 un kas notiek, lai būtu galvenais Mūsu analīze tikai brīdi. 836 00:37:26,360 --> 00:37:27,859 >> Tāpēc tagad pieņemsim pabeigt šo augšu strauji. 837 00:37:27,859 --> 00:37:31,650 Tātad trīs nāk nākamais, Pēc tam četras nāk nākamais, 838 00:37:31,650 --> 00:37:38,750 un tagad pieci nāk nākamais, tad seši, un septiņi, un tad beidzot astoņi. 839 00:37:38,750 --> 00:37:42,960 Jūtas kā vislēnākā algoritmu vēl, bet ne tad, ja mēs faktiski 840 00:37:42,960 --> 00:37:45,510 darbojas vienā un tajā pašā veida par pulksteni ātrumu, tāpēc, lai 841 00:37:45,510 --> 00:37:48,106 runā, ar pašu atzīmējot pulksteni kā iepriekš. 842 00:37:48,106 --> 00:37:48,605 Kāpēc? 843 00:37:48,605 --> 00:37:51,100 Nu, Paņemsim apskatīt gala rezultātu. 844 00:37:51,100 --> 00:37:56,990 >> Atgriezīsimies nekā šeit, ļaujiet man uzvilkt demonstrāciju vizuāli 845 00:37:56,990 --> 00:37:59,030 par to, ko mēs tikko izdarījām. 846 00:37:59,030 --> 00:38:06,110 Attālināt šeit, par šo lapā šeit, stāstot Firefox 847 00:38:06,110 --> 00:38:08,200 ka mēs vēlamies rindā up šajā ailē, pieņemsim 848 00:38:08,200 --> 00:38:11,260 saka burbulis veida, ar kuru Tagad mēs esam labi pazīstami, 849 00:38:11,260 --> 00:38:14,130 atlases veida, kas ir vēl viens diezgan vienkārši viens, 850 00:38:14,130 --> 00:38:18,250 un tagad šodienas sapludināšanas kārtošanas, kas būs mūsu klimatiskajiem beidzas. 851 00:38:18,250 --> 00:38:21,530 Iemesls tas bija tik daudz ilgāk šeit ar cilvēkiem, un man mutiski ir, 852 00:38:21,530 --> 00:38:23,480 protams, es esmu izskaidrojot katru soli. 853 00:38:23,480 --> 00:38:26,920 Bet, ja jūs vienkārši izpildīt šo, daudz tāpat kā mēs to darījām burbulis kārtot un atlase 854 00:38:26,920 --> 00:38:30,890 kārtot ne tikai vizuāli, pulkstenis cik daudz efektīvāk 855 00:38:30,890 --> 00:38:33,330 šis piesaistīšana nodaļa un iekarošana 856 00:38:33,330 --> 00:38:39,150 var, ja piemēro datu kopu, kas ir nav pat izmēra astoņi, bet pat daudz, 857 00:38:39,150 --> 00:38:39,970 daudz lielāks. 858 00:38:39,970 --> 00:38:44,585 Es dodu jums apvienot kārtot, otram pusē ar šiem citiem algoritmiem. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Tas ir gatavojas saņemt sāpīga ātri, un beidzas 861 00:38:58,530 --> 00:39:00,890 nav īpaši klimatiskajiem, viņi vienkārši beigties sakārtoti. 862 00:39:00,890 --> 00:39:05,280 Bet galvenais atņemt ir tas, ka izskatās, cik daudz ātrāk apvienot kārtošanas 863 00:39:05,280 --> 00:39:08,110 bija, ja jūs domājat, ka es esmu tikko veida messing ar jums. 864 00:39:08,110 --> 00:39:13,100 Ja mēs to darām vienu pēdējo reizi, pieņemsim pārlādēt to, iesim atpakaļ 865 00:39:13,100 --> 00:39:14,960 un izvēlēties burbulis veida, un tikai sākas, 866 00:39:14,960 --> 00:39:17,330 pieņemsim izvēlēties ievietošanas kārtot, vienkārši labs pasākums. 867 00:39:17,330 --> 00:39:20,020 Un šoreiz atkal, pieņemsim izvēlēties sapludināšanas veida un pieņemsim 868 00:39:20,020 --> 00:39:21,595 faktiski vada šos blakus. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Un tas nav, patiesībā, parazīts. 871 00:39:26,930 --> 00:39:31,140 Ko es esmu efektīvi panākt ir Esmu sadalīta manu ievadi uz pusēm, atkal, 872 00:39:31,140 --> 00:39:32,240 un atkal, un atkal. 873 00:39:32,240 --> 00:39:35,590 Un tur ir tikai tik daudz reizes jūs varat sadalīt savu ieguldījumu daļās, pa kreisi 874 00:39:35,590 --> 00:39:36,240 un pa labi. 875 00:39:36,240 --> 00:39:39,425 Kas ir formula, ka mēs turpinām redzam kas apraksta sadalījumu pusē 876 00:39:39,425 --> 00:39:41,050 atkal, un atkal, un atkal, un atkal? 877 00:39:41,050 --> 00:39:41,890 >> AUDITORIJA: Pieteikties n. 878 00:39:41,890 --> 00:39:42,760 >> SPEAKER: Pieteikties n. 879 00:39:42,760 --> 00:39:46,300 Bet tad tur ir viena cita galvenais solis, šis algoritms nav log n soļi. 880 00:39:46,300 --> 00:39:48,992 Ja tas būtu tikai log n soļi, mēs būtu tādā pašā problēmu 881 00:39:48,992 --> 00:39:51,200 kā agrāk, kad mēs nevaram būt ka viss ir sakārtots. 882 00:39:51,200 --> 00:39:54,480 Jums ir minimāli apskatīt n elementiem lai pārliecinātos n elementi ir sakārtoti, 883 00:39:54,480 --> 00:39:55,950 citādi tas ir lēciens ticības. 884 00:39:55,950 --> 00:39:59,810 >> Tātad, tas ir minimāli log n soļi, taču ko par šo svarīgo soli apvienošanu 885 00:39:59,810 --> 00:40:04,370 kur es apvienojās manu kreiso pusi un pa labi pusi un gāja pāri skatuves? 886 00:40:04,370 --> 00:40:06,980 Cik soļi ir tas, ka apvienot? 887 00:40:06,980 --> 00:40:10,150 Tas ir n, bet man nebija ne tikai apvienot galīgo laiku. 888 00:40:10,150 --> 00:40:15,089 Par katru no šiem ligzdotu zvaniem, par katru Šo ligzdotu asimilē, es joprojām sakārtoti. 889 00:40:15,089 --> 00:40:18,380 Es apvienoti šie divi puiši, tad šie divi puiši, tad šie divi puiši, un tā tālāk. 890 00:40:18,380 --> 00:40:19,955 >> Tāpēc es tomēr apvienojas atkal, un atkal. 891 00:40:19,955 --> 00:40:20,580 Cik reizes? 892 00:40:20,580 --> 00:40:23,510 Tāpēc katru reizi, kad es sadalīts saraksts pusē, I did sapludināšanu. 893 00:40:23,510 --> 00:40:25,460 Sadaliet sarakstu pusē, do sapludināšanu. 894 00:40:25,460 --> 00:40:28,570 Tātad, ja dalot sarakstu var izdarīt log n reizes, 895 00:40:28,570 --> 00:40:33,880 un apvienošanās galu galā notiek n soļi, kādi varētu būt tagad augšējais 896 00:40:33,880 --> 00:40:37,000 robeža ritošās laiks mūsu algoritmu? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Un, protams, ka ir kas mēs esam sasnieguši šeit. 899 00:40:40,560 --> 00:40:44,650 Tā justies, ka jūs redzēt vizuāli, kad šie trīs lietas darbojas līdzās 900 00:40:44,650 --> 00:40:47,930 ir n kvadrātā pret n brusas pret n log n. 901 00:40:47,930 --> 00:40:51,010 Kas pašos mēs redzēsim, ne tikai šodien, bet arī nākotnē, 902 00:40:51,010 --> 00:40:52,760 ir daudz, daudz ātrāk. 903 00:40:52,760 --> 00:40:56,010 Aplausu kārta šiem puišiem, Es apbalvot tos ar stresa bumbiņām. 904 00:40:56,010 --> 00:41:00,260 Pieņemsim šodien atlikt šeit, un mēs redzēt jūs pirmdien. 905 00:41:00,260 --> 00:41:02,255