[Powered by Google Translate] [Kunfandi Ordigi] [Rob Bowden - Universitato Harvard] [Jen CS50. - CS50.TV] Ni parolos pri merge varon. Ĝis nun vi vidis bobelo varo, inserción varo, kaj selektado varon. Kvankam Mi instruos vin speco de ondo mian manon je kio mi aludas per bona, kunfandi speco ĝenerale plenumas pli bone ol iu el tiuj 3 varoj. 

Sed antaŭ parolas merge varo, ni parolu pri kunfandi 2 ordo listoj. Ni vokos la procezo de prenante 2 ordo lertaj, kiel ĉi tiuj, kaj farante sola ordo listo el ili - kunfandi la listoj. Kiel ni povas fari ĉi tion? Nu, unu ideo estas simple resti unu listo sur la fino de la alia listo kaj poste ordigi la rezultan liston. 

Dum ĉi tiu funkcias, estas multe da nenecesaj laboro. Ni povas fari ĝin pli rapide ol nur ordigi. Rimarku ke unu malĝustan ideo estas simple preni alternaj tasojn el ĉiu listo. Dum kiu povas simili ke verkoj unue, faras ke ni finos kun 4, 8, 15, 23, 16 - avertas ke 16 kaj 23 estas maloportune. Ĉi tiu estas ĉar 2 eroj kiuj devus aperi sinsekvaj en la kunfandita listo estas en la sama komenca listo. Ambaŭ 15 kaj 16 estas en la listo maldekstre. La artifiko estas utiligi la fakton ke ambaŭ listoj jam ordo. Tio signifas ke se oni nur rigardas la unuajn elementojn de ambaŭ listoj - tie, 4 kaj 8 - unu el ili devas ankaŭ esti la unua elemento de la kunfandita listo. Nu, kial estas tio? Ambaŭ ĉi tiuj listoj jam ordo, kaj tiel aŭ 4 aŭ 8 devas esti la plej malgranda ero, kiam ni kombini la 2 listojn. En ĉi tiu kazo, la plej malgranda estas 4, tiel ni povas preni el 4 kaj faru ĝin la unua elemento de nia kunfandis listo. Nun ni daŭrigas kunfandi la ceteraj 3 elementoj de la unua listo kaj 4 eroj de la dua listo. 

Denove, ni nur bezonas rigardi la unua elemento de ambaŭ listojn. La plej malgranda el la 2 devas esti la dua elemento de nia kunfandis listo. Ĉi-foje, inter 8 kaj 15 la plej malgranda estas 8, kaj tial ni enŝovu ke kiel la dua ero de nia ordo listo. Ni povas daŭrigi kompari la unua elementoj de ambaŭ listoj kaj forigante la plej malgranda el la 2. Komparante 15 kaj 23, 15 estas pli malgranda kaj por ke la nia tria elemento. Nun kompari 16 kaj 23, 16 estas pli malgranda. Do jen la kvara elemento. 

Rimarku ke 2 eroj venis de la sama listo en vico. Jen kial la kunfandita listo ne povas simple alternaj elementoj de la 2-listoj. Komparante 50 kaj 23, 23 estas pli malgranda, do ni elektu kiun. Inter 50 kaj 42, 42 estas pli malgranda. Inter 50 kaj 108, 50 estas pli malgranda. Kaj, fine, ni nur devas 108, do ĝi devas iri en la fino de nia listo. Rimarku ke ni havas belan, ordo listo. Ĉiufoje ni komparis la unuaj 2 eroj de la 2 listojn ni povis determini la sekvanta elemento de la kunfandita listo. Tio signifas, ke se la fina listo enhavas n nombroj, kie n tie estas 8, tiam ni bezonas maksimume n komparoj preni ĉiun el tiuj nombroj en la ĝustan lokon. Tia algoritmo estas dirita por kuri en lineara tempo, sed ne maltrankviliĝu pri tio ĉi tie. 

Uzanta nia algoritmo por kunfandi, ni povas fari rapidan merge speco algoritmo. Do, ni retrovu niaj listoj. Estas 2 grandaj paŝoj en la procezo de merge varon. Unue, senĉese fendi la listo de tasojn en duonoj gxis ni havas amason da listoj kun nur 1 taso en ili. Ne maltrankviliĝu, se listo enhavas nepara nombro kaj vi ne povas fari perfekte pura kortego inter ili. Nur arbitre elekti kio listo por inkludi la ekstra tason in Do, ni fendi tiuj listoj. Nun ni havas 2 listojn. Nun ni havas 4 listoj. 

Kaj nun ni havas 8 lertaj kun sola tason en ĉiu listo. Do jen ĝi por paŝo 1. Por paŝo 2, ni ree kunfandi paroj de lertaj uzanta la merge algoritmo ni lernis antaŭe. Kunfandi 108 kaj 15, ni finos kun la listo 15, 108. Kunfandi 50 kaj 4, ni finos kun 4, 50. Kunfandi 8 kaj 42, ni finos kun 8, 42. Kaj kunfandi 23 kaj 16, ni finos kun 16, 23. Nun ĉiuj niaj listoj estas de amplekso 2. Rimarki, ke ĉiu el la 4 listoj estas ordigitaj. 

Do ni povas starti kunfandi paroj de lertaj denove. Kunfandi 15 kaj 108 kaj 4 kaj 50 - eligu unue la 4, tiam la 15, tiam la 50, tiam la 108. Kunfandi 8, 42 kaj 16, 23, ni unue prenas la 8, tiam la 16, tiam la 23, tiam la 42. Do nun ni havas nur 2 listojn de grandeco 4, ĉiu el kiuj estas ordo. Do nun ni kunfandi tiuj 2 listojn. Unue ni prenas la 4. Tiam ni prenos la 8. Tiam ni prenos la 15 kaj 16, tiam 23, do 42, tiam 50, do 108. Kaj ni faris. Ni nun havas ordo listo. Do kiom rapide estis jena ĝuste? En teknika terminoj, merge varo estas O (n log n), dum kiu ĉiuj de bobelo varo, inserción varo, kaj selektado varo estas O (n ²). Fakte, kiel vi lernos baldaŭ, vi ne povos veni supren kun ia kiu realigas bona ol O (n logo n) en la ĝenerala kazo. Denove, ne zorgu pri tiu granda a skribmaniero se vi ne vidis ĝin ankoraŭ. 

Nur scias, ke ĉi tio signifas se ni volis ordigi vere granda listo bobelo varo, inserción varo, kaj selektado speco povus potenciale preni signife pli longa ol kunfandi varon. Ĝi ne signifas ke merge speco estos pli rapida por ĉiuj listoj aŭ eĉ iun ajn simpla listo sub certa grandeco. Ekzemple, inserción speco povus esti la plej rapida varo por ĉiuj listoj malgranda ol 5 elementoj. En praktiko, merge varo estas kutime rapida por lertaj kiel malgranda kiel 50 eroj. 

Sed ĉi tiu ekstra rapido ne venas sen prezo. Kontraste niaj aliaj varoj, kiujn prenas listo kaj modifi la liston en loko ĝis ni preni ordo listo, merge speco bezonas plian spacon kunfandi 2 listojn kune. Ni ne povas tuj uzi la listojn kiuj estas kunfandita por stoki la kunfandita listo ĉar ni povus nuligi elementoj kiuj ankoraŭ bezonas esti kunfandita. Ĉi tiu spaco estas iom el la prezo, sed kutime ne estas senkaŭza. Kaj tio estas por merge varon. 

Mia nomo estas Rob Bowden, kaj ĉi tiu estas CS50. [CS50.TV] - Kaj selektado varon. [Ridas] Ho, alvenis al tiu el tro ĉar mi ŝanĝis kiom mi prezenti gxin. Listo maldekstre. Tio estis eraro. [Misspoke] Mi ŝraŭbita supren - [Ridas] Mi ne scias, kion -