>> [MUZIKO Ludante]
>> DAVID J. Malan: Jen CS50.
Kaj tiu estas la komenco de semajno tri.
Do ni havas multajn ekscita aferojn kovri hodiaŭ.
Multaj eblecoj por volontas supren sur scenejo.
Kaj finfine, hodiaŭ estas Ne pri kodo ajn.
Sed ĝi temas pri ideoj, kaj temas pri algoritmoj,
kaj efektive alportanta reen kelkaj la lecionoj lernis de semajno nulo,
kien revokon, ni enkondukis ĉi monstraĵo.
Kaj pruntado inspiro de tio, por komenci
solvi ĉiam pli kompleksaj problemoj algorítmicamente.
Sed unue, paro de anoncoj.
Do unu, se vi ŝatus aliĝi CS50 bastonon kaj samklasanoj ĉe lunĉo
tiu vendredo, ambaŭ ĉi tie kaj en Kembriĝo, kaj en New Haven,
bonvolu viziti la kurso retejo, kie URL troviĝas.
Prelegi tiu merkredo havos ne estos ĉi tie en Sanders.
Estos rete nur, tial agordu ĉe CS50 la retejo,
ĉu tie en Kembriĝo aŭ New Haven ankaŭ.
>> Kaj tiam problemo starigis du estas jam en viaj manoj.
Se vi ne plonĝis en ankoraŭ, permesu min proponi la energia sugesto
ke, precipe nun, kiam la problemo aroj antaŭas,
vi vere volas komenci nun, se ne dabble iom sur la semajnfino aŭ antaŭ
kiam ili unue eliri sur Vendredo, ĉar vi
trovi ke ili ne estas nepre atingi pli longa aŭ pli defia po
SE.
Mi pensas ke vi trovos ke, Ĝenerale, ili emas preni malglate
ĉirkaŭ sama kvanto de tempo.
Sed certe dependas sur la studento, kaj ĝi
dependas la pensmanieron kun kiu vi alproksimiĝas ĝin.
Sed senescepte, vi tuj kuri supren kontraŭ iu muro,
kaj vi tuj trafis kelkaj cimoj, kaj vi estas nur
ne tuj povos reĝustiĝos ĉe iu punkto.
Kaj ĝi estas tre valora por povi paŝi for, revenu la venontan tagon,
iri al oficejo horoj, post en CS50 Diskutu aŭ simile, por fakte akiri desbloqueado.
Observu do, ke en menso.
Komencante fruaj kiel eble estas la plej bona afero vi povas fari.
Do jen kie ni komencis la klaso, super en semajno nulo.
Kaj ni surterigos volontulo tie helpi min trovi mics?
BONE.
Starante, jam.
Venu supren.
Divenu tiel estas kiel ĝi tuj labori.
Kio estas via nomo?
ALAN ESTRADA Alan Estrado.
DAVID J. Malan: Alan Estrado.
Venu supren.
Agrable renkonti vin.
ALAN ESTRADA: Nice to meet you.
DAVID J. Malan: Sed vi estis tie kun ni en semajno nulo, kompreneble.
ALAN ESTRADA: mi estis.
Mi estis.
>> DAVID J. Malan: Do vi povus iri antaŭen kaj trovi por ni Mike Smith,
kiel rapida kiel vi povas?
Kiel rapida kiel vi povas.
Laŭvorte ŝirante la problemo en duono kiel vi bezonas.
>> ALAN ESTRADA: Um.
DAVID J. Malan: Laŭvorte ŝirante la problemo en duono.
>> ALAN ESTRADA: Ho.
Mm.
Tre bone.
>> DAVID J. Malan: Bone.
Bona.
Dankon.
ALAN ESTRADA: Tre bone.
BONE.
>> DAVID J. Malan: Do nun, vi ĉizis ĝin
al duono de la grandeco de la problemo.
Nun, ni estas malsupren al kvarono.
Ĉu vi atentante kiu flanko ni tenanta?
>> [Ridanta]
>> ALAN ESTRADA: Jes, mi think--
>> DAVID J. Malan: Kio sekcio estas ni en?
ALAN ESTRADA: cxirkauxligojn, tiel.
>> DAVID J. Malan: Bone.
Sed Mike Smith tuj esti post Mufflers.
So--
>> [Ridanta]
>> Bone.
ALAN ESTRADA: Kien ni rigardas?
DAVID J. Malan: Mike Smith.
ALAN ESTRADA: Mike Smith.
DAVID J. Malan: Nun, ni estas en kirurgia.
Nun, kuracistoj.
Now--
>> ALAN ESTRADA: Let's- ni iru kun reala.
Reala.
>> DAVID J. Malan: Real.
BONE.
Se vi bezonas Reala.
Nun, kiudirekten estas Mike Smith?
>> ALAN ESTRADA: Tiu vojo.
>> DAVID J. Malan: Kiun vojon?
ALAN ESTRADA: Atendu.
M is-- pravas?
Ni komencis with--
>> DAVID J. Malan: Yeah.
Ili lasis.
Via dekstra.
>> ALAN ESTRADA: Yeah.
>> DAVID J. Malan: Do Mike tien.
ALAN ESTRADA: Kio?
>> [Ridanta]
>> Malbona ekzemplo, knaboj.
Pardonon.
DAVID J. Malan: Ĉi instruos vi salteti el via seĝo.
>> ALAN ESTRADA: Ho.
Oh.
Mi havas vin.
Oh.
Ĉi is-- OK, Mi havas vin.
Forgxiston ĝuste ĉi tie?
>> DAVID J. Malan: Smith, dankon.
Do mi gardos suprenrigardinte Smith?
>> ALAN ESTRADA: Ho, jes.
Ne, ne, ne.
Ho ne.
Tiu estas mia.
>> DAVID J. Malan: Ah, vi havas Smith.
BONE.
>> ALAN ESTRADA: Yeah, Mi akiris Smith ĉi tie.
Pardonu, knaboj.
Mi pensis Michael-- ni serĉis Michael.
Pardonon.
>> DAVID J. Malan: Estas bone.
Bone, nun ni estas en Paccini kaj Sons.
>> ALAN ESTRADA: Paccini kaj filoj.
DAVID J. Malan: Nur vin kaj mi estas en sur ĉi.
BONE.
Trovi nin Mike Smith.
Forgxiston.
>> ALAN ESTRADA: Smith.
>> DAVID J. Malan: Smith.
Ni estas en R por rubo.
ALAN ESTRADA: rubo.
Oh.
Tiu tuj prenos tempon.
>> [Ridanta]
DAVID J. Malan: Ŝuoj.
Ni estas en ŝuoj.
>> ALAN ESTRADA: Nun ni gonna--
>> DAVID J. Malan: Nice.
ALAN ESTRADA: Which--
[Ridanta]
Ho, tiu estas granda.
[Ridanta]
>> DAVID J. Malan: Estas bone.
>> ALAN ESTRADA: Ho, tiu estas bona.
Mi ne kredas mi tuj havas PSAT amikoj post tio.
DAVID J. Malan: Bonan.
Sporting.
ALAN ESTRADA Sporting.
Um, L, M, N, O, P.
DAVID J. Malan: Bone.
Do ni disŝiros tiun duono.
Estas bone.
Ĉi finiĝas nebone ĉiuokaze, ĉar Mike Forgxiston ne estos en la flava paĝoj.
>> ALAN ESTRADA: Aw.
>> DAVID J. Malan: Ne, estas OK.
Sed ni ŝajnigi kiel li estas en tiu ĉi paĝo.
Do nun, vi jam ĉizis la problemo malsupren al unu paĝo, kaj ni trovis Mike Smith.
>> [Huraado]
OK, dankon.
BONE.
Tio estis eksterordinara.
Sed ĝi estis ankoraŭ pli rapida ol lineara serĉo,
kiun ni starti je la komencante de la libro,
kaj ni movas nia vojo de maldekstre dekstren, eventuale serĉas Mike Smith.
Kaj tiel, se la telefono libro havis eble 1.000 paĝoj,
eble ĝi estus preninta us 10 aŭ tiel paĝon larmoj.
>> Sed eble vi ekspluatita tuŝis antaŭsupozo
dum ĉiuj de tiu, kiu estas ke la telefono libro anticipe estis kio?
Publiko: Ordigitaj.
DAVID J. Malan: ĝi estas ordo.
Dekstra?
Ĝi estas ordo alfabete, do ke ĉiuj el tiuj nomoj kaj nombroj
estas ordo de la -a por la Z, kaj alfabete intere.
Sed hodiaŭ, ni nun demandas la demando, nu,
kiel faris Verizon aŭ telefone kompanio akiri ĝin en tiu stato?
>> Ĉar estas unu afero utiligi tiu supozo, kaj sekve,
solvi problemon per algoritmo pli kompetente.
Sed ni neniam vere demandis en semajno nulo, nu,
Kiom ĝi kostis Verizon aŭ iu alia
bonstata telefono libro en ordo ordo?
>> Dekstra?
Ne gravas se suprenrigardinte Mike Smith
estas super rapida, se ĝi prenas vin jaro ordigi la paĝojn komence.
Dekstra?
Vi povus tiel nur kribri tra randomigitaj telefono libro,
se ĝi okazas esti súper multekosta por ordigi ĝin.
Do se ni povas havi alian volontulo.
Ni rigardu supren tie ĉe kiamaniere ni might-- trafos up-- kiom
ni povus iri pri ordigado tiuj.
>> Kaj se Jordan povis reale aliĝi nin tie sur la scenejo.
Venu supren por nur momento.
Kio estas via nomo?
CAROLINE: Caroline.
DAVID J. Malan: Caroline, venu supren.
Kaj vi aligxos apud mi kaj Jordanio tie.
Caroline, dankon.
Bone.
Do kion ni havas ĉi tie por Caroline estas 26 bluaj libroj
ke FAS uzas administri certaj finaj ekzamenoj.
Tiuj iĝas malfacile trovi, sed kion ni faris anticipe
estas ke ni metis ies nomon sur la fronto de ĉiu el tiuj,
sed ni konservis ĝin simpla per tiam elmetanta plenaj nomoj.
Do ni metus la persono kun la nomo L, D, J, B, tuta vojo A tra Z,
sed ili estas en hazarda ordo.
Kaj do se vi farus, parolante via vojo tra la problemon kiel vi
cxu gxi, cxu vi povas antaŭeniri kaj ordigi tiujn por ni, de A al Z.
>> Publiko: Bone, do L estas kiel, la mezo.
C komencas.
B. J antaŭ L. B, Q.
>> DAVID J. Malan: Premu ke pensis por unu sekundo.
Ĉar alie, tio estas nur Interese vi, mi, kaj Jordanio.
Tie ni marŝos.
Spektantaro: [inaudible].
R.
DAVID J. Malan: Bone.
Kion vi faras?
>> CAROLINE: M venas post O.
>> DAVID J. Malan: Bone.
>> CAROLINE: O.
DAVID J. Malan: Ho, Bonan.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Yeah.
>> CAROLINE T, U, V.
>> DAVID J. Malan: V, T, U, V. Do aspektas kiel vi making-- plu iri.
Aspektas kiel vi faras granda amaso super tie,
kaj speco de granda amaso super tie.
Do la unua duono de la alfabeto, dua duono de la alfabeto.
BONE.
Bona.
Speco de fendanta la problemo en du.
M, N, X. Yeah.
CAROLINE: K.
DAVID J. Malan: Bone.
K. Do vi speco de elektanta ilin unu post alia,
metante ĝin aŭ maldekstra aŭ dekstra, aŭ Z iranta sur la planko.
BONE.
>> CAROLINE: Z okazas surplanke.
>> DAVID J. Malan: Bone.
Y tuj surplanke.
Nun ni povas meti X.
>> CAROLINE: G.
DAVID J. Malan: G okazas lasis.
S tuj dekstre.
Bone, A estas iranta tute forlasis.
>> CAROLINE: A, B, C, D.
>> DAVID J. Malan: Nun, bone.
Ni havas A, B, C. W la subiro tie.
Bone, T.
>> CAROLINE H, I, J
DAVID J. Malan: H, I, J Bonan.
CAROLINE: En la centro, mi gonna--
DAVID J. Malan: Bone.
Do nun, ni tuj speco de kunfandi tiujn diversajn amasoj.
Do A tra C, tiam mi vidas D kaj E, kaj F, kaj G, kaj H, kaj I. Nice.
J, K. Kaj tiam, tiu stako estas renversita, sed tio estas bone.
Certe.
Ni povas tranĉi kelkajn angulojn.
BONE.
Kaj tiam ni bezonas W, X, Y, Z.
>> CAROLINE: Yeah.
>> DAVID J. Malan: Bonega.
Do grandan dankon al Caroline por ordigado tiuj.
>> [Huraado]
>> Dankon.
Dankegon.
Do nun ni pripensu dum momento kiom Caroline rondiris fari tion,
kaj kion ekzakte ni povis to-- kiamaniere ni
povis solvi tiun problemo kiam ni estis ĵus
donita tuta amaso de hazardaj enigoj.
>> Nu, tio aspektas kiel ekzistas estis iom de sistemo tie?
Dekstra.
Do la fruaj literoj en la alfabeto, ŝi
estis metante al la maldekstra, kaj la poste literoj en la alfabeto,
ŝi estis metanta en la dekstra.
Kaj tuj kiam ŝi trovis iuj proximal literoj, tiuj
kiuj iras dekstre apud la alia, ŝi metus tiujn en ordo.
Kaj tial ni ia havis tiujn malgrandajn amasoj de ordo enigoj okazanta.
>> Kaj tiel tio estas tute kiel kio plimulto de ni homoj farus.
Ni estus ia kribri tra ĝi, kaj ni estus ia havas mekanismon.
Sed ĝi povus esti malfacile skribi ĝin malsupren en formulo por se.
Ĝi sentis iom pli organika ol tio.
Do ni vidu se ni povas nun mallibera la problemo kun malpli enigoj.
>> Anstataŭ 26, ni fari ion ege malpli
kun nur diru, sep, malantaŭ tiuj pordoj, tiel diri.
Ĉu ekzistas nur sep numeroj?
Kaj se la celo nun ĉe mano estas trovi valoron,
ni vidu kiel kompetente ni povas iri pri faranta tion ĉi.
Kaj ni vidos se ni povas nun komenci apliki iujn numerojn,
aŭ iuj formuloj kun kiu priskribi la efikeco de nia telefono libro
algoritmo, nia ekzameno libro algoritmo, kaj pli ĝenerale, trovanta informon.
>> Do pro tio, lasu min antaŭeniri kaj sur la ekrano táctil tien,
toleri foliumilo kiu havas ĝuste tiuj sep pordoj.
Kaj se ni povus akiri unu alia volontuli veni tien,
Mi metis tiujn samajn pordojn super tie.
Rapida volontulo.
>> Ĉi one-- demonstraĵoj iras al pli kaj pli rapide nun.
Venu malsupren.
Kio estas via nomo?
TREVOR: Trevor.
>> DAVID J. Malan: Trevor?
Bone, Trevor, venu malsupren.
Do Trevor jam volontulis tie fari similan problemon, sed kiu estas
mallarĝa en amplekso, kaj ke tuj por permesi nin provi formaligi nun
la procezo por ordigado tiuj nombroj.
>> Do Trevor, agrable renkonti vin.
Do tie estas tabelo, do al paroli, liston de sep pordoj.
Antaŭen kaj trovi nin la numero 50.
Kaj tiam post la fakto, diru al ni, kiel vi trovis ĝin.
Devus be-- gxuste.
Jes, tiu estas tie?
Uh-oh.
BONE.
Vi klakis tiu.
Bona.
>> Kaj bona.
Nun vi klakis tiu.
Kaj mi donos al vi la mikrofonon, por ke vi havas ĝin en nur momento.
Iru antaŭen kaj klaku najbare ke vi intencas.
Jes, bone.
TREVOR: Ĉu mi unclick pordon?
DAVID J. Malan: Ne, vi ne povas unclick.
TREVOR: OK.
Ĉi tiu.
DAVID J. Malan: Kie vi volas iri?
Kiu?
>> TREVOR: Tiu.
>> DAVID J. Malan: No.
>> TREVOR: OK.
Ĉi tiu.
>> DAVID J. Malan: Jes.
Tio estis bona.
Bone.
Do kio estis via algoritmo aŭ proceduro por fari tion, Trevor?
>> TREVOR: Mi ĵus iris tra pordoj ĝis mi trovis 50.
DAVID J. Malan: Bone.
Bonegaj algoritmo.
Do tio estas bone.
Ĉar fakte, se mi malkaŝus kio estas malantaŭ tiuj du aliajn pordojn, kion
ni trovos tie estas ke ni nur havas hazardaj enigo.
Tiel ke estis vere kiel bona kiel vi povus akiri.
Kaj fakte, vi igxis pli ol ĝisfunde esploras la tuta tabelo,
ĉar ĝi estintus vere malbonŝanca se vi trafis la numeron
50 je la lasta pordo.
Sed kio se ni anstataŭ donis vin supozo.
Supozi Mi ordigas ĉiujn tiuj pordoj ĉirkaŭe,
por ke vi havas la nombroj ordigitaj tiu tempo,
sed ĉifoje ĝi estas fakte a different-- tiu tempo,
ĝi estas fakte ordo por vi.
Kaj nun la celon ĉe mano estas frapi la numero 50.
>> TREVOR: OK.
>> DAVID J. Malan: Kio estas via algoritmo tuj estos?
>> TREVOR: Nu, se ĝi estas ordo, estas ĉu irante
al be-- se plej granda al plej grandaj, malsuprenirantan, ĝi estos la unua,
aŭ se ĝi estas la malo, tio estos la lasta.
Do mi nur tap ĉi pordo, kaj tiam nur tushi la lasta pordo.
DAVID J. Malan: Bonega.
Bone.
Do ni trovis la numero 50.
Tuj, kiam vi konis ili ordigataj ni
sukcesis uzi tiun supozon.
Do ili estas tro kiel la telefono libro ekzemplo.
Tuj kiam vi havas, eĉ kun malgrandan problemon kiel tiu,
viaj enigoj pre-ordo, ni povas reale trovi la valoron disputeble
pli kompetente.
>> Kaj mi ne diras al vi se ĝi estis ordo malgranda al granda, aŭ granda por malgranda,
kaj tiel estis tre racia komenci ĉe unu fino aŭ la aliaj
por fakte trovi ke objektiva valoro.
Do dankon al Trevor ankaŭ.
Kaj mi propose-- bele farita.
Ni havas iom klipo, fakte, ke estas inter niaj momentoj favoritos en CS50,
whereby kelkfoje tiuj demonstraĵoj ne tute iru laŭ plano.
Kaj ja ĝuste nun, mi tirita supren malĝustan interfaco
kun kiu uzi la ekranon táctil.
Por ke estis mia kulpo tie.
>> Do ĉi faros por venontjara klipo kiel
kial mi klakanta sur mia propra ekrano.
Sed ni prenu rapidan rigardon kio okazis pasintjare
kun Jay, kiuj venadis multe kiel Trevor tie, volontulis,
kaj en tiu mallonga tranĉeto, vi vidos kiel tiu sama demo faris ne tute
malkaŝi la sama lecionoj lernitaj.
[VIDEO reprodukto]
-All Mi volas vin fari nun estas trovi por mi kaj por ni,
vere, la nombro 50 unu paŝon samtempe.
>> -La Nombro 50?
>> -La Nombro 50.
Kaj vi povas malkaŝi kio estas malantaŭ ĉiu el tiuj pordoj
simple tuŝante ĝin per la fingro.
Damnu ĝin.
>> [Ridanta]
>> [FINO reprodukto]
DAVID J. Malan: Do tiu iris tre bone.
Tiuj estis la unsorted pordoj.
Kaj Jay, kompreneble, trovis ĝin tro rapide.
Trevor faris multe pli bonan laboron en terminoj de teachable momento,
tiel diri, tiun jaron en prenante plu trovi ĝin.
Kompreneble, tiam ni donis Jay duan ŝancon,
per kiu ni ordigitaj la pordojn, ĝuste kiel ni faris por Trevor,
kaj Trevor faris súper bone ĉi tiu tempo.
Sed Jay faris duono tiel rapide.
[VIDEO reprodukto]
-La Celo nun estas ankaŭ trovi nin la numero 50,
sed faru ĝin algorítmicamente, kaj diru al ni kiel vi tuj pri ĝi.
>> -BONE.
>> -Kaj Se vi trovas ĝin, vi tenas la filmon.
Se vi ne trovas ĝin, vi donos ĝin reen.
>> -man.
>> -Ho!
>> - [Inaudible] OK.
Do mi tuj kontroli la finoj unua determini se there's-- Oh.
>> [Aplaŭdo]
>> [FINO reprodukto]
DAVID J. Malan: Bone.
Do ordigado pordoj klare kondukas al pli granda efikeco.
Kaj do, duoble rapida estas kion mi volis diri tie.
Kaj tiel Jay akiris bonŝanca ambaŭ fojojn.
Li ankaŭ akiris bonŝanca en tiu lasta jaro, mi mendis iuj Blu-ray
reale sonigas.
Mi bedaŭras tiu jaro, ni ne havas la saman, Trevor.
Sed bona ankoraŭ kelkajn jarojn reen.
Kaj iuj el vi eble scias tion ulo, Sean, kiu kiam li estis en CS50,
estis defiita kun la ĝusta saman problemon, kvankam en SD,
kiel vi baldaŭ vidos, reen en la tago.
Kaj vi trovos, ke ne nur faris li prenos iom pli ol Jay,
iom pli ol Trevor, estis fakte tiu mirinda ŝanco
okupi preskaŭ ĉiuj en la amaso a la Prezo estas Dekstra, kuraĝigante
lin trovi la nombro ni sercxis.
Ni. prenu rapidan rigardon.
>> [VIDEO reprodukto]
>> -BONE.
Do via tasko tie, Sean, estas jeno.
Mi kaŝis malantaŭ tiuj pordojn la nombro sep.
Sed ie en iuj el tiuj pordoj tiel estas aliaj negativaj nombroj.
Kaj via celo estas pensi de tiu supera vico de nombroj
kiel nur tabelo, aŭ nur sekvenco de pecoj de papero
kun nombroj malantaŭ ili.
Kaj via celo estas, nur uzante la supro tabelo tie, trovi min la numero sep.
Kaj ni tiam tuj kritiko kiel vi iras pri faranta ĝin.
-Bone.
-Trovu Ni la nombro sep, bonvolu.
No.
Kvin, 19, 13.
>> [Ridanta]
>> Ĝi ne estas lertaĵo demando.
Unu.
>> [Ridanta]
Ĉe tiu punkto, via poentaro ne estas tre bona, do vi povus tiel plu iri.
Tri.
>> [Ridanta]
>> Daŭrigu.
Sincere, mi ne povas helpi sed scivolas kion vi eĉ pensas pri, so--
>> [Ridanta]
Nur la supera vico, do vi havas tri maldekstre.
Do trovi min sep.
>> [Ridanta]
17.
Sep.
>> [Aplaŭdo]
>> Bone.
>> [FINO reprodukto]
>> DAVID J. Malan: Do ni povis spekti tiujn tuttage.
Kaj kompreneble, kelkaj el ĉijara demonstraĵoj eble
nun finas en proksima ĉijara vídeo ankaŭ.
Do nun ni vere temigi la algoritmoj
tie kaj vidi se ni ne povas nun komenci formaligi
kiel ni povas iri pri akiri niajn datumojn en tiu stato ke ĝi estas ordo,
por ke finfine, ni povas reale esplorrigardi gxin pli kompetente.
Kaj eĉ se ni iras uzi sufiĉe malgrandaj datumaj aroj,
kiel la ok numerojn ni havas ĉi tie sur la tabulon,
finfine tiuj samaj ideoj povus apliki 1.000 enigoj, miliono enigoj,
4 miliardoj enigoj, ĉar la algoritmoj tuj estos fundamente la sama.
>> Kaj tiel tio estas nia lasta ŝanco volontulojn hodiaŭ,
sed eble la plej implikitaj unu, por kiu ni bezonas ok volontuloj
veni supren kaj piediras nin tra procezo de ordigado kio baldaŭ
esti sur tiujn muziko staras tie.
Permesu min komenci ĉi tien.
>> Do unu en la turquoise-- verda estas?
Cxu vi faras?
Du.
Venu malsupren.
BONE.
Tri.
Kvar.
Lasu kunulinon OK, kvin.
Vi estanta nomumita fare via amiko.
Ses, sep, kaj ok.
Venu supren.
Bone.
Multan dankon.
Venu supren.
>> Bone.
Do kion ni havas here-- kaj ĉi estas inter la pli mallerta, ili
ĉar tio postulos ke vi humuro min nur iomete de tempo.
Vi devas esti numero unu.
Kio estas via nomo?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
Davido.
Kio estas via nomo?
>> JOSEPH: Jozef.
>> DAVID J. Malan: Jozef, vi estas numero du.
>> Serena: Serena, numero tri.
Stefan, numero kvar.
CYNTHIA: Cynthia.
DAVID J. Malan: Cynthia, numero kvin.
[Inaudible]
DAVID J. Malan: [inaudible].
David nombro ses.
MATT Matt.
DAVID J. Malan: Matt numero sep.
Kaj?
>> WAVERLY Waverly.
>> DAVID J. Malan: Waverly, numero ok.
Bone.
Se vi could-- whoops.
Se vi cxiuj, kiel via unua defio, tie
Estas ok muziko standojn tie alfrontante la spektantaron.
Se vi povus meti viajn numerojn sur tiuj muziko staras tiel
ke ili viciĝas supren kun la samajn nombrojn sur la tabulo.
Sanktigu vin similos ke de metante vian nombrojn sur tiuj muziko
staras tie.
Bonegaj ĝis nun.
>> Bonege.
BONE.
Do nun, ni tuj demandas la demandon en kelkaj malsamaj vojoj.
Kiel ni iras pri ordigado tiuj uloj tie?
Ĉar ni havis kelkajn alirojn antaŭe, per kiu ni
speco de farante du malsamaj siteloj.
Kaj tiam ni estis ĝenerale piecing aferojn kune.
Tuj kiam ni vidis du nombroj kiuj apartenis kune,
ni metis ilin kune.
Du leteroj kiuj apartenas kune.
>> Sed ni vidu se ni ne povas formaligi tiun,
tiel ke ni finfine havas kelkaj pseŭdo-kodo vi volas,
kun kiu vi povas solvi tiujn problemojn.
Do nun, mi estas elrigardanta ĉe tiuj numeroj tie.
Kaj mi vidas tutan faskon da erarojn.
Finfine, mi volas unu sur la lasis ok dekstre.
>> Kaj tial mi rigardas tiuj du, kvar kaj du.
Kaj kio estas la problemo, evidente?
Yeah.
So.
Du evidente venas antaux kvar, tiel vi scias kion?
Lasu min unue avara alproksimiĝo, se vi volas, multe kiel problemo
fiksita one-- se vi memoras de la Norma Eldono de Problemo Ara Unu,
kie mi nur loke solvi la problemon ke pravas tie antaŭ mi
kaj vidi kie kondukas min.
>> BONE.
Do du kaj kvar, mi iros antaŭen kaj nur interŝanĝu vi du.
Se vi povas fizike movas vin kaj via papero,
Mi ŝajnas esti alveninta la listo en pli bona stato.
>> Nun, ili estas bonaj.
Mi tuj pluiri, kvar kaj ses, aspektas bone.
Ne estas problemo.
Ses kaj ok, OK.
Ok kaj unu, alia problemo.
Ĉar kio estas vera pri ok kaj unu?
Unu venas antaŭ ok, do kion ni faru?
Ni interŝanĝu tiujn du.
Unu ok.
Kaj nun, mi tuj plu iri.
Mi tuj teni rigardante antaŭen.
Kaj ni vidu kio okazas.
Ok kaj tri, de Kompreneble, el ordo.
Ni interŝanĝa.
Ok kaj sep, kompreneble.
Misfunkcias.
Ni interŝanĝa.
Ok kaj kvin, kompreneble, ni interŝanĝa.
Bone.
Listo estas aranĝita.
jes?
>> OK, evidente ne.
Sed estas iom pli bona, ĉu ne?
Ĉar avizo kio okazis.
Ĉiufoje ni elfaris swap, pli malgranda numeron ia percolated tiel,
kaj pli granda nombro percolated tiu maniero, aŭ ni
komenci dirante bobelis al la maldekstra aŭ bobelis dekstre.
>> Nun, ĝi ne sufiĉas, ĉar ĉe bona nombro povus
movis unu loko antaŭen, aŭ en la plej malbona,
kelkaj havu movita punkto cetere.
Do vi scias kion tiu speco el funkciis sufiĉe bone ĝis nun.
Lasu min nur provi ĝin denove.
Du kaj kvar, ili estas okej.
Kvar kaj ses, ili estas okej.
Ses kaj unu, el ordo.
Do ni interŝanĝu vi du.
Kaj nun, rimarki la problemo la komencanta akiri iom pli bone denove.
Ses kaj tri, el ordo.
Ni interŝanĝu vi du.
Ses kaj sep, vi estas bona.
Sep kaj kvin, kompreneble, el ordo.
Sep kaj ok, en ordo.
Kaj nun mi eble bezonas fari tion kelkajn fojojn.
Kaj fakte, pensi por vi eble kiomfoje maksimume
eble mi devas piediri tien kaj reen?
>> Ni revenos al tiu.
Do du kaj kvar estas ankoraŭ OK.
Kvar kaj unu, Nope.
Do, ni interŝanĝa.
Kaj denove, rimarki vide estas speco de bobelanta
maldekstren, kie ĝi devus esti.
Kvar kaj tri interŝanĝa.
Kvar kaj ses.
Ses kaj kvin interŝanĝa.
Ses kaj sep.
Sep kaj ok estas bona.
>> Bona.
Ni nun estas eĉ pli bona.
Do ni vidu.
Nun, ni havas du unu.
Kompreneble, interŝanĝi.
Du kaj tri, tri kaj kvar, kvar kaj kvin, ses kaj sep, sep kaj ok.
Bona.
Kaj vi scias kion?
Ĉar mi faris unu ŝanĝon tie, lasu min fari unu prudento ĉeko.
Lasu min iri la tutan vojon reen al la komenco.
BONE.
Unu, two-- Yup, vidi?
Io eraris.
Tri, kvar, kvin, ses, sep, ok.
Kaj en ĉi tiu lasta paŝo, estas vi komforta kun mia nun
Asertante estas ordo?
BONE.
Vide, tio estas absolute vera.
Sed funkcie, kio ja ankaŭ nur hazarde
en tiu lasta paŝo kiu permesas konfirmi ke ĉi tiu listo estas ja
ordo?
>> Kion mi faru aŭ ne faru ĉi lasta pasu?
Spektantaro: Ne estis ŝanĝoj.
DAVID J. Malan: Pardonu?
Publiko: Neniuj ŝanĝoj.
DAVID J. Malan: Ne estis ŝanĝoj.
Do estus stulta de mi faros tion saman algoritmon denove
se mi ne faris ajnan ŝanĝas la unua fojo.
Kaj la stato ne ŝanĝiĝis.
Certe, mi ne tuj fari ajna ŝanĝas duafoje.
Kaj se tiel, estas sekura nun diri, listo estas aranĝita.
>> Kaj efektive, tiu estas nun iu kiu ni ĝenerale
alvoko bobelo varo, per duope, vi korekti erarojn denove,
kaj denove, kaj denove, kaj vi plu iri tien kaj reen,
kaj reen, ĝis vi faru nenian tian svopoj, ĉe kiu punkto
vi povas esti certa, jes, mi finis fiksi ĉiujn la erarojn.
Ni retrovu kaj provi alian aliron.
Se vi infanoj povis reeniri la ordon vi estis antaŭ momento,
kiu aspektis kiel ĉi.
Nun, ni prenu alproksimiĝon de iom pli kiel la ekzameno libro,
per kiu ni estis konstante elektanta la litero de la alfabeto
ke ni ia volis trakti sekva.
Eble estis alta leteron, kiel A, aŭ malalta letero Z.
>> Do ĉiuj estas reen en tiu ordo.
Kaj nun lasu min fari tion.
Ni vidu Mi scias min havas ok numeroj tie.
Mi tuj iros antaŭen kaj nur intence elektu
la plej malgranda eroj.
Dekstra?
Tio ŝajnas tro intuicia.
Kial mi ne trovos la plej malgranda elemento, metis ĝin kie ĝi apartenas,
tiam akiri la sekva plej malgranda elemento, metis ĝin kie ĝi apartenas, kaj nur ripetas.
>> Ĉar intuicie, kiuj devus labori tro.
Do kvar, kiuj estas sufiĉe malgranda nombro.
Mi tuj memori kie tiu estas.
Atendu minuton.
Du estas pli malgranda.
Lasu min nun memoras kie du estas, kaj forgesas pri kvar.
Ni agos laŭ tiu poste.
Ses, mi ne estas interesita.
Ok, mi ne interesiĝis.
Unu mia nova malgranda nombro.
Do mi tuj memoras, kie oni estas.
Tri, ne interesas.
Sep, ne interesas.
Kvin, ne interesas.
>> Do sen defalado la scenejo ĉi jaro,
Mi tuj ekpreni nombro one-- kaj kio estis via nomo denove?
>> Annan: Annan.
>> DAVID J. Malan: Annan.
Kaj se vi povus aliĝi min ĉe la komenco de la listo,
ni kunigu vin kie vi apartenas.
Unfortunately-- kio estas via nomo?
>> Stefan: Stefan.
>> DAVID J. Malan: Stefan estas en la vojo.
Do antaŭ Stefan solvas tiun problemon, kion ni faru?
Kion ni faru kun Stefan?
>> Spektantaro: [inaudible].
DAVID J. Malan: Bone.
Do ni povus fari tion.
Ni povus ia preni Stefan kaj liaj kvar, kaj nur metis ĝin en variablo
kaj teni ĝin por iu kvanto de tempo,
tiel farante spaco por numero unu.
Kaj tio estas ne malbona.
Mi povus sugesti, kial ne ni ĵus metis Stefan tie?
Kial povus tiu seksperforti unu de la ideoj ni komencis
parolante pri pasinta tempo, pasinta semajno?
Yeah?
>> Spektantaro: [inaudible].
>> DAVID J. Malan: Estas ne indekso por ĝi.
Se vi pensas pri tio, ja, kiel tabelo, tio estas kiel negativa,
do ne memoro reale tie se ĉi tiu estas ja tabelo,
kiel ni deklaris pasintsemajne en prelego.
Do ni ne devus fari tion.
Ni povus stoki ĝin en variablo.
>> Aŭ vi scias kion?
Mi aŭdis iun ajn sugestas ĝin.
Kion alian ni povus fari kun Stefan?
Kial ni ne simple elhejmigi lin kaj metis lin super kie numero unu estis.
Do se vi volas iri tien.
Kaj efektive, tiu estas sufiĉe bona solvo.
Nun unuflanke, mi havas specon de farita la problemo malbona.
Kvar estas nun pli malproksima de kie ĝi devus esti.
Ĝi devus estos kun tiu duono.
>> Sed vi scias kion?
Kiu povus esti estinta malbona sorto.
Eble nombro ok estis tie.
Kaj do, eble ni farus akiris bonŝanca,
kaj puŝis ok pli proksime al la fino.
Do en la fino de la tago, ĝi specon de ĉiuj mezumoj eksteren.
Ni ne bezonas zorgi pri kvar.
Ĉiuj mi zorgas pri nun estas elektante la plej malgranda ero.
>> Kaj nun, kion mi tuj fari estas forgesas pri nombro unu
konstante, ĉar mi konas la listo malantaŭ mi nun ordo.
Do mia listo estis antaŭe grandeco ok.
Nun, estas de grandeco sep.
Do mia problemo fariĝas malgranda, kvankam lineare.
Do nun, mi tuj elektu la nuna malgranda elemento, du.
Ses, ok, kvar, tri, sep, kvin.
Tio estis la plej malgranda ero.
Do kio mi estas iranta fari with-- kio via nomo denove?
>> JOSEPH: Jozef.
>> DAVID J. Malan: Jozef?
Ni tuj forlasi Jozef en loko.
Nun, mi tuj ŝajnigi ke tiuj infanoj are-- bone,
Mi scias ke tiuj du estas jam ordo.
Ni nun enfokusigi la resto de la listo.
Ses estas la nuna plej malgranda.
Ok estas granda.
Kvar estas nun la nuna malgranda.
Tri estas nun la nuna malgranda.
Kaj tial nun, mi tuj elektu tri, kiuj is-- kio estas via nomo denove?
Serena: Serena.
DAVID J. Malan: Serena, se vi povus Ekpreni vian numeron kaj interŝanĝa with--
KALSANG: Kalsang.
DAVID J. Malan: Kalsang.
Venu reen, kaj ni estas tuj interŝanĝi tiujn du.
Kaj nun ni kunigu ĉi sur autopilot.
Mi tuj iros kaj lasi ĝin al vi infanoj elekti la sekva plej malgranda eroj.
Dun, dun, dun, dun.
Numero kvar, kion vi faras?
Bonege.
Nun, mi tuj faros alian enirpermesilon.
Dun, dun, dun, dun.
Mi vidas kvin estas la sekva plej malgranda.
Nun, mi tuj prenos alian enirpermesilon.
Dun, dun, dun, dun.
Ses estas la plej malgranda.
Bona.
Sep estas la plej malgranda.
Neniu ŝanĝo.
Ok estas la plej malgranda.
Done.
>> Do kion ni ĵus faris per ripete selektante unu elemento post la alia
estas implementar iu kiun ni estas tuj formaligi kiel selektado varon.
Kaj estas eble eĉ pli simple klarigi,
en kiu laŭvorte ĉiuj vi volas fari estas simple observu
iri tien kaj reen tra la listo elektante, la sekva plej malgranda elemento,
ĝis vi faris.
>> Do estas eĉ pli simpla, eble intuicie, ol lasta.
Ni provu unu lasta.
Se vi uloj povas reagordi mem en jenajn poziciojn
unu fina tempo, ni vidu, se ni ne povas nun formaligi unu alia alproksimiĝo.
Fakte, ĉu iu tie ekstere ŝatus proponi
kiel alie ni povus iri pri fari ĉi tion?
Sen balanciĝadis el buzzwords aŭ varo de respondoj kiuj estas jam konataj,
nur intuicie, kion ni povis fari?
>> Spektantaro: [inaudible].
DAVID J. Malan: Yeah.
Do ekzistas iu granda intuicio tie.
Bonaj aĵoj ŝajnas okazi tiel malproksime en komputiko, kiam ni dividu
kaj konkeri la problemo de dividanta ĝin en duono kaj duono kaj duono.
Kaj tiel ja, ni povis komenci fari tion.
Kaj fakte, tiu tuj estos, ni vidu, unu el niaj plej bonaj solvoj ankoraŭ.
Sed ni revenu al tiu post nelonge.
Fakte, ni tuj faros ke iom poste tiun semajnon.
Kion alian povus fari por solvi tiun?
Do ĉiuj ĉi tie estas en ŝajne hazarda ordo.
Vi scias kion?
Prefere ol iri tien kaj reen, tien kaj reen, tien kaj reen
ĉiun fojon, ĉi sentas kiel Mi faras multajn piedirado.
Kial ne mi simple komencu ĉe la komenco de la listo,
kaj nur meti kvar kie apartenas?
Do mi supozas ke por la momento mia listo estas nur tiu unua elemento.
Estas kvar ordo ĉe tiu momento en tempo, se ne gravas al mi pri estas ĉio ĉi?
Tiu estas speco de bagatele vera, ĉu ne?
Kiel la liston enhavantan unu nombro, kaj tiu numero kvar estas evidente ordigita.
>> Do mi simple kondiĉas ke tiu listo estas aranĝita.
Sed nun mi havas la reston de tiu listo.
Do nun, mi renkontas du.
Kie faras du evidente apartenas kun respekto al kvar?
Antaŭ kvar.
Do kion mi povas fari tie?
Kio estas via nomo denove?
>> JOSEPH: Jozef.
>> DAVID J. Malan: Jozef, se vi povus retropaŝi
por nur momento kun via nombro.
Kaj nun kio devus Stefan faras tie?
Ni movi Stefan super tie.
Lasu do Jozef venis ĉi tien.
Kaj nun lasu min aserti ke ĉio tie estas ordo.
Do, simila rezulto, sed fundamente malsama alproksimiĝo.
Mi eĉ ne rigardis kio estas tie malsupre.
Mi daŭre prenante la elementoj kiam ili estas transdonitaj al mi,
kaj trakti ilin.
>> Do nun, mi vidas la numero ses.
Kie numero ses aparteni?
Ni havas du, kvar, ses.
Precize kie ŝi estas ĝuste nun.
Do ni lasos tion sole, kaj nun asertas ke tiu parto de la listo
nun ordo.
Kaj do, ĉi sentas fundamente malsama en ke mi estas nur
movante tra la listo ĉi tie linie, kaj mi neniam duobliganta reen.
Jes.
Bone.
Do ok, kie vi estas?
Dekstra tie.
Perfekta.
Do nun, unu.
Uh-oh.
Tiu sentas estas tuj estos multekosta.
Nun, en la antaŭa algoritmo, Mi ĵus interŝanĝis personoj.
Do mi povu lin la tutan vojon en la komenco, sed poste movis Jozef.
Sed se mi kopias Jozef, nun kio okazas estas malĝusta?
>> Nun, mi havas ian undone-- mi havas prenita unu paŝon antaŭen kaj tiam
retropaŝo, ĉar nun Joseph estus el ordo.
Do ni faru ĉi.
Se vi povus preni nombro unu kaj retropaŝi por nur momento.
Kiel ni povas put-- kio estis via nomo denove?
>> Annan: Annan.
>> DAVID J. Malan: Annan en loko?
Kio devas okazi kun respekto por du, kvar, ses, ok?
Ili ĉiuj devas movi.
Do se ok ŝatus ŝanĝi unua, tiam ses, tiam kvar, tiam du.
Kaj tiam Annan, se vi estus deziras veni tien, bone.
Sed ĉi tie, ni ĵus ia pagis prezon
ĉe malsama punkto en la algoritmo.
Dum lasta tempo kun selektado speco, kaj eĉ bobelo varo,
Mi promenis tien kaj elirante, tien kaj reen,
kiu estas certe adicio tempo-saĝa, kaj laŭvorte _stepwise_.
>> Inserción varo, unue rigardo, aspektas kiel ĝi estas
súper inteligentaj, en kiuj mi estas nur farante malrapida, dumtajpa progreso,
sed mi ne tuj ĉi tien kaj reen.
Sed se iu estas ja el ordo, avizo
ĉiuj la laboro mi nur devis fari.
Mi devis movi duono de la listo nur por fari lokon por nombro unu.
Do estas la sama kvanto de laboro kaj tiel ege ĝi
sentas, nur malsama tipo de laboro.
>> Ni daŭrigos.
Do nun ni scias ke ĉiuj inter unu kaj ok estas ordo.
Ĉi tie, mi havas numeron tri.
Se vi ŝatus repreni numero tri, retropaŝi unu.
Kaj kion vi uloj bezonas fari?
Yep.
Do jen alia, du, tri paŝoj.
Tri unuoj de tempo kiu nur kostis mi, tiel ke tri povas nun taŭgas.
Fine, sep.
>> Ni iru antaŭen kaj havas vi doni retropaŝon.
Ĉi nur tuj kostos nin unu unuo de tempo, sed tio estas bone.
Kaj nun, kvin tuj esti iom pli multekostaj.
Se vi ŝatus retropaŝi.
Ni devas movi ok, kaj sep kaj ses.
Kaj poste ĉiuj estas nun ordo.
Do grandan manon al niaj volontuloj tie.
Multan dankon.
>> [Aplaŭdo]
>> Dankon ĉiuj.
Dankon ĉiuj.
Do ni vidu nun kiom kosta ĉiuj kiu estis.
Ni konsideras eble la simpla el tiuj, bobelo varon.
Kaj mi diras simple, nur ĉar vi povas solvi ĝin avide per nur
ripari la duope problemo tie.
Ripari la problemon duope tie, ree kaj ree
kaj denove, ripetante kiel multaj tempoj kiel vi vere bezonas.
>> Do rezultas ke kun bobelo varo, nu,
kiom da paŝoj mi devas alpreni la unua enirpermesilo de tiu algoritmo?
Mi povus take-- ni Konsideru unu, du, tri, kvar, kvin, ses, sep.
Kaj estas ok elementoj tie.
Do estas kiel n minus 1 paŝoj al ricevas el la komenco de la listo
al la fino de la listo.
>> Sed kun selektado varon, memoras ke mi elektanta la elementojn denove kaj denove
kaj denove jen malgranda, Mi metas ĝin en lokon,
sed tiam mi ne rigardante malantaŭ mi.
Do mi kredas ke estas iom pli klara tiam ke la unua fojo, mi povus
devas preni ĉiuj n minus 1 paŝoj por trovi la plej malgranda ero.
Tiam mi metis ilin en lokon kaj elhejmigi ajn estis tie antaŭe.
>> Sed tiam mi ne devas teni rigardanta tiun elementon,
ĉar mi scias, ke tio Jam la plej eta.
Do nun, mi povas rigardi nur sep elementoj, tiam ses elementoj,
tiam kvin elementoj, tiam kvar elementoj.
Do matematike, se n estas la nombro de elementoj aŭ nombroj
ke ni komencis kun, vi povas imagi ke tio estas la sama kiel n minus 1,
plus n minus 2 paŝoj, plus n minus 3 paŝojn,
plus n minus 4 paŝoj, ĉiuj vojon malsupren al nur unu paŝo.
Kaj mi sur mia lasta persono.
>> Kaj se vi memoras, ke multo el stats libroj aŭ math libroj
havas tiujn formulojn sur la Hardcover dorso aŭ antaŭ ili,
ĝi rezultas ke ĉi tiu serio povas esti esprimita pli simple
kiel n × n minus 1 super 2.
Kaj ĝi estas bone se tio ne ĉe la avangardo de via menso.
Sed tio estas ja vera.
Tio estas nur pli simpla maniero skribi ĝin.
Kaj tiam se vi opinias reen al grado lernejo,
kiam vi komencu multiplikante aferojn, ĉi kompreneble
estas nur n kvadratoj minus n dividita per 2.
Ĉiuj mi faris estas pligrandigi la esprimoj tie.
Kaj do ni reverki tiun iom malsame.
Jen n kvadrato dividita per 2 minus n / 2.
>> Do denove, mi estas nur speco de aplikanta iuj aritmetiko regas tie.
Sed rimarki nun ke la plej granda termino en ĉi tiu esprimo, tiel diri,
estas ke n kvadratoj.
Do jes, ĝi estas n kvadratoj dividita per 2, minus n / 2.
>> Sed ĝenerale, se n estas tuj estos granda valoro,
Mi tuj asertas ke n kvadratoj tuj estos la domina faktoro.
Ĝi simple tuj estos pli granda kontribuanto
la nombro de paŝoj ol n / 2.
Do kion mi celas per tio?
Ni provu simplan ekzemplon, eĉ kvankam la math ricevas iom granda.
>> Do eble ni havis 1 miliono personoj sur scenejo, aŭ 1 miliono aferoj
ke ni volas ordigi.
Ni plug miliono en ĝuste tiu formulo
vidi kiom da ŝtupoj prenas entute ordigi miliono elementoj uzante diru,
selektado varon.
>> Do ni havus la saman formulon kiel antaŭe.
Mi plug miliono, tiel ke mi ricevas miliono kvadrato dividita per 2,
minus miliono dividita per 2.
Se mi faras tion math anticipe tie, ni havas 500 Miliardo
minuso 500,000, kiu donas nin 499.999.500.000,
kiuj estas sufiĉe darn granda.
>> Fakte, se vi komparas nun 499 miliardoj, 999 milionoj,
500.000 kontraŭ nia originala valoro, 500 miliardoj, estas tiel malbenita proksime.
Dekstra? n kvadrato dividita per 2 donas us-- aŭ prefere, n kvadrato dividita per 2
donis al ni 500 miliardoj.
Tio estas sufiĉe darn Fermi al 499.999.500.000,
kio estas restante ekstere 500.000, aŭ pli ĝenerale, restante ekstere
n kvadratoj, ne estas vere granda interkonsento.
La n kvadratoj faras tiujn nombroj kreskos vere rapida.
>> Nun, ĉi tiu estas grava nur en la mezuro kiel ni, kiel komputilo sciencistoj,
ĝenerale ne tuj zorgas tiom pri la nuancoj de tiuj formuloj
kaj ĝuste kion la preciza respondoj.
Ni zorgas nur tio, vi scias kion?
Fine de la tago, tiu formulo estas sur la ordo de n kvadratoj.
>> Jes, ni dividante per 2 en tie.
Jes, ni restante ekstere n minus 2.
Sed fine de la tago, la termino ke vere doloras nin kaj kostas nin
multaj paŝoj estas ke kvadrata terminon.
Kaj tiel kion komputilo sciencisto tuj ĝenerale faras
estas ignori ĉiuj tiuj malgrandaj por terminoj,
kaj nur rigardi la unu kiu kontribuas la plej al la kosto.
>> Kaj tiu estas bela, ĉar ni povas nun paroli en multa plej granda ĝeneraleco
pri algoritmoj, kaj povas kompari ilin.
Kaj la fakto ke mi estas uzante tiu O estas intenca.
Kiam mi diras sur la ordo de, mi estas specife
aludas ion nomata granda O. Kaj granda a
Estas notacio ke komputilo sciencisto uzas por priskribi
supera baro sur io.
>> Do se vi diras ke algoritmo estas en granda a de n kvadratoj,
kiel mi proponis nur antaŭ momento, ke per
ke en terminoj de lia kurado tempo aŭ lia efikeco,
prenas sur la ordo de n kvadratoj paŝoj.
Eble pli, eble malpli.
Sed ĝi estas sur la ordo de n kvadratoj.
Kaj tio estas la superulo.
Oni ne tuj esti pli dolora ol tio.
Oni ne tuj esti n Cubed, aŭ 2 al la n, aŭ io multe pli granda.
Tio estas supera baro sur kii ke kosto estas.
Do donita ke, ni konsideru nur kelkajn ekzemplojn.
Kaj tiu estas nur finia listo de tre komunaj kurante fojojn
por algoritmoj kiu signifis esti ilustrativo de iuj aferoj ni
vidita jam.
>> Do ekzemple, en la kazo de selektado speco, kion mi asertante tie
estas ke selektado speco de kurado tempo estas sur la ordo de n kvadratoj.
En la plej malbona kazo, mi tuj havi tuta amaso de hazardaj nombroj tie.
Kaj kiel ni vidis matematike, se mi teni marŝi
tra la listo, tra la listo, selektante la sekva plej malgranda
elemento denove kaj denove, se mi fakte skribi malsupren ĉiuj la paŝoj
Mi prenas kiel mi proponis formulaically antaŭe, ĝi estas sur la ordo de n kvadratoj
paŝoj kiuj mi prenas.
>> Kaj ĝi rezultas ke bobelo varo kaj inserción varo
estas tiel malrapida en la plej malbona kazo.
Konsideru, ekzemple, inserción varo, la tre lasta algoritmo ni pritraktis,
kiu havis ni rigardu la elementon, kaj poste enmeti ĝin kie ĝi apartenas.
Kaj poste ni rigardis la sekva elemento, kaj enmetita ĝin kie ĝi apartenas.
>> Do konsideru la plej bona ebla scenaro.
Supozu mi mian volontuloj laŭliniigi laŭvorte kiel tiu, unu tra ok,
jam ordo.
Kiom da paŝoj estas inserción varo tuj prenos ordigi ok personoj,
se ili alvenas sur scenejo rigardante tiel?
>> Ok personoj jam ordo.
Kaj mi uzas inserción varon.
Ke lasta el la algoritmoj.
Nu, ni reenact reala rapida.
Do se mi komencas tie, mi vidas unu.
Kie oni apartenas?
Ĝi apartenas ĉi tie.
Mi vidas du.
Kie du apartenas?
Dekstra tie.
Mi vidas tri.
Kie tri aparteni?
Dekstra tie.
>> Mi vidas kvar.
Dekstra tie.
Kvin, ses, sep, ok.
Ekzistas neniu kialo por ripeti min mem.
Kaj tiel, kiom da ŝtupoj estas ke en terminoj de n?
Ĝi estas sur la ordo de n paŝoj, dekstra? n minus 1.
Sed Mi prenis lineara nombro de paŝoj kaj nun mi estas farita.
Do jen la plej bona kazo, tamen.
Kio pri la plej malbona kazo?
Kio ok estis tie, kaj sep estis malsupren tie,
kaj unu kaj du estis tie, tiom ke la listo estis vere inversigis?
>> Nu, kio okazas ja se tiu estas la nombro?
Kaj ni tion faros nur kelkaj ekzemploj.
Kio se, efektive, la numero ok estas tie, kaj la number-- whoops.
Do kio se, efektive, la nombro ok estas tute super tie,
kaj Mi uzas inserción varo?
>> BONE.
Mi asertas nuntempe estas en loko.
Sed nun, seven-- kie does sep iras?
Kompreneble, ĝi iras tien.
Do mi devas movi ok super unu loko.
Nun ses, kie ĝi iras?
Nu, bone.
Nun, mi devas movi ok super lokon, kaj sep super loko,
kaj tiam mi Plop malsupren ses.
>> Do la unua fojo, ĝi kosto mi unu paŝo ripari aĵojn,
tiam ĝi kostis al mi du paŝojn al ripari aĵojn.
Kiom da paŝoj estas tuj prenos ripari
aferojn meti kvin en la ĝusta loko?
Tri.
Ĉar nun mi devas movi unu, du, tri.
Kiom da paŝoj estas ĝi iranta preni meti kvar en la ĝusta loko?
4 plus 5, plus 6, plus 7.
>> Kaj do ĝi estas matematike identa al kion ni priskribis por selektado speco.
Ni havas ĉi tiu serio Tio simple kreskanta.
1 plus 2 plus 3 plus 4, aŭ inverse, estas 7, 6
plus 5 Plus 4 adicias supren por hodiaŭaj intencoj al sur la ordo de n kvadratoj.
>> Do lasu min kondiĉas tro ke bobelo varo estas ankaŭ en n kvadratoj.
Ĉar kun bobelo varo, ĉiu tempo mi iras tra la listo,
Mi prenas proksimume kiom da paŝoj?
Ĉiufoje mi laŭvorte marŝi de tie al tie?
Malglate n paŝoj.
Sed kiom da fojoj eble mi bezonas iri tra la listo?
>> Nu, malglate n tempon.
Eble n minus 1, sed malglate n fojojn.
Nu, kial do?
Nu, kun bobelo varo, se ni komencu per bobelo varo,
kun la listo en la plej malbona ebla situacio, kiu denove estas tute
dorsdirekte kio okazos?
Mi iros tra la listo, kaj nombro oni apartenas tuta vojo super tie.
>> Sed kun bobelo varo, kiom faras unu movi mian unuan enirpermesilon tra la listo?
Kiom da makuloj ĉu li ricevos pli proksima al la ĝusta loko?
Nur unu.
Do se vi ia kialo tra tiu, ĉiufoje tra tiu algoritmo,
David prenante malglate n paŝoj.
Sed kiom da paŝoj tra la listo estas ĝi
tuj prenos unu al bobelo maldekstren kie apartenas?
>> Li havas movi kiel, n spacoj tiamaniere.
Do simple fari la ordigado de la listo, Mi devas piediri reen n fojojn.
Kaj ĉiufoje, mi estas rigardante n elementoj.
Do faru n aferoj n fojoj sur la ordo de n kvadratoj.
>> Nun, ni vidos en iuj de la mallongaj kiu
estas enigita en CS50 la sekva problemo fiksita, alia alproksimiĝo ĉe tiuj,
Sed nuntempe, ni nur konsideras iuj aliaj kurante fojojn,
speciale se la ordigado prenas iomete da tempo sinki je.
Kio estas algoritmo ni vidis jam kiu prenas sur la ordo de n paŝoj?
>> Kio devus preni lineara nombro de paŝoj kiujn ni vidis ĝis nun?
Kio estas tio?
La telefono dosierujo serĉo.
La unua algoritmo.
Dekstra?
Kie ni estas lineare serĉanta Mike Smith?
Fakte.
De semajno nulo, kiam mi komencis turnante unu paĝo samtempe,
kaj mi eĉ diris ke estis speco de lineara sento algoritmo,
kaj ni havis tiun bildon sur la tabulo kun la rektan ruĝan linion
kaj la rektan flavan linio, estis ĝuste
algoritmoj kiuj estas en granda a de n.
>> Ĉar trovi Mike Smith en telefono libro de n paĝoj, en la plej malbona kazo,
povus porti min n paŝoj.
Kio pri preni asistencia?
Unu, du, tri, kvar, kvin, ses.
Kio estas la rula tempo de ĉi tiu Algoritmo por prenanta asistencia?
Big O de n, ĉar en teorio mi devas atentigi ĉiuj en la ĉambro.
>> Nun kiel flanken, kio pri la aliaj optimumigo el semajno nulo?
Du, kvar, ses, ok, 10, 12.
Komputila sciencisto realigi, atendu minuton,
jen sur la ordo de n dividita per du paŝoj.
Dekstra?
Ĉar mi faras du personoj samtempe.
Sed ni tuj ignori tiuj malsupera ordo terminoj,
kaj ni ĵus tuj forĵetu la dividi per 2,
kaj ĝuste diri, granda a de n por ke algoritmo ankaŭ.
>> Kio pri ĉi tiu?
Ni salti super iu de ĉi tiuj, sed kio Estis algoritmo kiu estis log de n?
Kiu prenis proksimume log n paŝoj?
La dividu kaj regu.
Ekzakte.
Kiel la telefono libro ekzemple en semajno nulo kaj pli frue hodiaŭ,
kie ni dividis la problemo denove kaj denove kaj denove.
Ni tiris ĝin sur la tabulo en semajno nulo kiel kurba verda linio,
kaj ni diris ke tago estis logaritma algoritmo.
>> Kaj efektive, la nombro de paŝoj prenas elfari dividu kaj regu,
aŭ duuma serĉo kiel ni komencos nomante ĝin, kiel en la telefono libro,
estas sur la ordo de protokolo kaj paŝoj.
Kaj tiu estas iom de bizara unu.
>> Kio prenas unu paŝon, aŭ pli specife
konstanta nombro de paŝoj?
Eble estas du, eble estas tri, sed komputila sciencisto ĵus
simpligas ĝin kiel granda O de 1, iu konstanto nombro de paŝoj.
Kio estas io vi povus fari tion prenas konstanta nombro de paŝoj?
>> Kio estas la rula tempo de kunfrapante?
Konstanta tempo.
Dekstra?
Kiel, kio estas la rula tempo de fari ion kio prenas nur unu
operacion, kiel presi F Saluton Mondo.
Tio povus esti dirita esti konstanta tempo, se malpli angulo kazo kun presitaj F,
Kio povus la rultempo de presaĵo F reale esti?
Kaj kial?
Kio estas n mezura en tiu kazo?
>> Spektantaro: [inaudible].
DAVID J. Malan: Ĝuste.
La nombro de karakteroj ni volas presi.
Do estas tre kuntekst-sentema.
Hodiaŭ, ni estis enfokusigante multe sur literoj kaj numeroj tie sur la tabulo.
Sed povus ankaŭ esti karakteroj en reala kordoj.
Do rezultas ke estas alia mezurilo komencos zorgi pri,
kaj tio estas la malo de granda a, por tiel diri.
>> Tio omega skribmaniero.
Dum granda a signifas kio estas, la supera baro sur via rultempo?
Maksimume, kiom da tempo povus ion prenos?
Omega-- bedaŭras ĉi levas up-- estas la malo de tio,
per ĝi estas suba baro sur la kvanto de tempo iu povus preni.
>> So. Ekzemple, kio estas algoritmo kiu postrestas ĉiam n kvadratoj paŝoj?
Nu, unu el la algoritmoj ni vidis hodiaŭ, fakte, povus esti ke ankaŭ.
Selektado varo.
Selektado speco estas sufiĉe stulta.
Eĉ se la algorithm-- bedaŭras, eĉ se la tabelo jam ordo,
selektado varo estas tuj teni promenante tra la listo
certigi ĝi havas la plej malgrandan elemento denove kaj denove kaj denove.
Kaj eĉ se vi homoj en la spektantaron scii ke, atendu minuton,
vi jam pasis la plej malgranda elemento, la komputilo
Ne scias ke ĝis ĝi aspektas tutan vojon tra la listo.
Simile, suba baro ke povus ankaŭ konsideri
estu lineara tempo.
>> Kiom da tempo estas bezonata por ia n elementoj en la plej bona
kazo uzante ion kiel bobelo varo?
Supozi via listo estas jam ordo.
Ni diris bobelo varo prenas sur la ordo de n kvadratoj paŝoj.
Sed kio se ĝi estas jam ordo?
Kio se oni rimarkas post unu enirpermesilo tra la tabelo
ke vi faris neniun svopoj?
Ĉu vi devas teni farante pli pasas?
>> No.
Do suba baro sur bobelo varo povus esti dirita esti lineara.
Omega de n.
Kaj ni povas rigardi aliaj de ĉi tiuj tiel.
Do ni prenu rapidan rigardon ĉe ĝuste visualización tie
vidi kiel tiuj heroe.
Mi tuj iros malsupren tie en tiu paĝo kiu estas havebla sur la retejo de C50,
sed estos doloro akiri laborante, kiam ĝi uzas teknologion nomita
Java apletoj, kiu estas grandparte nesubtenata tiuj tagoj,
almenaŭ per Chrome kaj iuj aliaj.
>> Kaj lasu min antaŭeniri kaj akceli ĉi tien kaj klarigi kio okazas.
Jen pruvo de bobelo varon, la unua algoritmo ni rigardis.
Kaj ĝi estas visualización en kiuj ĉiu de tiuj stangoj reprezentas ciferon.
La pli granda la trinkejo, la pli granda la nombro.
La pli malgranda la trinkejo, la pli malgranda la nombro.
Kaj kion vi povas vidi vide, eĉ kvankam ĉi tiu tuj super rapida,
estas ke la ruĝa stango estas kiel mi, marŝi tien kaj reen fiksi problemojn.
Vi povas vidi ke la pli grandaj elementoj estas ja bobelis supren dekstren,
kaj la pli malgrandaj elementoj estas bobelis supren maldekstren.
Kaj ĉi tie malsupre, se ni fakte aspektas pli proksime,
ni povas vere kalkuli la numeron de komparoj kaj svopoj
ke oni fabrikis.
>> Sed anstataŭe, ni rigardu ĉe la dua algoritmo
ni rigardis antaŭe kun nia volontuloj, selektado varo.
Vide, ĝi havas tre malsama efiko.
Sed estas, denove, tre intuicia, en ke ni observas elektanta la sekva plej malgranda
elemento, kaj ni akiris iom bonŝanca.
Kiu sentis funde rapida.
Sed se ni kuris ĉi denove kaj denove kaj denove kun multaj enigoj,
ni vidus ke ĝi estas efektive ankoraŭ en granda a de n kvadratoj.
>> Ni faru unu lasta tie, inserción varo,
kiu estis la tria algoritmo Ni rigardis, kaj revoko
ke ĉi tiu traktas la elementoj kiel ĝi renkontas ilin,
sed tiam eble ŝanĝoj aĵoj super fari ĉambron,
enmeto elementoj kie apartenas.
>> Kaj tiun tro finas donante la finan rezulton. Nun ĉiuj tri de tiuj
sentis sufiĉe rapida.
Kaj efektive, mi kuris ilin ĉe sufiĉe bona klipo.
Sed fundamente, ili ja ĉiuj bela hororiga esti honesta.
Ĉiuj de ĉi tiuj algoritmoj ĝis nun kiuj kuras en granda a de n kvadratoj
preni sufiĉe de tempo por kuri en la fino.
>> Kaj efektive, ni povas vidi Kaj senti ĉi persiste
se mi elsxiros ĉi tria kaj lasta demo.
Tio estas alia videbligo kiu tuj
montri bobelo varo maldekstre selektado varo en la mezo,
kaj io, kiel unu el niaj mano levas frue sugestis,
kunfandi speco sur la dekstran.
Dividu kaj regu strategio dekstre.
Kaj tio estas, fakte, kion ni estas tuj rigardi merkrede.
Sed ni tempo tiuj kuri en paralela.
Ĝi estas malglate la sama nombro de elementoj, ĉiu kurante samtempe.
Bobelo varo vs selektado ia vs merge varon.
>> Nun, ili ĉiuj kuras teorie samtempe.
La CPU kuras ĉe la sama rapido, sed vi
povas senti kiom enuiga ĉi estas tre rapide tuj fariĝis,
kaj kiom rapida kiam ni injekti iom de semajno
nulo la algoritmoj povas ni rapidi aferojn supre.
>> Kaj nun ni komparu tiuj en unu lasta formo.
Mi tuj iros antaŭen al CS50 la retejo, kie
ni havas tiun finan ligon por hodiaŭ, kie iu en la interreto
afable kunmetis video kiu kaptas kion malsamaj ordigado
algoritmoj soni kiel.
Jen inserción varon.
>> [BEEPING]
>> Whereby vi aplikante frekvenco bazita sur la alto de la stango trinkejo.
Tio estas bobelo varon.
>> [Warped BEEPING]
>> Coming up sekva is-- venanta supren sekva is-- selektado speco,
kie denove, ni elektanta la sekva plej malgranda elemento,
kaj ni povas vidi ĝin kreskas de maldekstre al dekstre.
>> Kunfandi varon, nian gajninto ĝis nun hodiaŭ.
Rimarku kiel ĝi estas dividanta aferojn en [inaudible] duono kaj kvaronoj.
Gnome speco, kiun ni havas ne raportis, kaj kreas vide
kaj audally iom de malsama formo kaj sono.
Irante tien kaj reen, purigante aĵojn.
Ankaŭ kontrolu heapsort sur ĉi ulo de afiŝinto.
>> Kaj tio estas ĝi.
Ni vidos vin proksima fojo.
>> [WHOOSHING KAJ MUZIKO]