[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.