1 00:00:00,000 --> 00:00:11,270 2 00:00:11,270 --> 00:00:14,910 >> GARSIAKALBIS: Gerai, tai yra CS50. 3 00:00:14,910 --> 00:00:19,020 Tai savaitės trijų pabaigoje, ir, jei turite ne pasinaudojo jau, 4 00:00:19,020 --> 00:00:21,790 žinau, kad ten bus pietūs šį penktadienį, kaip įprasta, kur 5 00:00:21,790 --> 00:00:25,430 jūs galite mėgautis geras pokalbis ir maisto tuo Priešgaisrinės apsaugos ir ledo 6 00:00:25,430 --> 00:00:27,980 su kai kuriais iš CS50 s darbuotojai ir klasiokais. 7 00:00:27,980 --> 00:00:30,170 Eikite į šį URL čia. 8 00:00:30,170 --> 00:00:33,420 >> Dabar tu gali prisiminti, ar jūs greitai gali būti susipažinę su, 9 00:00:33,420 --> 00:00:35,970 šie dalykai čia, kurios išduodamos pabaigoje 10 00:00:35,970 --> 00:00:37,850 iš daugelio klasių semestrą. 11 00:00:37,850 --> 00:00:40,870 Vadinamasis egzamino mėlynos knygos, kurioje rašote savo atsakymus į egzaminus. 12 00:00:40,870 --> 00:00:44,240 Dabar aš turiu čia 26 tokių mėlynos knygos, apie kiekvieną iš jų 13 00:00:44,240 --> 00:00:47,580 parašyta pavadinimą, nuo A iki Z. Ir iš tikrųjų pavadinimai yra taip paprasta, 14 00:00:47,580 --> 00:00:50,490 per Z. Ir vienas iš po ranka šiandien tikslai 15 00:00:50,490 --> 00:00:53,910 bus toliau, ką mes prasidėjo pirmadienį, kuris yra ne 16 00:00:53,910 --> 00:00:57,830 tiek daug žiūri kodą, bet tikrai ieško idėjų ir problemų sprendimo. 17 00:00:57,830 --> 00:01:00,170 Vienas iš tikslų, ir pažadai šį kursą 18 00:01:00,170 --> 00:01:02,985 yra išmokyti jus mąstyti atsargiai, daugiau metodiškai, 19 00:01:02,985 --> 00:01:05,400 ir efektyviau spręsti problemas. 20 00:01:05,400 --> 00:01:09,526 Ir iš tiesų, mes galime padaryti, kad tikrai net neliesdamas kodo eilutę. 21 00:01:09,526 --> 00:01:12,150 Taigi turiu dramblių pora čia šiandien, oranžinė ir mėlyna, 22 00:01:12,150 --> 00:01:15,780 jei mes galime gauti vieną savanorį, gal iš toliau atgal nei įprasta. 23 00:01:15,780 --> 00:01:18,070 Kaip apie teisę ten, nagi žemyn. 24 00:01:18,070 --> 00:01:24,180 Kurių tikslas bus į padėti plius administruoti šį egzaminą čia. 25 00:01:24,180 --> 00:01:24,935 Koks tavo vardas? 26 00:01:24,935 --> 00:01:25,768 >> PUBLIKA: Mary Beth. 27 00:01:25,768 --> 00:01:27,560 GARSIAKALBIS: Mary Beth, nagi iki. 28 00:01:27,560 --> 00:01:29,560 Leiskite gauti mikrofoną čia jums. 29 00:01:29,560 --> 00:01:32,172 30 00:01:32,172 --> 00:01:32,880 Nice to meet you. 31 00:01:32,880 --> 00:01:34,005 >> PUBLIKA: Nice to meet you. 32 00:01:34,005 --> 00:01:36,790 GARSIAKALBIS: Gerai, kad turiu čia mėlyna knygos iki Z, 33 00:01:36,790 --> 00:01:41,680 ir aš ruošiuosi apsimesti, kad Aš turiu vieną iš mokinių, 34 00:01:41,680 --> 00:01:45,770 ir jie ateina šiek tiek atsitiktinai pasibaigus trijų valandų egzaminą bloko pabaigos, 35 00:01:45,770 --> 00:01:49,400 todėl jie baigiant kai pusiau atsitiktine tvarka, kaip šis. 36 00:01:49,400 --> 00:01:54,510 Dabar jūsų darbas tik akimirką vyksta į be-- iš tikrųjų tai yra, kaip jie gauti 37 00:01:54,510 --> 00:01:56,820 sužaidė pabaigoje klasė, greičiausiai. 38 00:01:56,820 --> 00:02:01,120 Jūsų darbas dabar bus gana tiesiog, rūšiuoti šiuos mėlynus knygas mus 39 00:02:01,120 --> 00:02:05,220 nuo A iki Z. 40 00:02:05,220 --> 00:02:08,400 >> PUBLIKA: O, tai yra ketina imtis amžinai. 41 00:02:08,400 --> 00:02:13,747 >> GARSIAKALBIS: Ir mes žiūrėti kaip jums tai padaryti, jokio spaudimo. 42 00:02:13,747 --> 00:02:15,330 PUBLIKA: Ne, jokio spaudimo arba nieko. 43 00:02:15,330 --> 00:02:19,230 44 00:02:19,230 --> 00:02:23,570 >> GARSIAKALBIS: Ir smagu, tegul supakuoti laikmatį. 45 00:02:23,570 --> 00:02:26,680 46 00:02:26,680 --> 00:02:28,700 >> PUBLIKA: Labai smagu, taip smagu. 47 00:02:28,700 --> 00:02:36,741 48 00:02:36,741 --> 00:02:38,574 >> GARSIAKALBIS: galiu turėti mikrofoną už jus. 49 00:02:38,574 --> 00:02:40,240 Gerai, mes ką tik dvigubai mūsų greitį. 50 00:02:40,240 --> 00:02:44,190 51 00:02:44,190 --> 00:02:49,060 Taigi tuo metu, leiskite man kelia tai, kas bus už Mary Beth klausimas 52 00:02:49,060 --> 00:02:51,540 yra tai, ką ji daro, kaip yra ji vyksta apie sprendžiant tai? 53 00:02:51,540 --> 00:02:54,040 Ir iš tiesų, jūs galite neturėti kada nors galvojote apie tai, kas 54 00:02:54,040 --> 00:02:57,440 taip paprasta, kaip kai jūs pasirenkate iki 26 knygų, pavyzdžiui, tai, 55 00:02:57,440 --> 00:02:59,350 kurie turi natūralių Užsakant į juos. 56 00:02:59,350 --> 00:03:01,335 Kas yra procesas kad jūs iš tikrųjų naudoti? 57 00:03:01,335 --> 00:03:03,770 Ar tai gana atsitiktinai tiesiog skinti pirmasis matote 58 00:03:03,770 --> 00:03:05,250 ir išleisti jį į savo vietą? 59 00:03:05,250 --> 00:03:09,680 Ar jūs pirmą kartą perkelti savo rankas aplink ieško tada ieško B? 60 00:03:09,680 --> 00:03:11,722 Ar jums pažvelgti išvaizdą pora juos šalia 61 00:03:11,722 --> 00:03:14,680 ir tiesiog pasakyti, palauk, tai nėra teisinga, ir tada apsikeitimo tvarką? 62 00:03:14,680 --> 00:03:16,960 Mes jau matė pirmadienį kad ten iš būdų 63 00:03:16,960 --> 00:03:22,140 , kurioje mes galime tai padaryti, ir Iš tiesų, kaip mes prie pabaigos čia 64 00:03:22,140 --> 00:03:26,360 Norėčiau atkreipti dėmesį, galbūt KĄ Mary Beth daro. 65 00:03:26,360 --> 00:03:30,040 Mes turime keletą poliai atrodo, didesnis vienas, trys smulkesni. 66 00:03:30,040 --> 00:03:33,790 67 00:03:33,790 --> 00:03:36,415 >> PUBLIKA: aš užsisakyti juos kai aš susirasti du laiškus 68 00:03:36,415 --> 00:03:39,540 kad aš žinau, yra kartu seka, Aš juos kartu, kad aš ne 69 00:03:39,540 --> 00:03:42,915 jaudintis išlaikyti trasa visą eilę knygų. 70 00:03:42,915 --> 00:03:45,706 Tai tiesiog, oi, yra, pirma, Aš gavau šį krūvą čia. 71 00:03:45,706 --> 00:03:47,580 GARSIAKALBIS: Taigi, beveik kaip Puzzle gabalus, 72 00:03:47,580 --> 00:03:49,860 turėti tinkamą pavidalą sutapti su tarpusavyje. 73 00:03:49,860 --> 00:03:51,026 PUBLIKA: Gana daug, taip. 74 00:03:51,026 --> 00:03:55,320 GARSIAKALBIS: Gerai, puikus. 75 00:03:55,320 --> 00:03:59,850 Ir dabar kiekvienos iš jų poliai yra turbūt rūšiuojami? 76 00:03:59,850 --> 00:04:00,990 >> PUBLIKA: Taip. 77 00:04:00,990 --> 00:04:09,900 >> GARSIAKALBIS: Gerai, per Z. Viskas teisė, sveikinimai, jūs tai padarė. 78 00:04:09,900 --> 00:04:11,461 Jūs turite savo pasirinkimą. 79 00:04:11,461 --> 00:04:11,960 Mėlyna? 80 00:04:11,960 --> 00:04:13,530 Gerai, ačiū už tai. 81 00:04:13,530 --> 00:04:16,679 Taigi Marija Bet nebuvo pasiūlyti ką jos požiūris buvo 82 00:04:16,679 --> 00:04:19,720 bet kas yra dar vienas būdas, kaip jus gali eiti apie rūšiavimą šiuos dalykus? 83 00:04:19,720 --> 00:04:21,130 Ką tu padarei? 84 00:04:21,130 --> 00:04:24,060 Įrašas įveikti būtų buvę vieną minutę ir 50 sekundžių, arba tiek, 85 00:04:24,060 --> 00:04:26,039 plius tie Aš pamiršau skaičiuoti. 86 00:04:26,039 --> 00:04:27,080 Ką tu padarei? 87 00:04:27,080 --> 00:04:27,579 Taip? 88 00:04:27,579 --> 00:04:28,735 PUBLIKA: Paimkite kamino. 89 00:04:28,735 --> 00:04:29,776 Pradėti nuo pradžių. 90 00:04:29,776 --> 00:04:32,284 Patikrinkite savo dokumentus. 91 00:04:32,284 --> 00:04:36,586 Ir jei viršutinė vienas yra didesnis nei, galbūt, jie yra, 92 00:04:36,586 --> 00:04:38,980 Apatinė yra didesnis, tada įjunkite juos. 93 00:04:38,980 --> 00:04:41,300 >> GARSIAKALBIS: Gerai, kad pradedant viršuje ir apačioje, 94 00:04:41,300 --> 00:04:43,716 ir tada dirbti savo kelią į vidų, kaip kad, keičiant juos? 95 00:04:43,716 --> 00:04:46,580 Gerai, kad šiek tiek panašus dvasia burbulas rūšiuoti, 96 00:04:46,580 --> 00:04:49,160 bet renkantis kraštutinumų ne gretimos poros. 97 00:04:49,160 --> 00:04:52,080 Bet tai trumpas yra tai, kad ten tikrai įvairių būdų krūva 98 00:04:52,080 --> 00:04:54,210 galėtume tai padaryti, ir atvirai, manau, kad jums rūšies 99 00:04:54,210 --> 00:04:55,700 priėmė keletą metodų, tiesa? 100 00:04:55,700 --> 00:05:00,567 Jūs padarė tarsi keturių rūšiuotų krūvos, ir tada efektyviai sujungta kartu. 101 00:05:00,567 --> 00:05:02,650 Ir tai, Manyti, kita metodas apskritai. 102 00:05:02,650 --> 00:05:06,950 Jūs ne gydyti jį kaip vieną didelį krūva, Jūs padalintas problemą į keturias keturračiai, 103 00:05:06,950 --> 00:05:09,820 jei norite, ir tada kažkaip susijungė juos pabaigoje. 104 00:05:09,820 --> 00:05:13,410 >> Taigi aptarkime, galiausiai, kaip kitaip mes galime tai padaryti. 105 00:05:13,410 --> 00:05:15,860 Mes oficialiai nuomonei, burbuliukų rūšiavimo paskutinį kartą, 106 00:05:15,860 --> 00:05:18,780 ir burbulas tarsi priminti buvo algoritmas, kad mes ryškinamos 107 00:05:18,780 --> 00:05:22,640 su aštuonių Klasiokų čia, atrodytų, atsitiktinai rūšiuojami ne pirmas. 108 00:05:22,640 --> 00:05:26,110 Ir tada mes nusprendėme poromis, jei du elementai yra iš tam, 109 00:05:26,110 --> 00:05:26,950 tiesiog sukeisti juos. 110 00:05:26,950 --> 00:05:28,930 Taigi keturių ir dviejų, yra akivaizdžiai neveikia, 111 00:05:28,930 --> 00:05:31,080 Taigi tie du klasiokai susikeitė pozicijomis. 112 00:05:31,080 --> 00:05:35,390 Ir tada mes kartojamas keturis ir šešis, aštuonių tada šešių ir, kiekvienos iteracijos, 113 00:05:35,390 --> 00:05:36,980 juda į dešinę. 114 00:05:36,980 --> 00:05:42,590 >> Taigi suteiktas aštuonių žmonių, kiek Porinis palyginimai aš padariau vaikštant nuo 115 00:05:42,590 --> 00:05:45,220 iš kairės į dešinę per vieną tokį iteracijos? 116 00:05:45,220 --> 00:05:48,410 Kiek palyginimai? 117 00:05:48,410 --> 00:05:49,197 Septyni, tiesa? 118 00:05:49,197 --> 00:05:51,405 Nes jei ten aštuonis žmonės, bet jūs turite porą 119 00:05:51,405 --> 00:05:53,880 juos, ir jūs nuolat juda viena apynių į dešinę, 120 00:05:53,880 --> 00:05:56,060 jūs nesiruošia turėti aštuonis palyginimai, nes tu negali palyginti 121 00:05:56,060 --> 00:05:59,226 prieš save elementas, ar tai būtų tiesiog beprasmiška, todėl jūs turite septynias. 122 00:05:59,226 --> 00:06:01,290 Arba apskritai, jei mes turime n žmonių, mes 123 00:06:01,290 --> 00:06:04,300 padaryti n atėmus 1 palyginimus su burbulo rūšiuoti. 124 00:06:04,300 --> 00:06:08,150 >> Taigi aptarkime dabar kaip geras ar blogai burbulas tarsi iš tikrųjų buvo, ir bandykite 125 00:06:08,150 --> 00:06:13,570 suteikti sau žodyną su kuri kritikos algoritmų, pavyzdžiui, tai, 126 00:06:13,570 --> 00:06:14,430 ir netrukus mūsų. 127 00:06:14,430 --> 00:06:16,970 Taigi pirmąjį perdavimą per burbulas rūšiuoti, pirmą kartą 128 00:06:16,970 --> 00:06:20,909 Ėjau iš kairės į dešinę visoje etapas, paėmė mane n minuso 1 palyginimų. 129 00:06:20,909 --> 00:06:22,950 Ir tai bus mano matavimo vienetas, tiesa? 130 00:06:22,950 --> 00:06:26,170 Buvau rūšies kalbėti ir pasivaikščioti, šiek tiek greitai, kiek lėtas, 131 00:06:26,170 --> 00:06:29,300 taip skaičiuoti mano sekundžių skaičių nėra labai svarbi, 132 00:06:29,300 --> 00:06:32,260 bet skaičiuodamas skaičių operacijos, kad aš pirmadienį, 133 00:06:32,260 --> 00:06:35,900 Lyginant du žmones, kad jaučiasi kaip gražus matavimo vienetas. 134 00:06:35,900 --> 00:06:40,980 >> Taigi n atėmus 1 žingsnius pirmą kartą, bet tada tai, kas atsitiko po to? 135 00:06:40,980 --> 00:06:46,610 Kas vienas aukštyn kojom vieno perdavimo per kitaip nerūšiuotų sąrašą? 136 00:06:46,610 --> 00:06:49,840 Ką galite papasakoti apie elemento kas buvo viskas ten taip? 137 00:06:49,840 --> 00:06:51,300 Taip? 138 00:06:51,300 --> 00:06:52,870 Tai buvo didžiausias elementas, tiesa? 139 00:06:52,870 --> 00:06:55,710 Taškų aštuonių, nors ji pradėjo čia, kiekvieną kartą, kai aš 140 00:06:55,710 --> 00:06:57,860 palyginti ją su kaimynas, ji nuolat 141 00:06:57,860 --> 00:07:00,480 burbuliuoja iki dešinę pusėje sąrašo. 142 00:07:00,480 --> 00:07:02,710 Ir iš tiesų, tai kur algoritmas gauna savo pavadinimą. 143 00:07:02,710 --> 00:07:07,630 >> Dabar ta logika, kiek palyginimai reikia man padaryti antrą kartą 144 00:07:07,630 --> 00:07:09,800 Aš padaryti, kad perdavimą iš kairės į dešinę? 145 00:07:09,800 --> 00:07:10,730 n atėmus 2, tiesa? 146 00:07:10,730 --> 00:07:14,297 Tai tiesiog eikvoti savo laiką, jei I išlaikyti lyginant aštuonių prieš ką nors 147 00:07:14,297 --> 00:07:16,630 kitur, nes mes jau žinome, ji buvo reikiamoje vietoje. 148 00:07:16,630 --> 00:07:19,760 Štai iš tiek optimizavimas, todėl šalia perdavimas 149 00:07:19,760 --> 00:07:23,899 bus plius n atėmus du žingsniai, kur n yra žmonių skaičius. 150 00:07:23,899 --> 00:07:26,940 Dabar galite rūšies ekstrapoliuoti, net jei nesate kompiuterių mokslininkas, 151 00:07:26,940 --> 00:07:27,680 kaip tai baigiasi. 152 00:07:27,680 --> 00:07:31,259 Šio algoritmo pabaigoje, matyt jūs turite tik vieną palyginimas kairėje. 153 00:07:31,259 --> 00:07:33,800 Turite rūšies nustatyti pradžioje sąrašo atveju dviejų 154 00:07:33,800 --> 00:07:36,540 ir vienas yra iš tam ir turėtų būti vienas ir du, 155 00:07:36,540 --> 00:07:40,330 todėl tai iki dugno iš ne plius 1 galutinis palyginimas. 156 00:07:40,330 --> 00:07:44,500 >> Dabar dot, dot, dot rūšies bangų tai rankos, o kai kuriose sultingesnis informacijos 157 00:07:44,500 --> 00:07:46,452 bet tegul tiesiog eiti į priekį ir supaprastinti. 158 00:07:46,452 --> 00:07:48,660 Jei prisimenate iš aukštos mokykla, tiesą sakant, iš jūsų daug 159 00:07:48,660 --> 00:07:50,340 turėjo matematikos knygas, kurios turėjo mažai apgauti lapas 160 00:07:50,340 --> 00:07:52,550 ant priekinio dangčio ar galinį dangtelį, kad jums parodė, 161 00:07:52,550 --> 00:07:56,400 kas serijos summations kaip tai galiausiai pridėti iki. 162 00:07:56,400 --> 00:07:59,600 Bendroje atveju, jei turite kintamasis kaip n, o iš tikrųjų tai viena, 163 00:07:59,600 --> 00:08:01,634 jei jūs žiūrite į savo senosios mokyklos matematikos knyga, 164 00:08:01,634 --> 00:08:04,050 jūs pamatysite, kad tai iš tiesų išauga iki šios sumos čia 165 00:08:04,050 --> 00:08:07,970 n kartų n atėmus 1 visi padalinti iš 2. 166 00:08:07,970 --> 00:08:11,172 Taigi dabar leiskite man tiesiog nustatyti tai tiesa, kad dėl tikėjimo šuolis, 167 00:08:11,172 --> 00:08:12,880 kad tai, ką šis apibendrina iki, ir mes galime 168 00:08:12,880 --> 00:08:14,341 įrodyti, kad bendresniu atveju. 169 00:08:14,341 --> 00:08:15,590 Bet dabar tegul išplėsti this out. 170 00:08:15,590 --> 00:08:19,920 Taigi leiskite padauginti, ir todėl, kad tai n kvadratu, atėmus n visi padalinti iš 2. 171 00:08:19,920 --> 00:08:23,200 Tai tikrai n kvadratu, padalinti iš 2, atėmus n daugiau kaip 2 172 00:08:23,200 --> 00:08:25,010 kad viskas gražu ir įdomu. 173 00:08:25,010 --> 00:08:27,060 Bet kas atsitinka, jei mes dabar plug-in vertė? 174 00:08:27,060 --> 00:08:29,724 Tarkime, aš neturėjo aštuoni žmonės, bet pasakyti mln. 175 00:08:29,724 --> 00:08:31,890 Ir tik todėl, kad milijonų tai gana didelis skaičius, 176 00:08:31,890 --> 00:08:34,039 tegul įjunkite, kad ir pamatyti, kas atsitiks. 177 00:08:34,039 --> 00:08:39,039 Taigi, jei aš prijunkite milijonų į tą formulę Aš ruošiuosi gauti milijonų kvadrato, 178 00:08:39,039 --> 00:08:42,868 padalinti iš 2, atėmus milijonų eurų, padalintas iš 2. 179 00:08:42,868 --> 00:08:44,159 Dabar kas, kad vyksta prilygti? 180 00:08:44,159 --> 00:08:47,354 Taigi 500 mlrd minus 500,000. 181 00:08:47,354 --> 00:08:49,270 Ir jei aš iš tikrųjų kad matematikos, ši priemonė 182 00:08:49,270 --> 00:08:53,920 kad rūšiavimas milijono žmonės su burbulas rūšiuoti 183 00:08:53,920 --> 00:09:01,800 gali imtis man 499.999.500.000 žingsniai ar palyginimai, galų gale, 184 00:09:01,800 --> 00:09:02,900 mes tiesiog ekstrapoliuoti. 185 00:09:02,900 --> 00:09:06,860 >> Tai jaučiasi gana lėtas, bet atvirai matavimo vieną konkretų indėlį 186 00:09:06,860 --> 00:09:09,160 kaip šis, yra ne visi, kad spėjimas. 187 00:09:09,160 --> 00:09:14,050 Bet iš tikrųjų jis rodo, kad n gauna didesnį ir didesnį, šį algoritmą 188 00:09:14,050 --> 00:09:16,280 rūšies jaučiasi blogiau ir Dar blogiau, ar jūs tikrai 189 00:09:16,280 --> 00:09:20,450 pradėti jausti, kad skausmas kėlimas laipsniu, kad n kvadratu, 190 00:09:20,450 --> 00:09:21,770 kuris išauga iki gana greitai. 191 00:09:21,770 --> 00:09:25,340 Ir tai detalė nėra neteko žmonių, iš tikrųjų 192 00:09:25,340 --> 00:09:29,640 Prieš keletą metų tikra senatorius, kuris buvo kampanijos, susėdo pokalbiui 193 00:09:29,640 --> 00:09:32,180 su "Google" Eric Schmidt direktorius tuo metu, 194 00:09:32,180 --> 00:09:36,380 ir ginčijo su klausimu daug, kaip mes ištirti šiandien. 195 00:09:36,380 --> 00:09:38,468 Paimkime išvaizdą. 196 00:09:38,468 --> 00:09:45,280 >> [VIDEO PLAYBACK] 197 00:09:45,280 --> 00:09:48,560 >> -Senator, Jūs čia "Google", ir man patinka 198 00:09:48,560 --> 00:09:53,382 galvoti apie pirmininkavimo kaip darbo interviu. 199 00:09:53,382 --> 00:09:56,434 Dabar, tai sunku gauti darbas, kaip prezidentas, 200 00:09:56,434 --> 00:09:58,100 ir jūs ketinate per sąstingis dabar. 201 00:09:58,100 --> 00:10:01,860 Taip pat sunku gauti darbą "Google". 202 00:10:01,860 --> 00:10:05,490 Mes turime klausimų, ir mes paklausti mūsų kandidatams klausimus, 203 00:10:05,490 --> 00:10:09,770 ir tai vienas iš Larry Schwimmer. 204 00:10:09,770 --> 00:10:14,760 What-- jūs manote aš juokauji, tai čia. 205 00:10:14,760 --> 00:10:17,930 Kas yra efektyviausias būdas rūšiuoti milijoną 32 bitų sveikųjų skaičių? 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 >> -Aš Atsiprašome, maybe-- 209 00:10:25,200 --> 00:10:27,400 >> Ne, ne, ne. 210 00:10:27,400 --> 00:10:30,700 Manau, kad burbulas rūšiuoti Būtų neteisinga būdas eiti. 211 00:10:30,700 --> 00:10:34,165 212 00:10:34,165 --> 00:10:38,180 >> Nagi, kas jį šį pasakyta? 213 00:10:38,180 --> 00:10:40,590 Nemačiau kompiuterį mokslas savo fone. 214 00:10:40,590 --> 00:10:42,130 >> -Mes Gavo mūsų šnipai ten. 215 00:10:42,130 --> 00:10:44,930 216 00:10:44,930 --> 00:10:48,444 >> Ok, tegul paklausti skiriasi interviu klausimą. 217 00:10:48,444 --> 00:10:49,300 >> [END VIDEO PLAYBACK] 218 00:10:49,300 --> 00:10:52,290 >> GARSIAKALBIS: Taigi kalbame apie konkretūs skaičiai, nors, 219 00:10:52,290 --> 00:10:53,890 nesiruošia būti visi, kad naudinga. 220 00:10:53,890 --> 00:10:56,810 Tai nėra gyvenimo pamoka, kad burbulas Rūšiuoti, atsižvelgiant milijono įėjimai, 221 00:10:56,810 --> 00:10:58,590 gali užtrukti net 500 mlrd veiksmus. 222 00:10:58,590 --> 00:11:01,120 Jūs tikrai negali apibendrinti per efektyviai nuo 223 00:11:01,120 --> 00:11:03,560 ir padaryti gerus dizaino sprendimus, rašant programas. 224 00:11:03,560 --> 00:11:07,070 Taigi susitelkime nors apie tai, kaip mes galime supaprastinti šį rezultatą. 225 00:11:07,070 --> 00:11:11,780 >> Taigi aš paryškinamas geltonai čia n rezultatas kvadratėliais padalintas iš 2, 226 00:11:11,780 --> 00:11:14,330 taip mln kvadrato padalinti iš 2, tada 227 00:11:14,330 --> 00:11:16,710 Aš pabrėžė, kas Galutinis atsakymas buvo 228 00:11:16,710 --> 00:11:20,180 kai mes atimama išjungta n padalinti iš 2. 229 00:11:20,180 --> 00:11:24,850 Ir teiginys aš ruošiuosi padaryti dabar yra, kas gi cares, jei jūs atimkite išjungtas 230 00:11:24,850 --> 00:11:30,060 tiek metų n virš 2, kai pirmą kartą dalis šios formulės yra daug didesnis? 231 00:11:30,060 --> 00:11:33,910 Ji dominuoja kitos terminas n kvadratėliais padalintas iš 2 232 00:11:33,910 --> 00:11:37,510 Yra tiek daug daugiau, be abejo, kaip n gauna didelis kaip milijonas, 233 00:11:37,510 --> 00:11:41,450 tai ten tikrai didelis skirtumas ne dienos pabaigos nuo 500 mlrd 234 00:11:41,450 --> 00:11:45,730 ir 499.999.500.000? 235 00:11:45,730 --> 00:11:46,349 Ne tikrai. 236 00:11:46,349 --> 00:11:48,640 Ir taip, ką mes ketiname daryti, kaip kompiuterių specialistai yra 237 00:11:48,640 --> 00:11:53,270 ignoruoti tuos mažesnius užsakymo sąlygų ir imtis ko nors panašaus į tai ir tikrai 238 00:11:53,270 --> 00:11:56,050 tiesiog supaprastinti ją terminas, kuris ketina reikšmės. 239 00:11:56,050 --> 00:12:00,315 Didesnės mūsų duomenų rinkiniai gauti, didesnis mūsų duomenų bazės gauti, tuo daugiau tinklalapius 240 00:12:00,315 --> 00:12:02,690 mes turime ieškoti, daugiau draugai turite "Facebook". 241 00:12:02,690 --> 00:12:07,340 >> Kaip n gauna didesni, mes tikrai ketina rūpintis didžiausia 242 00:12:07,340 --> 00:12:11,560 terminas tokio analizės mūsų algoritmai efektyvumą. 243 00:12:11,560 --> 00:12:16,230 Ir aš ruošiuosi pasakyti, žinote, ką, burbulas tarsi yra ant didžiojo O tam, 244 00:12:16,230 --> 00:12:18,060 nuo n, kad kvadrato. 245 00:12:18,060 --> 00:12:20,090 Tai nėra tiksliai n kvadrato, kaip mes matėme, 246 00:12:20,090 --> 00:12:22,060 bet kas tikrai rūpi apie tuos mažesnius sąlygomis, 247 00:12:22,060 --> 00:12:24,390 ir tiesą sakant, kas iš tikrųjų cares, jei mes padalinti iš 2? 248 00:12:24,390 --> 00:12:25,870 Tai tiesiog pastovus veiksnys. 249 00:12:25,870 --> 00:12:29,480 Ir yra 500 milijardų, palyginti su 250 milijardų tikrai, kad didelis spręsti? 250 00:12:29,480 --> 00:12:32,190 Galėčiau tik laukti vienerius metus, tegul mano nešiojamas pažodžiui 251 00:12:32,190 --> 00:12:34,810 gauti du kartus taip greitai, aparatūros, ir kad skirtumas tarsi 252 00:12:34,810 --> 00:12:36,650 tiesiog nueina natūraliai per tam tikrą laiką. 253 00:12:36,650 --> 00:12:39,300 >> Kas mums rūpi tai išraiška, dalis 254 00:12:39,300 --> 00:12:42,489 išraiškos, kad ketina skirtis kaip mūsų indėlis tampa didesni ir didesni. 255 00:12:42,489 --> 00:12:45,280 Ir iš tiesų, realiame pasaulyje, tai, kas vyksta vis 256 00:12:45,280 --> 00:12:48,330 yra mūsų problemų įėjimai ir algoritmai vis didesni. 257 00:12:48,330 --> 00:12:53,470 Taigi didelis O bus notacija, asimptotinio notacija, kad mes tiesiog 258 00:12:53,470 --> 00:12:57,160 naudoti kaip kompiuterių mokslininkai apibūdinti veiklai arba važiavimo laikas, 259 00:12:57,160 --> 00:12:58,130 algoritmą. 260 00:12:58,130 --> 00:13:00,800 Taigi, kad mes galime palyginti algoritmus skirtinguose kompiuteriuose raštu 261 00:13:00,800 --> 00:13:04,170 skirtingi žmonės, naudojant kai iš esmės panašus metrika 262 00:13:04,170 --> 00:13:07,557 kaip palyginimų skaičius esate priėmimo, o gal apie sandorius skaičių 263 00:13:07,557 --> 00:13:08,140 jūs darote. 264 00:13:08,140 --> 00:13:11,910 >> Ką mes neketiname skaičius yra laiko suma 265 00:13:11,910 --> 00:13:13,981 kad eina į laikrodį ant sienos: paprastai. 266 00:13:13,981 --> 00:13:16,230 Ką mes neketiname jaudintis apie tai, kiek atminties 267 00:13:16,230 --> 00:13:17,820 Jūs naudojate šiandien mažiau, nors tai 268 00:13:17,820 --> 00:13:19,370 kitas šaltinis, mes galime išmatuoti. 269 00:13:19,370 --> 00:13:23,610 Mes ketiname bandyti grįsti savo analizę teisingomis pagrindines operacijas, tie, 270 00:13:23,610 --> 00:13:25,930 tiesą sakant, kad jūs galite pamatyti dauguma vizualiai. 271 00:13:25,930 --> 00:13:30,700 Taigi su kažką panašaus į didįjį O n kvadrato, aš teigti, kad O n kvadratu 272 00:13:30,700 --> 00:13:35,820 yra viršutinė riba nuo vadinamųjų važiavimo laikas burbuliukų rūšiuoti. 273 00:13:35,820 --> 00:13:38,820 Kitaip tariant, jei jūs norėjo teigti, kad ten 274 00:13:38,820 --> 00:13:41,370 ši viršutinė riba, kiek veiksmus algoritmas gali užtrukti, 275 00:13:41,370 --> 00:13:46,240 jis ketina būti didelis O n kvadrato šiuo atveju viršutinė riba. 276 00:13:46,240 --> 00:13:49,710 >> Ką daryti, jei aš vietoj keisti istorija būtų ne apie burbulo rūšiuoti, 277 00:13:49,710 --> 00:13:50,910 bet apie tai viršutinė riba. 278 00:13:50,910 --> 00:13:54,030 Ar manote, kad algoritmas kad mes pažvelgė jau 279 00:13:54,030 --> 00:13:59,530 kurio viršutinė riba, maksimalus išmatuoti laiko ar operacijų, 280 00:13:59,530 --> 00:14:04,300 būtų teigti, kad būti ribojama iš n, tiesinė funkcija, 281 00:14:04,300 --> 00:14:07,260 ne kvadratinis vienas, kad yra lenkta? 282 00:14:07,260 --> 00:14:10,780 Kas algoritmas, visada užtrunka ne daugiau 283 00:14:10,780 --> 00:14:12,860 nei kaip n žingsnių, arba 2n žingsniai, ar 3n žingsniai? 284 00:14:12,860 --> 00:14:13,360 Taip? 285 00:14:13,360 --> 00:14:15,030 >> PUBLIKA: Ieškoti Daugiausia sąraše? 286 00:14:15,030 --> 00:14:16,930 >> GARSIAKALBIS: Puikiai, rasti Didžiausias skaičius sąraše. 287 00:14:16,930 --> 00:14:18,940 Jei aš duotas sąrašą žmonės pavyzdžiui, 288 00:14:18,940 --> 00:14:21,440 kiekvienas laikiusį numerį, kas yra didžiausias skaičius 289 00:14:21,440 --> 00:14:23,770 žingsnių ji turėtų imtis man, pagrįstai protingas asmuo, 290 00:14:23,770 --> 00:14:27,530 rasti didžiausią asmenį į tą sąrašą? 291 00:14:27,530 --> 00:14:28,100 n, tiesa? 292 00:14:28,100 --> 00:14:31,320 Nes blogiausiu atveju, kur gali didžiausia vertė būtų? 293 00:14:31,320 --> 00:14:32,700 Teisė, visi pabaigoje būdas. 294 00:14:32,700 --> 00:14:34,575 Taigi, blogiausiu atveju viršutinė riba, galiu 295 00:14:34,575 --> 00:14:36,450 turi pereiti visą kelią čia ir bus kaip, 296 00:14:36,450 --> 00:14:39,170 Oh, štai numeris aštuonių, ar kokia ta vertė. 297 00:14:39,170 --> 00:14:41,330 Dabar ji tiesiog kvaila jei aš nuolat vyksta, tiesa? 298 00:14:41,330 --> 00:14:43,840 Ieškote daugiau ir daugiau elementų jei paskutinis iš jų yra ten? 299 00:14:43,840 --> 00:14:45,340 Taigi tikrai, n yra viršutinė riba. 300 00:14:45,340 --> 00:14:47,420 Man nereikia imtis daugiau veiksmų, nei nurodyta. 301 00:14:47,420 --> 00:14:51,580 >> Taigi ką daryti, jei vietoj aš pasiūliau, kad yra algoritmai šiame pasaulyje, kad 302 00:14:51,580 --> 00:14:57,750 turėti darbo laiką, kad yra riboja didelis O log n, prisijunkite n? 303 00:14:57,750 --> 00:15:00,390 Kur mes matėme tai anksčiau? 304 00:15:00,390 --> 00:15:00,890 Taip? 305 00:15:00,890 --> 00:15:03,309 >> PUBLIKA: telefonų knygoje problemos? 306 00:15:03,309 --> 00:15:04,850 GARSIAKALBIS: Kaip telefonų knygos problema. 307 00:15:04,850 --> 00:15:07,754 Kas buvo, kaip priemonė kiek laiko ar kiek ašaros IT 308 00:15:07,754 --> 00:15:10,170 paėmė mane rasti ką nors panašaus Mike Smith telefonų knygoje? 309 00:15:10,170 --> 00:15:13,212 Mes teigė, kad buvo log n, o net jei nepažįstamas ar jis tai 310 00:15:13,212 --> 00:15:15,170 tiek miglotas, ką pagrindu arba eksponentė buvo 311 00:15:15,170 --> 00:15:17,650 Tiesiog neužmirškite, kad log n paprastai reiškia procesą, 312 00:15:17,650 --> 00:15:20,790 šiuo atveju, dalijant kažkas per pusę vėl, ir vėl, 313 00:15:20,790 --> 00:15:25,790 ir vėl, ir vėl, taip, kad juo gauna vis maža, kaip jums tai padaryti. 314 00:15:25,790 --> 00:15:28,470 >> Taigi prisijunkite n reiškia, tikrai, į telefonų knygą, pavyzdžiui, 315 00:15:28,470 --> 00:15:32,662 dvejetainis paieškos teorija, kai mes turėjo virtualias duris ant lentos, 316 00:15:32,662 --> 00:15:34,370 arba kai Seanas buvo ieškoti kažko. 317 00:15:34,370 --> 00:15:37,374 Jei jis naudojamas dvejetainis paiešką, prisijunkite n būtų viršutinė riba, kiek 318 00:15:37,374 --> 00:15:38,040 laikas, kad mano. 319 00:15:38,040 --> 00:15:44,027 Bet tie algoritmai, kad vykdavo log n prielaida kas svarbiausią detalę? 320 00:15:44,027 --> 00:15:45,360 Tai sąrašas buvo rūšiuojamos, tiesa? 321 00:15:45,360 --> 00:15:47,789 Jūsų algoritmas yra negerai, jei jūsų indėlis nėra rūšiuojamos, 322 00:15:47,789 --> 00:15:49,830 ir dar jūs naudojate kažkas panašaus dvejetainėje paiešką 323 00:15:49,830 --> 00:15:51,704 nes jums gali šokinėti tiesiai virš elemento 324 00:15:51,704 --> 00:15:53,600 nesuvokdami, kad tai iš tikrųjų yra. 325 00:15:53,600 --> 00:15:55,600 >> Dabar kas gali tai reiškia, didelis O vieną? 326 00:15:55,600 --> 00:15:59,117 Tai nereiškia, kad savo algoritmą trunka vienas ir tik vienas žingsnis, 327 00:15:59,117 --> 00:16:01,200 tai tiesiog reiškia, kad ji trunka pastovus pakopų skaičius. 328 00:16:01,200 --> 00:16:04,060 Gal tai 1, o gal tai 10, gal tai 1000, 329 00:16:04,060 --> 00:16:07,750 bet tai nepriklauso nuo Problemos dydis. 330 00:16:07,750 --> 00:16:10,850 Nesvarbu, kaip didelis n, pastovus laikas algoritmas 331 00:16:10,850 --> 00:16:12,747 visada užima tiek pat žingsnių. 332 00:16:12,747 --> 00:16:15,080 Taigi, kas gali būti algoritmas mes kalbėjome apie ar tiesiog 333 00:16:15,080 --> 00:16:20,418 intuityviai, kad ateis pas jus, kad visada veikia vadinamąjį nuolat laiku? 334 00:16:20,418 --> 00:16:20,918 Taip? 335 00:16:20,918 --> 00:16:22,001 >> PUBLIKA: Įlašinkite du numerius. 336 00:16:22,001 --> 00:16:25,320 GARSIAKALBIS: Pridėti du numerius, 2 plius 2 lygi 4, padaryta. 337 00:16:25,320 --> 00:16:27,227 Taigi, kad galėtų dirbti, kas dar? 338 00:16:27,227 --> 00:16:28,560 Kaip apie daugiau realiame pasaulyje, taip? 339 00:16:28,560 --> 00:16:30,686 >> PUBLIKA: Ieškoti Pirmas dalykas, sąraše. 340 00:16:30,686 --> 00:16:32,810 GARSIAKALBIS: Ieškoti pirmas elementas sąraše, tikrai. 341 00:16:32,810 --> 00:16:34,540 Mes iš tikrųjų buvo kalbama apie masyvų jau 342 00:16:34,540 --> 00:16:36,540 kaip jums ne Pirmasis elementas masyve, 343 00:16:36,540 --> 00:16:40,465 nesvarbu, kiek laiko masyvas C kodą? 344 00:16:40,465 --> 00:16:43,090 Jūs tiesiog naudoti kaip kronšteino nulis notacija, bam jūs ten. 345 00:16:43,090 --> 00:16:46,120 Ir iš tiesų matricos, kaip panaikinti, parama kažkas visuotinai žinomas 346 00:16:46,120 --> 00:16:49,240 kaip laisvą prieigą, laisvosios kreipties atminties, nes jūs galite tiesiog 347 00:16:49,240 --> 00:16:50,284 peršokti į vieną vietą. 348 00:16:50,284 --> 00:16:52,700 Mes galime tai padaryti dar paprasčiau mes galime atsukti iki nulio savaitę 349 00:16:52,700 --> 00:16:53,900 kai mes padarėme nulio. 350 00:16:53,900 --> 00:16:59,707 Kiek laiko užtruks pasakyti blokas Scratch vykdyti? 351 00:16:59,707 --> 00:17:00,790 Tiesiog pastovus laikas, tiesa? 352 00:17:00,790 --> 00:17:03,960 Pasakyk ką nors, tarkim, kažkas, nesvarbu 353 00:17:03,960 --> 00:17:07,359 Kaip didelis Įbrėžimai pasaulis, tai visada ketina imtis tą patį laiko 354 00:17:07,359 --> 00:17:08,490 tiesiog pasakyti kažką. 355 00:17:08,490 --> 00:17:11,089 >> Štai pastovus laikas, bet kas Pasitaiko? 356 00:17:11,089 --> 00:17:13,030 Jei tai buvo viršutinis ribos, ką daryti, jei norime 357 00:17:13,030 --> 00:17:17,089 apibūdinti mažesnes ribas mūsų algoritmų veikimo laikas? 358 00:17:17,089 --> 00:17:19,852 Beveik geriausias atvejis potencialiai jei norite, 359 00:17:19,852 --> 00:17:23,060 nors šie terminai gali būti taikomas geriausias dėklai, blogiausiu atveju, vidutinis atvejai daugiau 360 00:17:23,060 --> 00:17:26,359 Paprastai, bet tegul tik sutelkti mažesnes ribas apskritai. 361 00:17:26,359 --> 00:17:31,920 Kas algoritmas, kuris turi Apatinė riba n žingsnių, 362 00:17:31,920 --> 00:17:33,350 ar 2n žingsniai, ar 3n žingsniai? 363 00:17:33,350 --> 00:17:36,241 Kai n žingsnių veiksnys, tai jo apatinė. 364 00:17:36,241 --> 00:17:36,740 Taip? 365 00:17:36,740 --> 00:17:37,910 >> PUBLIKA: burbulas rūšiuoti? 366 00:17:37,910 --> 00:17:41,610 >> GARSIAKALBIS: burbulas tarsi užima Jūs minimaliai n žingsnių, kodėl? 367 00:17:41,610 --> 00:17:42,279 Kodėl taip yra? 368 00:17:42,279 --> 00:17:45,320 Kodėl reikėtų, kad pradžia ateiti pas tave intuityviai, net jei ji ne tik 369 00:17:45,320 --> 00:17:46,530 Dar neužsiregistravote? 370 00:17:46,530 --> 00:17:47,030 Taip? 371 00:17:47,030 --> 00:17:47,990 >> PUBLIKA: [nesigirdi]. 372 00:17:47,990 --> 00:17:51,652 373 00:17:51,652 --> 00:17:52,360 GARSIAKALBIS: Būtent. 374 00:17:52,360 --> 00:17:55,810 Į geriausią scenarijų burbulas rūšiuoti ir algoritmų daug, 375 00:17:55,810 --> 00:17:58,769 jei aš ranka jums aštuonis žmones kurie jau rūšiuojamos, 376 00:17:58,769 --> 00:18:00,560 būtų kvaila už jus, algoritmas, 377 00:18:00,560 --> 00:18:02,202 eiti pirmyn ir atgal daugiau nei vieną kartą, tiesa? 378 00:18:02,202 --> 00:18:04,285 Kadangi, kaip greitai, kaip jūs vaikščioti per sąrašą iš karto, 379 00:18:04,285 --> 00:18:08,090 jūs turėtumėte suprasti, oh, aš padariau ne apsikeitimo sandoriai, šis sąrašas surūšiuotas, išėjimą. 380 00:18:08,090 --> 00:18:09,700 Bet, kad ketina imtis jums n žingsnių. 381 00:18:09,700 --> 00:18:12,033 >> Ir atvirkščiai, kas dar būdas galvoti apie tai? 382 00:18:12,033 --> 00:18:15,240 Burbulas tarsi yra omega, taip sakant, n, 383 00:18:15,240 --> 00:18:19,050 nes jei peržvelgsite mažiau nei n elementai, tai, kas 384 00:18:19,050 --> 00:18:23,009 yra esminis klausimas yra? 385 00:18:23,009 --> 00:18:24,550 Jūs nežinote, jei ji rūšiuojamos, į dešinę. 386 00:18:24,550 --> 00:18:26,800 Mes, žmonės gali pažvelgti į aštuonis žmonės ir bus kaip, oi, tai rūšiuojamos, 387 00:18:26,800 --> 00:18:28,430 kad neatsižvelgė man n žingsnių, tačiau tai padarė. 388 00:18:28,430 --> 00:18:30,810 Tavo akys, nors jums natūra iš turi didelį matymo lauką, 389 00:18:30,810 --> 00:18:33,184 jūs pažvelgė aštuonių elementų, jūs pažvelgė aštuonių žmonių, 390 00:18:33,184 --> 00:18:34,610 kad aštuonių žingsnių veiksmingai. 391 00:18:34,610 --> 00:18:38,612 Ir tik tada, kai aš vaikščioti per visą sąrašas daryti Suprantu taip, rūšiuojamos. 392 00:18:38,612 --> 00:18:41,320 Jei aš sustabdytas įpusėjus galvoju, visi Gerai, tai gana rūšiuojami šiol, 393 00:18:41,320 --> 00:18:42,520 kas yra šansai tai nėra surūšiuoti? 394 00:18:42,520 --> 00:18:44,186 Tai algoritmai nesiruošia būti teisinga. 395 00:18:44,186 --> 00:18:46,250 Gali būti greitesnis, bet neteisingas. 396 00:18:46,250 --> 00:18:48,500 >> Taigi dabar mes turime būdą aprašant mažesnę ribas, 397 00:18:48,500 --> 00:18:49,710 ir ką apie nuolat laiku? 398 00:18:49,710 --> 00:18:54,565 Kas algoritmas, kuris yra mažesnis privalo savo veikimo laiką vienos? 399 00:18:54,565 --> 00:18:58,350 1 žingsnis 2 žingsniai, 10 žingsnių, tačiau pastovus, nepriklauso nuo n, 400 00:18:58,350 --> 00:18:59,310 iš įėjimo dydis? 401 00:18:59,310 --> 00:19:03,930 402 00:19:03,930 --> 00:19:04,600 Taip, iš nugaros. 403 00:19:04,600 --> 00:19:05,309 >> PUBLIKA: Printf? 404 00:19:05,309 --> 00:19:06,183 GARSIAKALBIS: Kas tai? 405 00:19:06,183 --> 00:19:07,184 PUBLIKA: Printf? 406 00:19:07,184 --> 00:19:07,850 GARSIAKALBIS: Printf. 407 00:19:07,850 --> 00:19:08,400 Gerai, tikrai. 408 00:19:08,400 --> 00:19:10,720 Taigi užtrunka fiksuotą skaičių žingsnių. 409 00:19:10,720 --> 00:19:13,170 Ir turėčiau now-- dabar, mes kalbame apie C kodas 410 00:19:13,170 --> 00:19:16,040 ir ne nulio, kažkas kaip tarkim, su printf, 411 00:19:16,040 --> 00:19:17,710 turėtume pradėti gauti atsargūs. 412 00:19:17,710 --> 00:19:21,090 Kadangi printf nėra priimti įėjimo, tai eilutė, 413 00:19:21,090 --> 00:19:23,220 ir styginiams tai techniškai turi ilgį. 414 00:19:23,220 --> 00:19:25,530 Taigi, jei mes dabar nori pasiimti jums, jei jūs neprieštaraujate, 415 00:19:25,530 --> 00:19:29,430 techniškai galėtume teigti, kad printf nėra priimti kintamo ilgio įvestį, 416 00:19:29,430 --> 00:19:32,270 ir, žinoma, tai gali užtrukti daugiau laikas atspausdinti eilutę taip ilgai, 417 00:19:32,270 --> 00:19:33,560 nei šis ilgai. 418 00:19:33,560 --> 00:19:36,570 >> Taigi ką daryti, jei mes manome, tik rūšiavimo ir ieškoti pavyzdžių? 419 00:19:36,570 --> 00:19:40,450 Ką apie Mike Smith telefone knyga, ar dvejetainis paieškos apskritai? 420 00:19:40,450 --> 00:19:42,220 Geriausiu atveju, kas gali atsitikti? 421 00:19:42,220 --> 00:19:45,577 Atidaryti telefono knyga ir bam ten Mike Smith skaičius. 422 00:19:45,577 --> 00:19:46,660 Galiu skambinti jam iš karto. 423 00:19:46,660 --> 00:19:49,390 >> Paėmė vieną žingsnį, gal dviem etapais, bet pastovus pakopų skaičius 424 00:19:49,390 --> 00:19:50,230 jei aš laimingas. 425 00:19:50,230 --> 00:19:52,570 Ir tiesą sakant, matėme Pirmadienis jūsų klasiokas 426 00:19:52,570 --> 00:19:54,710 gauti gana pasisekė du kartus iš eilės. 427 00:19:54,710 --> 00:19:57,050 Ir tai iš tiesų buvo nuolatinis laikas per apatinių ribų 428 00:19:57,050 --> 00:20:01,280 dėl tos algoritmas ieškant skaičius 50 už tuos uždarytas 429 00:20:01,280 --> 00:20:01,830 durys. 430 00:20:01,830 --> 00:20:06,400 >> Dabar, kaip panaikinti, jei jums atrasti kad tiek didelis O viršutinė riba, 431 00:20:06,400 --> 00:20:09,310 ir omega, apačios, yra vienas pats, kad 432 00:20:09,310 --> 00:20:11,830 yra pati formulė skliausteliai, taip pat galite 433 00:20:11,830 --> 00:20:15,170 pasakyti, tiesiog, kad būtų išgalvotas, kad kažkas yra teta 434 00:20:15,170 --> 00:20:18,270 n ar teta iš kitu vertę. 435 00:20:18,270 --> 00:20:20,661 Tai tiesiog reiškia, kad kai didelis O ir omega yra tas pats. 436 00:20:20,661 --> 00:20:21,910 Dabar ką apie atrankos rūšiuoti? 437 00:20:21,910 --> 00:20:23,400 Leiskite naudoti šią naują žodyną. 438 00:20:23,400 --> 00:20:27,407 Be atrankos rūšiuoti, ką gi mes buvome daro vėl ir vėl, ir vėl? 439 00:20:27,407 --> 00:20:29,990 Aš buvau ketinate pirmyn ir atgal per sąrašas, ieško kam? 440 00:20:29,990 --> 00:20:33,260 441 00:20:33,260 --> 00:20:34,730 Mažiausias skaičius. 442 00:20:34,730 --> 00:20:37,560 >> Taigi, kaip daug priemonių, kaip daug palyginimų aš 443 00:20:37,560 --> 00:20:43,250 turite padaryti, siekiant išsiaiškinti, kas mažiausias elementas sąraše buvo? 444 00:20:43,250 --> 00:20:44,437 n atėmus 1, tiesa? 445 00:20:44,437 --> 00:20:47,770 Nes jei aš tiesiog pradėkite su vienas aš tikiu, suteikta ir aš pradedu lyginant jį ar ją, 446 00:20:47,770 --> 00:20:49,519 tada jam ar jai, jam ar jai, jam ar jai, aš 447 00:20:49,519 --> 00:20:52,010 gali tik suporuoti elementai kartu n atėmus 1 kartus. 448 00:20:52,010 --> 00:20:55,630 Taigi pasirinkimas tarsi panašiai trunka n atėmus 1 žingsnius pirmą kartą. 449 00:20:55,630 --> 00:20:59,540 >> Kiek žingsnių užtrunka mane rasti antrą mažiausią elementą? 450 00:20:59,540 --> 00:21:02,920 n atėmus 2, nes aš būdamas kvailas jei aš nuolat ieško pačių žmonių 451 00:21:02,920 --> 00:21:06,280 dar kartą, jei aš jau pasirinkote jį ar jos ir įdėti juos į jų vietą. 452 00:21:06,280 --> 00:21:09,270 Ir trečiasis etapas, n minus 3, 4, tada n atėmus. 453 00:21:09,270 --> 00:21:11,020 Mes matėme šį modelį anksčiau, ir iš tiesų 454 00:21:11,020 --> 00:21:13,460 pasirinkimas tarsi panašiai turi viršutinė riba 455 00:21:13,460 --> 00:21:16,210 n kvadratu, jei mes iki tos api. 456 00:21:16,210 --> 00:21:19,790 Koks jo apatinė atranka rikiuoti? 457 00:21:19,790 --> 00:21:25,350 Minimaliai, kiek laiko būtina atranka Rūšiuoti imtis, kaip mes apibrėžti jį pirmadienį? 458 00:21:25,350 --> 00:21:29,370 459 00:21:29,370 --> 00:21:30,490 Pasiūlyti du variantai. 460 00:21:30,490 --> 00:21:32,360 Gal tai n, kaip ir anksčiau. 461 00:21:32,360 --> 00:21:35,040 Gal tai n kvadratu, nes ji dabar kaip viršutinė riba. 462 00:21:35,040 --> 00:21:35,874 >> PUBLIKA: n kvadratu. 463 00:21:35,874 --> 00:21:36,664 GARSIAKALBIS: n kvadratu. 464 00:21:36,664 --> 00:21:37,368 Kodėl? 465 00:21:37,368 --> 00:21:40,060 >> PUBLIKA: Kadangi jūs turite apibrėžti [nesigirdi]. 466 00:21:40,060 --> 00:21:41,510 >> GARSIAKALBIS: Būtent. 467 00:21:41,510 --> 00:21:45,077 Bent jau aš apibrėžti atrankos rūšiuoti jis buvo gana naivus, nesustoti, 468 00:21:45,077 --> 00:21:46,160 rasti mažiausias elementas. 469 00:21:46,160 --> 00:21:47,770 Eiti vėl, rasti mažiausią elementą. 470 00:21:47,770 --> 00:21:49,490 Eiti vėl, rasti mažiausią elementą. 471 00:21:49,490 --> 00:21:51,700 Nėra rūšiuoti optimizavimas ten, kad 472 00:21:51,700 --> 00:21:54,350 gali leiskite nutraukti po tik n arba tiek žingsnių. 473 00:21:54,350 --> 00:21:57,080 Taigi iš tiesų, pasirinkimas Rūšiuoti, omega n kvadratu. 474 00:21:57,080 --> 00:22:00,667 >> Ką apie įterpimo rūšiuoti, kur aš paėmė kas man buvo suteikta, ir tada aš plopped jį 475 00:22:00,667 --> 00:22:01,750 ar jos tinkamoje vietoje? 476 00:22:01,750 --> 00:22:04,958 Tada aš pradėjo antrąjį asmenį, plopped jį ar ją į tinkamą vietą. 477 00:22:04,958 --> 00:22:07,910 Tada kitas asmuo, plopped jam ar jai į tinkamą vietą. 478 00:22:07,910 --> 00:22:10,537 Atkreipkite dėmesį, kad tai yra labai linijinis, taip sakant. 479 00:22:10,537 --> 00:22:12,620 Aš tiesi linija, aš nesiruošia pirmyn ir atgal, 480 00:22:12,620 --> 00:22:16,080 Aš niekada Prisiminus tikrai, bet tai, kas vyksta, kai aš įdėti jį 481 00:22:16,080 --> 00:22:20,302 ar jai į pradžią sąrašas, kaip mes padarėme pirmadienį? 482 00:22:20,302 --> 00:22:21,010 Kas vyksta? 483 00:22:21,010 --> 00:22:21,510 Taip? 484 00:22:21,510 --> 00:22:23,122 PUBLIKA: [nesigirdi]. 485 00:22:23,122 --> 00:22:24,830 GARSIAKALBIS: Taip, kad buvo sugauti, tiesa? 486 00:22:24,830 --> 00:22:26,746 Galbūt jūs žinote, iš Jūsų klasiokais, jei jie 487 00:22:26,746 --> 00:22:29,670 buvo padaryti bet kokį judėjimą su jų kojos, kad buvo operacija. 488 00:22:29,670 --> 00:22:33,610 Taigi, jei ten buvo trys žmonės čia ir naujas žmogus priklausė būdas ten, 489 00:22:33,610 --> 00:22:37,360 ant ilgo etape, kaip tai, tikrai, jis arba ji gali tiesiog eiti iki galo. 490 00:22:37,360 --> 00:22:40,074 Bet jei mes galvojame apie kompiuteris ir atminties masyvas, 491 00:22:40,074 --> 00:22:41,990 šie žmonės vyksta turėti shuffle per 492 00:22:41,990 --> 00:22:43,260 padaryti kambarį tą asmenį. 493 00:22:43,260 --> 00:22:46,930 Ir taip, kad n atėmus 1 shufflings, n atėmus 2 shufflings, n 494 00:22:46,930 --> 00:22:50,660 minus 3 shufflings yra tik rūšies vyksta už mane, o ne priešais mane 495 00:22:50,660 --> 00:22:52,710 kaip ir anksčiau, tam tikra prasme. 499 00:22:52,557 --> 00:22:54,640 Dabar, kaip žemę, ir kaip galite matyti internete 500 00:22:54,640 --> 00:22:57,699 jei jums pradėti išnyra aplink apie rūšių, yra tiek daug skirtingų tie 501 00:22:57,699 --> 00:22:59,490 ten, kai kurie iš jų geriau nei kiti. 502 00:22:59,490 --> 00:23:02,200 Iš tiesų, bogosort yra vienas tai įdomus natūra ieškoti. 503 00:23:02,200 --> 00:23:06,650 Bogosort užima rinkinį numerius ar pasakyti kortų kaladę, 504 00:23:06,650 --> 00:23:09,870 atsitiktinai sumaišo juos, ir patikrina, ar jie rūšiuojami. 505 00:23:09,870 --> 00:23:12,130 Ir jei ne, ar jį dar kartą. 506 00:23:12,130 --> 00:23:14,140 Ir jei ne, ar jį dar kartą. 507 00:23:14,140 --> 00:23:15,440 Jei ne, ar jį dar kartą. 508 00:23:15,440 --> 00:23:17,060 Neįtikėtina kvaila. 509 00:23:17,060 --> 00:23:19,520 >> Ir iš tiesų, jei jūs skaitote kaip Vikipedijos straipsnio, 510 00:23:19,520 --> 00:23:21,200 jo slapyvardis yra kvaila rikiuoti. 511 00:23:21,200 --> 00:23:25,180 Tai galų gale dirbti, tikiuosi, suteikta pakankamai laiko, 512 00:23:25,180 --> 00:23:28,240 bet kiek laiko gali užtrukti šiek tiek laiko. 513 00:23:28,240 --> 00:23:31,650 Taigi, jei aš galėtų tegul greičio dalykų iki iš Mary Beth pavyzdžiu anksčiau, 514 00:23:31,650 --> 00:23:35,150 turėdami kelis elementus, bet dar dvi procesoriai. 515 00:23:35,150 --> 00:23:37,100 Du žmonės, jei jums ne tai prisijungti prie manęs. 516 00:23:37,100 --> 00:23:40,972 Kaip apie 1 per čia, ir tegul go-- niekas ten? 517 00:23:40,972 --> 00:23:41,722 Niekas ten? 518 00:23:41,722 --> 00:23:42,221 Gerai. 519 00:23:42,221 --> 00:23:44,190 Jūs su juoda marškinėliai, taip, nagi žemyn. 520 00:23:44,190 --> 00:23:45,000 Gerai, koks tavo vardas? 521 00:23:45,000 --> 00:23:45,720 >> PUBLIKA: Petras. 522 00:23:45,720 --> 00:23:46,100 >> GARSIAKALBIS: Kas tai? 523 00:23:46,100 --> 00:23:46,766 >> PUBLIKA: Petras. 524 00:23:46,766 --> 00:23:49,450 GARSIAKALBIS: Petras Dovydas malonu susitikti su jumis. 525 00:23:49,450 --> 00:23:53,670 Gerai, mes turime Petrui čia, jei jus nori ateiti ant stalo čia. 526 00:23:53,670 --> 00:23:54,550 Ir koks tavo vardas? 527 00:23:54,550 --> 00:23:55,216 >> PUBLIKA: Elena. 528 00:23:55,216 --> 00:23:55,970 GARSIAKALBIS: Elena. 529 00:23:55,970 --> 00:23:57,030 Gerai, nice to meet you. 530 00:23:57,030 --> 00:23:58,060 Elena susitikti Petrą. 531 00:23:58,060 --> 00:23:59,170 Petras, Elena. 532 00:23:59,170 --> 00:24:02,290 Ir mes turime Andrew čia taip pat, prašom. 533 00:24:02,290 --> 00:24:06,107 Ir jūsų užduotis vyksta būti rūšiuoti kortų kaladę. 534 00:24:06,107 --> 00:24:08,190 Ir jei nepažįstamas, denio korteles turėtų galiausiai 535 00:24:08,190 --> 00:24:11,064 būti rūšiuojami truputį kažką panašaus tai kur mes padarysime klubai, tada 536 00:24:11,064 --> 00:24:13,660 kad kastuvai, tada širdis ir deimantai, nuo tūzo kaip vienas, 537 00:24:13,660 --> 00:24:15,570 visą kelią iki karaliaus. 538 00:24:15,570 --> 00:24:20,890 >> Kortos Aš ruošiuosi duoti jums ketiname būti 52 kiekybe. 539 00:24:20,890 --> 00:24:23,160 Mes ketiname panašiai laikas jums, vos akimirką. 540 00:24:23,160 --> 00:24:26,410 Mes ketiname mesti Andrew Ekrane čia 541 00:24:26,410 --> 00:24:28,170 taip žiūrėti, kaip jums tai padaryti. 542 00:24:28,170 --> 00:24:31,070 Ir taip, kad visa tai yra dar akivaizdesnis, 543 00:24:31,070 --> 00:24:33,490 tai kortelės gavau "Amazon". 544 00:24:33,490 --> 00:24:42,861 Taigi jie jau atsitiktinai rūšiuojami, ir mes ketiname kartą jums. 545 00:24:42,861 --> 00:24:44,610 Ir mes ketiname keep it real šį kartą, 546 00:24:44,610 --> 00:24:47,820 todėl mes ketiname bandyti spausti jus nes kitaip tai bus sunkus 547 00:24:47,820 --> 00:24:48,460 greitai. 548 00:24:48,460 --> 00:24:53,860 Jei galėtumėte tęsti rūšiuoti 52 elementus, kartu per kai kurių priemonių, dabar. 549 00:24:53,860 --> 00:25:04,710 550 00:25:04,710 --> 00:25:07,180 >> Ir vėl, kaip mes žiūrėti šiuos vaikinai ką daryti, galų gale 551 00:25:07,180 --> 00:25:10,200 ketina gaminti akivaizdus rezultatas, galvoti apie tikrai 552 00:25:10,200 --> 00:25:12,962 kaip jie kiekvienas daro tai, kaip jūs galėtumėte apibūdinti. 553 00:25:12,962 --> 00:25:15,045 Nes vėl, tai yra Visi procesai, algoritmai 554 00:25:15,045 --> 00:25:17,090 kad mes priimame kaip savaime, kaip žmogaus. 555 00:25:17,090 --> 00:25:22,349 Bet jūs tikriausiai seniai intuicija, ilgai prieš jums dar 556 00:25:22,349 --> 00:25:24,390 maniau apie vartojate informatikos klasė jums 557 00:25:24,390 --> 00:25:27,223 galėjo intuicija su kuri, siekiant išspręsti problemas, kaip šis. 558 00:25:27,223 --> 00:25:29,560 Bet kai jūs pripažinti modeliai ir pradėti 559 00:25:29,560 --> 00:25:32,407 formalizuoti veiksmus, su kuriomis jūs spręsti šias problemas, 560 00:25:32,407 --> 00:25:35,490 jūs pamatysite, kad jūs galite išspręsti daug įdomesnis ir daug sudėtingesnis 561 00:25:35,490 --> 00:25:39,190 problemos greitai. 562 00:25:39,190 --> 00:25:42,351 Taigi kažkas iš auditorijos, kas yra bent vienas iš elementų, algoritmas 563 00:25:42,351 --> 00:25:43,350 kad jie naudoja čia? 564 00:25:43,350 --> 00:25:44,275 >> PUBLIKA: [nesigirdi] 565 00:25:44,275 --> 00:25:45,150 GARSIAKALBIS: Kas tai? 566 00:25:45,150 --> 00:25:47,062 PUBLIKA: Pagal kostiumas. 567 00:25:47,062 --> 00:25:47,770 GARSIAKALBIS: Pagal kostiumas. 568 00:25:47,770 --> 00:25:50,630 Taigi, pirmiausia jie grupavimo visi deimantai kartu 569 00:25:50,630 --> 00:25:52,560 atrodo, visi širdys kartu atrodo, 570 00:25:52,560 --> 00:25:56,520 ir taip toliau, be pagarbos už dėl kortelių numerius. 571 00:25:56,520 --> 00:26:00,900 Ir dabar jie atrodo, pavyzdžiui, būti rūšiavimą skaičiaus. 572 00:26:00,900 --> 00:26:06,870 573 00:26:06,870 --> 00:26:08,910 Labai gerai. 574 00:26:08,910 --> 00:26:12,370 >> Gerai, kad tai, kas vyksta būti galutinis žingsnis tada čia? 575 00:26:12,370 --> 00:26:16,950 Kai mes turime keturis surūšiuotas kostiumai, ką mes turime daryti, kad keturių polių 576 00:26:16,950 --> 00:26:20,059 siekiant vieno rūšiuoti denio, tiesiog? 577 00:26:20,059 --> 00:26:21,350 Taigi, mes turime sujungti juos vėl. 578 00:26:21,350 --> 00:26:25,160 >> Taigi, čia yra įdomi mintis, kad vėl Manyti, yra labai intuityvus, net 579 00:26:25,160 --> 00:26:28,140 jei gali niekada antausį kad etiketės ant jo natūra. 580 00:26:28,140 --> 00:26:31,900 Ši pagrindinė sąvoka dalijant problema ne pusę šio laiko, 581 00:26:31,900 --> 00:26:33,410 bet bent į keturis gabalus. 582 00:26:33,410 --> 00:26:36,810 Spręsti gana daug iš esmės identiškos problemos 583 00:26:36,810 --> 00:26:40,480 atskirai vienas nuo kito, ir tada sujungti rezultatus. 584 00:26:40,480 --> 00:26:46,940 585 00:26:46,940 --> 00:26:50,140 Ir puikus, padaryta. 586 00:26:50,140 --> 00:26:52,140 Gerai, didelis apvalus plojimų, jei galėtume. 587 00:26:52,140 --> 00:26:56,480 >> [Plojimai] 588 00:26:56,480 --> 00:26:59,740 >> GARSIAKALBIS: aš neįsivaizduoju, ką jūs daryti su tai, bet čia jums eiti. 589 00:26:59,740 --> 00:27:01,690 Labai ačiū. 590 00:27:01,690 --> 00:27:04,660 Taigi pažiūrėkime, dvi minutes ir aštuonios sekundės, 591 00:27:04,660 --> 00:27:07,490 jei norite mesti iššūkį savo draugams. 592 00:27:07,490 --> 00:27:12,160 Kas tada vyksta į būti atimti iš to 593 00:27:12,160 --> 00:27:13,830 kad mes galime pritraukti daugiau apskritai? 594 00:27:13,830 --> 00:27:16,080 Na, manau, kad atgal į šis skaičius masyvas, 595 00:27:16,080 --> 00:27:19,060 ir manau, kad dabar sugrįžote pas kai Pseudocode mes parašiau anksčiau, 596 00:27:19,060 --> 00:27:22,080 ir tai buvo dėl Pseudocode sprendžiant telefonų knygos problema. 597 00:27:22,080 --> 00:27:25,150 , Pagal kurį Pseudocode I išvardijo daugiau metodinę būdas 598 00:27:25,150 --> 00:27:28,400 aprašyti, kaip aš labai intuityvus žmogaus algoritmas dalijant telefoną 599 00:27:28,400 --> 00:27:31,650 knyga per pusę, kartoju, kartoju, kartoju, kol aš rasti ką nors, kaip Mike Smith, 600 00:27:31,650 --> 00:27:33,790 jei jis iš tikrųjų yra telefonų knygoje. 601 00:27:33,790 --> 00:27:37,610 >> Bet aš rūšies naudojami, ką aš kviesiu labai pasikartojantis požiūris čia 602 00:27:37,610 --> 00:27:42,160 ypač įspėjimo linija 8 ir linija 11. 603 00:27:42,160 --> 00:27:46,750 Tai yra įrodymas, pasikartojantis požiūris, apsisukimo požiūris, 604 00:27:46,750 --> 00:27:49,040 nes tai yra būtent tai, elgesys jie sukelia. 605 00:27:49,040 --> 00:27:52,910 Tos linijos abu sako eiti į rūšies linija trijų, ir jūs galite iš 606 00:27:52,910 --> 00:27:55,140 manau, kad jūsų proto akis kaip kilpa. 607 00:27:55,140 --> 00:27:59,080 Tai sakau, kad grįžti iki žingsnio trijų ir pakartoti, vėl, ir vėl, 608 00:27:59,080 --> 00:28:00,010 ir vėl. 609 00:28:00,010 --> 00:28:04,410 >> Bet ką daryti, jei mes sverto pagrindinį idėją čia, kad mes ne paskutinį kartą, 610 00:28:04,410 --> 00:28:10,280 ir supaprastinti linija 8 ir 11 eilutė ir jų kaimynai 611 00:28:10,280 --> 00:28:12,840 kaip tik tai, geltonai. 612 00:28:12,840 --> 00:28:16,480 Tai nėra iš esmės sutrumpinti Pseudocode labai daug, 613 00:28:16,480 --> 00:28:20,530 bet tai iš esmės keičia mano algoritmas pobūdis. 614 00:28:20,530 --> 00:28:24,220 Ką aš dabar sako, 7 žingsnis 10 žingsnis, 615 00:28:24,220 --> 00:28:29,140 yra ieškoti Mike į tą patį kelią, 616 00:28:29,140 --> 00:28:31,580 bet tik į kairę pusę arba į dešinę pusę. 617 00:28:31,580 --> 00:28:33,420 >> Taigi, kitaip tariant, jei Pradėsiu nuo vieno žingsnio 618 00:28:33,420 --> 00:28:36,150 pasiimti telefono knyga, atvira viduryje iš telefonų knygos, pažvelgti pavadinimų, 619 00:28:36,150 --> 00:28:39,010 jei Smithas yra tarp NAME, skambinkite Mike, kita 620 00:28:39,010 --> 00:28:44,340 jei Smith anksčiau knygos, Žingsnis Septyni ieškoti Mike kairėje pusėje knygoje. 621 00:28:44,340 --> 00:28:47,130 Tačiau, kad šios rūšies jaučiasi jis palieka mane kabo, tiesa? 622 00:28:47,130 --> 00:28:49,240 Geltonai, yra instrukcija, bet kaip man 623 00:28:49,240 --> 00:28:51,870 ieškoti Mike į kairę pusė telefonų knygoje? 624 00:28:51,870 --> 00:28:54,210 Kai turiu algoritmas, su kuria aš 625 00:28:54,210 --> 00:28:57,100 galite ieškoti kažkas panašaus Mike Smith? 626 00:28:57,100 --> 00:28:58,980 Na, tai žiūri mums į veidą. 627 00:28:58,980 --> 00:29:03,090 Galiu tiesiog naudoti patį programa efektyviai einame į viršų 628 00:29:03,090 --> 00:29:06,490 vėl ir vėl veikia tie patys eilučių kodo. 629 00:29:06,490 --> 00:29:10,610 >> Taigi, nors tai turėtų jaustis kaip ciklinio apibrėžimą šiek tiek 630 00:29:10,610 --> 00:29:13,480 kur jūs atsakyti į kažkieno klausimas, tiesiog tarsi klausia 631 00:29:13,480 --> 00:29:15,990 tą patį klausimą vėl, kaip, kodėl, kodėl, kodėl? 632 00:29:15,990 --> 00:29:21,580 Realybė yra tai, nes mes sunkiai koduojami Specialiųjų linijų pora, 4 žingsnis, 633 00:29:21,580 --> 00:29:25,320 kuris yra, jei ir 12 žingsnis, yra efektyviai kitą filialas, 634 00:29:25,320 --> 00:29:30,120 nes mes turime tuos laikina priemones, Šis algoritmas bus nutraukti, jei mes 635 00:29:30,120 --> 00:29:32,050 rasite Mike, ar jei mes ne. 636 00:29:32,050 --> 00:29:36,810 Tačiau 7 ir 10 etapas dabar, mes turime ką mes vadiname rekursinį algoritmą. 637 00:29:36,810 --> 00:29:40,420 Ir rekursija yra iš tiesų galinga idėja kad šiek tiek proto lenkimo per pirmąjį, 638 00:29:40,420 --> 00:29:42,500 kad dabar mes galime taikyti taip. 639 00:29:42,500 --> 00:29:46,600 >> Sujungti Rūšiuoti bus paskutinis rūšiuoti, kad mes pažvelgti, bent jau klasę formaliai. 640 00:29:46,600 --> 00:29:50,040 Ir tai iš esmės skiriasi nuo Šių trijų, ir tikrai 641 00:29:50,040 --> 00:29:52,140 keturi paskutinieji, jei mes įtraukti bogosort. 642 00:29:52,140 --> 00:29:54,810 Štai už merge rūšiuoti Pseudocode. 643 00:29:54,810 --> 00:30:00,170 Kai ant įvesties n elementų, todėl atsižvelgiant į iš dydžio n matrica, jei n yra mažesnis nei 2, 644 00:30:00,170 --> 00:30:01,040 grįžti. 645 00:30:01,040 --> 00:30:03,610 Taigi, kodėl aš turiu, kad normalumas patikrinti pirmiausia? 646 00:30:03,610 --> 00:30:09,477 Kas iškyla, jei aš ranka jums masyvas, kurio ilgis n yra mažesnis nei 2? 647 00:30:09,477 --> 00:30:11,060 Tai jau rūšiuojamos, be abejo, tiesa? 648 00:30:11,060 --> 00:30:13,640 Kadangi sąrašas arba turi vienas elementas, kuris yra banaliai 649 00:30:13,640 --> 00:30:15,180 rūšiuojami, nes tai Vienintelis dalykas ten. 650 00:30:15,180 --> 00:30:18,138 Arba, tai dydžio nulinio o tai reiškia, nieko rūšiuoti, todėl pagal savo pobūdį 651 00:30:18,138 --> 00:30:18,720 ji yra rūšiuojama. 652 00:30:18,720 --> 00:30:20,410 Yra tik nieko blogo ten. 653 00:30:20,410 --> 00:30:22,310 Taigi, kad mūsų vadinamosios bazinį scenarijų. 654 00:30:22,310 --> 00:30:24,440 >> Tai yra panašus į dvasią tai, ką mes padarėme su Mike. 655 00:30:24,440 --> 00:30:26,023 Jei Mike telefonų knygoje, skambinti jam. 656 00:30:26,023 --> 00:30:27,740 Jei jis nėra, pasiduoti. 657 00:30:27,740 --> 00:30:31,240 Tai vadinamasis bazinį scenarijų, įsitikinkite, kad Šis algoritmas ne dienos pabaigoje 658 00:30:31,240 --> 00:30:33,540 sustos tam tikromis aplinkybėmis. 659 00:30:33,540 --> 00:30:37,890 >> Bet čia tikėjimo šuolis dabar kitur, rūšiuoti kairėje pusėje, elementų, 660 00:30:37,890 --> 00:30:39,740 tada rūšiuoti teisę pusė iš elementų, 661 00:30:39,740 --> 00:30:41,189 ir tada sujungti rūšiuoti puses. 662 00:30:41,189 --> 00:30:43,230 Ir čia, kur jis jaučiasi kaip mes copping iš. 663 00:30:43,230 --> 00:30:46,900 Aš paklausiau, rūšiuoti n elementų, ir aš 664 00:30:46,900 --> 00:30:50,712 sakydamas, gerai, tai jį rūšiavimas kairę ir rūšiavimas teisę. 665 00:30:50,712 --> 00:30:52,420 Bet aš sakau, vieną kitas dalykas, ir tai 666 00:30:52,420 --> 00:30:55,530 yra pagrindinė tema atrodo į intuicija iki šiol, 667 00:30:55,530 --> 00:30:57,380 ten šis trečiasis žingsnis sujungiant. 668 00:30:57,380 --> 00:31:00,430 Kuris nors jį atrodo, kad kvailas dvasia, 669 00:31:00,430 --> 00:31:02,320 kaip tik sujungti dalykų kartu, atrodo, 670 00:31:02,320 --> 00:31:05,380 būti svarbus žingsnis link sumontavimu dvi problemas, kad 671 00:31:05,380 --> 00:31:07,330 buvo suskirstyti galiausiai per pusę. 672 00:31:07,330 --> 00:31:12,090 >> Taigi sujungti rūšiuoti, tegul tai padaryti, jei jūs humoras man, dar vienu demonstravimo, 673 00:31:12,090 --> 00:31:14,730 tik todėl, kad mes turime kai Skaičiai dirbti. 674 00:31:14,730 --> 00:31:19,470 Ar galiu pasikeisti aštuonis stresą kamuoliukai aštuonių žmonių? 675 00:31:19,470 --> 00:31:29,320 Gerai, kaip apie jus trijų, jūs keturių Šiame skyriuje, penki, šeši, ir tegul 676 00:31:29,320 --> 00:31:30,720 do, 7, 8, nagi iki. 677 00:31:30,720 --> 00:31:35,120 678 00:31:35,120 --> 00:31:36,520 Gerai, taip gerai. 679 00:31:36,520 --> 00:31:38,640 Minus 8, ten mes einame, plius 1. 680 00:31:38,640 --> 00:31:39,150 Puikus. 681 00:31:39,150 --> 00:31:42,000 Visos teisės ateiti iki, tegul greitai jums numerius. 682 00:31:42,000 --> 00:31:50,800 Taškų du, skaičius "trys", ketvirtą, skaičius penkis, šešis, septynis, o aštuoni. 683 00:31:50,800 --> 00:31:52,140 Aš aštuonis teisingai šį kartą. 684 00:31:52,140 --> 00:31:56,390 >> Gerai, kad eiti į priekį, jei galėtų, ir tegul rūšiuoti originalioje kad 685 00:31:56,390 --> 00:31:59,810 , kad mes turėjome vakar kuris atrodė kaip tai, jei ne tai. 686 00:31:59,810 --> 00:32:03,620 Ir tegul tai padaryti priešais esančioje lentelėje. 687 00:32:03,620 --> 00:32:06,510 Gerai, kad sujungti rūšiuoti. 688 00:32:06,510 --> 00:32:08,820 Tai kur ji vyksta gauti natūra įdomu, 689 00:32:08,820 --> 00:32:12,800 nes man atrodo, kad reikia duoti save tiek mažiau informacijos šiandien. 690 00:32:12,800 --> 00:32:15,149 >> Taigi sujungti tarsi visų pirma indėliu į n elementų, 691 00:32:15,149 --> 00:32:18,440 ir, žinoma, ne mažiau kaip du, tai aštuonių, todėl turiu šiek tiek daugiau nuveikti. 692 00:32:18,440 --> 00:32:21,140 Taigi, dabar mintyse mes, kaip klasės yra dabar kitas filialas 693 00:32:21,140 --> 00:32:22,540 o tai reiškia, tris žingsnius. 694 00:32:22,540 --> 00:32:25,017 Pirma, aš turiu rūšiuoti kairė pusė elementų. 695 00:32:25,017 --> 00:32:26,350 Taigi, kaip aš galiu eiti apie tai daro? 696 00:32:26,350 --> 00:32:28,950 Na, aš ruošiuosi rūšies protiškai padalinti sąrašą čia 697 00:32:28,950 --> 00:32:30,700 Jūs neturite fiziškai judėti, ir aš 698 00:32:30,700 --> 00:32:33,180 ketina sutelkti dėmesį tik į kairė pusė čia elementų. 699 00:32:33,180 --> 00:32:36,770 Taigi, kaip aš galiu eiti apie rūšiavimą Sąraše dydžio keturių? 700 00:32:36,770 --> 00:32:38,730 Koks mano algoritmas? 701 00:32:38,730 --> 00:32:42,580 Pirmiausia aš patikrinti yra n mažiau kaip du, ne, todėl aš pereiti prie kito bloko dar kartą. 702 00:32:42,580 --> 00:32:43,900 Rūšiuoti paliko pusę elementų. 703 00:32:43,900 --> 00:32:45,608 >> Taigi dabar vėl, psichiškai, ir tai yra, kai 704 00:32:45,608 --> 00:32:49,550 jūs turite sukaupti daug daug psichikos istorija, jei bus. 705 00:32:49,550 --> 00:32:51,940 Dabar aš rūšiavimas į kairę pusė kairėje pusėje. 706 00:32:51,940 --> 00:32:57,000 Gerai, kad dabar aš vadinu mano paties suliejimą rūšiavimo algoritmą, yra n mažiau nei du? 707 00:32:57,000 --> 00:33:00,590 Ne, tai yra du, todėl aš turiu rūšiuoti kairė pusė, o į dešinę pusę. 708 00:33:00,590 --> 00:33:02,042 Taigi čia mes einame, rūšiuoti yra kairėje pusėje. 709 00:33:02,042 --> 00:33:03,750 Kodėl ne jūs tiesiog išgerkite vieną žingsnį į priekį. 710 00:33:03,750 --> 00:33:04,415 Koks tavo vardas? 711 00:33:04,415 --> 00:33:04,860 >> PUBLIKA: Darren. 712 00:33:04,860 --> 00:33:05,260 >> GARSIAKALBIS: Dan. 713 00:33:05,260 --> 00:33:06,040 Danas žengė į priekį. 714 00:33:06,040 --> 00:33:06,748 >> PUBLIKA: Darren. 715 00:33:06,748 --> 00:33:09,000 GARSIAKALBIS: Darren, padaryta. 716 00:33:09,000 --> 00:33:10,090 Ar galite pasakyti Darren arba Dan? 717 00:33:10,090 --> 00:33:10,550 >> PUBLIKA: Darren. 718 00:33:10,550 --> 00:33:11,216 >> GARSIAKALBIS: Darren. 719 00:33:11,216 --> 00:33:14,422 Gerai, Darren sustiprino į priekį ir jis yra dabar rūšiuojami. 720 00:33:14,422 --> 00:33:16,130 Ir tai yra beveik kvailas teiginys, tiesa? 721 00:33:16,130 --> 00:33:18,862 Nemanau, tikrai atrodo, kad būti pasiekti nieko, bet tegul tęsti. 722 00:33:18,862 --> 00:33:20,820 Dabar leiskite man rūšiuoti teisę pusė iš elementų. 723 00:33:20,820 --> 00:33:21,200 Koks tavo vardas? 724 00:33:21,200 --> 00:33:21,690 >> PUBLIKA: Lukas. 725 00:33:21,690 --> 00:33:22,273 >> GARSIAKALBIS: Lukas. 726 00:33:22,273 --> 00:33:23,400 Nagi, žingsnį į priekį. 727 00:33:23,400 --> 00:33:25,640 Priimta, aš rūšiuojami Luko. 728 00:33:25,640 --> 00:33:28,570 Kairė pusė dabar rūšiuojami ir Dešinė pusė dabar rūšiuojamos, 729 00:33:28,570 --> 00:33:30,770 bet vėlgi, ten svarbiausias žingsnis čia. 730 00:33:30,770 --> 00:33:32,940 Ką aš šalia reikia daryti? 731 00:33:32,940 --> 00:33:33,941 Sulieti rūšiuoti puses. 732 00:33:33,941 --> 00:33:36,648 Dabar mes ketiname tiesiog kiekvienas pirmyn ir atgal, tokiu būdu, 733 00:33:36,648 --> 00:33:38,620 nes aš tipo reikia kai įbrėžimams vietos. 734 00:33:38,620 --> 00:33:40,411 Tai beveik kaip jie vaikinai yra ant stalo, 735 00:33:40,411 --> 00:33:42,460 ir man reikia šiek tiek kambarį perkelti juos aplink. 736 00:33:42,460 --> 00:33:44,170 Taigi, aš ruošiuosi sujungti vaikinai, žiūrėdamas 737 00:33:44,170 --> 00:33:45,960 kairėje pusėje ir dešinėje pusėje. 738 00:33:45,960 --> 00:33:48,740 Ir kas akivaizdžiai ateina pirma, į kairę arba į dešinę pusę pusę? 739 00:33:48,740 --> 00:33:52,710 Taigi teisė pusę, todėl galime pereiti per Luko Čia Darren pradinę padėtį. 740 00:33:52,710 --> 00:33:57,640 Ir dabar sujungti savo kairiąją pusę, Darren ketina perkelti tiesiai ten. 741 00:33:57,640 --> 00:33:59,750 >> Taigi jaučiasi beveik burbulas tarsi poveikis, 742 00:33:59,750 --> 00:34:02,482 bet mano pagrindinis algoritmas, labai skiriasi šiuo metu. 743 00:34:02,482 --> 00:34:04,815 Bet dabar kur viskas susitvarko šiek tiek erzina, nes jums 744 00:34:04,815 --> 00:34:06,810 reikia atsukti protiškai kur aš palikti išjungtas. 745 00:34:06,810 --> 00:34:09,893 Aš tiesiog sujungė surūšiuotas puses, kuris reiškia, kad aš kur mano algoritmas? 746 00:34:09,893 --> 00:34:12,229 747 00:34:12,229 --> 00:34:13,770 Turiu rūšiuoti tinkamą pusę, tiesa? 748 00:34:13,770 --> 00:34:15,910 >> Jei atsukti, tiesiog ant vaizdo, jums 749 00:34:15,910 --> 00:34:18,339 matyti, kad mes turime tai taškas ir Luko Darren 750 00:34:18,339 --> 00:34:21,370 rūšiuoti kairę pusė kairėje pusėje. 751 00:34:21,370 --> 00:34:23,430 Tada mes susijungė tie rūšiuotas puselės, kurios 752 00:34:23,430 --> 00:34:27,941 tai sekantis žingsnis yra tarsi Teisė pusė kairėje pusėje. 753 00:34:27,941 --> 00:34:29,649 Gerai, tad tai greičiau padaryti. 754 00:34:29,649 --> 00:34:33,282 Visos teisės, šešių aš ruošiuosi teigia jūs dabar rūšiuojami, nagi pirmyn. 755 00:34:33,282 --> 00:34:33,990 Koks tavo vardas? 756 00:34:33,990 --> 00:34:34,589 >> PUBLIKA: Adriano. 757 00:34:34,589 --> 00:34:35,200 >> GARSIAKALBIS: Adriano. 758 00:34:35,200 --> 00:34:36,010 Adriano dabar rūšiuojami. 759 00:34:36,010 --> 00:34:36,450 Ir koks tavo vardas? 760 00:34:36,450 --> 00:34:37,080 >> PUBLIKA: Alex. 761 00:34:37,080 --> 00:34:38,379 >> GARSIAKALBIS: Alex dabar rūšiuojami. 762 00:34:38,379 --> 00:34:40,750 Kairysis pusę, į dešinę pusę, kas paskutinis žingsnis? 763 00:34:40,750 --> 00:34:41,250 Sujungti. 764 00:34:41,250 --> 00:34:44,310 Gana trivialus, todėl aš ketina sujungti į šešias, 765 00:34:44,310 --> 00:34:46,930 žengti žingsnį atgal, aštuonių, žengti žingsnį atgal. 766 00:34:46,930 --> 00:34:49,530 Ir dabar pastebėti tai naudinga Takeaway, ką 767 00:34:49,530 --> 00:34:53,930 dabar tiesa apie kairėje pusėje sąrašas, nepriklausomai nuo to, kaip mes pradėjome? 768 00:34:53,930 --> 00:34:55,090 Jis rūšiuojami. 769 00:34:55,090 --> 00:34:57,750 >> Dabar tai nėra rūšiuojamos didelis schema dalykų, 770 00:34:57,750 --> 00:35:00,250 tačiau ji yra rūšiuojami nepriklausomai kitos pusės. 771 00:35:00,250 --> 00:35:04,100 Dabar, kas žingsnis esu I jei aš nuolat pervyniojimas, kaip istorija prasidėjo? 772 00:35:04,100 --> 00:35:05,680 Dabar aš turiu rūšiuoti tinkamą pusę. 773 00:35:05,680 --> 00:35:07,630 Taigi dabar mes grįžta į Istorijos pradžia, 774 00:35:07,630 --> 00:35:08,921 ir tegul tai greičiau padaryti. 775 00:35:08,921 --> 00:35:11,320 Taigi, aš ruošiuosi rūšiuoti Teisė pusė viso sąrašo. 776 00:35:11,320 --> 00:35:13,060 Kas kitas žingsnis? 777 00:35:13,060 --> 00:35:15,840 Rūšiuoti kairėje pusėje, dešinėje pusėje. 778 00:35:15,840 --> 00:35:18,715 Rūšiuoti kairįjį pusę kairė pusė dešinėje pusėje. 779 00:35:18,715 --> 00:35:19,590 Ir koks tavo vardas? 780 00:35:19,590 --> 00:35:20,230 >> PUBLIKA: Omaras. 781 00:35:20,230 --> 00:35:21,970 >> GARSIAKALBIS: Omaras, žingsnis į priekį, daroma. 782 00:35:21,970 --> 00:35:22,860 Kairė pusė yra rūšiuojami. 783 00:35:22,860 --> 00:35:23,330 Ir koks tavo vardas? 784 00:35:23,330 --> 00:35:23,820 >> PUBLIKA: Chris. 785 00:35:23,820 --> 00:35:25,620 >> GARSIAKALBIS: Chris žengti žingsnį į priekį, jūs dabar rūšiuojami. 786 00:35:25,620 --> 00:35:27,010 Kas svarbus žingsnis dabar? 787 00:35:27,010 --> 00:35:27,510 Sujungti. 788 00:35:27,510 --> 00:35:30,509 Taigi vienas ketina sujungti į vietą čia, jei galėtumėte žengti žingsnį atgal, 789 00:35:30,509 --> 00:35:32,930 ir trijų ketina žengti žingsnį atgal, sujungti. 790 00:35:32,930 --> 00:35:38,080 Taigi kairę pusę Teisė pusė, dabar rūšiuojami. 791 00:35:38,080 --> 00:35:41,747 Atvirai kalbant, tai algoritmas jaučiasi mes eikvoti būdas daugiau laiko nei anksčiau, 792 00:35:41,747 --> 00:35:44,830 bet jei mes padarėme tai realiu laiku, mes pamatyti, kas takeaways bus. 793 00:35:44,830 --> 00:35:47,970 Dabar aš esu čia, teisė pusė dešinėje pusėje, 794 00:35:47,970 --> 00:35:50,170 leiskite man eiti į priekį ir rūšiuoti kairįjį pusę. 795 00:35:50,170 --> 00:35:51,482 Žingsnis į priekį, koks tavo vardas? 796 00:35:51,482 --> 00:35:52,190 PUBLIKA: Ramsey. 797 00:35:52,190 --> 00:35:53,210 GARSIAKALBIS: Ramsey dabar rūšiuojami. 798 00:35:53,210 --> 00:35:53,570 Koks tavo vardas? 799 00:35:53,570 --> 00:35:54,200 >> PUBLIKA: Marina. 800 00:35:54,200 --> 00:35:57,033 >> GARSIAKALBIS: Marina dabar surūšiuoti kaip gerai, jei vartojate vieną žingsnį į priekį. 801 00:35:57,033 --> 00:36:00,690 Pagrindinis žingsnis čia yra dabar sujungti, aš ketina skinti iš mano dviejų sąrašų, 802 00:36:00,690 --> 00:36:01,720 į kairę ir į dešinę. 803 00:36:01,720 --> 00:36:05,150 Penki ketina ateiti pirma, septyni ketina ateiti kitą. 804 00:36:05,150 --> 00:36:06,410 Ir vėl, tai yra tyčinis. 805 00:36:06,410 --> 00:36:08,535 Faktas, kad jie, atsižvelgiant žingsnius į priekį ir atgal 806 00:36:08,535 --> 00:36:12,997 reiškia atstovauti, kad mes negalime padaryti šį algoritmą vietoje taip pat lengvai 807 00:36:12,997 --> 00:36:15,830 kaip burbulas rūšiuoti ir atrankos rūšiuoti, ir įterpimo rūšiuoti, jei mes tiesiog 808 00:36:15,830 --> 00:36:16,960 nuolat Swapping žmonių. 809 00:36:16,960 --> 00:36:19,940 Aš tiesiog reikia rūšiuoti iš nulio popieriaus, kuris 810 00:36:19,940 --> 00:36:21,827 įdėti šie žmonės o aš susijungimas, 811 00:36:21,827 --> 00:36:23,410 ir tada aš galiu įdėti juos į vietą. 812 00:36:23,410 --> 00:36:27,260 Ir tai raktas, nes aš naudoju nauji ištekliai, erdvė, ne tik laiko. 813 00:36:27,260 --> 00:36:28,270 >> Gerai, tai yra nuostabu. 814 00:36:28,270 --> 00:36:32,050 Kairėje pusėje, rūšiuojamos, tiesa pusė rūšiuojami, kad dabar svarbiausias sujungimo žingsnis. 815 00:36:32,050 --> 00:36:33,450 Kaip aš sujungti tai? 816 00:36:33,450 --> 00:36:35,470 Taigi, jei jums sekti mano į kairę ranką ir dešinę ranką, 817 00:36:35,470 --> 00:36:38,930 Aš ruošiuosi atkreipti mano kairę ranką kairėje pusėje, mano dešinė 818 00:36:38,930 --> 00:36:42,680 dešinėje pusėje, ir dabar turiu nuspręsti, žingsnis po žingsnio, kurį galima sujungti į. 819 00:36:42,680 --> 00:36:44,650 Kas akivaizdžiai ateina pirmiausia? 820 00:36:44,650 --> 00:36:45,150 Taškų vienas. 821 00:36:45,150 --> 00:36:47,327 Taigi ateiti per čia čia mūsų Užrašinė. 822 00:36:47,327 --> 00:36:49,910 Taigi dabar numeris vienas ir pranešti ką aš daryti su mano dešinėje, 823 00:36:49,910 --> 00:36:54,152 Aš ruošiuosi perkelti savo vieną dešinėje perlipti atkreipti skaičių tris, 824 00:36:54,152 --> 00:36:55,860 ir dabar aš turiu padaryti Analogišką sprendimą. 825 00:36:55,860 --> 00:36:58,387 Ir iš tikrųjų stovėti teisę frontas Luko čia, jei galėtų, 826 00:36:58,387 --> 00:36:59,720 nes tai yra mūsų Užrašinė. 827 00:36:59,720 --> 00:37:00,610 Taigi, kas toliau? 828 00:37:00,610 --> 00:37:05,000 Mes turime Lk numeriu dviejų ar Chrisas numeriu trys. 829 00:37:05,000 --> 00:37:07,460 Akivaizdu Lukas, skaičius du, kad jūs čia. 830 00:37:07,460 --> 00:37:11,270 >> Bet mano kairė ranka dabar ketina būti padidinta atkreipti dėmesį į Darren, 831 00:37:11,270 --> 00:37:15,160 ir čia svarbiausia atimti su sujungti, aš nuolat daro tai, 832 00:37:15,160 --> 00:37:17,340 Žinoma, jei jums natūra iš sekti logika. 833 00:37:17,340 --> 00:37:19,670 Bet mano rankos niekada ketina eiti atgal, 834 00:37:19,670 --> 00:37:23,861 o tai reiškia, aš tik kada nors pereinant prie liko su mano sujungimo procesą, 835 00:37:23,861 --> 00:37:26,360 ir kad tai bus raktas į Mūsų analizė vos akimirką. 836 00:37:26,360 --> 00:37:27,859 >> Taigi dabar galime baigti šį sparčiai. 837 00:37:27,859 --> 00:37:31,650 Taigi trijų ateina šalia, tada keturių ateina šalia, 838 00:37:31,650 --> 00:37:38,750 ir dabar penkios ateina šalia, tada šešių, septyni, ir galiausiai aštuoni. 839 00:37:38,750 --> 00:37:42,960 Jaučia lėčiausiai algoritmas dar, bet ne, jei mes iš tikrųjų 840 00:37:42,960 --> 00:37:45,510 paleisti jį tos pačios rūšies laikrodis greičiu, taip 841 00:37:45,510 --> 00:37:48,106 kalbėti, su tos pačios tiksi laikrodis, kaip ir anksčiau. 842 00:37:48,106 --> 00:37:48,605 Kodėl? 843 00:37:48,605 --> 00:37:51,100 Na, Paimkime pažvelgti į galutinį rezultatą. 844 00:37:51,100 --> 00:37:56,990 >> Grįžkime per čia, leiskite man atsigriebti demonstraciją vizualiai 845 00:37:56,990 --> 00:37:59,030 kas mes ką tik padarė. 846 00:37:59,030 --> 00:38:06,110 Didinimas čia apie tai puslapis čia, pasakoja Firefox 847 00:38:06,110 --> 00:38:08,200 kad mes norime eilėje iki šiame langelyje, tegul 848 00:38:08,200 --> 00:38:11,260 pasakyti burbulas rūšiuoti, su kuria mes dabar gerai pažįstamas, 849 00:38:11,260 --> 00:38:14,130 pasirinkimas tarsi, kuris yra dar vienas gana paprastas vienas, 850 00:38:14,130 --> 00:38:18,250 ir dabar šiandien sujungti rūšiuoti, kuris bus mūsų kulminacinis pabaiga. 851 00:38:18,250 --> 00:38:21,530 Priežastis jis paėmė tiek daug ilgiau čia su žmonėmis ir man žodžiu yra 852 00:38:21,530 --> 00:38:23,480 žinoma, aš paaiškinti kiekvieną žingsnį. 853 00:38:23,480 --> 00:38:26,920 Bet jei jūs tiesiog atlikti tai, kas kaip mes padarėme burbulas rūšiuoti ir atranka 854 00:38:26,920 --> 00:38:30,890 Rūšiuoti ne tik vizualiai, laikrodis kiek daug efektyviau 855 00:38:30,890 --> 00:38:33,330 šis sverto pasidalijimas ir užkariauja 856 00:38:33,330 --> 00:38:39,150 gali būti, kai taikoma duomenų rinkinio ŠTAI net dydis aštuonių, tačiau net daug, 857 00:38:39,150 --> 00:38:39,970 daug didesni. 858 00:38:39,970 --> 00:38:44,585 Aš duodu jums sujungti rūšiuoti, šalia pusė šių kitų algoritmų. 859 00:38:44,585 --> 00:38:56,364 860 00:38:56,364 --> 00:38:58,530 Tai ketiname gauti skausmingas greitai ir pabaiga 861 00:38:58,530 --> 00:39:00,890 nėra labai kulminacinis, jie tiesiog baigti rūšiuojami. 862 00:39:00,890 --> 00:39:05,280 Bet svarbiausia atimti tai, kad Pažiūrėkite, kaip daug greičiau sujungti tarsi 863 00:39:05,280 --> 00:39:08,110 buvo, jei jūs manote, kad aš tiesiog rūšies Messing su jumis. 864 00:39:08,110 --> 00:39:13,100 Jei mes darome šį vieną galutinį laiką, Leiskite Perkrauti šį, grįžkime 865 00:39:13,100 --> 00:39:14,960 ir pasirinkite burbulas rūšiuoti, ir tik smūgių, 866 00:39:14,960 --> 00:39:17,330 tegul pasirinkti įterpimo Rūšiuoti, tiesiog gera priemonė. 867 00:39:17,330 --> 00:39:20,020 Ir šį kartą vėl tegul pasirinkti merge rūšiuoti ir tegul 868 00:39:20,020 --> 00:39:21,595 iš tikrųjų paleisti šias šalia. 869 00:39:21,595 --> 00:39:24,140 870 00:39:24,140 --> 00:39:26,930 >> Ir tai ne, iš tikrųjų, atsitiktinumas. 871 00:39:26,930 --> 00:39:31,140 Ką aš veiksmingai atlikti yra aš suskirstyti savo indėlį per pusę, vėlgi, 872 00:39:31,140 --> 00:39:32,240 ir vėl, ir vėl. 873 00:39:32,240 --> 00:39:35,590 Ir ten tik tiek daug kartų jūs galite padalinti savo indėlį į dvi dalis, į kairę 874 00:39:35,590 --> 00:39:36,240 ir į dešinę. 875 00:39:36,240 --> 00:39:39,425 Kas formulė, kad mes nuolat matome , kuris apibūdina padalijimą pusę 876 00:39:39,425 --> 00:39:41,050 vėl, ir vėl, ir vėl, ir vėl? 877 00:39:41,050 --> 00:39:41,890 >> PUBLIKA: Prisijungti n. 878 00:39:41,890 --> 00:39:42,760 >> GARSIAKALBIS: Prisijungti n. 879 00:39:42,760 --> 00:39:46,300 Bet ten yra vienas kitas svarbus žingsnis, Šis algoritmas yra ne prisijungti n žingsnių. 880 00:39:46,300 --> 00:39:48,992 Jei jis buvo prisijungti tik n žingsnių, mes būtume tą pačią problemą 881 00:39:48,992 --> 00:39:51,200 kaip ir anksčiau, kur mes negali būti Ar tikrai viskas rūšiuojami. 882 00:39:51,200 --> 00:39:54,480 Jūs turite minimaliai pažvelgti n elementų būti tikri, kad n elementai rūšiuojami, 883 00:39:54,480 --> 00:39:55,950 kitaip tai tikėjimo šuolis. 884 00:39:55,950 --> 00:39:59,810 >> Taigi, tai minimaliai žurnalas n priemonių, tačiau ką apie šio svarbaus sujungimo žingsnio 885 00:39:59,810 --> 00:40:04,370 kur aš susijungė mano kairė pusė ir teisė pusę ir ėjo per sceną? 886 00:40:04,370 --> 00:40:06,980 Kiek žingsnių yra tai, kad sujungti? 887 00:40:06,980 --> 00:40:10,150 Tai n, bet aš ne tik sujungti galutinį laiką. 888 00:40:10,150 --> 00:40:15,089 Dėl kiekvieno iš šių įdėtos į skambučius, ant kiekvieno tų įdėtos susilieja, aš vis dar rūšiuojami. 889 00:40:15,089 --> 00:40:18,380 Aš susijungė šiuos du vaikinai, tada šie du vaikinai, tada šie du vaikinai ir pan. 890 00:40:18,380 --> 00:40:19,955 >> Taigi aš sujungti vėl ir vėl. 891 00:40:19,955 --> 00:40:20,580 Kiek kartų? 892 00:40:20,580 --> 00:40:23,510 Taigi kiekvieną kartą, kai aš padalintas sąrašas per pusę, aš padariau suliejimą. 893 00:40:23,510 --> 00:40:25,460 Padalinkite sąrašą per pusę, padaryti suliejimą. 894 00:40:25,460 --> 00:40:28,570 Taigi, jei padalijus sąrašą galima padaryti log n kartų, 895 00:40:28,570 --> 00:40:33,880 ir sujungti galiausiai trunka n žingsnių, kas gali būti dabar viršutinė 896 00:40:33,880 --> 00:40:37,000 jungiasi į važiavimo laikas mūsų algoritmas? 897 00:40:37,000 --> 00:40:37,980 n log n. 898 00:40:37,980 --> 00:40:40,560 >> Ir iš tiesų, tai, ką mes pasiekėme čia. 899 00:40:40,560 --> 00:40:44,650 Taigi manote, kad pamatyti vizualiai šie trys dalykai paleisti greta 900 00:40:44,650 --> 00:40:47,930 yra n kvadratu nuo n kvadrato prieš n log n. 901 00:40:47,930 --> 00:40:51,010 Kuris iš esmės matysime, ne tik šiandien, bet ir ateityje, 902 00:40:51,010 --> 00:40:52,760 yra daug, daug greičiau. 903 00:40:52,760 --> 00:40:56,010 Plojimų šių vaikinai, Aš apdovanos juos streso kamuolius. 904 00:40:56,010 --> 00:41:00,260 Leiskite atidėti čia šiandien, ir matysime jus pirmadienį. 905 00:41:00,260 --> 00:41:02,255