[Powered by Google Translate] Tommy: Hebu tuangalie aina ya uteuzi, algorithm
kwa ajili ya kuchukua orodha ya namba na kuchagua yao.
algorithm, kumbuka, ni tu hatua kwa hatua
utaratibu kwa ajili ya kukamilisha kazi.
wazo la msingi nyuma ya aina uteuzi ni ya kugawanya
orodha yetu ya ndani ya sehemu mbili -
sehemu sorted na sehemu zisizochambuliwa.
Katika kila hatua ya algorithm, idadi ni wakiongozwa kutoka
zisizochambuliwa fungu kwa fungu sorted mpaka hatimaye
orodha nzima ni Iliyopangwa.
Hivyo hapa ni orodha ya namba sita -
23, 42, 4, 16, 8, na 15.
Hivi sasa orodha nzima ni kuchukuliwa zisizochambuliwa.
Hata ingawa idadi kama Mei 16 tayari katika sahihi yake
mahali, algorithm wetu hana njia ya kujua kwamba mpaka
orodha nzima ni Iliyopangwa.
Hivyo tutaweza kufikiria kila idadi kuwa zisizochambuliwa mpaka sisi wachambue
ni sisi wenyewe.
Tunajua kwamba tunataka kuwa katika orodha wakipanda utaratibu.
Hivyo tutaweza wanataka kujenga sehemu sorted ya orodha yetu ya
kutoka kushoto kwenda kulia, ndogo kwa ukubwa.
Ili kufanya hivyo, tutaweza haja ya kutafuta chini ya kipengele zisizochambuliwa
na kuiweka katika mwisho wa sehemu Iliyopangwa.
Tangu orodha hii si sorted, njia pekee ya kufanya hivyo ni
kuangalia kila kipengele katika sehemu zisizochambuliwa, wakikumbuka
ambayo ni kipengele cha chini na kulinganisha
kila kipengele kwamba.
Hivyo tutaweza kwanza tuangalie 23.
Hii ni kipengele kwanza tumeona, hivyo tutaweza kukumbuka
ni kama kima cha chini.
Next tutaangalia 42.
42 ni kubwa kuliko 23, hivyo ni 23 bado kiwango cha chini.
Next ni 4 ambayo ni chini ya 23, hivyo tutaweza kumbuka 4
kama kima cha chini mpya.
Next ni 16 ambayo ni kubwa kuliko 4, hivyo 4
bado ni kiwango cha chini.
8 ni kubwa kuliko 4, na 15 ni kubwa kuliko 4, hivyo lazima 4
ndogo zisizochambuliwa kipengele.
Hivyo ingawa kama binadamu tunaweza mara moja kuona kwamba ni 4
kipengele cha chini, algorithm mahitaji yetu ya kuangalia
kila kipengele zisizochambuliwa, hata baada ya sisi Nimepata 4 -
kima cha chini ya kipengele.
Hivyo sasa kwamba tumekuwa kupatikana kipengele cha chini, 4, tutaweza wanataka
kwa hoja ndani ya fungu sorted ya orodha.
Tangu hii ni hatua ya kwanza, hii ina maana tunataka kuweka 4 katika
mwanzo wa orodha.
Hivi sasa ni 23 wakati wa mwanzo wa orodha, hivyo
hebu wabadilishane 4 na 23.
Hivyo sasa orodha yetu inaonekana kama hii.
Tunajua kwamba 4 lazima kuwa katika eneo lake la mwisho, kwa sababu ni
wote kipengele ndogo na kipengele mwanzoni
ya orodha.
Hivyo hii ina maana kwamba sisi si milele haja ya hoja hiyo tena.
Basi hebu kurudia utaratibu huu kwa kuongeza mwingine kipengele kwa
Iliyopangwa sehemu ya orodha.
Tunajua kwamba hatuna haja ya kuangalia 4, kwa sababu ni
tayari Iliyopangwa.
Hivyo tunaweza kuanza saa 42, ambayo tutaweza kumbuka kama
kima cha chini ya kipengele.
Hivyo ijayo tutaangalia 23 ambayo ni chini ya 42, hivyo sisi
kumbuka ni kiwango cha chini 23 mpya.
Next sisi kuona 16 ambayo ni chini ya 23, hivyo
16 ni kiwango cha chini mpya.
Sasa tunaangalia 8 ambayo ni chini ya 16, hivyo
8 ni kima cha chini mpya.
Na hatimaye 8 ni chini ya 15, hivyo tunajua kwamba ni kima cha chini cha 8
zisizochambuliwa kipengele.
Hivyo kwamba maana tunapaswa append 8 kwa sorted
sehemu ya orodha.
Hivi sasa ni kipengele 4 tu sorted, hivyo tunataka kuweka
Ijayo 8-4.
Tangu 42 ni kipengele kwanza katika sehemu ya zisizochambuliwa
orodha, tutaweza wanataka wabadilishane 42 na 8.
Hivyo sasa orodha yetu inaonekana kama hii.
4 na 8 kuwakilisha sehemu sorted ya orodha, na
iliyobaki idadi kuwakilisha zisizochambuliwa
sehemu ya orodha.
Basi hebu kuendelea na iteration mwingine.
Tunaweza kuanza na 23 wakati huu, kwa vile hatuna haja ya kuangalia
4 na 8 tena kwa sababu wameweza
tayari Iliyopangwa.
16 ni chini ya 23, hivyo tutaweza kukumbuka
16 kama kiwango cha chini mpya.
16 ni chini ya 42, lakini 15 ni chini ya 16, hivyo 15 lazima
kima cha chini cha zisizochambuliwa kipengele.
Hivyo sasa tunataka wabadilishane 15 na 23 kwa
kutupatia orodha hii.
sehemu ya orodha Iliyopangwa lina 4, 8 na 15, na
mambo haya bado zisizochambuliwa.
Lakini tu hivyo hutokea kwamba ijayo zisizochambuliwa kipengele, 16,
tayari Iliyopangwa.
Hata hivyo, hakuna njia kwa algorithm yetu ya kujua kwamba 16
ni tayari katika eneo lake sahihi, hivyo bado tunahitaji
kurudia hasa mchakato huo.
Hivyo tunaona kuwa 16 ni chini ya 42, na 16 ni chini ya 23, hivyo
16 lazima kipengele cha chini.
Ni vigumu wabadilishane hii kipengele kwa yenyewe, ili tuweze
tu kuondoka katika eneo hili.
Hivyo tunahitaji moja zaidi kupita ya kompyuta yetu.
42, ni mkubwa kuliko 23, hivyo 23 lazima
kima cha chini cha zisizochambuliwa kipengele.
Mara sisi byta 23 na 42, sisi kuishia na mwisho wetu
Iliyopangwa orodha -
4, 8, 15, 16, 23, 42.
Tunajua 42 lazima kuwa katika mahali sahihi tangu ni
kipengele tu kushoto, na kwamba ni uteuzi aina.
Hebu sasa kurasimisha algorithm wetu na baadhi ya
pseudocode.
On line moja, tunaweza kuona kuwa tunahitaji kuunganisha juu ya
kila kipengele cha orodha.
Isipokuwa kipengele mwisho, tangu kipengele 1
orodha tayari Iliyopangwa.
On line mbili, tunaona kipengele kwanza ya zisizochambuliwa
sehemu ya orodha ya kuwa kima cha chini, kama tulivyofanya kwa wetu
mfano, hivyo tuna kitu kulinganisha na.
Line tatu huanza kitanzi pili ambayo sisi iterate juu ya
kila kipengele zisizochambuliwa.
Tunajua kwamba baada i iterations, fungu sorted
ya orodha yetu lazima i vipengele ndani yake tangu kila hatua
aina moja ya kipengele.
Hivyo kwanza kipengele zisizochambuliwa lazima kuwa katika nafasi i plus 1.
On line nne, sisi kulinganisha kipengele sasa kwa kiwango cha chini
kipengele kwamba tumekuwa kuona hadi sasa.
Kama kipengele sasa ni ndogo kuliko kima cha chini cha
kipengele, basi sisi kukumbuka kipengele sasa kama mpya
kima cha chini kwenye mstari tano.
Hatimaye, kwa mistari sita na saba, sisi byta kima cha chini cha
kipengele kwa kipengele kwanza zisizochambuliwa, na hivyo
akiongeza kuwa sehemu ya orodha Iliyopangwa.
Mara tuna algorithm, swali muhimu kuuliza
wenyewe kama programmers ni muda gani ili kuchukua?
Tutaweza kwanza kuuliza swali jinsi gani kuchukua muda mrefu kwa ajili ya hii
algorithm kukimbia katika hali mbaya?
Wanakumbuka sisi kuwakilisha hii mbio
muda na nukuu kubwa O.
Ili kuamua kiwango cha chini zisizochambuliwa kipengele, sisi
kimsingi alikuwa kulinganisha kila kipengele katika orodha ya
kila kipengele nyingine katika orodha.
Intuitively, hii inaonekana kama O ya operesheni n squared.
Kuangalia pseudocode yetu, sisi pia kuwa kitanzi nested ndani ya
mwingine kitanzi, ambayo kwa hakika inaonekana kama O
ya n operesheni squared.
Hata hivyo, kumbuka kwamba sisi hakuwa na haja ya kuangalia juu ya
nzima orodha wakati kuamua kiwango cha chini zisizochambuliwa kipengele?
Mara sisi alijua kwamba alikuwa 4 sorted, kwa mfano, hatukuwa
haja ya kuangalia tena.
Hivyo gani hii chini wakati mbio?
Kwa orodha ya urefu 6, sisi zinahitajika ili kufanya tano
kulinganisha kwa kipengele kwanza, nne kulinganisha kwa
kipengele cha pili, na kadhalika.
Hiyo ina maana kwamba idadi ya jumla ya hatua ni jumla ya
integers kutoka 1 kwa urefu wa orodha minus 1.
Tunaweza kuwakilisha jambo hili kwa summation.
Sisi si kwenda katika summations hapa.
Lakini zinageuka kuwa summation hii ni sawa na mara n
n minus 1 juu ya 2.
Au equivalently, n squared zaidi ya 2 bala n zaidi ya 2.
Tunapozungumzia Runtime asymptotic, hii n squared mrefu
ni kwenda kutawala muda huu n.
Hivyo uteuzi aina ni O ya n squared.
Kumbuka kwamba katika mfano wetu, uteuzi aina bado zinahitajika
kuangalia kama namba kwamba alikuwa tayari sorted
zinahitajika kuwa wakiongozwa.
Hivyo kwamba ina maana kwamba kama sisi mbio uteuzi aina zaidi ya tayari
Iliyopangwa orodha, ni itahitaji idadi sawa ya hatua kama
ingekuwa wakati wa mbio juu ya orodha kabisa zisizochambuliwa.
Hivyo uteuzi aina ana bora kesi ya utendaji ya n squared,
ambayo sisi kuwakilisha na omega n squared.
Na hiyo ni kwa ajili ya aina ya uteuzi.
Moja tu ya algorithms wengi tunaweza
kutumia aina orodha.
Jina langu ni Tommy, na hii ni cs50.