[Powered by Google Translate] Tá tú éisteacht dócha daoine labhairt faoi algartam tapa nó éifeachtach do forghníomhaitheach do thasc áirithe, ach cad é go díreach a chiallaíonn sé do algartam a bheith tapa nó éifeachtach? Bhuel, ní ag caint é faoi tomhais i bhfíor-am, cosúil soicind nó nóiméad. Tá sé seo toisc crua-earraí ríomhaireachta agus athrú bogearraí go suntasach. D'fhéadfadh mo chlár ar siúl níos moille ná mise, mar go bhfuil mé ag rith sé ar ríomhaire níos sine, nó mar gheall ar a tharlóidh liom a bheith ag imirt cluiche físe ar líne ag an am céanna, a bhfuil hogging gach mo chuimhne, nó a d'fhéadfadh liom a bheith ag rith mo chlár trí mheán bogearraí éagsúla a dhéanann cumarsáid leis an meaisín difriúil ag leibhéal íseal. Tá sé cosúil le comparáid úlla agus oráistí. Díreach mar a thógann mo ríomhaire níos moille níos faide ná mise a thabhairt ar ais le freagra Ní chiallaíonn sé bhfuil tú ar an algartam níos éifeachtaí. 

Mar sin, ós rud é nach féidir linn a chur i gcomparáid go díreach leis an runtimes na gclár i soicind nó nóiméad, conas is féidir linn comparáid a dhéanamh idir 2 halgartaim éagsúla beag beann ar a crua-earraí nó bogearraí timpeallacht? Chun a chruthú ar bhealach níos aonfhoirmí a thomhas éifeachtacht algorithmic, eolaithe ríomhaireachta agus matamaiticeoirí ag ceapadh coincheapa a thomhas an chastacht asymptotic de chlár agus a dtugtar nodaireacht 'Ohnotation Big' chun cur síos seo. Is é an sainmhíniú foirmiúil go fheidhm f (x) Ritheann ar an ord g (x) má tá roinnt luach (x), x ₀ agus roinnt tairiseach, C, a f (x) atá níos lú ná nó cothrom le go leanúnach amanna g (x) le haghaidh gach x níos mó ná x ₀. 

Ach ná a bheith eagla ar shiúl ag an sainmhíniú foirmiúil. Cad a chiallaíonn sé seo i ndáiríre i níos lú ó thaobh teoiriciúil? Bhuel, tá sé go bunúsach ar bhealach a anailísiú cé chomh tapa a fhásann chláir runtime asymptotically. Is é sin, mar a ardaíonn an méid do ionchuir i dtreo Infinity, rá, tá tú ag sórtáil le sraith de mhéid 1000 i gcomparáid le sraith de mhéid 10. Conas a dhéanann an runtime de do chlár fás? Mar shampla, a shamhlú comhaireamh ar líon na carachtair i teaghrán ar an mbealach is simplí  ag siúl tríd an teaghrán iomlán litir-by-litir agus ag cur 1 go cuntar le haghaidh gach carachtair. Tá an algartam sin a reáchtáil in am líneach maidir le líon na gcarachtar, 'N' sa téad. I mbeagán focal, ritheann sé i O (n). Cén fáth go bhfuil seo? Bhuel, ag baint úsáide as an gcur chuige seo, is gá an t-am a thrasnaíonn an teaghrán ar fad Is i gcomhréir leis an líon na gcarachtar. Comhaireamh ar líon na carachtair sa teaghrán 20-charachtar ag dul a ghlacadh dhá uair chomh fada a thógann sé comhaireamh na carachtair i teaghrán 10-charachtar, toisc go bhfuil tú chun breathnú ar na carachtair go léir agus tógann sé gach carachtar ar an méid céanna ama chun breathnú ar. Mar tú méadú ar líon na carachtair, Beidh an runtime méadú líneach le fad ionchur. 

Anois, a shamhlú má shocraíonn tú an am sin líneach, O (n), ní raibh ach go tapa go leor chun tú? B'fhéidir go bhfuil tú ag a stóráil teaghráin ollmhór, agus nach féidir leat acmhainn an t-am breise a bheadh ​​sé a lean go léir a carachtair chomhaireamh aon-le-duine. Mar sin, shocraíonn tú chun iarracht rud éigin difriúil. Cad a tharlaíonn má ba mhaith leat a tharlóidh a stóráil cheana líon na gcarachtar sa téad, a rá, i athróg ar a dtugtar 'LEN,' go luath sa chlár, roimh stóráiltear tú fiú an carachtar an-an chéad i do theaghrán? Ansin, gach gur mhaith leat a dhéanamh anois chun a fháil amach an fad téad, Tá seiceáil cad é luach an athróg. Ní bheadh ​​tú ag féachaint ar an teaghrán féin ar chor ar bith, agus tá sé rochtain a fháil ar an luach a athróg ar nós LEN a mheas oibríocht am asymptotically tairiseach, nó O (1). Cén fáth go bhfuil seo? Bhuel, cuimhneamh ar cad a chiallaíonn chastacht asymptotic. Conas a dhéanann an t-athrú runtime mar an méid de do chuid ionchuir Fásann? 

Abair go raibh tú ag iarraidh a fháil ar líon na carachtair sa teaghrán níos mó. Bhuel, ní bheadh ​​sé cuma cé chomh mór a dhéanann tú an teaghrán, fiú milliún carachtair ar fad, ar fad gur mhaith leat a dhéanamh chun teacht ar an teaghrán ar fad leis an gcur chuige seo, Is é a léamh amach luach an LEN athraitheach, a rinne tú cheana féin. An fad ionchur, is é sin, an fad na sreinge bhfuil tú ag iarraidh a fháil, ní chuireann sé isteach ar chor ar bith cé chomh tapa ritheann do chlár. Chuirfeadh sé seo ar chuid de do chlár a reáchtáil chomh tapa ar shreangán aon-charachtar agus teaghrán míle-charachtar, agus sin an fáth a mbeadh an clár seo a chur faoi bhráid a rith in am i gcónaí maidir leis an méid ionchur. 

Ar ndóigh, níl a aisíoc. Chaitheann tú spás cuimhne breise ar do ríomhaire stóráil an athróg agus an t-am breise a thógann sé ort a dhéanamh ar an stóráil iarbhír an athróg, ach seasann an pointe go fóill, fáil amach cé chomh fada is a bhí do theaghrán nach bhfuil ag brath ar fhad na sreinge ar chor ar bith. Mar sin, ritheann sé i O (1) nó am i gcónaí. Sé seo nach bhfuil cinnte a chiallaíonn a ritheann do chód i 1 chéim, ach is cuma cé mhéad céimeanna atá sé, más rud é nach ndéanann sé athrú leis an méid de na hionchuir, tá sé fós asymptotically leanúnach a dhéanann ionadaíocht againn mar O (1). 

Mar is féidir leat buille faoi thuairim is dócha, tá go leor runtimes éagsúla O mór le halgartaim a thomhas leis. Tá O (n) ² halgartaim asymptotically níos moille ná O (n) halgartaim. Is é sin, mar a fhásann an líon de na gnéithe (n), deireadh thiar beidh O (n) ² halgartaim a ghlacadh níos mó ama ná O (n) halgartaim a rith. Ní chiallaíonn sé seo O (n) halgartaim a reáchtáil i gcónaí níos tapúla ná O (n) ² halgartaim, fiú sa timpeallacht chéanna, ar na crua-earraí céanna. B'fhéidir do mhéideanna ionchur beag,  d'fhéadfadh an O (n) ² algartam obair iarbhír níos tapúla, ach, sa deireadh, méadaíonn an méid ionchur i dtreo Infinity, an (n) O ² algartam ar runtime Beidh eclipse deireadh thiar an runtime de algartam na (n) O. Díreach mar aon fheidhm chearnach matamaiticiúla  Beidh overtake ndeireadh na dála aon fheidhm líneach, Tosaíonn cuma cé mhéad de cheann tús an fheidhm líneach amach le. Má tá tú ag obair le suimeanna móra sonraí, halgartaim a reáchtáil i O (n) Is féidir ² am deireadh ndáiríre suas slowing síos do chlár, ach do mhéideanna ionchur beag, tú nach mbeidh is dócha fiú faoi deara. 

Eile is ea castacht asymptotic, am logartamach, O (log n). Sampla de algartam a ritheann seo go tapa Is é an algartam cuardaigh clasaiceach dhénártha, a aimsiú le haghaidh gné i liosta sórtáilte cheana féin na n-eilimintí. 

Más rud é nach bhfuil a fhios agat cad a dhéanann cuardaigh dénártha, Míneoidh mé é le haghaidh tú i ndáiríre go tapa. Ligean le rá go bhfuil tú ag lorg ar an uimhir 3 sa sraith de slánuimhreacha. Breathnaíonn sé ar an ghné lár an eagar agus iarrann, "An bhfuil an ghné ba mhaith liom níos mó ná, cothrom le, nó níos lú ná seo?" Má tá sé cothrom, ansin mór. Fuair ​​tú an eilimint, agus tú ag déanamh. Má tá sé níos mó, ansin a fhios agat an eilimint tar éis a bheith ar an taobh na láimhe deise den eagar, agus is féidir leat breathnú ach amháin ag an sa todhchaí, agus má tá sé níos lú, ansin a fhios agat tá sé le bheith ar an taobh clé. Tá an próiseas seo arís agus arís eile ansin leis an eagar níos lú-mhéid go dtí go eilimint ceart aimsithe. 

Laghduithe seo ar algartam cumhachtach an méid eagar i leath le gach oibríocht. Mar sin, chun teacht ar an eilimint i sraith curtha in eagar de mhéid 8, ar a mhéad (logáil isteach ₂ 8), nó 3 de na hoibríochtaí sin, Beidh seiceáil an eilimint láir, ag gearradh ansin an sraith ina dhá leath ag teastáil, cé go dtarlaíonn le sraith de mhéid 16 (logáil isteach ₂ 16), nó 4 oibríochtaí. Sin ach 1 oibriú níos mó le haghaidh sraith dhó-mhéid. Dúbailt ar mhéid an eagar Méadaíonn sé seo an runtime ag amháin 1 smután de chód seo. Arís, seiceáil an ghné lár an liosta, ansin scoilteadh. Mar sin, tá sé sin a oibriú i am logartamach, O (log n). Ach go fóill, a deir tú, Ní seo ag brath ar an áit ina bhfuil an liosta an ghné bhfuil tú ag lorg? Cad a tharlaíonn má tharlaíonn an chéad eilimint fhéachann tú ar a bheith ar an ceann ceart? Ansin, ní thógann sé ach 1 oibriú, is cuma cé chomh mór is atá an liosta. 

Bhuel, sin an fáth go bhfuil eolaithe ríomhaire téarmaí níos do chastacht asymptotic a léiríonn an chuid is fearr ar chás agus is measa ar chás léirithe ar algartam. Níos mó i gceart, an bounds uachtaracha agus íochtaracha ar an runtime. I gcás is fearr le haghaidh cuardaigh dénártha, is é ár eilimint ceart ann i lár, agus gheobhaidh tú sé in am i gcónaí, is cuma cé chomh mór is atá an chuid eile den eagar. Is é an tsiombail a úsáidtear le haghaidh an Ω. Mar sin, tá an algartam sin a reáchtáil i Ω (1). I gcás is fearr, fhaigheann sé an eilimint go tapa, is cuma cé chomh mór is atá an eagar, ach i gcás is measa, tá sé a dhéanamh (log n) seiceálacha scoilt an eagar a fháil ar an eilimint ceart. Bounds is measa cás uachtair dá dtagraítear leis an mór "O" go bhfuil a fhios agat cheana féin. Mar sin, tá sé O (log n), ach Ω (1). 

A search líneach, ag gcodarsnacht leis sin, a shiúlann tú trí gach gné den eagar chun teacht ar an ceann is mian leat, ag Ω is fearr (1). Arís, ba mhaith an chéad eilimint tú. Mar sin, ní dhéanann sé cuma cé chomh mór is atá an eagar. Sa chás is measa, tá sé an ghné dheireanach den eagar. Mar sin, tá tú ag siúl trí gach eilimint n sa eagar a fháil air, Is maith má bhí tú ag lorg ar 3. Mar sin, ritheann sé in am O (n) mar tá sé comhréireach leis an líon na n-eilimintí sa eagar. 

Is é ceann siombail níos mó a úsáidtear Θ. Is féidir é seo a úsáid chun cur síos a dhéanamh halgartaim nuair na cásanna is fearr agus is measa mar an gcéanna. Is é seo an cás i na halgartaim teaghrán-fhad phléamar níos luaithe. Is é sin, má táimid é a stóráil i athróg roimh stóráil againn ar an sreang agus rochtain a fháil air ina dhiaidh sin in am i gcónaí. Is cuma cén uimhir táimid ag a stóráil sa athróg, beidh orainn chun breathnú ar sé. Is é an cás is fearr, táimid ag dul dó agus teacht ar an fad na sreinge. Mar sin, Ω (1) nó is fearr chás am tairiseach. Is é an cás is measa, táimid ag dul dó agus a fháil ar an fad na sreinge. Mar sin, O (1) nó am i gcónaí i gcás is measa. Mar sin, tá ós rud é an cás is fearr agus cásanna is measa mar an gcéanna, is féidir é seo a rá a reáchtáil in am Θ (1). 

Go hachomair, ní mór dúinn bealaí dea-chúis faoi éifeachtúlacht cóid gan a fhios agam aon rud faoi an t-am fíor-domhan a ghlacann siad a rith, a bhfuil tionchar ag go leor de na fachtóirí taobh amuigh, lena n-áirítear crua-earraí éagsúla, bogearraí, nó na saintréithe atá ag do chód. Chomh maith leis sin, ligeann sé ar ár gcumas a réasúnú go maith faoi cad a tharlóidh nuair an méid de na méaduithe ionchur. 

Má tá tú ag rith i O algartam (n) ², nó níos measa, a O (2 ⁿ) algartam, cheann de na cineálacha is mó fáis, go mbainfidh tú tús a chur i ndáiríre a thabhairt faoi deara an moilliú nuair a thosaíonn tú ag obair le méideanna níos mó sonraí. 

Sin chastacht asymptotic. Go raibh maith agat.