>> [MUZIKO ludi]
DAVID Malan: Bone.
Bone, bonvenigas dorso.
Do tiu estas Semajno 4, la komenco gxia jam.
Kaj vi memoras, ke pasintsemajne, ni metis kodi flanken por nur iom
kaj ni komencis paroli iom pli alta nivelo, pri aferoj kiel
serĉi kaj ordigi, kiu kvankam iom simplaj ideoj, estas
reprezentanto de klaso de problemoj vi komencos solvi aparte
kiel vi komencas pensi fino projektoj kaj interesaj solvoj vi
eble devus reala mondo problemojn.
Nun bobelo varo estis unu el la plej simpla tiaj algoritmoj, kaj ĝi
laboris por havi tiujn malgrandajn nombrojn en lerta aŭ en tabelo speco de
bobelo sian vojon sur la supron, kaj la grandaj nombroj movi sian vojon malsupren al
la fino de tiu listo.
>> Kaj memoru ke ni povus bildigi bobelo speco iom
iu kiel ĉi tio.
Do lasu min antaŭeniri kaj klaku Start.
Mi antaŭselektita bobelo varo.
Kaj se vi memoras, ke la alta blua linioj reprezentas grandaj nombroj, malgranda
bluaj linioj reprezentas malgrandaj nombroj, kiel ni iru tra tiu denove kaj denove kaj
denove, komparas du trinkejoj apud ĉiu aliaj en ruĝa, ni tuj interŝanĝi la
plej granda kaj la plej malgranda se ili estas el ordo.
>> Do tiu iros kaj iros kaj iri on, kaj vi vidos, ke la pli granda
elementoj faras sian vojon al la rajto, kaj la plej malgranda eroj estas
fari sian vojon al la maldekstra.
Sed ni komencis kvantigi la efikeco, la
kvaliton de ĉi tiu algoritmo.
Kaj ni diris ke en la plej malbona kazo, ĉi tiu algoritmo prenis
proksimume kiom da paŝoj?
>> Do la n kvadratoj.
Kaj kio estis n?
>> Spektantaro: Nombro da elementoj.
>> DAVID Malan: Do la n estis la nombro de elementoj.
Kaj tiel ni faros ĉi ofte.
Ajna tempo ni volas paroli pri la grandeco de problemo aŭ la grandeco de
enigo, aŭ la kvanto de tempo necesa por produkti eliro, ni nur
ĝeneraligita ajn la enigo estas kiel n.
Do denove en Semajno 0, la nombro paĝoj en la telefono libro estis n.
La nombro de studentoj en la ĉambro estis n.
Do jen, tro, ni sekvi ke mastro.
>> Nun n kvadratoj estas ne aparte rapida, do ni provis fari pli bone.
Kaj tiel ni rigardis paro de aliaj algoritmoj, inter kiuj
estis selektado varo.
Do selektado varo estis iom malsama.
Ĝi estis preskaŭ pli simpla, mi kuraĝas diri, per kiu mi komencis je la komenco de la
Listo de niaj volontuloj kaj mi ĵus denove kaj denove kaj denove iris tra
la listo, plukinte el la plej malgranda elemento samtempe kaj metante lin aŭ
ŝi komence de la listo.
>> Sed tio ankaŭ, iam ni komencis pensi tra la matematiko kaj pli granda
bildo, pensis pri kiom da fojoj Mi tuj tien kaj reen kaj reen
kaj reen, ni diris en la plej malbona kazo, selektado varon, ankaŭ, estis kio?
n akordis.
Nun en la reala mondo, ĝi povus reale esti bagatele rapida.
Ĉar denove, mi ne devis subteni backtracking fojon mi estis ordigitaj la
plej malgranda eroj.
Sed se ni pensas pri tre granda n, kaj se vi speco de fari el la matematiko, kiel
Mi faris sur la tabulo, kun la n kvadratoj minus io, ĉio alia
krom la n kvadratoj, fojo n ricevas vere granda, ne
vere gravas tiel.
Do kiel komputikistoj, ni ordigi de turnu la okulojn al la plej malgranda
faktoroj kaj fokuso nur sur la faktoron esprimo kiu tuj fari
la plej granda diferenco.
>> Nu, laste, ni rigardis ĉe inserción varo.
Kaj tio estis simila en spirito, sed anstataŭ iri tra ripete kaj
selektu la plej malgranda ero unu ĉe tempo, mi anstataŭe prenis la manon, kiun Mi
komercis, kaj mi decidis, ĉiuj Bone, vi apartenas ĉi tie.
Poste mi iris al la sekva elemento kaj ili decidis ke li aŭ
ŝi apartenis tie.
Kaj poste mi kopiis kaj plu.
Kaj mi povus al, survoje, ŝanĝi tiuj infanoj por
fari lokon al ili.
Do tio estis speco de la mensa renversigon de selektado varo kiu ni
vokis inserción varo.
>> Tiuj temoj okazi en la reala mondo.
Nur antaŭ kelkaj jaroj, kiam iu senatano kuris al prezidanto,
Eric Schmidt, en la tempo de la ĝenerala direktoro de Google, efektive havis la ŝancon
intervjui lin.
Kaj ni pensis ke ni volas dividi tiun YouTube detranĉi al vi tie, se ni povus turni supren
la volumon.
>> [VIDEO reprodukto]
>> -Nun, Senatano, vi estas ĉi tie en Google, kaj mi ŝatas pensi pri la prezidanteco
kiel laboron intervjuo.
>> [Ridado]
>> -Nun estas malfacile akiri laboron kiel prezidanto.
Kaj vi iros tra la rigorecoj nun.
Ĝi estas ankaŭ malfacile atingi laboron ĉe Google.
Ni havas demandojn kaj ni petas niaj kandidatoj demandoj.
Kaj ĉi tiu estas de Larry Schwimmer.
>> [Ridado]
-Vi infanoj pensas ke mi ŝercas?
Ĝi estas ĉi tie.
Kio estas la plej efika maniero ordigi miliono du bitoj entjeroj?
>> [Ridado]
>> -Nu, uh -
>> -I'm sorry.
Eble ni devus -
>> -Ne, ne, ne, ne, ne.
>> -Tio ne estas -
Akcepti.
>> -Mi kredas ke la bobelo speco estus esti la malĝusta maniero iri.
>> [Ridado]
>> [Huraado kaj aplaŭdoj]
>> -Venu, kiu rakontis al li tion?
Akcepti.
>> [FINO reprodukto de vídeo]
>> DAVID Malan: Do vi havas ĝin.
Do ni komencis kvantigi tiuj kurante tempoj, por tiel diri, per io
vokis asimptota skribmaniero, kiu estas nur referenco al nia speco de turnante
blinda okulo al tiuj malgrandaj faktoroj kaj nur rigardante la rula tempo,
la agado de ĉi tiuj algoritmoj, kiel n prenas vere granda tempo.
Kaj tiel ni enkondukis granda O. Kaj granda O reprezentis iu kiun ni pensis
de kiel supera baro.
Kaj efektive, Barry, ĉu ni povas malsupreniri ol la mic iomete?
>> Ni pensis pri ĉi tiu estas supera baro.
Tiel granda O de n kvadratoj signifas ke en la plej malbona kazo, iun kiel
selektado speco prenus n kvadrata paŝoj.
Aŭ ion similan inserción speco farus n kvadratoj paŝoj.
Nun por iu kiel inserción varon, kio estis la plej malbona kazo?
Donita aro, kio estas la plej malbona ebla scenaro, ke vi povus trovi
mem alfrontis kun?
>> Estas tute malantaŭen, ĉu ne?
Ĉar se ĝi estas tute malantaŭen, vi devas fari tutan multe da laboro.
Ĉar se vi estas tute malantaŭen, vi tuj trovos la
plej granda elemento tie, eĉ se ĝi apartenas tie.
Do vi intencas diri, gravas, ĉe ĉi tiu momento en tempo, vi apartenas ĉi tie,
tiel vi lasas ĝin sola.
>> Tiam vi rimarkos, ho, malbenita, mi devas movi tiun iomete pli malgranda elemento
maldekstre de vi.
Do mi devos fari tion denove kaj denove kaj denove.
Kaj se mi iradis tien kaj reen, vi estus ordigi de senti la agado de
ke algoritmo, ĉar senĉese estas mi miksanta ĉiuj aliaj malsupren en la
tabelo por fari lokon por ĝi.
Do jen la plej malbona kazo.
>> Kontraŭe -
kaj ĉi tiu estis cliffhanger lasta fojo -
ni diris ke inserción speco Estis omega de kio?
Kio estas la plej kazo kurado tempo de inserción speco?
Do ĝi estas reale n.
Tio estis la celo, ke ni lasis sur la tabulo lasta fojo.
>> Kaj estas omega de n ĉar por kio?
Nu, en la plej bona kazo, kio estas inserción speco tuj estos transdonita?
Nu, lerta, ke estas tute ordo jam, minimuma laboro por fari.
Sed kio estas neta pri inserción speco estas ke ĉar ĝi komenciĝas ĉi tie kaj
decidas, ho, vi estas la nombro unu, vi apartenas ĉi tie.
Ho, kia bona fortuno.
>> Vi estas la numero du.
Vi apartenas ankaŭ ĉi tie.
Numero tri, eĉ pli bone, vi apartenas ĉi tie.
Tuj kiam ĝi alvenas al la fino de la listo, por inserción speco de _pseudocode_
ke ni promenis tra parole lasta fojo, ĝi estas farita.
Sed selektado varon, per kontrasto, tenis fari kion?
>> Tenis irante tra la listo denove kaj denove kaj denove.
Ĉar la ŝlosilo komprenon estis nur iam vi rigardis la tutan vojon al la
fino de la listo vi povas esti certa ke la elemento vi selektis estis
ja la nuntempe plej malgranda ero.
Do tiuj malsamaj mensaj modeloj fino cedante iuj tre reala mondo
diferencoj por ni, tiel kiel tiuj teoria asimptota diferencoj.
>> Do nur por recap do granda O de n kvadrata, ni vidis kelkajn tiajn
algoritmoj tiom.
Granda a de n?
Kio estas algoritmo kiu povis esti dirita al esti granda O de n?
En la plej malbona kazo, ĝi prenas lineara nombro da paŝoj.
>> OK, lineara serĉo.
Kaj en la plej malbona kazo, kie estas la elemento vi serĉas kiam
aplikante lineara serĉo?
>> OK, en la plej malbona kazo, ĝi ne estas ankoraŭ tie.
Aŭ en la dua plej malbona kazo, ĝi estas tuta vojo al la fino, kiu estas
pli-aŭ-minus unu-paŝo diferencon.
Do, je la fino de la tago, ni povas diri estas lineara.
Granda a de n devus esti lineara serĉo, ĉar en la plej malbona kazo, la
elemento estas eĉ ne ekzistas aŭ estas tuta vojo al la fino.
>> Nu, granda O de logo de n.
Ni ne parolas tre detale pri ĉi tio, sed ni vidis ĉi tion antaŭe.
Kio kuras en tn logaritma tempo, en la plej malbona kazo?
>> Jes, tiel duuma serĉo.
Kaj duuma serĉo en la plej malbona kazo povus havi la elemento ie en
la meza, aŭ ie ene de la tabelo.
Sed vi nur trovos ĝin iam vi dividi la liston en duono, en
duono, la duono, la duono.
Kaj tiam voilà, estas tie.
Aŭ denove, plej malbona kazo, ĝi ne estas ankoraŭ tie.
Sed vi ne scias ke ĝi ne estas tie ĝis vi ia atingi tiun lastan
fundo-plej elementojn per _halving_ kaj _halving_ kaj _halving_.
>> Granda a de 1.
Do ni povus granda O de 2, granda O de 3.
Anytime vi volas nur konstanta numeron, ni simple ordigi de iom simpligi
ke kiel granda O de 1.
Kvankam se realisme, preno 2 aŭ eĉ 100 paŝoj, se estas
konstanta nombro da paŝoj, ni simple diru granda O de 1.
Kio estas algoritmo kiu estas en granda a de 1?
>> Spektantaro: Trovanta la longo de variablo.
>> DAVID Malan: Trovanta la longo de variablo?
>> Spektantaro: Ne, la longo se ĝi estas jam ordo.
>> DAVID Malan: Bonan.
Bone, do trovi la longo de io se la longo de tiu io, kiel
tabelo, estas stokita en iu variablo.
Ĉar vi povas simple legis la variablo, aŭ presi la variablo, aux
nur ĝenerale konsentas, ke variablo.
Kaj voilà, kiu prenas konstantan tempo.
>> Por kontrasto, pensu reen al skrapi.
Pensu reen al la unua semajno de C, nomante nur printf kaj presi
iun sur la ekrano estas nediskuteble konstanta tempo, ĉar ĝi nur prenas
iu numero de CPU cikloj montri ke teksto sur la ekrano.
Aŭ atendu - faras ĝin?
Kiel alia eble ni modeligi la agado de printf?
Ĉu iu ŝatus malkonsentas, ke eble ĝi ne estas vere konstanta tempo?
En kiu senco povus printf estas kurante tempo, vere presi ĉenon sur
la ekrano, esti io alia ol konstanta.
>> Spektantaro: [inaudibles].
>> DAVID Malan: Jes.
Do ĝi dependas nia perspektivo.
Se ni vere pensas pri la enigo al printf kiel la kordo, kaj
do ni mezuri la grandecon de tiu enigo de ĝia longo - do ni nomas
ke longo n tiel -
nediskuteble, printf estas sin granda O de n ĉar tuj prenos vin n paŝoj
por presi ĉiu el tiuj n karakterojn, plej probabla.
Almenaŭ en la mezuro ke ni supozi ke eble ĝi estas uzanta por buklo
sub la kapuĉo.
>> Sed ni devus rigardi ke kodi kompreni ĝin pli bone.
Kaj efektive, post kiam vi infanoj komencu analizi vian propran algoritmoj, vi
laŭvorte fari ĝuste tion.
Speco de okulo via kodo kaj opinias pri - bone, mi havas buklo
ĉi tie aŭ Mi havas nestitaj maŝojn tie, ke tuj faros n aĵoj n fojoj,
kaj vi povas ordigi de racio vian vojon tra la kodon, eĉ se ĝi estas
_pseudocode_ kaj ne reala kodo.
>> Do kio pri omega de n kvadratoj?
Kio estis algoritmo kiu en la plej bona kazo, ankoraŭ prenis n kvadrataj gradoj?
Jes?
>> Spektantaro: [inaudibles].
>> DAVID Malan: Do selektado varo.
Ĉar en tiu problemo vere reduktita al la fakto ke denove, mi ne scias
Mi trovis la nuna malgranda ĝis Mi kontrolis ĉiujn Darn elementoj.
Do omega de, ekzemple, n, ni nur suprenvenis kun tiu.
Insertion varo.
Se la listo okazas esti ordo Jam, en la plej bona kazo nur devas
por fari unu pasas tra ĝi, je kiu punkto ni estas certa.
Kaj tiam tiu povus diri esti lineara, sekura.
>> Kio pri omega de 1?
Kio, en la plej bona kazo, povus preni konstanta nombro da paŝoj?
Do lineara serĉo, se vi simple akiri bonŝanca kaj la elemento vi serĉas
Estas ĝuste en la komenco de la listo, se tio estas kie vi estas startanta via
lineara trairado de tiu listo.
>> Kaj ĉi tiu estas vera de nombro de aĵoj.
Ekzemple, eĉ duumaj serĉo estas omega de 1.
Pro kio se vi ricevas vere Darn sorton kaj smack-DAB en la mezo de
via tabelo estas la nombro vi serĉas?
Do vi povas akiri bonŝanca tie, kiel bone.
>> Ĉi tiu, laste, omega de n logo n.
Do n logo n, ni ne vere paroli ankoraŭ, sed -
>> Spektantaro: Kunfandi speco?
>> DAVID Malan: Merge varo.
Tio estis la cliffhanger de lasta fojo, kie oni proponis, kaj ni montris
vide, ke ekzistas algoritmoj.
Kaj kunfandi speco de nur unu tia algoritmo kiu estas fundamente rapida
ol iuj el tiuj aliaj infanoj.
Fakte, kunfandi mallonga ne estas nur en la bona kazo n logo n, en la plej malbona
kazo n logo n.
Kaj kiam vi havas ĉi koincido de omega kaj granda O estas la sama afero?
Ni povas vere priskribi ke kiel kio estas vokis theta, kvankam ĝi estas
iom malpli komunaj.
Sed tio nur signifas la du baroj, en ĉi tiu kazo, estas la sama.
>> Do kunfandi varon, kion faras tiu vere boli malsupren al por ni?
Nu, memoru la motivado.
Lasu min eltiri alian kuraĝigo kiu Ni ne rigardu lasta fojo.
Ĉi tiu, sama ideo, sed ĝi estas iom pli granda.
Kaj mi tuj iros antaŭen kaj atentigi unua - ni havas inserción speco de
supre maldekstre, tiam selektado varon, bobelo varon, paro de aliaj varoj -
konko kaj rapidaj - ke ni ne parolis pri, kaj amaso kaj kunfandi varo.
>> Do almenaŭ provi enfokusigi viajn okulojn la supro tri sur la maldekstra kaj poste
kunfandi speco kiam mi premas tiu verda sago.
Sed mi permesos ĉiuj ili kuras, nur por doni al vi la senton de la diverseco de
algoritmoj kiuj ekzistas en la mondo.
Mi tuj liberigos tiun run por nur kelkajn sekundojn.
Kaj se vi enfokusigi la okulojn - elektu algoritmo, enfokusigi ĝin por nur
duaj - vi komencos vidi la mastro ke ĝi estas apliko.
>> Kunfandi varon, avizo, estas farita.
Multigu varon, rapida varon, konko -
do ŝajnas al ni enkondukis la tri plej malbona algoritmoj pasintsemajne.
Sed tio estas bone, ke ni estas ĉi tie hodiaŭ rigardi merge varon, kiu estas unu el
des pli facile ones estas rigardi, eĉ kvankam ĝi probable estos fleksi via menso
malmulta.
Ĉi tie ni povas vidi kiom da selektado speco sucks.
>> Sed sur la turnon flanko, estas vere facile apliki.
Kaj eble por P Serio 3, kiu estas unu el la algoritmoj vi elektis por apliki
por la normo eldono.
Perfekte bone, perfekte ĝustaj.
>> Sed denove, kiel n prenas granda, se vi elekti apliki pli rapida algoritmo
kiel kunfandi varon, prognozoj estas en pli granda kaj granda enigoj, via kodo estas nur
tuj kuri pli rapide.
Via retejo estas tuj pli bone funkcii.
Via uzantoj tuj estos pli feliĉa.
Kaj tiel estas tiuj efektoj de reale donante
ni iom pli profunde pensis.
>> Do ni rigardu kion kunfandi varo estas reale okazas.
La malvarmeta estas kiu kunfandi varo estas ĝuste ĉi tiu.
Jen, denove, kion ni nomas _pseudocode_, _pseudocode_ estaĵo
Esperanto-simila sintakso.
Kaj la simpleco estas speco de fascina.
>> Do enigo de n elementoj - tiel ke nur signifas, jen tabelo.
Ĝi atingis n aĵoj en ĝi.
Tio estas ĉio ni dirante tie.
>> Se n estas malpli ol 2, reveni.
Do tio estas nur la bagatela afero.
Se n estas malpli ol 2, tiam evidente estas 1 aŭ 0, en kiu kazo la afero
Jam ordo aŭ neekzistanta, tiel simple reveni.
Estas nenio por fari.
Do tio estas simpla kazo desxiri malproksime.
>> Alie, ni havas tri paŝoj.
Ordigi la maldekstra duono de la elementoj, speco la dekstra duono de la elementoj,
kaj poste kunfandi la ordo duonoj.
Kio estas interese estas, ke Mi estas speco de punting, ĉu ne?
Estas speco de cirkla difino al ĉi algoritmo.
En kiu senco ĉi tiu algoritmo estas difino cirkuli?
>> Spektantaro: [inaudibles].
>> DAVID Malan: Jes, mia ordigado algoritmo, du de liaj paŝoj estas "speco
io. "Kaj tial petas la demando, nu, kion mi povos uzi
ordigi la maldekstra duono kaj la dekstra duono?
Kaj la beleco estas, ke kvankam denove, ĉi tiu estas la menso-fleksante
parto potenciale, vi povas uzi saman algoritmo por ordigi la maldekstra duono.
>> Sed atendu momenton.
Kiam vi diris ordigi la maldekstra duono, kio estas la du
paŝoj tuj estos poste?
Ni ordigi la maldekstra duono de la maldekstra duono kaj la rajto
duonon de la maldekstra duono.
Malbenita, kiel mi ordigi tiujn du duonoj aux kazernoj, nun?
>> Sed tio estas okej.
Ni havas ordiga algoritmo tie.
Kaj eĉ se vi povus maltrankviligi ĉe unue tio estas speco de senfina
buklo, estas ciklo tio neniam tuj enfluos - tuj
fini unufoje kio okazas?
Iam n estas malpli ol 2.
Kiu eventuale okazos, ĉar se vi observos kaj _halving_
_halving_ en _halving_ tiuj duonoj, verŝajne eventuale vi tuj enfluos
kun nur 1 aŭ 0 elementoj.
Je kiu punkto, ĉi tiu algoritmo Diras vi faris.
>> Do la vera magio en tiu algoritmo ŝajnas esti en
tiu fina paŝo, kunfandante.
Tiu simpla ideo nur kunfandi du aferoj, tio estas kio finfine irante
por permesi al ni ordigi tabelo de, diru, ok elementoj.
Do mi havas ok pli streso pilkojn supren ĉi tie, ok pecoj de papero, kaj unu
Google Vitra -
kiun mi ricevas gardi.
>> [Ridado]
>> DAVID Malan: Se ni povus preni ok volontuloj, kaj ni vidu, se ni povas
ludi ĉi, do.
Wow, OK.
Komputika fariĝas amuzo.
Ĉio bone.
Do kiel pri vi tri, grandaj manoj tie supre.
Kvar en la dorso.
Kaj kion pri ni faros vin tri en tiu vico?
Kaj kvar en la fronto.
Do vi ok, venu supren.
>> [Ridado]
>> DAVID Malan: Mi estas reale ne certas kion ĝi estas.
Ĉu la streso pilkoj?
La tablo lampojn?
La materialo?
La interreto?
>> Akcepti.
Do venu supren.
Kiu ŝatus -
teni venas supren.
Ni vidu.
Kaj ĉi tio metas vin en situo -
vi estas en loko unu.
Uh-oh, atendu momenton.
1, 2, 3, 4, 5, 6, 7 - ho, bona.
Bone, ni estas bona.
Bone, do ĉiuj havas sidejon, sed ne sur la Google Pokalo.
Lasu min vosto tiuj supren.
Kio estas via nomo?
>> Michelle: Michelle.
>> DAVID Malan: Michelle?
Bone, vi akiras por simili la geek, se tio estas okej.
Nu, mi ne faras tro, mi supozas, por nur momento.
Bone, atendas.
Ni estis provante supreniru kun uzi kazo por Google Pokalo, kaj ni
pensis ke estus amuze nur faru tiu, kiam homoj estas scenejo.
Ni registros la mondo de lia perspektivo.
Ĉio bone.
Ne verŝajne kio Google intencita.
Bone, se vi ne atentas portante tiu por la sekvanta mallerta minutoj,
kiu estus mirinda.
>> Bone, do ni havas ĉi tie tabelo de elementoj, kaj tiu tabelo, kiel por la
pecoj de papero en ĉi tiuj uloj ' manoj, nuntempe Unsorted.
>> Michelle: Ho, tio estas tiom stranga.
>> DAVID Malan: Estas sufiĉe multe hazardo.
Kaj en nur momente, ni tuj provi apliki kunfandi speco kune
kaj vidu kie tiu ŝlosilo komprenon estas.
Kaj la artifiko ĉi tie kun merge varo estas iu kiun ni ne supozis ankoraŭ.
Ni vere bezonas iun plia spaco.
Do kio okazas al esti aparte interesa pri tio estas, ke tiuj
infanoj tuj movi iom iom, ĉar mi tuj supozi ke
ekzistas ekstra tabelo de spaco, diri, ĝuste malantaŭ ili.
>> Do, se ili estas malantaŭ lia seĝo, tio estas la malĉefa tabelo.
Se ili estas sidas ĉi tie, tio estas la ĉefa tabelo.
Sed tio estas rimedo, kiun ni havas ne leveraged tiel for kun bobelo
varo, kun elekto varon, kun inserción varo.
Memori pasintsemajne, ĉiuj nur speco de ludkartaro en loko.
Ili ne uzis neniu plia memoro.
Ni faris spacon por homoj de movi homoj ĉirkaŭe.
>> Do tiu estas ŝlosila komprenon, ankaŭ.
Estas ĉi tiu kompromiso, ĝenerale en komputiko, de rimedoj.
Se vi volas rapidigi ion kiel tempo, vi tuj
devas pagi prezon.
Kaj unu el tiuj prezoj estas tre ofte spaco, la kvanto de memoro aŭ malmola
diskspaco ke vi uzas.
Aŭ, sincere, la kvanto de programisto tempo.
Kiom da tempo prenas al vi, la homo, al reale efektivigi iujn pli
komplika algoritmo.
Sed por hodiaŭ, la kompromiso estas tempo kaj spaco.
>> Do se vi infanoj povus simple teni vian nombroj do ni povas vidi ke vi estas
ja kongruas 4, 2, 6, 1, 3, 7, 8.
Bonega.
Do mi tuj provos orquestar aĵoj, se vi infanoj povas simple
sekvas mian plumbo tie.
>> Do mi tuj apliki, unue, la unua paŝo de la _pseudocode_, kiu estas
sur enigo de n eroj, se n estas malpli ol 2, tiam revenu.
Evidente, ke ne validas, do ni pluiru.
Do ordigi la maldekstra duono de la elementoj.
Do tio signifas ke mi tuj enfokusigi mia atenton por nur momente sur tiuj
kvar infanoj tie.
Bone, kion mi sekva fari?
>> Spektantaro: ordigi la maldekstra duono.
>> DAVID Malan: Do nun mi devas ordigi la maldekstra duono de tiuj infanoj.
Ĉar denove, supozi al vi mem la celo estas ordigi la maldekstra duono.
Kiel vi faris tion?
Nur sekvi la instrukciojn, eĉ kvankam ni faras ĝin denove.
Do ordigi la maldekstra duono.
Nun mi ordiga tiuj du infanoj.
Kio venas tuj?
>> Spektantaro: ordigi la maldekstra duono.
>> DAVID Malan: ordigi la maldekstra duono.
Do nun ĉi tiuj, tiu seĝo ĉi tie, estas listo de amplekso 1.
Kaj kio estas via nomo denove?
>> PRINCINO lekanto: Princino Lekanto.
>> DAVID Malan: Princino Lekanto estas ĉi tie.
Kaj tiel ŝi jam ordo, ĉar la listo estas de amplekso 1.
Kion mi sekva fari?
OK, revenu, ĉar tiu listo estas de grandeco 1, kiu estas malpli ol 2.
Tiam kio estas la sekva paŝo?
Kaj nun vi devas speco de backtrack en via menso.
>> Ordigi la dekstran duonon, kiu estas -
kio estas via nomo?
>> Linda: Linda.
>> DAVID Malan: Linda.
Kaj do kion ni faru nun ke ni havas liston de amplekso 1?
>> Spektantaro: Reveno.
>> DAVID Malan: Zorga.
Ni revenos unua, kaj nun la tria paŝo - kaj se mi specon de bildigas ĝin
brakumante la du seĝoj nun, nun mi devas mem kunfandi tiujn du elementoj.
Do nun, bedaŭrinde, la elementoj estas ekstere de ordo.
Sed tio estas kie la kunfandi procezo komencas akiri konvinka.
>> Do se vi infanoj povis ekstari por nur momento, mi tuj bezonas vin, en
Nuntempe, por treti malantaux vian seĝon.
Kaj se Linda, ĉar 2 estas pli malgranda ol 4, kial ne
vi venis ĉirkaŭ la unua?
Restu tie.
Do Bela, vi alvenis ĉirkaŭ unue.
>> Nun en la realo, se estas nur tabelo ni povus simple movi sxin en reala tempo
el tiu ĉi seĝo ĉi loko.
Do imagu, ke prenis iu konstanto nombro de paŝoj 1.
Kaj nun -
sed ni bezonas meti vin en la unua loko tie.
>> Kaj nun se vi povus veni ĉirkaŭe, tiel, ni tuj
esti en loko du.
Kaj eĉ se tio sentas kiel ĝi estas preni iom da tempo, kio estas agrabla nun estas
ke la maldekstra duono de la maldekstra duono estas nun ordo.
Do kio estas la sekva paŝo, se ni nun malantaŭenigi plu en la rakonto?
>> Spektantaro: Dekstra duono.
>> DAVID Malan: ordigi la dekstra duono.
Do you guys devas fari tion, tiel.
Do, se vi povus ekstari por nur momenta?
Kaj kio estas via nomo?
>> Jess: Jess.
>> DAVID Malan: Jess.
Bone, do Jess estas nun la maldekstra duono de la dekstra duono.
Kaj tiel ŝi estas listo de amplekso 1.
Ŝi evidente ordo.
Kaj via nomo denove?
>> Michelle: Michelle.
>> DAVID Malan: Michelle estas evidente listo de amplekso 1.
Ŝi jam ordo.
Do nun la magion okazas, la kunfandi procezo.
Do, kiu tuj veni antaŭe?
Evidente Michelle.
Do se vi povus veni ĉirkaŭ dorso.
La spaco ni havas disponebla por ŝi nun estas ĝuste malantaŭ tiu seĝo tie.
Kaj nun se vi povus veni reen kiel bone, ni nun havas, esti klara, du
duonoj, ĉiu de amplekso 2 -
kaj ĝuste por bildigo de sake, se vi povus fari iom da spaco -
tiu eliris duono tie, unu dekstra duono tien.
>> Malantaŭenigi plu en la rakonto.
Kio paŝo estas poste?
>> Spektantaro: Merge.
>> DAVID Malan: Do nun ni devas mem kunfandi.
Do okej, do nun, feliĉe, ni nur liberigita ĝis kvar seĝoj.
Do ni uzis duoble da memoro, sed ni povas doni flip-flopping inter
la du tabeloj.
Do kiu nombro estas veni antauxe?
Do Michelle, evidente.
Do venu ĉirkaŭe kaj prenu Via sidejo ĉi tie.
Kaj tiam nombro 2 estas evidente sekva, do vi venis ĉi tien.
Numero 4, numero 6.
Kaj denove, kvankam tie estas iomete da marŝante implikitaj,
vere, tiuj povus okazi tuj, movante unu -
Bone, bone ludis.
>> [Ridado]
>> DAVID Malan: Kaj nun ni estas en sufiĉe bona formo.
La maldekstra duono de la tuta enigo estas nun ordo.
Bone, do tiuj infanoj havis la avantaĝo de mia -
kiamaniere ĝi finos ĉiuj la knabinoj sur la forlasis kaj ĉiuj knaboj sur la dekstra?
>> Bone, do infanoj 'turnu nun.
Do mi ne iros tra vi tiuj paŝoj.
Ni vidos se ni povas rekandidatiĝi la sama _pseudocode_.
Se vi volas antaŭeniri kaj levigxu, kaj vi, knaboj, mi donos al vi la mic.
Vidu se vi ne povas repliki kio Ni ĵus faris tie sur la
alia fino de la listo.
Kiu bezonas paroli unua, bazitaj sur la algoritmo?
Do klarigi kion vi faras antaŭe vi faros neniun piedo movadoj.
>> Parolanto 1: Bone, do ekde Mi estas la maldekstra duono de la
maldekstra duono, mi revenos.
Ĝuste?
>> DAVID Malan: Bonan.
>> Parolanto 1: Kaj tiam -
>> DAVID Malan: Kiu faras la mic iri al poste?
>> Parolanto 1: Next nombro.
>> Speaker 2: Do mi estas la dekstra duono de la maldekstra duono de la
maldekstra duono, kaj mi revenos.
>> DAVID Malan: Bonan.
Vi revenis.
Do nun kio estas la sekva por vi du?
>> Speaker 2: Ni volas vidi kiu estas pli malgranda.
>> DAVID Malan: Ĝuste.
Ni volas kunfandi.
La spaco ni tuj uzi por kunfandi vin en, kvankam ili estas
evidente ordo jam, ni iras sekvi la saman algoritmon.
Do, kiu iras en reen unua?
Do 3, kaj tiam 7.
Kaj nun la mic iras al ĉi tiuj infanoj, okej?
>> Parolanto 3: Do mi estas la dekstra duono de la maldekstra duono, kaj mia n estas malpli ol
1, do mi simple tuj pasos -
>> DAVID Malan: Bonan.
>> Parolanto 4: Mi estas la dekstra duono de la dekstra duono de la dekstra duono, kaj mi estas
ankaŭ unu persono, tial mi estas tuj revenos.
Do nun ni kunfandi.
>> Parolanto 3: Do ni iru reen.
>> DAVID Malan: Do vi iru en la dorso.
Do 5 iras unue, tiam 8.
Kaj nun publiko, kiu estas la treti ni devas nun malantaŭenigi
apogi al en niaj mensoj?
>> Spektantaro: Merge.
>> DAVID Malan: kunfandi maldekstra duono kaj dekstra duono de la originala maldekstra duono.
Do nun -
kaj justa por fari ĉi tiu klara, fari iom da spaco
inter vi du infanoj.
Do nun jen la du listoj, maldekstra kaj dekstra.
Nu do kiel ni nun kunfandi you guys en la unua vico de seĝoj denove?
>> 3 iras unue.
Tiam 5, evidente.
Tiam 7, kaj nun 8.
Bone, kaj nun ni estas?
>> Spektantaro: Not done.
>> DAVID Malan: Ne farita, ĉar evidente, estas unu paŝo restanton.
Sed denove, la kialo Mi uzas tiun ĵargono kiel "rebobinado en via menso,"
estas ĉar tio estas vere kio okazis.
Ni iras tra ĉiu el tiuj paŝoj, sed ni estas speco de paŭzante por
momento, plonĝado pli profunden en la algoritmo, paŭzante dum momento,
subnaĝado pli profunden en la algoritmo, kaj nun ni devas ordigi de rebobinado en nia
mensoj kaj malfari ĉiuj de ĉi tiuj tavoloj ke ni ia en ĉesigita.
>> Do nun ni havas du listoj de grandeco 4.
Se vi infanoj povis ekstari lasta fojo kaj fari iom da spaco tie por
klarigi ke tiu estas la maldekstra duono de la originalo, la
dekstra duono de la originalo.
Kiu estas la unua numero, ke ni bezonas tiri en la malantaŭan?
Michelle, kompreneble.
>> Do ni metas Michelle tie.
Kaj kiu havas numeron 2?
Numero 2 venas sur dorson tiel.
Numero 3?
Bonega.
Numero 4, numero 5, numero 6, numero 7, kaj la numero 8.
>> Bone, do li sentis kiel multe de paŝoj, por certa.
Sed nun ni vidu se ni ne povas konfirmi speco de intuicie ke tiu
algoritmo fundamente, aparte n ricevas vere granda, kiel ni vidis
kun la kuraĝigoj, estas fundamente rapida.
Do mi asertas tiu algoritmo, en la plej malbona kazo kaj eĉ en la plej bona kazo,
estas granda O de n fojoj logo n.
Tio estas, ne estas iu aspekto de tiu algoritmo kiu prenas n paŝoj, sed
estas alia aspekto ie en ke ripeta, ke looping, ke
prenas logo n paŝoj.
Ĉu ni povas meti nian fingron sur kio tiuj du nombroj estas referanta al?
Nu, kie -
where'd la mic iras?
>> Parolanto 1: Ĉu ensaluti n esti rompi nin en du -
dividanta per du, esence.
>> DAVID Malan: Ĝuste.
Ajna tempo ni vidas en iu ajn algoritmo tiel nun, tie jam pasis tiun bildon de
dividanta, dividante, dividante.
Kaj ĝi estas tipe reduktita al iu kiu estas
logaritma, log bazo 2.
Sed povus esti vere nenion, sed ensaluti bazo 2.
>> Nun kio pri la n?
Mi povas vidi ke ni ia dividita vin infanoj - dividita vi, dividita vi,
dividita vi, dividita vi.
Kie la fino venis?
>> Do estas la fandado.
Ĉar pensi pri ĝi.
Kiam vi kunfandi ok homojn, per kiu duono de ili estas aro de kvar
kaj la alia duono estas alia aro de kvar, how do you go
pri fari la kunfandi?
Nu, vi infanoj faris sufiĉe intuicie.
>> Sed se mi anstataŭ faris ĝin iom pli metode, mi povus indik
la plej maldekstra persono unue kun mia maldekstra manon, indik la plej maldekstra persono
de tiu duono kun mia dekstra mano, kaj nur poste promenis tra la
listo, fingromontrante la plej malgranda ero ĉiu tempo, movante mian fingron sur kaj
super drajvo tra la listo.
Sed kio estas pri tiu klavo kunfandi procezo estas mi komparante tiujn parojn
de elementoj.
De la dekstra duono kaj de maldekstre duono, mi neniam unufoje backtracking.
>> Do la merge mem prenas ne pli ol n paŝoj.
Kaj kiom da fojoj faris mi havas por fari tion kunfandi?
Nu, ne pli ol n, kaj ni simple vidis, ke kun la fina merge.
Kaj do se vi faras iu kiu prenas log n paŝoj n fojoj, aŭ inverse,
ĝi tuj donas al ni n fojoj logo n.
>> Kaj kial estas tiu pli bona?
Nu, se ni jam scias ke log n estas pli bona ol n - ne?
Ni vidis en duuma serĉo, la telefono libro ekzemple, log n estis definitive
pli bona ol lineara.
Do tio signifas n fojoj log n estas definitive pli bona ol n fojojn alian
n, AKA n kvadratoj.
Kaj tio kion ni fine sentas.
>> Tiel granda ronda da aplaŭdoj, se ni povis, por ĉi tiuj infanoj.
>> [Aplaŭdo]
>> DAVID Malan: Kaj via adiaŭa donacoj - sed observu la numerojn,
se vi ŝatus.
Kaj via adiaŭa donaco, kiel kutime.
Ho, kaj ni sendos al vi la materialo, Michelle.
Dankon.
Ĉio bone.
Prenu al streso pilko.
>> Kaj lasu min eltiri supren, dume, nia amiko Rob Bowden proponi
tiel malsama perspektivo pri tio, ĉar vi povas pensi pri tiuj
paŝoj okazas en iom malsama maniero.
Fakte, la aro-ĉe kio Rob temas pri por montri al ni supozas ke ni
jam faris la dividanta supren de la grandan liston en ok malgrandaj lertaj,
ĉiu de amplekso 1.
>> Do ni ŝanĝas la _pseudocode_ a iom simple ordigi de atingi la
kerno ideon de kiel la kunfandi verkoj.
Sed la rula tempo de kio li estas faronta, estas ankoraŭ
tuj estos la sama.
Kaj denove, la starigo de ĉi tie estas ke li estas komencinta kun ok listoj de amplekso 1.
Do vi maltrafis la parto kie li estas efektive plenumis sian log n, logo n, log n
dividante de la enigo.
>> [VIDEO reprodukto]
>> -Estas tio por paŝo unu.
Por paŝo du, ree kunfandi paroj de listoj.
>> DAVID Malan: Hm.
Nur sono venas el mia komputilo.
Ni provu ĉi denove.
>> -Ĝuste arbitre elekti kio - nun ni havas kvar listoj.
Lernu antaŭe.
>> DAVID Malan: Tie ni iru.
>> -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 fini kun 16, 23.
>> Nun ĉiuj niaj listoj de amplekso 2.
Rimarku ke ĉiu el la kvar listoj estas ordigitaj.
Do ni povas starti kunfandi paroj de lertaj denove.
Kunfandi 15 kaj 108 kaj 4 kaj 50, ni unue prenu la 4, tiam la 15, tiam
la 50, tiam la 108.
Kunfandi 8, 42 kaj 16, 23, ni unue prenas la 8, tiam la 16an de tiam la 23,
tiam la 42.
>> Do nun ni havas nur du listoj de grandeco 4, ĉiu el kiuj estas ordo.
Do nun ni kunfandi tiujn du listojn.
Unue, ni prenu la 4, tiam ni prenos la 8, tiam ni prenos la 15, tiam 16, do
23, poste 42, tiam 50, do 108.
>> [FINO reprodukto de vídeo]
>> DAVID Malan: Denove, rimarki, li neniam tusxis donita taso pli ol unu horo
post antaŭi preter ĝi.
Do li neniam ripetas.
Do li ĉiam movi al la bordo, kaj tie estas kie ni poste ricevis nian n.
>> Kial ne lasu min eltiri supren unu kuraĝigo kiun ni vidis antaŭe, sed ĉi tiu tempo
enfokusigante nur sur merge varo.
Lasu min antaŭeniri kaj zomi en ĉi tiu tie.
Unue, mi elektas hazarda eniro, altigi tiun, kaj vi povas ordigi de vidos
kion ni prenis koncedis, pli frue, kunfandi varo estas efektive faras.
>> Do rimarki ke vi ricevas tiujn duonoj aŭ tiuj kvaraj aŭ tiuj okaj de la
problemo kiu subite komenci preni bona formo.
Kaj tiam finfine, vi vidos en la fino ke bam,
ĉiu estas kunfanditaj kune.
>> Do tiuj estas nur tri malsamajn prenas sur la sama ideo.
Sed la ŝlosilo komprenon, kiel dividi kaj venkos en la unua klaso,
estis, ke ni decidis iel dividi la problemo en ion grandan, en
io ia identa en spirito, sed pli malgranda kaj pli kaj pli malgranda
kaj pli malgrandaj.
>> Nun alia amuza maniero por ordigi de opinias pri tiuj, kvankam ĝi ne estas
tuj donos al vi la saman intuicia kompreno, estas
la jena kuraĝigo.
Do tiu estas video iu kunmetita ke asociita malsamajn
sonoj kun la diversaj operacioj por inserción varon, por merge varo, kaj
por paro de la aliaj.
Do, momente, mi tuj batis Play.
Temas pri unu minuto longe.
Kaj eĉ se vi ankoraŭ povas vidi la ŝablonoj okazas, ĉi tiu tempo vi povas
ankaŭ aŭdi kiel tiuj algoritmoj estas agi malsame kaj kun
tiel malsama ŝablonoj.
>> Ĉi tiu estas inserción varo.
>> [Tonoj ludi]
>> DAVID Malan: ĝi estas denove provas insertar ĉiu elemento
en kie apartenas.
Ĉi tiu estas bobelo varo.
>> [Tonoj ludi]
>> DAVID Malan: Kaj vi povas ordigi de sento kiel relative malmulta labori ĝi estas faranta
sur ĉiu paŝo.
Jen kion tediousness sonas.
>> [Tonoj ludi]
>> DAVID Malan: Ĉi tiu estas elekto varon, kie ni elektu la elemento ni volas per
irante tra denove kaj denove kaj denove kaj metante ĝin en la komenco.
>> [Tonoj ludi]
>> DAVID Malan: Ĉi tiu estas kunfandi varon, kiun Vi povas vere komenci senti.
>> [Tonoj ludi]
>> [Ridado]
>> DAVID Malan: Iu nomis gnomo varon, kiun ni ne rigardis.
>> [Tonoj ludi]
>> DAVID Malan: Do lasu min vidi, nun, distris kiel vi espereble estas por la
muziko, se mi povas gliti iom iom da matematiko en ĉi tie.
Do tie estas kvara vojon, kiun ni povas pensi kion signifas tiuj
funkcioj al esti pli rapida ol aĵoj ke ni vidis antaŭe.
Kaj se vi venas je la kurso de de matematiko fono, vi
efektive scias eble jam, ke vi povas vangofrapon termino en tiu tekniko -
nome rekursio, funkcio ke iel nomas sin.
>> Kaj denove, memoru ke merge speco _pseudocode_ estis rekursie en la senco
ke unu el merge speco de paŝoj estis nomi speco -
tio estas, mem.
Sed feliĉe, ĉar ni daŭre nomante varon, aŭ kunfandi varon,
specife, en pli kaj pli malgranda kaj pli malgrandaj listo, ni fine
fundo el danke al kio ni vokos bazo kazo, la malmola-kodita kazo kiu
diris se la listo estas malgranda, malpli ol 2 en tiu kazo, simple reveni tuj.
Se ni ne havas tiun specialan kazon, la algoritmo Neniam fundo eksteren,
kaj vi ja eniros en la senfinan buklon vere ĉiam.
>> Sed supozu ke ni volis jam metis iuj nombroj sur ĉi, denove, uzante n
kiel la grandeco de la enigo.
Kaj mi volis demandi vin, kio estas la tuta tempo partoprenas en
kurante merge speco?
Aŭ pli ĝenerale, kio estas la kosto de ĝi en la tempo?
>> Nu estas sufiĉe facila por mezuri tion.
Se n estas malpli ol 2, la tempo implikita en ordigi n eroj,
kie n estas 2, estas 0.
Ĉar ni ĵus revenas.
Ne estas laboro farenda.
Nun eble, eble estas unu paŝo aŭ du paŝoj por kalkuli la kvanton de
funkcii, sed ĝi estas sufiĉe proksime al 0, ke Mi nur volis diri sen laboro estas
bezonata se la listo estas tiel malgrandaj esti neinteresa.
>> Sed ĉi tiu kazo estas interesa.
La rekursie kazo estis la branĉo de la _pseudocode_ kiu diris alie, speco
la maldekstra duono, ordigi la dekstra duono, kunfandi la du duonoj.
Nun kial faras ĉi esprimo reprezenti ke elspezo?
Nu, T de n simple signifas la tempo por ordigi n eroj.
Kaj poste sur la dekstra flanko de la egala signo tie, la T de n dividita
per 2 estas referenco al la kosto de kio?
Ordigo la maldekstra duono.
La aliaj T de n dividita per 2 estas supozeble raportante al la kosto
ordigi la dekstra duono.
>> Kaj tiam la alpago n?
Ĉu la fandado.
Ĉar se vi havas du listoj, unu el amplekso n super 2 kaj alia de amplekso n
super 2, vi devas esence tuŝi ĉiu el tiuj elementoj, ĝuste kiel Rob
altusxantaj unu el la kalikojn, kaj nur kiel ni notis al ĉiu el la
volontuloj en la scenejo.
Do n estas la kosto de fandado.
>> Nun bedaŭrinde, ĉi tiu formulo Estas ankaŭ sin rekursie.
Do se demandis la demando, se n estas, ni diru, 16, se estas 16 personoj en la scenejo
aŭ 16 tasoj en la video, kiom entute paŝoj faras ĝi preni por ordigi ilin
kun merge speco?
Ĝi fakte ne estas evidenta respondo, ĉar nun vi devas ordigi de
rekursie respondi tiun formulon.
>> Sed tio estas bone, ĉar mi volas proponi ke ni faru la sekvajn.
La tempo implikita ordigi 16 personoj aŭ 16 tasoj tuj estos reprezentitaj
ĝenerale kiel T de 16.
Sed kiu egalas, laŭ nia antaŭa formulo, 2 fojoj la kvanto
el tempo necesa por ordigi 8 tasoj plus 16.
Kaj denove, plus 16 estas la tempo por kunfandi, kaj la du fojoj T de 8 estas la
tempo por ordigi maldekstra duono kaj dekstra duono.
>> Sed denove, tio ne estas sufiĉa.
Ni devas mergi en pli profunda.
Tiu signifas ke ni devas respondi al la demando, kio estas T de la 8?
Nu T de 8 estas nur 2 fojoj T de 4 plus 8.
Nu, kio estas T de 4?
T de 4 estas nur 2 fojojn T de 2 plus 4.
Nu, kio estas T de 2?
T de 2 estas nur 2 fojojn T de 1 plus 2.
>> Kaj denove, ni estas speco de prenanta fiksitaj en ĉi tiu ciklo.
Sed temas pri bati ke tiel nomata bazon kazo.
Ĉar kio estas T de 1, ni asertas?
0.
Do nun, fine, ni povas laboro malantaŭen.
>> Se T de 1 estas 0, mi povas nun reiru supren unu vicigas al ĉi tiu ulo ĉi tie, kaj mi povas
konekti 0 por T de 1.
Do tio signifas ke ghi egalas 2 fojoj nulo, alie sciata kiel 0, plus 2.
Kaj por ke ĉiu esprimo estas 2.
>> Nu, se mi prenus la T de 2, kies respondo estas 2, ŝtopi ĝin en la mezo linio, T
de 4, kiu donas al mi 2 fojoj 2 plus 4, do 8.
Se do mi konektiĝas en 8 al la antaŭa linio, kiu donas al mi 2 fojoj 8, 16.
Kaj se ni tiam sekvas ke kun la 24, aldonante en 16, ni fine akiras
valoro de 64.
>> Nun kiam en kaj per si speco de lingvo nenion por la n skribmaniero, la
granda O, la omega ke ni estis parolas.
Sed ĝi rezultas ke 64 estas ja 16, la grandeco de la enigo,
ensaluti bazo 2 de 16.
Kaj se tiu estas iom nekonataj, same pensas dorso, kaj ĝi revenos
al vi fine.
Se ĉi tiu estas log bazo 2, estas kiel 2 altigita al la kio donas al vi 16?
Ho, tio estas 4, do estas 16 fojoj 4.
>> Kaj denove, tio ne estas granda interkonsento se tiu estas speco de malprecizaj memoro nun.
Sed nuntempe, preni sur fido ke 16 log 16 estas 64.
Kaj tiel ja, kun tiu simpla prudento kontroli, ni konfirmis -
sed ne pruvis formale -
ke la rula tempo de merge varo estas ja n log n.
>> Do ne estas malbona.
Estas definitive pli bona ol la algoritmoj ni vidis tiel multe, kaj
estas ĉar ni leveraged, oni, tekniko nomita rekursio.
Sed pli interesa ol tio, ke nocio de dividanta kaj konkerante.
Denove, vere semajno 0 aĵoj kiuj eĉ nun estas recurrente en
pli konvinka maniero.
>> Nun amuza iom ekzercon, se vi havas neniam faris tion - kaj vi probable
ne volis havi, ĉar ia normala homoj ne pensas por fari tion.
Sed se mi iras al google.com kaj se Mi volas lerni ion pri
rekursio, Enter.
>> [Ridado]
[PLI ridado]
DAVID Malan: Malbona ŝerco malrapide etendas.
[Ridado]
DAVID Malan: Ĉiaokaze, estas tie.
Mi ne literumi ĝin erara, kaj tie estas la ŝerco.
Ĉio bone.
Klarigi ĝin al la popolo apud vi, se ĝi ne sufiĉe alklakis nur ankoraŭ.
Sed rekursio, pli ĝenerale, referas al la procezo de funkcio vokas
mem, aŭ pli ĝenerale, dividante al problemo en iu kiu povas esti
solvita piecemeal per solvanta identa reprezentanto problemojn.
>> Nu, ni ŝanĝo dentaĵoj por nur momento.
Ni ŝatas fini sur certa cliffhangers, do ni komencu meti
la etapo, dum kelkaj minutoj, sur tre simpla ideo -
tiu de swapping du elementoj, ĉu ne?
Ĉiuj de ĉi tiuj algoritmoj ni vizitis parolas pri la pasintaj kelkaj
prelegoj engaĝi kelkajn speco de swapping.
Hodiaŭ ĝi imagis per ili atingi el iliaj seĝoj kaj
marsxante, sed en kodo, ni volus nur prenu ero de unu aro
kaj Plop ĝin en alian.
>> Nu do kiel ni irad faras tion?
Nu, lasu min antaŭeniri kaj skribi rapida programo tie.
Mi tuj iros antaŭen kaj fari tion kiel la sekvajn.
Ni nomas tion -
kion ni volas nomi ĉi tiu?
>> Efektive, ne.
Lasu min malantaŭenigi.
Mi ne volas fari tion cliffhanger ankoraŭ.
Ĝi difektas la amuzo.
Ni faras ĉi anstataŭe.
>> Supozu, ke mi volas skribi iomete programo kaj kiu nun ampleksas ĉi
ideo de rekursio.
Mi specon de atingis antaŭ min tie.
Mi tuj faros la sekvajn.
>> Unue, rapida inkludas de normo io.h, tiel kiel inkluzivas de cs50.h.
Kaj poste mi iros por antaŭeniri kaj deklari int main void
en la kutima maniero.
Mi rimarkis mi misnamed la dosieron, do lasu min nur aldoni. c etendo tie tiel
ke ni povas kompili ĝin ĝuste.
Start tiu funkcio malproksime.
>> Kaj la funkcio mi volas skribi, sufiĉe simple, unu, kiu petas la
uzanton por nombro kaj poste aldonas supren ĉiuj numeroj inter tiu
numeron kaj, ni diru, 0.
Do unue mi tuj iros antaŭen kaj deklari int n.
Tiam mi kopii iujn kodo kiu ni uzis por tempo.
Dum io estas vera.
Mi revenos al tio en momento.
>> Kion mi volas fari?
Mi volas diri printf pozitiva entjero bonvolu.
Kaj poste mi iros al diru n gets akiri int.
Do denove, iuj Boilerplate kodo ke ni uzis antaŭe.
Kaj mi faros tiun dum n estas malpli ol 1.
Do tio certigos ke la uzanto donas al mi pozitiva entjero.
>> Kaj nun mi faros la sekvajn.
Mi volas aldoni la tutan de la nombroj inter 1 kaj kaj n, aŭ 0 kaj n,
ekvivalente, por akiri la tuta sumo.
Do la granda sigma simbolo ke vi eble memoras.
Do mi tuj faros tion per la unua voko funkcio nomita sigma,
pasante ĝin en n, kaj do mi tuj diru printf, la respondo estas prava.
>> Do, en mallonga, mi alvenas kaj int de la uzanto.
Mi certigas ĝi estas pozitiva.
Mi deklaras variablon nomata respondon de tipo int kaj vendejo en tio la reveno
valoro de sigmo, pasante en n kiel enigo.
Kaj tiam mi elprinti tiun respondon.
>> Bedaŭrinde, kvankam sigma sonas kiel iu kiu povus esti en
la math.h dosieron, ĝia deklaro, fakte ne estas.
Por ke estas bone.
Mi povas apliki ĉi mi mem.
Mi tuj apliki funkcio nomata sigma, kaj gxi tuj preni
parametro -
ni simple nomas ĝin m, nur tial estas malsama.
Kaj tiam ĉi tien, mi tuj diros, bone, se m estas malpli ol 1 - tio estas
tre seninteresa programo.
Do mi tuj iros antaŭen kaj tuj revenos 0.
Ĝi simple ne havas sencon por aldoni ĉiujn la numeroj inter 1 kaj m se m
estas sin 0 aŭ negativa.
>> Kaj poste mi iros por antaŭeniri kaj faros cxi tre ripete.
Mi tuj faros ĉi speco de malnova lernejo, kaj mi tuj iros antaŭen
kaj diru, ke mi tuj deklari sumo al esti 0.
Tiam mi tuj devos a por buklo de int -
kaj lasu min fari tion por kongrui nia dissendo kodo, do vi havas kopion
hejme. int i ricevas 1 sur ĝis i estas malpli ol aŭ egala al m.
i plus plus.
Kaj poste ene de ĉi por buklo -
ni estas preskaŭ tie -
sumo atingas sumon plus 1.
Kaj poste mi iros por reveni la sumon.
>> Do mi faris tion rapide, sufiĉe Certe.
Sed denove, la ĉefa funkcio estas sufiĉe simpla, bazita sur kodo Ni
skribita tiel nun.
Uzas la duobla banto akiri pozitivajn int de la uzanto.
Mi tiam preterpasonta int al nova funkcio vokis sigma, nomante ĝin, denove, n.
Kaj mi stoki la reveno valoro, la respondo el la nigra skatolo aktuale
konata kiel sigma, en variablo vokis respondo.
Tiam mi presi ĝin.
>> Se ni nun sekvos la historio, kiele sigma implementado?
Mi proponas apliki jene.
Unue, iom de eraro-kontrolanta por certigi ke la uzanto ne
rompado kun mi kaj pasante en iuj negativaj aŭ 0 valoro.
Tiam mi deklaras variablon nomata Resume kaj starigis gxin al 0.
>> Kaj nun mi komencas movi de i egalas 1 la tuta vojo ĝis kaj inkluzive de m,
ĉar mi volas inkludi ĉiujn nombroj de unu tra m, inkluziva.
Kaj ene de ĉi por ciklo, mi simple fari sumo atingas ĉion, kio estas nun, plus la
valoro de i.
Plus la valoro de i.
>> Kiel flanken, se vi ne vidis tiun antaŭe, tie estas kelkaj sintaksaj sukero
por ĉi tiu linio.
Mi povas reverki ĉi tiu kiel pli egalas i, nur por savi min kelkaj klavoj
kaj serĉi iom pli freŝa.
Sed tio estas ĉio.
Ĝi estas funkcie la sama aĵo.
>> Bedaŭrinde, ĉi tiu kodo estas ne tuj kompili ankoraŭ.
Se mi kuras fari sigma 0, kiel estas Mi tuj get kriis al?
Kio ĝi tuj ne plaĉas?
>> Spektantaro: [inaudibles].
>> DAVID Malan: Jes, mi ne deklaris la funkcio ĝis supro, ĉu ne?
C estas speco de stulta, en kiu nur faras kion vi diros ĝin fari, kaj vi
devas fari gxin en tiu ordo.
Kaj tial, se mi batis Indiku ĉi tie, mi tuj ricevas averton pri sigma implicitan
deklaro.
>> Ho, ne estas problemo.
Mi povas iri sur la supron, kaj mi povas diri, gravas, atendu momenton.
Sigma estas funkcio kiu revenas an int kaj atendas de
int kiel enigo, punktokomo.
Aux mi povus meti la tuta funkcio supre ĉefa, sed en ĝenerala, mi dirus
rekomendas kontraŭ tio, ĉar ĝi estas nice ĉiam havi ĉefan ĉe la supro tiel
vi povas plonĝi juste kaj scias kia programo estas faranta per legado ĉefa unua.
>> Do nun lasu min liberigi la ekrano.
Refari sigma 0.
Ĉio ŝajnas ekiri.
Permesu al mi kuri sigma 0.
Pozitivaj intermilita.
Mi donos al gxi la nombron 3 teni ĝin simpla.
Por ke oni donu al mi 3 plus 2 plus 1, do 6.
Enter, kaj ja mi ricevas 6.
>> Mi povas fari ion pli granda -
50, 12, 75.
Ĝuste kiel tangento, mi faros io ridinda kiel vere granda
nombro, Ho, kiu fakte prilaborita -
eh, mi ne kredas ke tio estas prava.
Ni vidu.
Ni vere metas kun ĝi.
>> Tio estas problemo.
Kio okazas?
La kodo ne estas tiel malbona.
Ĝi estas ankoraŭ lineara.
Fajfante estas bona efekto, tamen.
Kio okazas?
>> Ne certas se mi aŭdis.
Do rezultas - kaj ĉi tiu estas kiel flanken.
Ĉi tio ne estas kerna al la ideo de rekursio.
Rezultas, ĉar mi klopodas reprezenti tia granda nombro, plej
verŝajne ĝi estos esti misinterpretita per C kiel ne pozitiva nombro,
sed negativa nombro.
>> Ni ne parolis pri tio, sed rezultas tie estas negativaj nombroj
en la mondo krom por pozitivaj nombroj.
Kaj la rimedoj, per kiuj vi povas reprezentas negativan numeron
esence, vi uzas unu speciala bito por indiki
pozitiva ol negativa.
Ĝi estas iom pli kompleksa ol tio, sed tio estas la baza ideo.
>> Do, bedaŭrinde, se C estas malklara oni de tiuj bitoj kiel fakte signifas,
oh, tio estas negativa nombro, mia buklo ĉi tie, ekzemple, estas fakte neniam
tuj finiĝi.
Do, se mi efektive presi ion denove kaj denove, ni volus
vidi tutan sorton.
Sed denove, tio estas krom la punkto.
Tio estas vere nur ia intelekta scivolo, ke ni venos
apogi al fine.
Sed nuntempe, ĉi tiu estas korekta efektivigo se ni supozas ke la
uzanto provizos ints kiu persvadas ene ints.
>> Sed mi asertas ke tiu kodo, sincere, povus fari tiel multe pli simple.
Se la celo en mano estas preni nombro kiel m kaj adicii ĉiujn
nombroj inter ĝi kaj 1, aŭ inverse inter 1 kaj ĝi, mi asertas
ke mi povas pruntepreni tiun ideon kiu kunfandi speco havis, kion prenis problemo
de tiu grandeco kaj dividante ĝin en iu pli malgranda.
Eble ne duono, sed pli malgranda, sed representatively la sama.
Sama ideo, sed plej malgranda problemo.
>> Do mi fakte - lasu min konservi tiun dosieron kun malsama versio numeron.
Ni nomas tiun versio 1 anstataŭ 0.
Kaj mi asertas ke mi povas reale reimplement tion en ĉi tia
menso-fleksante vojo.
>> Mi tuj forlasi parton de ĝi nur.
Mi intencis diri, se m estas malpli ol aŭ eĉ egala al 0 -
Mi simple tuj estos iom pli anal ĉi tiu tempo
kun mia eraro kontrolanta -
Mi tuj iros antaŭen kaj reveni 0.
Ĉi tio estas arbitra.
Mi nur simple decidi se la uzanto donas al mi negativa nombro, mi estas
reveni 0, kaj ili devas esti legita la dokumentado pli atente.
>> Else -
rimarki kion mi faros.
Alie, mi tuj revenos m pli -
kio estas sigma de m?
Nu, sigma de m plus m minus 1, krom m minus 2, plus m minus 3.
Mi ne volas skribi ĉiujn kiuj ekstere.
Kial ne Mi nur liberigas?
Rekursie voki min kun iomete plej malgranda problemo, punktokomo,
kaj voku gxin tago?
>> Ĝuste?
Nun ĉi tie ankaŭ vi povus senti aŭ maltrankviligi ke tio estas malfinia buklo kiun mi
indukti, per kiu mi estas apliko sigma per voko sigmo.
Sed tio estas perfekte OK, ĉar mi pensis antaŭen aldonita kies linioj?
>> Spektantaro: [inaudibles].
>> DAVID Malan: 23 al 26, kio estas mia se kondiĉo.
Ĉar kio estas bela pri la subtraho tie, ĉar mi konservos
disdonado sigma malgrandaj problemoj, pli malgranda problemoj, pli malgranda - ĝi ne estas
duonon de la grandeco.
Tio estas nur bebo paŝon pli malgranda, sed tio ne gravas.
Ĉar fine, ni laboros nia vojo suben al 1 aŭ 0.
Kaj unufoje ni batis 0, sigma ne tuj nomos sin plu.
Ĝi tuj tuj revenos 0.
>> Do la efikon, se vi ia vento ĉi en via menso, estas aldoni m pli
m minus 1, plus m minus 2, plus m minus 3, plus dot, punkto, ĝi pentras, m minus
m, fine transdonante vin 0, kaj la efekto estas finfine aldoni ĉiuj
tion kune.
Do ni ne havas, per rekursio, solvis la problemon, ke ni
ne povis solvi antaŭe.
Ja, versio 0 de tiu, kaj ĉiu problemo ĝis nun, estis solvebla
kun nur uzante por maŝojn aŭ dum maŝojn aŭ similaj konstruoj.
>> Sed rekursio, mi daresay, donas al ni malsama maniero de pensi
problemoj, per kiu, se ni povas preni problemo, dividi ĝin el io
iom grandaj en iu iomete malgranda, mi asertas, ke ni povas solvi ĝin
eble iom pli elegante en terminoj de la dezajno, kun malpli da kodo,
kaj eble eĉ solvi problemojn kiuj volus esti pli forta, kiel ni instruos vin eventuale
vidu, solvante pure ripete.
>> Sed la cliffhanger kiun mi faris volas forlasi nin, estis jena.
Lasu min antaŭeniri kaj malfermi supren dosiero de -
fakte, lasu min iri fari ĉi reala rapida.
Lasu min kaj proponi la jena.
Inter la hodiaŭa kodo estas ĉi dosieron ĉi tie.
Ĉi tiu tie, noswap.
>> Do tiu estas stulta iom programo kiu Mi ekfrapis ke asertoj fari
la jena.
En ĉefa, ĝi unue deklaras int nomata x kaj asignas ĝin
la valoron de 1.
Tiam ĝi deklaras int y kaj asignas al ĝi la valoro 2.
Tiam ĝi presas kion x kaj y estas.
Tiam ĝi diras: swapping, dot dot dot.
>> Tiam ĝi diras esti nomante funkcio vokis swap, pasante en x kaj
y, la ideo de kiu estas kiu espereble x kaj y revenos
malsama, la malo.
Tiam ĝi asertas interŝanĝis!
kun krio punkto.
Tiam ĝi presas el x kaj y.
>> Sed ĝi rezultas ke tiu tre simpla pruvo malsupren
ĉi tie estas reale kalesxo.
Eĉ se mi deklarante portempan ŝanĝiĝema kaj provizore meti en
ĝi, tiam mi reassigning de la valoro de b -
kiuj sentas racia, ĉar mi havas savis kopion de en temp.
Tiam mi ĝisdatigos b al egala kiom estis en temp.
Ĉi tiu speco de konko ludo de movi en b kaj b en uzante tiun
meza viro nomata temp sentas perfekte racia.
>> Sed mi asertas, ke kiam mi kuros ĉi kodo, kiel mi faros nun -
lasu min iri antaŭen kaj gluu ĝin en ĉi tie.
Mi nomas tiun noswap.c.
Kaj kiel la nomo sugestas, ĉi tio ne estas tuj estos korekta programo.
Faru noswap. / Ne interŝanĝa.
x estas 1, y estas 2, swapping, interŝanĝitaj.
x estas 1, y estas 2.
Ĉi tiu estas fundamente malĝusta, eĉ Kvankam tio ŝajnas perfekte
racie mi.
Kaj estas kialo, sed ni ne estas tuj malkaŝus la kialo ĝuste ankoraŭ.
>> Ĉar nun la dua cliffhanger Mi volis lasi vin estas ĉi tiu,
anonco de varoj en kupono kodoj.
Nia novigo kun malfrua tagoj ĉi tiu jaro provokis ne-bagatela nombro
de demandoj, kiuj estis ne estas nia intenco.
La intenco de ĉi tiuj kupono kodoj, per kio, se vi faras parto de la problemo
starigis frue, tiel atingante ekstran tagon, estis vere helpi vin infanoj helpi
vi komencos frue, speco de de incentivizing vi.
Helpas nin disdoni ŝarĝo trans oficejo horoj pli bone por ke
ĝi estas speco de gajni-gajni.
>> Bedaŭrinde, mi kredas miaj instrukcioj ne restis, ĝis nun, tre klara, tiel
Mi reiris ĉi semajnfino kaj ĝisdatigita la spec en pli granda, revenante pli aŭdacaj teksto
ekspliki kuglojn kiel tiuj.
Kaj ĝuste diri ĝin pli publike, por Implicite, problemo aroj estas pro ĵaŭdo
tagmeze, por la Syllabus.
Se vi komencas frue, finante parto de la problemo starigis merkredo je 12:00
GMT, la parto kiu rilatas al kupono kodo, la ideo estas ke vi povas etendi
via limdato por la P starigis ĝis vendredo.
Tio estas, iom for eta parto de la P starigis parenco al kio tipe estas la
granda problemo, kaj vi aĉetos mem ekstran tagon.
Denove, ĝi ricevas vi pensas pri la problemo aro, prenas vin al
oficejo horojn pli frue.
Sed la kupono kodo problemo estas ankoraŭ bezonata, eĉ se vi ne submeti ĝin.
>> Sed pli compellingly estas tiu.
(STADIO flustre) Kaj tiuj uloj lasante Komence estas gonna bedaŭros.
Kiel estas la homoj sur la balkono.
Mi pardonpetas anticipe al la homoj sur la balkono de kialoj kiuj estos
certe en nur momento.
>> Do ni estas feliĉa havi unu el CS50 la eksĉefo instruado uloj ĉe
kompanio nomita dropbox.com.
Ili tre malavare donacis kupono kodo tie ĉi multe spaco,
kiu estas el la kutima 2 gigabajtoj.
Do kion mi pensis ke ni farus en tiu fina noto estas fari iom de evidenta sinmalkaŝo,
per kiu en nur momente, ni malkaŝos la gajnanto kaj kiu havas kupono
kodo kiun vi povas tiam iru al sia TTT-ejo, tajpu ĝin en, kaj voilà, ricevi
tuta multe pli Dropbox spaco por via aparato kaj pro viaj personaj dosieroj.
>> Kaj la unua, kiu ŝatus partopreni en ĉi desegnon?
OK, nun ke faras ankoraŭ pli amuza.
La persono, kiu ricevas tiun 25-gigabajto kupono kodo - kiu estas malproksime
pli konvinka ol la malfrua tagoj nun, eble -
estas tiu, kiu sidas sur supro de sidejo kuseno sub kiuj estas
ke kupono kodo.
Vi povas nun rigardi sube Via sidejo kuseno.
>> [VIDEO reprodukto]
>> -Unu, du, tri.
>> [Screaming]
>> -Vi ricevas aŭton!
Vi ricevas aŭton!
>> DAVID Malan: Ni vidos vi merkredon.
>> -Vi ricevas aŭton!
Vi ricevas aŭton!
>> DAVID Malan: Balkono ulojn, venu cxi tie ĉe la fronto,
kie ni havas ekstraj.
>> -Ĉiuj gets aŭton!
Ĉiuj gets aŭton!
>> [FINO reprodukto de vídeo]
>> Rakontanto: Je la sekvanta CS50 -
>> Parolanto 5: Ho mia gosh gosh gosh gosh gosh gosh gosh gosh gosh gosh -
>> [Ukelele Teatraĵoj]