[Daqq tal-mużika] 

Professur: Kull dritt. Dan huwa CS50 u dan huwa l-aħħar ta 'tlieta ġimgħa. Allura aħna qed hawn illum, mhux fil Sanders Teatru, minflok fil Weidner Librerija. Ġewwa tiegħu hija studio magħrufa bħala Hauser Studio, jew nistgħu ngħidu Studio H, jew għandhom aħna say-- jekk inti jgawdu dan ċajta, huwa attwalment mil classmate, Mark, online, li ssuġġeriet kemm permezz Twitter. Issa x'hemm jibred dwar tkun hawn fi studjo huwa li jien mdawra minn dawn aħdar ħitan, skrin aħdar jew chromakey, biex ngħidu hekk, li jfisser li s CS50 tim tal-produzzjoni, unbeknownst lili dritt issa, jista 'jkun it-tqegħid me aktar kullimkien fid-dinja, għall-aħjar jew għall-agħar. 

Issa dak li jinsab quddiem, il-problema sett tnejn hija f'idejk għal din il-ġimgħa, iżda bil-problema stabbiliti tliet din il-ġimgħa li ġejjin, inti ser jiġu kkontestati ma il-logħba hekk imsejħa ta '15, favor parti antik li inti tista 'recall tirċievi bħala wild li għandha mazz sħiħ ta 'numri li jistgħu slide up, down, xellug u lemin, u hemm distakk wieħed fi ħdan il-puzzle, li fih inti jistgħu attwalment slide dawk il-biċċiet puzzle. Fl-aħħar inti tirċievi dan puzzle f'xi ordni każwali semi, u l-għan huwa li sort dan, fuq għal isfel, xellug għal-lemin, minn wieħed it-triq kollha sa permezz 15. 

Sfortunatament, l-implimentazzjoni inti ser ikollok fil-idejn se tkun software ibbażata, mhux fiżikament. Int fil-fatt se jkollhom jiktbu kodiċi li magħhom student jew utent jista jilagħbu l-logħba tal-15. U fil-fatt, fil-Hacker edizzjoni ta 'logħba tal-15, inti ser tkun sfida biex jimplimentaw, mhux biss l-daqq ta 'din l-iskola antika logħba, iżda pjuttost il-solving ta 'dan, l-implimentazzjoni modalità god, biex ngħidu hekk, li attwalment issolvi l-puzzle għall-bniedem, billi jipprovdulhom ħjiel, wara ħjiel, wara ħjiel. Allura aktar fuq dik il-ġimgħa d-dieħla. Imma dan huwa dak li jinsab quddiem. 

Għal issa ifakkar li aktar kmieni din il-ġimgħa kellna dan cliffhanger, jekk inti se, li biha l-aħjar aħna kienu qed jagħmlu l-issortjar għaqli kien limitu massimu ta 'big o ta n kwadrat. Fi kliem ieħor, sort bużżieqa, sort għażla, sort inserzjoni, kollha kemm huma, filwaqt li jkunu differenti fl-implimentazzjoni tagħhom, devoluti fi n kwadrat taħdem time fil-ħafna agħar każ. U aħna ġeneralment tassumi li il ħafna agħar każ għall-għażla huwa wieħed li inputs tiegħek huma kompletament lura. U fil-fatt, hija ħadet pjuttost ftit passi biex timplimenta kull waħda minn dawk il algoritmi. 

Issa fl-aħħar nett tal-klassi irtirar, qabbilna sort bużżieqa kontra sort għażla kontra ieħor li aħna msejħa jingħaqdu sort fil-ħin, u nipproponi li huwa jieħu vantaġġ ta 'lezzjoni minn ġimgħa żero, qasma u conquer. U b'xi mod kisba xi tip ta ' logaritmika running time finalment, minflok xi ħaġa dan huwa purament kwadratiċi. U huwa pjuttost mhux logaritmika, huwa daqsxejn aktar minn dak. Imma jekk inti recall mill-klassi, kien ħafna, ħafna aktar mgħaġġla. Ejja tagħti ħarsa lejn fejn aħna jitħalla 'off. 

Bubble sort versus għażla sort versus sort jingħaqdu. Issa dawn qed kollha timxi, fil teorija, fl-istess ħin. Il-CPU qed taħdem bl-istess veloċità. Iżda int tista 'tħossok kif boring dan huwa malajr ħafna se ssir, u kemm fast, meta aħna injetta daqsxejn ta 'algoritmi ġimgħa żero, il nistgħu veloċità affarijiet up. 

Allura sort marka jistenna aqwa. Kif nistgħu lieva, sabiex sort numri aktar malajr. Well ejja jaħsbu lura li ingredjent li aħna kellhom lura fil żero ġimgħa, dak ta ' tiftix għal xi ħadd fil-ktieb tat-telefon, u tfakkar li l- pseudocode li aħna propost, li permezz tagħhom nistgħu nsibu xi ħadd bħal Mike Smith, stenna ftit xi ħaġa bħal din. 

Issa tagħti ħarsa b'mod partikolari fil-linja 7 u 8, u 10 u 11, li jinduċi li loop, fejn aħna tinżamm tmur lura għal-linja 3 għal darb'oħra, u għal darb'oħra, u għal darb'oħra. Iżda jirriżulta li nistgħu tara dan algoritmu, hawnhekk fil pseudocode, ftit aktar ħolistiku. Fil-fatt, dak li jien tfittex fil hawn fuq l-iskrin, huwa algoritmu għat-tiftix għal Mike Smith fost uħud sett ta 'paġni. U fil-fatt, nistgħu jissimplifika dan algoritmu fil dawk il-linji 7 u 8, u 10 u 11 biss jgħidu dan, li stajt ppreżentati hawnhekk bl-isfar. Fi kliem ieħor, jekk Mike Smith huwa aktar kmieni fil-ktieb, aħna ma bżonn li jispeċifikaw pass pass issa kif imorru issib lilu. Aħna ma jkollhom biex tispeċifika li jmorru lura għal-linja 3, għaliex ma we biss minflok, jiġifieri, b'mod iktar ġenerali, tfittxija għall Mike fil- nofs tax-xellug tal-ktieb. 

Bil-maqlub, jekk Mike huwa attwalment aktar tard fil-ktieb, għaliex ma aħna biss jikkwotaw tfittxija unquote għall Mike fil-nofs tal-lemin tal-ktieb. Fi kliem ieħor, għaliex ma we biss tip ta 'Punt li lilna nfusna qal, tfittxija għal Mike f'dan subsett tal-ktieb, u tħalli f'idejn l eżistenti tagħna algoritmu biex tgħidilna Kif tfittex Mike fil li nofs tax-xellug tal-ktieb. Fi kliem ieħor, tagħna algoritmu jaħdem jekk huwa ktieb tat-telefon ta 'din il-ħxuna, ta' dan ħxuna, jew kwalunkwe ħxuna tkun xi tkun. Allura nistgħu recursively jiddefinixxu dan algoritmu. Fi kliem ieħor, fuq il- screen hawn, huwa algoritmu għat-tiftix għal Mike Smith fost il-paġni ta 'ktieb tat-telefon. Dan b'konformità 7 u 10, ejja biss jgħidu eżattament dan. U jien jużaw dan it-terminu mument ilu, u tabilħaqq, recursion huwa l-buzzword għal issa, u huwa dan il-proċess ta 'kif isir xi ħaġa ċiklika mill b'xi użu kodiċi li diġà għandek, u ssejjaħ dan mill-ġdid, u għal darb'oħra, u għal darb'oħra. Issa li għaddej biex tkun importanti li aħna b'xi mod qiegħ out, u ma tagħmel dan infinitament twil. Inkella aħna qed tmur biex ikollhom tabilħaqq loop infinita. Imma ejja ara jekk nistgħu tissellef din l-idea ta 'recursion, tagħmel xi ħaġa mill-ġdid u għal darb'oħra u għal darb'oħra, biex isolvu il-problema issortjar permezz jingħaqdu sort, l-aktar effiċjenti. 

So I jagħtuk jingħaqdu sort. Ejja tagħti ħarsa. Allura hawnhekk huwa pseudocode, ma li nistgħu jimplimentaw issortjar, jużaw dan algoritmu imsejħa tip jingħaqdu. U huwa pjuttost sempliċi dan. Fuq l-input ta 'elementi N, fi kliem ieħor, jekk int minħabba n elementi u n-numri u ittri jew ikun x'ikun l-input huwa, jekk int tingħata l-elementi n, jekk n huwa inqas minn 2, biss jirritorna. Dritt? Għaliex jekk n hija inqas minn 2, li ifisser dik il-lista tiegħi ta 'elementi huwa jew daqs 0 jew 1, u f'dawn iż-żewġ każijiet trivjali, l-lista hija diġà riżolta. Jekk ma jkunx hemm lista, huwa magħżula. U jekk hemm lista ta 'tul 1, huwa ovvjament magħżula. Allura l-algoritmu biss jeħtieġ li verament tagħmel xi ħaġa interessanti, jekk ikollna tnejn jew aktar elementi mogħtija lilna. Mela ejja nħarsu lejn il-magic imbagħad. Else issolvi l nofs tax-xellug tal-elementi, imbagħad sort in-nofs lemini ta 'elementi, imbagħad jingħaqdu l-nofsijiet magħżula. U x'hemm tip tal-moħħ liwi hawnhekk, huwa li jien ma verament jidhru li qallek xejn għadha biss, id-dritt? All I ve qal huwa, tingħata lista ta n elementi, issolvi l-nofs xellugi, allura l-nofs tal-lemin, imbagħad jingħaqdu l-nofsijiet magħżula, iżda fejn huwa l-zalza sigriet attwali? Fejn hi l-algoritmu? Ukoll jirriżulta li dawn iż-żewġ linji ewwel, nofs tip xellug ta 'elementi, u tip dritt nofs ta 'elementi, huma sejħiet rikursivi, biex ngħidu hekk. 

Wara kollox, f'dan il-ħin, għandi algoritmu li biex sort mazz sħiħ ta 'elementi? Iva. Huwa dritt hawn. Huwa dritt hawn fuq l-iskrin, u so I jistgħu jużaw l-istess sett ta 'passi biex isolvi l-nofs tax-xellug, kif nista in-nofs lemini. U fil-fatt, għal darb'oħra, u għal darb'oħra. Allura b'xi mod jew ieħor, u aħna ser dalwaqt tara dan, il-maġija ta 'tip jingħaqdu huwa inkorporat f'dak finali ħafna linja, li qed jingħaqdu in-nofsijiet magħżula. U li jidher pjuttost intuwittivi. Tieħu żewġ nofsijiet, u int, b'xi, jingħaqdu flimkien, u aħna ser tara dan konkret fil-mument. 

Iżda din hija algoritmu kompluta. U ejja tara eżattament għaliex. Well ejja ngħidu li aħna qed jingħataw dawn l-istess tmien elementi hawn fuq l-iskrin, wieħed permezz tmienja, iżda dawn qed sabiex apparentement każwali. U l-għan fil-idejn huwa biex issolvi dawn l-elementi. Well kif nista tmur dwar nagħmilx hekk tuża, għal darb'oħra, jingħaqdu sort, permezz ta 'dan pseudocode? U għal darb'oħra, ingrain dan moħħok, għal ftit mument. L-ewwel każ hija pjuttost trivjali, jekk huwa inqas minn 2, redditu ġust, hemm ebda xogħol xi jsir. Allura verament hemm biss tlieta passi biex verament iżomm f'moħħu. Għal darb'oħra, u għal darb'oħra, jien tmur jridu jkollhom biex isolvi l-nofs tax-xellug, sort l-nofs tal-lemin, u mbagħad darba tagħhom żewġ nofsijiet huma magħżula, Irrid li jingħaqdu flimkien fil-lista Issortjati wieħed. Sabiex iżommu dan f'moħħhom. 

Allura hawnhekk-lista oriġinali. Ejja jittratta dan bħala array, kif aħna bdew f'żewġ ġimgħa, li huwa blokk kontigwa ta 'memorja. F'dan il-każ, li jkun fih tmien numri, lura lura lura. U ejja issa japplikaw sort jingħaqdu. So I l-ewwel trid issolvi in-nofs tax-xellug ta 'din il-lista, u ejja, għalhekk, tiffoka fuq 4, 8, 6, u 2. 

Issa kif nista tmur dwar issortjar lista ta 'daqs 4? Well I għandhom issa jqisu issortjar ix-xellug tan-nofs tax-xellug. Għal darb'oħra, ejja Rewind għal ftit mument. Jekk il-pseudocode huwa dan, u jien mogħtija tmien elementi, 8 huwa ovvjament akbar minn jew ugwali għal 2. Allura l-ewwel każ ma japplikax. Allura biex issolvi tmien elementi, I-ewwel sort l-nofs tax-xellug ta 'elementi, imbagħad I sort l-nofs tal-lemin, imbagħad I jingħaqdu l-żewġ nofsijiet magħżula, kull waħda ta 'daqs 4. KOLLOX SEW. 

Imma jekk inti stajt biss told me, isolvi l- nofs tax-xellug, li issa hija d-daqs 4, kif nista sort l-nofs xellug? Ukoll jekk I jkollhom input ta 'erba' elementi, I ewwel sort ix-xellug tnejn, allura l-tnejn id-dritt, u mbagħad I jingħaqdu flimkien. Għalhekk għal darb'oħra, din issir bit ta mind liwi logħba hawn, għaliex inti, tip ta ', għandek ftakar fejn inti fil-istorja, iżda fl-aħħar tal-ġurnata, minħabba kwalunkwe numru ta 'elementi, inti l-ewwel trid issolvi l- nofs tax-xellug, allura l-nofs tal-lemin, imbagħad jingħaqdu flimkien. Nibdew biex jagħmlu eżattament dan. Hawn il-input ta 'tmien elementi. Issa aħna qed tħares lejn in-nofs tax-xellug hawn. Kif nista sort erba 'elementi? Well I ewwel isolvi l-nofs tax-xellug. Issa kif nista sort l-nofs xellug? Well I kont qed jingħataw żewġ elementi. Mela ejja sort dawn iż-żewġ elementi. 2 hija akbar minn jew ugwali għal 2, tal-kors. Allura li l-ewwel każ ma japplikax. 

So I issa għandhom biex issolvi ix-xellug nofs ta 'dawn iż-żewġ elementi. Il-half-xellug, naturalment, huwa biss 4. Allura kif nista sort lista ta 'element wieħed? Ukoll issa, din il-bażi speċjali top up, biex ngħidu hekk, tapplika. 1 huwa inqas minn 2, u tiegħi lista hija tabilħaqq ta 'daqs 1. So I biss ritorn. I ma tagħmel xejn. U fil-fatt, tħares lejn dak li stajt jsir, 4 huwa diġà magħżula. Bħal Jien diġà parzjalment suċċess hawn. 

Issa li jidher tip ta 'stupid li jitlob, iżda huwa veru. 4 hija lista ta 'daqs 1. Huwa diġà magħżula. Dik hija l-nofs tax-xellug. Now I sort l-nofs tal-lemin. Input tiegħi huwa element wieħed, 8 bl-istess mod, diġà magħżula. Stupid, wisq, iżda għal darb'oħra, dan il-prinċipju bażiku se jippermettilna naslu biex issa jibnu fuq quċċata ta 'dan b'suċċess. 4 magħżula, 8 huwa magħżul, issa dak li kien dan l-aħħar pass? Allura l-tielet u laħħar pass, kwalunkwe ħin li inti qed issortjar lista, irtirar, kien li jingħaqdu ż-żewġ nofsijiet, ix-xellug u d-dritt. Mela ejja nagħmlu eżattament dan. Nofs tax-xellug tiegħi huwa, ovvjament, 4. Nofs tal-lemin tiegħi hija 8. 

Mela ejja tagħmel dan. L-ewwel jien ser talloka xi memorja addizzjonali, li jien ser jirrappreżentaw hawn, biss bħala firxa sekondarja, li l-kbir biżżejjed biex joqgħodu f'din. Iżda int tista 'timmaġina li testendi li rettangolu t-tul kollu, jekk għandna bżonn aktar tard. Kif nista 'tieħu 4 u 8, u jingħaqdu dawn iż-żewġ listi ta 'daqs 1 flimkien? Hawnhekk, ukoll, pretty sempliċi. 4 jiġi l-ewwel, mbagħad taqa 8. Għaliex jekk irrid biex issolvi l- nofs tax-xellug, allura l-nofs tal-lemin, u mbagħad jingħaqdu dawn iż-żewġ nofsijiet flimkien, sabiex magħżula, 4 jiġi l-ewwel, mbagħad taqa 8. 

Allura aħna jidhru li jagħmlu progress, anke għalkemm I ma jsir ebda xogħol effettiv. Imma ftakar fejn ninsabu fl-istorja. Aħna oriġinarjament ħadet tmien elementi. Aħna magħżula l-nofs tax-xellug, li huwa ta '4. Imbagħad aħna magħżula in-nofs tax-xellug tan-nofs tax-xellug, li kien ta '2. U here we go. Aħna qed isir ma dak il-pass. 

Allura jekk aħna ve magħżula l xellug nofs ta '2, issa aħna jkollhom biex issolvi l-nofs tal-lemin tat-2. Allura l-nofs tal-lemin tat-2 huwa dawn iż-żewġ valuri hawn, 6 u 2. Mela ejja issa tieħu l-input ta 'daqs 2, u sort l-nofs tax-xellug, u mbagħad in-nofs lemini, u mbagħad jingħaqdu flimkien. Well kif nista sort lista ta 'daqs 1, li jkun fiha biss in-numru 6? Jien diġà sar. Dik il-lista ta 'daqs 1 huwa magħżul. 

Kif nista sort lista oħra ta ' daqs 1, l-hekk imsejħa nofs tal-lemin. Ukoll, wisq, huwa diġà magħżula. In-numru 2 huwa waħdu. Allura issa I għandhom żewġ nofsijiet, tax-xellug u dritt, I-ħtieġa li jingħaqdu flimkien. Ħalli nagħtikom myself xi spazju żejjed. U mqiegħda 2 fil hemm, allura 6 fil hemm, u b'hekk issortjar dik il-lista, tax-xellug u lemin, u li jingħaqad flimkien, finalment. Hekk jien fil-forma ftit aħjar. Jien ma jsirx, minħabba b'mod ċar 4, 8, 2, 6 mhijiex l-ordni finali li nixtieq. Imma jien issa għandhom żewġ listi ta 'daqs 2, li ikunu t-tnejn, rispettivament, ġew magħżula. Allura issa jekk inti kontrina fil moħħ tiegħek għajn, fejn ma dan il-leave us? I bdew bi tmien elementi, imbagħad I fadal l-isfel man-nofs tax-xellug ta '4, allura l-nofs tax-xellug ta '2, u allura l-nofs tal-lemin ta '2, I lest, għalhekk, l-issortjar ix-xellug nofs ta '2, u n-nofs dritt ta' 2, Allura x'inhu l-tielet u laħħar pass hawn? Għandi biex jingħaqdu flimkien żewġ listi ta 'daqs 2. Mela ejja imorru quddiem. U fuq l-iskrin hawn, jagħtu me xi memorja addizzjonali, għalkemm teknikament, avviż li stajt ltqajna mazz sħiħ ta 'vojt ispazju top up hemmhekk. Jekk Nixtieq inkun speċjalment ispazju effiċjenti għaqli, I tista 'biss tibda miexja l-elementi quddiem u lura, fuq u isfel. Iżda biss għaċ-ċarezza viżwali, Jien ser tpoġġi l-isfel hawn taħt, li żżomm affarijiet sbieħ u nodfa. 

So I ħadthom ltqajna żewġ listi ta 'daqs 2. L-ewwel lista għandha 4 u 8. It-tieni lista tkun 2 u 6. Ejja jingħaqdu dawk flimkien sabiex Issortjat. 2, naturalment, jiġi l-ewwel, imbagħad 4, imbagħad 6, imbagħad 8. U issa aħna jidhru li qegħdin ikunu x'imkien interessanti. Nofs Issa stajt magħżula tal- lista, u inzerta, huwa il-numri anke, iżda li huwa, tabilħaqq, biss koinċidenza. U jien issa magħżula ix-xellug nofs, b'tali mod li huwa 2, 4, 6, u 8. Xejn huwa out of order. Li jħoss simili progress. 

Issa jħoss simili stajt kien jitkellem dejjem issa, Allura dak għad irid jara jekk din algoritmu huwa, tabilħaqq, aktar effiċjenti. Iżda aħna qed tmur permezz super metodiku. A kompjuter, naturalment, tagħmel dan bħal dik. Għalhekk, fejn huma aħna? Bdejna bi tmien elementi. I magħżula l nofs tax-xellug tal-4. I jidhru li jsir ma 'dak. Allura issa l-pass li jmiss huwa li sort in-nofs lemini tal-4. U din il-parti nistgħu mmorru permezz ta 'aktar ftit malajr, għalkemm int merħba lill kontrina jew nieqaf, biss jaħsbu permezz dan fid pass tiegħek, imma dak għandna issa hija opportunità biex jagħmlu l-istess algoritmu eżatt fuq erba numri differenti. 

Mela ejja aqbad, u tiffoka fuq in-nofs lemini, li aħna qegħdin hawn. Il-half xellug ta 'dik nofs tal-lemin, u issa l- nofs xellugija xellug nofs ta 'li nofs id-dritt, u kif nista sort lista ta 'daqs 1 fih biss in-numru 1? Huwa diġà sar. Kif nista 'tagħmel l-istess lista ta 'daqs 1 fih biss 7? Huwa diġà sar. It-tielet pass għal dan nofs imbagħad huwa li jingħaqdu dawn iż-żewġ elementi fi lista ġdida ta 'daqs 2, 1 u 7. Ma jidhirx li għamlu kollha xogħol li ħafna interessanti. Ejja naraw x'jiġri li jmiss. I biss magħżula l-nofs tax-xellug tal- nofs tal-lemin tal-input oriġinali tiegħi. Issa ejja sort-dritt nofs, li jkun fih 5 u 3. Ejja darb'oħra nħarsu lejn ix-xellug nofs, magħżula, nofs tal-lemin, magħżula, u jingħaqdu dawn iż-żewġ flimkien, fis xi spazju addizzjonali, 3 jiġi l-ewwel, mbagħad taqa 5. U hekk issa, aħna għandna magħżula l nofs xellugija nofs tal-lemin tal-problema oriġinali, u in-nofs lemini tal-nofs tal-lemin tal-problema oriġinali. X'hemm-tielet u laħħar Pass? Ukoll biex jingħaqdu dawn iż-żewġ nofsijiet flimkien. So let me nikseb myself xi ispazju żejda, iżda, għal darb'oħra, I jista 'jkun jużaw dak l-ispazju up żejda top. Iżda aħna qed tmur biex iżommu sempliċi viżwalment. Let me jingħaqdu fil issa 1, u imbagħad 3, u mbagħad 5, u mbagħad 7. B'hekk jħallu me issa mal- nofs tal-lemin tal-problema oriġinali li l-perfettament riżolta. 

Allura dak li jibqa? Inħoss bħal I iżommu qal il istess affarijiet darb'oħra, u għal darb'oħra, iżda li jirrifletti tal- fatt li aħna qed tuża recursion. Il-proċess ta 'użu ta algoritmu darb'oħra, u għal darb'oħra, fuq sottogruppi iżgħar ta ' il-problema oriġinali. So I issa għandhom xellug magħżula nofs il-problema oriġinali. I jkollu nofs Issortjat dritt tal-problema oriġinali. X'hemm-tielet u laħħar pass? Oh, huwa qed jingħaqdu. Mela ejja tagħmel dan. Ejja jalloka xi addizzjonali memorja, iżda god tiegħi, aħna tista 'tpoġġi kullimkien issa. Għandna spazju tant disponibbli lilna, imma aħna ser jżommha sempliċi. Minflok tmur lura u raba memorja oriġinali tagħna, ejja biss tagħmel dan viżwalment stabbiliti hawn taħt, biex jintemm l-għaqda tal- nofs tax-xellug u n-nofs lemin. 

Allura bl-inkorporazzjoni, dak li għandi bżonn tagħmel? I tixtieq li tieħu l-elementi fl-ordni. Allura tħares lejn l-nofs tax-xellug, Nara l-ewwel numru huwa 2. I tħares lejn in-nofs lemini, Nara l-ewwel numru huwa 1, dan ovvjament li Numru do Irrid ġewwieni out, u mqiegħda ewwel fil-lista finali tiegħi? Of course, 1. Issa nixtieq li jistaqsu l-istess kwistjoni. Fuq in-nofs tax-xellug, stajt għadhom kisbu n-numru 2. Min-nofs tal-lemin, Stajt ltqajna l-għadd 3. Liema wieħed do Irrid li jagħżlu? Of course, numru 2 U issa avviż l-kandidati huma 4 fuq ix-xellug, 3 fuq il-lemin. Ejja, naturalment, jagħżlu 3. Issa l-kandidati huma 4 dwar fuq ix-xellug, 5 fuq il-lemin. Aħna, naturalment, jagħżlu 4. 6 fuq ix-xellug, 5 fuq il-lemin. Aħna, naturalment, jagħżlu 5. 6 fuq ix-xellug, 7 fuq il-lemin. Nagħżlu 6, u allura aħna jagħżlu 7, u allura aħna jagħżlu 8. Voila. 

Allura numru kbir ta 'kliem aktar tard, we jkunu magħżula din il-lista ta 'tmien elementi fi lista ta 'wieħed permezz tmienja, li żied ma 'kull pass, imma kemm ħin ma jieħdu magħna biex tagħmel dan. Well stajt deliberatament affarijiet stabbiliti pictorially hawn, sabiex inkunu nistgħu tip ta ' tara jew japprezzaw id-diviżjoni fil conquering li kien jiġri. 

Tabilħaqq jekk inti tħares lura lejn il-qawmien, Stajt xellug kollha ta 'dawn il-linji bit-tikek fis-seħħ id-detenturi, inti tista ', tip ta ', ara, f'ordni riversa, jekk inti tip ta 'ħarsa lura fil istorja issa, lista oriġinali tiegħi huwa, ovvjament, ta 'daqs ta' 8. U allura qabel, I kien jittrattaw żewġ listi ta 'daqs 4, u mbagħad erba 'listi ta' daqs 2, u mbagħad tmien listi ta 'daqs 1. 

Allura dak li ma dan, tip ta ', infakkarkom ta'? Ukoll, fil-fatt, xi wieħed l-algoritmi Imxejna ħares lejn s'issa fejn aħna firda, u jaqsmu, u qasma, iżommu jkollhom affarijiet mill-ġdid, u għal darb'oħra, jirriżulta din l-idea ġenerali. U hekk hemm xi ħaġa logaritmika għaddejjin hawn. U m'humiex log pjuttost ta n, iżda hemm komponent logaritmiku għal dak li aħna ħadthom biss isir. 

Issa ejja tikkunsidra kif dan fil-fatt hu. Allura log ta n, reġa 'kien żmien running kbir, meta għamilna xi ħaġa bħal tfittxija binarju, kif aħna issa sejħa hija, l-istrateġija firda u conquer permezz tagħhom sibna Mike Smith. Issa teknikament. C'est log bażi 2 tal n, anke għalkemm fil-klassijiet matematika aktar, 10 huwa normalment il-bażi li għandek tassumi. Imma x-xjenzjati tal-kompjuter kważi dejjem jaħsbu u jitkellmu f'termini ta 'bażi ​​2, hekk aħna ġeneralment biss jgħidu log ta n, minflok log bażi 2 tal n, iżda dawn qed eżattament waħda u l- istess fid-dinja tal-kompjuter xjenza, u bħala twarrib, hemm fattur kostanti differenza bejn it-tnejn, dan huwa irrilevanti xorta waħda, għal raġunijiet aktar formali. 

Iżda għal issa, dak li aħna kura dwar huwa dan l-eżempju. Mela ejja ma jipprova bl-eżempju, iżda fl inqas użu eżempju tan-numri fil-idejn bħala kontroll sanità, jekk inti se. Allura qabel il-formula kienet log bażi 2 ta 'n, imma dak li hu n f'dan il-każ. Kelli numri n oriġinali, jew 8 numru oriġinali speċifikament. Issa huwa kien ftit imma jien pretty żgur li log bażi 2 tal-valur 8 huwa 3, u fil-fatt, x'hemm sbieħ dwar dan hija li 3 huwa eżattament l-għadd ta 'drabi li inti tista 'taqsam lista ta 'tul 8 darb'oħra, u għal darb'oħra, u għal darb'oħra, sakemm int xellug ma 'listi ta' ftit daqs 1. Dritt? 8 tmur sa 4, tmur għal 2, tmur għal 1, u li l- jirriflettu eżattament dak stampa kellna ftit mument ilu. Allura sanità ftit jiċċekkjaw dwar fejn l-logaritmu huwa attwalment involut. 

Allura issa, x'iktar huwa involut hawnhekk? n. Allura avviż li kull time I maqsuma l-lista, għalkemm ordni invers fl-istorja hawn, I kien għadhom jagħmlu n-affarijiet. Dak il-pass li qed jingħaqdu meħtieġ li I tolqot kull wieħed mill-numri, sabiex mexxiha fil post xieraq tagħha. Għalhekk anki jekk l-għoli ta 'din dijagramma tkun ta 'daqs log n ta' n jew 3, speċifikament, fi kliem ieħor, Jien għamilt tliet diviżjonijiet hawn. Kemm ix-xogħol ma nagħmel orizzontalment flimkien din it-tabella kull darba? 

Well, I ma n-passi ta ' xogħol, għaliex jekk stajt ltqajna erba 'elementi u erba' elementi, u għandi bżonn biex jingħaqdu flimkien. I bżonn li tgħaddi minn dawn l-erba u dawn l-erba, finalment jingħaqdu magħhom lura fi tmien elementi. Jekk maqlub Stajt ltqajna tmien swaba minn hawn, li jiena ma, u tmienja fingers-- sorry-- Jekk stajt ltqajna erba 'frottiet hawn fuq, li nagħmel, erba 'frottiet minn hawn, li nagħmel, allura dak l-istess eżempju bħal qabel, jekk nagħmel tmien swaba għalkemm fil B'kollox, li nista ', tip ta', do. I tista 'eżattament do hawnhekk, imbagħad I jista 'ċertament jingħaqdu kollha ta 'dawn il-listi ta 'daqs 1 flimkien. Imma I ċertament jkollha tħares f'kull element darba eżattament. Allura l-għoli ta 'dan il-proċess huwa log n, il-wisa 'dan il-proċess, biex ngħidu hekk, huwa n, sabiex dak we jidhru li jkollhom, finalment, huwa żmien running-daqs n drabi log n. 

Fi kliem ieħor, aħna maqsuma il-lista, log n drabi, imma kull darba għamilna dan, kellna tmissx kull wieħed mill-elementi sabiex jingħaqdu kollha flimkien, li kien n pass, hekk aħna n ħinijiet log n, jew bħala xjenzat kompjuter ngħid, asimptotikalment, li ikun il-kelma big biex jiddeskrivu l-ogħla marbuta fuq running time, qed norganizzaw fil-o big ta 'log n żmien, biex ngħidu hekk. 

Issa dan huwa sinifikanti, għaliex tfakkar dak il-ħinijiet tmexxija kienu ma sort bużżieqa, u l-għażla sort, u sort inserzjoni, u anki ftit oħrajn li jeżistu, n kwadrat kien fejn konna fuq. U inti tista ', tip ta', tara dan hawn. Jekk n kwadrat hija ovvjament n darbiet n, iżda hawnhekk għandna n ħinijiet log n, u aħna diġà jafu minn ġimgħa żero, li log n, l-logaritmika, huwa aħjar minn lineari xi ħaġa. Wara kollox, tfakkar l-istampa mal-aħmar u l-isfar u l-linji aħdar li aħna ġibdet, l linja logaritmika aħdar kien ħafna inqas. U għalhekk, ħafna aħjar u aktar malajr mill-linji sofor u ħomor dritta, n ħinijiet log n jiġifieri, tabilħaqq, aħjar minn żminijiet n n, jew n kwadrat. 

Allura aħna jidhru li jkollhom identifikat jingħaqdu algoritmu sort li tmur fil ħafna iktar ħeffa, u tabilħaqq, hu għalhekk, aktar kmieni din il-ġimgħa, meta rajna dak il-konkors bejn bużżieqa sort, sort għażla, u jingħaqdu sort, jingħaqdu sort tassew, tassew rebaħ. U fil-fatt, aħna lanqas biss stenna għall bubble sort u sort għażla biex jintemm. 

Issa ejja tagħti pass ieħor għal dan, minn ftit aktar perspettiva formali, biss fil- każ, dan resonates aħjar minn dik id-diskussjoni f'livell ogħla. Allura hawnhekk-algoritmu ġdid. Ejja nistaqsu lilna nfusna, dak il-ħin qed taħdem huwa ta 'din algoritmi diversi passi? Ejja diviż l-ewwel każ u t-tieni każ. L-IF u l-ieħor fil-każ IF, JEKK n huwa inqas minn 2, biss jirritorna. Iħoss bħal time kostanti. Huwa, tip ta, bħal żewġ passi, JEKK n huwa inqas minn 2, mbagħad jirritornaw. Imma kif għidna nhar it-Tnejn, ħin kostanti, jew kbar o ta '1, jista jkun żewġ skali, tliet passi, anke 1,000 passi. Li huwa importanti huwa li huwa numru kostanti ta 'passi. Allura l-isfar enfasizzati pseudocode hawn runs fi, aħna ser sejħa hija, ħin kostanti. Allura b'mod aktar formali, u aħna qed tmur to-- dan se jkun il-punt sa fejn aħna jifformalizza dan id-dritt now-- T ta n, l running time ta 'problema li jieħu somethings n bħala input, ugwali big o wieħed, JEKK n huwa inqas minn 2. Allura huwa kondizzjonali fuq dan. Allura biex tkun ċara, JEKK n huwa inqas minn 2, aħna għandna lista qasira ħafna, imbagħad l-running time, T ta 'n, fejn n hija 1 jew 0, f'dan il-każ speċifiku ħafna, huwa biss se jkun żmien kostanti. Huwa ser jieħu waħda pass, żewġ passi, tkun xi tkun. Huwa numru fiss ta 'passi. 

Allura l-parti mmerraq żgur li jridu fil il każ l-ieħor fil-pseudocode. Il-każ IKTAR. Sort nofs tax-xellug ta 'elementi, tip dritt nofs ta 'elementi, jingħaqdu nofsijiet magħżula. Kemm idum ma kull wieħed minn dawk il-passi tieħu? Ukoll, jekk it-tmexxija ħin biex issolvi elementi n huwa, ejja sejħa hija ħafna ġenerikament, T ta n, imbagħad issortjar ix-xellug nofs mill-elementi huwa, tip ta ', simili qal, T ta 'n diviż bi 2, u l-istess għażla in-nofs lemini ta 'elementi huwa, tip ta', simili qal, T ta 'n maqsuma 2, u mbagħad jingħaqdu l nofsijiet magħżula. Ukoll jekk stajt ltqajna xi numru ta 'elementi hawn, bħall erba, u xi numru ta 'elementi hawn, bħal erbgħa, u I għandhom jingħaqdu kull wieħed minn dawn l-erba fi, u kull wieħed minn dawn l-erba fi, wieħed wara l-oħra, b'tali mod li finalment I jkollhom tmien elementi. Hija tħoss bħal dan huwa big o ta 'passi n? Jekk Stajt ltqajna n swaba u kull wieħed minnhom għandu jiġu amalgamati fis-seħħ, dan huwa simili ieħor passi n. 

Allura fil-fatt formulaically, nistgħu tesprimi din, għalkemm scarily ftit fl-ewwel daqqa t'għajn, iżda hija xi ħaġa li jaqbad eżattament li l-loġika. Il-ħin taħdem, T ta n-IF n hija akbar minn jew ugwali għal 2. F'dan il-każ, il-każ IKTAR, huwa T ta n maqsum bi 2, flimkien ma T ta 'N diviż bi 2, plus big o ta n, xi Numru lineari ta 'passi, forsi eżattament n, forsi 2 darbiet n, imma hija bejn wieħed u ieħor, l-ordni ta 'n. Allura dan, wisq, huwa kif nistgħu tesprimi din formulaically. Issa inti ma tkunx taf dan sakemm inti ħadthom rreġistrati fil moħħok, jew tfittex it up fil- lura ta 'textbook, li jista 'jkollhom ftit iqarrqu sheet fit-tmiem, iżda dan huwa, tabilħaqq, ser tagħtina big o ta n log n, minħabba r-rikorrenza li int tara hawn fuq l-iskrin, jekk inti fil-fatt ma kien out, ma numru infinit ta 'eżempji, jew inti ma kien formulaically, inti tara li dan, minħabba din il-formula innifsu huwa rikursivi, ma 't ta n fuq xi ħaġa fuq il-lemin, u t ta 'N fuq ix-xellug, din tista fil-fatt jiġu espressi, finalment, go kemm kbar ta 'log n n. Jekk ma konvint, li multa għal issa, ftit jieħdu fuq il-fidi, li dan huwa, tabilħaqq, dak li rikorrenza twassal għal, iżda din hija biss daqsxejn aktar ta ' approċċ matematika li tfittex fil-mument tmexxija ta sort jingħaqdu ibbażata fuq pseudocode tagħha waħdu. 

Issa ejja tagħti daqsxejn ta ' breather minn dak kollu li, u tagħti ħarsa lejn ċerti ex Senatur, li tista 'tidher ftit familjari, li poġġa bilqiegħda ma 'Eric Google Schmidt, xi żmien ilu, għal intervista fuq il-palk, quddiem il-mazz sħiħ ta 'nies, jitkellem finalment dwar suġġett, li pjuttost issa familjari. Ejja tagħti ħarsa. 

ERIC SCHMIDT: Issa Senatur, int hawn fuq Google, u Inħobb naħseb tal- presidenza bħala intervista tax-xogħol. Issa huwa diffiċli li jsibu xogħol bħala president. PRESIDENT OBAMA: Dritt. ERIC SCHMIDT: U int se tagħmel [inaudible] issa. Huwa wkoll diffiċli li jsibu xogħol fil-Google. PRESIDENT OBAMA: Dritt. 

ERIC SCHMIDT: Aħna mistoqsijiet, u aħna jistaqsu mistoqsijiet kandidati tagħna, u dan huwa wieħed mill Larry Schwimmer. 

PRESIDENT OBAMA: OK. 

ERIC SCHMIDT: What? You guys think jien kidding? Huwa dritt hawn. X'inhu l-aktar mod effiċjenti biex sort xi interi miljun 32 bit? 

PRESIDENT OBAMA: Well-- ERIC SCHMIDT: Kultant, forsi jien sorry, maybe-- PRESIDENT OBAMA: No, no, no, no, no, I think-- ERIC SCHMIDT: Li mhux it-- PRESIDENT OBAMA: I think, naħseb li l-bużżieqa sort tkun l-mod żbaljat biex imorru. ERIC SCHMIDT: Come on. Li qallu dan? KOLLOX SEW. I ma l-xjenza tal-kompjuter on-- 

PRESIDENT OBAMA: Imxejna ltqajna Spies tagħna fil hemmhekk. Professur: Kull dritt. Ejja jħallu warajhom us issa l dinja teoretiku ta 'algoritmi fl-analiżi asintotika tiegħu, u r-ritorn għal xi suġġetti minn ġimgħa żero u wieħed, u l-bidu li jitneħħew xi roti ta 'taħriġ, jekk inti se. Sabiex inti verament jifhmu finalment mill-art up, x'hemm għaddej taħt il-barnuża, meta inti jiktbu, jikkompilaw, u tesegwixxi programmi. Recall b'mod partikolari, li dan kien l-ewwel programm C ħarisna lejn, a, programm sempliċi canonical ta 'tipi, relattivament, fejn, prints, Hello World. U recall li għidt, il-proċess li source code tmur permezz huwa eżattament dan. Tieħu kodiċi sors tiegħek, jgħaddu permezz kompilatur, bħal Clang, u l jaqa object code, li tista 'tidher bħal dan, żerijiet u dawk li CPU tal-kompjuter, ċentrali ipproċessar unità jew moħħ, finalment jifhem. 

Jirriżulta li li l- daqsxejn ta oversimplification, li aħna qed issa fil- f'pożizzjoni li tease apparti biex jifhem dak li verament kien għaddej taħt il-barnuża kull darba li inti tmexxi Clang, jew b'mod iktar ġenerali, kull darba li inti tagħmel programm, użu Għamla u CF 50 IDE. B'mod partikolari, għalf bħal dan huwa l-ewwel ġġenerat, meta inti l-ewwel jikkompilaw program tiegħek. Fi kliem ieħor, meta inti tieħu kodiċi sors tiegħek u josservawha, x'hemm ewwel qed outputted mill Clang hija xi ħaġa magħrufa bħala kodiċi assemblea. U fil-fatt, jidher eżattament bħal dan. 

I dam kmand fil- linja ta 'kmand qabel. Kapital sing Clang s hello.c, u dan ħoloq fajl għalija imsejħa hello.s, ġewwa minnhom kienu eżattament dawn il-kontenuti, u aktar ftit hawn fuq u ftit aktar hawn taħt, imma stajt tpoġġi l-juiciest informazzjoni hawn fuq l-iskrin. U jekk inti tħares mill-qrib, tkun taf tara keywords familjari mill-inqas ftit. Għandna prinċipali fil-quċċata. Aħna printf fl-nofs. U għandna wkoll bonjour dinja backslash n fil-kwotazzjonijiet isfel hawn taħt. 

U kull ħaġa oħra fil hawn huwa istruzzjonijiet f'livell baxx ħafna li CPU tal-kompjuter jifhem. Istruzzjonijiet CPU li jiċċaqalqu memorja madwar, li kordi tagħbija mill-memorja, u finalment, jistampa affarijiet fuq l-iskrin. Issa x'jiġri għalkemm wara din il-kodiċi assemblaġġ huwa ġġenerat? Fl-aħħarnett, inti tagħmel, tabilħaqq, xorta jiġġeneraw object code. Iżda l-passi li għandhom verament ilu għaddej taħt il-barnuża tfittex ftit aktar bħal dan. Kodiċi tas-sors isir kodiċi assemblaġġ, li mbagħad isir object code, u l-kliem operattiva hawnhekk huma li, meta inti tiġbor kodiċi sors tiegħek, out taqa kodiċi assemblaġġ, u mbagħad meta inti tiġbor kodiċi assemblaġġ tiegħek, out taqa object code. 

Issa Clang huwa super sofistikati, simili ħafna ta 'kompilaturi, u dan ma kollha ta 'dawn il-passi flimkien, u għaliex mhux neċessarjament output kwalunkwe intermedjarja fajls li inti tista 'anki tara. Hija biss jikkompila affarijiet, li huwa t-terminu ġenerali li jiddeskrivi dan il-proċess kollu. Imma jekk int verament tixtieq li jkun partikulari, hemm ħafna aktar għaddejjin hemmhekk ukoll. 

Imma ejja jikkunsidraw ukoll issa li anke dak il-programm super sempliċi, hello.c, imsejħa funzjoni. Huwa sejjaħ printf. Imma jien ma jiktbu printf, tabilħaqq, li jiġi ma ċ, biex ngħidu hekk. Huwa irtirar funzjoni li l- iddikjarat io.h standard, li huwa fajl header, li huwa suġġett aħna ser fil-fatt adsa fis f'aktar dettal qabel ma twil. Iżda fajl header hija tipikament akkumpanjat minn fajl kodiċi, fajl source code, hekk ferm simili teżisti io.h. standard 

F'xi ilu, xi ħadd, jew someones, kiteb ukoll fajl imsejjaħ io.c standard, fil li d-definizzjonijiet attwali, jew implimentazzjonijiet ta printf, u għenieqed ta 'funzjonijiet oħra, huma attwalment miktuba. Allura peress li, jekk wieħed jikkunsidra li hawn fuq il-, hello.c xellug, li meta ikkumpilata, jagħtina hello.s, anki jekk Clang ma jolqot iffrankar fil-post nistgħu naraw dan, u dan il-kodiċi assemblaġġ gets mmuntati fi hello.o, li huwa, tabilħaqq, l-isem default mogħtija kull meta inti tiġbor sors kodiċi fis object code, iżda mhumiex pjuttost lesta li teżegwixxi encore, minħabba pass ieħor għandu jiġri, u għandha kien jiġri għall-aħħar ftit ġimgħat, forsi unbeknownst lilek. 

Speċifikament x'imkien fil CS50 IDE, u dan, wisq, se tkun daqsxejn ta ' oversimplification għal mument, hemm, jew kien fuq żmien, fajl imsejjaħ io.c standard, li xi ħadd ikkumpilata fis io.s standard jew l-ekwivalenti, li xi ħadd allura immuntati fis io.o standard, jew jirriżulta fi fajl kemmxejn differenti f'format li jista 'jkollhom differenti fajl estensjoni għal kollox, iżda fit-teorija u kunċettwali, eżattament dawk il-passi kellhom jiġri f'xi forma. Li jfisser, li issa meta jien kitba ta 'programm, hello.c, li biss jgħid, bonjour dinja, u jien jużaw kodiċi xi ħadd ieħor bħal printf, li darba kien fuq time, fil-fajl imsejħa io.c standard, imbagħad b'xi I għandhom jieħdu tiegħi object code, żerijiet tiegħi u dawk, u l-għan tal-persuna kodiċi, jew żero u dawk, u b'xi mod torbothom flimkien fi fajl wieħed finali, imsejħa hello, li għandu l-żerijiet u dawk mill-funzjoni prinċipali tiegħi, u kollha ta 'l-żerijiet u dawk għall-printf. 

U fil-fatt, dan il-proċess l-aħħar huwa imsejħa, li jgħaqqdu kodiċi ta 'oġġett tiegħek. L-produzzjoni tagħhom huwa fajl eżekutibbli. Għalhekk fl-ekwità, fil- aħħar tal-ġurnata, xejn inbidlet mill ġimgħa, meta aħna ewwel beda kumpilazzjoni programmi. Tabilħaqq, dan kollu kien jiġri taħt il-barnuża, iżda issa aħna qed f'pożizzjoni fejn nistgħu attwalment tease apparti dawn il-passi varji. U fil-fatt, fl-aħħar tal-ġurnata, aħna qed għadhom xellug b'żero u dawk li huwa attwalment segue kbir issa għall-kapaċità oħra ta 'C, li konna ma kellhom lieva aktar probabbli sal-lum, magħrufa bħala operaturi bitwise. Fi kliem ieħor, s'issa, f'kull waqt konna ttrattati bid-data fi C jew varjabbli fis-C, aħna kellna affarijiet simili Chars u sufruni u ins u twal u doubles u simili, iżda kollha ta 'dawn huma mill-inqas tmien bits. Imxejna qatt għadu jista jimmanipulaw bits individwali, anki jekk daqsxejn individwali, aħna jafu, jista 'jirrappreżenta 0 u 1. Issa jirriżulta li fis-C, inti jistgħu jiksbu aċċess għall-bits individwali, jekk inti taf l-sintassi, li biex tikseb għalihom. 

Mela ejja tagħti ħarsa fil operaturi bitwise. Allura isaffru hawn huma simboli ftit li konna, tip ta ', tip ta', rajna qabel. Nara ampersand, vertikali bar, u xi oħrajn kif ukoll, u jfakkru li ampersand ampersand hija xi ħaġa rajna qabel. L-operatur loġiku U, fejn inti għandek tnejn minnhom flimkien, jew il-loġika OR operatur, fejn inti għandhom żewġ bars vertikali. Operaturi bitwise, li aħna ser tara joperaw fuq bits individwalment, biss użu ampersand waħda, bar vertikali waħda, is-simbolu caret li jmiss tidħol, il-ftit tilde, u mbagħad titħalla parentesi xellug parentesi, jew bracket dritt bracket dritt. Kull wieħed minn dawn għandhom tifsiriet differenti. 

Fil-fatt, ejja tagħti ħarsa. Ejja ħa mmorru l-iskola antika llum, u l-użu touch screen mill-imgħoddi, magħrufa bħala bord abjad. U dan il-bord abjad se jippermettilna naslu li jesprimu xi simboli pjuttost sempliċi, jew pjuttost xi formuli pjuttost sempliċi, li nistgħu mbagħad finalment ingranaġġ, sabiex għall-aċċess individwali bits fi ħdan programm C. Fi kliem ieħor, ejja tagħmel dan. Ejja ewwel talk għal mument dwar ampersand, li hija l-bitwise U operatur. Fi kliem ieħor, dan huwa operatur li jippermetti me li jkollhom varjabbli fuq ix-xellug tipikament, u varjabbli tal-lemin, jew valur individwali, li jekk aħna U flimkien, tagħti me riżultat finali. Allura dak li għandi jfisser? Jekk fi programm, għandek varjabbli li l-ħażniet waħda minn dawn il-valuri, jew ejja jżommha sempliċi, u biss jiktbu l żerijiet u dawk individwalment, hawnhekk kif l-operatur ampersand xogħlijiet. 0 ampersand 0 se ugwali 0. Issa għaliex huwa li? 

Dan huwa simili ħafna għal Espressjonijiet Boolean, li konna diskussi s'issa. Jekk taħseb wara kollox, il 0 hija falza, 0 hija falza, foloz u foloz huwa, kif konna diskussi loġikament, ukoll falza. Allura aħna nikseb 0 hawnhekk ukoll. Jekk tieħu 0 ampersand 1, sew li, wisq, se jkun 0, għaliex għal dan espressjoni tan-naħa tax-xellug biex ikunu vera jew 1, ikun jeħtieġ li jkun veru u vera. Iżda hawnhekk għandna falza u vera, jew 0 u 1. Issa mill-ġdid, jekk ikollna 1 ampersand 0, dan, wisq, se jkun 0, u jekk ikollna 1 ampersand 1, finalment do għandna 1 bit. Allura fi kliem ieħor, aħna mhux qed isir xejn interessanti ma 'dan l-operatur għadha biss, dan l-operatur ampersand. Hu l-bitwise U operatur. Iżda dawn huma l-ingredjenti li permezz tagħhom nistgħu nagħmlu affarijiet interessanti, kif aħna ser dalwaqt tara. 

Issa ejja nħarsu lejn biss l-uniku bar vertikali minn hawn fuq il-lemin. Jekk ikolli 0 daqsxejn u I Jew ma ', l bitwise JEW operatur, 0 bit ieħor, li għaddej biex jagħti me 0. Jekk I tieħu 0 daqsxejn u OR ma ta '1 bit, allura jien ser tikseb 1. U fil-fatt, biss għall ċarezza, let me jmorru lura, sabiex bars vertikali tiegħi mhumiex żbaljata għal 1 s. Let me jikteb kollha ta ' my 1 l-ftit aktar b'mod ċar, sabiex inkunu jmiss tara, jekk I jkunu ta '1 JEW 0, li għaddej biex tkun ta' 1, u jekk ikolli 1 JEW 1 li, wisq, se tkun ta '1. Allura tista 'tara loġikament li l-OR operatur iġib ruħu b'mod differenti ħafna. Dan jagħti me 0 JEW 0 tagħti me 0, iżda kull kombinazzjoni oħra tagħti me 1. Sakemm I jkollhom waħda 1 fil- formula, ir-riżultat se tkun 1. 

B'kuntrast mal-U operatur, il ampersand, biss jekk Għandi żewġ 1 fil- ekwazzjoni, nista attwalment nikseb out 1. Issa hemm ieħor ftit operaturi kif ukoll. Waħda minnhom hija ftit aktar involuti. So let me jimxi 'l quddiem u tħassar dan biex tillibera xi spazju. U ejja tagħti ħarsa lejn l- simbolu caret, għal ftit mument. Dan huwa tipikament karattru inti tista tip fuq Shift azjenda tastiera tiegħek u mbagħad wieħed mill-numri atop Istati Uniti tiegħek keyboard. 

Allura dan huwa l esklussiva JEW operatur, esklussiv JEW. Allura aħna biss raw l-operatur OR. Dan huwa operatur l esklussiv JEW. X'hemm fil-fatt id-differenza? Well ejja biss ħarsa lejn il-formula, u jużaw dan bħala ingredjenti fl-aħħar. 0 XOR 0. Jien se ngħid huwa dejjem 0. Dik hija d-definizzjoni ta XOR. 0 XOR 1 se tkun 1. 1 XOR 0 se jkun 1, u 1 XOR 1 se tkun? Wrong? Jew id-dritt? I do not know. 0. Issa dak li qed jiġri hawn? Ukoll jaħsbu dwar il- isem ta 'dan l-operatur. Esklussiva JEW, sabiex il- isem, it-tip ta ', jissuġġerixxi, it-tweġiba hija biss ser tkun a 1 jekk l-inputs huma esklussivi, esklussivament differenti. Allura hawnhekk l-inputs huma l- istess, sabiex il-produzzjoni hija ta '0. Hawn l-inputs huma l- istess, sabiex il-produzzjoni hija ta '0. Hawn huma l-outputs huma differenti, dawn huma esklussivi, u għalhekk l-output huwa 1. Allura huwa simili ħafna għall U, huwa simili ħafna, jew pjuttost huwa simili ħafna għall JEW, iżda biss b'mod esklussiv. Dan huwa wieħed m'għadux 1, għaliex għandna żewġ 1, il u mhux esklużivament, biss wieħed minnhom. Kull dritt. Xi ngħidu dwar l-oħrajn? Ukoll l-tilde, sadanittant, hija attwalment sbieħ u sempliċi, Thankfully. U dan huwa unary operatur, li jfisser huwa applikat għall-input wieħed biss, operand wieħed, biex ngħidu hekk. Mhux għal xellug u dritt. Fi kliem ieħor, jekk inti tieħu tilde ta 0, ir-risposta se tkun l-oppost. U jekk inti tieħu tilde ta '1, il- tweġiba se jkun hemm l-oppost. Allura l-operatur tilde hija mod ta 'ċaħdu daqsxejn, jew flipping daqsxejn minn 0-1, jew 1-0. 

U li l-weraq us finalment bil biss żewġ operaturi finali, l-hekk imsejħa shift xellug, u l- hekk imsejħa operatur shift dritt. Ejja tagħti ħarsa lejn kif dawn ix-xogħol. L-operatur shift xellug, miktuba b'żewġ parentesi angolu bħal dak, topera kif ġej. Jekk input tiegħi, jew operand tiegħi, lejn ix-xellug operatur shift hija sempliċament 1. U I imbagħad tgħid il-kompjuter li xellug shift li 1, jgħidu seba postijiet, ir-riżultat huwa bħallikieku I jieħdu dik 1, u jġorrhom seba postijiet fuq l- xellug, u awtomatikament, aħna qed tmur biex wieħed jassumi li l-ispazju fuq il-lemin se tkun padded b'żero. Fi kliem ieħor, 1 ħallew shift 7 va li tagħti me dak 1, segwit minn 1, 2, 3, 4, 5, 6, 7 żerijiet. Dan b'mod, li jippermettilek li tieħu numru żgħir bħal 1, u b'mod ċar jagħmilha ferm ħafna, ħafna akbar b'dan il-mod, imma aħna qed attwalment għaddejjin biex tara approċċi aktar għaqlija għal dan minflok, kif ukoll, 

Kull dritt. Li lilha għall tliet ġimgħat. Aħna se tara inti ħin li jmiss. Dan kien CS50. 

[Daqq tal-mużika] 

SPEAKER 1: Hu kien fil-snack bar tiekol fudge hot sundae. Huwa kellu dan kollu fuq wiċċu. Hu ilbies li ċikkulata bħal beard SPEAKER 2: X'Ser tagħmel? SPEAKER 3: Hmmm? Xiex? 

SPEAKER 2: Ridt biss dip doppja? Inti double dipped-ċippa. SPEAKER 3: Skuża me. SPEAKER 2: Inti dipped-ċippa, inti ħa gidma, u inti dipped-ġdid. SPEAKER 3: SPEAKER 2: Allura dak hu simili tqegħid dritt tiegħek ħalq sħiħa fil-dip. Next time inti tieħu chip, biss dip darba, u t-tmiem dan. 

SPEAKER 3: Inti taf liema, Dan? Inti dip-mod li inti tixtieq li dip. I ser dip l-mod li nixtieq li dip.