[Powered by Google Translate] [Merge Panga] [Rob Bowden - Chuo Kikuu cha Harvard] [Hii ni CS50. - CS50.TV] Hebu majadiliano kuhusu aina kuunganisha. Hadi sasa wewe ve kuonekana Bubble aina, aina insertion, na aina ya uteuzi. Ingawa mimi itabidi aina ya wimbi mkono wangu katika nini maana na bora zaidi, kuchanganya aina ujumla hufanya bora kuliko yoyote ya aina hizi 3. 

Lakini kabla ya kuzungumza juu ya aina kuunganisha, hebu majadiliano juu ya kuunganisha 2 orodha Iliyopangwa. Tutamwita mchakato wa kuchukua 2 orodha Iliyopangwa, kama haya, na kufanya moja sorted orodha nje ya yao - kuunganisha orodha. Tunawezaje kufanya hivyo? Naam, wazo moja ni moja tu fimbo orodha kwenye mwisho wa orodha nyingine na kisha kusababisha aina orodha. 

Wakati kazi hii, ni mengi ya kazi ya lazima. Tunaweza kufanya hivyo kwa kasi zaidi kuliko tu kuchagua. Ona kwamba wazo moja ni makosa kuchukua tu vikombe alternating kutoka orodha ya kila. Wakati kwamba inaweza kuonekana kama kazi ya kwanza, kufanya kwamba sisi kuishia na 4, 8, 15, 23, 16 - ona kwamba 16 na 23 ni nje ya mahali. Hii ni kwa sababu 2 vipengele kwamba inapaswa kuonekana mfululizo katika orodha enheten ni katika orodha hiyo ya awali. Wote 15 na 16 ni katika orodha upande wa kushoto. hila ni kuchukua faida ya ukweli kwamba orodha zote mbili tayari Iliyopangwa. Hii ina maana kwamba kama sisi tu kuangalia mambo ya kwanza ya orodha zote mbili - hapa, 4 na 8 - mmoja wao lazima pia kuwa kipengele kwanza ya orodha enheten. Naam, kwa nini ni hivyo? Wote wa orodha hizi tayari Iliyopangwa, na hivyo aidha 4 au 8 lazima kipengele ndogo wakati sisi kuchanganya orodha 2. Katika kesi hiyo, ndogo ni 4, ili tuweze kuchukua nje 4 na kufanya ni kipengele kwanza ya orodha yetu ya enheten. Sasa tutaendelea kuunganisha iliyobaki vipengele 3 ya orodha ya kwanza na 4 mambo ya orodha ya pili. 

Mara nyingine tena, sisi tu haja ya kuangalia kipengele kwanza ya orodha zote mbili. ndogo ya 2 lazima kipengele pili ya orodha yetu ya enheten. Wakati huu, kati ya 8 na 15 ni ndogo 8, na hivyo sisi Insert kwamba kama kipengele pili ya orodha yetu ya Iliyopangwa. Tunaweza kuendelea kulinganisha mambo ya kwanza ya orodha zote mbili na kuondoa ndogo ya 2. Kulinganisha 15 na 23, 15 ni ndogo na hivyo kuwa wa tatu kipengele yetu. Sasa kulinganisha 16 na 23, 16 ni ndogo. Basi hiyo ni kipengele cha nne. 

Ona kwamba vipengele 2 alikuja kutoka orodha hiyo katika mstari. Hii ni kwa nini orodha enheten hawezi tu mbadala vipengele kutoka orodha 2. Kulinganisha 50 na 23, 23 ni ndogo, hivyo sisi kuchagua kwamba. Kati ya 50 na 42, 42 ni ndogo. Kati ya 50 na 108, 50 ni ndogo. Na, hatimaye, sisi tu 108, hivyo ni lazima kwenda juu ya mwisho wa orodha yetu. Taarifa kwamba tuna nice, Iliyopangwa orodha. Kila wakati sisi ikilinganishwa kwanza vipengele 2 ya orodha 2 tulikuwa na uwezo wa kuamua kipengele kingine cha orodha enheten. Hii ina maana kwamba kama orodha ya mwisho ina idadi n, ambapo n hapa ni 8, basi tunahitaji katika kulinganisha zaidi n kupata yote ya wale idadi ndani ya mahali pa haki. Algorithm vile ni alisema kukimbia katika wakati linear, lakini usijali kuhusu kwamba hapa. 

Kutumia kompyuta yetu kwa kuunganisha, tunaweza kufanya haraka kuunganisha aina algorithm. Hivyo, hebu upya orodha yetu. Kuna hatua kubwa 2 katika mchakato wa aina kuunganisha. Kwanza, kuendelea kupasuliwa orodha ya vikombe katika halves mpaka sisi kuwa na rundo la orodha na kikombe 1 tu katika wao. Usijali kama orodha ina idadi isiyo ya kawaida na huwezi kufanya kukatwa kikamilifu safi kati yao. Tu kiholela pick ambayo kwa pamoja orodha kikombe ziada in Hivyo, hebu kupasuliwa orodha hizi. Sasa tuna orodha 2. Sasa tuna orodha 4. 

Na sasa tuna orodha 8 na kikombe moja katika orodha ya kila. Basi hiyo ni kwa ajili ya hatua 1. Kwa hatua ya 2, sisi kurudia kuunganisha jozi ya orodha ya wagombea kutumia algorithm kuunganisha tulijifunza kabla. Kuunganisha 108 na 15, sisi kuishia na orodha 15, 108. Kuunganisha 50 na 4, sisi kuishia na 4, 50. Kuunganisha 8 na 42, sisi kuishia na 8, 42. Na kuunganisha 23 na 16, sisi kuishia na 16, 23. Sasa wetu orodha zote ni ya kawaida 2. Ona kwamba kila moja ya orodha 4 ni Iliyopangwa. 

Hivyo tunaweza kuanza kuunganisha jozi ya orodha tena. Kuunganisha 15 na 108 na 4 na 50 - kwanza kuchukua 4, kisha 15, kisha 50, kisha 108. Kuunganisha 8, 42 na 16, 23, sisi kwanza kuchukua 8, kisha 16, kisha 23, kisha 42. Hivyo basi, tuna tu 2 orodha ya ukubwa 4, ya kila ambayo ni Iliyopangwa. Hivyo sasa sisi kuunganisha orodha hizi 2. Kwanza sisi kuchukua 4. Kisha sisi kuchukua 8. Kisha sisi kuchukua 15 na 16, kisha 23, kisha 42, kisha 50, kisha 108. Na sisi ni kosa. Sisi sasa kuwa na orodha Iliyopangwa. Hivyo jinsi ya kufunga ilikuwa hii, hasa? Katika suala kiufundi, kuunganisha aina ni O (n logi n), ambapo wote wa Bubble aina, aina insertion, na aina ya uteuzi ni O (n ²). Kwa kweli, kama wewe utakuwa kujifunza haraka, huwezi kuwa na uwezo wa kuja na aina ambayo hufanya bora kuliko O (n logi n) katika kesi ujumla. Tena, msiwe na wasiwasi juu ya nukuu hii kubwa O kama hawajaona bado. 

Tu kujua kwamba hii ina maana kama sisi alitaka aina orodha kubwa kweli kweli Bubble aina, aina insertion, na uteuzi aina inaweza uwezekano kuchukua kikubwa zaidi ya kuunganisha aina. Haina maana kwamba kuunganisha aina itakuwa kasi kwa wote orodha au hata kwa orodha yoyote moja chini ya ukubwa fulani. Kwa mfano, insertion aina inaweza kuwa aina ya haraka sana kwa orodha zote ndogo kuliko vipengele 5. Katika mazoezi, kuunganisha aina ni kawaida kwa kasi kwa orodha ndogo kama vipengele 50. 

Lakini hii kasi ya ziada haina kuja bila gharama. Tofauti na aina yetu nyingine, ambayo kuchukua orodha na kurekebisha orodha katika mahali mpaka sisi kupata orodha Iliyopangwa, kuunganisha aina ya mahitaji ya baadhi nafasi ya ziada kuunganisha orodha 2 pamoja. Hatuwezi mara moja kutumia orodha hiyo ni kuwa zimeunganishwa kuhifadhi orodha enheten tangu tupate override mambo ambayo bado wanahitaji zitachanganywa. Nafasi hii ni kidogo ya bei, lakini ni kawaida ni si unreasonable. Na hiyo ni kwa ajili ya aina kuunganisha. 

Jina langu ni Rob Bowden, na hii ni CS50. [CS50.TV] - Na uteuzi aina. [Atacheka] Oh, got kuchukua nje pia kwa sababu mimi nilikuwa switched jinsi kuwasilisha. Orodha ya upande wa kushoto. Hiyo ilikuwa kosa. [Misspoke] Mimi Star up - [Atacheka] Mimi sijui nini -