>> [Predvajanja glasbe]
>> DAVID J. Malan V redu.
Torej, dobrodošli nazaj.
To je CS50, in je koncu tretjega tedna.
>> Tako opozarjajo v zadnjih nekaj tednih, smo se porabi zelo malo
Čas na C, v programiranju, o skladnji.
In to je povsem normalno, če ste še vedno bori s Problem Set 2, se
razbijati glavo ob zid.
To je skrivnosten usmerjene sporočil o napakah in napake, ki jih
ne more povsem lovil.
Ker, prepričani, da je v pravkar čas nekaj tednov boste ozrli nazaj na
stvari, kot Cezar, in [? V-genair,?] morda celo Crack in
zavedajo, kako daleč ste prišli v kratkem času.
Torej, če je to v tolažbo, potrpi za zdaj.
>> Danes, čeprav smo začeli prehod da stvari višjo raven.
In smo začeli jemati za samoumevno, da veste, kako program, ali
Najmanj začetki da je raven udobja.
In bomo začeli razmisliti, kako smo lahko iti o oblikovanju programov več
učinkovito.
Kako lahko greste o optimizaciji Učinkovitost naših algoritmov in
splošno reševanje več zanimivih problemov.
In začetek samoumevno, da če bi želeli, bi lahko kodo gor koli
od primerov, ki jih imamo v mislih.
Torej danes, ne bomo se dotaknete tipkovnice za kakršno koli obliko kode.
To bo precej višji ravni, in navsezadnje, o reševanju problemov.
>> Torej, da bi prišli do te točke, naj predlaga da naslednjih sedmih
pravokotniki predstavljajo sedem vrata, zadaj ki so cel kup
številke, med katerimi je številka 50.
Dovolite mi, da je to projekt na tem zaslon tudi tukaj.
In predlaga, da potrebujemo prostovoljca pomoč pri iskanju mi ​​številko pred
internet tu za ogled.
Pridi gor, v roza barvi.
Vse je v redu.
Kako ti je ime?
>> JENNIFER: [neslišno]
>> DAVID J. Malan: Oprostite?
>> JENNIFER: Jennifer.
>> DAVID J. Malan: Jennifer.
Vse je v redu, Jennifer.
Lepo, da sva se spoznala.
Pridi gor.
Torej, to tukaj je sedem vrata, in kaj Rad bi, da narediš za nas,
pred vsemi sošolci, se zdi nam, številko 50.
Če želite najti številko, lahko pokukati za vas vsaka od teh vrat s preprostim dotikom
na eno stran vrat, in to bo razkrila svojo številko.
In da vidimo, kako hitro nam lahko najdem številko 50.
>> 15.
16.
50.
Lepo opravljeno.
Vse je v redu.
Aplavz za Jennifer.
>> [APLAVZ]
>> Vse je v redu.
Torej, kaj je vaša strategija za najti številko, 50?
>> JENNIFER: Hm, sem mislil, če -
[Neslišno]
>> DAVID J. Malan: Oh.
Daj mu eno sekundo.
Torej je bila vaša strategija za najti številko, 50?
>> JENNIFER: Torej sem začela ob že videli, kaj je prva številka
je bil, potem pa sem mislil, mogoče če oni so razporejene, bom samo nadaljuj
prisluškovanje višje?
>> DAVID J. Malan: OK.
In zdi se, da so ugotovili, , da bi bilo tako.
Čeprav, kaj je lupina nazaj plasti Samo malo, in želite, da gredo
naprej in se razkrivajo druga vrata lahko bi izbrali?
>> JENNIFER: Oh, draga.
>> DAVID J. Malan: Ah.
>> JENNIFER: Torej, pravkar sem srečen.
>> DAVID J. Malan: Torej imaš srečo.
Vse je v redu.
Torej ni slabo.
Ampak to je zanimivo vpogled, kajne?
Če se domneva, in si zaslužiti, res, malo srečen tam.
Ampak, če domnevamo, da so bile številke razporejene, ste lahko bolj natančni
, kako, da vplivajo tvoje obnašanje?
>> JENNIFER: Torej, če so bile razporejene sem Mislil najmanjših do največjih.
>> DAVID J. Malan: OK.
>> JENNIFER: Ali pa, če je ta končal pa res velik, potem največjih do najmanjših.
>> DAVID J. Malan: OK.
Torej največjih do najmanjših, ali najmanjših do največjih.
Ampak naj predlagajo, da ste imeli gotten sreče, in domnevam, da so
niso bili v resnici, razporejene, koliko ta vrata ste morda moral pokukati
zadaj v tem najslabšem primeru?
>> JENNIFER: Vsi izmed njih.
>> DAVID J. Malan: Vsi izmed njih.
Torej, kaj je posploševati, da so n.
Se zgodi, da bo 7, vendar naj bolj na splošno reči, tam je n vrata na
Zaslon tukaj.
Torej, v najslabšem primeru pa bi morali pogledati za 7 vrat ali N vrata.
In tako je to res, da je malo sreče danes, ampak to je res linearna
algoritem z menoj, čeprav ste so bili nekako preskoči okoli.
Je to pošteno?
>> JENNIFER: Ja.
>> DAVID J. Malan: No, da vidim, če vaš Strategija spremembe, če sem se gibljejo do nas
naš drugi primer tukaj z 7 različnih vrata.
Same številke, vendar je to ko so razporejene.
Kakšna je vaša strategija tu bo, poskuša dati ven iz svojega uma, kar
druge številke so -
>> JENNIFER: OK.
>> DAVID J. Malan: - prej?
>> JENNIFER: Začnimo s prvo.
>> DAVID J. Malan V redu.
Začnite s prvo.
4.
Zdaj, če boš šel in zakaj?
>> JENNIFER: 4, je res majhen.
Torej, če si neke morda najmanjši da največji, morajo to
se dvakrat, in -.
>> DAVID J. Malan: OK.
Poglejmo, katere misliš?
>> JENNIFER: Poskusite zadnjega.
Lepo.
>> DAVID J. Malan: Zelo lepo opravljeno.
Vse je v redu.
>> [APLAVZ]
>> DAVID J. Malan: OK.
Torej ste pravzaprav počne to strašno, ker si
to počne zelo dobro.
Ki nas pusti more nekatere točke.
Torej poskusimo roll nazaj.
>> JENNIFER: OK.
>> DAVID J. Malan: Zelo dobro narediti, vseeno.
Torej ste začeli na začetku, ste videli, da je bil 4., potem
premakne na konec.
Ampak predvidevam, da niste dobili srečo tam, in domnevam 50
je bil nekje drugje.
Kaj je tvoj Tretji korak je bilo?
>> JENNIFER: Pojdite nazaj na začetek.
>> DAVID J. Malan: Pojdi nazaj na začetku.
OK, tako da bi si dotaknil ta vrata, ki je 8.
Vse je v redu.
Torej to ni 50.
Kje bi si pogledal naslednji?
>> JENNIFER: Če nisem vedeli so razporejene.
>> DAVID J. Malan: Pravilno.
No, če si vedel so razporejene -
>> JENNIFER: Oh, vedel, ja.
>> DAVID J. Malan: -, vendar si ne vem, kje je še 50?
>> JENNIFER: Samo nadaljuj.
>> DAVID J. Malan V redu.
OK.
Nadaljuj.
OK, da ne morem delati.
>> JENNIFER: OK.
>> DAVID J. Malan: Zdaj, če ste pravkar dogaja, da se dogaja, kaj je tvoj
algoritem, ki se prenašajo stisnil v.
>> JENNIFER: linearna -.
>> DAVID J. Malan: To je nekako linearno.
Ampak naj predlagajo, naj me je dal na kraju samem.
Dovolite mi, da osvežite stran.
Enako število, enako ureditev, ista vrata.
Ampak pomislite na ta prvi dan razred, ko smo trgali imenik, v
pol, nekako, in kaj je bilo Naša strategija je?
>> JENNIFER: Začnite na sredini.
>> DAVID J. Malan: OK.
Torej, začeti na sredini.
Torej, gremo naprej in simulira to.
Začnite na sredini razkrivajo ta vrata.
Torej številka 16.
Torej, kaj bi naredil močan fant, ki strgal telefonski imenik na pol,
priti na naslednjo ugibati?
>> JENNIFER: Pojdi v tej polovici.
>> DAVID J. Malan: In zakaj na desni?
>> JENNIFER: Če bi bile nekakšen najmanjši do največjega, nato 50 mora biti
v ta namen.
>> DAVID J. Malan: Dobro.
Povsem razumno.
Tako kot telefonski imenik, greš na prav v nasprotju z leve strani, vendar tukaj
je ključna hrana za s seboj.
Sedaj lahko vrgel proč, ali odtrgajte, polovica tega problema, kar vam bo pustilo ne
s 7 vrata, ampak res samo z 3.
Kar je približno polovica velikost problema.
Vse je v redu.
Torej, kaj zdaj bi morali storiti, ko gremo desno?
>> JENNIFER: Torej, 16 je še vedno zelo majhen, v primerjavi z 50, tako da morda bom poskusil,
podobno, je ta.
>> DAVID J. Malan V redu.
42.
Vse je v redu, tako da zdaj kaj je vaša instinkt vam pove?
>> JENNIFER: Lahko mečejo to nato le -
>> DAVID J. Malan: OK.
Dobro, lahko mečejo levo polovico tam.
>> JENNIFER: - izberite to.
>> DAVID J. Malan: In prav.
>> JENNIFER: Ja.
>> DAVID J. Malan: Torej, čeprav je težko da vidim, morda, če obstaja samo
7 vrata, pomislite, zdaj, doslednost
algoritem, ki ste jo pravkar uporabljali.
V prejšnjem primeru, da si posreči, kar je super.
Ampak si uporabite hevristično, Jaz bi rekel.
Uporabili ste nekako instinktom, in vedoč, da je urejeno, če je to precej
majhne na začetku, seveda, ki smo jih Moram iti bolj v desno.
Toda v nekem smislu imaš srečo, ker je mogoče to številko 100,
in morda 50 je bil bolj v sredini.
Mogoče 50 je bil celo tukaj.
>> Ampak kaj si naredil malo drugače je bil to čas, da si isto stvar
znova in znova.
In trdim, da tisto, kar ste pravkar ni, čeprav vplivajo na telefonu
Knjiga primer, je nekaj veliko več algoritmično, in še veliko
manj posebna opazoval.
Veliko manj nagonsko.
Torej, na koncu dneva, kako bi opišete učinkovitost
Prvi algoritem, kjer ste šli od leve proti desni, v primerjavi
Drugi algoritem tukaj?
>> JENNIFER: To bi moral biti eden, kot je, morda polovico zmanjša čas, ali celo več, ja.
>> DAVID J. Malan: OK, morda celo več.
Oglejmo potisnite malo težje na to.
Kaj res, če bomo še naprej to logika, bomo zagotovo prepolovila
teče čas s tem drugim algoritmom ga vrgel proč polovico
številke, ampak kaj smo storili na naslednji ponovitev, ko je Jennifer razkrila
druga številka?
>> Ponovno smo prepolovili števila vrat.
In kaj potem smo naredili po tem, če je bilo več vrat, da igrajo z?
Mi bi jih prepolovili, in spet, znova in znova.
In to je ravno tako kot vama vse stoje v prvem tednu
razred, pol si sedel, pol od vas sedel, pol vas
sedel, dokler eden od lone Duša je stal.
In mi je rekel, da čas teče da je število korakov je trajalo
o vrstnem redu kaj?
>> SPEAKER 1: [neslišno]
>> DAVID J. Malan: Torej dnevnik baza 2 n, ali pa bolj enostavno, da se prijavite na n.
Torej, kaj logaritemsko.
In graf ni ravna črta da bo še slabši in slabši, je bilo
Ta zanimiva krivulja, ki ni dobili tako slabo daljšem časovnem obdobju.
Torej, da imajo na tej ideji.
Oglejmo hvala Jennifer.
Hvala, da si prišel gor.
In ena sek.
Ni desk svetilke danes, vendar smo pa imajo CS50 stres kroglice.
>> JENNIFER: Bravo.
>> DAVID J. Malan: V redu, tukaj.
Zahvaljujemo se vam za nastale Stres tukaj.
Vse je v redu.
Torej, da vidimo, če ne moremo zdaj To formalizira malo več.
Torej še enkrat, kaj smo pravkar storil, je bilo v bistvu ista stvar kot smo
V tem prvem tednu.
Toda namesto konca s samo linearno Algoritem, ki jo je prikazano
prej kot to premico, pri čemer, če bi dal še eno vrat
zaslon, nato Jennifer bi moral pogledati, potencialno
zadaj še ena vrata.
Če smo se še dve vrati, je morda da si za dve vrata.
>> Tako je bilo to linearna razmerje med velikostjo
Problem na, recimo, na x-osi, in Količina časa, ki je potreben za
rešiti na y.
Ampak slike sem namiguje na prej je bila ta zelena črta.
Zelena namerno, ker to šele počutil bolje.
V teoriji, algoritem, ko nam je uspelo z imeniku, ko nam je uspelo
z vidva štetje seboj, in V drugem primeru, ko Jennifer samo
Uspelo ti je tukaj gor, to je neke za bistveno bolje.
Ker to ni bila samo dvakrat hitreje.
Ni bilo celo štirikrat hitro.
Bilo je povsem odvisna od tega, kaj velikost vhodu je, o tem, koliko
ukrepe, ki jih na koncu vzel.
>> In tako je to preprosto idejo, da smo vsi vzel za odobrene z imenika,
Podobno se lahko uporablja za kaj takega.
In to bi bilo bolj mimogrede znani kot, kot si morda
predstavljate, deli in vladaj.
Ni razliko kar smo seveda z imeniku.
>> Ampak psevdokoda, odpoklic, je bilo to.
Tako da ne bo to naredil še enkrat, ampak spomni da je prvi teden, vse nas je vstal
in potem polovica vas usedel, polovica si se usedel, polovica vas sedel.
Ta algoritem je bil izveden v malo goljufanja način, s tem, da
ni bil le eden od mene štetja, bistveno bolj učinkovito.
V tem primeru sem vplivno sekundarni vir.
Nekako, več procesorjev, več možgani, več pametnih ljudi
Prostor so mi pomagali priti iz nečesa linearno na nekaj
logaritemska, od nečesa rdeča za nekaj zelene barve.
>> Ampak v tem primeru, ne more sam Jennifer bistveno izboljšati
uspešnost svojega prvega algoritma, ki ga, še enkrat, samo razmišljanje malo težje.
Sedaj, ko pride čas za izvedbo te stvari, ugotoviti
kaj vrstic kode lahko pišete na primer ki jih lahko ponovite še enkrat, in
znova in znova, nekako v krožnem način.
Ker ne boš šel, da imajo luksuz, kot je Jennifer storila na eni strani,
samo še cel kup investicijskih skladov in pravijo, hmm, če je to prva številka 4,
Naj skok vse do konca.
Oh, če je ta številka je prevelika, Naj premakniti samovoljno nazaj
z drugim elementom.
Boste ugotovili, da se dogaja, da je veliko težje formalizirati, kaj smo ljudje
samoumevno kot zelo razumen tolči, ampak računalnik je le
naredili tisto, kar je povedal, da ne.
>> Zdaj to je zelo zanimivo posledice.
Ta graf je nekako pomenilo, da nekako preplavijo vizualno, ampak obvestilo, kjer je
je premica v grafu?
Kje je linearen graf , ki ga imenujemo n?
No, to je nekako proti dnu te slike, kajne?
Torej, vse smo naredili, je, ki smo jih nekako pomanjšana na x-osi in
y-os, da bi poskušali dobiti občutek, kaj druge vrste krivulj izgledal.
>> In posebnosti matematično Izrazi danes ne bo pomembno, da
veliko, ampak obvestilo, da obstaja veliko algoritmi, ki so slabša od
nekaj, kar je linearna.
Dejansko n kubikov izgleda precej slabo.
2 do n izgleda precej slabo. n kvadrat izgleda precej slabo.
In bomo videli, kaj nekateri od tistih, Morda je v resnici še danes.
In log n ne počuti tako slabo, vendar bolje kot je n dnevnik baza 2 n.
Ampak veste, bi bilo še bolj neverjetno, če Jennifer, ali pa če mi,
da je prvi teden, je prišel do nekaj, kar je log log n.
>> Torej, z drugimi besedami, da je to celo spekter možnih rešitvah
težave, ampak tudi tu obvestilo kaj se bo zgodilo.
Ko sem pomanjšati, katera od teh krivulj se bo izkazalo, da je absolutna
najslabše od tiste na zaslonu sedaj?
Torej n kubikov izgleda precej slab v tem trenutku.
Ampak, če bomo pomanjšati in si oglejte več x in y os, ki bo
prevladujejo na koncu?
Torej je dejansko izkazalo, da je 2 do n, in lahko to ugotovite le s
priklopom na nekaterih vedno veliko številke, in boste videli, da od 2 do
n, dejansko postane večji veliko hitreje.
Če bomo res pomanjšati, je 2 do n algoritem popolnoma zanič.
Mislim, to se dogaja, da sprejmejo zelo malo časa za
Računalnik churn skozi.
>> Ampak boste videli čez čas, še posebej, s prihodnjimi problematičnih sklopov in celo
končni projekti, so vaši podatki set dobi velik, prav?
Tudi v prvi različici Facebooku kot število prijateljev, in
Število registriranih uporabnikov dobil velik, lahko nekako it v telefon in
izvesti nekaj z linearno iskanje, ali zelo preprosta sortiranje
algoritem, kot bomo videli danes.
Moraš začeti razmišljati težje in težje o teh problemih.
In vrste težave krajih, kot so Facebook in Google in Microsoft,
in drugi delajo na točno ti nekakšen veliki podatkov vrste vprašanj
vedno bolj v teh dneh.
>> Vse je v redu.
Torej uspeh Jenniferjevem v ta drugi algoritem, odkrito povedano, ona presenetljivo
tudi prvič, vendar naj je kot sreče napisati tako, da smo
lahko to točko.
V drugem primeru pa je spodbudil algoritem, ki ponovi in
spet, vendar je vzela za samoumevno nekatere predpostavke, da smo dovolili
njo, ampak ona izkoristiti nekaj podrobnosti drugič, da ni imela
prvič.
, Ki je bil kaj?
>> Ta seznam je bil razvrščen.
Torej, takoj ko razporejene seznam smo trdijo, da je Jennifer sposobna narediti
bistveno bolje.
7 vrata, ja, ni to zanimivo, ampak to domnevam, da smo 7 milijonov vrata.
Log n se definitivno bo opraviti še veliko, veliko
hitreje na dolgi rok.
Ampak ona je morala imeti Vrata razporejene za njo.
Zdaj sem vzel svobodo tem, da vnaprej na računalniškem zaslonu
tu, ampak predvidevam, da je Jennifer moral storiti, da zase?
Recimo, da so vrata v zadevni zastopane podatkov v zbirki podatkov, ali
prijatelji, registrirane za Facebook, ali vse spletne strani na internetu, ki
različne spletne strani, bi morali indeks ali iskanje več.
>> Predvidevam, da si imel neobdelanih podatkov določiti in je bila prepuščena vam, ali
Jennifer storiti je, da sortiranje?
Da ne zahteva, da smo odgovorili Vprašanje, no, koliko časa
bi bili sprejeti Jennifer, ali celo mi, razvrstiti te številke vnaprej, tako
da bi ona to izkoristil?
Kajne?
Ker posledice, seveda, , če se mi je precej časa za razvrščanje
številke, ki so vraga briga, da vas lahko najdete številne kot 50 tako hitro,
kot v primeru Jenniferjevem, če smo več kot preobremenjeni količino celotnega časa
to je s sortiranjem stvari vnaprej?
>> Torej, da vidimo, če ne moremo naslikati sliko tukaj.
Imam cel kup več stresa kroglice, če to pomaga
prebiti led tukaj.
In če ne bi motilo, smo potrebujemo sedem prostovoljec -
no, OK.
Wow.
Tako da nam ne bo treba porabiti na svetilk mizo, se zdi.
Vse je v redu.
Torej, kako pa ti dve spredaj.
Kaj pa ti dve fantje v hrbtu.
Torej, to je štiri leta.
Kaj pa ti pred pet, šest in sedem.
Tam.
Tvoj prijatelj te je poudaril, tako da boste dobili nagrado.
>> Vse je v redu.
Pridi gor.
In zakaj ne imate fantje, pridi sem.
Bom dal vsako številko.
In iti naprej in se dogovorite sami identično s tem, kar je
prikazano na zaslonu.
>> [Interposing GLAS]
>> DAVID J. Malan: OOP, žal.
Bug.
Vse je v redu.
No, pa gremo.
Številka pet.
Število šest.
Ena, dva, tri, štiri, pet, šest, sedem.
Oh, to je čudno.
>> ZVOČNIK 2: bom dobil -.
>> DAVID J. Malan: Dober posel.
Vse je v redu.
Hvala za sodelovanje.
>> [APLAVZ]
>> OK.
Vse je v redu.
Torej imamo štiri, dva, šest, ena, tri, sedem, pet.
Izpopolniti tako da imamo sedem prostovoljcev tukaj, ki so enake v širino
matrika, da igramo s prej.
In sem se odločil, sedem razlogov da bo prav
priročno v malo.
In jaz bom predlagala, prvič, da moramo rešiti teh sedem prostovoljcev.
Če želite, prvič, pozdravit, čeprav.
Glede na to, se bo nerodni nekaj minut.
Predstavite se.
>> GRACE: Živjo, jaz sem Grace.
Sem letniku Leverett House.
>> BRANSON: Pozdravljeni.
Jaz sem Branson.
Jaz sem novinec v Weld.
>> GABE: Pozdravljeni.
Jaz sem Gabe.
Jaz sem junior v Cabot.
>> Neil: Jaz sem Neil.
Jaz sem novinec v Matthews.
>> JASON: Jaz sem Jason.
Jaz sem novinec v Greenough.
>> MIKE: Jaz sem Mike.
Jaz sem novinec v Grays.
>> JESS: Jaz sem Jess.
Sem letniku Leverett.
>> DAVID J. Malan: Odlično.
Vse je v redu.
No, hvala za vse naše Prostovoljci tukaj tako daleč.
In izziv pri roki zdaj se dogaja da razvrstiti od teh fantov, potem pa
bomo morali razmišljati malo težko o tem, kako učinkovito smo dejansko
jih razporejene.
Torej, kaj je najprej poskusite s tem.
Vi lahko vidite število enih in drugih samo z dajanjem okoli vogalov.
Pojdi naprej in traja nekaj sekund, in sortiranje sami od najmanjših na
levo največji na desni strani.
Pojdi.
>> OK.
Dobro.
To je bilo res presneto hitro.
Zdaj tukaj je nekdo, kaj je algoritem da se ti fantje?
>> SPEAKER 1: Najmanj do največje.
>> DAVID J. Malan: OK.
Vsaj do največje je res nekako Cilj, vendar nisem prepričan, da je
Res algoritem.
Vsaj največje ne pove me korak za korakom, kaj storiti.
Ja?
>> SPEAKER 1: [neslišno]
>> DAVID J. Malan: OK.
Torej, če ste videli oseba, manjši od vašo številko, potem premaknete
Pravica do njih.
Tako da je sedaj vse bolj ekspresivna, več kot algoritem, ker ste
lahko rečemo, če je to, potem je to.
Torej imamo nekakšno pogojen konstrukt.
In ti fantje zdelo, da to, da nekaj krat, saj nekateri izmed vas preselili malo
na daljavo.
Tako je bilo verjetno nekakšen zanka se dogaja v njihovih glavah.
>> Ampak poskusimo formalizirati to.
Če bi vidva ponastaviti nazaj k temu dogovoru.
Poglejmo, če ne moremo formalizirati to bit, in potem vprašati, samo
kako učinkovito je to?
Seveda, ko smo to naredili bolj počasi, to se dogaja, da se počutijo kot dobro
algoritem, ampak poglejmo, če lahko dal svoje prste na natančnih korakih.
>> Torej, vidva sta štiri in dve.
Ali ste pravilno ali napačno, da?
Očitno napačna.
Tako smo zamenjali.
Zdaj bom umaknite tu in reči, 05:56.
Ste pravilna ali napačna?
>> GABE: Pravilno.
>> DAVID J. Malan: Pravilno.
Šest in ena?
Nope.
Swap.
Torej, to sta dve zamenjave.
Šest in tri?
Nope.
Swap.
Šest in sedem?
Videti je v redu.
Sedem in pet?
>> JESS: [neslišno]
>> DAVID J. Malan: OK, zamenjali.
In razporejene.
Vse je v redu.
Torej očitno ni, kajne?
Torej je bil tam več dogaja.
Ampak, seveda, ti fantje, čeprav samo nagonsko.
hranijo premika.
Niso samo ustavi, ko popravljena eno težavo.
Torej.
Vsekakor bom še da storijo enako stvar.
Bom moral nekako previjanje nazaj na začetku tega problema,
ali začetku tega sklopa ljudje, začnimo jih kliče.
>> In kaj zdaj, naj moja algoritem na drugem prehodu biti?
>> SPEAKER 1: Ista stvar.
>> DAVID J. Malan: Ista stvar.
In to, da sem začel imeti rad, kajne?
Kakor hitro lahko znajdete početje isto stvar znova in znova, da je
postaja vse bolj podoben algoritmu, in manj človeški instinkt.
>> Torej, zdaj, tukaj smo spet tam.
Dve leti in štiri?
Število
Štiri in ena?
Ah, tam je bil res nekaj dela še treba storiti.
Za in tremi?
Dobro.
Štiri in šest?
Šest in pet?
Šest in sedem?
OK, sedaj storiti.
OK, ne.
Moram iti nazaj.
>> Torej sedaj, še enkrat, to delamo malo bolj načrtno.
In zdaj, obstaja samo ena možgani izvršitve ta algoritem.
Ena CPU, če ga boste.
In odkrito povedano, to je edini vir da bomo imeli dostop do.
In ko smo se vrniti na tipkovnico in imajo nekaj podobnega C na našem
odstranjevanje, smo samo pisno program da lahko naredimo eno stvar naenkrat.
Ker ti fantje pred nekaj trenutki smo vzvodom njihova kolektivna intelektualnega potenciala
tako kot vi storili v tednu nič.
Torej, kaj je obdržati to.
>> Dva in ena.
Dva in tri.
Tri in štiri.
Štiri in pet.
Pet in šest.
Šest in sedem.
Naredil?
Torej, jaz sem, ampak naj igrajo hudičev odvetnik.
Jaz tudi neke vrste računalnik, ki je pravkar je točno skozi ta niz
ljudje, veste, da sem naredil?
>> SPEAKER 1: Ne
>> DAVID J. Malan: Torej, zakaj?
Kaj bi morali storiti, da bi se sklene odločilno, da sem naredil?
Verjetno še ena podaja.
Kajne?
Ker vem, da je od prejšnje Preval je, da sem popraviti napako.
In to pomeni, morda je še ena napaka
da moram popraviti.
Tako sem lahko prepričani samo s previjanjem in nato preverjanje, 01:59, dve in
tri, tri in štiri, štiri in pet, pet in šest, šest in sedem.
OK, zdaj sem brez dela.
>> Vsekakor se spomnim, da sem storil ne delo z nekaj podobnega spremenljivke,
všeč int.
Da zamenjave klic, in če zamenjave je 0 nekoč I tu in se je začel na 0, potem
Rad bi le bilo neumno, da nadaljujem in nazaj, ponovno preverjanje in
spet in spet, kajne?
Ker se vam zatakne pri nekaterih nekako neskončno zanko.
Torej, kakor hitro je 0 zamenjave, lahko trdimo, da je to
Algoritem je res popolna.
>> Zdaj, kaj je dal ime za to.
Algoritem, ki Predlagam smo pravkar izvajati je nekaj, kar ti mehurček
vrste, znane kot tak v smislu, da številke, ki so večje vrste
mehurček svojo pot do vrha, ali do na koncu niza številk.
Ampak kako učinkovito je to algoritem?
Koliko korakov sem fizično moral da, na primer, reda oglasov
sedem ljudi?
>> Štiri do pet?
OK, preveč je navsezadnje bo odgovor.
Toda tudi takrat, določeno število ni tako zanimivo.
Kaj je to, kot n posploševati.
Torej, če sem n ljudi tu gor, in so so bili nekako v naključnem vrstnem redu na
začenši v tem prvotnem vrstnem redu.
No, koliko korakov pa imam da se v prvem prehodu?
To je bila ena, dva, tri, štiri, pet, šest, in oni so sedem ljudi, tako
da je sedem, šest -, tako da je n minus ena korake prvič.
>> Zdaj, koliko korakov pa imam da se, ko sem previti?
No, lahko bi dejansko podvojila, da če smo res želeli, vendar za zdaj, sem
Samo reči, vse v redu, še n minus 1.
Torej n minus 1 bo dobil nadležno slediti, tako da je
Samo zaokrožitev nekoliko.
Tako 2n koraki.
Torej 14 korakov, gor ali dol.
>> Kolikokrat sem se korak naslednjič?
No, to je 3n.
res.
In zdaj, v najslabšem primeru za na primer, kolikokrat bom moral
šli naprej in nazaj, naprej in nazaj, izvršitve ta algoritem, menjava
ljudje na vsakem prehodu, grobo?
To je dejansko n kvadrat, kajne?
>> Ker v najslabšem primeru lahko nekako si od razmišljati o tem intuitivno,
čeprav bo trajalo malo malo časa, da se potopi noter
V najslabšem primeru, kaj bi ti Sedem ljudi je izgledala v
pogoji dogovora njihovih številk?
Popolnoma nazaj, kajne?
In samo, da simulira, da kaj je ime?
>> MIKE: Mike.
>> DAVID J. Malan: Mike?
V redu, Mike, si lahko samo se mi pridruži preko tukaj samo eno sekundo?
Pravzaprav ne.
Žal Mike, kaj je navijanje.
Kaj ti je že ime?
>> Neil Neil.
>> DAVID J. Malan: Neil.
OK, Neil, prideš z me, če vas ne moti.
Torej bom predlagal, samo za preprostost, ki je zdaj v njegovi Neil
najslabši možen primer.
Ampak spomnim, kako sem izvajala moj algoritem.
Jaz sem primerjavo, primerjanje, primerjanje, primerjanje, primerjanje, oh.
Zdaj so ti ljudje iz reda, tako da sem popraviti.
Torej vidva zamenjali.
Vendar menijo, zdaj, koliko dlje pa Neil iti?
To je približno n.
Veš, to ni dejansko n.
To je kot, n minus 1, a se bom motenih sledenja malo
Številka, zato naj samo call it n.
>> Torej, če Neil premakne en korak maksimalno vsak čas, in da se premaknete Neil en korak,
Moram narediti to res dolgočasno glavo in nazaj, to je približno
delaš to, n korakov, skupaj z n-krat, saj se dogaja, da me
da veliko ukrepov, da bi dobili Neil vse pot do tam, kamor spada.
Kaj šele vsi ostali, če vidva so bili vsi napačno naročiti kot dobro.
>> Torej recimo mehurček vrste n kvadrat.
Čas tega algoritem teče, izvajanje tega algoritma,
učinkovitost tega algoritma smo se pravkar opisali več
splošno kot n kvadrat.
Kar je lepo, ker nisem mogel storiti Enako primer z osem ljudi, devet
ljudi, milijon ljudi, in da Odgovor se ne bo spremenilo.
>> Torej, če vi ne bi motilo, dajmo ti prikrivati, kjer ste začeli.
In poskusimo še dva druga pristopov in glej, če ne moremo narediti bistveno
bolje od tega.
Torej ta čas, bom predlagala nekako drugačen algoritem.
To je bil zelo pameten od nas zadnji čas, in vi imeli prav, da imajo
pravi instinkt za samo vrste za zamenjavo parih.
Ampak, če sem res želela približati to preprosto in moj cilj je, da se premaknete
vseh malih številk na ta način, in all velikih številk, ki
način, zakaj ne bi jaz samo to, da je v najbolj naiven način mogoče, in videli, če sem
Lahko si boljši od tistega, kar je bilo dokaj zapleten algoritem?
>> Torej, da vidimo.
Štiri je zelo majhno število, torej sem vas bo pustil tam trenutek.
Ooh, številka dve je še bolje.
Tako da lahko samo korak naprej za trenutek?
To je trenutno moj najmanjši oštevilčena Kandidat, in bom, da se spomnimo
da se z, recimo, spremenljivko.
Ampak bom sproti preverja.
Ali obstaja nekdo, čigar število je manjše?
Šest, št.
Oh, tam je Neil znova.
>> Torej, jaz vas bom potisnite nazaj nekako konceptualno.
Neil bo prišel naprej.
In zdaj, spremenljivke, ki sem uporabo na slediti, kdo ima najmanjši
Številka je posodobiti, da vsebujejo Lokacija Neil je.
No, pa poglejmo.
Tri, sedem, pet.
OK, vem, Neil je najmanjša.
Kaj je najenostavnejša stvar mi pa zdaj?
Jaz ne bom izgubljal časa, ki ga pravkar bisernih Neil eno mesto v levo.
Zakaj ne bi samo dal Neil kjer je pripada, kar je seveda kje?
>> Vse smer na začetku.
Torej Neil, pridi z mano.
In kaj je bilo ime?
>> GRACE: Grace.
>> DAVID J. Malan: Grace.
OK.
Torej Grace, žal, si nekako na poti.
Torej, kako bomo rešili ta problem?
Kajne?
Če je to polje, ni le sedem lokacij.
Spomnimo se, da je z Robom, smo se pogovarjali o razglasitvi starosti, in smo imeli samo
končno število starosti?
Isto idejo tukaj.
Imamo le končno število ints.
Grace je nekako v našem način, tako da kako popraviti?
>> Najenostavnejši način je všeč, Grace, oprosti.
Boš moral iti tja tam, tako da bomo lahko naredili prostor.
Zdaj, če menite o tem, morda smo samo na problem slabše.
In morda smo storili, ker kaj če Grace so bili na pravem mestu?
Vemo pa, da je ni, ker V nasprotnem primeru bi ji bilo
stoji naprej namesto Neil v tem trenutku, kajne?
Smo že preverili njeno številko ven.
>> Vse je v redu.
Torej, zdaj, Neil je na pravem mestu, in Jaz lahko naredim rahlo optimizacijo.
Za naslednjo minuto, bom ignorirati Neil vse skupaj, tako da ne
zapravljajo svoj čas, ali nehote ga zamenjali na napačnem mestu.
Torej, zdaj, kako se mi zdi Naslednja element, ki je najmanjša?
Dva.
To je zelo dobra številka, če želite korak naprej in
Zapomnil si vas bom.
Šest, ni dobro.
Štiri, tri, sedem, pet, ni dobro.
Naj vas premestimo na vaš pravi kraj.
In pravkar smo srečo tokrat.
>> Zdaj bom prezreti teh dva fanta, zdaj pa naredite nekaj več
skozi to.
Šest, da je zelo majhno število.
Pridi naprej.
Oh, oprostite.
Številka Grace je bolje, tako stopiti naprej.
Štiri.
Oprostite, Grace.
Spet nazaj.
Številka tri je bolje.
Sedem.
Pet.
In kaj zdaj ti je že ime?
>> JASON: Jason.
>> DAVID J. Malan: Jason.
Torej, Jason je zdaj najmanjši Element sem izbran.
Kje je šel?
Torej, kje je šest.
In tvoje ime je spet?
>> GABE: Gabe.
>> DAVID J. Malan: Gabe.
Gabe je na poti.
Kaj je najlažja stvar?
Swap ta dva fanta in še naprej.
Torej, zdaj pa poglejmo.
Kdo je najmanjša?
Štiri.
Dovolite mi, da nekako goljufija.
Pet se bo najmanjši.
Se mi zdi naslednji, če želite stopiti naprej, kaj moram storiti s
ti fantje, s Gabe?
Spet zamenjali.
Torej, zdaj, še vedno rahlo v okvari.
Ugotovil sem, Gabe za najmanjšega, tako Jaz pop ga, vam premakniti fantje znova.
In naredil.
>> Torej odgovor je enak.
Končni rezultat je enak.
Kateri od teh dveh algoritmov je boljši?
Drugi pa, sem slišal.
Zakaj?
>> ZVOČNIK 3: To je n korake [neslišno].
>> DAVID J. Malan: To je n koraki v večini.
Zanimivo.
Tako je, čeprav?
Torej, kako si se mi zdi najmanjši element?
Koliko korakov sem moral vzeti najti najmanjši element?
Imel sem videti konca Na koncu, kajne?
Ker v tem najslabšem primeru, kaj če bi bil Neil tukaj?
Torej le ugotovitev, najmanjši element se mi n korakov ali N minus 1.
Ampak, v redu.
Torej popraviti Neil.
Ne pozabite, da je minuto ali dve nazaj.
>> Toda kako se mi zdi naslednja najmanjši element?
To je n minus 1 ali n minus 2 res, iz več korakov.
Torej, v redu.
Torej nisem n minus 2.
Vse je v redu.
Tako, da se počuti malo bolje.
Vse je v redu.
Koliko korakov naslednjič poiskati številko tri?
Torej n minus 4.
Tako da se zmanjšuje, ena manj stopiti na vsaki ponovitvi.
Torej to ne počutite bolje, kajne?
Če zadnjem času je bilo približno n krat n, ta čas je n minus 1, plus minus n
2, plus n minus 3 plus n minus 4, pika, dot, pika.
Ampak, če se spomnite iz srednje šole učbeniki, malo goljufija
stanja na zadnji strani, ki je formul, če dodate to vrsto številk,
kar je skupno število korakov bo, da bom tukaj?
>> To je eden od tistih, všeč, n minus 1 krat n, deljeno z 2.
Torej, da vidim, če sem lahko pull to gor za trenutek.
In spet, sem nekako zaokroževanja nekatere številke samo, da naše življenje preprosto,
ampak kot se spomnim, da je nekaj takega kot če Jaz n minus 1 stvari, potem je n minus
2, potem je n minus 3, je v grobem kaj takega več kot 2, in če sem
pomnožite to jasno, da je dejansko n kvadrat.
Da se ne počuti preveč dobro. n minus n čez 2.
>> Ampak tukaj je stvar.
V računalništvu, ko je problematika začeli, da bi dobili zanimivo je, ko n
postane zelo velik.
In ko n postane zelo velik, katera te vrednosti se dogaja, da obvladujejo vse
od drugih?
To je nekako n kvadrat, kajne?
Ja, deljenje z 2 je precej dobro.
Ampak, če govorimo o milijardah koščkov podatkov, ali bilijonov
koščki podatkov, ok, tako da ste dvakrat hitreje.
Ampak kdo res briga, če tega veliko število, če ta faktor kaj dobi
večji in večji.
In zagotovo, da naredi več Razlika od tega tipa.
Torej, čeprav imate prav, Drugi algoritem, bomo ga pokličete
Izbor vrste, je v realnem svetu, malo hitreje lahko, ker sem
ob manj in manj korake vsakič.
>> To ni res bistveno hitreje.
Ker, če smo dejansko igrajo to ven velike vrednosti n, na koncu
dan, za dovolj velik n, da je še vedno dogaja, da se počutijo zelo počasi.
No, naj vzamem eno zadnja podaja na to.
To je tisto, kar bi vas vabim Izbor vrste.
Lahko vidva ponastaviti sami zadnjič?
In v tem zadnjem primeru, bom predlaga nekaj
imenovano vstavljanja vrste.
Vstavljanje neke počutje, konceptualno, malo drugačen.
>> Namesto gredo naprej in nazaj in izbiri najmanjši element, sem
šele tekoč, da se ukvarjajo z vsako od teh fantje, kot sem jih srečujejo, in vstavite
jih v svojem pravem mestu.
Torej bom samo, da začnete z Grace, in vidim, da je ona številka štiri.
Kje številka štiri pripada?
Nisem začel sortiranje ničesar, tako Grace pride, da ostanejo tam.
In zdaj bom trditi, če bi lahko narediti korak na vaši desni strani, to
moj razporejene seznam, to je moj unsorted preostali seznam.
Torej, zdaj bom nadaljuje naslednji, in kaj ti je že ime?
>> BRANSON: Branson.
>> DAVID J. Malan: Branson.
Torej Branson je številka dve.
Torej bom peljal ven za trenutek.
In zdaj, kam spadaš V tem polju?
Torej za pravico do Grace.
Torej še enkrat, mi smo nekako tako Grace storiti veliko dela tukaj.
Kje vas čaka?
Torej bomo vas potisnite levo in vstavite Branson tam.
Zdaj pa trdijo, da fantje so storili.
Ampak obvestilo, da sem ne uporabljate dodaten prostor.
To je še vedno 2 elementi Tukaj, 5. sem.
Skupna velikost polja je 7, torej sem ne vara, v redu?
>> Torej, zdaj imamo z Gabe tukaj Številka šest, kam spadaš?
Spet imaš srečo.
Tako da boste dobili, da ostanejo tam.
Vzemite majhen korak v desno Samo da bo jasno, da ste razvrščeni.
In zdaj imamo Neil spet številka ena, kam greš?
In zdaj je, če bomo začeli razumeti, da Ta algoritem, čeprav na prvi
pogled, počuti zelo pameten, pazi kaj se bo zgodilo.
Če bi lahko stopite naprej.
>> Kje želimo postaviti Neil?
Torej očitno tu, da kako bomo dobili Neil tam?
Naredimo to korak za korakom.
Gabe, kam morate iti?
Ja, tako bo en velik korak, ali dva pol-korakov, da
en korak tja.
Grace, kje si?
Dobro.
Torej še en korak.
In končno, Branson?
Še en korak.
In sedaj bomo lahko Neil na svoje mesto.
>> Torej, zdaj, še to logiko.
Čeprav mi ne premikajo Neil več in več in več, da bi ga dal
kam gre, v najslabšem primeru, Naslednja številka se lahko srečajo bi
je število, jasno je, da je število nič, potem pa bomo preusmeriti vse
ti fantje.
Denimo, da je številka, negativna ena, potem imamo za premik
vseh teh fantov.
Tako da smo res nekako lahkota Problem okrog, tako da smo
prenos stroškov iz Postopek izbire tako vstavitev
proces, tako da samo še vidva premakniti približno n minus nekaj
število korakov.
In da je število korakov je samo še povečati, kot sem izberete več številk,
če imam, da pometemo vaju nazaj in nazaj in nazaj.
>> Tako žalostna stvar, zdaj je vse to algoritmi so n kvadrat.
Pojdimo naprej in hvala ti fantje, in vizualizirati te malo
drugače.
Zelo dobro opravljeno.
>> [APLAVZ]
>> Vse je v redu.
Tukaj imaš.
Hvala za -
>> BRANSON: [neslišno] obdržati številke.
>> DAVID J. Malan: No, lahko vam da številke, kot dobro.
Vse je v redu.
Lepo opravljeno.
Vse je v redu.
Torej, da vidimo, če ne bomo zdaj lahko povzamemo hitreje in bolj vizualno
kaj se je zgodilo tukaj, kot sledi.
Jaz grem naprej in dvigni Firefox.
Bomo povezati to demonstracijo na spletni strani seveda je.
Java je malce nadležno, da se delo v nekaterih brskalnikih teh dneh.
Torej, če igrajo z to doma, spoznali boste morda morali uporabljati Firefox
da bo stvar delovala.
In kaj bom naredil s tem predstavitev je naslednji.
>> Na dnu, imam cel kup možnosti menija, vključno z začetkom in
Stop.
Prav tako, kot sedmih, se zdi, da bug v teh programih, s katerimi si
ne more dejansko videli začetek ali zaustavitev gumb, če imate Command ali Alt
plus in povečaj, ki radovedno prikazuje več gumbov.
Torej, samo v vednost, če igrate s tem doma.
Zdaj grem kliknite Start v pravkar Trenutek, ko podate zamudo,
podobno, 200 milisekund tukaj, samo tako da bomo lahko videli, kaj se bo zgodilo.
>> Zato trdim, da je to vizualizacija prvega algoritma
ti fantje naredili, bubble sort, pri čemer smo zamenjali ljudi, par-modrih.
Ključ vpogled v vizualizacijo je, da višina palic
predstavlja velikost števila.
Torej višji bar, večje število.
Krajša bar, manjše število.
In če ste opazili, da gremo skozi Prvi primer tega algoritma
zamenjavo velike in majhne številke, tako da Manjše število na prvem mestu in
Veliko število gre v desno.
>> In takoj, ko smo dobili konec niza veliko več kot sedem številk, smo
šel nazaj na začetek.
In to pričakuje.
Na skrajni levi, da malček se dogaja da bi zamenjali na stran, in to
postopek se ponavlja.
Zdaj je to vizualizacija hitro dobi dolgočasno, zato naj gredo naprej in ustavi
da spremenite zakasnitve nekaj veliko hitreje, samo da bi dobili zdaj, občutek za
Ta algoritem.
>> Torej, čeprav sem jo pospešiti, to je kot nadgradnja mojega procesorja, nakup
nov računalnik.
Nisem bistveno spremenila moje algoritem, vendar lahko dejansko videli več
očitno kot pri ljudeh, ki veliko Številke so bisernih do vrha,
in na majhne številke so prepihovanja na dno.
In zdaj to stvar tukaj razporejene.
In kot praha, v kvadrate, obstaja samo nekaj knjigovodstvo tam
vam prešteti, koliko primerjav ali koliko zamenjave so
bilo dejansko narejeno.
>> No, pa poskusite eno ostali pa bomo videli.
Dovolite mi, kliknite tukaj mehurček vrste, in Naj izberejo, in to celo spletno stran
je malo nečistnik.
Oglejmo sprejeti tveganje in ga ponovno zagnati.
Takole.
Torej, kaj je naredil izbor vrste.
Ne vem, zakaj meni se pojavi tam.
Oglejmo povečavo, da se določi, da bug, to spremeni do 50.
Ah, kaj je dejansko naredil da je veliko hitreje.
Pet milisekund ali tako, in začeti.
>> Torej je ta izbor sort.
Torej še enkrat, pomislite, kaj smo storil z ljudmi tukaj.
Šli smo skozi niz in izbrano Najmanjše ponovno element
znova in znova.
Zdaj pa trdijo, da je še vedno precej slabo.
To je bil še n kvadrat, Vzemi ali pusti, vendar je bilo v resničnem svetu, nekoliko
hitreje, ker sem bil res ob nekoliko manj korake vsakič.
Ampak mi govorimo samo kaj?
Morda 40 ali tako bari tukaj?
Ne govorimo 40 milijonov.
Tako da ni povsem jasno, se mi, da je bil res velik dobiček.
>> Dovolite mi, da zdaj iti nazaj in spremeniti v našem Tretji algoritem, ki je bil izbere
Vstavitev vrste.
In zdaj je res buggy, ker meni res ni treba dol.
Torej, zdaj bomo se pomaknete nazaj tu gor in začeti ta algoritem.
Poklič, start in stop.
Torej je to ena vrsta ima precej vzorec z njim, pri čemer smo spet
vstavljanje ljudi, ali V tem primeru, palice v
njihovo ustrezno lokacijo.
In to že storila, preden Obrnil sem se.
Ampak tale je tudi v teoriji, še n kvadrat.
>> Torej, da vidimo, če ne moremo povzeti te, kot sledi.
Jaz grem naprej in samo, da nas neke skupne poti govoril
o teh stvareh, naj vam predstavim samo malo zapis tukaj.
Kmalu boste videli nekaj, kar se imenuje velika O, saj je dobesedno velika
O. in na ta način, da računalnik znanstvenik ali matematik celo uporablja
opisati časa vožnje nekega algoritma.
Koliko korakov se je dejansko trajalo?
>> Zdaj bom jaz spravila v zadrego s moj rokopis tu vsak trenutek.
Ampak naj gredo naprej in rekli, da To bo velik O tukaj.
In naj vam predstavim eno drugo Simbol, kapital omega.
Omega se bo nasprotno v bistvu, z velikim O. ker veliko O
sredstvo, v najslabšem primeru, koliko časa Morda nekateri algoritem sprejme v
Pogoji n, omega bo je, koliko časa bi lahko bilo
da v najboljšem primeru.
In bomo videli, kaj mislimo s Najboljši primer v samo nekaj trenutkov.
>> Torej, začnimo nekaj preprostega.
Naj začnem z linearno iskanje.
Torej ni sortiranja.
Mi bomo to imenujemo linearno iskanje.
In zdaj, da malo miza iz tega.
Zdaj pa v primeru linearnega iskanju v najslabšem primeru, koliko korakov je
se dogaja, da me bo najti Število samovoljne izbire?
In tam je n skupno vrata ali n skupno število.
Najslabšem primeru.
Koliko korakov bom moral da bi našli številko 50 v matriki
iz n vrat?
In zakaj?
Ker bi bilo vse Tako kot na koncu.
Toliko kot Jennifer naleteli, Številka 50 je bilo vse tako kot, tako da v
najslabšem primeru linearna iskanje je velik O n, bomo rekli.
>> Kaj najboljšem primeru če dobiš res srečo?
To je samo bo trajalo en korak, ali nespremenjeno število korakov.
Torej bomo opisali, da kot 1..
Torej, to je zelo dobro.
Kaj zdaj, če bomo naredili nekaj kot binarni iskanje?
Torej binarno iskanje, v najslabšem zadevo, je, koliko časa?
>> [Interposing GLAS]
>> DAVID J. Malan: Torej, pravzaprav sem Slišal v nekaj mestih.
Torej, to je pravzaprav log n, Vzemi ali pusti, saj, kot smo razdeliti seznam na polovici
spet in spet in spet, smo sposobni najti končno vrednost,
če je tam, vendar pa je ulov.
Kaj je predpostavka, da moramo samoumevno, pri binarnem iskanju?
To mora biti urejeno.
To ni urejeno, se lahko razdeli stvar spet in spet pol, in ti
Lahko greš levo, in lahko greš desno, in lahko greš levo in desno, ampak si
ne boš našel element, če seznam ni urejen, ker
ste morda zamudili.
Ker vaše tolči, za odhod na levi ali desno, se bo napačno, če je
res ne sortirajo.
Torej je neke vrste skritih stroškov s pomočjo nekaj takega.
>> Zdaj pa gremo v našo sortiranje algoritmi ne išče -
oh, pravzaprav gremo v to prazno.
Iskanje binarno v najboljšem primeru?
Prav tako je 1, če je to le zgodi, da se v samem središču matrike, ali
Sredi imeniku.
Sedaj naredimo mehurček vrste.
Torej še enkrat, zdaj vstopamo vrste, ne pa iskanja.
>> V najslabšem primeru, koliko korakov smo naredili Trditev bubble sort bo trajalo?
n kvadrat.
Torej bom pripraviti, da.
Oh, moj rokopis izgleda še slabše če je to predvideno, da je velik.
Vse je v redu.
Tako da je n kvadrat.
In v najboljšem primeru mehurček vrste, koliko korakov je to bo trajalo?
1, sem slišal.
>> SPEAKER 1: n.
>> DAVID J. Malan: n, sem slišal.
>> SPEAKER 1: 2.
>> DAVID J. Malan: 2, sem slišal.
Slišim 3?
Vse je v redu.
Tako sem slišal 1, n, 2, vendar naj poberem poleg vsaj prvonavedenega
predlogi, 1.
To ni slabo, instinkt, saj je nekako takole vzorec tukaj.
Ampak, če to traja le 1 korak, kako v svet sem mogel trditi, da je seznam
so razporejene, ker če sem dovoljena le vzeti 1 korak, koliko elementov
Jaz bi dejansko, da preverite?
No, samo 1, kar pomeni, da je n minus 1 elemente, ki bi lahko iz
Da, in grem na veri po gledaš 1 element, ki
stvar je razvrščena.
Torej 1 se ne popravi tukaj.
Torej minimalno, koliko moram gledati?
>> [Interposing GLAS]
>> DAVID J. Malan: n minus 1, ali res, n, ker moram gledati na vsak
element, se prepričajte, da to ni v okvari.
Ampak še enkrat, bomo nekako val našega roke pri manjših številkah in
predvidevamo, da, kot je n postane velika, oni nezanimiv vseeno.
Tako da je mehurček vrste.
In zdaj, kaj je naredil zadnji dve.
Izbor vrste, nato pa se bomo storiti vstavljanja vrste.
In potem bomo odpihnil um z nekaj veliko
boljši od vseh teh.
Vse je v redu.
>> Kaj je v najslabšem primeru teče čas izbirnem vrste?
>> ZVOČNIK 4: n kvadrat.
>> DAVID J. Malan: n kvadrat, slišim.
Ampak zakaj n kvadrat, intuitivno?
>> ZVOČNIK 4: Ker smo pravkar storil.
>> DAVID J. Malan: Ker smo pravkar storil.
OK.
Dober odgovor.
Vendar intuitivno, zakaj je izbor sortiranje n kvadrat?
Kaj moramo storiti znova in znova?
Sva, da skeniranje skozi, se si najmanjši, ste
najmanjših, ste najmanjša.
In odobri, da smo sposobni sprejeti n koraki, potem je n minus 1, potem je n minus 2.
Ampak, če ste nekako Seątejte vse, ali ga vzamete na veri, da sem dodal
jih je predhodno, dobimo približno n kvadrat minus nekaterih manjših številk.
Torej bom poklical to n kvadrat.
Ampak z izbiro vrste v najboljši primer, koliko korakov je
da me bodo?
>> ZVOČNIK 5: [neslišno]
>> DAVID J. Malan: To je žal še n kvadrat, kajne?
Ker če sem izbiro najmanjši element, in smo imeli sedem ljudi tukaj,
Vem le, ko pridem do zelo Konec, ki sem ugotovila, najmanjši
Številka, kjer je on ali ona bi lahko bilo.
Ampak kako se mi zdi naslednja Najmanjše število?
Moram narediti novo sredino.
Torej, v najboljšem primeru, kar je vhod za izbiro vrste?
To je že seznam sort, številka ena, Številka dve, številka tri, številka štiri.
Ampak jaz sem računalnik.
Jaz lahko ogledate le na eni stvar naenkrat.
Ne morem se nekako stopijo korak nazaj, kot človek in pravi,
Ooh, to izgleda pravilna.
>> Ne morem odločati le v pravilnost Izbor razvrsti po izbiri
Najmanjše število.
A tudi če se mi zdi številka ena prvič, če ne vem kaj o
druge številke, ki jih jaz ne, vse sem vem, da sem dobil niz
ali niz vrat za katere številke, edini način, vem, da je eden
je najmanjša?
Če dobim vso pot sem in zavedaš, Prekleto, eden je bil res najmanjši.
>> Ampak kako naj potem ugotovijo, da dve je naslednji najmanjši?
Ki jih počne isto neučinkovitost znova in znova.
Torej, končno, z vstavljanja vrste, kako, v najslabšem primeru,
smo rekli, da opravlja?
To je preveč n kvadrat.
In kako približno pri najboljšem primeru?
Bomo pustite, da se kot Cliffhanger.
Bomo izpolnite v tem praznem naslednjem trenutku, ampak najprej naj vam predlagam, da
bistveno boljši od vsi ti, v redu?
>> Torej mislite sami, kaj vstavljanje vrsta se bo.
No, to ni bilo preveč dramatično, ker sem edini
da je videl spremembo.
Wow.
OK.
Torej, tukaj imamo nekoliko drugačna predstavitev.
Če sem povečate tukaj, boste videli, da je na Na levi strani imamo mehurček vrste, pri
srednji imamo izbiro vrste in na skrajni desni, imamo nekaj smo
niso pogledal še imenovano zlivanjem.
Vendar menijo, kar smo bili tukaj doslej še danes.
Ko Jennifer prvič prišel na oder, smo šli skozi niz številk
znova in znova, z linearno iskanje, in imamo linearni čas teče, veliki O
n, tako rekoč.
>> Ko si zdaj prvi teden razred, ko smo imeli deli in vladaj,
in smo imeli telefonski imenik solzenje, in Jennifer, in smo skupaj
spodbudil, da ključni uvid, ki je bil znova in znova se ga
nekako vrže proč, metali proč, metanje stran, polovica problem, ali
na splošno, tako težave na pol, in nato z obdelavo manjši del
problem kot konceptualno enakovredni na drugi strani pa smo nekako pa
bistveno bolje.
Ampak s mehurčkov vrste, z izbiro vrste, z vstavljanja vrste, smo lahko smo
nobena takšna spoznanja, da Jennifer ni.
Imamo precej preprosto hodil nazaj in tja cel kup časa in mi
uglasili stvari malo, menjava v tem vrstnem redu, morda
vstavljanje ali izbiro.
Toda na koncu dneva, sem veliko v nerodni hoji naprej in nazaj.
Mi ni res vzvoda nekaj pameten kot Jennifer maral tako
in osvajanje.
>> Torej zlivanjem, nasprotno, kar smo ne bomo videli do naslednjega tedna, da se dogaja
vzvoda, da je ključna ideja z deljenjem vnos in nato razpolovi, nato
prepolovili, nato pa razpolovi.
In na vsaki ponovitvi te zanke, sortiranje levo polovico, in prav
pol, nato levo polovico levi polovici in desno polovico levi, nato
levi polovici desni polovici in desni polovici desni polovici.
In spet in spet ponavlja.
>> Torej boste to videli vizualno, vendar to je tisto, kar nas čaka naslednji teden.
In na splošno, ko mislimo, da malo malo težje od takšnih težav.
Smo n kvadrat na levi strani, n kvadrat v sredini in n
log n na desni strani.
Torej je tvoj pravi Alpinista.
Se vidimo v ponedeljek.
>> [APLAVZ]