>> [Музика Відтворення]
>> Девід Дж. мала: Добре.
Так що ласкаво просимо назад.
Це CS50, і є До кінця тижня три.
>> Так згадаємо в останні кілька тижнів, Ми проводили досить багато
час на C, з програмування, з синтаксису.
І це цілком нормально, якщо ви все ще бореться з проблемою встановити 2, щоб бути
битися головою об стіну.
Це загадкове виду повідомлення про помилку а помилки, які ви
Не цілком може погнати вниз.
Тому що, будьте впевнені, що всього за час кілька тижнів ви будете оглядатися на
речі, як Цезар, і [? V-genair,?] може бути, навіть тріщина, і
розуміють, наскільки далеко ви приїхали протягом короткого періоду часу.
Так що, якщо це втішить, повісити там на даний момент.
>> Сьогодні, однак, ми починаємо перехід до речей більш високого рівня.
І ми починаємо вважати само собою зрозумілим, що ви, хлопці, знаєте, як програмувати, або, по крайней
міру початку що рівень комфорту.
І ми почнемо, як ми можемо йти про розробку програми більш
ефективно.
Як ми можемо йти про оптимізацію Ефективність наших алгоритмів і
взагалі вирішення більш цікаві завдання.
І починають вважати само собою зрозумілим, що, якщо б ми хотіли, ми могли б код до будь-якого
з прикладів ми маємо на увазі.
Таким чином, сьогодні ми не чіпайте клавіатуру будь-якої форми коду.
Це буде набагато вищому рівні, і У кінцевому рахунку, про вирішення проблем.
>> Таким чином, щоб дістатися до цієї точки, то дозвольте мені висунути що наступні сім
прямокутники представляють сім'ю дверима, за які цілий букет
номери, серед яких число 50.
Дозвольте мені проектувати на цьому Екран тут також.
І пропоную потрібен доброволець, щоб допомогти знайти мені номер перед
Інтернет тут, щоб подивитися.
Піднімайся, в рожевому.
Добре.
Як тебе звуть?
>> Дженніфер: [нерозбірливо]
>> Девід Дж. мала: Пробачте?
>> Дженніфер: Дженніфер.
>> Девід Дж. мала: Дженніфер.
Гаразд, Дженніфер.
Дуже приємно.
Піднімайся.
Таким чином, ці ось сім дверей, і те, що Я хочу, щоб ти зробив для нас тут,
на очах у всіх своїх однокласників, це знайти нам номер, 50.
Щоб знайти номер, ви можете зазирнути за будь-який з цих дверей, просто натиснувши
на одній з дверей, і це покаже його номер.
І давайте подивимося, як швидко ви можете знайти нас числом, 50.
>> 15.
16.
50.
Красиво зроблено.
Добре.
Оплесків для Дженніфер.
>> [Оплески]
>> Добре.
Так яка була ваша стратегія знаходження числа, 50?
>> Дженніфер: Хм, я думав, може бути, якщо -
[Нерозбірливість]
>> Девід Дж. мала: Ох.
Дайте йому одну секунду.
Так була ваша стратегія знаходження числа, 50?
>> Дженніфер: Так що я просто почати в починаємо бачити те, що перший номер
було, а потім я подумав: може бути, якщо вони сортуються, я буду просто продовжувати
натиснувши вище?
>> Девід Дж. мала: OK.
І ми, здається, знайшли , Що, щоб мати місце.
Хоча, давайте відігніть верств тільки трохи, і ви хочете піти
вперед і розкрити інші двері Ви могли б обрали?
>> Дженніфер: О, любий.
>> Девід Дж. мала: Ах.
>> Дженніфер: Так, мені просто пощастило.
>> Девід Дж. мала: Таким чином, ви пощастило.
Добре.
Так не погано.
Але це цікаво розуміння, чи не так?
Якщо передбачається, і ви дійсно отримували, Дійсно, трохи пощастило там.
Але якщо припустити, що номери були упорядковано, ви можете бути більш точним
, Як, які вплинули Ваша поведінка?
>> Дженніфер: Так що, якщо в них розібралися, я думав, може бути, від меншого до більшого.
>> Девід Дж. мала: OK.
>> Дженніфер: Або, якщо це закінчило тим, дійсно великий, то від більшого до меншого.
>> Девід Дж. мала: OK.
Так що від більшого до меншого, або меншого до більшого.
Але дозвольте мені запропонувати, припустимо, що у вас було отримали не пощастило, і припустити, що вони
були, по суті, сортують, скільки ці двері може у вас було зазирнути
за що в гіршому випадку?
>> Дженніфер: Всі з них.
>> Девід Дж. мала: Всі з них.
Так що давайте узагальнювати, що при п.
Там, виявляється, 7, але давайте більше зазвичай кажуть, що є N на двері
Екран тут.
Таким чином, в гіршому випадку, вам доведеться зазирнути за 7 дверей, двері або н.
І так це насправді, це трохи удачі сьогодні, але це дійсно лінійний
Алгоритм у дусі, навіть якщо ви були частково пропускаючи навколо.
Хіба це справедливо?
>> Дженніфер: Так.
>> Девід Дж. мала: Ну, дозвольте мені побачити, якщо ваш Стратегія зміни, якщо я переїду нам
В якості другого прикладу тут з 7 різних дверей.
Однакові номери, але це час вони сортуються.
Що ваша стратегія тут буде, намагаються поставити в своєму розумі, що
інші номери були -
>> Дженніфер: OK.
>> Девід Дж. мала: - раніше?
>> Дженніфер: Давайте почнемо з першою.
>> Девід Дж. мала: Добре.
Почнемо з першого.
4.
А де ви збираєтеся піти, і чому?
>> Дженніфер: 4 дійсно малий.
Так що, якщо вони роду, може бути, найменша до великих, він повинен
, Що в два рази, і -.
>> Девід Дж. мала: OK.
Давайте подивимося, що ви думаєте?
>> Дженніфер: Спробуйте останній.
Ніццу.
>> Девід Дж. мала: Дуже красиво зроблено.
Добре.
>> [Оплески]
>> Девід Дж. мала: OK.
Так що насправді ви робите це жахливо, тому що ти
робить це дуже добре.
Що залишає нас нездатними зробити певні точки.
Так давайте спробуємо тут відкат.
>> Дженніфер: OK.
>> Девід Дж. мала: Добре зроблено, тим не менш.
Отже, ви почали з самого початку, Ви бачили, що це було 4, то ви
переміщається в кінець.
Але припустимо, що ви не повезти там, і припустимо, 50
був десь в іншому місці.
Що ваш третій крок був?
>> Дженніфер: Догори.
>> Девід Дж. мала: Поверніться до початку.
Отже, ви б вже торкнувся ці двері, яка була 8.
Добре.
Так що це не 50.
Де б ви дивилися далі?
>> Дженніфер: Якби я не знають, що вони відсортовані.
>> Девід Дж. мала: Правильно.
Ну, якщо ви знали в них розібралися -
>> Дженніфер: О, знав, так.
>> Девід Дж. мала: - Але ви не знаю, де був ще 50?
>> Дженніфер: Просто продовжуйте йти.
>> Девід Дж. мала: Добре.
ОК.
Продовжуйте.
Добре, що я можу працювати.
>> Дженніфер: OK.
>> Девід Дж. мала: Тепер, якщо ви просто збираємося продовжувати, як тебе
Алгоритм покладених загнаний у.
>> Дженніфер: лінійна -.
>> Девід Дж. мала: Це різновид лінійної.
Але дозвольте мені запропонувати, нехай мені покласти на місці.
Дозвольте мені оновити сторінку.
ж число, однакове розташування, ж дверей.
Але згадайте, що перший день у класі, коли ми розірвали в телефонній книзі
половину, начебто, і те, що було нашої стратегії є?
>> Дженніфер: Початок в середині.
>> Девід Дж. мала: OK.
Так починаються в середині.
Так що давайте йти вперед і імітувати це.
Початок в середньому по Показово, що двері.
Таким чином, число 16.
Отже, що б сильний хлопець зробив, хто зірвав телефонну книгу в два рази,
щоб дістатися до наступного Guess?
>> Дженніфер: Перейти в цю половину.
>> Девід Дж. мала: А чому б не так?
>> Дженніфер: Якщо вони були видом найменша до великих, то 50 повинно бути
в цьому напрямку.
>> Девід Дж. мала: Добре.
Повністю розумним.
Так як телефонна книга, ви йдете в право на відміну від лівої сторони, але тут
є ключовим їжі додому.
Тепер ви можете або просто викинути його відірвати, половина цієї проблеми, залишаючи вас не
з 7 дверей, але насправді всього лише 3.
Що приблизно половина Масштаби проблеми.
Добре.
Так що тепер вам доведеться зроблено після ви йдете прямо?
>> Дженніфер: Так 16 все ще досить малий, в порівнянні з 50, так що, можливо, я постараюся,
як, на цей раз.
>> Девід Дж. мала: Добре.
42.
Гаразд, так що тепер твоя інстинкт говорить вам?
>> Дженніфер: Я можу викинути це, а потім просто -
>> Девід Дж. мала: OK.
Добре, ви можете викинути Ліва половина там.
>> Дженніфер: - вибрати цього.
>> Девід Дж. мала: І правильно.
>> Дженніфер: Так.
>> Девід Дж. мала: Тому, навіть якщо це важко , Щоб побачити, можливо, коли є тільки
7 дверей, подумайте про те, в даний час, узгодженість
алгоритму, який просто застосовується.
У попередньому випадку, ви зробили повезти, яка була відмінною.
Але ви дійсно використовував евристичний, Я б сказав.
Ви використовували роду своїм інстинктам, і знаючи, що це розсортувати це досить
слабкий на початку, очевидно, ми в треба йти правіше.
Але в певному сенсі, Вам пощастило, , Тому що, може бути, це був номер 100,
і, можливо, було більше 50 в середині.
Може бути, навіть 50 було тут.
>> Але те, що ви зробили трохи по-іншому на цей раз було, ви зробили те ж саме
знову і знову.
І я стверджую, що те, що ви просто дійсно, хоч і залежить від телефону
Книга Наприклад, щось набагато більш алгоритмічного і багато
менше спеціальних обсаджених.
Набагато менше інстинктивним.
Таким чином, в кінці дня, як би Ви описали ефективність
Перший алгоритм, куди ви пішли зліва направо, порівняно
Другий алгоритм тут?
>> Дженніфер: Це потрібно, як, можливо, вдвічі скоротити час, або навіть більше, так.
>> Девід Дж. мала: Добре, може бути, навіть більше.
Давайте натиснути трохи сильніше на цьому.
Те, що дійсно, якщо ми будемо продовжувати цю логікою, ми, безумовно, вдвічі
час роботи з цією другий алгоритм відкиданням половини
цифри, але те, що ми зробили на наступний ітерації, коли Дженніфер показала
друге число?
>> Ми вдвічі кількість дверей знову.
І що тоді ми зробили після цього, якщо було більше дверей, щоб грати з?
Ми б удвічі скоротити їх, і знову, і знову і знову.
І це було так само, як ви, хлопці, все стоячи на першому тижні
класу, половина з вас сидить, половина з вас сидить, половина з вас
не сідати, поки в один самотній Душа стояла.
І ми говорили, що час роботи , Що кількість кроків, що було потрібно,
про порядок і що?
>> Виступаючий 1: [нерозбірливо]
>> Девід Дж. мала: Так логарифм за основою 2 п, або просто простіше кажучи, увійти н.
Так щось логарифмічна.
І графіка була не пряма лінія , Що стало ще гірше і гірше, це було
цю цікаву криву, що не отримати так погано з плином часу.
Так що давайте триматися за цю ідею.
Давайте дякувати Дженніфер.
Спасибо большое, що прийшли і вище.
І, однієї секунди.
Немає настільних ламп сьогодні, але ми дійсно є CS50 кулі стресу.
>> Дженніфер: Ура.
>> Девід Дж. мала: Добре, тут.
Дякуємо за несучи стрес тут.
Добре.
Отже, давайте подивимося, якщо ми не можемо зараз формалізувати це трохи більше.
Отже, ще раз, що ми тільки що зробили, практично те ж саме, як ми зробили
, Що в перший тиждень.
Але замість того, закінчується просто лінійна Алгоритм, який ми зображені
Раніше, як ця пряма, якою, якщо покласти ще одні двері
екрана, а потім Дженніфер б повинні були виглядати, можливо,
за ще одні двері.
Якщо ми поставимо ще двоє дверей, вона може мати зазирнути за дві двері.
>> Так от, там була ця лінійна відносини між розміром
Проблема, скажімо, на осі х, а Кількість часу, необхідне для
вирішити на у.
Але картина, яку я мав на увазі раніше була Ця зелена лінія.
Зелений навмисно, тому що він просто відчув себе краще.
У теорії, алгоритм, коли ми зробили це з телефонною книгою, коли ми зробили це
з вами підрахунок один до одного, і У другому випадку, коли Дженніфер просто
зробив це тут, це був свого роду принципово краще.
Тому що це було не тільки в два рази швидше.
Це була навіть не в чотири рази швидше.
Це було повністю залежить від того, що Розмір вхідного було відносно того, скільки
кроки, які він в кінцевому рахунку прийняв.
>> І ось ця проста ідея, що ми всі взяли само собою зрозумілим з телефонною книгою,
Аналогічним чином можна застосовувати щось на зразок цього.
І це могло б бути більш недбало відомий як, як можна було б
уявити, розділяй і володарюй.
Не в відміну від того, що ми зробили, звичайно, з телефонною книгою.
>> Але псевдокод, нагадаємо, було це.
Тому ми не будемо робити це знову, але згадати У перший тиждень, всі ми встали
а потім і половину ви сіли, половина з ви сіли, половина з вас сіл.
Цей алгоритм був реалізований в Трохи обману речі, в тому, що воно
не тільки один з мене підрахунку По суті, більш ефективно.
У такому випадку, я використовуючи вторинний ресурс.
Начебто, кілька процесорів, кілька мізків, кілька розумних людей в
Номер мені допомагали отримати від чогось лінійної до чогось
логарифмічні, від чогось червоне на щось зелене.
>> Але в даному випадку, Дженніфер тільки й може принципово поліпшити
виконання свого першого алгоритму, знову, просто подумавши трохи складніше.
І тепер, коли приходить час для реалізації ці речі, з'ясовуючи
які рядки коду ви можете написати такий що ви можете повторювати їх знову, і
знову, і знову, як би Алгоритм циклічно повторюється.
Тому що ви не будете мати розкіш, як Дженніфер зробили спочатку, щоб
просто ціла купа IFS і сказати: хм, якщо це перше число 4,
Дозвольте мені стрибати всю дорогу до кінця.
Ох, якщо це число занадто велике, Переходжу довільно тому
другий елемент.
Ви побачите, що це збирається бути багато важче формалізувати те, що ми, люди,
прийняти як належне, як дуже розумний евристики, але комп'ютер тільки
збираюся робити те, що ви скажете їй зробити.
>> Тепер це дуже цікаво наслідки.
Цей графік є свого роду означало для сортування розтрощити візуально, але повідомлення, де
є прямою на цьому графіку?
Де лінійний графік , Які ми називаємо п?
Ну, це ніби до нижнього цієї картини, чи не так?
Так що все, що ми зробили, ми є вид зменшенні до осі Х і
Y-осі, щоб спробувати отримати відчуття того, що іншими типами кривих виглядати.
>> І специфіка математичного Вирази сьогодні не буде мати значення так
багато, але зауважив, що є багато алгоритми, які набагато гірше, ніж
те, що це лінійна.
Дійсно, N кубі виглядає досить погано.
2 до N виглядає досить погано. N квадрат виглядає досить погано.
І ми побачимо, що деякі з цих може бути в сьогоднішній реальності.
І журнал N не відчуває, як погано, але краще, ніж п логарифм за основою 2 н.
Але ви знаєте, це було б ще більше дивно, якщо Дженніфер, або якщо ми,
У перший тиждень, придумали те, що це журнал журнал N.
>> Отже, іншими словами, є всі це Діапазон можливих рішень
проблеми, але навіть тут, повідомлення що станеться.
Коли я зменшити масштаб, який з цих кривих збирається виявитися абсолютним
гіршого з тих, на екрані тепер?
Таким N куб виглядає досить погано на даний момент.
Але якщо ми зменшення і бачити більше X і Y-осі, хто збирається
домінувати в кінцевому рахунку?
Так що насправді виявляється, що від 2 до N, і ви можете зрозуміти це просто
підключення в деяких більших номери, і ви побачите, що від 2 до
N, дійсно, стає все більше набагато швидше.
Якщо ми дійсно зменшити масштаб, 2 до N алгоритм абсолютно смокче.
Я маю на увазі, що це збирається взяти зовсім небагато часу для того,
Комп'ютер у великій кількості через.
>> Але ви побачите, з часом, особливо з майбутніми домашні завдання і навіть
дипломні проекти, це ваші дані набір отримує великі, все гаразд?
Навіть у першій версії Facebook, як кількість друзів і
число зареєстрованих користувачів отримали великі, Ви можете сортувати її в телефон і
здійснити те, з лінійним пошуком, або дуже простий сортування
Алгоритм, як ми побачимо сьогодні.
Ви повинні почати думати важче і важче про ці проблеми.
І типи проблем таких місцях, як Facebook, і Google, і Microsoft,
та інші роботи є саме ці роду великі сортування даних питань
більше в ці дні.
>> Добре.
Так що успіх Дженніфер в цьому другому Алгоритм, чесно кажучи, вона зробила дивно
а в перший раз, але давайте пишу це як удачу, так що ми
може зробити цю точку.
У другому випадку, вона використовувала Алгоритм, який повторюється знову і
знову, але вона прийняла як належне певні припущення, що ми дозволили
їй, але вона використана деякими подробицями другий раз, що у неї не було
перший раз.
Що було що?
>> Те, що список був відсортований.
Тому, як тільки список був відсортований, ми стверджують, що Дженніфер була в змозі зробити
принципово краще.
7 дверей, так, вже не так цікаво, Однак припустимо, що ми 7000000 дверей.
Журнал N, безумовно, буде виконувати багато, багато
швидше в довгостроковій перспективі.
Але вона повинна була бути Двері відсортовані для неї.
Тепер, я взяв на себе сміливість зробити це Заздалегідь на екрані комп'ютера
тут, але припустимо, що Дженніфер повинен був зробити це самій?
Припустимо, що двері в питання представлені дані в базі даних, або
Друзі зареєстровані для Facebook, або будь-який веб-сторінки в Інтернеті, які
різні веб-сайти, можливо, буде потрібно в індекс або пошук.
>> Припустимо, що ви тільки що вихідні дані встановлений, і це залишили для Вас, або
Дженніфер це зробити сортування?
Це, швидше, вимагає, щоб ми відповідаємо питання, ну, скільки часу
взяв би Дженніфер, або навіть мене, для сортування цих цифр заздалегідь, щоб
що вона може скористатися цим?
Вірно?
Тому що мається на увазі, звичайно, якщо це займе якийсь час, щоб розібратися
номерів, хто, чорт візьми, що ви піклується можна знайти таке число, як 50 так швидко,
як у випадку з Дженніфер, якщо ми більш перевантажені кількість загального часу
знадобилося сортуванням речей заздалегідь?
>> Отже, давайте подивимося, якщо ми не можемо намалювати картину тут.
У мене є ціла купа більше стресу куль, якщо це допомагає
зламати лід тут.
І якщо ви не проти, ми потрібно сім добровольців -
о, добре.
Нічого собі.
Так що ми не повинні витрачати на настільні лампи, здається.
Добре.
Так, як ви два на передній панелі.
Як щодо вас двоє хлопців у спині.
Так от чотири.
Як щодо вас перед п'ять, шість і сім.
Ось тут.
Ваш друг, вказуючи вам, так що ви отримаєте приз.
>> Добре.
Піднімайся.
І чому б нам не мати вас Хлопці іди сюди.
Я збираюся дати вам кожен ряд.
І піти далі і влаштувати собі однаково до того, що
зображено на екрані.
>> [Проміжне VOICES]
>> Девід Дж. мала: Oop, вибачте.
Помилка.
Добре.
Ну, ось ми йдемо.
Номер п'ять.
Номер шість.
Один, два, три, чотири, п'ять, шість, сім.
О, це незручно.
>> Доповідач 2: Я буду просто отримати -.
>> Девід Дж. мала: Дуже.
Добре.
Дякуємо за участь.
>> [Оплески]
>> ОК.
Добре.
Отже, ми маємо чотири, два, шість, один, три, сім, п'ять.
Прекрасно, таким чином ми маємо сім добровольців тут, які дорівнюють по ширині
масив, який ми граємо з раніше.
І я вибрав сім з причин які будуть просто
зручна в небагато.
І я збираюся запропонувати спочатку, що ми сортуємо ці сім добровольців.
Якщо ви хотіли б, по-перше, , Щоб привітатися, хоча.
Так як це буде ніяково кілька хвилин.
Назвіться.
>> GRACE: Привіт, я Грейс.
Я на другому курсі в Леверетт будинок.
>> BRANSON: Привіт.
Я Бренсон.
Я на першому курсі у зварюванні.
>> GABE: Привіт.
Я Гейб.
Я молодший у Кабот.
>> Ніл: Я Ніл.
Я на першому курсі в Метьюз.
>> Джейсон: Я Джейсоном.
Я на першому курсі в Greenough.
>> Майк: Я Майком.
Я на першому курсі в сірих.
>> Джессі: Я Джесс.
Я на другому курсі в Леверетт.
>> Девід Дж. мала: Відмінно.
Добре.
Що ж, спасибі всім нашим добровольці тут досі.
І завдання під рукою тепер збирається бути для сортування з цих хлопців, але потім
ми збираємося мати трохи подумати над тим, як ефективно ми насправді
сортував їх.
Так давайте спочатку спробувати це.
Ви, хлопці, можете бачити один одного номера просто шляхом розміщення навколо кутів.
Йти вперед і приймати кілька секунд, а Розбийтеся від найменших на
ліворуч найбільших праворуч.
Go.
>> ОК.
Добре.
Це було дійсно штопати швидко.
Тепер хтось тут, що був алгоритм що ці хлопці застосовувати?
>> Виступаючий 1: найменшого до найбільшого.
>> Девід Дж. мала: OK.
Найменшого до найбільшого дійсно свого роду мети, але я не впевнений, що це
дійсно алгоритму.
Меншого до більшого не говорить мене крок за кроком, що робити.
Так?
>> Виступаючий 1: [нерозбірливо]
>> Девід Дж. мала: OK.
Так що якщо ви бачите людину, менше, ніж свій номер, а потім перейти до
праворуч від них.
Так що тепер стає все більш виразним, більше схоже на алгоритм, тому що ви
можна говорити, якщо це, те, що.
Тому у нас є свого роду умовні конструкції.
І ці хлопці, здавалося, зробив, що кілька раз, тому що деякі з вас переїхав трохи
від відстані.
Так з'явився імовірно якийсь цикл відбувається в їх умах.
>> Але давайте спробуємо формалізувати це.
Якщо ви, хлопці могли скинути назад таким компонуванням.
Давайте подивимося, якщо ми не можемо формалізувати трохи, а потім поставити запитання, просто
наскільки ефективно це?
Звичайно, коли ми робимо це більш повільно, він буде почувати себе як благо
алгоритм, але давайте подивимося, якщо ми можемо поставити наші пальці на конкретні кроки.
>> Таким чином, ви два хлопця і чотири два.
Або Ви правильним чи неправильним замовленням?
Очевидно неправильно.
Таким чином, ми помінялися місцями.
Тепер я збираюся відійти убік тут і говорити, 5:56.
Ви правильно чи неправильно?
>> GABE: Правильно.
>> Девід Дж. мала: Правильно.
Шість і один?
Нє-а.
Підкачки.
Так от змінами.
Шість і три?
Нє-а.
Підкачки.
Шістьма і сім'ю?
Виглядає добре.
Сім і п'ять?
>> Джессі: [нерозбірливо]
>> Девід Дж. мала: Добре, обміняти.
І сортуються.
Добре.
Так, очевидно, немає, чи не так?
Так було більше відбувається.
Але, справді, ці хлопці, навіть просто інстинктивно.
продовжував рухатися.
Вони не просто зупинитися, як тільки вони виправлена ​​одна проблема.
Так.
Більше того, я буду мати зробити те ж саме.
Я збираюся повинні розібратися задніх перемотування до початку цієї проблеми
або на початку цього масиву люди, давайте почнемо називаючи їх.
>> І тепер, які повинні мій алгоритм на другому проході бути?
>> Виступаючий 1: Те ж саме.
>> Девід Дж. мала: Те ж саме.
І це, я починаю любити, чи не так?
Як тільки ви можете знайти собі робити одне і те ж знову і знову, це
все більше походить на алгоритм, і менш людський інстинкт.
>> Так що тепер, тут ми йдемо знову.
Два і чотири?
Ні.
Чотири і один?
Ах, було дійсно деякі роботи, яку ще належить зробити.
Для і три?
Добре.
Чотирьох до шести?
Шести і п'яти?
Шістьма і сім'ю?
Добре, тепер, зроблено.
ОК, немає.
Я повинен повернутися.
>> Так що тепер, знову ж таки, ми робимо це трохи більш свідомо.
А тепер, є тільки один мозок виконання цього алгоритму.
Один процесор, якщо ви будете.
І, чесно кажучи, це єдиний ресурс, ми будемо мати доступ.
І як тільки ми дійсно повертаємося до клавіатури і є щось на зразок C у нашому
розпорядженні, ми тільки пишемо програму , Які можуть зробити одну річ за один раз.
Беручи до уваги, ці хлопці хвилину назад, ми позикових їх колективного розуму
як ви, хлопці зробили в тиждень нулю.
Так що давайте продовжувати робити це.
>> Два с.
Два і три.
Три і чотири.
Чотири і п'ять.
П'ять і шість.
Шість і сім.
Робити?
Так що я, але дозвольте мені грати Адвокат диявола.
Я теж, начебто комп'ютера, який просто зробив пас через цей масив
люди, знають, що я зробив?
>> Виступаючий 1: N:
>> Девід Дж. мала: Так чому?
Що я повинен зробити для того, щоб рішуче укласти, що я зробив?
Напевно, ще один прохід.
Вірно?
Тому що все, що я знаю з попереднього прохід, що я виправив помилку.
А значить, може бути, є ще одна помилка
що мені потрібно виправити.
Тому я можу лише бути впевнені перемотувати, і Потім перевірка, 1:59, двох-і
три, три і чотири, чотири і п'ять, п'ять і шість, шість і сім.
Добре, тепер я не зробив ніякої роботи.
>> Я не можу, звичайно, пам'ятаєте, що я зробив не працювати з чимось як змінна,
подобається Int.
Назвіть це свопи, свопи і якщо дорівнює 0, як тільки я потрапити сюди, і це почалося в 0, то
Я б просто нерозумно продовжувати йти взад і вперед, перевіряючи знову, і
знову, і знову, чи не так?
Тому що, якщо ви застрягли в деяких вид нескінченний цикл.
Тому, як тільки є 0 свопи, ми можемо стверджувати, що це
Алгоритм дійсно повним.
>> Тепер, давайте поставимо на цьому ім'я.
Алгоритм, який я пропоную, ми просто реалізоване те, що називається міхуром
виду, відомого як такої в тому сенсі, що числа, великі види
Пузир їх шлях до вершини, або до в кінці масиву чисел.
Але наскільки ефективним був цей алгоритм?
Скільки кроків я фізично повинні взяти, наприклад, для сортування цих
сім людей?
>> Від чотирьох до п'яти?
ОК, занадто багато, в кінцевому рахунку буде відповідь.
Але навіть тоді, певну кількість це не так цікаво.
Давайте узагальнимо її як н.
Так що якщо я російського народу тут, і вони були, начебто, у випадковому порядку на
починається, в цьому вихідному порядку.
Ну, скільки кроків я є взяти на першому проході?
Це був один, два, три, чотири, п'ять, шість, і вони семеро людей, тому
це сім, шість -, так що це н мінус один крок в перший раз.
>> Тепер, скільки кроків я є прийняти, коли я перемотана?
Ну, ми могли фактично подвоїться, що якщо ми дійсно хотіли, але зараз, я
саме збирався сказати, все в порядку, інша N мінус 1.
Таким чином, N мінус 1 збирається отримати дратує відстежувати, так що давайте
просто за злегка.
Так 2n кроків.
Так 14 кроків, плюс-мінус.
>> Скільки разів я беру крок в наступний раз?
Ну, це 3n.
насправді.
І тепер, в гіршому випадку, для Наприклад, скільки разів у мене є
туди і назад, туди і назад, виконання цього алгоритму, обмінюючи
людей на кожному проході, грубо?
Це насправді п квадрат, вірно?
>> Тому що в гіршому випадку ви можете виду з думати про це інтуїтивно,
хоча це може зайняти трохи трохи часу, щоб потонути всередині
У гіршому випадку, що б ці сім чоловік, були схожі, в
умови угоди з їх числа?
Абсолютно у зворотному напрямку, чи не так?
І так само, щоб імітувати, що, те, що було, тебе звуть?
>> Майк: Майк.
>> Девід Дж. мала: Майк?
Добре, Майк, ти можеш просто приєднатися до мене за тут протягом всього однієї секунди?
Взагалі-то, немає.
На жаль Майк, давай тому.
Як тебе звуть?
>> Ніл: Ніл.
>> Девід Дж. мала: Ніл.
ОК, Ніл, ти підеш зі мені, якщо ви не проти.
Так що я збираюся запропонувати, тільки для простоти, що Ніл є тепер у його
найгірший можливий випадок.
Але згадайте, як я реалізував мій алгоритм.
Я порівнюю, порівняння, порівняння, порівняння, порівняння, о.
Тепер ці хлопці з порядку, так що я можу виправити.
Так ви, хлопці поміняти.
А зараз розглянемо, як далеко Нейл дійсно повинні піти?
Це приблизно п.
Ви знаєте, це насправді не с.
Це все одно, N мінус 1, але я отримую роздратований відстеження мало
числа, так що давайте просто називати його п.
>> Так що якщо Ніл переміщається на один крок максимально кожного часу і перемістити Ніл один крок,
Я повинен зробити це дійсно втомлює прохід туди і назад, це приблизно
Роблячи це, п кроків, в загальній складності п раз, тому що він збирається взяти мене
що багато кроків, щоб отримати всі Нейл туди, де він належить.
Не кажучи вже про всіх інших, якщо ви, хлопці, були неправильно замовлені, а також.
>> Так що давайте називати бульбашкового сортування N квадраті.
Час роботи цього алгоритму, виконання цього алгоритму,
Ефективність цього алгоритму ми будемо просто описати більш
взагалі як N у квадрат.
Що приємно, тому що я міг зробити Той же приклад з восьми осіб, дев'ять
люди, мільйони людей, і що Відповідь не зміниться.
>> Так що, якщо ви, хлопці, не заперечували б, давайте скинути вас туди, де ви почали.
І давайте звернемося до двох інших підходам і побачити, якщо ми не можемо зробити принципово
краще, ніж ця.
Тому цього разу, я збираюся запропонувати свого роду інший алгоритм.
Це був дуже розумний з нас в минулий раз, і ви, хлопці були праві, щоб мати
Право інстинкти тільки почасти перекачування попарно.
Але якщо я дійсно хотів підійти до цього просто, і моя мета полягає у переміщенні
всі маленькі номери таким чином, і штовхати всі великі числа, які
До речі, чому б мені не зробити це в найнаївніші можливими способами і подивитися, якщо я
може зробити краще, ніж те, що було досить складний алгоритм?
>> Отже, давайте подивимося.
Чотири є досить невеликим числом, так що я збираюся залишити вас є момент.
Ох, номер два ще краще.
Так ви можете просто крок вперед на хвилинку?
В даний час це мій найменшим номером кандидата, і я буду пам'ятати
, Що з, як, змінної.
Але я збираюся продовжувати перевіряти.
Чи є хтось, чиї число менше?
Шість, немає.
О, є Ніл знову.
>> Так що я збираюся, щоб підштовхнути вас назад роду концептуально.
Ніл буде вийти вперед.
А тепер, мінлива, який я використовую, щоб відслідковувати, хто має найменший
кількість оновлюється, щоб утримувати Нейл місці.
Ну, давайте подивимося.
Три, сім, п'ять.
Добре, я знаю Нілу був найменшим.
Що найпростіше, що Для мене ж тепер робити?
Я не збираюся витрачати свій час, просто пузириться Ніл одне місце вліво.
Чому я не можу просто поставити Нілу, де він належить, що є, звичайно, де?
>> Всі шляхи на самому початку.
Так Ніл, ходімо зі мною.
І що тебе звуть?
>> GRACE: благодать.
>> Девід Дж. мала: благодать.
ОК.
Так і благодать, на жаль, ви вид на шляху.
Так як же нам вирішити цю проблему?
Вірно?
Якщо це масив, є тільки семи місцях.
Нагадаємо, що з Робом, ми говорили про оголосивши віків, і у нас тільки було
кінцеве число віків?
Та ж сама ідея тут.
У нас є тільки кінцеве число цілих чисел.
Грейс знаходиться почасти в нашій До речі, так як ми можемо виправити?
>> Найпростіший спосіб, як, Грейс, вибачте.
Ви будете мати, щоб перейти там, так ми можемо зробити кімнату.
Тепер, якщо ви думаєте про це, може бути, ми просто зробили цю проблему ще гірше.
А може бути, ми зробили, тому що, якщо Грейс була в потрібному місці?
Але ми знаємо, що вона не так, тому що В іншому випадку вона була б
стоять вперед, а не Ніл в цей час, чи не так?
Ми вже перевірили її номер поза.
>> Добре.
Так що тепер, Ніл в потрібному місці, і Я можу зробити невелику оптимізацію.
Для наступної хвилини, я буду ігнорувати Ніл всі разом, так, щоб не
витрачати час, або випадково обміняти його в неправильному місці.
Так що тепер, як я можу знайти наступну елемент, який найменший?
Два.
Це досить хороший номер, якщо Ви хочете зробити крок вперед і
Я буду пам'ятати тебе.
Шість, нічого хорошого.
Чотири, три, сім, п'ять, нічого хорошого.
Отже, дозвольте мені перевести вас на ваше правильне місце.
І ми просто пощастило на цей раз.
>> Тепер, я збираюся ігнорувати ці два хлопця, і тепер зробити ще одну
пройти через це.
Шість, що досить мале число.
Давай вперед.
Ой, вибачте.
Число Грейс краще, так що крок вперед на швидкості.
Чотири.
На жаль, Грейс.
Повернутися знову.
Номер три краще.
Сім.
П'ять.
І що тепер тебе звуть?
>> Джейсон: Джейсон.
>> Девід Дж. мала: Джейсон.
Так Джейсон зараз найменша Елемент я вибрав.
Куди він піде?
То де шість є.
І ваше ім'я знову?
>> GABE: Гейб.
>> Девід Дж. мала: Гейб.
Гейб знаходиться в дорозі.
Що найпростіше зробити?
Поміняти ці два хлопця і продовжити.
Отже, тепер давайте подивимося.
Хто найменший?
Чотири.
Дозвольте мені тільки почасти обман.
П'ять буде найменшим.
Я знаходжу Далі, якщо, ви хочете до кроку вперед, що я повинен робити з
ці хлопці, з Гейб?
Поміняйте знову.
Так що тепер, все ще трохи не в порядку.
Я знайшов Гейб бути найменшим, так що Я суну його, перемістити вас хлопці.
І зроблено.
>> Так що відповідь така ж.
Кінцевим результатом є те ж саме.
Який з цих двох алгоритмів що краще?
Другий, я чув.
Чому?
>> Виступаючий 3: Це п кроків [нерозбірливо].
>> Девід Дж. мала: Це п кроків по більшій мірі.
Цікаво.
Так це хоч?
Так як же я можу знайти найменший елемент?
Скільки кроків я повинні прийняти знайти найменший елемент?
Я глянув на всьому шляху Зрештою, чи не так?
Тому що в гіршому випадку, те, що Якщо Ніл були тут?
Так просто знайти найменший елемент бере мене п кроків, або N мінус 1.
Але, добре.
Так виправити Ніл.
Пам'ятайте, що, хвилину або близько того тому.
>> Але як же я знайти наступну найменший елемент?
Це мінус N 1 або N 2 дійсно мінус, від кількості кроків.
Так добре.
Так що я п мінус 2.
Добре.
Так, що відчуває себе трохи краще.
Добре.
Скільки кроків наступного разу знайти номер три?
Таким N мінус 4.
Так що це зниження, на одну менше наступати на кожній ітерації.
Так що це відчувати себе краще, чи не так?
Якщо минулого разу це були приблизно N раз N, на цей раз це N мінус 1, плюс мінус N
2, N плюс мінус 3, плюс N мінус 4, точка, точка, точка.
Але якщо ви пам'ятаєте з вашій школі підручники, маленький обман
лист на задній який має формули, якщо Ви складаєте цей числовий ряд,
що загальна кількість кроків буде, що я беру тут?
>> Це одна з тих, начебто, N мінус 1, N раз, поділеній на 2.
Отже, дозвольте мені побачити, якщо я можу витягнути до цього на мить.
І знову ж, я спосіб округлення деяких номери тільки, щоб тримати наше життя просто,
але наскільки я пам'ятаю, це те, що, якби Я роблю N мінус 1 речі, то N мінус
2, то N мінус 3, це приблизно щось на зразок цього більше 2, і якщо я
помножити це, от і насправді N площі.
Це відчуває себе не дуже добре. N п над мінус 2.
>> Але от у чому справа.
У комп'ютерній науці, коли проблеми стає набагато цікавіше, коли п
стає дійсно великим.
І коли N стає дійсно великим, що з цих значень буде домінувати все
від інших?
Це свого роду N в квадраті, чи не так?
Так, ділячи на 2 досить добре.
Але якщо ви говорите про мільярди частин даних, або трильйонами
частин даних, ОК, так Ви два рази швидше.
Але хто справді дбає, якщо це велике число, Якщо цей фактор те, що отримує
більше і більше.
І, звичайно, він робить більше різниці, чим цей хлопець.
Тому, навіть якщо ви, хлопці мають рацію, Другий алгоритм, ми будемо називати його
вибір виду, тобто в реальному світі потенційно трохи швидше, бо я
приймаючи все менше і менше кроки кожного разу.
>> Це не так вже принципово швидше.
Тому що, якщо ми граємо це для більших значень п, в кінці
день, протягом досить велике N, вона як і раніше почуватиметься досить повільно.
Ну, дозвольте мені взяти один останній прохід на цьому.
Це те, що я б назвав Вибір виду.
Може ви, хлопці скинути себе в останній раз?
І в цьому останньому випадку, я збираюся запропонувати щось
називається сортування вставками.
Сортування вставками буття, концептуально, трохи по-іншому.
>> Замість того, щоб йти вперед і назад і вибору найменшого елемента, я
тільки збираєтеся мати справу з кожним з цих хлопців, як я стикаюся з ними, і вставте
їх в потрібні місця.
Так що я просто збираюся почати з Грейс, і я бачу, що вона номер чотири.
Де номер чотири належать?
Я ще не почав сортування нічого, так і благодать отримує право залишитися там.
І тепер я збираюся стверджувати, якби ви могли зробити крок з правої, це
мій відсортований список, це моя несортоване список залишилися.
Так що тепер я збираюся перейти до наступного, і те, що тебе звуть?
>> BRANSON: Бренсон.
>> Девід Дж. мала: Бренсон.
Так Бренсон номер два.
Так що я збираюся взяти тебе за моментом.
І тепер, де ви належите в цьому масиві?
Таким чином, щоб право благодаті.
Отже, ще раз, ми як би робить Грейс зробити багато роботи тут.
Де ми ставимо вас?
Отже, ми збираємося, щоб ковзати вам ліворуч, і вставте Бренсон там.
Але зараз я стверджую, що ви, хлопці, зробили.
Але зверніть увагу, що я не використовую додатковий простір.
Він як і раніше 2 елементи Тут 5 тут.
Загальна площа масиву складає 7, так що я не брехня, все гаразд?
>> Так що тепер у нас є, з Гейб тут, номер шість, де ви належите?
Ви знову пощастило.
Таким чином, ви отримаєте, щоб залишитися на місці.
Просто візьміть невеликий крок вправо просто дати зрозуміти, що ви сортуються.
І тепер у нас є Ніл знову, число Один з них, куди ви йдете?
А тепер те, де ми почнемо бачити, що Цей алгоритм, хоча на перший
погляд, почувається досить розумним, дивитися те, що має статися.
Якщо б ви могли вийти вперед.
>> Куди ми хочемо поставити Ніл?
Так, очевидно, тут, так як ми можемо отримати там Ніл?
Давайте зробимо це крок за кроком.
Гейб, куди вам потрібно йти?
Так, так візьміть один великий крок, або дві половини кроки, щоб зробити
на один ступінь вище там.
Грейс, куди ви йдете?
Добре.
Так що ще один крок.
І, нарешті, Бренсон?
Ще один крок.
І тепер ми можемо поставити на місце Ніл.
>> Так що тепер, продовжувати цю логіку.
Хоча ми і не перекладаючи Ніл знову, і знову, і знову, щоб покласти його
, Куди він іде, в гіршому випадку, Наступний номер ми могли б зіткнутися міг
бути кількість, наприклад, було число нулю, то ми збираємося перенести всі
цих хлопців.
Припустимо, що є числа, негативні одиницю, то ми повинні перейти
Всі ці хлопці.
Так що ми дійсно тільки почасти гортати Проблема навколо, так, що ми
за рахунок передачі з Процес відбору так вставки
Процес, таким чином, що ви, хлопці, тільки що рухатися приблизно N мінус щось
число кроків.
І це число кроків буде тільки рости, як я вибираю кілька номерів,
Якщо я повинен продовжувати штовхати вас, хлопці назад, і назад, і назад.
>> Так сумно то зараз всі ці Алгоритми п квадрат.
Давайте підемо далі і завдяки цим хлопців, і візуалізувати ці трохи
різному.
Дуже добре зроблено.
>> [Оплески]
>> Добре.
Там ви йдете.
Дякуємо за -
>> BRANSON: [нерозбірливо] тримати номеру.
>> Девід Дж. мала: Ні, не можеш тримати номери, а також.
Добре.
Красиво зроблено.
Добре.
Отже, давайте подивимося, якщо ми зараз не можемо підсумувати більш швидко і більш візуально
саме те, що тільки що відбулося Тут такий спосіб.
Я збираюся йти вперед і підтягнути Firefox.
Ми зв'яжемо цю демонстрацію на сайті курсу.
Java трохи дратує, щоб отримати роботу У деяких браузерах ці дні.
Так що якщо ви граєте з цим в домашніх умовах, розумію, що ви, можливо, буде потрібно використовувати Firefox
щоб змусити його працювати.
І те, що я збираюся робити з цією демонстрації полягає в наступному.
>> Внизу, у мене є ціла купа меню, включаючи час початку і
Стоп.
Крім того, як осторонь, там, здається, помилка в цих програмах, в якому ви
не може реально побачити запуску або зупинки Кнопка якщо не утримувати Команда або Alt
плюс і збільшити, яка з цікавістю показує вам більше кнопок.
Так що просто FYI, якщо ви граєте З цим у себе вдома.
Тепер я збираюся, натисніть кнопку Пуск всього за момент, після вказівки затримки,
як, 200 мілісекунд тут, просто тому ми можемо бачити, що відбувається.
>> Тому я стверджую, що це візуалізація першого алгоритму
ці хлопці зробили, бульбашкова сортування, в результаті чого ми обмінялися людей попарно.
Ключовим моментом у цій візуалізації є те, що висота барів
представляє розмір числом.
Таким чином, вище бару, Чим більше число.
Чим коротше лінія, чим менше число.
І якщо ви помітили, ми проходимо першій ітерації цього алгоритму,
обмін великими і маленькими числами, так що Невелике число стоїть на першому місці і
великого числа йде вправо.
>> І як тільки ми отримуємо в кінець масиву багато більше номерів, ніж сім, ми
збираюся повернутися до початку.
І очікуємо, що це.
На лівій, що малюк збирається помінятися в бік, і це
процес повторюється.
Тепер цієї візуалізації швидко потрапляє нудно, так що дозвольте мені йти вперед і зупинитися
його, змінити затримку щось набагато швидше тільки, щоб отримати зараз, відчути
цього алгоритму.
>> Так що, хоча я прискорив його, це модернізації як мій процесор, купуючи
новий комп'ютер.
Я принципово не змінилася моя алгоритм, але ви дійсно можете побачити більше
ясно, чим з людьми, що більша Номери тут вирує до самого верху,
і маленькими числами барботированием на дно.
І тепер ця річ тут сортуються.
І як у бік, на площах, є просто деякі бухгалтерські там
допоможе вам підрахувати, скільки порівнянь, або скільки свопи
насправді було зроблено.
>> Ну, давайте спробуємо один з інших ми бачили.
Дозвольте мені натисніть на бульбашкового сортування тут, і дозвольте мені вибирати, і вся ця веб-сторінка
трохи баггі.
Приймемо ризику і запустити його знову.
Там ми йдемо.
Так давайте зробимо вибір роду.
Я не знаю, чому мене з'являється там.
Давайте на збільшення, щоб виправити це помилка, змініть це до 50.
Ах, давайте насправді , Що набагато швидше.
П'ять мілісекунд або близько того, і почати.
>> Так що це вибір роду.
Отже, ще раз, подумайте про те, що ми зробили з людьми тут.
Ми пройшли через масив і обраний найменший елемент знову
і знову і знову.
Тепер я стверджую, що був досі досить погано.
Це було досі п квадрат, плюс-мінус, але це було, в реальному світі, трохи
швидше, тому що я дійсно приймає трохи менше кроків кожен раз.
Але ми говоримо тільки те, що?
Може бути, 40 або близько бари тут?
Ми не говоримо 40000000.
Так що це не зовсім ясно, що був дійсно значним посиленням.
>> Дозвольте мені тепер повернутися назад і змінити нашу Третій алгоритм, який був вибрати
сортування вставками.
І тепер це дійсно дитяча коляска, тому що Меню дійсно не повинно бути там.
Так що тепер ми будемо прокручувати повернутися сюди і почати цей алгоритм.
Вигук, запускати і зупиняти.
Так що це один вид має досить візерунком до нього, в результаті чого ми знову
вставки людей або в цьому випадку в барах
їх відповідне місце.
І це вже зроблено до Я обернувся.
Але цей, теж, по ідеї, як і раніше п квадрат.
>> Отже, давайте подивимося, якщо ми не можемо підвести підсумок ці наступним чином.
Я збираюся йти вперед і тільки, щоб дати нам начебто поширений спосіб говорити
про ці речі, дозвольте мені представитися просто трохи позначень тут.
Ви зараз побачите те, що називається великим О, тому що це буквально великий
О. І це таким чином, що комп'ютер вчений або математик навіть використовує
, Щоб описати час роботи деякого алгоритму.
Скільки кроків це насправді взяти?
>> Тепер я збираюся ганьбитися з мій почерк тут через хвилину.
Але дозвольте мені піти далі і сказати, що це буде Big O тут.
І дозвольте мені представити одного друга Символ, омега капіталу.
Omega буде протилежним, По суті, великих О. У той час як більша O
кошти, в гіршому випадку, скільки часу Чи можуть деякі алгоритму приймають у
через п, омега збирається бути, скільки часу це може
взяти в кращому випадку.
І ми побачимо, що ми розуміємо під кращому разі через хвилину.
>> Отже, давайте почнемо щось просте.
Дозвольте мені розпочати з лінійним пошуком.
Так що не сортування.
Ми називаємо це лінійний пошук.
І тепер, щоб трохи таблиця з цього.
І тепер, у разі лінійного пошуку, в гіршому випадку, скільки кроків
він збирається зробити, щоб я знайшов число довільних вибір?
І є N Всього двері або н загального числа.
Гіршому випадку.
Скільки кроків я буду мати, щоб вжити, щоб знайти число 50 в масив
п дверима?
І чому?
Тому що це може бути все, перекинувши на кінці.
Так багато, як Дженніфер зустрічається, номер 50 був всю дорогу, так що в
гіршому випадку лінійного пошуку велика O п, ми будемо говорити.
>> А в кращому випадку, Якщо ви отримуєте дійсно пощастило?
Це просто буде зробити один крок, або постійне кількість кроків.
Таким чином, ми опишемо, що 1.
Так що це досить добре.
А що, якщо ми зробили щось подобається бінарний пошук?
Так бінарний пошук, в гіршому випадок, взяв, скільки часу?
>> [Проміжне VOICES]
>> Девід Дж. мала: Так насправді, я чув його в парі місць.
Так це насправді необхідно увійти N, плюс-мінус, тому що, як ми ділимо навпіл список
знову, і знову, і знову, ми можемо знайти, в кінцевому рахунку, значення
Якщо вона є, але є одна заковика.
Що припущення, що ми повинні само собою зрозумілим для бінарного пошуку?
Він повинен бути відсортований.
Це не сортуються, ви можете розділити речі в половині знову і знову, і ви
може піти наліво, і ви можете піти прямо, а Ви можете піти з обох сторін, але ви
Не збираюся знайти елемент, якщо списку не відсортований, так як
Ви могли б пропустити його.
Тому що ваш евристичні, для того, ліва або вправо збирається бути недоліки, якщо це
справді не відсортовані.
Таким чином, є свого роду приховані витрати щоб використовувати щось на зразок цього.
>> Тепер давайте перейдемо в сортуванні Алгоритми не шукає -
О, насправді підуть у це поле порожнім.
Двійковий пошук в кращому випадку?
Це також 1, якщо він просто буває в самому центрі масиву, або
середині телефонної книги.
Тепер давайте зробимо бульбашкового сортування.
Отже, ще раз, тепер ми входимо в пологів, не пошук.
>> У гіршому випадку, скільки кроків ми зробили Сортувати претензії міхура збирається взяти?
N у квадрат.
Так що я збираюся зробити це.
Ох, мій почерк виглядає ще гірше коли він прогнозує, що великі.
Добре.
Так що це п квадрат.
І в кращому випадку бульбашкового сортування, скільки кроків він збирається зробити?
1, я чув.
>> Виступаючий 1: N.
>> Девід Дж. мала: N, я чув.
>> Виступаючий 1: 2.
>> Девід Дж. мала: 2, я чув.
Я чую 3?
Добре.
Я чув про це 1, N, 2, але давайте виберемо крім щонайменше першої з цих
пропозиції, 1.
Це не погано інстинкт, тому що вона вид відповідає моделі тут.
Але якщо це займе всього 1 крок, як у світу я міг стверджувати, що список
сортується, тому що, якщо я тільки дозволив приймати по 1 кроці, скільки елементів
я можу насправді перевірити, щоб переконатися?
Ну, всього в 1, яка означає, що є N мінус 1 елементів, які можуть бути з
порядку, а я тільки збираюся на віру після дивлячись на 1 елемент, який
речі відсортовані.
Таким чином, 1 неправильно тут.
Таким чином, мінімально, скільки я повинен дивитися?
>> [Проміжне VOICES]
>> Девід Дж. мала: N мінус 1, або насправді, N, тому що мені потрібно дивитися на кожну
Елемент щоб переконатися, що це не вийшов з ладу.
Але знову ж, ми розберемося з нашими хвильових руки в менших кількостях і
Припустимо, що при п стає великим, вони нецікавих в будь-якому випадку.
Так от бульбашкового сортування.
А тепер, давайте зробимо ці два останніх.
Вибір виду, і тоді ми будемо зробити сортування вставками.
І тоді ми буде ударом свідомості з чимось набагато
краще, ніж всі з них.
Добре.
>> Що таке гіршому випадку працює момент вибору виду?
>> Виступаючий 4: N в квадраті.
>> Девід Дж. мала: N площі, я чую.
Але чому N в квадраті, інтуїтивно?
>> Виступаючий 4: Тому що ми просто зробили це.
>> Девід Дж. мала: Тому що ми просто зробили це.
ОК.
Хороший відповідь.
Але інтуїтивно, чому вибір Сортувати N квадратів?
Що ми повинні зробити, знову і знову?
Ми повинні були тримати сканування за рахунок, є Ви найменший, ви
найменша, ти найменшим.
І експлуатацію, ми змогли взяти п дії, а потім N мінус 1, то п мінус 2.
Але якщо ви начебто додати ці підсумки, або взяти його на віру, що я додав
їх заздалегідь, ми отримуємо приблизно N квадрата за вирахуванням деяких меншій кількості.
Так що я буду називати це N квадраті.
Але з вибором роду в кращих випадку, скільки кроків він
збирається взяти мене?
>> SPEAKER 5: [нерозбірливо]
>> Девід Дж. мала: Це, на жаль ще N в квадраті, чи не так?
Тому що, якщо я вибираю найменше елементом, і у нас було сім чоловік тут,
Я знаю тільки, як тільки я доберуся до дуже скінчилося тим, що я знайшов найменшу
числа, де б він чи вона могла бути.
Але як мені знайти наступний Найменше число?
Я повинен зробити ще один прохід.
Таким чином, в кращому випадку, те, що вхід вибору виду?
Це вже список сортування, номер один, номер два, номер три, номер чотири.
Але я комп'ютер.
Я можу тільки дивитися один на річ за один раз.
Я не можу сортувати зробити крок тому, як людині і сказати:
ох, це виглядає правильним.
>> Я можу тільки виносити рішення у правильності критеріям Сортувати за вибором
Найменше число.
Але навіть якщо я знайду номер один перший, Якщо я не знаю, що ще щодо
інші номери, які я не роблю, все, що я знаю, що я був переданий масив
або набір двері, за якими є номери, тільки так я знаю, що один
був найменшим?
Якщо я отримую весь цей шлях і зрозуміти, Блін, один був дійсно найменшим.
>> Але як же я тоді визначити, що два є наступним найменшим?
Роблячи те ж неефективності знову і знову.
Отже, нарешті, з сортування вставкою, як, в гіршому випадку,
ми сказали він виконує?
Це теж п квадрат.
А як щодо з кращому випадку?
Ми залишимо це в якості захоплюючим.
Ми заповнити цей порожній наступного разу, Але спочатку я пропоную, щоб ми
принципово краще, ніж Всі вони, все в порядку?
>> Так що думайте самі, що вставка Сортування буде.
Ну, це було не дуже драматичні, тому що я тільки один
що побачили зміни.
Нічого собі.
ОК.
Так що тут у нас є кілька різні демонстрації.
Якщо Чи збільшити тут, ви побачите, що за Зліва ми повинні бульбашкового сортування, в
середнього у нас є вибір роду, а на вкрай правих, у нас є те, що ми
не дивився на ще називається сортування злиттям.
Але уявіть, що ми були тут роблю досі сьогодні.
Коли Дженніфер вперше вийшов на сцену, ми пішли через масив чисел
знову, і знову, з лінійним пошуком, і ми отримали лінійне час роботи, Big O
п, так би мовити.
>> Коли ми розглянемо перший тиждень класі, коли ми розділяй і володарюй,
і у нас була телефонна книга сльозотеча, і Дженніфер, і ми всі разом
використовувала, що ключове розуміння, яке мало повторюватися знову і знову
якось викидати, викидати, викидати, половина проблеми, або
як правило, розділивши проблемою в два рази, і потім обробкою невеликий шматок
проблеми, як концептуально еквівалентні з іншого боку, ми якось робили
принципово краще.
Але з бульбашкового сортування, з вибором сортування, сортування вставками з, у нас може
Немає такої ідеї, які Дженніфер зробила.
Ми в значній мірі просто ходив взад і вперед цілу купу разів, і ми
оптимальної речі трохи, обмінюючи в цьому порядку, може бути
вставки або виділення.
Але врешті-решт, я зробив багато ніяково ходити взад і вперед.
Нам справді не щось важелі розумний, як Дженніфер зробив, як поділ
і завоювання.
>> Таким чином, сортування злиттям, навпаки, яку ми не побачимо до наступного тижня, це буде
використовувати, що ключовою ідеєю шляхом ділення вхід, а потім наполовину, а потім
вдвічі, а потім вдвічі.
І на кожній ітерації цього циклу, сортування лівій половині, а також право
навпіл, то ліва половина лівій половині, і праву половину лівою, а потім
ліва половина права половина, і правій половині правій половині.
І повторює знову і знову.
>> Таким чином, ви побачите, що це візуально, але це це те, що нас чекає наступного тижня.
І взагалі, коли ми думаємо, мало трохи складніше, на будь такій проблемі.
Ми п квадрат ліворуч, п квадрат в середині, і N
н увійти праворуч.
Так що ваші реальні захоплюючим.
Побачимося в понеділок.
>> [Оплески]