>> [Muzika]
>> PROFESORI: Në rregull.
Kjo është CS50 dhe kjo është fundi i javës së tretë.
Pra, ne jemi sot këtu, jo në Sanders Teatri, në vend të kësaj në Weidner Bibliotekën.
Brenda e cila është një studio i njohur si Hauser Studio,
apo do të themi Studio H, apo duhet të ne say-- Nëse ju ka gëzuar këtë shaka,
është e vërtetë nga shok klase, Mark, online,
i cili sugjeroi sa më shumë nëpërmjet Twitter.
Tani çfarë është e ftohtë në lidhje qenë këtu në një studio
është se unë jam e rrethuar nga këto jeshile muret, një ekran të gjelbër ose chromakey,
kështu që të flasin, që do të thotë se CS50-së ekipi i prodhimit, unbeknownst për mua
tani, mund të jetë duke mua më kudo në botë,
për mirë apo për keq.
>> Tani çfarë shtrihet përpara, problemi vendosur dy është në duart tuaja për këtë javë,
por me problemin e ngritur tri këtë javë që vjen,
ju do të sfidohet me e ashtuquajtura lojë e 15,
një favor të vjetër parti që ju mund të kujtojnë marrjen
si një fëmijë që ka një bandë e tërë e numrave që mund të rrëshqitje lart, poshtë,
majtë dhe të djathtë, dhe ka një hendek brenda enigmës, në të cilën ju
në fakt mund të rrëshqas ato copa mister.
Në fund të fundit ju merrni këtë mister në një mënyrë gjysmë të rastit,
dhe qëllimi është për të zgjidhur atë, lartë deri në fund,
majta në të djathtë, nga një të gjithë rrugën deri me 15.
>> Për fat të keq, zbatimi ju do të keni në dorë
do të jetë software bazuar, jo fizikisht.
Ju jeni të vërtetë do të ketë për të shkruar Kodi me të cilin një student ose përdorues mund të
luajnë lojë e 15.
Dhe në fakt, në hacker botim i lojës së 15,
ju do të jetë një sfidë për të zbatuar, jo vetëm duke luajtur e kësaj shkolle të vjetër
lojë, por zgjidhja e saj, zbatimin mënyrën zot,
kështu që të flasin, që në fakt zgjidh mister për të njeriut,
duke u ofruar atyre me aluzion, pas aluzion, pas aluzion.
Pra, më shumë në atë javën e ardhshme.
Por kjo është ajo që shtrihet përpara.
>> Tani për tani kujtojmë se më herët këtë javë kemi pasur këtë cliffhanger, në qoftë se ju do të,
ku më të mirë ne ishim duke bërë klasifikim i urtë ishte një kufi i sipërm i madh o të n
katror.
Me fjalë të tjera, flluskë lloj, lloj përzgjedhje, futje lloj,
të gjitha prej tyre, ndërsa të ndryshme në zbatimin e tyre,
transferuar në një n katror drejtimin kohë në rastin më të keq.
Dhe ne përgjithësi të supozojmë se rastin më të keq për klasifikim
është ai që inputeve tuaj janë krejtësisht prapa.
Dhe me të vërtetë, ai mori mjaft disa hapa për të zbatuar secili prej këtyre algoritmeve.
>> Tani në fund të klasës së Recall, ne krahasim flluskë lloj
kundër lloj përzgjedhjes kundër një tjetër që ne e quajti lloj bashkojë në atë kohë,
dhe unë propozoj që ajo është duke marrë Përparësia e një mësim nga javë
zero, përça dhe sundo.
Dhe disi arritjen e disa lloj logaritmike running kohë në fund të fundit,
në vend të diçka kjo është thjesht katror.
Dhe kjo nuk është mjaft logaritmike, kjo është pak më shumë se kaq.
Por nëse ju kujtohet nga klasa, ajo ishte shumë, shumë më të shpejtë.
Le të bëjmë një vështrim në ku ne u ndërpre.
>> Bubble lloj kundrejt përzgjedhjes lloj kundrejt merge lloji.
Tani ata janë të gjithë në punë, në teori, në të njëjtën kohë.
CPU po kandidon në të njëjtën shpejtësi.
Por ju mund të ndjeheni si i mërzitshëm ky po shumë shpejt do të bëhet,
dhe se sa shpejt, kur kemi të injektuar pak e algoritme të javës zero-së,
mund të shpejtojë gjërat.
>> Kështu lloj shenjë duket e mahnitshme.
Si mund të levave atë, në mënyrë që për të zgjidhur numra më shpejt.
E pra, le të mendoj se mbrapa për një përbërës që
kishte mbrapa në javën zero, që i kërkim për dikë në një libër telefoni,
dhe kujtojnë se pseudokod që kemi propozuar,
nëpërmjet të cilës ne mund të gjeni dikush si Mike Smith,
dukej një diçka të vogël si kjo.
>> Tani të marrë një sy në veçanti në përputhje 7 dhe 8, dhe 10 dhe 11,
të cilat shkaktojnë këtë lak, me të cilin ne kemi mbajtur duke shkuar prapa në linjë 3 përsëri, dhe përsëri,
dhe përsëri.
Por kjo rezulton se ne mund të shikoni ky algoritëm, këtu në pseudokod,
pak më shumë në mënyrë holistike.
Në fakt, ajo që unë jam duke kërkuar në këtu në ekran,
është një algoritmi për kërkim të Mike Smith në mesin e një sërë faqesh.
Dhe me të vërtetë, ne mund të thjeshtojë këtë algorithm në ato linja 7 dhe 8,
dhe 10 dhe 11 të them vetëm këtë, që unë kam paraqitur këtu në të verdhë.
Me fjalë të tjera, në qoftë se Mike Smith është parë në libër,
ne nuk kemi nevojë të specifikojë hap hapi tani se si të shkojë gjetur atë.
Ne nuk duhet të specifikojë për të shkuar mbrapa në linjë 3,
Pse nuk kemi vetëm në vend të kësaj, të themi, më në përgjithësi,
kërkoni për Mike në gjysma e majtë e librit.
>> Në anën tjetër, nëse është Mike në fakt më vonë në libër,
pse nuk kemi vetëm të japin kuotën kërkimin siç janë quajtur ato për Mike në gjysmën e djathtë të librit.
Me fjalë të tjera, pse nuk e bëjmë ne vetëm lloj i vë bast për veten duke i thënë:
kërkoni për Mike në këtë mesin e librit,
dhe të lënë atë për ekzistuese tonë algorithm për të na tregoni
si për të kërkuar për Mike në se gjysma e majtë e librit.
Me fjalë të tjera, tonë algorithm punon nëse kjo është
një libër telefon i këtij trashësi, e kjo trashësi, ose ndonjë trashësi whatsoever.
Pra, ne mund Recursively përcaktojnë këtë algorithm.
Me fjalë të tjera, mbi ekran këtu, është një algoritëm
për kërkim për Mike Smith ndër faqet e një libri të telefonit.
Pra, në përputhje 7 dhe 10, le të vetëm të them saktësisht se.
Dhe unë e përdorin këtë term një moment më parë, dhe në të vërtetë, recursion
është buzzword për tani, dhe kjo është ky proces
të bërë diçka ciklike nga disi duke përdorur kodin që ju tashmë e keni,
dhe duke e quajtur atë përsëri, dhe përsëri, dhe përsëri.
Tani ajo do të jetë e rëndësishme se ne disi fund
jashtë, dhe nuk e bëjmë atë pafundësisht të gjatë.
Përndryshe ne do të kanë me të vërtetë një lak pafund.
Por le të shohim nëse ne mund të marrë hua këtë ide e një recursion, duke bërë diçka përsëri
dhe përsëri dhe përsëri, për të zgjidhur problemi sorting nëpërmjet bashkohen
lloj, të gjithë më efikase.
>> Kështu që unë ju jap bashkojë lloj.
Le të marrin një vështrim.
Kështu që këtu është pseudokod, me të cilat ne mund të zbatojë klasifikim,
duke përdorur këtë algoritëm të quajtur bashkojë lloj.
Dhe kjo është mjaft e thjesht kjo.
Në të dhënat e elementeve n, me fjalë të tjera, në qoftë se ju jeni
duke pasur parasysh n elemente dhe numrat dhe letra ose çfarëdo input është,
në qoftë se ju jeni duke i dhënë elementet n, nëse n është më pak se 2, vetëm kthehen.
E drejtë?
Sepse nëse n është më pak se 2, që do të thotë se lista ime e elementeve
ose është i madhësisë 0 ose 1, dhe në të dy këto raste të parëndësishme,
lista është renditur tashmë.
Nëse nuk ka lista, është e renditura.
Dhe në qoftë se ka një listë të gjatësisë 1, është e renditura qartë.
Pra, algoritmi ka nevojë vetëm për të me të vërtetë të bëjë diçka interesante,
në qoftë se ne kemi dy ose më shumë Elementet e dhënë për të na.
Pra, le të shohim në magji pastaj.
Tjetër lloj gjysmën e majtë të elementeve, pastaj lloj gjysmën e djathtë të elementeve,
pastaj bashkojë gjysmave renditur.
Dhe çfarë është lloj i mendjes bending këtu, është se unë nuk të vërtetë
duket se kanë thënë çdo gjë vetëm ende, e drejtë?
Të gjitha unë kam thënë po, jepet një listë të Elementet n, lloj gjysmën e majtë,
atëherë gjysma e drejtë, atëherë bashkojë gjysmave të renditura,
por ku është prevede aktual sekret?
Ku është algoritmi?
E pra kjo rezulton se këto dy linja së pari, u largua lloj gjysma e elementeve,
dhe lloj të drejtën gjysmën e elementeve, thirrje gjithkund rekursive, kështu që të flasin.
>> Pas të gjitha, në këtë pikë në kohë, nuk kam
një algoritmi me të cilin do të zgjidhur një bandë e tërë e elementeve?
Po.
Kjo është e drejtë këtu.
Kjo është e drejtë këtu në ekran, dhe kështu që unë mund të përdorni atë grup të njëjtë të hapave
për të zgjidhur gjysmën e majtë, si unë mund gjysma e drejtë.
Dhe me të vërtetë, përsëri, dhe përsëri.
Pra, në njëfarë mënyre apo tjetër, dhe ne do të së shpejti shihni këtë, magjinë e merge lloj
është ngulitur në se shumë finale line, bashkimi gjysmave të renditura.
Dhe kjo duket mjaft intuitiv.
Ju merrni dy gjysmave, dhe ju, disi, bashkojë ato së bashku,
dhe ne do të shohim këtë konkretisht në një moment.
>> Por kjo është një algoritëm i plotë.
Dhe le të shohim saktësisht pse.
Pra mendoj se ne jemi duke i dhënë këto njëjtë tetë elemente këtu në ekran, një
nëpërmjet tetë, por ata janë në mënyrë që në dukje të rastit.
Dhe qëllimi në fjalë është për të zgjidhur këto elemente.
Mirë se si mund të shkoj në lidhje me bërë atë duke përdorur, përsëri,
shkrihen lloj, sipas këtij pseudokod?
Dhe përsëri, ngjyer këtë në mendjen tuaj, për vetëm një moment.
Rasti i parë është shumë e i parëndësishëm, në qoftë se ajo është më pak se 2,
vetëm të kthehet, nuk ka punë për t'u bërë.
Pra, me të vërtetë ka vetëm tre hapa për të vërtetë të mbajtur në mendje.
Përsëri, dhe përsëri, unë jam do të duan të kenë
për të zgjidhur gjysmën e majtë, lloj gjysmën e djathtë,
dhe pastaj një herë e tyre dy gjysmat janë të renditura,
Unë dua të bashkojë ata së bashku në një listë të rradhitur.
Pra, mbani në mend.
>> Kështu që këtu është lista origjinale.
Le të trajtojnë këtë si një array, pasi kemi filluar të
në javë dy, e cila është një bllok puqur e kujtesës.
Në këtë rast, që përmban tetë numra, për të kthyer prapa në shpinë.
Dhe tani le të aplikojnë bashkojë lloj.
Kështu që unë së pari dua të lloj gjysmën e majtë të kësaj liste,
dhe le të, prandaj, përqëndrohet në 4, 8, 6, dhe 2.
>> Tani si mund të shkoni në lidhje me klasifikim një listë të madhësisë 4?
E pra unë duhet të marrin në konsideratë tani klasifikim të majtë të pjesës së majtë.
Përsëri, le të Rewind për vetëm një moment.
Nëse pseudokod është kjo, dhe unë jam duke i dhënë tetë elemente,
8 është padyshim më e madhe se ose e barabartë me 2.
Pra, me rasti i parë nuk zbatohet.
Pra, për të zgjidhur tetë elemente, unë së pari lloj gjysmën e majtë të elementeve,
atëherë unë lloj gjysmën e duhur, atëherë unë bashkojë të dy gjysmat renditura, secila me madhësi 4.
NE RREGULL.
>> Por në qoftë se ju keni më tha vetëm, të lloj gjysma e majtë, e cila tani është e madhësisë 4,
si mund ta zgjidhur gjysmën e majtë?
E pra, nëse unë kam një të dhëna të katër elementeve,
Unë së pari lloj majtë dy, atëherë e drejta e dy,
dhe pastaj unë bashkojë ato së bashku.
Pra, përsëri, kjo bëhet pak e një mendje lojë lakimi këtu,
sepse ti, lloj, duhet të mbani mend se ku je në histori,
por në fund të ditës, dhënë ndonjë numër të elementeve,
ju së pari doni të lloj gjysma e majtë, atëherë gjysma e drejtë,
pastaj bashkojë ato së bashku.
Le të fillojë për të bërë pikërisht atë.
Ja input i tetë elementeve.
Tani ne jemi duke kërkuar në gjysmën e majtë këtu.
Si mund të zgjidhur katër elemente?
Edhe unë së pari zgjidhur gjysmën e majtë.
Tani si mund ta zgjidhur gjysmën e majtë?
E pra unë kam qenë dhënë dy elemente.
Pra, le të zgjidhur këto dy elemente.
2 është më e madhe se ose e e barabartë me 2, sigurisht.
Kështu që rasti i parë nuk zbatohet.
>> Kështu që unë tani keni për të zgjidhur majtë gjysma e këtyre dy elementeve.
Gjysmën e majtë, natyrisht, është vetëm 4.
Pra, si mund unë të zgjidhur një listë të një elementi?
E pra tani, se rasti i veçantë bazë deri të lartë, kështu që të flasin, vlen.
1 është më pak se 2, dhe kur Lista është me të vërtetë e madhësisë 1.
Kështu që unë vetëm të kthehen.
Unë nuk bëj asgjë.
Dhe me të vërtetë, të shikojmë se çfarë kam bërë, 4 është renditur tashmë.
Ashtu si unë jam tashmë pjesërisht i suksesshëm këtu.
>> Tani që duket lloj i trashë për të kërkuar, por është e vërtetë.
4 është një listë e madhësisë 1.
Është renditura tashmë.
Kjo është gjysma e majtë.
Tani unë lloj gjysmën e djathtë.
Input ime është një element, 8 Në mënyrë të ngjashme, të renditura tashmë.
Stupid, gjithashtu, por përsëri, ky parim themelor
do të na lejojë të ndërtojmë tani në krye të kësaj sukses.
4 renditura, 8 është e renditura, tani çfarë ishte se hapi i fundit?
Pra, hapi i tretë dhe i fundit, çdo herë ju jeni klasifikim një listë, risjell,
ishte që të bashkojë dy gjysmave, majtas dhe djathtas.
Pra, le të bëjë pikërisht këtë.
Gjysma ime e majtë është, natyrisht, 4.
Gjysma ime e drejtë është 8.
>> Pra, le ta bëjmë këtë.
Së pari unë jam duke shkuar për të alokuar disa kujtesës shtesë,
që unë do të përfaqësoj këtu, si vetëm një grup të mesme,
kjo është mjaft e madhe për të përshtaten këtë.
Por ju mund të imagjinoni shtrirë se drejtkëndësh të gjithë gjatësinë,
në qoftë se ne kemi nevojë për më vonë.
Si mund ta marrë 4 dhe 8, dhe shkrihen këto dy listat e madhësisë 1 së bashku?
Këtu, gjithashtu, shumë e thjeshtë.
4 vjen e para, pastaj vjen 8.
Sepse në qoftë se unë dua të të lloj gjysma e majtë, atëherë gjysma e drejtë,
dhe pastaj bashkojë këto dy gjysmave së bashku në mënyrë renditura,
4 vjen e para, pastaj vjen 8.
>> Pra, ne duket të jetë bërë përparim, madje edhe pse unë nuk kam bërë ndonjë punë aktuale.
Por mos harroni se ku jemi në histori.
Ne fillimisht mori tetë elemente.
Ne renditura gjysmën e majtë, e cila është 4.
Pastaj ne të renditura gjysmën e majtë e pjesës së majtë, e cila ishte 2.
Dhe këtu ne do të shkojmë.
Ne jemi duke bërë me këtë hap.
>> Pra, nëse ne kemi renditur la gjysmën e 2, tani ne
kanë për të zgjidhur gjysmën e djathtë të 2.
Pra, gjysma e drejta e 2 është këto dy vlera këtu, 6 dhe 2.
Pra, le të marrë tani një kontribut të madhësisë 2, dhe lloj gjysmën e majtë, dhe pastaj
gjysma e drejtë, dhe pastaj bashkojë ato së bashku.
Pra si mund të zgjidhur një listë të madhësisë 1, që përmban vetëm numrin 6?
Unë jam bërë tashmë.
Kjo listë e madhësisë 1 është e renditura.
>> Si mund të zgjidhur një listë të madhësia 1, e ashtuquajtura gjysmë e drejtë.
E pra kjo, gjithashtu, është e renditura tashmë.
Numri 2 është e vetme.
Deri tani unë kam dy gjysmave, majtas dhe e drejtë, unë duhet të bashkojë ato së bashku.
Më lejoni të jap vetes një hapësirë ​​ekstra.
Dhe të vënë 2 në atje, pastaj 6 në atje, duke
sorting se lista, majtas dhe djathtas, dhe bashkimi atë së bashku, në fund të fundit.
Kështu që unë jam në formë pak më të mirë.
Unë nuk jam bërë, për shkak se në mënyrë të qartë 4, 8, 2, 6 nuk është urdhëruar fundit që unë dua.
Por unë tani kanë dy listave të madhësisë 2, që kanë të dy, përkatësisht, janë të renditura.
Kështu që tani, nëse ju Rewind në mendjen e juaj sy, ku bëri që na lënë?
Unë fillova me tetë elemente, atëherë unë whittled atë poshtë për gjysmën e majtë të 4,
atëherë gjysma e majtë e 2, dhe atëherë gjysma e drejta e 2,
Kam mbaruar, pra, zgjidhja e majtë gjysma e 2, dhe gjysma e drejta e 2,
kështu që çfarë është hapi i tretë dhe i fundit këtu?
Unë duhet të bashkojë së bashku dy lista të madhësisë 2.
Pra, le të shkojë përpara.
Dhe në ekran këtu, japin mua disa kujtesës shtesë,
edhe pse teknikisht, vëreni se unë kam mori një bandë e tërë e hapësirës deri bosh krye
atje.
Nëse unë dua të jetë veçanërisht hapësirë ​​efikas i mençur,
Unë mund vetëm të fillojnë të lëvizin elementet mbrapa dhe me radhë, lartë dhe në fund.
Por vetëm për qartësi vizuale, Unë jam duke shkuar për ta vënë atë poshtë,
për të mbajtur gjërat bukur dhe të pastër.
>> Kështu që unë kam marrë dy listave të madhësisë 2.
Lista e parë ka 4 dhe 8.
Lista e dytë ka 2 dhe 6.
Le të bashkojë ato së bashku në mënyrë renditura.
2, natyrisht, vjen e para, atëherë 4, pastaj 6, pastaj 8.
Dhe tani ne duket të jenë marrë diku interesante.
Gjysmë tani unë kam renditura nga lista, dhe rastësisht, kjo është
të gjitha edhe numrat, por kjo është, me të vërtetë, vetëm një rastësi.
Dhe unë tani kam renditura majtë gjysmë, kështu që është 2, 4, 6 dhe 8.
Asgjë nuk është jashtë rendit.
Që ndjehet si progres.
>> Tani ajo ndjehet si e kam qenë duke folur përgjithmonë tani,
kështu që ajo që mbetet për t'u parë nëse kjo algoritmi është, me të vërtetë, më efikase.
Por, ne jemi duke shkuar nëpër atë super metodike.
Një kompjuter, natyrisht, do ta bëjë atë si kjo.
Pra, ku jemi ne?
Ne kemi filluar me tetë elemente.
Unë renditura gjysmën e majtë të 4.
I duket për të bërë me atë.
Pra, tani hapi tjetër është për të lloj gjysmën e djathtë të 4.
Dhe kjo pjesë mund të shkojmë përmes një më të vogël
shpejt, edhe pse ju jeni mirëpritur të Rewind, ose pushim, vetëm
mendoj nëpërmjet saj në ritmin tuaj, por çfarë
ne kemi tani është një mundësi për bëjë të njëjtën algorithm saktë në katër
numra të ndryshëm.
>> Pra, le të shkojnë përpara, dhe të përqëndrohet në gjysma e drejta, të cilat ne jemi këtu.
Gjysma e majtë e që gjysmë të drejtë, dhe tani
gjysma e majtë të majtë gjysma e atij gjysmën e djathtë,
dhe si mund të zgjidhur një listë të madhësisë 1 që përmban vetëm numrin 1?
Është bërë tashmë.
Si mund ta bëjë të njëjtën gjë për një listë e madhësisë 1 përmban vetëm 7?
Është bërë tashmë.
Hapi i tretë për këtë gjysmë, atëherë është të bashkojë këto dy elemente
në një listë të re të madhësisë 2, 1 dhe 7.
Nuk duket të ketë bërë gjithçka Puna që shumë interesante.
Le të shohim se çfarë ndodh më pas.
Unë vetëm të renditura gjysmën e majtë të gjysma e djathtë e input tim origjinal.
Tani le të lloj të drejtën gjysmë, e cila përmban 5 dhe 3.
Le të shikojmë përsëri në të majtë gjysmë, të renditura, gjysmë e drejtë, të renditura,
dhe bashkojë ata të dy së ​​bashku, në një hapësirë ​​shtesë,
3 vjen e para, pastaj vjen 5.
Dhe kështu që tani, ne kemi të renditura gjysma e majtë të gjysmën e djathtë
e problemit origjinale, dhe gjysma e djathtë të pjesës së djathtë
e problemit origjinal.
Çfarë është hapi i tretë dhe të fundit?
E pra të bashkojë këto dy gjysmave së bashku.
Pra më lejoni të marrë veten disa hapësirë ​​shtesë, por, përsëri, unë
mund të jetë duke përdorur këtë hapësirë ​​deri rezervë lartë.
Por ne jemi duke shkuar për të mbajtur atë të thjeshtë me sy.
Më lejoni të bashkojë në tani 1, dhe atëherë 3, dhe pastaj 5, dhe më pas 7.
Duke i lënë mua tani me gjysma e drejtë e problemit origjinale
që është renditur në mënyrë të përkryer.
>> Pra, çfarë mbetet?
Ndjehem si unë mbaj duke thënë se njëjtat gjëra përsëri, dhe përsëri,
por kjo është reflektues i Fakti që ne jemi duke përdorur recursion.
Procesi i përdorimit të një algorithm përsëri, dhe përsëri,
në subsets të vogla të problemi fillestar.
Kështu që unë tani kam një të majtë të renditura gjysma e problemit origjinal.
Unë kam një gjysmë të drejtë renditura e problemit origjinal.
Cili është hapi i tretë dhe i fundit?
Oh, kjo është bashkimi.
Pra, le ta bëjmë atë.
Le të ndajë disa shtesë kujtesës, por Perëndia im, ne
mund të vënë atë kudo tani.
Ne kemi hapësirë ​​aq shumë në dispozicion për ne, por ne do të mbani atë të thjeshtë.
Në vend që të shkojnë prapa dhe radhë me kujtesën tonë origjinal,
le të vetëm të bëjë atë vizualisht poshtë këtu më poshtë,
të përfundojë bashkimin e gjysma e majtë dhe gjysma e drejtë.
>> Pra nga bashkimi, çfarë duhet të bëj?
Unë dua të të marrë elementet në rregull.
Pra, duke kërkuar në gjysmën e majtë, Unë shoh numri i parë është 2.
Unë shoh në gjysmën e djathtë, Unë shoh numrin e parë
është 1, në mënyrë të qartë cila Numri i bëjnë dua të këpusin jashtë,
dhe të vënë së pari në listën time të fundit?
Sigurisht, 1.
Tani unë dua të pyes këtë pyetje të njëjtën.
Në gjysmën e majtë, unë kam ende mori numrin 2.
Në pjesën e djathtë, Unë kam marrë numrin 3.
Cila një dua për të zgjedhur?
Sigurisht, numri 2 tani vini re kandidatët
janë 4 në të majtë, 3 në të djathtë.
Le të, natyrisht, të zgjedhin 3.
Tani kandidatët janë 4 në e majta, 5 në të djathtë.
Ne, natyrisht, të zgjedhin 4.
6 në të majtë, 5 në të djathtë.
Ne, natyrisht, të zgjedhin 5.
6 në të majtë, 7 në të djathtë.
Kemi zgjedhur 6, dhe pastaj ne zgjedh 7, dhe pastaj kemi zgjedhur 8.
Voila.
>> Pra, një numër i madh i fjalëve më vonë, ne kanë të renditura në këtë listë të tetë elementeve
në një listë të njërit nëpërmjet tetë, që është në rritje me çdo hap,
por sa kohë ka ajo na merr për të bërë këtë.
E pra unë kam qëllim gjëra të paraqitura në pikturë
këtu, në mënyrë që ne mund të lloj shohin ose të vlerësojmë ndarjen
në pushtues që është duke ndodhur.
>> Në të vërtetë në qoftë se ju shikoni mbrapa në prag, Unë e kam lënë të gjitha këto vija me pika
në mbajtësit vend, ju mund, lloj, shih, në mënyrë të kundërt,
në qoftë se ju lloj i shohim mbrapa në historia tani, lista ime origjinale
është, natyrisht, i madhësisë 8.
Dhe pastaj më parë, unë kam qenë që kanë të bëjnë me dy listave të madhësisë 4,
dhe pastaj katër listat e madhësisë 2, dhe pastaj tetë listat e madhësisë 1.
>> Pra, çfarë e bën këtë, lloj, ju kujtoj të?
E pra, në të vërtetë, asnjë nga algoritme ne kemi
shikuar deri më tani ku ne ndarje, dhe ndarje, dhe ndarja,
mbani duke pasur gjëra përsëri, dhe përsëri, rezulton në këtë ide të përgjithshme.
Dhe kështu që nuk është diçka logaritmike ndodh këtu.
Dhe kjo nuk është mjaft e log n, por ka një komponent logaritmike
për atë që ne kemi bërë vetëm.
>> Tani le të shqyrtojmë se si që në fakt është.
Pra, log i n, përsëri ishte një kohë e madhe running,
kur ne e bëmë diçka si kërko binar, si ne tani e quajmë atë,
strategjia Përça dhe sundo nëpërmjet të cilat kemi gjetur Mike Smith.
Tani teknikisht.
Kjo është bazë log 2 i n, madje edhe edhe pse në klasat më të madhe e matematikës,
10 zakonisht është baza që ju të marrë.
Por shkencëtarët kompjuterike pothuajse gjithmonë mendojnë dhe të flasin në drejtim të bazës 2,
kështu që ne në përgjithësi vetëm thonë regjistër të n, në vend të bazës log 2 n,
por ata janë pikërisht një dhe njëjtë në botën e kompjuterit
shkencë, dhe si një mënjanë, ka një faktor konstant
Diferenca midis të dyjave, kështu që është e Moot gjithsesi, për arsye më formale.
>> Por tani për tani, ajo që ne kujdesemi lidhje është ky shembull.
Pra, le të mos provojnë me shembullin, por në paktën të përdorni një shembull të numrave
në dorë si një kontroll mendje e shëndoshë, nëse ju do.
Kështu që më parë ishte formula bazë log 2 i n, por ajo që është n në këtë rast.
Unë kisha numrat n origjinale, ose 8 e numrit origjinale specifike.
Tani kjo është pak ndërsa, por unë jam goxha
i sigurt se baza log 2 e vlerës së 8 është 3,
dhe në të vërtetë, çfarë është e bukur për të cilat është se 3 është pikërisht numri i herë
që ju mund të ndajnë një listë e gjatësisë 8 përsëri, dhe përsëri,
dhe përsëri, derisa ju jeni mbetur me listat e vetëm madhësisë 1.
E drejtë?
8 shkon në 4, shkon në 2, shkon në 1, dhe kjo është
reflektuese e saktësisht se foto ne kishim vetëm një moment më parë.
Pra, një mendje e shëndoshë pak të kontrolluar se ku logaritmi është i përfshirë në të vërtetë.
>> Deri tani, çfarë tjetër është e përfshirë këtu? n.
Pra, vini re se çdo herë kam ndarë listën,
megjithëse në mënyrë të kundërt në histori këtu, unë isha ende duke bërë n gjëra.
Që hap bashkimi kërkonte që I prek çdo një nga numrat,
në mënyrë që të rrëshqitje atë në vendndodhjen e saj të përshtatshme.
Pra, edhe pse lartësia e kësaj diagram është i madhësisë log n e n ose 3,
në mënyrë specifike, me fjalë të tjera, Unë e bëri tre divizione këtu.
Sa punë e kam bërë horizontalisht së bashku këtë tabelë çdo kohë?
>> E pra, unë e bëri n hapat e punë, sepse në qoftë se unë kam
mori katër elementet dhe katër elemente, dhe kam nevojë për të bashkojë ato së bashku.
Unë duhet të kalojnë nëpër këto katër dhe këto katër,
në fund të fundit të bashkojë ato përsëri në tetë elemente.
Nëse anasjelltas Unë kam marrë tetë gishtat këtu, që unë nuk e bëjnë, dhe tetë
fingers-- sorry-- Nëse unë kam mori katër gishta gjatë këtu,
që unë bëj, katër gishtërinj këtu, që unë bëj,
atëherë kjo është e njëjtë shembull si më parë, në qoftë se unë bëj
kanë tetë gishtat edhe pse në totale, që unë mund të, lloj, të bëjë.
Unë mund të bëj pikërisht këtu, atëherë unë mund sigurisht
bashkojë të gjitha këto lista nga madhësia 1 së bashku.
Por unë me siguri duhet të shikoni në çdo element saktësisht një herë.
Pra, lartësia e këtij procesi është log n, gjerësia e këtij procesi, në mënyrë që të flasin,
është n, kështu që ajo që ne duket të ketë, në fund të fundit, është
një kohë running me madhësi n herë log n.
>> Me fjalë të tjera, ne të ndarë lista, log n herë,
por çdo herë ne e bëmë atë, ne kishim për të prekur çdo një nga elementet
në mënyrë që ato bashkohen të gjithë së bashku, e cila
ishte N hap, kështu që ne kemi n herë log n, ose siç do të thoshte një shkencëtar kompjuteri,
asymptotically, e cila do të jetë fjala e madhe
për të përshkruar pjesën e sipërme i lidhur në një kohë running,
ne do të vrapojnë në një o madhe i log n kohës, kështu që të flasin.
>> Tani kjo është e rëndësishme, sepse kujtojnë se çfarë kohët running ishin
with lloj flluskë, dhe përzgjedhjes lloj, dhe futje lloj,
dhe madje edhe disa të tjerë që ekzistojnë, n katror ishte vendi ku ishim ne.
Dhe ju mund të, lloj, shih këtë këtu.
Nëse n katror është padyshim n herë n, por këtu kemi n herë log n,
dhe ne tashmë e dimë që nga java e zero, që log n, The logaritmike,
është më mirë se diçka lineare.
Pas të gjitha, kujtojnë foto me të kuqe dhe të verdhë
dhe linjat e gjelbër që ne të aftë, The Linja jeshile logaritmike ishte shumë më e ulët.
Dhe për këtë arsye, shumë më mirë dhe më të shpejtë se vija e drejtë verdhë dhe të kuqe,
n herë log n është, me të vërtetë, më mirë se kohët e n n, ose n katror.
>> Pra, ne duket të ketë identifikuar një bashkohen algorithm
lloj që shkon në shumë kohë më të shpejtë, dhe në të vërtetë,
kjo është arsyeja pse, më parë këtë javë, kur ne pamë atë garë mes flluskë
lloj, lloj përzgjedhja, dhe shkrihen lloj, shkrihen lloj të vërtetë, fitoi me të vërtetë.
Dhe me të vërtetë, ne as nuk presim për lloj flluskë dhe përzgjedhjes lloj
te mbaroj.
>> Tani le të marrin një abone të tjera në këtë, nga një pak më shumë
Perspektiva formale, vetëm në rast, kjo rezonon mirë
se atë diskutim të nivelit më të lartë.
Kështu që këtu është algoritmi përsëri.
Le të pyesim veten, çfarë kohë running
është kjo algoritme hapat e ndryshëm?
Le të ndajnë atë në e parë rast dhe rasti i dytë.
If dhe tjetër në rast se, IF n është më pak se 2, vetëm kthehen.
Ndjehet si herë të vazhdueshme.
Kjo është, lloj, si dy hapa, IF n është më pak se 2, pastaj kthehen.
Por, siç thamë të hënën, kohë konstante apo të mëdha o të 1,
mund të jetë dy hapa, tre hapa, madje edhe 1.000 hapa.
Ajo që ka rëndësi është se kjo është një numër i vazhdueshëm i hapave.
Pra verdhë theksuar pseudokod këtu shkon në, ne do të thërrasë atë,
kohë konstante.
Pra më formalisht, dhe ne jemi duke shkuar to-- kjo
do të jetë shkalla në të cilën ne formalizuar këtë të drejtë now-- T i N,
koha drejtimin e një problemi që merr ca n si input,
barabartë i madh o nga një, IF n është më pak se 2.
Pra, kjo është kushtëzuar nga ajo.
Në mënyrë të qartë, IF n është më pak se 2, ne kemi një listë shumë të shkurtër, atëherë
koha drejtimin, T i n, ku n është 1 ose 0, në këtë rast shumë specifike,
ajo është vetëm do të jetë kohë konstante.
Ajo do të marrë një të tillë hap, dy hapa, çfarëdo.
Është një numër të caktuar të hapave.
>> Pra, pjesa me lëng me siguri duhet të jetë në Rasti tjetër në pseudokod.
Rasti tjetër.
Lloj gjysma e majtë e elementeve, lloj e drejtë gjysma e elementeve, të bashkohen gjysmave renditura.
Sa kohë secili prej këtyre hapave të marrë?
E pra, në qoftë se running kohë për të zgjidhur elementet n
është, le ta quajmë shumë generically, T i N,
atëherë zgjidhja e majtë gjysma e elementeve
është, lloj, si të thuash, T e n ndarë nga 2,
dhe në mënyrë të ngjashme klasifikim gjysmën e djathtë e elementeve është, lloj, si të thuash,
T e n ndarë 2, dhe pastaj bashkimi gjysmave renditur.
E pra, nëse unë kam marrë disa Numri i elementeve këtu,
si katër, dhe disa numrin e elementeve këtu, si katër,
dhe unë duhet të bashkojë secili prej këtyre katër në, dhe secili prej këtyre katër në, një
pas tjetrës, në mënyrë që në fund të fundit unë kam tetë elemente.
Ajo ndjehet si kjo është e madhe o të hapave n?
Nëse unë kam marrë n gishtat dhe secili prej ata duhet të bashkohen në vend,
kjo është si një tjetër hapa n.
>> Pra me të vërtetë formulaically, ne mund të shprehim këtë,
megjithëse një scarily pak në fillim shikim, por kjo është diçka
që kap pikërisht këtë logjikë.
Koha drejtimin, T i N, NËSE n është më e madhe se ose e barabartë me 2.
Në këtë rast, rasti tjetër është i T n ndarë nga 2, plus T i N ndarë nga 2,
plus i madh o të n, disa Numri linear i hapave,
ndoshta pikërisht n, ndoshta 2 herë n, por kjo është afërsisht, radha e n.
Kështu që, gjithashtu, është se si ne mund të shprehur kjo formulaically.
Tani ju nuk do të dinë këtë nëse ju keni regjistruar atë në mendjen tuaj,
apo të shikoni atë deri në prapa e një teksti, i cili
mund të ketë pak mashtrojnë fletë në fund,
por kjo është, me të vërtetë, do të na japin një i madh o të n log n,
sepse përsëritje që ju jeni duke parë këtu në ekran,
në qoftë se ju në të vërtetë e bëri atë, me një numër të pafund të shembujve,
ose ju e bëri atë formulaically, ju do të shihni se kjo, për shkak se këtë formulë
vetvete është gjithkund rekursive, me t e n mbi diçka nga e djathta,
dhe t i n e majta, kjo mund të në fakt të shprehet, në fund të fundit,
Go aq i madh i log n n.
Nëse jo i bindur, kjo është gjobë për tani, vetëm
të marrë në besim, se kjo është, me të vërtetë, ajo që të çon në përsëritje,
por kjo është vetëm një pak më shumë një Qasja matematikore në kërkim
në kohën drejtimin e merge lloji bazuar në pseudokod e saj vetëm.
>> Tani le të marrin një grimë e një pushim nga të gjithë se,
dhe për të marrë një sy në një ish-senator i caktuar, i cili
mund të duket një të njohur pak, i cili u ul me Eric Google
Schmidt, disa kohë më parë, për një intervistë në skenë, në frontin e një bandë e tërë
e njerëzve, duke folur në fund të fundit për një temë, kjo është goxha e njohur tani.
Le të marrin një vështrim.
>> Eric Schmidt: Tani Senator, ju jeni këtu në Google,
dhe unë doja të mendoj e Presidenca si një intervistë për punë.
Tani është e vështirë për të marrë një punë si president.
PRESIDENTI OBAMA: E drejta.
Eric Schmidt: Dhe ju jeni shkuar për të bërë [e padëgjueshme] tani.
Është gjithashtu e vështirë për të marrë një punë në Google.
PRESIDENTI OBAMA: E drejta.
>> Eric Schmidt: Kemi pyetje, dhe ne të bëni pyetje kandidatët tanë,
dhe kjo është nga Larry Schwimmer.
>> PRESIDENTI OBAMA: OK.
>> Eric Schmidt: Çfarë?
Ju djema mendoni se unë jam kidding?
Kjo është e drejtë këtu.
Çfarë është mënyra më efikase për zgjidhur një milion 32 bit integers?
>> PRESIDENTI OBAMA: Well--
Eric Schmidt: Ndonjëherë, ndoshta unë jam i keq, maybe--
PRESIDENTI OBAMA: Jo, jo, jo, jo, jo, unë think--
Eric Schmidt: Kjo nuk është it--
PRESIDENTI OBAMA: I mendoj, unë mendoj flluskë
lloj do të jetë mënyra e gabuar për të shkuar.
Eric Schmidt: Eja.
I cili i tha atij këtë?
NE RREGULL.
Unë nuk e bëri shkenca kompjuterike on--
>> PRESIDENTI OBAMA: Ne kemi mori spiunë tona në atje.
PROFESORI: Në rregull.
Le të lëmë pas nesh tani Bota teorik i algoritmeve
në analizën asymptotic saj, dhe të kthehet në disa tema
nga javën zero dhe një, dhe të fillojnë për të hequr disa rrota të trajnimit,
nëse ju do.
Kështu që ju të vërtetë kuptojnë në fund të fundit nga toka lart, çfarë është
ndodh nën kapuç, kur ju shkruaj, përpilojnë, dhe ekzekutuar programet.
Kujtojnë në mënyrë të veçantë, se kjo ishte programi i parë C kemi shikuar,
një program kanonik, i thjeshtë në terezi, relativisht të folur,
ku, ajo printon, Hello World.
Dhe kujtojnë se unë thashë, procesi që kodi burim shkon përmes
është pikërisht kjo.
Ju merrni kodin tuaj burim, të kalojë ajo përmes një përpilues, si tingëllimë,
dhe nga vjen kod objekt, që mund të duket si kjo, zero dhe ato
se CPU e kompjuterit, qendrore përpunimit të njësisë apo të trurit,
në fund të fundit e kupton.
>> Ajo rezulton se kjo është një pak e një oversimplification,
që ne jemi tani në një pozicion për të ngas përveç
për të kuptuar se çfarë ka qenë me të vërtetë ndodh nën kapuç
çdo herë që të kandidojë Tingëllimë, ose më në përgjithësi,
çdo herë që bëni një program, Bëni përdorimin dhe CF 50 IDE.
Në veçanti, stuff like kjo është gjeneruar së pari,
kur ju së pari të hartojnë programin tuaj.
Me fjalë të tjera, kur ju të marrë kodin tuaj burim
dhe të përpilojnë atë, çfarë është parë being outputted by tingëllimë
është diçka e njohur si kodi kuvendit.
Dhe në fakt, ajo duket tamam si kjo.
>> Unë u zhvillua një komandë në nivel Command Line herët.
Tingëllimë kryeqytetit Dash s hello.c, dhe kjo krijoi një fotografi
për mua quajtur hello.s, brenda të cilave ishin pikërisht
këto përmbajtje, dhe një më pak sipër dhe pak më poshtë,
por unë e kam vënë juiciest informacion këtu në ekran.
Dhe në qoftë se ju shikoni nga afër, ju do të shihni të paktën disa fjalë kyçe të njohur.
Ne kemi kryesor në krye.
Ne kemi printf poshtë në mes.
Dhe ne gjithashtu kemi Hello World backslash n në thonjëza poshtë më poshtë.
>> Dhe çdo gjë tjetër në këtu është udhëzime nivel shumë të ulët
se CPU e kompjuterit kupton.
Udhëzimet CPU që lëvizin kujtesën rreth, se vargjet ngarkesës nga kujtesa,
dhe në fund të fundit, të shtypura gjëra në ekran.
Tani çfarë ndodh pse pas ky kod kuvendi është gjeneruar?
Në fund të fundit, ju bëni, me të vërtetë, ende të gjeneruar kodin objekt.
Por hapat që kanë me të vërtetë vazhduar nën kapuç
shikoni pak më shumë si kjo.
Source code bëhet kod kuvendi, e cila pastaj bëhet kod objekt,
dhe fjalët operative këtu janë se, kur ju përpilojnë kodin tuaj burim,
nga vjen kodin kuvendit, dhe pastaj kur ju mblidhen kodin tuaj kuvendit,
nga vjen kod objekt.
>> Tani tingëllimë është super i sofistikuar, si një shumë e hartuesit,
dhe kjo e bën të gjitha këto hapa së bashku, dhe kjo e bën jo domosdoshmërisht
Prodhimi ndonjë ndërmjetme fotografi që ju mund të shihni edhe.
Ajo thjesht harton gjëra, cila është termi përgjithshme që
përshkruan të gjithë këtë proces.
Por në qoftë se ju vërtet doni për të qenë të veçantë, nuk ka
shumë më tepër ndodh edhe atje.
>> Por le të marrë në konsideratë tani se edhe se programi super e thjeshtë, hello.c,
quajtur një funksion.
Ajo quajtur printf.
Por unë nuk shkruaj printf, me të vërtetë, që vjen me c, kështu që të flasin.
Kjo është një kujtojnë funksion kjo është deklaroi në io.h standarde, e cila
është një header file, e cila është një temë që ne do të vërtetë të
zhyten në thellësi më shumë para se të gjatë.
Por një header skedë është shoqëruar në mënyrë tipike
nga një skedar kod, kodin burim file, kështu që ashtu si ekziston io.h. standarde
>> Pak kohë më parë, dikush, ose someones, gjithashtu shkroi
një file i quajtur io.c standarde, në që përkufizimet aktuale,
ose Implementimi i printf, dhe bunches e funksioneve të tjera,
janë të shkruara në fakt.
Pra duke pasur parasysh se, në qoftë se ne e konsiderojmë të pasur këtu në të majtë, hello.c, se kur
hartuar, na jep hello.s, edhe në qoftë se Tingëllimë nuk bother kursimin në një vend
ne mund të shohim atë, dhe se kodi kuvendit merr mbledhur në hello.o, e cila
është, me të vërtetë, emri i parazgjedhur dhënë sa herë që ju të përpilojnë burim
kodin në kodin objekt, por nuk janë të mjaft të gatshëm për të ekzekutuar atë ende,
sepse një hap tjetër duhet të ndodhë, dhe ka
është duke ndodhur për të kaluarën pak javë, ndoshta unbeknownst për ju.
>> Në mënyrë të veçantë diku në CS50 IDE, dhe kjo,
gjithashtu, do të jetë pak e një thjeshtëzim për një moment,
ka, ose ishte e nje kohe, një file i quajtur io.c standarde,
që dikush hartuar në io.s standarde ose ekuivalent,
që dikush pastaj mblodhi në io.o standarde,
apo rezulton në një skedar pak më të ndryshme
format që mund të ketë një tjetër fotografi extension krejt,
por në teori dhe konceptualisht, pikërisht këto hapa është dashur të ndodhë në një formë.
Që do të thotë se tani kur unë jam me shkrim një program,
hello.c, që vetëm thotë, Hello World, dhe unë jam duke përdorur kodin e dikujt tjetër
si printf, e cila ishte një herë e një kohë, në një skedar të quajtur io.c standarde,
atëherë disi unë kam për të marr My Kodi objekt, zero e mia dhe ato,
dhe objekt atij personi Kodi ose zero dhe ato,
dhe disi lidhjen e tyre së bashku në një skedar i fundit, i quajtur hello, që
ka të gjitha zero dhe ato nga funksioni im kryesor,
dhe të gjitha zero dhe ato për printf.
>> Dhe me të vërtetë, se procesi fundit është quajtur, lidh kodin tuaj objekt.
Prodhimi i të cilave është një skedar i ekzekutueshëm.
Pra, në drejtësi, në nivel fundi i ditës, asgjë
ka ndryshuar që nga java e parë, kur ne së pari ka filluar hartimin e programeve.
Në të vërtetë, e gjithë kjo ka qenë ndodh nën kapuç,
por tani ne jemi në një pozicion ku ne mund të vërtetë
vë në lojë përveç këto hapa të ndryshme.
Dhe në të vërtetë, në fund e ditës, ne jemi ende
u largua me zero dhe ato, të cilat është në fakt një Segue i madh tani
në një aftësi për të C, që ne nuk kemi pasur për të levave më shumë gjasa
deri më sot, i njohur si operatorët bitwise.
Me fjalë të tjera, deri më tani, në çdo kohë ne kemi trajtohen me të dhëna në C ose variablave në C,
ne kemi pasur gjëra të tilla si chars dhe gjithandej dhe ins
dhe longs dhe dyshe dhe të ngjashme, por të gjithë ata që janë të paktën tetë bit.
Ne kurrë nuk kam qenë ende në gjendje për të manipuluar bit individuale,
edhe pse një grimë individuale, ne e di, mund të përfaqësojnë një 0 dhe një 1.
Tani del se në C, ju mund të merrni qasje në copa individuale,
në qoftë se ju e dini sintaksë, me të cilin për të marrë me ta.
>> Pra, le të marrin një vështrim në operatorët bitwise.
Pra foto këtu janë disa simbole që ne kemi, lloj, lloj, parë më parë.
Unë shoh një 'e, një vertikale bar, dhe disa të tjerë, si dhe,
dhe kujtojnë se simbol të ampersand është diçka që ne kemi parë më parë.
Operatori logjik AND, ku ju keni dy prej tyre së bashku, ose logjik OR
operator, ku ju kanë dy bare vertikale.
Operatorët bitwise, të cilat ne do të shih veprojnë në copa individuale,
vetëm përdorni një simbol të vetme, një bar vetme vertikale, simboli caret
vjen më pas, pak Tilde, dhe pastaj u largua
kllapa majtas kllapa, ose kllapa drejtë kllapa drejtë.
Secili prej tyre kanë kuptime të ndryshme.
>> Në fakt, le të marrin një sy.
Le të shkojnë shkollës së vjetër sot, dhe përdorimi një ekran touch nga kaluar,
i njohur si një bord të bardhë.
Dhe kjo bordit të bardhë do të na lejojë
të shpreh disa simbole mjaft e thjeshtë, ose më mirë disa formula të thjeshta në mënyrë të drejtë,
që ne mund pastaj në fund të fundit levave, në mënyrë
për të hyrë në individ bit brenda një programi C.
Me fjalë të tjera, le ta bëjmë këtë.
Flasim së pari le për një moment për simbolin komercial,
që është bitwise DHE operatori.
Me fjalë të tjera, kjo është një operator që lejon
mua që të ketë një ndryshore të majtë në mënyrë tipike, dhe një variabël djathtë,
ose një vlerë individ, se në qoftë se ne DHE ata së bashku, më jep një rezultat përfundimtar.
Pra, çfarë dua të them?
Në qoftë se në një program, ju keni një ndryshore që ruan një prej këtyre vlerave,
ose le të mbani atë të thjeshtë, dhe vetëm shkruani nga zero dhe ato individualisht,
këtu është se si funksionon operatori simbol.
0 simbol 0 do të barabartë 0.
Tani pse është kjo?
>> Është shumë e ngjashme me Shprehje Boolean,
që ne kemi diskutuar deri tani.
Nëse ju mendoni se pas të gjitha, 0 është false, 0 është false, false dhe të rreme
është, siç kemi diskutuar logjikisht, edhe rreme.
Pra, ne të merrni 0 si edhe këtu.
Nëse ju merrni 0 simbol të 1, mirë që, gjithashtu,
do të jetë 0, sepse për këtë shprehje i majtë të jetë e vërtetë ose 1,
ai do të duhet të jetë e vërtetë dhe e vërtetë.
Por këtu kemi false dhe i vërtetë, ose 0 dhe 1.
Tani përsëri, në qoftë se ne kemi 1 simbol të 0, që, gjithashtu, do të jetë 0,
dhe në qoftë se ne kemi 1 zëvendësojeni me 1, më në fund do të kemi një grimë 1.
Pra, me fjalë të tjera, ne nuk jemi duke bërë çdo gjë interesante me këtë operator
vetëm ende, ky operator simbol.
Është bitwise DHE operatori.
Por këto janë përbërësit nëpërmjet të cilës ne mund të bëjmë
gjëra interesante, si ne do të shohim së shpejti.
>> Tani le të shohim vetëm të vetme bar vertikale mbi këtu në të djathtë.
Nëse unë kam një grimë 0 dhe unë Ose me, The bitwise
Ose operatori, një tjetër 0 bit, që do të jepni 0.
Nëse unë të marrë një grimë 0 dhe ose me një 1 bit, atëherë unë jam duke shkuar për të marrë 1.
Dhe në fakt, vetëm për qartësi, më lejoni të kthehem,
kështu që baret e mia vertikale nuk janë të gabuar për 1 s.
Më lejoni të rishkruaj të gjithë 1 im është pak më shumë
në mënyrë të qartë, në mënyrë që ne të ardhshëm të shohim, nëse unë kanë një 1 ose 0, kjo do të jetë një 1,
dhe në qoftë se unë kam një 1 ose 1 që, gjithashtu, do të jetë një 1.
Kështu që ju mund të shihni logjikisht se OR Operatori sillet shumë ndryshe.
Kjo më jep 0 ose 0 jep me 0, por çdo kombinim tjetër më jep 1.
Për sa kohë që unë kam një 1 në formula, rezultati do të jetë 1.
>> Në kontrast me dhe operatorit, simbol,
vetëm në qoftë se unë kam dy 1 është në ekuacion, mund të vërtetë të marrë një 1 nga.
Tani ka një tjetër pak Operatorët si.
Një prej tyre është pak më shumë të përfshira.
Pra më lejoni të shkoj përpara dhe të fshihet kjo për të liruar deri disa hapësirë.
Dhe le të marrin një vështrim në simbol caret, për vetëm një moment.
Kjo është zakonisht një karakter ju mund të shtypni
në tuaj Shift mbajtjes tastierë dhe pastaj një nga numrat në majë SHBA tuaj
tastierë.
>> Pra, kjo është ekskluzive Ose operatori, ekskluzive ose.
Pra, ne vetëm e pa operatorin OSE.
Kjo është ekskluziv ose operatori.
Çfarë është në të vërtetë ndryshimi?
E pra, le të vetëm shikoni në formulë, dhe e përdorin këtë si përbërës në fund të fundit.
0 XOR 0.
Unë jam duke shkuar për të thënë është gjithmonë 0.
Ky është përkufizimi i XOR.
0 XOR 1 do të jetë 1.
1 XOR 0 do të jetë 1, dhe 1 XOR 1 do të jetë?
Gabuar?
Apo e drejtë?
Une nuk e di.
0.
Tani çfarë po ndodh këtu?
E pra mendoj në lidhje me Emri i këtij operatori.
Ekskluzive OSE, ashtu si emri, lloj, sugjeron,
përgjigja është vetëm do të jetë një 1 në qoftë se inputet janë të veçantë,
ekskluzivisht e ndryshme.
Kështu që këtu inputet janë njëjtë, kështu që prodhimi është 0.
Këtu inputet janë njëjtë, kështu që prodhimi është 0.
Këtu janë rezultatet janë të ndryshme, ata janë ekskluzive, dhe kështu prodhimi është 1.
Kështu që është shumë e ngjashme me DHE, kjo është shumë e ngjashme,
ose më mirë është shumë e ngjashme me OSE, por vetëm në një mënyrë të veçantë.
Kjo nuk është më një 1, sepse ne kemi dy 1-së,
dhe jo vetëm, vetëm një prej tyre.
Në rregull.
Po në lidhje me të tjerët?
Well Tilde, ndërkohë, është në fakt e bukur dhe të thjeshtë, fatmirësisht.
Dhe kjo është një unary operatori, që do të thotë
ajo është aplikuar në vetëm një input, një madhësi, kështu që të flasin.
Jo për një të majtë dhe një e drejtë.
Me fjalë të tjera, në qoftë se ju merrni shenjë tildë e 0, përgjigja do të jetë e kundërta.
Dhe në qoftë se ju merrni Tilde nga 1, Përgjigja nuk do të jetë e kundërta.
Pra, operatori Tilde është një mënyrë për të mohuar një grimë,
ose Flipping pak nga 0 deri 1, ose nga 1 ne 0.
>> Dhe kjo na lë në fund me vetëm dy operatorë të formës së prerë,
e ashtuquajtura ndryshim majtë, dhe ashtuquajturi operator djathtas ndryshim.
Le të marrin një sy se si ato punë.
Operatori i la ndryshim, i shkruar me dy kllapa kënd si kjo,
vepron si më poshtë.
Në qoftë se input tim, ose operandi im, në të majtë Operatori ndryshim është thjesht një 1.
Dhe unë pastaj tregoni kompjuterin në la ndryshim se 1, thonë shtatë vende,
rezultati është sikur unë marrë atë 1, dhe të lëvizin atë
shtatë vende mbi të majtë, dhe nga default,
ne jemi duke shkuar për të supozojmë se hapësira në të djathtë
do të jetë i mbushur me zero.
Me fjalë të tjera, 1 u largua ndryshim 7 po shkon për të dhënë më se 1, e ndjekur nga 1, 2, 3,
4, 5, 6, 7 zero.
Pra, në një mënyrë, kjo ju lejon të të marrë një numër të vogël si 1,
dhe në mënyrë të qartë të bëjë atë shumë shumë, shumë më të madhe në këtë mënyrë,
por ne jemi të vërtetë do të shohim qasje më të zgjuar për të
në vend të kësaj, po ashtu,
>> Në rregull.
Kjo është ajo për javën e tretë.
Ne do të ju shohim herën tjetër.
Kjo ishte CS50.
>> [Muzika]
>> SPEAKER 1: Ai ishte në rostiçeri bar të hahet një sundae nxehtë krem ​​karamel.
Ai kishte të gjitha mbi fytyrën e tij.
Ai është veshur se çokollata si një mjekër
SPEAKER 2: Çfarë po bën?
SPEAKER 3: Hmmm?
Çfarë?
>> SPEAKER 2: A ju vetëm dip dyfishtë?
Ju dyfishtë zhytur chip.
SPEAKER 3: Më falni.
SPEAKER 2: Ju zhytur chip, ju mori një pickim, dhe ju zhytur përsëri.
SPEAKER 3:
SPEAKER 2: Pra kjo është vënë si e drejta juaj e tërë gojën në dip.
Herën tjetër ju merrni një çip, vetëm dip atë një herë, dhe do të përfundojë atë.
>> SPEAKER 3: Ju e dini se çfarë, Dan?
Ju dip në mënyrën që ju dëshironi për të dip.
Unë do të kridhem në mënyrën që unë dua të kridhem.