>> [За възпроизвеждане на музика]
>> DAVID J. Malan: Добре.
Така че, добре дошъл отново.
Това е CS50, и е В края на седмицата три.
>> Така спомням през последните няколко седмици, Прекарали сме доста малко
време на C, на програмиране, на синтаксис.
И това е съвсем нормално, ако сте все още се борят с проблема Set 2, да бъде
блъскате главата в стената.
Това е загадъчен изглеждащи съобщения за грешки и грешки, които сте
съвсем не могат да преследват.
Защото, бъдете сигурни, че само за една време, няколко седмици ще погледнем назад
неща, като Цезар, и [? V-genair,?] може би дори пляскане, и
осъзнават колко далеч сте дошли в кратък период от време.
Така че, ако това е някаква утеха, Дръж се за сега.
>> Днес, обаче, ние започваме да прехода към нещата по-високо ниво.
И започваме да приемаме за даденост, че вие знаете как да програмирате, или най-
най-началото на че нивото на комфорт.
И ние ще започнем да се помисли как можем отида за проектиране на програми за по-
ефективно.
Как можем да отидем за оптимизиране на ефективност на нашите алгоритми и
общо решаване на по- интересни проблеми.
И започват да се приемат за даденост, че ако искаме да, бихме могли кода си всеки
от примерите, които имаме в ума.
Така че днес, ние не докосвайте клавиатурата за всяка форма на код.
Ще бъде много по-високо ниво, и в крайна сметка, за решаване на проблеми.
>> Така че, за да стигнем до този момент, нека да предложи че следните седем
правоъгълници представляват седем врати, зад които са цял куп
числа, сред които е и номер 50.
Позволете ми да проектира тази по този екран и тук.
И предлагам да се нуждаят от доброволци да помогне да ме намери редица пред
интернет тук, за да видите.
Ела, в розово.
Добре.
Как се казваш?
>> ДЖЕНИФЪР: [недоловим]
>> DAVID J. Malan: Моля?
>> ДЖЕНИФЪР: Дженифър.
>> DAVID J. Malan: Дженифър.
Добре, Дженифър.
Приятно ми е да се запознаем.
Хайде нагоре.
Така че тези тук са седем врати, и това, което Бих искал да направиш за нас тук,
пред всичките си съученици, ни намерите броя, 50.
За да намерите броя, можете да надникнем зад нито един от тези врати, като просто докосване
на една от вратите, и ще разкрие неговия номер.
И нека да видим колко бързо да ни намерите броя, 50.
>> 15.
16.
50.
Браво.
Добре.
Аплодисменти за Дженифър.
>> [APPLAUSE]
>> Добре.
Така че това, което е вашата стратегия за намиране на броя, 50?
>> ДЖЕНИФЪР: Хм, мислех, че може би, ако -
[Недоловим]
>> DAVID J. Malan: Oh.
Дай го секунда.
Така е вашата стратегия за намиране на броя, 50?
>> ДЖЕНИФЪР: Така че аз просто започне в започваме да виждаме това, което първият брой
е, и тогава си помислих, може би, ако те са подредени, просто ще запази
потупване по-нагоре?
>> DAVID J. Malan: OK.
И ние като че ли са намерили , че е така.
Въпреки че, нека да свали пластовете само малко, и искате да отидете
напред и разкриват други врати можеше да избереш?
>> Дженифър: О, боже.
>> DAVID J. Malan: Ah.
>> ДЖЕНИФЪР: Така че аз просто имам късмет.
>> DAVID J. Malan: Значи имаш късмет.
Добре.
Така че не е зле.
Но това е интересен поглед, нали?
Ако приема, а ти се получи, Наистина, малко късмет там.
Но ако се приеме, че цифрите са подредени, може ли да бъдем по-точни
за това как това влияе Вашето поведение?
>> ДЖЕНИФЪР: Така че, ако те са били подредени, I че може би най-малката до най-голямата.
>> DAVID J. Malan: OK.
>> ДЖЕНИФЪР: Или, ако това в крайна сметка е наистина голям, а след това най-голямата до най-малката.
>> DAVID J. Malan: OK.
Така че най-голямата до най-малката, или най-малките до най-големите.
Но нека да предложи да предположим, че сте имали намерила късмет, и предполагам, че те
не са, в действителност, сортирани, колко от тези врати може да ви се наложи да надникнем
зад това, че най-лошия случай?
>> ДЖЕНИФЪР: Всички от тях.
>> DAVID J. Malan: Всички от тях.
Така че нека да обобщим, че като п.
Там се случва да бъде 7, но нека по- обикновено казват има п врати на
екрана тук.
Така че в най-лошия случай, ще трябва да погледнем зад седем врати, или п врати.
И така, това наистина е, че е малко на късмет днес, но това е наистина линейна
алгоритъм на видове, въпреки че са вид прескочите наоколо.
Това честно ли е?
>> ДЖЕНИФЪР: Да.
>> DAVID J. Malan: Е, нека да видим дали си стратегически промени ако се преместя от нас да
вторият ни пример тук с 7 различни врати.
Същите номера, но това времето, когато те са подредени.
Каква е стратегията ви тук ще бъде, се опитва да изкара от ума си това, което
другите цифри са -
>> ДЖЕНИФЪР: OK.
>> DAVID J. Malan: - по-рано?
>> ДЖЕНИФЪР: Нека да започнем с първия.
>> DAVID J. Malan: Добре.
Започнете с първия.
4.
Сега къде ще отиде, и защо?
>> ДЖЕНИФЪР: 4 е наистина малка.
Така че, ако те са вид може би най-малката до най-големия, следва
двоен, и -.
>> DAVID J. Malan: OK.
Нека да видим, което мислиш?
>> ДЖЕНИФЪР: Опитайте последният.
Ница.
>> DAVID J. Malan: Много добре направено.
Добре.
>> [APPLAUSE]
>> DAVID J. Malan: OK.
Значи всъщност прави това ужасно, защото си
да го прави много добре.
Което ни оставя в състояние да се направят някои точки.
Така че, нека се опитаме да победим тук.
>> ДЖЕНИФЪР: OK.
>> DAVID J. Malan: Много добре направено, все пак.
Така че започна в началото, ти видя, че беше 4, а след това
се премества в края.
Но предполагам, че не си щастлив там, и предполагам 50
беше някъде другаде.
Какво ви Третата стъпка са били?
>> ДЖЕНИФЪР: Върни се в началото.
>> DAVID J. Malan: Върни се в началото.
ОК, така че ще съм трогнат тази врата, която е 8.
Добре.
Така че това не е 50.
Къде бихте изглеждала следващия?
>> ДЖЕНИФЪР: ако не знаят, че подредени.
>> DAVID J. Malan: Правилно.
Е, ако знаех са сортирани -
>> Дженифър: О, знаех, да.
>> DAVID J. Malan: - Но ти не Знам къде 50 беше още?
>> ДЖЕНИФЪР: Просто продължавай.
>> DAVID J. Malan: Добре.
OK.
Продължавай.
OK, за да мога да работя.
>> ДЖЕНИФЪР: OK.
>> DAVID J. Malan: Сега, ако ти си просто Ще продължа, какво е вашето
алгоритъм възложени подкрепени в.
>> ДЖЕНИФЪР: Линейната -.
>> DAVID J. Malan: Това е вид линейно.
Но нека да предложи, нека ме постави на място.
Позволете ми да обнови страницата.
същия номер, същия режим, същите врати.
Но мисля, че обратно към първия ден в клас, когато се откъсна телефонния указател в
половина, нещо, и това, което беше стратегията ни там?
>> ДЖЕНИФЪР: Започнете от средата.
>> DAVID J. Malan: OK.
Така започне в средата.
Така че да вървим напред и да се симулира това.
Започнете от центъра на разкрива, че вратата.
Така че номер 16.
И така, какво ще силния човек са направили, който откъсна телефонния указател на половина,
да стигнем до следващото предположение?
>> ДЖЕНИФЪР: Отиди в това полувреме.
>> DAVID J. Malan: И защо в дясно?
>> ДЖЕНИФЪР: Ако те бяха нещо като най-малката до най-големия, след това 50 трябва да бъде
в тази насока.
>> DAVID J. Malan: Добре.
Напълно разумно.
Така че, като телефонен указател, можете да отидете в право, за разлика от ляво, но тук
е от ключово значение за вкъщи.
Вие сега може да изхвърли, или да откъсне, половината от този проблем, оставяйки не сте
със седем врати, но наистина само с три.
Което е приблизително половината от размер на проблема.
Добре.
Така че сега това, което вие ще трябва извършва след отидеш нали?
>> ДЖЕНИФЪР: So 16 все още е доста малък, в сравнение с 50, така че може би ще се опитам,
подобни, тази.
>> DAVID J. Malan: Добре.
42.
Добре, така че сега какво е вашето инстинктът ви казва?
>> ДЖЕНИФЪР: Мога да изхвърлите това и след това просто -
>> DAVID J. Malan: OK.
Добър, можете да изхвърлите лявата половина има.
>> ДЖЕНИФЪР: - вземете тази.
>> DAVID J. Malan: И отдясно.
>> ДЖЕНИФЪР: Да.
>> DAVID J. Malan: Така че, въпреки че това е трудно , за да видите може би, когато има само
7 врати, мислим за това, сега, последователността на
алгоритъм просто прилага.
В предишния случай, нали късмет, което е страхотно.
Но ти се използват евристични, Бих казал.
Ти някак си инстинкти, и знаейки, че подредени, ако това е доста
малка в началото, очевидно, ние сме Трябва да вървя по-надясно.
Но в известен смисъл, имаш късмет, защото може би това е номер 100,
и може би 50 е повече в центъра.
Може би 50 е още тук.
>> Но това, което направи малко по-различно този път бе, ти направи същото
отново и отново.
И бих казал, че това, което току-що е, макар и повлиян от телефона
книга, например, е нещо много по- по алгоритмично, и много
по-малко специален двукорпусен.
Много по-малко инстинктивно.
Така че в края на деня, как ще описали ефективността на
първият алгоритъм, къде си ляво на дясно, срещу
втори алгоритъм тук?
>> ДЖЕНИФЪР: това трябва да, като, може би намаляване наполовина на времето, или дори повече, да.
>> DAVID J. Malan: OK, може би дори повече.
Да натиснете малко по-трудно от това.
Това, което наистина, ако продължим тази логика, ние определено намали наполовина
времето за работа с този втори алгоритъм от изхвърляне на половината от
номера, но това, което сме направили на следващия итерация, когато Дженифър разкри
второто число?
>> Ние наполовина броят на врати отново.
И тогава какво правим след това, ако имаше повече врати да играе с?
Ние ще ги намали наполовина, и отново, и отново, и отново.
И това беше точно като вас, момчета всички изправяне на първата седмица на
клас, половината от вас в седнало положение, половината на Седнал ли си, половината от вас
в седнало положение, докато един самотен душата стоеше.
И ние казахме, че времето за работа на че броя на стъпките, които се е
от порядъка на какво?
>> SPEAKER 1: [недоловим]
>> DAVID J. Malan: Така регистър база 2 на N, или просто по-просто, влезте от п.
Така че нещо логаритмична.
И графиката не е права линия че просто имам по-лошо и по-лошо, това е
тази интересна крива, която не се толкова зле с течение на времето.
Така че нека да се държа за тази идея.
Нека да благодарим на Дженифър.
Благодаря, че дойдохте нагоре.
И една секунда.
Не настолни лампи днес, но нужно CS50 стрес топки.
>> ДЖЕНИФЪР: Уау.
>> DAVID J. Malan: Добре, тук.
Благодаря ви за нанасянето на стреса тук.
Добре.
Така че нека да видим дали можем да не сега официално това малко повече.
И отново, това, което току-що направих, беше по същество едно и също нещо, както направихме
с това, че първата седмица.
Но вместо края само с линейна алгоритъм, който изобразена
преди това, тъй като това права линия, при което, ако сложим още една врата
екрана, след което ще Jennifer трябваше да изглежда, потенциално,
зад още една врата.
Ако сложим още две врати, тя може да има да погледнем зад още две врати.
>> И така, не е този линеен връзката между размера на
Проблемът на, да речем, на оста х и размера на времето, необходимо за
решаване на у.
Но картината I загатваше рано е тази зелена линия.
Green умишлено, защото тя просто се чувствам по-добре.
На теория, алгоритъм, когато го направихме с телефонния указател, когато го направихме
с вас, момчета преброяване един от друг, и Във втория случай, когато Дженифър просто
го е направил до тук, това беше нещо от фундаментално по-добре.
Тъй като това не е само два пъти по-бързо.
Той дори не е четири пъти по-бързо.
Това е изцяло зависима от това, което Размерът на входа е, за това колко
стъпките, които в крайна сметка взех.
>> И така, тази проста идея, че ние всички за даденост, с телефонния указател,
По същия начин може да се прилага за нещо подобно.
И това може да бъде по-небрежно известен като, когато имате възможност
си представим, разделяй и владей.
Не е за разлика от това, което направихме, разбира се, с телефонния указател.
>> Но pseudocode, изземване, е това.
Така че ние няма да го направя отново, но припомни, че първата седмица, всеки от нас се изправи
и след това половината от вас седна, половината от ти седна, половината от вас седна.
Този алгоритъм се реализира в малко на измама начин, с това, че е
е не само един от мен броене, фундаментално, по-ефективно.
В този случай, аз бях деблокирането вторичен ресурс.
Нещо, няколко процесора, множество мозъци, множество умни хора в
стая са ми помогна да получите от нещо линейна с нещо
логаритмична, от нещо червено с нещо зелено.
>> Но в този случай, Дженифър не може самостоятелно да фундаментално подобрява при
изпълнението на първия си алгоритъм от, отново, само като си помисля малко по-трудно.
И сега, когато дойде време за прилагане на тези неща, фигуриращ
какво реда код можете да пишете такива че можете да ги повтарям отново, и
отново, и отново, нещо в примка мода.
Защото няма да има лукс, като Дженифър направи в началото, за да
Просто трябва един куп ИС и да кажа, Хм, ако този първи брой е четири,
нека да скачат по целия път до края.
О, ако този брой е твърде голям, нека да се движат произволно назад
на втория елемент.
Ще откриете, че това ще бъде много по- по-трудно да се формализира това, което ние, хората,
приемаме за даденост, като много разумна евристични методи, а компютърът е само
Ще правя това, което му кажете да прави.
>> Сега това е много интересно последици.
Тази графика е вид означаваше някак да смаже визуално, но забележете, където
е права линия в тази графика?
Къде е линейна графика което ние наричаме п?
Е, това е нещо към дъното на тази снимка, нали?
Така че всичко, което направихме, ние сме нещо като приближение на х-ос и
ордината да се опита да се получи усещане за това, което други видове криви изглеждат.
>> И спецификата на математическото изрази днес няма да има значение, така
много, но забелязвам, че има много алгоритми, които са далеч по-лошо от
нещо, което е линейна.
Наистина, нарязани на кубчета п изглежда доста зле.
2 до п изглежда доста зле. N квадрат изглежда доста зле.
И ще видим какво някои от тези може да бъде в действителност днес.
И влезте п не се чувства толкова зле, но по-добре от п е регистър на основата 2 п.
Но знаете ли, това щеше да бъде още по-невероятно, ако Дженифър, или ако ние,
че първата седмица, е дошъл с нещо, което е регистър на дневника на п.
>> Така че с други думи, има цялата тази спектър от възможни решения
проблеми, но дори и тук, бележка какво ще се случи.
Когато намалявате, кои от тези криви ще се окаже абсолютната
най-лошото от тези, на екрана в момента?
Така п куб изглежда доста зле в момента.
Но ако се увеличи, за да видите повече от X и Y-ос, който ще
доминират в крайна сметка?
Така че всъщност Оказва се, че 2 към N, и можете да разбера това само като
включване на някои все големи номера, и ще видите, че 2 към
п, наистина, стане по-голям много по-бързо.
Ако наистина отдалечаване, на 2 до N алгоритъм абсолютно гадно.
Искам да кажа, че това ще се доста малко време за
компютъра, за да бълват сам.
>> Но ще видите, с течение на времето, особено с бъдещите комплекти проблем и дори
окончателните проекти, е вашите данни набор стане голям, нали?
Дори и в първата версия на Facebook, тъй като броят на приятели, и
Броят на регистрираните потребители има голям, можете да сортирате на телефона го и
изпълнение нещо, с линейна търсене, или много прост сортиране
алгоритъм, както ще видим днес.
Трябва да започнем да мислим по-трудно и по-трудно за тези проблеми.
И вида проблеми места като Facebook и Google, и Microsoft,
а други работят по точно тези нещо като голямо количество от данни вид въпроси
все по-често тези дни.
>> Добре.
Така че успех на Дженифър в тази секунда алгоритъм, честно казано, тя направи невероятно
и за първи път, но нека напишете го като късмет, за да можем
може да направи тази точка.
Във втория случай, тя е отнесена алгоритъм, който повтаря отново и
отново, но тя взе за даденост, а някои предположението, че ние право
, но тя използва някои подробности втори път, че тя не е имала
първи път.
Което е какво?
>> Че списъкът е сортиран.
Така че веднага след като списъкът е сортирана, ние твърдят, че Дженифър е в състояние да направи
фундаментално по-добре.
7 врати, да, не е толкова интересно, но предполагам, че сме 7 милиона врати.
Вход на п определено ще да изпълнява много, много
по-бързо в дългосрочен план.
Но тя трябваше да има врати подредени за нея.
Сега, аз си позволих да правиш това предварително на екрана на компютъра
тук, но предполагам, че Jennifer Трябваше да го направя сама?
Да предположим, че вратите въпросните представени данни в база данни или
приятели, регистрирани за Facebook, или всички уеб страници в интернет, които
различни сайтове, може да се наложи за индексиране или търсене в над.
>> Да предположим, че просто трябваше необработени данни определени и се оставя на вас, или да
Jennifer да направя, че сортирането?
Това по-скоро изисква да отговоря въпросът, добре, колко време
би взел Дженифър, или дори мен, да подреди тези цифри предварително, така
че тя може да се възползва от това?
Така ли е?
Тъй като косвено, разбира се, е ако това ми отнема доста време да се справи
цифрите, които, по дяволите, му пука, че сте да намерите редица като 50 толкова бързо,
като в случай на Дженифър, ако повече от претоварени размера на общото време
го хвана сортиране неща предварително?
>> Така че нека да видим дали не можем да на нарисува картина тук.
Имам цял куп повече стрес топки, ако това помага
разчупване на леда тук.
И ако не би имал нищо против, ние трябва седем доброволци -
на, OK.
Wow.
Така че не е нужно да прекарват на настолни лампи, както изглежда.
Добре.
Така че как за две отпред.
Какво ще кажете вие ​​двамата отзад.
Така че това е четири.
Какво ще кажете вие ​​пред пет, шест и седем.
Точно там.
Приятелят ти те посочи, така че да получите награда.
>> Добре.
Хайде нагоре.
И защо не трябва момчета, ела тук.
Аз ще ви дам един номер.
И давай напред и сами организира идентично с това, което е
изобразени на екрана.
>> [Вмъкване VOICES]
>> DAVID J. Malan: Oop, съжалявам.
Bug.
Добре.
Е, ето.
Номер пет.
Номер шест.
Едно, две, три, четири, пет, шест, седем.
О, това е неудобно.
>> SPEAKER 2: Просто ще се получи -.
>> DAVID J. Malan: добра сделка.
Добре.
Благодаря ви за участието.
>> [APPLAUSE]
>> OK.
Добре.
Така че ние имаме четири, две, шест, един, три, седем, пет.
Идеален, така че ние имаме седем доброволци тук, които са равни по ширина до
масив, който ние играем с по-рано.
И аз избрах седем причини това ще бъде само
разположен в малко.
И аз отивам да предложи първо, че ние сортирате тези седем доброволци.
Ако искате, първо, да кажа здрасти все пак.
Тъй като това ще бъде неудобни няколко минути.
Въвеждане на себе си.
>> GRACE: Здравейте, аз съм Грейс.
Аз съм второкурсник в Leverett House.
>> Брансън: Hi.
Аз съм Брансън.
Аз съм първокурсник в Weld.
>> GABE: Hi.
Аз съм Гейб.
Аз съм младши в Cabot.
>> Нийл: Аз съм Нийл.
Аз съм първокурсник в Matthews.
>> JASON: Аз съм Джейсън.
Аз съм първокурсник в Greenough.
>> MIKE: Аз съм Майк.
Аз съм първокурсник в Grays.
>> ДЖЕС: Аз съм Джес.
Аз съм второкурсник в Leverett.
>> DAVID J. Malan: отлично.
Добре.
Е, благодаря на всички наши доброволци тук, до този момент.
И предизвикателството под ръка сега ще за да се справи с тези момчета, но след това
ние ще трябва да се мисли малко трудно за това как ефективно ние всъщност
сортирани тях.
Така че нека първо да се опита това.
Вие може да виждате взаимно номера просто чрез поставяне на около ъглите.
Давай напред и да отнеме няколко секунди, и подреди сами от малкото на
оставено на най-голямата в дясно.
Go.
>> OK.
Добре.
Това беше наистина дяволски бързо.
Сега някой тук, каква е алгоритъм че тези момчета се приложи?
>> SPEAKER 1: поне най-голямо.
>> DAVID J. Malan: OK.
Най-малкото да е наистина нещо като цел, но аз не съм сигурен, че е
наистина алгоритъм.
Най-малкото да не кажа ми стъпка по стъпка какво да правя.
Да?
>> SPEAKER 1: [недоловим]
>> DAVID J. Malan: OK.
Така че, ако видите човек по-малък от си номер, след това преминете към
правото на тях.
Така че това е сега получават по-изразителен, по-скоро като един алгоритъм, защото
може да се каже, ако това, тогава това.
Така че ние имаме някакъв вид условно конструкция.
И тези момчета изглежда да се направи, че няколко пъти, защото някои от вас преместили малко
на въздух.
Така че е вероятно някои видове примка случва в съзнанието им.
>> Но нека се опитаме да формализира това.
Ако вие може да възстановите обратно към настоящата договореност.
Да видим дали не можем официално това на малко, и след това се зададе въпросът, просто
колко ефективно е това?
Разбира се, когато правим това по-бавно, то се случва да се чувствам толкова добре на
алгоритъм, но нека да видим дали можем да с пръстите си за точните стъпки.
>> Значи вие двамата са четири и две.
Или можете правилен или неправилен ред?
Очевидно е неправилно.
Така че ние разменят.
Сега аз ще се отмести тук и да кажа, 5:56.
Добре ли правилен или неправилен?
>> GABE: Правилно.
>> DAVID J. Malan: Правилно.
Шест и една?
Не.
Разменени.
Така че това е два суапове.
Шест и три?
Не.
Разменени.
Шест и седем?
Изглежда добре.
Седем и пет?
>> ДЖЕС: [недоловим]
>> DAVID J. Malan: OK, суап.
И сортирани.
Добре.
Така че не очевидно, нали?
Така че там е по-става.
Но, наистина, тези момчета, дори просто инстинктивно.
продължаваше да се движи.
Те не просто спрете, след като те коригирани един проблем.
Така.
Всъщност, аз ще трябва да направи същото нещо.
Ще трябва някак да се върна назад в началото на този проблем,
или в началото на тази гама хората, да започнем да ги вика.
>> И сега какво трябва да ми алгоритъм на втория пас бъде?
>> SPEAKER 1: Същото нещо.
>> DAVID J. Malan: Същото нещо.
И това, аз съм се започне да се харесва, нали?
Веднага след като можете да откриете себе си правиш едно и също нещо отново и отново, че е
все повече като един алгоритъм, и по-малко човешки инстинкт.
>> Така че сега, ето ни отново.
Две и четири?
Не.
Четири и един?
Ах, действително е имало някои работят все още да се направи.
За и три?
Добре.
Четири и шест?
Шест и пет?
Шест и седем?
Добре, сега, направи.
OK, не.
Аз трябва да се върна.
>> Така че сега, отново, че правим това малко по-бавно.
И сега, има само един мозък изпълнението на този алгоритъм.
Един CPU, ако щете.
И честно казано, това е единственият ресурс, ние ще имаме достъп.
И след като ние се върнем към клавиатура и има нещо като C в нашия
разположение, ние сме само за написването на програмата който може да направи едно нещо в даден момент.
Като има предвид, тези момчета преди малко, ние ливъридж колективната си интелекта
като вас, момчета направиха в седмицата нула.
Така че нека да продължаваме така.
>> Две и една.
Две и три.
Три и четири.
Четири и пет.
Пет и шест.
Шест и седем.
Съставено?
Така че аз съм, но нека играе застъпник на погрешна кауза.
Трябва ли, нещо като компютър, който просто направи атака през тази гама
хора, знаете, че аз съм направил?
>> SPEAKER 1: Не.
>> DAVID J. Malan: Така че, защо?
Какво ще трябва да направя, за да се сключва решително, че аз съм направил?
Вероятно още един пропуск.
Така ли е?
Защото всичко, което знам, че от предишния подаване е, че аз коригира грешка.
А това означава, може би има още една грешка
че трябва да се коригира.
Така че може да бъдете сигурни само от пренавиване и след проверка, 01:59, две и
три, три и четири, четири и пет, пет и шест, шест и седем.
Добре, сега аз направих никаква работа.
>> Със сигурност мога да помня, че съм направил не работи с нещо като променлива,
като едно цяло число.
Наречете го суапове, суапове и ако е 0 след I стигна до тук, и започна на 0, след което
Аз просто ще бъде глупаво да продължава напред назад и напред, като се проверяват отново, и
отново, и отново, нали?
Тъй като се заби в някои вид на безкраен цикъл.
Така че веднага щом има 0 суапове, можем да твърдим, че това
алгоритъм е наистина пълна.
>> Сега, нека да сложи името на това.
Алгоритъмът, че ние предлагаме само изпълнена, е нещо, наречено балон
вид, известен като такъв в смисъл, че номерата, които са по-големи вид
балон пътя си до върха, или до към края на масив от числа.
Но колко ефективно е този алгоритъм?
Колко стъпки съм физически трябва да Вземете например, да подреди тези
седем човека?
>> Четири до пет?
OK, твърде много, в крайна сметка е ще бъде отговорът.
Но дори и тогава, на определен брой не е толкова интересно.
Нека обобщим това като п.
Така че, ако бях п хората тук, и те бяха, нещо, в произволен ред в
началото, че в първоначалния ред.
Е, колко стъпки имах да вземе на първия пас?
Това е един, два, три, четири, пет, шест, а те са седем души, така че
това е седем, шест -, така че това е п минус един стъпки за първи път.
>> Сега, колко стъпки имах да се предприемат, когато аз пренавит?
Е, ние в действителност може да удвои, че ако ние наистина искахме да, но за сега, аз съм
Само ще кажа, добре, друга п минус 1.
Така че п минус 1 ще се получи, досадно, за да следите, така че нека
точно зад леко.
Така 2n стъпки.
Така 14 стъпки, или да се даде.
>> Колко пъти съм се стъпка следващия път?
Е, това е 3n.
наистина.
И сега, в най-лошия случай, за Например, колко пъти съм искал да
отиде назад и напред, назад и напред, изпълнението на този алгоритъм, смяна
хора на всяко преминаване, грубо?
Всъщност е п квадрат, нали?
>> Защото в най-лошия случай, можете да вид от мислите за това интуитивно,
въпреки че може да отнеме малко малко време, за да потънат инча
В най-лошия случай, какво би те седем души са изглеждаше, в
условията на споразумението на техния брой?
Напълно назад, нали?
И само да се симулира, че как ти беше името?
>> MIKE: Mike.
>> DAVID J. Malan: Майк?
OK, Майк, можеш просто да се присъедините към мен през тук само за една секунда?
Всъщност, не.
Съжаляваме Mike, назад нека.
Какъв ти е името?
>> НИЙЛ: Нийл.
>> DAVID J. Malan: Нийл.
OK, Нийл, ти идваш с мен, ако нямате нищо против.
Така че аз ще да предложи, само за простота, че Neil сега е в неговата
възможно най-лошия случай.
Но припомни как се прилагат ми алгоритъм.
Аз съм сравняване, сравняване, като се сравняват сравнение, сравняване, о.
Сега тези хора са навън на ред, така че аз се определи.
Така че вие ​​сменяте.
Но помислете сега, колко по-далеч Neil се наложи да отидете?
Това е грубо п.
Знаеш ли, това всъщност не е п.
Това е като, п минус 1, но аз съм се раздразнен следене на малката
номер, така че нека просто го наречем п.
>> Така че, ако Neil премества една стъпка максимално всеки време, и да се движат Neil една стъпка,
Трябва да направя това наистина досаден пас назад и напред, това е грубо
правят това, N стъпки, общо пъти N, защото тя ще ме вземе
че много стъпки, за да получите Neil всички Между другото там, където му е мястото.
Да не говорим, всички останали, ако вие Всички бяха погрешно подредени, както добре.
>> Така че, нека го наречем балон подреди N квадрат.
По време на работа на този алгоритъм, на изпълнение на този алгоритъм, на
Ефективността на този алгоритъм, ние трябва просто да опише по-
общо като п квадрат.
Което е хубаво, защото може да направи същия пример с осем души, девет
души, един милион души, както и че Отговорът няма да се промени.
>> Така че, ако вие не би имал нищо против, нека да изчисти ли до мястото, където сте започнали.
И нека се опитаме две други подходи и видим дали не можем да направим фундаментално
по-добро от това.
Така че този път, аз отивам да предложи един вид различен алгоритъм.
Това беше много умно от нас последния път, и бяхте правото да поиска
правилните инстинкти на просто вид на смяна по двойки.
Но ако наистина исках да се подходи към този просто, и моята цел е да се движи
всички от малките номера по този начин, и бутнете всички големи числа, които
начин, защо да не го направя в най-наивен начин е възможно и да видим дали I
може да направи по-добре от това, което беше доста сложен алгоритъм?
>> Така че нека да видим.
Четири е доста малко на брой, така че аз съм Ще те оставя там момента.
О, номер две е още по-добре.
Така че може просто да излязат напред за момент?
В момента това е най-малката ми номериран кандидат, и аз отивам да се помни,
че с нещо като променлива.
Но аз ще продължа да проверявам.
Има ли някой, чието брой е по-малък?
Six, не.
О, има Нийл отново.
>> Така че аз ще ви оттласнем вид концептуално.
Neil ще излезе.
И сега, променливата, че аз съм с помощта на следите, които има най-малък
Номерът се актуализира, за да съдържат Нийл място.
Е, нека да видим.
Три, седем, пет.
ОК, знам, Нийл беше най-малкият.
Какво е най-простото нещо за мен да направя сега?
Нямам намерение да си губя времето, като просто бълбука Neil едно място наляво.
Защо да не съм сложил Neil където той принадлежи, което, разбира се, къде?
>> Чак в началото.
Така Нийл, ела с мен.
И какво ти беше името?
>> GRACE: Grace.
>> DAVID J. Malan: Grace.
OK.
Така Grace, за съжаление, ти си вид на пътя.
И как ще се реши този проблем?
Така ли е?
Ако това е масив, има само седем места.
Спомнете си, че с Роб, ние говорихме за обявяване възрасти, и имахме само един
краен брой възрасти?
Същата идея тук.
Ние имаме само краен брой цели числа.
Грейс е вид в нашия начин, така че как ще се оправиш?
>> Най-простият начин е като, Грейс, съжалявам.
Вие ще трябва да разясни няма да можем да направим място.
Сега, ако мислите, че за това, може би ние просто влошил проблема.
И може би сме направили, защото това, което, ако Grace са на мястото си?
Но ние знаем, че не е, защото В противен случай тя би била
права напред, вместо да Neil по това време, нали?
Ние вече си погледна броя навън.
>> Добре.
Така че сега, Нийл е на мястото си, и Мога да го направя леко оптимизация.
За следващата минута, аз отивам да се игнорира Neil всички заедно, така че да не
си губи времето, или случайно сменяте го на грешното място.
Така че сега, как да намерите следващия елемент, който е най-малката?
Two.
Това е доста добър брой, ако искате да излязат напред и
Ще се сетите.
Шест, не е добре.
Четири, три, седем, пет, не е добре.
Затова ми позволете да продължа да си правилното място.
И ние просто имам късмет този път.
>> Сега, аз отивам да се игнорира тези две момчета, а сега направи още една
мине през това.
Six, че доста малко на брой.
Хайде напред.
О, съжалявам.
Броя на Грейс е по-добре, така стъпка по напред.
Четири.
Съжаляваме, Грейс.
Върнете се отново.
Номер три е по-добре.
Seven.
Five.
И сега това, което ти беше името?
>> JASON: Jason.
>> DAVID J. Malan: Jason.
Така че Джейсън вече е най-малката елемент съм избран.
Къде отива да отидете?
Е, къде е шест.
И името ти е отново?
>> GABE: Гейб.
>> DAVID J. Malan: Гейб.
Гейб е в пътя.
Какво е най-лесното нещо да направите?
Разменени тези две момчета и да продължите.
Така че сега да видим.
Кой е най-малък?
Четири.
Нека просто вид измама.
Five ще бъде най-малкият.
Да намеря следващия, ако искате да се оттегли напред, какво трябва да направя с
тези момчета, с Гейб?
Разменени отново.
Така че сега, все още е малко на ред.
Намерени Габе да бъде най-малкото, за да Казах му, поп, движи ви момчета свърши.
И направи.
>> Така че отговорът е един и същ.
Крайният резултат е един и същ.
Кой от тези два алгоритъма е по-добре?
Вторият, чух.
Защо?
>> SPEAKER 3: това е п стъпки [недоловим].
>> DAVID J. Malan: Това е н стъпките на най-много.
Интересно.
Така че това е все пак?
И така, как да намеря малкият елемент?
Колко стъпки е, че трябва да се на най-малкия общ елемент?
Имах поглед целия път в края, нали?
Поради това, че най-лошия случай, това, което Neil ако бяха тук?
Така че просто намери най-малкият елемент ми отнема N стъпки, или п минус 1.
Но, OK.
Така определи Нийл.
Не забравяйте, че една минута или така преди.
>> Но как да намеря следващия малкият елемент?
Това е п минус 1, или п минус 2 наистина, от броя на стъпките.
Така OK.
Така че аз съм п минус 2.
Добре.
Така, че се чувства малко по-добре.
Добре.
Колко стъпки следващия път да намерите номер три?
Така п минус 4.
Така че това е намаляване, една по-малко стъпите на всяка итерация.
Така че това се чувстват по-добре, нали?
Ако последния път беше грубо N пъти N, този път е п минус 1, плюс п минус
2, както и п минус 3, плюс п минус четири, точка, точка, точка.
Но ако си спомняш от гимназията учебници, малката мамят
лист на гърба че има формули, ако съберете тази поредица от числа,
Какъв е общият брой стъпки ще бъде, че аз се тук?
>> Това е един от тези, които, като, N минус 1, п пъти, разделена на две.
Така че нека да видим дали мога да дръпнете това се само за миг.
И отново, аз съм вид на закръгляване някои номера само за да поддържат живота ни прости,
но доколкото си спомням, това е нещо като, ако Правя п минус едно неща, тогава п минус
2, след N минус 3, това е грубо нещо като това над 2, и ако
умножете това, че е всъщност н квадрат.
Това не се чувства много добре. N минус N над 2.
>> Но тук е нещо.
В компютърните науки, когато проблемите започват да се интересно е, когато п
стане наистина голям.
И когато п стане наистина голям, което на тези стойности ще доминират всички
на другите?
Това е вид на п квадрат, нали?
Да, се дели на две е доста добър.
Но ако говорим за милиарди на парчета от данни или трилиони
парчета на данни, ОК, така че ти си два пъти по-бързо.
Но кой наистина му пука, ако толкова голям брой, ако този фактор е това, което получава
по-големи и по-големи.
И със сигурност, че има повече от разлика от този човек.
И въпреки, че вие ​​сте прав, втори алгоритъм, ние ще го наричаме
избор сортиране, е, в реалния свят, а малко по-бързо потенциално, защото аз съм
като все по-малко стъпки при всеки.
>> Това не е наистина фундаментално по-бързо.
Защото, ако ние всъщност играе това за големи стойности на N, в края на
на ден, за достатъчно голям, N, тя все още е ще се чувстват доста бавен.
Е, нека да бъде в една последния пас в това.
Това е, което аз бих нарекъл избор подреди.
Можете ли себе си изчисти за последен път?
И в този последен случай, аз ще да предложи нещо
нарича вмъкване вид.
Insertion вид е, концептуално, малко по-различно.
>> Вместо да се върви напред и назад и изберете най-малкият елемент, аз съм
Просто ще се справят с всяка една от тези момчета, тъй като аз попаднали на тях, и поставете
тях в правилното им място.
Така че аз съм просто ще започнем с Грейс, и виждам, че тя е номер четири.
Къде номер четири принадлежат?
Аз не са започнали сортиране нищо, така Grace получава да останем там.
И сега аз отивам да претендира, ако може предприеме стъпка в дясно, това
ми сортиран списък, това е моят несортиран останалата част от списъка.
Така че сега аз отивам да продължите нататък, и какво ти беше името?
>> Брансън: Брансън.
>> DAVID J. Malan: Брансън.
Така че Брансън е номер две.
Така че аз ще те заведа излезете за малко.
А сега, къде ти е мястото в този масив?
Така правото на Грейс.
Така че отново, ние сме вид вземане Grace направи много работа тук.
Къде ще ви постави?
Така че ние ще ви се плъзга към наляво, и го поставете Branson там.
Но сега твърдят, че момчета са готови.
Но забележете, аз не съм с допълнително пространство.
Тя все още е два елемента Оттук 5 тук.
Общ размер на масива е 7, така че аз съм не изневерява, нали?
>> Така че сега ние имаме, с Gabe тук, на номер шест, къде ти е мястото?
Имаш късмет отново.
Така че можете да останем там.
Просто отделете лека стъпка в дясно само за да стане ясно, че сте подредени.
И сега имаме Нийл отново, брой един, къде отиваш?
И сега е мястото, където ние ще започнем да виждаме, че този алгоритъм, че на първо
поглед, се чувства доста интелигентен, гледай това, което е на път да се случи.
Ако можеше да излезе напред.
>> Къде искаме да се сложи Нийл?
Така че очевидно тук, така че как ще стигнем Neil там?
Да го направим стъпка по стъпка.
Гейб, къде трябва да отида?
Да, така да бъде в една голяма крачка, или две половинки стъпки, за да
една стъпка там.
Грейс, къде отиваш?
Добре.
Така че още една стъпка.
И накрая, Branson?
Друга стъпка.
И сега можем да сложим Neil на място.
>> Така че сега, да продължи тази логика.
Макар и да не се изместват Neil над, и отново, и отново, за да го сложи
къде отива, в най-лошия случай, следващия брой ние може да срещнете
е броят, да речем, има редица нула, а след това ние ще измести всички
тези момчета.
Да предположим, че има номер, отрицателно един, тогава ние трябва да се пренасочат
всички тези момчета.
Така че наистина сме просто вид на обръщане проблема наоколо, така че ние сме
прехвърляне на разходи от процеса на подбор, така включването
процес, така че вие ​​просто трябваше да се движи приблизително N минус нещо
брой стъпки.
И това редица стъпки само ще да се увеличи, както аз изберете повече номера,
ако трябва да се запази блъскане момчета обратно, и обратно, и обратно.
>> Така че тъжно нещо сега е всички тези алгоритми са п квадрат.
Да вървим напред и благодарение на тези момчета, и визуализира тези малко
по различен начин.
Много добре направено.
>> [APPLAUSE]
>> Добре.
Ето.
Благодаря за -
>> Брансън: [недоловим] запазите номера.
>> DAVID J. Malan: Не, Вие може да запази номера, както добре.
Добре.
Браво.
Добре.
Така че нека да видим дали не можем да обобщим сега по-бързо и по-визуално,
точно това, което се случи Тук, както следва.
Отивам да вървим напред и издърпайте нагоре Firefox.
Ние ще свързват тази демонстрация на интернет страницата на курса.
Java е малко досадно да се работи На някои браузъри тези дни.
Така че, ако си играят с това у дома, Разбирам, че може да се наложи да използвате Firefox
да го работи.
И това, което ще направя с този демонстрация е следната.
>> В долната част, имам цял куп опции на менюто, включително началото и
стоп.
Също така, като настрана, изглежда, че е бъг в тези програми, за да
действителност не може да съвпадне с началото или да спре Ако не държите бутона Command или Alt
плюс и увеличавате, които любопитно ви показва повече бутони.
Така че просто FYI ако играете с това у дома.
Сега отивам да щракнете върху Start, само за момент, след уточняване закъснение,
подобни, 200 милисекунди тук, просто за да можем да видим какво ще стане.
>> Така че аз твърдя, че това е визуализация на първия алгоритъм
тези момчета е, балон вид, при което заменихме хора по двойки.
Ключът усет за визуализация е, че височината на прътите
представлява размера на брой.
Така че по-високият на бара, увеличаването на броя.
Shorter бара, по-малки номера.
И ако забележите, отиваме чрез първата итерация на този алгоритъм,
смяна на големи и малки номера, така че малкия брой е на първо място и
големия брой върви надясно.
>> И веднага след като стигнем края на масива на много повече от седем цифри, ние сме
Ще се върнем към началото.
И предвиждат това.
Най-вляво, че малкото момче става за размяна на страната, а това
процесът се повтаря.
Сега тази визуализация бързо получава скучно, така че нека да вървим напред и да се спре
го, променете нещо много закъснение по-бързо, само за да получите сега, усещане за
този алгоритъм.
>> И въпреки, че съм го ускори, това е като модернизация моя процесор, закупуване
нов компютър.
Не са променили основно ми алгоритъм, но наистина може да получите повече
ясно, отколкото с хора, че голяма номера се надига в началото,
и малките номера са бълбука надолу към дъното.
И сега това нещо тук подредени.
И като настрана, по площадите, има само някои счетоводство там, за да
да ви помогне да преброите колко сравнения, или колко замените
всъщност е направено.
>> Е, нека се опитаме един от другите видяхме.
Позволете ми да кликнете върху балон подреди тук, и Искам да си избера, и цялата тази уеб страница
е малко бъгав.
Нека приемем риска и да го стартирате отново.
Ето.
Така че нека да направим избор подреди.
Не знам защо в менюто се появява там.
Да се ​​увеличи за да се определи, че бъг, промените това на 50.
Ах, нека всъщност правят че много по-бързо.
Пет милисекунди, или така, както и започна.
>> Така че това е избор на вид.
Така че, отново, мисля за това, което ние направихме с хората тук.
Минахме през масива и избрани най-малкия елемент отново
и отново, и отново.
Сега твърдят, че все още е доста зле.
Тя е все още п квадрат, или да се даде, но това беше, в реалния свят, малко
по-бързо, защото бях наистина предприемат малко по-малко стъпки всеки път.
Но ние сме само говори какво?
Може би 40 или така барове тук?
Ние не говорим 40 милиона.
Така че това не е напълно ясно за мен, че наистина е значителна печалба.
>> Позволете ми сега да се върна и да се промени в нашия трета алгоритъм, който е изберете
вмъкване вид.
И сега това е наистина бъги защото меню, наистина не трябва да бъде там.
Така че сега ние ще превъртите обратно тук и да започне този алгоритъм.
Whoop, пускане и спиране.
Така че това един вид е доста модел към него, с което ние сме отново
вкарване на хора, или в този случай бара в
правилното им място.
И това вече е направено преди Обърнах се.
Но това също на теория, все още п квадрат.
>> Така че нека да видим дали не можем да обобщим тях, както следва.
Аз ще отида напред и само за да дам ни нещо като общ начин на говорене
за тези неща, нека представим малко на нотация тук.
Вие сте на път да се види нещо, наречено голям О, защото е буквално голям
O. И това е начин, че един компютър учен или математик дори използва
да опише времето за работа на някои алгоритъм.
Колко стъпки пък всъщност взема?
>> Сега аз ще се излагам с почерка ми тук, в един момент.
Но нека да вървим напред и да кажа, че това ще бъде голяма O тук.
И нека представим една друга символ, столица омега.
Омега ще бъде точно обратното, по същество, на голям O. като има предвид големия O
средства, в най-лошия случай, колко време може някои алгоритъм се, в
отношение на N, омега ще се колко време може
предприеме в най-добрия случай.
И ще видим какво имаме предвид под най-добрия случай само за един миг.
>> Така че нека да започнем нещо по-просто.
Позволете ми да започна с линеен търсене.
Така че не сортирането.
Ще наричаме този линеен търсене.
И сега, направи малко таблицата от това.
И сега, в случай на линейно търсене, в най-лошия случай, колко стъпки е
това ще ми отнеме да се намери броя на произволно място?
И има п общо врати или п общия брой.
Най-лошия случай.
Колко стъпки съм аз ще трябва да предприеме, за да намерите номера 50 в масив
врати, п?
И защо?
Защото тя може да бъде през цялото начин над към края.
Толкова много, като Jennifer срещат, на номер 50 е целия път, така че в
най-лошия случай линейно търсене е голяма O М, ще кажем.
>> Ами най-добрия случай, ако получите наистина късмет?
Той просто ще вземе една стъпка, или постоянен брой стъпки.
Така че ние ще опишем, че като един.
Така че това е доста добър.
Сега какво, ако сме направили нещо като двоично търсене?
Така двоично търсене, в най-лошия случай се колко време?
>> [Вмъкване VOICES]
>> DAVID J. Malan: Значи всъщност, Чух, че в няколко места.
Така че това е всъщност влезте N, или да се даде, тъй като ние разделяме списък на половина
отново, и отново, и отново, ние сме в състояние да се намери, в крайна сметка, на стойност,
ако я има, но има и уловка.
Какво е предположението, че ние трябва да приемаме за даденост, за двоично търсене?
Тя трябва да бъде разрешен.
Това не е сортирана, можете да разделите на нещо в половината отново и отново, и вие
може да отиде наляво, и можете да отидете надясно и можете да отидете наляво и надясно, но ти си
Няма да намерите елемент, ако Списъкът не е сортирана, защото
можете да го пропуснете.
Защото си евристичен, за да отида наляво или надясно, ще бъде опорочено, ако това е
наистина не са сортирани.
Така че има нещо като скрит разход да се използва нещо като това.
>> Сега, нека да отидат в нашата сортиране алгоритми не търсите -
О, всъщност да вървим в тази празна.
Binary търсене в най-добрия случай?
Това е също един, ако тя просто се случва да бъде в самия центъра на масива, или
средата на телефонния указател.
Сега нека да направим балон подреди.
Така че отново, сега навлизаме в видове, а не на търсения.
>> В най-лошия случай, колко стъпки е ние подреди претенция балон ще отнеме?
N на квадрат.
Така че аз ще да изготви това.
О, моят почерк изглежда още по-зле когато се очаква, че голяма.
Добре.
Така че това е п квадрат.
И в най-добрия случай на балон вид, колко стъпки е тя ще отнеме?
1, чух.
>> SPEAKER 1: п.
>> DAVID J. Malan: N, чух.
>> SPEAKER 1: 2.
>> DAVID J. Malan: 2, чух.
Чувам ли 3?
Добре.
Така че аз съм чувал 1, п, 2, но нека да вземете Освен най-малко първият от тези
предложения, 1.
Той не е лош инстинкт, защото вид следва модел тук.
Но ако тя отнема само една стъпка, как в светът може ли да претендирам, че списъкът
се сортира, защото ако аз съм само право да вземе една стъпка, колко елементи
бих могъл да се провери действително да бъде сигурен?
Е, само един, което означава, че има п минус 1 елементи, които биха могли да бъдат изложени на
ред, а аз съм просто ще на вярата след погледнете в един елемент, че
нещо, което се сортира.
Така че едно е да не коригира тук.
Така минимално, колко трябва ли да гледам?
>> [Вмъкване VOICES]
>> DAVID J. Malan: N минус 1, или наистина, п, защото аз трябва да разгледаме всеки
елемент, за да се уверите, че това не е в ред.
Но отново, ние ще сортирате на вълна ни ръцете на по-малките номера и
приемем, че, като п получава голяма, те са безинтересно или иначе.
Така че това е балон подреди.
А сега, нека да направим тези последните две.
Избор на вид, и след това ще направи сортиране вмъкване.
И тогава ние ще ти пръсна съзнанието с нещо много по-
по-добре от всичко това.
Добре.
>> Какво е най-лошия случай работи момента на избора вид?
>> SPEAKER 4: N квадрат.
>> DAVID J. Malan: N квадрат, което чувам.
Но защо п квадрат, интуитивно?
>> SPEAKER 4: Защото ние просто го направих.
>> DAVID J. Malan: Защото ние просто го направих.
OK.
Добър отговор.
Но интуитивно, защо е избор подреди N квадрат?
Какво трябва да направим отново и отново?
Ние трябваше да се запази чрез сканиране, са Вие най-малкото, че Вие сте
малката, вие сте най-малкият.
И отпуснати, ние бяхме в състояние да се п стъпки, след това N минус 1, а след това N минус 2.
Но ако нещо добавите онези, всичко, или да го вземат на вярата, че сте добавили
тях в аванс, получаваме около п квадрат минус някои по-малки номера.
Така че аз ще се обадя на този п квадрат.
Но с избора подреди по най-добрия случай, колко стъпки е
ще ме вземе?
>> SPEAKER 5: [недоловим]
>> DAVID J. Malan: Това е за съжаление още п квадрат, нали?
Защото, ако аз съм избора на най-малката елемент, и имахме седем души тук,
Аз знам само, след като стигна до много края, че аз открих най-малките
номер, той или където и тя може да е била.
Но как мога да намеря следващия малкият брой?
Трябва да направя още един пропуск.
Така че в най-добрия случай, това, което е вход за избор на вид?
Това е вече вид списък, номер едно, номер две, номер три, номер четири.
Но аз съм на компютър.
Мога само да погледнете един нещо в даден момент.
Не мога някак да предприеме стъпка обратно като човек и да кажа,
ох, това изглежда правилно.
>> Мога само да се произнесе коректност в избор подреди по избор на
малкото число.
Но дори и ако намеря номер едно първо, ако аз не знам нищо друго за
другите цифри, които аз не, всичко, което Знам, че съм подаде масив
или набор от врати, зад които са номера, единственият начин Знам, че един
е най-малката?
Ако получа чак тук и осъзнавам, По дяволите, един наистина е най-малък.
>> Но как мога след това да определи, че две е следващата по-малка?
По този същия неефективност отново и отново.
Така че най-накрая, с вмъкване вид, как, в най-лошия случай,
казахме го изпълнява?
Тя също е М квадрат.
А какво ще кажеш с най-добрия случай?
Ще оставим това за Катерачът.
Ще попълнете че празен следващия път, но първо нека да предложи, че ние
основно и по-добре всичко това, нали?
>> Така че мисля за себе си това, което вмъкване подреди ще бъде.
Е, това не беше много драматична, защото аз съм единственият,
който е видял промяната.
Wow.
OK.
Така че тук имаме малко различни демонстрации.
Ако аз я увеличите тук, ще видите, че на отляво имаме балон подреди, в
средата имаме избор вид, и на крайната десница, ние имаме нещо, което
не погледна още нарича се слеят вид.
Но помислете върху това, което ние сме били правиш тук до този момент днес.
Когато Дженифър първо изскочи на сцената, минахме през масив от числа
отново и отново, с линейна търсене и имаме линейно време на работа, голяма O
М, така да се каже.
>> Когато ние сега разгледаме първата седмица на клас, когато бяхме разделяй и владей,
и бяхме телефонния указател сълзене, и Дженифър, и ние колективно
отнесена, че ключовата поглед, който е трябвало да повтаря себе си отново и отново, като
някак изхвърляне, изхвърляне, изхвърлите, половината от проблема, или
като цяло, се раздели проблемът на половина, и след това взаимодействие на по-малък брой на
проблем, тъй като концептуално еквивалентни до друг, някак си направи
фундаментално по-добре.
Но с балон вид, с избор сортиране с вмъкване вид, ние сме може
няма такива прозрения, че Дженифър е направил.
Ние доста много просто се върна и роди цял куп пъти, а ние
променени нещата малко по малко, смяна в този ред, може би
въвеждане или избор.
Но в края на деня, аз направих много на неудобно ходене напред-назад.
Всъщност не ливъридж нещо умен като Дженифър ми хареса раздели
и завладяване.
>> Така се слеят вид, от друга страна, ние, които няма да видите до следващата седмица, че ще
да се наберат, че ключовата идея, като се раздели на входа, и след това се намали наполовина и след това
намаляване наполовина, а след това се намали наполовина.
И на всяка итерация на тази линия, сортиране на лявата половина, и правото
половина, а след това в лявата половина на лявата половина, и дясната половина на ляво, после
лявата половина на дясната половина, и дясната половина на дясната половина.
И повтаря отново и отново.
>> Така ще видите това визуално, но това е това, което ни очаква през следващата седмица.
И като цяло, когато ни се струва малко малко по-трудно върху такъв проблем.
Ние п квадрат в ляво, п квадрат в средата, и п
влезте п отдясно.
Така че там е истинското ти Катерачът.
Ще се видим в понеделник.
>> [APPLAUSE]