[MUZIKO Ludante] 

PROFESORO: Bone. Jen CS50 kaj ĉi tiu estas la fino de semajno tri. Do ni estas ĉi tie hodiaŭ, ne en Sanders Teatro, anstataŭ en Weidner Biblioteko. Ene de kio estas studo konata kiel Hauser Studio, aux ni diru Studio H, aux cxu ni say-- se vi ĝuis tiun ŝercon, ĝi estas fakte de samklasano, Marko, rete, kiu sugestis tiel tra Twitter. Nun kio estas malvarmeta pri esti tie en studio estas ke mi ĉirkaŭitaj de tiuj verdaj muroj, verda ekrano aŭ chromakey, tiel diri, kio signifas ke CS50 la produktteamo, nekonata al mi ĝuste nun, povus esti metante min plej ie ajn en la mondo, por bone aŭ por malbone. 

Nun kio estas antauxe, problemo aro du estas en viaj manoj por tiu semajno, sed kun problemo aro tri ĉi venanta semajnon, Vi estos defiita kun la tn ludo de 15, malnova partio favoro ke vi eble memoras ricevanta kiel infano kiu havas tutan faskon de nombroj kiuj povas gliti supren, suben, maldekstre kaj dekstre, kaj tie estas unu breĉo ene de la enigmo, en kiun vi povas fakte gliti tiuj puzlo pecoj. Finfine vi ricevis ĉi puzlo en iuj duon hazarda ordo, kaj la celo estas ordigi ĝin, supre sube, maldekstre dekstren, de unu tutan vojon supren tra 15. 

Bedaŭrinde, la efektivigo vi devos mane tuj esti programaro bazita, ne fizike. Vi efektive tuj havos skribi kodo kun kiu studento aŭ uzanto povas ludi la ludon de 15. Kaj fakte, en la hacker eldono de ludo de 15, Vi estos defio al implementar, Ne nur la ludado de tiu malnova lernejo ludo, sed prefere la solvado de ĝi, implementando dio moduso, tiel diri, ke reale solvas la enigmon por la homaj, provizante ilin per aludo, post aludo, post aludo. Do pli en tiu proksima semajno. Sed tio kio kuŝas antaŭen. 

Por nun memoras ke antaŭe ĉi tiu semajno ni havis ĉi cliffhanger, se vi volas, per kio la plej bona ni faris ordiga saĝa estis supera baro de big o de n kvadrato. Alivorte, bobelo varo, selektado varon, inserción varo, ĉiuj el ili, dum malsamaj en ilia efektivigo, ekhavis en n kvadratoj kurante tempo en la plej malbona kazo. Kaj ni ĝenerale supozas ke la plej malbona kazo por ordigado Estas kiu via enigoj estas tute malantaŭen. Kaj ja, ĝi prenis tre kelkajn paŝojn implementar ĉiu de tiuj algoritmoj. 

Nun je la fino de klaso revokon, ni komparis bobelo varo kontraŭ selektado speco kontraŭ unu alia ke ni nomis merge speco tiutempe, kaj mi proponas ke ĝi estas prenanta avantaĝon lecionon de semajno nulo, dividi kaj venki. Kaj iel atingi ian logaritma rultempo finfine, anstataŭ ion ke estas pure kvadrata. Kaj ĝi ne estas sufiĉe logaritma, estas iom pli ol tio. Sed se vi memoras de klaso, estis multe, multe pli rapida. Ni rigardu, kie ni cxesis. 

Bobelo varo kontre selektado ia kontre merge varon. Nun ili ĉiuj kuras, en teorio, samtempe. La CPU kuras ĉe la sama rapido. Sed vi povas senti kiel enuiga ĉi Estas tre rapide tuj fariĝis, kaj kiom rapida, kiam ni injekti iom de semajno nulo la algoritmoj, ni povas akceli aĵojn. 

Do markon speco aspektas miriga. Kiel ni povas utiligi ĝin, por ordigi nombroj pli rapide. Bone ni pensas reen al ingredienco kiun ni havis reen en semajno nulo, tiu de sercxas iu en telefono libro, kaj memoras ke la _pseudocode_ ke ni proponis, tra kiu ni povas trovi iu kiel Mike Smith, aspektis iom io tiamaniere. 

Nun rigardu en aparta ĉe la linio 7 kaj 8, kaj 10 kaj 11, kiu induktas ke buklo, per kiu ni gardis revenanta al linio 3 denove, kaj denove, kaj denove. Sed rezultu ke ni povas vidi tiu algoritmo, tie en _pseudocode_, iom pli amplekse. Fakte, kion mi serĉas ĉe tie sur la ekrano, estas algoritmo por serĉanta Mike Smith inter iu aro de paĝoj. Kaj efektive, ni povus simpligi ĉi algoritmo en tiuj linioj 7 kaj 8, kaj 10 kaj 11 por nur diras, kiun mi prezentis ĉi tie en flava. En aliaj vortoj, se Mike Forgxiston estas pli frue en la libro, ni ne bezonas specifi paŝo paŝo nun kiel iri trovi lin. Ni ne devas specifi reiri al la linio 3, Kial ni ne simple anstataŭe, diru, pli ĝenerale, serĉi Mike en la maldekstra duono de la libro. 

Male, se Mike estas fakte poste en la libro, kial ni ne simple citi unquote serĉo Mike en la dekstra duono de la libro. Alivorte, kial ni ne simple ia puŝpeli al ni dirante, serĉi Mike en tiu subaro de la libro, kaj lasi ĝin al nia ekzistanta Algoritmo por diri nin kiel sercxi por Mike en ke maldekstran duonon de la libro. Alivorte, nia algoritmo laboras ĉu ĝi estas telefono libro de dikeco, de tiu dikeco, aŭ ajna dikeco whatsoever. Do ni povas rikure difini tiun algoritmon. En aliaj vortoj, sur la ekrano tie, estas algoritmo por serĉi Mike Smith inter la paĝoj de telefono libro. Do en linio 7 kaj 10, ni nur diru precize tion. Kaj mi uzas tiun terminon momente antaŭe, Kaj efektive, rekursio estas la buzzword por nun, kaj estas tiu procezo fari ion cikla de iel uzante kodon kiun vi jam havas, kaj nomante ĝin denove, kaj denove, kaj denove. Nun ĝi estas tuj estos grava ke ni iel fundo eksteren, kaj ne faras tion malfinie longa. Alie ni tuj havas ja senfina ciklo. Sed ni vidu se ni povas pruntepreni tiun ideon de rikuro, farante ion denove kaj denove kaj denove, solvi la ordigado problemo tra merge varon, des pli efike. 

Do mi donos al vi kunfandi speco. Ni rigardu. Do jen _pseudocode_, kun kiun ni povus apliki ordigado, uzante tiun algoritmon vokis merge varon. Kaj ĝi estas tute simple tio. Sur enigo de n eroj, en aliaj vortoj, se vi estas donita n elementoj kaj nombrojn kaj literoj aŭ nenial la enigo estas, se vi donita n eroj, se n estas malpli ol 2, simple reveni. Dekstra? Ĉar se n estas malpli ol 2, ke signifas ke mia listo de elementoj estas aŭ de amplekso 0 aŭ 1, kaj en ambaŭ de tiuj bagatelaj okazoj, la listo estas jam ordo. Se ne estas lerta, ĝi estas ordo. Kaj se tie estas listo de longo 1, ĝi estas evidente ordigita. Do la algoritmo bezonas nur vere fari ion interesan, se ni havas du aŭ pli elementoj donita al ni. Do ni rigardu la magio tiam. Else ordigi la maldekstra duono de la elementoj, tiam ordigi la dekstra duono de elementoj, tiam kunfandi la ordo duonoj. Kaj kio estas speco de menso fleksanta tie, estas ke mi ne vere sxajne diris vin ion nur ankoraŭ, ĉu ne? Ĉiuj mi diris estas, donita listo de n eroj, ordigi la maldekstra duono, tiam la dekstran duonon, do kunfandi la ordo duonoj, sed kie estas la efektiva sekreta saŭco? Kie estas la algoritmo? Bone ĝi rezultas ke tiuj du linioj unua, varo lasis duonon de elementoj, kaj varo pravas duono de elementoj, estas rekursiaj vokoj, tiel diri. 

Post ĉiu, ĉe tiu punkto en tempo, ĉu mi havas algoritmo kun kiu ordigi tuta amaso de elementoj? Jes. Ĝi estas ĝuste ĉi tie. Ĝi estas ĝuste sur la ekrano, kaj do mi povas uzi tiun saman aron de paŝoj ordigi la maldekstra duono, kiel mi povas la dekstra duono. Kaj ja, denove kaj denove. Do iumaniere, kaj ni baldaŭ vidi tion, la magio de merge varo estas enigita en tiu finalo linio, kunfandante la ordo duonoj. Kaj tio ŝajnas sufiĉe intuicia. Vi prenu du duonoj, kaj vi, iel, kunfandi ilin kune, kaj ni vidos tiun konkrete en momento. 

Sed tio estas kompleta algoritmo. Kaj ni vidos ekzakte kial. Nu supozu ke ni donis tiujn samajn ok elementoj tie sur la ekrano, unu tra ok, sed ili estas en ŝajne hazarda ordo. Kaj la celo ĉe mano estas ordigi tiujn elementojn. Nu kiel mi iros pri faranta ĝin uzanta, denove, kunfandi speco, kiel po ĉi _pseudocode_? Kaj denove, ingrain ĉi en via menso, por nur momento. La unua kazo estas sufiĉe bagatela, se ĝi estas malpli ol 2, simple reveni, ne estas laboro farenda. Do vere tie estas nur tri paŝojn por vere teni en menso. Denove kaj denove, mi estas tuj volas havi ordigi la maldekstra duono, ordigi la dekstra duono, kaj tiam iam iliajn du duonoj estas ordigataj Mi volas kunfandi ilin kune en unu ordo listo. Observu do, ke en menso. 

Do jen la originala listo. Ni traktos tion kiel ornamo, ni komencis en semajno du, kio estas apuda bloko de memoro. En tiu kazo, enhavanta ok nombroj, malantaÅ­o al malantaÅ­o al dorso. Kaj ni nun apliku merge varon. Do mi unue volas ordigi la maldekstra duono de la listo, kaj ni, do, temigi 4, 8, 6, kaj 2. 

Nun kiel mi iros pri ordiga listo de grandeco 4? Nu mi devas nun konsideri ordigado la maldekstra de la maldekstra duono. Denove, ni malantaŭenigi por nur momento. Se la _pseudocode_ estas tiu, kaj Mi transdonis ok elementojn, 8 estas evidente pli granda ol aŭ egala al 2. Do kun la unua kazo ne validas. Do ordigi ok elementojn, mi unue ordigi la maldekstra duono de elementoj, tiam mi ordigi la dekstra duono, tiam mi kunfandi la du ordo duonoj, ĉiu de amplekso 4. BONE. 

Sed se vi ĵus rakontis al mi, ordigi la maldekstra duono, kio estas nun de grandeco 4, kiel mi ordigi la maldekstra duono? Nu, se mi havas enigo de kvar elementoj, Mi unue ordigi la maldekstra du, tiam dekstre du, kaj tiam mi kunfandi ilin kune. Do denove, ĝi iĝas iom de menso fleksanta ludon ĉi tie, ĉar vi, ia, devi memoras kie vi estas en la rakonto, sed fine de la tago, donita ajna nombro de elementoj, vi unue volas ordigi la maldekstra duono, tiam la dekstra duono, tiam kunfandi ilin kune. Komencu fari ĝuste tion. Jen la enigo de ok elementoj. Nun ni rigardas la maldekstra duono tien. Kiel mi ordigi kvar elementoj? Nu mi unue ordigi la maldekstra duono. Nun kiel mi ordigi la maldekstra duono? Nu mi estis donita du elementoj. Do ni ordigi tiujn du elementojn. 2 estas pli granda ol aŭ egala al 2, kompreneble. Do tiu unua kazo ne validas. 

Do mi nun devas ordigi la maldekstra duono de tiuj du elementoj. La maldekstra duono, kompreneble, estas nur 4. Do kiel mi ordigi liston de unu elemento? Nu nun, ke speciala baza kazo supren supro, tiel diri, aplikiĝas. 1 estas malpli ol 2, kaj mia listo estas efektive de grandeco 1. Do mi simple reveni. Mi ne faras nenion. Kaj efektive, rigardu kion mi havas farita, 4 jam ordo. Kiel mi jam parte sukcesan tie. 

Nun ke ĝi similas specon de stultaj aserti, sed ĝi estas vera. 4 estas listo de amplekso 1. Ĝi estas jam ordo. Tio estas la maldekstra duono. Nun mi ordigi la dekstra duono. Mia enigo estas unu elemento, 8 simile, jam ordo. Stulta, tro, sed denove, ĉi baza principo tuj permesos nin nun konstrui aldone tiu sukcese. 4 ordigataj 8 estas ordigataj nun kio estis tiu fina paŝo? Do la tria kaj lasta paŝo, ajna tempo vi ordigi liston, revokon, estis kunfandi la du duonoj, maldekstre kaj dekstre. Do ni faru ĝuste tion. Mia maldekstra duono estas, kompreneble, 4. Mia dekstra duono estas 8. 

Do ni faru ĉi. Unue mi tuj rezervu iu plia memoro, ke mi reprezentas ĉi tie, kiel nur sekundara tabelo, tio sufiĉe granda por konveni tion. Sed vi povas imagi etendante ke rektangulo la tuta longo se ni bezonas pli poste. Kiel mi prenos 4 kaj 8, kaj kunfandi tiuj du listoj de grandeco 1 kune? Ankaŭ tie sufiĉe simpla. 4 venas unue, tiam venas 8. Ĉar se mi volas ordigi la maldekstra duono, tiam la dekstra duono, kaj poste kunfandi tiujn du duonoj kune, en ordo ordo, 4 venas unue, tiam venas 8. 

Do ni ŝajnas esti faranta progreson, eĉ kvankam mi ne faris ajnan efektiva laboro. Sed memoru kie ni estas en la rakonto. Ni origine prenis ok elementoj. Ni ordo la maldekstra duono, kio estas 4. Poste ni ordo la maldekstra duono de la maldekstra duono, 2. Kaj tie ni iru. Ni faris kun tiu paŝo. 

Do se ni ordo la maldekstra duono de 2, nun ni devas ordigi la dekstra duono de 2. Do la dekstra duono de 2 estas tiuj du valoroj tie, 6 kaj 2. Do ni nun prenu enigaĵoj de grandeco 2, kaj ordigi la maldekstra duono, kaj tiam la dekstra duono, kaj tiam kunfandi ilin kune. Nu kiel mi ordigi liston de grandeco 1, enhavanta nur la numero 6? Mi jam faris. Tio listo de grandeco 1 estas ordo. 

Kiel mi ordigi alian liston de grandeco 1, la tn dekstra duono. Nu, tro, jam ordo. La nombro 2 estas sola. Do nun mi havas du duonoj, maldekstra kaj Bone, mi devas mem kunfandi ilin kune. Lasu min donu min iom da ekstra spaco. Kaj metis 2 en tie, tiam 6 tien, tiel ordigado tiu listo, maldekstra kaj dekstra, kaj kunfandante ĝin kune, finfine. Do mi estas en iomete pli bona formo. Mi ne faris, ĉar klare 4, 8, 2, 6 ne estas la fina ordigante ke mi volas. Sed mi nun havas du listojn de grandeco 2, ke ambaux respektive solviĝis. Do nun se vi malantaŭenigi en via menso okulo, kie kiuj lasas nin? Mi komencis kun ok elementojn, tiam mi cxizis gxin malsupren al la maldekstra duono de 4, tiam la maldekstra duono de 2, kaj tiam la dekstra duono de 2, Mi finis do ordigado maldekstren duono de 2, kaj la dekstran duonon de 2, Do kio estas la tria kaj fina paŝo tie? Mi devas mem kunfandi kune du listojn de grandeco 2. Do ni iru antaŭen. Kaj sur la ekrano tie, doni mi iom plia memoro, kvankam teknike, rimarkos ke mi atingis tutan faskon da malplenan spacon ĝis supro tie. Se mi volas esti speciale efika spaco saĝa, Mi povis nur komenci movanta la elementoj tien kaj reen, supro kaj malsupro. Sed ĝuste por vida klareco, Mi tuj metis ĝin malsupre teni aferojn bela kaj pura. 

Do mi havas du listojn de grandeco 2. La unua listo havas 4 kaj 8. La dua listo havas 2 kaj 6. Ni kunfandi tiujn kune en ordo ordo. 2, kompreneble, unue venas, tiam 4, tiam 6, tiam 8. Kaj nun ni ŝajnas esti akiranta ie interesa. Nun mi ordigitaj duono de la listo, kaj hazarde, ĝi estas ĉiuj paraj nombroj, sed ke estas ja nur koincido. Kaj mi nun ordo maldekstren duono, tiel ke ĝi estas 2, 4, 6, kaj 8. Nenio estas el ordo. Kiu sentas same kiel progreso. 

Nun sentas mi havas parolis ĉiam nun, do kio mankas vidi se ĉi algoritmo estas ja pli efika. Sed ni tuj tra ĝin super metode. Komputila kompreneble farus tiel. Do kie ni estas? Ni komencis kun ok elementoj. Mi ordo la maldekstra duono de 4. Mi ŝajnas esti farita kun tiu. Do nun la sekva paŝo estas ordigi la dekstra duono de 4. Kaj tiun parton ni povas iri tra iom pli rapide, kvankam vi estas bonvena malantaŭenigi aŭ paŭzo, ĵus pensi tra ĝi al via propra ritmo, sed kion ni havas nun estas ebleco do la ĝusta sama algoritmo sur kvar malsamaj nombroj. 

Do ni iru antaŭen kaj temigi la dekstra duono, kiu estas tie. La maldekstra duono de tiu dekstra duono, kaj nun la maldekstra duono de la maldekstra duono de tiu dekstra duono, kaj kiel mi ordigi liston de grandeco 1 enhavanta nur la numero 1? Ĝi estas jam farita. Kiel mi fari same por listo de grandeco 1 enhavanta nur 7? Ĝi estas jam farita. Paŝo tri por tiu duono tiam estas kunfandi tiujn du elementojn en novan liston de grandeco 2, 1 kaj 7. Ŝajne ne faris cxion ke multe interesa laboro. Ni vidu kion okazas poste. Mi nur ordigitaj la maldekstra duono de la dekstra duono de mia originala enigo. Nun ni ordigi la dekstra duono, kiun enhavas 5 kaj 3. Ni denove rigardu maldekstren duono, ordigataj dekstra duono, ordigataj kaj kunfandi tiujn du kune, en iu plia spaco, 3 unue venas, tiam venas 5. Kaj tial nun, ni ordo la maldekstra duono de la dekstra duono de la origina problemo, kaj la dekstra duono de la dekstra duono de la originala problemo. Kio estas la tria kaj fina paŝo? Nu kunfandi tiujn du duonoj kune. Do lasu min atingi min iuj ekstran spacon, sed, denove, mi povus esti uzante ke rezervaj spaco ĝis supro. Sed ni tuj daŭre ĝin simpla vide. Lasu min enkunigi nun 1, kaj tiam 3 kaj poste 5, kaj tiam 7. Per tio lasi min nun kun la dekstran duonon de la originala problemo ke estas perfekte ordigita. 

Do kio restas? Mi sentas kiel mi tenas diranta la samajn aferojn ree kaj ree, sed tio estas reflekta de la fakto ke ni uzas rekursio. La procezo de uzi algoritmo denove, kaj denove, sur malgrandaj subaroj de la originala problemo. Do mi nun havas maldekstra ordo duonon de la originala problemo. Mi rajtas ordo duone de la originala problemo. Kio estas la tria kaj fina paŝo? Ho, ĝi estas kunfando. Do ni faru tion. Ni rezervu iun suplementan memoro, sed mia dio, ni povis meti ĝin ie nun. Ni havas tiom da spaco disponebla al ni, sed ni observu ĝin simpla. Anstataŭ iri reen kaj eliras kun nia originala memoro, ni nur faros vide malsupren tie sube, fini supren kunfandante la maldekstra duono kaj la dekstra duono. 

Do kunfandante, kion mi devas fari? Mi deziras preni la elementojn en ordo. Do rigardante la maldekstra duono, Mi vidas la unua nombro estas 2. Mi rigardas la dekstran duonon, Mi vidas la unuan numeron estas 1, tiel evidente kion numeron mi volas elŝiri, kaj metis unua en mia lerta fino? Kompreneble, 1. Nun mi volas demandi tion saman demandon. Sur la maldekstra duono, mi havas ankoraŭ havas la numeron 2. Sur la dekstran duonon, Mi havas la numeron 3. Kiun mi volas elekti? Kompreneble, numero 2 Kaj nun rimarkas la kandidatoj Estas 4 maldekstre, 3 dekstre. Ni, kompreneble, elektu 3. Nun la kandidatoj estas 4 sur la maldekstra, 5 dekstre. Ni, kompreneble, elektu 4. 6 sur la maldekstra, 5 dekstre. Ni, kompreneble, elektu 5. 6 maldekstre 7 dekstre. Ni elektas 6, kaj tiam ni elekti 7, kaj tiam ni elektus 8. Voila. 

Do multegajn vortojn poste, ni esti ordigitaj tiun liston de ok elementoj en listo de unu tra ok, ke estas kreskanta kun ĉiu paŝo, sed kiom da tempo faris ni bezonos por fari tion. Nu mi havas intence Laid aferojn bilde tie, por ke ni povas ia vidi aŭ aprezi la divido en konkeradon ke tio estis okazanta. 

Ja se vi retrorigardas al la maldormo, Mi lasis ĉiujn tiujn punktita linioj en lokokupilojn, vi povas, ia, vidu, en inversa ordo, se ia retrorigardas en historio nun, mia originala listo estas, kompreneble, de grandeco 8. Kaj tiam antaŭe, mi estis kontraktanta kun du listojn de grandeco 4, kaj tiam kvar listoj de amplekso 2, kaj tiam ok listojn de grandeco 1. 

Do kio faras tiun, ia, memorigas vin pri? Nu, ja, iu el la algoritmoj ni havas rigardis ĝis nun, kie ni breĉo, kaj dividiĝas, kaj dividiĝas, teni havanta aferojn denove, kaj denove, rezultigas ĉi ĝenerala ideo. Kaj do estas io logaritma okazas ĉi tie. Kaj ĝi ne estas sufiĉe log de n, sed Tie estas logaritma komponanto al kion ni ĵus faris. 

Nun ni konsideru ke fakte estas. Do log de n, denove estis grandan rultempo, kiam ni faris ion kiel duuma serĉo, kiel ni nun nomas ĝin, la dividu kaj regu strategion tra kiu ni trovis Mike Smith. Nun teknike. Jen protokolo bazo 2 de n, eĉ kvankam en plej math klasoj, 10 estas kutime la bazo ke vi supozas. Sed komputikistoj preskaŭ ĉiam pensi kaj paroli en terminoj de bazo 2, do ni ĝenerale nur diru loglibro de n, anstataŭ log bazo 2 de n, sed ili estas ĝuste unu kaj la sama en la mondo de komputilo scienco, kaj kiel flanken, Tie estas konstanta faktoro diferenco inter la du, do estas Moot ĉiuokaze, por pli formalaj motivoj. 

Sed nuntempe, kion ni zorgas pri estas ĉi ekzemplo. Do ni ne pruvi per ekzemplo, sed ĉe almenaŭ uzi ekzemplon de la nombroj ĉe mano kiel prudento ĉeko, se vi volas. Do antaŭe la formulo estis log bazo 2 de n, sed kion estas n tiukaze. Mi devis n originalaj nombroj, aŭ 8 de originala numero specife. Nun jam pasis iom dum, sed mi estas sufiĉe certas ke log bazo 2 de la valoro 8 estas 3, kaj ja, kio estas agrabla pri tio estas ke 3 estas ĝuste la nombro de tempoj ke vi povas dividi listo de longo 8 denove, kaj denove, kaj denove, ĝis vi lasis kun listoj de ĵus grandecon 1. Dekstra? 8 iras al 4, iras al 2, iras al 1, kaj tio estas reflekta ĝuste tiun bildo ni devis nur antaŭ momento. Do iom prudento kontroli kiel al kie la logaritmo estas fakte implikita. 

Do nun, kion alia estas implikita tie? n. Do rimarki ke ĉiu fojon mi fendi la listo, kvankam en inversa ordo en historio tie, mi estis ankoraŭ faranta n aferoj. Ke kunfando paŝo postulis ke Mi tuŝas ĉiun el la nombroj, por gliti ĝin lia taŭga loko. Do kvankam la alteco de tiu diagramo estas de grandeco log n de n aŭ 3, specife, en aliaj vortoj, Mi faris tri dividoj tie. Kiom laboro mi faris horizontale laŭ tiu diagramo ĉiu tempo? 

Nu, mi faris n paŝoj de labori, ĉar se mi havas ricevis kvar elementoj kaj kvar elementoj, kaj mi bezonas kunfandi ilin kune. Mi bezonas iri tra tiuj kvar kaj tiuj kvar, finfine kunfandi ilin reen en ok elementoj. Se inverse Mi havas ok fingrojn super tie, kiun mi ne, kaj ok fingers-- sorry-- Se mi havas ricevis kvar fingroj super tie, kiun mi faros, kvar fingroj super tie, kiujn mi faras; tiam tio estas la sama Ekzemple kiel antaŭe, se mi faras havas ok fingrojn kvazaŭ en Entute kiun mi povas, ia, faru. Mi povas ekzakte fari tie, tiam mi certe povas kunfandi ĉiuj tiuj listoj de grandeco 1 kune. Sed mi certe devas rigardi ĉe ĉiu elemento ekzakte unufoje. Do la alteco de ĉi tiu procezo estas log n, la larĝo de tiu procezo, tiel diri, estas n, do kion ni ŝajnas havi, finfine, estas kura tempo de amplekso n fojoj logo n. 

En aliaj vortoj, ni dividis la listo, log n fojojn, sed ĉiun fojon ni faris tion, ni havis tuŝi ĉiun de la elementoj por kunfandi ilin ĉiuj kune, kiuj estis n paŝo, tial ni havas n fojoj logo n, aŭ por komputila sciencisto dirus, asimptote, kiu estus la granda vorto priskribi la supra ligis sur rultempo, ni kuras en granda O de log n tempo, por tiel diri. 

Nun tiu estas signifa, ĉar memori kio la kuranta tempoj estis kun bobelo varo, kaj selektado speco, kaj inserción varo, kaj eĉ kelkaj aliaj ke ekzistas, n kvadratoj estis kie ni estis ĉe. Kaj vi povas, ia, vidu ĉi tie. Se n kvadratoj estas evidente n fojoj n, sed ĉi tie ni havas n fojoj logo n, kaj ni jam scias el semajno nulo, ke log n, la logaritma, estas pli bona ol io lineara. Post ĉiu, memoru la bildon kun la ruĝa kaj la flava kaj la verda linioj kiuj ni tiris, la verda logaritma linio estis multe pli malalta. Kaj sekve, multe pli bona kaj pli rapida ol la rektan flavan kaj ruĝan linioj, n fojoj logo n, vere, bonaj ol n × n, aŭ n kvadratoj. 

Do ni ŝajnas havi identigitaj algoritmo merge speco kiu kuras en multe rapida tempo, kaj efektive, jen kial, komence de ĉi tiu semajno, kiam ni vidis, ke konkurso inter bobelo varon, selektado speco, kaj kunfandi varon, merge varo vere, vere gajnis. Kaj efektive, ni eĉ ne atendu por bobelo varo kaj selektado speco fini. 

Nun ni prenu unu alia enirpermesilo pro tio, de iomete pli formala perspektivo, nur en kazo, ĉi resonas bone ol tiu alta nivelo diskuto. Do jen la algoritmon denove. Ni demandas nin, kion la rultempo estas de ĉi algoritmoj, algoritmas diversaj paŝoj? Ni dividu ĝin en la unua kazo kaj la dua kazo. La IF kaj la alia en la IF kazo, Se n estas malpli ol 2, simple reveni. Sentas kiel konstanta tempo. Estas, ia, kiel du ŝtupoj, Se n estas malpli ol 2, tiam revenu. Sed kiel ni diris lundon, konstanta tempo, aŭ granda o de 1, eblas du paŝojn, tri ŝtupoj, eĉ 1.000 ŝtupoj. Kio gravas estas ke ĝi estas konstanta nombro de paŝoj. Do la flava elstarigita _pseudocode_ tie kuras en, ni nomas ĝin, konstanta tempo. Do pli formale, kaj Ni tuj to-- ĉi estos la amplekso al kiu ni formaligi tiun rajton now-- T de n, la rula tempo de problemo ke prenas n somethings kiel enigo, egalas big o de unu, Se n estas malpli ol 2. Do estas kondiĉa sur tio. Do esti klara, se n estas malpli ol 2, ni havas tre mallongajn listo, tiam la rula tempo, T de n, kie n estas 1 aŭ 0, en tiu tre specifa kazo, ĝi estas nur tuj estos konstanta tempo. Ĝi tuj prenu unu paŝi, du paŝojn, ajn. Ĝi estas fiksita nombro de paŝoj. 

Do la suka parto nepre esti en la alia kazo en la _pseudocode_. La alian kazon. Ordigi maldekstra duono de elementoj, ia dekstra duono de elementoj, kunfandi ordo duonoj. Kiom longe faras ĉiu el tiuj ŝtupoj sekvu? Nu, se la kurado tempo ordigi n elementoj estas, ni nomas ĝin tre genéricamente, T de n, tiam ordigado maldekstren duono de la elementoj Estas, ia, kiel diri, T n dividita per 2, kaj simile ordigado la dekstra duono de elementoj estas, speco de, kiel diri, T n dividita 2, kaj tiam kunfandante la ordo duonoj. Nu, se mi havas iun nombro de elementoj tie, kiel kvar, kaj iuj nombro de elementoj tie, kiel kvar, kaj mi devas mem kunfandi ĉiu de tiuj kvar en, kaj ĉiu el tiuj kvar en unu post la alia, tiel ke finfine mi havas ok elementojn. Ĝi sentas ke estas granda O de n paŝoj? Se mi havas n fingroj kaj ĉiu el ili devas esti kunfandita en loko, tio estas kiel alia n paŝoj. 

Do ja formulaically, ni povas esprimi tiun, kvankam iom scarily unue rigardo, sed estas io kiu kaptas ĝuste tiu logiko. La rultempo, T n, se n estas pli granda ol aŭ egala al 2. En tiu kazo, la alian kazon, estas T de n dividita per 2, plus T de n dividita per 2, plus granda O de n, iuj lineara nombro de paŝoj, eble ĝuste n, eble 2 fojoj n, sed estas krude, ordo de n. Tiel ke ankaŭ estas kiel ni povas esprimi tiun formulaically. Nun vi ne scias tion, se vi jam registris ĝin en vian menson, aŭ rigardi gxin en la dorso de lernolibro, ke havu iom cheat folio fine, sed tio ja tuj donu al ni grandan o de n logo n, ĉar la rekursieca ke vi vidas tie en la ekrano, se vi vere faris ĝin, kun senfinan nombron de ekzemploj, aŭ vi faris formulaically, vi farus vidi ke tiu, ĉar tiu formulo sin estas rekursie, kun t de n super io dekstre kaj t de n super maldekstre, tiu povas reale esti esprimita, finfine, tiel granda go de n logo n. Se ne konvinkis, ke estas fajna por nun, nur preni sur fido, ke tio estas ja kion tio ripetiĝo kondukas al, sed tiu estas nur iom pli de matematika alproksimiĝo al rigardanta ĉe la rula tempo de merge varo bazita sur lia _pseudocode_ sola. 

Nu, ni prenu iom de elspiras el ĉiuj de tiu, kaj rigardu la certaj iamaj senatano, kiu povus rigardi iomete familiara, kiuj sidis kun Google Eric Schmidt, antaŭ kelka tempo, por intervjuo sur scenejo, antaŭ tuta amaso de homoj, parolantaj finfine pri temo, jen vere nun konata. Ni rigardu. 

Eric Schmidt: Nun Senatano, vi estas tie ĉe Google, kaj mi ŝatas pensi pri la prezidanteco kiel dungointervjuo. Nun estas malfacile akiri taskon kiel prezidento. PREZIDANTO OBAMA: Dekstra. Eric Schmidt: Kaj vi estas tuj fari [inaudible] nun. Ĝi estas ankaŭ malfacile akiri laboron ĉe Google. PREZIDANTO OBAMA: Dekstra. 

Eric Schmidt: Ni havas demandojn, kaj ni petas niajn kandidatojn demandoj, kaj ĉi tiu estas de Larry Schwimmer. 

PREZIDANTO OBAMA: OK. 

Eric Schmidt: Kio? Vi uloj pensas mi kidding? Ĝi estas ĝuste ĉi tie. Kio estas la plej efika vojo ordigi miliono 32 bita entjeroj? 

PREZIDANTO OBAMA: Well-- Eric Schmidt: Kelkfoje, eble mi bedaŭras, maybe-- PREZIDANTO OBAMA: Ne, ne, ne, ne, ne, mi think-- Eric Schmidt: Tio ne it-- PREZIDANTO OBAMA: Mi pensas, mi kredas ke la bobelo speco estus la malĝusta vojo iri. Eric Schmidt: Venu. Kiu diris lin tio? BONE. Mi ne forgesis la komputiko on-- 

PREZIDANTO OBAMA: Ni jam havas nian spionoj en tie. PROFESORO: Bone. Ni lasas malantaŭ ni nun la teoria mondo de algoritmoj en la asimptota analitiko el gxi kaj reveni al iuj temoj el semajno nulo kaj unu, kaj komenco forigi iuj trejnado radoj, se vi volas. Por ke vi vere komprenas finfine de la tero supren, kio estas daŭriganta sub la kapuĉo, kiam vi skribi, kompili kaj ekzekuti programojn. Memori precipe, ke tio la unua C programon ni rigardis, kanona, simpla programo de varoj, relative parolante, kien, ĝi presas, Saluton Mondo. Kaj memoru, ke mi diris, la procezo ke fontkodon iras tra Estas ĝuste tiu. Vi prenas vian fontkodon, transiru ĝin tra kompililo, kiel Clang, kaj eksteren venas celkodo, ke povus aspekti kiel ĉi, nuloj kaj ke la komputilo CPU, centra prilaborado unuo aŭ cerbo, finfine komprenas. 

Ĝi turnas ke tio estas Iom de simplificación, ke ni estas nun en pozicio por inciteti dise kompreni kio vere estis daŭriganta sub la kapuĉo ĉiufoje kiam vi kuros Tin, aŭ pli ĝenerale, ĉiu tempo vi faras programon, uzante Faru kaj CF 50 IDE. En aparta, aĵoj kiel ĉi estas unua generita, kiam vi unue kompili vian programon. Alivorte, kiam vi prenu vian fontkodon kaj kompili ĝin, kio estas unua estanta outputted per Clang Estas io konata kiel asembleo kodo. Kaj fakte, ĝi aspektas precize kiel tiu. 

Mi kuris komando ĉe la komandlinio antaŭe. Tin haltostreko ĉefurbo s hello.c, kaj tio kreis dosieron por mi vokis hello.s, interne de kiu estis ĝuste tiuj enhavoj, kaj iom pli supre kaj iom pli sube, sed mi metis la plej sukaj informojn tie sur la ekrano. Kaj se vi rigardas atente, vi vidos almenaŭ kelkajn familiara ŝlosilvortoj. Ni havas ĉefan ĉe supro. Ni printf malsupren en la mezo. Kaj ni ankaŭ havas saluton mondo backslash n inter citiloj sube. 

Kaj ĉio en ĉi estas tre malalta nivelo instrukcioj ke la komputilo CPU komprenas. CPU instrukcioj kiuj movas memoro ĉirkaŭ, ke ŝarĝo kordoj de memoro, kaj finfine, presaĵo aferoj sur la ekrano. Nun kio okazas post kiam tiu asembleo kodo estas generita? Finfine, vi ja ankoraŭ generi celkodo. Sed la paŝoj kiuj havas vere daŭras sub la kapuĉo rigardi iom pli kiel tiu. Fontkodon iĝas asembleo kodo, kiu fariĝas objekto kodo, kaj la operativa vortoj tie estas ke, kiam vi kompili vian fontkodon, eksteren venas asembleo kodo, kaj poste kiam vi kolektos viajn asembleo kodo, eksteren venas celkodo. 

Nun Clang estas súper kompleksaj, kiel multaj kompililoj, kaj ĝi faras ĉiu el tiuj ŝtupoj kune, kaj tio ne nepre eligo ajna intera dosieroj kiujn vi povas eĉ vidi. Ĝi ĵus kompilas aferojn, kiu estas la ĝenerala termino kiu Priskribas ĉi tuta procezo. Sed se vi vere volas esti aparta, ekzistas multe pli okazas tie ankaŭ. 

Sed ni ankaŭ konsideras nun ke eĉ ke super simpla programo, hello.c, nomita funkcio. Ĝi vokis printf. Sed mi ne skribis printf ja kiu venas kun C, tiel diri. Estas funkcio revokon tio deklaris en norma io.h, kiu Estas kaplinio dosiero, kiu estas temo ni vere plonĝi en pli profundo antaŭ longe. Sed header dosiero tipe akompanitaj per kodo dosiero, fontkodo dosiero, do multe kiel tie ekzistas normo io.h. 

Iam antaŭe, iu, aŭ ies, ankaŭ skribis dosiero nomata norma io.c, en kiu la efektiva difinoj, aŭ implementaciones de printf, kaj gxibo de aliaj funkcioj, estas efektive skribita. Do donita ke, se ni konsideras havi tie sur la maldekstra, hello.c, ke kiam kompilis, donas ni hello.s, eĉ se Tin ne tedas ŝparado en loko ni povas vidi ĝin, kaj tiu asembleo kodo gets kolektiĝis en hello.o, kiu Estas ja la defaŭltan nomon donita whenever vi kompili fonto kodigi en celkodo, sed ne tute preta ekzekuti ĝin, ĉar alia paŝo devas okazi, kaj havas estis pasante por la lastaj semajnojn, eble nekonata al vi. 

Specife ie en CS50 IDE, kaj tiu, Ankaŭ estos iom de simplificación momente, ekzistas, aŭ estis antaŭ longa tempo, dosiero nomata norma io.c, ke iu kompilita en norma io.s aŭ la ekvivalento, ke iu tiam kunvenigis en norma io.o, aŭ ĝi rezultas enen iomete malsama dosiero formato kiu povas havi malsamajn dosiersufikso entute, sed teorie kaj koncepte, ĝuste tiuj ŝtupoj devis okazi en iu formo. Kiu estas diri, ke nun kiam mi estas skribanta programon, hello.c, ke nur diras, saluton mondo, kaj Mi uzas aliulaj kodo kiel printf, kiu iam estis sur tempo, en dosiero nomata norma io.c, tiam iel mi devas preni miajn celkodo, mia nuloj kaj, kaj tiu persono objekto kodo, aŭ nuloj kaj, kaj iel ligi ilin kune en unu fina dosiero, nomata saluton, ke havas ĉiujn la nuloj kaj ones de mia ĉefa funkcio, kaj ĉiuj la nuloj kaj aĵoj por printf. 

Kaj ja, ke lasta procezo estas nomita, kunligi vian celkodo. La eligo de kiu estas plenumebla dosiero. Do juste la fino de la tago, nenio ŝanĝiĝis ekde semajno unu, kiam ni unue komencis kompili programojn. Efektive, ĉio ĉi estis okazas sub la kapuĉo, sed nun ni estas en pozicio Kie ni povas reale turmentus aparte tiujn diversajn ŝtupojn. Kaj efektive, fine de la tago, ni ankoraŭ lasis kun nuloj kaj, kio Estas efektive granda segue nun al alia kapablo de C, kiu ni ne devis utiligi plej verŝajna ĝis nun, konata kiel bitlarĝa operatoroj. En aliaj vortoj, tiel malproksime, anytime ni havas pritraktis datumoj en C aŭ variabloj en C, ni havis aĵojn kiel signoj kaj floto kaj ins kaj sopiras kaj duobloj kaj similaj, sed ĉiuj el tiuj estas almenaŭ ok bitoj. Ni neniam ankoraŭ povis manipuli individuaj bitoj, kvankam individuo bito, ni Know, povas reprezenti 0 kaj 1. Nun ĝi rezultas ke en C, oni povas akiri aliron al individua bitoj, se vi scias la sintakson, kun kiu akiri ilin. 

Do ni rigardu ĉe bitlarĝa operatoroj. Do bildigis ĉi tie estas kelkaj simboloj kiuj ni, speco de, ia, vidis antaŭe. Mi vidas simbolo, vertikala trinkejo, kaj iuj aliaj ankaŭ, kaj memoras ke ampersand ampersand Estas io ni vidis antaŭe. La logika KAJ operatoro, kie vi havas du el ili kune, aŭ la logika AŬ operatoro, kie vi havas du vertikalaj stangoj. Bitlarĝa operatoroj, kiun ni vidi operacii sur bitoj individue, nur uzi ununuran ampersand, a ununura vertikala trinkejo, la ĉapelo simbolo venas poste, la malgranda tildo, kaj tiam foriris krampo lasis krampon, aŭ dekstra krampo dekstra krampo. Ĉiu de ĉi tiuj havas malsamajn signifojn. 

Fakte, ni rigardu. Ni iru malnova lernejo hodiaŭ, kaj uzo ekrano táctil de la pasintaj tempoj, konata kiel blanka tabulo. Kaj tiu blanka tabulo tuj permesos nin esprimi iun sufiĉe simplaj simboloj, aŭ prefere iuj sufiĉe simplaj formuloj, ke ni povas tiam finfine levilforton, por aliri individuajn bitoj ene C programon. Alivorte, ni faru tion. Ni unue diskuto por momento pri ampersand, kiu estas la bitlarĝa KAJ operatoro. En aliaj vortoj, tiu estas operatoro kiu permesas mi havi maldekstra ŝanĝiĝema tipe, kaj dekstran ŝanĝiĝema, aŭ individuo valoro, ke se ni KAJ ili kune, donas al mi finan rezulton. Do kion mi volas diri? Se en programo, vi havas variablo kiu stokas unu el tiuj valoroj, aŭ ni tenas ĝin simpla, kaj nur skribi el nuloj kaj individue, jen kiel la ampersand operatoro funkcias. 0 ampersand 0 tuj egali 0. Nun kial estas tio? 

Ĝi estas tre simila al Buleaj esprimoj, ke ni diskutis tiom. Se vi pensas finfine, la 0 estas falsa, 0 estas falsa, malvera kaj malvera estas, kiel ni diskutis logike, ankaŭ malvera. Do ni ricevas 0 tie ankaŭ. Se vi prenos 0 ampersand 1, bone ke, tro, tuj esti 0, ĉar por tio maldekstra esprimo esti vera aŭ 1, ĝi devas esti vera kaj vera. Sed ĉi tie ni havas falsan kaj vera, aŭ 0 kaj 1. Nun ree, se ni havas 1 ampersand 0, kiu ankaŭ tuj esti 0, kaj se ni havas 1-simbolo 1, fine ni havas 1 bito. Do alivorte, ni ne faras ion interesan kun ĉi operatoro nur ankoraŭ, ĉi-simbolo operatoro. Estas la bitlarĝa KAJ operatoro. Sed jen estas la ingrediencoj per kiu ni povas fari interesaj aferoj, kiel ni baldaŭ vidos. 

Nun ni rigardu nur la sola vertikala stango super tie sur la dekstra. Se mi havas 0 iom kaj mi AŬ ĝin kun la bitlarĝa OR operatoro, alia 0 iom, ke tuj doni al mi 0. Se mi prenos 0 brido kaj AŬ ĝin kun a 1 bito, tiam mi tuj ricevas 1. Kaj fakte, nur por klareco, lasu min reiri, Kaj miajn vertikala stangoj ne eraris ĉar 1-a. Lasu min reverki ĉiujn mia 1 estas iom pli klare, por ke ni sekva rigardu: se mi esti ĉirkaŭ 1 aŭ 0, ke tuj esti 1, kaj se mi havas 1 aŭ 1 kiu, tro, tuj esti 1. Do vi povas vidi logike ke la AŬ operatoro kondutas tre malsame. Tio donas min 0 aŭ 0 donas min 0, sed ĉiu alia kombino donas min 1. Tiom longe kiel mi havas unu 1 en la formulo, la rezulto tuj estos 1. 

Kompare kun la KAJ operatoro, la signo, nur se mi havas du 1-a en la ekvacio, do mi reale preni ĉirkaŭ 1 el. Nun tie estas kelkaj aliaj operatoroj ankaŭ. Unu el ili estas iom pli implikitaj. Do lasu min antaŭeniri kaj forviŝi ĉi liberigi iun spacon. Kaj ni rigardu la tekstkursoran simbolo, por nur momento. Tiu estas tipe karaktero vi povas tajpi sur via klavaro okazigon Shift kaj tiam unu el la nombroj atop via usonaj klavaro. 

Do tiu estas la ekskluziva OR operatoro, ekskluziva AŬ. Do ni nur vidis la OR operatoro. Tio estas la ekskluziva AŬ operatoro. Kio estas fakte la diferenco? Bone ni nur rigardas la formulo, kaj uzi tion kiel ingrediencoj finfine. 0 XOR 0. Mi tuj diros estas ĉiam 0. Jen la difino de XOR. 0 XOR 1 tuj esti 1. 1 XOR 0 tuj esti 1, kaj 1 XOR 1 tuj estos? Malĝusta? Aŭ dekstra? Mi ne scias. 0. Nun kio okazas ĉi tie? Nu pensu pri la nomo de tiu operatoro. Ekskluziva AŬ, tiel kiel la nomo, ia, sugestas, la respondo estas nur tuj estos ĉirkaŭ 1 se la enigoj estas ekskluzivaj, ekskluzive malsamaj. Do jen la enigoj estas la samaj, do la eligo estas 0. Tie la enigoj estas la samaj, do la eligo estas 0. Jen la eliroj estas malsama, ili estas ekskluzivaj, do la eligo estas 1. Do ĝi estas tre simila al KAJ, ĝi estas tre simila, aŭ prefere ĝi estas tre simila al AŬ, sed nur en ekskluziva maniero. Ĉi tiu jam ne estas 1, ĉar ni havas du 1-a, kaj ne ekskluzive, nur unu el ili. Bone. Kio pri la aliaj? Nu la supersigno, dume, estas vere bela kaj simpla, dankeme. Kaj tiu estas unuloka operatoro, kiu signifas ĝi estas aplikita al nur unu enigo, unu argumento, por tiel diri. Ne al maldekstra kaj dekstra. Alivorte, se vi prenos de supersigno 0, la respondo estos la malo. Kaj se vi prenos supersigno de 1, la respondo estos la malo. Do la supersigno operatoro estas maniero nei iom, aŭ klakanta iom el 0 al 1, aŭ 1 al 0. 

Kaj tio lasas por ni fine kun nur du finaj operatoroj, la tn maldekstra movo, kaj la tn dekstra skipa operatoro. Ni rigardu kiel tiuj laboroj. La maldekstra skipa operatoro, skribita kun du angulajn krampojn tiel, operacias kiel sekvas. Se mia enigo, aŭ mia argumento al la maldekstra skipa operatoro estas sufiĉe simple 1. Kaj mi diru ke la komputilo lasis movo ke 1, diru sep lokoj, la rezulto estas kvazaŭ mi preni ke 1, kaj movi ĝin sep lokoj trans la maldekstra, kaj defaŭlte, ni tuj supozi ke la spaco dekstren tuj esti suplementata nuloj. Alivorte, 1 lasis movo 7 tuj doni min ke 1, sekvita per 1, 2, 3, 4, 5, 6, 7 nuloj. Do en maniero, ĝi permesas preni malgrandan nombron kiel 1, kaj klare fari ĝin multe multe, multe pli granda en tiu maniero, sed ni vere tuj vidos pli ruza alproksimiĝojn por ĝi anstataŭe, tiel, 

Bone. Estas tio por semajno tri. Ni vidos vin proksima fojo. Ĉi estis CS50. 

[MUZIKO Ludante] 

Parolanto 1: Li estis ĉe la manĝeto bari manĝi varman fudge sundae. Li havis ĝin sur lian vizaĝon. Li portas ke ĉokolado kiel barbo Parolanto 2: Kion vi faras? Parolanto 3: Hmmm? Kio? 

Parolanto 2: Ĉu vi ĵus duobla ekfalo? Vi duobla trempis la blato. Parolanto 3: Pardonu. Parolanto 2: Vi trempis la blato, vi prenis mordon, kaj vi trempis denove. Parolanto 3: Parolanto 2: Do jen kiel meti via tuta busxo bone ekfalo. Sekvanta tempo vi prenas blato, nur trempu gxin unufoje, kaj fini ĝin. 

Parolanto 3: Vi scias kion, Dan? Vi trempu la maniero kiun vi volas trempi. Mi trempos la vojo ke mi volas trempu.