[Powered by Google Translate] [Infogande Panga] [Tommy MacWilliam] [Chuo Kikuu cha Harvard] [Hii ni CS50.TV] Hebu tuangalie aina insertion, algorithm kwa ajili ya kuchukua orodha ya namba na kuchagua yao. algorithm, kumbuka, ni tu utaratibu wa hatua kwa hatua kwa ajili ya kukamilisha kazi. wazo la msingi nyuma ya aina insertion, ni kugawanya orodha yetu katika sehemu mbili, sehemu sorted na sehemu zisizochambuliwa. 

Katika kila hatua ya algorithm, idadi ni wakiongozwa kutoka sehemu zisizochambuliwa kwa sehemu sorted mpaka hatimaye orodha nzima ni Iliyopangwa. Hapa ni orodha ya namba sita zisizochambuliwa - 23, 42, 4, 16, 8, na 15. Tangu hizi namba ni si wote katika wakipanda ili, wao ni zisizochambuliwa. Tangu sisi si kuanza kuchagua bado, tutaweza kufikiria yote vipengele sita sehemu yetu zisizochambuliwa. 

Mara sisi kuanza kuchagua, tutaweza kuweka namba hizi sorted ya kushoto ya haya. Hivyo, hebu kuanza na 23, kipengele kwanza katika orodha yetu. Hatuna mambo yoyote katika sehemu yetu ya sorted bado, hivyo hebu fikiria tu 23 kuwa mwanzo na mwisho wa sehemu yetu ya Iliyopangwa. Sasa, sehemu yetu ina Iliyopangwa namba moja, 23, na sehemu yetu zisizochambuliwa ina namba hizi tano. Hebu sasa Insert namba inayofuata katika sehemu yetu ya zisizochambuliwa, 42, katika sehemu Iliyopangwa. 

Kwa kufanya hivyo, tutaweza haja ya kulinganisha 42-23 - kipengele tu katika sehemu yetu ya sorted hivyo mbali. Arobaini na mbili ni kubwa kuliko 23, ili tuweze tu append 42 hadi mwisho ya fungu sorted ya orodha. Mkuu! Sasa sehemu yetu sorted ina mambo mawili, na sehemu yetu zisizochambuliwa una mambo manne. Hivyo, hebu sasa hoja ya 4, kipengele ijayo katika sehemu zisizochambuliwa. Hivyo, ambapo lazima hii kuwekwa katika fungu sorted? 

Kumbuka, tunataka kuweka namba hii ili sorted hivyo sehemu yetu sorted bado usahihi sorted wakati wote. Tukiweka 4 na haki ya 42, basi orodha yetu itakuwa nje ya utaratibu. Hivyo, hebu kuendelea kusonga kulia-hadi-kushoto katika aina sehemu yetu. Kama sisi hoja, hebu kuhama kila idadi chini mahali kufanya chumba kwa idadi mpya. Okay, 4 pia ni chini ya 23, hivyo hatuwezi kuiweka hapa aidha. Hebu hoja 23 haki ya mtu mahali. 

Hiyo ina maana tunatarajia kuweka 4 katika yanayopangwa kwanza katika sehemu Iliyopangwa. Angalia jinsi hii nafasi katika orodha ilikuwa tayari tupu, kwa sababu tumekuwa kusonga vipengele sorted chini kama tumekuwa wamekutana yao. Wote haki. Hivyo, sisi ni nusu ya huko. Wacha tuendelee algorithm yetu kwa kuingiza 16 katika sehemu Iliyopangwa. Kumi na sita ni chini ya 42, hivyo hebu kuhama 42 ya kulia. Kumi na sita pia ni chini ya 23, hivyo hebu pia kuhama kwamba kipengele. 

Sasa, 16, ni mkubwa kuliko 4. Hivyo, inaonekana kama tunatarajia kuingiza 16 kati ya 4 na 23. Wakati kusonga kupitia sehemu ya orodha Iliyopangwa kutoka kulia kwenda kushoto, 4 ni idadi ya kwanza tumeona kwamba ni ndogo kuliko idadi ya sisi ni kujaribu kuingiza. Hivyo, sasa tunaweza Insert 16 katika yanayopangwa hii tupu, ambayo, kumbuka, tumekuwa umba na mambo kusonga katika sehemu aina zaidi ya kama tumekuwa wamekutana yao. 

Wote haki. Sasa, tuna nne vipengele sorted na mbili vipengele zisizochambuliwa. Hivyo, hebu hoja 8 katika sehemu Iliyopangwa. Nane ni chini ya 42. Nane ni chini ya 23. Na 8 ni chini ya 16. Lakini 8, ni mkubwa kuliko 4. Hivyo, tunatarajia kuingiza 8 kati ya 4 na 16. Na sasa sisi tu moja zaidi ya kipengele kushoto kutatua - 15. Kumi na tano ni chini ya 42, Kumi na tano ni chini ya 23. Na 15 ni chini ya 16. Lakini 15 ni mkuu zaidi kuliko 8. 

Kwa hiyo, hapa ni mahali ambapo tunataka kufanya insertion yetu ya mwisho. Na sisi ni kosa. Tuna mambo tena katika sehemu zisizochambuliwa, na sehemu yetu ni Iliyopangwa katika mpangilio sahihi. idadi ni amri kutoka wadogo na ukubwa. Hivyo, hebu tuangalie baadhi pseudocode kwamba inaelezea hatua sisi tu kutumbuiza. 

On line 1, tunaweza kuona kwamba tutaweza haja ya iterate juu ya kila kipengele katika orodha ila kwanza, tangu kipengele kwanza katika sehemu zisizochambuliwa mapenzi tu kuwa kipengele kwanza katika sehemu Iliyopangwa. Juu ya mistari 2 na 3, sisi ni kuweka wimbo wa nafasi yetu ya sasa katika sehemu zisizochambuliwa. Kipengele inawakilisha idadi sisi sasa kuhamia katika sehemu Iliyopangwa, na j inawakilisha index yetu katika sehemu zisizochambuliwa. 

On line 4, tuko iterating kupitia sehemu sorted kutoka kulia kwenda kushoto. Tunataka kukomesha iterating mara moja kipengele upande wa kushoto wa msimamo wetu wa sasa ni chini ya kipengele sisi ni kujaribu kuingiza. On line 5, sisi ni shifting kila kipengele sisi kukutana moja nafasi ya kulia. Kwa njia hiyo, tutaweza kuwa na nafasi ya wazi ya kuingiza katika wakati sisi kupata kipengele kwanza chini ya kipengele tuko kusonga mbele. On line 6, sisi ni uppdatering counter yetu kuendelea kwa hoja kushoto kupitia sehemu Iliyopangwa. Hatimaye, katika mstari wa 7, sisi ni kuingiza kipengele katika sehemu sorted ya orodha. 

Tunajua kwamba ni sawa na kuingiza ndani ya j nafasi, kwa sababu tumekuwa tayari wakiongozwa kipengele kwamba kutumika kuwa kuna nafasi moja ya kulia. Kumbuka, sisi ni kusonga kupitia sehemu sorted kutoka kulia kwenda kushoto, lakini sisi ni kusonga kupitia sehemu zisizochambuliwa kutoka kushoto kwenda kulia. Wote haki. Hebu sasa tuangalie jinsi ya muda mrefu mbio kwamba alichukua algorithm. Tutaweza kwanza kuuliza swali jinsi gani kuchukua muda mrefu kwa algorithm hii na kukimbia katika hali mbaya. Kumbuka kwamba sisi kuwakilisha hii wakati mbio na nukuu Kubwa O. Ili aina orodha yetu, tulikuwa na iterate juu ya vipengele katika sehemu zisizochambuliwa, na kwa kila moja ya mambo hayo, uwezekano juu ya mambo yote katika sehemu Iliyopangwa. Intuitively, hii inaonekana kama operesheni O (n ^ 2). 

Kuangalia pseudocode yetu, tuna kitanzi nested ndani ya kitanzi mwingine, ambayo, kwa hakika, inaonekana kama operesheni O (n ^ 2). Hata hivyo, sehemu ya orodha Iliyopangwa hakuwa vyenye orodha nzima mpaka mwisho sana. Hata hivyo, sisi inaweza uwezekano Insert kipengele mpya mwanzoni mwa sehemu sorted juu ya kila iteration ya algorithm, ambayo ina maana kwamba tunatarajia kuwa na kuangalia kila kipengele sasa katika sehemu Iliyopangwa. Hivyo, hiyo ina maana sisi inaweza uwezekano kufanya moja kulinganisha kwa kipengele cha pili, mbili kulinganisha kwa kipengele cha tatu, na kadhalika. Hivyo, 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 n (n - 1) zaidi ya 2, ambayo ni sawa n ^ 2/2 - n / 2. Tunapozungumzia Runtime asymptotic, n ^ 2 mrefu ni kwenda kutawala muda huu n. Hivyo, insertion aina ni Kubwa O (n ^ 2). Nini kama sisi mbio insertion aina katika orodha tayari Iliyopangwa. Katika kesi hiyo, tunatarajia tu kujenga sehemu sorted kutoka kushoto kwenda kulia. Hivyo, tutaweza tu haja juu ya utaratibu wa hatua n. 

Hiyo ina maana kwamba insertion aina ina utendaji bora-kesi ya n, ambayo sisi kuwakilisha kwa Ω (n). Na hiyo ni kwa ajili ya aina insertion, moja tu ya algorithms wengi tunaweza kutumia aina orodha. Jina langu ni Tommy, na hii ni CS50. [CS50.TV] Oh, wewe tu hawezi kuacha kuwa mara kinapoanza. Oh, sisi gani kwamba - >> Boom!