>> [За възпроизвеждане на музика]
>> DAVID J. Malan: Това е CS50.
И това е началото на три седмица.
Така че ние имаме много вълнуващо неща, които да обхващат днес.
Много възможности за доброволци на сцената.
И накрая, днес е не става въпрос за код на всички.
Но това е за идеи, и това е за алгоритми,
и действително връщането обратно някои от поуките от нула седмица,
където изземване, ние въведено това чудовище.
И заеми вдъхновение от това, за да започне
за решаване на все по-сложни проблеми алгоритмично.
Но първо, няколко съобщения.
Така един, ако искате да се присъедините Персонал и съученици CS50 е на обяд
този петък, тук и в Cambridge, и в Ню Haven,
моля, посетете на курса сайт, където може да се намери на URL.
Лекция тази сряда ще Не е тук Сандърс.
Тя ще бъде само онлайн, така че мелодия на интернет страницата на CS50,
дали тук, в Кеймбридж или Ню Хейвън, както добре.
>> И тогава проблем зададете два вече е в ръцете ви.
Ако не сте се хвърли в още, позволете ми да предложи на остро внушението
че особено сега, когато проблема определя предварително,
Наистина ли искате да започне още сега, ако не бъркам малко през уикенда или преди
когато за първи път излизат на Петък, защото ще
откриете, че те не са непременно получаване на по-дълъг или по-голямо предизвикателство за
себе си.
Мисля, че ще се намери, че в Като цяло, те са склонни да вземат приблизително
около един и същ период от време.
Но това със сигурност зависи на студента, и то
зависи от нагласата с която го подход.
Но неизменно, ти започваш да тичам нагоре срещу някои стена,
и ти започваш да се удари някои бъгове, и ти си просто
няма да бъде в състояние да го преодолееш в някакъв момент.
И това е изключително ценно, за да може да се излезе, да се върне на следващия ден,
отидете в работно време, пост на CS50 Обсъдете или други подобни, за да се получи в действителност разблокиране.
Така че имайте това предвид.
Като се започне най-ранната е възможно е най-доброто нещо което можете да направите.
Така че тук е мястото, където ние започнахме класа, над нулата в седмицата.
И можем да получим доброволец тук, за да ми помогне да намерите микрофони?
ДОБРЕ.
Отстояване вече.
Хайде нагоре.
Предполагам, че това е начина, по който ще се работи.
Как се казваш?
ALAN Естрада: Alan Estrada.
DAVID J. Malan: Alan Estrada.
Хайде нагоре.
Приятно ми е.
ALAN Естрада: Приятно ми е да се запознаем.
DAVID J. Malan: И ти беше тук с нас в нула седмица, разбира се.
ALAN Естрада: Бях.
Аз бях.
>> DAVID J. Malan: Така че може да отидеш напред и да се намери за нас Mike Smith,
колкото може по-бързо?
Колкото може по-бързо.
Буквално разкъсване на проблема на половина, колкото е необходимо, за да.
>> ALAN Естрада: Um.
DAVID J. Malan: Буквално разкъсване на проблема на половина.
>> ALAN Естрада: Oh.
Мм.
Много добре.
>> DAVID J. Malan: OK.
Good.
Благодаря.
ALAN Естрада: Много добре.
ДОБРЕ.
>> DAVID J. Malan: И така, сега, сте го сведено
на половината от размера на проблема.
Сега, ние сме до една четвърт.
Възможно ли е да се обръща внимание на чия страна сме поддържаш?
>> [Сайта]
>> ALAN Естрада: Да, аз think--
>> DAVID J. Malan: Какво точка ние сме в?
ALAN Естрада: ауспуси, така.
>> DAVID J. Malan: OK.
Но Майк Смит се случва да бъде след ауспуси.
So--
>> [Сайта]
>> Всичко е наред.
ALAN Естрада: Когато търсим?
DAVID J. Malan: Майк Смит.
ALAN Естрада: Майк Смит.
DAVID J. Malan: Сега, ние сме в хирургично.
Сега, лекарите.
Сега--
>> ALAN Естрада: Let's- да вървим с реални.
Real.
>> DAVID J. Malan: Real.
ДОБРЕ.
Ако имате нужда от Реал.
Сега, по какъв начин е Майк Смит?
>> ALAN Естрада: Този начин.
>> DAVID J. Malan: Накъде?
ALAN Естрада: Изчакайте.
M is-- нали?
Започнахме with--
>> DAVID J. Malan: Да.
Те са напуснали.
Прав си.
>> ALAN Естрада: Да.
>> DAVID J. Malan: Така Майк тук.
ALAN Естрада: Какво?
>> [Сайта]
>> Лош пример, момчета.
Извинете.
DAVID J. Malan: Това ще научи можете да скочи от стола си.
>> ALAN Естрада: Oh.
Oh.
Хванах те.
Oh.
Това is-- OK, имам теб.
Smith точно тук?
>> DAVID J. Malan: Smith, благодаря ви.
Така че аз ще продължавам да гледам Смит?
>> ALAN Естрада: О, да.
Не не не.
О, не.
Това е мое.
>> DAVID J. Malan: О, имаш Smith.
ДОБРЕ.
>> ALAN Естрада: Да, имам Smith точно тук.
Съжаляваме, момчета.
Мислех, че сме Michael-- търсеха Майкъл.
Извинете.
>> DAVID J. Malan: Всичко е наред.
Добре, сега сме в Paccini и синове.
>> ALAN Естрада: Paccini и синовете.
DAVID J. Malan: Само ти и аз сме в по този въпрос.
ДОБРЕ.
Намерете ни Майк Смит.
Smith.
>> ALAN Естрада: Smith.
>> DAVID J. Malan: Smith.
Ние сме в R за боклук.
ALAN Естрада: За боклука.
Oh.
Това ще отнеме известно време.
>> [Сайта]
DAVID J. Malan: обувки.
Ние сме в обувките.
>> ALAN Естрада: Сега ние сме gonna--
>> DAVID J. Malan: Nice.
ALAN Естрада: Which--
[Сайта]
О, това е страхотно.
[Сайта]
>> DAVID J. Malan: Всичко е наред.
>> ALAN Естрада: О, това е добре.
Не мисля, че аз отивам да Трябва PSAT приятели след това.
DAVID J. Malan: Добро.
Спортинг.
ALAN Естрада: Спортинг.
Хм, L, M, N, O, P.
DAVID J. Malan: OK.
Така че нека да разкъсат тази наполовина.
ОК е.
Това завършва зле, така или иначе, защото Майк Смит не ще бъде в жълтите страници.
>> ALAN Естрада: Aw.
>> DAVID J. Malan: Не, това е ОК.
Но нека да се преструвам, като той е на тази страница.
Така че сега, че сте сведено проблема надолу до една страница, и ние открихме, Майк Смит.
>> [Аплодисменти]
Добре благодаря.
ДОБРЕ.
Това беше изключително.
Но все пак това е по-бързо отколкото линейно търсене,
където можем да започне в началото на книгата,
и ние преминаваме от ляво на дясно, в крайна сметка търси Майк Смит.
И така, ако телефонния указател имаше може би хиляда страници,
може би това щеше да отнеме ни 10 или така сълзи страница.
>> Но може би сте ливъридж докосна предположение
по време на всичко това, което ще рече че в телефонния указател предварително е какво?
АУДИТОРИЯ: Сортирани.
DAVID J. Malan: Тя е сортирани.
Нали така?
Това подредени по азбучен ред, така че че всички тези имена и номера
са подредени от A към Z, а по азбучен ред по средата.
Но днес, ние сега питам въпросът, добре,
как направих Verizon или телефона фирма го получите в това състояние?
>> Защото това е едно нещо, за да се наберат това предположение, и следователно,
решаване на проблема с алгоритъм по-ефективно.
Но ние никога не попита нула седмица, добре,
колко много го е направил разходи Verizon или някой друг
за да получите този телефон книга в сортиран ред?
>> Нали така?
Това няма значение, ако погледна Mike Smith
е супер бързо, ако това ви отнема година, за да се справи страниците първоначално.
Нали така?
Вие може и просто да се пресее чрез рандомизирани телефонен указател,
ако то се случва да бъде супер скъпо да го оправи.
Така че, ако можем да имаме друг доброволец.
Нека да потърсим тук как можем might-- хайде up-- как
бихме могли да отидем за сортиране тях.
>> И ако в действителност може да Jordan Присъединете се към нас тук на сцената.
Хайде нагоре само за миг.
Как се казваш?
CAROLINE: Каролин.
DAVID J. Malan: Caroline, хайде нагоре.
И вие ще се присъедини от мен и Йордания тук.
Caroline, благодаря ви.
Всичко е наред.
Така че това, което имаме тук за Каролин е 26 сини книги
че FAS използва за администриране определени изпити.
Те стават трудно да се намери, но това, което ние сме направили предварително
е, че ние сме поставени нечие име на лицевата страна на всяка от тях,
но ние продължаваме да се прости с него След гасенето пълните имена.
Така че ние ще постави на лицето с името L, D, J, B, по целия път от А до Z,
но те са в произволен ред.
И така, ако щете, да говорим си път през проблема, колкото
го, може ли да отида напред и сортирате те за нас, от А до Я.
>> АУДИТОРИЯ: ОК, така че L е като, по средата.
C започва.
B. J преди L. B, Q.
>> DAVID J. Malan: Задръжте че помислих за една секунда.
Защото в противен случай това е само интересна за вас, мен и Йордания.
Ето.
АУДИТОРИЯ: [недоловим].
R.
DAVID J. Malan: OK.
Какво правиш?
>> CAROLINE: M идва след О.
>> DAVID J. Malan: OK.
>> CAROLINE: O.
DAVID J. Malan: O, Good.
>> CAROLINE: E.
>> DAVID J. Malan: E, F. Да.
>> CAROLINE: T, U, V.
>> DAVID J. Malan: V, T, U, V. Така че Изглежда сте making-- продължавай.
Тя изглежда като вие правите голяма купчина тук,
и вид на голяма купчина там.
Така че през първата половина на азбуката, втората половина на азбуката.
ДОБРЕ.
Good.
Вид на разделянето на проблема на две.
M, N, X. Да.
CAROLINE: K.
DAVID J. Malan: OK.
K. Значи вид избиране ги един след друг,
поставяйки я вляво или вдясно, или Z, става на пода.
ДОБРЕ.
>> CAROLINE: Z става на пода.
>> DAVID J. Malan: OK.
Y се случва на пода.
Сега можем да сложим X.
>> CAROLINE: G.
DAVID J. Malan: G ще напусна.
S ще полето.
Добре, A ще целия път наляво.
>> CAROLINE: A, B, C, D.
>> DAVID J. Malan: Сега добро.
Имаме A, B, C. W, става там долу.
Добре, T.
>> CAROLINE: H, I, J.
DAVID J. Malan: H, I, J. Good.
CAROLINE: В центъра, аз съм gonna--
DAVID J. Malan: OK.
Така че сега, ние ще натура на сливането на тези различни пилоти.
Така A през C, тогава виждам D, и E, и F, и G, H и и I. Ница.
J, К. И тогава, това е купчина с главата надолу, но това е ОК.
Разбира се.
Ние може да намали някои ъгли.
ДОБРЕ.
И тогава ние трябва W, X, Y, Z.
>> CAROLINE: Да.
>> DAVID J. Malan: отлично.
Така че по-голямо благодаря на Caroline за сортиране тях.
>> [Аплодисменти]
>> Благодаря.
Благодаря ти много.
Така че сега нека да разгледаме за момент как Caroline обикаляше да прави, че,
и какво точно сме успяхме to-- как можем
са били в състояние да реши, че проблем, когато бяхме просто
дал цял куп случайни входове.
>> Е, изглежда, че има беше малко на система там?
Право.
Така че по-ранните писма в азбуката, тя
беше удар от ляво, и късните букви в азбуката,
тя е въвеждането в правото.
И веднага след като тя намери някои близки букви, Ones
които отиват в непосредствена близост един до друг, тя ще постави тези в ред.
И така, ние вид имаше тези малки купища сортирани подаване на данни.
>> И така, това е съвсем като това, което повечето от нас, хората ще направят.
Бихме нещо пресее през него, и ние бихме вид има механизъм.
Но това може да бъде трудно да се напише тя установени в една формула, само по себе си.
Той се почувства малко по-органично от това.
Така че нека да видим дали можем сега да свързания Проблемът с малко входове.
>> Вместо 26, нека направи нещо много по-малко
с просто кажем, седем, зад тези врати, така да се каже.
Има само седем числа?
И ако целта сега в ръка е да се намери стойност,
нека да видим как ефективно ние можем да го направим.
И нека да видим дали можем сега започват да се прилагат някои цифри,
или някои формули, с които да се опише ефективността на нашия телефонен указател
алгоритъм, нашия изпит книга алгоритъм, и по-общо, намиране на информация.
>> Така че за това, нека да вървим напред, и на сензорния екран тук,
поставя на уеб браузър, който има точно тези седем врати.
И ако можем да се получи един друг доброволно да дойде върху тук,
Вложил съм същите тези врати тук.
Quick доброволец.
>> Този one-- демонстрации вървят до по-бързо и по-бързо сега.
Хайде надолу.
Как се казваш?
TREVOR: Тревър.
>> DAVID J. Malan: Тревър?
Добре, Тревър, хайде надолу.
Така че Тревър е доброволно тук, за да направя подобен проблем, но този, който е
тесен обхват, както и че ще ходи за да ни позволи да се опита да се формализира сега
процеса на сортиране тези номера.
>> Така че Тревър, хубаво е да се запознаем.
Така че тук е масив, така че да говори, списък на седем врати.
Давай напред и да ни намерите на броя 50.
И тогава след факта, да ни кажете как сте го намерили.
Трябва be-- оправи.
Да, това е този тук?
Охо.
ДОБРЕ.
Можете кликнали, че един.
Good.
>> И добре.
Сега вие сте кликнали, че един.
И нека да ви дам микрофона, така че да можете да го имат в един момент.
Давай напред и да щракнете на в съседство, който възнамерявате.
Да добре.
TREVOR: Мога ли да махнете отметката врата?
DAVID J. Malan: Не, вие не можете да махнете отметката.
TREVOR: OK.
Този.
DAVID J. Malan: Къде искате да отидете?
Кое?
>> TREVOR: Това един.
>> DAVID J. Malan: No.
>> TREVOR: OK.
Този.
>> DAVID J. Malan: Да.
Това беше добре.
Всичко е наред.
И така, какво е алгоритъм си или Процедура за този начин, Тревър?
>> TREVOR: Току-що премина през врати, докато не намерили 50.
DAVID J. Malan: OK.
Отлично алгоритъм.
Така че това е добре.
Защото в действителност, ако разкрие какво е зад тези две други врати, това, което
ние ще намерим тук е, че имаме само случаен вход.
Така че това е всъщност като добър, колкото бихте могли да получите.
И всъщност, имаш по-добър от изчерпателно търсене в целия масив,
защото това би било наистина Нещастната ако е ударил броя
50 в последната врата.
Но какво, ако ние, вместо ти даде предположение.
Да предположим, че подреди всички тези врати, около
така че да имат номера сортирани този път,
но този път това е всъщност а different-- този път,
това е всъщност подредени за вас.
И сега целта на една ръка разстояние е да се удари в брой 50.
>> TREVOR: OK.
>> DAVID J. Malan: Какво е алгоритъм ви ще бъде?
>> TREVOR: Е, ако това е подредени, това е или ще
да be--, ако най-голямата до най-големия, низходящ, това ще бъде първата,
или, ако това е точно обратното, това ще бъде последният.
Така че аз просто ще се включи тази врата, и след това просто докоснете последната врата.
DAVID J. Malan: отлично.
Всичко е наред.
Така че ние открихме броя 50.
Така че веднага щом се знаеше те са подредени, ние
са били в състояние да се наберат това предположение.
Така че те са твърде много като примера на телефонния указател.
Веднага след като имате, дори и с един малък проблем, подобен на този,
Вашите входове предварително подредени, можем всъщност се намери стойността спорно
по-ефективно.
>> И аз не ви кажа, ако това е сортирани малки до големи, или големи до малки,
и така че е много разумно да започне в единия край или другата
действително да откриете, че целевата стойност.
Така че благодаря на Тревър, както добре.
И аз ще propose-- добре направено.
Имаме малка скоба, всъщност, че е сред любимите ни моменти в CS50,
при което понякога тези демонстрации не съвсем отиде по план.
И наистина точно сега, аз придърпа грешен интерфейс
с които да се използват сензорния екран.
Така че това беше по моя вина там.
>> Така че това ще допринесе за за следващата година, както клип
защо аз бях като кликнете върху собствения си екран.
Но нека хвърлим един бърз поглед какво се случи миналата година
с Jay, който дойде, много по- като Тревър тук, доброволно,
и в този кратък клип, ще видите как същата тази демонстрация не е съвсем
разкрие същите поуките.
[Възпроизвеждане на видео]
-Всички Искам да направя сега е да се намери за мен, и за нас,
Наистина, броят 50 стъпка по стъпка.
>> -В Номер 50?
>> -В Номер 50.
И вие може да разкрие какво е зад всяка от тези врати
просто като го докоснете с пръст.
Мамка му.
>> [Сайта]
>> [END PLAYBACK]
DAVID J. Malan: Така, че мина много добре.
Това бяха несортиран вратите.
И Jay, разбира се, всичко намерено твърде бързо.
Тревър е направил много по-добра работа от гледна точка на поучаеми момент,
така да се каже, тази година в отнема повече време, за да го намерите.
Разбира се, след това дадохме Jay втори шанс,
чрез което сортирани вратите, точно както направихме за Trevor,
и Trevor направих супер добре този път.
Но Джей го направи два пъти по-бързо.
[Възпроизвеждане на видео]
-В Цел сега е да се ни намерите номера 50,
но го направи алгоритмично, и да ни кажете как започваш за това.
>> -ДОБРЕ.
>> -И Ако го намери, да поддържате филма.
Ако не го намерите, можете да го върне.
>> -Man.
>> -О!
>> - [Недоловим] OK.
Така че аз отивам да проверите краищата първо да се определи дали there's-- Oh.
>> [Аплодисменти]
>> [END PLAYBACK]
DAVID J. Malan: OK.
Така сортиране врати ясно води до по-голяма ефективност.
И така, два пъти по-бързо това имах предвид там.
И така Jay извади късмет и двата пъти.
И той също извади късмет с това, че последната години, си поръчах някои блу-рей дискове
действително да дават.
Съжалявам за тази година, ние не са имали една и съща, Тревър.
Но все пак по-добре е за няколко години назад.
И някои от вас може би знаят това колега, Шон, който, когато е бил в CS50,
е обжалван с точната същия проблем, макар и в SD,
както вие скоро ще видите, през деня.
И вие ще откриете, че не само е направил Той отнеме малко повече време, отколкото Jay,
малко по-дълго, отколкото Trevor, че е Всъщност тази чудесна възможност
да се ангажира почти всички в тълпа а ла цената е правилна, насърчаване
него да се намери броя бяхме търси.
Нека. хвърлим един бърз поглед.
>> [Възпроизвеждане на видео]
>> -ДОБРЕ.
Така че вашата задача тук, Шон, е следното.
Имам скрити зад тях врати числото седем.
Но закътано в някои от тези врати както и други отрицателни числа.
И целта ви е да се мисли, на този най-горния ред на номерата
като само масив, или просто поредица от парчета хартия
с числа, които стоят зад тях.
И целта ви е, само с помощта на върха масив тук, ме намери числото седем.
И ние тогава ще критикуваме как да отидете за да го прави.
-Всичко е наред.
-Find Ни числото седем, моля.
Не.
Пет, 19, 13.
>> [Сайта]
>> Това не е подвеждащ въпрос.
One.
>> [Сайта]
В този момент, резултатът ви не е много добро, така че може и да продължи да функционира.
Three.
>> [Сайта]
>> Продължи.
Честно казано, аз не мога да помогна, но се чудя това, което дори и да мисля за, so--
>> [Сайта]
Само най-горния ред, така че имаш три лявата.
Така ме намерят седем.
>> [Сайта]
17.
Seven.
>> [Аплодисменти]
>> Всичко е наред.
>> [END PLAYBACK]
>> DAVID J. Malan: Така можехме гледате тези през целия ден.
И разбира се, някои от тазгодишните демонстрации може би
сега ще се окажете в следващия Тазгодишният видео, както добре.
Така че сега е нека действително съсредоточи върху алгоритмите
тук, и да видим дали не можем Сега започнете да се формализира
как можем да отида за получаване нашия данни в това състояние, че това е сортирана,
така че в крайна сметка, ние можем действително го търси по-ефективно.
И въпреки, че отиваме да се използва сравнително малки групи от данни,
Както вече на осем числа имаме тук на дъската,
в крайна сметка успя да достигне същите тези идеи 1000 входа, един милион входове,
4 милиарда входове, тъй като алгоритмите ще бъде коренно същото.
>> И така, това е нашата последна възможност за доброволци и днес,
но може би най-въпрос за един, за които ние се нуждаем от осем доброволци
да се качи и да ходи с нас чрез Веднага след процес на сортиране какво ще
да бъде на тях музика стои тук.
Позволете ми да започна отново тук.
>> Така че един в turquoise-- зелено е това?
Възможно ли е да извърши?
Two.
Хайде надолу.
ДОБРЕ.
Three.
Four.
Нека me-- OK, пет.
Вие сте били номинирани от приятеля си.
Шест, седем, а осем.
Хайде нагоре.
Всичко е наред.
Благодаря ти много.
Хайде нагоре.
>> Всичко е наред.
Така че това, което имаме и това here-- е сред по-неудобни тези,
тъй като това ще изисква от вас хумор ми за по малко от време.
Ти ще бъдеш номер едно.
Как се казваш?
>> Анан: Анан.
>> DAVID J. Malan: Анан.
Дейвид.
Как се казваш?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, Ако сте номер две.
>> СЕРЕНА: Серина, номер три.
Стефан, номер четири.
Синтия: Синтия.
DAVID J. Malan: Синтия, номер пет.
[Недоловим]
DAVID J. Malan: [недоловим].
Дейвид, номер шест.
MATT: Мат.
DAVID J. Malan: брой на Мат седем.
И?
>> Waverly: Waverly.
>> DAVID J. Malan: Waverly, номер осем.
Всичко е наред.
Ако could-- Опа.
Ако всичко, което, както си първо влизане, има
Осем са музикални щандове тук с лице към публиката.
Ако можеше да сложиш номера на тези музика стои по такъв начин,
че те е изравнена с същите номера на дъската.
Така че да се правите, че да изглежда като от поставите номера на тези музика
стои тук.
Отлично досега.
>> Отлично.
ДОБРЕ.
Така че сега, ние ще зададем въпрос по няколко различни начина.
Как можем да отидем за сортиране тези хора тук?
Тъй като имахме няколко подходи по-рано, при което бяхме
вид вземане на две различни кофи.
И тогава ние бяхме като цяло реди неща заедно.
Веднага след като видяхме две числа че бе заедно,
ние ги съберете заедно.
Две писма, които вървят заедно.
>> Но нека да видим дали можем не може да се формализира това,
така че да можем в крайна сметка да има някои псевдо-код щете,
с която можете да реши тези проблеми.
Така че сега, аз съм гледам навън при тези номера тук.
И виждам цял куп грешки.
В крайна сметка, аз искам един на наляво и осем от дясно.
>> И така, аз разглеждам тези две, четири и две.
И какъв е проблемът, очевидно?
Да.
So.
Две очевидно идва преди четири, така че знам какво?
Позволете ми първо да алчни подход, ако щете, който много прилича на проблеми
зададете one--, ако си спомняте от Standard Edition на Проблем Set One,
когато аз просто локално реши проблема това е точно тук пред мен
и да видим къде той ме води.
>> ДОБРЕ.
Така че две и четири, да ме пусне напред и просто да ви суап две.
Ако физически можете да се движите себе си и вашата хартия,
Изглежда съм намерила изброят в по-добро състояние.
>> Сега, те са добри.
Отивам да се премине, четири и шест, изглежда добре.
Не е проблем.
Six и осем, OK.
Осем и един, друг проблем.
Защото това, което е вярно, около осем и един?
One идва преди осем, и така, какво да правим?
Нека да сменяте тези две.
One и осем.
И сега, аз отивам да продължи да функционира.
Отивам да продължим да търсим напред.
И нека да видим какво ще стане.
Осем и три, на Разбира се, в ред.
Нека суап.
Осем и седем, разбира се.
Няма ред.
Нека суап.
Осем и пет, разбира се, нека да суап.
Всичко е наред.
Списък се сортира.
нали?
>> OK, явно не.
Но това е малко по-добре, нали?
Защото известие, което се случи.
Всеки път, когато се извършва замяна, по-малък Номер вид прецедени по този начин,
и по-голям брой прецедени този начин, или ще
започнете поговорка разпенва до наляво или надясно пропуска.
>> Сега, това не е достатъчно, тъй като в най-добрия редица мощ
са се преместили на едно място напред, или в най-лошия,
редица може да има премества едно място по-нататък.
Така ли какво, този вид от работил доста добре досега.
Нека просто го опитайте отново.
Две и четири, те са ОК.
Четири и шест, те са ОК.
Six и един, в ред.
Така че нека да ви две суап.
И сега, забележите проблем те години започва да става малко по-добре отново.
Шест и три, в ред.
Нека вие двамата разменят.
Шест и седем, вие сте добре.
Седем и пет, разбира се, в ред.
Седем и осем, в ред.
И сега, може да се наложи да направите това още няколко пъти.
И всъщност, мисля за себе си може би колко пъти максимално
може ли да ходи напред-назад?
>> Ще се върна към това.
Така че две и четири са все още OK.
Четири и един, Не.
Така че, нека суап.
И пак забележите визуално един е вид бълбука
наляво, където трябва да бъде.
Четири и три суап.
Четири и шест.
Шест и пет суап.
Шест и седем.
Седем и осем са добри.
>> Good.
Ние получаваме още по-добре.
Така че нека да видим.
Сега, ние имаме две и една.
Разбира се, сменяте.
Две и три, три и четири, четири и пет, шест и седем, седем и осем.
Good.
И знаеш ли какво?
Защото аз направих една промяна там, позволете ми да направя една проверка здрав разум.
Нека да отидем по целия път обратно в началото.
ДОБРЕ.
One, two-- Мда, виждаш ли?
Нещо не беше наред.
Три, четири, пет, шест, седем, осем.
И в този последен пас, са можете удобно с моя сега
твърдейки, че е сортирани?
ДОБРЕ.
Визуално, това е абсолютно вярно.
Но функционално, което е също така просто да се случи
с това, че последната атака, която ви позволява да потвърдя, че този списък е наистина
сортирани?
>> Какво съм направил или не направи това миналата пас?
АУДИТОРИЯ: Няма промяна.
DAVID J. Malan: Съжаляваме?
АУДИТОРИЯ: Няма промени.
DAVID J. Malan: Няма промяна.
Така че би било глупаво от моя страна да направя същата алгоритъм отново
ако не е допуснал променя първи път.
И държавата не се е променило.
Разбира се, аз няма да се направи Всички промени, за втори път.
И така, това е безопасно сега да се каже, списък е сортиран.
>> И наистина, това е сега нещо, което ние ще принцип
повикване балон сортиране, при което по двойки, можете поправяне на грешки отново,
и отново, и отново, и вие продължавай напред и назад,
и назад и напред, докато не да няма такива суапове, като в този момент
можете да сте сигурни, да, аз завърши определяне на всички грешки.
Нека да изчисти и да се опита друг подход.
Ако вие може да се върне в реда, в който са били преди малко,
която изглеждаше така.
Сега, нека да подход на Малко по-скоро като на изпит книгата,
с което бяхме постоянно избор на буква от азбуката
че ние вид исках да се справят с по-нататък.
Може би това е високо писмо, като A, или нисък писмо Z.
>> Така че всеки се е върнала в този ред.
А сега нека да направим това.
Нека да видим Знам, че имам осем номера тук.
Отивам да вървим напред и да просто избират съзнателно
най-малките елементи.
Нали така?
Това изглежда твърде интуитивен.
Защо не мога да намеря най-малките елемент, сложи я там, където принадлежи,
след това получи следващата по-малка елемент, сложи то там, където принадлежи, и просто се повтаря.
>> Защото интуитивно, че трябва да работи също.
Така четири, че е доста малък брой.
Отивам да си спомни къде е това.
Чакай малко.
Две е по-малък.
Нека сега да си спомня къде двама е, и да забравите за четири.
Ние ще се справим с това по-късно.
Six, не ме интересува.
Eight, аз не съм интересуват.
Един от тях е новата ми малко на брой.
Така че аз отивам да си спомни къде е една.
Три, не се интересувам.
Seven, не се интересувам.
Five, не се интересувам.
>> Така че, без да пада на сцената тази година,
Отивам да вземете номер one-- и какво е вашето име отново?
>> Анан: Анан.
>> DAVID J. Malan: Анан.
И ако можете да се присъедините към мен в началото на списъка
нека да си сложиш където ти е мястото.
Unfortunately-- какво е вашето име?
>> СТЕФАН: Стефан.
>> DAVID J. Malan: Стефан е в пътя.
Така че, преди Стефан решава този проблем, какво да правим?
Какво да правим със Стефан?
>> АУДИТОРИЯ: [недоловим].
DAVID J. Malan: OK.
Така че бихме могли да направим това.
Бихме могли да вземат нещо като Стефан и неговият четири, а просто да го постави в променлива
и държа на него за някаква сума от време,
като по този начин място за номер едно.
И това не е лошо.
Мога да предложа, защо да не направим ние просто сложи Стефан тук?
Защо може да наруши този един от идеите, ние започнахме
Говорим за последен път, миналата седмица?
Да?
>> АУДИТОРИЯ: [недоловим].
>> DAVID J. Malan: Няма по индекса за него.
Ако мислите, че на този, наистина, като масив, това е като отрицателен,
така че няма памет всъщност тук, ако това наистина е масив,
като ние обявена миналата седмица в лекция.
Така че ние не трябва да направите това.
Бихме могли да го съхранява в променлива.
>> Или знаеш ли какво?
Чух някой друг да го предложи.
Какво друго можем да направим със Стефан?
Защо не можем просто да го изгони и го постави върху това къде номер едно беше.
Така че, ако искате да отидете там.
И наистина, това е доста добро решение.
Сега, от една страна, аз съм вид на прави проблема по-лошо.
Сега е по-далеч Четири от мястото, където трябва да бъде.
Тя трябва да бъде към тази половина.
>> Но знаете ли какво?
Това можеше да е лош късмет.
Може би номер осем е бил тук.
И така, може би бихме са придобили късмет,
и бутна осем по-близо до края.
Така че в края на деня, то вид на всички средни място.
Ние не трябва да се грижи за четири.
Всичко, което ме интересува в момента е избиране на най-малкия елемент.
>> И сега, това, което аз отивам да направите, е да забравите за номер едно
постоянно, защото знам, че на списък зад мен сега се сортира.
Така че моят списък беше преди осем размер.
Сега, това е с размер на седем.
Така че моят проблем е все малки, макар и линейно.
Така че сега, аз отивам да изберете ток-малкият елемент, две.
Шест, осем, четири, три, седем, пет.
Това е най-малкия елемент.
Така че това, което съм аз ще направя with-- какво е вашето име отново?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Йосиф?
Отиваме да напусне Joseph на място.
Сега, аз отивам да се преструвам че тези момчета are-- добре,
Знам, че тези две вече са подредени.
Нека сега се съсредоточи върху остатък от списъка.
Шест е текущата малката.
Осем е по-голям.
Сега Four е текущата малката.
Три сега е текущата малката.
И така, сега, аз отивам да изберете три, които is-- какво се казваше?
СЕРЕНА: Серена.
DAVID J. Malan: Серина, ако можех вземете своя номер и суап with--
KALSANG: Kalsang.
DAVID J. Malan: Kalsang.
Хайде обратно, и ние сме Ще сменяте тези две.
И сега, нека да поставим този на автопилот.
Отивам да отида и да я оставите да вие, момчета, за да изберете следващите най-малките елементи.
Dun, сивокафяв, сивокафяв, сивокафяв.
Номер четири, какво трябва да направя?
Отлично.
Сега, аз отивам да се направи още един пропуск.
Dun, сивокафяв, сивокафяв, сивокафяв.
Виждам пет е следващата по-малка.
Сега, аз ще взема още един пас.
Dun, сивокафяв, сивокафяв, сивокафяв.
Six е най-малката.
Good.
Седем е най-малката.
Няма промяна.
Осем е най-малката.
Съставено.
>> Така че това, което току-що направено чрез итеративно избиране на един елемент след друга
се приложи нещо, което сме ще официализира като избор на сортиране.
И това е може би дори по-лесно да се обясни,
в които буквално всичко, което искате да направите, е просто да
Ще назад и напред през списъка избиране, следващата по-малка елемент,
докато сте готови.
>> Така че това е още по-лесно, може би интуитивно, в сравнение с миналата.
Нека се опитаме за последен една.
Ако вие може да себе си нулират в следните позиции
за последен път, нека да видим дали не можем Сега се формализира един друг подход.
В действителност, би някой там искал да предложа
как иначе бихме могли да го направим?
Без да хвърлят вън модерни думички или сортиране на отговорите, които вече са известни,
просто интуитивно, какво можем да направим?
>> АУДИТОРИЯ: [недоловим].
DAVID J. Malan: Да.
Така че има някои много интуиция там.
Хубавите неща се случват по този начин досега по компютърни науки, когато ние разделяме
и завладяване на проблема за разделяне го на половина и половина и половина.
И така наистина, ние може да започне да се направи това.
И в действителност, че ще бъде, ще виж, един от най-добрите ни решения, все още.
Но нека се върна към това след дълго.
В действителност, ние ще направим че малко по-късно тази седмица.
Какво друго може да направим, за да се реши този?
Така че всеки тук е в привидно случаен ред.
Знаеш ли какво?
Вместо да отида напред и назад, назад и напред, назад и напред
всеки път, това се чувства като Правя много разходки.
Защо не мога просто да започне в началото на списъка
и просто сложи четири където му е мястото?
Така че нека да приемем за момент, че моя списък е само този първи елемент.
Е четири подредени в този момент във времето, ако всичко, което ме интересува е всичко тук?
Това е нещо тривиално вярно, нали?
Подобно на списъка, съдържащ един номер, и че номер четири е очевидно сортирани.
>> Така че нека просто да предвидят че този списък е сортиран.
Но сега имам останалата част на този списък.
Така че сега, аз се сблъскват две.
Къде два очевидно принадлежат по отношение на четири?
Преди четири.
Така че това, което мога да направя тук?
Какво е вашето име отново?
>> JOSEPH: Joseph.
>> DAVID J. Malan: Joseph, ако бихте могли да се върнем назад
само за миг с вашия номер.
И сега какво трябва да направя Стефан тук?
Нека да смени Стефан тук.
И сега, нека Йосиф дойде тук.
И сега, нека да се твърди, че тук всичко се сортира.
Така че, подобен резултат, но по- коренно различен подход.
Аз дори не погледнах какво има там долу.
Аз просто продължавате да приемате елементите като те са предадени за мен,
и да се справят с тях.
>> Така че сега, виждам, номер шест.
Къде номер шест принадлежат?
Имаме две, четири, шест.
Точно къде е тя в момента.
Така че нека да оставим това сам, а сега твърдят, че тази част от списъка
сега сортирани.
И така, това се чувства фундаментално различна с това, че аз съм просто
движещи се през списъка тук линейно, а аз никога не съм удвояване обратно.
Да.
Всичко е наред.
Така осем, къде ти е мястото?
Точно тук.
Perfect.
Така че сега, една.
Охо.
Това се чувства като това е ще бъде скъпо.
Сега в предишния алгоритъм, Аз просто замениха хората.
Така че аз може да го постави по целия път към началото, но след това се премества Йосиф.
Но ако се преместя Йосиф, сега каква ще е наред?
>> Сега, аз съм нещо като undone-- съм една стъпка напред и след това
една крачка назад, защото сега Йосиф ще бъде извън строя.
Така че нека да направим това.
Ако можеше да вземе номер едно и стъпка назад само за миг.
Как можем да put-- какво е името ви отново?
>> Анан: Анан.
>> DAVID J. Malan: Анан на място?
Какво трябва да се случи по отношение до две, четири, шест, а осем?
Всички те ще трябва да се смени.
Така че, ако осем биха искали да се смени Първо, след шест, след четири, след това два.
И тогава Анан, ако искате искал да дойде тук, добре.
Но тук, ние сме просто вид платена цена
на различен етап в алгоритъма.
Като има предвид, за последен път с избор сортиране, и дори балон сортиране,
Вървя назад и напред, назад и напред,
който е със сигурност добавяне време-мъдър, и буквално поетапно.
>> Въвежда се подреди, на първо поглед, изглежда, че е
супер-умни, по който аз съм просто вземане на бавен, постепенен прогрес,
но аз няма да ходя тази назад и напред.
Но ако някой е наистина в ред, известие
цялата работа аз просто трябваше да се направи.
Аз трябваше да се движат половината от списъка само за да направи място за номер едно.
Така че това е една и съща сума на работата до този момент тя
чувства, просто различен вид работа.
>> Да продължим.
Така че сега ние знаем, че всеки, от едно до осем са подредени.
Ето, имам номер три.
Ако искате да вземете номер три, една крачка назад.
И какво вие трябва да направите?
Да.
Така че това е още един, два, три стъпки.
Три единици за време, което просто струват мен, така че сега може да се побере три.
И накрая, седем.
>> Да вървим напред и да имат можете да се върнем назад.
Това само ще ни струва една единица време, но това е ОК.
И сега, пет ще да е малко по-скъпо.
Ако искате да се върнем назад.
Ние трябва да се движат осем, и седем, а шест.
И тогава всеки е сега сортирани.
Така че голяма ръка на нашите доброволци тук.
Благодаря ти много.
>> [Аплодисменти]
>> Благодаря на всички.
Благодаря на всички.
Така че нека да видим сега колко скъпо всичко това е.
Нека разгледаме може би най- простият от тях, метод на мехурчето.
И аз казвам простата, само защото можете да го решим лакомо, като просто
фиксира двойки Проблемът тук.
Фиксирайте двойки проблема тук, отново и отново
и отново, повтаряйки, тъй като много пъти, колкото всъщност трябва да.
>> Така се оказва, че с балон сортиране, добре,
колко стъпки трябва ли да се вземат на първото преминаване на този алгоритъм?
Аз може take-- нека see-- една, две, три, четири, пет, шест, седем.
А има и осем елементи тук.
Така че това е като п минус 1 стъпки за получите от началото на списъка
на края на списъка.
>> Но с избор на сортиране, припомни, че аз съм избор на елементи отново и отново
и отново, че това е най-малкото, Аз съм го поставя на мястото,
но след това аз не съм търси зад мен отново.
Така че аз мисля, че е малко по-ясно, след това, че за първи път, бих могъл
Трябва да се вземат всички п минус 1 етапи да се намери най-малкия елемент.
След това ги сложи на място, и аз изгони всеки, който е бил тук преди това.
>> Но тогава не е нужно да продължи да гледаш този елемент,
защото знам, че това е вече най-малките.
Така че сега, не мога да гледам само седем елементи, след шест елемента,
След пет елемента, след четири елемента.
И така, математически, ако п е броя на елементите или номера
че ние започнахме с, можете да си представите че това е същото като N минус 1,
плюс п минус 2 стъпки, плюс п минус 3 стъпки,
плюс п минус 4 стъпки, през цялото път до само една крачка.
И аз съм на последната ми човек.
>> И ако си спомняте, че много на статистики книги или книги по математика
имат тези формули на Твърда назад или пред тях,
се оказва, че тази серия може да се изрази по-просто
като N пъти N минус 1 над 2.
И това е добре, ако това не е в челните редици на вашия ум.
Но това наистина е вярно.
Това е просто по-прост начин да го пишете.
И след това, ако смятате обратно към началното училище,
когато просто започнете да се умножи неща, това, разбира се,
е просто п квадрат минус п разделена на две.
Всичко, което съм направил, е разширяване изразите там.
И така, нека да пренапише този малко по-различно.
Това е п карирани, разделено на две минус п / 2.
>> Така че отново, аз съм просто вид на прилагането някои аритметика правила там.
Но забележете, че сега най-големият план в този израз, така да се каже,
е, че N квадрат.
Така че, да, това е п квадрат разделена на две, минус N / 2.
>> Но обикновено, ако п е Ще бъде голяма стойност,
Отивам да се твърди, че п квадрат ще бъде доминиращ фактор.
Това е просто щеше да бъде по-голям принос
на броя на стъпки от п / 2.
Така че това, което мога да кажа от това?
Нека се опитаме един прост пример, дори макар и по математика получава малко голям.
>> Така че предполагам, че имахме 1 милион души на сцената, или 1 милион неща
че искаме да сортирате.
Нека да включите милиона в точно тази формула
да видим колко стъпки е необходимо общо да сортирате милион елементи, използвайки речем,
Избор на вид.
>> Така че ние ще трябва по същата формула, както преди.
Бих включите милиона, така че мога да получа един милион карирани, разделено на две,
минус милион разделена на две.
Ако го направя, че математиката в аванс Оттук имаме 500 милиарда
минус 500 000, които ни дава 499 999 500 000,
което е дяволски много голям.
>> В действителност, ако се сравни с предприятието 499 милиарда, 999 милиона,
500 000 срещу нашата първоначална стойност, 500 милиарда, това е така, по дяволите близо.
Нали така? п карирани, разделено на 2 дава us-- или по-скоро, п карирани, разделено на две
ни даде 500 милиарда.
Това е дяволски много близки до 499 999 500 000,
което означава изваждане на разстояние 500 000, или по-общо, изваждане на разстояние
п издялан, наистина е голяма работа.
The п квадрат прави тези числа растат много по-бързо.
>> Сега, това е важно само доколкото както ние, като компютърни специалисти,
По принцип не се случва да се грижи толкова много около нюансите на тези формули
и точно това, което точни отговори са.
Ние само, че се полагат грижи, знаеш ли какво?
В края на деня, тази формула е от порядъка на п квадрат.
>> Да, ние сме се дели на две в там.
Да, ние сме се извади извън п минус 2.
Но в края на деня, терминът че наистина ни боли и да ни струва
много стъпки е, че квадратен план.
И така, какво компютърен учен ще обикновено правя
се игнорира всички тези, по-малки поръчки, термини
и просто да погледнете този, който допринася най-много за цената.
>> И това е хубаво, защото можем Сега се говори в много по-голяма универсалност
за алгоритми, както и да ги сравните.
А фактът, че аз съм използването на тази O е умишлено.
Когато казвам на реда на, аз съм по-специално
отнасящи се до нещо нарича голяма О. И голяма O
е нотация че компютър учен използва, за да опише
горна граница на нещо.
>> Така че, ако се каже, че един алгоритъм е в голяма О п квадрат,
както аз предложих просто Преди миг, че средства
че от гледна точка на неговото движение време или на нейната ефективност,
отнема от порядъка п квадрат стъпки.
Може би повече, може би по-малко.
Но това е от порядъка на п квадрат.
И това е горната граница.
Това няма да бъде по-болезнено от това.
Това няма да е п кубчета, или 2 до п, или нещо много по-голямо.
Това е горна граница на каквото и да е цена.
Така че има предвид, че, нека разгледа само няколко примера.
И това е само ограничен списък на много чести, работещи пъти
за алгоритми, които е писано да бъде илюстративни за някои неща, с които сме се
Вече видяхме.
>> Така например, в случай на Избор на вид, това, което аз твърдя тук
е бягане, че изборът на сортиране време е от порядъка на п квадрат.
В най-лошия случай, аз отивам да има цял куп случайни числа тук.
И както видяхме математически, ако аз държа ходене
в списъка, през списък, избора на следващия най-малкият
елемент, отново и отново, ако съм всъщност запиша всички стъпки
Аз съм като, както аз предложих formulaically преди, това е от порядъка на п квадрат
стъпки, които аз съм като.
>> И се оказва, че балон сортиране и сортиране чрез вмъкване
са също толкова бавно в най-лошия случай.
Помислете, например, сортиране чрез вмъкване, последния алгоритъм ние разгледани,
които трябваше да разгледаме елемента, и след това го поставете там, където принадлежи.
И тогава ще погледна следващия елемент, и я поставили там, където принадлежи.
>> Така че, помисли за най-добрия възможен сценарий.
Да предположим, че бях ми доброволци се наредят буквално като този, от едно до осем,
вече сортирани.
Колко стъпки е вмъкване на сортиране ще отнеме, за да сортирате осем души,
ако те пристигнат на сцената търси по този начин?
>> Осем души вече са подредени.
И аз използвам сортиране чрез вмъкване.
Това последното на алгоритмите.
Ами, нека да установят отново доста бързо.
Така че ако започна тук, виждам една.
Когато човек принадлежи?
Той принадлежи точно тук.
Виждам две.
Откъде идва два принадлежат?
Точно тук.
Виждам три.
Откъде идва три принадлежат?
Точно тук.
>> Виждам четири.
Точно тук.
Пет, шест, седем, осем.
Няма причина да се повтарям.
И така, как много стъпки е, че по отношение на N?
Това е от порядъка на п стъпки, нали? N минус 1.
Но аз взех един линеен номер от стъпки, и сега съм свършен.
Така че това е най-добрия случай, все пак.
Какво ще кажете за най-лошия случай?
Какво осем са били там, а седем са били там,
и едно и две са тук, така че че списъкът беше наистина обърнати?
>> Е, какво ще се случи в действителност ако това е номерът?
И ние ще направим само няколко примера.
Какво става, ако наистина, броят осем е тук, а number-- Опа.
И какво, ако наистина броя осем е чак тук,
и аз съм с вкарване подреди?
>> ДОБРЕ.
Аз твърдя, в момента тя е на мястото си.
Но сега, когато се seven-- седем отидете?
Разбира се, тя отива тук.
Така че аз трябва да се движат и осем над едно място.
Сега шест, къде отиде?
Е, добре.
Сега, аз трябва да се движат и осем над място, а седем над място,
и тогава аз цоп установени шест.
>> Така за първи път, то разходите ми една стъпка да оправя нещата,
След това ми струва две стъпки, за да оправи нещата.
Колко стъпки е ще предприеме, за да се определи
неща, които да поставят пет на правилното място?
Three.
Защото сега ще трябва да изместват една, две, три.
Колко стъпки е то ще отнеме да сложи четири на правилното място?
4 плюс 5 плюс 6, плюс 7.
>> И така, това е математически идентичен това, което ние, описан за избор на вид.
Ние имаме тази серия това е просто увеличаване.
1 плюс 2 плюс 3 плюс 4, или обратното, 7 плюс 6
плюс 5 плюс 4 добавя за днешния цели на по нареждане на п квадрат.
>> Така че нека да предвижда също, че метод на мехурчето е и в п квадрат.
Защото с балон сортиране, всеки път, когато отида в списъка,
Аз съм като приблизително, колко стъпки?
Всеки път, когато буквално ходи от там до там?
Около н стъпки.
Но колко пъти мощ I трябва да преминете през списъка?
>> Е, грубо п време.
Може би п минус 1, но около п пъти.
Е, защо е това?
Е, с балон сортиране, ако ние започваме с балон сортиране,
със списъка в най-лошия възможен ситуация, която отново е напълно
назад, какво ще се случи?
I проверете списъка, и номер една принадлежи целия път там.
>> Но с балон сортиране, колко далеч прави една преминем първата ми атака през списъка?
Колко петна прави той получи по-близо до правилното място?
Само един.
Така че, ако нещо през тази причина, всеки път, чрез този алгоритъм,
Приемащи около п стъпки на Дейвид.
Но колко пасове в списъка е
ще вземе за един да се балон наляво където принадлежи?
>> Той трябва да се движат като, п пространства по този начин.
Така че просто да се направи сортиране на списъка, Имам да ходи напред-назад н пъти.
И всеки път, аз съм погледнете в наш елементи.
Така правят неща н н пъти по реда на N квадрат.
>> Сега, ние ще видим в някои на шортите, че
са вградени в следващия проблем е CS50 зададете, друг подход към тях,
но за сега, нека просто да разгледа някои други, работещи пъти,
особено ако тези вземат сортиране малко време, за да потънат инча
Какво е един алгоритъм, които вече сме виждали който взема от порядъка на п стъпки?
>> Какво трябва да се вземат линеен номер на стъпки, които сме виждали до този момент?
Какво е това?
Търсене на телефонния указател.
Първият алгоритъм.
Нали така?
Къде сме линейно търсите Майк Смит?
Наистина.
От нула седмица, когато започнах превръщайки една страница в даден момент,
и дори заяви, че е вид алгоритъм линеен чувство,
и ние имахме, че картината на дъска с директен червен линия
и правата жълтото линия, тези, които наистина са били
алгоритми, които са в голяма О п.
>> Защото, за да намерите Mike Smith в телефонен Книга от п страници, в най-лошия случай,
може да ме п стъпки предприема.
Ами като посещаемостта?
Едно две три четири пет шест.
Какво е времето за работа на този алгоритъм за вземане на посещаемостта?
Голям О М, защото на теория I Трябва да отбележим всички в залата.
>> Сега като настрана, какво да кажем за друга оптимизация от нула седмица?
Две, четири, шест, осем, 10, 12.
A компютърен специалист би осъзнават, чакай малко,
това е от порядъка на N, разделено на два етапа.
Нали така?
Защото аз съм това двама души в даден момент.
Но ние ще пренебрегнем тези по-ниски условия за поръчки,
и ние просто ще изхвърлите разделете на две,
и само да кажа, голяма O на п че за алгоритъм, както добре.
>> Какво ще кажете за това?
Ще прескочим някои от тях, но това, което е алгоритъм, който е дневник на п?
Това отне около влезте н стъпки?
The разделяй и владей.
Точно.
Като пример на телефонен указател в нула-рано днес седмица и,
където сме разделени на проблема отново и отново и отново.
Ние го привлече на дъската в седмицата нула като извита зелена линия,
и ние, каза онзи ден, че е логаритмична алгоритъм.
>> И наистина, номера му стъпки необходимо, за да извършите разделяй и владей,
или двоично търсене, тъй като ние ще започнем наричайки го, като в телефонния указател,
е от порядъка на дневника и стъпки.
И това е малко странно един.
>> Какво става с една стъпка, или по-специално
постоянна редица стъпки?
Може би това е две, може би това е три, но компютърен учен просто
той опростява толкова голям O на 1, някои постоянен брой стъпки.
Каква е нещо, което може да направи това отнема постоянен брой стъпки?
>> Какво е времето за работа на пляскайки?
Constant време.
Нали така?
Подобно на това, което е времето за работа на прави нищо, че отнема само един
операция, като отпечатате F Hello World.
Това може да се каже, че константно време, освен ако не е по-малко от ъглов случай с щампа F,
това, което биха могли времето за изпълнение от печат F действително да бъде?
И защо?
Какво е п измервателна в този случай?
>> АУДИТОРИЯ: [недоловим].
DAVID J. Malan: Точно така.
Броят на символите ние искаме да отпечатате.
Така че това е много в зависимост от контекста.
Днес, ние сме били с акцент върху много букви и цифри, тук на дъската.
Но това може да бъде и герои в действително низ.
Така се оказва, че има друг мярка, която ще започне да се грижат за,
и това е точно обратното на големия О, така да се каже.
>> Това е омега нотация.
Като има предвид големия O означава това, което е, на горна граница на времето си на работа?
Максимално, колко време може да отнеме нещо?
Omega-- съжалявам това продължава да идва up-- е обратното на това,
при което тя е по-ниска граница на период от време може да отнеме нещо.
>> So. Например, какво е алгоритъм който взема винаги п квадрат стъпки?
Е, един от алгоритмите, които сме виждали Днес, в действителност, може да бъде и това.
Избор на сортиране.
Избор на сортиране е доста глупаво.
Дори ако algorithm-- съжалявам, дори и ако масивът е вече подредени,
Избор на вид ще запази разхождах из списъка
да се уверите, че има най-малките елемент отново и отново и отново.
И въпреки че на хора при аудитория знаете, че, чакай малко,
вие вече премина малкия елемент, компютърът
не знае, че докато тя изглежда през целия път списъка.
По същия начин, долна граница, която може също така да се вземе предвид
може да бъде линейно време.
>> Колко време отнема да се подреди наш елементи в най-добрия
При използване на нещо като балон подреди?
Да предположим, че вашия списък вече е сортиран.
Казахме балон подреди поема реда на N квадрат стъпки.
Но какво, ако той вече е сортирано?
Ами ако ти осъзнаваш, след едно преминаване през масива
че сте прави не суапове?
Имате ли нужда да продължат да правят повече преминавания?
>> Не.
Така че по-ниска граница на метод на мехурчето Може да се каже, за да бъде линейна.
Омега на п.
И ние можем да погледнем други от тях, както добре.
Така че нека да хвърлим един бърз поглед най-просто визуализация тук
да се види как те се отличат.
Отивам да сляза тук в тази страница, която е на разположение на интернет страницата на C50,
но то ще бъде болка, за да получите работи, тъй като тя използва технология, наречена
Java аплети, което е до голяма степен не се поддържа тези дни,
най-малко от Chrome и някои други.
>> И нека да вървим напред и да се ускори този и обясни какво се случва.
Това е демонстрация на балон сортиране, първият алгоритъм ще погледна.
И това е визуализация това, че всеки на тези пръти представлява номер.
Колкото по-голям бар, толкова по-големи номера.
Колкото по-малка бара, по-малък номер.
И това, което можете да видите визуално, дори въпреки че това се случва супер бързо,
е, че червената лента е като мен, ходене напред и назад за определяне на проблеми.
Можете да видите, че по-големите елементи са наистина ври до правото,
и по-малки елементи се надига в ляво.
И тук, ако ние всъщност изглежда по-тясно сътрудничество,
всъщност можем да преброим брой сравнения и суапове
които са били направени.
>> Но вместо това, нека да погледнем при втория алгоритъм
разгледахме по-рано с нашите доброволци, селекция за сортиране.
Визуално, тя има много по-различен ефект.
Но това е, отново, много интуитивен, в да пазим избора на следващия най-малкият
елемент, и имаме малко късмет.
Това почувствах фундаментално по-бързо.
Но ако ние се завтече това отново и отново и отново с много входове,
ще видим, че това е наистина все още в голяма O на п квадрат.
>> Нека да направим едно последно една тук, сортиране чрез вмъкване,
което е третият алгоритъм ще погледна, и изземване
че това се занимава с елементи, тъй като им се сблъсква,
Но след това може би смени нещата да се правят по стаите,
вмъкване на елементи, където им е мястото.
>> И това също завършва давайки краен резултат. Сега всички три от тези,
усети доста бързо.
И наистина, аз ги прокара в един доста добър клип.
Но в основата си, всички те са доста ужасно, за да бъдем честни.
Всички тези алгоритми досега които работят в големия O на п квадрат
отнеме доста малко време, за да работи в края.
>> И наистина, ние можем да видим и се чувствам по този накрая
ако аз спра тази третата и последна демонстрация.
Това е друга визуализация, което се случва
за да се покаже балонче подредени в ляво, подбор подреди по средата,
и нещо, като един от нашите ръката повдига по-рано предложи,
сортиране чрез сливане в дясно.
A разделяй и владей стратегия в дясно.
И това е, в действителност, това, което сме ще разгледаме в сряда.
Но нека си време те да вървят паралелно.
Това е приблизително същия брой елементи, всички работещи едновременно.
Bubble подреди срещу селекция подреди срещу сливането на сортиране.
>> Сега, всички те са течаща на теория в същото време.
Процесорът работи по най- със същата скорост, но вие
може да се почувства как скучно това е много бързо ще стане,
и колко бързо, когато ние се инжектира малко на седмица
алгоритми нула може да ние ускори нещата.
>> А сега нека да сравни те в един последен форма.
Отивам да се продължи напред към страницата на CS50, където
имаме този последен линк за днес, където някой в ​​интернет
Любезно се сглоби видеоклип, който улавя какво различно сортиране
алгоритми звучи като.
Това е сортиране чрез вмъкване.
>> [Сигнализиращ]
>> Чрез която можете да започнете прилагането на честота въз основа на височината на лентата с бар.
Това е метод на мехурчето.
>> [Ненормален сигнализиращ]
>> Очаквайте следващата is-- пришествие до следващия is-- селекция сортиране,
където отново ни е да изберем следващата по-малка елемент,
и ние можем да видим, че нарастващото от ляво на дясно.
>> Обединяване на сортиране, като по този начин нашият победител далеч днес.
Забележете как се раздели неща в [недоловим] половина и квартали.
Gnome сортиране, която нямаме говори, и създава визуално
и audally малко на различна форма и звук.
Връщайки се назад и напред, почистване на нещата.
Също така проверете пирамидално сортиране на интернет страницата на този човек.
>> И това е.
Ние ще ви видим следващия път.
>> [Свистящ И MUSIC]