[Музички] 

Дејвид Џ MALAN: Ова е CS50. И ова е почеток на три недела. Значи имаме многу возбудливи работи кои треба да се покријат и денес. А многу можности за волонтира на сцената. И во крајна линија, денес е не за код на сите. Но, тоа е за идеи, и тоа е за алгоритми, а всушност враќање на некои од научените лекции од нула недела назначено со тоа, да се потсетиме, ние воведени оваа монструозност. Задолжување и инспирација од тоа, да се започне за да се реши уште софистицирани алгоритамски проблеми. Но, прво, неколку пораки. Значи една, ако би сакал да се приклучи Вработените и соучениците CS50 е за време на ручекот овој петок, и тука и во Кембриџ, и во Њу Хевн, Ве молиме посетете на курсот веб-страница, каде што може да се најде на URL-то. Предавање оваа среда ќе не биде тука во Сандерс. Тоа ќе биде само на интернет, па Барај на сајтот CS50 е, дали тука во Кембриџ или Њу Хевн, како и. 

А потоа проблем во собата на две веќе е во ваши раце. Ако не сте се нурна во уште, дозволете ми да им понуди на силно формулиран предлог дека, особено сега, како проблемот поставува однапред, што навистина сакам да се започне сега, ако не плискам малку за време на викендот, односно пред кога тие за првпат излезе на Петок, бидејќи ќе најде дека тие не се нужно добивање на повеќе и повеќе предизвик по себе. Мислам дека ќе најдете дека, во Генерално, тие имаат тенденција да се земе околу околу иста количина на време. Но, тоа секако зависи на студентот, и тоа зависи од начинот на размислување со кои можете да го пристап. Но секогаш, си оди да се кандидира против некој ѕид, и ви се случува да се погоди некоја ларва, и ти си само нема да биде во можност да добие повеќе од тоа во некоја точка. И тоа е многу вредни за да може да се чекор подалеку, да се врати следниот ден, одат на работното време, пост на CS50 Разговараат или слично, да се всушност одблокиран. Па задржи дека во умот. Почнувајќи најрано што е можно е најдоброто нешто што можете да направите. Значи тука е каде што почнавме класа, во текот на нула недела. И може да се добие еден волонтер тука за да ми помогне да најдам микрофони? ВО РЕД. Стоејќи веќе. Качи. Претпоставувам дека тоа е како тоа се случува да се работи. Како се викаш? ALAN Естрада: Алан Естрада. Дејвид Џ MALAN: Алан Естрада. Качи. Мило ми е што те запознав. ALAN Естрада: Убаво да ви се исполнат. Дејвид Џ MALAN: И сте биле тука со нас во нулта недела, се разбира. ALAN Естрада: бев. Јас бев. 

Дејвид Џ MALAN: Така би можело да одите напред и да се најде за нас Мајк Смит, како најбрзо што можеш? Како најбрзо што можеш. Буквално кинење на проблемот во половина како што треба. 

ALAN Естрада: Хм. Дејвид Џ MALAN: Буквално кинење на проблемот на половина. 

ALAN Естрада: О. Мм. Многу добро. 

Дејвид Џ MALAN: Во ред. Добро. Ти благодарам. ALAN Естрада: Многу добро. ВО РЕД. 

Дејвид Џ MALAN: И така сега, сте го намалено надолу до половина од големината на проблемот. Сега, ние сме долу на една четвртина. Дали сте обрнувајќи внимание на која страна сме чување? 

[Се смее] 

ALAN Естрада: Да, јас think-- 

Дејвид Џ MALAN: Што секција сме? ALAN Естрада: ауспуси, така. 

Дејвид Џ MALAN: Во ред. Но Мајк Смит се случува да биде по ауспуси. So-- 

[Се смее] 

Во ред. ALAN Естрада: Каде би можеле да очекуваме? Дејвид Џ MALAN: Мајк Смит. ALAN Естрада: Мајк Смит. Дејвид Џ MALAN: Сега, ние сме во хируршки. Сега, лекарите. Now-- 

ALAN Естрада: Let's- ајде да одиме со вистински. Реално. 

Дејвид Џ MALAN: Реал. ВО РЕД. Ако ви треба вистински. Сега, на кој начин е Мајк Смит? 

ALAN Естрада: Овој начин. 

Дејвид Џ MALAN: На кој начин? ALAN Естрада: Чекај. М is-- нели? Почнавме with-- 

Дејвид Џ MALAN: Да. Тие си заминале. Вашето право. 

ALAN Естрада: Да. 

Дејвид Џ MALAN: Значи Мајк тука. ALAN Естрада: Што? 

[Се смее] 

Лош пример, момци. Жал ми е. Дејвид Џ MALAN: Ова ќе учат можете да се фрлиш од столот. 

ALAN Естрада: О. Ох. Те фатив. Те фатив. Ох. Ох. Оваа is-- Добро, јас го добив. Смит тука? 

Дејвид Џ MALAN: Смит, ви благодарам. Па јас ќе го задржи погледот нагоре Смит? 

ALAN Естрада: О, да. Не, не, не. О не. Ова е мое. 

Дејвид Џ MALAN: Ох, ќе морате Смит. ВО РЕД. 

ALAN Естрада: Да, јас Смит доби токму тука. Извинете, момци. Мислев Michael-- ние барате Мајкл. Жал ми е. 

Дејвид Џ MALAN: Тоа е во ред. Во ред, сега ние сме во Paccini и синови. 

ALAN Естрада: Paccini и синови. Дејвид Џ MALAN: Само вие и јас сме во за ова. ВО РЕД. Најди ги ни Мајк Смит. Смит. 

ALAN Естрада: Смит. 

Дејвид Џ MALAN: Смит. Ние сме во R за ѓубре. ALAN Естрада: отпадоци. Ох. Ова се случува да се земе некое време. 

[Се смее] Дејвид Џ MALAN: чевли. Ние сме во чевли. 

ALAN Естрада: Сега сме gonna-- 

Дејвид Џ MALAN: Ница. ALAN Естрада: Which-- [Се смее] Ох, ова е одлично. [Се смее] 

Дејвид Џ MALAN: Тоа е во ред. 

ALAN Естрада: Ох, ова е добро. Јас не мислам дека ќе одам да се имаат PSAT пријатели по ова. Дејвид Џ MALAN: Добро. Спортинг. ALAN Естрада: Спортинг. Хм, L, M, N, O, P. Дејвид Џ MALAN: Во ред. Значи, да се солза овој на половина. Во ред е. Ова завршува лошо во секој случај, бидејќи на Мајк Смит нема да биде во жолти страници. 

ALAN Естрада: Aw. 

Дејвид Џ MALAN: Не, тоа е во ред. Но, ајде да се преправаме како тој е на оваа страница. Па сега, сте намалено проблемот надолу подолго од една страна, и најдовме Мајк Смит. 

[Навива] Во ред, ви благодарам. ВО РЕД. Која беше извонредна. Но сепак тоа беше побрз од линеарно пребарување, назначено со тоа, што со почеток во почетокот на книгата, и се движиме нашиот пат од лево кон десно, на крајот барате Мајк Смит. И така, ако телефонот книга имаше можеби и 1.000 страници, Можеби тоа ќе се преземат ни 10 или така солзи страница. 

Но, може да имаат балон допре претпоставка време сето тоа, што да се каже дека телефонот книга однапред беше она? ПУБЛИКАТА: подредени. Дејвид Џ MALAN: Тоа е сортирана. Нели? Тоа е подредени по азбучен ред, така дека сите оние имиња и броеви се подредени од А до Z, и по азбучен ред помеѓу. Но, денес, ние сега се бара На прашањето, добро, како го направи Веризон или на телефон компанијата да го во ваква состојба? 

Бидејќи тоа е една работа да се потпора таа претпоставка, и затоа, во решавањето на проблемот со алгоритам поефикасно. Но, ние никогаш не побарано во нулта недела, добро, колку тоа го правеше на трошоците Веризон или некој друг да се добие дека телефонот книга во по некаков ред? 

Нели? Тоа не е важно ако угледување Мајк Смит е супер брз, ако тоа ви е потребно година да се најде решение на страниците на почетокот. Нели? Вие, како може само да се кваси, преку рандомизирани телефон книга, ако тоа се случува да биде супер скапо да го средиме. Па ако може да имаме уште еден волонтер. Ајде да ги гледам нагоре тука во како ние might-- ајде up-- како ние би можеле да се обратите за сортирање овие. 

И ако Јордан всушност би можеле да ни се придружат до тука на сцена. Качи за само еден миг. Како се викаш? CAROLINE: Каролина. Дејвид Џ MALAN: Каролина, ајде до. И ќе се приклучи од страна на мене и Јордан тука. Каролина, ви благодарам. Во ред. Значи она што го имаме овде Каролина е 26 сини книги дека ФАС користи за администрирање одредени завршните испити. Овие се добива тешко да се најде, Но, она што ние го направивме во однапред е тоа што ние се стави нечие име на предниот дел на секоја од овие, но ние сме го чуваат едноставна страна потоа да се стави надвор целосни имиња. Па ние ќе ја стави на лицето со името L, Д, Ј, Б, по целиот пат од A до Z, но тие се по случаен редослед. И така, ако би, зборува вашиот пат низ проблем како тебе го прават тоа, може да оди напред и средиме овие за нас, од А до Ш 

ПУБЛИКАТА: Добро, така што L е како, на средината. С е почетокот. Б. Ј пред Л Б, П. 

Дејвид Џ MALAN: Држете дека мисла за една секунда. Бидејќи во спротивно, ова е само интересно за вас, мене, и Јордан. Таму ќе одиме. ПУБЛИКАТА: [Беззвучен]. Р. Дејвид Џ MALAN: Во ред. Што правиш? 

CAROLINE: M доаѓа по О. 

Дејвид Џ MALAN: Во ред. 

CAROLINE: О. Дејвид Џ MALAN: О, добро. 

CAROLINE: Е. 

Дејвид Џ MALAN: Е, Ф Да. 

CAROLINE: Т, U, В. 

Дејвид Џ MALAN: V, Т, У, В Па тоа изгледа како да сте making-- продолжувам да одам. Тоа изгледа како си прави еден голем куп овде, и вид на еден голем куп таму. Значи првата половина од азбуката, Втората половина од азбуката. ВО РЕД. Добро. Вид на поделба на проблемот на два дела. M, N, X. Да. CAROLINE: К. Дејвид Џ MALAN: Во ред. К. Па ти си вид на изборот нив еден по друг, ставање лево или десно, или Z се случува на подот. ВО РЕД. 

CAROLINE: Z се случува на подот. 

Дејвид Џ MALAN: Во ред. Y се случува на подот. Сега можеме да се стави X. 

CAROLINE: Г. Дејвид Џ MALAN: G е одеше лево. S ќе десно. Добро, А се оди на целиот пат замина. 

CAROLINE: A, B, C, D. 

Дејвид Џ MALAN: Сега, добро. Имаме А, Б, В В случува таму долу. Добро, Т. 

CAROLINE: H, I, Џ Дејвид Џ MALAN: H, I, Ј Добро. CAROLINE: Во центарот, јас сум gonna-- Дејвид Џ MALAN: Во ред. Па сега, ние ќе треба да се вид на спојување на овие различни купови. Па A до C, а потоа ќе видам D, и Е, и F и G, и H, и I. Ница. Ј, К И тогаш, овој куп е наопаку, но тоа е во ред. Сигурен. Ние може да се намалат некои ќошиња. ВО РЕД. И тогаш ние треба W, X, Y, Z. 

CAROLINE: Да. 

Дејвид Џ MALAN: Одлично. Така голема благодарност до Каролин за сортирање овие. 

[Навива] 

Ти благодарам. Ти благодарам многу. Па сега ајде да се разгледа за момент Каролин како помина правејќи дека, и што точно ние беа во можност to-- како ние беа во можност да го реши тој проблем кога бевме само со оглед на целиот куп на случајни влезови. 

Па, тоа изгледа како таму беше малку на систем таму? Право. Па порано писма во азбуката, таа е ставање на левата страна, а подоцна букви во азбуката, таа е ставање во право. И штом таа се најде некои проксимална писма, оние кои се веднаш до едни со други, таа ќе се стави оние во ред. И така ние вид на имале овие мали купови сортирани влезови случуваат. 

И така тоа е слично на она што повеќето од нас луѓето не би го направил. Ние би вид на кваси преку неа, и ние би вид на имаат механизам. Но, тоа може да биде тешко да се напише тоа долу во формула по себе. Тоа се чувствува малку повеќе органски од тоа. Па ајде да видиме дали можеме да сега е врзана проблемот со помалку влезови. 

Наместо на 26, ајде направи нешто многу помалку со речеме, седум, зад овие врати, така да се каже. Дали има само седум броеви? И ако целта сега во страна е да се најде вредноста, Да видиме колку ефикасно ние може да се обратите за тоа. И да видиме дали можеме сега започнат да се применуваат некои броеви, или некои формули со кои може да се опише на ефикасноста на нашите телефонски именик алгоритам, нашите испит книга алгоритам, и поопшто, наоѓање на информации. 

Па за тоа, дозволете ми да оди напред, и на екранот на допир овде, постави на веб пребарувач, кој има Токму овие седум врати. И ако ние би можеле да добијат уште еден доброволно да Дојди овде, Јас сум се стави овие исти вратите овде. Брзо волонтер. 

Оваа one-- демо снимки се случува до побрзо и побрзо сега. Ајде надолу. Како се викаш? TREVOR: Тревор. 

Дејвид Џ MALAN: Тревор? Добро, Тревор, ајде долу. Значи Тревор доброволно тука за да се направи сличен проблем, туку она што е потесни во обем, и што се случува за да ни овозможи да се обиде да го формализира сега процесот за сортирање на овие броеви. 

Значи Тревор, убаво да ви се исполнат. Значи тука е низа, така да зборувам, листа од седум врати. Оди напред и да ни се најде бројот 50. А потоа и по фактот, да ни кажете како вие го најде. Треба be-- ред. Да, ова е оној во оваа ситуација? Ух-ах. ВО РЕД. Ако кликнавте оној. Добро. 

И добро. Сега ако кликнавте оној. И дозволете ми да ви даде микрофон, така што ќе го има во само еден миг. Оди напред и да кликнете на соседството дека имате намера. Да, добро. TREVOR: Може ли unclick врата? Дејвид Џ MALAN: Не, вие не може да unclick. TREVOR: Во ред. Оваа. Дејвид Џ MALAN: Каде сакаш да одиме? Кое? 

TREVOR: Тоа човек. 

Дејвид Џ MALAN: Не 

TREVOR: Во ред. Оваа. 

Дејвид Џ MALAN: Да. Тоа беше добро. Во ред. Значи, што беше вашата алгоритам или постапка за тоа, Тревор? 

TREVOR: Јас само отиде преку врати додека не го најдов 50. Дејвид Џ MALAN: Во ред. Одлично алгоритам. Па тоа е добро. Бидејќи во Всушност, ако јас се открие што е зад овие две други врати, што ние ќе најдете тука е дека имаме само случаен влез. Така што беше, всушност, како добра како што може да се добие. И всушност, имаш подобра од исцрпно пребарување на целата низа, затоа што тоа би било навистина баксуз ако го погоди бројот 50 во последен врата. Но, што ако, наместо ви даде претпоставка. Претпоставувам дека вид сите овие врати околу себе, така што ќе ги имаат броеви подредени тоа време, но овој пат тоа е всушност different-- на овој пат, тоа е всушност подредени за вас. И сега целта при рака е да се погоди бројот 50. 

TREVOR: Во ред. 

Дејвид Џ MALAN: Што не е во алгоритам вашиот ќе биде? 

TREVOR: Па, ако тоа е сортирани, тоа е или ќе да be-- ако најголемата до најголемите, обратно, тоа ќе биде првиот, или ако тоа е токму спротивното, тоа ќе биде последен. Па јас само ќе ја допрете оваа врата, потоа допрете само последната врата. Дејвид Џ MALAN: Одлично. Во ред. Па најдовме бројот 50. Па штом ќе знаеше се сочувани, ние беа во можност да потпора оваа претпоставка. Па тие се премногу како на пример телефонски именик. Штом имаш, па дури и со еден мал проблем, како таков, вашата влезови пред-сортирани, можеме да всушност се најде вредноста веројатно поефикасно. 

И јас не ти кажам, ако тоа беше сортирани мали до големи, или големи до мали, и така тоа е многу разумно да се започне на едниот крај или на друг за да всушност се најде дека целната вредност. Така им се заблагодарам на Тревор, како и. А јас ќе propose-- убаво направено. Имаме малку клип, всушност, дека е меѓу нашите омилени моменти во CS50, при што понекогаш овие демонстрации не сосема оди според планот. И навистина, токму сега, јас застана на погрешна интерфејс со која треба да се користи екран на допир. Па тоа беше моја грешка таму. 

Така што ова ќе се направи за следната година клип како зошто бев кликнување на мојот екран. Но, ајде да се земе брз поглед што се случи минатата година со Џеј, кои дојдоа, многу како Тревор тука, доброволно, и во овој краток клип, ќе видите како истата оваа демократската не сосема откриваат исто научените лекции. [Видео репродукција] -Сите Сакам да се направи сега е да се најде за мене, и за нас, Навистина, бројот 50 еден чекор во исто време. 

-Број 50? 

-Број 50. И може да се открие што е зад секоја од овие врати со едноставно допирање со прст. По ѓаволите. 

[Се смее] 

[END репродукција] Дејвид Џ MALAN: Така што помина многу добро. Тоа беа несортиран врати. И Џеј, се разбира, сето тоа се наоѓаат премногу брзо. Тревор правеше многу подобра работа во смисла на способен момент, така да се каже, оваа година во потребен подолг временски период за да го најдете. Се разбира, потоа дадовме Џеј втора шанса, при што се подредени на вратите, исто како што направивме за Тревор, и Тревор направив супер и овој пат. Џеј но тоа го правеше половина како брзо. [Видео репродукција] -на Цел сега е да, исто така, ни се најде бројот 50, но направете го тоа алгоритамски, и да ни кажете како ви се случува за тоа. 

-ВО РЕД. 

-И Ако го најдете, ќе се задржи на филмот. Ако не го најдете, ќе ти ја вратам. 

-Man. 

-OH! 

- [Беззвучен] Во ред. Па јас ќе одам да се провери на крајот прво да се утврди дали there's-- О. 

[Аплауз] 

[END репродукција] Дејвид Џ MALAN: Во ред. Па сортирање врати јасно доведува до поголема ефикасност. И така, два пати толку брзо е она што мислев таму. И така Џеј доби среќен двата пати. И тој, исто така, доби среќен со тоа што последната година, јас нареди некои Blu-ray дисковите всушност да даде. Жал ми е оваа година, ние не ги имаат истите, Тревор. Но сепак подобро е за неколку години назад. И некои од вас можеби знаете ова колеги, Шон, кој кога беше во CS50, беше оспорена со точна Истиот проблем, иако во С.Д. како што наскоро ќе видиме, во тоа време. И ќе најдете дека не само што тој да потрае малку подолго од Џеј, малку подолго од Тревор, тоа беше всушност оваа прекрасна можност да се вклучат речиси сите во Толпата а ла цената е во право, поттикнување него да се најде на бројот што се бараат. Ајде. се земе брз поглед. 

[Видео репродукција] 

-ВО РЕД. Па вашата задача овде, Шон, е следниот. Имам крие зад овие Вратите на бројот седум. Но подвиткано далеку во некои од овие врати како и други негативни броеви. И вашата цел е да се мисли на овој врвот ред на броеви како само низа, или само Редоследот на парчиња хартија со броеви зад нив. И вашата цел е, само користење на врвот Низа тука, да ме најдете на бројот седум. И ние сме тогаш ќе го критикувам како да се обратите за тоа го правам. -Во ред. Најди-ни бројот седум, ве молам. Бр Пет, 19, 13. 

[Се смее] 

Тоа не е трик прашање. Еден. 

[Се смее] Во овој момент, вашиот резултат не е многу добро, така што би можело да се насочи. Три. 

[Се смее] 

Продолжи. Искрено, не може да им помогне, но се прашувам она што сте дури и размислува за, so-- 

[Се смее] Само најгорниот ред, така имаш три лево. Па да ме најдете седум. 

[Се смее] 17. Седум. 

[Аплауз] 

Во ред. 

[END репродукција] 

Дејвид Џ MALAN: ние да можеме да види овие на целиот ден. И, се разбира, некои од овогодинешната демос можеби сега ќе завршат во следните година видео, како и. Па сега ајде, всушност, се фокусираат на алгоритми тука, и да видиме ако не можеме да сега да почне да се формализира како ние може да се обратите за добивање на нашите податоци во оваа држава дека е сортирана, така што во крајна линија, ние всушност може да тоа бара поефикасно. И покрај тоа што ние ќе треба да се користи прилично мала збирки на податоци, како ние осумте броеви имаме овде на табла, крајна линија може да ја применувате овие идеи 1.000 влеза, еден милион влезови, 4 милијарди влезови, бидејќи на алгоритми се ќе биде во основа исти. 

Па така ова е нашата последна можност за волонтерите и денес, но можеби најмногу ангажира, за кои ние треба осум волонтери да излезе и да одат низ нас наскоро процесот на сортирање што ќе бидат на овие музички стои тука. Дозволете ми да започнам повторно тука. 

Па еден во turquoise-- зелени е тоа? Дали сте сториле? Две. Ајде надолу. ВО РЕД. Три. Четири. Нека me-- ред, пет. Сте се номинирани од страна на вашиот пријател. Шест, седум, осум. Качи. Во ред. Ви благодарам многу. Качи. Качи. 

Во ред. Значи она што го имаме here-- и ова е меѓу повеќе непријатно оние, бидејќи тоа ќе бара од вас да хумор мене за само малку време. Ти ќе биде број еден. Како се викаш? 

Анан: Анан. 

Дејвид Џ MALAN: Анан. Давид. Како се викаш? 

Џозеф: Јосиф. 

Дејвид Џ MALAN: Јосиф, вие сте број два. 

Серена: Серена, бројот три. Стефан, број четири. CYNTHIA: Синтија. Дејвид Џ MALAN: Синтија, број пет. [Беззвучен] Дејвид Џ MALAN: [Беззвучен]. Давид, број шест. Мет: Мат. Дејвид Џ MALAN: број на Мет седум. И? 

WAVERLY: Waverly. 

Дејвид Џ MALAN: Waverly, број осум. Во ред. Ако could-- whoops. Ако сите вие, како вашиот Првиот предизвик, има осум музички штандови тука се соочуваат со публиката. Ако може да се стави вашите броеви на овие музички стои на таков начин дека тие се редат со истите броеви на табла. Така бидете сами изгледа дека со ставање на вашите броеви на овие музички стои тука. Одлично досега. 

Одличен. ВО РЕД. Па сега, ние ќе треба да побара од прашање во неколку различни начини. Како можеме да се обратите за подредување овие луѓе тука? Бидејќи имавме неколку приоди порано, при што бевме вид на правење две различни кофи. А потоа ние, главно, се piecing работите заедно. Штом видовме два броја кои припаѓаат заедно, ние ги стави заедно. Двете писма што одат заедно. 

Но, ајде да видиме дали можеме не може да го формализира ова, за да можеме конечно да го имаат некои псевдо-кодот ќе, со која можете да ги реши овие проблеми. Па сега, го гледам овие бројки тука. И гледам еден куп грешки. На крајот на краиштата, сакам еден од лево и осум од десно. 

И така јас сум во потрага на овие два, четири и два. И што е проблемот, очигледно? Је. So. Две очигледно доаѓа пред четири, па да знаете што? Дозволете ми прво да се земе еден алчен пристап, ако сакате, многу сличен проблем постави one-- ако се потсетиме од Стандардното издание на Проблем Постави Еден, каде што само локално реши проблемот дека е во право тука пред мене и да видиме каде што ме води. 

ВО РЕД. Па две и четири, дозволете ми да оди напред и само ќе трампа два. Ако физички може да се движи себе си и вашиот документ, Ми се чини дека има добивано листата во подобра состојба. 

Сега, тие се добри. Одам да се движи, четири и шест, изгледа добро. Не е проблем. Шест и осум години, во ред. Осум и еден, уште еден проблем. Затоа што е вистина за осум и еден? Еден збор пред осум години, и така што ние треба да направам? Ајде да се разменуваат со овие две. Една и осум. И сега, јас ќе одам да се насочи. Одам да се задржи во потрага напред. И да видиме што се случува. Осум и три, на Се разбира, на ред. Ајде да се трампа. Осум и седум години, се разбира. На ред. Ајде да се трампа. Осум и пет, се разбира, да ги трампа. Во ред. Листата се подредени. Да? 

Добро, јасно не. Но, тоа е малку подобро, нели? Бидејќи известување што се случило. Секој пат кога ќе се врши замената, помал Бројот вид на пат на процедување на тој начин, и поголем број процедено овој начин, или ќе почнеме да ја кажуваме клобуркаше до клобуркаше лево или на десно. 

Сега, тоа не е доволно, бидејќи во најдобар случај, бројот би можел се преселија на едно место напред или, во најлош случај, број може да има скокна за едно место и понатаму. Па да знаете што, овој вид на работеа доста добро досега. Дозволете ми само да го пробате повторно. Две и четири, тие се во ред. Четири и шест, тие се во ред. Шест и еден, на ред. Па ајде вие ​​двајца трампа. И сега, известување на проблемот почнуваат да се добие малку подобро повторно. Шест и три, на ред. Ајде вие ​​двајца трампа. Шест и седум, ти си добро. Седум и пет, се разбира, на ред. Седум и осум години, во ред. И сега, јас би можеле да треба да се направите тоа уште неколку пати. И всушност, мислам за себе можеби колку пати максимално Јас би можеле да треба да одиме напред и назад? 

Ние ќе се вратам на тоа. Па две и четири се уште се во ред. Четири и еден, бе. Значи, ајде да трампа. И повторно, известување визуелно еден е вид на клокотот на левата страна, каде што треба да биде. Четири и три трампа. Четири и шест. Шест и пет трампа. Шест и седум. Седум и осум се добри. 

Добро. Ние сме добивање на уште подобри. Ќе видиме. Сега, имаме две и еден. Се разбира, се разменуваат. Два и три, три и четири, четири и пет, шест и седум, седум и осум години. Добро. И знаете што? Бидејќи не сум направил една замена таму, дозволете ми да се направи една разумност провери. Дозволете ми да одат сите на патот Вратете се на почетокот. ВО РЕД. Еден, two-- То, види? Нешто не е во ред. Три, четири, пет, шест, седум, осум. И во овој последен помине, се вие сигурно со мојот сега тврдејќи дека истата е сортирана? ВО РЕД. Визуелно, тоа е апсолутно точно. Но функционално, она што се, исто така, само што се случи во тој последен пас што овозможува да се потврди дека оваа листа е навистина подредени? 

Што сум направил или не овој последен помине? ПУБЛИКАТА: Немаше промени. Дејвид Џ MALAN: Жал ми е? ПУБЛИКАТА: Нема промени. Дејвид Џ MALAN: Немаше промени. Па тоа би било глупаво од мене да направите тоа истиот алгоритам повторно ако јас не се направи било менува за прв пат. И државата не е променет. Секако, јас не одам да се направи Било какви промени по вторпат. И така, тоа е безбедно сега да се каже, листата е подредена. 

И навистина, ова е сега нешто што ние ќе обично повик меур вид, при што, во парови, можете да ги поправите грешките повторно, и повторно, и повторно, и вие Продолжувам да одам напред и назад, и напред и назад, додека не не прават такво свопови, на која точка можете да бидете сигурни, да, јас заврши одредување сите грешки. Ајде да се ресетира и да се обиде друг пристап. Ако вие момци може да се врати во редот што беа пред еден миг, која изгледаше вака. Сега, ајде да се земе пристап малку повеќе како на испит книга, при што беа постојано избирање на буква од азбуката дека ние вид на сакав да се справи со следниот. Можеби тоа беше голема буква, како А, или низок букви Z. 

Па секој е назад во оваа цел. А сега дозволете ми да го направите тоа. Да видиме знам дека имам осум броеви тука. Одам да се оди напред и да само намерно одберете најмалиот елементи. Нели? Ова изгледа интуитивно премногу. Зошто не можам да најдам на најмалите елемент, го стави таму каде што припаѓа, потоа го добиете следниот најмалиот елемент, ставете тоа каде припаѓа, и само се повторува. 

Бидејќи интуитивно, кои треба да работат премногу. Па четири, што е прилично мал број. Одам да се сети каде е оваа. Почекај минута. Две е помала. Дозволете ми сега да се сетам каде две е, и да заборавите за четири. Ние ќе се справи со тоа подоцна. Шест, не сум заинтересирана. Осум, не сум заинтересиран. Една од нив е мојот нов мал број. Па јас ќе одам да се сети каде еден е. Три, не се заинтересирани. Седум, не се заинтересирани. Пет, не се заинтересирани. 

Значи без паѓање на сцената на оваа година, Одам да го зграби број one-- и она што беше вашето име повторно? 

Анан: Анан. 

Дејвид Џ MALAN: Анан. И ако може да ми се придружат во на почетокот на листата, ајде да се стави каде што припаѓаат. Unfortunately-- што е вашето име? 

СТЕФАН: Стефан. 

Дејвид Џ MALAN: Стефан е во тек. Па пред Стефан го решава овој проблем, што треба да направам? Што ќе правиме со Стефан? 

ПУБЛИКАТА: [Беззвучен]. Дејвид Џ MALAN: Во ред. За да можеме да го направите тоа. Ние би можеле да се земе вид на Стефан и неговите четири, и само да го стави во една променлива и се држи до тоа за некои износот на време, правејќи простор за број еден. И тоа не е лошо. Јас би можеле да сугерираат, зошто да не се направи ние едноставно се стави Стефан тука? Зошто ова го наруши еден од идеите почнавме Станува збор за последен пат, минатата недела? Да? 

ПУБЛИКАТА: [Беззвучен]. 

Дејвид Џ MALAN: Не постои индекс за тоа. Ако мислите дека за тоа, навистина, како низа, ова е како негативен, па нема меморија, всушност, тука ако ова навистина низа, како ние прогласи минатата недела во предавањето. Затоа не треба да го направите тоа. Да ја чувате вредности. 

Или знаете што? Слушнав некој друг тоа го предложат. Што друго би можел да правиме со Стефан? Зошто ние да не само да го исфрли и го стави над местото каде беше број еден. Значи, ако сакате да се оди таму. И навистина, ова е прилично добро решение. Сега, од една страна, јас сум вид на направени влоши проблемот. Сега четири е подалеку од каде што треба да биде. Тоа треба да биде кон ова полувреме. 

Но знаеш што? Што можеше да биде лоша среќа. Можеби број осум беше тука. И така, можеби ќе има добивано и среќа, и се наметнува осум поблиску до крајот. Така, на крајот на денот, тој вид на сите просеци надвор. Ние не треба да се грижи за четири. Сите што се грижат за сега е избирање на најмалиот елемент. 

И сега, она што јас ќе одам да направите е да се заборави за број еден засекогаш, затоа што знам на листа зад мене сега е сортирана. Значи мојата листа претходно беше големината осум. Сега, тоа е големината на седум. Значи мојот проблем е добивање на помали, иако линеарно. Па сега, јас ќе одам да го изберете тековната најмалиот елемент, два. Шест, осум, четири, три, седум, пет. Тоа беше најмалиот елемент. Значи она што сум јас ќе одам да направите with-- она што беше вашето име повторно? 

Џозеф: Јосиф. 

Дејвид Џ MALAN: Јосиф? Ние ќе треба да ја напушти Јосиф во место. Сега, јас ќе одам да се преправам дека овие момци are-- добро, Знам дека овие два веќе се подредени. Ајде сега да се фокусира на Остатокот од листата. Шест е моменталниот најмалите. Осум е поголем. Сега четири е моменталниот најмалите. Сега три е моменталниот најмалите. И така сега, јас ќе одам да одберете три, кој is-- Што е вашето име повторно? Серена: Серена. Дејвид Џ MALAN: Серена, ако може имате своја број и swap with-- KALSANG: Kalsang. Дејвид Џ MALAN: Kalsang. Ајде назад, а ние сме ќе разменуваат овие две. А сега, ајде да се стави ова на автоматски. Одам да одиме и да го оставиме тоа за вас момци да изберете следниот најмалиот елементи. Dun, Dun, Dun, Dun. Број четири, она што треба да направам? Одличен. Сега, јас ќе одам да се направи уште една помине. Dun, Dun, Dun, Dun. Гледам пет е следниот најмалите. Сега, јас ќе одам да се земе друг помине. Dun, Dun, Dun, Dun. Шест е најмалиот. Добро. Седум е најмалиот. Нема промена. Осум е најмалиот. Направено. 

Значи она што ние сме само направено од страна iteratively избирање на еден елемент по друг се спроведе нешто што ние сме ќе се формализира како селекција вид. И тоа е можеби дури и поедноставно да се објасни, во кои буквално сите вас сакате да направите е само да се задржи ќе напред и назад низ листата изборот, следниот најмалиот елемент, додека не завршиш. 

Па тоа е уште поедноставно, можеби интуитивно, во однос на минатата. Ајде да пробаме еден последен. Ако вие момци би можел да си го ресетирате во следниве позиции една конечна време, ајде да видиме ако не можеме да сега формализира еден друг пристап. Всушност, некој би таму сакал да предложам Како инаку би можеле да се обратите за тоа? Без истурам од buzzwords или вид на одговори кои се веќе познати, само интуитивно, што би можело да правиме? 

ПУБЛИКАТА: [Беззвучен]. Дејвид Џ MALAN: Да. Значи има некоја голема интуиција таму. Добри работи изгледа да се случи досега по компјутерски науки, кога ние се подели и освојување на проблемот со делење ја на половина и половина и половина. И така навистина, би можеле да почнат да се направи тоа. И во фактот, дека нема да биде, ние ќе види, еден од нашите најдобри решенија уште. Но, ајде да се вратам на тоа пред долго. Всушност, ние ќе треба да се направи дека малку подоцна оваа недела. Што друго би можеле да направиме за да се реши овој? Па секој овде е во навидум случаен редослед. Знаеш што? Наместо да одат напред и назад, напред и назад, напред и назад секој пат, ова се чувствува како Јас го правам многу одење. Зошто не јас само почеток во на почетокот на листата, и само стави четири таму каде што припаѓа? Па дозволете ми да претпоставиме за момент дека мојата листа е само првиот елемент. Е четири подредени во овој момент во времето, ако сите што се грижат за се што е во оваа ситуација? Ова е вид на тривијално вистина, нели? Како на листа која содржи еден број, и тој број четири е очигледно подредени. 

Па дозволете ми да пропише дека оваа листа е сортирана. Но сега имам на остатокот од оваа листа. Па сега, ги среќавам две. Каде се двајца очигледно припаѓаат во однос на четири? Пред четири. Значи она што можам да направам тука? Што е вашето име повторно? 

Џозеф: Јосиф. 

Дејвид Џ MALAN: Јосиф, ако може да се чекор назад за само еден миг со вашиот број. И сега што треба Стефан направите тука? Ајде да се префрлат Стефан овде. А сега, ајде да Јосиф влезам овде. И сега, дозволете ми да се тврди дека овде сè е сортирана. Значи, сличен резултат, туку сосема различен пристап. Јас дури и не се гледаше што е таму. Јас само ги земате на елементи како што тие се предаде за мене, и да се справат со нив. 

Па сега, гледам бројот шест. Каде што го прави број шест припаѓаат? Имаме два, четири, шест. Точно каде таа е во моментов. Па ајде да го оставиме на мира, а сега тврдат дека овој дел од листата сега се подредени. И така, ова се чувствува фундаментално различни по тоа јас сум само движејќи се низ листата овде линеарно, а јас никогаш не сум удвојување назад. Да. Во ред. Па осум, каде што припаѓаш? Точно тука. Совршен. Па сега, еден. Ух-ах. Ова се чувствува како да е ќе биде скапо. Сега, во претходниот алгоритам, Јас само се сменил луѓе. Па би можел да го стави целиот пат на на почетокот, но потоа се пресели Јосиф. Но, ако јас се движат Џозеф, сега она што се случува да биде во ред? 

Сега, јас сум вид на undone-- сум се зема еден чекор напред, а потоа еден чекор назад, бидејќи сега Јосиф ќе биде надвор од употреба. Па ајде да го направите тоа. Ако може да потрае број еден и чекор назад за само еден миг. Како можеме да се put-- што е вашето име повторно? 

Анан: Анан. 

Дејвид Џ MALAN: Анан во место? Што треба да се случи во однос до два, четири, шест и осум? Сите тие треба да се префрли. Осум па ако би сакале да се префрлат прво, а потоа шест, а потоа четири, потоа две. А потоа на Анан, доколку сакате сакал да дојдеш овде, добро. Но, еве, ние сме само вид на плати цената на друга точка во алгоритам. Оглед на тоа што за последен пат со избор вид, па дури и меур вид, Јас сум одење назад и назад, напред и назад, која е, секако, се збира време-мудар, и буквално во чекори. 

Вметнување вид, на прв поглед, изгледа како да е супер попаметни, со тоа што јас сум само бавно, поединечни напредок, но јас не одам на оваа и назад. Но, ако некој е навистина на ред, огласот сите на работа јас само мораше да се направи. Морав да се движи половина од листата само за да се направи простор за број еден. Така, тоа е истата сума на работа досега тоа чувствува, само поинаков тип на работа. 

Да продолжиме. Така, сега знаете дека секој од една до осум се подредени. Еве, јас имам бројот три. Ако ви се допаѓа да ги собереш бројот три, чекор назад еден. И она што вие момци треба да направите? Да. Па тоа е уште еден, два, три чекори. Три единици на време дека само трошоците мене, така што три сега може да се вклопи. Конечно, седум. 

Ајде да одиме напред и да имаат можете да направиме чекор назад. Ова е само ќе не чини една единица на време, но тоа е во ред. И сега, пет ќе да биде малку поскапо. Ако сакате да се вратите назад. Ние треба да се движи осум, и седум години и шест. А потоа сите сега се подредени. Толку голема рака на нашите волонтери тука. Ви благодарам многу. 

[Аплауз] 

Ви благодарам на сите. Ви благодарам на сите. Да видиме сега колку скапи сето тоа беше. Ајде да се разгледа можеби Наједноставниот од овие, меур вид. И велам наједноставен, само затоа што може да го решите лакомо од само поправат парови проблем тука. Поправат проблемот парови овде, повторно и повторно и повторно, повторувајќи како многу пати колку што, всушност, треба да се. 

Значи излегува дека со балон вид, добро, колку чекори и вие да ја преземат првиот помине на тој алгоритам? Јас би можеле да take-- ајде see-- еден, два, три, четири, пет, шест, седум. И има осум елементи тука. Па тоа е како n 1 минус чекори за да добие од почетокот на листата до крајот на листата. 

Но со селекција вид, да се потсетиме дека сум изборот на елементи повторно и повторно и повторно тоа е најмалиот, Јас сум тоа ставање во место, но тогаш јас не сум во потрага зад мене повторно. Па мислам дека тоа е малку повеќе јасно тогаш тоа прв пат, би можел треба да ги преземат сите n 1 минус чекори да се најде најмалиот елемент. Тогаш јас ги стави во место, а јас иселат кој претходно беше тука. 

Но, тогаш јас не треба да се ги бараме во овој елемент, затоа што знам дека тоа е веќе најмалите. Па сега, можам да се погледне во само седум елементи, а потоа шест елементи, потоа пет елементи, а потоа четири елементи. И така математички, ако n е бројот на елементите или броеви што почнавме со тоа, може да се замисли дека ова е иста како и n минус 1, плус n минус 2 чекори, n плус минус 3 чекори, плус n минус 4 чекори, сите начин се сведува на само еден чекор. И јас сум на мојот последен човек. 

И ако се потсетиме дека многу статистика на книги или математика книги имаат овие формули за тврд повез назад или пред нив, излегува дека оваа серија може да се изрази преку едноставно како n пати n 1 минус над 2. И тоа е во ред, ако тоа не е во првите редови на вашиот ум. Но, ова е навистина точно. Тоа е само на поедноставен начин на пишување. А потоа, ако мислите дека назад во основно училиште, кога само на проектот множење работите надвор, ова се разбира, е само n квадрат минус n поделено со 2. Сите што го направив е проширување изразите таму. И па ајде да ја преработи оваа малку поинаку. Тоа е n квадрат поделен со 2 минус n / 2. 

Значи, повторно, јас сум само вид на примена некои аритметички владее таму. Но забележите веднаш дека најголемиот мандат во овој израз, така да се каже, е тоа што n квадрат. Така да, тоа е n квадрат поделен со 2, минус n / 2. 

Но, генерално, ако n е ќе биде голема вредност, Одам да се тврди дека n квадрат ќе биде доминантен фактор. Тоа е само ќе да биде поголем придонес на бројот на чекори од n / 2. Значи она што мислам кога го велам ова? Ајде да се обидеме едноставен пример, дури и иако математика добива малку голема. 

Значи да претпоставиме имавме 1 милион луѓе на сцената, или 1 милион работи дека ние сакаме да се најде решение. Ајде да го приклучиш на милиони во токму таа формула за да видите колку чекори се потребни вкупно да се најде решение милион елементи користејќи речеме, селекција вид. 

Па ние ќе мора истата формула како порано. Јас би го приклучиш на милиони евра, така што можам да добијам милион квадрат поделен со 2, минус еден милион поделено со 2. Ако го направам тоа математика однапред тука, ние имаме 500 милијарди минус 500.000, што ни дава 499.999.500.000, која е прилично ебам голема. 

Всушност, ако се споредат сега 499.000.000.000, 999 милиони евра, 500.000 против нашата оригинална вредност, 500 милијарди долари, што е толку проклето блиску. Нели? n квадрат поделен со 2 дава us-- или подобро кажано, n квадрат поделен со 2 ни даде 500 милијарди. Тоа е прилично ебам блиску до 499.999.500.000, што значи одземање исклучите 500.000, или поопшто, одземање на исклучување n квадрат, навистина не е голема работа. На n квадрат прави овие броеви расте навистина брзо. 

Сега, ова е важно само доколку како што ние, како компјутерски научници, обично не се случува да се грижат толку многу за нијанси на овие формули и токму она што го прецизни одговори се. Ние само што се грижат, знаеш што? На крајот од денот, оваа формула е од редот на n квадрат. 

Да, ние сме делење со 2 во таму. Да, ние сме одземање исклучена n минус 2. Но, на крајот на денот, терминот што навистина нè повредува и ни чини многу чекори е дека плоштадот рок. И така, компјутерски научник се случува да се направи, генерално, се игнорираат сите оние помали термини со цел, и само погледнете во она што придонесува најмногу на трошоците. 

И тоа е убаво, бидејќи можеме да сега се зборува во многу поголема општост за алгоритми, и да ги споредите. Како и фактот дека јас сум со користење на овој о е намерно. Кога велам од редот на, јас сум конкретно кои се однесуваат на нешто наречен голем О. И големи О е нотација дека секој компјутер научник користи за да се опише горна граница на нешто. 

Па ако може да се каже дека еден алгоритам е во голема О од n квадрат, како што предложи само еден Пред момент, тоа значи дека во однос на неговото водење пат или на неговата ефикасност, што е потребно за да од n квадрат чекори. Можеби и повеќе, можеби и помалку. Но, тоа е од редот на n квадрат. И тоа е горната граница. Тоа нема да биде поболно од тоа. Тоа нема да биде n коцки, или 2 на n, или нешто многу поголемо. Ова е горната граница на она што цена е. Па со оглед на тоа, да се сметаат само неколку примери. И ова е само еден конечен список на многу заеднички работи пати за алгоритми кои е замислена да биде илустрација на некои работи кои ги имаме веќе видено. 

Така на пример, во случај на селекција вид, она што јас сум тврдејќи тука се извршува на тој вид на селекција време е од редот на n квадрат. Во најлош случај, јас ќе одам да се има еден куп на случајни броеви тука. И како што видовме, математички ако јас се задржи одење низ листата, преку листа, изборот на следниот најмалите елемент повторно и повторно, ако јас всушност, ги запишувам сите чекори Јас сум земајќи како што предложи formulaically пред, тоа е од редот на n квадрат чекори кои јас сум преземање. 

И излегува дека меурот сортирање и вметнување вид се исто толку бавно во најлош случај. Погледнете ги, на пример, вметнување вид, На самиот крај, алгоритам ние занимаваа со тоа, кој имаше се погледне на елемент, а потоа вметнете ја таму каде што припаѓа. А потоа ние погледна следниот елемент, и додава дека таму каде што припаѓа. 

Па сметаат дека најдобро можно сценарио. Да претпоставиме дека имав мојот волонтери редат буквално вака, еден низ осум, веќе подредени. Колку чекори е вметнување вид ќе се преземат за да се најде решение за осум лица, ако тие ќе пристигнат на сцената во потрага се допаѓа ова? 

Осум лица веќе се подредени. И јас го користам вметнување вид. Дека минатата на алгоритми. Па, ајде да повторуваат вистински пост. Па ако почнам тука, гледам еден. Каде што го прави еден припаѓаат? Таа му припаѓа право тука. Гледам две. Каде што го прави две припаѓаат? Точно тука. Гледам три. Каде што го прави три припаѓаат? Точно тука. 

Јас гледам четири. Точно тука. Пет, шест, седум, осум. Нема причина да се повторувам. И така, колку чекори е дека во однос на n? Тоа е од редот на n чекори, нели? n минус 1. Но јас се линеарна број на чекори, и сега јас сум се направи. Значи тоа е најдобар случај, иако. Што е со најлош случај? Што осум беа таму, а седум беа таму долу, и еден и два беа над тука, па дека на листата се навистина обратна? 

Па, она што се случува навистина ако ова е бројот? И ние ќе се само неколку примери. Што ако, навистина, бројот осум е тука, а number-- whoops. Па што ако, навистина, бројот осум е целиот пат овде, и јас сум со користење вметнување вид? 

ВО РЕД. Јас тврдат дека во моментот тоа е на место. Но, сега, каде што го прави seven-- седум се оди? Се разбира, тоа оди овде. Па морам да се движи осум текот на едно место. Сега има шест години, каде се движи? Па, добро. Сега, јас треба да се движат повеќе од осум место, и седум во текот на место, и јас тогаш паднала по шест. 

Па прв пат, таа цена мене еден чекор да ги поправи работите, тогаш тоа ме чини два чекори за да ги поправи работите. Колку чекори тоа е случува да се земе да се утврдат работи кои треба да се стави пет во право место? Три. Бидејќи сега морам да се движат еден, два, три. Колку чекори е тоа нема да потрае да се стави четири во право место? 4 плус 5, плус 6, плус 7. 

И така тоа е математички идентична она што го опиша за избор на вид. Имаме оваа серија тоа е само се зголемува. 1 плус 2 плус 3 и 4, или обратно, 7 плус 6 плус 5 плус 4 придонесува за денешните цели да по наредба на n квадрат. 

Па дозволете ми да пропише дека премногу меур вид е, исто така, во n квадрат. Затоа што со балон вид, секој кога одам низ листата, Јас сум земајќи приближно колку чекори? Секој пат кога јас буквално одат од таму да има? Грубо n чекори. Но колку пати би можел треба да поминат низ оваа листа? 

Па, грубо n време. Можеби n минус 1, но грубо n пати. Па, зошто е тоа така? Па, со балон вид, ако ние започнуваме со балон вид, со листата во најлошо можно ситуација, што повторно е целосно наназад, што ќе се случи? Одам низ листата, и број некој припаѓа на целиот пат таму. 

Но со балон вид, колку далеку не еден се движат на мојот прв замина во текот на оваа листа? Колку спотови добива тој поблиску до правилната место? Само на еден. Значи, ако сте вид на разумот преку ова, во секое време во текот на овој алгоритам, Земајќи приближно n чекори на Давид. Но, колку додавања низ листата е случува да се земе еден до меурот од лево каде што припаѓа? 

Тој мора да се движат како, n простори на овој начин. Па само да се направи за сортирање на листата, Морам да одиме напред и назад n пати. И секој пат, јас сум гледање на n елементи. Затоа направете n работите n пати на редоследот на n квадрат. 

Сега, ќе видиме во некои на шорцеви, кои се вградени во следниот проблем е CS50 поставени, поинаков пристап на овие, но сега за сега, ајде да се разгледа некои други работи времиња, особено ако се земе оние сортирање малку време да потонам. Што е алгоритам веќе видовме кој што се од редот на n чекори? 

Она што треба да се земе еден линеарен број на чекори кои што сум го видел досега? Што е тоа? Пребарување на телефон директориум. Првиот алгоритам. Нели? Каде сме линеарно во потрага за Мајк Смит? Навистина. Од нула недела, кога почнав претворање на една страница во еден момент, и јас дури и рече дека тоа е вид на еден линеарен алгоритам чувство, и имавме таа слика на табла со исправен црвената линија и исправен жолта линија, тие навистина беа алгоритми, кои се во голема О на n. 

Бидејќи да се најде Мајк Смит во телефонот книга на n-страници, во најлош случај, може да ме n чекори земе. Што е со преземање на посетеност? Еден, два, три, четири, пет, шест. Колку е саат работи на овој алгоритам за полагање присуство? Биг О на n, затоа што во теорија, треба да се истакне сите присутни во просторијата. 

Сега како настрана, она што за други оптимизација од нула недела? Два, четири, шест, осум, 10, 12. Компјутерски научник би реализира, почекајте една минута, тоа е од редот на n поделен со два чекори. Нели? Затоа што јас го правам двајца луѓе во исто време. Но, ние ќе треба да се игнорира оние пониски термини со цел, и ние сме само ќе фрлаат подели со 2, и само велат, големи О на n за тоа алгоритам, како и. 

Она што за оваа? Ние ќе ги прескокне некои од овие, но она што беше алгоритам кој беше дневникот на n? Кои се околу логирате n чекори? На поделба и освојување. Токму така. Како пример на телефонот книга во нула порано и денес, недела и, каде сме поделени на проблемот повторно и повторно и повторно. Ние тоа го привлече на табла во недела нула како криви зелена линија, и рече дека денот кога беше логаритамска алгоритам. 

И навистина, бројот на таа чекори потребно да се изврши поделба и освојување, или бинарни пребарување како што ќе почнете нарекувајќи, како и во книгата на телефонот, е од редот на најавите и чекори. И ова е малку чудно еден. 

Што носи еден чекор, или поконкретно константен број на чекори? Можеби тоа е два, можеби тоа е три, но, компјутерски научник само ги поедноставува како голема О од 1, некои константен број на чекори. Што е нешто што може да го направи тоа зема константен број на чекори? 

Колку е саат работи на плескање? Временска константа. Нели? Како, на она што е на трчање време на правите нешто што трае само еден работењето, како печати F Здраво светот. Тоа би можело да се каже дека е постојана време, освен ако не е помалку агол случај со печатот F, она што може трчање време на печатените F всушност може да биде? И зошто? Што е n мерење во тој случај? 

ПУБЛИКАТА: [Беззвучен]. Дејвид Џ MALAN: Токму така. Бројот на карактери ние сакаме да се печати. Така што е многу чувствителна. Денес, ние сме се фокусира многу на букви и броеви овде на табла. Но, тоа исто така може да бидат ликови во вистински стринг. Значи излегува, има уште една мерка која ќе почнат да се грижат за тоа, и тоа е токму спротивното на големи О, така да се каже. 

Тоа е омега нотација. Со оглед на големите О значи што е, на горна граница на вашето време на работа? Максимално, колку време Може да се земе нешто? Omega-- жал ова постојано доаѓаат up-- е спротивно на тоа, при што тоа е долната граница на износот на време нешто може да потрае. 

So. на пример, што е еден алгоритам кој што се секогаш n квадрат чекори? Па, еден од алгоритми што сум го видел денес, всушност, може да биде и тоа. Селекција вид. Селекција вид е прилично глупави. Дури и ако algorithm-- ми е, па дури и ако низата е веќе сортирана, селекција вид ќе Продолжуваат да одат низ листата за да бидете сигурни дека тоа има најмала елемент повторно и повторно и повторно. Па дури и покрај тоа што луѓето во публика знае дека, почекајте една минута, веќе поминале најмалиот елемент, компјутерот не знае дека до тоа изгледа на целиот пат низ листата. Слично на тоа, дека долната граница исто така може да бидат земени во предвид Може да биде линеарно време. 

Колку време е потребно за да вид n елементи во најдобар случај користење на нешто како меур вид? Да претпоставиме дека вашата листа е веќе сортирана. Ние рековме меур вид зема редоследот на n квадрат чекори. Но, што ако тоа е веќе сортирана? Што ако се реализира по еден поминат низ низа кои сте направиле никаква размена? Дали ви е потребна за да се задржи правење повеќе додавања? 

Бр Толку пониска граница на меур вид може да се рече дека е линеарна. Омега на n. И ние може да се погледне во другите од нив, како и. Значи, да се земе брз поглед на само визуелизација тука да се види како тие се разликуваат. Одам да одат надолу тука во оваа страница, која е достапна на веб страната C50 е, но тоа ќе биде болка за да се добие работа, бидејќи користи технологијата наречена Java аплети, што е во голема мера не е поддржан, овие денови, барем со хром и некои други. 

И дозволете ми да оди напред и да го забрза овој и да се објасни она што се случува. Ова е демонстрација на меурот вид, првиот алгоритам ние погледна. И тоа е визуелизација со тоа што секој на овие барови претставува број. Поголем, бар, на поголем број. Помалите барот, толку е помал бројот. И она што може да се види визуелно, дури и покрај тоа што ова се случува супер брз, е дека црвената лента е како мене, одење напред и назад одредување проблеми. Можете да видите дека поголемите елементи се навистина жуборот на правото, и помалите елементи се жуборот на левата страна. И овде, ако ние всушност погледнете поблиску, ние всушност може да се избројат на број на споредби и свопови кои биле направени. 

Но, наместо тоа, да ги погледнеме на вториот алгоритам што ја погледна порано со нашите волонтери, селекција вид. Визуелно, има многу различен ефект. Но, тоа е, повторно, многу интуитивен, во да ги исполнуваме изборот на следниот најмалите елемент, и добивме малку среќа. Дека се чувствува фундаментално побрзо. Но, ако ние се стрча ова повторно и повторно и повторно со многу влезови, ќе видите дека тоа е навистина уште е во голема О од n квадрат. 

Ајде да направиме еден последен тука, вметнување вид, кој бил третиот алгоритам ние погледна, и се потсетиме дека ова се занимава со елементи како што ги среќава, но тогаш тоа можеби смени нештата да се направи простор, вметнување на елементи каде што припаѓа. 

И тоа исто така завршува давање на конечниот резултат. Сега сите три од овие чувствував прилично брзо. И, навистина, јас им се стрча во прилично добра клип. Но, во основа, сите тие се прилично страшни, да бидам искрен. Сите од овие алгоритми досега кои работат во големите О од n квадрат да потрае доста од време да се кандидира на крајот. 

И, навистина, може да се види и чувствувате дека ова на крај ако јас се повлече до овој трет и последен демо. Ова е уште еден визуелизација кој ќе да се покаже меур вид на лево, селекција вид во средината, и нешто, како едно од нашите рака крева посочува, спојат вид на десната страна. А подели, па владеј стратегија на десната страна. А тоа е, всушност, она што ние сме ќе се погледне во средата. Но ајде време тие да работат во паралела. Тоа е приближно ист број на елементи, сите работи во исто време. Меур вид vs избор вид vs спојат вид. 

Сега, тие се сите работи во теорија, во исто време. Процесорот е вклучен на иста брзина, но вие може да се чувствуваат како тоа е здодевен многу брзо ќе стане, и колку брзо кога ние внесе малку на неделата алгоритми нула може ние ги забрзаат работите. 

И сега ајде да се споредат овие во еден последен форма. Одам да се оди напред на веб страницата CS50, каде имаме оваа последна алка за денес, каде што некој на интернет љубезно се стави заедно со видео кое доловува она различни сортирање алгоритми за да звучи како. Ова е вметнување вид. 

[Beeping] 

При што ќе бидете примена на фреквенција врз основа на висината на пречката пречката. Ова е меур вид. 

[Наснован beeping] 

Доаѓа следната is-- доаѓаат до следната is-- селекција вид, каде што, повторно, ние сме избирање следниот најмалиот елемент, и може да се види тоа во пораст од лево кон десно. 

Спојат вид, со што нашиот победник досега денес. Забележите како се делат работите во [Беззвучен] половина и четвртини. Gnome вид, што ние не треба зборуваше, и создава визуелно и audally малку различен облик и звук. Ќе напред и назад, чистење работите. Исто така проверете heapsort на веб-страницата на овој човек е. 

И тоа е тоа. Ние ќе се видиме следниот пат. 

[Whooshing И МУЗИКА]