1 00:00:00,000 --> 00:00:11,904 >> [Mūzikas atskaņošanai] 2 00:00:11,904 --> 00:00:12,910 >> PROFESSOR: Nu labi. 3 00:00:12,910 --> 00:00:16,730 Tas ir CS50 un tas ir nedēļas beigām trīs. 4 00:00:16,730 --> 00:00:20,230 Tāpēc mēs šodien esam šeit, nevis Sanders Teātris, tā vietā WEIDNER bibliotēkā. 5 00:00:20,230 --> 00:00:23,170 Iekšpusē, kas ir studijas pazīstams kā Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 vai teiksim Studio H, vai veic mēs say-- ja jums patika šī joks, 7 00:00:28,310 --> 00:00:30,540 tas ir faktiski no klasesbiedrs, Mark, online, 8 00:00:30,540 --> 00:00:32,420 kurš ieteica tik daudz caur Twitter. 9 00:00:32,420 --> 00:00:34,270 Tagad to, kas ir cool par ir šeit studijā 10 00:00:34,270 --> 00:00:38,410 ir tas, ka es esmu ieskauj šie zaļš sienas, zaļā ekrāna vai chromakey, 11 00:00:38,410 --> 00:00:43,290 tā sakot, tas nozīmē, ka CS50 s ražošanas komandas, nezinot mani 12 00:00:43,290 --> 00:00:47,380 tieši tagad, varētu būt liekot mani visvairāk jebkur pasaulē, 13 00:00:47,380 --> 00:00:48,660 lai labāk vai sliktāk. 14 00:00:48,660 --> 00:00:51,800 >> Tagad to, kas ir priekšā, problēma noteikti divi ir jūsu rokās par šo nedēļu, 15 00:00:51,800 --> 00:00:53,830 bet ar problēmu noteikt Trīs šo nāk šonedēļ, 16 00:00:53,830 --> 00:00:56,600 jums tiks apstrīdēti ar tā sauktais spēle 15., 17 00:00:56,600 --> 00:00:58,960 veca puse favor kas jūs varētu atgādināt saņemšanu 18 00:00:58,960 --> 00:01:02,030 kā bērns, kas ir visu ķekars skaitļu, kas var slaidu augšu, uz leju, 19 00:01:02,030 --> 00:01:05,790 pa kreisi un pa labi, un tur ir viena plaisa ietvaros puzzle, kurā jums 20 00:01:05,790 --> 00:01:07,840 faktiski var slīdēt šos puzzle gabalus. 21 00:01:07,840 --> 00:01:11,150 Galu galā jūs saņemsiet šo puzle kaut daļēji jauktā secībā, 22 00:01:11,150 --> 00:01:12,940 un mērķis ir šķirot to, augšas uz leju, 23 00:01:12,940 --> 00:01:16,310 kreisās uz labo, no vienas visu ceļu augšup pa 15. 24 00:01:16,310 --> 00:01:19,360 >> Diemžēl, īstenojot jums ir pie rokas 25 00:01:19,360 --> 00:01:21,590 būs programmatūra pamatā, ne fiziski. 26 00:01:21,590 --> 00:01:25,280 Jūs faktiski nāksies rakstīt kods, ar kuru students vai lietotājs var 27 00:01:25,280 --> 00:01:26,760 spēlēt spēli 15. 28 00:01:26,760 --> 00:01:29,030 Un patiesībā, jo hakeris izdevums spēle 15., 29 00:01:29,030 --> 00:01:32,155 Jums būs izaicinājums, lai īstenotu, ne tikai spēlē šīs vecās skolas 30 00:01:32,155 --> 00:01:35,010 spēle, bet gan risināšana no tā, ko īsteno Dieva režīms, 31 00:01:35,010 --> 00:01:38,280 tā sakot, ka patiesībā atrisina mīklu par cilvēku, 32 00:01:38,280 --> 00:01:41,080 nodrošinot tos ar mājienu, pēc mājienu, pēc mājienu. 33 00:01:41,080 --> 00:01:42,280 Tik daudz par šo nākamnedēļ. 34 00:01:42,280 --> 00:01:43,720 Bet tas, kas ir priekšā. 35 00:01:43,720 --> 00:01:47,610 >> Tagad atceros, ka šonedēļ mums bija šis cliffhanger, ja jūs, 36 00:01:47,610 --> 00:01:52,560 kuru vislabāk mēs darām šķirošana gudrs bija augšējā robeža liels o n 37 00:01:52,560 --> 00:01:53,210 brusas. 38 00:01:53,210 --> 00:01:56,520 Citiem vārdiem sakot, burbulis šķirot, atlase kārtot, ievietošanas kārtošanas, 39 00:01:56,520 --> 00:01:59,120 viņiem visiem, bet atšķirīgs to īstenošanā, 40 00:01:59,120 --> 00:02:03,480 nodota stājas n brusas darbojas reize ļoti sliktākajā gadījumā. 41 00:02:03,480 --> 00:02:06,010 Un mēs parasti pieņemam, ka ļoti sliktākajā gadījumā šķirošanas 42 00:02:06,010 --> 00:02:08,814 ir viens, ka jūsu ieejas Ir pilnīgi atpakaļ. 43 00:02:08,814 --> 00:02:11,980 Un tiešām, tas bija diezgan dažus soļus lai īstenotu katru no šiem algoritmiem. 44 00:02:11,980 --> 00:02:15,110 >> Tagad pašās beigās klases Atsaukt, mēs salīdzinājām burbulis šķirot 45 00:02:15,110 --> 00:02:19,390 pret atlases veida pret kādu citu ka mēs sauc sapludināšanas veida tajā laikā, 46 00:02:19,390 --> 00:02:22,120 un es ierosinu, ka tas ir ņemot priekšrocība mācība no nedēļas 47 00:02:22,120 --> 00:02:24,060 nulle, skaldi un valdi. 48 00:02:24,060 --> 00:02:28,810 Un kaut kā sasniegšanai kādu logaritmiska darba laika, galu galā, 49 00:02:28,810 --> 00:02:31,024 tā vietā, lai kaut ko tas ir tīri kvadrāts. 50 00:02:31,024 --> 00:02:33,440 Un tas nav gluži logaritmiska, tas ir mazliet vairāk nekā. 51 00:02:33,440 --> 00:02:36,520 Bet, ja jūs atceraties no klases, tas bija daudz, daudz ātrāk. 52 00:02:36,520 --> 00:02:38,210 Pieņemsim to apskatīt, kur mēs left off. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble kārtot versus atlasē Kārtot pret sapludināšanas kārtošanas. 55 00:02:45,370 --> 00:02:47,700 Tagad viņi visi darbojas, jo teoriju, tajā pašā laikā. 56 00:02:47,700 --> 00:02:50,510 CPU darbojas ar tādu pašu ātrumu. 57 00:02:50,510 --> 00:02:54,990 Bet jūs varat sajust, cik garlaicīgi tas ir ļoti ātri kļūs, 58 00:02:54,990 --> 00:02:58,790 un cik ātri, kad mēs injicēt mazliet nedēļā nulle s algoritmu, 59 00:02:58,790 --> 00:03:00,080 mēs varam paātrināt lietas uz augšu. 60 00:03:00,080 --> 00:03:01,630 >> Tātad zīme kārtot izskatās pārsteidzošs. 61 00:03:01,630 --> 00:03:05,220 Kā mēs varam piesaistīt to, lai lai ātrāk sakārtotu numurus. 62 00:03:05,220 --> 00:03:07,140 Nu pieņemsim domāt atpakaļ sastāvdaļai, ka mēs 63 00:03:07,140 --> 00:03:10,380 bija atpakaļ nedēļā nulles, ka meklējot kādu, ar tālruņu grāmatā, 64 00:03:10,380 --> 00:03:12,380 un atgādina, ka pseudocode ka mēs ierosinājām, 65 00:03:12,380 --> 00:03:14,560 caur kuru mēs varam atrast kāds, piemēram, Mike Smith, 66 00:03:14,560 --> 00:03:16,310 izskatījās nedaudz kaut kas līdzīgs šim. 67 00:03:16,310 --> 00:03:20,820 >> Tagad to apskatīt, jo īpaši pie līnijas 7 un 8, un 10 un 11, 68 00:03:20,820 --> 00:03:25,240 kas inducē, ka cilpa, kuru mēs tur atgriežās 3 līniju atkal, un atkal, 69 00:03:25,240 --> 00:03:26,520 un atkal. 70 00:03:26,520 --> 00:03:31,790 Bet izrādās, ka mēs varam apskatīt Šis algoritms, šeit pseudocode, 71 00:03:31,790 --> 00:03:33,620 nedaudz vairāk veselums. 72 00:03:33,620 --> 00:03:35,960 Patiesībā tas, ko es meklēju pie šeit uz ekrāna, 73 00:03:35,960 --> 00:03:41,180 ir algoritms meklējot Mike Smith starp kādu kopumu lapas. 74 00:03:41,180 --> 00:03:45,520 Un tiešām, mēs varētu vienkāršot šo algoritms tajās līnijās 7. un 8., 75 00:03:45,520 --> 00:03:49,860 un 10 un 11, lai tikai teikt, kas es esmu parādīti šeit dzeltenā krāsā. 76 00:03:49,860 --> 00:03:52,210 Citiem vārdiem sakot, ja Mike Smits ir agrāk grāmatā, 77 00:03:52,210 --> 00:03:55,004 mums nav nepieciešams norādīt soli pa solim, tagad, kā iet atrastu viņu. 78 00:03:55,004 --> 00:03:56,920 Mums nav jānorāda doties atpakaļ uz 3. līniju, 79 00:03:56,920 --> 00:03:58,960 kāpēc nav mēs tikai vietā, teiksim, vispārīgāk, 80 00:03:58,960 --> 00:04:01,500 meklēt Mike In kreisā puse no grāmatas. 81 00:04:01,500 --> 00:04:03,960 >> Un otrādi, ja Mike ir faktiski vēlāk grāmatā, 82 00:04:03,960 --> 00:04:07,540 kāpēc nav mēs vienkārši citēt likt pēdiņas beigās meklēšanu Mike labajā pusē grāmatas. 83 00:04:07,540 --> 00:04:11,030 Citiem vārdiem sakot, kāpēc nav mēs vienkārši kārtot punt uz sevi saprotams, 84 00:04:11,030 --> 00:04:13,130 meklēt Mike šajā apakšgrupa grāmatas, 85 00:04:13,130 --> 00:04:16,279 un atstāt to mūsu esošajiem algoritms, lai pastāstītu mums 86 00:04:16,279 --> 00:04:18,750 Kā meklēt Mike ka kreisā puse no grāmatas. 87 00:04:18,750 --> 00:04:20,750 Citiem vārdiem sakot, mūsu algoritms strādā vai tas ir 88 00:04:20,750 --> 00:04:24,670 tālrunis grāmata šajā biezuma, tas biezums, vai jebkura biezuma whatsoever. 89 00:04:24,670 --> 00:04:27,826 Tātad mēs varam rekursīvi definēt šo algoritmu. 90 00:04:27,826 --> 00:04:29,950 Citiem vārdiem, uz ekrāns šeit, ir algoritms 91 00:04:29,950 --> 00:04:33,130 meklējot Mike Smith Starp lapām telefona grāmatu. 92 00:04:33,130 --> 00:04:37,410 Tātad 7. līnijā un 10, pieņemsim tikai teikt, tieši tā. 93 00:04:37,410 --> 00:04:40,250 Un es izmantot šo terminu brīdi atpakaļ, un, protams, rekursijas 94 00:04:40,250 --> 00:04:42,450 ir buzzword tagad, un tas ir tas process 95 00:04:42,450 --> 00:04:47,210 darīt kaut ko ciklisko pēc kaut kā izmantojot kodu, kas jums jau ir, 96 00:04:47,210 --> 00:04:49,722 un aicinot to vēlreiz, un atkal, un atkal. 97 00:04:49,722 --> 00:04:51,930 Tagad tas būs svarīgi ka mēs kaut kā dibens 98 00:04:51,930 --> 00:04:53,821 ārā, un nav darīt, ka bezgalīgi ilgi. 99 00:04:53,821 --> 00:04:56,070 Pretējā gadījumā mēs spēsim ir patiešām bezgalīgs cilpa. 100 00:04:56,070 --> 00:04:59,810 Bet pieņemsim redzēt, ja mēs varam aizņemties šo ideju no recursion, atkal kaut ko dara 101 00:04:59,810 --> 00:05:03,600 un atkal un atkal, lai atrisinātu šķirošanas problēma via sapludināšanas 102 00:05:03,600 --> 00:05:05,900 kārtot, viss efektīvāk. 103 00:05:05,900 --> 00:05:06,970 >> Tāpēc es dodu jums apvienot kārtot. 104 00:05:06,970 --> 00:05:07,920 Pieņemsim to apskatīt. 105 00:05:07,920 --> 00:05:10,850 Tātad, šeit ir pseudocode, ar ko mēs varētu ieviest šķirošanas, 106 00:05:10,850 --> 00:05:12,640 Izmantojot šo algoritmu sauc sapludināšanas kārtošanas. 107 00:05:12,640 --> 00:05:13,880 Un tas ir diezgan vienkārši tas. 108 00:05:13,880 --> 00:05:15,940 Par ieejas n elementiem, citiem vārdiem sakot, ja jūs esat 109 00:05:15,940 --> 00:05:18,830 ņemot n elementi un numuri un burti vai kāds ieguldījums ir, 110 00:05:18,830 --> 00:05:22,430 ja jūs esat dota n elementus, ja tie n ir mazāks par 2, tikai atgriežas. 111 00:05:22,430 --> 00:05:22,930 Tiesības? 112 00:05:22,930 --> 00:05:26,430 Jo ja n ir mazāks par 2, kas nozīmē, ka mans saraksts elementu 113 00:05:26,430 --> 00:05:30,446 ir vai nu no izmēram 0 vai 1, un abās šajās trivial lietās 114 00:05:30,446 --> 00:05:31,570 saraksts jau ir sakārtots. 115 00:05:31,570 --> 00:05:32,810 Ja saraksta nav, tas ir sakārtoti. 116 00:05:32,810 --> 00:05:35,185 Un, ja tur ir saraksts ar garumu 1, tas ir acīmredzami sakārtoti. 117 00:05:35,185 --> 00:05:38,280 Tātad algoritms tikai vajag tiešām kaut ko interesantu, 118 00:05:38,280 --> 00:05:40,870 ja mums ir divi vai vairāk elementi dota mums. 119 00:05:40,870 --> 00:05:42,440 So aplūkosim burvju tad. 120 00:05:42,440 --> 00:05:47,500 Else kārtot kreiso pusi no elementiem, tad kārtot labajā pusē elementiem, 121 00:05:47,500 --> 00:05:49,640 tad apvienot sakārtoti pusītes. 122 00:05:49,640 --> 00:05:52,440 Un, kas ir sava veida prāta lieces šeit ir tā, ka man nav īsti 123 00:05:52,440 --> 00:05:56,190 likties jums ir teicis kaut kas tikai vēl, vai ne? 124 00:05:56,190 --> 00:05:59,560 Viss, ko es esmu teica, ir, ņemot vērā, sarakstu n elementi, kārtot kreiso pusi, 125 00:05:59,560 --> 00:06:01,800 tad labajā pusē, tad apvienot sakārtoti pusītes, 126 00:06:01,800 --> 00:06:03,840 bet kur ir faktiskā noslēpums mērce? 127 00:06:03,840 --> 00:06:05,260 Kur ir algoritms? 128 00:06:05,260 --> 00:06:09,150 Nu izrādās, ka šīm divām līnijām pirmkārt, kārtot atstājis pusi no elementiem, 129 00:06:09,150 --> 00:06:13,970 un kārtot tiesības puse no elementiem, ir rekursīvas zvanu, lai runāt. 130 00:06:13,970 --> 00:06:16,120 >> Galu galā, šajā brīdis, man ir 131 00:06:16,120 --> 00:06:18,950 algoritms, ar kuru kārtot visu ķekars elementu? 132 00:06:18,950 --> 00:06:19,450 Jā. 133 00:06:19,450 --> 00:06:20,620 Tas ir labi šeit. 134 00:06:20,620 --> 00:06:25,180 Tas ir tepat uz ekrāna, un lai es varētu izmantot to pašu komplektu soļiem 135 00:06:25,180 --> 00:06:28,500 kārtot kreiso pusi, kā es varu labajā pusē. 136 00:06:28,500 --> 00:06:30,420 Un tiešām, atkal un atkal. 137 00:06:30,420 --> 00:06:34,210 Tātad tā vai citādi, un mēs drīz redzu, burvību sapludināšanas veida 138 00:06:34,210 --> 00:06:37,967 ir iestrādāts ar to, ka ļoti gala līnija, apvienojot sakārtotos pusītes. 139 00:06:37,967 --> 00:06:39,300 Un tas šķiet diezgan intuitīvi. 140 00:06:39,300 --> 00:06:41,050 Jūs lietojat divas pusītes, un jūs, kaut kā, apvienot tos kopā, 141 00:06:41,050 --> 00:06:43,260 un mēs redzam konkrēti brīdi. 142 00:06:43,260 --> 00:06:45,080 >> Bet tas ir pilnīgs algoritms. 143 00:06:45,080 --> 00:06:46,640 Un pieņemsim redzēt, tieši kāpēc. 144 00:06:46,640 --> 00:06:50,912 Nu pieņemsim, ka mēs esam dota tiem pats astoņi elementi šeit uz ekrāna, kas ir viens 145 00:06:50,912 --> 00:06:53,120 pa astoņiem, bet viņi šķietami nejaušā secībā. 146 00:06:53,120 --> 00:06:55,320 Un mērķis pie rokas ir kārtot šos elementus. 147 00:06:55,320 --> 00:06:58,280 Nu kā es varu iet par darot to, izmantojot, atkal, 148 00:06:58,280 --> 00:07:00,407 apvienot kārtot, kā par šo pseudocode? 149 00:07:00,407 --> 00:07:02,740 Un atkal, iesakņojies tas Tavs prāts, lai tikai uz mirkli. 150 00:07:02,740 --> 00:07:05,270 Pirmais gadījums ir diezgan niecīgs, ja tas ir mazāks par 2, 151 00:07:05,270 --> 00:07:07,060 vienkārši atgriezties, tur nav jāstrādā. 152 00:07:07,060 --> 00:07:09,290 Tik tiešām tur ir tikai trīs pasākumus, lai tiešām paturēt prātā. 153 00:07:09,290 --> 00:07:11,081 Atkal, un atkal, es esmu gatavojas vēlaties, lai būtu 154 00:07:11,081 --> 00:07:13,980 kārtot kreiso pusi, kārtot labo pusi, 155 00:07:13,980 --> 00:07:15,890 un pēc tam, kad viņu divas pusītes ir sakārtoti, 156 00:07:15,890 --> 00:07:18,710 Es gribu apvienot tos kopā vienā šķiroto sarakstā. 157 00:07:18,710 --> 00:07:19,940 Lai saglabātu, ka prātā. 158 00:07:19,940 --> 00:07:21,310 >> Tātad, šeit ir oriģināls sarakstā. 159 00:07:21,310 --> 00:07:23,510 Pieņemsim ārstēt to kā masīvs, kā mēs sākām 160 00:07:23,510 --> 00:07:25,800 nedēļā divas, kas ir blakus bloks atmiņas. 161 00:07:25,800 --> 00:07:28,480 Šajā gadījumā, kas satur astoņus numuri, atpakaļ atpakaļ atpakaļ. 162 00:07:28,480 --> 00:07:30,700 Un pieņemsim tagad pieteikties sapludināšanas veida. 163 00:07:30,700 --> 00:07:33,300 Tāpēc es vispirms gribu, lai sakārtotu kreiso pusi no šī saraksta, 164 00:07:33,300 --> 00:07:37,370 un pieņemsim, tādēļ, koncentrējas uz 4, 8, 6, un 2. 165 00:07:37,370 --> 00:07:41,000 >> Tagad, kā es varu iet par šķirošanas sarakstu izmēra 4? 166 00:07:41,000 --> 00:07:45,990 Nu man ir tagad uzskata šķirošanas kreisi no kreisā pusē. 167 00:07:45,990 --> 00:07:47,720 Atkal, pieņemsim attīt tikai brīdi. 168 00:07:47,720 --> 00:07:51,010 Ja pseudocode ir tas, un es esmu dota astoņiem elementus, 169 00:07:51,010 --> 00:07:53,230 8 ir acīmredzami lielāka par vai vienāds ar 2. 170 00:07:53,230 --> 00:07:54,980 Tātad ar pirmo lietu neattiecas. 171 00:07:54,980 --> 00:07:58,120 Tātad, lai kārtotu astoņus elementus, es vispirms kārtot kreiso pusi no elementiem, 172 00:07:58,120 --> 00:08:01,930 tad es sakārtotu pareizo pusi, tad es apvienot abas šķirotas pusītes, katra lieluma 4. 173 00:08:01,930 --> 00:08:02,470 LABI. 174 00:08:02,470 --> 00:08:07,480 >> Bet, ja jūs esat tikko man teica, sakārtot kreisā puse, kas tagad no lieluma 4, 175 00:08:07,480 --> 00:08:09,350 kā es varu kārtot kreiso pusi? 176 00:08:09,350 --> 00:08:11,430 Nu, ja man ir ievade no četriem elementiem, 177 00:08:11,430 --> 00:08:14,590 Es vispirms kārtot kreiso divi, tad pa labi divi, 178 00:08:14,590 --> 00:08:16,210 un tad es apvienot tos kopā. 179 00:08:16,210 --> 00:08:18,700 Tātad vēlreiz, tas kļūst mazliet no prāta lieces spēli šeit, 180 00:08:18,700 --> 00:08:21,450 jo jums, veida, ir atcerēties, kur jums ir stāsts, 181 00:08:21,450 --> 00:08:23,620 bet beigās, dienā, ņemot vērā jebkādu elementu skaits, 182 00:08:23,620 --> 00:08:25,620 jūs vispirms vēlaties, lai sakārtotu kreiso pusi, tad labajā pusē, 183 00:08:25,620 --> 00:08:26,661 tad apvienot tos kopā. 184 00:08:26,661 --> 00:08:28,630 Sāksim to darīt tieši to. 185 00:08:28,630 --> 00:08:30,170 Lūk ieejas no astoņiem elementiem. 186 00:08:30,170 --> 00:08:31,910 Tagad mēs meklējam kreisajā pusē šeit. 187 00:08:31,910 --> 00:08:33,720 Kā es varu kārtot četrus elementus? 188 00:08:33,720 --> 00:08:35,610 Nu es vispirms kārtot kreiso pusi. 189 00:08:35,610 --> 00:08:37,720 Tagad, kā es varu kārtot kreiso pusi? 190 00:08:37,720 --> 00:08:39,419 Nu es esmu bijusi divus elementus. 191 00:08:39,419 --> 00:08:41,240 Tātad pieņemsim šķirot šos divus elementus. 192 00:08:41,240 --> 00:08:44,540 2 ir lielāks par vai vienāds ar 2, protams. 193 00:08:44,540 --> 00:08:46,170 Tā, ka pirmā lieta neattiecas. 194 00:08:46,170 --> 00:08:49,010 >> Tāpēc man tagad ir, lai sakārtotu kreiso puse no šiem diviem elementiem. 195 00:08:49,010 --> 00:08:50,870 Kreisajā pusē, protams, ir tikai 4. 196 00:08:50,870 --> 00:08:54,020 Tātad, kā es varu kārtot sarakstu viena elementa? 197 00:08:54,020 --> 00:08:57,960 Nu tagad, ka īpaša pamatne gadījums up top, tā sakot, ir piemērojama. 198 00:08:57,960 --> 00:09:01,470 1 ir mazāks par 2, un mans saraksts ir patiešām izmērs 1. 199 00:09:01,470 --> 00:09:02,747 Tāpēc es vienkārši atgriezties. 200 00:09:02,747 --> 00:09:03,580 Es neko nedara. 201 00:09:03,580 --> 00:09:06,770 Un tiešām, apskatīt to, ko es esmu darīts, 4 jau ir sakārtots. 202 00:09:06,770 --> 00:09:09,220 Tāpat kā es esmu jau daļēji veiksmīga šeit. 203 00:09:09,220 --> 00:09:11,750 >> Tagad, šķiet, sava veida stulba pieprasīt, bet tā ir taisnība. 204 00:09:11,750 --> 00:09:13,700 4 ir saraksts ar izmēru 1. 205 00:09:13,700 --> 00:09:15,090 Tas jau ir sakārtoti. 206 00:09:15,090 --> 00:09:16,270 Tas ir kreiso pusi. 207 00:09:16,270 --> 00:09:18,010 Tagad es sakārtotu pareizo pusi. 208 00:09:18,010 --> 00:09:22,310 Mans ieguldījums ir viens no elementiem, 8 Līdzīgi jau sakārtoti. 209 00:09:22,310 --> 00:09:25,170 Stulba, pārāk, bet atkal, šis pamatprincips 210 00:09:25,170 --> 00:09:28,310 gatavojas ļauj mums tagad būvēt virsū tas veiksmīgi. 211 00:09:28,310 --> 00:09:32,260 4 sakārtots, 8 ir sakārtots, tagad Kas tas bija pēdējais solis? 212 00:09:32,260 --> 00:09:35,330 Tātad trešais un pēdējais solis, jebkurš laiks jūs šķirošanas sarakstā, atsaukšanu, 213 00:09:35,330 --> 00:09:38,310 bija apvienot abas pusītes, kreiso un labo. 214 00:09:38,310 --> 00:09:39,900 Tātad, pieņemsim darīt tieši to. 215 00:09:39,900 --> 00:09:41,940 Mana kreisā puse, protams, 4. 216 00:09:41,940 --> 00:09:43,310 Mana labā puse ir 8. 217 00:09:43,310 --> 00:09:44,100 >> Tātad, pieņemsim darīt. 218 00:09:44,100 --> 00:09:46,410 Vispirms es esmu gatavojas piešķirt daži papildu atmiņu, 219 00:09:46,410 --> 00:09:48,680 ka es ņemšu pārstāv šeit, kā tikai sekundāra masīvs, 220 00:09:48,680 --> 00:09:49,660 tas ir pietiekami liels, lai ietilptu to. 221 00:09:49,660 --> 00:09:52,243 Bet jūs varat iedomāties, paplašinot ka taisnstūris visā garumā, 222 00:09:52,243 --> 00:09:53,290 ja mums ir nepieciešams vairāk vēlāk. 223 00:09:53,290 --> 00:09:58,440 Kā es varu veikt 4 un 8, un apvienot šie divi saraksti izmērs 1 kopā? 224 00:09:58,440 --> 00:10:00,270 Arī šeit, diezgan vienkārši. 225 00:10:00,270 --> 00:10:03,300 4 ir pirmajā vietā, tad nāk 8. 226 00:10:03,300 --> 00:10:07,130 Jo, ja es gribu, lai sakārtotu kreiso pusi, tad labajā pusē, 227 00:10:07,130 --> 00:10:09,900 un pēc tam apvienot šos divus pusītes kopā, jo šķiroto kārtībā, 228 00:10:09,900 --> 00:10:11,940 4 ir pirmajā vietā, tad nāk 8. 229 00:10:11,940 --> 00:10:15,810 >> Tāpēc mēs, šķiet, ir gūt panākumus, pat lai gan man nav izdarīts jebkurā faktisko darbu. 230 00:10:15,810 --> 00:10:17,800 Bet atcerieties, kur mēs esam stāsts. 231 00:10:17,800 --> 00:10:19,360 Mēs sākotnēji pieņēma astoņus elementus. 232 00:10:19,360 --> 00:10:21,480 Mēs sakārtoti kreiso pusi, kas ir 4. 233 00:10:21,480 --> 00:10:24,450 Tad mēs sakārtoti kreiso pusi no kreisā pusē, kas bija 2. 234 00:10:24,450 --> 00:10:25,270 Un šeit mēs iet. 235 00:10:25,270 --> 00:10:26,920 Mēs esam darījuši ar šo soli. 236 00:10:26,920 --> 00:10:29,930 >> Tātad, ja mēs esam sakārtoti atstājis pusi no 2., tagad mēs 237 00:10:29,930 --> 00:10:32,130 ir kārtot labajā pusē 2. 238 00:10:32,130 --> 00:10:35,710 Tātad labajā pusē 2 ir šīm divām vērtībām šeit, 6 un 2. 239 00:10:35,710 --> 00:10:40,620 Tātad pieņemsim tagad veikt ievadi izmēra 2, un sakārtot kreiso pusi, un pēc tam 240 00:10:40,620 --> 00:10:42,610 labajā pusē, un pēc tam apvienot tos kopā. 241 00:10:42,610 --> 00:10:45,722 Nu kā es varu kārtot sarakstu izmēra 1, kas satur tikai numurs 6? 242 00:10:45,722 --> 00:10:46,430 Es esmu jau darīts. 243 00:10:46,430 --> 00:10:48,680 Šis saraksts izmēra 1 ir sakārtots. 244 00:10:48,680 --> 00:10:52,140 >> Kā es varu kārtot citu sarakstu izmērs 1, tā saukto labo pusi. 245 00:10:52,140 --> 00:10:54,690 Nu tas arī ir jau sakārtots. 246 00:10:54,690 --> 00:10:56,190 Skaitlis 2 ir viens pats. 247 00:10:56,190 --> 00:11:00,160 Tāpēc tagad man ir divas pusītes, pa kreisi un labi, man ir nepieciešams apvienot tos kopā. 248 00:11:00,160 --> 00:11:01,800 Ļaujiet man dot sev kādu papildus telpu. 249 00:11:01,800 --> 00:11:05,580 Un nodot 2 tur, tad 6 tur, tādējādi 250 00:11:05,580 --> 00:11:10,740 šķirošana šo sarakstu, pa kreisi un pa labi, un apvienojot to kopā, galu galā. 251 00:11:10,740 --> 00:11:12,160 Tāpēc es esmu nedaudz labāks. 252 00:11:12,160 --> 00:11:16,250 Es ne darīts, jo skaidri 4, 8, 2, 6 nav galīgs pasūtīšanas ka es gribu. 253 00:11:16,250 --> 00:11:20,640 Bet man tagad ir divi saraksti izmērs 2, kas ir gan, attiecīgi, tika sakārtots. 254 00:11:20,640 --> 00:11:24,580 Tāpēc tagad, ja jūs attīt savā prātā s acs, kur bija, ka atstāj mūs? 255 00:11:24,580 --> 00:11:28,520 Es sāku ar astoņiem elementiem, tad es whittled to uz leju līdz kreisajā pusē 4, 256 00:11:28,520 --> 00:11:31,386 tad kreiso pusi no 2, un tad labajā pusē 2, 257 00:11:31,386 --> 00:11:34,510 Es pabeidzu, tāpēc, šķirošana kreiso puse no 2, un labajā pusē 2, 258 00:11:34,510 --> 00:11:37,800 Tātad, kas ir trešais un pēdējais solis šeit? 259 00:11:37,800 --> 00:11:41,290 Man ir apvienot kopā divi saraksti izmēra 2. 260 00:11:41,290 --> 00:11:42,040 So iesim uz priekšu. 261 00:11:42,040 --> 00:11:43,940 Un uz ekrāna šeit, dot man daži papildu atmiņu, 262 00:11:43,940 --> 00:11:47,170 gan tehniski, ievērosiet, ka es esmu ieguva visai ķekars tukšu vietu uz augšu augšu 263 00:11:47,170 --> 00:11:47,670 tur. 264 00:11:47,670 --> 00:11:50,044 Ja es gribu būt īpaši efektīva telpa gudrs, 265 00:11:50,044 --> 00:11:52,960 Es varētu vienkārši sākt pārvietojas elementi un atpakaļ, augšas un apakšas. 266 00:11:52,960 --> 00:11:55,460 Bet tikai uz vizuālo skaidrību, Es esmu gatavojas nodot to uz leju zem, 267 00:11:55,460 --> 00:11:56,800 lai saglabātu lietas jauka un tīra. 268 00:11:56,800 --> 00:11:58,150 >> Tāpēc es esam ieguvuši divus sarakstus ar izmēru 2. 269 00:11:58,150 --> 00:11:59,770 Pirmajā sarakstā ir 4 un 8. 270 00:11:59,770 --> 00:12:01,500 Otrais sarakstā ir 2 un 6. 271 00:12:01,500 --> 00:12:03,950 Pieņemsim, apvienot tos, kopā šķiroto kārtībā. 272 00:12:03,950 --> 00:12:09,910 2, protams, nāk no vienas puses, tad 4, tad 6, tad 8. 273 00:12:09,910 --> 00:12:12,560 Un tagad mēs, šķiet, kļūst kaut kur interesanti. 274 00:12:12,560 --> 00:12:15,720 Tagad es esmu sakārtoti pusi no uzskaitīt, un nejauši, tas ir 275 00:12:15,720 --> 00:12:18,650 visi pāra numuri, taču tas Ir, protams, ir tikai nejaušība. 276 00:12:18,650 --> 00:12:22,220 Un es tagad ir sakārtoti pa kreisi puse, tāpēc, ka tas ir 2, 4, 6, un 8. 277 00:12:22,220 --> 00:12:23,430 Nekas ir bojātas. 278 00:12:23,430 --> 00:12:24,620 Ka jūtas kā progresam. 279 00:12:24,620 --> 00:12:26,650 >> Tagad tā uzskata, tāpat kā es esmu runājis uz visiem laikiem tagad, 280 00:12:26,650 --> 00:12:29,850 Tātad, ko Jāskatās, ja tas algoritms ir, patiešām, efektīvāku. 281 00:12:29,850 --> 00:12:31,766 Bet mēs ejam cauri tas super metodiski. 282 00:12:31,766 --> 00:12:34,060 Dators, protams, varētu darīt to, piemēram, ka. 283 00:12:34,060 --> 00:12:34,840 Tātad, kur mēs esam? 284 00:12:34,840 --> 00:12:36,180 Mēs sākām ar astoņiem elementiem. 285 00:12:36,180 --> 00:12:37,840 Es sakārtoti kreiso pusi 4. 286 00:12:37,840 --> 00:12:39,290 Man šķiet, ir darīts ar to. 287 00:12:39,290 --> 00:12:42,535 Tāpēc tagad nākamais solis ir kārtot labajā pusē 4. 288 00:12:42,535 --> 00:12:44,410 Un šī daļa, mēs varam iet caur nedaudz vairāk 289 00:12:44,410 --> 00:12:47,140 ātri, lai gan jūs esat Aicinām attītu vai apturētu, vienkārši 290 00:12:47,140 --> 00:12:49,910 domāju, ka ar to ir savā tempā, bet to, kas 291 00:12:49,910 --> 00:12:53,290 mums tagad ir iespēja darīt tieši to pašu algoritmu uz četriem 292 00:12:53,290 --> 00:12:54,380 dažādiem numuriem. 293 00:12:54,380 --> 00:12:57,740 >> So iesim uz priekšu, un koncentrēties uz labajā pusē, ko mēs esam šeit. 294 00:12:57,740 --> 00:13:01,260 Kreisajā pusē, kas Labajā pusē, un tagad 295 00:13:01,260 --> 00:13:04,560 kreiso pusi no kreisās puses puse no šīs labās puse, 296 00:13:04,560 --> 00:13:08,030 un kā es varu kārtot sarakstu izmēra 1, kas satur tikai numuru 1? 297 00:13:08,030 --> 00:13:09,030 Tas jau darīts. 298 00:13:09,030 --> 00:13:11,830 Kā es varu darīt to pašu par sarakstu izmēru 1, kas satur tikai 7? 299 00:13:11,830 --> 00:13:12,840 Tas jau darīts. 300 00:13:12,840 --> 00:13:16,790 Trešais solis šai pusē, tad ir apvienot šos abus elementus 301 00:13:16,790 --> 00:13:20,889 jaunā saraksta izmērs 2, 1 un 7. 302 00:13:20,889 --> 00:13:23,180 Nešķiet, ka esam darījuši visu ka daudz interesantu darbu. 303 00:13:23,180 --> 00:13:24,346 Let 's redzēt, kas notiks tālāk. 304 00:13:24,346 --> 00:13:29,210 Es tikko sakārtoti kreiso pusi no tiesības puse manu sākotnējo ieguldījumu. 305 00:13:29,210 --> 00:13:32,360 Tagad pieņemsim kārtot tiesības puse, kas satur 5 un 3. 306 00:13:32,360 --> 00:13:35,740 Pieņemsim vēlreiz apskatīt kreisi puse, sakārtots, labi pusi, sakārtoti, 307 00:13:35,740 --> 00:13:39,120 un apvienot tos abus kopā, par kādu papildu telpas, 308 00:13:39,120 --> 00:13:41,670 3 ir pirmajā vietā, tad nāk 5. 309 00:13:41,670 --> 00:13:46,190 Un tā nu mēs esam sakārtoti kreisā puse no labajā pusē 310 00:13:46,190 --> 00:13:49,420 no sākotnējā problēma, un labajā pusē labajā pusē 311 00:13:49,420 --> 00:13:50,800 no sākotnējā problēma. 312 00:13:50,800 --> 00:13:52,480 Kas ir trešais un pēdējais posms? 313 00:13:52,480 --> 00:13:54,854 Nu apvienot šīs divas pusītes kopā. 314 00:13:54,854 --> 00:13:57,020 So let me get sev kādu papildu telpas, bet, atkal, es 315 00:13:57,020 --> 00:13:58,699 varētu būt, izmantojot šo rezerves kosmosa up top. 316 00:13:58,699 --> 00:14:00,490 Bet mēs ejam, lai saglabātu tas vienkārši vizuāli. 317 00:14:00,490 --> 00:14:07,070 Ļaujiet man saplūst tagad 1, un pēc tam 3, un pēc tam 5, un pēc tam 7. 318 00:14:07,070 --> 00:14:10,740 Tādējādi atstājot mani tagad ar tiesības puse no sākotnējās problēmas 319 00:14:10,740 --> 00:14:12,840 kas ir perfekti sakārtots. 320 00:14:12,840 --> 00:14:13,662 >> Tātad, kas paliek? 321 00:14:13,662 --> 00:14:16,120 Es jūtu, es glabāt sakot pašas lietas atkal un atkal, 322 00:14:16,120 --> 00:14:18,700 bet tas ir atstarojošs no Tas, ka mēs esam izmantojot Rekursija. 323 00:14:18,700 --> 00:14:21,050 Par Izmantojot process algoritms atkal, un atkal, 324 00:14:21,050 --> 00:14:23,940 uz mazākiem apakšgrupās sākotnējā problēma. 325 00:14:23,940 --> 00:14:27,580 Tāpēc man tagad ir pa kreiso sakārtoti puse no sākotnējā problēma. 326 00:14:27,580 --> 00:14:30,847 Man ir tiesības sakārtoti pusi no sākotnējā problēma. 327 00:14:30,847 --> 00:14:32,180 Kas ir trešais un pēdējais solis? 328 00:14:32,180 --> 00:14:33,590 Ak, tas ir apvienojot. 329 00:14:33,590 --> 00:14:34,480 Tātad, pieņemsim darīt. 330 00:14:34,480 --> 00:14:36,420 Pieņemsim piešķirt dažas papildu atmiņa, bet mans dievs, mēs 331 00:14:36,420 --> 00:14:37,503 varētu nodot to jebkur tagad. 332 00:14:37,503 --> 00:14:40,356 Mums ir tik daudz brīvas vietas pie mums, bet mēs turpinām to vienkārši. 333 00:14:40,356 --> 00:14:42,730 Tā vietā, lai iet atpakaļ un tālāk ar mūsu sākotnējā atmiņu, 334 00:14:42,730 --> 00:14:44,480 pieņemsim tikai to darīt vizuāli uz leju šeit zemāk, 335 00:14:44,480 --> 00:14:47,240 pabeigt līdz apvienot kreiso pusi un labajā pusē. 336 00:14:47,240 --> 00:14:49,279 >> Tātad, apvienojot, kas man jādara? 337 00:14:49,279 --> 00:14:50,820 Es gribu, lai elementus kārtībā. 338 00:14:50,820 --> 00:14:53,230 Tātad apskatot kreisajā pusē, Es redzu pirmais numurs ir 2. 339 00:14:53,230 --> 00:14:55,230 Es paskatos uz labajā pusē, Es redzu pirmo numuru 340 00:14:55,230 --> 00:14:58,290 ir 1, tā protams kas numurs vēlos raut ārā, 341 00:14:58,290 --> 00:15:00,430 un nodot pirmais manā galīgajā sarakstā? 342 00:15:00,430 --> 00:15:01,449 Protams, 1. 343 00:15:01,449 --> 00:15:02,990 Tagad es gribu uzdot šo pašu jautājumu. 344 00:15:02,990 --> 00:15:05,040 Kreisajā pusē, es esmu joprojām got numuru 2. 345 00:15:05,040 --> 00:15:07,490 Labajā pusē, Man numuru 3. 346 00:15:07,490 --> 00:15:08,930 Kuriem viens vēlos izvēlēties? 347 00:15:08,930 --> 00:15:11,760 Protams, skaits 2 Un tagad paziņojums kandidātus 348 00:15:11,760 --> 00:15:13,620 ir 4 kreisajā pusē, 3. labajā pusē. 349 00:15:13,620 --> 00:15:15,020 Pieņemsim, protams, izvēlēties 3. 350 00:15:15,020 --> 00:15:18,020 Tagad kandidāti ir 4 par pa kreisi, 5 pa labi. 351 00:15:18,020 --> 00:15:19,460 Mēs, protams, izvēlēties 4. 352 00:15:19,460 --> 00:15:21,240 6 kreisajā pusē, 5 pa labi. 353 00:15:21,240 --> 00:15:22,730 Mēs, protams, izvēlēties 5. 354 00:15:22,730 --> 00:15:25,020 6 kreisajā pusē, 7 labajā pusē. 355 00:15:25,020 --> 00:15:29,320 Mēs izvēlēties 6, un tad mēs izvēlēties 7, un tad mēs izvēlamies 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Tik milzīgs skaits vārdiem vēlāk, mēs ir sakārtoti šo sarakstu astoņiem elementiem 358 00:15:34,370 --> 00:15:38,450 uz sarakstu vienas līdz astoņām, kas ir pieaug ar katru soli, 359 00:15:38,450 --> 00:15:40,850 bet cik daudz laika tas mūs to darīt. 360 00:15:40,850 --> 00:15:43,190 Nu es esmu apzināti Laid lietas gleznieciski 361 00:15:43,190 --> 00:15:46,330 šeit, tāpēc, ka mēs varam veida redzēt vai novērtējam sadalījumu 362 00:15:46,330 --> 00:15:49,060 iekarošana, kas ir noticis. 363 00:15:49,060 --> 00:15:52,830 >> Patiešām, ja paskatās atpakaļ pie uzmosties, Es esmu atstājis visus šos punktotajām līnijām 364 00:15:52,830 --> 00:15:55,660 in vietturus, jūs varat, veida, skat, apgrieztā secībā, 365 00:15:55,660 --> 00:15:58,800 ja jūs veida skatīties atpakaļ vēsture tagad, mans sākotnējais saraksts 366 00:15:58,800 --> 00:16:00,250 ir, protams, no izmēra 8. 367 00:16:00,250 --> 00:16:03,480 Un tad jau iepriekš, es biju nodarbojas ar diviem sarakstiem lieluma 4, 368 00:16:03,480 --> 00:16:08,400 un tad četri saraksti izmērs 2, un pēc tam astoņas saraksti izmēru 1. 369 00:16:08,400 --> 00:16:10,151 >> Tātad, ko tas, veida, atgādināt jums? 370 00:16:10,151 --> 00:16:11,858 Nu, protams, jebkurš no algoritmi mēs esam 371 00:16:11,858 --> 00:16:14,430 paskatījās līdz šim, kur mēs dalīt, un dalīt, un dalīt, 372 00:16:14,430 --> 00:16:19,500 glabāt, kam lietas atkal, un atkal, rezultātā šajā vispārējā ideja. 373 00:16:19,500 --> 00:16:23,100 Un tāpēc tur ir kaut kas logaritmiska notiek šeit. 374 00:16:23,100 --> 00:16:26,790 Un tas nav gluži log n, bet tur ir logaritmiska sastāvdaļa 375 00:16:26,790 --> 00:16:28,280 to, ko mēs esam tikko darīts. 376 00:16:28,280 --> 00:16:31,570 >> Tagad pieņemsim apsvērt, cik tas patiesībā ir. 377 00:16:31,570 --> 00:16:34,481 Tātad log n, atkal bija liels darba laiks, 378 00:16:34,481 --> 00:16:36,980 kad mēs kaut ko līdzīgu bināro meklēšanu, kā mēs tagad saucam, 379 00:16:36,980 --> 00:16:40,090 plaisa un iekarot stratēģija caur kuru mēs atradām Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Tagad tehniski. 381 00:16:41,020 --> 00:16:43,640 Tas ir log bāze 2 n, pat lai gan vairumā matemātikas klasēs, 382 00:16:43,640 --> 00:16:45,770 10 parasti ir pamats, ka jūs pieņemt. 383 00:16:45,770 --> 00:16:48,940 Bet datoru zinātnieki gandrīz vienmēr domāt un runāt ziņā bāzes 2, 384 00:16:48,940 --> 00:16:52,569 tāpēc mēs parasti tikai teikt žurnālu n, tā vietā, lai log bāzes 2 n, 385 00:16:52,569 --> 00:16:55,110 bet viņi tieši vienu un to pats pasaulē datora 386 00:16:55,110 --> 00:16:57,234 zinātne, un kā malā, tur ir nemainīgs faktors 387 00:16:57,234 --> 00:17:01,070 atšķirība starp diviem, tāpēc tas ir strīdīgs anyway, lai iegūtu formālu iemeslu dēļ. 388 00:17:01,070 --> 00:17:04,520 >> Bet tagad, ko mēs rūpējamies par to ir šis piemērs. 389 00:17:04,520 --> 00:17:08,520 Tātad pieņemsim nav pierādīt ar piemēru, bet Vismaz izmantot piemēru no numuriem 390 00:17:08,520 --> 00:17:10,730 pie rokas kā veselība pārbaudītu, ja Jums gribas. 391 00:17:10,730 --> 00:17:14,510 Tātad iepriekš formula bija log bāze 2 n, bet to, kas ir n, šajā gadījumā. 392 00:17:14,510 --> 00:17:18,526 Man bija n oriģinālus numurus, vai 8 no sākotnējā skaita konkrēti. 393 00:17:18,526 --> 00:17:20,359 Tagad tas ir bijis maz kamēr, bet es esmu diezgan 394 00:17:20,359 --> 00:17:25,300 pārliecināts, ka log bāze 2 no vērtības 8 ir 3, 395 00:17:25,300 --> 00:17:29,630 un, protams, to, kas ir jauki, par to, ka ir ka 3 ir tieši vairākas reizes 396 00:17:29,630 --> 00:17:33,320 ka jūs varat sadalīt sarakstu garums 8 atkal, un atkal, 397 00:17:33,320 --> 00:17:36,160 un atkal, līdz jūs esat palicis sarakstu, tikai izmēru 1. 398 00:17:36,160 --> 00:17:36,660 Tiesības? 399 00:17:36,660 --> 00:17:40,790 8 iet līdz 4, iet līdz 2, iet uz 1, un tas ir 400 00:17:40,790 --> 00:17:43,470 atspoguļo tieši tā picture mums bija tikai pirms brīža. 401 00:17:43,470 --> 00:17:47,160 Tātad mazliet veselība pārbaudītu par to, kur logaritms ir faktiski iesaistīti. 402 00:17:47,160 --> 00:17:50,180 >> Tāpēc tagad, kas vēl ir iesaistīts šeit? n. 403 00:17:50,180 --> 00:17:53,440 Tik ievēroju, ka katrs Šoreiz es sadalīt sarakstu, 404 00:17:53,440 --> 00:17:58,260 kaut arī apgrieztā secībā vēsturē šeit, es joprojām dara n lietas. 405 00:17:58,260 --> 00:18:02,320 Kas apvienojas solis prasīts, lai Es pieskarties ik vienu no numuriem, 406 00:18:02,320 --> 00:18:05,060 lai slide to tās atbilstošā vietā. 407 00:18:05,060 --> 00:18:10,760 Tātad, kaut gan augstums no šī diagramma ir no lieluma log n n vai 3, 408 00:18:10,760 --> 00:18:13,860 Konkrētāk, citiem vārdiem sakot, Es darīju trīs nodaļas šeit. 409 00:18:13,860 --> 00:18:18,800 Cik daudz darba man darīt horizontāli pa šo tabulu katru reizi? 410 00:18:18,800 --> 00:18:21,110 >> Nu, es darīju n soļus darbu, jo, ja es esmu 411 00:18:21,110 --> 00:18:24,080 ieguva četrus elementus un četrus elementus, un man ir nepieciešams apvienot tos kopā. 412 00:18:24,080 --> 00:18:26,040 Man vajag, lai iet cauri šie četri un tie četri, 413 00:18:26,040 --> 00:18:28,123 galu galā tos apvienot atpakaļ astoņiem elementiem. 414 00:18:28,123 --> 00:18:32,182 Ja otrādi Man astoņi pirksti vairāk nekā šeit, kuras man nav, un astoņas 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Ja es esmu ieguva četrus pirkstus nekā šeit, 416 00:18:34,390 --> 00:18:37,380 ko es daru, četri pirksti vairāk nekā šeit, ko es daru, 417 00:18:37,380 --> 00:18:40,590 tad tas ir tas pats piemērs kā iepriekš, ja man 418 00:18:40,590 --> 00:18:44,010 ir astoņi pirksti lai gan Kopumā, ko es varu, veida, darīt. 419 00:18:44,010 --> 00:18:47,950 Es varu darīt tieši šeit, tad es noteikti var 420 00:18:47,950 --> 00:18:50,370 apvienot visus šos sarakstus no to lieluma 1 kopā. 421 00:18:50,370 --> 00:18:54,050 Bet es, protams, ir jāskatās katrā elementā tieši vienu reizi. 422 00:18:54,050 --> 00:18:59,640 Tā augstums šajā procesā ir log n, platums šajā procesā, tā sakot, 423 00:18:59,640 --> 00:19:02,490 ir n, lai to, ko mēs, šķiet, ir, galu galā, ir 424 00:19:02,490 --> 00:19:06,470 tekošās laiks lieluma n reizes log n. 425 00:19:06,470 --> 00:19:08,977 >> Citiem vārdiem sakot, mēs sadalīta saraksts, log n reizes, 426 00:19:08,977 --> 00:19:11,810 bet katru reizi, kad mēs to izdarījām, ka mums bija pieskarties ik viens no elementiem 427 00:19:11,810 --> 00:19:13,560 lai tos apvienot visi kopā, kas 428 00:19:13,560 --> 00:19:18,120 tika n soli, tāpēc mums ir n reizes log n, vai kā dators zinātnieks teiktu, 429 00:19:18,120 --> 00:19:20,380 asimptotiski, kas būtu liels vārds 430 00:19:20,380 --> 00:19:22,810 aprakstīt augšējo saistās ar darba laika, 431 00:19:22,810 --> 00:19:28,010 mēs darbojas liels o log n laiku, lai runāt. 432 00:19:28,010 --> 00:19:31,510 >> Tagad tas ir nozīmīgs, jo atgādināt kādi darbojas laiki bija 433 00:19:31,510 --> 00:19:34,120 ar burbuļu kārtot un atlase kārtot, un ievietošanas kārtot, 434 00:19:34,120 --> 00:19:38,200 un pat daži citi, kas pastāv, n brusas bija, kad mēs bijām. 435 00:19:38,200 --> 00:19:39,990 Un jūs varat, veida, redzēt to šeit. 436 00:19:39,990 --> 00:19:45,720 Ja n brusas ir acīmredzami n reizes n, bet šeit mums ir n reizes log n, 437 00:19:45,720 --> 00:19:48,770 un mēs jau zinām no nedēļas nulle, ka log n, logaritmisko, 438 00:19:48,770 --> 00:19:50,550 ir labāks nekā kaut lineāra. 439 00:19:50,550 --> 00:19:52,930 Galu galā, atgādināt attēlu ar sarkano un dzelteno 440 00:19:52,930 --> 00:19:56,500 un zaļās līnijas, kas uzzīmētas, tad green logaritmiska līnija bija daudz zemāks. 441 00:19:56,500 --> 00:20:00,920 Un tāpēc, daudz labāk un ātrāk nekā taisni dzeltenās un sarkanās līnijas, 442 00:20:00,920 --> 00:20:05,900 n reizes log n ir, protams, labāk nekā n reizes n, vai n brusas. 443 00:20:05,900 --> 00:20:09,110 >> Tāpēc mēs, šķiet, ir identificē algoritms sapludināšanu 444 00:20:09,110 --> 00:20:11,870 kārtot, kas darbojas daudz ātrāku laiku, un, protams, 445 00:20:11,870 --> 00:20:16,560 tāpēc, šonedēļ, kad Mēs redzējām, ka konkurss starp burbulis 446 00:20:16,560 --> 00:20:20,750 kārtot, atlase kārtot, un apvienot kārtot, apvienot kārtot tiešām, tiešām uzvarēja. 447 00:20:20,750 --> 00:20:23,660 Un tiešām, mums nebija pat jāgaida burbuļu veida un atlases veida 448 00:20:23,660 --> 00:20:24,790 pabeigt. 449 00:20:24,790 --> 00:20:27,410 >> Tagad pieņemsim vienu citu caurlaide pie tam, no nedaudz vairāk 450 00:20:27,410 --> 00:20:31,030 formālā viedokļa, tikai gadījumā, tas rezonē labāk 451 00:20:31,030 --> 00:20:33,380 nekā šī augstākā līmeņa diskusijas. 452 00:20:33,380 --> 00:20:34,880 Tātad, šeit ir algoritms vēlreiz. 453 00:20:34,880 --> 00:20:36,770 Pajautāsim sev, ko darba laiks 454 00:20:36,770 --> 00:20:39,287 ir šī algoritmi dažādus pasākumus? 455 00:20:39,287 --> 00:20:41,620 Pieņemsim to sadala pirmais gadījums un otra lieta. 456 00:20:41,620 --> 00:20:46,280 IF un citur IF gadījumā Ja n ir mazāks par 2, tikai atgriezties. 457 00:20:46,280 --> 00:20:47,580 Jūtas kā pastāvīgu laiku. 458 00:20:47,580 --> 00:20:50,970 Tas ir, veida, piemēram, divos posmos, Ja n ir mazāks par 2, tad atgriezties. 459 00:20:50,970 --> 00:20:54,580 Bet kā mēs teicām pirmdien, pastāvīgs laiks, vai liels o 1, 460 00:20:54,580 --> 00:20:57,130 var būt divi soļi, trīs pakāpieni, pat 1000 pakāpieni. 461 00:20:57,130 --> 00:20:59,870 Svarīgi ir tas, ka tā ir pastāvīgs vairāki soļi. 462 00:20:59,870 --> 00:21:03,240 Tātad dzeltens uzsvēra pseudocode šeit darbojas, mēs to saucam, 463 00:21:03,240 --> 00:21:04,490 konstante laiks. 464 00:21:04,490 --> 00:21:06,780 Tātad vairāk formāli, un mēs ejam kuri paredzēti, šis 465 00:21:06,780 --> 00:21:09,910 būs, cik lielā mērā mēs formalizēt šīs tiesības now-- T n, 466 00:21:09,910 --> 00:21:15,030 darbības laiks problēmu kas ņem n somethings kā ievade, 467 00:21:15,030 --> 00:21:19,150 vienāds liels o vienu, , N ir mazāks par 2. 468 00:21:19,150 --> 00:21:20,640 Tātad, tas ir atkarīgs no tā. 469 00:21:20,640 --> 00:21:24,150 Tātad, lai būtu skaidrs, ja n ir mazāks nekā 2, mums ir ļoti īss saraksts, tad 470 00:21:24,150 --> 00:21:29,151 darbības laiks, T no n, kur n ir 1 vai 0, šajā ļoti konkrētajā gadījumā, 471 00:21:29,151 --> 00:21:30,650 tas tikai būs nemainīga laiks. 472 00:21:30,650 --> 00:21:32,691 Tas gatavojas veikt vienu soli, divus soļus, neatkarīgi. 473 00:21:32,691 --> 00:21:33,950 Tas ir fiksēts vairāki soļi. 474 00:21:33,950 --> 00:21:38,840 >> Tātad sulīgs daļa ir noteikti jābūt otrs gadījums pseudocode. 475 00:21:38,840 --> 00:21:40,220 VĒL gadījums. 476 00:21:40,220 --> 00:21:44,870 Kārtot kreisā puse no elementiem, kārtot tiesības puse no elementiem, apvienot sakārtotās pusītes. 477 00:21:44,870 --> 00:21:46,800 Cik ilgi katrs no šiem soļiem veikt? 478 00:21:46,800 --> 00:21:49,780 Nu, ja darbojas laiks, lai sakārtotu n elementiem 479 00:21:49,780 --> 00:21:53,010 ir, sauksim to par ļoti vispārēji, T no n, 480 00:21:53,010 --> 00:21:55,500 tad šķirošana kreiso puse no elementiem 481 00:21:55,500 --> 00:21:59,720 ir, veida, piemēram, sakot, T n dalīts ar 2, 482 00:21:59,720 --> 00:22:03,000 un līdzīgi šķirošanas pareizo pusi elementiem ir, veida, piemēram, sakot, 483 00:22:03,000 --> 00:22:06,974 T n sadalīta 2, un pēc tam apvienojot sakārtoti pusītes. 484 00:22:06,974 --> 00:22:08,890 Nu, ja man daži elementu skaits šeit, 485 00:22:08,890 --> 00:22:11,230 piemēram, četri, un dažas numurs Elementu šeit, tāpat kā četri, 486 00:22:11,230 --> 00:22:14,650 un man ir apvienot katra no šiem četriem in, un katrs no tiem četri, viens 487 00:22:14,650 --> 00:22:17,160 pēc otras, lai galu galā man ir astoņi elementus. 488 00:22:17,160 --> 00:22:20,230 Tā uzskata, piemēram, ka ir liels o n soļiem? 489 00:22:20,230 --> 00:22:23,500 Ja man n pirkstiem un katrai viņiem ir jāapvieno vietā, 490 00:22:23,500 --> 00:22:25,270 tas ir tāpat kā vēl n soļiem. 491 00:22:25,270 --> 00:22:27,360 >> Tātad patiešām formulaically, mēs varam izteikt to, 492 00:22:27,360 --> 00:22:29,960 kaut nedaudz scarily sākumā skatienu, bet tas ir kaut kas 493 00:22:29,960 --> 00:22:31,600 kas atspoguļo tieši šo loģiku. 494 00:22:31,600 --> 00:22:35,710 Darbības laiks, T no n, ja n ir lielāks par vai vienāds ar 2. 495 00:22:35,710 --> 00:22:42,500 Tādā gadījumā cits lietas, ir T n dalīts ar 2, plus T no N dalīts ar 2, 496 00:22:42,500 --> 00:22:45,320 plus liels o n, daži pakāpienu lineārā skaits, 497 00:22:45,320 --> 00:22:51,630 varbūt tieši n, varbūt 2 reizes n, bet tas ir apmēram, lai n. 498 00:22:51,630 --> 00:22:54,060 Tā, ka, arī ir tas, kā mēs varam izteikt šo formulaically. 499 00:22:54,060 --> 00:22:56,809 Tagad jūs nezināt, ja vien Jūs esat ierakstīts to savā prātā, 500 00:22:56,809 --> 00:22:58,710 vai meklēt to atbalstīts atpakaļ mācību grāmata, kas 501 00:22:58,710 --> 00:23:00,501 varētu būt nedaudz pievilt lapu beigās, 502 00:23:00,501 --> 00:23:03,940 bet tas, protams, gatavojas dod mums liels o n log n, 503 00:23:03,940 --> 00:23:06,620 jo atkārtošanās ka jūs redzēt šeit uz ekrāna, 504 00:23:06,620 --> 00:23:09,550 ja jūs tiešām izdarīja to ārā, ar bezgalīgs piemēri skaits, 505 00:23:09,550 --> 00:23:13,000 vai jūs to formulaically, turat redzēt, ka tas, ka šo formulu 506 00:23:13,000 --> 00:23:17,100 pati par sevi ir rekursīvs, ar t n pār kaut labajā pusē, 507 00:23:17,100 --> 00:23:21,680 un t n pāri pa kreisi, tas var faktiski izsaka, galu galā, 508 00:23:21,680 --> 00:23:24,339 kā liels aiziet no n log n. 509 00:23:24,339 --> 00:23:26,130 Ja tā nav pārliecināta, ka tas fine tagad, tikai 510 00:23:26,130 --> 00:23:28,960 uzņemties ticību, ka tas, protams, ko tas atkārtošanās izraisa, 511 00:23:28,960 --> 00:23:31,780 bet tas ir tikai nedaudz vairāk par matemātiska pieeja meklē 512 00:23:31,780 --> 00:23:36,520 tajā darbojas laikā sapludināšanas veida pamatojoties uz tās pseudocode vien. 513 00:23:36,520 --> 00:23:39,030 >> Tagad pieņemsim mazliet breather no visiem, ka, 514 00:23:39,030 --> 00:23:41,710 un veikt apskatīt pārliecināts bijušais senators, kurš 515 00:23:41,710 --> 00:23:44,260 varētu izskatīties nedaudz pazīstami, kurš apsēdās ar Google Eric 516 00:23:44,260 --> 00:23:48,410 Schmidt, kādu laiku atpakaļ, uz pārrunām uz posmā, pie visu ķekars 517 00:23:48,410 --> 00:23:53,710 cilvēku, runājot galu galā par tēmu, kas ir diezgan tagad pazīstams. 518 00:23:53,710 --> 00:23:54,575 Pieņemsim to apskatīt. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Tagad Senator, Jūs esat šeit Google, 521 00:24:03,890 --> 00:24:09,490 un man patīk domāt no prezidentūra kā darba interviju. 522 00:24:09,490 --> 00:24:11,712 Tagad tas ir grūti, lai iegūtu darbu, kā prezidents. 523 00:24:11,712 --> 00:24:12,670 Prezidents Obama: Right. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: Un jūs esat darīsim [nedzirdama] tagad. 525 00:24:13,940 --> 00:24:15,523 Tas ir arī grūti iegūt darbu pie Google. 526 00:24:15,523 --> 00:24:17,700 Prezidents Obama: Right. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Mums ir jautājumi, un mēs lūdzam mūsu kandidātiem jautājumus, 528 00:24:21,330 --> 00:24:24,310 un tas viens ir no Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> Prezidents Obama: OK. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Kas? 531 00:24:27,005 --> 00:24:28,130 Jūs guys domā, ka es esmu kidding? 532 00:24:28,130 --> 00:24:30,590 Tas ir labi šeit. 533 00:24:30,590 --> 00:24:33,490 Kas ir visefektīvākais veids, kā šķirot miljons 32 bitu integers? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> Prezidents Obama: Well-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Dažreiz, varbūt es esmu sorry, maybe-- 537 00:24:41,020 --> 00:24:42,750 Prezidents Obama: Nē, nē, nē, nē, nē, es think-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: Tas nav it-- 539 00:24:43,240 --> 00:24:45,430 Prezidents Obama: I domāju, es domāju, ka burbuli 540 00:24:45,430 --> 00:24:46,875 kārtot būtu nepareizs ceļš. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Come on. 543 00:24:50,535 --> 00:24:52,200 Kas viņam šo teicis? 544 00:24:52,200 --> 00:24:54,020 LABI. 545 00:24:54,020 --> 00:24:55,590 Es darīju ne datorzinātnes on-- 546 00:24:55,590 --> 00:24:58,986 >> Prezidents Obama: Mēs esam ieguva mūsu spiegi tur. 547 00:24:58,986 --> 00:24:59,860 PROFESSOR: Nu labi. 548 00:24:59,860 --> 00:25:03,370 Atstāsim aiz mums tagad teorētiskā pasaule algoritmu 549 00:25:03,370 --> 00:25:06,520 jo asimptotiskās analīzē apakšpunktu, un atgriezties pie dažiem jautājumiem 550 00:25:06,520 --> 00:25:09,940 no nedēļas nulli un vienu, un sākt noņemt dažus mācību riteņiem, 551 00:25:09,940 --> 00:25:10,450 ja Jums gribas. 552 00:25:10,450 --> 00:25:13,241 Tā, ka jūs patiešām saprotat galu galā no zemes uz augšu, kas ir 553 00:25:13,241 --> 00:25:16,805 notiek zem motora pārsega, kad jūs rakstīt, apkopot un izpildīt programmas. 554 00:25:16,805 --> 00:25:19,680 Atgādināt it īpaši, ka tas bija pirmais C programma, mēs paskatījās, 555 00:25:19,680 --> 00:25:22,840 kanoniskās, vienkārša programma par veidu, relatīvi runājot, 556 00:25:22,840 --> 00:25:24,620 kur, tas drukā, Hello World. 557 00:25:24,620 --> 00:25:27,610 Un atceros, ka es teicu, šis process ka pirmkods iet cauri 558 00:25:27,610 --> 00:25:28,430 ir tieši tas. 559 00:25:28,430 --> 00:25:31,180 Tu ņem savu pirmkodu, iet tas caur kompilatoru, piemēram šķindēt, 560 00:25:31,180 --> 00:25:34,650 un ārā nāk objekta kodu, kas varētu izskatīties šādi, nullēm un uzņēmumiem 561 00:25:34,650 --> 00:25:37,880 ka datora CPU, centrālā apstrādes bloks vai smadzenes, 562 00:25:37,880 --> 00:25:39,760 galu galā saprot. 563 00:25:39,760 --> 00:25:42,460 >> Izrādās, ka tas ir mazliet pārāk vienkāršota, 564 00:25:42,460 --> 00:25:44,480 ka mēs esam šobrīd ir amats kaitināt intervālu 565 00:25:44,480 --> 00:25:46,720 saprast, kas īsti bijis notiek zem motora pārsega 566 00:25:46,720 --> 00:25:48,600 Katru reizi palaižot Šķindēt, vai vispārīgāk, 567 00:25:48,600 --> 00:25:53,040 Katru reizi, kad jūs veicat programmu, izmantojot Marka un CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Jo īpaši, sīkumi, piemēram, Šī ir pirmā radīts, 569 00:25:56,760 --> 00:25:58,684 kad pirmo reizi sastādīt savu programmu. 570 00:25:58,684 --> 00:26:00,600 Citiem vārdiem sakot, ja jūs veikt savu pirmkodu 571 00:26:00,600 --> 00:26:04,390 un apkopot to, kas ir pirmais tiek izvadīts ar šķindēt 572 00:26:04,390 --> 00:26:06,370 ir kaut kas pazīstams kā montāžas kodu. 573 00:26:06,370 --> 00:26:08,990 Un patiesībā, tas izskatās tieši tā, kā šis. 574 00:26:08,990 --> 00:26:11,170 >> I ilga komandu pie komandrindas agrāk. 575 00:26:11,170 --> 00:26:16,260 Šķindēt Dash galvaspilsētas s hello.c, un tas radīja failu 576 00:26:16,260 --> 00:26:19,490 man sauc par hello.s, iekšpusē, kas bija tieši 577 00:26:19,490 --> 00:26:22,290 šie saturs, un nedaudz vairāk virs un nedaudz vairāk zemāk, 578 00:26:22,290 --> 00:26:25,080 bet es esmu likts juiciest informācija šeit uz ekrāna. 579 00:26:25,080 --> 00:26:29,190 Un, ja paskatās tuvāk, jūs redzēsiet vismaz daži pazīstami atslēgvārdiem. 580 00:26:29,190 --> 00:26:31,330 Mums ir galvenais augšpusē. 581 00:26:31,330 --> 00:26:35,140 Mēs esam printf leju vidū. 582 00:26:35,140 --> 00:26:38,670 Un mums ir arī hello world slīpsvītru n pēdiņās zemāk. 583 00:26:38,670 --> 00:26:42,450 >> Un viss pārējais šeit ir ļoti zema līmeņa instrukcija 584 00:26:42,450 --> 00:26:45,500 ka datora CPU saprot. 585 00:26:45,500 --> 00:26:50,090 CPU instrukcijas, kas pārvietojas atmiņu apkārt, ka slodze stīgas no atmiņas, 586 00:26:50,090 --> 00:26:52,750 un galu galā, drukāt lietas uz ekrāna. 587 00:26:52,750 --> 00:26:56,780 Tagad to, kas notiek, lai gan pēc tam, kad šis montāža kods tiek ģenerēts? 588 00:26:56,780 --> 00:26:59,964 Galu galā, jūs, protams, joprojām rada objekta kodu. 589 00:26:59,964 --> 00:27:02,630 Bet soļi, kas ir patiešām turpinās jau zem pārsega 590 00:27:02,630 --> 00:27:04,180 izskatās nedaudz vairāk kā šis. 591 00:27:04,180 --> 00:27:08,390 Pirmkods kļūst montāža kods, kas tad kļūst objekta kodu, 592 00:27:08,390 --> 00:27:11,930 un rezolutīvā vārdi šeit ir, ka, kad jūs sastādīt savu pirmkodu, 593 00:27:11,930 --> 00:27:16,300 ārā nāk montāžas kodu, un pēc tam kad jūs savākt savu montāžas kodu, 594 00:27:16,300 --> 00:27:17,800 ārā nāk objekta kodu. 595 00:27:17,800 --> 00:27:20,360 >> Tagad šķindēt ir super sarežģīta, piemēram, daudz kompilatoru, 596 00:27:20,360 --> 00:27:23,151 un tas viss no šiem soļiem kopā, un tas nav obligāti 597 00:27:23,151 --> 00:27:25,360 izlaide jebkurš starpposma failus, ka jūs pat varat redzēt. 598 00:27:25,360 --> 00:27:28,400 Tas tikai apkopo lietas, kas ir vispārīgs termins, kas 599 00:27:28,400 --> 00:27:30,000 apraksta visu šo procesu. 600 00:27:30,000 --> 00:27:32,000 Bet, ja jūs patiešām vēlaties būt īpaši, tur ir 601 00:27:32,000 --> 00:27:34,330 daudz vairāk notiek tur, kā labi. 602 00:27:34,330 --> 00:27:38,860 >> Bet pieņemsim apsvērt arī tagad, ka pat ka super vienkārša programma, hello.c, 603 00:27:38,860 --> 00:27:40,540 sauc par funkciju. 604 00:27:40,540 --> 00:27:41,870 To sauc printf. 605 00:27:41,870 --> 00:27:46,900 Bet man nav rakstīt printf, protams, kas nāk ar C, lai runāt. 606 00:27:46,900 --> 00:27:51,139 Tā ir funkcija, atgādināt, ka ir deklarēta standarta io.h, kas 607 00:27:51,139 --> 00:27:53,180 ir header fails, kurā ir jautājums, mēs faktiski 608 00:27:53,180 --> 00:27:55,780 nirt dziļāk pirms ilgi. 609 00:27:55,780 --> 00:27:58,000 Bet header fails ir parasti pavada 610 00:27:58,000 --> 00:28:02,920 ar koda failu, kods failu, tāpēc daudz, piemēram, pastāv standarta io.h. 611 00:28:02,920 --> 00:28:05,930 >> Dažkārt atpakaļ, kāds, vai someones, arī uzrakstīja 612 00:28:05,930 --> 00:28:11,040 failu sauc standarts io.c, jo kuru faktiskais definīcijas, 613 00:28:11,040 --> 00:28:15,220 vai implementācijas printf, un ķekarus citas funkcijas, 614 00:28:15,220 --> 00:28:16,870 faktiski rakstīts. 615 00:28:16,870 --> 00:28:22,140 Tātad, ņemot vērā, ka, ja mēs uzskatām, kam šeit pa kreisi, hello.c, ka tad, kad 616 00:28:22,140 --> 00:28:26,250 apkopoti, dod mums hello.s, pat ja Šķindēt nav apnikt ietaupījumu vietā 617 00:28:26,250 --> 00:28:31,360 mēs varam redzēt to, un ka montāža kods izpaužas samontēt hello.o, kas 618 00:28:31,360 --> 00:28:34,630 Ir, protams, noklusējuma nosaukums ņemot vērā, kad jūs sastādīt avots 619 00:28:34,630 --> 00:28:39,350 kodu objekta kodu, bet nav diezgan gatavs izpildīt to vēl, 620 00:28:39,350 --> 00:28:41,460 jo vēl vienu soli ir noticis, un ir 621 00:28:41,460 --> 00:28:44,440 noticis par pēdējo nedēļas, varbūt nezinot jums. 622 00:28:44,440 --> 00:28:47,290 >> Konkrēti kaut kur in CS50 IDE, un tas, 623 00:28:47,290 --> 00:28:49,870 Arī, būs mazliet pārmērīga uz brīdi, 624 00:28:49,870 --> 00:28:54,670 tur ir, vai bija sensenos laikos, failu sauc standarta io.c, 625 00:28:54,670 --> 00:28:58,440 ka kāds apkopo standarta io.s vai ekvivalents, 626 00:28:58,440 --> 00:29:02,010 ka kāds tad samontēti par standarta io.o, 627 00:29:02,010 --> 00:29:04,600 vai izrādās ārā nedaudz atšķiras fails 628 00:29:04,600 --> 00:29:07,220 formāts, kas var būt atšķirīgs faila paplašinājumu vispār, 629 00:29:07,220 --> 00:29:11,720 bet teorētiski un konceptuāli, tieši šie pasākumi bija jānotiek tādā vai citādā veidā. 630 00:29:11,720 --> 00:29:14,060 Kas ir teikt, ka tagad kad es esmu rakstot programmu, 631 00:29:14,060 --> 00:29:17,870 hello.c, ka vienkārši saka, hello world, un es esmu, izmantojot kādu citu kodu 632 00:29:17,870 --> 00:29:22,480 piemēram printf, kas bija Reiz laiks, failā ar nosaukumu standarta io.c, 633 00:29:22,480 --> 00:29:26,390 tad kaut kā man, lai mana objekts kods, mani nullēm un tiem, 634 00:29:26,390 --> 00:29:29,260 un šīs personas objekts kodu vai nullēm un tiem, 635 00:29:29,260 --> 00:29:34,970 un kaut kā saistīt tos kopā Viena gala fails, ko sauc sveiki, ka 636 00:29:34,970 --> 00:29:38,070 ir visas nulles un tie no mana galvenā funkcija, 637 00:29:38,070 --> 00:29:40,830 un visi no nullēm un domātos printf. 638 00:29:40,830 --> 00:29:44,900 >> Un tiešām, tas pēdējais process ir sauc, saistot savu objekta kodu. 639 00:29:44,900 --> 00:29:47,490 Kuras izejas signāls ir izpildāmais fails. 640 00:29:47,490 --> 00:29:49,780 Tātad taisnīgumu, pie Dienas beigās, nekas 641 00:29:49,780 --> 00:29:52,660 kas ir mainījies kopš nedēļā vienu, kad mēs pirmo reizi sāka apkopojot programmas. 642 00:29:52,660 --> 00:29:55,200 Patiešām, tas viss ir bijis kas notiek zem motora pārsega, 643 00:29:55,200 --> 00:29:57,241 bet tagad mēs esam tādā stāvoklī, kur mēs varam reāli 644 00:29:57,241 --> 00:29:58,794 ķircināt izņemot šos dažādos pasākumus. 645 00:29:58,794 --> 00:30:00,710 Un tiešām, beigās no dienas, mēs joprojām esam 646 00:30:00,710 --> 00:30:04,480 atstāts ar nullēm un tiem, kas ir tiešām liels segue tagad 647 00:30:04,480 --> 00:30:08,620 uz citu spēju C, ka mēs esam nav bijis, lai piesaistītu visticamāk 648 00:30:08,620 --> 00:30:11,250 līdz šim pazīstams kā Bitu līmeņa operatoriem. 649 00:30:11,250 --> 00:30:15,220 Citiem vārdiem sakot, līdz šim, jebkurā laikā mēs esam aplūkoti datiem C vai mainīgo C, 650 00:30:15,220 --> 00:30:17,660 mēs esam bija lietas, piemēram, chars un pludiņi un ins 651 00:30:17,660 --> 00:30:21,990 un ilgojas un dubultspēlēs un tamlīdzīgi, bet visi no tiem ir vismaz astoņi biti. 652 00:30:21,990 --> 00:30:25,550 Mēs nekad vēl spējusi manipulēt atsevišķus biti, 653 00:30:25,550 --> 00:30:28,970 kaut gan individuāla mazliet, mēs zina, var pārstāvēt 0 un 1. 654 00:30:28,970 --> 00:30:32,640 Tagad izrādās, ka C, jums var piekļūt atsevišķiem bitiem, 655 00:30:32,640 --> 00:30:35,530 Ja jūs zināt sintaksi, ar kuru nokļūt pie viņiem. 656 00:30:35,530 --> 00:30:38,010 >> Tātad, pieņemsim to apskatīt at Bitu līmeņa operatoriem. 657 00:30:38,010 --> 00:30:41,700 Tātad attēlotie šeit ir daži simboli, kas mēs esam, veida, veida, redzējis. 658 00:30:41,700 --> 00:30:45,580 Es redzu aizvieto & zīmes, vertikāla bārs, un daži citi, kā arī, 659 00:30:45,580 --> 00:30:49,430 un atgādina, ka aizvieto & zīmes aizvieto & zīmes ir kaut kas mēs esam redzējuši iepriekš. 660 00:30:49,430 --> 00:30:54,060 Loģisks un operators, kur jums ir divi no tiem kopā, vai loģiskā VAI 661 00:30:54,060 --> 00:30:56,300 operators, ja jūs ir divas vertikālas joslas. 662 00:30:56,300 --> 00:31:00,550 Bitu līmeņa operatoriem, ko mēs sk darboties bitiem individuāli, 663 00:31:00,550 --> 00:31:03,810 tikai izmantot vienu aizvieto & zīmes A single vertikāla josla, tad caret simbols 664 00:31:03,810 --> 00:31:06,620 nāk nākamais, maz Tilde, un tad pa kreisi 665 00:31:06,620 --> 00:31:08,990 kronšteins kreisi kronšteinu, vai Tiesības kronšteins tiesības kronšteins. 666 00:31:08,990 --> 00:31:10,770 Katrs no tiem ir dažādas nozīmes. 667 00:31:10,770 --> 00:31:11,950 >> Patiesībā, pieņemsim to apskatīt. 668 00:31:11,950 --> 00:31:16,560 Iesim vecās skolas šodien, un lietošana touch screen no vakardienas, 669 00:31:16,560 --> 00:31:18,002 pazīstams kā balta kuģa. 670 00:31:18,002 --> 00:31:19,710 Un šī baltā tāfele gatavojas ļaut mums 671 00:31:19,710 --> 00:31:27,360 izteikt dažus diezgan vienkārši simboli, vai drīzāk daži diezgan vienkāršas formulas, 672 00:31:27,360 --> 00:31:29,560 ka mēs varam, tad galu galā sviras, lai 673 00:31:29,560 --> 00:31:33,230 piekļūt individuāls biti ietvaros C programmas. 674 00:31:33,230 --> 00:31:34,480 Citiem vārdiem sakot, pieņemsim to izdarītu. 675 00:31:34,480 --> 00:31:37,080 Pieņemsim vispirms runāt priekšlikums moments Ampersand, 676 00:31:37,080 --> 00:31:39,560 kas ir Bitu līmeņa un operators. 677 00:31:39,560 --> 00:31:42,130 Citiem vārdiem sakot, tas ir operators, kas ļauj 678 00:31:42,130 --> 00:31:45,930 man ir kreisās puses mainīgo parasti, un labās puses mainīgo, 679 00:31:45,930 --> 00:31:50,640 vai privātpersona vērtība, ka, ja mēs UN tos kopā, dod man gala rezultātu. 680 00:31:50,640 --> 00:31:51,560 Tātad, ko es domāju? 681 00:31:51,560 --> 00:31:54,840 Ja programmā, jums ir mainīgais kas saglabā vienu no šīm vērtībām, 682 00:31:54,840 --> 00:31:58,000 vai pieņemsim glabā to vienkārši, un tikai izrakstīt nullēm un tiem atsevišķi, 683 00:31:58,000 --> 00:32:00,940 lūk, kā Ampersand operators darbojas. 684 00:32:00,940 --> 00:32:06,400 0 Ampersand 0 gatavojas vienāds 0. 685 00:32:06,400 --> 00:32:07,210 Tagad, kāpēc tā? 686 00:32:07,210 --> 00:32:09,291 >> Tas ir ļoti līdzīgs Būla izteiksmes, 687 00:32:09,291 --> 00:32:10,540 ka mēs esam apspriests līdz šim. 688 00:32:10,540 --> 00:32:15,800 Ja jūs domājat, ka galu galā, 0 ir nepatiesa, 0 ir nepatiesa, nepatiesu un viltus 689 00:32:15,800 --> 00:32:18,720 ir, kā mēs esam apspriests loģiski, arī nepatiesa. 690 00:32:18,720 --> 00:32:20,270 Tātad mēs 0 arī šeit. 691 00:32:20,270 --> 00:32:24,390 Ja esat lietojis 0 aizvieto & zīmes 1, labi, ka arī 692 00:32:24,390 --> 00:32:29,890 būs 0, jo par šī kreisā izpausme, lai būtu patiesība, vai 1, 693 00:32:29,890 --> 00:32:32,360 tas būtu nepieciešams, lai būtu patiesība un taisnība. 694 00:32:32,360 --> 00:32:36,320 Bet šeit mums ir nepatiesa un patiess, vai 0 un 1. 695 00:32:36,320 --> 00:32:42,000 Tagad atkal, ja mums ir 1 aizvieto & zīmes 0, ka, arī, būs 0, 696 00:32:42,000 --> 00:32:47,240 un, ja mums ir 1 aizvieto & zīmes 1, beidzot mums ir 1 bit. 697 00:32:47,240 --> 00:32:50,340 Tātad citiem vārdiem sakot, mēs nedarām kaut kas interesants ar šo operatoru 698 00:32:50,340 --> 00:32:51,850 tikai vēl, šī zīme operators. 699 00:32:51,850 --> 00:32:53,780 Tas ir Bitu līmeņa un operators. 700 00:32:53,780 --> 00:32:57,290 Bet tie ir sastāvdaļas caur kuru mēs varam darīt 701 00:32:57,290 --> 00:32:59,240 interesantas lietas, kā mēs drīz redzēt. 702 00:32:59,240 --> 00:33:02,790 >> Tagad aplūkosim tikai vienotais vertikāla josla nekā šeit labajā pusē. 703 00:33:02,790 --> 00:33:06,710 Ja man ir 0, mazliet, un es VAI tas ar, Bitu līmeņa 704 00:33:06,710 --> 00:33:11,030 Vai operators, cits 0 bit, kas notiek, lai dotu man 0. 705 00:33:11,030 --> 00:33:17,540 Ja es ņemtu 0 mazliet un vai IT ar 1 bit, tad es esmu gatavojas iegūt 1. 706 00:33:17,540 --> 00:33:19,830 Un patiesībā, tikai skaidrība, ļaujiet man iet atpakaļ, 707 00:33:19,830 --> 00:33:23,380 tāpēc, ka mani vertikālie stieņi nav sajaukt 1 s. 708 00:33:23,380 --> 00:33:26,560 Ļaujiet man pārrakstīt visu mans 1 ir nedaudz vairāk 709 00:33:26,560 --> 00:33:32,700 skaidri, lai mēs blakus redzēt, ja es ir 1 vai 0, kas notiek, ir 1, 710 00:33:32,700 --> 00:33:39,060 un ja man ir 1 vai 1, ka, pārāk, būs 1. 711 00:33:39,060 --> 00:33:42,900 Tātad jūs varat redzēt, loģiski, ka OR Operators uzvedas ļoti atšķirīgi. 712 00:33:42,900 --> 00:33:48,070 Tas dod man 0 vai 0 dod man 0, bet katru otro kombinācija dod man 1. 713 00:33:48,070 --> 00:33:52,480 Tik ilgi, kamēr man ir viens 1 formula, rezultāts būs 1. 714 00:33:52,480 --> 00:33:55,580 >> Savukārt ar AND operators, Ampersand, 715 00:33:55,580 --> 00:34:00,940 tikai tad, ja man ir divi 1 ir iekļauts vienādojums, man tiešām iegūt 1 no. 716 00:34:00,940 --> 00:34:02,850 Tagad tur ir dažas citas operatoriem, kā arī. 717 00:34:02,850 --> 00:34:04,810 Viens no tiem ir mazliet vairāk iesaistīties. 718 00:34:04,810 --> 00:34:07,980 Tāpēc ļaujiet man iet uz priekšu un dzēst tas, lai atbrīvotu dažas vietas. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Un pieņemsim ieskatieties caret simbols, tikai brīdi. 721 00:34:16,460 --> 00:34:18,210 Tas parasti ir raksturs jūs varat ierakstīt 722 00:34:18,210 --> 00:34:21,420 uz klaviatūras saimniecības Shift un tad viens no numuriem atop jūsu ASV 723 00:34:21,420 --> 00:34:22,250 tastatūra. 724 00:34:22,250 --> 00:34:26,190 >> Tātad šis ir ekskluzīvs Vai operators, ekskluzīva OR. 725 00:34:26,190 --> 00:34:27,790 Tātad mēs vienkārši redzēja vai operators. 726 00:34:27,790 --> 00:34:29,348 Šī ir ekskluzīva vai operators. 727 00:34:29,348 --> 00:34:30,639 Kas patiesībā ir atšķirība? 728 00:34:30,639 --> 00:34:34,570 Nu pieņemsim tikai apskatīt formulu, un izmantot to kā sastāvdaļas galu galā. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Es esmu gatavojas teikt, ir vienmēr 0. 731 00:34:39,650 --> 00:34:41,400 Tas ir definīcija XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 būs 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 būs 1, un 1 XOR 1 būs? 734 00:34:58,810 --> 00:34:59,890 Nepareizi? 735 00:34:59,890 --> 00:35:00,520 Vai ne? 736 00:35:00,520 --> 00:35:01,860 Es nezinu. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Tagad to, kas notiek šeit? 739 00:35:04,700 --> 00:35:06,630 Nu domāt par Nosaukums šī operatora. 740 00:35:06,630 --> 00:35:09,980 Exclusive OR, tā kā nosaukums, veids, liecina, 741 00:35:09,980 --> 00:35:13,940 atbilde ir tikai būs 1, ja izejvielas ir ekskluzīvas, 742 00:35:13,940 --> 00:35:15,560 tikai atšķirīgs. 743 00:35:15,560 --> 00:35:18,170 Tātad šeit izejvielas ir Tas pats, tāpēc rezultāts ir 0. 744 00:35:18,170 --> 00:35:20,700 Šeit izejvielas ir Tas pats, tāpēc rezultāts ir 0. 745 00:35:20,700 --> 00:35:25,640 Šeit ir rezultāti ir atšķirīgi, tie ir ekskluzīvas, un tā rezultāts ir 1. 746 00:35:25,640 --> 00:35:28,190 Tātad, tas ir ļoti līdzīgs Un tas ir ļoti līdzīgs, 747 00:35:28,190 --> 00:35:32,760 vai drīzāk tas ir ļoti līdzīgs OR, bet tikai ekskluzīvā veidā. 748 00:35:32,760 --> 00:35:36,210 Tas viens vairs nav 1, jo mums ir divi 1 s, 749 00:35:36,210 --> 00:35:38,621 un ne tikai, tikai viens no tiem. 750 00:35:38,621 --> 00:35:39,120 Viss kārtībā. 751 00:35:39,120 --> 00:35:40,080 Kas par citiem? 752 00:35:40,080 --> 00:35:44,220 Nu tildes, tikmēr, ir tiešām jauks un vienkāršs, par laimi. 753 00:35:44,220 --> 00:35:46,410 Un tas ir unary operators, kas nozīmē, 754 00:35:46,410 --> 00:35:50,400 tas ir piemērots tikai vienu ieejas, viens operands, lai runāt. 755 00:35:50,400 --> 00:35:51,800 Nav pa kreiso un tiesības. 756 00:35:51,800 --> 00:35:56,050 Citiem vārdiem sakot, ja jūs lietojat tildi no 0, atbilde būs pretējs. 757 00:35:56,050 --> 00:35:59,710 Un, ja jūs lietojat Tilde par 1, Atbilde būs pretējs. 758 00:35:59,710 --> 00:36:02,570 Tātad tildes operators ir veids, noliedzot mazliet, 759 00:36:02,570 --> 00:36:06,000 vai flipping mazliet no 0 līdz 1, vai 1 līdz 0. 760 00:36:06,000 --> 00:36:09,820 >> Un tas atstāj mūs beidzot tikai ar diviem gala operatoru, 761 00:36:09,820 --> 00:36:13,840 tā saukto kreiso maiņu, un tā saukto labo nobīdes operators. 762 00:36:13,840 --> 00:36:16,620 Pieņemsim to apskatīt, kā šie darbā. 763 00:36:16,620 --> 00:36:20,780 Kreisā maiņu operators, rakstisks ar divām iekavām, piemēram, ka, 764 00:36:20,780 --> 00:36:22,110 darbojas šādi. 765 00:36:22,110 --> 00:36:27,390 Ja mans ieguldījums, vai mans operands, pa kreisi pāreja operators ir diezgan vienkārši 1. 766 00:36:27,390 --> 00:36:33,750 Un es tad pateikt datora uz atstāja maiņu, ka 1., teiksim septiņas vietas, 767 00:36:33,750 --> 00:36:37,150 rezultāts ir tā, it kā I pieņemt, ka 1, un pārvietot to 768 00:36:37,150 --> 00:36:40,160 septiņas vietas, nekā uz pa kreisi, un pēc noklusējuma, 769 00:36:40,160 --> 00:36:42,270 mēs spēsim pieņemt, ka telpa pa labi 770 00:36:42,270 --> 00:36:44,080 tiks polsterētām ar nullēm. 771 00:36:44,080 --> 00:36:50,316 Citiem vārdiem sakot, 1 atstāja pāreja 7 dodas man dot ka 1, kam seko 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 nullēm. 773 00:36:54,060 --> 00:36:57,380 Tātad tādā veidā, tas ļauj jums veikt nelielu skaitu, piemēram, 1, 774 00:36:57,380 --> 00:37:00,740 un skaidri padarīt to daudz daudz, daudz lielāks šādā veidā, 775 00:37:00,740 --> 00:37:06,460 bet mēs patiešām gatavojas, lai redzētu vairāk gudrs pieejas to 776 00:37:06,460 --> 00:37:08,080 vietā, kā arī, 777 00:37:08,080 --> 00:37:08,720 >> Viss kārtībā. 778 00:37:08,720 --> 00:37:10,060 Tas ir tas par nedēļu trīs. 779 00:37:10,060 --> 00:37:11,400 Mēs redzēsim jums nākamo reizi. 780 00:37:11,400 --> 00:37:12,770 Tas bija CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Mūzikas atskaņošanai] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: Viņš bija pie uzkodām bārs ēst karstu izdomājums Sundae. 784 00:37:25,766 --> 00:37:28,090 Viņš bija to visu pār viņa seju. 785 00:37:28,090 --> 00:37:30,506 Viņš valkā, ka šokolāde, piemēram bārdu 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Ko tu dari? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Ko? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: Vai jūs vienkārši double dip? 790 00:37:36,800 --> 00:37:38,585 Jūs double tuvās mikroshēmā. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Piedodiet. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: Jūs tuvās mikroshēmu, jūs paņēma uzkost, un jūs tuvās atkal. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 SPEAKER 2: Tātad, tas ir, piemēram, liekot visa tava mute pa labi krituma. 795 00:37:48,440 --> 00:37:52,400 Nākamreiz mikroshēmu, tikai iemērc to vienu reizi, un izbeigt. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Tu zini, ko, Dan? 797 00:37:53,890 --> 00:37:58,006 Jūs iemērc tā, kā jūs vēlaties, lai iemērc. 798 00:37:58,006 --> 00:38:01,900 Es iemērkšana tā, ka es gribu, lai iemērkšana. 799 00:38:01,900 --> 00:38:03,194