1 00:00:00,000 --> 00:00:11,904 >> [Musiikkia] 2 00:00:11,904 --> 00:00:12,910 >> PROFESSORI: Selvﾃ､. 3 00:00:12,910 --> 00:00:16,730 Tﾃ､mﾃ､ on CS50 ja tﾃ､mﾃ､ on viikon lopussa kolme. 4 00:00:16,730 --> 00:00:20,230 Joten olemme tﾃ､ﾃ､llﾃ､ tﾃ､nﾃ､ﾃ､n, eikﾃ､ Sanders Teatteri, sen sijaan Weidner kirjasto. 5 00:00:20,230 --> 00:00:23,170 Jonka sisﾃ､llﾃ､ on studio tunnetaan Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 tai sanokaamme Studio H, tai on me say-- jos olet nauttinut ettﾃ､ vitsi, 7 00:00:28,310 --> 00:00:30,540 se on todella maasta luokkatoveri, Mark, verkossa, 8 00:00:30,540 --> 00:00:32,420 joka ehdotti niin paljon Twitterin kautta. 9 00:00:32,420 --> 00:00:34,270 Nyt mitﾃ､ viileﾃ､ noin tﾃ､ﾃ､llﾃ､ studiossa 10 00:00:34,270 --> 00:00:38,410 on ettﾃ､ olen ympﾃ､rﾃｶi Vihreiden seinﾃ､t, green screen tai chromakey, 11 00:00:38,410 --> 00:00:43,290 niin sanoakseni, mikﾃ､ tarkoittaa, ettﾃ､ CS50: n tuotanto joukkue, tietﾃ､mﾃ､ttﾃ､ minulle 12 00:00:43,290 --> 00:00:47,380 nyt voisi olla laskemisesta minua eniten kaikkialla maailmassa, 13 00:00:47,380 --> 00:00:48,660 parempaan tai huonompaan. 14 00:00:48,660 --> 00:00:51,800 >> Nyt mitﾃ､ on edessﾃ､, Harjoitus kaksi on teidﾃ､n kﾃ､sissﾃ､nne Tﾃ､llﾃ､ viikolla 15 00:00:51,800 --> 00:00:53,830 mutta Harjoitus kolme tulevalla viikolla, 16 00:00:53,830 --> 00:00:56,600 teidﾃ､t haastetaan kanssa ns peli 15, 17 00:00:56,600 --> 00:00:58,960 vanhan puolueen puolesta, ettﾃ､ saatat muistaa saaneen 18 00:00:58,960 --> 00:01:02,030 kuin lapsi, joka on koko joukko numeroita, jotka voivat liukua ylﾃｶs, alas, 19 00:01:02,030 --> 00:01:05,790 vasemmalle ja oikealle, ja siellﾃ､ on yksi aukko sisﾃ､llﾃ､ palapeli, johon voit 20 00:01:05,790 --> 00:01:07,840 voi todella liukua ne palapelin palaset. 21 00:01:07,840 --> 00:01:11,150 Lopulta saat tﾃ､mﾃ､n palapeli joissakin semi satunnaisessa jﾃ､rjestyksessﾃ､, 22 00:01:11,150 --> 00:01:12,940 ja tavoitteena on lajitella, ylhﾃ､ﾃ､ltﾃ､ alas, 23 00:01:12,940 --> 00:01:16,310 vasemmalta oikealle, yhdestﾃ､ koko matkan lﾃ､pi 15. 24 00:01:16,310 --> 00:01:19,360 >> Valitettavasti tﾃ､ytﾃ､ntﾃｶﾃｶnpano sinulla on kﾃ､sillﾃ､ 25 00:01:19,360 --> 00:01:21,590 tulee olemaan ohjelmisto pohjainen, ei fyysisesti. 26 00:01:21,590 --> 00:01:25,280 Olet todella tﾃ､ytyy kirjoittaa koodia, jotka opiskelija tai kﾃ､yttﾃ､jﾃ､ voi 27 00:01:25,280 --> 00:01:26,760 pelata peliﾃ､ 15. 28 00:01:26,760 --> 00:01:29,030 Ja itse asiassa hakkeri painos peli 15, 29 00:01:29,030 --> 00:01:32,155 sinun on haaste toteuttaa, ei vain pelaaminen tﾃ､mﾃ､n vanhan koulun 30 00:01:32,155 --> 00:01:35,010 peli, vaan ratkaiseminen siitﾃ､, tﾃ､ytﾃ､ntﾃｶﾃｶnpanon jumala tilassa 31 00:01:35,010 --> 00:01:38,280 niin sanoakseni, ettﾃ､ todella ratkaisee palapeli ihmisen, 32 00:01:38,280 --> 00:01:41,080 tarjoamalla heille vihje, jﾃ､lkeen vihje, kun vihje. 33 00:01:41,080 --> 00:01:42,280 Niin siitﾃ､ lisﾃ､ﾃ､ ensi viikolla. 34 00:01:42,280 --> 00:01:43,720 Mutta se, mitﾃ､ on edessﾃ､. 35 00:01:43,720 --> 00:01:47,610 >> Nyt muistaa, ettﾃ､ aiemmin tﾃ､llﾃ､ viikolla meillﾃ､ oli jﾃ､nnitysnﾃ､ytelmﾃ､, jos haluatte, 36 00:01:47,610 --> 00:01:52,560 jolloin paras teemme lajittelu viisas oli ylﾃ､rajana Big O n 37 00:01:52,560 --> 00:01:53,210 potenssiin. 38 00:01:53,210 --> 00:01:56,520 Toisin sanoen, kuplalajittelu, valinta lajitella, lisﾃ､yslajittelun, 39 00:01:56,520 --> 00:01:59,120 ne kaikki, kun taas eri niiden tﾃ､ytﾃ､ntﾃｶﾃｶnpanossa, 40 00:01:59,120 --> 00:02:03,480 siirretty osaksi n potenssiin kﾃ､ynnissﾃ､ aika hyvin pahimmassa tapauksessa. 41 00:02:03,480 --> 00:02:06,010 Ja me yleensﾃ､ olettaa, ettﾃ､ hyvin pahimmassa tapauksessa lajitteluun 42 00:02:06,010 --> 00:02:08,814 on yksi ettﾃ､ tuloa ovat tﾃ､ysin taaksepﾃ､in. 43 00:02:08,814 --> 00:02:11,980 Ja todellakin, se kesti aivan muutaman askeleen toteuttaa jokainen nﾃ､istﾃ､ algoritmeja. 44 00:02:11,980 --> 00:02:15,110 >> Nyt aivan lopussa luokan Recall, vertasimme kuplalajittelu 45 00:02:15,110 --> 00:02:19,390 vastaan 窶銀€久alinta lajitella vastaan 窶銀€及ksi muu ettﾃ､ kutsuimme yhdistﾃ､ﾃ､ lajitella tuolloin, 46 00:02:19,390 --> 00:02:22,120 ja ehdotan, ettﾃ､ se ottaa etuna oppitunti viikossa 47 00:02:22,120 --> 00:02:24,060 nolla, hajota ja hallitse. 48 00:02:24,060 --> 00:02:28,810 Ja jotenkin saavuttaa jonkinlaista logaritminen kﾃ､yntiaika lopulta, 49 00:02:28,810 --> 00:02:31,024 sijasta jotain se on puhtaasti asteen. 50 00:02:31,024 --> 00:02:33,440 Ja se ei ole aivan logaritminen, se on hieman enemmﾃ､n. 51 00:02:33,440 --> 00:02:36,520 Mutta jos muistatte luokasta, se oli paljon, paljon nopeammin. 52 00:02:36,520 --> 00:02:38,210 Katsotaanpa katsomaan mihin jﾃ､imme. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Kuplalajittelu vs. valinta lajitella vs. Yhdistﾃ､misen lajitella. 55 00:02:45,370 --> 00:02:47,700 Nyt he kaikki kﾃ､ynnissﾃ､, vuonna Teoriassa samaan aikaan. 56 00:02:47,700 --> 00:02:50,510 CPU on kﾃ､ynnissﾃ､ samalla nopeudella. 57 00:02:50,510 --> 00:02:54,990 Mutta voit tuntea kuinka tylsﾃ､ﾃ､ tﾃ､mﾃ､ on hyvin nopeasti tulossa, 58 00:02:54,990 --> 00:02:58,790 ja kuinka nopeasti, kun pistﾃ､ﾃ､ hiukan viikon nolla algoritmit, 59 00:02:58,790 --> 00:03:00,080 voimme nopeuttaa asioita. 60 00:03:00,080 --> 00:03:01,630 >> Joten merkki lajitella nﾃ､yttﾃ､ﾃ､ hﾃ､mmﾃ､styttﾃ､vﾃ､n. 61 00:03:01,630 --> 00:03:05,220 Miten voimme hyﾃｶdyntﾃ､ﾃ､ sitﾃ､, jotta lajitella numeroita nopeammin. 62 00:03:05,220 --> 00:03:07,140 No katsotaanpa muistelen ainesosaa ettﾃ､ me 63 00:03:07,140 --> 00:03:10,380 oli takaisin viikolla nolla, ettﾃ､ etsivﾃ､t joku puhelinluettelosta, 64 00:03:10,380 --> 00:03:12,380 ja muistuttaa, ettﾃ､ pseudokoodilla ettﾃ､ ehdotimme, 65 00:03:12,380 --> 00:03:14,560 jonka kautta voimme lﾃｶytﾃ､ﾃ､ joku kuten Mike Smith, 66 00:03:14,560 --> 00:03:16,310 nﾃ､ytti vﾃ､hﾃ､n jotain tﾃ､llaista. 67 00:03:16,310 --> 00:03:20,820 >> Nyt katsomaan erityisesti rivillﾃ､ 7 ja 8, ja 10 ja 11, 68 00:03:20,820 --> 00:03:25,240 joka aiheuttaa ettﾃ､ silmukka, jolloin pidimme menee takaisin linja 3 uudestaan, ja uudestaan, 69 00:03:25,240 --> 00:03:26,520 ja uudelleen. 70 00:03:26,520 --> 00:03:31,790 Mutta kﾃ､y ilmi, ettﾃ､ voimme katsella tﾃ､mﾃ､ algoritmi, tﾃ､ﾃ､llﾃ､ pseudokoodilla, 71 00:03:31,790 --> 00:03:33,620 hieman kokonaisvaltaisemmin. 72 00:03:33,620 --> 00:03:35,960 Itse asiassa, mitﾃ､ etsin klo tﾃ､ﾃ､llﾃ､ ruudulla, 73 00:03:35,960 --> 00:03:41,180 on algoritmi etsii Mike Smith joukossa joitakin joukko sivuja. 74 00:03:41,180 --> 00:03:45,520 Ja todellakin, voisimme yksinkertaistaa tﾃ､mﾃ､ algoritmi ne rivit 7 ja 8, 75 00:03:45,520 --> 00:03:49,860 ja 10 ja 11 vain sanoa, jonka olen esitetﾃ､ﾃ､n tﾃ､ssﾃ､ keltaisella. 76 00:03:49,860 --> 00:03:52,210 Toisin sanoen, jos Mike Smith on aiemmin kirja, 77 00:03:52,210 --> 00:03:55,004 meidﾃ､n ei tarvitse mﾃ､ﾃ､rittﾃ､ﾃ､ vaiheessa askeleelta nyt miten edetﾃ､ lﾃｶytﾃ､ﾃ､ hﾃ､net. 78 00:03:55,004 --> 00:03:56,920 Meillﾃ､ ei tarvitse mﾃ､ﾃ､ritellﾃ､ palata linja 3, 79 00:03:56,920 --> 00:03:58,960 Miksi emme vain sen sijaan, sanoa yleisemmin, 80 00:03:58,960 --> 00:04:01,500 etsi Mike vasen puoli kirjan. 81 00:04:01,500 --> 00:04:03,960 >> Toisaalta, jos Mike on todella myﾃｶhemmin kirjan, 82 00:04:03,960 --> 00:04:07,540 miksi emme vain lainata lainaus haku Mike oikeassa puoliskossa kirjan. 83 00:04:07,540 --> 00:04:11,030 Toisin sanoen, miksi emme vain tavallaan punt itsellemme sanomalla, 84 00:04:11,030 --> 00:04:13,130 etsi Mike tﾃ､ssﾃ､ osajoukko kirjan, 85 00:04:13,130 --> 00:04:16,279 ja jﾃ､ttﾃ､ﾃ､ sen nykyisiﾃ､ algoritmi kertoa meille 86 00:04:16,279 --> 00:04:18,750 miten etsiﾃ､ Mike ettﾃ､ vasen puoli kirjan. 87 00:04:18,750 --> 00:04:20,750 Toisin sanoen, meidﾃ､n algoritmi toimii onko se 88 00:04:20,750 --> 00:04:24,670 puhelinluettelo tﾃ､mﾃ､n paksuus, tﾃ､mﾃ､n paksuus, tai paksuus lainkaan. 89 00:04:24,670 --> 00:04:27,826 Joten voimme rekursiivisesti mﾃ､ﾃ､ritellﾃ､ tﾃ､mﾃ､ algoritmi. 90 00:04:27,826 --> 00:04:29,950 Toisin sanoen, on nﾃ､yttﾃｶ tﾃ､ﾃ､llﾃ､, on algoritmi 91 00:04:29,950 --> 00:04:33,130 etsimiseen Mike Smith keskuudessa sivut puhelinluettelosta. 92 00:04:33,130 --> 00:04:37,410 Joten rivi 7 ja 10, katsotaanpa vain sanoa juuri sitﾃ､. 93 00:04:37,410 --> 00:04:40,250 Ja kﾃ､ytﾃ､n tﾃ､tﾃ､ termiﾃ､ hetki sitten, ja todellakin, rekursio 94 00:04:40,250 --> 00:04:42,450 on muotisana nyt, ja se on tﾃ､mﾃ､n prosessin 95 00:04:42,450 --> 00:04:47,210 tehdﾃ､ jotain syklistﾃ､ jotenkin koodia kﾃ､yttﾃ､mﾃ､llﾃ､ ettﾃ､ sinulla jo on, 96 00:04:47,210 --> 00:04:49,722 ja kutsuen sitﾃ､ uudelleen, ja uudestaan, ja uudestaan. 97 00:04:49,722 --> 00:04:51,930 Nyt se tulee olemaan tﾃ､rkeﾃ､ ettﾃ､ me jotenkin pohja 98 00:04:51,930 --> 00:04:53,821 pois, ja ﾃ､lﾃ､ tee sitﾃ､ ﾃ､ﾃ､rettﾃｶmﾃ､n pitkﾃ､. 99 00:04:53,821 --> 00:04:56,070 Muuten aiomme on todellakin pﾃ､ﾃ､ttymﾃ､ttﾃｶmﾃ､ﾃ､n silmukkaan. 100 00:04:56,070 --> 00:04:59,810 Mutta katsotaan jos voimme lainata tﾃ､tﾃ､ ajatusta rekursiivisen, tehdﾃ､ jotain uudelleen 101 00:04:59,810 --> 00:05:03,600 ja uudestaan 窶銀€桔a uudestaan, ratkaista lajittelu ongelma kautta yhdistﾃ､misen 102 00:05:03,600 --> 00:05:05,900 lajitella, kaikki tehokkaammin. 103 00:05:05,900 --> 00:05:06,970 >> Joten annan sinulle yhdistﾃ､ﾃ､ lajitella. 104 00:05:06,970 --> 00:05:07,920 Katsotaanpa katsomaan. 105 00:05:07,920 --> 00:05:10,850 Joten tﾃ､ssﾃ､ on pseudokoodilla, kanssa jotka voisimme toteuttaa lajittelu, 106 00:05:10,850 --> 00:05:12,640 Kﾃ､yttﾃ､mﾃ､llﾃ､ tﾃ､tﾃ､ algoritmia kutsutaan yhdistﾃ､misen lajitella. 107 00:05:12,640 --> 00:05:13,880 Ja se on yksinkertaisesti tﾃ､mﾃ､. 108 00:05:13,880 --> 00:05:15,940 Syﾃｶtteellﾃ､ n alkion, Toisin sanoen, jos olet 109 00:05:15,940 --> 00:05:18,830 annettuja n elementtejﾃ､ ja numeroita ja kirjaimia tai mikﾃ､ tulo on, 110 00:05:18,830 --> 00:05:22,430 jos olet antanut n elementtiﾃ､, jos n on pienempi kuin 2, palaa. 111 00:05:22,430 --> 00:05:22,930 Oikea? 112 00:05:22,930 --> 00:05:26,430 Koska jos n on pienempi kuin 2, ettﾃ､ tarkoittaa, ettﾃ､ minun luettelo elementtien 113 00:05:26,430 --> 00:05:30,446 on joko kokoa 0 tai 1, ja sekﾃ､ nﾃ､issﾃ､ triviaaleja tapauksissa 114 00:05:30,446 --> 00:05:31,570 luettelo on jo jﾃ､rjestetty. 115 00:05:31,570 --> 00:05:32,810 Jos ei ole luettelossa, se on jﾃ､rjestetty. 116 00:05:32,810 --> 00:05:35,185 Ja jos on lista pituus 1, se on tietenkin jﾃ､rjestetty. 117 00:05:35,185 --> 00:05:38,280 Joten algoritmi tarvitsee vain todella jotain mielenkiintoista, 118 00:05:38,280 --> 00:05:40,870 jos meillﾃ､ on kaksi tai useampia elementtejﾃ､ meille annettu. 119 00:05:40,870 --> 00:05:42,440 Joten katsokaamme taika sitten. 120 00:05:42,440 --> 00:05:47,500 Else jﾃ､rjestellﾃ､ vasemmalla puolella elementtejﾃ､, sitten lajitella oikealla puolella elementtejﾃ､, 121 00:05:47,500 --> 00:05:49,640 sitten yhdistﾃ､ﾃ､ lajiteltu puolikkaat. 122 00:05:49,640 --> 00:05:52,440 Ja mikﾃ､ on tavallaan mielen taivutus tﾃ､ﾃ､llﾃ､, on ettﾃ､ en ole oikeastaan 123 00:05:52,440 --> 00:05:56,190 nﾃ､yttﾃ､vﾃ､t mﾃ､ﾃ､rﾃ､nnyt mitﾃ､ﾃ､n ihan vielﾃ､, eikﾃｶ? 124 00:05:56,190 --> 00:05:59,560 Kaikki Olen sanonut on, annetaan luettelo n elementtiﾃ､, lajitella vasen puoli, 125 00:05:59,560 --> 00:06:01,800 sitten oikea puoli, sitten yhdistﾃ､ﾃ､ lajiteltu puolikkaat, 126 00:06:01,800 --> 00:06:03,840 mutta missﾃ､ on todellinen salainen kastike? 127 00:06:03,840 --> 00:06:05,260 Missﾃ､ algoritmi? 128 00:06:05,260 --> 00:06:09,150 No nﾃ､yttﾃ､ﾃ､ siltﾃ､, 窶銀€菊ttﾃ､ nﾃ､mﾃ､ kaksi riviﾃ､ ensimmﾃ､inen, erﾃ､ﾃ､nlainen vasen puoli elementtejﾃ､, 129 00:06:09,150 --> 00:06:13,970 ja tavallaan oikea puoli elementtejﾃ､, ovat rekursiokutsua, niin sanoakseni. 130 00:06:13,970 --> 00:06:16,120 >> Onhan tﾃ､ssﾃ､ vaiheessa, minulla on 131 00:06:16,120 --> 00:06:18,950 algoritmi, jolla voidaan lajitella koko joukko tekijﾃｶitﾃ､? 132 00:06:18,950 --> 00:06:19,450 Kyllﾃ､. 133 00:06:19,450 --> 00:06:20,620 Se on tﾃ､ﾃ､llﾃ､. 134 00:06:20,620 --> 00:06:25,180 Se on tﾃ､ﾃ､llﾃ､ ruudulla, ja joten voin kﾃ､yttﾃ､ﾃ､, ettﾃ､ samoja vaiheita 135 00:06:25,180 --> 00:06:28,500 lajitella vasen puoli, kuin voin oikea puoli. 136 00:06:28,500 --> 00:06:30,420 Ja todellakin, uudestaan, ja uudestaan. 137 00:06:30,420 --> 00:06:34,210 Joten tavalla tai toisella, ja me pian nﾃ､hdﾃ､ tﾃ､mﾃ､n, taika yhdistﾃ､misen sort 138 00:06:34,210 --> 00:06:37,967 on upotettu ettﾃ､ hyvin lopullisessa linja, yhdistﾃ､mﾃ､llﾃ､ lajitellut puoliskot. 139 00:06:37,967 --> 00:06:39,300 Ja joka tuntuu melko intuitiivinen. 140 00:06:39,300 --> 00:06:41,050 Otat kaksi puoliskoa, ja te, jotenkin, yhdistﾃ､ﾃ､ ne yhteen, 141 00:06:41,050 --> 00:06:43,260 ja nﾃ､emme tﾃ､mﾃ､n konkreettisesti hetki. 142 00:06:43,260 --> 00:06:45,080 >> Mutta tﾃ､mﾃ､ on tﾃ､ydellinen algoritmi. 143 00:06:45,080 --> 00:06:46,640 Ja nyt nﾃ､hdﾃ､ tarkalleen miksi. 144 00:06:46,640 --> 00:06:50,912 No olettaa, ettﾃ､ meille annetaan nﾃ､mﾃ､ samat kahdeksan elementtejﾃ､ tﾃ､ssﾃ､ ruudulla, yksi 145 00:06:50,912 --> 00:06:53,120 kautta kahdeksan, mutta ne ovat nﾃ､ennﾃ､isen satunnaisessa jﾃ､rjestyksessﾃ､. 146 00:06:53,120 --> 00:06:55,320 Ja tavoite kﾃ､sillﾃ､ on lajitella nﾃ､mﾃ､ elementit. 147 00:06:55,320 --> 00:06:58,280 No miten voin mennﾃ､ noin tekee sen avulla, jﾃ､lleen, 148 00:06:58,280 --> 00:07:00,407 yhdistﾃ､ﾃ､ lajitella, kuten per tﾃ､mﾃ､ pseudokoodina? 149 00:07:00,407 --> 00:07:02,740 Ja vielﾃ､, ingrain tﾃ､mﾃ､ mielesi, vain hetken. 150 00:07:02,740 --> 00:07:05,270 Ensimmﾃ､inen tapaus on melko triviaali, jos se on vﾃ､hemmﾃ､n kuin 2, 151 00:07:05,270 --> 00:07:07,060 vain palata, ei ole tehtﾃ､vﾃ､ﾃ､. 152 00:07:07,060 --> 00:07:09,290 Joten oikeastaan 窶銀€虐iellﾃ､ on vain kolme toimet todella pitﾃ､ﾃ､ mielessﾃ､. 153 00:07:09,290 --> 00:07:11,081 Jﾃ､lleen ja jﾃ､lleen, olen menossa haluavat olla 154 00:07:11,081 --> 00:07:13,980 lajitella vasen puoli, lajitella oikea puoli, 155 00:07:13,980 --> 00:07:15,890 ja sitten kun niiden kaksi puolikasta lajitellaan, 156 00:07:15,890 --> 00:07:18,710 Haluan yhdistﾃ､ﾃ､ ne yhteen yhdeksi lajiteltu lista. 157 00:07:18,710 --> 00:07:19,940 Niin pitﾃ､ﾃ､ tﾃ､mﾃ､ mielessﾃ､. 158 00:07:19,940 --> 00:07:21,310 >> Joten tﾃ､ssﾃ､ alkuperﾃ､isen luettelon. 159 00:07:21,310 --> 00:07:23,510 Katsotaanpa kﾃ､sittelemﾃ､ﾃ､n tﾃ､tﾃ､ array, kun aloimme 160 00:07:23,510 --> 00:07:25,800 viikolla kaksi, joka on yhtenﾃ､inen alue muistia. 161 00:07:25,800 --> 00:07:28,480 Tﾃ､ssﾃ､ tapauksessa, joka sisﾃ､ltﾃ､ﾃ､ kahdeksan numeroita, takaisin takaisin takaisin. 162 00:07:28,480 --> 00:07:30,700 Ja lﾃ､hdetﾃ､ﾃ､n nyt sovelletaan yhdistﾃ､misen lajitella. 163 00:07:30,700 --> 00:07:33,300 Joten Haluan ensin lajitella vasen puoli tﾃ､mﾃ､n luettelon, 164 00:07:33,300 --> 00:07:37,370 ja nyt, siksi, keskittyvﾃ､t 4, 8, 6, ja 2. 165 00:07:37,370 --> 00:07:41,000 >> Nyt miten voin mennﾃ､ noin lajittelun luettelo koko 4? 166 00:07:41,000 --> 00:07:45,990 No minun tﾃ､ytyy nyt harkita lajittelu vasemmalla vasemmalla puolella. 167 00:07:45,990 --> 00:07:47,720 Jﾃ､lleen, nyt kelata vain hetken. 168 00:07:47,720 --> 00:07:51,010 Jos pseudokoodi on tﾃ､mﾃ､, ja olen antanut kahdeksan elementtejﾃ､, 169 00:07:51,010 --> 00:07:53,230 8 on ilmeisesti suurempi kuin tai yhtﾃ､ suuri kuin 2. 170 00:07:53,230 --> 00:07:54,980 Joten ensimmﾃ､inen tapaus ei koske. 171 00:07:54,980 --> 00:07:58,120 Joten lajitella kahdeksan elementtejﾃ､, haluan ensin lajitella vasemmalla puolella elementtejﾃ､, 172 00:07:58,120 --> 00:08:01,930 sitten lajitella oikea puoli, sitten yhdistﾃ､ﾃ､ kaksi lajitellut puolikkaat, kukin koko 4. 173 00:08:01,930 --> 00:08:02,470 OK. 174 00:08:02,470 --> 00:08:07,480 >> Mutta jos olet juuri kertonut minulle, lajitella vasen puoli, joka on nyt on koko 4, 175 00:08:07,480 --> 00:08:09,350 miten voin lajitella vasen puoli? 176 00:08:09,350 --> 00:08:11,430 No jos minulla on tuloon neljﾃ､ elementtiﾃ､, 177 00:08:11,430 --> 00:08:14,590 Haluan ensin lajitella vasemmalle kaksi, sitten oikea kaksi, 178 00:08:14,590 --> 00:08:16,210 ja sitten yhdistﾃ､ﾃ､ ne yhteen. 179 00:08:16,210 --> 00:08:18,700 Niin uudelleen, se tulee hieman of mielen taivutus peli tﾃ､ﾃ､llﾃ､, 180 00:08:18,700 --> 00:08:21,450 koska te, tavallaan, on muistaa missﾃ､ olet tarina, 181 00:08:21,450 --> 00:08:23,620 mutta loppujen lopuksi, antanut mitﾃ､ﾃ､n useita tekijﾃｶitﾃ､, 182 00:08:23,620 --> 00:08:25,620 ensin haluat lajitella vasen puoli, sitten oikea puoli, 183 00:08:25,620 --> 00:08:26,661 sitten yhdistﾃ､ﾃ､ ne yhteen. 184 00:08:26,661 --> 00:08:28,630 Aloitetaan juuri siihen. 185 00:08:28,630 --> 00:08:30,170 Tﾃ､ssﾃ､ panos kahdeksan elementtejﾃ､. 186 00:08:30,170 --> 00:08:31,910 Nyt me tarkastelemme vasen puoli tﾃ､ﾃ､llﾃ､. 187 00:08:31,910 --> 00:08:33,720 Miten lajitella neljﾃ､ elementtiﾃ､? 188 00:08:33,720 --> 00:08:35,610 No ensin lajitella vasemmalle puolen. 189 00:08:35,610 --> 00:08:37,720 Nyt miten voin lajitella vasen puoli? 190 00:08:37,720 --> 00:08:39,419 No Olen saanut kaksi elementtiﾃ､. 191 00:08:39,419 --> 00:08:41,240 Joten jﾃ､rjestﾃ､ﾃ､ kaksi elementtiﾃ､. 192 00:08:41,240 --> 00:08:44,540 2 on suurempi tai vastaa 2, tietenkin. 193 00:08:44,540 --> 00:08:46,170 Niin ettﾃ､ ensimmﾃ､inen tapaus ei koske. 194 00:08:46,170 --> 00:08:49,010 >> Joten minulla on nyt lajitella vasemmalle puolet nﾃ､istﾃ､ kahdesta elementistﾃ､. 195 00:08:49,010 --> 00:08:50,870 Vasen puoli, tietenkin, on vain 4. 196 00:08:50,870 --> 00:08:54,020 Joten miten voin lajitella luettelon yhden elementin? 197 00:08:54,020 --> 00:08:57,960 No nyt, ettﾃ､ erityistﾃ､ perustapaus ylﾃｶs, niin sanotusti, sovelletaan. 198 00:08:57,960 --> 00:09:01,470 1 on pienempi kuin 2, ja minun luettelo on todellakin koko 1. 199 00:09:01,470 --> 00:09:02,747 Joten en juuri palata. 200 00:09:02,747 --> 00:09:03,580 En tee mitﾃ､ﾃ､n. 201 00:09:03,580 --> 00:09:06,770 Ja todellakin, katso mitﾃ､ olen tehty, 4 on jo jﾃ､rjestetty. 202 00:09:06,770 --> 00:09:09,220 Kuten olen jo osittain onnistunut tﾃ､ssﾃ､. 203 00:09:09,220 --> 00:09:11,750 >> Nyt nﾃ､yttﾃ､ﾃ､ typerﾃ､ﾃ､ vaatia, mutta se on totta. 204 00:09:11,750 --> 00:09:13,700 4 on luettelo koko 1. 205 00:09:13,700 --> 00:09:15,090 Se on jo jﾃ､rjestetty. 206 00:09:15,090 --> 00:09:16,270 Se vasen puoli. 207 00:09:16,270 --> 00:09:18,010 Nyt minﾃ､ lajitella oikea puoli. 208 00:09:18,010 --> 00:09:22,310 Minun panos on yksi elementti, 8 Samoin jo jﾃ､rjestetty. 209 00:09:22,310 --> 00:09:25,170 Tyhmﾃ､, liian, mutta jﾃ､lleen, tﾃ､mﾃ､ perusperiaate 210 00:09:25,170 --> 00:09:28,310 aikoo jotta voimme nyt rakentaa pﾃ､ﾃ､lle tﾃ､mﾃ､n onnistuneesti. 211 00:09:28,310 --> 00:09:32,260 4 lajiteltu, 8 lajitellaan, nyt mikﾃ､ oli viimeinen askel? 212 00:09:32,260 --> 00:09:35,330 Niin kolmas ja viimeinen vaihe, mikﾃ､ tahansa kerran olet lajittelun lista, muistaa, 213 00:09:35,330 --> 00:09:38,310 oli yhdistﾃ､ﾃ､ kaksi puolikasta, vasemmalle ja oikealle. 214 00:09:38,310 --> 00:09:39,900 Joten juuri siihen. 215 00:09:39,900 --> 00:09:41,940 Minun vasen puoli on tietenkin, 4. 216 00:09:41,940 --> 00:09:43,310 Minun oikea puoli on 8. 217 00:09:43,310 --> 00:09:44,100 >> Joten tehdﾃ､ﾃ､n tﾃ､mﾃ､. 218 00:09:44,100 --> 00:09:46,410 Ensinnﾃ､kin aion jakaa jotkut lisﾃ､muistia, 219 00:09:46,410 --> 00:09:48,680 ettﾃ､ minﾃ､ tﾃ､ﾃ､llﾃ､ edustan, koska vain toissijainen array, 220 00:09:48,680 --> 00:09:49,660 joka on iso mahtuakseen tﾃ､hﾃ､n. 221 00:09:49,660 --> 00:09:52,243 Mutta voit kuvitella jatkamisesta ettﾃ､ suorakulmion koko pituudeltaan, 222 00:09:52,243 --> 00:09:53,290 jos tarvitsemme lisﾃ､ﾃ､ myﾃｶhemmin. 223 00:09:53,290 --> 00:09:58,440 Miten otan 4 ja 8, ja yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi luetteloa koko 1 yhdessﾃ､? 224 00:09:58,440 --> 00:10:00,270 Tﾃ､ssﾃ､kin melko yksinkertainen. 225 00:10:00,270 --> 00:10:03,300 4 tulee ensin, sitten tulee 8. 226 00:10:03,300 --> 00:10:07,130 Koska jos haluan lajitella vasen puoli, sitten oikea puoli, 227 00:10:07,130 --> 00:10:09,900 ja sitten yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi puolikasta yhdessﾃ､, lajiteltu jﾃ､rjestyksessﾃ､, 228 00:10:09,900 --> 00:10:11,940 4 tulee ensin, sitten tulee 8. 229 00:10:11,940 --> 00:10:15,810 >> Joten nﾃ､ytﾃ､mme edistyy, vaikka vaikka en ole tehnyt mitﾃ､ﾃ､n varsinaista tyﾃｶtﾃ､. 230 00:10:15,810 --> 00:10:17,800 Mutta muista missﾃ､ olemme tarina. 231 00:10:17,800 --> 00:10:19,360 Olemme alunperin kesti kahdeksan elementtejﾃ､. 232 00:10:19,360 --> 00:10:21,480 Olemme jﾃ､rjestetty vasen puoli, joka on 4. 233 00:10:21,480 --> 00:10:24,450 Sitten lajitellaan vasen puoli vasemman puolen, mikﾃ､ oli 2. 234 00:10:24,450 --> 00:10:25,270 Ja tﾃ､ssﾃ､ sitﾃ､ mennﾃ､ﾃ､n. 235 00:10:25,270 --> 00:10:26,920 Olemme tehneet tﾃ､mﾃ､n askeleen. 236 00:10:26,920 --> 00:10:29,930 >> Joten jos olemme lajiteltu vasen puoli 2, nyt meillﾃ､ 237 00:10:29,930 --> 00:10:32,130 on lajitella oikea puoli 2. 238 00:10:32,130 --> 00:10:35,710 Joten oikea puoli 2 on nﾃ､mﾃ､ kaksi arvoa tﾃ､ﾃ､llﾃ､, 6 ja 2. 239 00:10:35,710 --> 00:10:40,620 Joten nyt ottaa panos koko 2, ja lajitella vasen puoli, ja sitten 240 00:10:40,620 --> 00:10:42,610 oikea puoli, ja sitten yhdistﾃ､ﾃ､ ne yhteen. 241 00:10:42,610 --> 00:10:45,722 No miten voin lajitella luettelon koko 1, joka sisﾃ､ltﾃ､ﾃ､ vain numero 6? 242 00:10:45,722 --> 00:10:46,430 Olen jo tehnyt. 243 00:10:46,430 --> 00:10:48,680 Ettﾃ､ luettelo koko 1 lajitellaan. 244 00:10:48,680 --> 00:10:52,140 >> Miten lajitella toinen luettelo koko 1, niin sanottu oikea puoli. 245 00:10:52,140 --> 00:10:54,690 No sekin on jo jﾃ､rjestetty. 246 00:10:54,690 --> 00:10:56,190 Numero 2 on yksin. 247 00:10:56,190 --> 00:11:00,160 Joten nyt minulla on kaksi puoliskoa, vasemmalle ja oikea, minun tﾃ､ytyy yhdistﾃ､ﾃ､ ne yhteen. 248 00:11:00,160 --> 00:11:01,800 Annan itselleni ylimﾃ､ﾃ､rﾃ､istﾃ､ tilaa. 249 00:11:01,800 --> 00:11:05,580 Ja laittaa 2 siellﾃ､, sitten 6 siellﾃ､, mikﾃ､ 250 00:11:05,580 --> 00:11:10,740 lajittelu ettﾃ､ luettelo, vasen ja oikea, ja yhdistﾃ､mﾃ､llﾃ､ se yhteen, lopulta. 251 00:11:10,740 --> 00:11:12,160 Joten olen hieman paremmassa kunnossa. 252 00:11:12,160 --> 00:11:16,250 En ole tehnyt, koska selvﾃ､sti 4, 8, 2, 6 ei ole lopullinen tilaus, ettﾃ､ haluan. 253 00:11:16,250 --> 00:11:20,640 Mutta Minulla on nyt kaksi luetteloa koko 2, ettﾃ､ ovat molemmat vastaavasti on lajiteltu. 254 00:11:20,640 --> 00:11:24,580 Joten nyt jos taaksepﾃ､in sielusi silmﾃ､, mistﾃ､ se jﾃ､ttﾃ､ﾃ､ meidﾃ､t? 255 00:11:24,580 --> 00:11:28,520 Aloitin kahdeksan elementtejﾃ､, niin minﾃ､ supistetaan se alas vasemmalla puolella 4, 256 00:11:28,520 --> 00:11:31,386 sitten vasen puoli 2, ja sitten oikea puoli 2, 257 00:11:31,386 --> 00:11:34,510 Lopetin, siis, lajittelu vasen puolet 2, ja oikea puoli 2, 258 00:11:34,510 --> 00:11:37,800 niin mitﾃ､ kolmas ja viimeinen vaihe tﾃ､ssﾃ､? 259 00:11:37,800 --> 00:11:41,290 Minun tﾃ､ytyy yhdistﾃ､ﾃ､ yhdessﾃ､ kaksi luetteloa koko 2. 260 00:11:41,290 --> 00:11:42,040 Joten mene eteenpﾃ､in. 261 00:11:42,040 --> 00:11:43,940 Ja ruudulla tﾃ､ﾃ､llﾃ､, antaa minulle lisﾃ､muistia, 262 00:11:43,940 --> 00:11:47,170 vaikka teknisesti, huomaa, ettﾃ､ olen sai koko joukko tyhjﾃ､ tila ylﾃｶs 263 00:11:47,170 --> 00:11:47,670 siellﾃ､. 264 00:11:47,670 --> 00:11:50,044 Jos haluan olla erityisen tehokkaasti tilaa viisas, 265 00:11:50,044 --> 00:11:52,960 Voisin vain alkaa liikkuvat osat edestakaisin, ylhﾃ､ﾃ､llﾃ､ ja alhaalla. 266 00:11:52,960 --> 00:11:55,460 Mutta vain visuaalinen selkeys, Aion laittaa se alas alla, 267 00:11:55,460 --> 00:11:56,800 pitﾃ､ﾃ､ asiat mukava ja puhdas. 268 00:11:56,800 --> 00:11:58,150 >> Joten minulla kaksi luetteloa koko 2. 269 00:11:58,150 --> 00:11:59,770 Ensimmﾃ､inen luettelo on 4 ja 8. 270 00:11:59,770 --> 00:12:01,500 Toisessa luettelossa on 2 ja 6. 271 00:12:01,500 --> 00:12:03,950 Katsotaanpa yhdistﾃ､ﾃ､ ne yhdessﾃ､ lajiteltu jﾃ､rjestyksessﾃ､. 272 00:12:03,950 --> 00:12:09,910 2, tietenkin, tulee ensin, sitten 4, sitten 6, sitten 8. 273 00:12:09,910 --> 00:12:12,560 Ja nyt me nﾃ､yttﾃ､vﾃ､t saada jonnekin mielenkiintoinen. 274 00:12:12,560 --> 00:12:15,720 Nyt olen lajiteltu puolet luetella, ja sattumalta, se on 275 00:12:15,720 --> 00:12:18,650 kaikki parilliset numerot, mutta ettﾃ､ on todellakin vain sattumaa. 276 00:12:18,650 --> 00:12:22,220 Ja nyt on lajiteltu vasen puoli, ettﾃ､ se on 2, 4, 6, ja 8. 277 00:12:22,220 --> 00:12:23,430 Mikﾃ､ﾃ､n ei ole epﾃ､kunnossa. 278 00:12:23,430 --> 00:12:24,620 Joka tuntuu edistystﾃ､. 279 00:12:24,620 --> 00:12:26,650 >> Nyt tuntuu kuin olisin puhuneet ikuisesti nyt, 280 00:12:26,650 --> 00:12:29,850 niin mitﾃ､ jﾃ､ﾃ､ nﾃ､htﾃ､vﾃ､ksi, jos tﾃ､mﾃ､ algoritmi on todellakin tehokkaampi. 281 00:12:29,850 --> 00:12:31,766 Mutta olemme menossa lﾃ､pi se erittﾃ､in jﾃ､rjestelmﾃ､llisesti. 282 00:12:31,766 --> 00:12:34,060 Tietokone, tietenkin, tekisi sen niin. 283 00:12:34,060 --> 00:12:34,840 Missﾃ､ siis olemme? 284 00:12:34,840 --> 00:12:36,180 Aloitimme kahdeksan elementtejﾃ､. 285 00:12:36,180 --> 00:12:37,840 Olen lajiteltu vasemmalla puolella 4. 286 00:12:37,840 --> 00:12:39,290 Nﾃ､ytﾃ､n tehdﾃ､ sen kanssa. 287 00:12:39,290 --> 00:12:42,535 Joten nyt seuraava askel on lajitella oikea puoli 4. 288 00:12:42,535 --> 00:12:44,410 Ja tﾃ､mﾃ､ osa voimme mennﾃ､ lﾃ､pi hieman enemmﾃ､n 289 00:12:44,410 --> 00:12:47,140 nopeasti, vaikka olet Tervetuloa kelata tai pysﾃ､yttﾃ､ﾃ､, vain 290 00:12:47,140 --> 00:12:49,910 ajatella sen lﾃ､pi omaan tahtiin, mutta mitﾃ､ 291 00:12:49,910 --> 00:12:53,290 meillﾃ､ nyt on tilaisuus tehdﾃ､ tﾃ､smﾃ､lleen samaa algoritmia neljﾃ､ﾃ､n 292 00:12:53,290 --> 00:12:54,380 eri numeroille. 293 00:12:54,380 --> 00:12:57,740 >> Joten mene eteenpﾃ､in, ja keskitytﾃ､ﾃ､n oikea puoli, jotka olemme tﾃ､ﾃ､llﾃ､. 294 00:12:57,740 --> 00:13:01,260 Vasen puoli on, ettﾃ､ oikea puoli, ja nyt 295 00:13:01,260 --> 00:13:04,560 vasen puoli vasemman puolet oikea puoli, 296 00:13:04,560 --> 00:13:08,030 ja miten lajitella luettelon koko 1, joka sisﾃ､lsi vain numero 1? 297 00:13:08,030 --> 00:13:09,030 Se on jo tehty. 298 00:13:09,030 --> 00:13:11,830 Miten teen sama lista koon 1, joka sisﾃ､ltﾃ､ﾃ､ vain 7? 299 00:13:11,830 --> 00:13:12,840 Se on jo tehty. 300 00:13:12,840 --> 00:13:16,790 Vaihe kolme tﾃ､hﾃ､n puoli sitten on yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi tekijﾃ､ﾃ､ 301 00:13:16,790 --> 00:13:20,889 uuteen luettelo koko 2, 1 ja 7. 302 00:13:20,889 --> 00:13:23,180 Eivﾃ､t nﾃ､ytﾃ､ tehneen kaikki ettﾃ､ paljon mielenkiintoista tyﾃｶtﾃ､. 303 00:13:23,180 --> 00:13:24,346 Katsotaan, mitﾃ､ tapahtuu seuraavaksi. 304 00:13:24,346 --> 00:13:29,210 Olen juuri jﾃ､rjestetty vasemmalla puolella oikea puoli minun alkuperﾃ､inen panos. 305 00:13:29,210 --> 00:13:32,360 Nyt lajitella oikealla puoli, joka sisﾃ､ltﾃ､ﾃ､ 5 ja 3. 306 00:13:32,360 --> 00:13:35,740 Katsotaanpa jﾃ､lleen katsoa vasemmalle puoli, lajiteltu, oikea puoli, lajiteltu, 307 00:13:35,740 --> 00:13:39,120 ja yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi yhdessﾃ､, johonkin lisﾃ､tilaa, 308 00:13:39,120 --> 00:13:41,670 3 tulee ensin, sitten tulee 5. 309 00:13:41,670 --> 00:13:46,190 Ja nyt olemme lajiteltu vasemmalla puolella oikea puoli 310 00:13:46,190 --> 00:13:49,420 alkuperﾃ､isen ongelman, ja oikea puoli oikea puoli 311 00:13:49,420 --> 00:13:50,800 alkuperﾃ､isen ongelman. 312 00:13:50,800 --> 00:13:52,480 Mikﾃ､ on kolmas ja viimeinen vaihe? 313 00:13:52,480 --> 00:13:54,854 Hyvin yhdistﾃ､ﾃ､ nﾃ､mﾃ､ kaksi puolikasta yhteen. 314 00:13:54,854 --> 00:13:57,020 Joten haluan saada itselleni lisﾃ､tilaa, mutta, jﾃ､lleen, minﾃ､ 315 00:13:57,020 --> 00:13:58,699 saattaa kﾃ､yttﾃ､ﾃ､, ettﾃ､ vapaata tilaa ylﾃｶs. 316 00:13:58,699 --> 00:14:00,490 Mutta aiomme pitﾃ､ﾃ､ se yksinkertainen visuaalisesti. 317 00:14:00,490 --> 00:14:07,070 Saanen sulautuvat nyt 1, ja sitten 3, ja sitten 5, ja sitten 7. 318 00:14:07,070 --> 00:14:10,740 Mikﾃ､ jﾃ､ttﾃ､ﾃ､ minua nyt oikeus puolet alkuperﾃ､isestﾃ､ ongelmasta 319 00:14:10,740 --> 00:14:12,840 joka on tﾃ､ydellisesti lajitellaan. 320 00:14:12,840 --> 00:14:13,662 >> Niin mitﾃ､ jﾃ､ﾃ､ jﾃ､ljelle? 321 00:14:13,662 --> 00:14:16,120 Tunnen pitﾃ､ﾃ､ sanoa samat asiat uudestaan, ja uudestaan, 322 00:14:16,120 --> 00:14:18,700 mutta se kuvastaa Se, ettﾃ､ kﾃ､ytﾃ､mme rekursion. 323 00:14:18,700 --> 00:14:21,050 Prosessi kﾃ､yttﾃ､ﾃ､ algoritmi uudestaan, ja uudestaan, 324 00:14:21,050 --> 00:14:23,940 pienempiin osajoukot alkuperﾃ､iseen ongelmaan. 325 00:14:23,940 --> 00:14:27,580 Joten minulla on nyt vasemmalle lajiteltu puolet alkuperﾃ､isestﾃ､ ongelmasta. 326 00:14:27,580 --> 00:14:30,847 Minulla on oikeus lajitellut puoli alkuperﾃ､isen ongelman. 327 00:14:30,847 --> 00:14:32,180 Mikﾃ､ on kolmas ja viimeinen vaihe? 328 00:14:32,180 --> 00:14:33,590 Voi, se on sulautuvat. 329 00:14:33,590 --> 00:14:34,480 Joten tehdﾃ､. 330 00:14:34,480 --> 00:14:36,420 Katsotaanpa jakaa joitakin uusia muisti, mutta luoja, me 331 00:14:36,420 --> 00:14:37,503 voisi laittaa sen minne nyt. 332 00:14:37,503 --> 00:14:40,356 Meillﾃ､ on niin paljon tilaa meille, mutta me pitﾃ､ﾃ､ se yksinkertainen. 333 00:14:40,356 --> 00:14:42,730 Sijaan menee takaisin ja esiin ja alkuperﾃ､istﾃ､ muistia, 334 00:14:42,730 --> 00:14:44,480 Haluan vain tehdﾃ､ se visuaalisesti tﾃ､ﾃ､llﾃ､ alla, 335 00:14:44,480 --> 00:14:47,240 loppuun asti sulautuvien vasen puoli ja oikea puoli. 336 00:14:47,240 --> 00:14:49,279 >> Joten yhdistﾃ､mﾃ､llﾃ､, mitﾃ､ minun pitﾃ､ﾃ､ tehdﾃ､? 337 00:14:49,279 --> 00:14:50,820 Haluan ottaa elementtejﾃ､ jﾃ､rjestyksessﾃ､. 338 00:14:50,820 --> 00:14:53,230 Joten etsit vasen puoli, Nﾃ､en ensimmﾃ､inen numero on 2. 339 00:14:53,230 --> 00:14:55,230 Katson oikea puoli, Nﾃ､en ensimmﾃ､inen numero 340 00:14:55,230 --> 00:14:58,290 on 1, niin ilmeisesti joka numero Haluanko nyppiﾃ､ pois, 341 00:14:58,290 --> 00:15:00,430 ja laittaa ensimmﾃ､inen minun lopullisen luettelon? 342 00:15:00,430 --> 00:15:01,449 Tietenkin, 1. 343 00:15:01,449 --> 00:15:02,990 Nyt haluan kysyﾃ､ saman kysymyksen. 344 00:15:02,990 --> 00:15:05,040 Vasemmalla puolella, olen silti saanut numero 2. 345 00:15:05,040 --> 00:15:07,490 Oikealla puoliskolla, Minulla numero 3. 346 00:15:07,490 --> 00:15:08,930 Kumpi minﾃ､ haluan valita? 347 00:15:08,930 --> 00:15:11,760 Tietenkin, numero 2 ja nyt huomaa ehdokkaat 348 00:15:11,760 --> 00:15:13,620 4 vasemmalla, 3 oikealla. 349 00:15:13,620 --> 00:15:15,020 Katsotaanpa, tietenkin, valitse 3. 350 00:15:15,020 --> 00:15:18,020 Nyt ehdokkaat ovat 4 vasemmalla, 5 oikealla. 351 00:15:18,020 --> 00:15:19,460 Me tietenkin valita 4. 352 00:15:19,460 --> 00:15:21,240 6 vasemmalla, 5 oikealla. 353 00:15:21,240 --> 00:15:22,730 Me tietenkin valita 5. 354 00:15:22,730 --> 00:15:25,020 6 vasemmalla, 7 oikealla. 355 00:15:25,020 --> 00:15:29,320 Valitsemme 6, ja sitten me valita 7, ja sitten pﾃ､ﾃ､tﾃ､mme 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Joten valtava mﾃ､ﾃ､rﾃ､ sanoja myﾃｶhemmin, me ovat lajiteltu tﾃ､mﾃ､ lista kahdeksan toiminnallisuutta 358 00:15:34,370 --> 00:15:38,450 listaan 窶銀€及hden kautta kahdeksan, joka on kasvaa jokaisessa vaiheessa, 359 00:15:38,450 --> 00:15:40,850 mutta kuinka paljon aikaa ja teki se vie meidﾃ､t siihen. 360 00:15:40,850 --> 00:15:43,190 No Olen tarkoituksella laid asioita kuvallisesti 361 00:15:43,190 --> 00:15:46,330 tﾃ､ﾃ､llﾃ､, jotta voimme tavallaan nﾃ､hdﾃ､ tai arvostaa divisioona 362 00:15:46,330 --> 00:15:49,060 valloittavat ettﾃ､ on tapahtunut. 363 00:15:49,060 --> 00:15:52,830 >> Todellakin jos muistella vanavedessﾃ､, Olen jﾃ､ttﾃ､nyt kaikki nﾃ､mﾃ､ pisteviivoilla 364 00:15:52,830 --> 00:15:55,660 paikallaan haltijoille, voit, sellainen, katso, pﾃ､invastaisessa jﾃ､rjestyksessﾃ､, 365 00:15:55,660 --> 00:15:58,800 jos sellainen muistella historia nyt, minun alkuperﾃ､inen lista 366 00:15:58,800 --> 00:16:00,250 on, tietenkin, koon 8. 367 00:16:00,250 --> 00:16:03,480 Ja sitten aikaisemmin, olin kﾃ､sittelevﾃ､t kaksi luetteloa koko 4, 368 00:16:03,480 --> 00:16:08,400 ja sitten neljﾃ､ luettelot koko 2, ja sitten kahdeksan luettelot koko 1. 369 00:16:08,400 --> 00:16:10,151 >> Mitﾃ､ tﾃ､mﾃ､, sellainen, muistuttaa teitﾃ､? 370 00:16:10,151 --> 00:16:11,858 Hyvin, itse asiassa, mitﾃ､ tahansa algoritmit olemme 371 00:16:11,858 --> 00:16:14,430 Katsoin toistaiseksi jossa jakaa, ja jakaa, ja jakaa, 372 00:16:14,430 --> 00:16:19,500 pitﾃ､ﾃ､ ottaa asioita uudelleen, ja jﾃ､lleen, johtaa tﾃ､mﾃ､ yleinen ajatus. 373 00:16:19,500 --> 00:16:23,100 Ja niin siellﾃ､ on jotain logaritminen tekeillﾃ､. 374 00:16:23,100 --> 00:16:26,790 Ja se ei ole aivan loki n, mutta siellﾃ､ on logaritminen komponentti 375 00:16:26,790 --> 00:16:28,280 mitﾃ､ olemme juuri tehneet. 376 00:16:28,280 --> 00:16:31,570 >> Nyt pohtia, miten se todella on. 377 00:16:31,570 --> 00:16:34,481 Joten log n, taas oli suuri kﾃ､yntiaika, 378 00:16:34,481 --> 00:16:36,980 kun teimme jotain binﾃ､ﾃ､rihakupuu, kuten me nyt kutsumme sitﾃ､, 379 00:16:36,980 --> 00:16:40,090 hajota ja hallitse strategia jonka kautta lﾃｶysimme Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Nyt teknisesti. 381 00:16:41,020 --> 00:16:43,640 Se on log pohja 2 n, jopa vaikka useimmissa matematiikka luokissa, 382 00:16:43,640 --> 00:16:45,770 10 on yleensﾃ､ pohja ettﾃ､ oletat. 383 00:16:45,770 --> 00:16:48,940 Mutta tietotekniikan tutkijoita lﾃ､hes aina ajatella ja puhutaan pohja 2, 384 00:16:48,940 --> 00:16:52,569 joten me yleensﾃ､ vain sanoa loki n, sen sijaan, ettﾃ､ tukin pohjaan 2 n, 385 00:16:52,569 --> 00:16:55,110 mutta ne ovat tﾃ､smﾃ､lleen yksi ja Sama maailmassa tietokone 386 00:16:55,110 --> 00:16:57,234 tiede, ja syrjﾃ､ﾃ､n, on jatkuva tekijﾃ､ 387 00:16:57,234 --> 00:17:01,070 Ero nﾃ､iden kahden vﾃ､lillﾃ､, joten se on kiistanalainen joka tapauksessa, enemmﾃ､n muodollista syistﾃ､. 388 00:17:01,070 --> 00:17:04,520 >> Mutta nyt, mitﾃ､ me vﾃ､litﾃ､mme Tietoja on tﾃ､ssﾃ､ esimerkissﾃ､. 389 00:17:04,520 --> 00:17:08,520 Joten ei osoittaa esimerkkiﾃ､, mutta Ainakin kﾃ､yttﾃ､ﾃ､ esimerkiksi numeroita 390 00:17:08,520 --> 00:17:10,730 kﾃ､sillﾃ､ jﾃ､rki tarkistaa, jos haluatte. 391 00:17:10,730 --> 00:17:14,510 Joten aiemmin kaava oli log pohja 2 n, mutta mikﾃ､ on n tﾃ､ssﾃ､ asiassa. 392 00:17:14,510 --> 00:17:18,526 Minulla oli n alkuperﾃ､inen numeroita tai 8 Alkuperﾃ､isen numero erityisesti. 393 00:17:18,526 --> 00:17:20,359 Nyt se on ollut hieman vaikka, mutta olen melko 394 00:17:20,359 --> 00:17:25,300 Varmista, ettﾃ､ log pohja 2 arvo 8 on 3, 395 00:17:25,300 --> 00:17:29,630 ja todellakin, mitﾃ､ kiva siitﾃ､ on ettﾃ､ 3 on juuri monta kertaa 396 00:17:29,630 --> 00:17:33,320 ettﾃ､ voit jakaa lista pituuden 8 uudestaan, ja uudestaan, 397 00:17:33,320 --> 00:17:36,160 ja uudelleen, kunnes olet jﾃ､ﾃ､nyt luettelot vain koko 1. 398 00:17:36,160 --> 00:17:36,660 Oikea? 399 00:17:36,660 --> 00:17:40,790 8 menee 4, menee 2, menee 1, ja se on 400 00:17:40,790 --> 00:17:43,470 heijastava nimenomaan kyseisen kuva meillﾃ､ oli vain hetki sitten. 401 00:17:43,470 --> 00:17:47,160 Niin vﾃ､hﾃ､n jﾃ､rki tarkistaa, missﾃ､ logaritmi on todella mukana. 402 00:17:47,160 --> 00:17:50,180 >> Joten nyt, mitﾃ､ muuta on mukana tﾃ､ssﾃ､? n. 403 00:17:50,180 --> 00:17:53,440 Niin huomaa, ettﾃ､ jokainen kerta kun jakaa luettelon, 404 00:17:53,440 --> 00:17:58,260 vaikkakin kﾃ､ﾃ､nteisessﾃ､ jﾃ､rjestyksessﾃ､ historiassa tﾃ､ﾃ､llﾃ､, olin vielﾃ､ tekemﾃ､ssﾃ､ n asioita. 405 00:17:58,260 --> 00:18:02,320 Ettﾃ､ sulautuvan vaihe edellytti, ettﾃ､ Kosketan jokainen numeroita, 406 00:18:02,320 --> 00:18:05,060 jotta tyﾃｶnnﾃ､ se sen sopivaan paikkaan. 407 00:18:05,060 --> 00:18:10,760 Joten vaikka korkeus tﾃ､mﾃ､n kaavio on koko lokin n n tai 3, 408 00:18:10,760 --> 00:18:13,860 Erityisesti, toisin sanoen, Tein kolme divisioonaa tﾃ､ﾃ､llﾃ､. 409 00:18:13,860 --> 00:18:18,800 Kuinka paljon tyﾃｶtﾃ､ minﾃ､ tein vaakasuunnassa pitkin tﾃ､mﾃ､ kaavio joka kerta? 410 00:18:18,800 --> 00:18:21,110 >> No, tein n vaiheet tyﾃｶtﾃ､, koska jos olen 411 00:18:21,110 --> 00:18:24,080 sai neljﾃ､ elementit ja neljﾃ､ elementtiﾃ､, ja minun tﾃ､ytyy yhdistﾃ､ﾃ､ ne yhteen. 412 00:18:24,080 --> 00:18:26,040 Minun tﾃ､ytyy mennﾃ､ lﾃ､pi nﾃ､mﾃ､ neljﾃ､ ja nﾃ､mﾃ､ neljﾃ､, 413 00:18:26,040 --> 00:18:28,123 lopulta yhdistﾃ､ﾃ､ ne takaisin kahdeksan elementtejﾃ､. 414 00:18:28,123 --> 00:18:32,182 Jos pﾃ､invastoin Minulla kahdeksan sormea tﾃ､nne, jota en ole, ja kahdeksan 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry--, jos olen sai neljﾃ､ sormea 窶銀€逆ﾃ､nne, 416 00:18:34,390 --> 00:18:37,380 jota en, neljﾃ､ sormea tﾃ､nne, jota en, 417 00:18:37,380 --> 00:18:40,590 niin se sama Esimerkiksi kuten ennenkin, jos en 418 00:18:40,590 --> 00:18:44,010 on kahdeksan sormea 窶銀€久aikka yhteensﾃ､, jota voin, sellainen, do. 419 00:18:44,010 --> 00:18:47,950 Voin tarkalleen tehdﾃ､ tﾃ､ﾃ､llﾃ､, Sitten voin varmasti 420 00:18:47,950 --> 00:18:50,370 yhdistﾃ､ﾃ､ kaikki nﾃ､mﾃ､ luettelot on koko 1 yhdessﾃ､. 421 00:18:50,370 --> 00:18:54,050 Mutta en todellakaan tarvitse katsoa kunkin alkion tasan kerran. 422 00:18:54,050 --> 00:18:59,640 Joten korkeus tﾃ､mﾃ､ prosessi on loki n, leveys tﾃ､mﾃ､n prosessin, niin sanoakseni, 423 00:18:59,640 --> 00:19:02,490 on n, niin mitﾃ､ me nﾃ､ytﾃ､mme on, lopulta, on 424 00:19:02,490 --> 00:19:06,470 ajoaika koko n kertaa log n. 425 00:19:06,470 --> 00:19:08,977 >> Toisin sanoen, jaoimme lista, log n kertaa, 426 00:19:08,977 --> 00:19:11,810 mutta joka kerta teimme ettﾃ､ meillﾃ､ oli koskettaa jokainen elementtien 427 00:19:11,810 --> 00:19:13,560 jotta yhdistﾃ､ﾃ､ ne kaikki yhdessﾃ､, jotka 428 00:19:13,560 --> 00:19:18,120 oli n kappaletta askel, joten meillﾃ､ on n kertaa log n, tai tietojenkﾃ､sittelytieteessﾃ､ sanoisi, 429 00:19:18,120 --> 00:19:20,380 asymptoottisesti, joka olisi iso sana 430 00:19:20,380 --> 00:19:22,810 kuvaamaan ylempﾃ､ﾃ､n sidottu aika, 431 00:19:22,810 --> 00:19:28,010 meillﾃ､ on kﾃ､ynnissﾃ､ iso O log n aikaa, niin sanoakseni. 432 00:19:28,010 --> 00:19:31,510 >> Nyt tﾃ､mﾃ､ on merkittﾃ､vﾃ､, koska muistaa, mitﾃ､ kﾃ､ynnissﾃ､ ajat olivat 433 00:19:31,510 --> 00:19:34,120 kupla lajitella, ja valinta lajitella, ja lisﾃ､yslajittelun, 434 00:19:34,120 --> 00:19:38,200 ja jopa muutamia muita olemassa, n potenssiin oli kun olimme. 435 00:19:38,200 --> 00:19:39,990 Ja voit, tavallaan, katso tﾃ､ﾃ､llﾃ､. 436 00:19:39,990 --> 00:19:45,720 Jos n potenssiin on selvﾃ､sti n kertaa n, mutta tﾃ､ﾃ､llﾃ､ meillﾃ､ on n kertaa log n, 437 00:19:45,720 --> 00:19:48,770 ja tiedﾃ､mme jo viikko nolla, ettﾃ､ log n, logaritminen, 438 00:19:48,770 --> 00:19:50,550 on parempi kuin jotain lineaarinen. 439 00:19:50,550 --> 00:19:52,930 Onhan muistaa kuva kanssa punainen ja keltainen 440 00:19:52,930 --> 00:19:56,500 ja vihreﾃ､t viivat ettﾃ､ me kiinnitti, vihreﾃ､ logaritminen linja oli paljon pienempi. 441 00:19:56,500 --> 00:20:00,920 Ja siksi, paljon paremmin ja nopeammin kuin suora keltainen ja punainen linjat, 442 00:20:00,920 --> 00:20:05,900 n kertaa log n on todellakin parempi kuin n kertaa n, tai n neliﾃｶ. 443 00:20:05,900 --> 00:20:09,110 >> Joten meillﾃ､ nﾃ､yttﾃ､ﾃ､ tunnistettu algoritmi yhdistﾃ､misen 444 00:20:09,110 --> 00:20:11,870 lajitella, joka toimii paljon lyhyemmﾃ､n ajan, ja todellakin, 445 00:20:11,870 --> 00:20:16,560 siksi, aiemmin tﾃ､llﾃ､ viikolla, kun nﾃ､imme ettﾃ､ kilpailun vﾃ､lillﾃ､ kupla 446 00:20:16,560 --> 00:20:20,750 lajitella, valinta lajitella, ja yhdistﾃ､ﾃ､ lajitella, yhdistﾃ､minen lajitella todella, todella voitti. 447 00:20:20,750 --> 00:20:23,660 Ja todellakin, emme edes odota varten kuplalajittelu ja valinta lajitella 448 00:20:23,660 --> 00:20:24,790 saada valmiiksi. 449 00:20:24,790 --> 00:20:27,410 >> Nyt ottaa yksi muu syﾃｶttﾃｶ tﾃ､ssﾃ､, mistﾃ､ hieman 450 00:20:27,410 --> 00:20:31,030 muodollinen nﾃ､kﾃｶkulmasta, vain tapauksessa tﾃ､mﾃ､ resonoi paremmin 451 00:20:31,030 --> 00:20:33,380 kuin tﾃ､mﾃ､n korkeamman tason keskustelu. 452 00:20:33,380 --> 00:20:34,880 Joten tﾃ､ssﾃ､ on algoritmi uudelleen. 453 00:20:34,880 --> 00:20:36,770 Katsotaanpa kysyﾃ､ itseltﾃ､mme, mitﾃ､ kﾃ､yntiaika 454 00:20:36,770 --> 00:20:39,287 on tﾃ､mﾃ､n algoritmit eri vaiheet? 455 00:20:39,287 --> 00:20:41,620 Katsotaanpa se jaetaan ensimmﾃ､iseen tapaus ja toisessa tapauksessa. 456 00:20:41,620 --> 00:20:46,280 IF ja muu IF tapauksessa, Jos N on pienempi kuin 2, palaa. 457 00:20:46,280 --> 00:20:47,580 Tuntuu vakio aikaa. 458 00:20:47,580 --> 00:20:50,970 Se on, tavallaan, kuten kahdessa vaiheessa, Jos n on pienempi kuin 2, palaa sitten. 459 00:20:50,970 --> 00:20:54,580 Mutta kuten sanoi maanantaina, vakio aikaa, tai Big O 1, 460 00:20:54,580 --> 00:20:57,130 voi olla kahdessa vaiheessa, kolme vaiheet, jopa 1000 askelta. 461 00:20:57,130 --> 00:20:59,870 Tﾃ､rkeintﾃ､ on, ettﾃ､ se on jatkuva useita vaiheita. 462 00:20:59,870 --> 00:21:03,240 Joten keltainen korostettu pseudokoodina tﾃ､ﾃ､llﾃ､ toimii, me kutsumme sitﾃ､, 463 00:21:03,240 --> 00:21:04,490 vakio aikaa. 464 00:21:04,490 --> 00:21:06,780 Joten enemmﾃ､n virallisesti, ja aiomme to-- tﾃ､mﾃ､ 465 00:21:06,780 --> 00:21:09,910 on se, missﾃ､ mﾃ､ﾃ､rin me virallistaa tﾃ､mﾃ､n oikeuden now-- T n, 466 00:21:09,910 --> 00:21:15,030 ajoaika ongelma joka vie n somethings syﾃｶtteenﾃ､ 467 00:21:15,030 --> 00:21:19,150 Yhtﾃ､ suuri O yhden, Jos n on pienempi kuin 2. 468 00:21:19,150 --> 00:21:20,640 Joten on edellytyksenﾃ､, ettﾃ､. 469 00:21:20,640 --> 00:21:24,150 Joten olla selkeﾃ､, jos n on pienempi kuin 2, meillﾃ､ on hyvin lyhyt lista, sitten 470 00:21:24,150 --> 00:21:29,151 ajoaika, T, n, missﾃ､ n on 1 tai 0, tﾃ､ssﾃ､ hyvin erityinen tapaus, 471 00:21:29,151 --> 00:21:30,650 se vain tulee olemaan vakio aikaa. 472 00:21:30,650 --> 00:21:32,691 Se tulee ottaa yksi vaihe, kaksi vaihetta riippumatta. 473 00:21:32,691 --> 00:21:33,950 Se on kiinteﾃ､ useita vaiheita. 474 00:21:33,950 --> 00:21:38,840 >> Niin mehukas osa on varmasti vuonna Toisessa tapauksessa vuonna pseudokoodina. 475 00:21:38,840 --> 00:21:40,220 ELSE tapaus. 476 00:21:40,220 --> 00:21:44,870 Lajittele vasemmalla puolella elementtejﾃ､, lajitella oikea puolet elementtejﾃ､, yhdistﾃ､ﾃ､ lajiteltu puolikkaat. 477 00:21:44,870 --> 00:21:46,800 Kuinka kauan kukin nﾃ､istﾃ､ askeleensa? 478 00:21:46,800 --> 00:21:49,780 No, jos kﾃ､ynnissﾃ､ aika lajitella n elementtiﾃ､ 479 00:21:49,780 --> 00:21:53,010 on, kutsukaamme sitﾃ､ hyvin yleisesti, T, n, 480 00:21:53,010 --> 00:21:55,500 sitten lajittelu vasen puolet elementit 481 00:21:55,500 --> 00:21:59,720 on, tavallaan, kuin sanoisi, T n jaettuna 2, 482 00:21:59,720 --> 00:22:03,000 ja samoin lajittelu oikea puoli elementtejﾃ､ on, sellainen, kuin sanoisi, 483 00:22:03,000 --> 00:22:06,974 T n jaettu 2, ja sitten yhdistﾃ､mﾃ､llﾃ､ lajiteltu puolikkaat. 484 00:22:06,974 --> 00:22:08,890 No jos minulla joitakin alkioiden lukumﾃ､ﾃ､rﾃ､ tﾃ､ﾃ､llﾃ､, 485 00:22:08,890 --> 00:22:11,230 kuten neljﾃ､, ja jotkut numero elementtejﾃ､ tﾃ､ﾃ､llﾃ､, kuten neljﾃ､, 486 00:22:11,230 --> 00:22:14,650 ja minun tﾃ､ytyy yhdistﾃ､ﾃ､ kuhunkin neljﾃ､ﾃ､n vuonna, ja jokainen nﾃ､istﾃ､ neljﾃ､, yksi 487 00:22:14,650 --> 00:22:17,160 toisensa jﾃ､lkeen siten, ettﾃ､ lopulta minulla on kahdeksan elementtejﾃ､. 488 00:22:17,160 --> 00:22:20,230 Tuntuu, ettﾃ､ on iso o n vaiheet? 489 00:22:20,230 --> 00:22:23,500 Jos Minulla n sormien ja kukin ne on tarkoitus sisﾃ､llyttﾃ､ﾃ､ paikalleen, 490 00:22:23,500 --> 00:22:25,270 se on kuin toinen n vaiheet. 491 00:22:25,270 --> 00:22:27,360 >> Joten todellakin formulaically, Voimme ilmaista tﾃ､mﾃ､n, 492 00:22:27,360 --> 00:22:29,960 vaikkakin hieman pelottavan aluksi silmﾃ､yksellﾃ､, mutta se on jotain 493 00:22:29,960 --> 00:22:31,600 ettﾃ､ kaappaa juuri tﾃ､tﾃ､ logiikkaa. 494 00:22:31,600 --> 00:22:35,710 Juokseva aika, T, n, jos n on suurempi tai yhtﾃ､ suuri kuin 2. 495 00:22:35,710 --> 00:22:42,500 Tﾃ､ssﾃ､ tapauksessa, MUUTEN tapauksessa on T n jaettuna 2, sekﾃ､ T N jaettuna 2, 496 00:22:42,500 --> 00:22:45,320 plus Big O n, jotkut lineaarinen useita vaiheita, 497 00:22:45,320 --> 00:22:51,630 ehkﾃ､ tﾃ､smﾃ､lleen n, ehkﾃ､ 2 kertaa n, mutta se on karkeasti, jotta n. 498 00:22:51,630 --> 00:22:54,060 Niin ettﾃ､ myﾃｶs, miten voimme ilmaista tﾃ､mﾃ､ formulaically. 499 00:22:54,060 --> 00:22:56,809 Nyt et tiedﾃ､ tﾃ､tﾃ､, ellei olet tallentanut sen mielessﾃ､si, 500 00:22:56,809 --> 00:22:58,710 tai etsiﾃ､ se takana oppikirja, joka 501 00:22:58,710 --> 00:23:00,501 saattaa olla hieman huijata arkki lopussa, 502 00:23:00,501 --> 00:23:03,940 mutta tﾃ､mﾃ､ on todellakin menossa antaa meille iso O n log n, 503 00:23:03,940 --> 00:23:06,620 koska toistumisen ettﾃ､ nﾃ､ette tﾃ､ﾃ､llﾃ､ ruudulla, 504 00:23:06,620 --> 00:23:09,550 jos todella teki sen ulos, kanssa ﾃ､ﾃ､retﾃｶn mﾃ､ﾃ､rﾃ､ esimerkkejﾃ､, 505 00:23:09,550 --> 00:23:13,000 tai teit sen formulaically, olisit nﾃ､hdﾃ､, ettﾃ､ tﾃ､mﾃ､, koska tﾃ､mﾃ､ kaava 506 00:23:13,000 --> 00:23:17,100 itsessﾃ､ﾃ､n on rekursiivinen, jossa t n yli jotain oikealla, 507 00:23:17,100 --> 00:23:21,680 ja t N yli vasemmalla, tﾃ､mﾃ､ voi todella ilmaistava, lopulta, 508 00:23:21,680 --> 00:23:24,339 niin suuri irti n log n. 509 00:23:24,339 --> 00:23:26,130 Jos ei vakuuttunut, ettﾃ､ on hieno nyt, vain 510 00:23:26,130 --> 00:23:28,960 ottaa uskossa, ettﾃ､ se on todellakin, mitﾃ､ se toistuminen johtaa, 511 00:23:28,960 --> 00:23:31,780 mutta tﾃ､mﾃ､ on vain hieman enemmﾃ､n matemaattinen lﾃ､hestymistapa nﾃ､kﾃｶinen 512 00:23:31,780 --> 00:23:36,520 klo ajoaika yhdistﾃ､misen sort perustuvat sen pseudokoodilla yksin. 513 00:23:36,520 --> 00:23:39,030 >> Nyt kestﾃ､ﾃ､ vﾃ､hﾃ､n hengﾃ､hdystauon kaiken tﾃ､mﾃ､n, 514 00:23:39,030 --> 00:23:41,710 ja katsomaan tiettyjﾃ､ entinen senaattori, joka 515 00:23:41,710 --> 00:23:44,260 saattaa nﾃ､yttﾃ､ﾃ､ hieman tuttu, joka istui Googlen Eric 516 00:23:44,260 --> 00:23:48,410 Schmidt, jokin aika sitten, haastatteluun lavalla, edessﾃ､ koko joukko 517 00:23:48,410 --> 00:23:53,710 ihmiset, puhuvat lopulta noin aihe, joka on aika nyt tuttu. 518 00:23:53,710 --> 00:23:54,575 Katsotaanpa katsomaan. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Nyt senaattori, olet tﾃ､ﾃ､llﾃ､ Googlessa, 521 00:24:03,890 --> 00:24:09,490 ja haluan ajatella puheenjohtajuudesta tyﾃｶhaastattelu. 522 00:24:09,490 --> 00:24:11,712 Nyt on vaikea saada tyﾃｶtﾃ､ presidenttinﾃ､. 523 00:24:11,712 --> 00:24:12,670 Presidentti Obama: Oikea. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: Ja olet aikoo tehdﾃ､ [kuulumattomiin] nyt. 525 00:24:13,940 --> 00:24:15,523 On myﾃｶs vaikea saada tyﾃｶtﾃ､ Google. 526 00:24:15,523 --> 00:24:17,700 Presidentti Obama: Oikea. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Meillﾃ､ on kysymyksiﾃ､, ja pyydﾃ､mme ehdokkaita kysymyksiﾃ､, 528 00:24:21,330 --> 00:24:24,310 ja tﾃ､mﾃ､ yksi on Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> Presidentti Obama: OK. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Mitﾃ､? 531 00:24:27,005 --> 00:24:28,130 Te ajatella olen tosissasi? 532 00:24:28,130 --> 00:24:30,590 Se on tﾃ､ﾃ､llﾃ､. 533 00:24:30,590 --> 00:24:33,490 Mikﾃ､ on tehokkain tapa lajitella miljoona 32 bittisiﾃ､ kokonaislukuja? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> Presidentti Obama: Well-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Joskus ehkﾃ､ olen pahoillani, maybe-- 537 00:24:41,020 --> 00:24:42,750 Presidentti Obama: Ei, ei, ei, ei, ei, minﾃ､ think-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: Se ei ole it-- 539 00:24:43,240 --> 00:24:45,430 Presidentti Obama: I ajatella, mielestﾃ､ni kupla 540 00:24:45,430 --> 00:24:46,875 lajitella olisi vﾃ､ﾃ､rﾃ､ tapa edetﾃ､. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Tule. 543 00:24:50,535 --> 00:24:52,200 Jotka kertoivat hﾃ､nelle tﾃ､mﾃ､n? 544 00:24:52,200 --> 00:24:54,020 OK. 545 00:24:54,020 --> 00:24:55,590 En tietojenkﾃ､sittelytieteen on-- 546 00:24:55,590 --> 00:24:58,986 >> Presidentti Obama: Olemme saimme vakoojia siellﾃ､. 547 00:24:58,986 --> 00:24:59,860 PROFESSORI: Selvﾃ､. 548 00:24:59,860 --> 00:25:03,370 Jﾃ､tetﾃ､ﾃ､n taaksemme nyt teoreettinen maailma algoritmien 549 00:25:03,370 --> 00:25:06,520 vuonna asymptoottinen analyysi sen, ja palata joitakin aiheita 550 00:25:06,520 --> 00:25:09,940 viikosta nolla ja yksi, ja alku poistaa joitakin apupyﾃｶrﾃ､t, 551 00:25:09,940 --> 00:25:10,450 jos haluatte. 552 00:25:10,450 --> 00:25:13,241 Niin ettﾃ､ te todella ymmﾃ､rtﾃ､ﾃ､ lopulta maasta ylﾃｶs, mitﾃ､ 553 00:25:13,241 --> 00:25:16,805 meneillﾃ､ﾃ､n alla huppu, kun kirjoittaa, kﾃ､ﾃ､ntﾃ､ﾃ､, ja suorittaa ohjelmia. 554 00:25:16,805 --> 00:25:19,680 Recall erityisesti, ettﾃ､ tﾃ､mﾃ､ oli ensimmﾃ､inen C-ohjelma me katsoimme, 555 00:25:19,680 --> 00:25:22,840 Canonical, yksinkertainen ohjelma tapaisena suhteellisesti 556 00:25:22,840 --> 00:25:24,620 jolloin se tulostaa, Hello World. 557 00:25:24,620 --> 00:25:27,610 Ja muistaa, ettﾃ､ minﾃ､ sanoin, prosessi ettﾃ､ lﾃ､hdekoodi menee lﾃ､pi 558 00:25:27,610 --> 00:25:28,430 on juuri tﾃ､mﾃ､. 559 00:25:28,430 --> 00:25:31,180 Otat lﾃ､hdekoodia, siirtﾃ､ﾃ､ se lﾃ､pi kﾃ､ﾃ､ntﾃ､jﾃ､, kuten kalahtaa, 560 00:25:31,180 --> 00:25:34,650 ja ulos tulee kohdekoodin, ettﾃ､ voisi nﾃ､yttﾃ､ﾃ､ tﾃ､ltﾃ､, nollia ja ykkﾃｶsiﾃ､ 561 00:25:34,650 --> 00:25:37,880 ettﾃ､ tietokoneen prosessoria, keskeinen kﾃ､sittely-yksikﾃｶn tai aivoissa, 562 00:25:37,880 --> 00:25:39,760 lopulta ymmﾃ､rtﾃ､ﾃ､. 563 00:25:39,760 --> 00:25:42,460 >> On kﾃ､ynyt ilmi, ettﾃ､ se on vﾃ､hﾃ､n yksinkertaistamista, 564 00:25:42,460 --> 00:25:44,480 ettﾃ､ olemme nyt kanta kiusanhenki toisistaan 565 00:25:44,480 --> 00:25:46,720 ymmﾃ､rtﾃ､ﾃ､, mitﾃ､ on todella ollut meneillﾃ､ﾃ､n alla huppu 566 00:25:46,720 --> 00:25:48,600 aina kﾃ､yttﾃ､ﾃ､ Sointi, tai yleisemmin, 567 00:25:48,600 --> 00:25:53,040 aina kun teet ohjelmaa, kﾃ､yttﾃ､mﾃ､llﾃ､ Tee ja CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Erityisesti tavaraa kuten tﾃ､mﾃ､ on ensin luotu, 569 00:25:56,760 --> 00:25:58,684 kun ensin kﾃ､ﾃ､ntﾃ､ﾃ､ ohjelma. 570 00:25:58,684 --> 00:26:00,600 Toisin sanoen, kun ota lﾃ､hdekoodi 571 00:26:00,600 --> 00:26:04,390 ja kﾃ､ﾃ､ntﾃ､ﾃ､ se, mikﾃ､ on ensimmﾃ､inen on ulostulevien kalahtaa 572 00:26:04,390 --> 00:26:06,370 on jotain tunnetaan kokoonpano koodi. 573 00:26:06,370 --> 00:26:08,990 Ja itse asiassa se nﾃ､yttﾃ､ﾃ､ tﾃ､smﾃ､lleen samalta kuin tﾃ､mﾃ､. 574 00:26:08,990 --> 00:26:11,170 >> Juoksin komento komentoriviltﾃ､ aikaisemmin. 575 00:26:11,170 --> 00:26:16,260 Kalahtaa viiva pﾃ､ﾃ､oma s hello.c, ja tﾃ､mﾃ､ loi tiedosto 576 00:26:16,260 --> 00:26:19,490 minulle kutsutaan hello.s, jonka sisﾃ､llﾃ､ olivat tﾃ､smﾃ､lleen 577 00:26:19,490 --> 00:26:22,290 nﾃ､itﾃ､ pitoisuuksia, ja hieman enemmﾃ､n ylﾃ､puolella ja hieman alle, 578 00:26:22,290 --> 00:26:25,080 mutta olen koonnut juiciest tietoa tﾃ､ﾃ､ltﾃ､ ruudulla. 579 00:26:25,080 --> 00:26:29,190 Ja jos katsot tarkkaan, nﾃ､et ainakin muutamia tuttuja avainsanoja. 580 00:26:29,190 --> 00:26:31,330 Olemme tﾃ､rkein ylhﾃ､ﾃ､llﾃ､. 581 00:26:31,330 --> 00:26:35,140 Olemme printf alas keskellﾃ､. 582 00:26:35,140 --> 00:26:38,670 Ja meillﾃ､ on myﾃｶs Hello World kenoviiva n lainausmerkkeihin alhaalla. 583 00:26:38,670 --> 00:26:42,450 >> Ja kaikki muu tﾃ､ﾃ､llﾃ､ on hyvin alhainen ohjeet 584 00:26:42,450 --> 00:26:45,500 ettﾃ､ tietokoneen prosessoria ymmﾃ､rtﾃ､ﾃ､. 585 00:26:45,500 --> 00:26:50,090 CPU ohjeet, jotka liikkuvat muisti ympﾃ､ri, jonka painon jouset muistista, 586 00:26:50,090 --> 00:26:52,750 ja lopulta, tulostaa asiat nﾃ､ytﾃｶltﾃ､. 587 00:26:52,750 --> 00:26:56,780 Nyt mitﾃ､ tapahtuu vaikka jﾃ､lkeen tﾃ､mﾃ､ kokoonpano koodi luodaan? 588 00:26:56,780 --> 00:26:59,964 Lopulta teet, todellakin, silti tuottaa kohdekoodilla. 589 00:26:59,964 --> 00:27:02,630 Mutta toimenpiteet, jotka ovat todella jatkunut alla huppu 590 00:27:02,630 --> 00:27:04,180 nﾃ､yttﾃ､ﾃ､ hieman enemmﾃ､n kuin tﾃ､mﾃ､. 591 00:27:04,180 --> 00:27:08,390 Lﾃ､hdekoodi tulee kokoonpano koodi, joka sitten tulee kohdekoodin, 592 00:27:08,390 --> 00:27:11,930 ja operatiiviset sanat tﾃ､ssﾃ､ on ettﾃ､, kun kﾃ､ﾃ､nnﾃ､t lﾃ､hdekoodin, 593 00:27:11,930 --> 00:27:16,300 ulos tulee kokoonpano koodi, ja sitten kun Kokoa kokoonpano koodi, 594 00:27:16,300 --> 00:27:17,800 ulos tulee kohdekoodilla. 595 00:27:17,800 --> 00:27:20,360 >> Nyt kalahtaa on erittﾃ､in hienostunut, kuten paljon kerﾃ､ﾃ､jiﾃ､, 596 00:27:20,360 --> 00:27:23,151 ja se tekee kaikki nﾃ､mﾃ､ vaiheet yhdessﾃ､, ja se ei vﾃ､lttﾃ､mﾃ､ttﾃ､ 597 00:27:23,151 --> 00:27:25,360 ulostulo vﾃ､livaiheen tiedostoja, jotka voit jopa nﾃ､hdﾃ､. 598 00:27:25,360 --> 00:27:28,400 Se vain kokoaa asioita, joka on yleinen termi, joka 599 00:27:28,400 --> 00:27:30,000 kuvaa tﾃ､tﾃ､ koko prosessia. 600 00:27:30,000 --> 00:27:32,000 Mutta jos todella haluat olla erityisesti siellﾃ､ 601 00:27:32,000 --> 00:27:34,330 paljon enemmﾃ､n tekeillﾃ､ myﾃｶs siellﾃ､. 602 00:27:34,330 --> 00:27:38,860 >> Mutta katsotaanpa myﾃｶs katsovat nyt, ettﾃ､ jopa ettﾃ､ super yksinkertainen ohjelma, hello.c, 603 00:27:38,860 --> 00:27:40,540 kutsutaan toimintoa. 604 00:27:40,540 --> 00:27:41,870 Se kutsutaan printf. 605 00:27:41,870 --> 00:27:46,900 Mutta en kirjoita printf, todellakin, mukana C, niin sanoakseni. 606 00:27:46,900 --> 00:27:51,139 Se on toiminto muistaa, joka on ilmoitettu standardin io.h, joka 607 00:27:51,139 --> 00:27:53,180 on header-tiedosto, joka on aihe me oikeastaan 608 00:27:53,180 --> 00:27:55,780 sukeltaa perusteellisemmin ennen pitkﾃ､ﾃ､. 609 00:27:55,780 --> 00:27:58,000 Mutta otsikkotiedosto on tyypillisesti mukana 610 00:27:58,000 --> 00:28:02,920 koodilla tiedoston, lﾃ､hdekooditiedostoa, joten paljon kuin on olemassa standardi io.h. 611 00:28:02,920 --> 00:28:05,930 >> Joskus sitten, joku, tai jonkun, myﾃｶs kirjoitti 612 00:28:05,930 --> 00:28:11,040 tiedosto nimeltﾃ､ standardi io.c, vuonna jonka todellinen mﾃ､ﾃ､ritelmﾃ､t, 613 00:28:11,040 --> 00:28:15,220 tai toteutukset printf, ja rypﾃ､leterttuja muita toimintoja, 614 00:28:15,220 --> 00:28:16,870 todella kirjoitettu. 615 00:28:16,870 --> 00:28:22,140 Niin sillﾃ､, jos me harkita tﾃ､ﾃ､llﾃ､ vasemmalla, hello.c, ettﾃ､ kun 616 00:28:22,140 --> 00:28:26,250 koottu, antaa meille hello.s, vaikka Kalahtaa ei vaivaudu sﾃ､ﾃ､stﾃｶ paikka 617 00:28:26,250 --> 00:28:31,360 voimme nﾃ､hdﾃ､ sen, ja ettﾃ､ assembly saa kootaan hello.o, joka 618 00:28:31,360 --> 00:28:34,630 on todellakin oletusnimi annetaan aina kﾃ､ﾃ､nnﾃ､t lﾃ､hde 619 00:28:34,630 --> 00:28:39,350 koodi kohdekoodi, mutta eivﾃ､t aivan valmis suorittamaan sitﾃ､ vielﾃ､, 620 00:28:39,350 --> 00:28:41,460 koska toinen vaihe pitﾃ､ﾃ､ tapahtua, ja on 621 00:28:41,460 --> 00:28:44,440 on tapahtunut muutaman viime viikkoa, ehkﾃ､ tietﾃ､mﾃ､ttﾃ､ﾃ､n sinua. 622 00:28:44,440 --> 00:28:47,290 >> Erityisesti jonnekin vuonna CS50 IDE, ja tﾃ､mﾃ､, 623 00:28:47,290 --> 00:28:49,870 Myﾃｶs, on vﾃ､hﾃ､n yksinkertaistava hetkeksi, 624 00:28:49,870 --> 00:28:54,670 siellﾃ､ on, tai oli upon a time, tiedosto nimeltﾃ､ standardi io.c, 625 00:28:54,670 --> 00:28:58,440 ettﾃ､ joku kﾃ､ﾃ､nnetty standardi io.s tai vastaava, 626 00:28:58,440 --> 00:29:02,010 ettﾃ､ joku sitten koottu standardiin io.o, 627 00:29:02,010 --> 00:29:04,600 tai se kﾃ､ﾃ､ntyy ulos hieman erilainen tiedosto 628 00:29:04,600 --> 00:29:07,220 muodossa, joka voi olla erilainen tiedostopﾃ､ﾃ､te kokonaan, 629 00:29:07,220 --> 00:29:11,720 mutta teoriassa ja kﾃ､sitteellisesti, tﾃ､smﾃ､lleen nﾃ､mﾃ､ toimenpiteet tﾃ､ytyi tapahtua jossain muodossa. 630 00:29:11,720 --> 00:29:14,060 Joka on sanoa, ettﾃ､ nyt kun olen kirjallisesti ohjelma, 631 00:29:14,060 --> 00:29:17,870 hello.c, ettﾃ､ vain sanoo, Hello World, ja olen kﾃ､yttﾃ､en jonkun toisen koodi 632 00:29:17,870 --> 00:29:22,480 kuten printf, joka oli aikoinaan pﾃ､ﾃ､llﾃ､ aika, tiedostossa nimeltﾃ､ standardi io.c, 633 00:29:22,480 --> 00:29:26,390 sitten jotenkin minun on otettava minun kohdekoodi, minun nollia ja ykkﾃｶsiﾃ､, 634 00:29:26,390 --> 00:29:29,260 ja ettﾃ､ henkilﾃｶn esine koodi tai nollia ja ykkﾃｶsiﾃ､, 635 00:29:29,260 --> 00:29:34,970 ja jotenkin yhdistﾃ､ﾃ､ ne yksi lopullinen tiedosto, nimeltﾃ､ﾃ､n Hei, ettﾃ､ 636 00:29:34,970 --> 00:29:38,070 on kaikki nollia ja niistﾃ､ minun pﾃ､ﾃ､tehtﾃ､vﾃ､, 637 00:29:38,070 --> 00:29:40,830 ja kaikki nollia ja ne, printf. 638 00:29:40,830 --> 00:29:44,900 >> Ja todellakin, ettﾃ､ viime prosessi on nimeltﾃ､ﾃ､n, liitﾃ､t kohdekoodilla. 639 00:29:44,900 --> 00:29:47,490 Jonka lﾃ､htﾃｶ on suoritettava tiedosto. 640 00:29:47,490 --> 00:29:49,780 Joten tasapuolisuuden on pﾃ､ivﾃ､n pﾃ､ﾃ､tteeksi, ei mitﾃ､ﾃ､n 641 00:29:49,780 --> 00:29:52,660 on muuttunut viikolla yksi, kun aloitti kokoamiseen ohjelmia. 642 00:29:52,660 --> 00:29:55,200 Itse asiassa tﾃ､mﾃ､ kaikki on ollut tapahtuu alla huppu, 643 00:29:55,200 --> 00:29:57,241 mutta nyt olemme asemassa jossa voimme todella 644 00:29:57,241 --> 00:29:58,794 tease lisﾃ､ksi nﾃ､mﾃ､ eri vaiheet. 645 00:29:58,794 --> 00:30:00,710 Ja itse asiassa lopussa pﾃ､ivﾃ､, olemme yhﾃ､ 646 00:30:00,710 --> 00:30:04,480 jﾃ､ﾃ､ nollia ja ykkﾃｶsiﾃ､, joka on todella suuri segue nyt 647 00:30:04,480 --> 00:30:08,620 Toinen ominaisuus C, ettﾃ､ olemme ole tarvinnut hyﾃｶdyntﾃ､ﾃ､ todennﾃ､kﾃｶisesti 648 00:30:08,620 --> 00:30:11,250 Tﾃ､hﾃ､n mennessﾃ､ tunnetaan bittioperaatioiden. 649 00:30:11,250 --> 00:30:15,220 Toisin sanoen, toistaiseksi, milloin olemme Puhuttiin tietojen C tai muuttujiin C, 650 00:30:15,220 --> 00:30:17,660 meillﾃ､ on ollut asioita, kuten merkkiﾃ､ ja kellukkeet ja laajennukset 651 00:30:17,660 --> 00:30:21,990 ja pitkﾃ､t ja kaksinkertaistuu ja vastaavat, mutta kaikki nﾃ､mﾃ､ ovat vﾃ､hintﾃ､ﾃ､n kahdeksan bittiﾃ､. 652 00:30:21,990 --> 00:30:25,550 Emme ole koskaan vielﾃ､ ole voinut manipuloida yksittﾃ､isiﾃ､ bittejﾃ､, 653 00:30:25,550 --> 00:30:28,970 vaikka yksittﾃ､isen vﾃ､hﾃ､n, me tietﾃ､ﾃ､, voi edustaa 0 ja 1. 654 00:30:28,970 --> 00:30:32,640 Nyt nﾃ､yttﾃ､ﾃ､ siltﾃ､, 窶銀€菊ttﾃ､ C, sinua voi pﾃ､ﾃ､stﾃ､ kﾃ､siksi yksittﾃ､isiﾃ､ bittejﾃ､, 655 00:30:32,640 --> 00:30:35,530 jos tiedﾃ､t syntaksin, jolla saada niitﾃ､. 656 00:30:35,530 --> 00:30:38,010 >> Joten katsomaan klo bittioperaatioiden. 657 00:30:38,010 --> 00:30:41,700 Joten Kuvassa on muutamia symboleja, olemme, tavallaan, tavallaan, ennen nﾃ､hty. 658 00:30:41,700 --> 00:30:45,580 Nﾃ､en et-merkki, pystysuora baari, ja jotkut muut samoin, 659 00:30:45,580 --> 00:30:49,430 ja muistuttavat, ettﾃ､ et-merkki et-merkki on jotain olemme nﾃ､hneet aiemmin. 660 00:30:49,430 --> 00:30:54,060 Looginen AND-operaattori, jossa sinulla on kaksi niistﾃ､ yhdessﾃ､ tai looginen TAI 661 00:30:54,060 --> 00:30:56,300 operaattori, jossa on kaksi pystypalkkia. 662 00:30:56,300 --> 00:31:00,550 Bittioperaatioiden, joka kﾃ､ymme katso toimivat bittiﾃ､ erikseen, 663 00:31:00,550 --> 00:31:03,810 vain kﾃ､yttﾃ､ﾃ､ yksi et-merkki, yksi pystysuora palkki, sirkumfleksi symboli 664 00:31:03,810 --> 00:31:06,620 tulee seuraavaksi, pieni tilde, ja sitten vasemmalle 665 00:31:06,620 --> 00:31:08,990 kannatin vasen kannatin, tai oikea kannatin oikea kiinnike. 666 00:31:08,990 --> 00:31:10,770 Kukin nﾃ､istﾃ､ on eri merkitykset. 667 00:31:10,770 --> 00:31:11,950 >> Itse asiassa, nyt katsomaan. 668 00:31:11,950 --> 00:31:16,560 Mennﾃ､ﾃ､n vanhan koulun tﾃ､nﾃ､ﾃ､n, ja kﾃ､yttﾃｶ kosketusnﾃ､yttﾃｶ menneiden, 669 00:31:16,560 --> 00:31:18,002 tunnetaan valkoinen levy. 670 00:31:18,002 --> 00:31:19,710 Ja tﾃ､mﾃ､ valkoinen lauta aikoo antaa meille 671 00:31:19,710 --> 00:31:27,360 ilmaista joitakin melko yksinkertaisia 窶銀€虐ymboleita, tai pikemminkin joitakin melko yksinkertaisia 窶銀€橘aavoja, 672 00:31:27,360 --> 00:31:29,560 ettﾃ､ voimme lopulta vipuvaikutus, jotta 673 00:31:29,560 --> 00:31:33,230 pﾃ､ﾃ､syn yksittﾃ､isiﾃ､ bittiﾃ､ C-ohjelma. 674 00:31:33,230 --> 00:31:34,480 Toisin sanoen, tehdﾃ､ﾃ､n tﾃ､mﾃ､. 675 00:31:34,480 --> 00:31:37,080 Katsotaanpa ensin puhua varten hetki et-merkki, 676 00:31:37,080 --> 00:31:39,560 joka on peiton ja Operaattori. 677 00:31:39,560 --> 00:31:42,130 Toisin sanoen, tﾃ､mﾃ､ on operaattori, jonka avulla 678 00:31:42,130 --> 00:31:45,930 minulle on vasen muuttuja tyypillisesti, ja oikea muuttuja, 679 00:31:45,930 --> 00:31:50,640 tai yksittﾃ､inen arvo, ettﾃ､ jos me ja ne yhteen, antaa minulle lopputulokseen. 680 00:31:50,640 --> 00:31:51,560 Joten mitﾃ､ minﾃ､ tarkoitan? 681 00:31:51,560 --> 00:31:54,840 Jos ohjelma, sinulla on muuttuva ettﾃ､ tallentaa yhden nﾃ､istﾃ､ arvoista, 682 00:31:54,840 --> 00:31:58,000 tai katsotaanpa pitﾃ､ﾃ､ asiat yksinkertaisina, ja vain kirjoittaa nollia ja ykkﾃｶsiﾃ､ erikseen, 683 00:31:58,000 --> 00:32:00,940 tﾃ､ssﾃ､ miten -merkki operaattori toimii. 684 00:32:00,940 --> 00:32:06,400 0 Ampersand 0 tulee yhtﾃ､ 0. 685 00:32:06,400 --> 00:32:07,210 Nyt Miksi? 686 00:32:07,210 --> 00:32:09,291 >> Se on hyvin samankaltainen Boolen operaattoreilla, 687 00:32:09,291 --> 00:32:10,540 ettﾃ､ olemme keskustelleet tﾃ､hﾃ､n asti. 688 00:32:10,540 --> 00:32:15,800 Jos luulet onhan 0 on vﾃ､ﾃ､rﾃ､, 0 on vﾃ､ﾃ､rﾃ､, vﾃ､ﾃ､rﾃ､ ja vﾃ､ﾃ､riﾃ､ 689 00:32:15,800 --> 00:32:18,720 on, kuten olemme keskustelleet loogisesti, myﾃｶs vﾃ､ﾃ､rﾃ､. 690 00:32:18,720 --> 00:32:20,270 Jotta saamme 0 myﾃｶs tﾃ､ﾃ､llﾃ､. 691 00:32:20,270 --> 00:32:24,390 Jos otat 0 ampersand 1, hyvin, ettﾃ､ myﾃｶs 692 00:32:24,390 --> 00:32:29,890 tulee olemaan 0, koska tﾃ､mﾃ､ vasen ilmaisun olevan totta tai 1, 693 00:32:29,890 --> 00:32:32,360 sen pitﾃ､isi olla totta ja totta. 694 00:32:32,360 --> 00:32:36,320 Mutta tﾃ､ssﾃ､ meillﾃ､ on vﾃ､ﾃ､rﾃ､ ja totta, tai 0 ja 1. 695 00:32:36,320 --> 00:32:42,000 Nyt uudelleen, jos meillﾃ､ on 1 ampersand 0, sekin tulee olemaan 0, 696 00:32:42,000 --> 00:32:47,240 ja jos meillﾃ､ on 1 et-merkki 1, Lopuksi meillﾃ､ on 1 bit. 697 00:32:47,240 --> 00:32:50,340 Eli toisin sanoen, me emme tee mitﾃ､ﾃ､n mielenkiintoista tﾃ､mﾃ､n operaattorin 698 00:32:50,340 --> 00:32:51,850 vain vielﾃ､, tﾃ､mﾃ､ Ampersand operaattori. 699 00:32:51,850 --> 00:32:53,780 Se peiton ja Operaattori. 700 00:32:53,780 --> 00:32:57,290 Mutta nﾃ､mﾃ､ ovat ainekset jonka kautta voimme tehdﾃ､ 701 00:32:57,290 --> 00:32:59,240 mielenkiintoisia asioita, kuten tulemme pian nﾃ､hdﾃ､. 702 00:32:59,240 --> 00:33:02,790 >> Nyt katsokaamme vain yhden pystyviiva tﾃ､nne oikealla. 703 00:33:02,790 --> 00:33:06,710 Jos minulla on 0 vﾃ､hﾃ､n ja minﾃ､ TAI se, bittivastineen 704 00:33:06,710 --> 00:33:11,030 OR operaattori, toinen 0 bit, joka tulee antamaan minulle 0. 705 00:33:11,030 --> 00:33:17,540 Jos otan 0 vﾃ､hﾃ､n ja OR sen 1 vﾃ､hﾃ､n, niin aion saada 1. 706 00:33:17,540 --> 00:33:19,830 Ja itse asiassa, vain selkeys, anna minun mennﾃ､ takaisin, 707 00:33:19,830 --> 00:33:23,380 niin ettﾃ､ minun pystypalkki ei erehtynyt 1: n. 708 00:33:23,380 --> 00:33:26,560 Saanen uusia koko minun 1 on hieman enemmﾃ､n 709 00:33:26,560 --> 00:33:32,700 selvﾃ､sti, jotta voimme ensi nﾃ､hdﾃ､, jos en on 1 tai 0, joka tulee olemaan 1, 710 00:33:32,700 --> 00:33:39,060 ja jos minulla on 1 tai 1 ettﾃ､, Myﾃｶs tulee olemaan 1. 711 00:33:39,060 --> 00:33:42,900 Voit siis nﾃ､hdﾃ､ loogisesti ettﾃ､ TAI operaattori kﾃ､yttﾃ､ytyy hyvin eri tavalla. 712 00:33:42,900 --> 00:33:48,070 Tﾃ､mﾃ､ antaa minulle 0 tai 0 antaa minulle 0, mutta joka toinen yhdistelmﾃ､ antaa minulle 1. 713 00:33:48,070 --> 00:33:52,480 Niin kauan kuin minulla on yksi 1 kaava, tulos tulee olemaan 1. 714 00:33:52,480 --> 00:33:55,580 >> Toisin JA operaattori, et-merkki, 715 00:33:55,580 --> 00:34:00,940 vain jos minulla on kaksi 1: n yhtﾃ､lﾃｶ, voin itse saada 1 ulos. 716 00:34:00,940 --> 00:34:02,850 Nyt on olemassa muutamia muita toimijat samoin. 717 00:34:02,850 --> 00:34:04,810 Yksi niistﾃ､ on hieman enemmﾃ､n mukana. 718 00:34:04,810 --> 00:34:07,980 Joten anna minun mennﾃ､ eteenpﾃ､in ja poistaa tﾃ､mﾃ､ vapauttaa levytilaa. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Ja lﾃ､hdetﾃ､ﾃ､n katsomaan caret symboli, vain hetken. 721 00:34:16,460 --> 00:34:18,210 Tﾃ､mﾃ､ on tyypillisesti merkki voit kirjoittaa 722 00:34:18,210 --> 00:34:21,420 nﾃ､ppﾃ､imistﾃｶn SHIFT ja sitten yksi numerot huipulla oman US 723 00:34:21,420 --> 00:34:22,250 nﾃ､ppﾃ､imistﾃｶ. 724 00:34:22,250 --> 00:34:26,190 >> Joten tﾃ､mﾃ､ on yksinomainen OR operaattori, eksklusiivinen TAI. 725 00:34:26,190 --> 00:34:27,790 Joten me vain nﾃ､imme tai toiminnanharjoittaja. 726 00:34:27,790 --> 00:34:29,348 Tﾃ､mﾃ､ on eksklusiivinen OR operaattori. 727 00:34:29,348 --> 00:34:30,639 Mitﾃ､ oikeastaan 窶銀€菊roa? 728 00:34:30,639 --> 00:34:34,570 No katsotaanpa katsokaa kaava, ja kﾃ､yttﾃ､ﾃ､ tﾃ､tﾃ､ ainesosina lopulta. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Aion sanoa on aina 0. 731 00:34:39,650 --> 00:34:41,400 Se mﾃ､ﾃ､ritelmﾃ､ XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 tulee olemaan 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 tulee olemaan 1, ja 1 XOR 1 tulee olemaan? 734 00:34:58,810 --> 00:34:59,890 Vﾃ､ﾃ､rﾃ､ssﾃ､? 735 00:34:59,890 --> 00:35:00,520 Tai oikea? 736 00:35:00,520 --> 00:35:01,860 Minﾃ､ en tiedﾃ､. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Nyt mitﾃ､ on tekeillﾃ､? 739 00:35:04,700 --> 00:35:06,630 No ajattele Nimi tﾃ､mﾃ､n operaattorin. 740 00:35:06,630 --> 00:35:09,980 Eksklusiivinen OR, jotta nimi, ehdottaa, 741 00:35:09,980 --> 00:35:13,940 vastaus on vain olemaan 1 jos tulot ovat yksin, 742 00:35:13,940 --> 00:35:15,560 yksinomaan eri. 743 00:35:15,560 --> 00:35:18,170 Joten tﾃ､ssﾃ､ tulot ovat sama, joten tuotos on 0. 744 00:35:18,170 --> 00:35:20,700 Tﾃ､ssﾃ､ tulot ovat sama, joten tuotos on 0. 745 00:35:20,700 --> 00:35:25,640 Tﾃ､ssﾃ､ ovat lﾃ､hdﾃｶt ovat erilaisia, ne ovat yksin, ja niin lﾃ､htﾃｶ on 1. 746 00:35:25,640 --> 00:35:28,190 Joten se on hyvin samankaltainen Ja se on hyvin samankaltainen, 747 00:35:28,190 --> 00:35:32,760 tai pikemminkin se on hyvin samankaltainen TAI, mutta vain yksinomainen tavalla. 748 00:35:32,760 --> 00:35:36,210 Tﾃ､mﾃ､ ei ole enﾃ､ﾃ､ 1, koska meillﾃ､ on kaksi 1 n, 749 00:35:36,210 --> 00:35:38,621 ja ei yksinomaan, vain yksi niistﾃ､. 750 00:35:38,621 --> 00:35:39,120 Selvﾃ､. 751 00:35:39,120 --> 00:35:40,080 Entﾃ､ muut? 752 00:35:40,080 --> 00:35:44,220 No tilde puolestaan 窶銀€黍n todella mukava ja yksinkertainen, onneksi. 753 00:35:44,220 --> 00:35:46,410 Ja tﾃ､mﾃ､ on unary operaattorin, joka tarkoittaa 754 00:35:46,410 --> 00:35:50,400 se on sovellettu ainoastaan 窶銀€及hteen tulo, yksi operandi, niin sanoakseni. 755 00:35:50,400 --> 00:35:51,800 Ei vasemmalle ja oikealle. 756 00:35:51,800 --> 00:35:56,050 Toisin sanoen, jos otat tilde of 0, vastaus on pﾃ､invastainen. 757 00:35:56,050 --> 00:35:59,710 Ja jos otat tilde 1, vastaus tulee olemaan pﾃ､invastainen. 758 00:35:59,710 --> 00:36:02,570 Joten tilde operaattori on tapa tyhjﾃ､ksi hieman, 759 00:36:02,570 --> 00:36:06,000 tai kﾃ､ﾃ､nnetﾃ､ﾃ､n verran 0-1 tai 1-0. 760 00:36:06,000 --> 00:36:09,820 >> Ja ettﾃ､ jﾃ､ttﾃ､ﾃ､ meidﾃ､t vihdoin vain kaksi viimeistﾃ､ toimijoiden, 761 00:36:09,820 --> 00:36:13,840 ns vasemmalla muutos, ja ns oikealla shift operaattori. 762 00:36:13,840 --> 00:36:16,620 Katsotaanpa katsomaan miten nﾃ､mﾃ､ tyﾃｶssﾃ､. 763 00:36:16,620 --> 00:36:20,780 Vasemmalle siirtyminen operaattori, kirjallinen kaksi kulmakiinnikkeet niin, 764 00:36:20,780 --> 00:36:22,110 toimii seuraavasti. 765 00:36:22,110 --> 00:36:27,390 Jos minun panos, tai minun operandi, vasemmalle shift operaattori on yksinkertaisesti 1. 766 00:36:27,390 --> 00:36:33,750 Ja minﾃ､ sitten kertoa tietokoneen vasen shift ettﾃ､ 1, sanovat seitsemﾃ､n paikkoja, 767 00:36:33,750 --> 00:36:37,150 tulos on kuin olisin ottaa tﾃ､mﾃ､n 1, ja siirrﾃ､ se 768 00:36:37,150 --> 00:36:40,160 seitsemﾃ､n paikkoja yli vasemmalle, ja oletuksena, 769 00:36:40,160 --> 00:36:42,270 aiomme olettaa, ettﾃ､ tilaa oikealle 770 00:36:42,270 --> 00:36:44,080 aiotaan nollilla. 771 00:36:44,080 --> 00:36:50,316 Toisin sanoen, 1 vasen muutos 7 on menossa antaa minulle, ettﾃ､ 1, jonka jﾃ､lkeen 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 nollia. 773 00:36:54,060 --> 00:36:57,380 Joten tavallaan, sen avulla voit ottaa pieni mﾃ､ﾃ､rﾃ､ kuten 1, 774 00:36:57,380 --> 00:37:00,740 ja selvﾃ､sti on paljon paljon, paljon suurempi tﾃ､llﾃ､ tavalla, 775 00:37:00,740 --> 00:37:06,460 mutta me todella tulee nﾃ､hdﾃ､ viisaampi lﾃ､hestymistapoja se 776 00:37:06,460 --> 00:37:08,080 sen sijaan, samoin, 777 00:37:08,080 --> 00:37:08,720 >> Selvﾃ､. 778 00:37:08,720 --> 00:37:10,060 Se on siinﾃ､ viikolla kolme. 779 00:37:10,060 --> 00:37:11,400 Tulemme nﾃ､kemﾃ､ﾃ､n ensi kerralla. 780 00:37:11,400 --> 00:37:12,770 Tﾃ､mﾃ､ oli CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Musiikkia] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: Hﾃ､n oli vﾃ､lipala baari syﾃｶminen kuuma tuhertaa jﾃ､ﾃ､telﾃｶannos. 784 00:37:25,766 --> 00:37:28,090 Hﾃ､nellﾃ､ oli se koko hﾃ､nen kasvonsa. 785 00:37:28,090 --> 00:37:30,506 Hﾃ､n on pﾃ､ﾃ､llﾃ､ﾃ､n, ettﾃ､ suklaa kuten parta 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Mitﾃ､ sinﾃ､ teet? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Mitﾃ､? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: Oletko juuri double dip? 790 00:37:36,800 --> 00:37:38,585 Voit kaksinkertainen kastetaan siru. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Anteeksi. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: Sinﾃ､ kastettu siru, sinﾃ､ otti purra, ja te kastetaan uudelleen. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 SPEAKER 2: Niin, ettﾃ､ kuin laittaisi koko suu aivan dip. 795 00:37:48,440 --> 00:37:52,400 Seuraavan kerran otat siru, vain kasta se kerran, ja lopettaa sen. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Tiedﾃ､tkﾃｶ mitﾃ､, Dan? 797 00:37:53,890 --> 00:37:58,006 Voit pulahtaa tavalla haluat pulahtaa. 798 00:37:58,006 --> 00:38:01,900 Minﾃ､ dip tapa, ettﾃ､ haluan notkahdus. 799 00:38:01,900 --> 00:38:03,194