1 00:00:00,000 --> 00:00:02,570 [Powered by Google Translate] [Pjesa 3 - më të rehatshme] 2 00:00:02,570 --> 00:00:05,070 [Rob Bowden - Universiteti i Harvardit] 3 00:00:05,070 --> 00:00:07,310 >> [Kjo është CS50. - CS50.TV] 4 00:00:07,310 --> 00:00:12,700 >> Pra, pyetja e parë është e formuluara cuditerisht. 5 00:00:12,700 --> 00:00:17,480 Gdb ju lejon "debug" një program, por, më konkretisht, çfarë e bën atë të ju lejojnë të bëni? 6 00:00:17,480 --> 00:00:22,590 Unë do të përgjigjem se një, dhe unë nuk e di se çfarë pritet saktësisht, 7 00:00:22,590 --> 00:00:27,910 kështu që unë jam guessing kjo është diçka që përgjatë vijave të saj ju lejon të hap pas hapi 8 00:00:27,910 --> 00:00:31,540 ecin përmes programit, të ndërveprojnë me të, variablave ndryshim, bëni të gjitha këto gjëra - 9 00:00:31,540 --> 00:00:34,270 në thelb plotësisht të kontrolluar ekzekutimin e një programi 10 00:00:34,270 --> 00:00:38,410 dhe të inspektojë çdo pjesë të caktuar të ekzekutimit të programit. 11 00:00:38,410 --> 00:00:43,030 Pra, këto karakteristika të ju lejojnë të korrigjoj gjërat. 12 00:00:43,030 --> 00:00:44,830 Rregull. 13 00:00:44,830 --> 00:00:50,520 Pse nuk kërkoni binare kërkojnë që një grup të ndahen? 14 00:00:50,520 --> 00:00:53,360 Kush dëshiron të përgjigjet se? 15 00:00:56,120 --> 00:01:00,070 [Student] Për shkak se ajo nuk punon në qoftë se ajo nuk është e renditura. Po >>. [Qeshura] 16 00:01:00,070 --> 00:01:04,910 Nëse kjo nuk është e renditura, atëherë kjo është e pamundur për të ndarë atë në gjysmën e 17 00:01:04,910 --> 00:01:07,850 dhe e di se çdo gjë në të majtë është më pak dhe çdo gjë në të djathtë 18 00:01:07,850 --> 00:01:10,490 është më e madhe se vlera e mesme. 19 00:01:10,490 --> 00:01:12,790 Pra, ajo duhet të zgjidhet. 20 00:01:12,790 --> 00:01:14,170 Rregull. 21 00:01:14,170 --> 00:01:17,570 Pse është lloj flluskë në O n katror? 22 00:01:17,570 --> 00:01:23,230 A ka dikush të parë duan të japin një pasqyrë shumë të shpejtë të nivelit të lartë të asaj lloj flluskë është? 23 00:01:25,950 --> 00:01:33,020 [Student] Ju në thelb të shkoni nëpër çdo element dhe ju shikoni elementet e para. 24 00:01:33,020 --> 00:01:37,150 Nëse ata janë nga ku bie në ujdi ato, atëherë ju shikoni elementet e ardhshme dhe kështu me radhë. 25 00:01:37,150 --> 00:01:40,770 Kur të keni arritur në fund, atëherë ju e dini se elementi më i madh është vendosur në fund, 26 00:01:40,770 --> 00:01:42,750 kështu që ju injorojnë se një, atëherë ju mbani në duke kaluar, 27 00:01:42,750 --> 00:01:48,490 dhe çdo herë që ju duhet të kontrolloni një element pak derisa ju të bëni asnjë ndryshim. Po >>. 28 00:01:48,490 --> 00:01:58,470 Ajo që quhet lloj flluskë sepse në qoftë se ju rrokullisje array në anën e saj kështu që është lart dhe poshtë, vertikale, 29 00:01:58,470 --> 00:02:03,100 atëherë vlerat e mëdha do të fundoset në fund dhe vlerat e vogla do të flluskë deri në krye. 30 00:02:03,100 --> 00:02:05,210 Kjo është se si ajo mori emrin e tij. 31 00:02:05,210 --> 00:02:08,220 Dhe vërtet, ju thjesht të shkojnë përmes. 32 00:02:08,220 --> 00:02:11,190 Ju mbani duke shkuar nëpër rrjet, shkëmbejnë vlerën më të madhe 33 00:02:11,190 --> 00:02:14,040 për të marrë vlerat më të mëdha në fund. 34 00:02:14,040 --> 00:02:17,500 >> Pse është ajo O n katror? 35 00:02:18,690 --> 00:02:24,620 Së pari, nuk dua të them dikush se pse kjo është O n katror? 36 00:02:24,620 --> 00:02:28,760 [Student] Sepse per cdo afat herë ajo shkon n. 37 00:02:28,760 --> 00:02:32,100 Ju vetëm mund të jetë i sigurt që ju keni marrë elementi më i madh të gjithë rrugën poshtë, 38 00:02:32,100 --> 00:02:35,230 atëherë ju duhet të përsëris se për aq shumë elemente. Po >>. 39 00:02:35,230 --> 00:02:41,800 Pra, mbani në mend se çfarë do të thotë i madh o dhe çfarë do të thotë të mëdha Omega. 40 00:02:41,800 --> 00:02:50,560 O i madh është si pjesën e sipërme të detyruar se si i ngadalshëm kjo në fakt mund të kandidojë. 41 00:02:50,560 --> 00:02:58,990 Pra, duke thënë: Ø e n katror, ​​ajo nuk është O n apo tjetër ajo do të jetë në gjendje për të kandiduar 42 00:02:58,990 --> 00:03:02,640 në kohë lineare, por kjo është e n o cubed 43 00:03:02,640 --> 00:03:06,390 sepse ajo kufizohet nga O n cubed. 44 00:03:06,390 --> 00:03:12,300 Nëse është e kufizohet nga O n katror, ​​atëherë ajo kufizohet edhe nga n cubed. 45 00:03:12,300 --> 00:03:20,280 Pra, kjo është n katror, ​​dhe në rastin më të keq absolute ajo nuk mund ta bëjë më mirë se n katror, 46 00:03:20,280 --> 00:03:22,830 cila është pse ajo është O i N katror. 47 00:03:22,830 --> 00:03:31,200 Pra, për të parë se si matematikë të vogël del të jetë n katror, 48 00:03:31,200 --> 00:03:40,530 në qoftë se ne kemi pesë gjëra në listën tonë, për herë të parë se sa këmbime mund të kemi potencialisht duhet të bëjnë 49 00:03:40,530 --> 00:03:47,170 në mënyrë që të marrë këtë? Le të vërtetë vetëm - 50 00:03:47,170 --> 00:03:52,040 Sa këmbime jemi ne do të duhet të bëjë në afat të parë të lloj flluskë nëpër rrjet? 51 00:03:52,040 --> 00:03:53,540 [Student] n - 1. Po >>. 52 00:03:53,540 --> 00:03:58,340 >> Nëse ka 5 elemente, ne do të duhet të bëjnë n - 1. 53 00:03:58,340 --> 00:04:01,100 Pastaj në një të dytë sa këmbime jemi ne do të duhet të bëjë? 54 00:04:01,100 --> 00:04:03,440 [Studenti n] - 2. Po >>. 55 00:04:03,440 --> 00:04:11,640 Dhe e treta do të jetë n - 3, dhe pastaj për komoditetin që unë do të shkruaj dy vitet e fundit 56 00:04:11,640 --> 00:04:15,270 si atëherë ne do të duhet të bëjë këmbime 2 dhe 1 Swap. 57 00:04:15,270 --> 00:04:19,899 I guess i fundit mund ose nuk mund të vërtetë duhet të ndodhë. 58 00:04:19,899 --> 00:04:22,820 A është kjo një shkëmbim? Nuk e di. 59 00:04:22,820 --> 00:04:26,490 Pra, këto janë shumat totale të këmbime ose së paku krahasimet që ju keni për të bërë. 60 00:04:26,490 --> 00:04:29,910 Edhe nëse ju nuk keni të bie në ujdi, ju ende nevojë për të krahasuar vlerat. 61 00:04:29,910 --> 00:04:33,910 Pra, ka n - 1 krahasime në afat parë nëpërmjet vektorit. 62 00:04:33,910 --> 00:04:42,050 Në qoftë se ju korrigjoj këto gjëra, le të bëjë në fakt atë gjashtë gjëra kaq gjëra të lart grumbulloj bukur, 63 00:04:42,050 --> 00:04:44,790 dhe pastaj unë do të bëj 3, 2, 1. 64 00:04:44,790 --> 00:04:49,910 Pra, vetëm këto shuma rearranging, ne duam të shohim se sa kemi bërë krahasime 65 00:04:49,910 --> 00:04:52,700 në algorithm tërë. 66 00:04:52,700 --> 00:04:56,550 Pra, nëse kemi sjellë këta njerëz këtu poshtë, 67 00:04:56,550 --> 00:05:07,470 atëherë ne jemi ende vetëm përmbledhje krahasime megjithatë shumë atje ishin. 68 00:05:07,470 --> 00:05:13,280 Por në qoftë se ne të përmbledhur këto dhe të përmbledhur këto dhe kemi përmbledhur këto, 69 00:05:13,280 --> 00:05:18,130 është ende të njëjtin problem. Ne vetëm të përmbledhur ato grupe të veçanta. 70 00:05:18,130 --> 00:05:22,400 >> Kështu që tani që ne jemi mbledhur së 3 n. Kjo nuk është vetëm 3 të n. 71 00:05:22,400 --> 00:05:27,650 Ajo gjithmonë do të jetë n / 2 të n. 72 00:05:27,650 --> 00:05:29,430 Pra, këtu kemi të ndodhë që të ketë 6. 73 00:05:29,430 --> 00:05:34,830 Nëse do të kishim 10 gjërat, atëherë ne mund të bëjmë këtë grupim për 5 çifte të ndryshme të gjërave 74 00:05:34,830 --> 00:05:37,180 dhe përfundojnë me n + n + n + n + n. 75 00:05:37,180 --> 00:05:45,840 Pra, ju jeni gjithmonë do të merrni n / 2 e N, dhe kështu kjo ne do të shënoj atë për n katror / 2. 76 00:05:45,840 --> 00:05:48,890 Dhe kështu edhe pse kjo është faktor i gjysmës së, gjë që ndodh për të ardhur në 77 00:05:48,890 --> 00:05:54,190 për shkak të faktit se nëpërmjet çdo ripërsëritje mbi array krahasojmë 1 më pak 78 00:05:54,190 --> 00:05:58,040 kështu që kjo është se si ne të merrni më shumë se 2, por ajo është ende n katror. 79 00:05:58,040 --> 00:06:01,650 Ne nuk e kujdesit në lidhje me faktor të vazhdueshëm të një gjysmë. 80 00:06:01,650 --> 00:06:07,760 Pra, një shumë gjëra të mëdha O si kjo mbështetet në vetëm një lloj të bërë këtë lloj të matematikë, 81 00:06:07,760 --> 00:06:12,260 bërë shuma aritmetike dhe gjeometrike sende seri, 82 00:06:12,260 --> 00:06:17,750 por shumica e tyre në këtë kurs janë goxha të thjeshtë. 83 00:06:17,750 --> 00:06:19,290 Rregull. 84 00:06:19,290 --> 00:06:24,430 Pse është lloj futje në Omega e n? Çfarë do të thotë omega? 85 00:06:24,430 --> 00:06:27,730 [Dy studentë duke folur në një herë - pakuptueshëm] Yeah >>. 86 00:06:27,730 --> 00:06:30,630 Omega ju mund të mendoni si të ulët detyruar. 87 00:06:30,630 --> 00:06:36,550 >> Pra nuk ka rëndësi se sa të efektshme lloj futje juaj algoritmi është, 88 00:06:36,550 --> 00:06:41,810 pavarësisht nga lista që është miratuar në, ajo gjithmonë ka për të krahasuar të paktën n gjërat 89 00:06:41,810 --> 00:06:44,620 ose ajo ka për të iterate mbi gjërat n. 90 00:06:44,620 --> 00:06:47,280 Pse është kjo? 91 00:06:47,280 --> 00:06:51,190 [Student] Sepse nëse lista është renditur tashmë, pastaj përmes përsëritje parë 92 00:06:51,190 --> 00:06:54,080 ju mund të garantojë se elementi i parë është pak, 93 00:06:54,080 --> 00:06:56,490 dhe përsëritje e dytë që ju vetëm mund të garantojë dy të parët janë 94 00:06:56,490 --> 00:07:00,010 sepse ju nuk e dini se pjesa tjetër e listës është renditur. Po >>. 95 00:07:00,010 --> 00:07:08,910 Në qoftë se ju të kalojë në një listë të renditura plotësisht, të paktën ju keni për të shkuar mbi të gjitha elementet e 96 00:07:08,910 --> 00:07:12,180 për të parë se asgjë nuk ka nevojë për të lëvizur rreth. 97 00:07:12,180 --> 00:07:14,720 Kështu kalon mbi listën dhe duke thënë, oh, kjo është tashmë e renditura, 98 00:07:14,720 --> 00:07:18,240 është e pamundur për ju të dini është e renditura derisa ju të kontrolloni çdo element 99 00:07:18,240 --> 00:07:20,660 për të parë se ata janë në mënyrë renditura. 100 00:07:20,660 --> 00:07:25,290 Kështu ulët i detyruar në lloj futje është i Omega n. 101 00:07:25,290 --> 00:07:28,210 Çfarë është rasti më i keq drejtimin koha e lloj bashkojë, 102 00:07:28,210 --> 00:07:31,390 Rasti më i keq qenë O mëdha përsëri? 103 00:07:31,390 --> 00:07:37,660 Pra, në rastin më të keq, si e bën lloj bashkojë të drejtuar? 104 00:07:42,170 --> 00:07:43,690 [Student] N log n. Po >>. 105 00:07:43,690 --> 00:07:49,990 Më të shpejtë algoritme përgjithshme rradhitje janë n log n. Ju nuk mund të bëjmë më mirë. 106 00:07:51,930 --> 00:07:55,130 >> Ka raste të veçanta, dhe në qoftë se ne kemi kohë sot - por ne ndoshta won't - 107 00:07:55,130 --> 00:07:59,330 ne mund të shohim atë që bën më mirë se n log n. 108 00:07:59,330 --> 00:08:04,050 Por në rastin e përgjithshëm, ju nuk mund të bëni më mirë se n log n. 109 00:08:04,050 --> 00:08:09,680 Dhe të shkrihej lloj ndodh të jetë një që ju duhet të dini për këtë kurs që është n log n. 110 00:08:09,680 --> 00:08:13,260 Dhe kështu që ne do të jetë në fakt zbatimin që sot. 111 00:08:13,260 --> 00:08:18,070 Dhe së fundi, në jo më shumë se tre fjali, si e bën punën e përzgjedhjes renditjes? 112 00:08:18,070 --> 00:08:20,370 A dikush dëshiron të përgjigjem, dhe unë do të llogariten dënimet tuaja 113 00:08:20,370 --> 00:08:22,390 sepse në qoftë se ju shkoni mbi 3 - 114 00:08:25,530 --> 00:08:28,330 A ka dikush kujtohet lloj përzgjedhje? 115 00:08:31,280 --> 00:08:37,809 Lloj Zgjedhja është zakonisht shumë e lehtë për të kujtuar vetëm nga emri. 116 00:08:37,809 --> 00:08:45,350 Ju vetëm iterate mbi array, të gjejnë çfarëdo vlera më e madhe është ose më i vogël - 117 00:08:45,350 --> 00:08:47,290 çfarëdo mënyrë që ju jeni klasifikim in 118 00:08:47,290 --> 00:08:50,750 Pra, le të thonë se ne jemi zgjidhja nga më i vogli tek më i madh. 119 00:08:50,750 --> 00:08:55,250 Ju iterate mbi array, duke kërkuar për çfarëdo elementi minimal është, 120 00:08:55,250 --> 00:08:59,750 përzgjidhe at, dhe pastaj vetëm shkëmbim atë çka është në vendin e parë. 121 00:08:59,750 --> 00:09:04,090 Dhe pastaj në kalimin e dytë mbi vektorit, po për të elementit minimale përsëri, 122 00:09:04,090 --> 00:09:07,490 zgjidhni atë, dhe pastaj të bie në ujdi me atë që është në pozitën e dytë. 123 00:09:07,490 --> 00:09:10,650 Pra, ne jemi vetëm picking dhe duke zgjedhur vlerat minimale 124 00:09:10,650 --> 00:09:16,050 dhe futur ato në frontin e vektorit deri sa ajo është e renditura. 125 00:09:19,210 --> 00:09:21,560 Pyetjet për këtë? 126 00:09:21,560 --> 00:09:25,710 >> Këto shfaqen në mënyrë të pashmangshme në format që ju duhet të plotësoni kur ju jeni dorëzimin e pset. 127 00:09:29,010 --> 00:09:32,360 Ata janë në thelb të përgjigjet atyre. 128 00:09:32,360 --> 00:09:34,230 Mirë, kështu që tani coding probleme. 129 00:09:34,230 --> 00:09:40,140 Unë tashmë e dërguar nga mbi email - A nuk merrni atë dikush email? Rregull. 130 00:09:40,140 --> 00:09:46,630 Unë tashmë dërguar email mbi hapësirën që ne jemi duke shkuar për të përdorur, 131 00:09:46,630 --> 00:09:52,120 dhe në qoftë se ju klikoni mbi emrin tim - kështu që unë mendoj se jam do të jetë në fund 132 00:09:52,120 --> 00:09:57,170 për shkak të r prapa - por nëse ju klikoni në emrin tim ju do të shihni 2 rishikime. 133 00:09:57,170 --> 00:10:02,650 Rishikimi 1 do të jetë I kopjuar dhe tashmë ngjit kodin në Spaces 134 00:10:02,650 --> 00:10:06,900 për gjë kërkimit ju jeni do të duhet të zbatojnë. 135 00:10:06,900 --> 00:10:10,540 Rishikimi dhe 2 do të jetë gjëja lloj që ne zbatimin e pas kësaj. 136 00:10:10,540 --> 00:10:15,770 Kështu që ju mund të klikoni mbi Revision time 1 dhe punojnë nga atje. 137 00:10:17,350 --> 00:10:22,060 Dhe tani ne duam të zbatojë kërkimin binar. 138 00:10:22,060 --> 00:10:26,470 >> A ka dikush duan të japin vetëm një shpjegim pseudokod të nivelit të lartë 139 00:10:26,470 --> 00:10:31,440 të asaj që ne do të duhet të bëni për kërkim? Po. 140 00:10:31,440 --> 00:10:36,170 [Student] Ju vetëm të marrë mes të grup dhe të shohim nëse ajo që ju jeni duke kërkuar për 141 00:10:36,170 --> 00:10:38,650 është më pak se që ose më shumë se që. 142 00:10:38,650 --> 00:10:41,080 Dhe në qoftë se kjo është pak, ju shkoni në gjysmën e që është më pak, 143 00:10:41,080 --> 00:10:44,750 dhe në qoftë se kjo është më shumë, ju shkoni në gjysmën që është më shumë dhe ju përsëris se deri sa ju të merrni vetëm një gjë. 144 00:10:44,750 --> 00:10:46,570 [Bowden] Yeah. 145 00:10:46,570 --> 00:10:51,320 Vini re se array numrat ynë është renditur tashmë, 146 00:10:51,320 --> 00:10:57,190 dhe kështu që do të thotë që ne të mund të përfitojnë nga kjo dhe ne mund të kontrolloni të parë, 147 00:10:57,190 --> 00:11:00,390 rregull, unë jam duke kërkuar për numrin 50. 148 00:11:00,390 --> 00:11:03,720 Kështu që unë mund të shkojnë në mes. 149 00:11:03,720 --> 00:11:07,380 Mesme është e vështirë të përcaktojë kur është një numër edhe më të gjëra, 150 00:11:07,380 --> 00:11:10,820 por le të them vetëm ne do të shkurtoj gjithmonë në mes. 151 00:11:10,820 --> 00:11:14,420 Pra, këtu kemi 8 gjëra, kështu që mesme do të jetë 16. 152 00:11:14,420 --> 00:11:17,330 Unë jam duke kërkuar për 50, 50 kështu që është më i madh se 16. 153 00:11:17,330 --> 00:11:21,310 Kështu që tani unë mund të trajtojë në thelb koleksion time si këto elemente. 154 00:11:21,310 --> 00:11:23,450 Unë mund të hedhin larg çdo gjë nga 16 gjatë. 155 00:11:23,450 --> 00:11:27,440 Tani array im është vetëm këto 4 elemente, dhe unë përsëris. 156 00:11:27,440 --> 00:11:31,910 Pra, atëherë unë dua të gjeni mesme përsëri, e cila do të jetë 42. 157 00:11:31,910 --> 00:11:34,730 42 është më pak se 50, kështu që unë mund të hedhin larg këto dy elemente. 158 00:11:34,730 --> 00:11:36,890 Ky është im array mbetur. 159 00:11:36,890 --> 00:11:38,430 Unë jam duke shkuar për të gjetur e mesme përsëri. 160 00:11:38,430 --> 00:11:42,100 I guess 50 ishte një shembull i keq, sepse unë kam qenë gjithmonë gjëra të hedhur larg në të majtë, 161 00:11:42,100 --> 00:11:48,280 por në të njëjtën masë, në qoftë se unë jam duke kërkuar për diçka 162 00:11:48,280 --> 00:11:52,100 dhe kjo është më pak se elementi Unë jam duke kërkuar në, 163 00:11:52,100 --> 00:11:55,080 atëherë unë jam duke shkuar për të hedhur larg çdo gjë në të djathtë. 164 00:11:55,080 --> 00:11:58,150 Pra, tani ne kemi nevojë për të zbatuar atë. 165 00:11:58,150 --> 00:12:02,310 Vini re se ne kemi nevojë për të kaluar në madhësi. 166 00:12:02,310 --> 00:12:06,730 Ne nuk mund të duhet për të vështirë-koduar madhësi. 167 00:12:06,730 --> 00:12:11,640 Pra, nëse ne të hequr qafe se # define - 168 00:12:19,630 --> 00:12:21,430 Rregull. 169 00:12:21,430 --> 00:12:27,180 Si mund ta kuptoj mirë se çfarë madhësia e array numrat aktualisht është? 170 00:12:27,180 --> 00:12:30,950 >> Sa elemente janë në grup numrat? 171 00:12:30,950 --> 00:12:33,630 [Student] Numrat, kllapa,. Gjatësi? 172 00:12:33,630 --> 00:12:36,600 [Bowden] Kjo nuk ekziston në C. 173 00:12:36,600 --> 00:12:38,580 Nevojë. Gjatësi. 174 00:12:38,580 --> 00:12:42,010 Vargjeve nuk kanë prona, kështu që nuk ka pronë gjatësia e vargjeve 175 00:12:42,010 --> 00:12:45,650 që thjesht do të ju jap kohë megjithatë ndodh që të jetë. 176 00:12:48,180 --> 00:12:51,620 [Student] Shih se sa memorie ka dhe ndani me sa - Po. >> 177 00:12:51,620 --> 00:12:55,810 Pra, si mund të shohim sa memorie ka? >> [Student] sizeof. Po >>, sizeof. 178 00:12:55,810 --> 00:13:01,680 Sizeof është operatori që do të kthehen në madhësinë e grup numrash. 179 00:13:01,680 --> 00:13:10,060 Dhe kjo do të jetë integers megjithatë shumë herë nuk janë të madhësisë së një numër i plotë 180 00:13:10,060 --> 00:13:14,050 pasi që është sa memorie është e vërtetë duke marrë deri. 181 00:13:14,050 --> 00:13:17,630 Pra, nëse unë dua numrin e gjërave në grup, 182 00:13:17,630 --> 00:13:20,560 atëherë unë jam duke shkuar për të dëshironi të ndani me madhësinë e një numër të plotë. 183 00:13:22,820 --> 00:13:26,010 Rregull. Kështu që lejon mua të kalojnë në madhësi këtu. 184 00:13:26,010 --> 00:13:29,430 Pse duhet të kalojë në madhësi në të gjitha? 185 00:13:29,430 --> 00:13:38,570 Pse nuk mund ta bëjë vetëm deri këtu madhësia int = sizeof (Kashtë) / sizeof (int)? 186 00:13:38,570 --> 00:13:41,490 Pse nuk është kjo punë? 187 00:13:41,490 --> 00:13:44,470 [Student] Kjo nuk është një ndryshore globale. 188 00:13:44,470 --> 00:13:51,540 [Bowden] Kashtë ekziston dhe ne jemi duke kaluar në numër si kashtë, 189 00:13:51,540 --> 00:13:54,700 dhe kjo është lloj i një paralajmërim i asaj që do të vijnë. Po. 190 00:13:54,700 --> 00:14:00,170 [Student] Kashtë është vetëm referencë për atë, kështu që ajo do të kthehet sa e madhe që është referencë. 191 00:14:00,170 --> 00:14:02,150 Po. 192 00:14:02,150 --> 00:14:09,000 Unë dyshoj në leksionin që e keni parë ende rafte me të vërtetë, e drejtë? 193 00:14:09,000 --> 00:14:11,270 Ne kemi folur vetëm në lidhje me të. 194 00:14:11,270 --> 00:14:16,090 Pra rafte është vendi ku të gjitha variablave tuaja do të ruhen. 195 00:14:16,090 --> 00:14:19,960 >> Çdo kujtesës që është ndarë për variablat lokale që po ndodh në rafte, 196 00:14:19,960 --> 00:14:24,790 dhe çdo funksion merr hapësirën e vet në rafte, kornizë vet rafte është ajo që është quajtur. 197 00:14:24,790 --> 00:14:31,590 Pra kryesor ka kuadrin e saj rafte, dhe në brendësi të tij do të ekzistojë në këtë koleksion numrat, 198 00:14:31,590 --> 00:14:34,270 dhe ajo do të jetë e madhësisë sizeof (numra). 199 00:14:34,270 --> 00:14:38,180 Ajo do të ketë madhësinë e numrave të ndarë nga madhësia e elementeve, 200 00:14:38,180 --> 00:14:42,010 por që gjithë jetën brenda kornizës kryesore e rafte. 201 00:14:42,010 --> 00:14:45,190 Kur ne e quajmë kërko, kërko merr vet kuadrin e saj rafte, 202 00:14:45,190 --> 00:14:48,840 Hapësira e vet për të ruajtur të gjitha variablave të saj lokale. 203 00:14:48,840 --> 00:14:56,420 Por këto argumente - kështu Kashtë nuk është një kopje e këtij grup të tërë. 204 00:14:56,420 --> 00:15:00,990 Ne nuk kalojnë në rrjet të tërë si një kopje në kërkim. 205 00:15:00,990 --> 00:15:04,030 Ajo vetëm kalon një referencë për këtë koleksion. 206 00:15:04,030 --> 00:15:11,470 Pra, kërkoni mund të hyni në këto numra nëpër këtë referencë. 207 00:15:11,470 --> 00:15:17,100 Është ende qasjen gjërat që jetojnë në brendësi të kornizës kryesore të rafte, 208 00:15:17,100 --> 00:15:22,990 por në thelb, kur ne të merrni për pointers, e cila duhet të jetë së shpejti, 209 00:15:22,990 --> 00:15:24,980 kjo është ajo që pointers janë. 210 00:15:24,980 --> 00:15:29,400 Pointers janë vetëm referenca të gjëra, dhe ju mund të përdorni pointers për të hyrë në gjërat 211 00:15:29,400 --> 00:15:32,030 që janë në korniza gjëra të tjera 'rafte. 212 00:15:32,030 --> 00:15:37,660 Pra, edhe pse numri është lokal me kryesor, ne ende mund të hyni në atë nëpërmjet këtij treguesin. 213 00:15:37,660 --> 00:15:41,770 Por, pasi ajo është vetëm një tregues dhe kjo është vetëm një referencë, 214 00:15:41,770 --> 00:15:45,040 sizeof (Kashtë) vetëm e kthen madhësinë e referencës vetë. 215 00:15:45,040 --> 00:15:47,950 Ajo nuk kthehet në madhësinë e gjë është e treguar për të. 216 00:15:47,950 --> 00:15:51,110 Ajo nuk kthehet madhësinë aktuale të numrave. 217 00:15:51,110 --> 00:15:55,660 Dhe kështu që kjo nuk do të punojë si ne duam që ajo të. 218 00:15:55,660 --> 00:15:57,320 >> Pyetjet për këtë? 219 00:15:57,320 --> 00:16:03,250 Pointers do të shkuar në detaje në mënyrë të konsiderueshme më shumë gjakosur në javët që do të vijnë. 220 00:16:06,750 --> 00:16:13,740 Dhe kjo është arsyeja pse shumë gjëra që ju shikoni, gjërat më të kërkimit apo gjërat lloj, 221 00:16:13,740 --> 00:16:16,990 ata janë pothuajse të gjithë do të duhet të marrë madhësinë aktuale të array, 222 00:16:16,990 --> 00:16:20,440 sepse në C, ne nuk kemi ide se çfarë madhësia e array është. 223 00:16:20,440 --> 00:16:22,720 Ju duhet të dorë të kalojë atë in 224 00:16:22,720 --> 00:16:27,190 Dhe ju nuk mund të kalojë dorë në rrjet të gjithë, sepse ju jeni vetëm duke kaluar në referencë 225 00:16:27,190 --> 00:16:30,390 dhe ajo nuk mund të marrë përmasat nga referencë. 226 00:16:30,390 --> 00:16:32,300 Rregull. 227 00:16:32,300 --> 00:16:38,160 Pra, tani ne duam të zbatojë atë që është shpjeguar më parë. 228 00:16:38,160 --> 00:16:41,530 Ju mund të punojnë në atë për një minutë, 229 00:16:41,530 --> 00:16:45,250 dhe ju nuk duhet të shqetësohen për marrjen e çdo gjë të përkryer 100% të punës. 230 00:16:45,250 --> 00:16:51,410 Vetëm shkruani deri pseudokod gjysmë për mënyrën se si ju mendoni se duhet të punojnë. 231 00:16:52,000 --> 00:16:53,630 Rregull. 232 00:16:53,630 --> 00:16:56,350 Nuk ka nevojë për të bërë plotësisht me këtë ende. 233 00:16:56,350 --> 00:17:02,380 Por ka dikush të ndjehen rehat me atë që ata kanë deri më tani, 234 00:17:02,380 --> 00:17:05,599 si diçka që ne mund të punojnë me të së bashku? 235 00:17:05,599 --> 00:17:09,690 A ka dikush doni te vullnetar? Ose unë do të marr rastësisht. 236 00:17:12,680 --> 00:17:18,599 Ajo nuk duhet të jetë e drejtë nga ndonjë masë, por diçka që ne mund të modifikoj në një shtet të punës. 237 00:17:18,599 --> 00:17:20,720 [Student] Sure. Mirë >>. 238 00:17:20,720 --> 00:17:27,220 Kështu që ju mund të ruani rishikimin duke klikuar në ikonën e vogël Save. 239 00:17:27,220 --> 00:17:29,950 Ju jeni Ramya, apo jo? >> [Student] Yeah. >> [Bowden] Okay. 240 00:17:29,950 --> 00:17:35,140 Deri tani unë mund të shikoni tuaj rishikimin dhe secili mund të tërheqë deri rishikim. 241 00:17:35,140 --> 00:17:38,600 Dhe këtu kemi - Mirë. 242 00:17:38,600 --> 00:17:43,160 Kështu Ramya shkoi me zgjidhjen gjithkund rekursive, i cili është padyshim një zgjidhje të vlefshme. 243 00:17:43,160 --> 00:17:44,970 Ka dy mënyra që ju mund të bëni këtë problem. 244 00:17:44,970 --> 00:17:48,060 Ju mund ta bëni atë apo iteratively Recursively. 245 00:17:48,060 --> 00:17:53,860 Shumica e problemeve që ju hasni që mund të bëhet Recursively mund të bëhet edhe iteratively. 246 00:17:53,860 --> 00:17:58,510 Kështu që këtu ne kemi bërë atë Recursively. 247 00:17:58,510 --> 00:18:03,730 >> Ka dikush doni të përcaktuar se çfarë do të thotë për të bërë një funksion recursive? 248 00:18:07,210 --> 00:18:08,920 [Student] Kur ju keni një funksion quajnë veten 249 00:18:08,920 --> 00:18:13,470 dhe pastaj e quajnë veten deri sa ajo vjen me të vërteta dhe të vërtetë. Po >>. 250 00:18:13,470 --> 00:18:17,680 Një funksion recursive është vetëm një funksion i cili e quan veten. 251 00:18:17,680 --> 00:18:24,140 Ka tri gjëra të mëdha që një funksion recursive duhet të ketë. 252 00:18:24,140 --> 00:18:27,310 E para është padyshim, që e quan veten. 253 00:18:27,310 --> 00:18:29,650 E dyta është rasti bazë. 254 00:18:29,650 --> 00:18:33,390 Pra, në disa pika funksioni ka nevojë për të ndaluar e quan veten, 255 00:18:33,390 --> 00:18:35,610 dhe kjo është ajo që ndodh është për bazë. 256 00:18:35,610 --> 00:18:43,860 Kështu që këtu ne e dimë se ne duhet të ndalet, ne duhet të heqim dorë në kërkimin tonë 257 00:18:43,860 --> 00:18:48,150 kur fillimi është e barabartë me fund - dhe ne do të shkojnë mbi atë që thotë. 258 00:18:48,150 --> 00:18:52,130 Por në fund, gjëja e fundit që është e rëndësishme për funksionet gjithkund rekursive: 259 00:18:52,130 --> 00:18:59,250 funksionet duhet disi qasen çështjen bazë. 260 00:18:59,250 --> 00:19:04,140 Ashtu si në qoftë se ju nuk jeni në të vërtetë përditësimin asgjë kur ju bëni thirrje rekursive dytë, 261 00:19:04,140 --> 00:19:07,880 në qoftë se ju jeni fjalë për fjalë vetëm duke e quajtur funksion përsëri me të njëjtat argumente 262 00:19:07,880 --> 00:19:10,130 dhe nuk variabla globale kanë ndryshuar apo ndonjë gjë, 263 00:19:10,130 --> 00:19:14,430 ju kurrë nuk do të arrijë çështjen bazë, në të cilin rast se është e keqe. 264 00:19:14,430 --> 00:19:17,950 Ajo do të jetë një recursion pafund dhe një pirg del nga shtrati. 265 00:19:17,950 --> 00:19:24,330 Por këtu ne shohim se update po ndodh pasi ne jemi përditësimin fillojnë + fund / 2, 266 00:19:24,330 --> 00:19:28,180 ne jemi përditësimin argumentin fund këtu, ne jemi përditësimin argumentin filloni këtu. 267 00:19:28,180 --> 00:19:32,860 Pra, në të gjitha thirrjet gjithkund rekursive ne jemi përditësimin diçka. Rregull. 268 00:19:32,860 --> 00:19:38,110 A doni të ecni ne nëpërmjet zgjidhjes tuaj? Sigurisht >>. 269 00:19:38,110 --> 00:19:44,270 Unë jam duke përdorur SearchHelp kështu që çdo herë që unë të bëjë këtë thirrje funksion 270 00:19:44,270 --> 00:19:47,910 Unë kam fillimin e ku unë jam duke kërkuar për në rrjet dhe në fund 271 00:19:47,910 --> 00:19:49,380 se ku unë jam duke kërkuar array. 272 00:19:49,380 --> 00:19:55,330 >> Në çdo hap ku është thënë se është element mesme, e cila është fillimi fundi + / 2, 273 00:19:55,330 --> 00:19:58,850 është se e barabartë me atë që ne jemi duke kërkuar për? 274 00:19:58,850 --> 00:20:04,650 Dhe në qoftë se ajo është, atëherë kemi gjetur atë, dhe unë mendoj se merr kaluar deri nivelet e recursion. 275 00:20:04,650 --> 00:20:12,540 Dhe në qoftë se nuk është e vërtetë, atëherë ne kontrolloni nëse se vlera e mesme e grup është shumë i madh, 276 00:20:12,540 --> 00:20:19,320 rast në të cilin ne e shohim në gjysmën e majtë të array duke shkuar nga fillimi në indeksin e mesme. 277 00:20:19,320 --> 00:20:22,710 Dhe ndryshe bëjmë gjysmën fund. 278 00:20:22,710 --> 00:20:24,740 [Bowden] Okay. 279 00:20:24,740 --> 00:20:27,730 Ide e mirë. 280 00:20:27,730 --> 00:20:36,640 Mirë, kështu që një çift gjërat, dhe në fakt, kjo është një gjë shumë e nivelit të lartë 281 00:20:36,640 --> 00:20:41,270 që ju kurrë nuk do të duhet të dini për këtë kurs, por kjo është e vërtetë. 282 00:20:41,270 --> 00:20:46,080 Funksionet gjithkund rekursive, ju gjithmonë dëgjuar se ata janë një marrëveshje e keqe 283 00:20:46,080 --> 00:20:51,160 sepse nëse ju telefononi Recursively veten shumë herë, ju merrni overflow stack 284 00:20:51,160 --> 00:20:54,990 pasi, siç kam thënë më parë, çdo funksion merr vet kuadrin e saj rafte. 285 00:20:54,990 --> 00:20:59,500 Kështu që çdo thirrje të funksionit rekursiv merr vet kuadrin e saj rafte. 286 00:20:59,500 --> 00:21:04,140 Pra, nëse ju të bëni thirrje 1.000 gjithkund rekursive, që ju të merrni 1.000 korniza rafte, 287 00:21:04,140 --> 00:21:08,390 dhe shpejt ju të çojë për të pasur korniza shumë rafte dhe gjëra vetëm thyer. 288 00:21:08,390 --> 00:21:13,480 Pra, kjo është arsyeja pse funksionet gjithkund rekursive në përgjithësi janë të këqija. 289 00:21:13,480 --> 00:21:19,370 Por nuk është një subset e bukur e funksioneve gjithkund rekursive gjithkund rekursive quajtur bisht-funksionet, 290 00:21:19,370 --> 00:21:26,120 dhe kjo ndodh të jetë një shembull i një ku në qoftë se përpiluesit e vëren këtë 291 00:21:26,120 --> 00:21:29,920 dhe kjo duhet, unë mendoj se - në qoftë se ju të kalojë tingëllimë atë-O2 flamur 292 00:21:29,920 --> 00:21:33,250 atëherë ajo do të vini re kjo është bishti rekursive dhe të bëjë gjëra të mira. 293 00:21:33,250 --> 00:21:40,050 >> Ajo do të ripërdorimin kornizë njëjtin rafte mbi dhe pa pushim për çdo thirrje rekursive. 294 00:21:40,050 --> 00:21:47,010 Dhe kështu që ju jeni duke përdorur të njëjtën kornizë rafte, ju nuk keni nevojë për t'u shqetësuar rreth 295 00:21:47,010 --> 00:21:51,690 ndonjëherë rafte tejmbushur, dhe në të njëjtën kohë, si ju tha më parë, 296 00:21:51,690 --> 00:21:56,380 ku sapo ju të ktheheni e vërtetë, atëherë ajo duhet të kthehet deri të gjitha këto korniza rafte 297 00:21:56,380 --> 00:22:01,740 dhe thirrja për 10 SearchHelp duhet të kthehet në 9, duhet të kthehen në 8. 298 00:22:01,740 --> 00:22:05,360 Kështu që nuk ka nevojë të ndodhë kur funksionet gjithkund rekursive janë bisht. 299 00:22:05,360 --> 00:22:13,740 Dhe kështu ajo që e bën këtë funksion recursive bishti është njoftimi që për çdo thirrje të dhënë për searchHelp 300 00:22:13,740 --> 00:22:18,470 thirrja rekursive që është bërë është ajo që po kthehen. 301 00:22:18,470 --> 00:22:25,290 Pra, në thirrjen e parë në SearchHelp, ne ose kthehen menjëherë të rreme, 302 00:22:25,290 --> 00:22:29,590 kthehen menjëherë e vërtetë, apo kemi bërë një thirrje rekursive për SearchHelp 303 00:22:29,590 --> 00:22:33,810 ku ajo që ne jemi duke u kthyer është ajo që thirrja është kthyer. 304 00:22:33,810 --> 00:22:51,560 Dhe ne nuk mund ta bëjë këtë në qoftë se ne e bëmë diçka si int x = SearchHelp, kthimit x * 2, 305 00:22:51,560 --> 00:22:55,440 vetëm disa ndryshime të rastit. 306 00:22:55,440 --> 00:23:01,470 >> Deri tani kjo thirrje rekursive, kjo int x = thirrje SearchHelp rekursive, 307 00:23:01,470 --> 00:23:05,740 nuk është më bisht recursive sepse ai në fakt nuk duhet të kthehet 308 00:23:05,740 --> 00:23:10,400 përsëri në një kornizë pirg në mënyrë që të mëparshme se thirrja e mëparshme në funksion 309 00:23:10,400 --> 00:23:13,040 pastaj mund të bëjë diçka me vlerë e kthimit. 310 00:23:13,040 --> 00:23:22,190 Pra, kjo nuk është bishti rekursive, por ajo që ne kishim para është bukur bisht rekursive. Po. 311 00:23:22,190 --> 00:23:27,000 [Student] nuk duhet të jetë rasti i dytë bazë kontrollohet parë 312 00:23:27,000 --> 00:23:30,640 sepse nuk mund të jetë një situatë ku, kur ju të kalojë atë argumentin 313 00:23:30,640 --> 00:23:35,770 ju keni filluar = fund, por ato janë vlera gjilpërë. 314 00:23:35,770 --> 00:23:47,310 Pyetja nuk ishte ne mund të kandidojë në rastin kur në fund është vlera gjilpërë 315 00:23:47,310 --> 00:23:52,000 ose të fillojnë = fund, të përshtatshme, të fillojë = fund 316 00:23:52,000 --> 00:23:59,480 dhe ju nuk keni kontrolluar të vërtetë atë vlerë të veçantë ende, 317 00:23:59,480 --> 00:24:03,910 pastaj të fillojë + fund / 2 është vetëm do të jetë vlera e njëjtë. 318 00:24:03,910 --> 00:24:07,890 Por ne kemi kthyer tashmë rreme dhe ne kurrë nuk kontrollohen në fakt vlerën. 319 00:24:07,890 --> 00:24:14,240 Pra, të paktën, në thirrjen e parë, në qoftë se madhësia është 0, atëherë ne duam të kthehen rreme. 320 00:24:14,240 --> 00:24:17,710 Por në qoftë se madhësia është 1, atëherë nuk do të fillojë deri në fund të barabartë, 321 00:24:17,710 --> 00:24:19,820 dhe ne do të të paktën të kontrolluar elementin një. 322 00:24:19,820 --> 00:24:26,750 Por unë mendoj se ju jeni të drejtë në atë që ne mund të përfundojë në një rast kur fillojnë + fund / 2, 323 00:24:26,750 --> 00:24:31,190 Fillimi përfundon duke qenë të njëjta si fillim + fund / 2, 324 00:24:31,190 --> 00:24:35,350 por kurrë nuk kemi kontrolluar të vërtetë atë element. 325 00:24:35,350 --> 00:24:44,740 >> Pra, në qoftë se ne së pari të kontrolloni është elementi mesme vlera ne jemi duke kërkuar për të, 326 00:24:44,740 --> 00:24:47,110 atëherë ne mund të kthehen menjëherë vërtetë. 327 00:24:47,110 --> 00:24:50,740 Tjetër në qoftë se ata janë të barabartë, atëherë nuk ka asnjë pikë për të vazhduar 328 00:24:50,740 --> 00:24:58,440 pasi ne jemi vetëm duke shkuar për të rinovuar në një rast ku ne jemi në një grup të vetëm element. 329 00:24:58,440 --> 00:25:01,110 Në qoftë se elementi i vetëm nuk është një ne jemi duke kërkuar për të, 330 00:25:01,110 --> 00:25:03,530 atëherë çdo gjë është e gabuar. Po. 331 00:25:03,530 --> 00:25:08,900 [Student] Gjë është se që nga madhësia është në të vërtetë më i madh se numri i elementeve në array, 332 00:25:08,900 --> 00:25:13,070 ka tashmë një kompensuar - >> Pra do size - 333 00:25:13,070 --> 00:25:19,380 [Student] Thuaj, nëse array ishte madhësia 0, atëherë SearchHelp të vërtetë do të kontrollojë kashtë e 0 334 00:25:19,380 --> 00:25:21,490 në thirrjen e parë. 335 00:25:21,490 --> 00:25:25,300 Grup ka madhësi 0, kështu që është 0 - >> Yeah. 336 00:25:25,300 --> 00:25:30,750 Nuk është një tjetër gjë që - kjo mund të jetë e mirë. Le të mendojmë. 337 00:25:30,750 --> 00:25:40,120 Pra, nëse array kishte 10 elemente dhe një e mesme ne jemi duke shkuar për të kontrolluar është indeksi 5, 338 00:25:40,120 --> 00:25:45,700 kështu që ne jemi duke kontrolluar 5, dhe le të thonë se vlera është më pak. 339 00:25:45,700 --> 00:25:50,720 Pra, ne jemi duke hedhur çdo gjë larg nga 5 e tutje. 340 00:25:50,720 --> 00:25:54,030 Pra, fillojë në fund + / 2 do të jetë fundi ynë i ri, 341 00:25:54,030 --> 00:25:57,450 Pra, vërtet, ajo është gjithmonë do të qëndrojë edhe pas përfundimit të vektorit. 342 00:25:57,450 --> 00:26:03,570 Në qoftë se kjo është një rast në qoftë se ajo ishte edhe apo i rastësishëm, atëherë ne do të kontrolloni, të themi, 4, 343 00:26:03,570 --> 00:26:05,770 por ne jemi ende duke hedhur larg - 344 00:26:05,770 --> 00:26:13,500 Pra, vërtet, në fund është gjithmonë do të jetë edhe pas përfundimit aktual të vektorit. 345 00:26:13,500 --> 00:26:18,350 Pra, elementet ne jemi duke u përqëndruar në, në fund është gjithmonë do të jetë njëri pas kësaj. 346 00:26:18,350 --> 00:26:24,270 Dhe kështu që nëse fillimi bën kurrë fund të barabartë, ne jemi në një grup të madhësisë 0. 347 00:26:24,270 --> 00:26:35,600 >> Gjë tjetër që unë isha duke menduar është që ne jemi përditësimin fillojnë të fillojnë + fund / 2, 348 00:26:35,600 --> 00:26:44,020 kështu që ky është rasti që unë jam i pasur probleme me të, kur fillojnë + fund / 2 349 00:26:44,020 --> 00:26:46,820 është elementi ne jemi të kontrolluar. 350 00:26:46,820 --> 00:26:58,150 Le të thonë se kemi pasur këtë koleksion 10-element. Çfarëdo. 351 00:26:58,150 --> 00:27:03,250 Pra, fillojë në fund + / 2 do të jetë diçka si ky, 352 00:27:03,250 --> 00:27:07,060 dhe në qoftë se nuk është vlera, thonë se ne duam për të rinovuar. 353 00:27:07,060 --> 00:27:10,060 Vlera është më e madhe, kështu që ne duam të shikojmë në këtë gjysmën e vektorit. 354 00:27:10,060 --> 00:27:15,910 Deri sa ne jemi përditësimin fillim, ne jemi përditësimin fillim të tani do të jetë ky element. 355 00:27:15,910 --> 00:27:23,790 Por kjo ende mund të punojnë, ose në shumë pak, ju mund të bëni të fillojë në fund + / 2 + 1. 356 00:27:23,790 --> 00:27:27,850 [Student] Ju nuk duhet të fillojë në fund + [padëgjueshme] >> Yeah. 357 00:27:27,850 --> 00:27:33,240 Ne kemi kontrolluar tashmë këtë element dhe e di se nuk është një ne jemi duke kërkuar për të. 358 00:27:33,240 --> 00:27:36,800 Pra, ne nuk kemi nevojë për të rinovuar të fillojë të jetë në këtë element. 359 00:27:36,800 --> 00:27:39,560 Ne vetëm mund të kaloni atë dhe përditësimin e të fillojë të jetë në këtë element. 360 00:27:39,560 --> 00:27:46,060 Dhe a ka kurrë një rast, le të themi, se ky ishte fundi, 361 00:27:46,060 --> 00:27:53,140 kështu që pastaj të fillojë do të jetë ky, të fillojnë + fund / 2 do të jetë kjo, 362 00:27:53,140 --> 00:28:00,580 fillojnë + fund - Po, unë mendoj se mund të përfundojë deri në recursion pafund. 363 00:28:00,580 --> 00:28:12,690 Le të thonë se kjo është vetëm një grup të madhësisë 2 ose një grup të madhësisë 1. Unë mendoj se kjo do të punojnë. 364 00:28:12,690 --> 00:28:19,490 Pra, aktualisht, fillimi është se elementi dhe në fund është 1 përtej tij. 365 00:28:19,490 --> 00:28:24,110 Pra, element që ne jemi duke shkuar për të kontrolluar është kjo një, 366 00:28:24,110 --> 00:28:29,400 dhe pastaj kur ne update fillim, ne jemi përditësimin fillojë të jetë 0 + 1/2, 367 00:28:29,400 --> 00:28:33,160 e cila do të përfundojë të na kthehet me fillimin qenë ky element. 368 00:28:33,160 --> 00:28:36,210 >> Pra, ne jemi të kontrolluar elementin njëjta pa pushim. 369 00:28:36,210 --> 00:28:43,310 Pra, ky është rasti ku çdo thirrje rekursive duhet të vërtetë të rinovuar diçka. 370 00:28:43,310 --> 00:28:48,370 Pra, ne duhet të bëjmë fillimin + fund / 2 + 1, ose tjetër ka një rast 371 00:28:48,370 --> 00:28:50,710 ku ne nuk jeni në të vërtetë fillimin përditësimin. 372 00:28:50,710 --> 00:28:53,820 Gjithkush shihni se? 373 00:28:53,820 --> 00:28:56,310 Rregull. 374 00:28:56,310 --> 00:29:03,860 A ka ndokush pyetje për këtë zgjidhje ose komente asnjë më shumë? 375 00:29:05,220 --> 00:29:10,280 Rregull. Does anyone kanë një përsëritës zgjidhje që ne të gjithë mund të shikojnë? 376 00:29:17,400 --> 00:29:20,940 A ne të gjithë bëjmë atë Recursively? 377 00:29:20,940 --> 00:29:25,950 Ose edhe unë mendoj se në qoftë se ju hap hers, atëherë ju mund të keni të parandalohet një tuaj të mëparshëm. 378 00:29:25,950 --> 00:29:28,810 E bën atë automatikisht të shpëtuar? Unë nuk jam pozitive. 379 00:29:35,090 --> 00:29:39,130 Does anyone kanë përsëritës? 380 00:29:39,130 --> 00:29:42,430 Ne mund të ecin nëpër atë së bashku, nëse jo. 381 00:29:46,080 --> 00:29:48,100 Ideja do të jetë e njëjtë. 382 00:30:00,260 --> 00:30:02,830 Përsëritës zgjidhje. 383 00:30:02,830 --> 00:30:07,140 Ne do të duan të bëjnë në thelb të njëjtën ide 384 00:30:07,140 --> 00:30:16,530 ku ne duam të mbajnë gjurmët e përfundimit të ri të grup dhe fillimin e ri të array 385 00:30:16,530 --> 00:30:18,510 dhe të bëjë atë mbi dhe mbi. 386 00:30:18,510 --> 00:30:22,430 Dhe në qoftë se ajo që ne jemi mbajtja e si fillim dhe në fund gjithnjë ndërpritet, 387 00:30:22,430 --> 00:30:29,020 atëherë ne nuk kemi gjetur atë dhe ne mund të kthehet rreme. 388 00:30:29,020 --> 00:30:37,540 Pra, si mund ta bëni këtë? Dikush ka sugjerime ose kod për mua për të tërhequr deri? 389 00:30:42,190 --> 00:30:47,450 [Student] A një lak kohë. Po >>. 390 00:30:47,450 --> 00:30:49,450 Ju do të dëshironi të bëni një lak. 391 00:30:49,450 --> 00:30:51,830 >> A keni kodin unë mund të tërheqë deri, ose çfarë u keni shkuar për të sugjeruar? 392 00:30:51,830 --> 00:30:56,340 [Student] Unë mendoj kështu. >> All drejtë. Kjo e bën gjërat më të lehtë. Cili ishte emri juaj? 393 00:30:56,340 --> 00:30:57,890 [Student] Lucas. 394 00:31:00,140 --> 00:31:04,190 Rishikimi 1. Rregull. 395 00:31:04,190 --> 00:31:13,200 Ulët është ajo që ne e quajti filluar më parë. 396 00:31:13,200 --> 00:31:17,080 Up nuk është mjaft atë që quhet fundi parë. 397 00:31:17,080 --> 00:31:22,750 Në fakt, në fund tani është në rrjet. Është një element që duhet marrë parasysh. 398 00:31:22,750 --> 00:31:26,890 Aq i ulët është 0, lart është madhësia e grup - 1, 399 00:31:26,890 --> 00:31:34,780 dhe tani ne jemi looping, dhe ne jemi të kontrolluar - 400 00:31:34,780 --> 00:31:37,340 I guess ju mund të ecin nëpër atë. 401 00:31:37,340 --> 00:31:41,420 Cili ishte menduarit tuaj nëpërmjet këtë? Ecni ne nëpërmjet kodit tuaj. 402 00:31:41,420 --> 00:31:49,940 [Student] Sure. Shikoni në vlerën e kashtë në mes dhe të krahasojnë atë me gjilpërë. 403 00:31:49,940 --> 00:31:58,520 Pra, në qoftë se ajo është më e madhe se gjilpërë tuaj, atëherë ju doni të - oh, në të vërtetë, që duhet të jetë prapa. 404 00:31:58,520 --> 00:32:05,180 Ju jeni do të duan të hedhin larg gjysmën e drejtë, dhe kështu vërtet, që duhet të jetë rruga. 405 00:32:05,180 --> 00:32:08,830 [Bowden] Pra, kjo duhet të jetë më pak? Është se ajo që keni thënë? >> [Student] Yeah. 406 00:32:08,830 --> 00:32:10,390 [Bowden] Okay. Më pak. 407 00:32:10,390 --> 00:32:15,700 Pra, në qoftë se ajo që ne jemi duke kërkuar në është më i vogël se ajo që ne duam, 408 00:32:15,700 --> 00:32:19,410 atëherë vërtet, ne duam që të hedhin larg gjysmën e majtë, 409 00:32:19,410 --> 00:32:22,210 që do të thotë ne jemi përditësimin çdo gjë që ne jemi duke marrë parasysh 410 00:32:22,210 --> 00:32:26,610 duke lëvizur në të djathtë të ulët të vektorit. 411 00:32:26,610 --> 00:32:30,130 Kjo duket e mirë. 412 00:32:30,130 --> 00:32:34,550 Unë mendoj se kjo ka të njëjtën çështje që ne tha në një mëparshme, 413 00:32:34,550 --> 00:32:49,760 ku nëse i ulët është 0 dhe lart është 1, atëherë të ulët + up / 2 do të jetë ngritur për të njëjtën gjë përsëri. 414 00:32:49,760 --> 00:32:53,860 >> Dhe edhe në qoftë se nuk është rasti, ajo është ende më efikase në shumë pak 415 00:32:53,860 --> 00:32:57,630 të vetëm hedhin larg elementin ne vetëm shikuar në të cilën ne e dimë është e gabuar. 416 00:32:57,630 --> 00:33:03,240 Në mënyrë të ulët + up / 2 + 1 - >> [Student] Kjo duhet të jetë mënyra të tjera. 417 00:33:03,240 --> 00:33:05,900 [Bowden] Apo kjo duhet të jetë - 1 dhe një tjetër duhet të jetë + 1. 418 00:33:05,900 --> 00:33:09,580 [Student] Dhe nuk duhet të jetë një shenjë të dyfishtë barabartë. >> [Bowden] Yeah. 419 00:33:09,580 --> 00:33:11,340 [Student] Yeah. 420 00:33:14,540 --> 00:33:15,910 Rregull. 421 00:33:15,910 --> 00:33:21,280 Dhe së fundi, tani që ne kemi këtë + 1-1 gjë, 422 00:33:21,280 --> 00:33:31,520 është ajo - ai nuk mund të jetë - është gjithnjë e mundur për të ulët të përfundojnë me një vlerë më të madhe se deri? 423 00:33:35,710 --> 00:33:40,320 Unë mendoj se mënyra e vetme që mund të ndodhë - është e mundur? >> [Student] Unë nuk e di. 424 00:33:40,320 --> 00:33:45,220 Por në qoftë se ajo merr cunguar dhe pastaj merr minus se 1 dhe pastaj - >> Yeah. 425 00:33:45,220 --> 00:33:47,480 [Student] Ajo ndoshta do të merrni messed up. 426 00:33:49,700 --> 00:33:53,940 Unë mendoj se kjo duhet të jetë e mirë vetëm për shkak se 427 00:33:53,940 --> 00:33:58,800 që ajo të përfundojë më të ulët se ata do të duhet të jenë të barabartë, unë mendoj. 428 00:33:58,800 --> 00:34:03,070 Por në qoftë se ata janë të barabartë, atëherë ne nuk do të kishte bërë lak, ndërsa për të filluar me 429 00:34:03,070 --> 00:34:06,670 dhe ne vetëm do të kthyer vlerën. Kështu që unë mendoj se ne jemi të mirë tani. 430 00:34:06,670 --> 00:34:11,530 Vini re se edhe pse ky problem nuk është më rekursive, 431 00:34:11,530 --> 00:34:17,400 njëjtin lloj e ideve të aplikojnë ku ne mund të shohim se si kjo kaq lehtë jep veten 432 00:34:17,400 --> 00:34:23,659 për një zgjidhje rekursiv nga fakti se ne jemi vetëm përditësimin e indekseve pa pushim, 433 00:34:23,659 --> 00:34:29,960 ne jemi duke e bërë problem vogla dhe të vogla, ne jemi duke u përqëndruar në një mesin e array. 434 00:34:29,960 --> 00:34:40,860 [Student] Nëse i ulët është 0 dhe lart është 1, ata do të jenë të dyja 0 + 1/2, i cili do të shkojë në 0, 435 00:34:40,860 --> 00:34:44,429 dhe pastaj do të jetë një + 1, një do të jetë - 1. 436 00:34:47,000 --> 00:34:50,870 [Student] Ku jemi ne kontrollimin e barazisë? 437 00:34:50,870 --> 00:34:55,100 Ashtu si në qoftë se një e mesme është në të vërtetë gjilpërë? 438 00:34:55,100 --> 00:34:58,590 Ne nuk jemi duke bërë atë? Oh! 439 00:35:00,610 --> 00:35:02,460 Nëse it's - 440 00:35:05,340 --> 00:35:13,740 Po. Ne nuk mund të bëjë testin këtu poshtë, sepse le të themi e mesme parë - 441 00:35:13,740 --> 00:35:16,430 [Student] Është fakt si nuk e hedhin larg lidhur. 442 00:35:16,430 --> 00:35:20,220 Pra, nëse ju hedh larg lidhur, ju duhet për të kontrolluar atë para apo çfarëdo. 443 00:35:20,220 --> 00:35:23,350 Ah. Po. >> [Student] Yeah. 444 00:35:23,350 --> 00:35:29,650 Pra, tani ne kemi hedhur larg atë që ne aktualisht shikuar në, 445 00:35:29,650 --> 00:35:33,260 që do të thotë që ne tani duhet të ketë gjithashtu 446 00:35:33,260 --> 00:35:44,810 në qoftë se (Kashtë [(Ulët + deri) / 2] == gjilpërë), atëherë ne mund të kthehen vërtetë. 447 00:35:44,810 --> 00:35:52,070 Dhe nëse kam vënë tjetër ose vetëm në qoftë se, kjo do të thotë fjalë për fjalë të njëjtën gjë 448 00:35:52,070 --> 00:35:57,110 sepse kjo do të janë kthyer vërtetë. 449 00:35:57,110 --> 00:36:01,450 Kështu që unë do të vënë tjetër në qoftë se, por kjo nuk ka rëndësi. 450 00:36:01,450 --> 00:36:10,440 >> Pra, nëse kjo tjetër, tjetër këtë, dhe kjo është një gjë e zakonshme të bëj 451 00:36:10,440 --> 00:36:14,340 ku edhe nëse ajo është rasti ku çdo gjë është e mirë këtu, 452 00:36:14,340 --> 00:36:22,780 si të ulët nuk mund të jetë më e madhe se lart, kjo nuk është arsyetim vlen rreth asaj nëse kjo është e vërtetë. 453 00:36:22,780 --> 00:36:28,010 Kështu që ju mund edhe të thonë, ndërsa të ulët është më pak se ose e barabartë me 454 00:36:28,010 --> 00:36:30,720 ose derisa të ulët është më pak se 455 00:36:30,720 --> 00:36:35,300 kështu që nëse ata janë të barabartë apo të ulët ndonjëherë ndodh që të kalojë deri, 456 00:36:35,300 --> 00:36:40,130 atëherë ne mund të shpërthejë nga ky lak. 457 00:36:41,410 --> 00:36:44,630 Pyetje, shqetësime, komente? 458 00:36:47,080 --> 00:36:49,270 Rregull. Kjo duket e mirë. 459 00:36:49,270 --> 00:36:52,230 Tani ne duam të bëjmë lloj. 460 00:36:52,230 --> 00:37:04,030 Nëse ne do të shkojmë për rishikimin e dytë, ne shohim këto shifra të njëjta, 461 00:37:04,030 --> 00:37:07,550 por tani ata nuk janë më në mënyrë renditura. 462 00:37:07,550 --> 00:37:12,840 Dhe ne duam të zbatojë përdorimin e ndonjë lloj algoritmi në të O n log n. 463 00:37:12,840 --> 00:37:17,240 Kështu që algoritmi mendoni ju se ne duhet të zbatojë këtu? >> [Student] lloj Merge. 464 00:37:17,240 --> 00:37:23,810 [Bowden] Yeah. Merge lloj është O (n log n), kështu që kjo është ajo që ne jemi duke shkuar për të bërë. 465 00:37:23,810 --> 00:37:26,680 Dhe problemi do të jetë shumë e ngjashme, 466 00:37:26,680 --> 00:37:31,920 ku të lehtë jep veten për një zgjidhje gjithkund rekursive. 467 00:37:31,920 --> 00:37:35,580 Ne gjithashtu mund të dalë me një zgjidhje përsëritës nëse duam, 468 00:37:35,580 --> 00:37:42,540 por recursion do të jetë më e lehtë këtu dhe ne duhet të bëjmë recursion. 469 00:37:45,120 --> 00:37:49,530 I guess ne do të ecim nëpër lloj bashkojë të parë, 470 00:37:49,530 --> 00:37:54,280 edhe pse nuk është një video e bukur në lloj Merge tashmë. [Qeshura] 471 00:37:54,280 --> 00:37:59,780 Pra bashkojë lloj ka - Unë jam humbur aq shumë i këtij punimi. 472 00:37:59,780 --> 00:38:02,080 Oh, ka vetëm një të majtë. 473 00:38:02,080 --> 00:38:03,630 Pra bashkohen. 474 00:38:08,190 --> 00:38:12,470 Oh, 1, 3, 5. 475 00:38:26,090 --> 00:38:27,440 Rregull. 476 00:38:29,910 --> 00:38:33,460 Merge merr dy vargjeve të veçanta. 477 00:38:33,460 --> 00:38:36,780 Individualisht këto dy vargjeve të dyja janë të renditura. 478 00:38:36,780 --> 00:38:40,970 Pra, ky grup, 1, 3, 5, të renditura. Ky grup, 0, 2, 4, renditura. 479 00:38:40,970 --> 00:38:46,710 Tani çfarë bashkojë duhet të bëni është të kombinohen ato në një rrjet të vetëm që është vetë renditura. 480 00:38:46,710 --> 00:38:57,130 Pra, ne duam një rrjet të madhësisë 6 që do të kenë këto elemente në brendësi të saj 481 00:38:57,130 --> 00:38:59,390 në mënyrë renditura. 482 00:38:59,390 --> 00:39:03,390 >> Dhe kështu që ne mund të përfitojnë nga fakti se këto dy vargjeve janë të renditura 483 00:39:03,390 --> 00:39:06,800 për të bërë këtë në kohë lineare, 484 00:39:06,800 --> 00:39:13,510 Kuptimi lineare Ora nëse ky grup është x madhësi dhe kjo është y madhësia, 485 00:39:13,510 --> 00:39:20,970 atëherë algoritmi i përgjithshëm duhet të jetë O (x + y). Rregull. 486 00:39:20,970 --> 00:39:23,150 Pra sugjerime. 487 00:39:23,150 --> 00:39:26,030 [Student] A mund të fillojnë nga e majta? 488 00:39:26,030 --> 00:39:30,150 Kështu që ju do të vënë poshtë 0 të parë dhe pastaj 1 dhe atëherë këtu ju jeni në 2. 489 00:39:30,150 --> 00:39:33,320 Pra, kjo është lloj i si ju keni një skedë që është duke lëvizur në të djathtë. >> [Bowden] Yeah. 490 00:39:33,320 --> 00:39:41,070 Për të dyja këto vargjeve nëse ne vetëm të përqëndrohet në elementin pari nga e majta. 491 00:39:41,070 --> 00:39:43,530 Sepse të dy vargjeve janë të renditura, ne e dimë se këto 2 elemente 492 00:39:43,530 --> 00:39:46,920 janë elementet më të vogla në secilin grup. 493 00:39:46,920 --> 00:39:53,500 Kështu që do të thotë se 1 nga ata 2 elemente duhet të jenë element i vogël në rrjet tonë bashkuar. 494 00:39:53,500 --> 00:39:58,190 Kjo ndodh pikërisht kështu që i vogël është ai në kohën e duhur këtë. 495 00:39:58,190 --> 00:40:02,580 Pra, ne kemi marrë 0, futur atë në të majtë, sepse është më pak se 0 1, 496 00:40:02,580 --> 00:40:08,210 kështu që të marrë 0, futur atë në pozitën tonë të parë, dhe pastaj ne update këtë 497 00:40:08,210 --> 00:40:12,070 tani përqëndrohet në elementin e parë. 498 00:40:12,070 --> 00:40:14,570 Dhe tani ne përsërisim. 499 00:40:14,570 --> 00:40:20,670 Deri tani ne krahasojmë 2 dhe 1. 1 është më i vogël, kështu që ne do të futni 1. 500 00:40:20,670 --> 00:40:25,300 Ne update këtë tregues të tregojnë për këtë djalë. 501 00:40:25,300 --> 00:40:33,160 Tani ne bëjmë atë përsëri, kështu që 2. Kjo do të update, krahasuar këto 2, 3. 502 00:40:33,160 --> 00:40:37,770 Kjo përditësime, pastaj 4 dhe 5. 503 00:40:37,770 --> 00:40:42,110 Kështu që është bashkojë. 504 00:40:42,110 --> 00:40:49,010 >> Ajo duhet të jetë goxha e qartë se kjo është koha lineare që ne vetëm të shkojnë nëpër çdo element herë. 505 00:40:49,010 --> 00:40:55,980 Dhe kjo është hapi më i madh në zbatimin lloj bashkojë është duke bërë këtë. 506 00:40:55,980 --> 00:40:59,330 Dhe kjo nuk është se e vështirë. 507 00:40:59,330 --> 00:41:15,020 Një disa gjëra për t'u shqetësuar rreth është le të themi se janë shkrirja 1, 2, 3, 4, 5, 6. 508 00:41:15,020 --> 00:41:30,930 Në këtë rast ne fund deri në skenar ku kjo është e do të jetë më i vogël, 509 00:41:30,930 --> 00:41:36,160 pastaj ne update këtë tregues, kjo do të jetë më i vogël, update this, 510 00:41:36,160 --> 00:41:41,280 kjo është më e vogël, dhe tani ju duhet të njohin 511 00:41:41,280 --> 00:41:44,220 kur ju keni të vërtetë të drejtuar nga elementë të krahasuar me të. 512 00:41:44,220 --> 00:41:49,400 Që nga viti ne kemi përdorur tashmë këtë koleksion të tërë, 513 00:41:49,400 --> 00:41:55,190 çdo gjë në këtë grup tani është futur vetëm në këtu. 514 00:41:55,190 --> 00:42:02,040 Pra, në qoftë se ne ndonjëherë të kandidojë në pikën ku një prej vargjeve tona është shkrirë plotësisht tashmë, 515 00:42:02,040 --> 00:42:06,510 atëherë ne vetëm të marrë të gjitha elementet e vektorit tjetër dhe futur ato në fund të vektorit. 516 00:42:06,510 --> 00:42:13,630 Pra, ne vetëm mund të futni 4, 5, 6. Rregull. 517 00:42:13,630 --> 00:42:18,070 Kjo është një gjë për të parë për të. 518 00:42:22,080 --> 00:42:26,120 Zbatimin që duhet të jetë hapi i 1. 519 00:42:26,120 --> 00:42:32,600 Merge lloj pastaj në bazë të kësaj, ajo është 2 hapa, 2 hapa pa kuptim. 520 00:42:38,800 --> 00:42:42,090 Le të japim këtë koleksion. 521 00:42:57,920 --> 00:43:05,680 Pra bashkojë lloj, hap 1 është që të Recursively të thyer grup në gjysmave. 522 00:43:05,680 --> 00:43:09,350 Ndarë kështu këtë grup në gjysmave. 523 00:43:09,350 --> 00:43:22,920 Ne tani kemi 4, 15, 16, 50 dhe 8, 23, 42, 108. 524 00:43:22,920 --> 00:43:25,800 Dhe tani ne e bëjmë atë përsëri dhe ne ndarë këto në gjysmave. 525 00:43:25,800 --> 00:43:27,530 Unë vetëm do të bëni atë në këtë anë. 526 00:43:27,530 --> 00:43:34,790 Kështu 4, 15 dhe 16, 50. 527 00:43:34,790 --> 00:43:37,440 Ne do të bëjmë të njëjtën gjë gjatë këtu. 528 00:43:37,440 --> 00:43:40,340 Dhe tani ne ndarë atë në gjysmave përsëri. 529 00:43:40,340 --> 00:43:51,080 Dhe ne kemi 4, 15, 16, 50. 530 00:43:51,080 --> 00:43:53,170 Kështu që është rasti ynë bazë. 531 00:43:53,170 --> 00:44:00,540 Pasi vargjeve janë të madhësisë 1, atëherë kemi të ndaluar me ndarjen në pjesë. 532 00:44:00,540 --> 00:44:03,190 >> Tani çfarë bëjmë ne me këtë? 533 00:44:03,190 --> 00:44:15,730 Ne deri në fund kjo do të prishen në 8, 23, 42, dhe 108. 534 00:44:15,730 --> 00:44:24,000 Pra, tani që ne jemi në këtë pikë, tani hap dy lloj bashkojë është vetëm bashkimi palë të listave. 535 00:44:24,000 --> 00:44:27,610 Pra, ne duam që të bashkojë këto. Ne vetëm thirrje të bashkohen. 536 00:44:27,610 --> 00:44:31,410 Ne e dimë se do të kthehet bashkojë këto në mënyrë renditura. 537 00:44:31,410 --> 00:44:33,920 4, 15. 538 00:44:33,920 --> 00:44:41,440 Tani ne duam të bashkojë këto, dhe se do të kthehet një listë me ato në mënyrë renditura, 539 00:44:41,440 --> 00:44:44,160 16, 50. 540 00:44:44,160 --> 00:44:57,380 Ne bashkojë ata - Unë nuk mund të shkruaj - 8, 23 dhe 42, 108. 541 00:44:57,380 --> 00:45:02,890 Pra, ne kemi çifte shkrirë njëherë. 542 00:45:02,890 --> 00:45:05,140 Tani ne vetëm të bashkohen përsëri. 543 00:45:05,140 --> 00:45:10,130 Vini re se secili prej këtyre listave është renditur në vetvete, 544 00:45:10,130 --> 00:45:15,220 dhe pastaj ne vetëm mund të bashkojë këto lista për të marrë një listë të madhësisë 4, i cili është renditur 545 00:45:15,220 --> 00:45:19,990 dhe të shkrihej këto dy lista të merrni një listë të madhësisë 4 që është renditura. 546 00:45:19,990 --> 00:45:25,710 Dhe në fund, ne mund të bashkojë këto dy lista të madhësisë 4 të merrni një listë të madhësisë 8 që është renditura. 547 00:45:25,710 --> 00:45:34,030 Pra, për të parë se kjo është e përgjithshme n log n, ne tashmë e pa se bashkojë është linear, 548 00:45:34,030 --> 00:45:40,390 kështu që kur ne jemi që kanë të bëjnë me bashkimin këto, kështu si koston e përgjithshme të bashkohen 549 00:45:40,390 --> 00:45:43,410 për këto dy listave është vetëm 2 sepse - 550 00:45:43,410 --> 00:45:49,610 Ose mirë, kjo është O n, por n këtu është vetëm këto 2 elemente, kështu që është 2. 551 00:45:49,610 --> 00:45:52,850 Dhe këto 2 do të jetë 2 dhe këto 2 do të jetë 2 dhe këto 2 do të jetë 2, 552 00:45:52,850 --> 00:45:58,820 kështu nëpër të gjitha bashkon që ne duhet të bëjmë, ne deri në fund duke bërë n. 553 00:45:58,820 --> 00:46:03,210 Si 2 + 2 + 2 + 2 është 8, e cila është n, 554 00:46:03,210 --> 00:46:08,060 kështu që kostoja e bashkimit në këtë grup është n. 555 00:46:08,060 --> 00:46:10,810 Dhe pastaj e njëjta gjë këtu. 556 00:46:10,810 --> 00:46:16,980 Ne do të bashkojë këto 2, atëherë këto 2, dhe individualisht ky bashkojë do të marrin katër operacione, 557 00:46:16,980 --> 00:46:23,610 kjo do të bashkojë katër operacionet, por edhe një herë, në mes të gjitha këto, 558 00:46:23,610 --> 00:46:29,030 deri ne fund bashkimin n gjërat totale, dhe kështu ky hap i merr n. 559 00:46:29,030 --> 00:46:33,670 Dhe kështu çdo nivel merr elemente n duke u shkrirë. 560 00:46:33,670 --> 00:46:36,110 >> Dhe sa nivelet janë atje? 561 00:46:36,110 --> 00:46:40,160 Në çdo nivel, array ynë rritet me madhësinë e 2. 562 00:46:40,160 --> 00:46:44,590 Këtu vargjeve tona janë të një madhësie 1, këtu ata janë të madhësisë 2, këtu ata janë të madhësisë 4, 563 00:46:44,590 --> 00:46:46,470 dhe më në fund, ata janë të madhësisë 8. 564 00:46:46,470 --> 00:46:56,450 Kështu që ajo është dyfishuar, nuk do të jetë një total prej log n nga këto nivele. 565 00:46:56,450 --> 00:47:02,090 Pra, me log n nivele, secili nivel individual marrë n operacionet në total, 566 00:47:02,090 --> 00:47:05,720 ne kemi marrë një log n n algorithm. 567 00:47:05,720 --> 00:47:07,790 Pyetje? 568 00:47:08,940 --> 00:47:13,320 Kanë njerëzit tashmë e bërë përparim në mënyrën se si për të zbatuar këtë? 569 00:47:13,320 --> 00:47:18,260 Është dikush tashmë në një shtet ku unë mund vetëm të tërheqë deri kodin e tyre? 570 00:47:20,320 --> 00:47:22,260 Unë mund të jap një minutë. 571 00:47:24,770 --> 00:47:27,470 Ky i fundit do të jetë më e gjatë. 572 00:47:27,470 --> 00:47:28,730 I highly recommend përsëritet - 573 00:47:28,730 --> 00:47:30,510 Ju nuk keni për të bërë recursion për bashkimin 574 00:47:30,510 --> 00:47:33,750 sepse për të bërë recursion për bashkimin, ju jeni do të duhet të kalojë një bandë e madhësive të ndryshme. 575 00:47:33,750 --> 00:47:37,150 Ju mund, por kjo është i bezdisshëm. 576 00:47:37,150 --> 00:47:43,720 Por për recursion lloj vetë është shumë e lehtë. 577 00:47:43,720 --> 00:47:49,190 Ju vetëm fjalë thirrje lloj në gjysmën e majtë, në gjysmën lloj djathtë. Rregull. 578 00:47:51,770 --> 00:47:54,860 Çdokush keni ndonjë gjë që unë mund të tërheqë deri akoma? 579 00:47:54,860 --> 00:47:57,540 Ose tjetër unë do të jap një minutë. 580 00:47:58,210 --> 00:47:59,900 Rregull. 581 00:47:59,900 --> 00:48:02,970 Çdokush ka diçka që ne mund të punojnë me të? 582 00:48:05,450 --> 00:48:09,680 Apo tjetër ne do të punojnë vetëm me këtë dhe pastaj të zgjerohet nga atje. 583 00:48:09,680 --> 00:48:14,050 >> Çdokush kanë më shumë se kjo që unë mund të tërheqë deri? 584 00:48:14,050 --> 00:48:17,770 [Student] Yeah. Ju mund të tërheqë deri minave. >> All drejtë. 585 00:48:17,770 --> 00:48:19,730 Po! 586 00:48:22,170 --> 00:48:25,280 [Student] Ka qenë një shumë të kushteve. >> Oh, xhiruar. Mund të ju - 587 00:48:25,280 --> 00:48:28,110 [Student] Unë duhet të ruani atë. Po >>. 588 00:48:32,420 --> 00:48:35,730 Pra, ne e bëmë të bëjë bashkim veçmas. 589 00:48:35,730 --> 00:48:38,570 Oh, por kjo nuk është edhe aq keq. 590 00:48:39,790 --> 00:48:41,650 Rregull. 591 00:48:41,650 --> 00:48:47,080 Kështu renditjes në vetvete është vetëm duke e quajtur mergeSortHelp. 592 00:48:47,080 --> 00:48:49,530 Na shpjegojë se çfarë mergeSortHelp bën. 593 00:48:49,530 --> 00:48:55,700 [Student] MergeSortHelp pretty much bën dy hapa kryesorë, 594 00:48:55,700 --> 00:49:01,270 e cila është për të zgjidhur çdo gjysmën e grup dhe pastaj të bashkojë dy prej tyre. 595 00:49:04,960 --> 00:49:08,050 [Bowden] Mirë, kështu që jepni një të dytë. 596 00:49:10,850 --> 00:49:13,210 Unë mendoj se kjo - >> [Student] Unë kam nevojë për të - 597 00:49:17,100 --> 00:49:19,400 Po. Unë jam humbur diçka. 598 00:49:19,400 --> 00:49:23,100 Në bashkimin, e kuptoj se kam nevojë për të krijuar një grup të ri 599 00:49:23,100 --> 00:49:26,530 sepse unë nuk mund të bëjë atë në vend. Po >>. Ju nuk mundeni. Korrigjuar. 600 00:49:26,530 --> 00:49:28,170 [Student] Kështu që unë krijuar një koleksion të ri. 601 00:49:28,170 --> 00:49:31,510 I harruar në fund të bashkohen për të ri-ndryshuar. 602 00:49:31,510 --> 00:49:34,490 Rregull. Ne kemi nevojë për një koleksion të ri. 603 00:49:34,490 --> 00:49:41,000 Në lloj të bashkojë, kjo është pothuajse gjithmonë e vërtetë. 604 00:49:41,000 --> 00:49:44,340 Pjesë e kostos së një algoritmi të mirë kohë i mençur 605 00:49:44,340 --> 00:49:47,310 është pothuajse gjithmonë kanë nevojë për të përdorur memorie pak më shumë. 606 00:49:47,310 --> 00:49:51,570 Kështu që këtu, pa marrë parasysh se si ju bëni bashkojë lloj, 607 00:49:51,570 --> 00:49:54,780 ju do të duhet të përdorni në mënyrë të pashmangshme disa memorie ekstra. 608 00:49:54,780 --> 00:49:58,240 Ai ose ajo ka krijuar një koleksion të ri. 609 00:49:58,240 --> 00:50:03,400 Dhe pastaj ju thoni në fund, ne vetëm duhet të kopjoni koleksion të ri në rrjet origjinal. 610 00:50:03,400 --> 00:50:04,830 [Student] Unë mendoj kështu, yeah. 611 00:50:04,830 --> 00:50:08,210 Unë nuk e di nëse që punon në drejtim të numëruar duke iu referuar apo çfarëdo - 612 00:50:08,210 --> 00:50:11,650 Po, ajo do të punojë. >> [Student] Okay. 613 00:50:20,620 --> 00:50:24,480 A ju provoni drejtimin kjo? >> [Student] Jo, jo ende. Mirë >>. 614 00:50:24,480 --> 00:50:28,880 Provoni drejtimin e tij, dhe pastaj unë do të flas në lidhje me atë për një të dytë. 615 00:50:28,880 --> 00:50:35,200 [Student] Unë duhet të ketë të gjitha prototypes funksion dhe gjithçka, edhe pse, apo jo? 616 00:50:37,640 --> 00:50:40,840 Të prototypes funksion. Oh, ju do të thotë si - Po. 617 00:50:40,840 --> 00:50:43,040 Rendit është duke bërë thirrje mergeSortHelp. 618 00:50:43,040 --> 00:50:47,390 >> Pra, në mënyrë për të thirrur lloj mergeSortHelp, mergeSortHelp duhet ose janë përcaktuar 619 00:50:47,390 --> 00:50:56,370 para lloj ose ne duhet vetëm prototip. Thjesht kopjoni dhe ngjisni këtë. 620 00:50:56,370 --> 00:50:59,490 Dhe në mënyrë të ngjashme, mergeSortHelp është duke bërë thirrje shkrihen, 621 00:50:59,490 --> 00:51:03,830 por bashkojë nuk është përcaktuar ende, kështu që ne mund vetëm le mergeSortHelp e di 622 00:51:03,830 --> 00:51:08,700 se kjo është ajo që do të bashkojë të duken si, dhe kjo është se. 623 00:51:09,950 --> 00:51:15,730 Pra mergeSortHelp. 624 00:51:22,770 --> 00:51:32,660 Ne kemi një problem këtu ku kemi asnjë rast bazë. 625 00:51:32,660 --> 00:51:38,110 MergeSortHelp është recursive, kështu që çdo funksion recursive 626 00:51:38,110 --> 00:51:42,610 do të ketë nevojë për një lloj të rastit bazë të dinë se kur do të ndalet Recursively quan veten. 627 00:51:42,610 --> 00:51:45,590 Çfarë është rasti ynë bazë do të jetë këtu? Po. 628 00:51:45,590 --> 00:51:49,110 [Student] Nëse madhësia është 1? >> [Bowden] Po. 629 00:51:49,110 --> 00:51:56,220 Pra, si e pamë të drejtë atje, ne ndaluam vargjeve ndarjen 630 00:51:56,220 --> 00:52:01,850 sapo kemi marrë në vargjeve të madhësisë 1, i cili në mënyrë të pashmangshme janë të renditura veten. 631 00:52:01,850 --> 00:52:09,530 Pra, nëse madhësia e barabartë me 1, ne e dimë array është renditur tashmë, 632 00:52:09,530 --> 00:52:12,970 kështu që ne vetëm mund të kthehen. 633 00:52:12,970 --> 00:52:16,880 >> Vini re se kjo është e pavlefshme, kështu që ne nuk do të kthehen asgjë të veçantë, ne vetëm të kthehen. 634 00:52:16,880 --> 00:52:19,580 Rregull. Pra, kjo është rasti ynë bazë. 635 00:52:19,580 --> 00:52:27,440 I guess rastin tonë bazë mund të jetë edhe në qoftë se ne të ndodhë të bashkimit një rrjet të madhësisë 0, 636 00:52:27,440 --> 00:52:30,030 ne ndoshta doni të ndaluar në një pikë, 637 00:52:30,030 --> 00:52:33,610 kështu që ne mund të them vetëm madhësinë më pak se 2 ose më pak se ose e barabartë me 1 638 00:52:33,610 --> 00:52:37,150 kështu që kjo do të punojë për çdo grup tani. 639 00:52:37,150 --> 00:52:38,870 Rregull. 640 00:52:38,870 --> 00:52:42,740 Pra, kjo është rasti ynë bazë. 641 00:52:42,740 --> 00:52:45,950 Tani ju doni të ecni ne nëpërmjet bashkimin? 642 00:52:45,950 --> 00:52:49,140 Çfarë do të thotë të gjitha këto raste? 643 00:52:49,140 --> 00:52:54,480 Deri këtu, ne jemi vetëm duke bërë të njëjtën ide, - 644 00:52:56,970 --> 00:53:02,470 [Student] Unë duhet të kalojnë madhësinë me të gjitha thirrjet mergeSortHelp. 645 00:53:02,470 --> 00:53:10,080 Kam shtuar madhësinë si një paraprake shtesë dhe kjo nuk është atje, si madhësi / 2. 646 00:53:10,080 --> 00:53:16,210 [Bowden] Oh, madhësia / 2, madhësia / 2. >> [Student] Yeah, dhe gjithashtu në funksionin e mësipërm si. 647 00:53:16,210 --> 00:53:21,320 [Bowden] Ketu? >> [Student] Vetëm size. >> [Bowden] Oh. Size, madhësia? >> [Student] Yeah. 648 00:53:21,320 --> 00:53:23,010 [Bowden] Okay. 649 00:53:23,010 --> 00:53:26,580 Më lejoni të mendoj për një të dytë. 650 00:53:26,580 --> 00:53:28,780 A kemi drejtuar në një çështje? 651 00:53:28,780 --> 00:53:33,690 Ne jemi gjithmonë trajtimin e lënë si 0. >> [Student] Nr 652 00:53:33,690 --> 00:53:36,340 Kjo është gabim shumë. Më vjen keq. Ajo duhet të jetë fillimi. Po. 653 00:53:36,340 --> 00:53:39,230 [Bowden] Okay. Më pëlqen më mirë. 654 00:53:39,230 --> 00:53:43,880 Dhe në fund. Rregull. 655 00:53:43,880 --> 00:53:47,200 Kështu që tani ju doni të ecni ne nëpërmjet bashkimin? >> [Student] Okay. 656 00:53:47,200 --> 00:53:52,150 Unë jam vetëm duke ecur nëpër këtë grup të ri që unë kam krijuar. 657 00:53:52,150 --> 00:53:57,420 Madhësia e saj është madhësia e pjesës së grup që ne duam të jenë të renditura sipas 658 00:53:57,420 --> 00:54:03,460 dhe duke u përpjekur për të gjetur element që unë duhet të vënë në hapin array ri. 659 00:54:03,460 --> 00:54:10,140 Pra, për të bërë këtë, së pari unë jam duke kontrolluar nëse gjysma e majtë të array vazhdon të ketë elemente të ndonjë më shumë, 660 00:54:10,140 --> 00:54:14,260 dhe në qoftë se nuk e bën, atëherë ju shkoni poshtë në atë gjendje tjetër, i cili sapo thotë 661 00:54:14,260 --> 00:54:20,180 rregull, ajo duhet të jetë në rrjet të drejtë, dhe ne do të vendos se në indeksin aktual të newArray. 662 00:54:20,180 --> 00:54:27,620 >> Dhe pastaj ndryshe, unë jam duke kontrolluar nëse pala e drejta e array është përfunduar edhe, 663 00:54:27,620 --> 00:54:30,630 në të cilin rast unë vetëm vënë në të majtë. 664 00:54:30,630 --> 00:54:34,180 Kjo nuk mund të vërtetë të jetë e nevojshme. Nuk jam i sigurt. 665 00:54:34,180 --> 00:54:40,970 Por, gjithsesi, të tjera dy kontrolloni se cili prej dy janë më të vogla në të majtë apo të djathtë. 666 00:54:40,970 --> 00:54:49,770 Dhe në secilin rast, unë jam i bën rritjen cilado placeholder I ardhura. 667 00:54:49,770 --> 00:54:52,040 [Bowden] Okay. 668 00:54:52,040 --> 00:54:53,840 Që duket e mirë. 669 00:54:53,840 --> 00:54:58,800 Ka njeri të ketë komente ose pyetje ose shqetësime? 670 00:55:00,660 --> 00:55:07,720 Pra katër raste që kemi për të sjellë gjërat në vetëm duke qenë - ose ajo që duket si pesë - 671 00:55:07,720 --> 00:55:13,100 por ne duhet të marrin në konsideratë nëse array majtë është drejtuar nga gjërat që ne duhet të shkrihen, 672 00:55:13,100 --> 00:55:16,390 nëse array drejtë është drejtuar nga gjërat që ne duhet të bashkojë - 673 00:55:16,390 --> 00:55:18,400 Unë jam vënë në asgjë. 674 00:55:18,400 --> 00:55:21,730 Pra, nëse array majtë është drejtuar nga gjëra apo array drejtë është drejtuar nga gjëra. 675 00:55:21,730 --> 00:55:24,320 Këto janë dy raste. 676 00:55:24,320 --> 00:55:30,920 Ne gjithashtu duhet rastin parëndësishëm e nëse gjëja e majtë është më pak se gjëja e duhur. 677 00:55:30,920 --> 00:55:33,910 Atëherë ne duam të zgjedhin gjënë e majtë. 678 00:55:33,910 --> 00:55:37,630 Ata janë raste. 679 00:55:37,630 --> 00:55:40,990 Pra, kjo ishte e drejtë, kështu që kjo është ajo. 680 00:55:40,990 --> 00:55:46,760 Array majtë. Ajo është 1, 2, 3. Rregull. Pra, vërtet, këto janë katër gjëra që ne mund të dëshironi të bëni. 681 00:55:50,350 --> 00:55:54,510 Dhe ne nuk do të shkoj për një përsëritës zgjidhje. 682 00:55:54,510 --> 00:55:55,980 Unë nuk do të rekomandojë - 683 00:55:55,980 --> 00:56:03,070 Merge lloj është një shembull i një funksion që është edhe mos bisht rekursive, 684 00:56:03,070 --> 00:56:07,040 kjo nuk është e lehtë për ta bërë atë bisht rekursive, 685 00:56:07,040 --> 00:56:13,450 por edhe kjo nuk është shumë e lehtë për ta bërë atë përsëritës. 686 00:56:13,450 --> 00:56:16,910 Kjo është shumë e lehtë. 687 00:56:16,910 --> 00:56:19,170 Ky lloj zbatimi i bashkojë, 688 00:56:19,170 --> 00:56:22,140 bashkojë, pa marrë parasysh atë që ju bëni, ju do të jeni për të ndërtuar bashkohen. 689 00:56:22,140 --> 00:56:29,170 >> Pra bashkojë lloj ndërtuar në majë të bashkohen Recursively është vetëm këto tri linja. 690 00:56:29,170 --> 00:56:34,700 Iteratively, ajo është më shumë i bezdisshëm dhe më të vështirë për të menduar. 691 00:56:34,700 --> 00:56:41,860 Por vini re se kjo nuk është bishti rekursive që mergeSortHelp - kur e quan veten - 692 00:56:41,860 --> 00:56:46,590 ajo ende ka nevojë për të bërë gjëra, pasi ky kthim thirrjes gjithkund rekursive. 693 00:56:46,590 --> 00:56:50,830 Pra, kjo kornizë rafte duhet të vazhdojë të ekzistojë edhe pas kësaj thirrje. 694 00:56:50,830 --> 00:56:54,170 Dhe pastaj kur ju telefononi këtë, korniza rafte duhet të vazhdojë të ekzistojë 695 00:56:54,170 --> 00:56:57,780 sepse edhe pas kësaj telefonate, ne ende nevojë për të bashkojë. 696 00:56:57,780 --> 00:57:01,920 Dhe kjo është jo banale për të bërë këtë bisht rekursive. 697 00:57:04,070 --> 00:57:06,270 Pyetje? 698 00:57:08,300 --> 00:57:09,860 Dakord. 699 00:57:09,860 --> 00:57:13,400 Pra, duke shkuar prapa për të zgjidhur - oh, ka dy gjëra që unë dua për të treguar. Rregull. 700 00:57:13,400 --> 00:57:17,840 Going back to lloj, ne do të bëjmë këtë shpejt. 701 00:57:17,840 --> 00:57:21,030 Ose search. Rendit? Rendit. Po. 702 00:57:21,030 --> 00:57:22,730 Going back to fillimet e lloji. 703 00:57:22,730 --> 00:57:29,870 Ne duam të krijojmë një algoritmi që llojet rrjet duke përdorur ndonjë algorithm 704 00:57:29,870 --> 00:57:33,660 O në të n. 705 00:57:33,660 --> 00:57:40,860 Pra, si është kjo e mundur? A ka dikush ndonjë lloj - 706 00:57:40,860 --> 00:57:44,300 I la të kuptohej më parë në - 707 00:57:44,300 --> 00:57:48,300 Nëse ne jemi gati për të përmirësuar nga n log n për O n, 708 00:57:48,300 --> 00:57:51,450 ne kemi përmirësuar algorithm tonë kohë i mençur, 709 00:57:51,450 --> 00:57:55,250 që do të thotë se çfarë jemi ne do të duhet të bëni për të bërë për këtë? 710 00:57:55,250 --> 00:57:59,520 [Student] hapësirë. Po >>. Ne jemi duke shkuar për të përdorur më shumë hapësirë. 711 00:57:59,520 --> 00:58:04,490 Dhe jo edhe vetëm më shumë hapësirë, kjo është hapësirë ​​në mënyrë eksponenciale më shumë. 712 00:58:04,490 --> 00:58:14,320 Kështu që unë mendoj se kjo lloj algoritmi është diçka pseudo, pseudo polynom - 713 00:58:14,320 --> 00:58:18,980 pseudo - Unë nuk mund të kujtohet. Diçka pseudo. 714 00:58:18,980 --> 00:58:22,210 Por kjo është për shkak se ne kemi nevojë që të përdorin hapësirën aq shumë 715 00:58:22,210 --> 00:58:28,610 se kjo është e arritshme, por jo realiste. 716 00:58:28,610 --> 00:58:31,220 >> Dhe si nuk kemi arritur këtë? 717 00:58:31,220 --> 00:58:36,810 Ne mund të arrijmë këtë nëse kemi të garantuar se çdo element i veçantë në rrjet 718 00:58:36,810 --> 00:58:39,600 është nën një madhësi të caktuar. 719 00:58:42,070 --> 00:58:44,500 Pra, le të them vetëm se madhësia është 200, 720 00:58:44,500 --> 00:58:48,130 çdo element në një grup është nën madhësia 200. 721 00:58:48,130 --> 00:58:51,080 Dhe kjo në fakt është shumë realiste. 722 00:58:51,080 --> 00:58:58,660 Ju mund shumë lehtë të ketë një rrjet që ju e dini çdo gjë në të 723 00:58:58,660 --> 00:59:00,570 do të jetë më pak se një numër. 724 00:59:00,570 --> 00:59:07,400 Ashtu si në qoftë se ju keni disa vektor absolutisht masiv apo diçka 725 00:59:07,400 --> 00:59:11,810 por ju e dini çdo gjë do të jetë midis 0 dhe 5, 726 00:59:11,810 --> 00:59:14,790 atëherë ajo do të jetë dukshëm më të shpejtë për të bërë këtë. 727 00:59:14,790 --> 00:59:17,930 Dhe lidhur në ndonjë prej elementeve është 5, 728 00:59:17,930 --> 00:59:21,980 kështu që kjo detyruar, që është sa memorie ju jeni do të jetë duke përdorur. 729 00:59:21,980 --> 00:59:26,300 Pra detyruar është 200. 730 00:59:26,300 --> 00:59:32,960 Në teori nuk është gjithmonë një i detyruar që një numër i plotë mund të jetë vetëm deri në 4 miliardë, 731 00:59:32,960 --> 00:59:40,600 por kjo është joreale që atëherë ne do të jetë duke përdorur hapësirë 732 00:59:40,600 --> 00:59:44,400 në mënyrë të 4 miliardë. Pra, kjo është joreale. 733 00:59:44,400 --> 00:59:47,060 Por këtu ne do të themi lidhur ynë është 200. 734 00:59:47,060 --> 00:59:59,570 Mashtrim për të bërë atë në të O n është që ne të bëjë një tjetër grup të quajtur akuza të madhësisë lidhur. 735 00:59:59,570 --> 01:00:10,470 Pra në fakt, kjo është një shkurtore për - Unë në fakt nuk e di nëse tingëllimë e bën këtë. 736 01:00:11,150 --> 01:00:15,330 Por në GCC, në shumë pak - tingëllimë Jam duke supozuar e bën atë shumë - 737 01:00:15,330 --> 01:00:18,180 kjo thjesht do të nisja array gjithë të jenë 0s. 738 01:00:18,180 --> 01:00:25,320 Pra, nëse unë nuk dua të bëj këtë, atëherë unë mund të bëj për vete (int i = 0; 739 01:00:25,320 --> 01:00:31,500 i 01:00:35,260 Deri tani çdo gjë është nisur në 0. 741 01:00:35,260 --> 01:00:39,570 Unë iterate mbi array tim, 742 01:00:39,570 --> 01:00:51,920 dhe atë që unë jam duke bërë është që unë jam duke numëruar numrin e njëri - Le të shkojnë poshtë këtu. 743 01:00:51,920 --> 01:00:55,480 Ne kemi 4, 15, 16, 50, 8, 23, 42, 108. 744 01:00:55,480 --> 01:01:00,010 Ajo që unë jam duke numëruar është numri i dukurive të secilit prej këtyre elementeve. 745 01:01:00,010 --> 01:01:03,470 Le të vërtetë të shtoni një çift shumë në këtu me disa përsërit. 746 01:01:03,470 --> 01:01:11,070 Pra, vlera e kemi këtu, vlera e që do të jetë array [i]. 747 01:01:11,070 --> 01:01:14,850 Pra, mund të jetë val 4 apo 8 apo çfarëdo. 748 01:01:14,850 --> 01:01:18,870 Dhe tani unë jam duke numëruar se sa i atij vlerën që unë kam parë, 749 01:01:18,870 --> 01:01:21,230 kështu akuza [val] + +; 750 01:01:21,230 --> 01:01:29,430 Pas kësaj është bërë, akuza do të shikojmë diçka si 0001. 751 01:01:29,430 --> 01:01:42,190 Le të bëjmë akuza [val] - BOUND + 1. 752 01:01:42,190 --> 01:01:48,230 >> Tani që është vetëm për të llogari për faktin se ne jemi duke filluar nga 0. 753 01:01:48,230 --> 01:01:50,850 Pra, nëse 200 do të jetë numri ynë më i madh, 754 01:01:50,850 --> 01:01:54,720 pastaj 0-200 është 201 gjëra. 755 01:01:54,720 --> 01:02:01,540 Pra akuza, ajo do të duket si 00.001, sepse ne kemi një 4. 756 01:02:01,540 --> 01:02:10,210 Atëherë ne do të kemi 0001 ku ne do të kemi një 1 në indeksin e 8 e numërimit. 757 01:02:10,210 --> 01:02:14,560 Ne do të kemi një 2 në indeksin e 23-të numërimit. 758 01:02:14,560 --> 01:02:17,630 Ne do të kemi një 2 në indeksin e 42-numërimin. 759 01:02:17,630 --> 01:02:21,670 Kështu që ne mund të përdorni numërimin. 760 01:02:34,270 --> 01:02:44,920 Pra num_of_item = numëron [i]. 761 01:02:44,920 --> 01:02:52,540 Dhe kështu që nëse num_of_item është 2, që do të thotë që ne duam të futur 2 e numrit i 762 01:02:52,540 --> 01:02:55,290 në grup tonë të renditura. 763 01:02:55,290 --> 01:03:02,000 Pra, ne kemi nevojë për të mbajtur gjurmët e sa larg jemi në grup. 764 01:03:02,000 --> 01:03:05,470 Pra, indeksi = 0. 765 01:03:05,470 --> 01:03:09,910 Array - Unë vetëm do të shkruaj atë. 766 01:03:16,660 --> 01:03:18,020 Pikat - 767 01:03:19,990 --> 01:03:28,580 array [Indeksi + +] = i; 768 01:03:28,580 --> 01:03:32,490 Është se ajo që unë dua? Unë mendoj se kjo është ajo që unë dua. 769 01:03:35,100 --> 01:03:38,290 Po, kjo duket e mirë. Rregull. 770 01:03:38,290 --> 01:03:43,050 Pra, ka të gjithë e kuptojnë se çfarë qëllimi i im është akuza grup? 771 01:03:43,050 --> 01:03:48,140 Ajo është duke numëruar numrin e dukurive të secilit prej këtyre numrave. 772 01:03:48,140 --> 01:03:51,780 Atëherë unë jam iterating mbi këtë koleksion akuza, 773 01:03:51,780 --> 01:03:57,190 dhe pozita ith në rrjet akuza 774 01:03:57,190 --> 01:04:01,930 është numri i kam e që duhet të paraqiten në grup tim renditura. 775 01:04:01,930 --> 01:04:06,840 Kjo është arsyeja pse akuza e 4 do të jetë 1 776 01:04:06,840 --> 01:04:11,840 dhe akuza të 8 do të jetë 1, akuza për 23 do të jetë 2. 777 01:04:11,840 --> 01:04:16,900 Pra, kjo është se si shumë prej tyre unë dua për të futur në rrjet tim renditura. 778 01:04:16,900 --> 01:04:19,200 Atëherë unë vetëm të bëjë këtë. 779 01:04:19,200 --> 01:04:28,960 Unë jam futur num_of_item unë është në rrjet tim renditura. 780 01:04:28,960 --> 01:04:31,670 >> Pyetje? 781 01:04:32,460 --> 01:04:43,100 Dhe kështu përsëri, kjo është koha lineare pasi ne jemi vetëm iterating mbi këtë herë, 782 01:04:43,100 --> 01:04:47,470 por gjithashtu edhe në atë linear ky numër ndodh që të jetë, 783 01:04:47,470 --> 01:04:50,730 dhe kështu që shumë varet nga ajo detyruar juaj. 784 01:04:50,730 --> 01:04:53,290 Me një kufi të 200, që nuk është edhe aq keq. 785 01:04:53,290 --> 01:04:58,330 Nëse detyruar juaj do të jetë 10.000, atëherë kjo është pak keq, 786 01:04:58,330 --> 01:05:01,360 por në qoftë se lidhur juaj do të jetë 4 miliardë dollarë, që është tërësisht joreale 787 01:05:01,360 --> 01:05:07,720 dhe ky grup do të duhet të jetë e madhësisë 4 miliardë, e cila është joreale. 788 01:05:07,720 --> 01:05:10,860 Pra, kjo është se. Pyetje? 789 01:05:10,860 --> 01:05:13,270 [Përgjigja e padëgjueshme Student] >> Okay. 790 01:05:13,270 --> 01:05:15,710 Kam kuptuar një gjë tjetër, kur ne ishim duke kaluar. 791 01:05:17,980 --> 01:05:23,720 Unë mendoj se problemi ishte në të Lukas dhe ndoshta çdo një të vetme kemi parë. 792 01:05:23,720 --> 01:05:26,330 Unë plotësisht harruar. 793 01:05:26,330 --> 01:05:31,040 E vetmja gjë që kam kërkuar për të komentuar në është se kur ju jeni që kanë të bëjnë me gjëra të tilla si indekse, 794 01:05:31,040 --> 01:05:38,320 ju kurrë nuk e shohin këtë të vërtetë, kur ju jeni duke shkruar një për lak, 795 01:05:38,320 --> 01:05:41,120 por teknikisht, kur ju jeni që kanë të bëjnë me këto indekse, 796 01:05:41,120 --> 01:05:45,950 ju duhet të pretty much gjithmonë të merren me integers panënshkruara. 797 01:05:45,950 --> 01:05:53,850 Arsyeja për këtë është kur ju jeni që kanë të bëjnë me integers nënshkruara, 798 01:05:53,850 --> 01:05:56,090 kështu që nëse ju keni 2 integers nënshkruar dhe ju shtoni ato së bashku 799 01:05:56,090 --> 01:06:00,640 dhe ata përfundojnë shumë i madh, atëherë ju përfundojnë me një numër negativ. 800 01:06:00,640 --> 01:06:03,410 Pra, kjo është ajo që del nga shtrati është numër i plotë. 801 01:06:03,410 --> 01:06:10,500 >> Nëse unë shtoni 2000000000 dhe 1000000000, unë deri në fund me 1 miliard negativ. 802 01:06:10,500 --> 01:06:15,480 Kjo është se si integers punojnë në kompjuter. 803 01:06:15,480 --> 01:06:17,510 Pra, problemi me përdorimin e - 804 01:06:17,510 --> 01:06:23,500 Kjo është në rregull, përveç nëse ndodh të jetë i ulët 2 miliardë dhe deri ndodh të jetë 1 miliard, 805 01:06:23,500 --> 01:06:27,120 atëherë kjo do të jetë 1 miliard negative dhe pastaj ne jemi duke shkuar për të ndarë që nga 2 806 01:06:27,120 --> 01:06:29,730 dhe përfundojnë me 500 milionë negativ. 807 01:06:29,730 --> 01:06:33,760 Pra, kjo është vetëm një çështje, nëse ju ndodh që të jetë në kërkim përmes një sërë 808 01:06:33,760 --> 01:06:38,070 prej miliarda gjërave. 809 01:06:38,070 --> 01:06:44,050 Por nëse ndodh + ulët deri të fryhen, atëherë kjo është një problem. 810 01:06:44,050 --> 01:06:47,750 Sapo kemi bërë ato unsigned, pastaj 2 miliardë plus 1 miliard është 3 miliard dollarë. 811 01:06:47,750 --> 01:06:51,960 3 miliardë ndarë nga 2 është 1.5 miliard dollarë. 812 01:06:51,960 --> 01:06:55,670 Pra, sa më shpejt që ata janë të panënshkruara, çdo gjë është e përsosur. 813 01:06:55,670 --> 01:06:59,900 Dhe kështu kjo është gjithashtu një çështje kur ju jeni shkrim tuaja për sythe, 814 01:06:59,900 --> 01:07:03,940 dhe në fakt, kjo ndoshta e bën atë automatikisht. 815 01:07:09,130 --> 01:07:12,330 Kjo në fakt do vetëm bërtasin në ju. 816 01:07:12,330 --> 01:07:21,610 Pra, nëse ky numër është shumë e madhe që të jetë në një numër të plotë vetëm, por kjo do të përshtatet në një numër të plotë panënshkruar, 817 01:07:21,610 --> 01:07:24,970 ajo do të bërtas me ju, kështu që kjo është arsyeja pse nuk ju drejtuar të vërtetë në këtë çështje. 818 01:07:29,150 --> 01:07:34,820 Ju mund të shihni se një indeks kurrë nuk do të jetë negative, 819 01:07:34,820 --> 01:07:39,220 dhe kështu kur ju jeni iterating mbi një rrjet, 820 01:07:39,220 --> 01:07:43,970 ju mund të pothuajse gjithmonë thonë unsigned int i, por ju nuk duhet të vërtetë kanë për të. 821 01:07:43,970 --> 01:07:47,110 Gjërat po shkojnë të punojnë goxha shumë po aq mirë. 822 01:07:48,740 --> 01:07:50,090 Rregull. [Pëshpërit] Sa është ora? 823 01:07:50,090 --> 01:07:54,020 Gjëja e fundit që kam kërkuar për të treguar - dhe unë vetëm do të bëjë atë me të vërtetë të shpejtë. 824 01:07:54,020 --> 01:08:03,190 Ju e dini se si ne kemi # define kështu që ne mund të përcaktojë # MAX si 5 apo diçka? 825 01:08:03,190 --> 01:08:05,940 Le të mos bëjmë MAX. # Define obligohemi si 200. Kjo është ajo që ne e bëmë më parë. 826 01:08:05,940 --> 01:08:10,380 Që përcakton një konstante, e cila është vetëm do të kopjohet dhe ngjit 827 01:08:10,380 --> 01:08:13,010 kudo që të ndodhë për të shkruar lidhur. 828 01:08:13,010 --> 01:08:18,189 >> Pra, ne në fakt mund të bëjë më shumë me # përcakton. 829 01:08:18,189 --> 01:08:21,170 Ne mund të përcaktojë funksionet #. 830 01:08:21,170 --> 01:08:23,410 Ata nuk janë me të vërtetë funksionon, por ne do të thërrasë ato funksione. 831 01:08:23,410 --> 01:08:36,000 Një shembull do të jetë diçka si MAX (x, y) është definuar si (x 01:08:40,660 Kështu që ju duhet të merrni përdorur për të sintaksës operator tresh, 833 01:08:40,660 --> 01:08:49,029 por është më pak se x y? Kthehu y, x kthehen tjetër. 834 01:08:49,029 --> 01:08:54,390 Kështu që ju mund të shihni që ju mund të bëni këtë një funksion të veçantë, 835 01:08:54,390 --> 01:09:01,399 dhe funksioni mund të jetë si bool MAX merr 2 argumente, kthehet këtë. 836 01:09:01,399 --> 01:09:08,340 Kjo është një nga ato më të zakonshme unë shoh bërë si kjo. Ne i quajmë ato macros. 837 01:09:08,340 --> 01:09:11,790 Kjo është një makro. 838 01:09:11,790 --> 01:09:15,859 Kjo është vetëm sintaksë për të. 839 01:09:15,859 --> 01:09:18,740 Ju mund të shkruani një makro për të bërë çdo gjë që ju dëshironi. 840 01:09:18,740 --> 01:09:22,649 Ju shpesh shohim macros për debugging printfs dhe sende. 841 01:09:22,649 --> 01:09:29,410 Pra, një lloj i printf, nuk janë konstante të veçanta në C si underscore LINE nënvizojnë, 842 01:09:29,410 --> 01:09:31,710 2 nënvizon LINE nënvizojnë, 843 01:09:31,710 --> 01:09:37,550 dhe ka edhe mendoj 2 nënvizon funk. Kjo mund të jetë ajo. Diçka të tillë. 844 01:09:37,550 --> 01:09:40,880 Këto gjëra do të zëvendësohet me emrin e funksionit 845 01:09:40,880 --> 01:09:42,930 ose numrin e linjës që ju jeni në. 846 01:09:42,930 --> 01:09:48,630 Shpesh, ju shkruani printfs debugging që këtu poshtë atëherë unë mund të shkruani vetëm 847 01:09:48,630 --> 01:09:54,260 Korrigjoj dhe ajo do të shtypura numrin e linjës dhe funksionin që unë të ndodhë të jetë në 848 01:09:54,260 --> 01:09:57,020 se ajo ka hasur atë deklaratë korrigjoj. 849 01:09:57,020 --> 01:09:59,550 Dhe ju gjithashtu mund të shkruar gjëra të tjera. 850 01:09:59,550 --> 01:10:05,990 Pra, një gjë që ju duhet të shikojnë për të është në qoftë se unë të ndodhë për # define DOUBLE_MAX 851 01:10:05,990 --> 01:10:11,380 si diçka si 2 * y dhe 2 * x. 852 01:10:11,380 --> 01:10:14,310 Pra, për arsye çfarëdo, ju ndodh për ta bërë këtë shumë. 853 01:10:14,310 --> 01:10:16,650 Kështu që e bëjnë atë një makro. 854 01:10:16,650 --> 01:10:18,680 Kjo është thyer në të vërtetë. 855 01:10:18,680 --> 01:10:23,050 Unë do ta quaja atë duke bërë diçka të tillë DOUBLE_MAX (3, 6). 856 01:10:23,050 --> 01:10:27,530 Pra, çfarë duhet të kthehen? 857 01:10:28,840 --> 01:10:30,580 [Student] 12. 858 01:10:30,580 --> 01:10:34,800 Po, 12 duhet të kthehen, dhe 12 është kthyer. 859 01:10:34,800 --> 01:10:43,350 3 merr zëvendësohet për x, 6 merr zëvendësohet për y, dhe ne kthim 2 * 6, e cila është 12. 860 01:10:43,350 --> 01:10:47,710 Tani çfarë në lidhje me këtë? Çfarë duhet të kthehen? 861 01:10:47,710 --> 01:10:50,330 [Student] 14. Idealisht >>, 14. 862 01:10:50,330 --> 01:10:55,290 Çështja është se si hash përcakton punën, mos harroni se kjo është një kopje e saktë dhe paste 863 01:10:55,290 --> 01:11:00,160 çdo gjë shumë e shumë, kështu që çfarë kjo do të interpretohet si 864 01:11:00,160 --> 01:11:11,270 është 3 më pak se 1 plus 6, 2 herë 1 plus 6, 2 herë 3. 865 01:11:11,270 --> 01:11:19,780 >> Pra, për këtë arsye ju pothuajse gjithmonë të përfundojë çdo gjë në kllapa. 866 01:11:22,180 --> 01:11:25,050 Çdo ndryshore ju pothuajse gjithmonë të përfundojë në kllapa. 867 01:11:25,050 --> 01:11:29,570 Ka raste ku ju nuk keni për të, ashtu si unë e di se unë nuk duhet të bëni se këtu 868 01:11:29,570 --> 01:11:32,110 sepse më pak se është shumë e shumë të gjithmonë vetëm të shkojnë në punë, 869 01:11:32,110 --> 01:11:34,330 edhe pse kjo mund të mos jetë edhe e vërtetë. 870 01:11:34,330 --> 01:11:41,870 Nëse ka diçka qesharake si DOUBLE_MAX (1 == 2), 871 01:11:41,870 --> 01:11:49,760 atëherë kjo do të merrni zëvendësohet me 3 më pak se 1 barabartë barabartë me 2, 872 01:11:49,760 --> 01:11:53,460 dhe kështu, atëherë kjo do të bëjë 3 më pak se 1, bën që 2 të barabartë, 873 01:11:53,460 --> 01:11:55,620 e cila nuk është ajo që ne duam. 874 01:11:55,620 --> 01:12:00,730 Kështu që në mënyrë për të parandaluar ndonjë problem operatorit përparësi, 875 01:12:00,730 --> 01:12:02,870 gjithmonë të përfundojë në kllapa. 876 01:12:03,290 --> 01:12:07,700 Rregull. Dhe kjo është ajo, 05:30. 877 01:12:08,140 --> 01:12:12,470 Nëse keni ndonjë pyetje në pset, le të na njohin. 878 01:12:12,470 --> 01:12:18,010 Ajo duhet të jetë kënaqësi, dhe edicioni hacker gjithashtu është shumë më realiste 879 01:12:18,010 --> 01:12:22,980 se edicionin e hacker të vitit të kaluar, kështu që ne shpresojmë se shumë prej jush të përpiqen atë. 880 01:12:22,980 --> 01:12:26,460 Vitin e kaluar ishte shumë e madhe. 881 01:12:28,370 --> 01:12:30,000 >> [CS50.TV]