[Mūzikas atskaņošanai] 

PROFESSOR: Nu labi. Tas ir CS50 un tas ir nedēļas beigām trīs. Tāpēc mēs šodien esam šeit, nevis Sanders Teātris, tā vietā WEIDNER bibliotēkā. Iekšpusē, kas ir studijas pazīstams kā Hauser Studio, vai teiksim Studio H, vai veic mēs say-- ja jums patika šī joks, tas ir faktiski no klasesbiedrs, Mark, online, kurš ieteica tik daudz caur Twitter. Tagad to, kas ir cool par ir šeit studijā ir tas, ka es esmu ieskauj šie zaļš sienas, zaļā ekrāna vai chromakey, tā sakot, tas nozīmē, ka CS50 s ražošanas komandas, nezinot mani tieši tagad, varētu būt liekot mani visvairāk jebkur pasaulē, lai labāk vai sliktāk. 

Tagad to, kas ir priekšā, problēma noteikti divi ir jūsu rokās par šo nedēļu, bet ar problēmu noteikt Trīs šo nāk šonedēļ, jums tiks apstrīdēti ar tā sauktais spēle 15., veca puse favor kas jūs varētu atgādināt saņemšanu kā bērns, kas ir visu ķekars skaitļu, kas var slaidu augšu, uz leju, pa kreisi un pa labi, un tur ir viena plaisa ietvaros puzzle, kurā jums faktiski var slīdēt šos puzzle gabalus. Galu galā jūs saņemsiet šo puzle kaut daļēji jauktā secībā, un mērķis ir šķirot to, augšas uz leju, kreisās uz labo, no vienas visu ceļu augšup pa 15. 

Diemžēl, īstenojot jums ir pie rokas būs programmatūra pamatā, ne fiziski. Jūs faktiski nāksies rakstīt kods, ar kuru students vai lietotājs var spēlēt spēli 15. Un patiesībā, jo hakeris izdevums spēle 15., Jums būs izaicinājums, lai īstenotu, ne tikai spēlē šīs vecās skolas spēle, bet gan risināšana no tā, ko īsteno Dieva režīms, tā sakot, ka patiesībā atrisina mīklu par cilvēku, nodrošinot tos ar mājienu, pēc mājienu, pēc mājienu. Tik daudz par šo nākamnedēļ. Bet tas, kas ir priekšā. 

Tagad atceros, ka šonedēļ mums bija šis cliffhanger, ja jūs, kuru vislabāk mēs darām šķirošana gudrs bija augšējā robeža liels o n brusas. Citiem vārdiem sakot, burbulis šķirot, atlase kārtot, ievietošanas kārtošanas, viņiem visiem, bet atšķirīgs to īstenošanā, nodota stājas n brusas darbojas reize ļoti sliktākajā gadījumā. Un mēs parasti pieņemam, ka ļoti sliktākajā gadījumā šķirošanas ir viens, ka jūsu ieejas Ir pilnīgi atpakaļ. Un tiešām, tas bija diezgan dažus soļus lai īstenotu katru no šiem algoritmiem. 

Tagad pašās beigās klases Atsaukt, mēs salīdzinājām burbulis šķirot pret atlases veida pret kādu citu ka mēs sauc sapludināšanas veida tajā laikā, un es ierosinu, ka tas ir ņemot priekšrocība mācība no nedēļas nulle, skaldi un valdi. Un kaut kā sasniegšanai kādu logaritmiska darba laika, galu galā, tā vietā, lai kaut ko tas ir tīri kvadrāts. Un tas nav gluži logaritmiska, tas ir mazliet vairāk nekā. Bet, ja jūs atceraties no klases, tas bija daudz, daudz ātrāk. Pieņemsim to apskatīt, kur mēs left off. 

Bubble kārtot versus atlasē Kārtot pret sapludināšanas kārtošanas. Tagad viņi visi darbojas, jo teoriju, tajā pašā laikā. CPU darbojas ar tādu pašu ātrumu. Bet jūs varat sajust, cik garlaicīgi tas ir ļoti ātri kļūs, un cik ātri, kad mēs injicēt mazliet nedēļā nulle s algoritmu, mēs varam paātrināt lietas uz augšu. 

Tātad zīme kārtot izskatās pārsteidzošs. Kā mēs varam piesaistīt to, lai lai ātrāk sakārtotu numurus. Nu pieņemsim domāt atpakaļ sastāvdaļai, ka mēs bija atpakaļ nedēļā nulles, ka meklējot kādu, ar tālruņu grāmatā, un atgādina, ka pseudocode ka mēs ierosinājām, caur kuru mēs varam atrast kāds, piemēram, Mike Smith, izskatījās nedaudz kaut kas līdzīgs šim. 

Tagad to apskatīt, jo īpaši pie līnijas 7 un 8, un 10 un 11, kas inducē, ka cilpa, kuru mēs tur atgriežās 3 līniju atkal, un atkal, un atkal. Bet izrādās, ka mēs varam apskatīt Šis algoritms, šeit pseudocode, nedaudz vairāk veselums. Patiesībā tas, ko es meklēju pie šeit uz ekrāna, ir algoritms meklējot Mike Smith starp kādu kopumu lapas. Un tiešām, mēs varētu vienkāršot šo algoritms tajās līnijās 7. un 8., un 10 un 11, lai tikai teikt, kas es esmu parādīti šeit dzeltenā krāsā. Citiem vārdiem sakot, ja Mike Smits ir agrāk grāmatā, mums nav nepieciešams norādīt soli pa solim, tagad, kā iet atrastu viņu. Mums nav jānorāda doties atpakaļ uz 3. līniju, kāpēc nav mēs tikai vietā, teiksim, vispārīgāk, meklēt Mike In kreisā puse no grāmatas. 

Un otrādi, ja Mike ir faktiski vēlāk grāmatā, kāpēc nav mēs vienkārši citēt likt pēdiņas beigās meklēšanu Mike labajā pusē grāmatas. Citiem vārdiem sakot, kāpēc nav mēs vienkārši kārtot punt uz sevi saprotams, meklēt Mike šajā apakšgrupa grāmatas, un atstāt to mūsu esošajiem algoritms, lai pastāstītu mums Kā meklēt Mike ka kreisā puse no grāmatas. Citiem vārdiem sakot, mūsu algoritms strādā vai tas ir tālrunis grāmata šajā biezuma, tas biezums, vai jebkura biezuma whatsoever. Tātad mēs varam rekursīvi definēt šo algoritmu. Citiem vārdiem, uz ekrāns šeit, ir algoritms meklējot Mike Smith Starp lapām telefona grāmatu. Tātad 7. līnijā un 10, pieņemsim tikai teikt, tieši tā. Un es izmantot šo terminu brīdi atpakaļ, un, protams, rekursijas ir buzzword tagad, un tas ir tas process darīt kaut ko ciklisko pēc kaut kā izmantojot kodu, kas jums jau ir, un aicinot to vēlreiz, un atkal, un atkal. Tagad tas būs svarīgi ka mēs kaut kā dibens ārā, un nav darīt, ka bezgalīgi ilgi. Pretējā gadījumā mēs spēsim ir patiešām bezgalīgs cilpa. Bet pieņemsim redzēt, ja mēs varam aizņemties šo ideju no recursion, atkal kaut ko dara un atkal un atkal, lai atrisinātu šķirošanas problēma via sapludināšanas kārtot, viss efektīvāk. 

Tāpēc es dodu jums apvienot kārtot. Pieņemsim to apskatīt. Tātad, šeit ir pseudocode, ar ko mēs varētu ieviest šķirošanas, Izmantojot šo algoritmu sauc sapludināšanas kārtošanas. Un tas ir diezgan vienkārši tas. Par ieejas n elementiem, citiem vārdiem sakot, ja jūs esat ņemot n elementi un numuri un burti vai kāds ieguldījums ir, ja jūs esat dota n elementus, ja tie n ir mazāks par 2, tikai atgriežas. Tiesības? Jo ja n ir mazāks par 2, kas nozīmē, ka mans saraksts elementu ir vai nu no izmēram 0 vai 1, un abās šajās trivial lietās saraksts jau ir sakārtots. Ja saraksta nav, tas ir sakārtoti. Un, ja tur ir saraksts ar garumu 1, tas ir acīmredzami sakārtoti. Tātad algoritms tikai vajag tiešām kaut ko interesantu, ja mums ir divi vai vairāk elementi dota mums. So aplūkosim burvju tad. Else kārtot kreiso pusi no elementiem, tad kārtot labajā pusē elementiem, tad apvienot sakārtoti pusītes. Un, kas ir sava veida prāta lieces šeit ir tā, ka man nav īsti likties jums ir teicis kaut kas tikai vēl, vai ne? Viss, ko es esmu teica, ir, ņemot vērā, sarakstu n elementi, kārtot kreiso pusi, tad labajā pusē, tad apvienot sakārtoti pusītes, bet kur ir faktiskā noslēpums mērce? Kur ir algoritms? Nu izrādās, ka šīm divām līnijām pirmkārt, kārtot atstājis pusi no elementiem, un kārtot tiesības puse no elementiem, ir rekursīvas zvanu, lai runāt. 

Galu galā, šajā brīdis, man ir algoritms, ar kuru kārtot visu ķekars elementu? Jā. Tas ir labi šeit. Tas ir tepat uz ekrāna, un lai es varētu izmantot to pašu komplektu soļiem kārtot kreiso pusi, kā es varu labajā pusē. Un tiešām, atkal un atkal. Tātad tā vai citādi, un mēs drīz redzu, burvību sapludināšanas veida ir iestrādāts ar to, ka ļoti gala līnija, apvienojot sakārtotos pusītes. Un tas šķiet diezgan intuitīvi. Jūs lietojat divas pusītes, un jūs, kaut kā, apvienot tos kopā, un mēs redzam konkrēti brīdi. 

Bet tas ir pilnīgs algoritms. Un pieņemsim redzēt, tieši kāpēc. Nu pieņemsim, ka mēs esam dota tiem pats astoņi elementi šeit uz ekrāna, kas ir viens pa astoņiem, bet viņi šķietami nejaušā secībā. Un mērķis pie rokas ir kārtot šos elementus. Nu kā es varu iet par darot to, izmantojot, atkal, apvienot kārtot, kā par šo pseudocode? Un atkal, iesakņojies tas Tavs prāts, lai tikai uz mirkli. Pirmais gadījums ir diezgan niecīgs, ja tas ir mazāks par 2, vienkārši atgriezties, tur nav jāstrādā. Tik tiešām tur ir tikai trīs pasākumus, lai tiešām paturēt prātā. Atkal, un atkal, es esmu gatavojas vēlaties, lai būtu kārtot kreiso pusi, kārtot labo pusi, un pēc tam, kad viņu divas pusītes ir sakārtoti, Es gribu apvienot tos kopā vienā šķiroto sarakstā. Lai saglabātu, ka prātā. 

Tātad, šeit ir oriģināls sarakstā. Pieņemsim ārstēt to kā masīvs, kā mēs sākām nedēļā divas, kas ir blakus bloks atmiņas. Šajā gadījumā, kas satur astoņus numuri, atpakaļ atpakaļ atpakaļ. Un pieņemsim tagad pieteikties sapludināšanas veida. Tāpēc es vispirms gribu, lai sakārtotu kreiso pusi no šī saraksta, un pieņemsim, tādēļ, koncentrējas uz 4, 8, 6, un 2. 

Tagad, kā es varu iet par šķirošanas sarakstu izmēra 4? Nu man ir tagad uzskata šķirošanas kreisi no kreisā pusē. Atkal, pieņemsim attīt tikai brīdi. Ja pseudocode ir tas, un es esmu dota astoņiem elementus, 8 ir acīmredzami lielāka par vai vienāds ar 2. Tātad ar pirmo lietu neattiecas. Tātad, lai kārtotu astoņus elementus, es vispirms kārtot kreiso pusi no elementiem, tad es sakārtotu pareizo pusi, tad es apvienot abas šķirotas pusītes, katra lieluma 4. LABI. 

Bet, ja jūs esat tikko man teica, sakārtot kreisā puse, kas tagad no lieluma 4, kā es varu kārtot kreiso pusi? Nu, ja man ir ievade no četriem elementiem, Es vispirms kārtot kreiso divi, tad pa labi divi, un tad es apvienot tos kopā. Tātad vēlreiz, tas kļūst mazliet no prāta lieces spēli šeit, jo jums, veida, ir atcerēties, kur jums ir stāsts, bet beigās, dienā, ņemot vērā jebkādu elementu skaits, jūs vispirms vēlaties, lai sakārtotu kreiso pusi, tad labajā pusē, tad apvienot tos kopā. Sāksim to darīt tieši to. Lūk ieejas no astoņiem elementiem. Tagad mēs meklējam kreisajā pusē šeit. Kā es varu kārtot četrus elementus? Nu es vispirms kārtot kreiso pusi. Tagad, kā es varu kārtot kreiso pusi? Nu es esmu bijusi divus elementus. Tātad pieņemsim šķirot šos divus elementus. 2 ir lielāks par vai vienāds ar 2, protams. Tā, ka pirmā lieta neattiecas. 

Tāpēc man tagad ir, lai sakārtotu kreiso puse no šiem diviem elementiem. Kreisajā pusē, protams, ir tikai 4. Tātad, kā es varu kārtot sarakstu viena elementa? Nu tagad, ka īpaša pamatne gadījums up top, tā sakot, ir piemērojama. 1 ir mazāks par 2, un mans saraksts ir patiešām izmērs 1. Tāpēc es vienkārši atgriezties. Es neko nedara. Un tiešām, apskatīt to, ko es esmu darīts, 4 jau ir sakārtots. Tāpat kā es esmu jau daļēji veiksmīga šeit. 

Tagad, šķiet, sava veida stulba pieprasīt, bet tā ir taisnība. 4 ir saraksts ar izmēru 1. Tas jau ir sakārtoti. Tas ir kreiso pusi. Tagad es sakārtotu pareizo pusi. Mans ieguldījums ir viens no elementiem, 8 Līdzīgi jau sakārtoti. Stulba, pārāk, bet atkal, šis pamatprincips gatavojas ļauj mums tagad būvēt virsū tas veiksmīgi. 4 sakārtots, 8 ir sakārtots, tagad Kas tas bija pēdējais solis? Tātad trešais un pēdējais solis, jebkurš laiks jūs šķirošanas sarakstā, atsaukšanu, bija apvienot abas pusītes, kreiso un labo. Tātad, pieņemsim darīt tieši to. Mana kreisā puse, protams, 4. Mana labā puse ir 8. 

Tātad, pieņemsim darīt. Vispirms es esmu gatavojas piešķirt daži papildu atmiņu, ka es ņemšu pārstāv šeit, kā tikai sekundāra masīvs, tas ir pietiekami liels, lai ietilptu to. Bet jūs varat iedomāties, paplašinot ka taisnstūris visā garumā, ja mums ir nepieciešams vairāk vēlāk. Kā es varu veikt 4 un 8, un apvienot šie divi saraksti izmērs 1 kopā? Arī šeit, diezgan vienkārši. 4 ir pirmajā vietā, tad nāk 8. Jo, ja es gribu, lai sakārtotu kreiso pusi, tad labajā pusē, un pēc tam apvienot šos divus pusītes kopā, jo šķiroto kārtībā, 4 ir pirmajā vietā, tad nāk 8. 

Tāpēc mēs, šķiet, ir gūt panākumus, pat lai gan man nav izdarīts jebkurā faktisko darbu. Bet atcerieties, kur mēs esam stāsts. Mēs sākotnēji pieņēma astoņus elementus. Mēs sakārtoti kreiso pusi, kas ir 4. Tad mēs sakārtoti kreiso pusi no kreisā pusē, kas bija 2. Un šeit mēs iet. Mēs esam darījuši ar šo soli. 

Tātad, ja mēs esam sakārtoti atstājis pusi no 2., tagad mēs ir kārtot labajā pusē 2. Tātad labajā pusē 2 ir šīm divām vērtībām šeit, 6 un 2. Tātad pieņemsim tagad veikt ievadi izmēra 2, un sakārtot kreiso pusi, un pēc tam labajā pusē, un pēc tam apvienot tos kopā. Nu kā es varu kārtot sarakstu izmēra 1, kas satur tikai numurs 6? Es esmu jau darīts. Šis saraksts izmēra 1 ir sakārtots. 

Kā es varu kārtot citu sarakstu izmērs 1, tā saukto labo pusi. Nu tas arī ir jau sakārtots. Skaitlis 2 ir viens pats. Tāpēc tagad man ir divas pusītes, pa kreisi un labi, man ir nepieciešams apvienot tos kopā. Ļaujiet man dot sev kādu papildus telpu. Un nodot 2 tur, tad 6 tur, tādējādi šķirošana šo sarakstu, pa kreisi un pa labi, un apvienojot to kopā, galu galā. Tāpēc es esmu nedaudz labāks. Es ne darīts, jo skaidri 4, 8, 2, 6 nav galīgs pasūtīšanas ka es gribu. Bet man tagad ir divi saraksti izmērs 2, kas ir gan, attiecīgi, tika sakārtots. Tāpēc tagad, ja jūs attīt savā prātā s acs, kur bija, ka atstāj mūs? Es sāku ar astoņiem elementiem, tad es whittled to uz leju līdz kreisajā pusē 4, tad kreiso pusi no 2, un tad labajā pusē 2, Es pabeidzu, tāpēc, šķirošana kreiso puse no 2, un labajā pusē 2, Tātad, kas ir trešais un pēdējais solis šeit? Man ir apvienot kopā divi saraksti izmēra 2. So iesim uz priekšu. Un uz ekrāna šeit, dot man daži papildu atmiņu, gan tehniski, ievērosiet, ka es esmu ieguva visai ķekars tukšu vietu uz augšu augšu tur. Ja es gribu būt īpaši efektīva telpa gudrs, Es varētu vienkārši sākt pārvietojas elementi un atpakaļ, augšas un apakšas. Bet tikai uz vizuālo skaidrību, Es esmu gatavojas nodot to uz leju zem, lai saglabātu lietas jauka un tīra. 

Tāpēc es esam ieguvuši divus sarakstus ar izmēru 2. Pirmajā sarakstā ir 4 un 8. Otrais sarakstā ir 2 un 6. Pieņemsim, apvienot tos, kopā šķiroto kārtībā. 2, protams, nāk no vienas puses, tad 4, tad 6, tad 8. Un tagad mēs, šķiet, kļūst kaut kur interesanti. Tagad es esmu sakārtoti pusi no uzskaitīt, un nejauši, tas ir visi pāra numuri, taču tas Ir, protams, ir tikai nejaušība. Un es tagad ir sakārtoti pa kreisi puse, tāpēc, ka tas ir 2, 4, 6, un 8. Nekas ir bojātas. Ka jūtas kā progresam. 

Tagad tā uzskata, tāpat kā es esmu runājis uz visiem laikiem tagad, Tātad, ko Jāskatās, ja tas algoritms ir, patiešām, efektīvāku. Bet mēs ejam cauri tas super metodiski. Dators, protams, varētu darīt to, piemēram, ka. Tātad, kur mēs esam? Mēs sākām ar astoņiem elementiem. Es sakārtoti kreiso pusi 4. Man šķiet, ir darīts ar to. Tāpēc tagad nākamais solis ir kārtot labajā pusē 4. Un šī daļa, mēs varam iet caur nedaudz vairāk ātri, lai gan jūs esat Aicinām attītu vai apturētu, vienkārši domāju, ka ar to ir savā tempā, bet to, kas mums tagad ir iespēja darīt tieši to pašu algoritmu uz četriem dažādiem numuriem. 

So iesim uz priekšu, un koncentrēties uz labajā pusē, ko mēs esam šeit. Kreisajā pusē, kas Labajā pusē, un tagad kreiso pusi no kreisās puses puse no šīs labās puse, un kā es varu kārtot sarakstu izmēra 1, kas satur tikai numuru 1? Tas jau darīts. Kā es varu darīt to pašu par sarakstu izmēru 1, kas satur tikai 7? Tas jau darīts. Trešais solis šai pusē, tad ir apvienot šos abus elementus jaunā saraksta izmērs 2, 1 un 7. Nešķiet, ka esam darījuši visu ka daudz interesantu darbu. Let 's redzēt, kas notiks tālāk. Es tikko sakārtoti kreiso pusi no tiesības puse manu sākotnējo ieguldījumu. Tagad pieņemsim kārtot tiesības puse, kas satur 5 un 3. Pieņemsim vēlreiz apskatīt kreisi puse, sakārtots, labi pusi, sakārtoti, un apvienot tos abus kopā, par kādu papildu telpas, 3 ir pirmajā vietā, tad nāk 5. Un tā nu mēs esam sakārtoti kreisā puse no labajā pusē no sākotnējā problēma, un labajā pusē labajā pusē no sākotnējā problēma. Kas ir trešais un pēdējais posms? Nu apvienot šīs divas pusītes kopā. So let me get sev kādu papildu telpas, bet, atkal, es varētu būt, izmantojot šo rezerves kosmosa up top. Bet mēs ejam, lai saglabātu tas vienkārši vizuāli. Ļaujiet man saplūst tagad 1, un pēc tam 3, un pēc tam 5, un pēc tam 7. Tādējādi atstājot mani tagad ar tiesības puse no sākotnējās problēmas kas ir perfekti sakārtots. 

Tātad, kas paliek? Es jūtu, es glabāt sakot pašas lietas atkal un atkal, bet tas ir atstarojošs no Tas, ka mēs esam izmantojot Rekursija. Par Izmantojot process algoritms atkal, un atkal, uz mazākiem apakšgrupās sākotnējā problēma. Tāpēc man tagad ir pa kreiso sakārtoti puse no sākotnējā problēma. Man ir tiesības sakārtoti pusi no sākotnējā problēma. Kas ir trešais un pēdējais solis? Ak, tas ir apvienojot. Tātad, pieņemsim darīt. Pieņemsim piešķirt dažas papildu atmiņa, bet mans dievs, mēs varētu nodot to jebkur tagad. Mums ir tik daudz brīvas vietas pie mums, bet mēs turpinām to vienkārši. Tā vietā, lai iet atpakaļ un tālāk ar mūsu sākotnējā atmiņu, pieņemsim tikai to darīt vizuāli uz leju šeit zemāk, pabeigt līdz apvienot kreiso pusi un labajā pusē. 

Tātad, apvienojot, kas man jādara? Es gribu, lai elementus kārtībā. Tātad apskatot kreisajā pusē, Es redzu pirmais numurs ir 2. Es paskatos uz labajā pusē, Es redzu pirmo numuru ir 1, tā protams kas numurs vēlos raut ārā, un nodot pirmais manā galīgajā sarakstā? Protams, 1. Tagad es gribu uzdot šo pašu jautājumu. Kreisajā pusē, es esmu joprojām got numuru 2. Labajā pusē, Man numuru 3. Kuriem viens vēlos izvēlēties? Protams, skaits 2 Un tagad paziņojums kandidātus ir 4 kreisajā pusē, 3. labajā pusē. Pieņemsim, protams, izvēlēties 3. Tagad kandidāti ir 4 par pa kreisi, 5 pa labi. Mēs, protams, izvēlēties 4. 6 kreisajā pusē, 5 pa labi. Mēs, protams, izvēlēties 5. 6 kreisajā pusē, 7 labajā pusē. Mēs izvēlēties 6, un tad mēs izvēlēties 7, un tad mēs izvēlamies 8. Voila. 

Tik milzīgs skaits vārdiem vēlāk, mēs ir sakārtoti šo sarakstu astoņiem elementiem uz sarakstu vienas līdz astoņām, kas ir pieaug ar katru soli, bet cik daudz laika tas mūs to darīt. Nu es esmu apzināti Laid lietas gleznieciski šeit, tāpēc, ka mēs varam veida redzēt vai novērtējam sadalījumu iekarošana, kas ir noticis. 

Patiešām, ja paskatās atpakaļ pie uzmosties, Es esmu atstājis visus šos punktotajām līnijām in vietturus, jūs varat, veida, skat, apgrieztā secībā, ja jūs veida skatīties atpakaļ vēsture tagad, mans sākotnējais saraksts ir, protams, no izmēra 8. Un tad jau iepriekš, es biju nodarbojas ar diviem sarakstiem lieluma 4, un tad četri saraksti izmērs 2, un pēc tam astoņas saraksti izmēru 1. 

Tātad, ko tas, veida, atgādināt jums? Nu, protams, jebkurš no algoritmi mēs esam paskatījās līdz šim, kur mēs dalīt, un dalīt, un dalīt, glabāt, kam lietas atkal, un atkal, rezultātā šajā vispārējā ideja. Un tāpēc tur ir kaut kas logaritmiska notiek šeit. Un tas nav gluži log n, bet tur ir logaritmiska sastāvdaļa to, ko mēs esam tikko darīts. 

Tagad pieņemsim apsvērt, cik tas patiesībā ir. Tātad log n, atkal bija liels darba laiks, kad mēs kaut ko līdzīgu bināro meklēšanu, kā mēs tagad saucam, plaisa un iekarot stratēģija caur kuru mēs atradām Mike Smith. Tagad tehniski. Tas ir log bāze 2 n, pat lai gan vairumā matemātikas klasēs, 10 parasti ir pamats, ka jūs pieņemt. Bet datoru zinātnieki gandrīz vienmēr domāt un runāt ziņā bāzes 2, tāpēc mēs parasti tikai teikt žurnālu n, tā vietā, lai log bāzes 2 n, bet viņi tieši vienu un to pats pasaulē datora zinātne, un kā malā, tur ir nemainīgs faktors atšķirība starp diviem, tāpēc tas ir strīdīgs anyway, lai iegūtu formālu iemeslu dēļ. 

Bet tagad, ko mēs rūpējamies par to ir šis piemērs. Tātad pieņemsim nav pierādīt ar piemēru, bet Vismaz izmantot piemēru no numuriem pie rokas kā veselība pārbaudītu, ja Jums gribas. Tātad iepriekš formula bija log bāze 2 n, bet to, kas ir n, šajā gadījumā. Man bija n oriģinālus numurus, vai 8 no sākotnējā skaita konkrēti. Tagad tas ir bijis maz kamēr, bet es esmu diezgan pārliecināts, ka log bāze 2 no vērtības 8 ir 3, un, protams, to, kas ir jauki, par to, ka ir ka 3 ir tieši vairākas reizes ka jūs varat sadalīt sarakstu garums 8 atkal, un atkal, un atkal, līdz jūs esat palicis sarakstu, tikai izmēru 1. Tiesības? 8 iet līdz 4, iet līdz 2, iet uz 1, un tas ir atspoguļo tieši tā picture mums bija tikai pirms brīža. Tātad mazliet veselība pārbaudītu par to, kur logaritms ir faktiski iesaistīti. 

Tāpēc tagad, kas vēl ir iesaistīts šeit? n. Tik ievēroju, ka katrs Šoreiz es sadalīt sarakstu, kaut arī apgrieztā secībā vēsturē šeit, es joprojām dara n lietas. Kas apvienojas solis prasīts, lai Es pieskarties ik vienu no numuriem, lai slide to tās atbilstošā vietā. Tātad, kaut gan augstums no šī diagramma ir no lieluma log n n vai 3, Konkrētāk, citiem vārdiem sakot, Es darīju trīs nodaļas šeit. Cik daudz darba man darīt horizontāli pa šo tabulu katru reizi? 

Nu, es darīju n soļus darbu, jo, ja es esmu ieguva četrus elementus un četrus elementus, un man ir nepieciešams apvienot tos kopā. Man vajag, lai iet cauri šie četri un tie četri, galu galā tos apvienot atpakaļ astoņiem elementiem. Ja otrādi Man astoņi pirksti vairāk nekā šeit, kuras man nav, un astoņas fingers-- sorry-- Ja es esmu ieguva četrus pirkstus nekā šeit, ko es daru, četri pirksti vairāk nekā šeit, ko es daru, tad tas ir tas pats piemērs kā iepriekš, ja man ir astoņi pirksti lai gan Kopumā, ko es varu, veida, darīt. Es varu darīt tieši šeit, tad es noteikti var apvienot visus šos sarakstus no to lieluma 1 kopā. Bet es, protams, ir jāskatās katrā elementā tieši vienu reizi. Tā augstums šajā procesā ir log n, platums šajā procesā, tā sakot, ir n, lai to, ko mēs, šķiet, ir, galu galā, ir tekošās laiks lieluma n reizes log n. 

Citiem vārdiem sakot, mēs sadalīta saraksts, log n reizes, bet katru reizi, kad mēs to izdarījām, ka mums bija pieskarties ik viens no elementiem lai tos apvienot visi kopā, kas tika n soli, tāpēc mums ir n reizes log n, vai kā dators zinātnieks teiktu, asimptotiski, kas būtu liels vārds aprakstīt augšējo saistās ar darba laika, mēs darbojas liels o log n laiku, lai runāt. 

Tagad tas ir nozīmīgs, jo atgādināt kādi darbojas laiki bija ar burbuļu kārtot un atlase kārtot, un ievietošanas kārtot, un pat daži citi, kas pastāv, n brusas bija, kad mēs bijām. Un jūs varat, veida, redzēt to šeit. Ja n brusas ir acīmredzami n reizes n, bet šeit mums ir n reizes log n, un mēs jau zinām no nedēļas nulle, ka log n, logaritmisko, ir labāks nekā kaut lineāra. Galu galā, atgādināt attēlu ar sarkano un dzelteno un zaļās līnijas, kas uzzīmētas, tad green logaritmiska līnija bija daudz zemāks. Un tāpēc, daudz labāk un ātrāk nekā taisni dzeltenās un sarkanās līnijas, n reizes log n ir, protams, labāk nekā n reizes n, vai n brusas. 

Tāpēc mēs, šķiet, ir identificē algoritms sapludināšanu kārtot, kas darbojas daudz ātrāku laiku, un, protams, tāpēc, šonedēļ, kad Mēs redzējām, ka konkurss starp burbulis kārtot, atlase kārtot, un apvienot kārtot, apvienot kārtot tiešām, tiešām uzvarēja. Un tiešām, mums nebija pat jāgaida burbuļu veida un atlases veida pabeigt. 

Tagad pieņemsim vienu citu caurlaide pie tam, no nedaudz vairāk formālā viedokļa, tikai gadījumā, tas rezonē labāk nekā šī augstākā līmeņa diskusijas. Tātad, šeit ir algoritms vēlreiz. Pajautāsim sev, ko darba laiks ir šī algoritmi dažādus pasākumus? Pieņemsim to sadala pirmais gadījums un otra lieta. IF un citur IF gadījumā Ja n ir mazāks par 2, tikai atgriezties. Jūtas kā pastāvīgu laiku. Tas ir, veida, piemēram, divos posmos, Ja n ir mazāks par 2, tad atgriezties. Bet kā mēs teicām pirmdien, pastāvīgs laiks, vai liels o 1, var būt divi soļi, trīs pakāpieni, pat 1000 pakāpieni. Svarīgi ir tas, ka tā ir pastāvīgs vairāki soļi. Tātad dzeltens uzsvēra pseudocode šeit darbojas, mēs to saucam, konstante laiks. Tātad vairāk formāli, un mēs ejam kuri paredzēti, šis būs, cik lielā mērā mēs formalizēt šīs tiesības now-- T n, darbības laiks problēmu kas ņem n somethings kā ievade, vienāds liels o vienu, , N ir mazāks par 2. Tātad, tas ir atkarīgs no tā. Tātad, lai būtu skaidrs, ja n ir mazāks nekā 2, mums ir ļoti īss saraksts, tad darbības laiks, T no n, kur n ir 1 vai 0, šajā ļoti konkrētajā gadījumā, tas tikai būs nemainīga laiks. Tas gatavojas veikt vienu soli, divus soļus, neatkarīgi. Tas ir fiksēts vairāki soļi. 

Tātad sulīgs daļa ir noteikti jābūt otrs gadījums pseudocode. VĒL gadījums. Kārtot kreisā puse no elementiem, kārtot tiesības puse no elementiem, apvienot sakārtotās pusītes. Cik ilgi katrs no šiem soļiem veikt? Nu, ja darbojas laiks, lai sakārtotu n elementiem ir, sauksim to par ļoti vispārēji, T no n, tad šķirošana kreiso puse no elementiem ir, veida, piemēram, sakot, T n dalīts ar 2, un līdzīgi šķirošanas pareizo pusi elementiem ir, veida, piemēram, sakot, T n sadalīta 2, un pēc tam apvienojot sakārtoti pusītes. Nu, ja man daži elementu skaits šeit, piemēram, četri, un dažas numurs Elementu šeit, tāpat kā četri, un man ir apvienot katra no šiem četriem in, un katrs no tiem četri, viens pēc otras, lai galu galā man ir astoņi elementus. Tā uzskata, piemēram, ka ir liels o n soļiem? Ja man n pirkstiem un katrai viņiem ir jāapvieno vietā, tas ir tāpat kā vēl n soļiem. 

Tātad patiešām formulaically, mēs varam izteikt to, kaut nedaudz scarily sākumā skatienu, bet tas ir kaut kas kas atspoguļo tieši šo loģiku. Darbības laiks, T no n, ja n ir lielāks par vai vienāds ar 2. Tādā gadījumā cits lietas, ir T n dalīts ar 2, plus T no N dalīts ar 2, plus liels o n, daži pakāpienu lineārā skaits, varbūt tieši n, varbūt 2 reizes n, bet tas ir apmēram, lai n. Tā, ka, arī ir tas, kā mēs varam izteikt šo formulaically. Tagad jūs nezināt, ja vien Jūs esat ierakstīts to savā prātā, vai meklēt to atbalstīts atpakaļ mācību grāmata, kas varētu būt nedaudz pievilt lapu beigās, bet tas, protams, gatavojas dod mums liels o n log n, jo atkārtošanās ka jūs redzēt šeit uz ekrāna, ja jūs tiešām izdarīja to ārā, ar bezgalīgs piemēri skaits, vai jūs to formulaically, turat redzēt, ka tas, ka šo formulu pati par sevi ir rekursīvs, ar t n pār kaut labajā pusē, un t n pāri pa kreisi, tas var faktiski izsaka, galu galā, kā liels aiziet no n log n. Ja tā nav pārliecināta, ka tas fine tagad, tikai uzņemties ticību, ka tas, protams, ko tas atkārtošanās izraisa, bet tas ir tikai nedaudz vairāk par matemātiska pieeja meklē tajā darbojas laikā sapludināšanas veida pamatojoties uz tās pseudocode vien. 

Tagad pieņemsim mazliet breather no visiem, ka, un veikt apskatīt pārliecināts bijušais senators, kurš varētu izskatīties nedaudz pazīstami, kurš apsēdās ar Google Eric Schmidt, kādu laiku atpakaļ, uz pārrunām uz posmā, pie visu ķekars cilvēku, runājot galu galā par tēmu, kas ir diezgan tagad pazīstams. Pieņemsim to apskatīt. 

Eric Schmidt: Tagad Senator, Jūs esat šeit Google, un man patīk domāt no prezidentūra kā darba interviju. Tagad tas ir grūti, lai iegūtu darbu, kā prezidents. Prezidents Obama: Right. Eric Schmidt: Un jūs esat darīsim [nedzirdama] tagad. Tas ir arī grūti iegūt darbu pie Google. Prezidents Obama: Right. 

Eric Schmidt: Mums ir jautājumi, un mēs lūdzam mūsu kandidātiem jautājumus, un tas viens ir no Larry Schwimmer. 

Prezidents Obama: OK. 

Eric Schmidt: Kas? Jūs guys domā, ka es esmu kidding? Tas ir labi šeit. Kas ir visefektīvākais veids, kā šķirot miljons 32 bitu integers? 

Prezidents Obama: Well-- Eric Schmidt: Dažreiz, varbūt es esmu sorry, maybe-- Prezidents Obama: Nē, nē, nē, nē, nē, es think-- Eric Schmidt: Tas nav it-- Prezidents Obama: I domāju, es domāju, ka burbuli kārtot būtu nepareizs ceļš. Eric Schmidt: Come on. Kas viņam šo teicis? LABI. Es darīju ne datorzinātnes on-- 

Prezidents Obama: Mēs esam ieguva mūsu spiegi tur. PROFESSOR: Nu labi. Atstāsim aiz mums tagad teorētiskā pasaule algoritmu jo asimptotiskās analīzē apakšpunktu, un atgriezties pie dažiem jautājumiem no nedēļas nulli un vienu, un sākt noņemt dažus mācību riteņiem, ja Jums gribas. Tā, ka jūs patiešām saprotat galu galā no zemes uz augšu, kas ir notiek zem motora pārsega, kad jūs rakstīt, apkopot un izpildīt programmas. Atgādināt it īpaši, ka tas bija pirmais C programma, mēs paskatījās, kanoniskās, vienkārša programma par veidu, relatīvi runājot, kur, tas drukā, Hello World. Un atceros, ka es teicu, šis process ka pirmkods iet cauri ir tieši tas. Tu ņem savu pirmkodu, iet tas caur kompilatoru, piemēram šķindēt, un ārā nāk objekta kodu, kas varētu izskatīties šādi, nullēm un uzņēmumiem ka datora CPU, centrālā apstrādes bloks vai smadzenes, galu galā saprot. 

Izrādās, ka tas ir mazliet pārāk vienkāršota, ka mēs esam šobrīd ir amats kaitināt intervālu saprast, kas īsti bijis notiek zem motora pārsega Katru reizi palaižot Šķindēt, vai vispārīgāk, Katru reizi, kad jūs veicat programmu, izmantojot Marka un CF 50 IDE. Jo īpaši, sīkumi, piemēram, Šī ir pirmā radīts, kad pirmo reizi sastādīt savu programmu. Citiem vārdiem sakot, ja jūs veikt savu pirmkodu un apkopot to, kas ir pirmais tiek izvadīts ar šķindēt ir kaut kas pazīstams kā montāžas kodu. Un patiesībā, tas izskatās tieši tā, kā šis. 

I ilga komandu pie komandrindas agrāk. Šķindēt Dash galvaspilsētas s hello.c, un tas radīja failu man sauc par hello.s, iekšpusē, kas bija tieši šie saturs, un nedaudz vairāk virs un nedaudz vairāk zemāk, bet es esmu likts juiciest informācija šeit uz ekrāna. Un, ja paskatās tuvāk, jūs redzēsiet vismaz daži pazīstami atslēgvārdiem. Mums ir galvenais augšpusē. Mēs esam printf leju vidū. Un mums ir arī hello world slīpsvītru n pēdiņās zemāk. 

Un viss pārējais šeit ir ļoti zema līmeņa instrukcija ka datora CPU saprot. CPU instrukcijas, kas pārvietojas atmiņu apkārt, ka slodze stīgas no atmiņas, un galu galā, drukāt lietas uz ekrāna. Tagad to, kas notiek, lai gan pēc tam, kad šis montāža kods tiek ģenerēts? Galu galā, jūs, protams, joprojām rada objekta kodu. Bet soļi, kas ir patiešām turpinās jau zem pārsega izskatās nedaudz vairāk kā šis. Pirmkods kļūst montāža kods, kas tad kļūst objekta kodu, un rezolutīvā vārdi šeit ir, ka, kad jūs sastādīt savu pirmkodu, ārā nāk montāžas kodu, un pēc tam kad jūs savākt savu montāžas kodu, ārā nāk objekta kodu. 

Tagad šķindēt ir super sarežģīta, piemēram, daudz kompilatoru, un tas viss no šiem soļiem kopā, un tas nav obligāti izlaide jebkurš starpposma failus, ka jūs pat varat redzēt. Tas tikai apkopo lietas, kas ir vispārīgs termins, kas apraksta visu šo procesu. Bet, ja jūs patiešām vēlaties būt īpaši, tur ir daudz vairāk notiek tur, kā labi. 

Bet pieņemsim apsvērt arī tagad, ka pat ka super vienkārša programma, hello.c, sauc par funkciju. To sauc printf. Bet man nav rakstīt printf, protams, kas nāk ar C, lai runāt. Tā ir funkcija, atgādināt, ka ir deklarēta standarta io.h, kas ir header fails, kurā ir jautājums, mēs faktiski nirt dziļāk pirms ilgi. Bet header fails ir parasti pavada ar koda failu, kods failu, tāpēc daudz, piemēram, pastāv standarta io.h. 

Dažkārt atpakaļ, kāds, vai someones, arī uzrakstīja failu sauc standarts io.c, jo kuru faktiskais definīcijas, vai implementācijas printf, un ķekarus citas funkcijas, faktiski rakstīts. Tātad, ņemot vērā, ka, ja mēs uzskatām, kam šeit pa kreisi, hello.c, ka tad, kad apkopoti, dod mums hello.s, pat ja Šķindēt nav apnikt ietaupījumu vietā mēs varam redzēt to, un ka montāža kods izpaužas samontēt hello.o, kas Ir, protams, noklusējuma nosaukums ņemot vērā, kad jūs sastādīt avots kodu objekta kodu, bet nav diezgan gatavs izpildīt to vēl, jo vēl vienu soli ir noticis, un ir noticis par pēdējo nedēļas, varbūt nezinot jums. 

Konkrēti kaut kur in CS50 IDE, un tas, Arī, būs mazliet pārmērīga uz brīdi, tur ir, vai bija sensenos laikos, failu sauc standarta io.c, ka kāds apkopo standarta io.s vai ekvivalents, ka kāds tad samontēti par standarta io.o, vai izrādās ārā nedaudz atšķiras fails formāts, kas var būt atšķirīgs faila paplašinājumu vispār, bet teorētiski un konceptuāli, tieši šie pasākumi bija jānotiek tādā vai citādā veidā. Kas ir teikt, ka tagad kad es esmu rakstot programmu, hello.c, ka vienkārši saka, hello world, un es esmu, izmantojot kādu citu kodu piemēram printf, kas bija Reiz laiks, failā ar nosaukumu standarta io.c, tad kaut kā man, lai mana objekts kods, mani nullēm un tiem, un šīs personas objekts kodu vai nullēm un tiem, un kaut kā saistīt tos kopā Viena gala fails, ko sauc sveiki, ka ir visas nulles un tie no mana galvenā funkcija, un visi no nullēm un domātos printf. 

Un tiešām, tas pēdējais process ir sauc, saistot savu objekta kodu. Kuras izejas signāls ir izpildāmais fails. Tātad taisnīgumu, pie Dienas beigās, nekas kas ir mainījies kopš nedēļā vienu, kad mēs pirmo reizi sāka apkopojot programmas. Patiešām, tas viss ir bijis kas notiek zem motora pārsega, bet tagad mēs esam tādā stāvoklī, kur mēs varam reāli ķircināt izņemot šos dažādos pasākumus. Un tiešām, beigās no dienas, mēs joprojām esam atstāts ar nullēm un tiem, kas ir tiešām liels segue tagad uz citu spēju C, ka mēs esam nav bijis, lai piesaistītu visticamāk līdz šim pazīstams kā Bitu līmeņa operatoriem. Citiem vārdiem sakot, līdz šim, jebkurā laikā mēs esam aplūkoti datiem C vai mainīgo C, mēs esam bija lietas, piemēram, chars un pludiņi un ins un ilgojas un dubultspēlēs un tamlīdzīgi, bet visi no tiem ir vismaz astoņi biti. Mēs nekad vēl spējusi manipulēt atsevišķus biti, kaut gan individuāla mazliet, mēs zina, var pārstāvēt 0 un 1. Tagad izrādās, ka C, jums var piekļūt atsevišķiem bitiem, Ja jūs zināt sintaksi, ar kuru nokļūt pie viņiem. 

Tātad, pieņemsim to apskatīt at Bitu līmeņa operatoriem. Tātad attēlotie šeit ir daži simboli, kas mēs esam, veida, veida, redzējis. Es redzu aizvieto & zīmes, vertikāla bārs, un daži citi, kā arī, un atgādina, ka aizvieto & zīmes aizvieto & zīmes ir kaut kas mēs esam redzējuši iepriekš. Loģisks un operators, kur jums ir divi no tiem kopā, vai loģiskā VAI operators, ja jūs ir divas vertikālas joslas. Bitu līmeņa operatoriem, ko mēs sk darboties bitiem individuāli, tikai izmantot vienu aizvieto & zīmes A single vertikāla josla, tad caret simbols nāk nākamais, maz Tilde, un tad pa kreisi kronšteins kreisi kronšteinu, vai Tiesības kronšteins tiesības kronšteins. Katrs no tiem ir dažādas nozīmes. 

Patiesībā, pieņemsim to apskatīt. Iesim vecās skolas šodien, un lietošana touch screen no vakardienas, pazīstams kā balta kuģa. Un šī baltā tāfele gatavojas ļaut mums izteikt dažus diezgan vienkārši simboli, vai drīzāk daži diezgan vienkāršas formulas, ka mēs varam, tad galu galā sviras, lai piekļūt individuāls biti ietvaros C programmas. Citiem vārdiem sakot, pieņemsim to izdarītu. Pieņemsim vispirms runāt priekšlikums moments Ampersand, kas ir Bitu līmeņa un operators. Citiem vārdiem sakot, tas ir operators, kas ļauj man ir kreisās puses mainīgo parasti, un labās puses mainīgo, vai privātpersona vērtība, ka, ja mēs UN tos kopā, dod man gala rezultātu. Tātad, ko es domāju? Ja programmā, jums ir mainīgais kas saglabā vienu no šīm vērtībām, vai pieņemsim glabā to vienkārši, un tikai izrakstīt nullēm un tiem atsevišķi, lūk, kā Ampersand operators darbojas. 0 Ampersand 0 gatavojas vienāds 0. Tagad, kāpēc tā? 

Tas ir ļoti līdzīgs Būla izteiksmes, ka mēs esam apspriests līdz šim. Ja jūs domājat, ka galu galā, 0 ir nepatiesa, 0 ir nepatiesa, nepatiesu un viltus ir, kā mēs esam apspriests loģiski, arī nepatiesa. Tātad mēs 0 arī šeit. Ja esat lietojis 0 aizvieto & zīmes 1, labi, ka arī būs 0, jo par šī kreisā izpausme, lai būtu patiesība, vai 1, tas būtu nepieciešams, lai būtu patiesība un taisnība. Bet šeit mums ir nepatiesa un patiess, vai 0 un 1. Tagad atkal, ja mums ir 1 aizvieto & zīmes 0, ka, arī, būs 0, un, ja mums ir 1 aizvieto & zīmes 1, beidzot mums ir 1 bit. Tātad citiem vārdiem sakot, mēs nedarām kaut kas interesants ar šo operatoru tikai vēl, šī zīme operators. Tas ir Bitu līmeņa un operators. Bet tie ir sastāvdaļas caur kuru mēs varam darīt interesantas lietas, kā mēs drīz redzēt. 

Tagad aplūkosim tikai vienotais vertikāla josla nekā šeit labajā pusē. Ja man ir 0, mazliet, un es VAI tas ar, Bitu līmeņa Vai operators, cits 0 bit, kas notiek, lai dotu man 0. Ja es ņemtu 0 mazliet un vai IT ar 1 bit, tad es esmu gatavojas iegūt 1. Un patiesībā, tikai skaidrība, ļaujiet man iet atpakaļ, tāpēc, ka mani vertikālie stieņi nav sajaukt 1 s. Ļaujiet man pārrakstīt visu mans 1 ir nedaudz vairāk skaidri, lai mēs blakus redzēt, ja es ir 1 vai 0, kas notiek, ir 1, un ja man ir 1 vai 1, ka, pārāk, būs 1. Tātad jūs varat redzēt, loģiski, ka OR Operators uzvedas ļoti atšķirīgi. Tas dod man 0 vai 0 dod man 0, bet katru otro kombinācija dod man 1. Tik ilgi, kamēr man ir viens 1 formula, rezultāts būs 1. 

Savukārt ar AND operators, Ampersand, tikai tad, ja man ir divi 1 ir iekļauts vienādojums, man tiešām iegūt 1 no. Tagad tur ir dažas citas operatoriem, kā arī. Viens no tiem ir mazliet vairāk iesaistīties. Tāpēc ļaujiet man iet uz priekšu un dzēst tas, lai atbrīvotu dažas vietas. Un pieņemsim ieskatieties caret simbols, tikai brīdi. Tas parasti ir raksturs jūs varat ierakstīt uz klaviatūras saimniecības Shift un tad viens no numuriem atop jūsu ASV tastatūra. 

Tātad šis ir ekskluzīvs Vai operators, ekskluzīva OR. Tātad mēs vienkārši redzēja vai operators. Šī ir ekskluzīva vai operators. Kas patiesībā ir atšķirība? Nu pieņemsim tikai apskatīt formulu, un izmantot to kā sastāvdaļas galu galā. 0 XOR 0. Es esmu gatavojas teikt, ir vienmēr 0. Tas ir definīcija XOR. 0 XOR 1 būs 1. 1 XOR 0 būs 1, un 1 XOR 1 būs? Nepareizi? Vai ne? Es nezinu. 0. Tagad to, kas notiek šeit? Nu domāt par Nosaukums šī operatora. Exclusive OR, tā kā nosaukums, veids, liecina, atbilde ir tikai būs 1, ja izejvielas ir ekskluzīvas, tikai atšķirīgs. Tātad šeit izejvielas ir Tas pats, tāpēc rezultāts ir 0. Šeit izejvielas ir Tas pats, tāpēc rezultāts ir 0. Šeit ir rezultāti ir atšķirīgi, tie ir ekskluzīvas, un tā rezultāts ir 1. Tātad, tas ir ļoti līdzīgs Un tas ir ļoti līdzīgs, vai drīzāk tas ir ļoti līdzīgs OR, bet tikai ekskluzīvā veidā. Tas viens vairs nav 1, jo mums ir divi 1 s, un ne tikai, tikai viens no tiem. Viss kārtībā. Kas par citiem? Nu tildes, tikmēr, ir tiešām jauks un vienkāršs, par laimi. Un tas ir unary operators, kas nozīmē, tas ir piemērots tikai vienu ieejas, viens operands, lai runāt. Nav pa kreiso un tiesības. Citiem vārdiem sakot, ja jūs lietojat tildi no 0, atbilde būs pretējs. Un, ja jūs lietojat Tilde par 1, Atbilde būs pretējs. Tātad tildes operators ir veids, noliedzot mazliet, vai flipping mazliet no 0 līdz 1, vai 1 līdz 0. 

Un tas atstāj mūs beidzot tikai ar diviem gala operatoru, tā saukto kreiso maiņu, un tā saukto labo nobīdes operators. Pieņemsim to apskatīt, kā šie darbā. Kreisā maiņu operators, rakstisks ar divām iekavām, piemēram, ka, darbojas šādi. Ja mans ieguldījums, vai mans operands, pa kreisi pāreja operators ir diezgan vienkārši 1. Un es tad pateikt datora uz atstāja maiņu, ka 1., teiksim septiņas vietas, rezultāts ir tā, it kā I pieņemt, ka 1, un pārvietot to septiņas vietas, nekā uz pa kreisi, un pēc noklusējuma, mēs spēsim pieņemt, ka telpa pa labi tiks polsterētām ar nullēm. Citiem vārdiem sakot, 1 atstāja pāreja 7 dodas man dot ka 1, kam seko 1, 2, 3, 4, 5, 6, 7 nullēm. Tātad tādā veidā, tas ļauj jums veikt nelielu skaitu, piemēram, 1, un skaidri padarīt to daudz daudz, daudz lielāks šādā veidā, bet mēs patiešām gatavojas, lai redzētu vairāk gudrs pieejas to vietā, kā arī, 

Viss kārtībā. Tas ir tas par nedēļu trīs. Mēs redzēsim jums nākamo reizi. Tas bija CS50. 

[Mūzikas atskaņošanai] 

SPEAKER 1: Viņš bija pie uzkodām bārs ēst karstu izdomājums Sundae. Viņš bija to visu pār viņa seju. Viņš valkā, ka šokolāde, piemēram bārdu SPEAKER 2: Ko tu dari? SPEAKER 3: Hmmm? Ko? 

SPEAKER 2: Vai jūs vienkārši double dip? Jūs double tuvās mikroshēmā. SPEAKER 3: Piedodiet. SPEAKER 2: Jūs tuvās mikroshēmu, jūs paņēma uzkost, un jūs tuvās atkal. SPEAKER 3: SPEAKER 2: Tātad, tas ir, piemēram, liekot visa tava mute pa labi krituma. Nākamreiz mikroshēmu, tikai iemērc to vienu reizi, un izbeigt. 

SPEAKER 3: Tu zini, ko, Dan? Jūs iemērc tā, kā jūs vēlaties, lai iemērc. Es iemērkšana tā, ka es gribu, lai iemērkšana.