SPEAKER: Bone, tiu estas CS50. Jen la fino de semajno tri, kaj se vi ne eluzis jam, scias ke estos tagmanĝo tiu vendredo kiel kutime, kie Vi povas ĝui bonan konversacion kaj manĝo ĉe Fajro kaj Ice kun kelkaj el CS50 La bastonon kaj samklasanoj. Estrus al tiu URL tie. Nun vi eble memoras, aŭ vi eble baldaŭ povos kompreni, tion ĉi tie, kiuj estas donita fine de la semestro por multaj klasoj. Tn ekzameno bluaj libroj, en kiuj vi skribas viajn respondojn al la ekzamenoj. Nun mi havas tie 26 tiajn bluaj libroj, sur ĉiu el ili Estas skribita nomo, A tra Z. Kaj ja la nomoj estas ke simpla, A tra Z. El la celoj proksimigxis hodiaŭ tuj estos daŭrigi kion ni komencis lunde, kiu ne estas tiel rigardante kodon, sed vere rigardas ideoj kaj problemo solvita. Unu el la celoj kaj promesoj de tiu kurso estas instrui vin pensi pli zorge, pli metode, kaj solvi problemojn pli efike. Kaj efektive, ni povas fari, ke vere sen eĉ tuŝi linion de kodo. Do mi havas kelkaj elefantoj tien hodiaŭ, oranĝa kaj blua, se ni povus atingi unu volontulo, eble el malantaux ol kutime. Kiom proksimume dekstra tie, venu malsupren. La celo de kio tuj estos al helpi plus administri ĉi ekzamenon tie. Kio estas via nomo? Publiko: Mary Beth. SPEAKER: Mary Beth, venu supren. Lasu min eltiri la mikrofono tie por vi. Agrable renkonti vin. Publiko: Nice to meet you. SPEAKER: Bone, do mi devas jen bluaj libroj A tra Z kaj mi tuj ŝajnigas ke Mi havas unu el la studentoj, kaj ili estas eniranta iom hazarde ĉe la fino de tri horo ekzamenon bloko, Do oni finas en iu duon-hazarda ordo kiel ĉi. Nun via laboro en nur momento tuj al be-- ĉi estas vere kiel akiri turnis al la fino de la klaso, verŝajne. Via tasko nun tuj estos, tute simple, ordigi tiujn bluajn librojn por ni de A tra Z Publiko: Ho, tio estas tuj prenos ĉiam. SPEAKER: Kaj ni viglu kiel vi faras tion, sen premo. Publiko: Ne, ne premon aŭ nenion. SPEAKER: Kaj por amuzo, ni starigis temporizador. Publiko: Tiom amuza, tiel amuza. SPEAKER: Mi povas teni la mic por vi. Bone, ni jhus duobliĝis nia rapido. Do intertempe, lasu min supozi kio estas tuj estos la demandon por Mary Beth estas kio ŝi faras, kiel estas ŝi rondirante solvanta ĉi? Kaj fakte, vi eble ne havas iam pensis pri io tiel simpla kiam vi elektu ĝis 26 libroj kiel tiu, kiu do havas naturan ordigante ilin. Kio estas la procezo ke vi vere uzas? Ĉu sufiĉe hazarda simple prenante la unua vi vidos kaj metante ĝin en lia loko? Ĉu vi unue movi viajn manojn ĉirkaŭ serĉi A tiam serĉi B? Ĉu vi rigardu al paro de ili flankon ĉe flanko kaj simple diri, atendu minuton, tiu ne estas rajto, kaj tiam interŝanĝi la ordon? Ni vidis jam lunde ke estas pluraj manieroj en kiu ni povas fari tion, kaj ja kiel ni apud la fino ĉi tie, Mi prenus noto eble kion Mary Beth faras. Ni havas malmultajn amasoj ĝi similas, granda unu, tri pli malgrandajn. Publiko: Mi ordigante ilin kiam mi trovas du leterojn kiun mi konas estas kune en sekvenco, Mi metis ilin kune tiel ke mi ne devi maltrankviligi konservante aŭtoveturejo de tuta vico da libroj. Estas nur, ho, A estas la unua, Mi havas ĉi stako tie. SPEAKER: Do, preskaŭ kiel puzlo pecoj kiuj rajti formon al parigi kun ĉiu alia. Publiko: Pli malpli, jes. SPEAKER: OK, bonega. Kaj nun ĉiu el tiuj aretoj estas supozeble ordo? Publiko: Yeah. SPEAKER: Bone, A tra Z Ĉiuj Bone, gratulon, vi faris gxin. Vi havas vian preferatan. Blua? Bone, dankon por tio. Do Mary Beth ne proponas kion ŝi alproksimiĝo estis, sed kio estas alia alproksimiĝo kiom vi venu pri ordiga tion? Kion vi faris? La rekordo bati estus estinta unu minuton kaj 50 aŭ tiel sekundoj, pli la aĵoj mi forgesis rakonti. Kion vi faris? Yeah? Publiko: Prenu la stako. Komencos de la komenco. Kontrolu vian paperoj. Se la supra estas pli altaj ol, eble, ili estas, malsupre estas alta, tiam ŝanĝi ilin. SPEAKER: OK, tiel komencante ĉe la supro kaj la malsupro, kaj tiam laboras vian vojon internen tiel, interŝanĝante ilin? OK, do iom similan en spirito bobelo speco, sed elektante la ekstremoj Ne la apudaj paroj. Sed la mallonga de ĝi estas ke ekzistas certe faskon de malsamaj manieroj ni povus fari tion, kaj sincere, mi kredas ke vi ia adoptita paro alproksimiĝoj, dekstra? Vi faris specon de kvar ordo amasoj, kaj tiam efike kunfandis ilin kune. Kaj tio, daresay, alia tekniko entute. Vi ne traktis ĝin kiel unu granda amaso, Vi dividis la problemon en kvar quads, se vi volas, kaj tiam iel kunfandis ilin en la fino. Do ni konsideru, en lasta petskribo, kiel alie oni povus fari tion. Ni formaligis la nocio de bobelo speco lasta fojo, kaj bobelo speco recall estis algoritmo kiu ni bildigita kun ok el viaj samklasanoj tien, ŝajne hazarde ordo unue. Kaj ni do decidis paroj, se du elementoj estas el ordo, simple interŝanĝu ilin. Do kvar kaj du estas evidente misfunkcias, tial tiuj du samklasanoj ŝanĝis poziciojn. Kaj tiam ni ripetis kun kvar kaj ses, tiam ses kaj ok, sur ĉiu ripeto, movas dekstren. Do donita ok homoj, kiom da paroj komparojn ĉu mi faras dum marŝante de maldekstre dekstren en unu tia ripeto? Kiom komparojn? Seven, dekstra? Ĉar se estas ok homoj sed vi havas la paro ilin kaj vi tenas movanta unu hop dekstren, vi ne tuj havos ok komparojn ĉar vi ne povas kompari elementon kontraŭ si, aŭ ĝi farus nur estu sencela, do vi havas sep. Aŭ pli ĝenerale, se ni havas n homoj, ni faru n minus 1 komparoj kun bobelo varo. Do ni konsideras nun kiel bonaj aŭ malbona bobelo speco efektive estis, kaj provi doni nin vortprovizon per kiu kritikon algoritmoj kiel tiu, kaj baldaŭ nia propra. Do la unuaj pasas tra bobelo varo, la unua fojo Mi promenis de maldekstre al dekstre tra la stadio, prenis min n minus 1 komparoj. Kaj ke tuj estos mia unueco de mezuro, dekstra? Mi estis afabla de paroli kaj promenado, iom rapida, iom malrapida, tiel rakontante mia nombro de sekundoj ne aparte diri, sed kalkulante la nombron de operacioj kiuj mi faris lunde, komparante du homoj, kiuj sentas kiel bela unueco de mezuro. Do n minus 1 paŝas la unua fojo, sed tiam kio okazis post tio? Kio estas la upside de unu paŝo tra alie Unsorted listo? Kion vi povas diri al mi pri la ero kiu estis la tuta vojo tien? Yeah? Tio estis la plej granda elemento, dekstra? Numero ok, kvankam ŝi komenciĝis tie, ĉiufoje mi komparis ŝin kontraŭ najbaro, ŝi tenis bobelanta supren dekstren flanko de la listo. Kaj efektive, jen kie la algoritmo prenas lian nomon. Nun ke logiko, kiom komparoj bezonas mi faras en la dua tempo Mi faros, ke pasu de maldekstre al dekstre? n minus 2, dekstra? Estus simple esti malŝparas mian tempon se mi konservi komparante ok kontraŭ iu alie, ĉar ni jam scias ŝi estis en la ĝusta loko. Do tio estas iom de optimumigo, do la venonta paŝo tuj estos plus n minus du paŝojn, kie n estas la nombro da homoj. Nun vi povas ia extrapolar, eĉ Se vi ne estas komputila sciencisto kiel tiu finas. Je la fino de tiu algoritmo, supozeble Vi havas nur unu komparo lasis. Vi devas speco de ripari la komencante de la listo se du kaj unu estas el ordo kaj devas esti unu kaj du, tial ĉi fundoj tra plus 1 fina komparo. Nun la skalara, dot, punkto speco de ondoj estas manojn iom el la juicier detaloj sed ni simple iru antaŭen kaj simpligi. Se vi memoras el alta lernejo, sincere, multe de vi havis math libroj kiuj havis iom lertaĵoj folio sur la kovrilo aŭ ferdeko trasera kiu montris al vi kion serio sumatorios ŝatas tio finfine aldonis ĝis. En la ĝenerala kazo, se vi havas variablon kiel n, kaj ja ĉi tiu, Se vi rigardis vian malnova lernejo math libro, vi vidus ke tio reale adicias supren al tiu sumo tie, n × n minus 1 ĉiu dividita per 2. Do nun lasu min nur kondiĉas tio estas vera, do sur salto de fido ke estas kion ĉi resumas ĝis, kaj ni povis pruvi ke en pli ĝenerala kazo. Sed nun ni ekspansiiĝi ​​ĉi ekstere. Do ni multiplikas ĉi, do tio n kvadratoj, minus n, ĉiu dividita per 2. Tio vere n kvadratoj, dividita per 2, minus n super 2 tiel ke ĉio bela kaj interesa. Sed kio okazas se ni nun ŝtopi-en valoro? Supozi Mi ne havis ok homoj, sed diru miliono. Kaj miliono nur ĉar ĝi estas iom granda nombro, ni ŝtopi ke en kaj vidu kio okazas. Do se mi ŝtopi miliono en tiu formulo Mi tuj akiri milionon kvadrato, dividita per 2, minus a milionoj, dividita per 2. Nun kio tio tuj egali? Do 500 miliardoj, minus 500.000. Kaj se mi efektive fari ke math ekstere, kiu signifas ke ordigo miliono homo kun la bobelo speco konduku min 499.999.500.000 ŝtupoj aŭ komparojn en la fino, Ni nur extrapolar. Kiu sentas bela malrapida, sed sincere mezurante unu aparta enigo kiel tiu, ne ĉiuj kiuj rakonton. Sed ja ĝi sugestas ke kiel n ricevas pli kaj pli grandaj, ĉi tiu algoritmo ia sentas malbona kaj malbona, aŭ vi vere komenci senti la doloron de tiu potencigo, ke n kvadratoj, kiu adicias supren sufiĉe rapide. Kaj tiu detalo ne estas perdiĝis homoj, fakte antaŭ kelkaj jaroj iu senatano kiu estis kampanjado, sidiĝis por intervjuo kun Google Eric Schmidt, CEO tiutempe, kaj estis defiita per demando multe kiel ni esploras hodiaŭ. Ni rigardu. [VIDEO Playback] -Senator, Vi estas ĉi tie ĉe Google, kaj mi ŝatas pensi pri la prezidanteco kiel laboron intervjuo. Nun, estas malfacile akiri laboron kiel prezidanto, kaj vi tuj tra la rigorecoj nun. Ĝi estas ankaŭ malfacile akiri laboron ĉe Google. Ni havas demandojn, kaj ni petu nian kandidatoj demandoj kaj ĉi tiu estas de Larry Schwimmer. What-- vi uloj pensas min kidding, estas ĝuste ĉi tie. Kio estas la plej efika maniero ordigi miliono 32 bitoj entjeroj? -Well-- -I'm Bedaŭras, maybe-- -No, Ne, ne. Mi kredas ke la bobelo speco estus malĝuste iri. -Come Je, kiu rakontis al li ĉi tiu? Mi ne vidis komputilo scienco en via fono. -We've Ricevis nian spionoj tie. -OK, Ni petu malsama intervjuo demando. [FINO VIDEO Playback] SPEAKER: Tiel parolas specifaj nombroj kvankam, ne tuj esti tiom utila. Ne estas vivo leciono ke bobelo varon, donis milionon enigoj, povus preni kiel multaj kiel 500 miliardoj paŝoj. Vi ne povas vere ĝeneraligi tro efike de tiu kaj fari bonan decidoj de dezajno kiam skribas programojn. Do ni enfokusigi kvankam sur kiel Ni povus simpligi tiun rezulton. Do mi reliefigis en flava tie la rezulto de n kvadrato dividita per 2, tiel miliono kvadrato dividita per 2, kaj tiam Mi reliefigis kio la finfina respondo estis iam ni subtrahita ekstere n dividita per 2. Kaj la aserto Mi iras fari nun, kiuj la heck zorgas se subtrahi ekstere iom maljuna n super 2 kiam la unuaj parto de tiu formulo estas tiel granda? Ĝi regas la alia termino, n kvadrato dividita per 2 estas tiel granda, klare, kiel n ricevas grandaj kiel miliono, ke estas vere granda diferenco ĉe la fino de la tago inter 500 miliardoj kaj 499.999.500.000? Ne vere. Kaj tiel kion ni tuj faru kiel komputilo sciencistoj estas ignori tiujn malsupera ordo terminoj kaj preni iun kiel ĉi tio kaj vere nur simpligi ĝin al la termino kiu tuj gravas. La pli granda nia datenaroj akiri, des pli niajn datumbazojn akiri, des pli da retpaĝoj ni devas esplori, la pli amikojn vi havas sur Facebook. Kiel n prenas pli granda, ni vere tuj zorgas pri la plej granda termino en ajna tia analizo de nia algoritmoj agado. Kaj mi tuj diros, vi scias kion, bobelo varo estas sur la ordo de granda O, sur la ordo de n kvadratoj. Ne ĝuste n kvadrato kiel ni vidis, sed kiuj vere zorgas pri tiuj malgrandaj terminoj kaj sincere, kiu vere zorgas se ni dividos 2? Tio estas nur konstanta faktoro. Kaj estas 500 miliardoj kontre 250 miliardo vere ke granda de traktadon? Mi povis nur atendi unu jaron, tiam mia tekkomputilo laŭvorte ricevi duoble rapida en aparataro, kaj tiu speco de diferenco nur foriras nature super tempo. Kion ni zorgas proksimume estas la esprimo, la parto de la esprimo ke tuj varios kiel nia eniro ricevas pli kaj pli granda. Kaj efektive, en la reala mondo, tio estas kio okazas ĉiufoje estas la eniroj al niaj problemoj kaj algoritmoj estas akirantaj pli granda. Tiel granda O tuj estos la skribmaniero, la asimptota skribmaniero, ke ni simple uzi kiel komputilo sciencistoj por priskribi la prezento, aŭ la rultempo, de algoritmo. Tiel ke ni povas kompari algoritmoj sur malsamaj komputiloj skribita de malsamaj personoj, uzante iu fundamente simila metriko kiel la numero de komparoj vi fari, aŭ eble la nombro de svopoj vi faras. Kion ni ne tuj grafo estas la kvanto de tempo kiu trasmite la horloĝo sur la muro tipe. Kion ni ne tuj maltrankviligos proksimume estas kiom memoro vi uzas nuntempe en Almenaŭ, kvankam tio alia rimedo ni povus mezuri. Ni provos bazi nian analizo sur nur la bazajn operaciojn, la aĵoj, sincere, ke vi povas vidi la plej vide. Do kun iu kiel granda O de n kvadrata, mi asertas ke O de n kvadratoj estas supra ligis sur la tn rultempo de bobelo varo. En aliaj vortoj, se vi volis aserti ke ekzistas tiu supra limo sur kiom paŝas algoritmo povus preni, ĝi tuj estos en la granda O de n akorditaj en tiu kazo, supera baro. Kio se mi anstataŭ ŝanĝi la rakonto esti ne pri bobelo speco, sed pri tiu supera baro. Ĉu vi pensas de algoritmo ke ni rigardis jam kies supera baro, maksimumo mezuri tempon aŭ operacioj, estus dirita esti barita per n, lineara funkcio, ne kvadrata kiu estas kurba? Kio estas algoritmo kiu ĉiam prenas neniun pli ol kiel n paŝoj, aŭ 2n paŝoj, aŭ 3n pasxojn? Yeah? Publiko: Trovanta la granda nombro en la listo? SPEAKER: Perfekta, trovante la plej granda nombro en lerta. Se mi donita listo homoj ekzemple, ĉiu de kiuj tenas numeron, kio estas la maksimuma nombro de ŝtupoj devus konduki min, prudente inteligenta persono, trovi la plej granda persono en tiu listo? n, ĉu ne? Ĉar en la plej malbona kazo, kie eble la plej granda valoro estos? Ĝuste, la tutan vojon al la fino. Do, en la plej malbona kazo superulo, mi povus devos iri la tutan vojon tien kaj estu kiel, ho, jen la numero ok, aŭ kion ajn tiu valoro estas. Nun estus nur stulta se mi faris, ne? Serĉante pli kaj pli elementoj se la lasta el ili estas tie? Tiel certe, n estas supera baro. Mi ne bezonas preni pli paŝoj ol tio. Do kio se anstataŭ mi proponis ke ekzistas algoritmoj en tiu mondo kiu havi rultempo tio barita per granda O de log n log n? Kie ni vidis tiun antaŭ? Yeah? Publiko: En la telefono libro problemo? SPEAKER: Kiel la telefono libro problemon. Kio estis la mezuro de kiel da tempo aŭ kiom da larmoj prenis mi trovi iun kiel Mike Smith en la telefono libro? Ni asertis estis log n kaj eĉ se nekonataj aŭ ĝi estas iom malprecizaj kia logaritma aŭ eksponento estis, nur memoras ke log n ĝenerale aludas al la procezo, en tiu kazo, la dividadon io en duono denove, kaj denove, kaj denove, kaj denove, tiaj ke ricevas pli malgranda kiel vi faras tion. Do log n aludas, certe, al la telefono libro ekzemple, al duuma serĉo teorie, kiam ni havis la virtualajn pordojn sur la tabulo, aŭ kiam Sean estis serĉante ion. Se li uzis duuma serĉo, log n estus la supera baro sur kiom tempo kiu postrestas. Sed tiuj algoritmoj kiuj kuris en log n supozis kio ŝlosilo detale? Ke la listo estis ordigitaj, dekstra? Via algoritmo estas erara se via enigo ne ordo, kaj tamen vi uzas iu kiel duuma serĉo ĉar vi povus salti rajton super la elemento sen rimarki estas ja tie. Nun kio povus ĉi signifas, granda O de unu? Tiu ne signifas, ke via algoritmo prenas unu kaj nur unu paŝo, Ĝi simple signifas ĝin prenas konstanta nombro de paŝoj. Eble estas 1, eble estas 10 eble estas 1.000, sed estas sendependa de la amplekso de la problemo. Neniu afero kiom granda n, konstanta tempa algoritmo ĉiam prenas la saman nombron de paŝoj. Do kio povus esti algoritmo Ni parolis pri aŭ simple intuicie, ke venas al vi ke ĉiam kuras en tn konstanta tempo? Yeah? Publiko: du nombroj. SPEAKER: du nombroj, 2 plus 2 estas 4, faritaj. Por ke povu labori, kion alian? Kion pri pli reala mondo, jes? Publiko: Trovanta la unua aĵo en listo. SPEAKER: Trovanta la unua ero en listo, sekura. Ni fakte parolis pri arrays jam, kiel vi atingi la unua ero en tabelo, negrave kiom longe la tabelo estas en C kodo? Vi nur uzos kiel la krampo nulo skribmaniero, bam, vi estas tie. Kaj efektive arrays, kiel flanken, subteno io ĝenerale konata kiel aliro aleatorio, hazarda aliro memoro, ĉar vi povas laŭvorte salti al iu loko. Ni povas fari ĉi tion eĉ pli simple ni povas malantaŭenigi al semajno nulo Kiam ni faris Scratch. Kiom tempo ĝi prenas por la diru bloko en Scratch ekzekuti? Nur konstanta tempo, ĉu ne? Diru ion, diri ion, tio ne gravas kiom granda Grat mondo estas, ĉiam tuj prenos la sama kvanto de tempo simple diri ion. Do tio estas konstanta tempo, sed kio estas la flip flanko? Se tiu estis supra baroj, kio se ni volas priskribi la subaj baroj de nia algoritmoj rultempo? Preskaŭ bona kazo potenciale, se vi volas, kvankam tiuj terminoj aplikeblas best kazoj, plej kazoj, mezumo kazoj pli ĝenerale, sed ni simple enfokusigi sur subaj baroj pli ĝenerale. Kio estas algoritmo kiu havas suba baro de n paŝoj, aŭ 2n paŝoj, aŭ 3n pasxojn? Iu faktoro de n paŝoj, tio estas lia malsupera. Yeah? Publiko: Bubble speco? SPEAKER: Bubble speco prenas vi minimume n paŝojn, kial? Kial estas tio? Kial tiu komenco veni al vi intuicie, eĉ se ĝi ne nur ankoraŭ? Yeah? Publiko: [inaudible]. SPEAKER: Ekzakte. En la plej bona ebla scenaro de bobelo speco, kaj amaso de algoritmoj, se mi transdonu al vi ok personoj kiuj jam ordo, estus malsaĝa Pri vi, la algoritmo, iri reen pli ol iam, ĉu ne? Ĉar kiam vi trairu la liston unufoje vi devus rimarki, ho, mi faris nenian svopoj, tiu listo estas ordigita, elirejo. Sed ke tuj prenos vin n paŝoj. Kaj inverse, kio estas alia pensmanierojn pri ĝi? Bobelo speco estas omega, tiel diri, de n, ĉar se vi rigardas malpli ol n elementoj, kio estas la fundamenta demando tie? Vi ne scias, ĉu ĝi estas ordo, dekstre. Ni homoj heroajxoj ekrigardi ok personoj kaj estu kiel, Ho, estas ordigitaj, kiu ne prenas min n paŝojn, sed faris. Viaj okuloj, kvankam vi speco de havas grandan kampon de vidado, vi rigardis ok elementojn, vi rigardis ok personoj, tio estas ok ŝtupoj efike. Kaj nur se mi iros tra la tuta Listo mi rimarkas, jes, ordigitaj. Se mi haltas duonvoje pensante, ĉiuj Bone, ĝi estas bela ordo ĝis nun, kio estas prognozo ĝi ne estas ordo? Tio algoritmoj ne tuj estos ĝusta. Povus esti pli rapida, sed malĝusta. Do nun ni havas manieron de priskribantaj subaj baroj, kaj kio pri konstanta tempo? Kio estas algoritmo kiu havas pli malaltan ligis sur ĝia rultempo de unu? 1 paŝo, 2 paŝoj, 10 paŝojn, sed konstanto sendependa de n, la amplekso de la enigo? Jes, en dorso. Publiko: printf? SPEAKER: Kio estas tio? Publiko: printf? SPEAKER: printf. OK, sekura. Do necesas fiksa kvanto de paŝoj. Mi devus now-- nun ni parolas pri C kodo kaj ne Scratch, iu kiel diri, kun printf, ni devas komenci akiri zorgema. Ĉar printf ne prenu enigo, estas cxeno, kaj kordoj do teknike havas longa. Do se ni nun volas kapti sur vi, se vi ne gravas, teknike ni povus argumenti ke printf ne prenu ŝanĝiĝema longitudo enigo, kaj certe ĝi povus preni pli tempon por presi kordo tiu longa, ol tiu longa. Do kio se ni konsideras nur la ordig kaj serĉanta ekzemplojn? Kio pri Mike Smith en la telefono libro aŭ duuma serĉo pli ĝenerale? En la plej bona kazo, kio povus okazi? Mi malfermas la telefono libro kaj, bam, ekzistas Mike Smith nombro. Mi povas voki lin tuj. Prenis unu paŝo, eble du paŝojn, sed konstanta nombro de paŝoj se mi akiris bonŝanca. Kaj sincere, ni vidis sur Lundo via samklasano akiri tute bonŝanca dufoje en vico. Kaj tio ja estis konstanta tempo en subaj baroj sur la algoritmo en demando por trovi la numero 50 malantaŭ tiuj fermitaj pordoj. Nun, kiel flanken, se vi malkovros ke tiel granda O, la supera baro, kaj omega, la suba baro, Estas unu en la sama, kiu Estas la sama formulo krampoj, vi povas ankaŭ diri, nur por esti fantazio, ke io estas theta de n aŭ theta de iu alia valoro. Tio simple signifas kiam grandaj O kaj omega estas samaj. Nun kio pri selektado speco? Ni uzu tiun novan vortprovizon. En selektado speco, kion ni neniam farante denove kaj denove, kaj denove? Mi tuj reen tra la listo, serĉante, kiun? La plej malgranda nombro. Do kiom da ŝtupoj, kiom multaj komparoj faris mi devas fari por eltrovi kiu la plej eta ero en la listo estis? n minus 1, dekstra? Ĉar se mi simple komencu per la unu mi donita kaj mi komencas kompari lin aŭ ŝin, tiam li aŭ ŝi, li aŭ ŝi, li aŭ ŝi, mi nur duo elementoj kune n minus 1 fojoj. Do selektado speco simile prenas n minus 1 paŝas unuafoje. Kiom da paŝoj preni min al trovi la dua plej malgranda ero? n minus 2, ĉar mi estas stulta se mi dauxre rigardante la samaj homoj denove se mi jam selektis lin aŭ ŝi kaj metis ilin en sian lokon. Kaj la tria paŝo, n minus 3, tiam n minus 4. Ni vidis ĉi ŝablono antaŭe, kaj ja selektado speco simile havas supera baro de n kvadratoj se ni faros tion sumado. Kio estas ĝia suba baro, selektado speco? Minimume, kiom da tempo devas selektado speco prenu, kiel ni difinis en lundo? Propono du ebloj. Eble estas n, kiel antaŭe. Eble ĝi estas n kvadratoj, kiel nun estas kiel la supera baro. Publiko: n kvadratoj. SPEAKER: n kvadratoj. Kial? Publiko: Ĉar vi havas difini [inaudible]. SPEAKER: Ekzakte. Almenaŭ tiel mi difinis selektado speco ĝi estis sufiĉe naiva, observu tuj, trovi la plej malgrandan elementon. Iru denove, trovi la plej malgrandan elementon. Iru denove, trovi la plej malgrandan elementon. Ne estas ia optimumigo en tie povus lasi min aborti post nur n aŭ tia paŝoj. Do ja, selektado varon, omega de n kvadratoj. Kio pri inserción varo, ĝi kie mi prenis kiuj mi donis, kaj tiam mi plopped li aŭ ŝin en la ĝusta loko? Poste mi iris al la dua persono, plopped lin aŭ ŝin en la ĝusta loko. Tiam la sekvanta persono, plopped li aŭ ŝi en la ĝusta loko. Rimarku ke tio estas tre lineara, por tiel diri. Mi rekto, mi ne iras tien kaj reen Mi neniam rigardis reen vere, sed kio okazas kiam mi enŝovu li aŭ ŝin en la komenco de la listo kiel ni faris en lundo? Kio okazas? Yeah? Publiko: [inaudible]. SPEAKER: Yeah, ke Estis la kaptisto, dekstra? Vi eble memoras de via samklasanoj, se ili estis farante ajnan movadon iliaj piedoj, kiuj estis operacio. Do se tri homoj ĉi tie kaj la nova persono apartenis vojon tien, sur longa etapo kiel tiu, kompreneble li aŭ ŝi povus nur iri al la fino mem. Sed se ni pensas pri komputilo kaj tabelo de memoro, tiuj homoj iras havi barajar super por fari lokon al tiu persono. Kaj tial n minus 1 shufflings, n minus 2 shufflings, n minus 3 shufflings estas ĝuste speco de okazas malantaŭ min, ne antaŭ mi kiel antaŭe, en iu senso. Nun kiel flanken, kaj kiel vi eble vidis en linio Se vi komencas ŝovas ĉirkaŭ ĉirkaŭ varoj, ekzistas multaj malsamaj aĵoj tie ekstere, kelkaj el ili bona ol aliaj. Ja, bogosort estas tio estas ia amuza rigardi supren. Bogosort prenas aron de nek nombroj diros ludkartaro de kartoj hazarde ludkartaro ilin kaj ĉekojn se ili estas ordigitaj. Kaj se ne, ĉu denove. Kaj se ne, ĉu denove. Se ne, ĉu denove. Nekredeble stulta. Kaj efektive, se vi legis kiel la Vikipedia artikolo, lia alnomo estas stulta varo. Ĝi eventuale labori, espereble, donita sufiĉa tempo, sed tiu kvanto de tempo povus preni sufiĉe tempo. Do, se mi povus, ni rapido aferoj el Mary Beth ekzemplon antaŭe, por havi kelkaj pli elementoj, sed du pli procesoroj. Du homoj, se vi ne gravas kunigi min. Kiom proksimume 1 pli tie, kaj ni go-- neniu tie? Neniu tie? OK. Vi kun la nigraj ĉemizo, jes, venu malsupren. Bone, kio estas via nomo? Publiko: Peter. SPEAKER: Kio estas tio? Publiko: Peter. SPEAKER: Peter David, agrable renkonti vin. Bone, ni havas Peter tie, se vi volas veni sur la tablo super tie. Kaj kio estas via nomo? Publiko: Helena. SPEAKER: Helena. OK, agrable renkonti vin. Elena renkonti Petron. Petro, Helena. Kaj ni bezonos Andrew tien tiel, bonvolu. Kaj via defio tuj esti ordigi ludkartaro de kartoj. Kaj se ne estas familiarizados, ferdeko de kartoj devus finfine ordigataj etaĵon ŝatas tiu kie ni faros la kluboj, tiam la sxovelilojn, la koroj kaj diamantoj, el as kiel unu, tuta vojo supren al reĝo. La kartoj Mi tuj donos al vi tuj estos 52 en kvanto. Ni tuj simile tempo vi, en nur momento. Ni tuj ĵetos Andrew supren sur la ekrano tie, tiel kiel por vidi kiel vi faras tion. Kaj por ke ĉiuj ĉi Estas des pli videbla, Jen estas la kartojn mi havas en Amazon. Do ili estas jam hazarde ordo, kaj ni iras al tempo vi. Kaj ni tuj teni ĝin reala tiu fojo, do ni provos premi vin ĉar alie tiu ricevos teda rapide. Se vi povus procedi ordigi 52 elementoj kune tra iuj rimedoj, nun. Kaj denove, kiel ni rigardas tiujn infanoj faras kion, en la fino tuj produktos evidentan Rezulte, pensi vere kiel ili estas ĉiu faras ĝin, kiel vi povus priskribi ĝin. Ĉar denove, ĉi tiuj estas ĉiuj procezoj, algoritmoj ke ni prenas por donita kiel homo. Sed vi verŝajne longe havis intuicio, longe antaŭ vi eĉ pripensis preni komputiko klaso vin eble havis la intuicion kun kiu solvi problemojn kiel ĉi. Sed unufoje vi rekonas la mastroj kaj komenci formaligi la paŝojn, per kiu vi solvi tiujn problemojn, Vi trovos ke vi povas solvi multe pli interesaj kaj multe pli kompleksa problemoj rapide. Do iu el la publiko, kio estas almenaŭ unu elemento de la algoritmo ke oni uzas tie? Publiko: [inaudible] SPEAKER: Kio estas tio? Publiko: Per kostumo. SPEAKER: Per kostumo. Do unue oni clustering ĉiuj diamantoj kune ĝi similas, ĉiuj koroj kune ŝajnas, ks, sen respekto por la nombroj sur la kartoj. Kaj nun aperas, ekzemple, esti ordiga ilin per nombro. Tre bona. Bone, do kion tuj esti la fina paŝo do tien? Iam ni havi kvar ordo kostumoj, kio ĉu ni bezonas fari por la kvar aretoj por atingi unu ordo ferdeko, tute simple? Do ni bezonas kunfandi ilin denove. Do tie estas interesa ideo, ke denove, daresay, estas tre intuicia eĉ se vi povus neniam manfrapis tian etikedon sur ĝi. Ĉi tiu fundamenta nocio de dividadon la problemo ne estas en la duono ĉi tempo, sed almenaŭ en kvar pecojn. Solvanta preskaux fundamente identa problemoj izolite unuj de la aliaj, kaj tiam kunfandas la rezultojn. Kaj, bonega, farita. Bone, granda ronda de aplaŭdoj, se ni povus. [Aplaŭdo] SPEAKER: Mi havas neniun ideon kion vi faru kun ili, sed ĉi tie vi iras. Dankon tiom. Do ni vidu, du minutoj ok sekundoj, Se vi ŝatus defii viajn amikojn. Kio do tuj esti forpreni el tiu ke ni povas utiligi pli ĝenerale? Nu, pensu reen al tiu tabelo de nombroj, kaj pensi reen nun iuj de la _pseudocode_ ni skribis en la pasinteco, kaj tio estis por la _pseudocode_ por solvanta la telefono libro problemon. Per en _pseudocode_ mi numeritaj pli metoda vojo priskribi kiel mi agis tre intuicia homa algoritmo la dividadon de la telefono libro en duono, ripeto, ripeti, ripeti, ĝis mi trovos iun kiel Mike Smith, se li estas ja en la telefono libro. Sed mi specon de uzataj kion mi vokos tre ripeta alproksimiĝo tie, en apartaj avizo linio 8 kaj linio 11. Tiuj estas evidenteco de ripeta proksimigo, a looping alproksimiĝo, ĉar tio estas ĝuste la konduto induktas. Tiuj linioj tiel diri iri linio tri, kaj vi povas ia pensi, ke en via Anime kiel estante buklo. Ĝi diras al vi reiri al paŝo tri kaj ripetas, denove kaj denove, kaj denove. Sed kio se ni utiligas ŝlosila ideo tie ni faris ne la lasta fojo, kaj simpligi linio 8 kaj linio 11 kaj iliaj najbaroj kiel ĝuste tiu, en flava. Ĝi ne estas fundamente mallongigi la _pseudocode_ tre multe, sed ĝi fundamente ŝanĝi la naturo de mia algoritmo. Kion mi nun diras en ŝtupo 7, en ŝtupo 10, estas serĉi Mike en la ĝusta sama maniero, sed nur en la maldekstra duono aŭ la dekstra duono. Do alivorte, se Mi komencos de ŝtupo unu, repreni telefono libro, malfermita al meza el telefono libro, rigardu nomoj se Smith estas inter nomo, nomita Mike, alia se Smith estas antaŭe en libro, treti sep serĉi Mike en maldekstran duonon de libro. Sed tian sentas ĝi estas lasi min pendantan, dekstra? En flava, estas instrukcion, sed kiom mi serĉi Mike en la maldekstra duono de la telefono libro? Kie mi havas algoritmo per kiu mi povas serĉi iu kiel Mike Smith? Nu, ĝi estas fiksrigardanta ni en la vizaĝo. Mi povas laŭvorte uzi la ĝustajn samajn programo efike suprenirantaj al la supro denove kaj re-funkciado la samaj linioj de kodo. Do kvankam tiu devus senti kiel iom de cikla difino kie vi respondi ies demando por nur ia demandante La sama demando denove, kiel kial, kial, kial? La realaĵo estas ĉar ni malfacile kodita kelkaj specialaj linioj, ŝtupo 4, kio estas se kaj ŝtupo 12, kiu estas efektive alia branĉo, ĉar ni havas tiujn stopgap mezuroj, tiu algoritmo finiĝi se ni trovi Mike, aŭ se ni ne faras. Sed en ŝtupo 7 kaj 10 nun ni havas kion ni nomas rekursia algoritmo. Kaj rekursio estas ja potenca ideo ke estas iom menso kliniĝante al la komenco, ke ni povas nun apliki jene. Kunfandi speco estos la lasta varo ke Ni rigardu, almenaŭ en klaso formale. Kaj estas fundamente malsama el tiuj lastaj tri, kaj certe lasta kvar se ni inkludas bogosort. Jen la _pseudocode_ por merge varo. Kiam la enigo de n elementoj, tiel donita tabelo de amplekso n, se n estas malpli ol 2, reveni. Do kial mi havas tiun prudento kontroli unuan? Kio implico se mi transdonos vin tabelo kies longo n estas malpli ol 2? Ĝi estas jam ordo, evidente, dekstra? Ĉar la listo aŭ havas unu elemento, kiu estas bagatele ordo ĉar estas la sola afero tie. Aŭ, ĝi estas de grandeco nulo kiu signifas nenio estas ordigi, do nature estas ordigitaj. Ekzistas nur nenio malĝusta tie. Do jen nia tn baza kazo. Tio estas simila en spirito kion ni faris kun Mike. Se Mike en la telefono libro, nomi lin. Se li ne estas tie, rezigni. Ĝi estas tiel nomata baza kazo, certigi tiu algoritmo al la fino de la tago ĉesos en certaj cirkonstancoj. Sed jen la salto de fido nun alia, ordigi la maldekstra duono de la elementoj, tiam ordigi dekstre duonon de la elementoj, kaj tiam kunfandi la ordo duonoj. Kaj tie estas kie sentas kiel ni copping ekstere. Mi petis vin ordigi n elementoj, kaj mi dirante, OK, ĉu ĝin ordiga maldekstren kaj ordigo dekstre. Sed mi diras unu alia afero, kaj tiu estas la ŝlosilo temo ŝajnas en la intuicio tiel multe, tie estas tio tria ŝtupo de kunfando. Kiun kvankam Ŝajnas tiel muta en spirito, kiel nur kunfandi aferoj kune, ŝajnas esti ŝlosila paŝo al la reassembly de du problemoj dividigxis finfine duono. Do kunfandi speco, ni faru tion, se vi humuron mi, kun pli pruvo, nur por ke ni havas iun nombroj labori kun. Ĉu mi povas interŝanĝi ok streso buloj por ok personoj? Bone, kio pri vi tri, vi kvar en ĉi tiu sekcio, kvin, ses, kaj ni cxu 7, 8, venu supren. OK, yeah OK. Minus 8, tie ni iru, plus 1. Bonega. Ĉiuj rajtas veni supren, ni rapide doni vin nombroj. Numeron du, numero tri, numero kvar, numero kvin, ses, sep, ok. Mi faris ok ĝuste tiu tempo. OK, do iru antaŭen se vi povis, kaj ni ordigi en la originalan ordon ke ni havis hieraŭ kiuj aspektis kiel tiu, se vi ne ĝenas. Kaj ni faros antaŭ la tablo. Bone, do kunfandi varo. Jen kie okazas akiri ia interesa, ĉar mi ŝajnas esti donante mem tiom malpli informo hodiaŭ. Do kunfandi speco unue sur eniro de n elementoj, kaj evidente ne malpli ol du, ĝi estas ok, do mi havas iom pli da laboro por fari. Do nun mense ni kiel klaso nun estas en la alia branĉo, kio signifas tri paŝoj. Unue, mi devas ordigi la maldekstra duono de la eroj. Do kiel mi iros en fari ĉi tion? Nu, mi tuj speco de mense dividi la liston ĉi tie, vi ne devas fizike movi kaj mi tuj enfokusigi nur en la maldekstra duono de la elementoj tie. Do kiel mi iros sur ordiga listo nun de grandeco kvar? Kio estas mia algoritmo? Unue mi kontrolu estas n malpli ol du ne, do mi povas daŭri al la alia bloko denove. Ordigi maldekstra duono de elementoj. Do nun denove, mense, kaj ĉi tiu estas kie Vi devas accrue multan mensa historio, se vi volas. Nun mi ordiga maldekstre duonon de la maldekstra duono. Bone, do nun mi vokas mian saman merge ordiga algoritmo, estas N malpli ol du? Ne, tio estas du, do mi devas ordigi maldekstre duono, kaj la dekstran duonon. Do tie ni iru, ordigi la maldekstra duono. Kial vi ne simple preni unu paŝon antaŭen. Kio estas via nomo? Publiko: Darren. SPEAKER: Dan. Dan tretis antaŭen. Publiko: Darren. SPEAKER: Darren, farita. Ĉu vi diras Darren aŭ Dan? Publiko: Darren. SPEAKER: Darren. OK, Darren tretis antaŭen kaj li estas nun ordo. Kaj tio estas preskaŭ inane aserton, dekstra? Mi ne vere ŝajnas esti atingante nenio, sed ni procedi. Nun lasu min ordigi dekstre duono de la eroj. Kio estas via nomo? Publiko: Luko. SPEAKER: Luko. Venu, paŝon antaŭen. Done mi ordigitaj Luko. La maldekstra duono estas nun ordo kaj la dekstran duonon nun ordo, sed denove, estas ŝlosila paŝo tie. Kion mi apud bezonas fari? Kunfandi la ordo duonoj. Nun ni iras al nur devas ĉiuj reen tiamaniere, ĉar mi specon de bezoni iu nulo spaco. Estas preskaŭ kiel tiuj knaboj sur tablo, Mi bezonas ĉambron movi ilin cxirkauxe. Do mi tuj kunfandi vi uloj rigardante ĉe la maldekstra duono kaj la dekstran duonon. Kaj kiu evidente venas unue, maldekstra duono aŭ dekstra duono? Do dekstran duonon, do ni movi Luko super tien por Darren originala pozicio. Kaj nun kunfandi sian maldekstran duonon en, Darren tuj iru dekstren tie. Do sentas preskaŭ bobelo speco efekto, sed mia fundamenta algoritmo, tre malsama tiu tempo. Sed nun estas kie aĵoj oni iom ĝena ĉar vi devas malantaŭenigi mense kien mi chesos. Mi ĵus kunfandis la ordo duonoj, kio signifas mi kie en mia algoritmo? Mi devas ordigi la dekstran duonon, ĉu ne? Se vi malantaŭenigi, laŭvorte sur la video, vi vidu ke ni alvenis al tiu punkto de Luko kaj Darren per ordiga maldekstre duonon de la maldekstra duono. Tiam ni kunfandis tiujn ordo duonoj, kiuj signifas la sekva paŝo estas speco la dekstran duonon de la maldekstra duono. Bone, do ni fari tion pli rapide. Bone, ses, mi tuj pretendi vi estas nun ordo, venu pluen. Kio estas via nomo? Publiko: Adriano. SPEAKER: Adriano. Adriano nun ordo. Kaj kio estas via nomo? Publiko: Alex. SPEAKER: Alex estas nun ordo. Maldekstra duono, dekstran duonon, kio estas la fina paŝo? Kunfandi. Bela bagatela, do mi estas tuj kunfandos en ses, preni retropaŝo, ok, preni retropaŝo. Kaj nun rimarki ĉi estas utila takeaway, kio nun estas vera pri la maldekstran duonon de la lerta, sendepende de kiel ni komencis? Ĝi estas ordigitaj. Nun ĝi ne estas ordo en la granda skemo de aferoj, sed estas ordo sendepende de la alia duono. Nun kio paŝo mi sur se mi konservos rewinding kiel la historio komencis? Nun mi devas ordigi la dekstran duonon. Do nun ni estas vojo reen ĉe la komenco de la rakonto, kaj ni faru tion pli rapide. Do mi tuj ordigi la dekstran duonon de la tuta listo. Kio estas la sekva paŝo? Ordigi la maldekstra duono de la dekstra duono. Ordigi la maldekstra duono de la maldekstra duono de la dekstra duono. Kaj kio estas via nomo? Publiko: Omar. SPEAKER: Omar, paŝas antaŭen farita. Maldekstra duono estas ordigitaj. Kaj kio estas via nomo? Publiko: Chris. SPEAKER: Chris, paŝon antaŭen, vi nun ordo. Kio estas la klavo paŝo nun? Kunfandi. Do oni tuj eniru loko ĉi tie, se vi povus preni retropaŝo, kaj tri tuj preni retropaŝon, kunfandi. Tiel la maldekstra duono de la dekstra duono, estas nun ordo. Sincere, ĉi tiu algoritmo sentas nin malŝparas vojon pli tempo ol antaŭe, sed se ni faris tion en reala tempo, ni vidu kion takeaways tuj estos. Nun mi estas preta, dekstra duono de la dekstra duono, lasu min antaŭeniri kaj ordigi la maldekstra duono. Paŝu antaŭen, kio estas via nomo? Publiko: Ramsey. SPEAKER: Ramsey estas nun ordo. Kio estas via nomo? Publiko: Marina. SPEAKER: Marina estas nun ordo kiel bone, se vi preni unu paŝon antaŭen. Ŝlosilo paŝo tie nun kunfandi, mi tuj deŝiri de miaj du listojn, maldekstra kaj dekstra. Kvin tuj veni unue kaj sep venos baldaŭ. Kaj denove, tio estas intenca. La fakto ke ili estas prenante paŝas antaŭen kaj reen celas reprezenti ke ni ne povas do tiu algoritmo en loko tiel facile kiel bobelo speco, kaj selektado speco, kaj inserción speco kie ni ĵus tenis interŝanĝante popolo. Mi laŭvorte bezonas ian de nulo papero en kiu meti tiujn ulojn dum mi faras la fandado, kaj tiam mi povas meti ilin en lokon. Kaj tio estas ŝlosilo ĉar mi uzas nova rimedo, spaco, ne nur tempon. OK, tiu estas mirinda. Maldekstra duono estas ordo, dekstra duono estas ordo, nun ke ŝlosilo kunfando paŝo. Kiamaniere mi povos kunfandi ĉi? Do se vi sekvas mian maldekstra mano kaj dekstren Mi tuj atentigi mia maldekstra mano ĉe la maldekstra duono, mia dekstra mano ĉe la dekstra duono, kaj nun mi devas decidi paŝo post paŝo, kiun por enkunigi. Kiu evidente venas unue? Nombro unu. Do venu tien, jen nia scratch pad. Do nun la numero unu, kaj avizo kion mi faru kun mia dekstra mano, Mi iras al movi mian dekstran manon unu Transpaŝi atentigi nombro tri, kaj nun mi devas fari la sama decido. Kaj efektive staras dekstre en antaŭ Luko tie se vi povus, ĉar tio estas nia scratch pad. Do kiu venas tuj? Ni havas Luke kun numero du aŭ Chris kun numero tri. Evidente Luko, nombro du, do vi venis. Sed mia maldekstra mano nun tuj esti incremented noti al Darren, kaj jen la ŝlosilo forpreni kun kunfando, Mi iras por subteni fari tion, Evidente, se vi speco de sekvi la logikon. Sed miaj manoj estas neniam tuj iru malantaŭen, kio signifas ke mi nur iam movanta al maldekstren kun mia kuniĝo procezo, kaj ke tuj estos ŝlosilo nian analizon en nur momento. Do nun ni finos tiun supren rapide. Do tri venas proksima, tiam kvar venas proksima, kaj nun kvin venas proksima, do ses, kaj sep, kaj tiam fine ok. Sentas la plej malrapida algoritmo tamen, sed ne se ni reale kuri al la sama speco de horloĝo rapido, tiel paroli kun la sama tiktakas horloĝo kiel antaŭe. Kial? Nu, Ni prenu rigardi la rezultita fino. Ni reiru tien, lasu min elsxiros manifestacio vide kion ni ĵus faris. Zoom tie, sur tiu paĝo ĉi tie, dirante Firefox ke ni volas enviciĝi en tiu skatolo, ni diru bobelo varo, kun kiu ni estas nun bone konata, selektado speco, kiu estas alia sufiĉe simpla unu, Nun hodiaŭa merge varon, kiun estos nia klimataj finaĵo. La kialo postrestis tiel plu tien kun homoj kaj mi parole estas, Evidente, mi klarigante ĉiu paŝo. Sed se vi simple ekzekuti ĉi, multe kiel ni faris bobelo varo kaj selektado speco ne nur vide, horloĝo kiom multe pli efike tio utiligante de divido kaj konkerante povas kiam aplikita al aro de datumoj kiuj estas eĉ grandeco ok, sed eĉ tiel, multe pli granda. Mi donos al vi kunigi varon, flankon ĉe flanke kun tiuj aliaj algoritmoj. Tiu tuj alvenos dolora rapide, kaj la finaĵo ne estas aparte klimataj, ili nur finos ordo. Sed la ŝlosilo forpreni estas ke aspektas kiel multe pli rapida kunfandi speco estis, krom se vi kredas ke mi estas nur ia rompado kun vi. Se ni faros ĉi tiu lasta fojo, Ni reŝargi tiun, ni iru reen kaj elekti bobelo speco, kaj ĝuste por piedbatoj, ni elektos inserción speco, nur por bonan mezuron. Kaj ĉi tiu fojo, ni elekti merge varo kaj ni reale kuri tiuj flank. Kaj ne, fakte, bonŝancaĵo. Kion mi efektive farata Mi havas dividita mia eniro en la duono, denove, kaj denove, kaj denove. Kaj tie estas nur tiom da fojoj vi povas dividi via enigo en duonoj, maldekstra kaj dekstra. Kio estas la formulo kiu ni daŭre vidas kiu priskribas la divido en duono denove kaj denove, kaj denove, kaj denove? Publiko: Log n. SPEAKER: Log n. Sed tiam ekzistas unu alia ŝlosilo paŝo, tiu algoritmo ne log n paŝoj. Se ĝi nur ensaluti n paŝoj, ni estus en la sama problemo kiel antaŭe, kie ni ne povas esti certe ĉio ordo. Vi devas minimume rigardi n elementoj certi n elementoj estas ordigitaj, alie ĝi estas salto de fido. Do estas minimume log n paŝojn, sed kio pri tiu klavo kuniĝo ŝtupo kie mi kunfandis mia maldekstra duono kaj dekstra duono kaj marŝis trans la scenejo? Kiom da paŝoj estas ke kunfandi? Estas n, sed mi ne faris nur kunfandi la fina tempo. Sur ĉiu el tiuj neston alvokojn, sur ĉiu de tiuj neston kunigoj Mi ankoraŭ ordo. Mi kunfandis tiujn du knaboj, tiam tiuj du Knaboj, tiam tiuj du onkloj ktp. Do mi kunfando denove kaj denove. Kiom da fojoj? Do ĉiufoje mi dividis la lerta en duono, mi faris merge. Dishaku la listo en duono, fari merge. Do se dividante la elenco povas fari log n fojojn, kaj la kombino finfine prenas n paŝojn, kio povus esti nun la supra baro sur la kurado tempo de nia algoritmo? n log n. Kaj efektive, jen kion ni atingis tien. Do la sento ke vi vidu vide kiam tiujn tri aferojn kuras flanko ĉe flanko Estas n kvadratoj kontraŭ n kvadrato kontraŭ n log n. Kio fundamente ni vidos, Ne nur hodiaŭ sed en la estonteco, estas multe, multe pli rapida. A ĉirkaŭvojon de aplaŭdoj por tiuj infanoj, Mi repagos kun streso pilkojn. Ni adjourn tie hodiaŭ, kaj Ni vidos vin lunde.