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