>> ЗВУЧНИЦИ 1: Еј сите!
Добредојдовте назад на секција.
Толку мило да се види толку многу од вас и тука, и секој, кој гледа на интернет.
Значи, како и обично добредојде назад.
Се надевам дека сите сте имале прекрасен викенд, полн со одмор, релаксација.
Тоа беше убава вчера.
Така, се надевам дека ќе уживаат на отворено.
>> Значи прво на неколку најави.
Оценување.
Значи, повеќето од вас треба да има добивано е-пошта од мене за вашиот гребење Pset,
како и за оценување на Pset 1.
Значи, само неколку работи.
Не заборавајте да користите check50 во style50.
Овие се наменети да бидат ресурси за вас момци,
да бидете сигурни дека сте добивање на што повеќе поени што можеш
без непотребно ги губи.
Така, работи како стил се многу важни.
Ние ќе се обидеме да ги тргнеме за тоа.
Некои од вас може да има веќе забележав дека од вашиот Pset.
И check50 е само навистина лесен начин да бидете сигурни дека
дека ние сме всушност се враќа она што треба да се враќа на корисникот,
и дека сè е работи правилно.
>> На вториот белешка, бидете сигурни дека вашата качувањето работи на точната папка.
Тоа го прави мојот живот само малку потешко
ако испраќате Pset 2 во Pset 1 бидејќи кога јас го симнете работи,
тие не преземете правилно.
И знам дека тоа е малку згреши во еден систем да се користи за да се,
но само да биде супер внимателен, ако е само за мене,
така што кога сте добивање пораки на како 02:00 и јас сум оценување.
Ако не предизвикаат Јас треба да се погледне сите околу за вашиот Pset.
Кул.
>> Знам дека е рано, но јас целосно доби соблече стража
од есеј тоа е поради овој петок, дека моите професори беа само се допаѓа, о, да.
Запомнете, имате есеј поради во петокот.
Така, знам никој не сака да се размислува за midterms,
но вашиот прв квиз е на 15-ти октомври, кој Октомври почнува оваа недела.
Па, може да биде порано отколку што се очекуваше е за сите.
Така што вие не сте фрлени исклучи стража, кога Јас се спомене делот следната недела дека ох,
вашиот квиз следната недела, Мислех, Би ви даде малку повеќе
на главите нагоре сега.
>> Така, вашиот проблем постави, број три.
Како луѓето ги прочитале спецификации од љубопитност?
ОК.
Добивме неколку.
Вид на долу од минатата недела, но тоа е во ред.
Знам, дека е убава надвор.
Така Break Out.
Дефинитивно откако ќе се направи денес ја прочитате вашата спецификации најмалку
се обиде како симнување дистрибуција код и трчање
како и првиот почетна нешто што тие ќе побара од вас да.
Затоа што ние сме со користење дистрибуција код и библиотека
дека ние сме само се using-- --Он само по втор пат сме направиле ова Pset,
луди работи може да се случи со вашиот уред,
и сакате да се најде дека сега наспроти подоцна.
>> Бидејќи ако тоа е во четврток навечер или тоа е Среда вечер и поради некоја причина
вашиот уред едноставно не сакате да се кандидира со библиотека
или со дистрибуција код, што значи дека
дури и не може да започне да го кодирање.
Затоа што не може да се провери да се види дали таа работи.
Ти не ќе бидам во состојба да се види дали компајлира.
Сакате да се грижи за оние кои во почетокот на недела, кога се уште може да ми мејл
или еден од другите TFS, а ние може да се добие оние фиксен.
Бидејќи тоа се прашања дека се случува да ви запре
од какви било вистински напредок.
Тоа не е како еден ошибка, дека можете да само вид на прескокнете над.
Ако имате проблеми со вашиот уред или дистрибуција код,
навистина сакате да се добие дека зема пука на порано отколку подоцна.
Па дури и ако не сте gonna всушност започне кодирање, симнете дистрибуција
код, да се прочита спецификации, бидете сигурни дека сè што работи таму.
ОК?
Ако вие само може да го направи тоа, јас ветувам вашиот живот ќе биде полесно.
И така сте веројатно нема да го направите токму сега, нели?
ОК.
Значи, било какви прашања има?
Било логистичка нешта?
Секој е добро?
ОК.
>> Disclaimer за оние од ти во соба и интернет.
Одам да се обидува да се префрлиш помеѓу PowerPoint, во апаратот
бидејќи ние се случува да се прават некои кодирање
денес од страна на популарни побарувачка на анонимните Анкетата сугестија јас испрати минатата недела.
Значи, ние ќе се прават некои кодирање.
Значи, ако вие момци исто така, сакаат да оган до вашиот апарати,
и што треба да го имаме е-маил од мене, со примерок датотека.
Ве молиме слободно да го стори тоа.
>> Значи, ние се случува да се зборува за GDB, што е дебагерот.
Тоа се случува да ви помогне вид дознаам каде
се одвиваат работите во ред во вашиот код.
Тоа е навистина само начин за вие да ги интензивираат преку вашиот код, како што се случува,
и да биде во можност да се печати од променливи или да видиме што е навистина се случува
под хауба стихове вашата програма само трчање, тоа е како Разлом,
и сте како, не знам што едноставно се случи тука.
Јас не знам што линија не успеа во.
Јас не знам од каде тоа не беше во ред.
Значи, GDB се случува да ви помогне со тоа.
Исто така, ако решите да продолжи да и земе 61,
тоа ќе навистина, навистина да ви биде најдобар пријател, причина јас да ви кажам
затоа што ќе одам низ таа класа.
>> Ние се случува да се погледне во бинарна пребарување, кои, ако вие момци се сеќавам
голема телефон книга пример спектакл од класа.
Ќе се спроведува тоа, и одење преку тоа малку повеќе,
а потоа ние ќе преку четири различни видови, кои се меур,
Избор, вметнување, и се спојуваат.
Кул.
Значи, GDB како што споменав, е дебагерот.
И овие се вид на големи работите, големи функции или команди
кои ги користите во рамките GDB, и јас ќе одиме вас преку демонстрација на тоа во една секунда.
>> Па, ова не е само ќе остане апстрактен.
Ќе се обидам и да ја направат како бетон што е можно за вас момци.
Значи, се скрши.
Таа или ќе биде пауза како на пример, некои број, кој
претставува линија во вашата програма, или можете да го името функција.
Значи, ако ви кажам скрши главната, ќе престане да на главната,
и нека ви прошетка низ таа функција.
>> Исто така, ако имате некои надворешни функционираат како Трампа или коцка,
дека ние погледна минатата недела.
Ако ви кажам наруши една од тие, секогаш кога вашата програма хитови кои,
тоа ќе чека за да каже дека тоа што да прави.
Пред тоа само ќе се изврши така можете всушност би можеле да се повлече во внатрешноста на функција
и да видиме што се случува.
Значи, следниот, само прескокнува следната линија, оди над функции.
Чекор.
Овие се сите малку апстрактен.
Значи, јас сум само ќе да се кандидира преку нив, но ќе ги видите во употреба во секунда.
>> Чекор во функција.
Така како што јас го кажувам, како и со Трампа, тоа ќе
ќе ви овозможи да всушност како да сте како физички ќе влезете внатре,
можете да се плеткаме со овие променливи, печатење што тие се, да видиме што се случува.
Листа ќе буквално само печати надвор околните код.
Значи, ако сте вид заборавајте каде се наоѓате во вашата програма,
или да се прашувате она што се случува околу него,
ова само ќе се печати сегмент на сакале пет или шест линии околу неа.
Значи, можете да се ориентирани за тоа каде се наоѓате.
>> Печати некои променлива.
Значи, ако имаш клучот како во Цезар, дека ние ќе се погледне.
Може да се каже за печатење Клучни во кој било момент.
Тоа ќе ви кажам она што вредност е така дека, можеби некаде по патот,
ви затирали вашиот клуч.
Ти всушност може да се каже дека поради што всушност може да се забележи дека вредноста.
>> Во локалните жители, само отпечатоци вашите локални променливи.
Така, во секое време сте во рамките на еден циклус, а вие само сакате да видите како, ох.
Што ми е јас?
Што е ова клучните вредност дека јас се иницијализира тука?
Која е пораката во овој момент?
Тоа само ќе печати сите на оние кои се, така што ќе
не мора да се индивидуално велат, печатење И. Печати порака.
Печати клуч.
И потоа екранот.
Она што го прави тоа е како да чекор преку програмата,
едноставно ќе бидете сигурни дека тоа е прикажување на некои одредени променлива
во секоја точка.
Така што ќе also-- --Он е вид на кратенка каде
вие не мора да продолжувам да одам како, ох.
Печати клуч или Печати I. Тоа само автоматски ќе го направи тоа за вас.
>> Значи, со тоа, ние ќе да се види како тоа оди.
Одам да се обиде и да се префрлате во текот на мојот уред.
Види дали можам да го направите тоа.
Сите.
Ние сме само ќе да го огледалото.
Там ништо луд на мојот лаптоп относнотова.
ОК.
Ова треба да биде оваа.
Тоа е толку мал.
Ајде да видиме дали можеме да го направите тоа.
>> ОК.
Алис е очигледно борат тука само малку,
но ние ќе го добие во Моменто.
ОК.
Ние сме само ќе се зголеми ова.
ОК.
Може секој вид види тоа?
Можеби малку?
Знам дека е малку мала.
Вие не може едноставно да дознаам како да се направи ова поголем.
Ако некој знае.
Дали некој знае како да го направи тоа поголеми?
ОК.
Ние си оди за да се тркалаат со него.
Не е важно относнотова бидејќи тоа е само тоа е код кој вие момци треба
имате.
>> Што е уште поважно е терминалот тука.
И ние го имаме тука Зошто е толку мал?
Поставувања.
Ох.
Точно Ајк.
Како е ова?
Од таму.
Дали е тоа подобро за сите?
ОК ,.
Кул.
>> Вие знаете кога сте во CS класа технички тешкотии
се вид на дел од the-- Значи, ајде да се расчисти ова.
ОК.
Значи, токму овде, во дел, кој имавме тука.
Цезар е извршна датотека.
Па јас ја направив.
Значи, една работа да се реализираат со GDB е дека тоа што работи на извршна датотека.
Значи, вие не може да се пушта и на dotsy.
Мора да всушност направи Осигурајте се дека вашиот код подготвува,
и дека тоа, всушност, може да се работи.
>> Значи, бидете сигурни дека ако тоа не се случи состави, да го да ги собере,
така што ќе вид на може да се поминува низ него.
Значи, да се започне GDB, сите што го правите, Gloria тип GDB, а потоа само на
датотеката што сакате.
Јас секогаш misspell Цезар.
Но вие сакате да бидете сигурни бидејќи тоа е извршна,
точка блиц ти, така што значи си оди
да се кандидира CSI си оди да се изврши ова фајлови или со дебагерот.
ОК.
Значи, вие го направите тоа, ќе го добиете овој вид на глупост.
Тоа е само сите работи во врска дебагерот.
Вие навистина не треба да се се грижи за тоа во моментов.
И како што гледате, имаме оваа отворен круглые скобки, БДП, во близина круглые скобки,
и само вид на личи нашите командната линија, нели?
>> Значи, она што ние сакаме да do-- --So, Првото нешто
ако сакаме да се избере место да го скрши.
Па, таму е еден ошибка во оваа Цезар програма
дека јас се воведе, дека ние си оди за да дознаете.
Тоа Што го прави тоа е што е потребно за внесување Barfoo во сите капи, и поради некоја причина
тоа не го менува A. Тоа само остава тоа сам, е се друго точни,
но втората буква Останува непроменет.
Значи, ние се случува да се обиде и дознаам зошто тоа е.
Значи, првото нешто што обично сакате да го направите секогаш кога ќе започне на GDB
е да дознаам каде да ја скрши.
>> Па Цезар е прилично кратка програма.
Ние само една функција, нели?
Она што беше нашата функција во Цезар?
Там е само една функција, Главна нели?
Main е функција за сите ваши програми.
Ако не имаат Главна, би можел да да биде малку загрижени токму сега,
но се надевам дека сите сте имале Главна таму.
Значи, она што можеме да направиме е можеме да само се скрши Мајна, исто како што.
Значи, што се вели, во ред.
Ние се постави нашата точка на прекин еден таму.
>> Значи, сега е да се запамети е Цезар зема една командната линија аргумент право
и ние не го направиле тоа никаде сеуште.
Значи, она што го правите е кога вие, всушност, оди да се кандидира
програма, секоја програма што сте работи во GDB дека треба командната линија
аргументи, си оди за да влез кога за првпат на проектот трчање.
Значи, во овој случај, тоа го правиме Стартувај со клуч на три.
И тоа, всушност, ќе започне.
>> Значи, ако видите тука, имаме Ако RC не е еднакво на 2.
Значи, ако вие момци сите имаат таа датотека дека јас испрати до
ќе видите дека тоа е како првата линија нашата главна функција, нели?
Тоа е проверка за да види дали имаме точниот број на аргументи.
Значи, ако се прашувате ако RC е точна,
можете да направите нешто исто како Печати РК.
RC е две, што е она што го очекуваше, нели?
>> Значи, можеме да одиме понатаму, и продолжи преку.
Значи, имаме некои клучни таму.
И ние може да испечатите нашите клучни да бидете сигурни дека тоа е точно.
Интересно.
Не е сосема она што го очекуваше.
Значи, една работа да се реализира с GDB, исто така, е
дека тоа не е се додека вие всушност хит Следната, дека линијата дека сте само видов
е, всушност, изврши.
Па, во овој случај клуч се уште не е доделен.
Значи, Клучни некои ѓубре вредност кои ги гледате на дното таму.
Негативни 120-- $ --Он е една милијарда и нешто чудно работите нели?
Тоа не е клуч, кој што очекувавме.
Но, ако ние хит на Next, и тогаш ние се обиде и печатење клуч, тоа е три.
>> Секој се види тоа?
Значи, ако добие нешто дека сте како, почекајте.
Оваа е целосно не е во ред, и јас не знам
како ова ќе се случи, бидејќи сите сакам да направите е да доделите број, променлива,
обидете се притискање Следно, се обиде печатење тоа повторно, и да видиме дали работи.
Бидејќи тоа е само ќе треба да се изврши и всушност додели нешто откако ќе
хит на Next.
Да има смисла за секого?
Ух нели?
>> ЗВУЧНИЦИ 2: Кога ќе случаен избор броеви што значи тоа?
>> ЗВУЧНИЦИ 1: Тоа е само случајна.
Тоа е само ѓубре.
Тоа е само нешто што вашиот компјутерски случајно ќе го доделите.
Кул.
Значи, сега ние може да се движи преку, и така сега имаме овој обичен текст GetString.
Значи, дозволете ми да се воведе она што ќе се случи кога ние хит Следна тука.
Нашите GDB вид исчезнува, нели?
Тоа е затоа што GetString сега е извршување, нели?
Значи, кога видовме обичен текст е еднаква на GetString, отворен круглые скобки и круглые скобки,
и ние хит Next, која има всушност извршува сега.
Значи, тоа е на чекање за ни да го внесете нешто.
>> Значи, ние се случува да се влезни нашата храна кои е она што е неуспехот како што ви кажав
и дека само вели дека тоа е заврши извршување, дека затворен
заградата значи дека е излегување надвор од таа јамка.
Значи, ние може да ја погоди Next, и сега, како што јас сум сигурни дека сте запознаени со Цезар,
ова е, она што е оваа линија случува да се направи.
Тоа е за Int I е еднакво на 0, N е еднаква на Strlen, обичен текст, а потоа
I е помала n, I, плус, плус.
Што е овој циклус се случува да направам?
Отвори вашата порака.
Кул.
Значи, ајде да почнете да го правите тоа.
>> Значи, треба оваа состојба одговара, за нашите првиот?
Ако тоа е Б, тоа е обичен текст I. Ние може да се добијат информации за нашите локални жители.
Па, I е нула, и ако шест, што ние очекуваме и нашите клучни е три.
Сите кои имаат смисла, нели?
Тие бројки се сите токму она што треба да биде.
Значи, потпевнувам?
ЗВУЧНИЦИ 3: Имам случајни броеви за рудникот.
ЗВУЧНИЦИ 1: Па, можеме да --мы check-- може да разговарате во врска со тоа во една секунда.
Но ќе треба да се добива ова.
Значи, ако имаме капитал B за првото еден,
оваа состојба треба да го фати, нели?
Значи, ако ние хит Следниот, ние се види дека овој Ако всушност извршува.
Затоа што ако ти си по заедно во вашиот код,
оваа линија тука, каде обичен текст јас се заменува со оваа аритметика,
само извршува ако Ако состојба е точно нели?
>> GDB е само нема да ти покаже работи кои се всушност извршување.
Затоа, ако тоа Ако состојбата не беше исполнет, тоа е само ќе да го прескокнете до следната линија.
ОК?
Значи, ние го имаме тоа.
Оваа заградата значи дека е затворен надвор од таа јамка сега.
Значи, тоа се случува да се започне одново.
Само како тоа.
Значи, тоа може да се добие информации за нашите локални жители тука,
и гледаме дека нашиот прв писмо е променет, нели?
Тоа е сега е, како што треба да биде.
Значи, можеме да продолжиме натаму.
>> И ние имаме оваа проверка.
И оваа проверка треба да се работи, нели?
Тоа е A. треба да се менува три писма напред.
Но, ако забележите, ние се добие нешто различно.
Значи во овој случај тука, го улови него, и така оваа линија извршува,
кој е изменета нашата B. Но, во овој случај тука,
имаме дека тоа само да го прескокнат, и отиде до [? L Сифф. ?]
Така нешто се случува таму.
Она што е ти го кажувам е дека, знаеме дека тоа треба да се фати тука,
но тоа не е.
Секој може да се види она што нашите Проблемот е во тоа што линијата?
Тоа е многу минута нешто.
И ти исто така може да се погледне во вашиот код.
Тоа е, исто така, line-- заборават што линија е во there-- но тоа е во [нечујни].
Да?
>> SPEAKER 4: Се наоѓа на поголема од страница, ако го прочитате во книгата.
ЗВУЧНИЦИ 1: Токму така.
Значи, дебагерот не можеше да каже ти тоа, но на дебагерот
може да ви се фаќате за линија дека знаете не функционира.
И, понекогаш, кога особено подоцна во текот на семестарот, кога
си имаш работа со сто, сто неколку линии на код, и вие
не знам од каде тоа е не, ова е одличен начин да го направи тоа.
Така, ние откривме нашите ошибка.
Можете да го поправите во датотеката, а потоа можете да го кандидира повторно,
и сè ќе работи совршено.
И најголемата работа е ова може да изгледа како, во ред.
Да.
Кул.
Ти знаеше дека она што го барате.
Значи, ти знаеше што да прави.
>> GDB може да биде супер корисни, бидејќи вие може да испечатите сите овие работи што ви
не би.
Тоа е многу повеќе корисни од printf.
Колкумина од вас го користите како printf изјави
да дознаам каде ошибка е, нели?
Значи, со ова, вие не мора да се задржи ќе се вратам,
и се допаѓа коментирајќи во Printf, или коментирате,
и дознаам што што треба да се печати.
Ова всушност само ти овозможува да чекор по чекор, се печати работи
како си оди преку, па така, можете да набљудуваат како тие промени во реално време,
како вашата програма работи.
>> И тоа не се малку малку се користи за добивање.
Јас високо ќе им препорачаат само вид на тоа што се малку фрустрирани со тоа
за сега.
Ако потрошите еден час во текот на следната недела за учење како да се користи GDB,
ќе се спаси толку многу време подоцна.
И буквално. ние им кажуваме тоа да се луѓе секоја година,
и јас се сеќавам кога отидов со класа, јас бев како, јас ќе бидам во ред.
Не.
PSET 6 дојде на и јас бев како, јас сум ќе научат
како да се користи GDB, бидејќи јас не знам што се случува тука.
>> Значи, ако имате време, така користат на помали програми
дека си оди за да биде работи, како работат
преку нешто како Visionare, како ова.
Или ако сакате дополнителна пракса, јас сум сигурен Би можел да излезе со кабриолет програми,
за да можете да debug ако сакате.
>> Но ако сте само да потрае некое време да се добие навикнеш на него, само се позанимавам со неа,
тоа навистина ќе ви служи добро.
И тоа е навистина еден од работи кои само
мора да се обидат и да ја добиете вашата раце валкани со, пред навистина да го разбираат.
Јас навистина само го разбрав еднаш Морав да debug работите со него,
и тоа е многу поубаво да имаме идеја за како да се debug порано отколку подоцна.
ОК.
Кул.
Знам дека е вид на како несреќата се разбира во GDB,
и јас дефинитивно ќе работи на добивање на овие да изгледаат поголеми следниот пат.
Кул.
>> Значи, ако ние се вратиме на нашите PowerPoint.
Е ова се случува да се работи?
AWH.
Да.
ОК.
Значи, ако некогаш треба било која од оние пак, има листа.
Па Бинарни Барај, кој секој се сеќава на големиот спектакл на Давид
расцепен телефон книги на половина.
Јас навистина не се добие телефон книги веќе,
затоа што како, каде и да правите се добие телефон книги, овие денови?
Јас навистина не знам.
Бинарни пребарување.
Дали некој се сеќавам како Бинарни Барај дела?
Никого на сите?
Да?
ЗВУЧНИЦИ 5: Знаеш кога ќе се погледне кои половина
тоа ќе биде кај, врз основа на тоа и да се ослободи од другата половина.
>> ЗВУЧНИЦИ 1 Токму така.
Значи, Бинарни Барај, тоа е вид на a-- --мы сакал да го наречам го раздели па владеј.
Значи, она што ќе го направиме е ќе изгледа во средината,
и ќе се види дали тоа се совпаѓа она што го барате.
И ако тоа не е така, тогаш ќе се обидат да дознаам, тоа е ќе се остави
половината или на десно половина.
Значи, ова може да биде ако сте во потрага на нешто што е по азбучен ред,
што гледате, ох.
Дали Алисон дојде пред М?
Да.
Значи, ние се случува да се гледаат во првата половина.
>> Или тоа би можело да биде како со броеви.
Нешто што можете да споредуваат, тоа може да бидат подредени.
Можете да го користите бинарни пребарување на.
Значи, некој се сеќавам ова графика или што е ова?
Тоа е асимптотска Сложеност.
Па, оваа крива само опишува колку долго
ви е потребно да се реши проблемот, како да се зголеми бројот на работи
дека сте користење.
>> Па, ние треба N, кој е линијски време.
Ако N текот на две, што е малку подобро, се уште расте супер брз.
И тогаш имаме најава, која е она што го сметаме Бинарни пребарување.
Ако ние се забележи, како вашиот проблем добива многу и многу поголема,
времето кое е потребно да го реши навистина не се зголеми тоа многу.
Тоа е како да се спореди тука во почетокот.
Вие сте како, во ред.
Нешто тука навистина не важно која ние ги користиме,
но ќе го добиете до еден милион, милијарди долари.
Вие се обидувате да најдете some-- --you're се обидува да најде игла во haystack.
>> Мислам дека сакате овој проблем.
Сакате оваа комплексност, не линеарна, бидејќи за сите вас
знаете вашата gonna се бараат преку секој поединец игла, нешто од сено,
обидувајќи се да се погледне за вашиот игла.
И тоа не е премногу забавно во моето мислење.
Ми се допаѓа брзо.
Ми се допаѓа ефикасни.
И како работливост студенти вас момци се, знаеш работите попаметно,
не потешко вид работа, како можете може да се направи на овие алгоритми.
>> Значи, ние се случува да одиме преку само еден брз пример.
Мислам дека вие момци треба да имаат страна на Бинарни Барај,
но во случај некој е малку нејасни, сакаат да го засилат,
ние се случува да се само оди преку еден пример тука.
Значи, ние сме во потрага за ако низата содржи седум.
>> Значи, првото нешто што го правиме е погледне во средината, нели?
И, исто така, си оди за да се кодирање Бинарни Барај во само една секунда.
Значи, тоа се случува да биде забавно.
Значи ние се погледне во средината малку низи 3.
Дали 3 еднакви 7?
Не го прави тоа.
Тоа е шест.
Па, тоа е помалку од или поголема од седум?
Помалку од.
Да.
Ница работа момци.
Се чувствувам ми се допаѓа мене да има бонбони, бидејќи јас
сакате да го исфрли во дворовите.
Тоа е она што јас идам да се направи следната недела.
Тоа ќе ви го задржи момци остар.
>> Значи, ние фрлаат дека првата половина, нели?
тоа беше помалку од.
ние знаеме дека сè на тој левата страна
се случува да биде помал од она ние сме всушност барате.
Значи, нема потреба да обрне внимание на тоа.
Само да заборавите за неа.
Значи, сега ние се погледне во нашите десната страна, и ние се погледне во средината таму,
и сега е девет.
Значи, 9 is-- --Everyone?
Поголема од она што ние сме во потрага по, нели?
Значи, ние се случува да се фрли намалува се за да на десно.
Како тоа.
Сега, сите ние си замина со е еден.
Значи ние се провери, дали е ова едно она што ние го барате? е.
Ние се најде она што сакавме.
Значи ние сме направиле.
Билинейна пребарување.
>> И ако забележите, ние имаше седум влезови таму.
Тоа само ни го зеде како три пати, но ако правиш како милијарди долари,
вие момци се знае колку чекори што би се земе ако имавме четири милијарди нешта?
Било нагаѓања?
Тоа е 32.
32 чекори за да се најде нешто во четири милијарди
елемент низа, бидејќи на власта на две деца.
Па две е до 32, не е до четири милијарда.
>> Така доста луд како сте се уште во рамките на како прилично мал број на чекори
да се најде нешто во четири милијарди елементи.
Така, на тој белешка, ние сме се случува да се код овој
па вие момци всушност може вид на се види како тоа функционира.
Сите права, па вие момци можат да се код.
Одам да ви момци нека се зборува за малку.
Да се ​​запознаат луѓето околу вас, што е она што некој сака од последниот дел.
>> Така да се запознаат со луѓето околу вас.
Се зборува за малку.
И сите сакам од тебе момци во моментов е само
обидете се да се создаде преглед на псевдокод.
ОК?
Стој.
Сите сакам од вас момци е ти си само ќе да се пополни во ова додека случајот.
Па јас го поставите овие горниот и долните граници во кои
претставуваат на почетокот и крајот на нашето низа.
И ви се случува да всушност поминете и да дознаам
она што го правиме во рамките на ова додека јамка.
>> Значи, ако можете да дознаам out-- имам навестување there-- она ​​што се случаите
дека имаме тука?
Значи, ако сакате да дознаам случаи, ние ќе Псевдокод оние
а потоа ние всушност ќе ги код.
И тоа се случува да биде, јас мислам, се надевам дека тоа ќе
да биде малку полесно отколку што очекувате.
Затоа што тоа не е толку многу код, всушност, што е навистина кул.
>> Мм хм?
>> СТУДЕНТСКИ: [нечујни]?
Инструктор: Да.
Существовал нешто да се најде во средината.
>> СТУДЕНТСКИ: Значи можеме да го користиме тоа.
ОК.
>> Инструктор: Совршен.
Значи тоа е првото нешто што треба да направите.
Па најдете средината.
Одлично.
Па имате идеја за тоа како ние би можеле да всушност се најде на средината со код?
>> СТУДЕНТСКИ: Да.
n над 2?
Инструктор: Значи n над 2.
Така една работа е да се запамети е дека вашиот горниот и долниот границите се промени.
Ние ги свива дел на низата ние сме во потрага да.
Па n над 2 ќе работи само за првото нешто што го правиме.
Па изведува горниот и долниот дел во предвид, како би можеле да ги добиеме тие средината елемент?
Затоа што ние сакаме средината помеѓу горниот и долниот дел, така?
Мм хм?
>> СТУДЕНТСКИ: [нечујни].
>> Инструктор: Значи имаме некои средината.
И тоа ќе биде плус горниот пониски над 2.
Страшни.
Там одиме.
Една линија надолу.
Вие момци се на вашиот начин.
Па сега дека ние имаме средината, што сакаме да направите?
Само во целина.
Вие не треба да го код.
Да.
СТУДЕНТСКИ: [нечујни]?
Инструктор: Значи тоа е плус затоа што ти си наоѓање на среден помеѓу двете
од нив.
Значи, ако мислите на нив како вид на зголемување на од двете страни,
се размислува за тоа како да се пријде средината, сакате се допаѓа.
Па ако беа на двете страни на средината, а ние имаме како 5 и 7.
Кога ќе им додадете заедно вас добијат 12, ќе ја подели со 2, е 6.
>> Понекогаш тоа е тешко да се објасни зошто тоа функционира,
но ако работите преку пример, понекогаш,
тоа ќе ви помогне да дознаам ако тоа треба да бидат плус или минус.
Да.
>> СТУДЕНТСКИ: [нечујни] токму во средината
ако тие имале случај кога има многу помал број
и како еден голем број?
>> Инструктор: Значи се што ви треба е на средината на низата.
Значи, ако сте имале еден куп мали броеви а потоа еден навистина голем број
на крајот, не е битно.
Сè што е важно е дека тие се подредени, вие само
сакате да се погледне во средината на низа, бидејќи ти си уште
режење вашиот проблем на половина.
Кул.
Па сега дека имаме средината, што ќе правиме следно?
>> СТУДЕНТСКИ: Споредба.
Инструктор: споредуваат.
Така се споредуваат средината value_wanted.
Кул.
Така што гледате тука имаме оваа вредност сакаме тука.
Се сеќавам ова е низа.
Па средината се однесува на индекс.
Значи, сакаме да се направи вредности на средината.
Не заборавајте ако сакате да се споредуваат, двојно еднакви.
Можете да направите еден е еднакво сте само ќе го превъзложите,
а потоа, се разбира, тоа е ќе биде вредноста што сакате.
Па не го сторат тоа.
>> Па ние си оди за да се види дали вредностите на средината
е еднаква на вредноста сакаме.
Не заборавајте вашите загради.
Dropbox е да заминам.
Така што ќе правиме во овој случај?
Ако тоа е она што сакаме да се вратат?
Ние се обидуваме да се каже.
>> СТУДЕНТ печати ја исклучи.
>> Инструктор: Па, ние не сакаат да се печати ја исклучи.
Па ова е bool тука, па ние сакаат да се вратат точно или неточно.
Ние сме велејќи, е овој број [? РРА? ?] Па ако е така,
ние едноставно се врати вистина.
Ако можам да ги запишува вистина.
>> СТУДЕНТСКИ: Зошто не би ви се врати нула?
Инструктор: така што би можеле врати нула, ако си сакал.
Но, во овој случај, бидејќи нашите функцијата враќа bool,
ние треба да се вратат или вистинити или лажни.
СТУДЕНТСКИ: Кога сте велејќи рационален израз,
може да ви го постави еднаква на лажни?
Како ако јас сакам да кажам, ако овој услов не е исполнет, како е горната е еднаква на лажни.
Тоа ќе се разбере ако само стави false на другата страна?
Инструктор: Да.
Така всушност, ако сте некогаш прави нешто
како е на горниот или е пониска, кој се враќа точно или неточно
а тоа е всушност лош стил на да речеме е еднакво е еднакво точно или еднаква на
е еднаква на лажни.
Сакате да го користите тој резултат како себеси како вашиот чек.
Не она што сакав.
Тоа е она што сакав.
Значи во случај од вас бараме за нешто како да се спаси оваа во в.
>> Значи, ако имаме int главната (празно) и нешто како ова.
И имаш ако е горната на некои влезни и вие сте
прашуваат дали можете да направите нешто како ова?
Нели?
СТУДЕНТСКИ: Се обидував да го направи тоа [нечујни].
Затоа што ако it's--
Инструктор: Токму така.
Па сакате тоа да биде лажно, нели?
СТУДЕНТСКИ: Да.
Инструктор: Значи во овој случај може сакате тоа да се изврши, ако тоа не е точно.
Така кул нешто што го правите таму е ова.
Па не заборавајте извичник точка негира работи?
Таа вели дека [нечујни] не значи.
Значи, ако ние се погледне само овој дел тука, ќе
велат дека евалуира до лажно како што сакате тоа да.
Не е неточно е точно кои значи ова ќе се изврши.
Дали тоа има смисла?
СТУДЕНТСКИ: Да.
Инструктор: Прекрасно.
ОК.
Па ние само може да се врати точно во овој случај.
Така, сега имаме две други случаи во овој случај.
Кои се нашите два други случаи?
Ајде да го на овој начин се направи.
Значи, да почнеме со друг ако вредностите на средината
е помал од вредноста сакаме.
Така и нашата вредност во средината е помалку од вредноста, дека ние сме во потрага за.
>> Така што врзани го правите мислам ние сакаме да се ажурираат?
Горниот или долниот?
Горниот?
Па на која страна на низа ние ќе треба да се гледа во?
>> СТУДЕНТ помал.
>> Инструктор: Ние одиме што треба да се гледа во левата страна.
Па што друго ако малку вредност е помала.
Така да твојот средна вредност тука е помалку од она што го сакаме.
Значи, сакаме да се земе десната страна на нашите низа.
Значи ние се случува да се ажурирање на нашите долната граница.
Па ние ќе превъзложите нашите пониски.
И што мислите пониски треба да биде?
СТУДЕНТ средна вредност?
Инструктор: Значи средината value--
СТУДЕНТ Плус 1.
Инструктор: --plus 1.
Може ли некој да ми каже зошто ние го имаме тоа плус 1?
>> СТУДЕНТСКИ [? Нема вредност?] е повеќе еднаква на неа.
>> Инструктор: Токму така.
Затоа што ние веќе знаете дека нашите средната вредност не е еднаква на
тоа и ние сакаме да го исклучат од сите наредни пребарувања.
Ако сте заборавиле дека плус 1, овој ќе се допаѓа јамка на неодредено време.
И само ќе бидат фатени во бесконечна јамка и тогаш ќе сегментации
и работите одат лошо.
Па секогаш да бидете сигурни дека не сте вклучувајќи го и вредност која вие само
погледна.
Па ние се грижи за тоа со плус 1.
>> Така, сега имаме нашата последна состојба кој јас секогаш за безбедност на доброто
можете да проверите тука, друго ако вредноста на средината е поголема од вредноста
сакаме.
Тоа значи дека ние сакаме левата рака половина.
Така што оној што ќе се дојде до ажурирање?
Горниот.
И она што е ова се случува да се изедначи?
Средниот минус 1, бидејќи, се разбира, ние сакаме
да бидете сигурни дека ние не сме гледајќи дека средната вредност повторно.
А потоа ние го имаме.
Тоа е тоа.
Тоа е сите бинарни пребарување е.
Тоа не е толку лошо, нели?
Тоа е како 10 линии на код со белиот простор.
Па многу моќен, многу корисно, ќе да биде користење на тоа во една од вашите подоцна psets.
Можеби не оваа, туку подоцна.
Па тоа се учи.
Тоа го сакаат.
Тоа ќе ви третираат добро.
Така Дали некој има било прашања за бинарни пребарување?
Да.
>> СТУДЕНТСКИ: Има ли значение дали вашата n е дури и чудно?
>> Инструктор: Не.
Затоа што ние го фрли на средината како int, тоа само ќе го намалит.
Па тоа ќе остане цел број и тоа ќе на крајот се најде решение преку сè.
Значи, вие не мора да се грижите за тоа.
Секој добар?
Страшни.
Кул.
Значи, вие момци доби тоа.
Слајдшоу.
Така како што ние се зборува за, знам Дејвид споменавме комплексноста runtimes.
>> Значи во најдобар случај, тоа е само еден, што ние го нарекуваме константен време.
Може ли некој да ми каже зошто тоа може да биде?
Каков тип на сценарио кое би значел?
Мм-НВ.
>> СТУДЕНТСКИ: [нечујни] first--
Инструктор: Значи средината се првиот елемент кој доаѓаме до, нели?
Значи или низа од една или што и ние сме во потрага за само
се случува да биде мирис бучица во средината.
Па тоа е нашиот најдобар случај.
Ќе го добиете во реални проблеми, веројатно не се случува да се постигне [нечујни] кои често.
Што е со нашите најлош случај?
Нашите најлош случај е дневник н.
И дека мора да се направи со целиот овластувањата на две нешто што јас разговаравме за.
>> Па во најлош случај тоа би значело дека моравме да се исецка надолу низа
се додека не беше елемент на еден.
Па моравме да го исецка надолу на половина онолку пати колку што ние би можел.
Тоа е зошто тоа е најавите n, бидејќи вие само задржи се дели на два дела.
Така претпоставки, работи што треба да знаете ако сте некогаш
случува да го користите бинарни пребарување.
Вашата елементи мора да бидат подредени.
Тие треба да бидат подредени, бидејќи тоа е единствениот начин на кој
може да знае ако сте во можност да се исфрли од половината.
>> Ако сте имале овој помешана торба на бројки и си ти што зборуваш,
Добро, јас одам да се провери средината број и бројот Јас барам
е помал од тоа, јас сум само ќе произволно да се исфрли од една половина.
Вие не би знаеле дали вашиот броеви со тоа, што другата половина.
Вашата листа треба да се подредени.
Исто така, ова може да биде оди напред малку,
но треба да има произволен пристап.
Што треба да биде во можност да само оди на тоа средниот елемент.
Ако треба да напречни преку нешто
или е потребно да дополнителни чекори да дојдеме до таа средината елемент,
тоа не е се логирате н повеќе, бидејќи сте додавање на повеќе работа во него.
И тоа ќе се направи малку повеќе смисла за две недели,
но јас само вид на сакаа да предговор, вие момци даде идеја за она што е
да дојде.
Но тие се две важно претпоставки
кои ви се потребни за бинарни листа.
Бидете сигурни дека тоа е подредени.
Тоа е голема за вие момци во моментов.
И на тој можеме да одиме во остатокот од нашите сорти.
Значи четири sorts-- меур, вметнување, селекција, и се логирате.
Сите тие се вид на кул.
Ако вие момци одлучи да ги преземе CS 124 ќе учат за сите видови на сорти.
И ако сте XKCD фен, има е навистина кул комично
како навистина неефективно видови, што јас Силно препорачувам случува да се погледне.
Еден од нив е како паника вид, кој е како, о не, врати случаен низа.
Исклучување на системот.
Остави.
Така хакерски хумор е секогаш добра.
>> Па дали некој се сеќавам вид на како само општа идеја
за тоа како меур вид работи.
Се сеќаваш ли?
>> СТУДЕНТСКИ: Да.
>> Инструктор: Одете за него.
>> СТУДЕНТСКИ: Значи си оди преку и ако тоа е поголем, тогаш ќе трампа два.
>> Инструктор: MM-хм.
Точно.
Така да само iterate преку.
Да проверите два броја.
Ако еден пред се поголеми од оној потоа,
само да ги разменуваат, така што во на овој начин сите од поголем број
меур нагоре кон крајот на листата и сите се пониски бројки меур надолу.
>> Дали тој ви покаже момци кул звук ефект сортирање видео?
Тоа е вид на кул.
Така како што Роберт само рече, алгоритам дека сте само чекор низ листата,
Замена на соседните вредности ако тие не се во ред.
А потоа само ги повторува додека не не прават никакви свопови.
Па не е лошо, нели?
Па ние само имаат брз пример тука.
Така што тоа се случува да се најде решение ги во растечки редослед.
Значи, кога ќе одиме во текот на првата време, ние се погледне преку осум
и шест очигледно не со цел, ние ги трампа.
>> Така се погледне на следниот.
Осум и четири не е во ред.
Разменуваат со нив.
А потоа осум и две, да ги разменуваат.
Там одиме.
Па по својата прва помине, вие знаете дека вашиот најголем број
ќе биде целиот пат на врвот, бидејќи тоа е само
ќе биде постојано поголема од се друго
и тоа е само случува да балон до сите на патот до крајот таму.
Дали тоа има смисла за секого?
Кул.
>> Па тогаш ние се погледне во нашата втора помине.
Шест и четири, прекинувач.
Шест и два, прекинувач.
И сега имаме неколку работи во ред.
Значи за секој пас дека ние направи преку целата наша листа,
ние знаеме дека, како и дека многу броеви на крајот ќе се подредени.
Така ги трета помине, која е една swap.
А потоа на нашата четврта помине, имаме нула слотови.
И така знаеме дека нашите низа е подредени.
>> А тоа е голема работа со балон вид.
Знаеме дека кога ние имаат нула свопови, дека
значи дека се што е во целосна ред.
Тоа е вид на тоа како ние се провери.
Значи ние сме, исто така, се случува да се код меур вид кој, исто така, не е толку лош.
Ниту еден од овие се толку лоши.
Знам дека тие може да изгледа малку страшно.
Знам кога Зедов класа, дури и кога
беше настава класа за прв пат минатата година,
Јас бев како, како можам да го направите ова?
Тоа го прави смисла во теорија, но како ние всушност го направите ова?
Кој е зошто јас исто така, сакаат да пешачат преку код со вас момци тука.
Па имам псевдокод за вас момци тоа време.
Па само имајте го ова на ум, како ние сме за да транзиција повеќе.
Па ние имаме некои контра дека следи на нашата размена,
затоа што ние треба да бидете сигурни дека ние сме проверка тоа.
И ние iterate целата низа како што скоро сторив со овој пример.
Ако елемент пред е поголема од елемент после каде сме во,
ние ги разменуваат и ние инкремент нашите шанкот, бидејќи веднаш штом ќе се разменуваат,
ние сакаме да ги споделите со нашите контра знам тоа.
Било какви прашања има?
Нешто се чини смешно овде.
СТУДЕНТСКИ: Дали се постави контра на нула секој пат кога ќе одат преку телефонска линија?
Не ви продолжувам да одам назад до нула секој пат?
Инструктор: Не мора да значи.
Па што се случува е да одиме низ овде.
Затоа направете време, се сеќавам, ова ќе се изврши еднаш без да успее.
Па затоа се случува да се постави counter еднаков на нула,
после тоа се случува да iterate преку.
Како што перебирает, тоа ќе се ажурира шанкот.
Како тоа надградби контра, кога тоа е направено, кога е постигнат на крајот на низата,
ако нашата листа не е сортирана, контра ќе се ажурира.
>> Па тогаш тоа проверува состојба и тоа вели, OK, е контра поголема од нула.
Ако е така, го направи тоа повторно.
Сакате да ги ресетирате така што кога ќе поминат низ, counter е еднаков на нула.
Ако одите преку сортирани низа, ништо не се менува,
ова не успее, и вие врати подредени листа.
Дали тоа има смисла?
СТУДЕНТСКИ: Тоа би можело во малку.
Инструктор: ОК.
Ако има било која друга прашање што доаѓа до.
Да.
>> СТУДЕНТСКИ: Што би функција биде за Замена елементи?
>> Инструктор: Па ние всушност може да се напише дека ако ние се случува да се во моментов.
Кул.
Така, на тој белешка, Алисон се случува за да се вратите на апаратот.
Тоа се случува да биде забавно.
И ние имаме убаво меур вид нешто овде.
Па јас веќе не велосипедизам преку низа.
Ние имаме свопови дека се еднакви на нула.
Значи, сакаме да се разменуваат со соседните елементи ако тие се на ред.
Па првото нешто што треба да не се iterate преку нашата низа.
>> Па, како мислите дека ние би можеле да iterate преку нашата низа?
Имаме за и јас е еднаква на 0.
Ние сакаме јас се помалку од n минус 1 минус k.
И јас ќе објасни дека во една секунда.
Па ова е optimization тука, каде што, се сеќавам како што реков по секоја пас
преку низа ние знаете дека што и е on--
>> Па по еден поминат ние знаат дека ова е сортирана.
По две минува знаеме е фактот што сите се подредени.
По три поминува ние знам што се подредени.
Па начинот на кој јас сум процесирањето преку низа тука,
е тоа е што си сигурен само да одиме преку она што го знаеме е несортиран.
ОК?
Тоа е само оптимизација.
Можете да го напише наивно само итерации сè,
тоа само ќе потрае подолго.
Со оваа четири јамка тоа е само еден убав оптимизација
затоа што знаеме дека по секоја целосна повторување преку низа тука,
како и секоја целосна јамка тука, знаеме дека еден повеќе од следниве елементи
ќе бидат подредени на крајот.
>> Значи ние не треба да се грижите за нив.
Дали тоа има смисла за секого?
Кул малку трик?
Па во тој случај, ако ние сме итерации,
знаеме дека сакате да проверите дали низа n и n плус 1 се во ред.
ОК.
Значи тука е псевдокод.
Ние сакаме да се провери ако низа н и n плус 1 се во ред.
Така што би можело да имаме таму?
Тоа се случува да биде некој условно.
Тоа ќе биде ако.
>> СТУДЕНТСКИ: Ако низа n е помалку од низата n + 1.
Инструктор: MM-хм.
Па, помалку од или поголема од.
СТУДЕНТСКИ: Поголем од.
Тогаш ние сакаме да ги разменуваат.
Точно.
Па сега да се влезе во она што е механизам за Замена на нив?
Па отидовме преку оваа кратко, тип на swap функција минатата недела.
Дали некој се сеќавам како тоа работеше?
Па ние не може само да ги превъзложите, нели?
Поради тоа што еден од нив ќе се изгуби.
Ако ние, вели еден е еднаков на Б и после B е еднаков на A, сите одеднаш и двете од нив
се само еднаква на B.
>> Значи она што треба да направите е ние имаат привремен променлива која е
случува да се одржи еден наш додека ние сме во процес на Замена.
Значи она што го имаме е ќе имаме некои int температура е еднаква to-- можете да го доделите
за кое оној што го сакате, само бидете сигурни дека ги пратите на it--
така што во овој случај, јас ќе одам да се додели на низа n + 1.
Така што се случува да се одржи без оглед на вредноста не е со тоа, што вториот блок
дека ние сме во потрага на.
>> И потоа можеме да направиме е можеме да одиме напред и повторно низа н плус 1,
затоа што ние знаеме имаат тоа вредност се чуваат.
Ова е исто така еден од големите things-- Јас не знам дали некој од вас
имаше проблеми каде што ако се префрлат на две линии на код одеднаш функционираат работите.
Order е многу важна во CS.
Така бидете сигурни дека дијаграм работи надвор, ако е можно
како да се она што всушност се случува.
Па сега ние ќе се превъзложите низа н плус 1,
затоа што ние знаеме имаат тоа вредност се чуваат.
>> И ние може да се додели дека на низата n или во овој случај низа i.
Премногу варијабли.
ОК.
Така, сега сме прераспореден низа з плус 1 да се изедначи она што е во низа з.
И сега можеме да одиме назад и доделите низа јас на што?
Некој?
>> СТУДЕНТСКИ: 10.
>> Инструктор: 10.
Точно.
И едно последно нешто.
Ако сме го сменил сега, она што ние треба да направам?
Што е едно нешто кој се случува да ни каже
ако некогаш го прекине оваа програма?
Она што ни кажува дека ние имаат подредени листа?
Ако ние не вршат никакви свопови, нели?
Ако свопови е еднаква на нула на крајот на оваа.
Значи секогаш кога ќе се изврши, swap, како што само го направи тука, ние сакаме да се ажурира свопови.
И знам, имаше прашање рано за може да ви
користат нула или еден наместо на точно или неточно.
И тоа е она што ова го прави тука.
Па ова вели дека ако не свопови.
Значи, ако свопови е нула, кои is-- Јас секогаш добие мојата вистини и ми falses измешаат.
Ние сакаме ни да се оцени да точно и тоа не е.
Значи, ако тоа е нула, тогаш тоа е неточно.
Ако го негира со [? тресне?] станува вистина.
Па тогаш оваа линија извршува.
>> Вистини и лажни и нули и единици се луди.
Само ако имате бавно прошетка низ него тоа ќе го направи смисла.
Но тоа е она што оваа мала малку код овде прави.
Па ова проверки за да се види сме направиле било свопови.
Значи, ако тоа е ништо освен нула, тоа се случува да се лажни
и целата работа е оди да се изврши повторно.
Кул?
>> СТУДЕНТСКИ: Што значи пауза направам?
>> Инструктор: Break само ви избива на јамка.
Па во овој случај тоа би исто како и стави крај на програмата
и што би само имате подредени листа.
СТУДЕНТСКИ: Неверојатни.
Инструктор: Жал ми е?
СТУДЕНТСКИ: Бидејќи претходно ние употребиле писмени 1 над писмена нула
да се претстави дека ако кои ќе работат или не.
>> Инструктор: Да.
Така може да се врати нула или 1.
Во овој случај, бидејќи ние не сме всушност прави ништо со функцијата,
ние само сакаме да се скрши.
Ние навистина не се грижат за тоа.
Кочница е исто така добар, ако Се користи за кршење
на четири јамки или состојби кои вие не сакате да се задржи извршување.
Тоа само ќе ве однесе надвор од нив.
Тоа е малку на нијанса нешто.
Се чувствувам како да има многу рака мавтајќи,
како ќе дознаете за ова наскоро.
>> Но ќе дознаете за ова наскоро.
Јас ветувам.
ОК.
Значи не сите да балон вид?
Не е премногу лошо.
Iterate преку, swap работи со користење на температура променлива, и ние сме сите во собата таму?
Кул.
Страшни.
ОК.
Назад во PowerPoint.
Било какви прашања во целина за овие досега?
Кул.
Мм-НВ.
>> СТУДЕНТСКИ: [нечујни] int главната обично.
Дали треба да имате дека за ова?
>> Инструктор: Па бевме само бараат само на вистински сортирање алгоритам.
Ако го имаше во рамките на како поголеми програма,
вие ќе треба int главната некаде.
Во зависност од каде што го користите овој алгоритам,
тоа ќе се утврди што е да се врати од тоа.
Но, за нашиот случај, ние сме строго гледајќи како го прави ова всушност
iterate преку низа.
Така што не се грижи за тоа.
>> Па ние се зборува за најдобар случај и најлош случај сценарија за бинарни пребарување.
Така, тоа е исто така важно да се направи што за секој од нашите видови.
Па што мислите дека е најлошото случај траење на меурот вид?
Вие, момци, се сеќаваш?
>> СТУДЕНТСКИ: N минус 1.
Инструктор: N минус 1.
Па тоа значи дека има N минус 1 споредби.
Па едно нешто да се реализира е дека на првиот повторување,
ние поминат низ, ние споредуваат овие two--, така што е 1.
Овие два, три, четири.
Па по едно повторување ние веќе имаат четири споредби.
Кога јас зборувам за траење и n.
N претставува број на споредби како функција од колку елементи
имаме.
ОК?
>> Па ние одат преку, имаме четири.
Следниот пат кога ќе знаат дека ние не треба да се грижи за тоа.
Ние споредуваат овие две, овие две, овие две,
и ако ние не го имаат тоа оптимизација со четири јамка дека сум го напишала,
ќе се споредуваат тука относнотова.
Така ќе треба да се ја извршите преку низа
и направи н споредби н време, бидејќи секој пат кога ние
поминува низ него ние вид едно нешто.
>> И секој пат кога трчаме низ низа, правиме n споредби.
Така, нашето траење за ова е всушност n квадрат, што
е многу полоша во нашите логирате крајот, бидејќи тоа
значи ако ние имавме четири милијарда елементи, тоа е
ќе ни земе четири милијарди квадрат, наместо на 32.
Па не и најдобар траење, но за некои работи,
знаете, ако сте во рамките на одреден спектар на елементи
меур вид може да биде во ред да се користи.
>> ОК.
Па сега што е најдобар случај траење?
СТУДЕНТСКИ: Нулта?
Или 1?
>> Инструктор: Така 1 ќе биде еден споредба.
Прав.
>> СТУДЕНТСКИ: N минус 1?
>> Инструктор: Па, да.
Па n минус 1.
Секогаш кога имате концепт како н минус 1, тежнееме да само да го заспивам
а ние само се каже н затоа што имаат да се споредуваат секој од these-- секој пар.
Значи тоа ќе биде n минус 1, кое ние ние само би рекол е околу н.
Кога си имаш работа со траење, сè е во се приближува.
Се додека експонент правилно, вие сте прилично добар.
>> Тоа е како ние се справи со неа.
Па дека најдобар случај е n, што значи дека листата е веќе сортирани,
и сите ние се извршува преку и проверете дали тоа е подредени.
Кул.
Добре.
Така како што гледате тука, ние само треба малку повеќе графикони.
Па N на квадрат.
Забавно.
Многу полошо отколку n како што гледаме, и многу, многу полошо отколку најавите 2n.
И тогаш исто така се влезе најавите логови.
И да ве однесе 124, ќе го добиете во како најавите ѕвезда, која е како луди.
Значи, ако сте заинтересирани, пребарување најавите ѕвезда.
Тоа е вид на забава.
Па ние ја имаат оваа голема шема.
Само на главите нагоре, ова прекрасен шема да имаат
за вашиот среднорочна затоа што ние долго да ве прашам овие изтънява.
Па само главите нагоре, ја имаат оваа на вашиот среднорочна на вашиот убав измамник лист
таму.
Па ние само го погледна меур вид.
Најлош случај, n квадрат, најдобар случај, н.
И ние ќе да се погледне на други.
>> И како што можете да видите, само оној кој навистина прави добро
е спојување вид, кои ние ќе се влезе зошто.
Значи ние се случува да одат на Следниот here-- селекција вид.
Дали некој се сеќавам како селекција вид работел?
Одат за тоа.
>> СТУДЕНТСКИ: Во суштина оди преку цел и да се создаде нова листа.
И како што сте ставање елементи во, ги стави на вистинското место
во нова листа.
>> Инструктор: Значи тоа звуци повеќе како вметнување вид.
Но ти си навистина блиски.
Тие се многу слични.
Дури и јас да ги помешал понекогаш.
Пред овој дел јас бев како, почекајте.
ОК.
Па што сакате да го направите, е избор вид,
начин можете да се сетите во врска со тоа и начинот на кој
Јас бидете сигурни дека не се обидуваат да се добие им измешани, не е тоа оди преку
и тоа го избира најмал број и тоа
става, дека на почетокот на вашата листа.
Тоа го свопови со тоа прво место.
Тие всушност имаат пример за мене.
Страшни.
Па само начин да се мисли на it-- избор вид, изберете најмалите вредност.
И ние си оди за да поминува низ еден пример
што мислам дека ќе помогне, бидејќи Мислам дека визуелни секогаш помагаат.
Па ние почнуваме со нешто кој е комплетно несортиран.
Црвена ќе биде несортиран, зелен ќе бидат подредени.
Сето тоа ќе има смисла во една секунда.
>> Па ние одат преку и ние iterate од почетокот до крајот.
И ние се каже, во ред, 2 ни најмал број.
Па ние сме случува да се земе 2 и ние ќе да се движи кон предниот дел на нашите низа
затоа што тоа е најмал број што го имаме.
Значи тоа е она што ова е тоа тука.
Тоа е само случува да се разменуваат овие две.
Така, сега имаме сортирано дел и несортиран дел.
И она што е добро да се запамети за избор на вид
е ние сме само избор на од несортиран дел.
>> Подредено дел можете само остави на мира.
Мм хм?
>> СТУДЕНТСКИ: Како не го знае она што е на најмалиот без споредувајќи го
до секој друг вредност во низа.
Инструктор: Тоа го прави споредете го.
Ние се допаѓа тоа прескокнуваат.
Оваа е само општа целина.
Да.
Кога ние пишуваме кодот Јас сум сигурни дека ќе бидете позадоволни.
Но ќе ги чувате оваа прва елемент како најмала.
Ќе се споредат и вие се каже, во ред, тоа е помал?
Да.
Го чувам.
Еве што е помал?
Не?
>> Ова е ваша најмалите, превъзложите да вашата вредност.
И ќе бидете многу посреќни кога одиме преку код.
Па ние одат преку, ние го трампа, па потоа ние се погледне на овој несортиран дел.
Па ние си оди за да изберете три.
Ние си оди за да го постави на на на крајот од нашиот Подредено дел.
И ние сме само ќе да го задржи тоа тоа, тоа го прават, и тоа го прават.
Значи ова е нашата вид на псевдокод тука.
Ние ќе го кодот тука во секунда.
Но само нешто да одиме преку на високо ниво.
Си оди за да одат од i е еднаква на 0 до n минус 2.
Тоа е друга оптимизација.
Не грижете се премногу за неа.
Па како што можете велеа.
Како Јаков велеше, како ние ги пратите на она што нашите минимум е?
Како да знаеме?
Ние треба да се споредуваат се што е во нашата листа.
>> Па минимум е еднаква на i.
Тоа е само велејќи дека во овој случај индексот на нашата минимална вредност.
Па после тоа се случува да iterate преку и тоа оди од j е еднаква на i плус 1.
Па ние веќе знаете дека тоа е нашиот прв елемент.
Ние не треба да го споредуваат со себе.
Па да почнеме тоа во споредба со следниот еден кој е зошто тоа е i плус 1 до n
минус 1, кое е крајот на низата таму.
И ние изјави дека ако низа на j е помала низа min,
тогаш ние превъзложите каде нашите минимални индекси е.
>> И ако min не е еднаква на i, како во каде што бевме назад во текот тука.
Така се допаѓа кога првпат го направи ова.
Во овој случај, тоа ќе започне во нула, тоа ќе заврши се две.
Така мин не би еднаков јас на крајот.
Која ни овозможува да се знае дека ние треба да ги разменуваат.
Се чувствувам како конкретен пример ќе помогне да се многу повеќе од тоа.
Па јас ќе се кодира ова со вас момци токму сега и мислам дека ќе биде подобро.
>> Sorts имаат тенденција да работат на тој начин со тоа, што тоа е често подобро само да ги види.
Значи она што сакате да направите, е ние прво сакаат најмалите
елемент во својата позиција во низа.
Токму она што Јаков го кажувам.
Вие треба да ги чувате дека некако.
Па ние си оди за да започнете перебора низа.
Ние се случува да се каже, тоа е нашата првиот само за да се започне со.
Значи ние се случува да мора int најмалиот е еднаква на низа на i.
>> Така што едно нешто да се забележи, секој време овој циклус извршува,
ние почнуваме еден чекор понатаму заедно.
Кога ќе почнеме ние гледаме на оваа.
Следниот пат кога ние iterate преку, ние сме со почеток во оваа
и тоа ни најмалите вредност доделување.
Така што е многу слично на балон вид каде знаеме дека по еден поминат,
овој последен елемент се подредени.
Со избор на вид, тоа е токму спротивното.
>> Во секоја помине, ние знаеме дека првиот е подредени.
После вториот пас, на вториот ќе бидат подредени.
И како што видов со слајд примери, нашите подредени дел само расте.
Па со поставување на нашите најмала да низи јас, сето тоа го прави
се свива она што ние сме во потрага на, па како
да се минимизира бројот на споредби што ги направи.
Дали тоа се направи смисла на сите?
Дали ме треба да се води преку тоа повторно побавно или во различни зборови?
Јас сум среќен да.
ОК.
>> Па ние сме чување вредност во овој момент,
но ние исто така сакаме да ја запази индексот.
Значи ние се случува да се сместат позиција на најмалиот
еден, што е само ќе биде и.
Па сега Јаков е задоволен.
Имаме и со што се чуваат.
И сега ние треба да се погледне преку несортиран дел на низа.
Значи во овој случај ова ќе биде нашата несортиран.
Ова е з.
ОК.
>> Значи она што се случува да го направите се случува да биде за еден циклус.
Секогаш кога ќе треба да се iterate преку низа,
вашиот ум може да оди на за телефонска линија.
Па за некои int к equals-- она ​​што мислиме
k се случува да изнесува да се започне со?
Ова е она што го поставивме како наш најмалите вредност и ние сакаме да се спореди.
Што сакаме да го споредуваат со?
Тоа се случува да биде овој следната, нели?
Значи, сакаме k за да се иницијализира на i плус 1 за да започнете.
>> И ние сакаме k во овој случај ние веќе големина чуваат до тука,
па ние само може да се користи големина.
Size да бидат со големина на низата.
И ние само сакаме да ажурира k од страна на еден секој пат.
Кул.
Па сега ние треба да се најде на најмалиот елемент тука.
Значи, ако ние iterate преку, ние сакам да кажам, ако низа на к
е помала од нашата најмалиот value-- ова е местото каде што ние сме всушност
следење на она што е најмалиот here--
тогаш сакаме да преназначаване она што нашите најмалите вредност е.
>> Ова значи дека, ох, ние сме итерации тука.
Без оглед на вредноста е тука е не ни најмалите работа.
Ние не го сакаат тоа.
Ние сакаме да го превъзложите.
Значи, ако ние сме го прераспределување, што прават мислите дека би можеле да бидат во овој код овде?
Ние сакаме да преназначаване Најмалиот и позиција.
Значи она што е најмалиот сега?
СТУДЕНТСКИ: Низа к.
Инструктор: Низа к.
И она што е позиција сега?
Што е индекси на ни најмалите вредност?
Тоа е само k.
Па низа k, k, тие се совпаѓаат.
Па сакавме да преназначаване тоа.
А потоа по најдовме нашата најмалите, така што на крајот на овој за јамка
тука се најдоа она што нашите најмалите вредност е, па ние само го трампа.
Во овој случај, како што велат нашите најмалиот вредност не е од тука.
Ова е нашиот најмалиот вредност.
>> Ние само сакаме да го смениме тука, што е она што swap функција на дното
направив, кои ние едноставно напиша на заедно пред неколку минути.
Па затоа треба да изгледа познато.
И тогаш тоа само ќе iterate преку додека не се достигне сите на патот
до крај, што значи дека може имаат нула елементи кои се несортиран
и сè друго е сортирана.
Да има смисла?
Малку поконкретно?
Кодот помош?
>> СТУДЕНТСКИ: За големината, никогаш не навистина го дефинира или да го промените,
како не го знаеш?
>> Инструктор: Значи едно нешто да се забележите тука е int големина.
Па ние сме велејќи дека во овој sort-- вид е функција во овој case-- тоа е
селекција вид, тоа е усвоен во со функција.
Значи, ако тоа не е донесен во, ќе се направи нешто
како и со должината на низата или ќе iterate преку
да се најде должината.
Но, бидејќи тоа е донесен во, ние само може да го користи.
Можете само да се претпостави дека на корисникот ви даде валидна големина која
всушност претставува големината на низата.
Кул?
>> Ако вие момци имате било какви проблеми со овие или сакате повеќе пракса кодирање видови
на свој, треба да одат на study.cs50.
Тоа е алатка.
Тие имаат Проверка дека всушност можете да пишувам.
Тие го прават псевдокод.
Тие имаат повеќе видео и слајдови вклучувајќи ги и оние што се користи тука.
Значи, ако сте уште се чувствува малку нејасни, обидете се тоа.
Како и секогаш, дојде да разговара со мене, исто така.
Прашање?
>> СТУДЕНТСКИ: Дали сакаш да кажеш големина е претходно дефинирано?
Инструктор: Да.
Size е претходно дефинирано горе тука во декларацијата функција.
Така да се претпостави дека тоа е е донесен во од страна на корисникот, како и за простота,
ние ќе се претпостави дека кориснички ни даде точната големина.
Кул.
Значи тоа е избор на вид.
Дечки, знам дека учите многу денес.
Тоа е густа податоци за секција.
Така да со тоа, ние ќе се обидеме да се оди на вметнување вид.
>> ОК.
Па пред тоа ние треба да направите нашите траење анализа тука.
Па во најдобар случај, доделена бидејќи јас ви покажа
маса што веќе вид го даде далеку.
Но најдобар случај траење, она што мислиме?
Ќе бидат подредени.
N на квадрат.
Некој има објаснување зошто мислите?
>> СТУДЕНТСКИ: Ти си споредување through--
Инструктор: Токму така.
Ти си споредување преку.
На секој повторување, иако ние сме декрементирование ова по еден,
ти си уште бараат преку сè да се најде најмалиот еден.
Па дури и ако вашиот најмалиот вредност е тука на почетокот,
ти си уште го споредување против се друго
да бидете сигурни дека тоа е најмалиот нешто.
Па ќе се заокружи трчање преку приближно n квадрат пати.
Добре.
И, што е најлош случај?
Исто така n квадрат, бидејќи си оди што треба да се прави тоа истата постапка.
Значи во овој случај, селекција вид има нешто
дека ние исто така, повик очекуваното траење.
Значи, во другите, ние само знам на горниот и долниот границите.
Зависност од тоа колку луди нашите листата е или како несортиран е тоа,
тие се разликуваат помеѓу n или n квадрат.
Ние не знаеме.
>> Но, бидејќи селекција вид ги има истите најлошото и најдобар случај, што ни кажува дека
без оглед на тоа каков тип на влез ние имаат, без разлика дали тоа е сосема
сортирани или целосно обратна подредени, тоа е
случува да се земе иста количина на време.
Па во тој случај, ако се се сеќавам од нашата маса,
тоа всушност имал вредност која овие два вида немаат,
кој се очекува траење.
Па знаеме дека секогаш кога трчаме избор вид,
тоа е гарантирано да се кандидира n квадрат време.
Существует не варијабилност таму.
Тоа е само очекува.
И, повторно, ако сакате да дознаете повеќе, земете CS 124 во пролет.
Добре.
Ние сме виделе оваа.
Кул.
Така вметнување вид.
И јас сум веројатно нема да пожарот преку овој.
Јас не ќе мора вие момци го код.
Ние само ќе одат преку него.
Така вметнување вид е вид на слични на избор вид
со тоа, што ги имаме и двете несортированная и подредени дел на низа.
>> Но она што е различно е тоа што како што ние одиме преку една по една,
ние само се земе она број е следниот во нашата несортиран,
и правилно да го средиме во нашите Подредено низа.
Тоа ќе се направи повеќе смисла со пример.
Па сè започнува како несортиран, Исто како и со избор на вид.
И ние си оди за да се најде решение за ова во Растечки редослед како што биле.
Така, на нашиот прв пас ние го направи првиот вредност
и ние се каже, во ред, вие сте сега во листа со себе.
>> Затоа што ти се во листата на од страна на себе си, вие се подредени.
Алал да му е за да биде првиот елемент во оваа низа.
Сте веќе сортирани сите на свој.
Така, сега имаме сортирано и несортиран низа.
Па сега ние го направи првиот.
Она што се случува помеѓу тука и тука е дека ние се каже,
Добро, ние ќе се погледне на првата вредност на нашите несортиран низа
и ние си оди за да влез во својата правилната место во Подредено низа.
>> Значи она што го правиме е ние се 5 и ние се каже, во ред, 5 е поголем од 3,
па ние само го вметнете право на десно од тоа.
Ние сме добро.
Па потоа да одиме на нашите следниот.
И ние се 2.
Ние се каже, во ред, 2 е помалку од 3, па знаеме дека тоа
треба да биде во пред нашата листа сега.
Па она што го правиме е ние им помогнам на 3 и 5 долу и се движиме 2 во таа првиот слот.
Па ние сме само го поставите во правилната место треба да биде.
>> Тогаш ние се погледне во нашите следниот, и ние велиме 6.
OK, 6 е поголема од што е во наша Подредено низа,
па ние само тоа ознака на до крај.
А потоа ќе погледнеме во 4.
4 е помалку од 6, тоа е помалку од 5, но тоа е поголема од 3.
Па ние само го вметнете право во средината помеѓу 3 и 5.
Па да се направи тоа малку малку поконкретни,
тука е вид на идеја за она што се случило.
Па за секој несортиран елемент, ние се утврди каде во сортирани дел
е.
>> Па имајќи го во предвид сортирани и несортиран,
ние треба да напречни преку и фигура од каде што се вклопува во Подредено низа.
И ние го вметнете со менувањето елементи на правото го долу.
А потоа ние едноставно се задржи итерации, додека ние
имаат сосема подредени листа каде несортиран сега нула
и сортирани зазема интегритет на нашата листа.
Значи, повторно, да се направат работите уште поконкретни, имаме псевдокод.
>> Значи, во основа на i е еднаков на 0 до n минус 1,
тоа е само должината на нашите низа.
Имаме некои елемент, кој е еднаков на првата низа или првата индексите.
Ние во собата j еднаква на тоа.
Па така додека j е поголема од нула и низа, j минус 1
е поголема од елемент, така што сите тоа го прави
се што си сигурен дека Вашата ѕ навистина претставува
несортиран дел од низа.
>> Така, додека се уште постои нешта да се најде решение и ѕ минус еден is-- она ​​што
е елемент на неа?
Ј никогаш не бил дефиниран овде.
Тоа е вид на досадни.
ОК.
Относнотова.
Така й минус 1, ти си проверка елементот пред него.
Си ти што зборуваш, во ред, е елемент пред секаде каде што јас am-- нека
всушност се подготви ова.
Па да речеме ова е како на нашиот втор обид.
Па јас се случува да бидат еднакви до 1, кој е тука.
>> Па i ќе биде еднаков на 1.
Оваа ќе биде 2, 4, 5, 6, 7.
Добре.
Така, нашето елемент во овој случај се случува да биде еднакво на 4.
И ние имаме некои ѕ тоа е ќе биде еднаков на 1.
О, й се декрементирование.
Тоа е она што е.
Па j е еднаква на i, така што оваа е изрека е дека како што се движи напред,
ние сме само што си сигурен дека ние не сме над
индексирање на овој начин, кога ние се обидуваме да вметнете работи во нашите подредени листа.
>> Па кога j е еднакво на 1, во овој случај и низа ѕ минус одно-- така низа ѕ минус 1
е 2 во оваа case--, ако тоа е поголема од елемент,
после сето ова се прави се менува работите надолу.
Значи во овој случај, низа j минус еден ќе биде нула низа, што е 2.
2 не е поголем од 4, така што ова не се изврши.
Така промената не се движи надолу.
Што тоа не е тука само движење на сортиран низа надолу.
Во овој случај, всушност, ние би можеле да do-- ајде да се направи овој 3.
Значи, ако сакаме да одиме преку со овој пример, ние сме сега тука.
Ова се подредени.
Ова е несортиран.
Кул?
Па i е еднакво на 2, па нашите елемент е еднакво на 3.
И нашите j е еднакво на 2.
Значи ние се погледне преку и ние се каже, во ред, е низа ѕ минус еден
поголема од елемент дека ние сме во потрага по?
А одговорот е да, нели?
4 е поголемо од 3 и j е 2, така што овој код се извршува.
>> Па сега она што го правиме низа на 2, па токму тука, ние ги разменуваат.
Па ние само се каже, во ред, низа на 2 е сега се случува за да биде 3.
И j се случува да е еднаква на j минус 1, кој е 1.
Тоа е ужасно, но вие момци го добиете идеја.
J е сега еднаков на 1.
И низа й е само ќе биде еднаква на нашата елемент, кој е 4.
Јас избришани нешто што не треба имаат или miswrote нешто,
но вие момци го добиете идеја.
>> Да го преместите на н.
А потоа, ако тоа беа, што би јамка повторно и тоа ќе каже, во ред, j е 1 сега.
И низа j минус 1 е сега 2.
Е 2 помалку од нашите елемент?
Не?
Тоа значи дека ние сме вметнува овој елемент
во правилната место во нашата Подредено низа.
Тогаш можеме да се земе тоа предвид и да се каже, Добро, ни сортирани низа е тука.
И тоа ќе се земе овој број 6 и да биде како, добро, е 6 помалку од оваа бројка?
Не?
Кул.
Ние сме во ред.
>> Направете го тоа повторно.
Ние велиме 7.
Е 7 помалку од крајот на нашата Подредено низа?
Не.
Значи ние сме во ред.
Така што ова ќе бидат подредени.
Во основа сето тоа го прави е тоа е велејќи преземање
на првиот елемент на Вашата несортиран низа,
дознаам каде оди во вашиот Подредено низа.
И тоа само се грижи на свопови да го направите тоа.
Ти си во основа, само Замена додека не е во право место.
Визуелна слика е тоа што сте се движат се надолу со тоа.
>> Па тоа е како половина меур вид стил.
Проверете студија 50.
Силно препорачувам обидува да кодот тоа на своја.
Ако имате било какви прашања или сакате да види примерок код за вметнување вид,
молам да ме известите.
Јас сум секогаш околу.
Така најлош случај траење и најдобар случај траење.
Како што можете дечко видов од табелата што веќе покажа вас, тоа е и н квадрат и n.
>> Толку вид да оди надвор од она што ние разговаравме за со нашите претходни видови, најлош
случај траење е дека ако тоа е сосема вон едиции,
ние треба да се споредуваат сите овие n пати.
Ние го правиме целина многу споредби бидејќи ако тоа е во обратен редослед,
ние сме случува да се каже, во ред, овој е иста, тоа е добро,
и овој еден ќе треба да се во споредба против првиот корисник да се помести назад.
И како што ние се кон опашката крајот, ние имаме
да се споредуваат, да ги споредиме, и споредуваат против сè.
>> Па тоа завршува се приближно n квадрат.
Ако тоа е точно тогаш вие се каже, во ред, 2, ти си добро.
3, ти си во споредба со 2.
Ти си добро.
4, може само да се споредуваат со опашката.
Ти си добро.
6, да се спореди со опашката, ти си во ред.
Значи за секои место, ако тоа е веќе сортирани, ти си едно споредба.
Па тоа е само н.
И бидејќи ние имаме најдобар случај траење на n и најлош случај траење на n
квадрат, ние немаме очекуваното траење.
>> Тоа само зависи од хаос на нашата листа таму.
И повторно, уште крива и другата маса.
Па разлики помеѓу сорти.
Јас сум само ќе бриз преку, јас се чувствувам како ние сме зборуваше опширно
за тоа како тие сите видови на се разликуваат и се поврзат заедно.
Па се спојат вид е последен Јас ќе ти роди момци со.
Ние имаме прилично шарени сликата.
Па се спојат вид е рекурзивен алгоритам.
Така вие се знаете што рекурзивен функција е?
>> Секој сака да се каже?
Сакате да се обидете?
Така рекурзивен функција е само функција која што се нарекува.
Значи, ако вие момци се запознаени со Фибоначи секвенца,
тоа е смета рекурзивен затоа што ќе се земе претходните две
и додадете ги заедно да ја добиете вашата следниот.
Така рекурзивен, јас секогаш мислам на рекурзијата како што е како спирала
па ти си како незапирливото надолу во неа.
Но тоа е само функција дека се нарекува себеси.
>> И, всушност, навистина брзо можам може да ви покаже она што изгледа како.
Така рекурзивен тука, ако гледаме, ова е рекурзивен начин да се сумира во текот низа.
Така што сите тоа што го правиме е имаме сума функција
сумата што изведува големина и низа.
И ако забележите, големина понижавания од страна на еден секој пат.
И сите тоа го прави е ако x е еднаква на zero-- па ако на големината на низата
е еднаков на zero-- таа се враќа нула.
>> На друг начин го сумира ова последниот елемент на низата,
а потоа го претставува збир на остатокот од низа.
Така, тоа е само да го урива во помали и помали проблеми.
Скратам приказната, рекурзија, функција која се нарекува себеси.
Ако тоа е се што излезе од ова, тоа е она што рекурзивен функција е.
Ако се земе 51, ќе добиете многу, многу удобно со рекурзија.
Тоа е навистина кул.
Тоа го направи смисла на како 03:00 една ноќ надвор.
А јас бев како, зошто никогаш не ја користам оваа?
>> Значи за спојување вид, во основа она што се случува да се направи, е тоа е
случува да го срушат и се кршат тоа надолу, додека тоа е само еден елементи.
Единствена елементи се лесни да се најде решение.
Ние се види тоа.
Ако имате еден елемент, тоа е веќе се смета подредени.
Па за внесување на n елементи, ако n е помал од 2,
само се вратат, бидејќи тоа значи дека тоа е 0 или 1 како што видовме.
Оние се смета сортирани елементи.
>> Инаку тоа се скрши на половина.
Сортирате првата половина, сортирање втората половина, а потоа ги спои заедно.
Затоа се вика спојување вид.
Па ние имаме тука ние ќе средиме овие.
Значи ние ги задржи имајќи ги до големината низа е 1.
Па кога тоа е 1, ние само се вратат бидејќи ова е сортирани низа,
и ова е сортирани низа, и тоа е Подредено низа, сите ние сме подредени.
Па потоа она што го правиме е ние започнете спојување заедно.
>> Па начинот на кој можете размислуваат за спојување е
можете само отстранување на помали бројот на секој од под низи
и само да го додадете на се појавија низа.
Па ако се погледне тука, кога имаме овие групи имаме 4, 6, и 1.
Кога сакаме да се спојат овие, ние се погледне во овие први две
и ние се каже, во ред, 1 е помал, оди на фронт.
4 и 6, нема ништо да се споредат него за да, само да го ознака на до крај.
>> Кога ние се комбинираат овие два, ние само изведува на помали една од овие две,
така што е 1.
И сега ние се помал од овие две, па 2.
Помал од овие две, 3.
Помали од овие две, 4, 5, 6.
Па ти си само одлепувате овие.
И затоа што сум е сортирани и претходно,
вие само треба еден споредба секое време таму.
Така повеќе код овде, правична застапеност.
Значи кога ќе почнете на средината и Ви вид левата и десната
и можеш само да се спојат тие.
>> И ние немаме код за спојат во право тука.
Но, повторно, ако одите на учат 50, тоа ќе биде таму.
На друг начин доаѓаат разговара со мене ако сте сепак збунети.
Толку кул работа тука е дека најдобар случај, најлош случај, и се очекува траење
сите се во log n, што е далеку подобро отколку што сум
виден за остатокот од нашите сорти.
Ние сме виделе N на квадрат и она што ние, всушност,
добиете тука е н најавите n, што е одлично.
>> Гледам како многу подобро тоа е.
Таков убав крива.
Па многу повеќе ефикасни.
Ако некогаш може, употреба спојат вид.
Тоа ќе ви заштеди време.
Потоа повторно, како што рековме, ако не ви оди во овој пониски регионот,
тоа не го направат тој многу разлика.
Добивате до илјадници и илјадници влезови,
вие дефинитивно сакате повеќе ефикасен алгоритам.
И, повторно, нашата прекрасна маса на сите видови дека вие момци научив денес.
>> Па знам тоа е густа ден.
Ова не е секогаш се случува за да ви помогнат со вашиот PSET.
Но, јас само сакам да се направи одрекување тој дел не е само за psets.
Сите на овој материјал е фер игра за својата midterms.
И, исто така, ако го направите продолжи со ВС, овие се навистина важни основите
кои ќе треба да се знае.
Па некои денови ќе биде малку повеќе PSET помош,
но неколку недели ќе биде многу повеќе вистинската содржина
дека не може да се чини супер корисни за вас во моментов,
но јас ветувам ако продолжиш на ќе биде многу, многу корисни.
>> Па тоа е тоа за дел.
Down на жица.
I го направи тоа во рок од една минута.
Но таму да одите.
И јас ќе имаат крофни или бонбони.
Дали некој е алергичен на ништо, патем?
Јајца и млеко.
Така крофни се не?
ОК.
Добре.
Чоколадо не?
Активните.
Starbursts се добри.
ОК.
Ние си оди за да имаат StarBurst следната недела потоа.
Тоа е она што ќе добиете.
Вие момци имаат голема недела.
Прочитајте ја спец.
>> Дозволете ми да знам дали имате било какви прашања.
Pset два степени треба да биде до вас од страна на четврток.
Ако имате било какви прашања за тоа како јас оценето нешто
или зошто оценето нешто начинот на кој јас не, пишете ми, дојди да разговара со мене.
Јас сум малку луд ова недела, но јас ветувам
Јас се уште ќе одговори во рок од 24 часа.
Така имаат голема недела, секого.
Среќно на вашиот PSET.