>> [Muzikos grojimo]
>> PROFESORIUS: Visos dešinę.
Tai yra, ir tai yra CS50 savaitę nuo trijų pabaigos.
Taigi mes čia šiandien, o ne Sanders Teatras, o ne į WEIDNER bibliotekoje.
Kurio viduje yra studija žinomas kaip Hauser Studio,
arba sakome Studio H, arba mes say-- Jei jums patiko šį juokelį,
tai tikrai iš klasiokas, ženklas, internete,
kuris pasiūlė kiek per "Twitter".
Dabar kas kietas apie kad čia studijoje
yra tai, kad aš apsupta tai žalia sienos, žalia ekranas arba chromakey,
taip sakant, tai reiškia, kad CS50 s gamybos komanda, nežinant mane
dabar, gali būti išleisti man dauguma visame pasaulyje,
geriau ar blogiau.
>> Dabar, kas laukia priekyje, problema nustatyti du yra jūsų rankose šią savaitę,
bet su problema nustatyti tris šių metų savaitę
Jums bus užginčyti su vadinamasis žaidimas 15
senas šalis palankumą, kad jums gali prisiminti gavimo
kaip vaikas, kad turi visa krūva skaičių, kad gali skaidrę aukštyn, žemyn,
kairę ir į dešinę, ir ten vienas tarpas per galvosūkį, į kurį
iš tikrųjų galite skaidrę tuos įspūdį.
Galų gale jūs gaunate tai dėlionės kai pusiau atsitiktine tvarka,
ir tikslas yra rūšiuoti, iš viršaus į apačią,
kairės į dešinę, iš vienos visą kelią iki per 15.
>> Deja, įgyvendinimas jūs turėsite po ranka
bus programinė įranga pagrindu, ne fiziškai.
Jūs iš tikrųjų teks rašyti kodas, su kuriuo studentas arba vartotojas gali
žaisti 15 rungtynes.
Ir iš tikrųjų, hakeris leidimas žaidimas 15
jums bus iššūkis įgyvendinti, ne tik Šio seno mokykloje vienodos
žaidimas, bet veikiau sprendimas jo, įgyvendinant Dievo režimas,
taip sakant, kad iš tikrųjų išsprendžia galvosūkį už žmogaus,
suteikiant jiems užuomina, po užuominą, po užuominą.
Taigi daugiau apie tai kitą savaitę.
Bet tai, kas laukia priekyje.
>> Nes dabar priminti, kad anksčiau šią savaitę mes turėjome šį Įspūdingos filmą, jei norite,
kuriuo geriausia, ką veikėte rūšiavimas Išminčius buvo viršutinė riba didelis O n
kvadrato.
Kitaip tariant, burbulas rūšiuoti, pasirinkimas rūšiuoti, įterpimo rūšiuoti,
visi iš jų, tuo tarpu skirtingi jų įgyvendinimą,
perduotos į n kvadratu veikia Laikas labai blogiausiu atveju.
Ir mes paprastai manome, kad labai blogiausiu atveju rūšiavimo
yra vienas, kad jūsų indėlis yra visiškai atgal.
Ir iš tiesų, jis paėmė nemažai priemonių, įgyvendinti kiekviena iš šių algoritmo.
>> Dabar pačioje pabaigoje klasės Prisiminkite, mes palyginti burbulas rūšiuoti
prieš atrankos rūšiuoti prieš vieną kitą kad mes vadinami suliejimo rūšiuoti tuo metu,
ir siūlau, kad tai atsižvelgiant privalumas nuo savaitės pamoką
nulis, skaldyk ir valdyk.
Ir kažkaip pasiekti tam tikrą rūšį logaritminė bėgančio laiko, galiausiai,
vietoj kažką tai grynai kvadratinė.
Ir tai ne visai logaritminė, tai šiek tiek daugiau nei tai.
Bet jei jūs prisimenate iš klasės, tai buvo daug, daug greičiau.
Leiskite pažvelgti, kur mes baigėte išvaizdą.
>> Burbulas rūšiuoti, palyginti atrankos Rūšiuoti palyginti merge rūšiuoti.
Dabar jie visi veikia, yra teorija, tuo pačiu metu.
CPU veikia tuo pačiu greičiu.
Bet jūs galite pajusti, kaip nuobodu tai labai greitai taps,
ir tiesiog, kaip greitai, kai mes švirkšti visą savaitę Zero algoritmų tiek,
mes galime pagreitinti.
>> Taigi ženklas Rūšiuoti atrodo nuostabi.
Kaip mes galime išnaudoti jį, kad greičiau rūšiuoti numerius.
Na pagalvokime atgal komponentui, kad mes
turėjo grįžti į nulinę savaitę, kad ieškoti ką nors į telefonų knygą,
ir priminti, kad Pseudocode, kad mes pasiūlėme,
per kurį mes galime rasti kažkas panašaus Mike Smith,
atrodė šiek tiek kažką panašaus į tai.
>> Dabar imtis ypač išvaizdą eilutėje 7 ir 8, ir 10 ir 11,
kurios sukelia tą kilpą, kurią mes nuolat grįžta į liniją 3 vėl, ir vėl,
ir vėl.
Tačiau paaiškėja, kad mes galime pamatyti Šis algoritmas, čia Pseudocode,
šiek tiek daugiau holistiškai.
Tiesą sakant, tai, ką aš ieškote bent čia ekrane,
yra paieškai algoritmas Mike Smith tarp kai kurių puslapių rinkiniu.
Ir iš tiesų, mes galime supaprastinti šį algoritmas tose 7 ir 8 linijų,
ir 10 ir 11, tiesiog pasakyti, kad tai, kurios aš čia pateikiama geltonai.
Kitaip tariant, jei Mike Smith anksčiau knygoje,
mums nereikia nurodyti žingsnis po žingsnio, dabar, kaip eiti jo rasti.
Neturime nurodyti grįžti į liniją 3
Kodėl ne mes tiesiog vietoj to, tarkim, apskritai,
ieškoti Mike į kairė pusė knygos.
>> Ir atvirkščiai, jei Mike iš tikrųjų vėliau knygoje,
kodėl ne mes tiesiog pacituoti citatos pabaiga paiešką Mike dešinėje pusėje knygoje.
Kitaip tariant, tai kodėl gi ne mes tiesiog rūšiuoti punt sau sakydamas:
ieškoti Mike šiame poaibis knygos,
ir palikite jį į mūsų esamų algoritmas pasakykite mums
Kaip ieškoti mike kad kairė pusė knygos.
Kitaip tariant, mūsų algoritmas veikia, ar tai
telefono knyga tokio storio, tai storis, arba bet kokio storio kokia.
Taigi, mes galime rekursyviai apibrėžti šį algoritmą.
Kitaip tariant, dėl ekranas čia yra algoritmas
paieškai Mike Smith tarp telefono knygos puslapiuose.
Taigi 7 ir 10 eilutė, tegul tiesiog pasakyti būtent tai.
Ir aš naudoju šį terminą akimirkai Prieš ir iš tiesų, rekursija
yra madingas terminas dabar, ir tai šis procesas
daro kažką cikliško iki kažkaip naudojant kodą, kurį jūs jau turite,
ir raginama jį dar kartą, ir vėl, ir vėl.
Dabar jis ketina būti svarbi kad mes kažkaip apačioje
užduotis, ir nereikia daryti, kad be galo ilgai.
Priešingu atveju mes ketiname iš tikrųjų begalinis ciklas.
Bet pažiūrėkime, ar mes galime skolintis šią idėją iš rekursijos, daro kažką naujo
ir vėl, ir vėl, spręsti rūšiavimo problema per suliejimo
Rūšiuoti, visi efektyviau.
>> Taigi, aš suteikti jums sujungti rūšiuoti.
Leiskite pažvelgti.
Taigi čia yra Pseudocode, su kuris galėtume įgyvendinti rūšiavimo,
naudojant šį algoritmą, pavadintą sujungti rūšiuoti.
Ir tai paprasčiausiai tai.
Apie įvesties n elementų, Kitaip tariant, jei esate
suteikta n elementai ir numeriai bei laiškus ar kokia įvestis,
jei jums suteikta n elementų, jei n yra mažiau nei 2, tiesiog grįžti.
Teisė?
Nes jei n yra mažiau nei 2, kad tai reiškia, kad mano sąrašas elementų
yra arba dydžio 0 arba 1, ir tiek iš tų nereikšmingų atvejų,
sąrašas jau rūšiuojamos.
Jei nėra sąraše, tai rūšiuojamos.
Ir jei ten ilgio sąrašas 1, tai akivaizdžiai rūšiuojami.
Taigi algoritmas turi tik tikrai padaryti kažką įdomaus,
jei mes turime du ar daugiau elementai mums duota.
Taigi pažvelkime į magijos tada.
Kita rūšiuoti kairįjį pusę elementų, tada rūšiuoti tinkamą pusę elementų,
tada sujungti surūšiuoti puses.
Ir kas rūšies proto lenkimo čia yra, kad aš tikrai ne
Atrodo, kad jums sakiau, nieko nėra, tiesa?
Viskas, ką aš sakiau yra, nes iš sąrašo n elementų, rūšiuoti yra kairėje pusėje,
tada į dešinę pusę, tada sujungti rūšiuoti puses,
Bet kur yra tikrasis slaptą padažu?
Kur yra algoritmas?
Na paaiškėja, kad šių dviejų linijų Pirma, tarsi liko pusė elementų,
ir rūšiuoti teisę pusė elementų, yra pasikartojantys skambučiai, taip sakant.
>> Galų gale, ne tai momentas, turiu
algoritmas, su kuria rūšiuoti visa krūva elementų?
Taip.
Tai čia.
Tai čia ekrane ir todėl galiu naudoti tą patį rinkinį žingsnių
rūšiuoti yra kairėje pusėje, kaip aš galiu teisė pusę.
Ir iš tiesų, vėl, ir vėl.
Taigi vienaip ar kitaip, ir mes netrukus pamatyti tai, apie merge rūšiuoti magija
yra įdėta, kad labai galutinis linija, sujungti surūšiuoti puses.
Ir tai atrodo gana intuityvus.
Jūs imtis dvi dalis, ir jūs, kažkaip, sujungti juos kartu,
ir mes pamatyti, tai konkrečiai per akimirką.
>> Tačiau tai yra pilnas algoritmas.
Ir pažiūrėkime tiksliai, kodėl.
Na manau, kad mes Atsižvelgiant į šiuos pats aštuonios čia elementus ekrane, vienas
per aštuonių, bet jie iš pažiūros atsitiktine tvarka.
Ir po ranka tikslas rūšiuoti šiuos elementus.
Na kaip aš galiu eiti apie daro jį naudoti, vėlgi,
sujungti rūšiuoti, kaip už šio Pseudocode?
Ir vėl, Įsitvirtino tai jūsų protas, nes tik akimirką.
Pirmasis atvejis yra gana trivialus, jei ji mažesnė kaip 2,
tiesiog grįžti, nėra nuveikti.
Taigi tikrai ten tik trys žingsnių, kad tikrai reikia nepamiršti.
Vėlgi, ir vėl, aš ketinate nori turėti
rūšiuoti yra kairėje pusėje, rūšiuoti tinkamą pusę,
ir tada, kai jų dvi puselės yra rūšiuojami,
Noriu sujungti juos kartu į vieną rūšiuotų sąrašą.
Taigi keep that in mind.
>> Taigi čia originalus sąrašą.
Leiskite gydyti tai kaip masyvas, kaip mes pradėjome
dviejose savaitę, kuris yra ribotis blokas atminties.
Šiuo atveju, kurių sudėtyje yra aštuoni numeriai, atgal atgal į nugarą.
Ir tegul dabar taikomos suliejimo rūšiuoti.
Taigi aš pirmą norite rūšiuoti kairė pusė šio sąrašo,
Ir tegul, todėl sutelkti dėmesį į 4, 8, 6 ir 2.
>> Dabar kaip man eiti apie rūšiavimas nuo dydžio 4 sąrašą?
Na aš turiu dabar mano rūšiavimas kairiojo pusmetį kairėje.
Vėlgi, galime atsukti tik už akimirką.
Jei Pseudocode tai, ir aš suteiktas aštuonių elementų,
8 yra akivaizdžiai didesnis nei arba lygus 2.
Taigi su pirmas atvejis netaikomas.
Taigi rūšiuoti aštuonis elementus, aš pirmą kartą rūšiuoti kairįjį pusę elementų,
tada aš rūšiuoti tinkamą pusę, tada aš sujungti du rūšiuotos pusės, kiekvienas iš dydis 4.
GERAI.
>> Bet jei jūs tiesiog man pasakė, rūšiuoti kairėje pusėje,, kuris yra dabar dydžio 4,
Kaip rūšiuoti kairįjį pusę?
Na, jei aš turėti įėjimas iš keturių elementų,
Aš rikiuoti į kairę du, tada dešiniuoju du,
ir tada aš juos sujungti kartu.
Taigi dar kartą, ji tampa šiek tiek iš proto lenkimo žaidimą čia
nes jūs, tipo, turi prisiminti, kur jūs esate į istoriją,
bet tuo dienos pabaigoje, suteiktas joks elementų skaičių,
pirmiausia noriu rūšiuoti kairė pusė, tada į dešinę pusę,
tada sujungti juos kartu.
Pradėkime daryti būtent tai.
Štai aštuoni elementų įvestis.
Dabar mes ieškome kairėje pusėje čia.
Kaip rūšiuoti keturis elementus?
Na aš rikiuoti yra kairėje pusėje.
Dabar kaip man sutvarkyti kairįjį pusę?
Na aš buvo suteikta du elementus.
Taigi leiskite surūšiuoti šių dviejų elementų.
2 yra didesnis arba lygus 2, žinoma.
Taigi, kad pirmas atvejis netaikomas.
>> Taigi dabar aš turiu rūšiuoti į kairę pusė šių dviejų elementų.
Kairėje pusė, žinoma, yra tik 4.
Taigi, kaip man sutvarkyti iš vieno elemento sąrašą?
Na, dabar, kad ypatingas bazinį scenarijų iki viršaus, taip sakant, taikoma.
1 yra mažiau nei 2, ir savo sąrašas yra iš tiesų dydžio 1 d.
Taigi aš tiesiog grįžti.
Aš nieko negaliu daryti.
Ir iš tiesų, pažvelgti, ką aš padaryta, 4 jau rūšiuojamos.
Kaip jau esu dalinai sėkmingas čia.
>> Dabar, atrodo rūšies kvailas reikalauti, bet tai tiesa.
4 yra 1 dydžio sąrašas.
Tai jau rūšiuojamos.
Štai kairė pusė.
Dabar aš rūšiuoti tinkamą pusę.
Mano indėlis yra vienas elementas, 8 Be to, jau rūšiuojamos.
Kvailas, taip pat, tačiau ir vėl, Šis pagrindinis principas
ketina leisti mums dabar statyti ant sėkmingai tai.
4 rūšiuojamos, 8 rūšiuojamos, o dabar kas buvo, kad paskutinis žingsnis?
Taigi, trečiasis ir paskutinis žingsnis, bet kokia kartą jūs rūšiavimo sąrašas, prisiminti,
buvo sujungti dvi puses, kairėje ir dešinėje.
Taigi darykime būtent tai.
Mano kairė pusė, žinoma, 4.
Mano teisė pusė yra 8.
>> Taigi leiskite tai padaryti.
Pirmiausia aš ruošiuosi skirti Kai kurios papildomos atminties,
kad aš atstovauti čia kaip tik antrinis masyvas,
tai pakankamai didelis, kad tilptų tai.
Bet jūs galite įsivaizduoti, išplečiant kad stačiakampis visas ilgis,
jei mums reikia daugiau vėliau.
Kaip man imtis 4 ir 8, ir sujungti šie du sąrašai dydis 1 kartu?
Čia taip pat gana paprasta.
4 ateina pirmas, tada ateina 8.
Nes jei aš noriu rūšiuoti kairė pusė, tada į dešinę pusę,
ir tada sujungti šias dvi puses kartu, išrūšiuotų tam,
4 ateina pirmas, tada ateina 8.
>> Taigi, mes, atrodo, daro pažangą, net nors aš nepadariau jokio faktinio darbą.
Bet atsiminkite, kur mes esame į istoriją.
Mes iš pradžių priėmė aštuonis elementus.
Mes rūšiuojami kairįjį pusę, kuri yra 4.
Tada mes rūšiuojami kairįjį pusę kairiojo pusėje, kuri buvo 2.
Ir čia mes einame.
Mes padaryti su tuo žingsnio.
>> Taigi, jei mes surūšiuoti į kairę pusę 2, dabar mes
turi rūšiuoti tinkamą pusę 2.
Taigi teisė pusė 2 šių dviejų verčių čia, 6 ir 2.
Tad dabar pats imtis iš dydžio indėlį 2, ir rūšiuoti kairįjį pusę, ir tada
teisę pusę, ir tada sujungti juos kartu.
Na kaip man sutvarkyti iš dydį sąrašą 1, kurių sudėtyje yra tik skaičių 6?
Aš jau padaryta.
Šis dydis 1 sąrašas surūšiuotas.
>> Kaip rūšiuoti kitą sąrašą dydis 1, vadinamoji teisė pusę.
Na tai irgi jau rūšiuojamos.
Skaičius 2 yra vieni.
Taigi dabar turiu dvi dalis, į kairę ir Gerai, man reikia jas sujungti kartu.
Leiskite man duoti sau šiek tiek papildomos erdvės.
Ir 2 įdėti ten, tada 6 ten, taip
rūšiavimas šį sąrašą, į kairę ir į dešinę, ir sujungiant jį kartu, galiausiai.
Taigi, aš šiek tiek geresnės formos.
Aš ne padaryta, nes aiškiai 4, 8, 2, 6 nėra galutinė užsakymas, kad aš noriu.
Bet dabar aš turiu du sąrašus 2 dydžio, kad tiek, atitinkamai, rūšiuojami.
Taigi dabar, jei atsukti savo proto akių, kur gi, kad palieka mus?
Aš pradėjau su aštuonių elementų, tada aš sutrumpino jį žemyn į kairę pusę 4,
tada kairėje pusėje, 2, ir tada į dešinę pusę 2,
Aš baigiau todėl, rūšiavimas į kairę pusė 2, ir teisę pusė 2,
Taigi, kas yra trečiasis ir paskutinis žingsnis čia?
Turiu sujungti kartu du sąrašus 2 dydžio.
Taigi eikime į priekį.
Ir ekrane čia parašęs man kai papildoma atmintis,
nors techniškai, pastebėsite, kad aš turiu visa krūva tuščioje vietoje iki viršaus
ten.
Jei aš noriu būti ypač efektyvus plotas išmintingi,
Galėčiau tik pradėti judėti elementai pirmyn ir atgal, viršuje ir apačioje.
Bet tik vizualiai aiškumo, Aš ruošiuosi įdėti jį žemyn žemiau,
išlaikyti dalykų gražus ir švarus.
>> Taigi aš turiu du sąrašus 2 dydžio.
Pirmasis sąraše yra 4 ir 8.
Antrasis sąraše yra 2 ir 6.
Leiskite sujungti tuos kartu rūšiuotų tvarka.
2, žinoma, ateina pirma, tada 4, tada 6, tada 8.
Ir dabar mes, atrodo, vis kažkur įdomu.
Dabar aš rūšiuojami pusė sąrašą ir atsitiktinai, tai
visi net numeriai, bet yra, tiesą sakant, tik sutapimas.
Ir dabar aš turiu rūšiuojami į kairę pusė, taip, kad ji yra 2, 4, 6, ir 8.
Nieko tai iš eilės.
Tai jaučiasi pažangą.
>> Dabar jis jaučiasi aš buvo kalbama amžinai dabar
Taigi, kas dar turi būti peržiūrėta, jei tai algoritmas yra, iš tiesų, efektyviau.
Bet mes išgyvena super metodiškai.
Kompiuteris, žinoma, norėčiau tai padaryti, kaip kad.
Taigi, kur mes esame?
Mes pradėjome su aštuonių elementų.
Aš rūšiuojami kairėje pusėje, 4.
Man atrodo, kad reikia padaryti, kad.
Taigi, dabar kitas žingsnis yra rūšiuoti tinkamą pusę 4.
Ir ši dalis mes galime eiti per šiek tiek daugiau
greitai, nors esate Sveiki atsukti arba sustabdyti, tiesiog
manau, per jį savo tempu, bet ką
mes turime dabar yra galimybė padaryti tą patį algoritmą keturiais
su skirtingais numeriais.
>> Taigi eikime į priekį, ir sutelkti dėmesį į teisė pusė, kurią mes čia.
Kairėje pusėje, kad teisė pusę, o dabar
kairėje pusėje, kairėje pusė šios teisės pusę,
ir kaip man sutvarkyti iš dydį sąrašą 1, kuriame yra tik 1 numeriu?
Tai jau padaryta.
Kaip aš galiu padaryti dėl sąrašo pats dydžio 1, kuriame yra tik 7?
Tai jau padaryta.
Trečias žingsnis šiam pusę tada yra sujungti šiuos du elementus
į naują sąrašo 2 dydžio, 1 ir 7.
Ar neatrodo, kad padarėme viską kad daug įdomus darbas.
Pažiūrėkime, kas vyksta šalia.
Aš tik sutvarkyti kairįjį pusę teisė pusė mano originalus indėlis.
Dabar galime rūšiuoti teisę pusė, kuri yra 5 ir 3.
Leiskite dar kartą pažvelgti į kairę pusę, rūšiuojami, teisė pusę, rūšiuojami,
ir sujungti tuos du kartu, į tam tikrą papildomą erdvę,
3 ateina pirmas, tada ateina 5.
Ir todėl dabar, mes surūšiuoti kairėje pusėje, dešinės pusėje
pirminio problemą, ir teisę pusė dešinės pusėje
pirminio problemą.
Kas trečias ir paskutinis žingsnis?
Na sujungti šias dvi puses kartu.
Taigi leiskite man gauti sau kai papildomos vietos, bet, vėlgi, aš
gali būti naudoti, kad atsarginį kosmoso iki viršaus.
Tačiau mes ketiname išlaikyti paprasta vizualiai.
Leiskite sujungti dabar 1 ir tada 3, ir tada 5, ir tada 7.
Paliekant man dabar su teisė pusė originalo problemos
kad manimi puikiai rūšiuojami.
>> Taigi, kas lieka?
Aš jaučiuosi kaip aš nuolat sakydamas, kad tie patys dalykai vėl, ir vėl,
bet tai neparodo Faktas, kad mes naudojame rekursija.
Iš naudojate procesas algoritmas vėl, ir vėl,
mažesnių pogrupių originalus problema.
Taigi dabar aš turiu iš kairės rūšiuojami pusė pradinio problemą.
Turiu teisę rūšiuotą pusę pirminio problemą.
Kas trečias ir paskutinis žingsnis?
Oi, tai sujungti.
Taigi leiskite tai padaryti.
Leiskite skirti kai papildoma atminties, bet mano Dieve, mes
gali jį visur dabar.
Mes turime tiek daug laisvos vietos pas mus, bet mes keep it simple.
Vietoj grįžta ir atgal su mūsų originalios atminties,
tegul tiesiog padaryk tai vizualiai žemyn čia žemiau,
baigti iki apjungiant kairė pusė ir teisė pusę.
>> Taigi sujungus, ką man reikia daryti?
Noriu imtis elementus tvarka.
Taigi žiūri kairėje pusėje, Matau pirmas skaičius yra 2.
Žiūriu dešinėje pusėje, I žr pirmąjį skaičių
yra 1, taigi akivaizdu, kad, kuri Taškų aš noriu išplėšti,
ir įdėti pirmasis mano galutinį sąrašą?
Žinoma, 1.
Dabar aš noriu paprašyti, kad tą patį klausimą.
Kairėje pusėje, aš vis dar turiu 2 numeriu.
Dešinėje pusėje, Aš turiu 3 numeriu.
Kuris aš noriu pasirinkti?
Žinoma, numeris 2 dabar pastebėti kandidatus
yra 4 kairėje, 3 dešinėje.
Leiskite, žinoma, pasirinkti 3.
Dabar kandidatai yra 4 dėl kairysis, 5 dešinėje.
Mes, žinoma, pasirinkti 4.
6 kairėje, 5 dešinėje.
Mes, žinoma, pasirinkti 5.
6 kairėje, 7 dešinėje.
Renkamės 6, ir tada mes pasirinkti 7, ir tada mes renkamės 8.
Voila.
>> Taigi didžiulis skaičius tariant vėliau, mes surūšiuoti šį aštuonių elementų sąrašą
į vieną sąrašą per aštuonių, kad manimi didėja su kiekvienu žingsniu,
bet kiek laiko darė tai užtruks mums tai padaryti.
Na aš sąmoningai laid dalykų iš pavaizduotomis piktogramo-
čia, kad galėtume rūšies matyti ar vertiname padalinį
užkariauti kad buvo vyksta.
>> Iš tiesų, jei jūs atsigręžti į tinklą, Aš paliktas visų šių punktyrinėmis linijomis
įdiegtos turėtojų, galite, rūšies, žr atvirkštine tvarka,
jei rūšies atsigręžti į istorija, dabar, mano originalus sąrašas
yra, žinoma, dydžio 8 d.
Ir tada anksčiau buvau susiduriame su dviem sąrašus dydis 4,
ir tada keturi sąrašai dydis 2, ir tada aštuoni sąrašai dydis 1 d.
>> Taigi, kas tai daro, rūšies, priminti jums?
Na, iš tiesų, bet algoritmai mes
pažvelgė šiol, kur mes skaldyk ir skaldyk ir atskirties,
susilaukia dalykų ir vėl vėl atsiranda šiame bendrą idėją.
Ir taip yra kažkas logaritminė vyksta čia.
Ir tai ne visai žurnalas n, bet ten logaritminis komponentas
kas mes ką tik padaryti.
>> Dabar aptarkime, kaip kad iš tikrųjų yra.
Taigi prisijunkite n, vėl buvo puikus veikimo laikas,
kai mes padarėme kažką panašaus dvejetainis paieškos, kaip mes dabar vadiname,
skaldyk ir valdyk strategija per kurį mes nustatėme, Mike Smith.
Dabar techniškai.
Štai žurnalas bazė 2 n, net nors daugeliu matematikos klases,
10 dažniausiai bazinė kad jūs prisiimate.
Bet kompiuterių mokslininkai beveik visada galvoti ir kalbėti Kalbant apie pagrindą 2,
todėl mes paprastai tiesiog pasakyti žurnalą n, o ne log bazės 2 n,
bet jie tiksliai vieną ir tą pats į kompiuterį pasaulyje
Mokslas ir kaip panaikinti, ten pastovus veiksnys
skirtumas tarp šių dviejų, todėl inscenizacijos vistiek, daugiau formalių priežasčių.
>> Bet dabar, kas mums rūpi apie tai pavyzdys.
Taigi tegul ne įrodyti, pavyzdžiui, bet ne mažiau naudoti iš numerių pavyzdį
po ranka kaip normalumas patikrinti, jei bus.
Taigi anksčiau formulė buvo Prisijungti bazė 2 n, bet tai, kas yra n ir šiuo atveju.
Aš turėjau n originalius numerius arba 8 originalaus skaičius specialiai.
Dabar ji buvo šiek tiek o, bet aš esu gana
Įsitikinkite, kad žurnalas bazė 2 iš vertės 8 yra 3,
Ir iš tiesų, kas malonu apie tai kad 3 yra tiksliai kartų
kad jūs galite padalinti sąrašą Ilgio 8 vėl, ir vėl,
ir vėl, kol jūs liekate sąrašus tik 1 dydžio.
Teisė?
8 eina iki 4, eina iki 2, eina iki 1, ir kad tai
atspindi būtent tai nuotrauka mes turėjome vos prieš akimirką.
Taigi šiek tiek normalumas patikrinti, kur logaritmas yra faktiškai dalyvauja.
>> Taigi, dabar, ką dar dalyvauja čia? n.
Taigi pastebėti, kad kiekvienas kartą aš padalinti sąrašą
nors atvirkštine tvarka istorijos čia, aš vis dar daro n dalykų.
Tai sujungimo žingsnis reikalaujama, kad Liečiu kiekvieną numerių vieną,
tam, kad jį į skaidrių prireikus jo vieta.
Taigi, nors šis aukštis schema yra matmenų dalelių log n n arba 3,
Konkrečiau, kitaip tariant, Aš tris padalinius čia.
Kiek darbo aš padaryti horizontaliai kartu šios diagramos kiekvieną kartą?
>> Na, aš n žingsnių dirbti, nes jei aš
gavo keturis elementus ir keturis elementus, ir man reikia jas sujungti kartu.
Man reikia eiti per Šie keturi ir jie keturi,
galiausiai sujungti jas Atgal į aštuonias elementais.
Jei atvirkščiai, aš turiu aštuonis pirštus Čionai, kurį aš ne, ir aštuonios
fingers-- sorry-- Jei aš gavo keturis pirštus per čia
kuri man daryti, keturi pirštai Čionai, kuris man daryti,
tada, kad tas pats pavyzdys, kaip ir anksčiau, jei aš
turi aštuonis pirštus nors iš viso, kurį galiu, rūšies, daryti.
Galiu tiksliai padaryti čia tada aš tikrai gali
sujungti visus šiuos sąrašus dydžio 1 kartu.
Bet aš tikrai turime ieškoti kiekvieno elemento tik vieną kartą.
Taigi, šio proceso aukštis yra log n, Šio proceso plotis, taip sakant,
yra n, tai, ką mes, atrodo, turėti, galiausiai, yra
bėgimo laikas dydžio n kartų log n.
>> Kitaip tariant, mes padalintas sąrašas, žurnalas n kartų,
bet kiekvieną kartą mes padarėme, kad mes turėjome paliesti kiekvieną iš elementų vieną
siekiant sujungti juos visi kartu, kuris
buvo n žingsnis, todėl mes turime n kartų log n, arba kaip kompiuteris mokslininkas pasakytų,
asimptotiškai, kuris Būtų didelis žodis
apibūdinti viršutinė laikytis ant važiavimo laikas,
mes veikia dideliame o Rąstų n metu, taip sakant.
>> Dabar tai yra reikšminga, nes prisiminti ką veikia laikai buvo
su burbulas rūšiuoti, ir atrankos Rūšiuoti ir įterpimo rūšiuoti,
ir net keli kiti, kurie egzistuoja, n kvadratu buvo, kai mes buvome.
Ir jūs galite, rūšies, pamatyti tai čia.
Jei n kvadratu yra akivaizdžiai n kartų N, bet čia mes turime n kartų log n,
ir mes jau žinome iš savaitę nuliui, kad žurnalas N, logaritminis,
yra geriau nei kažkas tiesinis.
Galų gale, prisiminti paveikslėlį su raudona ir geltona
ir žalios linijos, kad mes atskleidžianti, tuo žalia logaritminė linija buvo daug mažesnis.
Ir todėl, daug geriau ir greičiau nei tiesios geltonos ir raudonos linijos,
n kartų log n yra, tiesą sakant, geriau nei n kartų, n, arba n kvadrato.
>> Taigi, mes, atrodo, nustatė algoritmą suliejimą
Rūšiuoti kuri veikia daug greičiau laikas, ir iš tiesų,
Štai kodėl, anksčiau šią savaitę, kai Mes matėme, kad tarp burbulas konkursas
Rūšiuoti atranka rūšiuoti, ir sujungti Rūšiuoti, sujungti rūšiuoti tikrai, tikrai laimėjo.
Ir iš tiesų, mes net ne laukti Kramtomoji rūšiuoti ir atrankos rūšiuoti
pabaigti.
>> Dabar galime imtis vieną kitą perdavimo į tai, iš šiek tiek daugiau
formalus požiūris, tik atveju, tai rezonuoja geriau
negu aukštesnio lygio diskusija.
Taigi čia algoritmas dar kartą.
Paklauskime savęs, ką veikia laikas
yra tai algoritmai įvairius veiksmus?
Leiskite padalinti jį į pirmą atveju ir antras atvejis.
IF ir kitur IF atveju, N yra mažiau nei 2, tiesiog grįžti.
Jaučia pastovaus laiko.
Tai, tipo, kaip ir dviejų pakopų, N yra mažiau nei 2, tada grįžti.
Bet kaip mes sakėme, pirmadienį, pastovus laikas, arba didelis O 1,
gali būti du žingsniai, trys žingsniai, net 1000 žingsnių.
Svarbu yra tai, kad pastovus skaičius žingsnius.
Taigi geltona pabrėžė Pseudocode čia veikia, mes jį vadiname,
pastovus laikas.
Taigi daugiau formaliai, ir mes ketiname to-- tai
bus kiek mes formalizuoti šią teisę now-- T n,
važiavimo laikas problema kad mano n septyniasdešimties kaip įvestį,
lygus didelis O vienas, N yra mažiau nei 2.
Taigi, tai sąlyga, kad.
Taigi, norint būti aišku, n yra mažiau nei 2, mes turime labai trumpą sąrašą, tada
filmo laikas, "T" n, kur n yra 1 arba 0, tai labai konkrečiu atveju,
tai tiesiog bus pastovus laikas.
Ji ketina imtis vieną dėti du žingsnius, nesvarbu.
Tai fiksuotas skaičius žingsnius.
>> Taigi sultinga dalis turi tikrai būti kitas atvejis Pseudocode.
Else atveju.
Rūšiuoti kairė pusė elementų, rūšiuoti teisė pusė elementų, sujungti surūšiuotas puses.
Kiek kiekviena iš šių žingsnių imtis?
Na, jei veikia laikas rūšiuoti n elementų
yra, tegul jį vadina labai bendrine, T n,
tada rūšiavimas į kairę pusė iš elementų,
yra, tipo, tarsi sakydamas, T n skirstomos 2,
ir panašiai rūšiavimo tinkamą pusę elementų yra, tipo, tarsi sakydamas,
T n padalintas 2, ir tada Sujungiant surūšiuotus puses.
Na, jei aš turiu kai skaičius elementų čia
kaip keturi, ir šiek tiek skaičių elementų čia, kaip ir keturių,
ir aš turiu sujungti kiekvieną iš šių keturių į, ir kiekvienas iš jų keturi, vieną
po kito, taip, kad galiausiai turiu aštuonis elementus.
Atrodo, kad tai didelis O n žingsnių?
Jei aš turiu n pirštus ir kiekviena iš jiems turi būti sujungtos į vietą,
tai kaip dar n žingsnių.
>> Taigi iš tiesų formulaically, galime išreikšti tai,
nors truputį scarily per pirmąjį žvilgsnis, bet tai yra kažkas,
kuri fiksuoja tiksliai tą logiką.
Judamasis laikas, T n JEI N yra didesnis arba lygus 2.
Šiuo atveju, kad ELSE atveju, yra T n padalintas iš 2, plius t n padalytą iš 2,
plius Didelės O n, kai linijinis pakopų skaičius,
gal lygiai n, gal 2 kartus N, bet tai maždaug, kad n.
Taigi, kad per daug, tai, kaip mes galime išreikšti tai formulaically.
Dabar jūs nežinote, nebent Jūs įrašyti jį į savo protą,
ar ieškoti jį į atgal vadovėlis, kad
gali turėti šiek tiek Cheat sheet pabaigoje
bet tai, žinoma, ketina Duok mums O n log n didelis,
nes pasikartojimo, kad jūs matote čia ekrane,
jei iš tikrųjų jį, su begalinis skaičius pavyzdžių,
ar tu ją formulaically, darytumėte matyti, kad tai, nes šią formulę
savaime yra grįžtamojo su t n per kažką dešinėje,
ir t n kairės, tai gali iš tikrųjų būti išreikštas, galiausiai,
tokie dideli Go n log n.
Jei nėra įsitikinęs, kad tai gerai dabar, tik
imtis tikėjimo, kad tai, tiesą sakant, ką, kad pasikartos, veda į,
tačiau tai yra tik šiek tiek daugiau matematinis metodas ieškote
tuo veikimo laikas merge rūšiuoti remiantis jos Pseudocode vieni.
>> Dabar galime imtis šiek tiek gurkšnis iš visų, kad
ir pažvelgti į išvaizdą tikras buvęs senatorius, kuris
gali atrodyti šiek tiek pažįstamas, kuris atsisėdo su "Google" Eric
Schmidt prieš kurį laiką, interviu scenoje, priešais visa krūva
žmonių, kalbėti apie galiausiai tema, tai gana dabar pažįstamas.
Leiskite pažvelgti.
>> Ericas Schmidtas: Dabar senatorius, esate čia Google,
ir man patinka galvoti apie Pirmininkaujanti kaip darbo interviu.
Dabar sunku gauti darbą, kaip prezidentas.
Prezidentas B. Obama: Dešiniuoju.
Ericas Schmidtas: Ir jūs ketina daryti [nesigirdi] dabar.
Taip pat sunku gauti darbą "Google".
Prezidentas B. Obama: Dešiniuoju.
>> Ericas Schmidtas: "Mes turime klausimų, ir mes prašome mūsų kandidatų klausimus,
ir tai vienas iš Larry Schwimmer.
>> Prezidentas B. Obama: "Gerai".
>> Ericas Schmidtas: Kas?
Jūs manote, aš nejuokauju?
Tai čia.
Kas yra efektyviausias būdas rūšiuoti milijoną 32 bitų sveikųjų skaičių?
>> Prezidentas B. Obama: Well--
Ericas Schmidtas: Kartais gal aš atsiprašau, maybe--
Prezidentas B. Obama: Ne, ne, ne, ne, ne, aš think--
Ericas Schmidtas: Tai ne it--
Prezidentas B. Obama: "Aš manau, manau burbulas
Rūšiuoti būtų neteisingas būdas eiti.
Ericas Schmidtas: Nagi.
Kas jam šį pasakė?
GERAI.
Aš ne informatikos on--
>> Prezidentas B. Obama: mes gavo mūsų šnipai ten.
PROFESORIUS: Visos dešinę.
Palikime už mus dabar Teorinis pasaulis algoritmai
į asimptotinėje analizės dalį, ir grįžti į kai kurias temas
nuo nulio ir vieną savaitę, ir pradžios pašalinti keletą mokymo ratus,
jei bus.
Taigi, kad jūs tikrai suprasti, galiausiai iš žemės, kas
vyksta po kapotu, kai jūs rašyti, kaupti, ir vykdyti programas.
Prisiminkite, ypač, kad tai buvo pirmasis C programa, mes pažvelgė,
kanoniniu, paprasta programa nekaip, santykinai kalbant,
kurioje jis spausdina, Hello World ".
Ir prisiminti, kad pasakiau, kad procesas kad kodo eina per
yra būtent tai.
Jūs imtis savo kodą, perduoti tai per sudarytojas, kaip klingsėti,
ir iš ateina objekto kodą, kad gali atrodyti taip, nulių ir
kad kompiuterio procesoriaus, centrinis apdorojimo blokas arba smegenų,
galiausiai supranta.
>> Pasirodo, kad tai yra tiek kaip supaprastinimas,
kad mes dabar yra pozicija erzinti išskyrus
suprasti, kas iš tikrųjų buvo vyksta po kapotu
kiekvieną kartą paleidus Klingsėti, arba apskritai,
kiekvieną kartą jums padaryti programą, naudojant Padaryti CF 50 IDE.
Visų pirma, stuff like tai visų pirma būtų sukuriami,
kai pirmą kartą sudaryti savo programą.
Kitaip tariant, kai jūs imtis savo kodą
ir kaupia jį, o kas pirmas yra išvedamas pagal klingsėti
yra kažkas žinomas kaip surinkimo kodą.
Ir iš tiesų, atrodo lygiai taip pat kaip tai.
>> Išbėgau komandą ne komandinės eilutės anksčiau.
Klingsėti Dash sostinės s hello.c, ir tai sukūrė failą
man vadinamų hello.s, kurio viduje buvo lygiai
Šie turinį ir šiek tiek daugiau aukščiau, ir šiek tiek daugiau žemiau,
bet aš įdėti Juiciest informacijos rasite čia ekrane.
Ir jei atidžiai, pamatysite bent keli pažįstami raktažodžius.
Mes turime Pagrindinis viršuje.
Mes printf žemyn viduryje.
Ir mes taip pat turime hello world Backslash n citatos apačioje.
>> Ir visa kita čia yra labai žemo lygio instrukcijos
kad kompiuterio procesorius supranta.
CPU instrukcijos, kad juda atminties aplink, kad apkrovos įsipareigojimų iš atminties,
ir galiausiai, spausdinti dalykų ekrane.
Dabar, kas atsitinka, nors po ši asamblėja kodas generuojamas?
Galų gale, jūs, žinoma, vis dar generuoja objekto kodą.
Bet žingsniai, kurie turi tikrai vyksta po kapotu
atrodo šiek tiek daugiau, kaip šis.
Šaltinis kodas tampa surinkimo kodas, kuris tada tampa objekto kodas,
ir rezoliucinė žodžiai čia yra, kad kai jūs surinkti savo kodą,
iš ateina surinkimo kodą ir kai jūs surinkti savo surinkimo kodą
iš ateina objekto kodą.
>> Dabar klingsėti yra super sudėtingas, tarsi sudarytojų daug,
ir ji visus šiuos veiksmus kartu, ir tai nereiškia, kad
išvesties bet koks tarpinis failai, jūs netgi galite pamatyti.
Jis tiesiog kaupia daiktus, kuris yra bendras terminas, kad
apibūdina visą šį procesą.
Bet jei jūs tikrai norite būti ypač ten
daug ten vyksta taip pat.
>> Bet tegul taip pat mano, kad dabar, net kad super paprasta programa, hello.c,
vadinama funkcija.
Ji paragino printf.
Bet aš ne rašyti printf, tiesą sakant, kuris ateina su C, taip sakant.
Tai funkcija Prisiminkite, kad tai paskelbta standartinio io.h, kuris
yra antraštės failas, kuris yra tema mes iš tikrųjų
pasinerti į daugiau gylio prieš ilgas.
Bet antraštės failas yra paprastai lydi
pagal kodą failą, kodo failą, panašiai kaip egzistuoja standartinės io.h.
>> Kažkada seniai, kažkas, ar kažkam, taip pat rašė
failas vadinamas standartiniu io.c, į kurių faktinė apibrėžimai,
arba realizacijos printf, ir kekių kitų funkcijų,
iš tikrųjų yra parašyta.
Taigi atsižvelgiant į tai, jei mes manome, turintys čia kairėje, hello.c, kad kai
parengta, suteikia mums hello.s, net jei Klingsėti nesivargina taupymo vietoje
galime matyti, ir kad surinkimo kodas gauna surinkti į hello.o, kuris
yra, iš tiesų, numatytasis pavadinimas teikiama, kai jūs surinkti šaltinį
kodą į objektiniu kodu, bet nėra visai pasirengę jį vykdyti dar,
nes dar vienas žingsnis turi atsitikti, ir turi
buvo daroma per pastaruosius keletą savaites, galbūt nežinant jums.
>> Tiksliau kažkur į CS50 IDE, ir tai,
taip pat, bus kraštui tiek supaprastinimas akimirką,
yra arba buvo ant metu, failas vadinamas standartiniu io.c,
kad kažkas surinkti į standartiniai io.s arba lygiaverčiai,
kad kažkas tada surinkti į standartinį io.o,
arba paaiškėja iš jo šiek tiek skiriasi failą
formatas, kuris gali turėti skirtingas Rinkmenos plėtinys apskritai,
bet teoriškai ir konceptualiai, tiksliai tie žingsniai turėjo įvykti tam tikra forma.
Kuris yra pasakyti, kad dabar kai aš rašau programą,
hello.c, kad tiesiog sako, hello world, ir aš naudoju kažkieno kodą
kaip printf, kuris buvo kadaise laikas, faile vadinamas standartinis io.c,
tada kažkaip turiu imtis savo objekto kodas, mano nulių ir,
ir kad asmens objektas kodą arba nulių ir,
ir kažkaip susieti juos kartu į Vienas galutinis failas, vadinamas labas, kad
turi visas nulio ir tie iš mano pagrindinės funkcijos,
ir visi nulio ir tie, printf.
>> Ir iš tiesų, tai paskutinis procesas vadinamas, susiejimas savo objektą kodą.
Įtaisas, kurio išėjimas yra vykdomąjį failą.
Taigi sąžiningumo, ne pabaigoje dieną, nieko
pasikeitė nuo savaitės viena, kai mes pirmą kartą pradėjo sudarant programas.
Iš tiesų, visa tai buvo vyksta po gaubtu,
bet dabar mes tokioje padėtyje, kur mes galime iš tikrųjų
erzinti, išskyrus šiuos įvairius veiksmus.
Ir iš tikrųjų, pabaigoje dienos, mes vis dar
liko nulių ir, kurie yra tikrai puikus Segue dabar
į kitą C galimybes, kad mes neturėjome sverto greičiausiai
iki šiol žinoma kaip Bitinis operatorių.
Kitaip tariant, iki šiol, bet kuriuo metu, mes nagrinėjami duomenų C arba kintamųjų C,
mes jau tokius dalykus kaip simbolių ir plūdės ir moduliai
ir ilgisi ir dviviečiai ir pan, bet visi iš jų yra bent aštuonis bitai.
Mes niekada dar galėjo manipuliuoti atskirus bitus,
nors individualaus tiek, mes žinau, gali atstovauti 0 ir 1.
Dabar paaiškėja, kad C, jums galite gauti prieigą prie atskirų bitų,
jei žinote, sintaksę, su kuria gauti į juos.
>> Taigi leiskite pažvelgti ne Bitinis operatorių.
Taigi nuotraukoje čia yra keletas simboliai mes, tipo, rūšiuoti, matęs.
Matau ampersendo, vertikalus Baras, ir kai kurie kiti, taip pat,
ir prisiminti, kad Ampersand ampersendo yra kažkas, ką mes matėme anksčiau.
Logiška operatorius AND, kur jūs turite du iš jų kartu, arba loginis ARBA
operatorius, kur jūs turi dvi vertikalias juostas.
Bitinis operatorių, kuris mes matyti veikti bitai individualiai,
tiesiog naudoti vieną ampersendo A vieno vertikali juosta, Žymeklis simbolis
ateina kitas, mažai Tilde, tada į kairę
laikiklis paliko laikiklį arba teisė laikiklis teisę laikiklis.
Kiekvienas iš jų turi skirtingas reikšmes.
>> Iš tiesų, tegul pažvelgti.
Vykime senosios mokyklos šiandien ir naudojimas jutiklinis ekranas iš praeities,
žinomas kaip baltos lentos.
Ir tai balta lenta ketina leisti mums
išreikšti keletą gana paprastų simbolius, ar veikiau kai gana paprastas formules,
, kad mes galime tada galiausiai svertas, kad būtų
prieiti prie atskirų bitai per C programa.
Kitaip tariant, galime tai padaryti.
Tegul pirmasis aptarimas dėl momentas apie ženklui,
kuri yra Bitinis operatorius AND.
Kitaip tariant, tai yra operatorius, kuris leidžia
man turėti kairinis kintamasis Paprastai ir dešinė kintamasis,
arba individualus vertė, tai jei mes IR juos kartu, suteikia man galutinį rezultatą.
Taigi, ką aš turiu galvoje?
Jei programoje, turite kintamąjį kuris saugo vieną iš šių reikšmių,
arba tegul keep it simple, ir tik rašyti nulių ir individualiai,
Štai kaip Ampersand operatorius veikia.
0 Ampersand 0 ketina lygus 0.
Dabar, kodėl taip yra?
>> Tai labai panašus į Būlio išraiškos,
kad mes aptarė iki šiol.
Jei manote, galų gale, yra 0 klaidinga, 0 yra klaidinga, klaidinga ir neteisinga
yra, kaip mes aptarti Logiškai mąstant, taip pat klaidinga.
Taigi mes gauname 0 čia taip pat.
Pavartojus 0 ampersendo 1, gerai, kad, taip pat,
bus 0, nes tai kairine išraiška, kad būtų tiesa arba 1,
ji turi būti teisinga ir tikra.
Bet čia mes turime klaidinga ir tiesa, arba 0 ir 1.
Dabar vėl, jei mes turime 1 ampersendo 0, tai taip pat bus 0,
ir jei mes turime 1 ampersendo 1, pagaliau mes turime 1 bitas.
Taigi, kitaip tariant, mes ne daro nieko įdomiau su šiuo operatoriumi
tik dar, tai Ampersand operatorius.
Tai Bitinis operatorius AND.
Tačiau tai yra ingredientai per kurį mes galime padaryti
įdomių dalykų, kaip mes netrukus pamatysite.
>> Dabar pažvelkime tik vieną vertikali juosta Čionai dešinėje.
Jei turiu 0 truputį ir aš Arba tai su ja Bitinis
Arba operatorius, kitas 0 truputį, kad ketina suteikti man 0.
Jei aš imtis 0 truputį ir ar IT su A 1 tiek, tada aš ruošiuosi gauti 1.
Ir iš tikrųjų, tik aiškumas, leiskite man grįžti,
kad mano vertikalios juostos nėra klaidingai palaikyta 1 s.
Leiskite man perrašyti visus mano 1 yra šiek tiek daugiau
aiškiai, taip, kad mes kitą žr, jei aš turėti 1 arba 0, kad ketina būti 1,
o jei turiu 1 arba 1, kad, taip pat ketina būti 1.
Taigi jūs galite pamatyti logiškai, kad AR operatorius elgiasi labai skirtingai.
Tai suteikia man 0 arba 0 man duoda 0, tačiau kiekvienas kitas derinys suteikia man 1.
Kol turiu vieną 1 dalyje, formulė, rezultatas bus 1 d.
>> Skirtingai nei paties ir operatorius, Ampersand,
tik tada, jei turiu du 1, The lygtis, aš iš tikrųjų gauti 1 iš.
Dabar yra keletas kitų operatoriai, taip pat.
Vienas iš jų yra šiek tiek daugiau įsitraukti.
Taigi leiskite man eiti į priekį ir ištrinti tai atlaisvinti šiek tiek vietos.
Ir tegul ne išvaizdą Žymeklis simboliu, tik akimirkai.
Tai yra paprastai charakteris galite įvesti
Jūsų klaviatūra laikymu Shift ir tada vienas ant savo JAV skaičiais
klaviatūra.
>> Taigi tai yra išskirtinis Arba operatorius, arba išimtines.
Taigi mes tiesiog pamačiau arba operatorius.
Tai yra išimtinė arba operatorius.
Kas iš tikrųjų skirtumas?
Na tegul tiesiog pažvelgti į formulę, ir tai naudoti kaip ingredientus galiausiai.
0 XOR 0.
Aš ruošiuosi pasakyti visada 0.
Štai iš XOR apibrėžimas.
0 XOR 1 bus 1 d.
1 XOR 0 bus 1, ir 1 XOR 1 bus?
Negerai?
Arba tiesa?
Nežinau.
0.
Dabar tai, kas vyksta čia?
Na manau, kad apie Pavadinimas šio operatoriaus.
Išskirtinis ARBA, taip, kaip pavadinimas, rūšis ir, rodo,
atsakymas tik bus A 1, jei indėlis yra išskirtinis,
tik skirtingi.
Taigi čia įėjimai yra pat, todėl išėjimas yra 0.
Čia įėjimai yra pat, todėl išėjimas yra 0.
Čia yra išėjimai yra skirtingi, todėl jie yra išimtinės, todėl produkcija yra 1.
Taigi, tai labai panašus į IR, tai labai panašūs,
ar veikiau tai labai panašus į ARBA, bet tik išskirtiniu būdu.
Tai vienas yra nebėra 1, nes mes turime dvi 1-ųjų,
ir ne išimtinai, tik vienas iš jų.
Gerai.
Ką apie kitus?
Na tildės, tuo tarpu, yra iš tikrųjų gražus ir paprastas, laimei.
Ir tai unarinį operatoriaus, kuris reiškia,
jis taikomas tik vieną įvesties, vienas operandas, taip sakant.
Ne iš kairės ir dešinę.
Kitaip tariant, jei vartojate tildės iš 0, atsakymas bus priešingas.
Ir jei jūs imtis Tilde 1, The Atsakymas bus priešingas.
Taigi tildės operatorius iš paneigiant truputį būdas,
arba prakeiktas nuo tiek 0-1, arba nuo 1 iki 0.
>> Ir tai palieka mus pagaliau tik su dviem galutiniais operatorių,
vadinamasis kairysis SHIFT ir Vadinamasis teisę perėjimas operatorius.
Paimkime, kaip tas darbas atrodo.
Ataka perėjimas operatorius, parašyta su dviem laužtiniuose skliaustuose, pavyzdžiui, kad
veikia taip.
Jei mano indėlis, ar mano operandas, į kairę perėjimas operatorius paprasčiausiai yra 1.
Ir aš tada pasakysiu kompiuterį į kairę, kad 1, pasakyti septyni vietos,
rezultatas yra tarsi būčiau imtis, kad 1, ir perkelti jį
septynios vietos perkelti į kairysis, ir pagal nutylėjimą,
mes ketiname daryti prielaidą, kad erdvė į dešinę
ketina būti su paminkštinimu nuliai.
Kitaip tariant, 1 paliktas poslinkio 7 vyksta duoti me, kad 1, po 1, 2, 3,
4, 5, 6, 7 nulio.
Taigi tokiu būdu, jis leidžia jums imtis nedidelį skaičių kaip 1,
ir aiškiai padaryti jį daug daug, daug didesnis šiuo būdu,
bet mes iš tikrųjų ketiname pamatyti daugiau protingas požiūriai jį
vietoj to, taip pat,
>> Gerai.
Štai jį savaitę trys.
Pamatysime, jums kitą kartą.
Tai buvo CS50.
>> [Muzikos grojimo]
>> GARSIAKALBIS 1: Jis buvo tuo užkandis bar valgyti karštą fudge ledai.
Jis turėjo viską per veidą.
Jis dėvi, kad kaip ir barzda šokoladą
SPEAKER 2: Ką tu darai?
GARSIAKALBIS 3: Hmmm?
Ką?
>> SPEAKER 2: Ar jums tiesiog dukart DIP?
Jūs dvigubai artimųjų lustas.
GARSIAKALBIS 3: Atleiskit.
SPEAKER 2: Jūs artimųjų lustas, jums paėmė įkandimo, ir jūs artimųjų vėl.
GARSIAKALBIS 3:
SPEAKER 2: Štai kaip pradėti Visa jūsų burna tiesiai į kritimo.
Kitą kartą išgėrėte lustą, tik panirti jį vieną kartą, ir ją baigti.
>> GARSIAKALBIS 3: jūs žinote, ką Dan?
Jūs panirti kelią, kurį norite panirti.
Aš panirti kelią, kad aš noriu panirti.