[Powered by Google Translate] TOMMY: Ligeann a ghlacadh le breathnú ar saghas a roghnú, algartaim as liosta d'uimhreacha agus sórtáil leo. Tá algartam, cuimhnigh, ach céim-ar-chéim nós imeachta maidir le accomplishing tasc. Is é an smaoineamh bunúsach taobh thiar de chineál roghnaithe a roinnt ár liosta ina dhá chuid - cuid curtha in eagar agus cuid neamhshórtáilte. Ag gach céim den algartam, tá roinnt ar athraíodh a ionad as an chuid neamhshórtáilte leis an gcuid curtha in eagar go dtí deireadh an Tá liosta iomlán curtha in eagar. Mar sin, tá anseo liosta de na sé uimhir - 23, 42, 4, 16, 8, agus 15. Ceart anois go bhfuil an liosta iomlán a mheas neamhshórtáilte. Cé go d'fhéadfadh roinnt mhaith 16 cheana féin ina ceart suíomh, tá ár algartam aon bhealach a fhios agam go dtí go mbeidh an Tá liosta iomlán curtha in eagar. Mar sin, beidh muid ag smaoineamh ar gach uimhir a neamhshórtáilte go dtí go againn a shórtáil é féin. Tá a fhios againn gur mian linn an liosta a bheith in ord ardaitheach. Mar sin, beidh muid ag iarraidh a thógáil suas an chuid eagar ar ár liosta ó chlé go deas, is lú go dtí mó. Chun é sin a dhéanamh, beidh orainn a fháil ar an ghné íosta neamhshórtáilte agus é a chur ag deireadh na coda in eagar. Ós rud é nach bhfuil an liosta seo curtha in eagar, is é an bealach amháin chun é sin a dhéanamh go breathnú ar gach gné sa chuid neamhshórtáilte, cuimhneamh a bhfuil gné is ísle agus comparáid a dhéanamh gach gné leis sin. Mar sin, beidh muid ag breathnú ar dtús ag an 23. Is é seo an chéad eilimint againn le feiceáil, mar sin beidh muid ag cuimhneamh sé mar an t-íosmhéid. Next beidh muid ag breathnú ar 42. 42 Tá níos mó ná 23, mar sin tá 23 fós ar an íosmhéid. Ansin, 4 atá níos lú ná 23, mar sin beidh muid ag cuimhneamh 4 mar an t-íosmhéid nua. Tá Next 16 a bhfuil níos mó ná 4, agus mar sin 4 tá sé fós an t-íosmhéid. 8 Tá níos mó ná 4, agus 15 is mó ná 4, mar sin ní mór 4 a bheith an ghné is lú neamhshórtáilte. Mar sin, cé mar dhaoine féidir linn a fheiceáil láithreach go bhfuil 4 an eilimint is lú, is gá ár n-algartam chun breathnú ar gach gné neamhshórtáilte, fiú tar éis againn fuair an 4 - an eilimint íosta. Mar sin anois go atá againn fuair an ghné íosta, 4, beidh muid ag iarraidh a bhogadh isteach sa chuid curtha in eagar ar an liosta. Ós rud é seo an chéad chéim, ciallaíonn sé seo ba mhaith linn a chur ar 4 ag tús an liosta. Ceart anois tá 23 ag tús an liosta, agus mar sin a ligean ar mhalartú an 4 agus an 23. Mar sin, anois tá ár liosta mar seo. Tá a fhios againn nach mór 4 a bheith ina suíomh deiridh, toisc go bhfuil sé an eilimint is lú agus an ghné ag an tús an liosta. Mar sin, ciallaíonn sé seo go ní mór dúinn riamh a bhogadh arís. Mar sin a ligean arís an próiseas seo go dtí ceann eile eilimint a chur leis an chuid curtha in eagar ar an liosta. Tá a fhios againn nach mór dúinn chun breathnú ar an 4, mar tá sé atá sórtáilte cheana. Mar sin, is féidir linn tús a chur ag 42, a beidh orainn a mheabhrú mar an eilimint íosta. Mar sin, seo chugainn beidh muid ag breathnú ar na 23 atá níos lú ná 42, mar sin againn cuimhneamh 23 Is é an t-íosmhéid nua. Next feicimid an 16 atá níos lú ná 23, agus mar sin Is é 16 an t-íosmhéid nua. Anois táimid ag breathnú ar na 8 atá níos lú ná 16, agus mar sin Is é 8 an t-íosmhéid nua. Agus is é ar deireadh 8 níos lú ná 15, agus mar sin tá a fhios againn go bhfuil 8 ar a laghad eilimint neamhshórtáilte. Mar sin, Ciallaíonn sé sin go mba cheart dúinn 8 fhoscríbhinn leis an eagar chuid den liosta. Ceart anois tá 4 an eilimint amháin a shórtáil, mar sin ba mhaith linn a chur an chéad cheann eile 8 ar an 4. Ós rud é 42 an chéad eilimint sa chuid neamhshórtáilte an liosta, beidh muid ag iarraidh a mhalartú ar an 42 agus an 8. Mar sin, anois tá ár liosta mar seo. 4 agus 8 ionadaíocht a dhéanamh ar an chuid curtha in eagar ar an liosta, agus an ionadaíocht a dhéanamh ar líon na fágtha ar an neamhshórtáilte chuid den liosta. Mar sin a ligean ar aghaidh le chéile leagan. Tús a chur againn le 23 an am seo, ós rud é nach mór dúinn chun breathnú ar an 4 agus an 8 níos mó mar tá siad curtha in eagar cheana féin. Is é 16 níos lú ná 23, mar sin beidh muid ag cuimhneamh 16 mar an t-íosmhéid nua. Is é 16 níos lú ná 42, ach 15 níos lú ná 16, mar sin ní mór 15 a bheith an ghné íosta neamhshórtáilte. Mar sin, anois ba mhaith linn a mhalartú ar an 15 agus an 23 go a thabhairt dúinn an liosta seo. Is éard atá sa chuid curtha in eagar ar an liosta de 4, 8 agus 15, agus na heilimintí neamhshórtáilte go fóill. Ach a tharlaíonn sé ach ionas go mbeidh an ghné seo chugainn neamhshórtáilte, 16, Tá curtha in eagar cheana féin. Mar sin féin, níl aon bhealach le haghaidh ár algartam a fhios go 16 cheana féin a shuíomh i gceart, mar sin ní mór dúinn fós arís go díreach leis an bpróiseas céanna. Mar sin, linn a fheiceáil go bhfuil 16 níos lú ná 42, agus 16 níos lú ná 23, agus mar sin Ní mór a bheith 16 an eilimint is lú. Tá sé dodhéanta a mhalartú ngné seo leis féin, ionas gur féidir linn ach é a fhágáil san áit seo. Mar sin, ní mór dúinn pas amháin níos mó ar ár algartam. 42 níos mó ná 23, mar sin ní mór a bheith 23 ar an eilimint neamhshórtáilte íosta. Chomh luath agus táimid ag mhalartú an 23 agus an 42, ní mór dúinn deireadh suas le lenár deiridh liosta in eagar - 4, 8, 15, 16, 23, 42. Tá a fhios againn ní mór a bheith 42 san áit cheart ó tá sé an eilimint amháin ar chlé, agus sin an saghas roghnaithe. A ligean ar bhonn foirmiúil anois ar ár algartam le roinnt pseudocode. Ar líne amháin, is féidir linn a fheiceáil go bhfuil gá le comhtháthú níos mó gach gné den liosta. Ach amháin an ghné dheireanach, ós rud é an eilimint 1 liosta in eagar cheana féin. Ar líne beirt, ní mór dúinn a mheas an chéad ghné den neamhshórtáilte an chuid sin den liosta go dtí an íosmhéid, mar a rinne muid lenár Mar shampla, ionas go mbeidh muid rud éigin a chur i gcomparáid le. Tosaíonn Líne trí lúb dara ina ndéanaimid iterate thar gach gné neamhshórtáilte. Tá a fhios againn gur tar éis i atriallta, an chuid in eagar Ní mór ar ár liosta ag dúile i ann ó gach céim cineál gné amháin. Mar sin, ní mór an chéad eilimint neamhshórtáilte a bheith i riocht i móide 1. Ar líne ceithre, comparáid idir an eilimint atá ann faoi láthair leis an íosmhéid eilimint go atá feicthe againn go dtí seo. Má tá an eilimint atá ann faoi láthair níos lú ná an íosmhéid eilimint, ansin cuimhin linn an eilimint atá ann faoi láthair mar an nua laghad ar líne a cúig. Mar fhocal scoir, ar línte sé agus seacht, babhtála muid an t-íosmhéid eilimint leis an chéad eilimint neamhshórtáilte, rud a ag cur sé leis an bpáirt curtha in eagar ar an liosta. Nuair a bheidh againn algartaim, ar cheist thábhachtach a iarraidh féin is a ríomhchláraitheoirí cé chomh fada raibh a ghlacadh? Beidh muid a iarraidh ar dtús leis an cheist cé chomh fada a thógfaidh sé ar an algartam a reáchtáil i gcás is measa? Cuimhin ionadaíocht againn seo a rith am le nodaireacht O mór. D'fhonn a chinneadh an ghné íosta neamhshórtáilte, ní mór dúinn go bunúsach go raibh a chur i gcomparáid gach eilimint sa liosta a gach gné eile ar an liosta. Intuitively, fuaimeanna seo cosúil le O oibríochta n cearnógach. Ag Breathnú ar an pseudocode, ní mór dúinn freisin lúb neadaithe taobh istigh eile lúb, a fuaimeanna go deimhin, cosúil le O n oibríocht cearnógach. Mar sin féin, cuimhnigh nach raibh muid gá chun breathnú ar an liosta iomlán nuair a chinneadh an ghné íosta neamhshórtáilte? Chomh luath agus a fhios againn go raibh curtha in eagar an 4, mar shampla, ní raibh muid Ní mór chun breathnú ar sé arís. Mar sin, a dhéanann an níos ísle ar an t-am ag rith? Chun ár liosta de fhad 6, is gá dúinn a dhéanamh ar chúig comparáidí le haghaidh an chéad eilimint, ceithre comparáidí le haghaidh an dara gné, agus mar sin de. Ciallaíonn sé sin go bhfuil líon iomlán na céimeanna agus suim na slánuimhreacha ó 1 go dtí fad an liosta lúide 1. Is féidir linn seo a léiriú le go léir a shuimiú. Ní féidir linn dul i summations anseo. Ach casadh sé amach go bhfuil an tsuimithe cothrom le hamanna n n lúide 1 níos mó ná 2. Nó equivalently, n cearnaithe níos mó ná 2 lúide n níos mó ná 2. Nuair a labhairt faoi runtime asymptotic, an téarma n cearnógach ag dul a tionchar an-mhór an téarma n. Dá bhrí sin tá saghas roghnú O n cearnógach. Glaoch ar ais go in ár mar shampla, is gá saghas rogha fós seiceáil má uimhir a bhí curtha in eagar cheana is gá chun a bhogadh. Mar sin, go Ciallaíonn sé sin má bhí ar siúl againn saghas roghnú thar cheana in eagar liosta, bheadh ​​sé a cheangal ar an líon céanna céimeanna mar a a bheadh ​​á reáchtáil thar liosta go hiomlán neamhshórtáilte. Mar sin, tá saghas roghnú ar fheidhmíocht gcás is fearr de n cearnógach, a dhéanann ionadaíocht againn le óimige n cearnógach. Agus sin é do saghas roghnaithe. Ach ceann amháin de na halgartaim a lán is féidir linn úsáid a shórtáil liosta. Is é mo ainm Tommy, agus tá sé seo cs50.