>> [Мусиц плаиинг]
>> Давид Ј Малан: Ово је ЦС50.
И то је почетак недеље три.
Дакле, имамо доста узбудљиво ствари да покрије данас.
Много могућности за волонтери на бину.
И на крају, данас је не о коду уопште.
Али ради се о идејама, и ради се о алгоритмима,
и заправо враћање неких од научене лекције из седмице нула,
где опозив, ми увео овај ужас.
И задуживање инспирација од тога, за почетак
да реши све софистициранији Проблеми алгоритмички.
Али прво, пар објава.
Дакле, један, ако желите да се придружите Особље ЦС50 и колеге на ручак
овог петка, и овде и у Кембриџ, ау Нев Хавен,
посетите курс је сајт, где могу да УРЛ адреса може наћи.
Предавање у среду ће неће бити овде у Сандерс.
То ће бити само онлине, тако подесите на сајту ЦС50 је,
да ли овде у Кембриџу или Нев Хавен као добро.
>> А онда Проблем сет два је већ у вашим рукама.
Ако нисте кренуо је још, дозволите ми да понуди оштар предлог
да, посебно сада, као проблем поставља напредак,
ти стварно желите да почнете сада, ако не површно мало на викенд или пре
када су први пут изаћи на Петком, јер ћете
сматрају да нису нужно све дужи или већи изазов по
се.
Мислим да ћете наћи да је, у Генерално, они имају тенденцију да се грубо
приближно истом временском периоду.
Али то свакако зависи на студента, и њега
зависи од менталног склопа са којом прићи.
Али увек, ти ћеш покренути против неком зиду,
и ти ћеш погодити нека буба, а ти си само
неће бити у стању да гет овер ит у неком тренутку.
И то је изузетно вредна да буде у стању на корак даље, врати следећег дана,
идите на радног времена, пост на ЦС50 Дисцусс или слично, да заиста добили деблокиран.
Дакле, имајте то на уму.
Почевши најраније могуће је најбоља ствар коју можете учинити.
Па, ево где смо почели класа, тамо у недељу нула.
И можемо добити волонтера овде да ми помогне да пронађу микрофонима?
ОК.
Стандинг уп већ.
Хајде горе.
Претпостављам да је то како ће радити.
Како се зовеш?
АЛАН ЕСТРАДА Алан Естрада.
Давид Ј Малан Алан Естрада.
Хајде горе.
Драго ми је да смо се упознали.
АЛАН ЕСТРАДА: Драго ми је.
Давид Ј Малан: И ви сте били овде са нама у недељу нула, наравно.
АЛАН ЕСТРАДА: Био сам.
Био сам.
>> Давид Ј Малан: Можете ли да одем напред и наћи за нас Мајк Смит,
као брз као можете!
Као брз као можете.
Буквално цепање проблем на пола као што треба.
>> АЛАН ЕСТРАДА: Хм.
Давид Ј Малан: Дословно цепања проблем на пола.
>> АЛАН ЕСТРАДА: О.
Мм.
Врло добар.
>> Давид Ј Малан: У реду.
Dobro.
Хвала вам.
АЛАН ЕСТРАДА: Врло добро.
ОК.
>> Давид Ј Малан: И сада, ти си га сведено
на половину величини проблема.
Сада смо до једне четвртине.
Да ли обраћате пажњу на на којој страни држимо?
>> [Лаугхинг]
>> АЛАН ЕСТРАДА: Да, мислим--
>> Давид Ј Малан: Који део смо у?
АЛАН ЕСТРАДА: Демистери, тако.
>> Давид Ј Малан: У реду.
Али Мике Смитх иде да се након муффлерс.
Prema tome--
>> [Лаугхинг]
>> У реду.
АЛАН ЕСТРАДА: Где тражимо?
Давид Ј Малан: Мајк Смит.
АЛАН ЕСТРАДА: Мајк Смит.
Давид Ј Малан: Сада смо у хируршки.
Сада, лекари.
Сад--
>> АЛАН ЕСТРАДА: хајде- идемо са стварним.
Реал.
>> Давид Ј Малан Реал.
ОК.
Ако вам је потребна Реал.
Сада, на који начин је Мајк Смит?
>> АЛАН ЕСТРАДА: Овако.
>> Давид Ј Малан: Којим путем?
АЛАН ЕСТРАДА: Чекај.
М је- зар не?
Почели смо са--
>> Давид Ј Малан: Да.
Они отишли.
Ваше право.
>> АЛАН ЕСТРАДА: Да.
>> Давид Ј Малан: Тако је Мајк овде.
АЛАН ЕСТРАДА: Шта?
>> [Лаугхинг]
>> Лош пример, момци.
Извините.
Давид Ј Малан: Ово ће научити да искочи из столице.
>> АЛАН ЕСТРАДА: О.
О.
Имам те.
О.
Ово је-- Ок, имам те.
Смит овде?
>> Давид Ј Малан: Смит, хвала.
Дакле, наставићу да тражим горе Смитх?
>> АЛАН ЕСТРАДА: Ох, да.
Не не не.
О, не.
Ово је моје.
>> Давид Ј Малан: О, имаш Смитх.
ОК.
>> АЛАН ЕСТРАДА: Да, Имам Смитх овде.
Жао ми је, момци.
Мислио сам да смо Мицхаел-- су у потрази за Мицхаел.
Извините.
>> Давид Ј Малан: У реду је.
У реду, сада смо у Паццини и синови.
>> АЛАН ЕСТРАДА: Паццини и синови.
Давид Ј Малан: Само ти и ја смо у овоме.
ОК.
Нађи нам Мике Смитх.
Смит.
>> АЛАН ЕСТРАДА: Смит.
>> Давид Ј Малан: Смит.
Ми смо у истраживање за глупости.
АЛАН ЕСТРАДА: Глупости.
О.
Ово ће потрајати.
>> [Лаугхинг]
Давид Ј Малан: Ципеле.
Ми смо у ципелама.
>> АЛАН ЕСТРАДА: Сада смо гонна--
>> Давид Ј Малан: Лепо.
АЛАН ЕСТРАДА: Вхицх--
[Лаугхинг]
Ох, ово је сјајно.
[Лаугхинг]
>> Давид Ј Малан: У реду је.
>> АЛАН ЕСТРАДА: Ох, ово је добро.
Ја не мислим да ћу имају ПСАТ пријатеље после овога.
Давид Ј Малан: Добро.
Спортска.
АЛАН ЕСТРАДА: Спортска.
Ум, Л, М, Н, О, П.
Давид Ј Малан: У реду.
Дакле, хајде да теар ово на пола.
У реду је.
Ово се завршава лоше у сваком случају, јер Мике Смит неће бити у жутим странама.
>> АЛАН ЕСТРАДА: Ау.
>> Давид Ј Малан: Не, то је у реду.
Али хајде да се претварамо као Он је на овој страни.
Дакле, сада сте сведено проблем доле на једној страни, и нашли смо Мике Смитх.
>> [Цхееринг]
Ок хвала.
ОК.
То је био изванредан.
Али ипак бржи био од линеарног претрагу,
где смо почети на почетку књиге,
и крећемо наш пут с лева на десно, на крају у потрази за Мајк Смит.
И тако, ако именик Имао можда 1.000 страница,
можда би узео УС 10-ак страница сузе.
>> Али можда искористио додирнуо претпоставку
у све то, што ће рећи да је именик унапред је оно?
ПУБЛИКА: Сортед.
Давид Ј Малан: То је средјено.
Jel tako?
То је по абецеди поредани, тако да су сви ови имена и бројева
су поредани од петице до З је, по абецедном реду и између.
Али данас, ми сада питати питање, па,
како је Спринт или телефон Компанија је ући у ту државу?
>> Зато што је једна ствар да искористе та претпоставка, а самим тим,
реши проблем са алгоритам ефикасније.
Али никада нисмо питао у недељу нула, добро,
koliko je koštalo Спринт или неко други
да се ту именик сортиране?
>> Jel tako?
Није битно да ли лоокинг уп Мике Смитх
је супер брзо, ако вам је потребно године за сортирање странице почетку.
Jel tako?
Можда је најбоље да само сејати кроз случајном телефонски именик,
ако ће то бити супер скупо да га сортирају.
Дакле, ако можемо да имамо још један добровољац.
Хајде да погледамо овде у како смо могао-- хајде их-- како
можемо ићи око сортирање њих.
>> А ако Џордан могао стварно придружите нам се овде на бини.
Хајде горе за тренутак.
Како се зовеш?
Царолине: Царолине.
Давид Ј Малан: Каролина, попни се.
И ти ћеш се придружити ја и Јордана овде.
Каролина, хвала.
У реду.
Дакле, оно што смо овде имамо Царолине је 26 плаве књиге
да ФАС користи да управља неке испите.
Они су тешко добити наћи, али оно што смо урадили у унапред
је да смо ставили нечије име на предњој страни сваки од њих,
али смо је држали једноставно од затим стављање ван именом и презименом.
Тако да би ставио особу са именом Л, Д, Ј, Б, скроз А до З,
али они су случајним редоследом.
И тако, ако би, говори твој пут кроз проблем као ти
не то, можете ићи напред и сортирали ове за нас, од А до З.
>> ПУБЛИКА: У реду, па сам је као, средњи.
Ц почиње.
Б. Ј прије Л. Б, П
>> Давид Ј Малан: Држи то Мислио за једну секунду.
Јер у супротном, ово је само занимљиво Ти, ја, и Јордану.
Ево га.
ПУБЛИКА: [неразумљиво].
Р.
Давид Ј Малан: У реду.
Шта радиш?
>> Царолине: П долази после О.
>> Давид Ј Малан: У реду.
>> Царолине: О.
Давид Ј Малан: О Добро.
>> Царолине: Е.
>> Давид Ј Малан: Е Ф. Да.
>> ЦАРОЛИНЕ: Т, У, В.
>> Давид Ј Малан: В, Т, У, В тако да Изгледа као да сте макинг-- настави.
Изгледа да правиш велика гомила овде,
и нека врста велике гомиле тамо.
Дакле, прва половина алфабета, друга половина алфабета.
ОК.
Dobro.
Врста поделе проблем на два дела.
М, Н, Кс Да.
Царолине: К.
Давид Ј Малан: У реду.
К. Дакле, ви врста избора они један за другим,
стављајући га лево или десно, или З иде на поду.
ОК.
>> Царолине: З иде на поду.
>> Давид Ј Малан: У реду.
И је одлазак на поду.
Сада можемо ставити Кс.
>> Царолине: Г.
Давид Ј Малан Г иде лево.
С иде право.
Добро А иде до краја лево.
>> ЦАРОЛИНЕ: А, Б, Ц, Д.
>> Давид Ј Малан: Сада, добро.
Имамо А, Б и Ц, Е иде тамо.
У реду Т.
>> Царолине: Х, И, Ј
Давид Ј Малан: Х, И, Ј Добро.
Царолине: У центру, ја гонна--
Давид Ј Малан: У реду.
Дакле, сада, идемо у натури од споји ове различите гомиле.
Тако А до Ц, онда не видим Д, и Е и Ф, и Г, и Х, и И. Нице.
Ј. К. А онда, ово је гомила наопако, али то је у реду.
Наравно.
Можемо смањити неке углове.
ОК.
И онда морамо В, Кс, И, З
>> Царолине: Да.
>> Давид Ј Малан: Одлично.
Дакле, велико хвала Каролина за сортирање њих.
>> [Цхееринг]
>> Хвала вам.
Много вам хвала.
Дакле, хајде да размотримо на тренутак Како Каролина је о то ради,
и шта смо су могли да-- како
су могли да ријешити проблем када смо били
с обзиром гомила случајних улаза.
>> Па, изгледа као да био помало система тамо?
Jel tako.
Тако ранијим писмима у писму, она
је стављање на лево, а касније слова у алфабету,
она је стављање у право.
И чим је сазнала нека Проксимални писма, оне
да иду право једни поред других, она би ставио оне у реду.
И тако смо некако имали ових малих гомиле издвојених улаза јављају.
>> И то је сасвим као што већина од нас људи ће учинити.
Ми бисмо некако да претура по њој, и да ћемо некако да има механизам.
Али, можда би било тешко написати Ит Довн у формули по себи.
Било је мало више органски од тога.
Дакле, хајде да видимо да ли можемо сада да веже Проблем са мање улаза.
>> Уместо 26, хајдемо уради нешто далеко мање
са само реци, седам, иза ова врата, да тако кажем.
Да ли постоје само седам бројева?
А ако је циљ сада на рука је да пронађе неку вредност,
хајде да видимо колико ефикасно можемо ићи око овога.
И да видимо да ли сада можемо почну да примењују неке бројеве,
или неке формуле са којима описује ефикасност нашег телефонског именика
алгоритам, наш испит књига алгоритам, и генерално, проналажење информација.
>> Дакле, за ово, пусти ме само напред, и на екрану осетљивом на додир овамо,
водство на веб бровсер који има управо ових седам врата.
И ако бисмо могли да добијемо један други добровољно да дођу овамо,
Ставио сам те исте врата овде.
Брзо волонтер.
>> Овај Један-- Демос иду да бржи и бржи сада.
Хајде доле.
Како се зовеш?
Тревор Тревор.
>> Давид Ј Малан Тревор?
У реду, Тревор, хајде доле.
Дакле, Тревор је овде добровољно раде сличан проблем, али то је
ужи у обиму, и да ће да нам омогућити да покушамо да сада формализује
процес за сортирање ове бројеве.
>> Тако Тревор, драго ми је.
Дакле, овде је низ, тако да говоре, списак седам врата.
Само напред и наћи нам број 50.
А онда након тога, реците нам како сте га нашли.
Ако бити-- добро.
Да, ово је овдје?
Ух.
ОК.
Кликнули сте ту.
Dobro.
>> И добро.
Сада сте кликнули ту.
И да ти дам микрофон, тако да га за тренутак.
Само напред и кликните на Нект Доор да намеравате.
Да добро.
Тревор: Могу ли унцлицк врата?
Давид Ј Малан: Не, не можеш унцлицк.
Тревор: У реду.
Овај.
Давид Ј Малан: Где желиш да идеш?
Који?
>> Тревор: Онај.
>> Давид Ј Малан: Не
>> Тревор: У реду.
Овај.
>> Давид Ј Малан: Да.
То је било добро.
У реду.
Дакле, шта је био ваш алгоритам или Поступак за ово, Тревор?
>> Тревор: Прошла сам кроз врата док нисам нашао 50.
Давид Ј Малан: У реду.
Одлично алгоритам.
Дакле, то је у реду.
Јер, у ствари, ако сам открио шта је иза ова два друга врата, што
ћемо наћи овде је да имамо само случајни улаз.
Дакле, то је заправо као добра као што сте могли добити.
А у ствари, имаш боље од исцрпно претраживање читав низ,
јер би било стварно несрећан ако је погодио број
50 на последњем врата.
Али шта ако уместо Дао сам ти претпоставку.
Претпостављам да врста сви ова врата, око
тако да имају Бројеви поредани овај пут,
али овај пут то је заправо дифферент-- овај пут,
то је заправо поредани за вас.
И сада циљ на дохват руке је погодити број 50.
>> Тревор: У реду.
>> Давид Ј Малан: Шта је Ваш алгоритам ће бити?
>> Тревор: Па, ако је то поредани, то је било иде
да бити-- ако највећи у величини, опадајући, то ће бити први,
или ако је супротно, то ће бити последњи.
Дакле, ја ћу додирните врата, и онда само додирните Задња врата.
Давид Ј Малан: Одлично.
У реду.
Дакле, пронашли смо бројне 50.
Дакле, чим сте знали су поредани ми
били у стању да искористе ову претпоставку.
Дакле, они су превише слично телефонски именик пример.
Чим имате, чак и са мали проблем овако,
Ваши улази пре-поредани, можемо заправо наћи вредност вероватно
ефикасније.
>> И нисам те да је било реци поредани мали да би велики, велики или малим,
па то је врло разумно да почну на једном крају или друга
да заправо пронаћи ту циљну вредност.
Дакле, хвала на Тревор као добро.
А ја ћу пропосе-- лепо урађено.
Имамо мало снимак, заправо, да је међу нашим омиљеним тренуцима ЦС50,
при чему понекад Те демонстрације не баш иде по плану.
И заиста сада, ја извукао погрешан интерфејс
са којима се користи екран осетљив на додир.
Дакле, то је било моја кривица.
>> Тако ће ово бити за наредну годину снимак као
зашто сам што ћете кликнути на свом екрану.
Али хајде да кратак поглед ста се десило прошле године
са Јаи, који је појавио, много као Тревор овде, добровољно,
и у овом кратком снимку, видећете како то исто није баш Демо
откривају исте лекције научене.
[ВИДЕО РЕПРОДУКЦИЈА]
-У Желим да урадите сада је да пронађе за мене, и за нас,
Заиста, број 50 један корак у исто време.
>> -Број 50?
>> -Број 50.
И ви можете открити шта је иза сваке ових врата
једноставним додиром га прстом.
Проклетство.
>> [Лаугхинг]
>> [Крај репродукције]
Давид Ј Малан: Тако да је врло добро.
То су Унсортед врата.
И Јаи, наравно, открила да је пребрзо.
Тревор урадио много бољи посао у смислу спремно да учи тренутка,
да тако кажем, ове године траје дуже да га нађем.
Наравно, тада смо дали Џеј друга шанса,
чиме смо поредани врата, као што смо урадили за Тревор,
и Тревор урадио супер и овај пут.
Али Џеј је то учинио упола брзо.
[ВИДЕО РЕПРОДУКЦИЈА]
-У Циљ сада је да се Пронађите нас на број 50,
али то алгоритмички, и реците нам како ћеш о томе.
>> -ОК.
>> А ако сте га наћи, стално филм.
Ако не нађемо, ви га вратити.
>> -Ман.
>> Ох!
>> - [Неразумљиво] У реду.
Зато ћу да проверим крајеве Прво да утврдимо да ли је-- О.
>> [АППЛАУСЕ]
>> [Крај репродукције]
Давид Ј Малан: У реду.
Дакле, сортирање врата јасно доводи до веће ефикасности.
И тако, дупло брже је оно што сам тамо мислио.
И тако Џеј посрећило оба пута.
И он је такође посрећило у тај последњи године, наредио сам неке Блу-раи дискова
да заиста дају.
Жао ми је ове године смо није имао исти, Тревор.
Али ипак боље да је пре неколико година.
А неки од вас можда знају момак, Шон, који је док је био у ЦС50,
је оспорио са тачан исти проблем, иако у СД,
као што ћете ускоро видети, назад у дан.
И видећете да не само да узме мало дуже него што Јаи,
мало дуже него што Тревор, било је Заправо ово дивна прилика
да се ангажује скоро сви у Публика ла Прице ис Ригхт, подстицање
да нађе број смо тражи.
Омогућава. узети кратак поглед.
>> [ВИДЕО РЕПРОДУКЦИЈА]
>> -ОК.
Дакле, ваш задатак овде, Шон је следећи.
Ја сам крије иза ове врата број седам.
Али, ушушкан у неким од ових врата као и друге негативне бројеве су.
И ваш циљ је да мисли ове горњем реду бројева
као само низ, или само Редослед комада папира
са бројевима иза њих.
И ваш циљ је, користећи само врх Арраи овде, нађи ми број седам.
И ми смо онда да критикује како се то ради ради.
-У реду.
-Финд Нам број седам, молим те.
Ne.
Пет, 19, 13.
>> [Лаугхинг]
>> То није трик питање.
Један.
>> [Лаугхинг]
У овом тренутку, ваш резултат није много добро, тако да ћете можда и настави.
Три.
>> [Лаугхинг]
>> Настави.
Искрено, ја не могу да се не запитам шта још размишљате о, па--
>> [Лаугхинг]
Само горњи ред, па Имаш три лево.
Дакле, ми наћи седам.
>> [Лаугхинг]
17.
Седам.
>> [АППЛАУСЕ]
>> У реду.
>> [Крај репродукције]
>> Давид Ј Малан: Тако смо могли ватцх ово цео дан.
И Наравно, неки од овогодишњи демонстрације можда
Сада ће завршити у наредном Овогодишњи видео као добро.
Дакле, сада нека ствари фокусирати на алгоритмима
овде, и види да ли не можемо сада почети да озваничи
Како можемо ићи око добијања нашим подацима у том стању да то поредани,
тако да на крају, можемо да тражење то ефикасније.
И иако ћемо користити прилично мале скупове података,
као и осам бројева и ми имам овде на табли,
на крају те исте идеје могу да се пријаве 1.000 улаза, милион улаза,
4 милијарде улаза, јер алгоритама ће бити у основи исти.
>> И то је наша задња прилика за волонтере данас,
али можда највише укључени један, за које је потребно осам волонтера
да дођу до нас и ходати кроз Процес сортирања што ће ускоро
бити на овим музику стоји овде.
Дозволите ми да почнем овде.
>> Дакле, један у зеленој туркуоисе-- је то?
Да ли је починио?
Два.
Хајде доле.
ОК.
Три.
Четири.
Нека ми-- реду, пет.
Ти си се именује свог пријатеља.
Шест, седам, осам и.
Хајде горе.
У реду.
Хвала Вам много.
Хајде горе.
>> У реду.
Дакле, оно што овде-- и ово има је међу више незгодних оне,
јер ће захтевати да хумор ја за само мало времена.
Ти ћеш бити број један.
Како се зовеш?
>> Анан: Анан.
>> Давид Ј Малан: Анан.
Дејвид.
Како се зовеш?
>> Јосепх Јосепх.
>> Давид Ј Малан Јосепх, ти си број два.
>> Серена: Серена број три.
Стефана, број четири.
ЦИНТХИА: Синтија.
Давид Ј Малан: Синтија, број пет.
[Неразумљиво]
ДАВИД Ј. Малан: [неразумљиво].
Давиде, број шест.
Матт Матт.
Давид Ј Малан: Матт број седам.
И?
>> ВАВЕРЛИ: Ваверли.
>> Давид Ј Малан: Ваверли, број осам.
У реду.
Ако могли-- Упс.
Ако вам се све, као твој Први изазов, ту
осам Мусиц Стандс овде пред публику.
Ако бисте могли да ставите бројеве ових музичких стоји на такав начин
да се построје са Исти бројеви на табли.
Дакле, сами себе изгледа као да је стављајући своје бројеве на овим музике
стоји овде.
Одлично до сада.
>> Одлично.
ОК.
Дакле, сада ћемо да питам питање у неколико различитих начина.
Како можемо ићи око сортирање ови људи овде?
Зато што смо имали неколико приступа раније, при чему смо били
врста израде два различита кашике.
И онда смо углавном били пиецинг ствари заједно.
Чим смо видели два броја који је припадао заједно,
смо их заједно.
Два слова која припадају заједно.
>> Али хајде да видимо да ли можемо Не могу да формализује ово,
тако да смо на крају имамо нека псеудо код хоћеш,
са којима можете решити ове проблеме.
Дакле, сада тражим од на овим бројевима овде.
И видим гомилу грешака.
На крају, желим један на лево и осам са десне стране.
>> И тако гледам ова два, четири и два.
А шта је проблем, очигледно?
Да.
Prema tome.
Два очигледно долази пре четири, тако да знате шта?
Дозволите ми прво да похлепан приступ, ако хоћете, баш као и проблема
сет једног-- ако се сећате из Стандардна издање Проблем Сет Оне,
где сам само на локалном нивоу реши проблем То је право испред мене
и види где ме води.
>> ОК.
Дакле, два и четири, пусти ме напред и само вас двоје замене.
Ако сте физички могу да се померим ви и ваш лист,
Чини ми се да имају стечен лист у бољем стању.
>> Сада, они су добри.
Идем да идемо даље, четири и шест, изгледа добро.
Није проблем.
Шест и осам, у реду.
Осам и један, још један проблем.
Јер оно што је истина о осам и један?
Један долази пре осам, па шта да радимо?
Хајде да заменимо ово двоје.
Један и осам.
И сада, ја ћу да наставим.
Идем да настави да гледаш напред.
И хајде да видимо шта се дешава.
Осам и три, од Наравно, не ради.
Идемо свап.
Осам и седам, наравно.
Неисправно.
Идемо свап.
Осам и пет, наравно, идемо замена.
У реду.
Листа је сортирана.
Да?
>> У реду, очигледно није.
Али то је мало боље, зар не?
Јер, обавештење шта се десило.
Сваки пут смо обавили замену, мањи број врста исфилтрирала на тај начин,
и већи број исфилтрирала на овај начин, или ћемо
поцео да говорим у мехурићима до лево или на десно барботира.
>> Дакле, то није довољно, јер у најбољем случају број могао
су се преселили на друго место напред, или у најгорем случају,
број можда има преселио једно место даље.
Знаш шта, ова врста од је прилично добро до сада.
Дозволите ми да пробамо поново.
Два и четири, они су у реду.
Четири и шест, они су у реду.
Шест и један, од реда.
Дакле, хајде да вас двоје замене.
А сада, приметите да је проблем Почињем да поново боље да се мало.
Шест и три, од реда.
Да те две замене.
Шест и седам, ти си добар.
Седам и пет, наравно, не ради.
Седам и осам, у реду.
И сада, можда ћете морати да ово још неколико пута.
И, у ствари, мислим за себе можда колико пута максимално
Можда морам да ходам напред и назад?
>> Вратићемо се на то.
Дакле, два и четири су још увек у реду.
Четири и један, не.
Дакле, хајде да свап.
И опет, приметити визуелно једна је врста продувавању
на лево, где треба да буде.
Четири и три замена.
Четири и шест.
Шест и пет замена.
Шест и седам.
Седам и осам су добри.
>> Dobro.
Ми смо се још боље.
Па да видимо.
Сада имамо два и један.
Наравно, замене.
Два и три, три и четири, четири и пет, шест и седам, седам и осам.
Dobro.
И знате шта?
Зато сам направио ту једну промену, пусти ме да један исправности проверу.
Пусти ме скроз назад на почетак.
ОК.
Један, два Аха, видиш?
Нешто није било у реду.
Три, четири, пет, шест, седам, осам.
А у овом последњем пролазу, су сте удобно са мојим сада
тврдећи да је поредани?
ОК.
Визуелно, то је апсолутно тачно.
Али шта функционално, да ли је управо десити
У том последњем пролазу који вам омогућује да потврди да је ова листа је заиста
поредани?
>> Оно што сам урадио, или не овај последњи пас?
ПУБЛИКА: Није било никаквих промена.
Давид Ј Малан: Молим?
ПУБЛИКА: Нема промена.
Давид Ј Малан: Није било никаквих промена.
Дакле, било би глупо од мене да Урадите то исто алгоритам поново
ако нисам направио ниједан мења први пут.
А држава се није променило.
Наравно, нећу да свака мења други пут.
И тако, то је сигурно сада да кажем, Листа је сортирана.
>> И заиста, ово је сада нешто што ћу генерално
Позив балон врста, при чему паровима, сте исправили грешке опет,
и опет, и опет, ти и наставити напред и назад,
и напред и назад, вас до да нема такве размене, на којој тачки
можете бити сигурни, да, завршио фиксирање све грешке.
Идемо ресет и другачији приступ.
Ако ви могли да се вратимо у редослед си малопре,
који је изгледао овако.
Сада, узмимо приступ, мало више као испит књиге,
чиме смо стално били одабир слово алфабета
да сам хтела да се баве следећи.
Можда је то био висок писмо, као А, или ниска слова З.
>> Дакле, сви су поново у овој наредби.
И сада пусти ме да радим ово.
Да видимо Знам да имам осам бројева овде.
Ја идем напред и само намерно изабрали
најмањи елементи.
Jel tako?
Ово изгледа интуитивно превише.
Зашто не налазе да је најмања елеменат, ставите га тамо где припада,
онда се следећи најмањи елемент, пут то где и припада, и само поновити.
>> Зато што интуитивно, који би требало да превише раде.
Дакле четири, то је прилично мали број.
Идем да се сетим где је то.
Сачекај минут.
Два мања.
Дозволите ми сада да се сетим где су две је, и заборавити четири.
Ми ћемо се бавити касније.
Шест, нисам заинтересован.
Осам, нисам интересују.
Један је мој нови мали број.
Зато ћу да се сетим где је.
Три, не занима ме.
Седам, не занима ме.
Пет, није заинтересован.
>> Дакле, без пада са бина ове године,
Идем да узмем број једног-- и оно што је зовеш?
>> Анан: Анан.
>> Давид Ј Малан: Анан.
И ако бисте могли да ми се придружите у почетак листе,
Хајде да те ставимо где ти је место.
Унфортунатели-- како се зовеш?
>> Стефан Стефан.
>> Давид Ј Малан: Стефан је на путу.
Дакле, пре него Стефан решава ово Проблем је, шта да радимо?
Шта да радимо са Стефаном?
>> ПУБЛИКА: [неразумљиво].
Давид Ј Малан: У реду.
Дакле, могли бисмо то да урадим.
Могли бисмо на неки начин преузме Стефана и његовог четири, и само ставите га у променљивој
и држите на томе одређена количина времена,
чиме простор за број један.
И то није лоше.
Ја може предложити, зашто не Управо смо ставили Стефан овде?
Зашто би ово могло нарушити један идеја смо почели
говоримо о последње време, прошле недеље?
Да?
>> ПУБЛИКА: [неразумљиво].
>> Давид Ј Малан: Нема индекс за њега.
Ако мислите да ово, заиста, као Арраи, ово је као негативан,
тако да нема меморије заправо Овде ако је ово заиста низ,
Као да је прошле недеље у предавању.
Дакле, не треба да урадимо ово.
Могли бисмо га сачувате у променљивој.
>> Или знаш шта?
Чуо сам неко други то указују.
Шта смо друго могли да урадимо са Стефаном?
Зашто не бисмо га избаци и стави га тамо где је био број један.
Дакле, ако желите да одете тамо.
И заиста, ово је прилично добро решење.
Сада са једне стране, некако сам од направила проблем још горе.
Четири је сада удаљенији одакле би требало да буде.
То би требало да буде према овом полувремену.
>> Али знаш шта?
То је могао бити лоша срећа.
Можда број осам је био овде.
И тако, можда бисмо су постале среће,
и гурнуо осам ближе крају.
Дакле, на крају дана, Некако све просек од.
Ми не треба да брину око четири.
Све ми је стало сада је одабир најмањи елемент.
>> И сад, шта ћу урадите је заборавити број један
трајно, јер знам да је Листа иза мене је сада поредани.
Дакле, моја листа је претходно био величине осам.
Сада је величине седам.
Дакле, мој проблем постаје мањи, мада линеарно.
Дакле, сада ћу да одаберете тренутна најмањи елемент, два.
Шест, осам, четири, три, седам, пет.
То је био најмањи елемент.
Па шта ја да радим са-- шта је зовеш?
>> Јосепх Јосепх.
>> Давид Ј Малан: Џозеф?
Ми ћемо оставити Јосепха на месту.
Сада ћу да се претварам да ови момци су-- добро,
Знам да ово двоје већ поредани.
Идемо сада фокусирати на Остатак листе.
Шест је тренутно најмањи.
Осам је већи.
Четири је сада актуелна најмањи.
Три је сада актуелна најмањи.
И сада ћу да изаберете три, ко је- шта је оно зовеш?
Серена: Серена.
Давид Ј Малан Серена, ако можеш зграбите број и свап са--
КАЛСАНГ: Калсанг.
Давид Ј Малан: Калсанг.
Врати се назад, и ми смо да замени ону двојицу.
А сада, хајде да стави ово на аутопилоту.
Ја ћу да одем и оставим га да вас да бисте изабрали следеће најситније елементе.
Дун, Дун Дун Дун.
Број четири, шта би требало да урадите?
Одлично.
Сада ћу направити још један пас.
Дун, Дун Дун Дун.
Видим пет је следећи најмањи.
Сада, ја ћу узети још један пас.
Дун, Дун Дун Дун.
Шест је најмањи.
Dobro.
Седам је најмањи.
Нема промене.
Осам је најмањи.
Готово.
>> Дакле, шта смо урадили од итеративно одабере један елемент за другим
се спроведе нешто што смо ми да формализује као избор врсте.
И можда је чак једноставније да објасни,
у да су буквално све вас Желим да урадите је да само настави
иде напред и назад кроз листу избора, следећи најмањи елемент,
док не завршите.
>> Дакле, то је још једноставније, можда интуитивно, него прошле.
Хајде да пробамо један последњи.
Ако ви могли сами ресет у следећим позицијама
један последњи пут, да видимо ако не можемо Сада формализује један други приступ.
У ствари, би неко тамо бих да предложи
Како другачије можемо ићи око радиш то?
Без бацање од Буззвордс или врсту одговора који су већ познати,
само интуитивно, шта можемо да урадимо?
>> ПУБЛИКА: [неразумљиво].
Давид Ј Малан: Да.
Тако да је изврсном интуиција тамо.
Добре ствари ми се дешавају до сада у компјутерској науци, када ми делимо
и освоји проблем поделе је на пола и пола-пола.
И тако заиста ми могао почети да то уради.
У ствари, то ће бити, ми ћемо види, један од наших најбољих решења још.
Али хајде да се вратимо на то убрзо.
У ствари, идемо да радимо да мало касније ове недеље.
Шта друго може да урадимо да решимо ово?
Дакле, сви овде у наизглед случајним редоследом.
Знаш шта?
Уместо иду напред и назад, напред и назад, напред и назад
сваки пут, ово изгледа као Радим пуно ходања.
Зашто не бих се крећу од почетак листе,
и само ставити четири тамо где и припада?
Дакле, дозволите ми да претпоставимо за тренутак да мој списак је само ово први елемент.
Да ли је четири поредани у овом тренутку, ако је све стало је све овде?
Ово је врста тривијално тачно, зар не?
Као листе која садржи један број, и тај број четири је очигледно поредани.
>> Дакле, дозволите ми само прописује да је ова листа сортирана.
Али сада имам остатак ове листе.
Дакле, сада, ја сусрести два.
Где се два очигледно припада у вези са четири?
Пре четири.
Дакле, шта могу да урадим овде?
Како се зовеш?
>> Јосепх Јосепх.
>> Давид Ј Малан Јосепх, ако би корак уназад
за тренутак са вашим бројем.
И шта сада треба Штефан ради овде?
Да схифт Стефана овде.
И сада, нека Џозеф овамо.
А сада, дозволите ми да тврде да све овде се разврстава.
Дакле, сличан резултат, али фундаментално другачији приступ.
Нисам ни гледао шта је тамо доле.
Стално узимање елементе као они предали мени,
и баве се њима.
>> Дакле, сада видим број шест.
Одакле број шест припада?
Имамо два, четири, шест.
Тачно где је сада.
Дакле, оставимо то на миру, и сада тврде да овај део списка
сада поредани.
И тако, то се осећа у основи разликује по томе сам само
креће кроз листу овде линеарно, а ја никада удвостручење назад.
Да.
У реду.
Дакле осам, где ти припадаш?
Баш овде.
Савршен.
Тако сада један.
Ух.
То се осећа као да је Биће скупо.
Сада, у претходном алгоритма, Само заменили људе.
Могла бих га ставио скроз на почетак, а онда се преселио Јосифа.
Али, ако се преселим Јосепх, сада шта ће бити у реду?
>> Сада, ја сам некако ундоне-- имам узети један корак напред и онда
један корак уназад, јер сада Џозеф би бити ван реда.
Па хајде да урадимо то.
Ако сте могли да број један и корак назад за тренутак.
Како можемо пут-- шта је опет твоје име?
>> Анан: Анан.
>> Давид Ј Малан: Анан на месту?
Шта треба да се деси у вези на два, четири, шест, осам и?
Сви они треба да пређу.
Дакле, ако осам бих да помера прво, а затим шест, па четири, па два.
А онда Анан, ако бих воле да долазе овде, добро.
Али овде, управо врста платио цену
на другом тачки у алгоритму.
Док задњи пут са селекцијом врста, па чак и балон врста,
Ходам уназад и напред, напред и назад,
што је свакако додаје до Временски гледано, и буквално постепено.
>> Убацивање врста, на први поглед поглед, изгледа као да је
Супер паметнији, у томе сам само споро, постепен напредак,
али нећу ово напред-назад.
Али, ако неко заиста из реда, обавештења
сав посао сам морао да урадим.
Морао сам да се пола листе само да би се направио простор за број један.
Дакле, то је исти износ рада тако да је сада
осећа, само другачија врста посла.
>> Идемо даље.
Дакле, сада знамо да свако између једне и осам су поредани.
Ево, ја имам број три.
Ако желите да покупи број три, корак уназад један.
А шта ви треба да урадите?
Да.
Дакле, то је још један, два, три корака.
Три јединице времена које коштају само ми, тако да сада може да стане три.
На крају, седам.
>> Идемо напред, узмете корак уназад.
Ово ће само да нас кошта једна јединица времена, али то је у реду.
И сада, пет иде у бити мало скупљи.
Ако желите да се вратите корак.
Морамо да кренемо осам, и седам и шест.
А онда сви сада поредани.
Тако велика рука наших волонтера овде.
Хвала Вам много.
>> [АППЛАУСЕ]
>> Хвала вам свима.
Хвала вам свима.
Дакле, хајде да сада колико видим скупе све је то било.
Хајде да можда размотри Најједноставнији од њих, балон врста.
И ја кажем најједноставније, само зато можете га решити за само похлепно
решили проблем паровима овде.
Поправите Паирвисе проблем Овде, изнова и изнова
и опет, понавља колико пута колико заправо треба.
>> Тако испада да са буббле врсте, добро,
колико корака морам да преузму Први пролаз тог алгоритма?
Можда таке-- идемо видим-- један, два, три, четири, пет, шест, седам.
А ту је осам елемената овде.
Дакле, то је као н минус 1 корака до добити од почетка листе
до краја листе.
>> Али са избором врсте, сећам се да сам изнова и изнова одабир елемената
и опет то је најмањи, Ја га стављам у месту,
али онда нисам гледајући иза мене поново.
Зато мислим да је мало јасније онда је први пут, могао бих
морати да предузме све кораке н минус 1 да пронађе најмањи елемент.
Онда сам их ставио на месту, и ја избаци ко је био овде раније.
>> Али онда не морам да стално гледајући овај елемент,
јер знам да је Већ најмањи.
Дакле, сада могу да гледам само седам елементи, затим шест елемената,
затим пет елемената, затим четири елемента.
И тако математички, ако је н број елемената или бројева
да смо почели са, можете замислити да је то исто као Н минус 1,
Плус Н минус 2 корака, Плус Н минус 3 корака,
плус минус 4 Н корака, све доле до само једном кораку.
И ја сам на мојој особи.
>> А ако се сећате да је доста од протокол књиге или математике књиге
имам те формуле на Папербацк назад или испред њих,
испада да ове серије може да се изрази једноставније
као н пута н минус 1 преко 2.
И то је у реду ако то није на челу вашег ума.
Али ово је заиста истина.
То је само једноставнији начин да се то писања.
А онда, ако мислите назад у основној школи,
када почнете да се помножи ствари, то наравно,
је само н на квадрат минус н подијељена 2.
Све што сам урадио је проширити изрази тамо.
И тако ћемо преписати ово мало другачије.
То је н квадрат подељеној 2 минус н / 2.
>> Па опет, ја сам некако примене нека аритметичка правила постоје.
Али приметите сада да је највећи израз У овом изразу, да тако кажем,
је то н квадрат.
Тако да, то је н квадрат подељено са 2, минус н / 2.
>> Али, генерално, ако је н Биће то велика вредност,
Идем да тврде да је н квадрат ће бити доминантан фактор.
Само ће бити већи допринос
на број корака него н / 2.
Па шта мислим под овим?
Хајде да пробамо једноставан пример, чак и иако је математика добија Литтле биг.
>> Претпостављам да имамо 1 милион људи на сцени, или 1 милион ствари
да желимо да средим.
Хајде да прикључите милиона у управо те формуле
да видимо колико корака је потребно укупно за сортирање милион елементе помоћу рецимо,
Избор врста.
>> Тако ћемо имати исту формулу као и раније.
Ја бих плуг милион, тако да сам се милион квадрат подељеној 2,
минус милиона подељено са 2.
Ако то урадим математику унапред Овде имамо 500 милијарди
минус 500,000, која даје нам 499.999.500.000,
што је прилично проклето велика.
>> У ствари, ако сад упоредите 499 милијарди, 999 милиона,
500.000 против нашег оригиналне вредности, 500 милијарди, то је тако проклето близу.
Jel tako? Н квадрат подељеној 2 даје нас-- односно н на квадрат подељеној 2
Дао нам је 500 милијарди долара.
То је проклето близу прилично да 499,999,500,000,
што ће рећи одузимањем са 500.000, или уопште, одузимањем са
Н квадрат, не баш велику ствар.
Н квадрат чини ово Бројеви расте врло брзо.
>> Дакле, ово је једино важно утолико као и ми, као и компјутерских научника,
се генерално неће толико стало о нијансама ових формула
и управо оно што је прецизни одговори су.
Ми само да је стало, знате шта?
На крају крајева, ова формула је реда од н на квадрат.
>> Да, ми смо дељењем са 2 унутра.
Да, ми смо сваки пут одузмемо н минус 2.
Али на крају дана, термин који нас заиста боли и кошта нас
много корака је да квадрат термин.
И шта рачунар научник ће генерално урадити
је игнорисати све оне мање услови ордер,
и само погледај оног који доприноси највише на цену.
>> И ово је лепо, јер можемо сада говорити у много већој општости
о алгоритмима, и да их упореди.
И чињеница да сам Коришћењем овог О је намерна.
Када кажем по налогу од, ја конкретно сам
који се односи на нешто позвао велики О. и Биг О
је нотација која рачунар научник користи да опише
горња граница на нешто.
>> Дакле, ако ви кажете да је алгоритам је у великој Ø Н квадрат,
као што сам предложио само малочас, то значи
да у смислу његовог трчања време или његова ефикасност,
траје реда од н на квадрат кораке.
Можда и више, можда и мање.
Али то је по наређењу н на квадрат.
И то је горња граница.
То неће бити болније од тога.
Неће бити Н коцки или 2 на Н или нешто много веће.
Ово је горња граница на шта год да је трошак.
Дакле, с обзиром да је, хајдемо размотрити само неколико примера.
И ово је само коначан списак веома уобичајене руннинг пута
за алгоритмима који је суђено илустрација неке ствари које смо
већ видели.
>> Тако, на пример, у случај Избор врста, шта ја овде тврдим
је трчање да је избор некако је Сада је на ред н на квадрат.
У најгорем случају, ја ћу имати гомила случајних бројева овде.
И као што смо видели математички, ако кееп валкинг
кроз листу, кроз листа, избором следећи најмањи
елеменат опет и опет, ако И заправо запишите све кораке
Узимам као што сам предложио формулаицалли пре, то је по налогу н квадрат
кораци које узимам.
>> И Испоставило се да мехур сортирају и уметање врста
су исто тако спори у најгорем случају.
Узмимо, на пример, уметање врста, је последња алгоритам смо се бавили,
која је погледајмо елемента, а затим га убаците тамо где припада.
А онда смо гледали следећег елемента, и убаци га тамо где припада.
>> Дакле, сматрам најбољи могући сценарио.
Претпоставимо да су ми добровољци построје дословно овако, један преко осам,
Већ поредани.
Колико корака је убацивање врста ће узети за сортирање осам људи,
ако стигну на сцени изгледају овако?
>> Осам људи је већ поредани.
И ја користим уметање врсту.
Ово последње алгоритама.
Па, хајде да реенацт веома брзо.
Дакле, ако сам овде почети, ја видим.
Где да припада?
Она припада овде.
Видим два.
Где се двоје припада?
Баш овде.
Видим три.
Одакле три припадају?
Баш овде.
>> Видим четири.
Баш овде.
Пет, шест, седам, осам.
Нема разлога да се понављам.
И тако, колико корака је да је у смислу н?
То је по налогу н кораци, зар не? Н минус 1.
Али сам узео линеарни број корака, а сада сам готов.
Дакле, то је најбољи случај.
Шта најгорем случају?
Шта осам су били тамо, а седам су били тамо,
и један и два су овде, тако да се на списку су заиста обрнута?
>> Па, шта се дешава заиста ако је ово број?
И ми ћемо учинити само пар примера.
Шта ако, заиста, број осам је овде, а нумбер-- упс.
Па шта ако, заиста, број осам је скроз овде,
и ја користим уметања врсту?
>> ОК.
Тврдим у овом тренутку то је на месту.
Али сада, севен-- гдје седам иде?
Наравно, то иде овамо.
Зато морам да се селим осам више од једном месту.
Сада шест, где то иде?
Па, добро.
Сада, морам да се креће преко осам место, и седам више места,
и онда бућ доле шест.
>> Дакле, први пут, то кошта ја један корак да поправим ствари,
онда ме је коштала два корака да поправи ствари.
Колико корака је ће узети да поправи
ствари које треба ставити пет на правом месту?
Три.
Зато сада морам да померите један, два, три.
Колико корака ће то узети ставити четири на правом месту?
4 плус 5 плус 6 плус 7.
>> И тако је математички идентична оно што је описано за избор врсте.
Ми имамо ову серију то је само расте.
1 плус 2 плус 3, плус 4, или обрнуто, 7 плус 6
плус 5 плус 4 додаје се у данашње сврхе за по налогу н на квадрат.
>> Па да и ја то прописано балон врста је такође у Н квадрат.
Јер са буббле сорт, сваки Време идем кроз листу,
Водим отприлике колико корака?
Сваки пут када сам буквално хода одатле тамо?
Око н кораци.
Али колико пута сам могао Морам да идем кроз листу?
>> Па, отприлике н време.
Можда н минус 1, али отприлике н пута.
Па, зашто је то тако?
Па, са буббле сорт, ако почнемо са буббле сорт,
са листе у најгори могући Ситуација, која је опет потпуно
уназад, шта ће се десити?
Идем кроз листу, и број припада скроз тамо.
>> Али са буббле врсте, колико ради један прећи на мом првом пролазу кроз листу?
Колико места он добија ближе правом месту?
Само један.
Дакле, ако вас нека од разлога кроз ово, сваки пут кроз овај алгоритам,
Давидове узимају око н корака.
Али колико пролази кроз листу да је
да се за један до буббле на левој страни где и припада?
>> Има да се креће као, н простори овај начин.
Дакле, само да урадим сортирање листе, Морам да хода напред и назад н пута.
И сваки пут, ја сам гледајући н елемената.
И ја н Тхингс н пута на редослед н на квадрат.
>> Сада ћемо видети у неким од шорц који
су уграђени у следећем проблему ЦС50 је сет, други приступ у њих,
али за сада, хајде да размотримо неке друге Руннинг Тимес,
нарочито ако оне за сортирање се мало времена да у потонути.
Шта је алгоритам који смо већ видели која се по налогу н корака?
>> Шта треба да линеарни број корака које смо видели до сада?
Шта је ово?
Потрага телефонски именик.
Први алгоритам.
Jel tako?
Где смо ми линеарно потрази за Мајк Смит?
Заиста.
Од недеље нула, када сам почео окрећући једну страну у исто време,
и чак сам рекао да је то нека је линеарног осећај алгоритма,
и ми смо имали ту слику на плоча са правом црвеном линијом
и право жута линија, они су заиста
алгоритми који су у великом О н.
>> Јер, да пронађе Мајк Смит у телефону Књига н странице, у најгорем случају,
Можда ме н кораке предузети.
Шта о томе да присуство?
Један два три четири пет шест.
Шта је ово време ради алгоритам за полагање присуство?
Велико О од н, јер у теорији сам треба да укаже све у соби.
>> Сада као на страну, шта о други оптимизација из седмице нула?
Два, четири, шест, осам, 10, 12.
Компјутерски научник би схватити, чекај мало,
То је по налогу н подељен два корака.
Jel tako?
Зато што радим двоје људи истовремено.
Али ми ћемо да игноришемо те ниже услови ордер,
а ми ћемо само да баците поделу за 2,
и само да кажем, Биг О од н за тај алгоритам као.
>> Ста је са овим?
Ми ћемо прескочити неке од њих, али оно што Била је алгоритам који је дневник н?
Који су грубо лог н кораке?
Ова подела па владај.
Baš tako.
Као телефонског именика пример у недеља нула и раније данас,
где смо подељени проблем опет и опет и опет.
Ми нацртао је на броду у недељу нула као закривљене зеленом линијом,
и рекли смо да је то дан био логаритамска алгоритам.
>> И заиста, број ИТ корака потребно да се изврши завади па владај,
или бинарна претрага као што ћемо почети назвавши га, као у телефонском именику,
је на налогу дневника и корака.
И ово је помало чудан један.
>> Оно што траје један корак, или још специфичније
исти број корака?
Можда је двоје, можда је три, али рачунар научник само
поједностављује га као Биг О 1, нека исти број корака.
Шта је нешто што могу да урадим узима сталан број корака?
>> Шта је покренут време цлаппинг?
Стална време.
Jel tako?
Као што је трчање време ради ништа да траје само један
рад, као и штампање Ф Хелло Ворлд.
То би се могло рећи да је константа времена, осим ако мање угла случај са штампаним Ф,
Шта би могло Руннинг тиме штампе П заправо бити?
И зашто?
Шта је н мерење у том случају?
>> ПУБЛИКА: [неразумљиво].
Давид Ј Малан: Управо тако.
Број карактера желимо да одштампате.
Дакле, то је врло контексту.
Данас, ми смо се фокусирају много о слова и бројеви овде на табли.
Али такође може бити ликови у стварном низ.
Тако испада постоји други мера која ће почети брине о,
а то је супротно од Биг О, да тако кажем.
>> То је Омега нотација.
Док Биг О значи оно што ја, горње границе на време трчања?
Максимално, колико времена Можда нешто предузети?
Омега-- ми је ово надолази их-- је супротно од тога,
при чему је доња граница на количину времена нешто могло трајати.
>> Prema tome. На пример, шта је алгоритам која се увијек Н квадрат кораке?
Па, један од алгоритама смо видели Данас, у ствари, може бити исто тако добро.
Избор врста.
Избор врста је прилично глупо.
Чак и ако алгоритхм-- жао, чак и ако је низ већ поредани,
Избор врста ће се кееп валкинг кроз листу
да се уверите да има најмањи елеменат опет и опет и опет.
И мада ви људи у Публика зна да, чекај мало,
већ прошло Најмањи елемент, рачунар
не знам да све док то изгледа скроз кроз листу.
Слично томе, доњу границу која може такође бити узети у обзир
можда линеарног времена.
>> Колико времена је потребно да Сорт н елементи у најбоље
Случај користите нешто попут буббле сорт?
Претпоставимо да ваша листа је већ сортирају.
Рекли смо балон врста преузима редослед н на квадрат кораке.
Али, шта ако је већ поредани?
Шта ако схватите после један пролаз кроз низ
да сте направили никакве свопови?
Да ли је потребно да би што више пролази?
>> Ne.
Тако доњу границу на буббле сорт може се рећи да је линеарна.
Омега од н.
И можемо да погледамо други за њих, као.
Дакле, хајде да кратак поглед на само визуализације овде
да видимо како они се разликују.
Ја идем доле у ​​ово страница која је доступна на сајту Ц50 је,
али то ће бити бол да раде, јер користи технологију која се зове
Јава аплети, што је у великој мери подржан ових дана,
барем Цхроме и неких других.
>> И пусти ме само напред и убрзати ово горе и објасни шта се дешава.
Ово је демонстрација буббле врста, први алгоритам смо гледали.
И то је визуализација у да сваки ових шипки представља број.
Што је већи бар, Што је већи број.
Мањи бар, мањи број.
А шта можете визуелно види, чак и мада ово ће супер брзо,
је да је црвена трака је попут мене, хода напред и назад фиксирање проблема.
Можете видети да су веће елементи уистину бубблинг до десно,
и мањи елементи се бубблинг до леве стране.
И овде, ако заправо изгледају ближе,
можемо да пребројимо број поређења и свопова
да су се направили.
>> Али, уместо тога, хајде да погледамо на другом алгоритам
погледали смо раније са нашим волонтери, избор врсте.
Визуелно, ит хас а веома другачији ефекат.
Али то је, опет, врло интуитивно, у да чувамо избора следећег најмањи
елеменат, а имамо мало среће.
То је било суштински брже.
Али, ако се поново и поново побегао ово и опет са пуно улаза,
ћемо видети да је то заиста је још увек у великој О од н на квадрат.
>> Хајде да урадимо једну последњу овде, уметање врста,
што је био трећа алгоритам погледали смо и поврат
да је ово једна бави елементи као што их сусрета,
али онда се можда смене ствари преко да бисте ослободили простор,
уметање елемената где они припадају.
>> И ово такође завршава постиже крајњи резултат. Сада све три оне
осећао веома брзо.
И заиста, њих налетео сам у прилично добром снимку.
Али у основи, сви су прилично страшно, да будем искрен.
Све ове алгоритама до сада који раде у великом О од н на квадрат
узети доста Време је да раде у крају.
>> И заиста, можемо видети и осећају ово на крају
ако повучем ову трећу и финалну демо.
Ово је још један визуелизација да иде
да покаже мехурића Сортирај по левој страни, Избор врста у средини,
и нешто, као један од наших рука подиже раније предложио,
споји Сортирај по десној страни.
Јаз па владај Стратегија на десној страни.
И то је, у ствари, оно што смо ћемо да погледамо у среду.
Али хајде да време ове да паралелно.
То је отприлике исти број елементи, све иде у исто време.
Буббле сорт против селекције Сорт против стапања врсте.
>> Сада, сви они руннинг у теорији истовремено.
Процесор ради на истом брзином, али
Могу да осетим како је досадан ово је врло брзо ће постати,
и колико брзо када да унесем недеље
Зеро алгоритми могу да убрзамо ствари.
>> А сада да упоредимо ово у једном последњи облик.
Ја ћу ићи напред да ЦС50 веб сајту, где
имамо ову коначну линк за данас, где је неко на интернету
љубазно ставио заједно видео који показује шта друго сортирање
алгоритми звучи.
Ово је уметање врста.
>> [Бееп]
>> Чиме сте применом фреквенцију заснована на висине бар бара.
Ово је балон врста.
>> [Варпед Бееп]
>> Цоминг уп нект је-- долази следеци је-- избор врста,
где опет смо одабир следећи најмањи елемент,
и видимо да расте с лева на десно.
>> Мерге врста, наш победник до сада данас.
Обратите пажњу како се дељењем ствари у [неразумљиво] пола и четвртине.
ГНОМЕ врста, које немамо говорио о, и ствара визуелно
и аудалли мало Оф А другачији облик и звук.
Гоинг напред и назад, чишћење ствари.
Алсо цхецк оут хеапсорт на сајту овог типа.
>> I to je to.
Ми ћемо вас следећи пут.
>> [ВХООСХИНГ И МУЗИКА]