[Грає музика] 

Девід Дж Малан: Це CS50. І це почало тижні три. Таким чином, ми отримали багато цікавої речі, щоб покрити сьогодні. Багато можливостей для добровольців на сцені. І в кінцевому рахунку, сьогодні нема про коді взагалі. Але це про ідеї, і це про алгоритми, а насправді повернути деякі з Уроки, витягнуті з нульовою тижня, де нагадаємо, ми представив це чудовисько. І запозичення натхнення того, щоб почати вирішити все витонченішими проблеми алгоритмічно. Але спочатку пару оголошень. Таким чином, одна, якщо ви хотіли б приєднатися до Співробітники та однокласники CS50 за ланчем в цю п'ятницю, і тут, і в Кембридж, і в Нью-Хейвені, будь ласка, відвідайте Курсу сайт, де URL може бути знайдений. Лекція в середу буде же не бути тут, в Сандерс. Це буде тільки онлайн, так налаштуватися на сайті CS50 на, в Чи тут в Кембриджі або Нью-Гейвен, а також. 

І тоді проблема встановити два вже у ваших руках. Якщо ви не пірнали в ще, дозвольте мені запропонувати сформульоване пропозицію сильно що особливо зараз, в проблема встановлює заздалегідь, Ви дійсно хочете, щоб почати зараз, якщо не плескатися трохи на вихідні або до коли вони вперше вийти на П'ятницях, тому що ви будете знайти, що вони не обов'язково отримувати більше або більш складним в SE. Я думаю, що ви знайдете, що в Взагалі, вони, як правило, приймати приблизно навколо стільки ж часу. Але це, звичайно, залежить на студента, і він залежить від менталітету з якою ви наближаєтеся до нього. Але незмінно, ви збираєтеся запустити проти якоїсь стіни, і ви збираєтеся вдарити якась помилка, і ви просто не буде в змозі отримати над ним в якийсь момент. І це дуже цінно, щоб мати можливість відійти, повернутися наступного дня, перейти до офісних годин, пост на CS50 Обговорити і т.п., насправді отримати розблокований. Так що майте це на увазі. Починаючи раннє, наскільки це можливо це найкраще, що ви можете зробити. Так от, де ми почали клас, за нульовою тижня. І ми можемо отримати добровольця тут, щоб допомогти мені знайти мікрофони? ДОБРЕ. Стоячи вже. Давай до. Вгадайте, що це, як це буде працювати. Як вас звати? АЛАН ESTRADA: Алан Естрада. Девід Дж Малан: Алан Естрада. Давай до. Приємно познайомитись. АЛАН ESTRADA: Приємно познайомитися. Девід Дж Малан: І ви були тут з нами в нульовому тижні, звичайно. АЛАН ESTRADA: я був. Я був. 

Девід Дж Малан: Так може ви йдете вперед і знайти для нас Майк Сміт, так швидко, як ви можете? Як швидко, як ви можете. Буквально розриваючи проблеми в половині, як вам потрібно. 

АЛАН ESTRADA: Хм. Девід Дж Малан: Буквально розриваючи проблему в два рази. 

АЛАН ESTRADA: Ой. Мм. Дуже добре. 

Девід Дж Малан: ОК. Добре. Дякую. АЛАН ESTRADA: Дуже добре. ДОБРЕ. 

Девід Дж Малан: І тепер, Ви звів його до половини розміру проблеми. Тепер, ми до чверті. Ви звертаючи уваги на з якого боку ми тримаємо? 

[Сміється] 

АЛАН ESTRADA: Так, я think-- 

Девід Дж Малан: Який розділ ми в? АЛАН ESTRADA: Глушителі, так. 

Девід Дж Малан: ОК. Але Майк Сміт збирається щоб бути після Глушники. Так-- 

[Сміється] 

Добре. АЛАН ESTRADA: Де ми шукаємо? Девід Дж Малан: Майк Сміт. АЛАН ESTRADA: Майк Сміт. Девід Дж Малан: Тепер ми в хірургічне. Тепер лікарі. Now-- 

АЛАН ESTRADA: Let's- давайте йти з реальною. Нерухомість. 

Девід Дж Малан: Нерухомість. ДОБРЕ. Якщо вам потрібно реальне. Тепер, який шлях Майк Сміт? 

АЛАН ESTRADA: Таким чином. 

Девід Дж Малан: Яким чином? АЛАН ESTRADA: Зачекайте. M is-- правильно? Ми почали with-- 

Девід Дж Малан: Так. Вони залишили. Ваше право. 

АЛАН ESTRADA: Так. 

Девід Дж Малан: Так Майк тут. АЛАН ESTRADA: Що? 

[Сміється] 

Поганий приклад, хлопці. Вибачте. Девід Дж Малан: Це навчить Ви вискочити з свого стільця. 

АЛАН ESTRADA: Ой. Ох. Я вам. Я вам. Ох. Ох. Це is-- ОК, я вам. Сміт прямо тут? 

Девід Дж Малан: Сміт, спасибі. Так що я буду тримати дивлячись Сміт? 

АЛАН ESTRADA: О, так. Ні-ні-ні. О ні. Це моє. 

Девід Дж Малан: О, ви отримали Сміт. ДОБРЕ. 

АЛАН ESTRADA: Так, я отримав Сміт прямо тут. Вибачте, хлопці. Я думав, ми Michael-- шукали Михайла. Вибачте. 

Девід Дж Малан: Це нормально. Гаразд, тепер ми в Paccini і сини. 

АЛАН ESTRADA: Paccini і сини. Девід Дж Малан: Тільки ви і я на цьому. ДОБРЕ. Як нас знайти Майк Сміт. Сміт. 

АЛАН ESTRADA: Сміт. 

Девід Дж Малан: Сміт. Ми в R для сміття. АЛАН ESTRADA: Сміття. Ох. Це займе якийсь час. 

[Сміється] Девід Дж Малан: Взуття. Ми у взутті. 

АЛАН ESTRADA: Тепер ми gonna-- 

Девід Дж Малан: Ніцца. АЛАН ESTRADA: Which-- [Сміється] О, це здорово. [Сміється] 

Девід Дж Малан: Це нормально. 

АЛАН ESTRADA: О, це добре. Я не думаю, що я збираюся є PSAT приятелів після цього. Девід Дж Малан: Добре. Спортивні. АЛАН ESTRADA: Спортивні. Хм, L, M, N, O, П. Девід Дж Малан: ОК. Так що давайте розірвати це навпіл. Все добре. На цьому закінчується погано в будь-якому випадку, тому що Майк Сміт не буде в жовтих сторінках. 

АЛАН ESTRADA: Ой. 

Девід Дж Малан: Ні, це нормально. Але давайте уявимо, як він на цій сторінці. Так що тепер, ви звели проблему вниз на одну сторінку, і ми знайшли Майка Сміта. 

[Радісної] Добре, дякую. ДОБРЕ. Це було незвично. Але це було ще швидше ніж лінійний пошук, де ми починаємо на початку книги, і ми рухаємося наш шлях зліва направо, в кінцевому підсумку, дивлячись на Майка Сміта. І так, якщо телефонна книга був, можливо, 1000 сторінок, може бути, це зайняло б нам 10 або близько того сторінок сльози. 

Але ви, можливо, використовувала торкнувся припущення у все це, що є що в телефонній книзі на заздалегідь було те, що? АУДИТОРІЯ: Сортувати. Девід Дж Малан: Це відсортовані. Вірно? Це відсортовані за алфавітом, тому що всі ці імена та номери упорядковано від А х до Z, і в алфавітному порядку між ними. Але сьогодні, ми тепер запитати питання, ну, як зробив Verizon або телефон Компанія отримати його в такому стані? 

Тому що одна справа використовувати Припущення, що, і тому вирішити проблему з Алгоритм більш ефективно. Але ми ніколи дійсно запитав нульовий тижня, ну, скільки це коштувало Verizon або хтось ще щоб отримати, що телефонну книгу в відсортованому порядку? 

Вірно? Це не має значення, якщо дивлячись Mike Smith супер швидкий, якщо вона приймає вас на рік сортувати сторінки спочатку. Вірно? Ви можете також просто просіяти через рандомізованому телефонній книзі, якщо це буде супер дорого для сортування. Так що, якщо ми можемо мати інший доброволець. Давайте дивитися тут візьмемо як ми might-- приходять на up-- як ми могли б йти про сортування них. 

І якщо насправді міг Йорданія приєднатися до нас тут, на сцені. Давай на мить. Як вас звати? Кароліна: Керолайн. Девід Дж Малан: Керолайн, давай до. І ви будете приєднався мною і Йорданії тут. Керолайн, спасибі. Добре. Отже, що ми маємо тут для Керолайн 26 сині книги що ФАС використовує для управління деякі випускні іспити. Вони стають важко знайти, але те, що ми зробили заздалегідь є те, що ми вклали чиєсь ім'я на передній кожен з них, але ми тримали його простим шляхом потім гасити повні імена. Таким чином, ми б поставити людину з ім'ям L, D, J, B, повністю від А до Z, але вони у випадковому порядку. І так, якби ви, кажу СВІЙ шлях через проблеми, як ви зробити це, ви можете йти вперед і сортувати їх для нас, від А до Я. 

АУДИТОРІЯ: ОК, так що я, як, середній. С починає. Б. Дж, перш ніж Л. В, В. 

Девід Дж Малан: Тримайте, що думав протягом однієї секунди. Бо інакше, це тільки цікавими для вас, мене і Йорданії. Там ми йдемо. АУДИТОРІЯ: [нерозбірливо]. Р. Девід Дж Малан: ОК. Що ви робите? 

Кароліна: М приходить після О. 

Девід Дж Малан: ОК. 

Кароліна: О. Девід Дж Малан: О, добре. 

Кароліна: Е. 

Девід Дж Малан: E, F. Так. 

Кароліна: T, U, V. 

Девід Дж Малан: V, T, U, V. Так-то воно Схоже, ви making-- продовжувати. Схоже, ви робите велика купа тут, і вид великої купи там. Таким чином, перша половина алфавіту, Друга половина алфавіту. ДОБРЕ. Добре. Вид поділу проблеми на дві частини. M, N, Х. Так. Кароліна: К. Девід Дж Малан: ОК. К. Отже, ви начебто вибору їх один за іншим, покласти його вліво або вправо, або Z збирається на підлозі. ДОБРЕ. 

Кароліна: Z збирається на підлозі. 

Девід Дж Малан: ОК. У збирається на підлозі. Тепер ми можемо поставити X. 

Кароліна: Г. Девід Дж Малан: G відбувається залишилося. S йде правильно. Гаразд, А пройшовши весь шлях вліво. 

Кароліна: A, B, C, D. 

Девід Дж Малан: Тепер, добре. У нас є A, B, C. Вт збирається там. Гаразд, Т. 

Кароліна: H, I, J. Девід Дж Малан: H, I, J. Добре. Кароліна: У центрі, я gonna-- Девід Дж Малан: ОК. Так що тепер, ми збираємося виду злиття цих різних паль. Таким чином, через С, тоді я бачу D, і Е, F і і G і Н, І. Ніцца. J, К. А потім, це купа з ніг на голову, але це нормально. Звичайно. Ми можемо скоротити деякі кути. ДОБРЕ. І тоді ми повинні W, X, Y, Z. 

Кароліна: Так. 

Девід Дж Малан: Відмінно. Таким чином, велике спасибі Керолайн для сортування них. 

[Радісної] 

Дякую. Велике спасибі. Так що тепер давайте на хвилину як Керолайн ходив, що і що саме ми змогли, метою яких, як ми змогли вирішити, що Проблема, коли ми були просто враховуючи цілий букет випадкових входів. 

Ну, схоже, є було небагато системи там? Право. Так раніше листів в алфавіті, вона був покласти ліворуч, а пізніх букви в алфавіті, вона була покласти в правий. І як тільки вона знайшла деякі проксимальних літери, ті, які йдуть поруч один з одним, вона вкладати їх в порядку. І таким чином, ми були свого роду ці маленькі купи відсортованих входів, що відбуваються. 

І так, що цілком як те, що більшість з нас люди будуть робити. Ми начебто просіяти через нього, і ми начебто є механізм. Але це може бути важко, щоб написати його вниз у формулі як такої. Він відчував себе трохи більш органічним, ніж це. Отже, давайте подивимося, якщо ми можемо в даний час межі Проблема з меншою кількістю входів. 

Замість 26, давайте зробити щось набагато менше з просто сказати, сім, за ці двері, так би мовити. Є тільки сьомій чисел? І якщо мета тепер в рука, щоб знайти значення, давайте подивимося, наскільки ефективно ми можемо йти про це. І давайте подивимося, якщо ми можемо в даний час почати застосовувати деякі цифри, або деякі формули, з якою, щоб описати ефективність нашої телефонній книзі Алгоритм, наш алгоритм іспит книги, і в більш загальному, пошуку інформації. 

Таким чином, для цього, дозвольте мені йти вперед, і на сенсорному екрані сюди, поставити веб-браузер, який має саме ці сім дверей. І якщо ми могли б отримати один добровільно прийти на тут, Я поклав ці ж двері тут. Швидкий громадських засадах. 

Це одно-- демо збираються до все швидше і швидше в даний час. Йдемо вниз. Як вас звати? Тревор: Тревор. 

Девід Дж Малан: Тревор? Гаразд, Тревор, давай вниз. Так Тревор добровільно тут, щоб зробити подібну проблему, але це вужчим за обсягом, і що відбувається щоб дозволити нам, щоб спробувати оформити в даний час процес сортування ці цифри. 

Так Тревор, приємно зустрітися з вами. Так от масив, так кажуть, список з семи дверей. Ідіть вперед і знайти нам номер 50. І потім, після того факту, розкажіть, як ви його знайшли. Якщо be-- всі права. Так, це один тут? Ой-ой. ДОБРЕ. Ви натиснули, що один. Добре. 

І добре. Тепер ви натиснули цю. І дозвольте мені дати вам мікрофон, так що у вас є це в мить. Ідіть вперед і натисніть поруч, що ви маєте намір. Так добре. Тревор: Чи можу я повторно клацніть двері? Девід Дж Малан: Ні, ви не можете повторно клацніть. Тревор: ОК. Ось цей. Девід Дж Малан: Де ви хочете піти? Який? 

Тревор: Це одне. 

Девід Дж Малан: Ні 

Тревор: ОК. Ось цей. 

Девід Дж Малан: Так. Це було добре. Добре. Так що ж ваш алгоритм або Процедура для цього, Тревор? 

Тревор: Я тільки що пройшов через двері, поки я не знайшов 50. Девід Дж Малан: ОК. Відмінно алгоритм. Так що все в порядку. Тому що справді, якщо я відкрию що за цими двома іншими дверима, те, що ми знайдемо тут є те, що у нас є тільки випадковий вхід. Так що насправді, як було добре, як ви могли б отримати. І справді, ви отримали краще, ніж вичерпно пошуку весь масив, тому що це було б дійсно пощастило, якщо ви вдарив кількість 50 в самий останній двері. Але що, якщо ми замість дав вам припущення. Припустимо, що я ніби все ці двері навколо, так що у вас є номера сортуються в цей раз, але цього разу він насправді different-- цей раз, це насправді упорядковано для вас. А тепер ставите боку полягає в хіт номер 50. 

Тревор: ОК. 

Девід Дж Малан: Що ваш алгоритм буде? 

Тревор: Ну, якщо це сортується, це або відбувається щоб be-- якщо великий, щоб за величиною, спаданням, це буде перший, або, якщо це навпаки, це буде останнім. Так що я просто натисніть цю двері, і Потім просто натисніть на останню двері. Девід Дж Малан: Відмінно. Добре. Таким чином, ми знайшли номер 50. Тому, як тільки ви знали, вони були відсортовані, ми змогли використати це припущення. Так що вони занадто багато, як приклад телефонної книги. Як тільки у вас є, навіть з невелика проблема, як це, Ваші входи попередньо відсортовані, ми можемо насправді знайти значення можливо більш ефективно. 

І я не кажу вам, якщо це було відсортовано мала до велика, або великого до малого, і так було дуже розумно щоб почати на одному кінці або інший насправді знайти, що цільове значення. Так що спасибі Тревору, а також. І я propose-- красиво зроблено. У нас є невеликий кліп, насправді, що є одним з наших улюблених моментів у CS50, в результаті чого іноді ці демки не зовсім за планом. І справді зараз я під'їхав неправильний інтерфейс з якою використовувати сенсорний екран. Так це була моя вина є. 

Так що це буде зробити для кліп в наступному році, як чому я був натиснувши на моєму власному екрані. Але давайте поглянемо на те, що сталося торік з Джеєм, який придумав, багато як Тревор тут, добровільно, і в цьому короткий кліп, ви побачите як ця ж демонстраційний не зовсім виявити ті ж уроки, витягнуті. [ВІДТВОРЕННЯ ВІДЕО] -Все Я хочу, щоб ви зараз зробити, це знайти для мене, і для нас, дійсно, число 50 один крок за один раз. 

-Кількість 50? 

-Кількість 50. І ви можете виявити те, що За кожним з цих дверей просто торкаючись його пальцем. Блін. 

[Сміється] 

[КІНЕЦЬ ПЕРЕГЛЯДУ] Девід Дж Малан: Так що пішли дуже добре. Ті були несортовані двері. І Джей, звичайно, знайти все це занадто швидко. Тревор зробив набагато кращу роботу в термінах доступний момент, так би мовити, в цьому році в займає більше часу, щоб знайти його. Звичайно, тоді ми дали Джей другий шанс, в результаті чого ми відсортували двері, як ми це робили для Тревора, і Тревор зробив супер добре в цей раз. Але Джей зробив це в два рази швидше. [ВІДТВОРЕННЯ ВІДЕО] -The Метою тепер є також знайти нам номер 50, але зробити це алгоритмічно, і розкажіть нам, як ви збираєтеся про це. 

-ДОБРЕ. 

-А Якщо ви знайдете його, ви тримаєте кіно. Якщо ви не знайдете його, ви дати його назад. 

-Man. 

-Ой! 

- [Нерозбірливо] ОК. Так що я збираюся перевірити кінці спочатку визначити, якщо there's-- О. 

[Оплески] 

[КІНЕЦЬ ПЕРЕГЛЯДУ] Девід Дж Малан: ОК. Так сортування двері ясно призводить до більшої ефективності. І так, в два рази швидше це те, що я мав на увазі там. І так Джей пощастило обидва рази. І він також пощастило в минулому, що рік, я замовив кілька Blu-Ray дисків насправді видають. Мені шкода, цього року ми не мають те ж саме, Тревор. Але все-таки краще було кілька років тому. І деякі з вас, можливо, знаєте, це хлопець, Шон, який, коли він був у CS50, був кинутий виклик з точним Та ж проблема, хоча і в SD, як ви скоро побачите, тому в день. І ви побачите, що не тільки зробив він займе трохи більше часу, ніж Джей, трохи більше, ніж Тревор, це було насправді це прекрасна можливість займатися майже всі в Натовп ла Ціна праворуч, заохочуючи йому знайти номер, ми шукали. Давайте. взяти швидкий погляд. 

[ВІДТВОРЕННЯ ВІДЕО] 

-ДОБРЕ. Так ваше завдання тут, Шон, полягає в наступному. Я сховав за ними Двері число сім. Але захований в деяких з цих дверей а також інші негативні числа. І ваша мета, щоб думати цієї верхньому рядку чисел як тільки масив, або просто Послідовність папірців з номерами позаду них. І ваша мета, використовуючи тільки верхню Масив тут, знайти мені номер сім. І ми потім збирається критикувати як ви йдете про робити це. -Добре. -Знайти Нам номер сім, будь ласка. Немає. П'ять, 19, 13. 

[Сміється] 

Це не питання з підступом. Один. 

[Сміється] На даний момент, ваш рахунок не надто добре, так що ви могли б також продовжувати. Три. 

[Сміється] 

Продовжуй. Чесно кажучи, я не можу допомогти, але цікаво, те, що ви навіть думати про, so-- 

[Сміється] Тільки верхній ряд, так у вас є три зліва. Так що знайдіть мені сім. 

[Сміється] 17. Сім. 

[Оплески] 

Добре. 

[КІНЕЦЬ ПЕРЕГЛЯДУ] 

Девід Дж Малан: Таким чином, ми могли дивитися це протягом усього дня. І, звичайно, деякі з демо в цьому році, можливо, Тепер буде в кінцевому підсумку в наступний відео року, а також. Так що тепер давайте насправді зосередитися на алгоритмах тут, щоб побачити, якщо ми не можемо Тепер починають формалізувати як ми можемо йти про отримання наших даних в цьому стані, що це сортується, так що в кінцевому рахунку, ми можемо насправді шукати його більш ефективно. І хоча ми збираємося використовувати досить невеликі набори даних, як ми восьмій чисел Тобто тут, на борту, в кінцевому рахунку, ці ж ідеї можна застосувати 1000 входів, мільйон входів, 4 млрд входи, тому що алгоритми будуть принципово те ж саме. 

І таким чином, це наш останній можливість для добровольців сьогодні, але, мабуть, найбільш активна участь одного, для яких ми повинні восьмій добровольців прийти і ходити з нами через Процес сортування, що скоро бути на цих музику варто тут. Дозвольте мені почати знову тут. 

Таким чином, одна в turquoise-- зелений це? Ви вчиненні? Два. Йдемо вниз. ДОБРЕ. Три. Чотири. Нехай me-- ОК, п'ять. Ви висувається вашим другом. Шість, сім, вісім. Давай до. Добре. Дуже дякую. Давай до. Давай до. 

Добре. Так що у нас є here-- і це є одним з найбільш незручних ті, так як це вимагає, щоб ви гумор мені протягом тільки трохи часу. Ви повинні бути номер один. Як вас звати? 

АННАН: Аннан. 

Девід Дж Малан: Аннан. Девід. Як вас звати? 

ЙОСИП: Джозеф. 

Девід Дж Малан: Йосип, Ви номер два. 

Серена: Серена, номер три. Стефан, номер чотири. СИНТИЯ: Синтія. Девід Дж Малан: Синтія, номер п'ять. [Нерозбірливо] Девід Дж Малан: [нерозбірливо]. Девід, номер шість. Метт: Метт. Девід Дж Малан: кількість Метта сім. І що ж? 

WAVERLY: Уеверлі. 

Девід Дж Малан: Уеверлі, номер вісім. Добре. Якщо ви could-- вигуки. Якщо ви все, як ваш Перше завдання, є восьмій пюпітри тут перед аудиторією. Якщо б ви могли помістити свої номери на Ці музичні виступає таким чином, що вони шикуються з ті ж номери на дошці. Так що самі виглядати по покласти ваші номери на цих музиці варто тут. Відмінно досі. 

Відмінно. ДОБРЕ. Так що тепер, ми збираємося запитати Питання в кілька різних способів. Як ми можемо йти про сортування ці люди тут? Тому що у нас було кілька підходів раніше, в результаті чого ми були вигляд робить дві різні відра. А потім ми, як правило, пірсингом речі разом. Як тільки ми побачили дві цифри який належав разом, покласти їх разом. Два листи, які належать разом. 

Але давайте подивимося, якщо ми не може оформити це, так що в кінцевому підсумку ми повинні деякі псевдо-код буде, за допомогою якого можна вирішити ці проблеми. Так що тепер, я дивився на ці цифри тут. І я бачу цілу купу помилок. У кінцевому рахунку, я хочу один на вліво і вісім на правій. 

І тому я, дивлячись на ці два, чотири і два. І в чому проблема, очевидно ,? Так. Так. Два явно йде перед чотирьох, так що ви знаєте, що? Дозвольте мені спочатку взяти жодній підхід, якщо ви будете, як і проблема встановити одно-- якщо ви пам'ятаєте з Стандартна редакція завдання один набір, де я тільки локально вирішити проблему що прямо тут переді мною і побачити, де вона веде мене. 

ДОБРЕ. Так два і чотири, дозвольте мені перейти вперед і просто поміняти вам два. Якщо ви можете фізично перемістити самі і ваша газета, Я, здається, отримали перерахувати в кращому стані. 

Тепер, вони гарні. Я збираюся рухатися далі, чотирьох і шести, виглядає добре. Не проблема. Шість і вісім, ОК. Вісім і один, ще одна проблема. Бо правда про вісім і однієї? Один приходить до восьми, і так, що ми повинні робити? Давайте поміняти ці два. Один і вісім. А тепер, я збираюся продовжувати. Я збираюся продовжувати дивитися вперед. І давайте подивимося, що станеться. Вісім і три, з Звичайно, в порядку. Давайте своп. Вісім і сім, звичайно. Вийшов з ладу. Давайте своп. Вісім років і п'ять, звичайно, давайте підкачки. Добре. Список сортується. так? 

ОК, очевидно, немає. Але це трохи краще, вірно? Тому що повідомлення, що сталося. Кожен раз, коли ми провели обмін, менше Кількість і тип проціджують, що шлях, і більше число перколюють цей шлях, або ми будемо почати говорити пропускають до вліво або барботируют вправо. 

Тепер, це не достатньо, тому що в кращому випадку число може перейшли одне місце вперед, або в гіршому випадку, ряд, можливо, переїхав на одну позицію далі. Таким чином, ви знаєте, що цей вид з працював дуже добре дотепер. Дозвольте мені спробувати ще раз. Два і чотири, вони ОК. Чотири і шість, вони ОК. Шість і один, вийшов з ладу. Отже, давайте поміняти вам два. А тепер зверніть увагу, що проблема-х починають отримувати трохи краще знову. Шість і три, вийшов з ладу. Давайте міняти вас два. Шість і сім, ви добре. Сім і п'ять, звичайно, в порядку. Сім і вісім, в порядку. А тепер, я, можливо, буде потрібно зробити це кілька разів. І справді, думаю, для себе можливо, скільки разів максимально може я повинен ходити взад і вперед? 

Ми повернемося до цього. Так два і чотири раніше ОК. Чотири і один, Ні. Отже, давайте своп. І знову, зверніть увагу, візуально один з бульбашок вид ліворуч, де він повинен бути. Чотири і три заміни. Чотири і шість. Шість і п'ять підкачки. Шість і сім. Сім і вісім хороші. 

Добре. Ми отримуємо ще краще. Отже, давайте подивимося. Тепер у нас є два і один. Звичайно, поміняти. Два і три, три і чотири, чотири і п'ять, шість і сім, сім і восьмій. Добре. І ви знаєте, що? Тому що я зробив одну зміну є, дозвольте мені зробити одну перевірку осудності. Дозвольте мені пройти весь шлях повернутися до початку. ДОБРЕ. Один з них, two-- да, бачите? Щось було не так. Три, чотири, п'ять, шість, сім, вісім. І в цьому останньому проході, є ви можете прямо зараз з моїм стверджуючи, що це сортується? ДОБРЕ. Візуально, це абсолютно вірно. Але функціонально, ніж так і просто так в цьому останньому проході, що дозволяє щоб підтвердити, що цей список дійсно відсортовано? 

Що я робити або не робити цього останнього пасу? АУДИТОРІЯ: Там не було ніяких змін. Девід Дж Малан: Вибачте? АУДИТОРІЯ: Немає змін. Девід Дж Малан: Там не було ніяких змін. Так що було б нерозумно з мого боку зробити це знову той же алгоритм якщо я не зробити будь зміни в перший раз. І держава не змінилася. Звичайно, я не збираюся робити будь-яких змін вдруге. І так, це тепер у безпеці сказати, список відсортований. 

І справді, це зараз те, що ми будемо, як правило Виклик бульбашкового сортування, в результаті чого попарно, вам виправити помилки знову, і знову, і знову, і вам тримати вперед і назад, ні і назад і вперед, поки ви не роблять такі свопи, на яких точка Ви можете бути впевнені, що, так, я закінчив фіксації всіх помилок. Давайте скидання і спробувати інший підхід. Якщо ви, хлопці, могли б повернутися в замовлення ви були хвилину тому, який виглядав, як це. Тепер, давайте розглянемо підхід, трохи більше, як іспит книги, в результаті чого ми були постійно вибравши букву алфавіту що ми якось хотів щоб мати справу з іншою. Може бути, це був високий лист, як А, або низької букви Z. 

Таким чином, кожен повернувся цього порядку. А тепер дозвольте мені зробити це. Давайте подивимося, я знаю, що є вісім цифр тут. Я збираюся йти вперед і просто свідомо вибрати найменші елементи. Вірно? Це, здається, інтуїтивно теж. Чому я не можу знайти найменший елемент, покласти його, де вона належить, а потім отримати наступний найменший елемент, поставити це, де це належить, і тільки повторити. 

Тому що інтуїтивно, який повинен працювати теж. Так чотирьох, це досить мале число. Я буду пам'ятати, де це. Почекай хвилинку. Два менше. Дозвольте мені тепер згадайте, коли два є, і забути про чотирьох. Ми будемо мати справу з цим пізніше. Шість, мені це не цікаво. Вісім, я не зацікавлений в. Один мій новий мале число. Так що я збираюся згадати, де ти є. Три, не цікавить. Сім, не цікавить. П'ять, не цікавить. 

Так, не падаючи етап у цьому році, Я збираюся захопити кількість одно-- і те, що знову ваше ім'я? 

АННАН: Аннан. 

Девід Дж Малан: Аннан. І якщо б ви могли приєднатися до мене в початок списку, давайте вам, де ви належите. Unfortunately-- що ваше ім'я? 

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

Девід Дж Малан: Стефан знаходиться в дорозі. Тому, перш ніж Стефан вирішує цю Проблема, що ми повинні робити? Що ми робимо зі Стефаном? 

АУДИТОРІЯ: [нерозбірливо]. Девід Дж Малан: ОК. Таким чином, ми могли б зробити це. Ми могли б прийняти своєрідний Стефана і його чотири, і просто покласти його в змінній і провести на ній деяка кількість часу, тим самим звільняючи місце для номер один. І це не погано. Я міг би запропонувати, чому не ми просто покласти Стефана тут? Чому це може порушити одне ідей ми почали говорити про останній час, минулого тижня? Так? 

АУДИТОРІЯ: [нерозбірливо]. 

Девід Дж Малан: Там немає Індекс для нього. Якщо ви думаєте, це, дійсно, як Масив, це як негативний, так що немає насправді пам'ять тут, якщо це дійсно масив, як ми оголосили минулого тижня в лекції. Таким чином, ми не повинні робити цього. Ми могли б зберігати його в змінної. 

Чи ви знаєте, що? Я чув, хтось ще запропонувати це. Що ще ми можемо зробити зі Стефаном? Чому б нам просто не виселити його і покласти його на себе, де номер один було. Так що, якщо ви хочете піти туди. І справді, це досить хороше рішення. Тепер, з одного боку, я начебто з зробив проблему гірше. Чотири тепер далі від того, де це повинно бути. Вона повинна бути до цього половині. 

Але ви знаєте, що? Це можна було б невезіння. Можливо, номер вісім був тут. І так, може бути, ми б отримали пощастило, і штовхнув восьмій ближче до кінця. Таким чином, в кінці кінців, Це частково всі середні з. Нам не потрібно піклуватися про чотирьох. Все, що я дбаю про прямо зараз вибору найменшого елемента. 

А тепер, що я збираюся зробити, це забути про номер один постійно, тому що я знаю Список позаду мене тепер сортуються. Так що мій список був раніше розмір восьмій. Тепер, це розмір сім. Так моя проблема стає менше, хоча лінійно. Так що тепер, я збираюся вибрати ток найменший елемент, два. Шість, вісім, чотири, три, сім, п'ять. Це був найменший елемент. Так що я збираюся зробити with-- який був ваше ім'я? 

ЙОСИП: Джозеф. 

Девід Дж Малан: Джозеф? Ми збираємося, щоб залишити Йосипа на місці. Тепер, я збираюся робити вигляд, що ці хлопці добре are--, Я знаю, що ці два вже відсортовані. Давайте тепер зосередитися на Інша частина списку. Шість є поточним найменшим. Вісім більше. Чотири тепер ток маленький. Три тепер струму мала. І ось тепер, я збираюся вибрати три, які is-- що ваше ім'я знову? Серена: Серена. Девід Дж Малан: Серена, якби ви могли захопити ваш номер і своп with-- Калсанг: Калсанг. Девід Дж Малан: Калсанг. Повертайся, і ми збирається поміняти ці два. А тепер, давайте поставити це на автопілоті. Я збираюся піти і залишити його з вами, хлопці щоб вибрати наступні найменші елементи. Дун, сірувато, сірувато, сірувато. Номер чотири, що ви повинні робити? Відмінно. Тепер, я збираюся зробити ще один прохід. Дун, сірувато, сірувато, сірувато. Я бачу п`ять є наступним найменшим. Тепер, я збираюся взяти ще один прохід. Дун, сірувато, сірувато, сірувато. Шість є найменшим. Добре. Сім найменших. Без змін. Вісім найменших. Готово. 

Так що ми тільки що зробили итеративно вибравши один елемент за іншим це реалізувати те, що ми збирається оформити у виборі роду. І це, можливо, навіть простіше пояснити, в тому, що буквально все, що ви хочу зробити, це просто тримати вперед і назад за списком вибору, наступний найменший елемент, поки ви не закінчите. 

Так що це навіть простіше, можливо, інтуїтивно, ніж торік. Давайте спробуємо один останній. Якщо ви, хлопці, може скинути себе в наступних положеннях один останній раз, давайте подивимося, якщо ми не можемо Тепер оформити ще один підхід. Справді, хтось там би запропонувати як ще ми могли б йти про це? Без викинути слівця або роду відповідей, які вже відомі, просто інтуїтивно, що ми могли зробити? 

АУДИТОРІЯ: [нерозбірливо]. Девід Дж Малан: Так. Так що деякі великі інтуїція є. Хороші речі, здається, досі трапляються в комп'ютерній науці, коли ми ділимо і завоювати проблему поділу це в два рази і половина на половину. І так насправді, ми може почати робити це. І справді, що буде, ми будемо см, один з наших кращих рішень поки. Але давайте повернемося до того, що незабаром. Насправді, ми збираємося зробити що трохи пізніше на цьому тижні. Що ще ми могли б зробити, щоб вирішити цю проблему? Таким чином, кожен тут в здавалося б, випадковому порядку. Знаєш, що? Замість йти вперед і назад, взад і вперед, взад і вперед кожен раз, це відчуває себе подібно Я роблю багато ходити. Чому я не можу просто почати в початок списку, і просто поставити чотирьох, де вона належить? Отже, дозвольте мені припустити, що в даний момент мій список тільки цей перший елемент. Чотирьох сортуються в цей момент часу, якщо все, що я дбаю про те все тут? Це свого роду тривіально, чи не так? Як список, що містить один номер, і що номер чотири, очевидно, сортуються. 

Отже, дозвольте мені просто обмовити що цей список сортується. Але тепер у мене є все інше в цьому списку. Так що тепер, я стикаюся з два. Де два, очевидно, належать відносно чотирьох? Перед чотирьох. Так що я можу тут робити? Ваше ім'я знову? 

ЙОСИП: Джозеф. 

Девід Дж Малан: Йосип, якби ви могли відступити на мить з вашим номером. А тепер те, що повинно Стефан тут робити? Давайте перекласти Стефана сюди. А тепер, давайте Йосип прийшов сюди. А тепер, дозвольте мені заявити, що тут все сортується. Так, аналогічний результат, але Принципово інший підхід. Я навіть не дивився, що там внизу. Я просто продовжувати приймати елементи як вони передали мені, і боротьби з ними. 

Так що тепер, я бачу, номер шість. Де номер шість належать? У нас є два, чотири, шість. Точно, де вона зараз знаходиться. Так що давайте залишимо в спокої, що, і в даний час стверджують, що цій частині списку тепер сортуються. І так, це відчуває себе принципово відрізняється тим, що я просто переміщення за списком тут лінійно, і я ніколи не подвоєння тому. Так. Добре. Так восьмій, де ви належите? Саме тут. Ідеальний. Так що тепер, один. Ой-ой. Це відчуває, як ніби це буде дорого. Тепер, в попередньому алгоритмі, Я просто помінялися людей. Так що я поклав йому може повністю на початок, але потім переїхав Йосипа. Але, якщо я переїду Йосипа, тепер що буде так? 

Тепер, я начебто undone-- У мене приймати один крок вперед, а потім один крок назад, тому що тепер Джозеф буде в порядку. Так давайте зробимо це. Якщо б ви могли взяти номер один і крок назад на мить. Як ми можемо put--, що Ваше ім'я було знову? 

АННАН: Аннан. 

Девід Дж Малан: Аннан на місці? Що має відбутися щодо до двох, чотирьох, шести, восьми і? Всі вони повинні перемістити. Так що, якщо восьмій хотів перекласти , А потім шість, потім чотири, потім два. І тоді Аннан, якби ви хотів приїхати сюди, добре. Але тут, ми тільки вид заплатила в іншій точці в алгоритмі. У той час як останній раз з вибором сортувати і навіть бульбашкового сортування, Я йду назад і вперед, назад і вперед, який, безумовно, додавши, до Час-мудрий, і буквально поетапно. 

Сортування вставками, на перший погляд, виглядає, як ніби це супер розумнішими, в тому, що я просто повільний, поступовий прогрес, але я не збираюся це назад і вперед. Але якщо хтось дійсно із порядку, попередження всі роботи я просто повинен був зробити. Мені довелося переїхати половина списку просто, щоб звільнити місце для номер один. Так що це те ж саме кількість роботи досі його відчуває, просто інший тип роботи. 

Давайте продовжимо. Так що тепер ми знаємо, що кожен від одного до восьми сортуються. Ось, у мене є номер три. Якщо ви хочете, щоб забрати Номер три крок назад один. І те, що ви, хлопці, потрібно зробити? Так. Так що ще один, два, три кроки. Три одиниці часу, які просто стоять я, так що три можуть тепер підходять. Нарешті, сім. 

Давайте йти вперед і Ви крок назад. Це буде тільки коштувати нам одна одиниця часу, але це нормально. А тепер, п'ять збирається бути трохи дорожче. Якщо ви хочете зробити крок назад. Ми повинні рухатися восьмій, і сім, а шість. І тоді все буде тепер сортуються. Таким чином, велика рука, щоб наші добровольці тут. Дуже дякую. 

[Оплески] 

Дякую вам всім. Дякую вам всім. Отже, давайте подивимося, як тепер просто дорого все, що було. Давайте розглянемо, мабуть, Найпростіший з них, бульбашкова сортування. І я кажу простий, тільки тому, що Ви можете вирішити її з жадібністю, просто виправити попарно проблема. Закріпіть попарно проблеми Тут, знову і знову і знову, повторюючи як багато раз, як ви насправді потрібно. 

Так що виходить, що з бульбашкового сортування, добре, скільки кроків я повинен взяти на себе перший прохід цього алгоритму? Я міг би take-- давайте see-- один, два, три, чотири, п'ять, шість, сім. І є вісім елементів тут. Так як п мінус 1 до кроки отримати від початку списку в кінці списку. 

Але вибору-то, нагадаємо, що я знову і знову, вибираючи елементи і знову, що це маленький, Я ставлю його на місці, але тоді я не шукаю позаду мене знову. Так що я думаю, що це трохи більш ясним те, що в перший раз, я міг би повинні прийняти всі п мінус 1 кроки знайти найменший елемент. Тоді я поставити їх на місце, і я виселити хто був тут раніше. 

Але тоді я не повинен тримати дивлячись на цей елемент, тому що я знаю, що це Вже найменшим. Так що тепер, я можу дивитися на всього сім елементів, то шість елементів, потім п'ять елементів, то чотири елементи. І так математично, якщо п число елементів або цифр що ми почали з того, що ви можете собі що це те ж саме, п мінус 1, плюс мінус 2 п кроків, плюс мінус 3 п кроків, плюс мінус 4 п кроків, все аж до всього один крок. І я на моєму останньому людини. 

І якщо ви пам'ятаєте, що багато з книги або статистика математичні книги є ті формули, на твердій палітурці назад або перед ними, з'ясовується, що цієї серії може бути виражено більш просто мінус, як у п раз п 1 над 2. І це нормально, якщо це не на передньому краї свого розуму. Але це дійсно так. Це просто простий спосіб написання. І потім, якщо ви думаєте, повернутися до початковій школі, коли ви тільки починаєте множення речі з, це, звичайно ,, просто н квадраті мінус п ділиться на 2. Все, що я зробив, це розширити висловлювання там. І так давайте перепишемо це трохи по-іншому. Ось н квадраті розділити на 2 мінус п / 2. 

Отже, ще раз, я просто вид застосування деякі арифметичні правила є. Але зверніть увагу, в даний час, що найбільша термін в цьому виразі, так би мовити, є те, що п в квадраті. Так що, так, це п квадрат ділиться на 2, мінус п / 2. 

Але в цілому, якщо п буде велике значення, Я збираюся стверджувати, що п в квадраті буде домінуючим фактором. Це просто буде велика внесок на число кроків, ніж N / 2. Так що я маю на увазі під цим? Давайте спробуємо простий приклад, навіть хоча математика отримує трохи більшим. 

Отже, нехай у нас було 1 млн осіб на сцені, або 1 млн речей що ми хочемо, щоб розібратися. Давайте підключити мільйон в цій формулі точно щоб побачити, скільки кроків він приймає загальної сортувати мільйон елементи, використовуючи скажімо, Вибір роду. 

Таким чином, ми повинні були б ту ж формулу, як і раніше. Я підключити мільйон, так що я отримую мільйон квадрат поділяється на 2, мінус мільйон розділити на 2. Якщо я що математику в заздалегідь тут, у нас є 500 млрд мінус 500000, який дає нам +499999500000, що чертовски великий. 

Справді, якщо порівняти з підприємством 499000000000 999 млн 500000 проти нашої первісної вартості, 500000000000, це так чертовски близько. Вірно? п квадраті розділити на 2 дає us-- або, скоріше, н квадраті розділити на 2 дав нам 500 млрд. Це чертовски близько щоб 499,999,500,000, який повинен сказати, віднімання від 500000, або в більш загальному, віднімаючи від п квадраті, насправді не велика справа. У Російській квадрат робить ці число виросте дуже швидко. 

Тепер, це тільки важливе значення, оскільки як ми, як комп'ютерні вчених, як правило, не буде піклуватися так багато про нюанси цих формул і саме те, що точні відповіді. Ми піклуємося лише, що, ви знаєте, що? Зрештою, ця формула складає близько п квадрат. 

Так, ми поділу на 2 в там. Так, ми віднімаючи від п мінус 2. Але врешті-решт, термін що насправді шкодить нам і варто нам багато кроків, що квадрат термін. І так, що вчений-комп'ютерник збирається як правило, роблять це ігнорувати всі ті менші терміни, порядок і просто подивитися на той, який сприяє найбільш до вартості. 

І це приємно, тому що ми можемо Тепер поговоримо набагато більшої спільності про алгоритми, і може порівняти їх. І той факт, що я за допомогою цього висновку є навмисним. Коли я кажу про порядок з, я спеціально посилаючись на те називається великий О. І Big O це позначення, що комп'ютер Вчений використовує, щоб описати верхня межа на щось. 

Так що, якщо ви говорите, що алгоритм у великому O н квадрат, як я запропонував просто Хвилину тому, що кошти що з точки зору його експлуатації часу або його ефективність, вона займає порядку н квадраті кроки. Може бути, більше, може менше. Але це на порядок п в квадраті. І це верхня межа. Це не буде більш болючим, ніж це. Це не буде п кубі, або 2 до п, або щось набагато більше. Це верхня межа на те, що, що вартість. Тому, враховуючи, що, давайте Розглянемо кілька прикладів. І це тільки кінцевий список дуже загальні часу проходження Для алгоритмів, які призначається, щоб бути ілюструють деякі речі, які ми бачив вже. 

Так, наприклад, у випадку Вибір роду, що я стверджуючи, тут працює, що вибір Сорти час на порядок п в квадраті. У гіршому випадку, я буду мати ціла купа випадкових чисел тут. І, як ми бачили математично, якщо я постійно ходити за списком, через Список, вибравши наступний маленький елемент знову і знову, якщо я насправді записати всі кроки Я приймаю я запропонував formulaically перш, це близько п квадратів кроки, які я приймаю. 

І виходить, що міхур відсортуйте сортування вставками так само, як повільно в гіршому випадку. Розглянемо, наприклад, сортування вставками, найостанніший алгоритм ми мали справу з, який змусив нас подивитися на елемент, а потім вставте його там, де він належить. А потім ми дивилися на наступний елемент, і вставляється там, де він належить. 

Так вважають кращий можливий сценарій. Припустимо, я мої добровольці шикуються буквально, як це, від одного до восьми, вже відсортовані. Скільки кроків є сортування вставками збирається зробити, щоб розібратися вісім чоловік, якщо вони прибувають на сцені дивлячись, як це? 

Вісім чоловік вже відсортовані. І я використовую вставки роду. Це останній з алгоритмів. Ну, давайте відтворити дуже швидко. Так що, якщо я починаю тут, я бачу один. Де ж можна належать? Він належить тут. Я бачу два. Де двоє належать? Саме тут. Я бачу зо три. Де три належать? Саме тут. 

Я бачу чотири. Саме тут. П'ять, шість, сім, вісім. Там немає причин, щоб повторюватися. І так, скільки кроків є те, що через п? Це на порядок п кроки, вірно? п мінус 1. Але я взяв лінійний номер кроків, і тепер я зробив. Так що це кращий випадок, хоча. Що можна сказати про гіршому випадку? Що вісім минулого там, і сім були там, і один і два були тут, так що список дійсно були назад? 

Ну, те, що відбувається насправді якщо це число? І ми будемо робити тільки пару прикладів. Що робити, якщо, дійсно, номер вісім тут, і number-- вигуки. Так що, якщо, дійсно, кількість Вісім повністю тут, і я використовую вставки роду? 

ДОБРЕ. Я стверджую, на даний момент він знаходиться в місці. Але тепер, seven-- де ж самі сім йти? Звичайно, це йде тут. Так що я повинен рухатися восьмій над одному місці. Тепер шостій, де це йде? Ну, все в порядку. Тепер, я повинен рухатися восьмій над місце, і сім над місцем, і тоді я плюхнутися шість. 

Таким чином, перший раз, це вартість мені один крок, щоб виправити становище, то це коштувало мені два кроки, щоб виправити становище. Скільки кроків це збирається зробити, щоб виправити речі, щоб поставити п'ять у потрібному місці? Три. Тому що тепер я повинен рухатися один, два, три. Скільки кроків він збирається взяти покласти чотири в потрібному місці? 4 плюс 5, плюс 6 плюс 7. 

І так це математично ідентичні те, що ми описали для вибору роду. У нас є ця серія ось тільки зростає. 1 плюс 2 плюс 3 плюс 4, або, навпаки, плюс 7 червня плюс 5 плюс 4 додає на сьогодні Цілі в порядку п в квадраті. 

Отже, дозвольте мені передбачають також, що бульбашкового сортування також у п квадраті. Тому що з бульбашкового сортування, кожен раз я йду за списком, Я приймаю приблизно, скільки кроків? Кожен раз, коли я буквально ходьби від туди потрапити? Приблизно п кроків. Але скільки разів я міг би потрібно йти за списком? 

Ну, приблизно п раз. Може п мінус 1, але приблизно в п раз. Ну, чому ж? Ну, з бульбашкового сортування, якщо ми починаємо з бульбашкового сортування, зі списком в гіршому ситуація, яка знову повністю у зворотному напрямку, то, що станеться? Я йду за списком, і номер одним належить весь шлях туди. 

Але з бульбашкового сортування, наскільки робить один рухатися на моєму першому проході за списком? Скільки місця він отримує ближче до правильного місця? Тільки один. Так що, якщо вас вид причина через це, кожен раз, коли через цей алгоритм, Давида, що приймають близько п кроків. Але скільки проходить через список його збирається взяти для одного міхура ліворуч, де вона належить? 

Він повинен рухатися, як, п простору таким чином. Так що, щоб зробити сортування списку, Я повинен ходити взад і вперед п раз. І кожен раз, я дивлячись на п елементів. Так що російські речі п раз на порядок п в квадраті. 

Тепер ми побачимо, в деяких шортів, що вбудовані в наступної проблеми CS50 в встановити, інший підхід в них, але зараз, давайте просто розглянемо деякі інші поточні часи, особливо якщо взяти ті сортування небагато часу, щоб зануритися в. Що таке алгоритм ми вже бачили що бере на себе порядку п кроків? 

Що слід прийняти лінійний номер кроків, які ми бачили дотепер? Що це? Пошук телефонний довідник. Перший алгоритм. Вірно? Де ми лінійно пошук Майк Сміт? Дійсно. Від нульової тижня, коли я почав перетворюючи одну сторінку в той час, і я навіть сказав, що це був вид алгоритму лінійної почуття, і у нас було що картинка на дошка з прямою червоної лінії і прямої жовтий лінія, це були дійсно алгоритми, які у великій O п. 

Тому що, щоб знайти Майка Сміта в телефоні Книга російських сторінок, в гіршому випадку, може взяти мене н кроки. Що про прийняття відвідуваність? Один два три чотири п'ять шість. Що час роботи цього Алгоритм для прийняття відвідуваності? Великий О п, тому що в теорії я повинен вказати всіх в кімнаті. 

Тепер, як в сторону, те, що про другий оптимізації з нуля тиждень? Два, чотири, шість, вісім, 10, 12. Комп'ютер вчений буде реалізувати, зачекайте хвилину, це близько п ділиться на два етапи. Вірно? Тому що я роблю дві людини одночасно. Але ми збираємося ігнорувати ці молодші члени, і ми тільки збираємося викинути розділити на 2, і просто сказати, великий виведення п для цього алгоритму, а також. 

Як щодо цього? Ми пропускаємо деякі з них, але те, що був алгоритм, який був журнал п? Це зайняло приблизно увійти п кроків? Розділяй і володарюй. Точно. Як, наприклад телефонної книги в нульовий тижня і сьогодні вранці, де ми розділили проблеми знову і знову, і знову. Ми звернули його на дошці в тиждень нулю при зігнутої зеленою лінією, і ми сказали, що це був день логарифмічна алгоритм. 

І справді, число кроків, вона, потрібно, щоб виконати розділяй і володарюй, або бінарний пошук, як ми почнемо називаючи його, як в телефонній книзі, на порядок журналі і кроків. І це трохи дивно одне. 

Що робить крок, або, більш конкретно постійне число кроків? Може бути, це двоє, може бути, це три, але вчений просто спрощує його як Big O 1, деяка константа число кроків. Щось ви могли б зробити, що бере постійну кількість кроків? 

Що час роботи ляскаючи? Постійне час. Вірно? Мовляв, те, що час роботи робити що-небудь, що бере тільки один Операція, як друкувати F Hello World. Це може бути названо постійна часу, якщо менше кут випадку з F друк, Що може час роботи друку F насправді бути? І чому? Що н вимірювання в цьому випадку? 

АУДИТОРІЯ: [нерозбірливо]. Девід Дж Малан: Точно. Кількість символів ми хочемо, щоб надрукувати. Так що це дуже контексту. Сьогодні ми зосередилися багато на букви і цифри тут на дошці. Але це може бути також символи в реальну рядок. Ось і виходить, є інший міра, яка почне піклуватися про, і це навпроти великого О, так би мовити. 

Це омега позначення. У той час як більша виведення означає, що це, то Верхня межа на біговій часу? Максимально, скільки часу може щось взяти? Omega-- шкода, що це продовжує прибувати up-- є протилежністю, що в результаті чого це нижня межа на кількість часу щось може зайняти. 

Так. Наприклад, те, що алгоритм який приймає завжди н в квадраті кроки? Ну, один з алгоритмів ми бачили Сьогодні, насправді, може бути, що, як добре. Сортувати Вибір. Вибір роду досить безглуздо. Навіть якщо algorithm-- вибачте, навіть якщо масив вже відсортовані, Вибір роду збирається продовжувати йти за списком щоб переконатися, що він має найменше елемент знову і знову, і знову. І хоча ви, люди в Глядачі знають, що, почекай хвилинку, Ви вже прийнятий найменший елемент, комп'ютер не знає, що, поки вона виглядає весь шлях через список. Аналогічним чином, нижня межа, що може бути також прийняті до уваги може бути лінійний час. 

Скільки часу потрібно, щоб Сортувати п елементів в краще Справа використовуючи щось на зразок міхура роду? Припустимо, що ваш список вже відсортований. Ми сказали, бульбашкова сортування бере на порядок п квадраті кроки. Але що, якщо це вже відсортовані? Що робити, якщо ви розумієте, після один прохід по масиву що ви не зробили жодного свопи? Ви повинні продовжувати робити більше проходить? 

Немає. Таким чином, нижня межа бульбашкового сортування можна сказати, бути лінійною. Омега п. І ми можемо дивитися на решта них, а також. Отже, давайте поглянемо на тільки візуалізації тут щоб побачити, як вони відрізняються. Я збираюся піти сюди в це сторінка, яка доступна на веб-сайті С50, в але це буде біль, щоб отримати роботу, так як він використовує технологію під назвою Java-аплети, який є в значній мірі підтримується в ці дні, принаймні, Chrome і деяких інших. 

І дозвольте мені йти вперед і прискорити цей і пояснити, що відбувається. Це демонстрація міхура сортувати, перший алгоритм, ми дивилися. І це візуалізація, що кожен з цих стрижнів являє собою число. Чим більше бар, тим більше число. Чим менше бар, чим менше число. І те, що ви можете побачити візуально, навіть хоча це буде дуже швидко, є те, що червона смуга, як мене, ходити взад і вперед фіксації проблеми. Ви можете бачити, що чим більше елементів дійсно б'ється праворуч, і менше елементів які б'ється зліва. І тут, якщо ми насправді виглядають більш тісно, ми можемо насправді підрахувати кількість порівнянь і обмінів що були зроблені. 

Але замість цього, давайте подивимося на другому алгоритмі ми дивилися на раніше з нашою волонтери, вибір сортування. Візуально він має дуже різні ефект. Але це, знову ж таки, дуже інтуїтивним, в що ми тримаємо вибору наступного маленький елемент, і ми отримали трохи пощастило. Це відчував принципово швидше. Але якщо ми побігли це знову і знову і знову з великою кількістю входів, ми побачимо, що насправді це ще у великій O п квадраті. 

Давайте зробимо один останній тут, сортування вставками, який був третім алгоритм ми дивилися на, і відкликання що це одна справа з елементи, як це стикається їх, Але тоді, може бути, зрушення речі, щоб звільнити місце, вставки елементів, де вони належать. 

І це теж закінчується даючи Остаточний результат. Тепер всі три з них відчував себе досить швидко. І справді, я побіг їх на досить хороший кліп. Але принципово, всі вони досить жахливо, чесно кажучи. Всі ці алгоритми досі які працюють у великому O п квадраті прийняти зовсім небагато час для запуску в кінці кінців. 

І дійсно, ми бачимо, і відчуваю, що це, нарешті, якщо тягнути цю третю і останню демо. Це ще одна візуалізації, що відбувається, показати бульбашкового сортування ліворуч, Вибір роду в середині, і щось, як один з наших Рука піднімає раніше запропонував, об'єднати то справа. Розділяй і володарюй Стратегія праворуч. І це, насправді, те, що ми будемо дивитися на середу. Але давайте час ці балотуватися паралельно. Це приблизно те ж саме кількість Елементи, все працює в той же час. Пузир роду проти вибору Сортувати проти злиття роду. 

Тепер вони все працює У теорії, в той же час. Процесор працює на з тією ж швидкістю, але ви може відчувати себе, як нудно це дуже швидко стане, і тільки, як швидко, коли ми вводимо трохи тиждень алгоритми Зеро може ми прискорити. 

А тепер давайте порівняємо це в останній формі. Я збираюся йти вперед на сайт CS50, де у нас є цей заключний посилання на сьогодні, де хтось в Інтернеті люб'язно воєдино відео, захоплює те, що різне сортування алгоритми звучати. Це свого роду вставки. 

[ЗВУКОВИЙ СИГНАЛ] 

Причому ви претендуєте частоту заснована на висоті бар бар. Це свого роду міхур. 

[Викривленням ЗВУКОВИЙ СИГНАЛ] 

Далі йде is-- на наступному is-- вибір роду, де знову, ми вибору наступний найменший елемент, і ми можемо бачити, як він росте зліва направо. 

Злиття сортувати, наш переможець досі сьогодні. Зверніть увагу, як це ділення речі в [нерозбірливо] половину і чверті. Гном роду, які ми не маємо говорили, і створює візуально і audally трохи різна форма і звук. Перехід вперед і назад, очищення речі. Крім того, перевірити пірамідальної сортування на веб-сайті цього хлопця. 

І це все. Ми побачимо вас наступного разу. 

[Свист І МУЗИКА]