Gach ceart, mar sin, castacht ríomhaireachtúil. Ach beagán de rabhadh sula Léim muid i ró far-- Beidh sé seo a bheith dócha i measc na rudaí is mó math-trom labhairt linn faoi i CS50. Tá súil againn nach mbeidh sé ró-mór agus beidh orainn iarracht a dhéanamh agus tú a threorú tríd an bpróiseas, ach ach beagán de rabhadh cothrom. Níl le beagán de math i gceist anseo. Ceart go leor, mar sin d'fhonn a dhéanamh úsáid a bhaint as ár n-acmhainní ríomhaireachta sa world-- fíor tá sé i ndáiríre tábhachtach a thuiscint halgartaim agus conas a phróiseáil siad sonraí. Má táimid tar éis i ndáiríre algartam éifeachtach, táimid ag Is féidir laghdú ar an méid na n-acmhainní ní mór dúinn ar fáil chun déileáil leis. Má tá algartaim go ag dul a ghlacadh a lán oibre a phróiseáil i ndáiríre sraith mór sonraí, tá sé ag dul a cheangal ar níos mó agus níos mó acmhainní, a Tá airgead, RAM, gach chineál sin de stuif. 

Mar sin, a bheith in ann anailís a ar algartam ag baint úsáide as an tacar uirlis, go bunúsach iarrann, an question-- conas a dhéanann an scála algartam mar chaitheann muid sonraí níos mó agus níos mó ar sé? I CS50, an méid sonraí táimid ag obair le go leor go bhfuil beag. Go ginearálta, is iad ár gcláir ag dul a reáchtáil i an dara nó less-- dócha a lán níos lú go háirithe go luath ar. 

Ach smaoineamh ar cuideachta a dhéileálann leis na céadta milliún na n gcustaiméirí. Agus is gá iad a phróiseáil sonraí do chustaiméirí. Mar líon na gcustaiméirí siad tá faigheann níos mó agus níos mó, tá sé ag dul chun a cheangal acmhainní níos mó agus níos mó. Cé mhéid níos mó acmhainní? Bhuel, braitheann sin ar an gcaoi anailís a dhéanamh againn ar an algartam, ag baint úsáide as na huirlisí seo bosca uirlisí. Nuair a labhairt linn faoi chastacht ar algorithm-- a uaireanta go mbainfidh tú chloisteáil thagair sé mar am castacht nó spás castacht ach táimid ag dul díreach chun glaoch complexity-- muid ag caint go ginearálta faoi an chás is measa. Mar gheall ar an carn glan is measa de sonraí go raibh muid ábalta a bheith ag caitheamh ar sé, gcaoi a bhfuil an algartam ag dul go dtí a phróiseáil nó déileáil le sonraí? Táimid ag glaoch go ginearálta an ceann is measa ar chás runtime de algartaim mór-O. Mar sin d'fhéadfadh algartaim a rá go reáchtáil i O de n nó O de n cearnógach. Agus níos mó faoi cad iad siúd Ciallaíonn sa dara. 

Uaireanta, áfach, a dhéanann muid cúram mar gheall ar an gcás is fearr. Má tá na sonraí a bhíomar ag iarraidh gach rud a é a bheith agus go raibh sé go hiomlán foirfe agus bhí muid a sheoladh seo foirfe sraith sonraí trí mheán ár algartam. Conas a bheadh ​​sé a láimhseáil i staid sin? Tagraímid uaireanta sin mar mór-Omega, mar sin i gcodarsnacht le mór-O, ní mór dúinn mór-Omega. Big-Omega le haghaidh an scéal is fearr ar chás. Big-O don chás is measa. Go ginearálta, nuair a labhairt linn faoi an chastacht algartaim, tá muid ag caint faoi na chás is measa. Mar sin a choinneáil sin san áireamh. 

Agus sa rang seo, táimid ag dul go ginearálta a fhágáil ar an anailís dhian ar leataobh. Tá eolaíochtaí agus réimsí a bheidh dírithe ar an gcineál seo stuif. Nuair a labhairt linn faoi réasúnaíocht trí halgartaim, a beidh orainn píosa-by-phíosa a dhéanamh do go leor halgartaim labhairt linn faoi sa rang. Táimid ag caint faoi i ndáiríre ach réasúnaíocht tríd sé le tuiscint coiteann, ní le foirmlí, nó cruthúnais, nó aon rud mar sin. Mar sin ná bíodh imní ort, ní bheimid casadh i rang math mór. 

Mar sin, dúirt mé cúram againn faoi chastacht toisc go iarrann sé an cheist, conas bhfuil ár halgartaim láimhseáil níos mó agus tacair sonraí níos mó a bheith caite orthu. Bhuel, cad é tacar sonraí? Cad a rinne mé nuair a dúirt mé i gceist go? Ciallaíonn sé cuma cad a dhéanann an chuid is mó ciall i gcomhthéacs, a bheith macánta. Má tá algartaim, an Próisis Strings-- tá muid dócha ag caint faoi an méid de na teaghrán. Sin na sonraí set-- an méid, líon de charachtair a dhéanann suas an teaghrán. Má tá muid ag caint faoi algartam próiseáil comhaid, d'fhéadfadh muid a bheith ag caint faoi conas Cuimsíonn leor cilibheart go comhad. Agus sin an tacar sonraí. Má tá muid ag caint faoi algartam go Láimhseálann arrays níos ginearálta, cosúil le halgartaim sórtáil nó halgartaim cuardach, muid ag caint is dócha mar gheall ar an líon na n-eilimintí a chuimsíonn sraith. 

Anois, is féidir linn a thomhas ar algorithm-- háirithe, nuair a rá liom gur féidir linn a thomhas algartam, mé ciallóidh is féidir linn a thomhas cé go leor acmhainní a thógann sé suas. Cibé an bhfuil na hacmhainní sin, cé mhéad bytes de RAM-- nó meigibheart de RAM úsáideann sé. Nó cé mhéad ama a thógann sé a rith. Agus is féidir linn glaoch seo a thomhas, treallach, f de n. I gcás ina bhfuil n líon na eilimintí sa tacar sonraí. Agus is é f an n cé mhéad somethings. Cé mhéad aonad na n-acmhainní a dhéanann sé a cheangal a phróiseáil na sonraí sin. 

Anois, táimid ag nach bhfuil i ndáiríre cúram faoi ​​cad f de n go díreach. Go deimhin, táimid ag will-- an-annamh Beidh cinnte riamh sa mé class-- Léim isteach in aon ndáiríre go domhain anailís a dhéanamh ar cad f de go bhfuil n. Táimid ag dul díreach chun labhairt faoi na rudaí f de Is n thart nó cad bíonn sé a. Agus is é an claonadh atá algartaim dheachtú ag a théarma ordú is airde. Agus is féidir linn a fheiceáil cad mé Ciallaíonn ag ag cur a breathnú ar sampla níos nithiúla. 

Mar sin, a ligean ar rá go bhfuil muid trí halgartaim éagsúla. Bíonn an chéad cheann a n chiúbaithe, roinnt aonad na n-acmhainní a phróiseáil tacar sonraí de mhéid n. Ní mór dúinn an dara algartam a thógann n chiúbaithe móide acmhainní n cearnógach a phróiseáil tacar sonraí de mhéid n. Agus ní mór dúinn an tríú algartam go ritheann in-- sin Bíonn suas n lúide chiúbaithe 8N cearnógach móide 20 n-aonad na n-acmhainní a phróiseáil algartam le sonraí a leagtar ar mhéid n. 

Anois arís, ní againn i ndáiríre ag dul chun dul isteach ar an leibhéal mionsonraí. Tá mé i ndáiríre ach tá na suas anseo mar léiriú de phointe go bhfuil mé ag dul a bheith dhéanamh sa dara, a is é sin táimid ag cúram ach i ndáiríre mar gheall ar an claonadh na rudaí mar a fháil ar na tacair sonraí níos mó. Mar sin, má tá an tacar sonraí beag, níl i ndáiríre difríocht mór go leor sna halgartaim. An tríú algartam ann Bíonn 13 uair níos faide, 13 uair an méid na n-acmhainní a reáchtáil i gcoibhneas leis an chéad cheann. 

Má tá ár tacar sonraí méid 10, a acu is mó, ach ní gá go mór, Is féidir linn a fheiceáil go níl i ndáiríre le beagán de difríocht. An tríú algartam thiocfaidh chun bheith níos éifeachtaí. Tá sé thart ar 40% i ndáiríre - nó 60% níos éifeachtaí. Bíonn sé 40% an méid ama. Is féidir é a run-- féidir é a ghlacadh 400 aonad na n-acmhainní a phróiseáil tacar sonraí de mhéid 10. De bharr an méid an chéad algartam, ag gcodarsnacht leis sin, Bíonn 1,000 aonad na n-acmhainní a phróiseáil tacar sonraí de mhéid 10. Ach breathnú cad a tharlaíonn mar ár n-uimhreacha a fháil fiú níos mó. 

Anois, an difríocht idir na halgartaim tús a bheith ina beagán níos lú le feiceáil. Agus ar an bhfíric go bhfuil ísealoird terms-- nó in áit, téarmaí exponents-- ísle tús a bheith nach mbaineann le hábhar. Má tá tacar sonraí de mhéid 1,000 agus an chéad algartam Ritheann i billiún céimeanna. Agus ritheann an dara algartam i billiún agus milliún céimeanna. Agus ritheann an tríú algartam i díreach cúthail de billiún céimeanna. Tá sé go leor i bhfad billiún céimeanna. Na téarmaí sin ísealoird tosú a bheith i ndáiríre nach mbaineann le hábhar. Agus díreach go dtí ndáiríre Baile casúr an point-- má tá an t-ionchur sonraí ar mhéid a million-- na trí cinn de na leor i bhfad ghlacadh quintillion-- amháin más rud é Is é mo math céimeanna correct-- a phróiseáil ionchur sonraí de mhéid a milliún. Sin a lán de na céimeanna. Agus ar an bhfíric go d'fhéadfadh duine amháin acu ghlacadh cúpla 100,000, nó lánúin 100 milliún fiú níos lú nuair muid ag caint faoi a PO go big-- tá sé de chineál nach mbaineann le hábhar. Claonadh a bhíonn siad go léir a ghlacadh thart n chiúbaithe, agus mar sin ba mhaith linn a tharchur i ndáiríre do gach ceann de na halgartaim mar ar an ord n chiúbaithe nó mór-O de n chiúbaithe. 

Seo liosta de roinnt de na níos Ranganna castacht ríomhaireachta coitianta go beidh orainn a bhíonn i halgartaim, go ginearálta. Agus freisin go sonrach i CS50. Tá siad seo a ordú ó go ginearálta is tapúla ag an mbarr, chun go ginearálta is moille ag bun an leathanaigh. Mar sin, claonadh a bhíonn halgartaim am tairiseach a bheith ar an tapúla, is cuma de mhéid an ionchur sonraí a théann tú i. Siad a ghlacadh i gcónaí oibriú ceann amháin nó aonad amháin de na hacmhainní chun déileáil leis. D'fhéadfadh sé a bheith 2, d'fhéadfadh sé a 3, d'fhéadfadh sé a bheith 4. Ach tá sé roinnt tairiseach. Ní chuireann sé athrú. 

Halgartaim am logartamach Tá beagán níos fearr. Agus is sampla gur maith algartam am logartamach tú atá le feiceáil surely ag anois go bhfuil an tearing seachas an leabhar teileafóin a fháil Mike Smith sa leabhar teileafóin. Gearrtha againn ar an fhadhb i leath. Agus mar sin mar a fhaigheann níos mó n agus níos mó agus larger-- i ndáiríre, gach uair a dhúbailt tú n, a thógann sé ach céim amháin níos mó. Mar sin tá go bhfuil a lán níos fearr ná, a rá, am líneach. Cé acu is má dúbailte tú n, é a Bíonn dhá oiread líon na céimeanna. Má tá tú triple n, a thógann sé triple líon na céimeanna. Céim amháin in aghaidh an aonaid. 

Ansin rudaí a fháil ar more-- beag beagán níos lú mór ó ann. Tá tú am rhythmic líneach, uaireanta ar a dtugtar logáil uair líneach nó díreach n logáil n. Agus beidh orainn sampla de algartaim a Ritheann i n logáil n, atá fós níos fearr ná chearnach time-- n cearnógach. Nó am polynomial, n beirt aon uimhir níos mó ná dhá. Nó am easpónantúil, a Is fiú worse-- C go dtí an n. Mar sin, roinnt uimhir leanúnach a ardaíodh le an cumhacht ag an méid de na ionchur. Mar sin, má níl 1,000-- má Tá ionchur sonraí de mhéid 1,000, thógfadh sé C chun an chumhacht 1000. Tá sé a lán níos measa ná am polynomial. 

Tá am factorial níos measa fós. Agus go deimhin, tá a dhéanamh i ndáiríre ann halgartaim am gan teorainn, ar nós sort-- dúr mar, mar a thugtar a bhfuil a Is post a Suaitheadh ​​randamach le sraith agus ansin seiceáil a fheiceáil cibé an bhfuil sé curtha in eagar. Agus más rud é nach bhfuil sé, go randamach Suaitheadh ​​an eagar arís agus seiceáil a fheiceáil cé acu tá sé curtha in eagar. Agus mar is féidir leat a imagine-- is dócha Is féidir leat a shamhlú staid nuair is i an ceann is measa ar chás, beidh sin Riamh tús iarbhír leis an eagar. Bheadh ​​sin a algartam a reáchtáil go deo. Agus mar sin a bheadh ​​ina algartam am gan teorainn. Súil go dtosnódh ní bheidh tú ag scríobh aon tráth factorial nó gan teorainn halgartaim i CS50. 

Mar sin, a ligean ar ghlacadh beagán níos mó breathnú coincréite ag roinnt níos simplí ranganna castacht ríomhaireachta. Mar sin, ní mór dúinn example-- nó dhá shampla here-- de halgartaim am tairiseach, a ghlacadh i gcónaí aon oibríocht amháin i an ceann is measa ar chás. Mar sin, an chéad example-- ní mór dúinn a fheidhm iarr 4 do shon, a Bíonn sraith de mhéid 1,000. Ach ansin cosúil nach cuma i ndáiríre ag nach bhfuil it-- cúram i ndáiríre cad atá taobh istigh de sé, de chuid eagar. I gcónaí tuairisceáin ach ceithre. Mar sin, go algartam, in ainneoin go bhfuil sé Bíonn 1,000 Eilimintí nach bhfuil aon ní leo a dhéanamh. Just a tuairisceáin a ceathair. Tá sé i gcónaí aon chéim amháin. 

Go deimhin, cuir 2 nums-- a againn le feiceáil roimh mar well-- ach próisis dhá slánuimhreacha. Níl sé aon chéim amháin. Tá sé i ndáiríre céimeanna cúpla. Fhaigheann tú, gheobhaidh tú b, cuir tú iad le chéile, agus aschur tú na torthaí. Mar sin tá sé 84 céimeanna. Ach tá sé i gcónaí tairiseach, beag beann ar a nó b. Tá tú a fháil a, b fháil, cuir iad le chéile, aschur an toradh. Mar sin, go bhfuil algartam am tairiseach. 

Seo sampla de algorithm-- am líneach algartaim a gets-- go dtógann céim amháin breise, b'fhéidir, mar a fhásann do ionchur ag 1. Mar sin, a ligean ar rá táimid ag lorg an uimhir 5 taobh istigh de eagar. D'fhéadfá a bheith staid ina Is féidir leat é a fháil go luath go cothrom. Ach d'fhéadfadh a bheith agat freisin staid áit a bhfuil sé d'fhéadfadh a bheith ar an ghné dheireanach an eagar. I sraith de mhéid 5, más rud é táimid ag lorg an uimhir 5. Bheadh ​​sé a ghlacadh 5 céimeanna. Agus go deimhin, a shamhlú go níl Ní 5 áit ar bith ar an eagar. Táimid fós i ndáiríre chun breathnú ar gach gné amháin den eagar d'fhonn a chinneadh an bhfuil nó nach 5 ann. 

Mar sin, i an ceann is measa ar chás, a bhfuil go Is é an ghné dheireanach den sraith nó gan a bheith ann ar chor ar bith. Tá muid go fóill chun breathnú ar gach ceann de na heilimintí n. Agus mar sin an algartam Ritheann in am líneach. Is féidir leat a dhearbhú go bhfuil ag a eachtarshuí le beagán ag rá, má bhí againn le sraith 6-eilimint agus bhí muid ag lorg an uimhir 5, d'fhéadfadh sé a ghlacadh 6 céimeanna. Má táimid tar éis sraith 7-eilimint agus táimid ag lorg an uimhir 5. D'fhéadfadh sé a ghlacadh 7 céimeanna. Mar chur linn eilimint amháin níos mó ar ár eagar, a thógann sé céim amháin níos mó. Sin a algartam líneach i an ceann is measa ar chás. 

Lánúin ceisteanna tapaidh ar do shon. Cad é an runtime-- cad atá an ceann is measa ar chás runtime den Blúire áirithe cód? Mar sin, tá mé lúb 4 anseo a ritheann as ionann j 0, léir ar an mbealach suas go dtí m. Agus cad mé ag féachaint anseo é, go bhfuil an Ritheann comhlacht ar an lúb in am tairiseach. Mar sin, ag baint úsáide as an téarmaíocht go tá muid Labhair cheana about-- méid bheadh ​​an ceann is measa ar chás runtime an algartam? Chur ar an dara. An chuid inmheánach den lúb Ritheann in am tairiseach. Agus an chuid amuigh den lúb ag dul a reáchtáil amanna m. Mar sin, cad é an ceann is measa ar chás runtime anseo? An raibh tú buille faoi thuairim mór-O de m? Gur mhaith leat a bheith ceart. 

Cad é faoi a chéile? An uair seo ní mór dúinn a lúb taobh istigh de lúb. Ní mór dúinn lúb seachtrach a ritheann ó náid go p. Agus ní mór dúinn lúb istigh a ritheann ó náid go p, agus taobh istigh de sin, Dearbhaím go bhfuil an comhlacht an Ritheann lúb in am tairiseach. Mar sin, cad é an ceann is measa ar chás runtime den Blúire áirithe cód? Bhuel, arís, ní mór dúinn lúb seachtrach go ritheann amanna p. Agus gach atriall time-- den lúb, in áit. Ní mór dúinn lúb istigh go ritheann freisin amanna p. Agus ansin taobh istigh de sin, níl an Blúire tairiseach time-- beag ann. 

Mar sin má tá lúb amuigh go Ritheann amanna p taobh istigh de a lúb istigh go Ritheann p times-- a bhfuil an ceann is measa ar chás runtime den Blúire de chód? An raibh tú buille faoi thuairim mór-O p cearnógach? 

Tá mé Doug Lloyd. Is é seo an CS50.