1 00:00:00,000 --> 00:00:05,830 2 00:00:05,830 --> 00:00:07,910 >> Gach ceart, mar sin, castacht ríomhaireachtúil. 3 00:00:07,910 --> 00:00:10,430 Ach beagán de rabhadh sula Léim muid i ró far-- 4 00:00:10,430 --> 00:00:13,070 Beidh sé seo a bheith dócha i measc na rudaí is mó math-trom 5 00:00:13,070 --> 00:00:14,200 labhairt linn faoi i CS50. 6 00:00:14,200 --> 00:00:16,950 Tá súil againn nach mbeidh sé ró-mór agus beidh orainn iarracht a dhéanamh agus tú a threorú 7 00:00:16,950 --> 00:00:19,200 tríd an bpróiseas, ach ach beagán de rabhadh cothrom. 8 00:00:19,200 --> 00:00:21,282 Níl le beagán de math i gceist anseo. 9 00:00:21,282 --> 00:00:23,990 Ceart go leor, mar sin d'fhonn a dhéanamh úsáid a bhaint as ár n-acmhainní ríomhaireachta 10 00:00:23,990 --> 00:00:28,170 sa world-- fíor tá sé i ndáiríre tábhachtach a thuiscint halgartaim 11 00:00:28,170 --> 00:00:30,750 agus conas a phróiseáil siad sonraí. 12 00:00:30,750 --> 00:00:32,810 Má táimid tar éis i ndáiríre algartam éifeachtach, táimid ag 13 00:00:32,810 --> 00:00:36,292 Is féidir laghdú ar an méid na n-acmhainní ní mór dúinn ar fáil chun déileáil leis. 14 00:00:36,292 --> 00:00:38,750 Má tá algartaim go ag dul a ghlacadh a lán oibre 15 00:00:38,750 --> 00:00:41,210 a phróiseáil i ndáiríre sraith mór sonraí, tá sé 16 00:00:41,210 --> 00:00:44,030 ag dul a cheangal ar níos mó agus níos mó acmhainní, a 17 00:00:44,030 --> 00:00:47,980 Tá airgead, RAM, gach chineál sin de stuif. 18 00:00:47,980 --> 00:00:52,090 >> Mar sin, a bheith in ann anailís a ar algartam ag baint úsáide as an tacar uirlis, 19 00:00:52,090 --> 00:00:56,110 go bunúsach iarrann, an question-- conas a dhéanann an scála algartam 20 00:00:56,110 --> 00:00:59,020 mar chaitheann muid sonraí níos mó agus níos mó ar sé? 21 00:00:59,020 --> 00:01:02,220 I CS50, an méid sonraí táimid ag obair le go leor go bhfuil beag. 22 00:01:02,220 --> 00:01:05,140 Go ginearálta, is iad ár gcláir ag dul a reáchtáil i an dara nó less-- 23 00:01:05,140 --> 00:01:07,830 dócha a lán níos lú go háirithe go luath ar. 24 00:01:07,830 --> 00:01:12,250 >> Ach smaoineamh ar cuideachta a dhéileálann leis na céadta milliún na n gcustaiméirí. 25 00:01:12,250 --> 00:01:14,970 Agus is gá iad a phróiseáil sonraí do chustaiméirí. 26 00:01:14,970 --> 00:01:18,260 Mar líon na gcustaiméirí siad tá faigheann níos mó agus níos mó, 27 00:01:18,260 --> 00:01:21,230 tá sé ag dul chun a cheangal acmhainní níos mó agus níos mó. 28 00:01:21,230 --> 00:01:22,926 Cé mhéid níos mó acmhainní? 29 00:01:22,926 --> 00:01:25,050 Bhuel, braitheann sin ar an gcaoi anailís a dhéanamh againn ar an algartam, 30 00:01:25,050 --> 00:01:28,097 ag baint úsáide as na huirlisí seo bosca uirlisí. 31 00:01:28,097 --> 00:01:31,180 Nuair a labhairt linn faoi chastacht ar algorithm-- a uaireanta go mbainfidh tú 32 00:01:31,180 --> 00:01:34,040 chloisteáil thagair sé mar am castacht nó spás castacht 33 00:01:34,040 --> 00:01:36,190 ach táimid ag dul díreach chun glaoch complexity-- 34 00:01:36,190 --> 00:01:38,770 muid ag caint go ginearálta faoi an chás is measa. 35 00:01:38,770 --> 00:01:42,640 Mar gheall ar an carn glan is measa de sonraí go raibh muid ábalta a bheith ag caitheamh ar sé, 36 00:01:42,640 --> 00:01:46,440 gcaoi a bhfuil an algartam ag dul go dtí a phróiseáil nó déileáil le sonraí? 37 00:01:46,440 --> 00:01:51,450 Táimid ag glaoch go ginearálta an ceann is measa ar chás runtime de algartaim mór-O. 38 00:01:51,450 --> 00:01:56,770 Mar sin d'fhéadfadh algartaim a rá go reáchtáil i O de n nó O de n cearnógach. 39 00:01:56,770 --> 00:01:59,110 Agus níos mó faoi cad iad siúd Ciallaíonn sa dara. 40 00:01:59,110 --> 00:02:01,620 >> Uaireanta, áfach, a dhéanann muid cúram mar gheall ar an gcás is fearr. 41 00:02:01,620 --> 00:02:05,400 Má tá na sonraí a bhíomar ag iarraidh gach rud a é a bheith agus go raibh sé go hiomlán foirfe 42 00:02:05,400 --> 00:02:09,630 agus bhí muid a sheoladh seo foirfe sraith sonraí trí mheán ár algartam. 43 00:02:09,630 --> 00:02:11,470 Conas a bheadh ​​sé a láimhseáil i staid sin? 44 00:02:11,470 --> 00:02:15,050 Tagraímid uaireanta sin mar mór-Omega, mar sin i gcodarsnacht le mór-O, 45 00:02:15,050 --> 00:02:16,530 ní mór dúinn mór-Omega. 46 00:02:16,530 --> 00:02:18,880 Big-Omega le haghaidh an scéal is fearr ar chás. 47 00:02:18,880 --> 00:02:21,319 Big-O don chás is measa. 48 00:02:21,319 --> 00:02:23,860 Go ginearálta, nuair a labhairt linn faoi an chastacht algartaim, 49 00:02:23,860 --> 00:02:26,370 tá muid ag caint faoi na chás is measa. 50 00:02:26,370 --> 00:02:28,100 Mar sin a choinneáil sin san áireamh. 51 00:02:28,100 --> 00:02:31,510 >> Agus sa rang seo, táimid ag dul go ginearálta a fhágáil ar an anailís dhian ar leataobh. 52 00:02:31,510 --> 00:02:35,350 Tá eolaíochtaí agus réimsí a bheidh dírithe ar an gcineál seo stuif. 53 00:02:35,350 --> 00:02:37,610 Nuair a labhairt linn faoi réasúnaíocht trí halgartaim, 54 00:02:37,610 --> 00:02:41,822 a beidh orainn píosa-by-phíosa a dhéanamh do go leor halgartaim labhairt linn faoi sa rang. 55 00:02:41,822 --> 00:02:44,780 Táimid ag caint faoi i ndáiríre ach réasúnaíocht tríd sé le tuiscint coiteann, 56 00:02:44,780 --> 00:02:47,070 ní le foirmlí, nó cruthúnais, nó aon rud mar sin. 57 00:02:47,070 --> 00:02:51,600 Mar sin ná bíodh imní ort, ní bheimid casadh i rang math mór. 58 00:02:51,600 --> 00:02:55,920 >> Mar sin, dúirt mé cúram againn faoi chastacht toisc go iarrann sé an cheist, conas 59 00:02:55,920 --> 00:03:00,160 bhfuil ár halgartaim láimhseáil níos mó agus tacair sonraí níos mó a bheith caite orthu. 60 00:03:00,160 --> 00:03:01,960 Bhuel, cad é tacar sonraí? 61 00:03:01,960 --> 00:03:03,910 Cad a rinne mé nuair a dúirt mé i gceist go? 62 00:03:03,910 --> 00:03:07,600 Ciallaíonn sé cuma cad a dhéanann an chuid is mó ciall i gcomhthéacs, a bheith macánta. 63 00:03:07,600 --> 00:03:11,160 Má tá algartaim, an Próisis Strings-- tá muid dócha 64 00:03:11,160 --> 00:03:13,440 ag caint faoi an méid de na teaghrán. 65 00:03:13,440 --> 00:03:15,190 Sin na sonraí set-- an méid, líon 66 00:03:15,190 --> 00:03:17,050 de charachtair a dhéanann suas an teaghrán. 67 00:03:17,050 --> 00:03:20,090 Má tá muid ag caint faoi algartam próiseáil comhaid, 68 00:03:20,090 --> 00:03:23,930 d'fhéadfadh muid a bheith ag caint faoi conas Cuimsíonn leor cilibheart go comhad. 69 00:03:23,930 --> 00:03:25,710 Agus sin an tacar sonraí. 70 00:03:25,710 --> 00:03:28,870 Má tá muid ag caint faoi algartam go Láimhseálann arrays níos ginearálta, 71 00:03:28,870 --> 00:03:31,510 cosúil le halgartaim sórtáil nó halgartaim cuardach, 72 00:03:31,510 --> 00:03:36,690 muid ag caint is dócha mar gheall ar an líon na n-eilimintí a chuimsíonn sraith. 73 00:03:36,690 --> 00:03:39,272 >> Anois, is féidir linn a thomhas ar algorithm-- háirithe, 74 00:03:39,272 --> 00:03:40,980 nuair a rá liom gur féidir linn a thomhas algartam, mé 75 00:03:40,980 --> 00:03:43,840 ciallóidh is féidir linn a thomhas cé go leor acmhainní a thógann sé suas. 76 00:03:43,840 --> 00:03:48,990 Cibé an bhfuil na hacmhainní sin, cé mhéad bytes de RAM-- nó meigibheart de RAM 77 00:03:48,990 --> 00:03:49,790 úsáideann sé. 78 00:03:49,790 --> 00:03:52,320 Nó cé mhéad ama a thógann sé a rith. 79 00:03:52,320 --> 00:03:56,200 Agus is féidir linn glaoch seo a thomhas, treallach, f de n. 80 00:03:56,200 --> 00:03:59,420 I gcás ina bhfuil n líon na eilimintí sa tacar sonraí. 81 00:03:59,420 --> 00:04:02,640 Agus is é f an n cé mhéad somethings. 82 00:04:02,640 --> 00:04:07,530 Cé mhéad aonad na n-acmhainní a dhéanann sé a cheangal a phróiseáil na sonraí sin. 83 00:04:07,530 --> 00:04:10,030 >> Anois, táimid ag nach bhfuil i ndáiríre cúram faoi ​​cad f de n go díreach. 84 00:04:10,030 --> 00:04:13,700 Go deimhin, táimid ag will-- an-annamh Beidh cinnte riamh sa mé class-- 85 00:04:13,700 --> 00:04:18,709 Léim isteach in aon ndáiríre go domhain anailís a dhéanamh ar cad f de go bhfuil n. 86 00:04:18,709 --> 00:04:23,510 Táimid ag dul díreach chun labhairt faoi na rudaí f de Is n thart nó cad bíonn sé a. 87 00:04:23,510 --> 00:04:27,600 Agus is é an claonadh atá algartaim dheachtú ag a théarma ordú is airde. 88 00:04:27,600 --> 00:04:29,440 Agus is féidir linn a fheiceáil cad mé Ciallaíonn ag ag cur 89 00:04:29,440 --> 00:04:31,910 a breathnú ar sampla níos nithiúla. 90 00:04:31,910 --> 00:04:34,620 >> Mar sin, a ligean ar rá go bhfuil muid trí halgartaim éagsúla. 91 00:04:34,620 --> 00:04:39,350 Bíonn an chéad cheann a n chiúbaithe, roinnt aonad na n-acmhainní 92 00:04:39,350 --> 00:04:42,880 a phróiseáil tacar sonraí de mhéid n. 93 00:04:42,880 --> 00:04:47,000 Ní mór dúinn an dara algartam a thógann n chiúbaithe móide acmhainní n cearnógach 94 00:04:47,000 --> 00:04:49,350 a phróiseáil tacar sonraí de mhéid n. 95 00:04:49,350 --> 00:04:52,030 Agus ní mór dúinn an tríú algartam go ritheann in-- sin 96 00:04:52,030 --> 00:04:58,300 Bíonn suas n lúide chiúbaithe 8N cearnógach móide 20 n-aonad na n-acmhainní 97 00:04:58,300 --> 00:05:02,370 a phróiseáil algartam le sonraí a leagtar ar mhéid n. 98 00:05:02,370 --> 00:05:05,594 >> Anois arís, ní againn i ndáiríre ag dul chun dul isteach ar an leibhéal mionsonraí. 99 00:05:05,594 --> 00:05:08,260 Tá mé i ndáiríre ach tá na suas anseo mar léiriú de phointe 100 00:05:08,260 --> 00:05:10,176 go bhfuil mé ag dul a bheith dhéanamh sa dara, a 101 00:05:10,176 --> 00:05:12,980 is é sin táimid ag cúram ach i ndáiríre mar gheall ar an claonadh na rudaí 102 00:05:12,980 --> 00:05:14,870 mar a fháil ar na tacair sonraí níos mó. 103 00:05:14,870 --> 00:05:18,220 Mar sin, má tá an tacar sonraí beag, níl i ndáiríre difríocht mór go leor 104 00:05:18,220 --> 00:05:19,870 sna halgartaim. 105 00:05:19,870 --> 00:05:23,000 An tríú algartam ann Bíonn 13 uair níos faide, 106 00:05:23,000 --> 00:05:27,980 13 uair an méid na n-acmhainní a reáchtáil i gcoibhneas leis an chéad cheann. 107 00:05:27,980 --> 00:05:31,659 >> Má tá ár tacar sonraí méid 10, a acu is mó, ach ní gá go mór, 108 00:05:31,659 --> 00:05:33,950 Is féidir linn a fheiceáil go níl i ndáiríre le beagán de difríocht. 109 00:05:33,950 --> 00:05:36,620 An tríú algartam thiocfaidh chun bheith níos éifeachtaí. 110 00:05:36,620 --> 00:05:40,120 Tá sé thart ar 40% i ndáiríre - nó 60% níos éifeachtaí. 111 00:05:40,120 --> 00:05:41,580 Bíonn sé 40% an méid ama. 112 00:05:41,580 --> 00:05:45,250 Is féidir é a run-- féidir é a ghlacadh 400 aonad na n-acmhainní 113 00:05:45,250 --> 00:05:47,570 a phróiseáil tacar sonraí de mhéid 10. 114 00:05:47,570 --> 00:05:49,410 De bharr an méid an chéad algartam, ag gcodarsnacht leis sin, 115 00:05:49,410 --> 00:05:54,520 Bíonn 1,000 aonad na n-acmhainní a phróiseáil tacar sonraí de mhéid 10. 116 00:05:54,520 --> 00:05:57,240 Ach breathnú cad a tharlaíonn mar ár n-uimhreacha a fháil fiú níos mó. 117 00:05:57,240 --> 00:05:59,500 >> Anois, an difríocht idir na halgartaim 118 00:05:59,500 --> 00:06:01,420 tús a bheith ina beagán níos lú le feiceáil. 119 00:06:01,420 --> 00:06:04,560 Agus ar an bhfíric go bhfuil ísealoird terms-- nó in áit, 120 00:06:04,560 --> 00:06:09,390 téarmaí exponents-- ísle tús a bheith nach mbaineann le hábhar. 121 00:06:09,390 --> 00:06:12,290 Má tá tacar sonraí de mhéid 1,000 agus an chéad algartam 122 00:06:12,290 --> 00:06:14,170 Ritheann i billiún céimeanna. 123 00:06:14,170 --> 00:06:17,880 Agus ritheann an dara algartam i billiún agus milliún céimeanna. 124 00:06:17,880 --> 00:06:20,870 Agus ritheann an tríú algartam i díreach cúthail de billiún céimeanna. 125 00:06:20,870 --> 00:06:22,620 Tá sé go leor i bhfad billiún céimeanna. 126 00:06:22,620 --> 00:06:25,640 Na téarmaí sin ísealoird tosú a bheith i ndáiríre nach mbaineann le hábhar. 127 00:06:25,640 --> 00:06:27,390 Agus díreach go dtí ndáiríre Baile casúr an point-- 128 00:06:27,390 --> 00:06:31,240 má tá an t-ionchur sonraí ar mhéid a million-- na trí cinn de na leor i bhfad 129 00:06:31,240 --> 00:06:34,960 ghlacadh quintillion-- amháin más rud é Is é mo math céimeanna correct-- 130 00:06:34,960 --> 00:06:37,260 a phróiseáil ionchur sonraí de mhéid a milliún. 131 00:06:37,260 --> 00:06:38,250 Sin a lán de na céimeanna. 132 00:06:38,250 --> 00:06:42,092 Agus ar an bhfíric go d'fhéadfadh duine amháin acu ghlacadh cúpla 100,000, nó lánúin 100 133 00:06:42,092 --> 00:06:44,650 milliún fiú níos lú nuair muid ag caint faoi a PO 134 00:06:44,650 --> 00:06:46,990 go big-- tá sé de chineál nach mbaineann le hábhar. 135 00:06:46,990 --> 00:06:50,006 Claonadh a bhíonn siad go léir a ghlacadh thart n chiúbaithe, 136 00:06:50,006 --> 00:06:52,380 agus mar sin ba mhaith linn a tharchur i ndáiríre do gach ceann de na halgartaim 137 00:06:52,380 --> 00:06:59,520 mar ar an ord n chiúbaithe nó mór-O de n chiúbaithe. 138 00:06:59,520 --> 00:07:03,220 >> Seo liosta de roinnt de na níos Ranganna castacht ríomhaireachta coitianta 139 00:07:03,220 --> 00:07:05,820 go beidh orainn a bhíonn i halgartaim, go ginearálta. 140 00:07:05,820 --> 00:07:07,970 Agus freisin go sonrach i CS50. 141 00:07:07,970 --> 00:07:11,410 Tá siad seo a ordú ó go ginearálta is tapúla ag an mbarr, 142 00:07:11,410 --> 00:07:13,940 chun go ginearálta is moille ag bun an leathanaigh. 143 00:07:13,940 --> 00:07:16,920 Mar sin, claonadh a bhíonn halgartaim am tairiseach a bheith ar an tapúla, is cuma 144 00:07:16,920 --> 00:07:19,110 de mhéid an ionchur sonraí a théann tú i. 145 00:07:19,110 --> 00:07:23,760 Siad a ghlacadh i gcónaí oibriú ceann amháin nó aonad amháin de na hacmhainní chun déileáil leis. 146 00:07:23,760 --> 00:07:25,730 D'fhéadfadh sé a bheith 2, d'fhéadfadh sé a 3, d'fhéadfadh sé a bheith 4. 147 00:07:25,730 --> 00:07:26,910 Ach tá sé roinnt tairiseach. 148 00:07:26,910 --> 00:07:28,400 Ní chuireann sé athrú. 149 00:07:28,400 --> 00:07:31,390 >> Halgartaim am logartamach Tá beagán níos fearr. 150 00:07:31,390 --> 00:07:33,950 Agus is sampla gur maith algartam am logartamach 151 00:07:33,950 --> 00:07:37,420 tú atá le feiceáil surely ag anois go bhfuil an tearing seachas an leabhar teileafóin 152 00:07:37,420 --> 00:07:39,480 a fháil Mike Smith sa leabhar teileafóin. 153 00:07:39,480 --> 00:07:40,980 Gearrtha againn ar an fhadhb i leath. 154 00:07:40,980 --> 00:07:43,580 Agus mar sin mar a fhaigheann níos mó n agus níos mó agus larger-- 155 00:07:43,580 --> 00:07:47,290 i ndáiríre, gach uair a dhúbailt tú n, a thógann sé ach céim amháin níos mó. 156 00:07:47,290 --> 00:07:49,770 Mar sin tá go bhfuil a lán níos fearr ná, a rá, am líneach. 157 00:07:49,770 --> 00:07:53,030 Cé acu is má dúbailte tú n, é a Bíonn dhá oiread líon na céimeanna. 158 00:07:53,030 --> 00:07:55,980 Má tá tú triple n, a thógann sé triple líon na céimeanna. 159 00:07:55,980 --> 00:07:58,580 Céim amháin in aghaidh an aonaid. 160 00:07:58,580 --> 00:08:01,790 >> Ansin rudaí a fháil ar more-- beag beagán níos lú mór ó ann. 161 00:08:01,790 --> 00:08:06,622 Tá tú am rhythmic líneach, uaireanta ar a dtugtar logáil uair líneach nó díreach n logáil n. 162 00:08:06,622 --> 00:08:08,330 Agus beidh orainn sampla de algartaim a 163 00:08:08,330 --> 00:08:13,370 Ritheann i n logáil n, atá fós níos fearr ná chearnach time-- n cearnógach. 164 00:08:13,370 --> 00:08:17,320 Nó am polynomial, n beirt aon uimhir níos mó ná dhá. 165 00:08:17,320 --> 00:08:20,810 Nó am easpónantúil, a Is fiú worse-- C go dtí an n. 166 00:08:20,810 --> 00:08:24,670 Mar sin, roinnt uimhir leanúnach a ardaíodh le an cumhacht ag an méid de na ionchur. 167 00:08:24,670 --> 00:08:28,990 Mar sin, má níl 1,000-- má Tá ionchur sonraí de mhéid 1,000, 168 00:08:28,990 --> 00:08:31,310 thógfadh sé C chun an chumhacht 1000. 169 00:08:31,310 --> 00:08:33,559 Tá sé a lán níos measa ná am polynomial. 170 00:08:33,559 --> 00:08:35,030 >> Tá am factorial níos measa fós. 171 00:08:35,030 --> 00:08:37,760 Agus go deimhin, tá a dhéanamh i ndáiríre ann halgartaim am gan teorainn, 172 00:08:37,760 --> 00:08:43,740 ar nós sort-- dúr mar, mar a thugtar a bhfuil a Is post a Suaitheadh ​​randamach le sraith 173 00:08:43,740 --> 00:08:45,490 agus ansin seiceáil a fheiceáil cibé an bhfuil sé curtha in eagar. 174 00:08:45,490 --> 00:08:47,589 Agus más rud é nach bhfuil sé, go randamach Suaitheadh ​​an eagar arís 175 00:08:47,589 --> 00:08:49,130 agus seiceáil a fheiceáil cé acu tá sé curtha in eagar. 176 00:08:49,130 --> 00:08:51,671 Agus mar is féidir leat a imagine-- is dócha Is féidir leat a shamhlú staid 177 00:08:51,671 --> 00:08:55,200 nuair is i an ceann is measa ar chás, beidh sin Riamh tús iarbhír leis an eagar. 178 00:08:55,200 --> 00:08:57,150 Bheadh ​​sin a algartam a reáchtáil go deo. 179 00:08:57,150 --> 00:08:59,349 Agus mar sin a bheadh ​​ina algartam am gan teorainn. 180 00:08:59,349 --> 00:09:01,890 Súil go dtosnódh ní bheidh tú ag scríobh aon tráth factorial nó gan teorainn 181 00:09:01,890 --> 00:09:04,510 halgartaim i CS50. 182 00:09:04,510 --> 00:09:09,150 >> Mar sin, a ligean ar ghlacadh beagán níos mó breathnú coincréite ag roinnt níos simplí 183 00:09:09,150 --> 00:09:11,154 ranganna castacht ríomhaireachta. 184 00:09:11,154 --> 00:09:13,070 Mar sin, ní mór dúinn example-- nó dhá shampla here-- 185 00:09:13,070 --> 00:09:15,590 de halgartaim am tairiseach, a ghlacadh i gcónaí 186 00:09:15,590 --> 00:09:17,980 aon oibríocht amháin i an ceann is measa ar chás. 187 00:09:17,980 --> 00:09:20,050 Mar sin, an chéad example-- ní mór dúinn a fheidhm 188 00:09:20,050 --> 00:09:23,952 iarr 4 do shon, a Bíonn sraith de mhéid 1,000. 189 00:09:23,952 --> 00:09:25,660 Ach ansin cosúil nach cuma i ndáiríre 190 00:09:25,660 --> 00:09:29,000 ag nach bhfuil it-- cúram i ndáiríre cad atá taobh istigh de sé, de chuid eagar. 191 00:09:29,000 --> 00:09:30,820 I gcónaí tuairisceáin ach ceithre. 192 00:09:30,820 --> 00:09:32,940 Mar sin, go algartam, in ainneoin go bhfuil sé 193 00:09:32,940 --> 00:09:35,840 Bíonn 1,000 Eilimintí nach bhfuil aon ní leo a dhéanamh. 194 00:09:35,840 --> 00:09:36,590 Just a tuairisceáin a ceathair. 195 00:09:36,590 --> 00:09:38,240 Tá sé i gcónaí aon chéim amháin. 196 00:09:38,240 --> 00:09:41,600 >> Go deimhin, cuir 2 nums-- a againn le feiceáil roimh mar well-- 197 00:09:41,600 --> 00:09:43,680 ach próisis dhá slánuimhreacha. 198 00:09:43,680 --> 00:09:44,692 Níl sé aon chéim amháin. 199 00:09:44,692 --> 00:09:45,900 Tá sé i ndáiríre céimeanna cúpla. 200 00:09:45,900 --> 00:09:50,780 Fhaigheann tú, gheobhaidh tú b, cuir tú iad le chéile, agus aschur tú na torthaí. 201 00:09:50,780 --> 00:09:53,270 Mar sin tá sé 84 céimeanna. 202 00:09:53,270 --> 00:09:55,510 Ach tá sé i gcónaí tairiseach, beag beann ar a nó b. 203 00:09:55,510 --> 00:09:59,240 Tá tú a fháil a, b fháil, cuir iad le chéile, aschur an toradh. 204 00:09:59,240 --> 00:10:02,900 Mar sin, go bhfuil algartam am tairiseach. 205 00:10:02,900 --> 00:10:05,170 >> Seo sampla de algorithm-- am líneach 206 00:10:05,170 --> 00:10:08,740 algartaim a gets-- go dtógann céim amháin breise, b'fhéidir, 207 00:10:08,740 --> 00:10:10,740 mar a fhásann do ionchur ag 1. 208 00:10:10,740 --> 00:10:14,190 Mar sin, a ligean ar rá táimid ag lorg an uimhir 5 taobh istigh de eagar. 209 00:10:14,190 --> 00:10:16,774 D'fhéadfá a bheith staid ina Is féidir leat é a fháil go luath go cothrom. 210 00:10:16,774 --> 00:10:18,606 Ach d'fhéadfadh a bheith agat freisin staid áit a bhfuil sé 211 00:10:18,606 --> 00:10:20,450 d'fhéadfadh a bheith ar an ghné dheireanach an eagar. 212 00:10:20,450 --> 00:10:23,780 I sraith de mhéid 5, más rud é táimid ag lorg an uimhir 5. 213 00:10:23,780 --> 00:10:25,930 Bheadh ​​sé a ghlacadh 5 céimeanna. 214 00:10:25,930 --> 00:10:29,180 Agus go deimhin, a shamhlú go níl Ní 5 áit ar bith ar an eagar. 215 00:10:29,180 --> 00:10:32,820 Táimid fós i ndáiríre chun breathnú ar gach gné amháin den eagar 216 00:10:32,820 --> 00:10:35,550 d'fhonn a chinneadh an bhfuil nó nach 5 ann. 217 00:10:35,550 --> 00:10:39,840 >> Mar sin, i an ceann is measa ar chás, a bhfuil go Is é an ghné dheireanach den sraith 218 00:10:39,840 --> 00:10:41,700 nó gan a bheith ann ar chor ar bith. 219 00:10:41,700 --> 00:10:44,690 Tá muid go fóill chun breathnú ar gach ceann de na heilimintí n. 220 00:10:44,690 --> 00:10:47,120 Agus mar sin an algartam Ritheann in am líneach. 221 00:10:47,120 --> 00:10:50,340 Is féidir leat a dhearbhú go bhfuil ag a eachtarshuí le beagán ag rá, 222 00:10:50,340 --> 00:10:53,080 má bhí againn le sraith 6-eilimint agus bhí muid ag lorg an uimhir 5, 223 00:10:53,080 --> 00:10:54,890 d'fhéadfadh sé a ghlacadh 6 céimeanna. 224 00:10:54,890 --> 00:10:57,620 Má táimid tar éis sraith 7-eilimint agus táimid ag lorg an uimhir 5. 225 00:10:57,620 --> 00:10:59,160 D'fhéadfadh sé a ghlacadh 7 céimeanna. 226 00:10:59,160 --> 00:11:02,920 Mar chur linn eilimint amháin níos mó ar ár eagar, a thógann sé céim amháin níos mó. 227 00:11:02,920 --> 00:11:06,750 Sin a algartam líneach i an ceann is measa ar chás. 228 00:11:06,750 --> 00:11:08,270 >> Lánúin ceisteanna tapaidh ar do shon. 229 00:11:08,270 --> 00:11:11,170 Cad é an runtime-- cad atá an ceann is measa ar chás runtime 230 00:11:11,170 --> 00:11:13,700 den Blúire áirithe cód? 231 00:11:13,700 --> 00:11:17,420 Mar sin, tá mé lúb 4 anseo a ritheann as ionann j 0, léir ar an mbealach suas go dtí m. 232 00:11:17,420 --> 00:11:21,980 Agus cad mé ag féachaint anseo é, go bhfuil an Ritheann comhlacht ar an lúb in am tairiseach. 233 00:11:21,980 --> 00:11:24,730 Mar sin, ag baint úsáide as an téarmaíocht go tá muid Labhair cheana about-- méid 234 00:11:24,730 --> 00:11:29,390 bheadh ​​an ceann is measa ar chás runtime an algartam? 235 00:11:29,390 --> 00:11:31,050 Chur ar an dara. 236 00:11:31,050 --> 00:11:34,270 An chuid inmheánach den lúb Ritheann in am tairiseach. 237 00:11:34,270 --> 00:11:37,510 Agus an chuid amuigh den lúb ag dul a reáchtáil amanna m. 238 00:11:37,510 --> 00:11:40,260 Mar sin, cad é an ceann is measa ar chás runtime anseo? 239 00:11:40,260 --> 00:11:43,210 An raibh tú buille faoi thuairim mór-O de m? 240 00:11:43,210 --> 00:11:44,686 Gur mhaith leat a bheith ceart. 241 00:11:44,686 --> 00:11:46,230 >> Cad é faoi a chéile? 242 00:11:46,230 --> 00:11:48,590 An uair seo ní mór dúinn a lúb taobh istigh de lúb. 243 00:11:48,590 --> 00:11:50,905 Ní mór dúinn lúb seachtrach a ritheann ó náid go p. 244 00:11:50,905 --> 00:11:54,630 Agus ní mór dúinn lúb istigh a ritheann ó náid go p, agus taobh istigh de sin, 245 00:11:54,630 --> 00:11:57,890 Dearbhaím go bhfuil an comhlacht an Ritheann lúb in am tairiseach. 246 00:11:57,890 --> 00:12:02,330 Mar sin, cad é an ceann is measa ar chás runtime den Blúire áirithe cód? 247 00:12:02,330 --> 00:12:06,140 Bhuel, arís, ní mór dúinn lúb seachtrach go ritheann amanna p. 248 00:12:06,140 --> 00:12:09,660 Agus gach atriall time-- den lúb, in áit. 249 00:12:09,660 --> 00:12:13,170 Ní mór dúinn lúb istigh go ritheann freisin amanna p. 250 00:12:13,170 --> 00:12:16,900 Agus ansin taobh istigh de sin, níl an Blúire tairiseach time-- beag ann. 251 00:12:16,900 --> 00:12:19,890 >> Mar sin má tá lúb amuigh go Ritheann amanna p taobh istigh de a 252 00:12:19,890 --> 00:12:22,880 lúb istigh go Ritheann p times-- a bhfuil 253 00:12:22,880 --> 00:12:26,480 an ceann is measa ar chás runtime den Blúire de chód? 254 00:12:26,480 --> 00:12:30,730 An raibh tú buille faoi thuairim mór-O p cearnógach? 255 00:12:30,730 --> 00:12:31,690 >> Tá mé Doug Lloyd. 256 00:12:31,690 --> 00:12:33,880 Is é seo an CS50. 257 00:12:33,880 --> 00:12:35,622