1 00:00:00,000 --> 00:00:11,904 >> [Muzika] 2 00:00:11,904 --> 00:00:12,910 >> PROFESORI: Në rregull. 3 00:00:12,910 --> 00:00:16,730 Kjo është CS50 dhe kjo është fundi i javës së tretë. 4 00:00:16,730 --> 00:00:20,230 Pra, ne jemi sot këtu, jo në Sanders Teatri, në vend të kësaj në Weidner Bibliotekën. 5 00:00:20,230 --> 00:00:23,170 Brenda e cila është një studio i njohur si Hauser Studio, 6 00:00:23,170 --> 00:00:28,310 apo do të themi Studio H, apo duhet të ne say-- Nëse ju ka gëzuar këtë shaka, 7 00:00:28,310 --> 00:00:30,540 është e vërtetë nga shok klase, Mark, online, 8 00:00:30,540 --> 00:00:32,420 i cili sugjeroi sa më shumë nëpërmjet Twitter. 9 00:00:32,420 --> 00:00:34,270 Tani çfarë është e ftohtë në lidhje qenë këtu në një studio 10 00:00:34,270 --> 00:00:38,410 është se unë jam e rrethuar nga këto jeshile muret, një ekran të gjelbër ose chromakey, 11 00:00:38,410 --> 00:00:43,290 kështu që të flasin, që do të thotë se CS50-së ekipi i prodhimit, unbeknownst për mua 12 00:00:43,290 --> 00:00:47,380 tani, mund të jetë duke mua më kudo në botë, 13 00:00:47,380 --> 00:00:48,660 për mirë apo për keq. 14 00:00:48,660 --> 00:00:51,800 >> Tani çfarë shtrihet përpara, problemi vendosur dy është në duart tuaja për këtë javë, 15 00:00:51,800 --> 00:00:53,830 por me problemin e ngritur tri këtë javë që vjen, 16 00:00:53,830 --> 00:00:56,600 ju do të sfidohet me e ashtuquajtura lojë e 15, 17 00:00:56,600 --> 00:00:58,960 një favor të vjetër parti që ju mund të kujtojnë marrjen 18 00:00:58,960 --> 00:01:02,030 si një fëmijë që ka një bandë e tërë e numrave që mund të rrëshqitje lart, poshtë, 19 00:01:02,030 --> 00:01:05,790 majtë dhe të djathtë, dhe ka një hendek brenda enigmës, në të cilën ju 20 00:01:05,790 --> 00:01:07,840 në fakt mund të rrëshqas ato copa mister. 21 00:01:07,840 --> 00:01:11,150 Në fund të fundit ju merrni këtë mister në një mënyrë gjysmë të rastit, 22 00:01:11,150 --> 00:01:12,940 dhe qëllimi është për të zgjidhur atë, lartë deri në fund, 23 00:01:12,940 --> 00:01:16,310 majta në të djathtë, nga një të gjithë rrugën deri me 15. 24 00:01:16,310 --> 00:01:19,360 >> Për fat të keq, zbatimi ju do të keni në dorë 25 00:01:19,360 --> 00:01:21,590 do të jetë software bazuar, jo fizikisht. 26 00:01:21,590 --> 00:01:25,280 Ju jeni të vërtetë do të ketë për të shkruar Kodi me të cilin një student ose përdorues mund të 27 00:01:25,280 --> 00:01:26,760 luajnë lojë e 15. 28 00:01:26,760 --> 00:01:29,030 Dhe në fakt, në hacker botim i lojës së 15, 29 00:01:29,030 --> 00:01:32,155 ju do të jetë një sfidë për të zbatuar, jo vetëm duke luajtur e kësaj shkolle të vjetër 30 00:01:32,155 --> 00:01:35,010 lojë, por zgjidhja e saj, zbatimin mënyrën zot, 31 00:01:35,010 --> 00:01:38,280 kështu që të flasin, që në fakt zgjidh mister për të njeriut, 32 00:01:38,280 --> 00:01:41,080 duke u ofruar atyre me aluzion, pas aluzion, pas aluzion. 33 00:01:41,080 --> 00:01:42,280 Pra, më shumë në atë javën e ardhshme. 34 00:01:42,280 --> 00:01:43,720 Por kjo është ajo që shtrihet përpara. 35 00:01:43,720 --> 00:01:47,610 >> Tani për tani kujtojmë se më herët këtë javë kemi pasur këtë cliffhanger, në qoftë se ju do të, 36 00:01:47,610 --> 00:01:52,560 ku më të mirë ne ishim duke bërë klasifikim i urtë ishte një kufi i sipërm i madh o të n 37 00:01:52,560 --> 00:01:53,210 katror. 38 00:01:53,210 --> 00:01:56,520 Me fjalë të tjera, flluskë lloj, lloj përzgjedhje, futje lloj, 39 00:01:56,520 --> 00:01:59,120 të gjitha prej tyre, ndërsa të ndryshme në zbatimin e tyre, 40 00:01:59,120 --> 00:02:03,480 transferuar në një n katror drejtimin kohë në rastin më të keq. 41 00:02:03,480 --> 00:02:06,010 Dhe ne përgjithësi të supozojmë se rastin më të keq për klasifikim 42 00:02:06,010 --> 00:02:08,814 është ai që inputeve tuaj janë krejtësisht prapa. 43 00:02:08,814 --> 00:02:11,980 Dhe me të vërtetë, ai mori mjaft disa hapa për të zbatuar secili prej këtyre algoritmeve. 44 00:02:11,980 --> 00:02:15,110 >> Tani në fund të klasës së Recall, ne krahasim flluskë lloj 45 00:02:15,110 --> 00:02:19,390 kundër lloj përzgjedhjes kundër një tjetër që ne e quajti lloj bashkojë në atë kohë, 46 00:02:19,390 --> 00:02:22,120 dhe unë propozoj që ajo është duke marrë Përparësia e një mësim nga javë 47 00:02:22,120 --> 00:02:24,060 zero, përça dhe sundo. 48 00:02:24,060 --> 00:02:28,810 Dhe disi arritjen e disa lloj logaritmike running kohë në fund të fundit, 49 00:02:28,810 --> 00:02:31,024 në vend të diçka kjo është thjesht katror. 50 00:02:31,024 --> 00:02:33,440 Dhe kjo nuk është mjaft logaritmike, kjo është pak më shumë se kaq. 51 00:02:33,440 --> 00:02:36,520 Por nëse ju kujtohet nga klasa, ajo ishte shumë, shumë më të shpejtë. 52 00:02:36,520 --> 00:02:38,210 Le të bëjmë një vështrim në ku ne u ndërpre. 53 00:02:38,210 --> 00:02:41,880 54 00:02:41,880 --> 00:02:45,370 >> Bubble lloj kundrejt përzgjedhjes lloj kundrejt merge lloji. 55 00:02:45,370 --> 00:02:47,700 Tani ata janë të gjithë në punë, në teori, në të njëjtën kohë. 56 00:02:47,700 --> 00:02:50,510 CPU po kandidon në të njëjtën shpejtësi. 57 00:02:50,510 --> 00:02:54,990 Por ju mund të ndjeheni si i mërzitshëm ky po shumë shpejt do të bëhet, 58 00:02:54,990 --> 00:02:58,790 dhe se sa shpejt, kur kemi të injektuar pak e algoritme të javës zero-së, 59 00:02:58,790 --> 00:03:00,080 mund të shpejtojë gjërat. 60 00:03:00,080 --> 00:03:01,630 >> Kështu lloj shenjë duket e mahnitshme. 61 00:03:01,630 --> 00:03:05,220 Si mund të levave atë, në mënyrë që për të zgjidhur numra më shpejt. 62 00:03:05,220 --> 00:03:07,140 E pra, le të mendoj se mbrapa për një përbërës që 63 00:03:07,140 --> 00:03:10,380 kishte mbrapa në javën zero, që i kërkim për dikë në një libër telefoni, 64 00:03:10,380 --> 00:03:12,380 dhe kujtojnë se pseudokod që kemi propozuar, 65 00:03:12,380 --> 00:03:14,560 nëpërmjet të cilës ne mund të gjeni dikush si Mike Smith, 66 00:03:14,560 --> 00:03:16,310 dukej një diçka të vogël si kjo. 67 00:03:16,310 --> 00:03:20,820 >> Tani të marrë një sy në veçanti në përputhje 7 dhe 8, dhe 10 dhe 11, 68 00:03:20,820 --> 00:03:25,240 të cilat shkaktojnë këtë lak, me të cilin ne kemi mbajtur duke shkuar prapa në linjë 3 përsëri, dhe përsëri, 69 00:03:25,240 --> 00:03:26,520 dhe përsëri. 70 00:03:26,520 --> 00:03:31,790 Por kjo rezulton se ne mund të shikoni ky algoritëm, këtu në pseudokod, 71 00:03:31,790 --> 00:03:33,620 pak më shumë në mënyrë holistike. 72 00:03:33,620 --> 00:03:35,960 Në fakt, ajo që unë jam duke kërkuar në këtu në ekran, 73 00:03:35,960 --> 00:03:41,180 është një algoritmi për kërkim të Mike Smith në mesin e një sërë faqesh. 74 00:03:41,180 --> 00:03:45,520 Dhe me të vërtetë, ne mund të thjeshtojë këtë algorithm në ato linja 7 dhe 8, 75 00:03:45,520 --> 00:03:49,860 dhe 10 dhe 11 të them vetëm këtë, që unë kam paraqitur këtu në të verdhë. 76 00:03:49,860 --> 00:03:52,210 Me fjalë të tjera, në qoftë se Mike Smith është parë në libër, 77 00:03:52,210 --> 00:03:55,004 ne nuk kemi nevojë të specifikojë hap hapi tani se si të shkojë gjetur atë. 78 00:03:55,004 --> 00:03:56,920 Ne nuk duhet të specifikojë për të shkuar mbrapa në linjë 3, 79 00:03:56,920 --> 00:03:58,960 Pse nuk kemi vetëm në vend të kësaj, të themi, më në përgjithësi, 80 00:03:58,960 --> 00:04:01,500 kërkoni për Mike në gjysma e majtë e librit. 81 00:04:01,500 --> 00:04:03,960 >> Në anën tjetër, nëse është Mike në fakt më vonë në libër, 82 00:04:03,960 --> 00:04:07,540 pse nuk kemi vetëm të japin kuotën kërkimin siç janë quajtur ato për Mike në gjysmën e djathtë të librit. 83 00:04:07,540 --> 00:04:11,030 Me fjalë të tjera, pse nuk e bëjmë ne vetëm lloj i vë bast për veten duke i thënë: 84 00:04:11,030 --> 00:04:13,130 kërkoni për Mike në këtë mesin e librit, 85 00:04:13,130 --> 00:04:16,279 dhe të lënë atë për ekzistuese tonë algorithm për të na tregoni 86 00:04:16,279 --> 00:04:18,750 si për të kërkuar për Mike në se gjysma e majtë e librit. 87 00:04:18,750 --> 00:04:20,750 Me fjalë të tjera, tonë algorithm punon nëse kjo është 88 00:04:20,750 --> 00:04:24,670 një libër telefon i këtij trashësi, e kjo trashësi, ose ndonjë trashësi whatsoever. 89 00:04:24,670 --> 00:04:27,826 Pra, ne mund Recursively përcaktojnë këtë algorithm. 90 00:04:27,826 --> 00:04:29,950 Me fjalë të tjera, mbi ekran këtu, është një algoritëm 91 00:04:29,950 --> 00:04:33,130 për kërkim për Mike Smith ndër faqet e një libri të telefonit. 92 00:04:33,130 --> 00:04:37,410 Pra, në përputhje 7 dhe 10, le të vetëm të them saktësisht se. 93 00:04:37,410 --> 00:04:40,250 Dhe unë e përdorin këtë term një moment më parë, dhe në të vërtetë, recursion 94 00:04:40,250 --> 00:04:42,450 është buzzword për tani, dhe kjo është ky proces 95 00:04:42,450 --> 00:04:47,210 të bërë diçka ciklike nga disi duke përdorur kodin që ju tashmë e keni, 96 00:04:47,210 --> 00:04:49,722 dhe duke e quajtur atë përsëri, dhe përsëri, dhe përsëri. 97 00:04:49,722 --> 00:04:51,930 Tani ajo do të jetë e rëndësishme se ne disi fund 98 00:04:51,930 --> 00:04:53,821 jashtë, dhe nuk e bëjmë atë pafundësisht të gjatë. 99 00:04:53,821 --> 00:04:56,070 Përndryshe ne do të kanë me të vërtetë një lak pafund. 100 00:04:56,070 --> 00:04:59,810 Por le të shohim nëse ne mund të marrë hua këtë ide e një recursion, duke bërë diçka përsëri 101 00:04:59,810 --> 00:05:03,600 dhe përsëri dhe përsëri, për të zgjidhur problemi sorting nëpërmjet bashkohen 102 00:05:03,600 --> 00:05:05,900 lloj, të gjithë më efikase. 103 00:05:05,900 --> 00:05:06,970 >> Kështu që unë ju jap bashkojë lloj. 104 00:05:06,970 --> 00:05:07,920 Le të marrin një vështrim. 105 00:05:07,920 --> 00:05:10,850 Kështu që këtu është pseudokod, me të cilat ne mund të zbatojë klasifikim, 106 00:05:10,850 --> 00:05:12,640 duke përdorur këtë algoritëm të quajtur bashkojë lloj. 107 00:05:12,640 --> 00:05:13,880 Dhe kjo është mjaft e thjesht kjo. 108 00:05:13,880 --> 00:05:15,940 Në të dhënat e elementeve n, me fjalë të tjera, në qoftë se ju jeni 109 00:05:15,940 --> 00:05:18,830 duke pasur parasysh n elemente dhe numrat dhe letra ose çfarëdo input është, 110 00:05:18,830 --> 00:05:22,430 në qoftë se ju jeni duke i dhënë elementet n, nëse n është më pak se 2, vetëm kthehen. 111 00:05:22,430 --> 00:05:22,930 E drejtë? 112 00:05:22,930 --> 00:05:26,430 Sepse nëse n është më pak se 2, që do të thotë se lista ime e elementeve 113 00:05:26,430 --> 00:05:30,446 ose është i madhësisë 0 ose 1, dhe në të dy këto raste të parëndësishme, 114 00:05:30,446 --> 00:05:31,570 lista është renditur tashmë. 115 00:05:31,570 --> 00:05:32,810 Nëse nuk ka lista, është e renditura. 116 00:05:32,810 --> 00:05:35,185 Dhe në qoftë se ka një listë të gjatësisë 1, është e renditura qartë. 117 00:05:35,185 --> 00:05:38,280 Pra, algoritmi ka nevojë vetëm për të me të vërtetë të bëjë diçka interesante, 118 00:05:38,280 --> 00:05:40,870 në qoftë se ne kemi dy ose më shumë Elementet e dhënë për të na. 119 00:05:40,870 --> 00:05:42,440 Pra, le të shohim në magji pastaj. 120 00:05:42,440 --> 00:05:47,500 Tjetër lloj gjysmën e majtë të elementeve, pastaj lloj gjysmën e djathtë të elementeve, 121 00:05:47,500 --> 00:05:49,640 pastaj bashkojë gjysmave renditur. 122 00:05:49,640 --> 00:05:52,440 Dhe çfarë është lloj i mendjes bending këtu, është se unë nuk të vërtetë 123 00:05:52,440 --> 00:05:56,190 duket se kanë thënë çdo gjë vetëm ende, e drejtë? 124 00:05:56,190 --> 00:05:59,560 Të gjitha unë kam thënë po, jepet një listë të Elementet n, lloj gjysmën e majtë, 125 00:05:59,560 --> 00:06:01,800 atëherë gjysma e drejtë, atëherë bashkojë gjysmave të renditura, 126 00:06:01,800 --> 00:06:03,840 por ku është prevede aktual sekret? 127 00:06:03,840 --> 00:06:05,260 Ku është algoritmi? 128 00:06:05,260 --> 00:06:09,150 E pra kjo rezulton se këto dy linja së pari, u largua lloj gjysma e elementeve, 129 00:06:09,150 --> 00:06:13,970 dhe lloj të drejtën gjysmën e elementeve, thirrje gjithkund rekursive, kështu që të flasin. 130 00:06:13,970 --> 00:06:16,120 >> Pas të gjitha, në këtë pikë në kohë, nuk kam 131 00:06:16,120 --> 00:06:18,950 një algoritmi me të cilin do të zgjidhur një bandë e tërë e elementeve? 132 00:06:18,950 --> 00:06:19,450 Po. 133 00:06:19,450 --> 00:06:20,620 Kjo është e drejtë këtu. 134 00:06:20,620 --> 00:06:25,180 Kjo është e drejtë këtu në ekran, dhe kështu që unë mund të përdorni atë grup të njëjtë të hapave 135 00:06:25,180 --> 00:06:28,500 për të zgjidhur gjysmën e majtë, si unë mund gjysma e drejtë. 136 00:06:28,500 --> 00:06:30,420 Dhe me të vërtetë, përsëri, dhe përsëri. 137 00:06:30,420 --> 00:06:34,210 Pra, në njëfarë mënyre apo tjetër, dhe ne do të së shpejti shihni këtë, magjinë e merge lloj 138 00:06:34,210 --> 00:06:37,967 është ngulitur në se shumë finale line, bashkimi gjysmave të renditura. 139 00:06:37,967 --> 00:06:39,300 Dhe kjo duket mjaft intuitiv. 140 00:06:39,300 --> 00:06:41,050 Ju merrni dy gjysmave, dhe ju, disi, bashkojë ato së bashku, 141 00:06:41,050 --> 00:06:43,260 dhe ne do të shohim këtë konkretisht në një moment. 142 00:06:43,260 --> 00:06:45,080 >> Por kjo është një algoritëm i plotë. 143 00:06:45,080 --> 00:06:46,640 Dhe le të shohim saktësisht pse. 144 00:06:46,640 --> 00:06:50,912 Pra mendoj se ne jemi duke i dhënë këto njëjtë tetë elemente këtu në ekran, një 145 00:06:50,912 --> 00:06:53,120 nëpërmjet tetë, por ata janë në mënyrë që në dukje të rastit. 146 00:06:53,120 --> 00:06:55,320 Dhe qëllimi në fjalë është për të zgjidhur këto elemente. 147 00:06:55,320 --> 00:06:58,280 Mirë se si mund të shkoj në lidhje me bërë atë duke përdorur, përsëri, 148 00:06:58,280 --> 00:07:00,407 shkrihen lloj, sipas këtij pseudokod? 149 00:07:00,407 --> 00:07:02,740 Dhe përsëri, ngjyer këtë në mendjen tuaj, për vetëm një moment. 150 00:07:02,740 --> 00:07:05,270 Rasti i parë është shumë e i parëndësishëm, në qoftë se ajo është më pak se 2, 151 00:07:05,270 --> 00:07:07,060 vetëm të kthehet, nuk ka punë për t'u bërë. 152 00:07:07,060 --> 00:07:09,290 Pra, me të vërtetë ka vetëm tre hapa për të vërtetë të mbajtur në mendje. 153 00:07:09,290 --> 00:07:11,081 Përsëri, dhe përsëri, unë jam do të duan të kenë 154 00:07:11,081 --> 00:07:13,980 për të zgjidhur gjysmën e majtë, lloj gjysmën e djathtë, 155 00:07:13,980 --> 00:07:15,890 dhe pastaj një herë e tyre dy gjysmat janë të renditura, 156 00:07:15,890 --> 00:07:18,710 Unë dua të bashkojë ata së bashku në një listë të rradhitur. 157 00:07:18,710 --> 00:07:19,940 Pra, mbani në mend. 158 00:07:19,940 --> 00:07:21,310 >> Kështu që këtu është lista origjinale. 159 00:07:21,310 --> 00:07:23,510 Le të trajtojnë këtë si një array, pasi kemi filluar të 160 00:07:23,510 --> 00:07:25,800 në javë dy, e cila është një bllok puqur e kujtesës. 161 00:07:25,800 --> 00:07:28,480 Në këtë rast, që përmban tetë numra, për të kthyer prapa në shpinë. 162 00:07:28,480 --> 00:07:30,700 Dhe tani le të aplikojnë bashkojë lloj. 163 00:07:30,700 --> 00:07:33,300 Kështu që unë së pari dua të lloj gjysmën e majtë të kësaj liste, 164 00:07:33,300 --> 00:07:37,370 dhe le të, prandaj, përqëndrohet në 4, 8, 6, dhe 2. 165 00:07:37,370 --> 00:07:41,000 >> Tani si mund të shkoni në lidhje me klasifikim një listë të madhësisë 4? 166 00:07:41,000 --> 00:07:45,990 E pra unë duhet të marrin në konsideratë tani klasifikim të majtë të pjesës së majtë. 167 00:07:45,990 --> 00:07:47,720 Përsëri, le të Rewind për vetëm një moment. 168 00:07:47,720 --> 00:07:51,010 Nëse pseudokod është kjo, dhe unë jam duke i dhënë tetë elemente, 169 00:07:51,010 --> 00:07:53,230 8 është padyshim më e madhe se ose e barabartë me 2. 170 00:07:53,230 --> 00:07:54,980 Pra, me rasti i parë nuk zbatohet. 171 00:07:54,980 --> 00:07:58,120 Pra, për të zgjidhur tetë elemente, unë së pari lloj gjysmën e majtë të elementeve, 172 00:07:58,120 --> 00:08:01,930 atëherë unë lloj gjysmën e duhur, atëherë unë bashkojë të dy gjysmat renditura, secila me madhësi 4. 173 00:08:01,930 --> 00:08:02,470 NE RREGULL. 174 00:08:02,470 --> 00:08:07,480 >> Por në qoftë se ju keni më tha vetëm, të lloj gjysma e majtë, e cila tani është e madhësisë 4, 175 00:08:07,480 --> 00:08:09,350 si mund ta zgjidhur gjysmën e majtë? 176 00:08:09,350 --> 00:08:11,430 E pra, nëse unë kam një të dhëna të katër elementeve, 177 00:08:11,430 --> 00:08:14,590 Unë së pari lloj majtë dy, atëherë e drejta e dy, 178 00:08:14,590 --> 00:08:16,210 dhe pastaj unë bashkojë ato së bashku. 179 00:08:16,210 --> 00:08:18,700 Pra, përsëri, kjo bëhet pak e një mendje lojë lakimi këtu, 180 00:08:18,700 --> 00:08:21,450 sepse ti, lloj, duhet të mbani mend se ku je në histori, 181 00:08:21,450 --> 00:08:23,620 por në fund të ditës, dhënë ndonjë numër të elementeve, 182 00:08:23,620 --> 00:08:25,620 ju së pari doni të lloj gjysma e majtë, atëherë gjysma e drejtë, 183 00:08:25,620 --> 00:08:26,661 pastaj bashkojë ato së bashku. 184 00:08:26,661 --> 00:08:28,630 Le të fillojë për të bërë pikërisht atë. 185 00:08:28,630 --> 00:08:30,170 Ja input i tetë elementeve. 186 00:08:30,170 --> 00:08:31,910 Tani ne jemi duke kërkuar në gjysmën e majtë këtu. 187 00:08:31,910 --> 00:08:33,720 Si mund të zgjidhur katër elemente? 188 00:08:33,720 --> 00:08:35,610 Edhe unë së pari zgjidhur gjysmën e majtë. 189 00:08:35,610 --> 00:08:37,720 Tani si mund ta zgjidhur gjysmën e majtë? 190 00:08:37,720 --> 00:08:39,419 E pra unë kam qenë dhënë dy elemente. 191 00:08:39,419 --> 00:08:41,240 Pra, le të zgjidhur këto dy elemente. 192 00:08:41,240 --> 00:08:44,540 2 është më e madhe se ose e e barabartë me 2, sigurisht. 193 00:08:44,540 --> 00:08:46,170 Kështu që rasti i parë nuk zbatohet. 194 00:08:46,170 --> 00:08:49,010 >> Kështu që unë tani keni për të zgjidhur majtë gjysma e këtyre dy elementeve. 195 00:08:49,010 --> 00:08:50,870 Gjysmën e majtë, natyrisht, është vetëm 4. 196 00:08:50,870 --> 00:08:54,020 Pra, si mund unë të zgjidhur një listë të një elementi? 197 00:08:54,020 --> 00:08:57,960 E pra tani, se rasti i veçantë bazë deri të lartë, kështu që të flasin, vlen. 198 00:08:57,960 --> 00:09:01,470 1 është më pak se 2, dhe kur Lista është me të vërtetë e madhësisë 1. 199 00:09:01,470 --> 00:09:02,747 Kështu që unë vetëm të kthehen. 200 00:09:02,747 --> 00:09:03,580 Unë nuk bëj asgjë. 201 00:09:03,580 --> 00:09:06,770 Dhe me të vërtetë, të shikojmë se çfarë kam bërë, 4 është renditur tashmë. 202 00:09:06,770 --> 00:09:09,220 Ashtu si unë jam tashmë pjesërisht i suksesshëm këtu. 203 00:09:09,220 --> 00:09:11,750 >> Tani që duket lloj i trashë për të kërkuar, por është e vërtetë. 204 00:09:11,750 --> 00:09:13,700 4 është një listë e madhësisë 1. 205 00:09:13,700 --> 00:09:15,090 Është renditura tashmë. 206 00:09:15,090 --> 00:09:16,270 Kjo është gjysma e majtë. 207 00:09:16,270 --> 00:09:18,010 Tani unë lloj gjysmën e djathtë. 208 00:09:18,010 --> 00:09:22,310 Input ime është një element, 8 Në mënyrë të ngjashme, të renditura tashmë. 209 00:09:22,310 --> 00:09:25,170 Stupid, gjithashtu, por përsëri, ky parim themelor 210 00:09:25,170 --> 00:09:28,310 do të na lejojë të ndërtojmë tani në krye të kësaj sukses. 211 00:09:28,310 --> 00:09:32,260 4 renditura, 8 është e renditura, tani çfarë ishte se hapi i fundit? 212 00:09:32,260 --> 00:09:35,330 Pra, hapi i tretë dhe i fundit, çdo herë ju jeni klasifikim një listë, risjell, 213 00:09:35,330 --> 00:09:38,310 ishte që të bashkojë dy gjysmave, majtas dhe djathtas. 214 00:09:38,310 --> 00:09:39,900 Pra, le të bëjë pikërisht këtë. 215 00:09:39,900 --> 00:09:41,940 Gjysma ime e majtë është, natyrisht, 4. 216 00:09:41,940 --> 00:09:43,310 Gjysma ime e drejtë është 8. 217 00:09:43,310 --> 00:09:44,100 >> Pra, le ta bëjmë këtë. 218 00:09:44,100 --> 00:09:46,410 Së pari unë jam duke shkuar për të alokuar disa kujtesës shtesë, 219 00:09:46,410 --> 00:09:48,680 që unë do të përfaqësoj këtu, si vetëm një grup të mesme, 220 00:09:48,680 --> 00:09:49,660 kjo është mjaft e madhe për të përshtaten këtë. 221 00:09:49,660 --> 00:09:52,243 Por ju mund të imagjinoni shtrirë se drejtkëndësh të gjithë gjatësinë, 222 00:09:52,243 --> 00:09:53,290 në qoftë se ne kemi nevojë për më vonë. 223 00:09:53,290 --> 00:09:58,440 Si mund ta marrë 4 dhe 8, dhe shkrihen këto dy listat e madhësisë 1 së bashku? 224 00:09:58,440 --> 00:10:00,270 Këtu, gjithashtu, shumë e thjeshtë. 225 00:10:00,270 --> 00:10:03,300 4 vjen e para, pastaj vjen 8. 226 00:10:03,300 --> 00:10:07,130 Sepse në qoftë se unë dua të të lloj gjysma e majtë, atëherë gjysma e drejtë, 227 00:10:07,130 --> 00:10:09,900 dhe pastaj bashkojë këto dy gjysmave së bashku në mënyrë renditura, 228 00:10:09,900 --> 00:10:11,940 4 vjen e para, pastaj vjen 8. 229 00:10:11,940 --> 00:10:15,810 >> Pra, ne duket të jetë bërë përparim, madje edhe pse unë nuk kam bërë ndonjë punë aktuale. 230 00:10:15,810 --> 00:10:17,800 Por mos harroni se ku jemi në histori. 231 00:10:17,800 --> 00:10:19,360 Ne fillimisht mori tetë elemente. 232 00:10:19,360 --> 00:10:21,480 Ne renditura gjysmën e majtë, e cila është 4. 233 00:10:21,480 --> 00:10:24,450 Pastaj ne të renditura gjysmën e majtë e pjesës së majtë, e cila ishte 2. 234 00:10:24,450 --> 00:10:25,270 Dhe këtu ne do të shkojmë. 235 00:10:25,270 --> 00:10:26,920 Ne jemi duke bërë me këtë hap. 236 00:10:26,920 --> 00:10:29,930 >> Pra, nëse ne kemi renditur la gjysmën e 2, tani ne 237 00:10:29,930 --> 00:10:32,130 kanë për të zgjidhur gjysmën e djathtë të 2. 238 00:10:32,130 --> 00:10:35,710 Pra, gjysma e drejta e 2 është këto dy vlera këtu, 6 dhe 2. 239 00:10:35,710 --> 00:10:40,620 Pra, le të marrë tani një kontribut të madhësisë 2, dhe lloj gjysmën e majtë, dhe pastaj 240 00:10:40,620 --> 00:10:42,610 gjysma e drejtë, dhe pastaj bashkojë ato së bashku. 241 00:10:42,610 --> 00:10:45,722 Pra si mund të zgjidhur një listë të madhësisë 1, që përmban vetëm numrin 6? 242 00:10:45,722 --> 00:10:46,430 Unë jam bërë tashmë. 243 00:10:46,430 --> 00:10:48,680 Kjo listë e madhësisë 1 është e renditura. 244 00:10:48,680 --> 00:10:52,140 >> Si mund të zgjidhur një listë të madhësia 1, e ashtuquajtura gjysmë e drejtë. 245 00:10:52,140 --> 00:10:54,690 E pra kjo, gjithashtu, është e renditura tashmë. 246 00:10:54,690 --> 00:10:56,190 Numri 2 është e vetme. 247 00:10:56,190 --> 00:11:00,160 Deri tani unë kam dy gjysmave, majtas dhe e drejtë, unë duhet të bashkojë ato së bashku. 248 00:11:00,160 --> 00:11:01,800 Më lejoni të jap vetes një hapësirë ​​ekstra. 249 00:11:01,800 --> 00:11:05,580 Dhe të vënë 2 në atje, pastaj 6 në atje, duke 250 00:11:05,580 --> 00:11:10,740 sorting se lista, majtas dhe djathtas, dhe bashkimi atë së bashku, në fund të fundit. 251 00:11:10,740 --> 00:11:12,160 Kështu që unë jam në formë pak më të mirë. 252 00:11:12,160 --> 00:11:16,250 Unë nuk jam bërë, për shkak se në mënyrë të qartë 4, 8, 2, 6 nuk është urdhëruar fundit që unë dua. 253 00:11:16,250 --> 00:11:20,640 Por unë tani kanë dy listave të madhësisë 2, që kanë të dy, përkatësisht, janë të renditura. 254 00:11:20,640 --> 00:11:24,580 Kështu që tani, nëse ju Rewind në mendjen e juaj sy, ku bëri që na lënë? 255 00:11:24,580 --> 00:11:28,520 Unë fillova me tetë elemente, atëherë unë whittled atë poshtë për gjysmën e majtë të 4, 256 00:11:28,520 --> 00:11:31,386 atëherë gjysma e majtë e 2, dhe atëherë gjysma e drejta e 2, 257 00:11:31,386 --> 00:11:34,510 Kam mbaruar, pra, zgjidhja e majtë gjysma e 2, dhe gjysma e drejta e 2, 258 00:11:34,510 --> 00:11:37,800 kështu që çfarë është hapi i tretë dhe i fundit këtu? 259 00:11:37,800 --> 00:11:41,290 Unë duhet të bashkojë së bashku dy lista të madhësisë 2. 260 00:11:41,290 --> 00:11:42,040 Pra, le të shkojë përpara. 261 00:11:42,040 --> 00:11:43,940 Dhe në ekran këtu, japin mua disa kujtesës shtesë, 262 00:11:43,940 --> 00:11:47,170 edhe pse teknikisht, vëreni se unë kam mori një bandë e tërë e hapësirës deri bosh krye 263 00:11:47,170 --> 00:11:47,670 atje. 264 00:11:47,670 --> 00:11:50,044 Nëse unë dua të jetë veçanërisht hapësirë ​​efikas i mençur, 265 00:11:50,044 --> 00:11:52,960 Unë mund vetëm të fillojnë të lëvizin elementet mbrapa dhe me radhë, lartë dhe në fund. 266 00:11:52,960 --> 00:11:55,460 Por vetëm për qartësi vizuale, Unë jam duke shkuar për ta vënë atë poshtë, 267 00:11:55,460 --> 00:11:56,800 për të mbajtur gjërat bukur dhe të pastër. 268 00:11:56,800 --> 00:11:58,150 >> Kështu që unë kam marrë dy listave të madhësisë 2. 269 00:11:58,150 --> 00:11:59,770 Lista e parë ka 4 dhe 8. 270 00:11:59,770 --> 00:12:01,500 Lista e dytë ka 2 dhe 6. 271 00:12:01,500 --> 00:12:03,950 Le të bashkojë ato së bashku në mënyrë renditura. 272 00:12:03,950 --> 00:12:09,910 2, natyrisht, vjen e para, atëherë 4, pastaj 6, pastaj 8. 273 00:12:09,910 --> 00:12:12,560 Dhe tani ne duket të jenë marrë diku interesante. 274 00:12:12,560 --> 00:12:15,720 Gjysmë tani unë kam renditura nga lista, dhe rastësisht, kjo është 275 00:12:15,720 --> 00:12:18,650 të gjitha edhe numrat, por kjo është, me të vërtetë, vetëm një rastësi. 276 00:12:18,650 --> 00:12:22,220 Dhe unë tani kam renditura majtë gjysmë, kështu që është 2, 4, 6 dhe 8. 277 00:12:22,220 --> 00:12:23,430 Asgjë nuk është jashtë rendit. 278 00:12:23,430 --> 00:12:24,620 Që ndjehet si progres. 279 00:12:24,620 --> 00:12:26,650 >> Tani ajo ndjehet si e kam qenë duke folur përgjithmonë tani, 280 00:12:26,650 --> 00:12:29,850 kështu që ajo që mbetet për t'u parë nëse kjo algoritmi është, me të vërtetë, më efikase. 281 00:12:29,850 --> 00:12:31,766 Por, ne jemi duke shkuar nëpër atë super metodike. 282 00:12:31,766 --> 00:12:34,060 Një kompjuter, natyrisht, do ta bëjë atë si kjo. 283 00:12:34,060 --> 00:12:34,840 Pra, ku jemi ne? 284 00:12:34,840 --> 00:12:36,180 Ne kemi filluar me tetë elemente. 285 00:12:36,180 --> 00:12:37,840 Unë renditura gjysmën e majtë të 4. 286 00:12:37,840 --> 00:12:39,290 I duket për të bërë me atë. 287 00:12:39,290 --> 00:12:42,535 Pra, tani hapi tjetër është për të lloj gjysmën e djathtë të 4. 288 00:12:42,535 --> 00:12:44,410 Dhe kjo pjesë mund të shkojmë përmes një më të vogël 289 00:12:44,410 --> 00:12:47,140 shpejt, edhe pse ju jeni mirëpritur të Rewind, ose pushim, vetëm 290 00:12:47,140 --> 00:12:49,910 mendoj nëpërmjet saj në ritmin tuaj, por çfarë 291 00:12:49,910 --> 00:12:53,290 ne kemi tani është një mundësi për bëjë të njëjtën algorithm saktë në katër 292 00:12:53,290 --> 00:12:54,380 numra të ndryshëm. 293 00:12:54,380 --> 00:12:57,740 >> Pra, le të shkojnë përpara, dhe të përqëndrohet në gjysma e drejta, të cilat ne jemi këtu. 294 00:12:57,740 --> 00:13:01,260 Gjysma e majtë e që gjysmë të drejtë, dhe tani 295 00:13:01,260 --> 00:13:04,560 gjysma e majtë të majtë gjysma e atij gjysmën e djathtë, 296 00:13:04,560 --> 00:13:08,030 dhe si mund të zgjidhur një listë të madhësisë 1 që përmban vetëm numrin 1? 297 00:13:08,030 --> 00:13:09,030 Është bërë tashmë. 298 00:13:09,030 --> 00:13:11,830 Si mund ta bëjë të njëjtën gjë për një listë e madhësisë 1 përmban vetëm 7? 299 00:13:11,830 --> 00:13:12,840 Është bërë tashmë. 300 00:13:12,840 --> 00:13:16,790 Hapi i tretë për këtë gjysmë, atëherë është të bashkojë këto dy elemente 301 00:13:16,790 --> 00:13:20,889 në një listë të re të madhësisë 2, 1 dhe 7. 302 00:13:20,889 --> 00:13:23,180 Nuk duket të ketë bërë gjithçka Puna që shumë interesante. 303 00:13:23,180 --> 00:13:24,346 Le të shohim se çfarë ndodh më pas. 304 00:13:24,346 --> 00:13:29,210 Unë vetëm të renditura gjysmën e majtë të gjysma e djathtë e input tim origjinal. 305 00:13:29,210 --> 00:13:32,360 Tani le të lloj të drejtën gjysmë, e cila përmban 5 dhe 3. 306 00:13:32,360 --> 00:13:35,740 Le të shikojmë përsëri në të majtë gjysmë, të renditura, gjysmë e drejtë, të renditura, 307 00:13:35,740 --> 00:13:39,120 dhe bashkojë ata të dy së ​​bashku, në një hapësirë ​​shtesë, 308 00:13:39,120 --> 00:13:41,670 3 vjen e para, pastaj vjen 5. 309 00:13:41,670 --> 00:13:46,190 Dhe kështu që tani, ne kemi të renditura gjysma e majtë të gjysmën e djathtë 310 00:13:46,190 --> 00:13:49,420 e problemit origjinale, dhe gjysma e djathtë të pjesës së djathtë 311 00:13:49,420 --> 00:13:50,800 e problemit origjinal. 312 00:13:50,800 --> 00:13:52,480 Çfarë është hapi i tretë dhe të fundit? 313 00:13:52,480 --> 00:13:54,854 E pra të bashkojë këto dy gjysmave së bashku. 314 00:13:54,854 --> 00:13:57,020 Pra më lejoni të marrë veten disa hapësirë ​​shtesë, por, përsëri, unë 315 00:13:57,020 --> 00:13:58,699 mund të jetë duke përdorur këtë hapësirë ​​deri rezervë lartë. 316 00:13:58,699 --> 00:14:00,490 Por ne jemi duke shkuar për të mbajtur atë të thjeshtë me sy. 317 00:14:00,490 --> 00:14:07,070 Më lejoni të bashkojë në tani 1, dhe atëherë 3, dhe pastaj 5, dhe më pas 7. 318 00:14:07,070 --> 00:14:10,740 Duke i lënë mua tani me gjysma e drejtë e problemit origjinale 319 00:14:10,740 --> 00:14:12,840 që është renditur në mënyrë të përkryer. 320 00:14:12,840 --> 00:14:13,662 >> Pra, çfarë mbetet? 321 00:14:13,662 --> 00:14:16,120 Ndjehem si unë mbaj duke thënë se njëjtat gjëra përsëri, dhe përsëri, 322 00:14:16,120 --> 00:14:18,700 por kjo është reflektues i Fakti që ne jemi duke përdorur recursion. 323 00:14:18,700 --> 00:14:21,050 Procesi i përdorimit të një algorithm përsëri, dhe përsëri, 324 00:14:21,050 --> 00:14:23,940 në subsets të vogla të problemi fillestar. 325 00:14:23,940 --> 00:14:27,580 Kështu që unë tani kam një të majtë të renditura gjysma e problemit origjinal. 326 00:14:27,580 --> 00:14:30,847 Unë kam një gjysmë të drejtë renditura e problemit origjinal. 327 00:14:30,847 --> 00:14:32,180 Cili është hapi i tretë dhe i fundit? 328 00:14:32,180 --> 00:14:33,590 Oh, kjo është bashkimi. 329 00:14:33,590 --> 00:14:34,480 Pra, le ta bëjmë atë. 330 00:14:34,480 --> 00:14:36,420 Le të ndajë disa shtesë kujtesës, por Perëndia im, ne 331 00:14:36,420 --> 00:14:37,503 mund të vënë atë kudo tani. 332 00:14:37,503 --> 00:14:40,356 Ne kemi hapësirë ​​aq shumë në dispozicion për ne, por ne do të mbani atë të thjeshtë. 333 00:14:40,356 --> 00:14:42,730 Në vend që të shkojnë prapa dhe radhë me kujtesën tonë origjinal, 334 00:14:42,730 --> 00:14:44,480 le të vetëm të bëjë atë vizualisht poshtë këtu më poshtë, 335 00:14:44,480 --> 00:14:47,240 të përfundojë bashkimin e gjysma e majtë dhe gjysma e drejtë. 336 00:14:47,240 --> 00:14:49,279 >> Pra nga bashkimi, çfarë duhet të bëj? 337 00:14:49,279 --> 00:14:50,820 Unë dua të të marrë elementet në rregull. 338 00:14:50,820 --> 00:14:53,230 Pra, duke kërkuar në gjysmën e majtë, Unë shoh numri i parë është 2. 339 00:14:53,230 --> 00:14:55,230 Unë shoh në gjysmën e djathtë, Unë shoh numrin e parë 340 00:14:55,230 --> 00:14:58,290 është 1, në mënyrë të qartë cila Numri i bëjnë dua të këpusin jashtë, 341 00:14:58,290 --> 00:15:00,430 dhe të vënë së pari në listën time të fundit? 342 00:15:00,430 --> 00:15:01,449 Sigurisht, 1. 343 00:15:01,449 --> 00:15:02,990 Tani unë dua të pyes këtë pyetje të njëjtën. 344 00:15:02,990 --> 00:15:05,040 Në gjysmën e majtë, unë kam ende mori numrin 2. 345 00:15:05,040 --> 00:15:07,490 Në pjesën e djathtë, Unë kam marrë numrin 3. 346 00:15:07,490 --> 00:15:08,930 Cila një dua për të zgjedhur? 347 00:15:08,930 --> 00:15:11,760 Sigurisht, numri 2 tani vini re kandidatët 348 00:15:11,760 --> 00:15:13,620 janë 4 në të majtë, 3 në të djathtë. 349 00:15:13,620 --> 00:15:15,020 Le të, natyrisht, të zgjedhin 3. 350 00:15:15,020 --> 00:15:18,020 Tani kandidatët janë 4 në e majta, 5 në të djathtë. 351 00:15:18,020 --> 00:15:19,460 Ne, natyrisht, të zgjedhin 4. 352 00:15:19,460 --> 00:15:21,240 6 në të majtë, 5 në të djathtë. 353 00:15:21,240 --> 00:15:22,730 Ne, natyrisht, të zgjedhin 5. 354 00:15:22,730 --> 00:15:25,020 6 në të majtë, 7 në të djathtë. 355 00:15:25,020 --> 00:15:29,320 Kemi zgjedhur 6, dhe pastaj ne zgjedh 7, dhe pastaj kemi zgjedhur 8. 356 00:15:29,320 --> 00:15:30,100 Voila. 357 00:15:30,100 --> 00:15:34,370 >> Pra, një numër i madh i fjalëve më vonë, ne kanë të renditura në këtë listë të tetë elementeve 358 00:15:34,370 --> 00:15:38,450 në një listë të njërit nëpërmjet tetë, që është në rritje me çdo hap, 359 00:15:38,450 --> 00:15:40,850 por sa kohë ka ajo na merr për të bërë këtë. 360 00:15:40,850 --> 00:15:43,190 E pra unë kam qëllim gjëra të paraqitura në pikturë 361 00:15:43,190 --> 00:15:46,330 këtu, në mënyrë që ne mund të lloj shohin ose të vlerësojmë ndarjen 362 00:15:46,330 --> 00:15:49,060 në pushtues që është duke ndodhur. 363 00:15:49,060 --> 00:15:52,830 >> Në të vërtetë në qoftë se ju shikoni mbrapa në prag, Unë e kam lënë të gjitha këto vija me pika 364 00:15:52,830 --> 00:15:55,660 në mbajtësit vend, ju mund, lloj, shih, në mënyrë të kundërt, 365 00:15:55,660 --> 00:15:58,800 në qoftë se ju lloj i shohim mbrapa në historia tani, lista ime origjinale 366 00:15:58,800 --> 00:16:00,250 është, natyrisht, i madhësisë 8. 367 00:16:00,250 --> 00:16:03,480 Dhe pastaj më parë, unë kam qenë që kanë të bëjnë me dy listave të madhësisë 4, 368 00:16:03,480 --> 00:16:08,400 dhe pastaj katër listat e madhësisë 2, dhe pastaj tetë listat e madhësisë 1. 369 00:16:08,400 --> 00:16:10,151 >> Pra, çfarë e bën këtë, lloj, ju kujtoj të? 370 00:16:10,151 --> 00:16:11,858 E pra, në të vërtetë, asnjë nga algoritme ne kemi 371 00:16:11,858 --> 00:16:14,430 shikuar deri më tani ku ne ndarje, dhe ndarje, dhe ndarja, 372 00:16:14,430 --> 00:16:19,500 mbani duke pasur gjëra përsëri, dhe përsëri, rezulton në këtë ide të përgjithshme. 373 00:16:19,500 --> 00:16:23,100 Dhe kështu që nuk është diçka logaritmike ndodh këtu. 374 00:16:23,100 --> 00:16:26,790 Dhe kjo nuk është mjaft e log n, por ka një komponent logaritmike 375 00:16:26,790 --> 00:16:28,280 për atë që ne kemi bërë vetëm. 376 00:16:28,280 --> 00:16:31,570 >> Tani le të shqyrtojmë se si që në fakt është. 377 00:16:31,570 --> 00:16:34,481 Pra, log i n, përsëri ishte një kohë e madhe running, 378 00:16:34,481 --> 00:16:36,980 kur ne e bëmë diçka si kërko binar, si ne tani e quajmë atë, 379 00:16:36,980 --> 00:16:40,090 strategjia Përça dhe sundo nëpërmjet të cilat kemi gjetur Mike Smith. 380 00:16:40,090 --> 00:16:41,020 Tani teknikisht. 381 00:16:41,020 --> 00:16:43,640 Kjo është bazë log 2 i n, madje edhe edhe pse në klasat më të madhe e matematikës, 382 00:16:43,640 --> 00:16:45,770 10 zakonisht është baza që ju të marrë. 383 00:16:45,770 --> 00:16:48,940 Por shkencëtarët kompjuterike pothuajse gjithmonë mendojnë dhe të flasin në drejtim të bazës 2, 384 00:16:48,940 --> 00:16:52,569 kështu që ne në përgjithësi vetëm thonë regjistër të n, në vend të bazës log 2 n, 385 00:16:52,569 --> 00:16:55,110 por ata janë pikërisht një dhe njëjtë në botën e kompjuterit 386 00:16:55,110 --> 00:16:57,234 shkencë, dhe si një mënjanë, ka një faktor konstant 387 00:16:57,234 --> 00:17:01,070 Diferenca midis të dyjave, kështu që është e Moot gjithsesi, për arsye më formale. 388 00:17:01,070 --> 00:17:04,520 >> Por tani për tani, ajo që ne kujdesemi lidhje është ky shembull. 389 00:17:04,520 --> 00:17:08,520 Pra, le të mos provojnë me shembullin, por në paktën të përdorni një shembull të numrave 390 00:17:08,520 --> 00:17:10,730 në dorë si një kontroll mendje e shëndoshë, nëse ju do. 391 00:17:10,730 --> 00:17:14,510 Kështu që më parë ishte formula bazë log 2 i n, por ajo që është n në këtë rast. 392 00:17:14,510 --> 00:17:18,526 Unë kisha numrat n origjinale, ose 8 e numrit origjinale specifike. 393 00:17:18,526 --> 00:17:20,359 Tani kjo është pak ndërsa, por unë jam goxha 394 00:17:20,359 --> 00:17:25,300 i sigurt se baza log 2 e vlerës së 8 është 3, 395 00:17:25,300 --> 00:17:29,630 dhe në të vërtetë, çfarë është e bukur për të cilat është se 3 është pikërisht numri i herë 396 00:17:29,630 --> 00:17:33,320 që ju mund të ndajnë një listë e gjatësisë 8 përsëri, dhe përsëri, 397 00:17:33,320 --> 00:17:36,160 dhe përsëri, derisa ju jeni mbetur me listat e vetëm madhësisë 1. 398 00:17:36,160 --> 00:17:36,660 E drejtë? 399 00:17:36,660 --> 00:17:40,790 8 shkon në 4, shkon në 2, shkon në 1, dhe kjo është 400 00:17:40,790 --> 00:17:43,470 reflektuese e saktësisht se foto ne kishim vetëm një moment më parë. 401 00:17:43,470 --> 00:17:47,160 Pra, një mendje e shëndoshë pak të kontrolluar se ku logaritmi është i përfshirë në të vërtetë. 402 00:17:47,160 --> 00:17:50,180 >> Deri tani, çfarë tjetër është e përfshirë këtu? n. 403 00:17:50,180 --> 00:17:53,440 Pra, vini re se çdo herë kam ndarë listën, 404 00:17:53,440 --> 00:17:58,260 megjithëse në mënyrë të kundërt në histori këtu, unë isha ende duke bërë n gjëra. 405 00:17:58,260 --> 00:18:02,320 Që hap bashkimi kërkonte që I prek çdo një nga numrat, 406 00:18:02,320 --> 00:18:05,060 në mënyrë që të rrëshqitje atë në vendndodhjen e saj të përshtatshme. 407 00:18:05,060 --> 00:18:10,760 Pra, edhe pse lartësia e kësaj diagram është i madhësisë log n e n ose 3, 408 00:18:10,760 --> 00:18:13,860 në mënyrë specifike, me fjalë të tjera, Unë e bëri tre divizione këtu. 409 00:18:13,860 --> 00:18:18,800 Sa punë e kam bërë horizontalisht së bashku këtë tabelë çdo kohë? 410 00:18:18,800 --> 00:18:21,110 >> E pra, unë e bëri n hapat e punë, sepse në qoftë se unë kam 411 00:18:21,110 --> 00:18:24,080 mori katër elementet dhe katër elemente, dhe kam nevojë për të bashkojë ato së bashku. 412 00:18:24,080 --> 00:18:26,040 Unë duhet të kalojnë nëpër këto katër dhe këto katër, 413 00:18:26,040 --> 00:18:28,123 në fund të fundit të bashkojë ato përsëri në tetë elemente. 414 00:18:28,123 --> 00:18:32,182 Nëse anasjelltas Unë kam marrë tetë gishtat këtu, që unë nuk e bëjnë, dhe tetë 415 00:18:32,182 --> 00:18:34,390 fingers-- sorry-- Nëse unë kam mori katër gishta gjatë këtu, 416 00:18:34,390 --> 00:18:37,380 që unë bëj, katër gishtërinj këtu, që unë bëj, 417 00:18:37,380 --> 00:18:40,590 atëherë kjo është e njëjtë shembull si më parë, në qoftë se unë bëj 418 00:18:40,590 --> 00:18:44,010 kanë tetë gishtat edhe pse në totale, që unë mund të, lloj, të bëjë. 419 00:18:44,010 --> 00:18:47,950 Unë mund të bëj pikërisht këtu, atëherë unë mund sigurisht 420 00:18:47,950 --> 00:18:50,370 bashkojë të gjitha këto lista nga madhësia 1 së bashku. 421 00:18:50,370 --> 00:18:54,050 Por unë me siguri duhet të shikoni në çdo element saktësisht një herë. 422 00:18:54,050 --> 00:18:59,640 Pra, lartësia e këtij procesi është log n, gjerësia e këtij procesi, në mënyrë që të flasin, 423 00:18:59,640 --> 00:19:02,490 është n, kështu që ajo që ne duket të ketë, në fund të fundit, është 424 00:19:02,490 --> 00:19:06,470 një kohë running me madhësi n herë log n. 425 00:19:06,470 --> 00:19:08,977 >> Me fjalë të tjera, ne të ndarë lista, log n herë, 426 00:19:08,977 --> 00:19:11,810 por çdo herë ne e bëmë atë, ne kishim për të prekur çdo një nga elementet 427 00:19:11,810 --> 00:19:13,560 në mënyrë që ato bashkohen të gjithë së bashku, e cila 428 00:19:13,560 --> 00:19:18,120 ishte N hap, kështu që ne kemi n herë log n, ose siç do të thoshte një shkencëtar kompjuteri, 429 00:19:18,120 --> 00:19:20,380 asymptotically, e cila do të jetë fjala e madhe 430 00:19:20,380 --> 00:19:22,810 për të përshkruar pjesën e sipërme i lidhur në një kohë running, 431 00:19:22,810 --> 00:19:28,010 ne do të vrapojnë në një o madhe i log n kohës, kështu që të flasin. 432 00:19:28,010 --> 00:19:31,510 >> Tani kjo është e rëndësishme, sepse kujtojnë se çfarë kohët running ishin 433 00:19:31,510 --> 00:19:34,120 with lloj flluskë, dhe përzgjedhjes lloj, dhe futje lloj, 434 00:19:34,120 --> 00:19:38,200 dhe madje edhe disa të tjerë që ekzistojnë, n katror ishte vendi ku ishim ne. 435 00:19:38,200 --> 00:19:39,990 Dhe ju mund të, lloj, shih këtë këtu. 436 00:19:39,990 --> 00:19:45,720 Nëse n katror është padyshim n herë n, por këtu kemi n herë log n, 437 00:19:45,720 --> 00:19:48,770 dhe ne tashmë e dimë që nga java e zero, që log n, The logaritmike, 438 00:19:48,770 --> 00:19:50,550 është më mirë se diçka lineare. 439 00:19:50,550 --> 00:19:52,930 Pas të gjitha, kujtojnë foto me të kuqe dhe të verdhë 440 00:19:52,930 --> 00:19:56,500 dhe linjat e gjelbër që ne të aftë, The Linja jeshile logaritmike ishte shumë më e ulët. 441 00:19:56,500 --> 00:20:00,920 Dhe për këtë arsye, shumë më mirë dhe më të shpejtë se vija e drejtë verdhë dhe të kuqe, 442 00:20:00,920 --> 00:20:05,900 n herë log n është, me të vërtetë, më mirë se kohët e n n, ose n katror. 443 00:20:05,900 --> 00:20:09,110 >> Pra, ne duket të ketë identifikuar një bashkohen algorithm 444 00:20:09,110 --> 00:20:11,870 lloj që shkon në shumë kohë më të shpejtë, dhe në të vërtetë, 445 00:20:11,870 --> 00:20:16,560 kjo është arsyeja pse, më parë këtë javë, kur ne pamë atë garë mes flluskë 446 00:20:16,560 --> 00:20:20,750 lloj, lloj përzgjedhja, dhe shkrihen lloj, shkrihen lloj të vërtetë, fitoi me të vërtetë. 447 00:20:20,750 --> 00:20:23,660 Dhe me të vërtetë, ne as nuk presim për lloj flluskë dhe përzgjedhjes lloj 448 00:20:23,660 --> 00:20:24,790 te mbaroj. 449 00:20:24,790 --> 00:20:27,410 >> Tani le të marrin një abone të tjera në këtë, nga një pak më shumë 450 00:20:27,410 --> 00:20:31,030 Perspektiva formale, vetëm në rast, kjo rezonon mirë 451 00:20:31,030 --> 00:20:33,380 se atë diskutim të nivelit më të lartë. 452 00:20:33,380 --> 00:20:34,880 Kështu që këtu është algoritmi përsëri. 453 00:20:34,880 --> 00:20:36,770 Le të pyesim veten, çfarë kohë running 454 00:20:36,770 --> 00:20:39,287 është kjo algoritme hapat e ndryshëm? 455 00:20:39,287 --> 00:20:41,620 Le të ndajnë atë në e parë rast dhe rasti i dytë. 456 00:20:41,620 --> 00:20:46,280 If dhe tjetër në rast se, IF n është më pak se 2, vetëm kthehen. 457 00:20:46,280 --> 00:20:47,580 Ndjehet si herë të vazhdueshme. 458 00:20:47,580 --> 00:20:50,970 Kjo është, lloj, si dy hapa, IF n është më pak se 2, pastaj kthehen. 459 00:20:50,970 --> 00:20:54,580 Por, siç thamë të hënën, kohë konstante apo të mëdha o të 1, 460 00:20:54,580 --> 00:20:57,130 mund të jetë dy hapa, tre hapa, madje edhe 1.000 hapa. 461 00:20:57,130 --> 00:20:59,870 Ajo që ka rëndësi është se kjo është një numër i vazhdueshëm i hapave. 462 00:20:59,870 --> 00:21:03,240 Pra verdhë theksuar pseudokod këtu shkon në, ne do të thërrasë atë, 463 00:21:03,240 --> 00:21:04,490 kohë konstante. 464 00:21:04,490 --> 00:21:06,780 Pra më formalisht, dhe ne jemi duke shkuar to-- kjo 465 00:21:06,780 --> 00:21:09,910 do të jetë shkalla në të cilën ne formalizuar këtë të drejtë now-- T i N, 466 00:21:09,910 --> 00:21:15,030 koha drejtimin e një problemi që merr ca n si input, 467 00:21:15,030 --> 00:21:19,150 barabartë i madh o nga një, IF n është më pak se 2. 468 00:21:19,150 --> 00:21:20,640 Pra, kjo është kushtëzuar nga ajo. 469 00:21:20,640 --> 00:21:24,150 Në mënyrë të qartë, IF n është më pak se 2, ne kemi një listë shumë të shkurtër, atëherë 470 00:21:24,150 --> 00:21:29,151 koha drejtimin, T i n, ku n është 1 ose 0, në këtë rast shumë specifike, 471 00:21:29,151 --> 00:21:30,650 ajo është vetëm do të jetë kohë konstante. 472 00:21:30,650 --> 00:21:32,691 Ajo do të marrë një të tillë hap, dy hapa, çfarëdo. 473 00:21:32,691 --> 00:21:33,950 Është një numër të caktuar të hapave. 474 00:21:33,950 --> 00:21:38,840 >> Pra, pjesa me lëng me siguri duhet të jetë në Rasti tjetër në pseudokod. 475 00:21:38,840 --> 00:21:40,220 Rasti tjetër. 476 00:21:40,220 --> 00:21:44,870 Lloj gjysma e majtë e elementeve, lloj e drejtë gjysma e elementeve, të bashkohen gjysmave renditura. 477 00:21:44,870 --> 00:21:46,800 Sa kohë secili prej këtyre hapave të marrë? 478 00:21:46,800 --> 00:21:49,780 E pra, në qoftë se running kohë për të zgjidhur elementet n 479 00:21:49,780 --> 00:21:53,010 është, le ta quajmë shumë generically, T i N, 480 00:21:53,010 --> 00:21:55,500 atëherë zgjidhja e majtë gjysma e elementeve 481 00:21:55,500 --> 00:21:59,720 është, lloj, si të thuash, T e n ndarë nga 2, 482 00:21:59,720 --> 00:22:03,000 dhe në mënyrë të ngjashme klasifikim gjysmën e djathtë e elementeve është, lloj, si të thuash, 483 00:22:03,000 --> 00:22:06,974 T e n ndarë 2, dhe pastaj bashkimi gjysmave renditur. 484 00:22:06,974 --> 00:22:08,890 E pra, nëse unë kam marrë disa Numri i elementeve këtu, 485 00:22:08,890 --> 00:22:11,230 si katër, dhe disa numrin e elementeve këtu, si katër, 486 00:22:11,230 --> 00:22:14,650 dhe unë duhet të bashkojë secili prej këtyre katër në, dhe secili prej këtyre katër në, një 487 00:22:14,650 --> 00:22:17,160 pas tjetrës, në mënyrë që në fund të fundit unë kam tetë elemente. 488 00:22:17,160 --> 00:22:20,230 Ajo ndjehet si kjo është e madhe o të hapave n? 489 00:22:20,230 --> 00:22:23,500 Nëse unë kam marrë n gishtat dhe secili prej ata duhet të bashkohen në vend, 490 00:22:23,500 --> 00:22:25,270 kjo është si një tjetër hapa n. 491 00:22:25,270 --> 00:22:27,360 >> Pra me të vërtetë formulaically, ne mund të shprehim këtë, 492 00:22:27,360 --> 00:22:29,960 megjithëse një scarily pak në fillim shikim, por kjo është diçka 493 00:22:29,960 --> 00:22:31,600 që kap pikërisht këtë logjikë. 494 00:22:31,600 --> 00:22:35,710 Koha drejtimin, T i N, NËSE n është më e madhe se ose e barabartë me 2. 495 00:22:35,710 --> 00:22:42,500 Në këtë rast, rasti tjetër është i T n ndarë nga 2, plus T i N ndarë nga 2, 496 00:22:42,500 --> 00:22:45,320 plus i madh o të n, disa Numri linear i hapave, 497 00:22:45,320 --> 00:22:51,630 ndoshta pikërisht n, ndoshta 2 herë n, por kjo është afërsisht, radha e n. 498 00:22:51,630 --> 00:22:54,060 Kështu që, gjithashtu, është se si ne mund të shprehur kjo formulaically. 499 00:22:54,060 --> 00:22:56,809 Tani ju nuk do të dinë këtë nëse ju keni regjistruar atë në mendjen tuaj, 500 00:22:56,809 --> 00:22:58,710 apo të shikoni atë deri në prapa e një teksti, i cili 501 00:22:58,710 --> 00:23:00,501 mund të ketë pak mashtrojnë fletë në fund, 502 00:23:00,501 --> 00:23:03,940 por kjo është, me të vërtetë, do të na japin një i madh o të n log n, 503 00:23:03,940 --> 00:23:06,620 sepse përsëritje që ju jeni duke parë këtu në ekran, 504 00:23:06,620 --> 00:23:09,550 në qoftë se ju në të vërtetë e bëri atë, me një numër të pafund të shembujve, 505 00:23:09,550 --> 00:23:13,000 ose ju e bëri atë formulaically, ju do të shihni se kjo, për shkak se këtë formulë 506 00:23:13,000 --> 00:23:17,100 vetvete është gjithkund rekursive, me t e n mbi diçka nga e djathta, 507 00:23:17,100 --> 00:23:21,680 dhe t i n e majta, kjo mund të në fakt të shprehet, në fund të fundit, 508 00:23:21,680 --> 00:23:24,339 Go aq i madh i log n n. 509 00:23:24,339 --> 00:23:26,130 Nëse jo i bindur, kjo është gjobë për tani, vetëm 510 00:23:26,130 --> 00:23:28,960 të marrë në besim, se kjo është, me të vërtetë, ajo që të çon në përsëritje, 511 00:23:28,960 --> 00:23:31,780 por kjo është vetëm një pak më shumë një Qasja matematikore në kërkim 512 00:23:31,780 --> 00:23:36,520 në kohën drejtimin e merge lloji bazuar në pseudokod e saj vetëm. 513 00:23:36,520 --> 00:23:39,030 >> Tani le të marrin një grimë e një pushim nga të gjithë se, 514 00:23:39,030 --> 00:23:41,710 dhe për të marrë një sy në një ish-senator i caktuar, i cili 515 00:23:41,710 --> 00:23:44,260 mund të duket një të njohur pak, i cili u ul me Eric Google 516 00:23:44,260 --> 00:23:48,410 Schmidt, disa kohë më parë, për një intervistë në skenë, në frontin e një bandë e tërë 517 00:23:48,410 --> 00:23:53,710 e njerëzve, duke folur në fund të fundit për një temë, kjo është goxha e njohur tani. 518 00:23:53,710 --> 00:23:54,575 Le të marrin një vështrim. 519 00:23:54,575 --> 00:24:01,020 520 00:24:01,020 --> 00:24:03,890 >> Eric Schmidt: Tani Senator, ju jeni këtu në Google, 521 00:24:03,890 --> 00:24:09,490 dhe unë doja të mendoj e Presidenca si një intervistë për punë. 522 00:24:09,490 --> 00:24:11,712 Tani është e vështirë për të marrë një punë si president. 523 00:24:11,712 --> 00:24:12,670 PRESIDENTI OBAMA: E drejta. 524 00:24:12,670 --> 00:24:13,940 Eric Schmidt: Dhe ju jeni shkuar për të bërë [e padëgjueshme] tani. 525 00:24:13,940 --> 00:24:15,523 Është gjithashtu e vështirë për të marrë një punë në Google. 526 00:24:15,523 --> 00:24:17,700 PRESIDENTI OBAMA: E drejta. 527 00:24:17,700 --> 00:24:21,330 >> Eric Schmidt: Kemi pyetje, dhe ne të bëni pyetje kandidatët tanë, 528 00:24:21,330 --> 00:24:24,310 dhe kjo është nga Larry Schwimmer. 529 00:24:24,310 --> 00:24:25,890 >> PRESIDENTI OBAMA: OK. 530 00:24:25,890 --> 00:24:27,005 >> Eric Schmidt: Çfarë? 531 00:24:27,005 --> 00:24:28,130 Ju djema mendoni se unë jam kidding? 532 00:24:28,130 --> 00:24:30,590 Kjo është e drejtë këtu. 533 00:24:30,590 --> 00:24:33,490 Çfarë është mënyra më efikase për zgjidhur një milion 32 bit integers? 534 00:24:33,490 --> 00:24:37,560 535 00:24:37,560 --> 00:24:38,979 >> PRESIDENTI OBAMA: Well-- 536 00:24:38,979 --> 00:24:41,020 Eric Schmidt: Ndonjëherë, ndoshta unë jam i keq, maybe-- 537 00:24:41,020 --> 00:24:42,750 PRESIDENTI OBAMA: Jo, jo, jo, jo, jo, unë think-- 538 00:24:42,750 --> 00:24:43,240 Eric Schmidt: Kjo nuk është it-- 539 00:24:43,240 --> 00:24:45,430 PRESIDENTI OBAMA: I mendoj, unë mendoj flluskë 540 00:24:45,430 --> 00:24:46,875 lloj do të jetë mënyra e gabuar për të shkuar. 541 00:24:46,875 --> 00:24:49,619 542 00:24:49,619 --> 00:24:50,535 Eric Schmidt: Eja. 543 00:24:50,535 --> 00:24:52,200 I cili i tha atij këtë? 544 00:24:52,200 --> 00:24:54,020 NE RREGULL. 545 00:24:54,020 --> 00:24:55,590 Unë nuk e bëri shkenca kompjuterike on-- 546 00:24:55,590 --> 00:24:58,986 >> PRESIDENTI OBAMA: Ne kemi mori spiunë tona në atje. 547 00:24:58,986 --> 00:24:59,860 PROFESORI: Në rregull. 548 00:24:59,860 --> 00:25:03,370 Le të lëmë pas nesh tani Bota teorik i algoritmeve 549 00:25:03,370 --> 00:25:06,520 në analizën asymptotic saj, dhe të kthehet në disa tema 550 00:25:06,520 --> 00:25:09,940 nga javën zero dhe një, dhe të fillojnë për të hequr disa rrota të trajnimit, 551 00:25:09,940 --> 00:25:10,450 nëse ju do. 552 00:25:10,450 --> 00:25:13,241 Kështu që ju të vërtetë kuptojnë në fund të fundit nga toka lart, çfarë është 553 00:25:13,241 --> 00:25:16,805 ndodh nën kapuç, kur ju shkruaj, përpilojnë, dhe ekzekutuar programet. 554 00:25:16,805 --> 00:25:19,680 Kujtojnë në mënyrë të veçantë, se kjo ishte programi i parë C kemi shikuar, 555 00:25:19,680 --> 00:25:22,840 një program kanonik, i thjeshtë në terezi, relativisht të folur, 556 00:25:22,840 --> 00:25:24,620 ku, ajo printon, Hello World. 557 00:25:24,620 --> 00:25:27,610 Dhe kujtojnë se unë thashë, procesi që kodi burim shkon përmes 558 00:25:27,610 --> 00:25:28,430 është pikërisht kjo. 559 00:25:28,430 --> 00:25:31,180 Ju merrni kodin tuaj burim, të kalojë ajo përmes një përpilues, si tingëllimë, 560 00:25:31,180 --> 00:25:34,650 dhe nga vjen kod objekt, që mund të duket si kjo, zero dhe ato 561 00:25:34,650 --> 00:25:37,880 se CPU e kompjuterit, qendrore përpunimit të njësisë apo të trurit, 562 00:25:37,880 --> 00:25:39,760 në fund të fundit e kupton. 563 00:25:39,760 --> 00:25:42,460 >> Ajo rezulton se kjo është një pak e një oversimplification, 564 00:25:42,460 --> 00:25:44,480 që ne jemi tani në një pozicion për të ngas përveç 565 00:25:44,480 --> 00:25:46,720 për të kuptuar se çfarë ka qenë me të vërtetë ndodh nën kapuç 566 00:25:46,720 --> 00:25:48,600 çdo herë që të kandidojë Tingëllimë, ose më në përgjithësi, 567 00:25:48,600 --> 00:25:53,040 çdo herë që bëni një program, Bëni përdorimin dhe CF 50 IDE. 568 00:25:53,040 --> 00:25:56,760 Në veçanti, stuff like kjo është gjeneruar së pari, 569 00:25:56,760 --> 00:25:58,684 kur ju së pari të hartojnë programin tuaj. 570 00:25:58,684 --> 00:26:00,600 Me fjalë të tjera, kur ju të marrë kodin tuaj burim 571 00:26:00,600 --> 00:26:04,390 dhe të përpilojnë atë, çfarë është parë being outputted by tingëllimë 572 00:26:04,390 --> 00:26:06,370 është diçka e njohur si kodi kuvendit. 573 00:26:06,370 --> 00:26:08,990 Dhe në fakt, ajo duket tamam si kjo. 574 00:26:08,990 --> 00:26:11,170 >> Unë u zhvillua një komandë në nivel Command Line herët. 575 00:26:11,170 --> 00:26:16,260 Tingëllimë kryeqytetit Dash s hello.c, dhe kjo krijoi një fotografi 576 00:26:16,260 --> 00:26:19,490 për mua quajtur hello.s, brenda të cilave ishin pikërisht 577 00:26:19,490 --> 00:26:22,290 këto përmbajtje, dhe një më pak sipër dhe pak më poshtë, 578 00:26:22,290 --> 00:26:25,080 por unë e kam vënë juiciest informacion këtu në ekran. 579 00:26:25,080 --> 00:26:29,190 Dhe në qoftë se ju shikoni nga afër, ju do të shihni të paktën disa fjalë kyçe të njohur. 580 00:26:29,190 --> 00:26:31,330 Ne kemi kryesor në krye. 581 00:26:31,330 --> 00:26:35,140 Ne kemi printf poshtë në mes. 582 00:26:35,140 --> 00:26:38,670 Dhe ne gjithashtu kemi Hello World backslash n në thonjëza poshtë më poshtë. 583 00:26:38,670 --> 00:26:42,450 >> Dhe çdo gjë tjetër në këtu është udhëzime nivel shumë të ulët 584 00:26:42,450 --> 00:26:45,500 se CPU e kompjuterit kupton. 585 00:26:45,500 --> 00:26:50,090 Udhëzimet CPU që lëvizin kujtesën rreth, se vargjet ngarkesës nga kujtesa, 586 00:26:50,090 --> 00:26:52,750 dhe në fund të fundit, të shtypura gjëra në ekran. 587 00:26:52,750 --> 00:26:56,780 Tani çfarë ndodh pse pas ky kod kuvendi është gjeneruar? 588 00:26:56,780 --> 00:26:59,964 Në fund të fundit, ju bëni, me të vërtetë, ende të gjeneruar kodin objekt. 589 00:26:59,964 --> 00:27:02,630 Por hapat që kanë me të vërtetë vazhduar nën kapuç 590 00:27:02,630 --> 00:27:04,180 shikoni pak më shumë si kjo. 591 00:27:04,180 --> 00:27:08,390 Source code bëhet kod kuvendi, e cila pastaj bëhet kod objekt, 592 00:27:08,390 --> 00:27:11,930 dhe fjalët operative këtu janë se, kur ju përpilojnë kodin tuaj burim, 593 00:27:11,930 --> 00:27:16,300 nga vjen kodin kuvendit, dhe pastaj kur ju mblidhen kodin tuaj kuvendit, 594 00:27:16,300 --> 00:27:17,800 nga vjen kod objekt. 595 00:27:17,800 --> 00:27:20,360 >> Tani tingëllimë është super i sofistikuar, si një shumë e hartuesit, 596 00:27:20,360 --> 00:27:23,151 dhe kjo e bën të gjitha këto hapa së bashku, dhe kjo e bën jo domosdoshmërisht 597 00:27:23,151 --> 00:27:25,360 Prodhimi ndonjë ndërmjetme fotografi që ju mund të shihni edhe. 598 00:27:25,360 --> 00:27:28,400 Ajo thjesht harton gjëra, cila është termi përgjithshme që 599 00:27:28,400 --> 00:27:30,000 përshkruan të gjithë këtë proces. 600 00:27:30,000 --> 00:27:32,000 Por në qoftë se ju vërtet doni për të qenë të veçantë, nuk ka 601 00:27:32,000 --> 00:27:34,330 shumë më tepër ndodh edhe atje. 602 00:27:34,330 --> 00:27:38,860 >> Por le të marrë në konsideratë tani se edhe se programi super e thjeshtë, hello.c, 603 00:27:38,860 --> 00:27:40,540 quajtur një funksion. 604 00:27:40,540 --> 00:27:41,870 Ajo quajtur printf. 605 00:27:41,870 --> 00:27:46,900 Por unë nuk shkruaj printf, me të vërtetë, që vjen me c, kështu që të flasin. 606 00:27:46,900 --> 00:27:51,139 Kjo është një kujtojnë funksion kjo është deklaroi në io.h standarde, e cila 607 00:27:51,139 --> 00:27:53,180 është një header file, e cila është një temë që ne do të vërtetë të 608 00:27:53,180 --> 00:27:55,780 zhyten në thellësi më shumë para se të gjatë. 609 00:27:55,780 --> 00:27:58,000 Por një header skedë është shoqëruar në mënyrë tipike 610 00:27:58,000 --> 00:28:02,920 nga një skedar kod, kodin burim file, kështu që ashtu si ekziston io.h. standarde 611 00:28:02,920 --> 00:28:05,930 >> Pak kohë më parë, dikush, ose someones, gjithashtu shkroi 612 00:28:05,930 --> 00:28:11,040 një file i quajtur io.c standarde, në që përkufizimet aktuale, 613 00:28:11,040 --> 00:28:15,220 ose Implementimi i printf, dhe bunches e funksioneve të tjera, 614 00:28:15,220 --> 00:28:16,870 janë të shkruara në fakt. 615 00:28:16,870 --> 00:28:22,140 Pra duke pasur parasysh se, në qoftë se ne e konsiderojmë të pasur këtu në të majtë, hello.c, se kur 616 00:28:22,140 --> 00:28:26,250 hartuar, na jep hello.s, edhe në qoftë se Tingëllimë nuk bother kursimin në një vend 617 00:28:26,250 --> 00:28:31,360 ne mund të shohim atë, dhe se kodi kuvendit merr mbledhur në hello.o, e cila 618 00:28:31,360 --> 00:28:34,630 është, me të vërtetë, emri i parazgjedhur dhënë sa herë që ju të përpilojnë burim 619 00:28:34,630 --> 00:28:39,350 kodin në kodin objekt, por nuk janë të mjaft të gatshëm për të ekzekutuar atë ende, 620 00:28:39,350 --> 00:28:41,460 sepse një hap tjetër duhet të ndodhë, dhe ka 621 00:28:41,460 --> 00:28:44,440 është duke ndodhur për të kaluarën pak javë, ndoshta unbeknownst për ju. 622 00:28:44,440 --> 00:28:47,290 >> Në mënyrë të veçantë diku në CS50 IDE, dhe kjo, 623 00:28:47,290 --> 00:28:49,870 gjithashtu, do të jetë pak e një thjeshtëzim për një moment, 624 00:28:49,870 --> 00:28:54,670 ka, ose ishte e nje kohe, një file i quajtur io.c standarde, 625 00:28:54,670 --> 00:28:58,440 që dikush hartuar në io.s standarde ose ekuivalent, 626 00:28:58,440 --> 00:29:02,010 që dikush pastaj mblodhi në io.o standarde, 627 00:29:02,010 --> 00:29:04,600 apo rezulton në një skedar pak më të ndryshme 628 00:29:04,600 --> 00:29:07,220 format që mund të ketë një tjetër fotografi extension krejt, 629 00:29:07,220 --> 00:29:11,720 por në teori dhe konceptualisht, pikërisht këto hapa është dashur të ndodhë në një formë. 630 00:29:11,720 --> 00:29:14,060 Që do të thotë se tani kur unë jam me shkrim një program, 631 00:29:14,060 --> 00:29:17,870 hello.c, që vetëm thotë, Hello World, dhe unë jam duke përdorur kodin e dikujt tjetër 632 00:29:17,870 --> 00:29:22,480 si printf, e cila ishte një herë e një kohë, në një skedar të quajtur io.c standarde, 633 00:29:22,480 --> 00:29:26,390 atëherë disi unë kam për të marr My Kodi objekt, zero e mia dhe ato, 634 00:29:26,390 --> 00:29:29,260 dhe objekt atij personi Kodi ose zero dhe ato, 635 00:29:29,260 --> 00:29:34,970 dhe disi lidhjen e tyre së bashku në një skedar i fundit, i quajtur hello, që 636 00:29:34,970 --> 00:29:38,070 ka të gjitha zero dhe ato nga funksioni im kryesor, 637 00:29:38,070 --> 00:29:40,830 dhe të gjitha zero dhe ato për printf. 638 00:29:40,830 --> 00:29:44,900 >> Dhe me të vërtetë, se procesi fundit është quajtur, lidh kodin tuaj objekt. 639 00:29:44,900 --> 00:29:47,490 Prodhimi i të cilave është një skedar i ekzekutueshëm. 640 00:29:47,490 --> 00:29:49,780 Pra, në drejtësi, në nivel fundi i ditës, asgjë 641 00:29:49,780 --> 00:29:52,660 ka ndryshuar që nga java e parë, kur ne së pari ka filluar hartimin e programeve. 642 00:29:52,660 --> 00:29:55,200 Në të vërtetë, e gjithë kjo ka qenë ndodh nën kapuç, 643 00:29:55,200 --> 00:29:57,241 por tani ne jemi në një pozicion ku ne mund të vërtetë 644 00:29:57,241 --> 00:29:58,794 vë në lojë përveç këto hapa të ndryshme. 645 00:29:58,794 --> 00:30:00,710 Dhe në të vërtetë, në fund e ditës, ne jemi ende 646 00:30:00,710 --> 00:30:04,480 u largua me zero dhe ato, të cilat është në fakt një Segue i madh tani 647 00:30:04,480 --> 00:30:08,620 në një aftësi për të C, që ne nuk kemi pasur për të levave më shumë gjasa 648 00:30:08,620 --> 00:30:11,250 deri më sot, i njohur si operatorët bitwise. 649 00:30:11,250 --> 00:30:15,220 Me fjalë të tjera, deri më tani, në çdo kohë ne kemi trajtohen me të dhëna në C ose variablave në C, 650 00:30:15,220 --> 00:30:17,660 ne kemi pasur gjëra të tilla si chars dhe gjithandej dhe ins 651 00:30:17,660 --> 00:30:21,990 dhe longs dhe dyshe dhe të ngjashme, por të gjithë ata që janë të paktën tetë bit. 652 00:30:21,990 --> 00:30:25,550 Ne kurrë nuk kam qenë ende në gjendje për të manipuluar bit individuale, 653 00:30:25,550 --> 00:30:28,970 edhe pse një grimë individuale, ne e di, mund të përfaqësojnë një 0 dhe një 1. 654 00:30:28,970 --> 00:30:32,640 Tani del se në C, ju mund të merrni qasje në copa individuale, 655 00:30:32,640 --> 00:30:35,530 në qoftë se ju e dini sintaksë, me të cilin për të marrë me ta. 656 00:30:35,530 --> 00:30:38,010 >> Pra, le të marrin një vështrim në operatorët bitwise. 657 00:30:38,010 --> 00:30:41,700 Pra foto këtu janë disa simbole që ne kemi, lloj, lloj, parë më parë. 658 00:30:41,700 --> 00:30:45,580 Unë shoh një 'e, një vertikale bar, dhe disa të tjerë, si dhe, 659 00:30:45,580 --> 00:30:49,430 dhe kujtojnë se simbol të ampersand është diçka që ne kemi parë më parë. 660 00:30:49,430 --> 00:30:54,060 Operatori logjik AND, ku ju keni dy prej tyre së bashku, ose logjik OR 661 00:30:54,060 --> 00:30:56,300 operator, ku ju kanë dy bare vertikale. 662 00:30:56,300 --> 00:31:00,550 Operatorët bitwise, të cilat ne do të shih veprojnë në copa individuale, 663 00:31:00,550 --> 00:31:03,810 vetëm përdorni një simbol të vetme, një bar vetme vertikale, simboli caret 664 00:31:03,810 --> 00:31:06,620 vjen më pas, pak Tilde, dhe pastaj u largua 665 00:31:06,620 --> 00:31:08,990 kllapa majtas kllapa, ose kllapa drejtë kllapa drejtë. 666 00:31:08,990 --> 00:31:10,770 Secili prej tyre kanë kuptime të ndryshme. 667 00:31:10,770 --> 00:31:11,950 >> Në fakt, le të marrin një sy. 668 00:31:11,950 --> 00:31:16,560 Le të shkojnë shkollës së vjetër sot, dhe përdorimi një ekran touch nga kaluar, 669 00:31:16,560 --> 00:31:18,002 i njohur si një bord të bardhë. 670 00:31:18,002 --> 00:31:19,710 Dhe kjo bordit të bardhë do të na lejojë 671 00:31:19,710 --> 00:31:27,360 të shpreh disa simbole mjaft e thjeshtë, ose më mirë disa formula të thjeshta në mënyrë të drejtë, 672 00:31:27,360 --> 00:31:29,560 që ne mund pastaj në fund të fundit levave, në mënyrë 673 00:31:29,560 --> 00:31:33,230 për të hyrë në individ bit brenda një programi C. 674 00:31:33,230 --> 00:31:34,480 Me fjalë të tjera, le ta bëjmë këtë. 675 00:31:34,480 --> 00:31:37,080 Flasim së pari le për një moment për simbolin komercial, 676 00:31:37,080 --> 00:31:39,560 që është bitwise DHE operatori. 677 00:31:39,560 --> 00:31:42,130 Me fjalë të tjera, kjo është një operator që lejon 678 00:31:42,130 --> 00:31:45,930 mua që të ketë një ndryshore të majtë në mënyrë tipike, dhe një variabël djathtë, 679 00:31:45,930 --> 00:31:50,640 ose një vlerë individ, se në qoftë se ne DHE ata së bashku, më jep një rezultat përfundimtar. 680 00:31:50,640 --> 00:31:51,560 Pra, çfarë dua të them? 681 00:31:51,560 --> 00:31:54,840 Në qoftë se në një program, ju keni një ndryshore që ruan një prej këtyre vlerave, 682 00:31:54,840 --> 00:31:58,000 ose le të mbani atë të thjeshtë, dhe vetëm shkruani nga zero dhe ato individualisht, 683 00:31:58,000 --> 00:32:00,940 këtu është se si funksionon operatori simbol. 684 00:32:00,940 --> 00:32:06,400 0 simbol 0 do të barabartë 0. 685 00:32:06,400 --> 00:32:07,210 Tani pse është kjo? 686 00:32:07,210 --> 00:32:09,291 >> Është shumë e ngjashme me Shprehje Boolean, 687 00:32:09,291 --> 00:32:10,540 që ne kemi diskutuar deri tani. 688 00:32:10,540 --> 00:32:15,800 Nëse ju mendoni se pas të gjitha, 0 është false, 0 është false, false dhe të rreme 689 00:32:15,800 --> 00:32:18,720 është, siç kemi diskutuar logjikisht, edhe rreme. 690 00:32:18,720 --> 00:32:20,270 Pra, ne të merrni 0 si edhe këtu. 691 00:32:20,270 --> 00:32:24,390 Nëse ju merrni 0 simbol të 1, mirë që, gjithashtu, 692 00:32:24,390 --> 00:32:29,890 do të jetë 0, sepse për këtë shprehje i majtë të jetë e vërtetë ose 1, 693 00:32:29,890 --> 00:32:32,360 ai do të duhet të jetë e vërtetë dhe e vërtetë. 694 00:32:32,360 --> 00:32:36,320 Por këtu kemi false dhe i vërtetë, ose 0 dhe 1. 695 00:32:36,320 --> 00:32:42,000 Tani përsëri, në qoftë se ne kemi 1 simbol të 0, që, gjithashtu, do të jetë 0, 696 00:32:42,000 --> 00:32:47,240 dhe në qoftë se ne kemi 1 zëvendësojeni me 1, më në fund do të kemi një grimë 1. 697 00:32:47,240 --> 00:32:50,340 Pra, me fjalë të tjera, ne nuk jemi duke bërë çdo gjë interesante me këtë operator 698 00:32:50,340 --> 00:32:51,850 vetëm ende, ky operator simbol. 699 00:32:51,850 --> 00:32:53,780 Është bitwise DHE operatori. 700 00:32:53,780 --> 00:32:57,290 Por këto janë përbërësit nëpërmjet të cilës ne mund të bëjmë 701 00:32:57,290 --> 00:32:59,240 gjëra interesante, si ne do të shohim së shpejti. 702 00:32:59,240 --> 00:33:02,790 >> Tani le të shohim vetëm të vetme bar vertikale mbi këtu në të djathtë. 703 00:33:02,790 --> 00:33:06,710 Nëse unë kam një grimë 0 dhe unë Ose me, The bitwise 704 00:33:06,710 --> 00:33:11,030 Ose operatori, një tjetër 0 bit, që do të jepni 0. 705 00:33:11,030 --> 00:33:17,540 Nëse unë të marrë një grimë 0 dhe ose me një 1 bit, atëherë unë jam duke shkuar për të marrë 1. 706 00:33:17,540 --> 00:33:19,830 Dhe në fakt, vetëm për qartësi, më lejoni të kthehem, 707 00:33:19,830 --> 00:33:23,380 kështu që baret e mia vertikale nuk janë të gabuar për 1 s. 708 00:33:23,380 --> 00:33:26,560 Më lejoni të rishkruaj të gjithë 1 im është pak më shumë 709 00:33:26,560 --> 00:33:32,700 në mënyrë të qartë, në mënyrë që ne të ardhshëm të shohim, nëse unë kanë një 1 ose 0, kjo do të jetë një 1, 710 00:33:32,700 --> 00:33:39,060 dhe në qoftë se unë kam një 1 ose 1 që, gjithashtu, do të jetë një 1. 711 00:33:39,060 --> 00:33:42,900 Kështu që ju mund të shihni logjikisht se OR Operatori sillet shumë ndryshe. 712 00:33:42,900 --> 00:33:48,070 Kjo më jep 0 ose 0 jep me 0, por çdo kombinim tjetër më jep 1. 713 00:33:48,070 --> 00:33:52,480 Për sa kohë që unë kam një 1 në formula, rezultati do të jetë 1. 714 00:33:52,480 --> 00:33:55,580 >> Në kontrast me dhe operatorit, simbol, 715 00:33:55,580 --> 00:34:00,940 vetëm në qoftë se unë kam dy 1 është në ekuacion, mund të vërtetë të marrë një 1 nga. 716 00:34:00,940 --> 00:34:02,850 Tani ka një tjetër pak Operatorët si. 717 00:34:02,850 --> 00:34:04,810 Një prej tyre është pak më shumë të përfshira. 718 00:34:04,810 --> 00:34:07,980 Pra më lejoni të shkoj përpara dhe të fshihet kjo për të liruar deri disa hapësirë. 719 00:34:07,980 --> 00:34:13,020 720 00:34:13,020 --> 00:34:16,460 Dhe le të marrin një vështrim në simbol caret, për vetëm një moment. 721 00:34:16,460 --> 00:34:18,210 Kjo është zakonisht një karakter ju mund të shtypni 722 00:34:18,210 --> 00:34:21,420 në tuaj Shift mbajtjes tastierë dhe pastaj një nga numrat në majë SHBA tuaj 723 00:34:21,420 --> 00:34:22,250 tastierë. 724 00:34:22,250 --> 00:34:26,190 >> Pra, kjo është ekskluzive Ose operatori, ekskluzive ose. 725 00:34:26,190 --> 00:34:27,790 Pra, ne vetëm e pa operatorin OSE. 726 00:34:27,790 --> 00:34:29,348 Kjo është ekskluziv ose operatori. 727 00:34:29,348 --> 00:34:30,639 Çfarë është në të vërtetë ndryshimi? 728 00:34:30,639 --> 00:34:34,570 E pra, le të vetëm shikoni në formulë, dhe e përdorin këtë si përbërës në fund të fundit. 729 00:34:34,570 --> 00:34:37,690 0 XOR 0. 730 00:34:37,690 --> 00:34:39,650 Unë jam duke shkuar për të thënë është gjithmonë 0. 731 00:34:39,650 --> 00:34:41,400 Ky është përkufizimi i XOR. 732 00:34:41,400 --> 00:34:47,104 0 XOR 1 do të jetë 1. 733 00:34:47,104 --> 00:34:58,810 1 XOR 0 do të jetë 1, dhe 1 XOR 1 do të jetë? 734 00:34:58,810 --> 00:34:59,890 Gabuar? 735 00:34:59,890 --> 00:35:00,520 Apo e drejtë? 736 00:35:00,520 --> 00:35:01,860 Une nuk e di. 737 00:35:01,860 --> 00:35:02,810 0. 738 00:35:02,810 --> 00:35:04,700 Tani çfarë po ndodh këtu? 739 00:35:04,700 --> 00:35:06,630 E pra mendoj në lidhje me Emri i këtij operatori. 740 00:35:06,630 --> 00:35:09,980 Ekskluzive OSE, ashtu si emri, lloj, sugjeron, 741 00:35:09,980 --> 00:35:13,940 përgjigja është vetëm do të jetë një 1 në qoftë se inputet janë të veçantë, 742 00:35:13,940 --> 00:35:15,560 ekskluzivisht e ndryshme. 743 00:35:15,560 --> 00:35:18,170 Kështu që këtu inputet janë njëjtë, kështu që prodhimi është 0. 744 00:35:18,170 --> 00:35:20,700 Këtu inputet janë njëjtë, kështu që prodhimi është 0. 745 00:35:20,700 --> 00:35:25,640 Këtu janë rezultatet janë të ndryshme, ata janë ekskluzive, dhe kështu prodhimi është 1. 746 00:35:25,640 --> 00:35:28,190 Kështu që është shumë e ngjashme me DHE, kjo është shumë e ngjashme, 747 00:35:28,190 --> 00:35:32,760 ose më mirë është shumë e ngjashme me OSE, por vetëm në një mënyrë të veçantë. 748 00:35:32,760 --> 00:35:36,210 Kjo nuk është më një 1, sepse ne kemi dy 1-së, 749 00:35:36,210 --> 00:35:38,621 dhe jo vetëm, vetëm një prej tyre. 750 00:35:38,621 --> 00:35:39,120 Në rregull. 751 00:35:39,120 --> 00:35:40,080 Po në lidhje me të tjerët? 752 00:35:40,080 --> 00:35:44,220 Well Tilde, ndërkohë, është në fakt e bukur dhe të thjeshtë, fatmirësisht. 753 00:35:44,220 --> 00:35:46,410 Dhe kjo është një unary operatori, që do të thotë 754 00:35:46,410 --> 00:35:50,400 ajo është aplikuar në vetëm një input, një madhësi, kështu që të flasin. 755 00:35:50,400 --> 00:35:51,800 Jo për një të majtë dhe një e drejtë. 756 00:35:51,800 --> 00:35:56,050 Me fjalë të tjera, në qoftë se ju merrni shenjë tildë e 0, përgjigja do të jetë e kundërta. 757 00:35:56,050 --> 00:35:59,710 Dhe në qoftë se ju merrni Tilde nga 1, Përgjigja nuk do të jetë e kundërta. 758 00:35:59,710 --> 00:36:02,570 Pra, operatori Tilde është një mënyrë për të mohuar një grimë, 759 00:36:02,570 --> 00:36:06,000 ose Flipping pak nga 0 deri 1, ose nga 1 ne 0. 760 00:36:06,000 --> 00:36:09,820 >> Dhe kjo na lë në fund me vetëm dy operatorë të formës së prerë, 761 00:36:09,820 --> 00:36:13,840 e ashtuquajtura ndryshim majtë, dhe ashtuquajturi operator djathtas ndryshim. 762 00:36:13,840 --> 00:36:16,620 Le të marrin një sy se si ato punë. 763 00:36:16,620 --> 00:36:20,780 Operatori i la ndryshim, i shkruar me dy kllapa kënd si kjo, 764 00:36:20,780 --> 00:36:22,110 vepron si më poshtë. 765 00:36:22,110 --> 00:36:27,390 Në qoftë se input tim, ose operandi im, në të majtë Operatori ndryshim është thjesht një 1. 766 00:36:27,390 --> 00:36:33,750 Dhe unë pastaj tregoni kompjuterin në la ndryshim se 1, thonë shtatë vende, 767 00:36:33,750 --> 00:36:37,150 rezultati është sikur unë marrë atë 1, dhe të lëvizin atë 768 00:36:37,150 --> 00:36:40,160 shtatë vende mbi të majtë, dhe nga default, 769 00:36:40,160 --> 00:36:42,270 ne jemi duke shkuar për të supozojmë se hapësira në të djathtë 770 00:36:42,270 --> 00:36:44,080 do të jetë i mbushur me zero. 771 00:36:44,080 --> 00:36:50,316 Me fjalë të tjera, 1 u largua ndryshim 7 po shkon për të dhënë më se 1, e ndjekur nga 1, 2, 3, 772 00:36:50,316 --> 00:36:54,060 4, 5, 6, 7 zero. 773 00:36:54,060 --> 00:36:57,380 Pra, në një mënyrë, kjo ju lejon të të marrë një numër të vogël si 1, 774 00:36:57,380 --> 00:37:00,740 dhe në mënyrë të qartë të bëjë atë shumë shumë, shumë më të madhe në këtë mënyrë, 775 00:37:00,740 --> 00:37:06,460 por ne jemi të vërtetë do të shohim qasje më të zgjuar për të 776 00:37:06,460 --> 00:37:08,080 në vend të kësaj, po ashtu, 777 00:37:08,080 --> 00:37:08,720 >> Në rregull. 778 00:37:08,720 --> 00:37:10,060 Kjo është ajo për javën e tretë. 779 00:37:10,060 --> 00:37:11,400 Ne do të ju shohim herën tjetër. 780 00:37:11,400 --> 00:37:12,770 Kjo ishte CS50. 781 00:37:12,770 --> 00:37:17,270 782 00:37:17,270 --> 00:37:22,243 >> [Muzika] 783 00:37:22,243 --> 00:37:25,766 >> SPEAKER 1: Ai ishte në rostiçeri bar të hahet një sundae nxehtë krem ​​karamel. 784 00:37:25,766 --> 00:37:28,090 Ai kishte të gjitha mbi fytyrën e tij. 785 00:37:28,090 --> 00:37:30,506 Ai është veshur se çokollata si një mjekër 786 00:37:30,506 --> 00:37:31,756 SPEAKER 2: Çfarë po bën? 787 00:37:31,756 --> 00:37:32,422 SPEAKER 3: Hmmm? 788 00:37:32,422 --> 00:37:33,500 Çfarë? 789 00:37:33,500 --> 00:37:36,800 >> SPEAKER 2: A ju vetëm dip dyfishtë? 790 00:37:36,800 --> 00:37:38,585 Ju dyfishtë zhytur chip. 791 00:37:38,585 --> 00:37:39,460 SPEAKER 3: Më falni. 792 00:37:39,460 --> 00:37:44,440 SPEAKER 2: Ju zhytur chip, ju mori një pickim, dhe ju zhytur përsëri. 793 00:37:44,440 --> 00:37:44,940 SPEAKER 3: 794 00:37:44,940 --> 00:37:48,440 SPEAKER 2: Pra kjo është vënë si e drejta juaj e tërë gojën në dip. 795 00:37:48,440 --> 00:37:52,400 Herën tjetër ju merrni një çip, vetëm dip atë një herë, dhe do të përfundojë atë. 796 00:37:52,400 --> 00:37:53,890 >> SPEAKER 3: Ju e dini se çfarë, Dan? 797 00:37:53,890 --> 00:37:58,006 Ju dip në mënyrën që ju dëshironi për të dip. 798 00:37:58,006 --> 00:38:01,900 Unë do të kridhem në mënyrën që unë dua të kridhem. 799 00:38:01,900 --> 00:38:03,194