1 00:00:00,000 --> 00:00:05,830 2 00:00:05,830 --> 00:00:07,910 >> Tout dwa, se konsa, enfòmatik konpleksite. 3 00:00:07,910 --> 00:00:10,430 Jis yon ti jan nan yon avètisman anvan nou plonje nan twò far-- 4 00:00:10,430 --> 00:00:13,070 sa a ap pwobableman dwe nan mitan bagay ki pi matematik-lou 5 00:00:13,070 --> 00:00:14,200 nou pale sou nan CS50. 6 00:00:14,200 --> 00:00:16,950 Nou swete ke li pa pral twò akablan epi n ap eseye ak gide ou 7 00:00:16,950 --> 00:00:19,200 atravè tout pwosesis la, men jis yon ti jan nan yon avètisman ki jis. 8 00:00:19,200 --> 00:00:21,282 Genyen yon ti jan nan matematik ki enplike isit la. 9 00:00:21,282 --> 00:00:23,990 Tout dwa, se konsa nan lòd fè pou sèvi ak resous enfòmatik nou an 10 00:00:23,990 --> 00:00:28,170 nan world-- nan byen li vrèman enpòtan ke ou konprann algoritm 11 00:00:28,170 --> 00:00:30,750 ak ki jan yo travay sou done. 12 00:00:30,750 --> 00:00:32,810 Si nou gen yon reyèlman algorithm efikas, nou 13 00:00:32,810 --> 00:00:36,292 kapab minimize kantite lajan an nan resous nou genyen disponib fè fas ak li. 14 00:00:36,292 --> 00:00:38,750 Si nou gen yon algorithm ki se pral pran yon anpil nan travay 15 00:00:38,750 --> 00:00:41,210 nan pwosesis yon vrèman gwo ansanm done, li la 16 00:00:41,210 --> 00:00:44,030 ale nan mande pou plis ak plis resous, ki 17 00:00:44,030 --> 00:00:47,980 se lajan, RAM, tout sa ki kalite bagay. 18 00:00:47,980 --> 00:00:52,090 >> Se konsa, ke yo te kapab analize yon algorithm lè l sèvi avèk sa a seri zouti, 19 00:00:52,090 --> 00:00:56,110 fondamantalman, mande question-- nan ki jan fè sa a algorithm echèl 20 00:00:56,110 --> 00:00:59,020 jan nou voye jete pi plis ak plis done nan li? 21 00:00:59,020 --> 00:01:02,220 Nan CS50, kantite lajan an nan done nou ap travay ak se trè piti. 22 00:01:02,220 --> 00:01:05,140 Anjeneral, pwogram nou yo ale nan kouri nan yon dezyèm oswa yon less-- 23 00:01:05,140 --> 00:01:07,830 pwobableman yon anpil mwens patikilyèman byen bonè nan. 24 00:01:07,830 --> 00:01:12,250 >> Men, panse osijè de yon konpayi ki kontra ak dè santèn de dè milyon de kliyan yo. 25 00:01:12,250 --> 00:01:14,970 Apre sa, yo bezwen nan pwosesis ke kliyan done. 26 00:01:14,970 --> 00:01:18,260 Kòm kantite kliyan yo gen vin pi gwo ak pi gwo, 27 00:01:18,260 --> 00:01:21,230 li k ap pase yo mande pou pi plis ak plis resous. 28 00:01:21,230 --> 00:01:22,926 Konbyen plis resous? 29 00:01:22,926 --> 00:01:25,050 Oke, ki depann sou ki jan nou analize algorithm a, 30 00:01:25,050 --> 00:01:28,097 lè l sèvi avèk zouti yo nan bwat zouti sa a. 31 00:01:28,097 --> 00:01:31,180 Lè nou pale sou konpleksite a nan yon algorithm ki pafwa ou pral 32 00:01:31,180 --> 00:01:34,040 tande l 'refere yo kòm tan konpleksite oswa espas konpleksite 33 00:01:34,040 --> 00:01:36,190 men nou ap jis ale yo rele complexity-- 34 00:01:36,190 --> 00:01:38,770 nou ap jeneralman pale de pi move-ka senaryo a. 35 00:01:38,770 --> 00:01:42,640 Bay absoli pil la pi mal la nan done ke nou te kapab voye nan li, 36 00:01:42,640 --> 00:01:46,440 ki jan se sa a algorithm pral travay oswa fè fas ak ke done? 37 00:01:46,440 --> 00:01:51,450 Nou jeneralman rele pi move-ka a ègzekutabl nan yon algorithm gwo-O. 38 00:01:51,450 --> 00:01:56,770 Se konsa, ta ka yon algorithm dwe di kouri nan O nan n oswa O nan n okib. 39 00:01:56,770 --> 00:01:59,110 Ak plis ankò sou sa moun vle di nan yon dezyèm fwa. 40 00:01:59,110 --> 00:02:01,620 >> Pafwa, menm si, nou fè swen sou senaryo a pi byen ki ka. 41 00:02:01,620 --> 00:02:05,400 Si done a se tout sa nou te vle li nan dwe epi li te absoliman pafè 42 00:02:05,400 --> 00:02:09,630 epi nou te voye sa a pafè mete nan done nan algorithm nou an. 43 00:02:09,630 --> 00:02:11,470 Ki jan li ta okipe nan ki sitiyasyon? 44 00:02:11,470 --> 00:02:15,050 Nou pafwa, al gade nan ke kòm gwo-Omega, se konsa nan kontra ak gwo-O, 45 00:02:15,050 --> 00:02:16,530 nou gen gwo-Omega. 46 00:02:16,530 --> 00:02:18,880 Big-Omega pou senaryo a pi byen ki ka. 47 00:02:18,880 --> 00:02:21,319 Big-O pou senaryo ki pi mal la-ka. 48 00:02:21,319 --> 00:02:23,860 Anjeneral, lè nou pale sou konpleksite nan yon algorithm, 49 00:02:23,860 --> 00:02:26,370 n ap pale a pi move-ka senaryo. 50 00:02:26,370 --> 00:02:28,100 Se konsa, kenbe sa nan tèt ou. 51 00:02:28,100 --> 00:02:31,510 >> Ak nan klas sa a, nou ap jeneralman ale yo kite analiz la solid sou kote. 52 00:02:31,510 --> 00:02:35,350 Gen syans ak lòt jaden konsakre nan sa a kalite bagay. 53 00:02:35,350 --> 00:02:37,610 Lè nou pale sou rezònman a algoritm, 54 00:02:37,610 --> 00:02:41,822 ki nou pral fè moso-pa-moso pou anpil algoritm nou pale sou nan klas la. 55 00:02:41,822 --> 00:02:44,780 Nou ap vrèman jis ap pale de rezònman nan li ak sans komen, 56 00:02:44,780 --> 00:02:47,070 pa avèk fòmil, oswa prèv, oswa yon bagay tankou sa. 57 00:02:47,070 --> 00:02:51,600 Se konsa, pa enkyete w, Nou pa pral vire nan yon klas matematik gwo. 58 00:02:51,600 --> 00:02:55,920 >> Se konsa, mwen te di nou pran swen sou konpleksite paske li mande kesyon an, ki jan 59 00:02:55,920 --> 00:03:00,160 algoritm nou an okipe pi gwo ak pi gwo kouche done ke yo te voye jete nan yo. 60 00:03:00,160 --> 00:03:01,960 Oke, sa se yon seri done? 61 00:03:01,960 --> 00:03:03,910 Ki sa mwen vle di lè m 'te di ke? 62 00:03:03,910 --> 00:03:07,600 Sa vle di tou sa fè pi plis nan sans nan yon kontèks, yo dwe onèt. 63 00:03:07,600 --> 00:03:11,160 Si nou gen yon algorithm a, Pwosesis strings nou ap pwobableman 64 00:03:11,160 --> 00:03:13,440 ap pale de gwosè a nan fisèl la. 65 00:03:13,440 --> 00:03:15,190 Sa a done yo set-- gwosè a, nimewo a 66 00:03:15,190 --> 00:03:17,050 nan karaktè ki fè moute fisèl la. 67 00:03:17,050 --> 00:03:20,090 Si nou ap pale sou yon algorithm ki trete dosye, 68 00:03:20,090 --> 00:03:23,930 nou ta ka dwe pale sou ki jan anpil kilookte genyen ki dosye-a. 69 00:03:23,930 --> 00:03:25,710 Epi sa a, mete nan done. 70 00:03:25,710 --> 00:03:28,870 Si nou ap pale de yon algorithm ki okipe zafè ranje plis jeneralman, 71 00:03:28,870 --> 00:03:31,510 tankou klasman algoritm oswa chèche algoritm, 72 00:03:31,510 --> 00:03:36,690 nou ap pwobableman ap pale de nimewo a nan eleman ki genyen yon etalaj. 73 00:03:36,690 --> 00:03:39,272 >> Koulye a, nou ka mezire yon algorithm an patikilye, 74 00:03:39,272 --> 00:03:40,980 lè m 'di sa nou kapab mezire yon algorithm, mwen 75 00:03:40,980 --> 00:03:43,840 vle di nou ka mezire ki anpil resous li pran yo. 76 00:03:43,840 --> 00:03:48,990 Si resous sa yo se, ki jan anpil bytes nan RAM-- oswa megabit nan RAM 77 00:03:48,990 --> 00:03:49,790 li itilize. 78 00:03:49,790 --> 00:03:52,320 Ou konbyen tan li pran yo kouri. 79 00:03:52,320 --> 00:03:56,200 Apre sa, nou ka rele sa a mezire, abitrèman, f nan n. 80 00:03:56,200 --> 00:03:59,420 Ki kote n se nimewo a nan eleman nan ansanm done a. 81 00:03:59,420 --> 00:04:02,640 Apre sa, f nan n se ki jan anpil nouvote. 82 00:04:02,640 --> 00:04:07,530 Konbyen inite nan resous fè li mande pou nan pwosesis ki done. 83 00:04:07,530 --> 00:04:10,030 >> Koulye a, nou aktyèlman pa pran swen sou sa ki f nan n se egzakteman. 84 00:04:10,030 --> 00:04:13,700 An reyalite, nou trè raman will-- sètènman pral pa janm nan sa a mwen class-- 85 00:04:13,700 --> 00:04:18,709 plonje nan gwo twou san fon vrèman nenpòt analiz de sa f nan n se. 86 00:04:18,709 --> 00:04:23,510 Nou ap jis ale nan pale sou sa f nan n se apeprè oswa ki sa li gen tandans fè. 87 00:04:23,510 --> 00:04:27,600 Apre sa, tandans a nan yon algorithm se dikte nan tèm pi wo lòd li yo. 88 00:04:27,600 --> 00:04:29,440 Apre sa, nou ka wè ki sa mwen vle di pa ki lè yo pran 89 00:04:29,440 --> 00:04:31,910 yon gade nan yon egzanp plis konkrè. 90 00:04:31,910 --> 00:04:34,620 >> Se konsa nou di ke nou gen twa algoritm diferan. 91 00:04:34,620 --> 00:04:39,350 Premye a nan ki te pran n Gleason, gen kèk inite nan resous 92 00:04:39,350 --> 00:04:42,880 nan pwosesis yon seri done nan gwosè n. 93 00:04:42,880 --> 00:04:47,000 Nou gen yon algorithm dezyèm ki pran n Gleason plis n okib resous 94 00:04:47,000 --> 00:04:49,350 nan pwosesis yon seri done nan gwosè n. 95 00:04:49,350 --> 00:04:52,030 Epi nou gen yon twazyèm algorithm ki kouri in-- ki 96 00:04:52,030 --> 00:04:58,300 pran moute n Gleason mwens 8n okib plis 20 N inite nan resous 97 00:04:58,300 --> 00:05:02,370 nan pwosesis yon algorithm ak done mete nan gwosè n. 98 00:05:02,370 --> 00:05:05,594 >> Koulye a, ankò, nou reyèlman pa pral jwenn nan nivo sa a nan detay. 99 00:05:05,594 --> 00:05:08,260 Mwen vrèman jis gen sa yo moute isit la tankou yon demonstrasyon pou montre yon pwen 100 00:05:08,260 --> 00:05:10,176 ke mwen pral yo dwe fè nan yon dezyèm lan, ki 101 00:05:10,176 --> 00:05:12,980 se ke nou sèlman reyèlman sousye sou tandans nan de bagay sa yo 102 00:05:12,980 --> 00:05:14,870 kòm ansanm sa yo, done jwenn pi gran. 103 00:05:14,870 --> 00:05:18,220 Se konsa, si ansanm done a se piti, gen nan aktyèlman yon bèl gwo diferans 104 00:05:18,220 --> 00:05:19,870 nan algoritm sa yo. 105 00:05:19,870 --> 00:05:23,000 Algorithm nan twazyèm gen pran 13 fwa pi long, 106 00:05:23,000 --> 00:05:27,980 13 fwa kantite lajan an nan resous nan kouri relatif nan yon sèl la an premye. 107 00:05:27,980 --> 00:05:31,659 >> Si nou an seri done se gwosè 10, ki se pi gwo, men se pa nesesèman gwo, 108 00:05:31,659 --> 00:05:33,950 nou ka wè ke gen nan aktyèlman yon ti jan nan yon diferans. 109 00:05:33,950 --> 00:05:36,620 Algorithm nan twazyèm vin pi efikas. 110 00:05:36,620 --> 00:05:40,120 Li nan sou aktyèlman 40% - oswa 60% pi efikas. 111 00:05:40,120 --> 00:05:41,580 Li pran 40% kantite lajan an nan tan. 112 00:05:41,580 --> 00:05:45,250 Li ka run-- li ka pran 400 inite nan resous 113 00:05:45,250 --> 00:05:47,570 nan pwosesis yon seri done nan gwosè 10. 114 00:05:47,570 --> 00:05:49,410 Lè nou konsidere ke premye a algorithm, pa kontra, 115 00:05:49,410 --> 00:05:54,520 pran 1,000 inite nan resous nan pwosesis yon seri done nan gwosè 10. 116 00:05:54,520 --> 00:05:57,240 Men, gade sa k ap pase kòm nimewo nou an jwenn menm pi gran. 117 00:05:57,240 --> 00:05:59,500 >> Koulye a, diferans ki genyen ant sa yo algoritm 118 00:05:59,500 --> 00:06:01,420 kòmanse vin yon ti kras mwens aparan. 119 00:06:01,420 --> 00:06:04,560 Ak lefèt ke gen pi ba-lòd terms-- ou pito, 120 00:06:04,560 --> 00:06:09,390 tèm ak pi ba exponents-- kòmanse vin petinan. 121 00:06:09,390 --> 00:06:12,290 Si yon seri done se nan gwosè 1,000 ak algorithm nan premye 122 00:06:12,290 --> 00:06:14,170 kouri nan yon milya dola etap. 123 00:06:14,170 --> 00:06:17,880 Men dezyèm algorithm nan kouri nan yon milya dola ak yon milyon dola etap. 124 00:06:17,880 --> 00:06:20,870 Ak twazyèm algorithm nan kouri nan jis timid nan yon milya dola etap. 125 00:06:20,870 --> 00:06:22,620 Li nan bèl anpil yon milya dola etap. 126 00:06:22,620 --> 00:06:25,640 Moun sa yo ki tèm pi ba-lòd kòmanse yo vin reyèlman petinan. 127 00:06:25,640 --> 00:06:27,390 Epi jis reyèlman mato lakay point-- nan 128 00:06:27,390 --> 00:06:31,240 si D 'a done se nan gwosè yon million-- tout twa nan sa yo bèl anpil 129 00:06:31,240 --> 00:06:34,960 pran yonn quintillion-- si matematik mwen an se etap correct-- 130 00:06:34,960 --> 00:06:37,260 nan pwosesis yon D 'done nan gwosè yon milyon dola. 131 00:06:37,260 --> 00:06:38,250 Sa se yon anpil nan etap. 132 00:06:38,250 --> 00:06:42,092 Ak lefèt ke youn nan yo ta ka pran yon koup 100,000, oswa yon koup 100 133 00:06:42,092 --> 00:06:44,650 milyon dola menm mwens lè nou ap pale de yon PO 134 00:06:44,650 --> 00:06:46,990 ki big-- li nan kalite petinan. 135 00:06:46,990 --> 00:06:50,006 Yo tout gen tandans pran apeprè n Gleason, 136 00:06:50,006 --> 00:06:52,380 epi pou nou ta aktyèlman al gade nan tout nan algoritm sa yo 137 00:06:52,380 --> 00:06:59,520 tankou se te sou lòd la nan n Gleason oswa gwo-O nan n Gleason. 138 00:06:59,520 --> 00:07:03,220 >> Isit la nan yon lis kèk nan plis nan klas komen konpleksite enfòmatik 139 00:07:03,220 --> 00:07:05,820 ke nou pral rankontre nan algoritm, jeneralman. 140 00:07:05,820 --> 00:07:07,970 Epi tou espesyalman nan CS50. 141 00:07:07,970 --> 00:07:11,410 Sa yo te bay lòd soti nan jeneralman pi rapid nan tèt la, 142 00:07:11,410 --> 00:07:13,940 jeneralman plus nan fon. 143 00:07:13,940 --> 00:07:16,920 Se konsa, algoritm tan konstan gen tandans yo dwe pi rapid la, kèlkeswa 144 00:07:16,920 --> 00:07:19,110 nan gwosè a nan la D 'done ou pase nan. 145 00:07:19,110 --> 00:07:23,760 Yo toujou pran yonn operasyon oswa yon inite nan resous fè fas ak. 146 00:07:23,760 --> 00:07:25,730 Li ta ka 2, li ta ka dwe 3, li ta kapab 4. 147 00:07:25,730 --> 00:07:26,910 Men, li la yon PO konstan. 148 00:07:26,910 --> 00:07:28,400 Li pa varye. 149 00:07:28,400 --> 00:07:31,390 >> Algoritm tan logaritmik se yon ti kras pi byen. 150 00:07:31,390 --> 00:07:33,950 Ak yon reyèlman bon ekzanp de yon algorithm tan logaritmik 151 00:07:33,950 --> 00:07:37,420 ou te siman wè pa kounye a se nan chire apa nan liv la telefòn 152 00:07:37,420 --> 00:07:39,480 jwenn Mike Smith nan liv la telefòn. 153 00:07:39,480 --> 00:07:40,980 Nou koupe pwoblèm nan nan mwatye. 154 00:07:40,980 --> 00:07:43,580 Se konsa, kòm n vin pi gwo ak pi gwo ak larger-- 155 00:07:43,580 --> 00:07:47,290 an reyalite, chak fwa ou double n, li sèlman pran yon sèl etap plis. 156 00:07:47,290 --> 00:07:49,770 Se konsa, sa a, se yon anpil pi bon pase, di, tan lineyè. 157 00:07:49,770 --> 00:07:53,030 Ki se si ou double n, li pran doub kantite etap. 158 00:07:53,030 --> 00:07:55,980 Si ou trip n, li pran trip ki kantite etap. 159 00:07:55,980 --> 00:07:58,580 Yon sèl etap pou chak inite. 160 00:07:58,580 --> 00:08:01,790 >> Lè sa a, bagay sa yo jwenn yon ti kras more-- ti kras mwens gwo soti nan la. 161 00:08:01,790 --> 00:08:06,622 Ou gen lineyè tan rit, pafwa rele boutèy demi lit tan lineyè oswa jis n boutèy demi lit n. 162 00:08:06,622 --> 00:08:08,330 Epitou, n ap yon egzanp nan yon algorithm ki 163 00:08:08,330 --> 00:08:13,370 kouri nan n boutèy demi lit n, ki se toujou pi bon pase kwadratik time-- n okib. 164 00:08:13,370 --> 00:08:17,320 Oswa tan polinòm, n de nenpòt ki kantite pi gran pase de. 165 00:08:17,320 --> 00:08:20,810 Oswa tan eksponansyèl, ki se menm worse-- C rive nan n nan. 166 00:08:20,810 --> 00:08:24,670 Se konsa, kèk nimewo konstan leve soti vivan nan pouvwa a nan gwosè a nan D 'a. 167 00:08:24,670 --> 00:08:28,990 Se konsa, si gen nan 1,000-- si nan D 'done se nan gwosè 1,000, 168 00:08:28,990 --> 00:08:31,310 li ta pran C rive nan pouvwa a 1,000 th. 169 00:08:31,310 --> 00:08:33,559 Li se yon anpil pi mal pase tan polinòm. 170 00:08:33,559 --> 00:08:35,030 >> Faktoryèl tan se menm vin pi mal. 171 00:08:35,030 --> 00:08:37,760 Ak nan reyalite, gen reyèlman fè egziste algoritm tan enfini, 172 00:08:37,760 --> 00:08:43,740 tankou, sa yo rele estipid sort-- ki gen travay se yo chefeul owaza yon etalaj 173 00:08:43,740 --> 00:08:45,490 ak Lè sa a tcheke yo wè si wi ou non li nan Ranje. 174 00:08:45,490 --> 00:08:47,589 Men, si li pa, owaza chefeul etalaj la ankò 175 00:08:47,589 --> 00:08:49,130 epi tcheke yo wè si wi ou non li nan Ranje. 176 00:08:49,130 --> 00:08:51,671 Ak jan ou ka pwobableman imagine-- ou ka imajine yon sitiyasyon 177 00:08:51,671 --> 00:08:55,200 kote nan pi move-ka a, ki volonte pa janm aktyèlman kòmanse ak etalaj la. 178 00:08:55,200 --> 00:08:57,150 Sa algorithm ta kouri pou tout tan. 179 00:08:57,150 --> 00:08:59,349 Se konsa, ki ta ka yon enfini tan algorithm. 180 00:08:59,349 --> 00:09:01,890 Nou swete ke ou pa pral ekri nenpòt ki lè faktoryèl oswa enfini 181 00:09:01,890 --> 00:09:04,510 algoritm nan CS50. 182 00:09:04,510 --> 00:09:09,150 >> Se konsa, kite a pran yon ti kras pi plis gade konkrè nan kèk ki pi senp 183 00:09:09,150 --> 00:09:11,154 enfòmatik konpleksite klas yo. 184 00:09:11,154 --> 00:09:13,070 Se konsa, nou gen yon example-- oswa de egzanp isit lan-- 185 00:09:13,070 --> 00:09:15,590 a algoritm tan konstan, ki toujou pran 186 00:09:15,590 --> 00:09:17,980 yon operasyon yon sèl nan pi move-ka-a. 187 00:09:17,980 --> 00:09:20,050 Se konsa, nan premye example-- nou gen yon fonksyon 188 00:09:20,050 --> 00:09:23,952 rele 4 pou ou, ki pran yon etalaj de gwosè 1,000. 189 00:09:23,952 --> 00:09:25,660 Men, Lè sa aparamman pa aktyèlman gade 190 00:09:25,660 --> 00:09:29,000 a l-- pa reyèlman sousye sa ki nan andedan nan li, nan ki etalaj. 191 00:09:29,000 --> 00:09:30,820 Toujou jis retounen kat. 192 00:09:30,820 --> 00:09:32,940 Se konsa, ki algorithm, malgre lefèt ke li 193 00:09:32,940 --> 00:09:35,840 pran 1,000 eleman pa fè anyen ak yo. 194 00:09:35,840 --> 00:09:36,590 Jis retounen kat. 195 00:09:36,590 --> 00:09:38,240 Li nan toujou yon etap sèl. 196 00:09:38,240 --> 00:09:41,600 >> An reyalite, ajoute 2 nums-- ki nou te wè anvan kòm well-- 197 00:09:41,600 --> 00:09:43,680 jis trete de nonm antye relatif. 198 00:09:43,680 --> 00:09:44,692 Li pa yon etap sèl. 199 00:09:44,692 --> 00:09:45,900 Li nan aktyèlman etap yon koup. 200 00:09:45,900 --> 00:09:50,780 Ou jwenn yon, ou jwenn b, ou ajoute yo ansanm, epi ou pwodiksyon rezilta yo. 201 00:09:50,780 --> 00:09:53,270 Se konsa, li 84 etap. 202 00:09:53,270 --> 00:09:55,510 Men, li la toujou konstan, kèlkeswa yon oswa b. 203 00:09:55,510 --> 00:09:59,240 Ou gen yo ka resevwa yon, jwenn b, ajoute yo ansanm, pwodiksyon rezilta a. 204 00:09:59,240 --> 00:10:02,900 Se konsa, sa a, se yon algorithm tan konstan. 205 00:10:02,900 --> 00:10:05,170 >> Isit la nan yon egzanp sou yon lineyè algorithm tan 206 00:10:05,170 --> 00:10:08,740 yon algorithm ki gen- ki pran yon sèl etap adisyonèl, petèt, 207 00:10:08,740 --> 00:10:10,740 kòm opinyon ou a ap grandi pa 1. 208 00:10:10,740 --> 00:10:14,190 Se konsa, kite pou nou di nou ap chèche pou nimewo 5 anndan an nan yon etalaj. 209 00:10:14,190 --> 00:10:16,774 Ou ta ka gen yon sitiyasyon kote ou ka jwenn li san patipri byen bonè. 210 00:10:16,774 --> 00:10:18,606 Men, ou te kapab gen tou yon sitiyasyon kote li 211 00:10:18,606 --> 00:10:20,450 ta ka eleman nan sot pase yo nan etalaj la. 212 00:10:20,450 --> 00:10:23,780 Nan yon etalaj de gwosè 5, si nou ap chèche pou yon nimewo pou la 5. 213 00:10:23,780 --> 00:10:25,930 Li ta pran 5 etap. 214 00:10:25,930 --> 00:10:29,180 Lè an reyalite, imajine ke gen nan pa nenpòt kote nan 5 etalaj sa a. 215 00:10:29,180 --> 00:10:32,820 Nou toujou gen aktyèlman fè yon gade nan chak eleman sèl nan etalaj la 216 00:10:32,820 --> 00:10:35,550 nan lòd yo detèmine si wi ou non 5 ki gen la. 217 00:10:35,550 --> 00:10:39,840 >> Se konsa, nan pi move ka a-yo, ki se ke eleman nan se dènye nan etalaj la 218 00:10:39,840 --> 00:10:41,700 oswa pa egziste nan tout. 219 00:10:41,700 --> 00:10:44,690 Nou toujou gen fè yon gade nan tout nan eleman yo n. 220 00:10:44,690 --> 00:10:47,120 Se konsa, sa a algorithm kouri nan tan lineyè. 221 00:10:47,120 --> 00:10:50,340 Ou ka konfime ke pa èkstrapolan yon ti jan lè li di, 222 00:10:50,340 --> 00:10:53,080 si nou te gen yon etalaj 6-eleman ak nou te kap chèche nimewo a 5, 223 00:10:53,080 --> 00:10:54,890 li ta ka pran 6 etap. 224 00:10:54,890 --> 00:10:57,620 Si nou gen yon etalaj 7-eleman ak nou ap chèche pou yon nimewo pou la 5. 225 00:10:57,620 --> 00:10:59,160 Li ta ka pran 7 etap. 226 00:10:59,160 --> 00:11:02,920 Kòm nou ajoute yon sèl eleman plis nan nou an etalaj, li pran yon sèl etap plis. 227 00:11:02,920 --> 00:11:06,750 Sa se yon algorithm lineyè nan pi move-ka-a. 228 00:11:06,750 --> 00:11:08,270 >> Koup kesyon rapid pou ou. 229 00:11:08,270 --> 00:11:11,170 Ki sa ki nan runtime-- nan sa ki nan pi move ka-ègzekutabl nan 230 00:11:11,170 --> 00:11:13,700 nan sa a brib patikilye nan Kòd? 231 00:11:13,700 --> 00:11:17,420 Se konsa, mwen gen yon riban 4 isit la ki kouri soti nan j egal 0, tout wout la jiska m. 232 00:11:17,420 --> 00:11:21,980 Apre sa, sa m ap wè isit la, se ke nan kò a riban an kouri nan tan konstan. 233 00:11:21,980 --> 00:11:24,730 Se konsa, lè l sèvi avèk tèminoloji a ki nou te deja pale sou- sa 234 00:11:24,730 --> 00:11:29,390 ta dwe pi mal la-ka a ègzekutabl nan algorithm sa a? 235 00:11:29,390 --> 00:11:31,050 Pran yon dezyèm fwa. 236 00:11:31,050 --> 00:11:34,270 Pati nan anndan an nan bouk la kouri nan tan konstan. 237 00:11:34,270 --> 00:11:37,510 Ak yon pati la deyò nan la bouk ki pral kouri m fwa. 238 00:11:37,510 --> 00:11:40,260 Se konsa, sa ki nan ègzekutabl ki pi mal la-ka isit la? 239 00:11:40,260 --> 00:11:43,210 Èske w te devine gwo-O nan m? 240 00:11:43,210 --> 00:11:44,686 Ou ta dwe gen dwa. 241 00:11:44,686 --> 00:11:46,230 >> Kouman sou yon lòt yon sèl? 242 00:11:46,230 --> 00:11:48,590 Fwa sa a, nou gen yon bouk andedan nan yon riban. 243 00:11:48,590 --> 00:11:50,905 Nou gen yon riban deyò ki kouri soti nan zewo rive p. 244 00:11:50,905 --> 00:11:54,630 Epi nou gen yon riban ki kouri anndan soti nan zewo rive p, ak andedan nan sa, 245 00:11:54,630 --> 00:11:57,890 Mwen deklare ke nan kò a bouk kouri nan tan konstan. 246 00:11:57,890 --> 00:12:02,330 Se konsa, sa ki nan ègzekutabl ki pi mal la-ka nan sa a brib patikilye nan Kòd? 247 00:12:02,330 --> 00:12:06,140 Bon, ankò, nou gen yon deyò bouk ki kouri fwa p. 248 00:12:06,140 --> 00:12:09,660 Epitou, chak iterasyon time-- nan ki bouk, olye. 249 00:12:09,660 --> 00:12:13,170 Nou gen yon riban enteryè ki tou kouri fwa p. 250 00:12:13,170 --> 00:12:16,900 Lè sa a, andedan nan ki, gen nan la konstan time-- ti kras brib a. 251 00:12:16,900 --> 00:12:19,890 >> Se konsa, si nou gen yon riban deyò ki kouri fwa p andedan nan ki se 252 00:12:19,890 --> 00:12:22,880 yon bouk enteryè ki kouri p jou- ki sa ki 253 00:12:22,880 --> 00:12:26,480 pi move ka-ègzekutabl nan nan sa a brib nan kòd? 254 00:12:26,480 --> 00:12:30,730 Èske w te devine gwo-O nan p au? 255 00:12:30,730 --> 00:12:31,690 >> Mwen se Doug Lloyd. 256 00:12:31,690 --> 00:12:33,880 Sa a se CS50. 257 00:12:33,880 --> 00:12:35,622