SPEAKER 1: Hej ĉiuj! Bonvenon al sekcio. Tiel ĝojis vidi tantos vin ambaux tie, kaj cxiu, kiu estas rigardi rete. Do, kiel kutime bonvenon reen. Mi esperas ke vi ĉiuj havis belan semajnfino, plena de ripozo, malstreĉiĝo. Estis bela el hieraŭ. Do, mi esperas, ke vi ĝuis la libera aero. Do unue kelkaj anoncoj. Grading. Do, la plimulto de ili devus esti alveninta al retmesaĝi de mi pri via Scratch Pset, krom grading por Pset 1. Do, nur paro aĵoj. Nepre uzu check50 en style50. Tiuj estas signifita esti rimedojn por vi uloj, por certiĝi, ke vi fariĝas kiel multaj punktoj kiel vi povas sen senbezone perdi ilin. Do, aĵoj kiel stilo estas tre grava. Ni iras al despegar por ĝi. Iuj el vi eble jam rimarkis ke de via Pset. Kaj check50 estas nur vere facila maniero por certigi ke ni vere revenis kio bezonas reveni al la uzanto, kaj ke ĉio funkcias konvene. Sur la dua noto, certigu vian alŝuti aĵojn por la ĝentila dosierujo. Ĝi faras mian vivon nur Iomete pli malfacila se vi alŝutu Pset 2 en Pset 1 ĉar kiam mi elŝuti aferojn, ne elŝuti korekte. Kaj mi scias, ke tio iom wonky en sistemo kutimi, sed simple esti súper zorgu, se nur por mi, tiel ke kiam vi fariĝas retpoŝtojn ĉe kiel 2-a horo matene kaj mi grading. Se ne tio mi devas rigardi ĉirkaŭe por via Pset. Malvarmeta. Mi scias ke estas frue, sed mi tute got forlevata gvardio per eseon tio pro tiu vendredo, ke miaj profesoroj ĵus ŝatas, oh yeah. Memoru, vi havas eseo pro vendrede. Do, mi konas neniun ŝatas pensi midterms, sed via unua kvizo estas sur Oktobro 15, kio oktobro komenciĝas ĉi-semajne. Do, eble estus pli frue ol vi atendis estas ĉio. Por ke vi ne ĵetitaj desprevenida kiam Mi mencias sekva semajno sekcio kiu ho, vian kvizon sekva semajno, mi pensis Mi ŝatus doni al vi iom pli de kapoj nun. Do, via problemo aro, numero tri. Kiel homoj legis la Spec pro scivolemo? OK. Ni ricevis paron. Speco de sube de lasta semajne sed tio estas en ordo. Mi scias, ke estis bela ekstere. Do Break Out. Definitive post vi get farita hodiaŭ legis vian specifon almenaŭ provu kiel elŝuti dissendo kodo kaj kurado kiel la unua komenca kion oni petas al vi. Ĉar ni estas uzanta dissendo kodo kaj biblioteko ke ni nur using-- --It nur duafoje ni faris ĉi Pset, frenezaj aĵoj povas okazi kun via aparato, kaj vi volas trovi ke el nun kontre poste. Ĉar se estas ĵaŭdo nokte aŭ estas Merkredo nokte kaj ial via aparato simple ne volas funkcii kun la biblioteko aŭ kun la dissendo kodo, ke per Vi eĉ ne povas komenci fari la kodigon. Ĉar vi ne povas kontroli vidi se funkcias. Viaj ne gonna povos por vidi se ĝi kompilas. Vi volas prizorgi tiujn frue la semajno, kiam vi ankoraŭ povas retmesaĝi min aŭ unu el la aliaj TFS, kaj ni povas akiri tiujn fiksita. Ĉar tiuj estas demandoj ke tuj haltos vin el farante ajnan realan progreson. Ne estas kiel unu cimon, ke Vi povas simple speco de salti super. Se vi havas demandojn per viaj aparato aŭ dissendo kodo, vi vere volas bonstata prenita Zorgi pri frue anstataŭ poste. Do eĉ se vi ne gonna reale komenci kodigo, elŝutu la distribuo kodo, legu la specifo, certigu ĉio laboras tie. OK? Se vi povas simple fari tion, mi promesi viajn vivojn estos facila. Kaj tiel vi probable irante fari ĝin ĝuste nun justa? OK. Do, demandojn tie? Ajna logistika aferojn? Ĉies bono? OK. Disclaimer por tiuj de vi en la ĉambron kaj online. Mi tuj esti provante ŝanĝi inter PowerPoint en la aparato ĉar tuj esti farante iu kodigo hodiaŭ por populara peto de la anonima sugesto enketo mi sendis lastan semajnon. Do, ni faros kelkajn kodigo. Do, se vi uloj volas ankaŭ pafi viajn aparatojn, kaj vi ricevus email de mi kun specimeno dosiero. Bonvolu senti liberan fari tion. Do, ni tuj parolu pri GDB, kiu estas sencimigilon. Ĝi tuj helpi vin speco de elŝeligi kie aferoj iras malbone en via kodo. Estas vere nur vojo por vi tretas tra via kodo kiel okazas, kaj povos elprinti variabloj aŭ vidi kio reale okazis sub la kapuĉo versoj via programo nur kurante, estas kiel faulting, kaj vi estas kiel, neniu ideo kio ĵus okazis tie. Mi ne scias kion linio malsukcesinta ĉe. Mi ne scias, kie li estis malĝusta. Do, GDB tuj helpi vin kun tio. Ankaŭ, se vi decidas daŭrigi jes, kaj prenu 61, gxi vere, vere via bona amiko, ĉar mi povas diri al vi ĉar Mi iras tra tiu klaso. Ni tuj rigardi duuma Serĉu, kaj se vi uloj memori la granda telefono libro ekzemplo spektaklo de klaso. Ni devas apliki tion, kaj promenante tra tiu iom pli, kaj tiam ni iras tra kvar malsamaj varoj, kiuj estas Bubble, Selektado, Insertion kaj Merge. Malvarmeta. Do, GDB kiel mi menciis, estas sencimigilon. Kaj tiuj estas speco de la granda aĵoj, la grandaj funkcioj aŭ komandoj ke vi uzas ene GDB, kaj Mi iros vi tra demo ĝin en dua. Do, ĉi tiu estas ne nur restos abstrakta. Mi provos kaj faros gxin kiel betono kiel ebla por vi uloj. Do, rompi. Ĝi devos ĉu esti rompo kiel, iu nombro, kiu reprezentas linio en via programo, aux vi povas nomumi funkcio. Do, se vi diras rompi ĉefa, ĝi haltos ĉe ĉefa, kaj lasos vin iri tra tiu funkcio. Simile, se vi havas iuj eksteraj funkcii kiel Swap aŭ Cube, ke ni rigardis pasintan semajnon. Se vi diras malobservos unu el tiuj, kiam via programo batas ke, ĝi atendos vin sciigi, kion fari. Antaŭ tio nur ekzekuti tiel vi povus reale enpaŝi la funkcio kaj vidu kio okazas. Do, tuj, simple saltas super la sekva linio, iras super funkcioj. Paŝo. Tiuj estas ĉiuj iom abstrakta. Do, mi simple tuj kuras tra ili, sed vi vidos ilin en uzo en dua. Paŝi al funkcio. Tiel kiel mi diris, kiel kun Swap, estus permesas al efektive kvazaŭ vi estas kiel fizike tretante enen, vi povas salaton kun tiuj variabloj, print kio estas, vidos kio okazas. Listo estos laŭvorte nur presi el la ĉirkaŭa kodo. Do, se vi ia forgesi kie vi estas en via programo, aŭ vi demandante kio okazas ĉirkaŭ li, tio ĝuste presi segmento de kiel kvin aŭ ses linioj ĉirkaŭ ĝi. Do, vi povas get orientis pri kie vi estas. Presi kelkaj variabloj. Do, se vi havas la ŝlosilon ŝatas en Cezaro, ke ni rigardu. Vi povas diri Presi Ŝlosilo en ajna punkto. Ĝi diros al vi, kion la valoro estas tiel ke, eble ie survoje, vi overwrote via ŝlosilo. Vi povas fakte diri ke ĉar Vi povas fakte observi tiun valoron. En la lokanoj, nur impresoj el via loka variabloj. Do, anytime vi ene banto, kaj vi simple volas vidi kiel, oh. Kio estas mia mi? Kio estas ĉi tiu ŝlosilo valoro ke mi pravalorizi ĉi tie? Kio estas la mesaĝo ĉe tiu punkto? Ĝi simple presi ĉiuj de tiuj, por ke vi ne devas individue diru Presi I. Presi Mesaĝo. Print Ŝlosilo. Kaj tiam Montriĝo. Kion faras estas kiel vi paŝo tra la programo, ĝi devos simple certigi ke ĝi estas montrante iuj certaj variablo je ĉiu punkto. Por ke vi also-- --it estas speco de ŝparvojo kie vi ne devas teni irante kiel, oh. Print Ŝlosilo aŭ Presi I. Ĝi simple aŭtomate fari ĝin por vi. Do, kun tio, ni iras Vidi kiel ĉi iras. Mi tuj provos kaj ŝaltilo super mian aparaton. Vidu se mi povas fari ĉi tion. Ĉiuj. Ni nur tuj speguli ĝin. Nenio freneza sur mia tekkomputilo anyways. OK. Ĉi devas esti ĉi tiu. Estas tiom eta. Vidu se ni povas fari ĉi tion. OK. Alice estas evidente baraktante tie nur iomete, sed ni akiros ĝin en momento. OK. Ni nur tuj pliigos ĉi. OK. Povas ĉiuj speco de vidi ke? Eble iomete? Mi scias ke estas iom malgranda. Vi ne povas tute elkompreni kiel fari tiu granda. Se iu scias. Ĉu iu scias kiel fari ĝin pli granda? OK. Ni tuj ruliĝi kun ĝi. Ne gravas anyways ĉar estas nur tio estas la kodo kiu vi uloj devus havas. Kio estas pli grava estas la fina tie. Kaj ni havas tie Kial estas tiel malgranda? Agordojn. Oh. Vera Ike. Kiel estas tio? El tie. Estas kiu pli bona por ĉiuj? OK ,. Malvarmeta. Vi scias, kiam vi estas en CS klaso teknikajn malfacilaĵojn estas ia parto de the-- Do, ni purigi ĉi. OK. Do, ĉi tie en sekcio, kiun ni havis ĉi tie. Cezaro estas plenumebla dosiero. Do mi faris ĝin. Do unu afero realigi kun GDB estas ke nur funkcias sur plenumeblajn dosierojn. Do, vi ne povas kuri ĝin sur dotsy. Vi devas efektive fari certa ke via kodo kompilas, kaj kiu povas fakte esti lanĉita. Do, certigi ke se ĝi ne kompili, prenu gxin por kompili, por ke vi povu ia trafluas ĝin. Do, por komenci GDB, ĉiuj vi devas fari; Gloria tipo GDB, kaj subite la dosiero, kiun vi volas. Mi ĉiam misspell Cezaro. Sed vi volas certigi ĉar ĝi estas plenumebla, ti la skalara flash por ke signifas ke vi iras kuri CSI vi tuj ekzekuti ĉi fajlilo ĉu kun la erarserĉilo. OK. Do, vi faros tion, vi ricevos tiu speco de stultaĵoj. Estas nur ĉio pri sencimigilon. Vi ne vere devas maltrankviligi ŝin nun. Kaj kiel vi vidas, ni havas ĉi malfermita parens, GDP, proksime parens, kaj ĝuste speco de aspektas nia komandlinio, dekstra? Do, kion ni volas do-- --So, La unua afero Estas ni volas elekti loko por rompi ĝin. Do, ekzistas unu cimon en ĉi Caesar programo ke mi prezenti, ke ni iras al elŝeligi. Ĝi Kio ĝi estas prenas la enigo Barfoo en ĉiuj kaskedoj kaj ial ĝi ne ŝanĝas A. Ĝi nur lasas ĝin sole, Ĉu ĉio ĝustas, sed la dua letero A restas neŝanĝita. Do, ni tuj provi elŝeligi kial tio estas. Do, la unua afero vi tipe volas fari kiam vi komencas en GDB estas elkompreni kie rompi ĝin. Do Cezaro estas sufiĉe mallonga programo. Ni nur havas unu funkcion, dekstra? Kio estis nia funkcio en Cezaro? Ekzistas nur unu funkcion, Ĉefa dekstra? Ĉefa estas funkcio por ĉiuj viaj programoj. Se vi ne havas Main, mi povus iom maltrankviliĝis nun, sed mi esperas, ke vi ĉiuj havis Ĉefa tien. Do, kion ni povas fari estas ni povas nur rompi Main, ĝuste tiel. Do, ĝi diras, OK. Ni metis niajn Haltpunkto unu tie. Do, nun la afero memori estas Cezaro prenas unu komandlinio argumento dekstra kaj ni ne faris tion, ie ankoraŭ. Do, kion vi faras kiam Vi vere iru kuri La programo, ajna programo kiu vi estas kurante en GDB kiu bezonas komandlinio argumentojn, vi tuj enigo kiam vi unue komencos kuri ĝin. Do, en ĉi tiu kazo, ni faru Kuri kun ŝlosilo de tri. Kaj ĝi efektive komenci. Do, se vi vidas tie, ni havas Se RC estas ne egala al 2. Do se vi uloj ĉiuj havas ke dosiero ke mi sendis supren vi vidos, ke tio estas kvazaŭ la unua linio nia ĉefa funkcio, dekstra? Ĝi estas kontrolanta vidi se ni havas la ĝusta nombro de argumentoj. Do, se vi scivolas se RC estas ĝentila, vi povas fari ion ĝuste kiel Presi RC. RC estas du, kio estas kion ni atendis, ĉu ne? Do, ni povas iri Venonta, kaj daŭrigas tra. Do, ni havas iun klavon tie. Kaj ni povas presi niajn ŝlosilo por certiĝi ke estas korekta. Interesa. Ne tute kion ni atendis. Do unu afero realigi kun GDB ankaŭ, estas ke ne ĝis vi efektive trafis Next, la linio kiun vi ĵus vidis fakte ekzekutita. Do, en ĉi tiu kazo Ŝlosilo ne estis atribuita ankoraŭ. Do, Cayo estas iuj rubo valoro ke vi vidas sur la fundo. Negativa $ 120-- --It la unu miliardo kaj iom strange aferojn dekstra? Ĝi ne estas la ŝlosilo kiun ni atendis. Sed se ni batis Venonta, kaj poste ni provu Presi ŝlosilon, estas tri. Ĉiuj vidis? Do, se vi prenos ion ke vi ŝatas, atendu. Tio estas tute malĝusta, kaj mi ne scias kiel tio okazus ĉar mi volas fari estas atribui numeron, variablo, provu bati Next, provu printado denove, kaj vidi se tiu funkcias. Ĉar ĝi estas nur tuj ekzekuti kaj efektive asigni ion post vi batita Next. Sencon por ĉiuj? Uh huh? SPEAKER 2: Kiam vi hazarda nombroj kion tio signifas? SPEAKER 1: Estas nur hazardo. Estas nur rubon. Estas nur ion ke via komputilo hazarde atribui. Malvarmeta. Do, nun ni povas movi tra, ktp Nun ni havas ĉi tekstaj GetString. Do, lasu min simple enkonduki kio okazos kiam ni batis Sekva tie. Niaj GDB ia malaperas, ĉu ne? Tio estas ĉar GetString nun ekzekutas, dekstra? Do, kiam ni vidis tekstaj egalas GetString, malferma parens kaj parens, kaj ni batis Next, kiu havas fakte ekzekutita nun. Do, ĝi estas atendante Ni enigi ion. Do, ni tuj input nia manĝaĵo kiu estas kio ĝi estas maltrafi kiel mi diris al vi, kaj ke nur diras ke ĝi estas finita ekzekuti, ke la fermita krampo signifas estas forlaso el tiu buklo. Do, ni povas bati Venonta, kaj nun, dum mi estas certe vi ja ĉiuj konas de Cezaro, tio estas, kio estas ĉi tiu linio tuj faros. Estas por Mez mi egalas 0, N egalas Strlen, plata teksto, kaj tiam Mi estas malpli ol n, mi, pli, pli. Kio estas ĉi tiu buklo faros? Malfermu vian mesaĝon. Malvarmeta. Do, ni komencu fari tion. Do, ĉu ĉi tiu kondiĉo parigi, por nia unua? Se ĝi estas B, estas tekstaj I. Ni povas akiri informojn pri niaj lokaj. Do, mi estas nulo, kaj se ses, kiuj ni atendas, kaj nia ŝlosilo estas tri. Ĉio tio havas sencon, ĉu ne? Tiuj nombroj estas ĉiuj ĝuste kio ili devus esti. Do, zumas? SPEAKER 3: Mi havas hazardaj nombroj por mia. SPEAKER 1: Nu, ni povas check-- --we povas babili pri tio en dua. Sed vi devus akiri ĉi. Do, se ni havas majusklan B por nia unua, tiu kondiĉo devas kapti ĝin, ĉu ne? Do, se ni batis Tuj, ni vidu ke tio Se efektive ekzekutas. Ĉar se vi jenajn kune en via kodo, tiu linio tie, kie tekstaj mi estas anstataŭita per tiu aritmetiko, nur ekzekutas se Se kondiĉo estas korekta dekstra? GDB nur tuj montros al vi kio estas reale ekzekuti. Do se tio Se kondiĉo ne renkontis, estas nur tuj saltas al la sekva linio. OK? Do, ni havas tiun. Ĉi krampo signifas estas fermita el tiu buklo nun. Do, ĝi tuj komencas denove. Ĝuste tiel. Tiel, ke ni povas akiri info pri niaj lokaj tie, kaj ni vidos, ke nia unua letero ŝanĝiĝis, ĉu ne? Estas nun E, kiel devus esti. Do, ni povas daŭrigi plu. Kaj ni havas ĉi ĉeko. Kaj tiu ĉeko devas labori, ĉu ne? Estas A. Ĝi devus esti ŝanĝita tri leteroj antaŭen. Sed se vi rimarkas, ni akiri iun malsama. Do en tiu kazo ĝis tie, li kaptis ĝin, kaj tial tiu linio ekzekutitaj, kio modifita nia B. Sed, en tiu kazo tie, ni havas ke nur saltis ĝi, kaj iris al la [? L Siff. ?] Do io okazas tie. Kio tio estas diranta al vi estas tiu, Ni scias ke ĝi devus kapti tie, sed estas ne. Ĉu iu povas vidi kion niaj problemo estas en tiu linio? Ĝi estas tre minuto afero. Kaj vi povas ankaŭ rigardi vian kodon. Ĝi estas ankaŭ line-- forgesu kion linio estas en there-- sed estas en la [inaudible]. Jes? SPEAKER 4: Ĝi estas sur la pli granda ol paĝo se vi legas ĝin en la libro. SPEAKER 1: Ekzakte. Do, la erarserĉilo ne povus diri vi tion, sed la erarserĉilo povis akiri vin malsupren al linio ke vi konas ne funkciis. Kaj kelkfoje, kiam precipe poste en la semestro, kiam vi kontraktanta kun cento, al cent malmultaj linioj de kodo, kaj vi ne scias, kie ĝi estas maltrafante, ĉi estas granda vojo por fari ĝin. Do, ni trovis nian cimon. Vi povas fiksi ĝin en vian dosieron, kaj tiam vi povus ruli ĝin denove, kaj ĉio funkcius perfekte. Kaj la plej granda aĵo tio povas ŝajni, OK. Yeah. Malvarmeta. Vi sciis, kion vi serĉas. Do, vi sciis, kion fari. GDB povas esti súper utila ĉar vi povas presi cxiujn tiujn farojn, kiujn vi ne volis. Ĝi estas multe pli utila ol printf. Kiel multaj el vi uzas kiel printf deklaroj elkompreni kie cimo estis, ĉu ne? Do, kun ĉi tio, vi ne devi teni reiri, kaj kiel dirante en Printf, aŭ komentoj ekstere, kaj elkompreni Vi devas presi. Tiu fakte nur permesas paŝo tra, presi tion kiel vi estas iranta tra, tiel, vi povas observi kiel ili ŝanĝas en reala tempo kiel via programo kuras. Kaj ne prenu iom iom de kutimante. Mi forte rekomendas ĝuste speco esti iom frustrita kun ĝi por nun. Se vi pasigas horon super la sekva semajno lerni kiel uzi GDB, vi savos vin mem tiom da tempo poste. Kaj laŭvorte. ni diru tio al personoj ĉiu jaro, Mi memoras kiam mi prenis la klaso, mi estis kiel, mi estos bone. No. Pset 6 eliris kaj mi kiel, mi gonna lerni kiel uzi GDB ĉar mi ne scias kio okazas tie. Do se vi preni la tempon por uzi gxin en malgrandaj programoj ke vi tuj estos funkcias plu, kiel labori tra iu kiel Visionare, kiel tiu. Aŭ se vi volas ekstrajn praktiko, mi certas Mi povis veni supren kun kalesxo programoj, Vi devas elpurigi se vi ŝatus. Sed se vi nur bezonos iom da tempo por akiri kutimiĝis, bonvolu ludi kun ĝi, ĝi vere servos al vi bone. Kaj estas vere unu el tiuj aferoj kiujn vi ĵus devas provi kaj instigi viajn manojn malpurajn kun, antaŭ vi vere komprenis. Mi vere nur komprenis ĝin unufoje Mi devis elpurigi aferojn kun ĝi, kaj tio estas multe pli agrable havi ideon de kiom elpurigi frue anstataŭ poste. OK. Malvarmeta. Mi scias ke estas speco de kiel urĝa kurso en GDB, Mi certe laboros pri atingi tiuj rigardi granda venontfoje. Malvarmeta. Do, se ni reiru al nia PowerPoint. Estas ĉi irante labori? Awh. Jes. OK. Do, se vi bezonos iun el tiujn denove, tie estas la listo. Do Binary Search, kiun chiuj memoras la grandan spektaklon de Davido ŝiri telefono libroj en duono. Mi ne vere akiri la telefono librojn plu, ĉar kiel kie vi akiri telefonon libroj tiujn tagojn? Mi vere ne scias. La Binary Search. Ĉu iu memoras kiom Binary Serĉo verkoj? Iu ajn? Yeah? SPEAKER 5: Vi scias, kiam Vi rigardu, kiu duone estus en, Bazita sur tio, kaj liveri de la alia duono. SPEAKER 1 Ĝuste. Do, Duuma Search, estas speco de a-- --we ŝatas nomi ŝin dividi kaj venki. Do, kion vi devos fari estas vi rigardu en la mezo, kaj vi vidos se ĝi egalas kion vi serĉas. Kaj se ne, tiam oni provas elkompreni, estas tio tuj estos lasita duono aŭ la dekstra duono. Do, tiu povus esti se vi serĉas en iu kiu estas alfabetizado, vi vidas, ho. Ĉu Allison venu antaux M? Jes. Do, ni tuj rigardi la unuan duonon. Aŭ ĝi povus esti kiel kun nombroj. Anything ke vi povas kompari, ĝi povas esti ordo. Vi povas uzi duuma serĉo plu. Do, iu memoras ĉi grafeo aŭ kia estas? Estas Asimptota Komplekseco. Do, ĉi grafikaĵo nur priskribas kiom longe prenas vin solvi problemon kiel Vi pliigas la nombron de aferoj ke vi uzas. Do, ni havas n, kiu estas lineara tempo. Se N super du, kio estas iomete bona, ankoraŭ kreskas super rapida. Kaj tiam ni Ensaluta, kio estas kion ni konsideras Binary Search. Se ni rimarkos, kiel via problemo ricevas multe kaj multe pli granda, la tempa ĝi prenas vin solvi ĝin vere ne pliigos ke multe. Estas kiel kompareblaj tie en la komenco. Vi ŝatas, OK. Nenio ĉi tie ne vere gravas kiun el ni uzas, sed vi eliru por miliono, miliardo. Vi provas trovi some-- --you're provante trovi nadlo en garbejo. Mi pensas ke vi volas ĉi tiun problemon. Vi volas kompleksecon, ne lineal ĉar por ĉiu vi koni vian gonna esti trasercxante ĉiu individua nadlo, aĵo de fojno, provante serĉi vian nadlo. Kaj tio ne estas tro amuza miaopinie. Mi ŝatas rapida. Mi ŝatas eficiente. Kaj kiel laboristo studentoj vi infanoj estas, vi scias labori inteligenta, Ne malfacila tipo afero, kiel vi povas fari tiujn algoritmojn. Do, ni iras promeni tra nur rapidan ekzemplon. Mi kredas ke vi infanoj devus havi mano sur Binary Search, sed se iu estas iom lanuga, volas plifortigi ĝin, Ni tuj ĝuste iri tra ekzemplo tie. Do, ni serĉas se La tabelo enhavas sep. Do, unue ni faras estas rigardi en la mezo, dekstra? Kaj ankaŭ vi tuj estos kodigo Duuma Serĉo en nur dua. Do, ĝi tuj estos amuza. Do ni atendu la mezo iom arrays 3. Ĉu 3 egalas 7? Ne. Estas ses. Do, ĝi estas malpli ol aŭ pli granda ol sep? Malpli ol. Jes. Nice laboron infanoj. Mi sentas min ŝatas mi devus havi bombono, ĉar mi voli ĵeti ĝin en la kortoj. Ĝi estas kion mi tuj faros la proksiman semajnon. Ĝi vin gardos infanoj akra. Do, ni forĵetu ke unua duono, dekstra? estis malpli ol. Ni scias ke ĉiu sur tiu maldekstra flanko tuj estos malpli ol kion ni fakte serĉas. Do, estas nenia bezono atentu lin. Simple forgesi pri tio. Do, nun ni rigardos niajn dekstra flanko, kaj ni rigardu la mezo tien, kaj nun estas naŭ. Do, 9 is-- --Everyone? Pli granda ol kio ni estas serĉante, ĉu ne? Do, ni tuj ĵeti for ĉiun dekstre. Tiel. Nun, ĉiuj ni marŝis kun unu. Do ni kontrolu, estas ĉi tiu kio Ni serĉas? estas. Ni trovis kion ni deziris. Do ni faris. Dulineara Search. Se vi rimarkas, ni havis sep enigoj tie. Ĝi nur prenis nin kiel tri fojojn, sed se vi faras kiel biliono, vi uloj scias kiom da paŝoj li volus preni se ni havis kvar miliardoj aferojn? Ajna divenas? Ĝi estas 32. 32 paŝojn por trovi ion en kvar miliardoj elemento tabelo pro potencoj de du. Do du estas 32, estas kvar miliardoj. Tiel bela freneza kiom vi ankoraŭ ene kiel sufiĉe malgranda nombro da ŝtupoj trovi ion kvar miliardoj elementoj. Do en tiu noto, ni estas tuj programi tiu tial vi uloj povas reale speco de vidi kiel tio funkcias. Bone, do vi uloj povas kodigi. Mi tuj lasos infanoj paroli iomete. Konatiĝu personoj ĉirkaŭ vi, kiu estas kion iu volis de lasta sekcio. Tiel ekkoni la homojn ĉirkaŭ vi. Paroli iomete. Kaj mi volas de vi infanoj nun estas nur provu krei modelon de _pseudocode_. OK? Halt. Mi volas de vi uloj estas vi nur tuj plenigi ĉi dum kazo. Do mi proponis tiujn suprajn kaj subaj baroj kiuj reprezenti la komenco kaj la fino de nia tabelo. Kaj vi tuj reale banto tra kaj elkompreni kion ni faras ene de tiu tempo buklo. Do se vi povas diveni out-- mi aludo there-- kio estas kazoj ke ni havas ĉi tie? Do se vi volas eltrovi la kazoj, ni _Pseudocode_ tiuj kaj tiam ni efektive programi ilin. Kaj tuj estos, mi opinias, espereble ĝi malebligos esti iom pli facila ol vi supozas. Ĉar ne ke multe kodon, efektive, kio estas vere genia. Hmm? Student: [inaudible]? Instruisto: Jes. Okazis io trovi en la mezo. Student: Do ni povas uzi tiun. OK. Instruisto: Perfekta. Do tio estas la unua aĵo kiun ni bezonas por fari. Do trovu la mezo. Granda. Do ĉu vi havas ideon de kiel ni povus vere trovos la mezo kun kodo? Student: Yeah. n ol 2? Instruisto: Do ​​n super 2. Do unu afero por memori estas ke via supra kaj subaj baroj ŝanĝi. Ni daǔre constricting la parto de la tabelo ni serĉas. Do n super 2 funkcias nur por la unua afero kiun ni faras. Tiel prenante supra kaj malsupra en rakontas, kiom eble ni atingos, ke meza ero? Ĉar ni deziras la mezo inter supra kaj malsupra dekstra? Hmm? Student: [inaudible]. Instruisto: Do ​​ni havas iom meza. Kaj tio estos supra plus malsupra ol 2. Awesome. Tie ni iras. Unu linio suben. Vi ĉiuj estas sur via vojo. Do nun ke ni havas niajn mezo, kion ni volas fari? Nur ĝenerale. Vi ne devas programi ĝin. Jes. Student: [inaudible]? Instruisto: Do ​​ĝi estas pli ĉar vi estas trovanta la mezumo inter la du de ili. Do, se vi pensas pri ili, kiel speco de kreskanta el la flankoj, pensi pri ĝi kiel vi alproksimigi meze, vi volas tiel. Do se vi estus ambaŭflanke de la mezo, kaj ni havas kiel 5 kaj 7. Kiam vi aldonas ilin al vi akiri 12, vi dividos 2, estas 6. Kelkfoje estas malfacile klarigi kial tio funkcias, sed se vi laboras per ekzemplo kelkfoje, Ĝi helpos vin eltrovi se Ĝi devus esti pli aŭ malpli. Jes. Student: [inaudible] precize en la mezo se ili havis kazon kie tie estas multa pli malgrandaj nombroj kaj kiel unu granda nombro? Instruisto: Do ​​ĉiuj vi bezonas Estas la mezo de la tabelo. Do se vi havis amason de malgrandaj nombroj kaj tiam oni vere granda nombro fine, ne gravas. Ĉiuj kiu importas estas kiu ili estas ordigataj vi nur deziras rigardi la mezo de la tabelo ĉar vi estas ankoraŭ tranĉaĵanta vian problemon en la duono. Malvarmeta. Do nun ke ni havas la mezo, kion ni faru nun? Student: Komparu. Instruisto: La kompari. Do kompari mezo al value_wanted. Malvarmeta. Do vi vidas tie supre ni havas tiun valoron ni volas tie supre. Memoru ke ni estas tabelo. Do mezo referencas al la indekso. Do ni volas fari valorojn de meza. Ne forgesu, se vi volas kompari, duobla egalaj. Vi do sola egalas vi nur tuj religi ĝin, kaj tiam, kompreneble, estas tuj estos la valoro vi volas. Do ne faru tion. Do ni tuj vidos se la valorojn ĉe la mezo estas egala al la valoro ni volas. Ne forgesu vian krampoj. Dropbox devus foriri. Do kion ni faru en tiu kazo? Se ĝi estas kion ni volas reveni? Ni provas diri. Student: Presu ekstere. Instruisto: Nu, ni ne volas presi ekstere. Do tio estas bool tie, do ni volas reveni vera aŭ malvera. Ni diras, estas tiu nombro unu [? RRA? ?] Do se ĝi estas, Ni nur redoni ĝin vera. Se mi povas literumi vera. Student: Kial vi ne revenos nulo? Instruisto: Tiel vi povus reveni nulo se vi volas. Sed en ĉi tiu kazo, ĉar nia funkcio redonas bool, Ni bezonas reveni ĉu vera aŭ malvera. Student: Kiam vi estas dirante bulea esprimo ĉu vi starigis ĝin egala al falsa? Kiel se mi volas diri, se tiu kondiĉo ne konis, kiel estas supra egalas malvera. Ĉu ĝi komprenos se vi nur metis falsajn transe? Instruisto: Jes. Do efektive, se vi estas iam fari ion kiel estas supra aŭ estas pli malaltaj, kiu revenas vera aŭ malvera kaj ĝi estas efektive malbona stilon diru egalas egalas veraj aŭ egalaj egalas malvera. Vi volas uzi tiun rezulto kiel kiel via ĉeko. Ne, kion mi volis. Tio estas kion mi volis. Do, en la kazo de vi demandante pri iu kiel savi ĉi en c. Do se ni havas int main (void) kaj ion kiel tiu. Kaj vi havas se estas supraj de iu enmeton kaj vi demandante se vi povas fari ion similan? Rajto? Lernanto: Mi provis fari ĝin [inaudible]. Ĉar se it's-- Instruisto: Ĝuste. Do vi volas ĉi tion al esti malvera, dekstra? Student: Yeah. Instruisto: Do ​​en tiu kazo vi volas lin ekzekuti se ĝi ne estas vera. Do la malvarmeta afero vi estas tio. Do memoru ekkrio punkto neas tion? Ĝi diras [inaudible] signifas ne. Do se ni rigardas nur tiun parton ĉi tie, oni kredus diri ke taksas al falsa kiel vi deziras ĝin. Ne falsaj veras kion signifas tiu ekzekutus. Ĉu tio havas sencon? Student: Yeah. Instruisto: Awesome. OK. Do ni povus simple reveni vera en tiu kazo. Do nun ni havas du aliajn kazoj en tiu kazo. Kio estas niaj du aliajn kazojn? Ni nur faru gxin tiamaniere. Do ni komencu per alia se taksas je la mezo estas malpli ol la valoro ni volas. Do nia valoro en la mezo estas malpli ol la valoro kiun ni serĉas. Do kion baro vi ke ni volas ĝisdatigi? Supra aŭ suba? Supra? Do kiu flanko de la tabelo ni tuj estos rigardante? Student: La malsupra. Instruisto: Ni ni iras esti rigardante maldekstren. Do alie se malmulta valoro estas malpli. Do via mezo valoron tie estas malpli ol kion ni volas. Do ni volas preni la dekstra flanko de nia tabelo. Do ni tuj ĝisdatigi niajn suba baro. Do ni religi nian malsupra. Kaj kion vi pensas malsupra devus esti? Student: La meza valoro? Instruisto: Do ​​la mezo value-- Student: Plus 1. Instruisto: --plus 1. Ĉu iu povas diri al mi, kial Ni havas tiun plus 1? Student: [? Neniu valoron?] estas pli egala al gxi. Instruisto: Ĝuste. Ĉar ni jam scias ke nia mezo valoro ne egala al kaj ni volas ekskludi ĝin de ĉiuj postaj serĉoj. Se vi forgesas ke plus 1, ĉi ŝatos buklo nedifinite. Kaj vi nur estos kaptitaj en senfina buklo kaj tiam vi segfault kaj aĵoj iras malbone. Tiel ĉiam certiĝu, ke vi ne inkludante la valoro kiun vi ĵus rigardis. Do ni prizorgas ke kun alpago 1. Do nun ni havas nia lasta kondiĉo kiun mi ĉiam por sekureco sake vi povas kontroli ĉi tie, alie se valoro Meze estas pli granda ol la valoro ni volas. Tio signifas, ke ni volas maldekstre duono. Do kiu ni tuj ĝisdatigi? Supra. Kaj kio estas ĉi tiu tuj egalos? Meza minus 1 ĉar, kompreneble ni volas por certiĝi, ke ni estas ne rigardante ke meza valoro denove. Kaj tiam ni havos. Nur tio. Jen ĉio duuma serĉo estas. Ne estas tiel malbona, dekstra? Estas kiel 10 linioj de Kodo kun blanka spaco. Do tre potenca, tre utila, vi volas esti uzante ĝin en unu el viaj postaj psets. Eble tio ne estas unu, sed poste. Tiel lernas ĝin. Amas ŝin. Ĝi traktos vin bone. Do ĉu iu havas ajnan demandoj pri duuma serĉo? Jes. Lernanto: Ĉu gravas ĉu via n estas para aŭ nepara? Instruisto: No. Ĉar ni jxetu gxin en la mezon de de int, gxi simple malpligrandigi ĝin. Do ĝi restos entjero kaj ĝi volas eventuale ordigi tra ĉio. Do vi ne devas maltrankviligi pri tio. CXiu bona? Awesome. Malvarmeta. Do, vi uloj havas ĉi. Slideshow. Do kiel ni parolas, mi scias David menciita komplekseco runtimes. Do, en la plej bona kazo, estas nur unu, kiun ni nomas konstanta tempo. Ĉu iu povas diri al mi, kial tiu povus esti? Kio tipo de scenaro estus kiu kunportas? Hmm. Student: [inaudible] first-- Instruisto: Do ​​la mezo estas la unua elemento kiun ni atingos, dekstra? Do ĉu tabelo de unu aŭ ajn ni serĉas nur sekvinbero al esti vangofrapon DAB en la mezo. Do tio estas nia plej bona kazo. Vi akiras en verajn problemojn, probable ne tuj atingos [inaudible] kiu ofte. Kio pri niaj plej malbona kazo? Nia plej malbona kazo estas log n. Kaj kiu devas vidi kun la tuta potencoj de du afero kiun mi raportis. Do, en la plej malbona kazo signifus ke ni devis haki la tabelo malsupren ĝis ĝi estis elemento de unu. Do ni devis haki ĝin en duono tantas fojoj kiel ni eble povus. Tio estas kial ĝi estas log n ĉar vi simple teni dividadon por du. Do premisoj, kiujn vi bezonas koni se vi iam tuj uzas binaran serĉon. Via elementoj devas esti ordo. Ili devas esti ordo ĉar tio estas la sola maniero vi povas scii se vi povas forĵeti duonon el ĝi. Se vi havis ĉi implikas sakon de nombroj kaj vi diras, OK, mi tuj kontrolu la mezo nombro kaj la nombro Mi serĉas estas malpli ol tio, mi simple irante arbitre elĵetas duonon. Vi ne scius se via nombroj en tiu alia duono. Via listo devas esti ordo. Siavice, ĉi tio povas esti antaŭenirante iom, sed vi bezonos havi hazarda aliro. Vi bezonos por povi ĝuste iri al tiu mezo elemento. Se vi devas trairi tra ion aŭ ĝi prenas vin ekstra paŝoj por atingi ke meza ero, ĝi ne log n anymore ĉar vi aldonante pli laboro en ĝin. Kaj ĉi faros iom pli sentita en du semajnoj, sed mi simple ia volis antaŭparolo, doni vi uloj ideon de kio estas veni. Sed tiuj estas la du gravaj premisoj ke vi bezonos por duuma listo. Certiĝu ke la ordo. Tio estas la granda unu por vi uloj nun. Kaj en kiun ni povas iri en la resto de niaj varoj. Do kvar sorts-- bobelo, inserción, selektado kaj kunigon. Ili estas ĉiaj malvarmeta. Se vi uloj decidas preni CS 124, Vi lernos pri ĉiaj varoj. Kaj se vi estas XKCD fano, tie Estas vere malvarmeta komikajn pri kiel vere senutila varoj, kiujn mi tre rekomendas vin tuj rigardi. Unu el ili estas kiel panikon varon, kiun estas kiel, ho ne, revenu hazarda tabelo. Elŝaltita sistemo. Lasu. Do geeky humuro estas ĉiam bona. Do ĉu iu memoras speco de kiel simple ĝenerala ideo de kiel bobelo speco funkcias. Vi memoras? Student: Yeah. Instruisto: Iru al ĝi. Student: Do vi iras tra kaj se ĝi estas pli granda, tiam vi interŝangi la du. Instruisto: Hmm. Ĝuste. Do vi nur persisti tra. Vi kontrolu du ciferoj. Se la antauxjugxo estas pli granda ol la poste, vi simple interŝanĝi ilin por ke tiamaniere ĉiuj altaj nombroj bobelo supren al la fino de la listo kaj la tuta suba nombroj bobelo suben. Li montras vi uloj malvarmeta soni efekton ordig video? Estas speco de malvarmeta. Tiel kiel Robert nur diris, la algoritmo ke vi simple paŝo tra la listo, interŝanĝante la najbaraj valoroj se ili ne estas en ordo. Kaj tiam simple daŭre ripetas ĝis vi ne faras neniun interŝanĝojn. Do ne estas malbona, ĉu? Do ni nur devas rapidan ekzemplo tie. Do tiu tuj ordigi ilin en supreniranta ordon. Do kiam ni trairu la unua tempo, ni rigardu tra ok kaj ses estas evidente ne en ordo, ni interŝanĝas ilin. Do rigardu la venonta unu. Ok kaj kvar ne en ordo. Permuta ilin. Kaj tiam ok kaj du, interŝanĝi ilin. Tie ni iras. Do post via unua paŝo, vi scias, ke via plej granda nombro tuj estos tuta vojo ĉe la supro, ĉar ĝi estas nur tuj estos senĉese pli granda ol ĉiu alia kaj ĝi estas nur tuj bobelo la tutan vojon al la fino. Ĉu tio havas sencon por ĉiuj? Malvarmeta. Tial do ni rigardas nian duan paŝon. Ses kaj kvar, ŝaltilo. Ses kaj du, ŝaltilo. Kaj nun ni havas kelkon en ordo. Do por ĉiu paŝo kiun ni fari per nia tutan liston, Ni scias, ke tiel multaj numeroj fine estos estinta ordo. Do ni faras trian pass, kiu estas unu swap. Kaj tiam en nia kvara pasas, ni havas nulon fendoj. Kaj do ni scias ke niaj tabelo estas ordigita. Kaj tio estas la granda aferon kun bobelo varo. Ni scias, ke kiam ni havas nulo interŝanĝojn, kiuj signifas ke ĉiu estas en kompleta ordo. Ĝi estas speco de kiel ni kontrolu. Do ni estas ankaux tuj programi bobelo speco kiu ankaŭ ne estas tro malbona. Neniu el tiuj estas ke malbona. Mi scias ke ili povas simili iom timiga. Mi sciis, kiam Mi prenis la klaso, eĉ kiam mi instruis la klason por la unuan fojon pasintjare, Mi ŝatas, kiel mi faru tion? Indas teorie, sed Kiel do ni efektive faru tion? Tial Mi ankaux volas marŝi tra kodo kun vi uloj tie. Do mi havas _pseudocode_ por vi uloj tiu tempo. Do ĝuste konservi ĉi tio en menso kiel ni al transiron super. Do ni havas kelkajn nombrilo ke sekvadon de niaj interŝanĝojn, ĉar ni bezonas por certigi ke ni kontrolanta tio. Kaj ni persisti la tuta tabelo kiel ni faris kun ĉi tiu ekzemplo. Se la elemento antaux estas pli granda ol la elemento post kie ni estas je, Ni interŝanĝas ilin kaj ni pliigo nia nombrilo ĉar ni apenaŭ interŝanĝi, Ni volas lasi nian nombrilo scias. Demandojn tie? Io ŝajnas amuza super tie. Lernanto: Ĉu vi starigis la vendotablo al nulo ĉiufoje kiam vi iros tra la buklo? Ĉu vi ne plu iri reen al nulo ĉiufoje? Instruisto: Ne nepre. Do kio okazas estas ni trairu tien. Tiel faru dum, memoru ĉi ekzekutos fojon sen halto. Do tuj starigis la nombrilo egala al nulo, tiam tuj persisti tra. Kiel ĝi ripetas tra, ĝi ĝisdatigos vendotablo. Kiel ĝi ĝisdatigas vendotablo, kiam ĝi estas farita, kiam ĝi atingis la finon de la milito, se nia listo ne ordigataj nombrilo estos ĝisdatigita. Tial ĝi kontrolas la kondiĉon kaj ĝi diras, OK, estas nombrilo granda ol nulo. Se jes, faru ĝin denove. Vi volas reagordi tiel ke kiam vi trairu, nombrilo estas egala al nulo. Se vi iras tra ordo tabelo, nenion ŝanĝas, tio fiaskos, kaj vi redoni la ordo listo. Ĉu tio havas sencon? Student: eble en iom. Instruisto: Bone. Se estas iu alia demando kiu venas supren. Jes. Student: Kion la funkcio prezentu interŝanĝante la elementoj? Instruisto: Do ​​ni povas fakte skribi ke se ni tuj nun. Malvarmeta. Do en tiu noto, Alison tuj por reiri al la aparato. Ĝi tuj estos amuza. Kaj ni havas nian belan bobelo speco afero tie. Do mi jam faris bicikladon tra la tabelo. Ni havas niajn interŝanĝojn kiuj estas egala al nulo. Do ni volas interŝanĝi apudajn elementoj se ili estas el ordo. Do la unua afero kiun ni bezonas por Ne estas persisti tra nia tabelo. Do kiel vi pensas ni povus persisti tra nia tabelo? Ni havas por kaj i egalas 0. Ni deziras mi al esti malpli ol n minus 1 minus k. Kaj mi klarigos ke en dua. Do tio estas optimumiga tie kie, memoras, ke mi diris post ĉiu paŝo tra la tabelo ni scias, ke kio estas on-- Do post paŝo ni scias ke tiu ordo. Post du paŝoj ni scias ke ĉiuj ĉi estas ordigitaj. Post tri paŝoj ni scias ke la ordo. Do la manieron mi ripetanta tra la tabelo ĉi tie, Estas ĝi estas certigi nur iri tra kion ni scias estas unsorted. OK? Tio estas nur unu optimumigo. Vi povus skribi ĝin naive simple ripetanta tra ĉio, estus simple preni plu. Kun ĉi kvar buklo estas nur bela optimumigo ĉar ni scias, ke post ĉiu plena ripeto tra la tabelo ĉi tie, kiel ĉiu plena buklo tie, ni scias ke oni pli de tiuj elementoj estos ordo fine. Do ni ne devas zorgi pri tiuj. Ĉu tio havas sencon por ĉiuj? Ke malvarmeta iom lertaĵon? Do en tiu kazo, se ni ripetanta tra, Ni scias, ke ni volas kontroli se tabelo n kaj n plus 1 estas en ordo. OK. Do jen la _pseudocode_. Ni volas kontroli se tabelo n kaj n plus 1 estas en ordo. Do kio povus ni havas tie? Ĝi tuj estos iuj kondiĉa. Estos se. Student: Se tabelo n estas malpli ol tabelo n plus 1. Instruisto: Hmm. Nu, malpli ol aŭ pli granda ol. Student: Pli granda ol. Tiam ni volas interŝanĝi ilin. Ĝuste. Do nun ni eniras kio estas la mekanismo por interŝanĝi ilin? Do ni iris tra ĉi brevemente, tipo de swap funkcio pasintsemajne. Ĉu iu memoras kiel ĝi funkciis? Do ni ne povas ĝuste religi ilin, ĉu ne? Ĉar unu el ili perdiĝas. Se ni diras A estas egala al B kaj tiam B estas egala al, ĉiuj subita ambaux Estas ĝuste egala al B. Do kion ni devas fari estas ni havi portempa variablo tio tuj tenos unu el nia tempo Ni estas en la procezo de interŝanĝi. Do kion ni havas estas ke ni devos iom int temp egalas to-- vi povas atribui ĝin al kiom oni volas, simple certiĝu vi konservi trako de it-- tial en ĉi tiu kazo, mi tuj atribuos ĝin al tabelo n plus 1. Tiel ke tuj teni ajn valoro estas en tiu dua bloko ke ni rigardas. Kaj tiam ni povas fari estas ni povas iri antaŭeniras kaj religi tabelo n plus 1, ĉar ni scias ke ni havas tiun valoron stokita. Tiu estas ankaŭ unu el la grandaj things-- Mi ne scias ĉu iu el vi havis temoj kie se vi ŝanĝos du linioj de kodo subite aferojn laboris. Ordo estas tre grava en CS. Tiel faro certe vi diagramo aferojn el laŭeble pri kio vere okazas. Do nun ni tuj religi tabelo n plus 1, ĉar ni scias ke ni havas tiun valoron stokita. Kaj ni povas atribui ke tabelo n aŭ en ĉi tiu kazo tabelo i. Tro multaj variabloj. OK. Do nun ni reasignado tabelo i plus 1 egali kio estas en tabelo i. Kaj nun ni povas iri tien kaj atribui tabelo i al kio? Iu? Student: 10. Instruisto: 10. Ĝuste. Kaj unu lasta afero. Se ni interŝanĝis ĝin nun, Kion ni devas fari? Kio estas la afero ke tuj informi nin se ni iam finiĝi tiun programon? Kion diras al ni, ke ni havi ordigita listo? Se ni ne plenumi ajnan interŝanĝojn, dekstra? Se interŝanĝojn egalas nulo je la fino de tiu ĉi. Do kiam ajn vi elfari swap, kiel ni nur faris ĉi tie, ni volas ĝisdatigi interŝanĝojn. Kaj mi scias, ke estis demando antaŭe pri ĉu eblas uzu nul aŭ unu anstataŭe de veraj aŭ falsaj. Kaj tio ĉi faras tie. Do tio diras se ne interŝanĝojn. Do se interŝanĝojn estas nulo, kiu is-- mi ĉiam alportu mian veroj kaj mia falses intermiksiĝas. Ni deziras al ni taksi al vera kaj ne estas. Do se estas nulo, tiam ĝi estas malvera. Se vi neas ĝin per [? bang?] devenas vera. Tial tiu linio ekzekutas. Veroj kaj falsa kaj nuloj kaj akiri freneza. Nur se vi malrapide marŝi tra ĝi faros senson. Sed tio, kio estas tiu malgranda iom da kodo tie faras. Do tiu kontrolas vidi ni faris ajnan interŝanĝojn. Do se io krom nulo, ĝi tuj estos falsa kaj la tuta aĵo estas tuj ekzekuti denove. Cool? Student: Kion signifas rompon fari? Instruisto: Break simple rompas vin el la buklo. Do en tiu kazo estus nur ŝatus fini la programon kaj vi farus ĝuste havas vian ordo listo. Student: Amazing. Instruisto: Mi bedaŭras? Student: Ĉar ni antaŭe uzis skribita 1 pli skribita nulo prezenti ke se kiuj funkcios aŭ ne. Instruisto: Jes. Do vi povas reveni nulo aŭ 1. En ĉi tiu kazo, ĉar ni ne vere fari ion kun la funkcio, Ni nur volas ĝin rompi. Ni ne vere zorgas pri tio. Bremso estas ankaŭ bona se ĝi estas uzata por florantajxo de kvar cikloj aŭ kondiĉoj kiuj vi ne volas konservi ekzekuti. Ĝi nur prenas vin de ili. Estas iom de nuancon afero. Mi sentas ke estas multan manon svingas, kiel vi lernos pri ĉi baldaŭ. Sed vi lernos pri ĉi baldaŭ. Mi promesas. OK. Do ne ĉiuj ricevas bobelo speco? Ne tro malbona. Persisti tra, swap aferojn uzante temp variablo, kaj ni ĉiuj starigis tie? Malvarmeta. Awesome. OK. Reen al la PowerPoint. Demandojn, ĝenerale pri tiuj ĝis nun? Malvarmeta. Hmm. Student: [inaudible] int ĉefa kutime. Ĉu vi devas havi tiun por tio? Instruisto: Do ​​ni nur rigardis ĝuste je la efektiva ordigado algoritmo. Se vi havus gxin interne kiel granda programo, vi havus int ĉefa ie. Depende kie vi utiligas ĉi algoritmon, ĝi determinus kio estas revenante de gxi. Sed por nia kazo, ni estas strikte rigardante kiel faras ĉi reale persisti tra tabelo. Do ni ne zorgu pri tio. Do ni parolis pri bona kazo kaj plej malbona kazo scenejoj por duuma serĉo. Do ĝi estas ankaŭ grava por fari kiu por ĉiu de niaj varoj. Do kion vi pensas estas la plej malbona kazo runtime de bobelo speco? Vi ĉiuj memoras? Student: N minus 1. Instruisto: N minus 1. Do tio signifas ke estas n minus 1 komparoj. Do unu afero realigi estas ke sur la unua ripeto, Ni iru tra, ni komparu tiuj two-- tiel ke estas 1. Tiuj du, tri, kvar. Do post ripeta ni jam havas kvar komparoj. Kiam mi parolas pri ekzekuto kaj n. N reprezentas la nombron de komparoj kiel funkcio de kiel multaj eroj ni havas. OK? Do ni iru tra, ni havas kvar. La venontan fojon vi scias ke ni ne devas prizorgi ĉi. Ni komparu ĉi tiuj du, tiuj du, tiuj du, kaj se ni ne havas tiun optimumigo kun la kvar buklo kiun mi skribis, Vi devus esti komparante tien anyways. Do vi devus kuri tra la tabelo kaj fari n komparoj n tempoj, ĉar ĉiufoje kiam ni kuras tra ĝi ni specon unu afero. Kaj ĉiufoje kiam ni kuras tra la tabelo, ni faru n komparoj. Do nia runtime cxar tio efektive n kvadratoj, kiuj Estas multe pli malbone en nia ensalutu fino ĉar tio signifas se ni havis kvar miliardo elementoj, ĝi estas tuj prenos al ni kvar miliardoj kvadrato anstataŭ 32. Do ne la plej bona tempo de ekzekuto, sed por iuj aferoj, vi scias, se vi estas ene certa gamo de eroj bobelo speco povas esti delikata uzi. OK. Do kio estas la plej bona kazo ekzekuto? Student: Zero? Aŭ 1? Instruisto: Do ​​1 farus unu komparon. Dekstre. Student: N minus 1? Instruisto: Do, jes. Do n minus 1. Whenever vi havas koncepton kiel n minus 1, ni inklinas nur faligi ĝin kaj ni simple diri n ĉar vi havas kompari ĉiun el these-- ĉiu paro. Do estus n minus 1, kiun ni ni volas nur diri estas proksimume n. Kiam vi kontraktanta kun ekzekuto, ĉio estas en aproksimas. Tiel longe kiel la eksponento estas ĝusta, vi estas sufiĉe bona. Tiel estas kiel ni pritrakti ĝin. Tial la plej bona okazo estas n, kiu signifas ke la listo estas jam ordigataj kaj ĉiuj ni kuras tra kaj kontrolu ke ĝi estas ordigitaj. Malvarmeta. Bone. Do kiel vi vidas tie, ni simple havas iom pli grafikaĵoj. Do n kvadratoj. Amuza. Multe pli malbone ol n kiel ni vidas, kaj multe, multe pli malbone ol log 2n. Kaj tiam vi ankaŭ eniras en log ŝtipoj. Kaj vi prenos 124, vi eniri kiel log stelo, kiu estas kiel freneza. Do, se vi interesiĝas, lookup log stelo. Estas speco de amuzo. Do ni havas tiun grandan abako. Nur kapoj supre, tiu estas mirinda abako havi por via meza termino ĉar ni longe demandi vin tiuj viaj. Do nur kapojn supren, havi tion en via Meze termino sur via bela Gvidfolio tie. Do ni nur rigardis bobelo varo. Plej malbona kazo, n kvadratoj, bona kazo, n. Kaj ni iras por rigardi la aliajn. Kaj kiel vi povas vidi, la sola Kiu vere faras bone Estas merge varon, kiun ni devos eniri kial. Do ni tuj iru al la proksima here-- selektado varo. Ĉu iu memoras kiom selektado speco funkciis? Iri por ĝi. Student: Esence trairu ordonon kaj krei novan liston. Kaj ĝuste kiel vi metante elementoj en, metis ilin en la ĝusta loko en la nova listo. Instruisto: Por ke sonoj pli kiel inserción varo. Sed vi estas vere proksimaj. Ili estas tre similaj. Eĉ mi havigu ilin miksas kelkfoje. Antaŭ ĉi tiu sekcio mi estis kiel, atendu. OK. Do kion vi volas fari estas selektado speco, la vojo vi povas pensi pri ĝi kaj la vojon Mi certiĝu mi provas ne akiri ili intermiksiĝas, estas ĝia transiro kaj ĝi selektas la malgranda nombro kaj ĝi metas ke komence de via listo. Ĝi interŝanĝas kun tiu unua loko. Ili fakte havas ekzemplon por mi. Awesome. Do simple maniero pensi it-- selektado varon, elektu la plej malgranda valoro. Kaj ni tuj kuri tra ekzemplo ke mi kredas helpos ĉar Mi kredas vidaĵojn ĉiam helpas. Do ni komencu per io kiu estas tute unsorted. Ruĝa estos unsorted, verda estos ordo. Ĝi ĉiuj sencon en dua. Do ni iru tra ni persisti de la komenco ĝis la fino. Kaj ni diras, OK, 2 nia malgranda nombro. Do ni tuj prenu 2 kaj ni iras movi ĝin al la fronto de niaj tabelo ĉar ĝi estas la malgranda kvanto ni havas. Do jen kion tiu faras tie. Estas nur tuj interŝanĝi tiujn du. Do nun ni estas ordo parto kaj unsorted parto. Kaj kio estas bona por memori pri selektado speco Estas ni nur elektanta el unsorted parto. La ordo parton vi simple forlasi sola. Hmm? Student: Kiel ĝi scias kio estas la pli malgranda sen kompari ĝin al ĉiu alia valoro en la tabelo. Instruisto: Edito kompari ĝin. Ni ŝatas saltis ĝin. Tiu estas nur ĝeneralaj entute. Yeah. Kiam ni skribas la kodon min certe vi estos pli kontenta. Sed vi stoki tiu unua elemento kiel la plej malgranda. Vi komparas vin diras, OK, ĉu malgrandaj? Jes. Konservu ĝin. Jen ĝi malgrandaj? Neniu? Tiu estas via malgranda, religi ĝin al via valoro. Kaj vi estos multe pli feliĉa Kiam ni trairu la kodon. Do ni iru tra, ni interŝanĝas ĝin, do tiam ni rigardas tiun unsorted porcion. Do ni tuj elektu tri eksteren. Ni tuj metis ĝin sur je Fine de nia ordo parton. Kaj ni simple intencas teni faranta ke, agante tiel, kaj farante tion. Do jen nia speco de _pseudocode_ tie. Ni programi ĝin tie en sekundo. Sed nur io marŝi tra sur alta nivelo. Vi tuj iros de i egalas 0 ĝis n minus 2. Tio estas alia optimumigo. Ne tro maltrankviliĝu pri tio. Do kiel vi diras. Kiel Jakob diris, kiel do ni konservi trako de kio nia minimuma estas? Kiel ni sciu? Ni devas kompari ĉio en nia listo. Do minimuma egalas i. Ĝi simple diri en tiu kazo la indico de nia minimuma valoro. Tial do tio okazas persisti tra kaj ĝi iras de la j egalas i plus 1. Do ni jam scias ke tio estas nia unua elemento. Ni ne bezonas kompari ĝin mem. Do ni komencu komparante ĝin al la venonta unu kiu estas kial i plus 1 al n minus 1, kiu estas la Fine de la tabelo tie. Kaj ni diris ke se tabelo cxe j estas malpli ol tabelo min, tiam ni religi kie nia minimuma indeksoj estas. Kaj se min ne estas egala al i, kiel en kie nin reen super tie. Tiel kiel kiam ni unue faris ĉi tiu. En ĉi tiu kazo, ĝi komencus je nulo, ĝi finus estante du. Do min ne volis egalaj i en la fino. Kiu lasas nin scii ke ni bezonas interŝanĝi ilin. Mi sentas kiel konkretan ekzemplon helpos multe pli ol tio. Do mi devos kodigi tiu kun vi uloj nun mi opinias ke estos pli bona. Varoj inklinas funkcias tiel en tiu ĝi estas ofte pli bone simple vidi ilin. Do kion ni volas fari estas ni unue volas la plej malgranda elemento en lia pozicio en la tabelo. Ĝuste kion Jakob diris. Vi devas gardi ke iel. Do ni tuj komenci tie ripetanta super la tabelo. Ni tuj diras ke nia unue oni nur komence. Do ni tuj havos int malgranda egalas tabelo je i. Do unu afero rimarki, ĉiu tempo ĉi buklo ekzekutas, Ni komencas unu paŝon antaŭen. Kiam ni komencos ni rigardu ĉi tiu. La venontan fojon ni persisti tra, ni ekde ĉi tiu kaj atribuante lin nia malgranda valoro. Do ĝi estas tre simila al bobelo speco kie ni scias, ke post unu pasas, tiu lasta elemento estas ordigitaj. Kun selektado speco, ĝi estas ĝuste la malo. Ĉe ĉiu paŝo, ni scias, ke La unua unu estas ordigitaj. Post la dua paŝo, la dua estos ordo. Kaj ke vi vidis kun la glito ekzemploj nia ordo parton ĝuste tenas kreskanta. Do per opcio niaj plej malgranda al arrays i, ĉio jam estas faranta Estas constricting kio ni rigardis tiom kiel minimumigi la nombron de komparoj ni faras. Ĉu tio havas sencon por ĉiuj? Ĉu vi bezonas min kuri tra tiu denove malrapidaj aŭ en malsamaj vortoj? Mi feliĉas. OK. Do ni stokante la valoro je tiu punkto, sed ni ankaŭ volas konservi la indekso. Do ni iras por stoki la pozicio de la plej malgranda unu, kiu estas ĝuste tuj estos mi. Do nun Jakob estas kontentigita. Ni havas aferojn stokitaj. Kaj nun ni bezonas trarigardi la unsorted parto de la tabelo. Do en tiu kazo ĉi estus nia unsorted. Tio estas mi. OK. Do kion ni faros tuj estos por buklo. Kiam ajn vi bezonos persisti tra tabelo, via menso povus iri por buklo. Do por iuj int k equals-- Kion ni pensas k tuj egalos komenci kun? Tio estas kion ni starigu kiel nia malgranda valoro kaj ni volas kompari ĝin. Kion ni volas kompari ĝin al? Ĝi tuj estos tiu proksima, dekstra? Do ni volas k esti inicializado i plus 1 por komenci. Kaj ni volas k en tiu kazo jam grandeco stokitaj ĝis tie, do ni povas simple uzi grandeco. Grandeco estas la grandeco de la tabelo. Kaj ni volas nur ĝisdatigi k per unu ĉiufoje. Malvarmeta. Do nun ni bezonas trovi la plej malgranda elemento tie. Do se ni persisti tra, ni volas diri, se arangxis antaux k estas malpli ol nia malgranda value-- ĉi tiu estas kie ni estas reale konservanta trako de kio estas la plej malgranda here-- do ni preferas religi kio nia malgranda valoro. Ĉi tio signifas ke, ho, ni estas ripetanta tra tie. Ajn valoro estas ĉi tie Ĉu nia malgranda afero. Ni ne volas ĝin. Ni preferas religi ĝin. Do se ni reassigning ĝi, kion fari vi pensas povus esti en tiu kodo tie? Ni preferas religi malgranda kaj pozicio. Do kio estas la plej malgranda nun? Student: Array k. Instruisto: Array k. Kaj kia estas pozicio nun? Kio estas la indicoj de nia malgranda valoro? Estas nur k. Do tabelo k, k, ili kongruas supren. Do ni volis religi tio. Kaj tiam poste ni trovis nian malgranda, tial al la fino de ĉi por buklo tie ni trovis kion nia malgranda valoro, do ni simple interŝanĝi ĝin. En tiu kazo, kiel diras nia malgranda valoro estas el cxi tie. Tio estas nia malgranda valoro. Ni nur volas interŝanĝi ĝin ĉi tie, kiu estas kion tio swap funkcio ĉe la malsupro faris, kion ni ĵus redaktis kune paro minutoj. Do ĝi devus rigardi familiara. Kaj tiam ĝi nur persisti tra ĝis ĝi atingas la tutan vojon al la fino, kio signifas, ke vi havas nulo elementoj kiuj unsorted kaj ĉio alia estas ordigitaj. Sencon? Iom pli konkrete? La kodo helpon? Student: Por grandecon, Vi neniam vere difini ĝin aŭ ŝanĝi ĝin, kiel faras ĝi scias? Instruisto: Do ​​unu afero rimarki ĝis tie estas int grandeco. Do ni diris en ĉi sort-- speco estas funkcio en ĉi case-- estas selektado speco, ĝi estas pasinta en la funkcio. Do se oni ne pasis , vi povus fari ion kiel kun la longo de la tabelo alie vi persisti tra trovi la longo. Sed ĉar ĝi pasis en, ni povas simple uzi ĝin. Vi nur supozi ke la uzanto donis al vi validan grandeco kiu efektive reprezentas grandecon de via tabelo. Cool? Se vi uloj havas problemojn kun tiuj aŭ volas pli oportuna kodigo specoj sur via propra, Vi devus iru study.cs50. Ĝi estas ilo. Ili havas Kontrolilo ke Vi povas fakte skribi. Ili faras _pseudocode_. Ili havas pli videoj kaj diapozitivoj inkludante tiujn mi uzas tie. Do se vi ankoraŭ sentas iom nebula, provu tion diveni. Kiel ĉiam, venis paroli al mi ankaŭ. Demando? Lernanto: Ĉu vi diras la grandeco estas difinita antaŭe? Instruisto: Jes. Grandeco estas antaŭe difinita supren tie en la funkcio deklaro. Do vi supozas ke ĝi estas estis pasita en de la uzanto, kaj pro simpleco kaj pro Ni tuj supozi ke la uzanto donis al ni la ĝustan grandecon. Malvarmeta. Do tio estas selektado varo. Knaboj, mi scias ni lernas multe hodiaŭ. Ĝi estas densa datumoj por sekcio. Do kun tio, ni iras iri inserción varo. OK. Tiel, ke ni devas fari nia runtime analizo tie. Do, en la plej bona kazo, donita de kiam mi montris al vi la tablon mi jam ia donis gxin. Sed bona kazo ekzekuto, kion ni pensas? Ĉiu ordo. N kvadrato. Ĉiu havas klarigon Kial vi opinias? Student: Vi komparante through-- Instruisto: Ĝuste. Vi komparas tra. Ĉe ĉiu ripeto, kvankam ni decrementing ĉi lauxvice, vi ankoraŭ trasercxante ĉion por trovi la plej malgranda. Do eĉ se via malgranda valoro estas tie en la komenco, vi ankoraŭ kompari ĝin kontraŭ ĉiu alia certigi ĝi estas la plej malgranda afero. Do vi finos kurante tra proksimume n kvadratoj fojojn. Bone. Kaj kio estas la plej malbona kazo? Ankaŭ n kvadratoj ĉar vi iras esti farante tiu sama proceduro. Do en ĉi tiu kazo, selektado varo havas ion ke ni ankaŭ nomas atendita ekzekuto. Do, en la aliaj, ni nur scias la supra kaj malsupra limoj. Dependanta sur kiel freneza nia lerta estas aŭ kiom unsorted estas, ili varias inter n aŭ n kvadratoj. Ni ne scias. Sed ĉar selektado varo havas la saman plej malbona kaj plej bona kazo, kiu nin diras ke negrave kio tipo de eniro nin havi, ĉu ĝi estas tute ordo aŭ tute inversigi ordo, estas tuj prenos la sama kvanto de tempo. Do en tiu kazo, se vi memoras el nia tablo Ĝi efektive havis valoron kiu tiuj du specoj ne havas, kio estas atendita ekzekuto. Do ni scias ke kiam ajn Ni kuras selektado speco, ĝi estas garantiita kuri n kvadratoj tempo. Ne estas variebleco tie. Estas nur atendis. Kaj denove, se vi volas lerni pli, kaptu CS 124 en la printempo. Bone. Ni vidis ĉi tiun. Malvarmeta. Do inserción varo. Kaj mi verŝajne iros al Blaze tra tiu. Mi ne havas vi uloj programi ĝin. Ni simple marŝi tra ĝi. Do inserción varo estas afabla simile al selektado speco cxar ni havas ambaŭ la unsorted kaj ordigitaj parto de la tabelo. Sed kio estas malsama estas ke kiel ni trairi unu post la alia: ni simple prenas kion ajn nombro estas apud niaj unsorted, kaj ĝuste ordigi ŝin en nian ordo tabelo. Ĝi faros pli sentita kun ekzemplo. Do ĉio komenciĝas kiel unsorted, nur ŝatas kun selektado varo. Kaj ni tuj ordigi tion en supreniranta ordon kiel ni. Do en nia unua paŝo Ni prenu la unua valoro kaj ni diru, bone, vi estas nun en lerta sola. Ĉar vi estas en lerta de vi mem, vi estas ordo. Gratulojn por esti la unua ero en tiu tabelo. Vi jam ordigitaj ĉiuj sur via propra. Do nun ni estas ordo kaj unsorted tabelo. Do nun ni prenu la unuan. Kio okazas inter tie kaj jen, kion ni diras, OK, ni iras por rigardi la unua valoro de nia unsorted tabelo kaj ni iras enigi ĝin en lia ĝusta loko en la ordo tabelo. Do kion ni faras estas ni prenas 5 Ni diru, OK, 5 estas pli granda ol 3, do ni nur insertarlo dekstra dekstre de tio. Ni estas bonaj. Do tiam ni veturos al nia proksima. Kaj ni prenos 2. Ni diras, OK, 2 estas malpli ol 3, do ni scias ke ĝi bezonas esti en la antaŭ nia listo nun. Do kion ni faras estas ni puŝi 3 kaj 5 malsupren kaj ni movas 2 en tiu unua fendo. Do ni nur enigante ĝin en la ĝusta loko devus esti. Tiam ni rigardas nian proksima, kaj ni diru 6. OK, 6 estas pli granda ol ĉio en nia ordo tabelo, do ni nur marki ĝin sur la fino. Kaj tiam ni rigardas 4. 4 estas malpli ol 6, estas malpli ol 5 sed estas pli granda ol 3. Do ni nur insertarlo rekte en meze inter 3 kaj 5. Do fari tiun iom iom pli konkretaj, jen speco de ideon pri kio okazis. Do por ĉiu unsorted elemento, ni determini kie en la ordo parto estas. Do konsiderante la ordo kaj unsorted, ni devas trairi tra kaj figuro el kie ĝi persvadas en la ordo tabelo. Kaj ni enŝovu ĝin movante la elementoj dekstren de ĝi malsupren. Kaj tiam ni simple teni ripetanta tra ĝis ni havas tute ordigita listo kie unsorted nun nulo kaj ordigitaj okupas la tuteco de nia listo. Do, denove, por fari aferojn eĉ pli konkreta, ni havas _pseudocode_. Do esence por i estas egala al 0 por n minus 1 tio estas nur la longon de nia tabelo. Ni havas elementon kiu estas egala al la unua tabelo aŭ la unuajn indicojn. Ni starigu j egala al tio. Do dum la j estas pli granda ol nulo kaj la tabelo, j minus 1 estas pli granda ol la elemento, tial ĉio tio, kio faras estas certigi ke via j vere reprezentas la unsorted parto de la tabelo. Do dum estas ankoraŭ tion ordigi kaj j minus unu is-- kio estas la elemento sxi? J neniam difinis tie. Estas speco de ĝena. OK. Anyways. Do j minus 1, vi kontrolanta la elemento antaŭ ĝi. Vi diras: Bone, estas la elemento antaŭ kien mi am-- ni efektive desegni ĉi ekstere. Tiel diru ĉi estas kiel sur nia dua pass. Do mi tuj estos egalaj 1, kiu estas tie. Do mi tuj estos egala al 1. Tiu estus 2, 4, 5, 6, 7. Bone. Do nia ero en tiu kazo tuj estos egala al 4. Kaj ni havas kelkajn j tio tuj estos egala al 1. Ho, j decrementing. Tio estas kion ĝi estas. Do j estas egala al i, do kia estas parolo estas kiu kiel ni movas antaŭen, Ni nur certigi ke ni ne estas sur indeksante tiu maniero kiam ni provas enmeti tion en nian ordo listo. Do kiam j estas egala al 1 en tiu kazo kaj tabelo j minus one-- tia tabelo j minus 1 estas 2 en ĉi case-- se tio granda ol la elemento, tiam cxio tio faras estas movanta aferojn suben. Do en ĉi tiu kazo, tabelo j minus unu estus tabelo nulo, kiu estas 2. 2 estas ne pli granda ol 4 tial ĉi ne ekzekuti. Do la movo ne moviĝas suben. Kion tiu faras ĉi tie estas nur movanta via ordo tabelo suben. En tiu kazo, fakte, ni povus do-- ni faru ĉi 3. Do se ni estos marŝi per ĉi tiu ekzemplo, ni estas nun ĉi tie. Tiu estas ordigitaj. Tio estas unsorted. Cool? Do i estas egala al 2, do nia elemento egalas al 3. Kaj niajn j estas egala al 2. Do ni trarigardu kaj ni diras, OK, estas tabelo j minus unu granda ol la elemento ke ni rigardas? Kaj la respondo estas jes, ĉu ne? 4 estas pli granda ol 3 kaj j estas 2, tial tiu kodo ekzekutas. Do kion ni faru tabelo cxe 2, do ĉi tie, ni interŝanĝas ilin. Tial ni diras, OK, tabelo je 2 estas nun tuj estos 3. Kaj j tuj egalos j minus 1, kiu estas 1. Tio estas terura, sed vi uloj akiras la ideon. J estas nun egala al 1. Kaj batalarangxis j ĝuste tuj estos egala al nia elemento, kiu estis 4. Mi viŝis ion mi neutilas havi aŭ miswrote ion, sed vi uloj akiras la ideon. Ĝi moviĝas n. Kaj tiam se tio estis, tio farus maŝo denove kaj ĝi dirus, OK, j estas 1 nun. Kaj batalarangxis j minus 1 nun estas 2. Estas 2 malpli ol nia ero? Neniu? Tio signifas, ke ni enmetita ĉi ero en la ĝusta loko en nia ordo tabelo. Tiam ni povas preni tion kaj ni diru, OK, nia ordo tabelo estas tie. Kaj ĝi prenus tiu numero 6 kaj estu kiel, nu bone, estas 6 malpli ol tiu nombro? Neniu? Malvarmeta. Ni estas fajna. Faru tion refoje. Ni diru 7. Estas 7 malpli ol la fino de nia ordo tabelo? No. Do ni estas fajna. Do tiu estus ordo. Esence ĉiu ĉi tio Estas ĝi estas jene take La unua elemento de via unsorted tabelo, elŝeligi kie eliras en via ordo tabelo. Kaj tiu nur prizorgas de interŝanĝojn fari tion. Vi esence nur interŝanĝante ĝis ĝi estas en la dekstra loko. La vida bildo estas ke vi estas movante ĉio malsupren de faranta tion. Tiel estas kiel duono bobelo speco-esque. Check out studo 50. Mi forte rekomendas provi kodigi tion en via propra. Se vi havas ajnajn demandojn aux volas vidi specimenon kodo por inserción varon, bonvolu sciigi min. Mi estas ĉiam ĉirkaŭ. Do plej malbona kazo runtime kaj bona kazo ekzekuto. Kiel knabo vidis el la tablo mi jam montris al vi, ĝi estas ambaŭ n kvadrato kaj n. Do ia ekpaŝis kion ni parolis pri niaj antaŭaj varoj, plej malbona kazo ekzekuto estas ke se ĝi estas tute unsorted, ni devas kompari ĉiuj tiuj n fojojn. Ni faras tuta loto de komparoj ĉar se ĝi estas en inversa ordo, Ni tuj diru, bone, tio estas la sama, tio estas bona; kaj ĉi tiu devos esti komparitaj kontraŭ la unua unu por esti movita reen. Kaj kiam ni atingos al la vosto fino, ni havas kompari, kompari, kaj kompari kontraŭ ĉiu. Do ĝi finas estante proksimume n kvadratoj. Se ĝi estas korekta tiam vi diras, OK, 2, vi estas bona. 3, vi komparis al 2. Vi estas bona. 4, vi simple komparas al la vosto. Vi estas bona. 6, komparu al la vosto, vi estas bela. Do por ĉiu punkto se ĝi estas jam ordigataj vi farante komparon. Do estas nur n. Kaj ĉar ni havas bonan kazon runtime de n kaj plej malbona kazo runtime de n kvadrato, ni ne havas atenditan ekzekuto. Ĝi nur dependas de la ĥaoso de nia listo tie. Kaj ankaux alia grafikaĵo kaj alia tablo. Do diferencoj inter varoj. Mi nur tuj brizo, Mi sentas kiel ni parolis vaste pri kio ili ĉiuj speco de varias kaj ligas kune. Do merge varo estas la lasta Mi trapiku vi uloj kun. Ni havas belan pitoreskan bildon. Do kunfandi varo estas rekursia algoritmo. Do ĉu vi uloj scias kion rekursia funkcio estas? Iu volas diri? Vi volas provi? Do rekursia funkcio estas nur funkcio kiu nomas sin. Do se vi uloj estas familiara kun la Fibonaĉi sinsekvo, kiuj estas konsiderataj rekursiaj ĉar vi prenos la du antaŭaj kaj aldoni ilin kune akiri vian proksima. Do rekursie, mi ĉiam pensas de rikuro kiel kiel spirala tial vi estas kiel kirliĝas en gxin. Sed estas nur funkcio kiu nomas sin. Kaj, efektive, vere rapide mi povas montri vin kion tio aspektas. Do rekursiaj tie, se ni rigardas, estas la rekursiaj maniero sumo super tabelo. Do ĉio, kion ni faras estas ni havos sum funkcio sumo kiu prenas grandecon kaj tabelo. Se vi rimarkas, grandeco dekrementojn per unu ĉiufoje. Kaj ĉiuj faras estas se x egalas al zero-- do se la grandeco de la tabelo egalas zero-- revenas nulo. Alie ĝi resumas ĉi lasta ero de la matrico, kaj tiam prenas sumo de la resto de la tabelo. Do ĝi estas nur rompas ĝin malsupren en malgrandaj kaj pli malgrandaj problemoj. Longan rakonton, rekursio, Funkcio kiu nomas sin. Se tio estas ĉio vi eliris el tiu, ke estas kion rekursia funkcio estas. Se vi prenos la 51, vi ricevos tre, tre komforta kun rekursio. Estas vere malvarmeta. Ĝi taŭgis je ŝatas 3 AM nokto eksteren. Kaj mi, kiel, kial Mi neniam uzas tion? Do por merge varon, esence kio okazos al fari estas ĝi estas tuj rompos ĝin kaj rompi ĝin boli ĝis ĝi estas nur sola elementoj. La sola elementoj estas facile ordigi. Ni vidas tion. Se vi havas unu elemento, estas jam konsiderita ordo. Ktp enigaĵoj de n elementoj, se n estas malpli ol 2, nur reveni ĉar tio signifas ĝi estas ĉu 0 aŭ 1, kiel ni vidis. Tiuj estas konsideritaj ordigitaj elementoj. Alie rompi ĝin en duono. Ordigi la unua duono, ordigi la dua duono, kaj poste kunigi ilin kune. Kial ĝi nomiĝas merge varo. Do ni havas ĉi tie ni ordigi tiujn. Do ni observas havante ilin ĝis la tabelo esas 1. Do kiam estas 1, ni simple reveni ĉar tiu estas ordo tabelo, kaj jen ia ordo tabelo, kaj tio estas kun ordo tabelo, ni ĉiuj ordo. Do kion ni faras estas ni komenci kunfandi ilin kune. Do kiel vi povas pensi fandado estas vi simple forigu la malgrandaj numeron de ĉiu de la sub arrays kaj ĝuste alfiksus ĝin al la emerĝis tabelo. Do se vi rigardas tie, kiam ni havas tiuj aroj ni havas 4, 6, kaj 1. Kiam ni volas kunfandi tiujn, Ni rigardu tiuj du unuaj kaj ni diru, OK, 1 estas malgranda, iras al la fronto. 4 kaj 6, estas nenio kompari ĝin, nur marki ĝin sur la fino. Kiam ni kombini tiujn du, ni simple preni la plej malgranda el tiuj du, do estas 1. Kaj nun ni prenu la malgranda de ĉi tiuj du, do 2. Malgranda de ĉi tiuj du, 3. Malgranda de ĉi tiuj du, 4, 5, 6. Do vi simple tirante ekstere tiujn. Kaj ĉar ili jam solviĝis antaŭe, vi nur havas unu komparo ĉiu tempo. Do pli kodo tien, simple prezento. Do vi komencas je la mezo kaj vi speco maldekstren kaj dekstren kaj tiam vi nur kunfandi tiujn. Kaj ni ne havas kodon por kunfandi ĉi tie. Sed, denove, se vi iros en studi 50, ĝi estos tie. Alie veni alparolas min Se vi ankoraŭ konfuzita. Tiel malvarmeta afero estas, ke plej bona kazo, plej malbona kazo, kaj atendita ekzekuto estas ĉiuj en log n, kiu estas multe pli bona ol ni viditaj dum la resto de niaj varoj. Ni vidis n kvadratoj kaj kion ni reale tien estas n logo n, kiu estas granda. Rigardu kiom bone tio estas. Tia bela kurbo. Tiom pli eficiente. Se vi iam povos, uzo kunfandi varo. Ĝi savos vin tempo. Tiam denove, kiel ni diris, se vi malsupren en tiu malsupra regiono, ne fari tiun multe de diferenco. Vi korpigi al miloj kaj miloj de enigoj, vi certe volas pli kompetenta algoritmo. Kaj, denove, nia bela tablo de ĉiuj varoj kiujn vi uloj lernis hodiaŭ. Do mi konas jam pasis densa tago. Tio ne nepre por helpi vin kun via pset. Sed mi nur volas fari malgarantio tiu sekcio ne estas nur cxirkaux psets. Ĉio ĉi materialo estas bela Ludo por via midterms. Kaj ankaŭ se vi faras daŭrigi kun CS, Tio estas vere gravaj fundamentoj ke vi bezonas scii. Do kelkaj tagoj estos Iom pli pset helpo, sed kelkaj semajnoj estos multe pli efektiva enhavo ke ne sxajnu súper utila al vi nun, sed mi promesas, se vi daŭre sur estos tre, tre utila. Do tio estas por sekcio. Malsupren al la drato. Mi faris gxin interne de unu minuto. Sed vi iru. Kaj mi havos benjetoj aŭ dolĉaĵoj. Ĉu iu alergia al io, sur la vojo? Ovoj kaj lakto. Do benjetoj estas ne? OK. Bone. Ĉokolado ne? Starburst. Starbursts estas bonaj. OK. Ni tuj devos Starburst venontan semajnon poste. Tio estas kion mi akiras. Vi ĉiuj havas grandan semajnon. Legu vian spec. Sciigi min se vi havas demandojn. Pset du kvalifikoj devus esti al Vi per ĵaŭdo. Se vi havas ajnajn demandojn pri kio mi gradita ion kaj kial mi gradita io kia mi ne, bonvolu retmesaĝi al mi, venu paroli kun mi. Mi estas iomete freneza ĉi semajno, sed mi promesas Mi ankoraŭ respondi ene de 24 horoj. Do havi grandan semajno, cxiu. Bonŝancon en via pset.