>> СПІКЕР: Гаразд, це CS50.
Це кінець три тижні, і якщо Ви не скористалися вже,
знаю, що там буде обід в цю п'ятницю, як завжди, десь
Ви можете насолоджуватися гарною бесідою і їжа в Вогонь і лід
з деякими з CS50 сайт персонал і однокласники.
Голова до цього URL тут.
>> Тепер ви, напевно, пам'ятаєте, або ви найближчим часом може бути знаком с,
ці речі тут, які наведені в кінці
семестру для багатьох класів.
Так звані екзаменаційні сині книги, в яких Ви пишете свої відповіді на іспитах.
Тепер у мене є тут 26 таких блакитні книги, на кожен з них
написано ім'я, до Z. І дійсно, імена, що просто,
до Z. І один з цілі під рукою сьогодні
буде продовжувати те, що ми почали в понеділок, який не є
стільки дивлячись на код, але насправді дивлячись на ідеї та вирішення проблем.
Одна з цілей і Обіцянки цього курсу
є навчити вас думати більше ретельно, більш методично,
і більш ефективно вирішувати проблеми.
І справді, що ми можемо зробити, що дійсно , Навіть не торкаючись жодного рядка коду.
Тому у мене є пару слонів тут сьогодні, помаранчевий і синій,
якби ми могли отримати один доброволець, може бути, від далі назад, ніж зазвичай.
Як щодо прямо там, давай вниз.
Мета, яка буде в допомогти плюс адмініструвати цей іспит тут.
Як тебе звуть?
>> АУДИТОРІЯ: Мері Бет.
СПІКЕР: Мері Бет, давай до.
Дозвольте мені мікрофон тут для вас.
Приємно познайомитися.
>> АУДИТОРІЯ: Приємно познайомитися.
СПІКЕР: Гаразд, у мене є тут синій книги через Z,
і я збираюся робити вигляд, що У мене є один зі студентів,
і вони йдуть в кілька випадковим Наприкінці тригодинного іспиту блоку,
таким чином, вони в кінцевому підсумку в деяких полуслучайная порядок, як це.
Тепер ваша задача в мить збирається щоб be-- це насправді, як вони отримують
Виявилося, в кінці клас, швидше за все.
Ваше завдання тепер буде, цілком просто, щоб впорядкувати ці сині книги для нас
від А до Z.
>> АУДИТОРІЯ: О, це збирається взяти назавжди.
>> СПІКЕР: І ми будемо дивитися не, як ви робите це, ніякого тиску.
АУДИТОРІЯ: Ні, ніякого тиску або нічого.
>> СПІКЕР: І для задоволення, давайте миритися таймер.
>> АУДИТОРІЯ: Так весело, так весело.
>> СПІКЕР: я можу тримати мікрофон для вас.
Добре, що ми тільки що подвоїли швидкість.
Таким чином, у той же час, Дозвольте мені задати що буде питання для Мері Бет
є те, що вона робить, як це вона збирається про вирішення цього?
І справді, ви не могли б Замислювалися про що
так просто, як коли ви вибираєте до 26 книгах, як це,
які мають природне замовлення до них.
Який процес що ви насправді використовувати?
Це досить випадковим просто вибираючи перший, який ви бачите
і покласти її на місце?
Ви спочатку перемістити свої руки навколо шукаю потім шукаєте B?
Ви погляньте на Пара з них пліч-о-пліч
і просто сказати, постійте, це не правий, а потім поміняти порядок?
Ми бачили вже в понеділок що є кілька способів
, В якому ми можемо зробити це, і дійсно, як ми наближаємося до кінця тут,
Я б взяти до відома, можливо, чого Мері Бет робить.
У нас є кілька паль схоже, більший, три поменше.
>> АУДИТОРІЯ: я їх замовленні коли я знаходжу два листи
що я знаю, разом в послідовності, Я поклав їх разом так, що я не
доведеться турбуватися про збереження трек з цілого ряду книг.
Це просто, ну, по-перше, У мене цей стек тут.
СПІКЕР: Так, майже як головоломка частин, які
мають правильну форму до збігаються один з одним.
АУДИТОРІЯ: Досить багато, так.
СПІКЕР: ОК, відмінно.
І тепер кожен з них палі Імовірно упорядковано?
>> АУДИТОРІЯ: Так.
>> СПІКЕР: Гаразд, до Z. All Добре, вітаю, ви зробили це.
У вас є вибір.
Синій?
Добре, спасибі вам за це.
Так Мері Бет зробив запропонувати що її підхід був,
але те, що це ще один підхід, як вам може йти про сортування ці речі?
Що б ви зробили?
Запис бити було б одна хвилина і 50 або близько того секунд,
плюс ті, які я забув порахувати.
Що б ви зробили?
Да?
АУДИТОРІЯ: Візьміть стопку.
Почніть з самого початку.
Перевірте ваші документи.
І якщо верхній вище ніж, може бути, вони,
нижній є вище, то поміняти їх.
>> СПІКЕР: ОК, так що починати у верхній і нижній,
а потім працювати ваш шлях всередину так, помінявши їх місцями?
Отже, трохи схожий по духу бульбашкового сортування,
але вибір крайності НЕ сусідні пари.
Але за винятком цього є те, що є напевно купа різному
ми могли б зробити це, і чесно кажучи, я думаю, вам вид
прийняв пару підходів, чи не так?
Ви зробили те чотирьох відсортованих паль, і потім ефективно об'єднали їх разом.
І ось, гадаю, ще один Техніка в цілому.
Ви не розглядати його як один великий купі, Ви розділили проблему на чотири каре,
якщо хочете, і тоді так чи інакше об'єднали їх в кінці.
>> Отже, давайте розглянемо, в кінцевому рахунку ,, як ще ми могли б зробити це.
Ми оформлено поняття бульбашкового сортування останній раз,
і бульбашкового сортування нагадаємо було Алгоритм, який ми візуалізували
з восьми своїх однокласників тут, здавалося б, випадково упорядковано спочатку.
І ми тоді вирішили попарно, якщо два елементи з того,
просто поміняти їх місцями.
Так чотири і два очевидно, з того,
так ці два однокласників помінялися місцями.
А потім ми повторили з чотирьох до шести років, потім шість і вісім, на кожній ітерації,
рухатися вправо.
>> Тому, враховуючи, вісім осіб, скільки попарно порівняння я зробив під час прогулянки з
зліва направо в одній такій ітерації?
Скільки порівняння?
Сім, чи не так?
Тому що, якщо є вісім люди, але у вас є пару
їм і ви продовжувати рухатися один хоп вправо,
ви не будете мати вісім порівняння, тому що ви не можете порівняти
елемент сам в собі, або це буде просто безглуздо, так що ви повинні сім.
Або в більш загальному, якщо у нас є російських людей, ми
зробити п мінус 1 порівнянь з бульбашкового сортування.
>> Отже, давайте розглянемо тепер, наскільки добре чи погано міхур був сам, і спробуйте
дати собі словник з для критики алгоритмів, як це,
і незабаром самостійно.
Так при першому проходженні через бульбашкового сортування, перший раз
Я йшов зліва направо по етап, взяв мене н мінус 1 порівнянь.
І це буде мій одиниця виміру, чи не так?
Я був почасти говорити і прогулюючись, кілька швидко, наскільки повільно,
так вважаю своїх секундах не дуже показово,
але підрахунку кількості операції, які я зробив у понеділок,
порівняння двох людей, що відчуває себе як хороший одиниці виміру.
>> Так н мінус 1 кроки в перший раз, але те що сталося після цього?
Що один Верх один прохід через іншому випадку несортоване список?
Що ви можете сказати мені про елемент який був повністю там?
Да?
Це був найбільший елемент, чи не так?
Номер вісім, хоча вона почалося тут, кожен раз, коли я
в порівнянні з нею проти сусід, вона продовжувала
б'ється праворуч Права частина списку.
І справді, ось де Алгоритм отримав свою назву.
>> Тепер за цією логікою, скільки порівняння чи потрібно робити на другий раз
Я роблю, що прохід зліва направо?
н мінус 2, чи не так?
Було б просто витрачати свій час, якщо I тримати порівнюючи вісім проти кого
ще, бо ми вже знаємо вона була в потрібному місці.
Так що це трохи оптимізація, тому наступного прохід
буде плюс н мінус два кроки, де п число людей.
Тепер ви можете роду екстраполяції, навіть якщо ви не фахівець з комп'ютерів,
як це закінчується.
В кінці цього алгоритму, мабуть у вас є тільки одне порівняння залишили.
Ви повинні роду виправити початку списку в разі двох
і один вийшли з ладу і повинен бути один і два,
так що це упору на плюс 1 Остаточне порівняння.
>> Тепер точка, точка, точка вид хвиль це руки у деяких з соковитіше деталей,
але давайте просто йти вперед і спрощення.
Якщо ви пам'ятаєте з високого школа, чесно кажучи, багато хто з вас
була математичні книги, які мали трохи шпаргалка
на обкладинці або задня кришка, що показав вам,
Підсумовування що серія, як це, зрештою складаються в.
У загальному випадку, якщо у вас є змінна, як п, і справді це одне,
якщо ви подивіться на ваш стара школа математика книга,
ви побачите, що це насправді додає до цієї суми тут,
п раз п мінус 1 все поділене на число 2.
Так що на даний дозвольте мені просто передбачають це вірно, так на стрибок віри,
це те, що це підводить до, і ми могли
довести, що в більш загальному випадку.
Але тепер давайте розширимо це.
Так що давайте помножимо це, так от н квадрат, мінус п, все розділити на 2.
Це дійсно п квадрат, поділене на 2, мінус п над 2,
так що все добре і цікаво.
Але що станеться, якщо ми Плагін значення?
Припустимо, у мене не було вісім люди, але сказати, мільйон.
І млн тільки тому, що це досить велика сума,
давайте підключити, що в і подивитися, що відбувається.
Так що, якщо я підключу млн в цій формулі Я йду, щоб отримати мільйон квадрат,
поділене на 2, мінус млн, поділене на 2.
Тепер те, що, що збирається рівнятися?
Так 500000000000, мінус 500 000.
А якщо я насправді що математика, це означає,
що сортування мільйон люди з бульбашкового сортування
може зайняти мені +499999500000 кроки чи порівняння зрештою,
ми просто екстраполяції.
>> Це відчуває себе досить повільно, але, чесно кажучи вимірювання один певний вхід
як це, не все, що говорить багато про що.
Але насправді це означає, що до як п отримує більше і більше, цей алгоритм
вид почуває себе гірше і гірше, або ви дійсно
починають відчувати біль, що спорудження до рівня, що п квадрат,
який додає досить швидко.
І ця деталь не втратив на людей, насправді
Кілька років тому якийсь сенатор, який був агітація, сів на співбесіду
з Еріком компанії Google Шмідт, генеральний директор в той час,
і був кинутий виклик з питанням так само, як ми досліджуємо сьогодні.
Давайте поглянемо.
>> [Відеовідтворення]
>> -Senator, Що ти тут в Google, і мені подобається
думати про президентство як співбесіда.
Тепер, це важко отримати робота в якості президента,
і ви збираєтеся через суворі зараз.
Це також важко отримати роботу в Google.
У нас є питання, і ми просимо наших кандидатів питання,
і цей від Ларрі Швіммер.
Подав що ви, хлопці, думаєте, що я жартую, це прямо тут.
Що є найбільш ефективним способом сортувати мільйон 32-розрядних цілих чисел?
>> -Well--
>> -Пробач, Maybe--
>> Ні, ні, ні.
Я думаю, що міхур то буде неправильний шлях.
>> -Давай, Який сказав йому, цей?
Я не бачив комп'ютер наука в фоні.
>> -Ми Отримали наші шпигуни там.
>> -OK, Давайте запитаємо відрізняється питання інтерв'ю.
>> [END відеовідтворення]
>> СПІКЕР: Так говорити про конкретні цифри, хоча,
не збирається бути все, що корисно.
Це не урок життя, що міхур сортувати, враховуючи мільйон входів,
може зайняти цілих 500 мільярдів кроків.
Ви не можете дійсно узагальнити надто ефективно від
і приймати правильні рішення дизайну при написанні програм.
Так що давайте хоча зосередитися на тому, ми могли б спростити цей результат.
>> Так що я виділені жовтим кольором тут Результатом п поділене на квадрат 2,
так млн квадрат поділене на 2, а потім
Я виділив те, що Остаточний відповідь була
як тільки ми віднімається від п поділене на число 2.
І претензії я збираюся зробити зараз, хто, чорт візьми піклується якщо відняти від
трохи старий п над 2, коли перший частина цієї формули є набагато більше?
Це домінує над іншим Термін, н квадрат розділений на 2
так набагато більше, ясно, як н стає великим, як мільйон,
що є насправді велика різниця в кінець дня між 500000000000
і +499999500000?
Не зовсім.
І так, що ми збираємося робити, як комп'ютерники є
ігнорувати ці молодші члени та прийняти те, як це і дійсно
тільки спростити його, щоб термін, який походить з матерією.
Чим більше наші набори даних отримати, тим більше наші бази даних отримати, тим більше веб-сторінок
ми повинні шукати, тим більше Друзі у вас є на Facebook.
>> Як н стає більше, ми дійсно дбатиме про величину
Термін в будь-якому такому аналізі наш виступ алгоритми.
І я збираюся сказати, ви знаєте, що, бульбашкового сортування порядку великого O,
порядку п квадрат.
Це не зовсім н квадрат, як ми бачили,
але хто дійсно піклується про тих невеликих точки,
і, чесно кажучи, хто насправді різниця, якщо ми ділимо на 2?
Ось тільки постійним фактором.
І це 500 мільярдів проти 250 млрд дійсно, що велика справа?
Я міг би просто чекати один рік, нехай мій ноутбук буквально
отримати в два рази швидше в апаратних засобах, і такого роду відмінності
просто йде природним плином часу.
>> Те, що ми дбаємо про те, вираз, частина
вирази, що буде мінятися в залежності як наш вклад стає більше і більше.
І справді, в реальному світі, це те, що все більше відбувається
є внеском у наші проблеми і алгоритми стають все більше.
Настільки великий O буде позначення, асимптотическое позначення, що ми просто
використовувати як комп'ютерні фахівці, щоб описати продуктивність, або час роботи,
алгоритму.
Так що ми можемо порівняти алгоритми на різних комп'ютерах, написаних
різними людьми, за допомогою деякі принципово схожі метрика
як числа порівнянь ви рішень, або, може бути, кількість свопів
ви робите.
>> Те, що ми не збираємося кількість являє собою кількість часу
, Який проходить по годинах на стіні зазвичай.
Те, що ми не збираємося турбуватися про те, скільки пам'яті
ви використовуєте сьогодні на міру, хоча це
ще один ресурс, ми могли б виміряти.
Ми збираємося, щоб спробувати засновувати наші аналізи на лише основні операції, ті,
чесно кажучи, що ви можете бачити найбільш візуально.
Так щось на зразок великої O п квадрат, я стверджую, що O н квадрат
є верхньою межею на так званий час роботи в бульбашкового сортування.
Іншими словами, якщо вас хотів стверджувати, що є
це верхня межа того, скільки кроки алгоритму може зайняти,
це буде у великій O п квадрат в цьому випадку верхня межа.
>> Що робити, якщо я замість змінити історія була нема про бульбашкового сортування,
але про це верхня межа.
Чи можете ви назвати алгоритмом що ми дивилися на вже
чия верхня межа, максимум вимірювання часу або операцій,
буде називається обмеженим, по п, лінійною функцією,
не квадратичного, ось вигнуті?
Що собою алгоритм, який завжди займає не більше
ніж як п кроків, або 2n кроків, або кроки 3n?
Да?
>> АУДИТОРІЯ: Пошук Найбільша кількість у списку?
>> СПІКЕР: Абсолютно, знаходячи Найбільша кількість у списку.
Якщо мені дадуть список люди наприклад,
кожен з який тримає ряд, що це максимальне число
кроків він повинен взяти мене, розумно розумна людина,
знайти найбільше людини в цьому списку?
п, чи не так?
Тому що в гіршому випадку, де може найбільша цінність бути?
Право, всю дорогу в кінці.
Таким чином, в гіршому випадку Верхня межа, я міг би
повинні пройти весь шлях тут і сказати:
ой, ось номер вісім, або що це значення.
Тепер було б просто нерозумно якщо я продовжував йти, чи не так?
Дивлячись на все більше і більше елементів якщо останній з них знаходиться там?
Так, звичайно ,, п є верхньою межею.
Мені не потрібно, щоб взяти більше кроків, ніж це.
>> Так що, якщо замість цього я запропонував, щоб Є алгоритми в цьому світі, що
є час, бігаючи Це обмежена великим O із журналу п, увійдіть н?
Де ми бачили цього раніше?
Да?
>> АУДИТОРІЯ: У задачі телефонної книги?
СПІКЕР: Як проблеми телефонної книги.
Те, що було показником того, наскільки скільки часу або скільки сліз IT
взяв мене, щоб знайти таку людину, як Майк Сміт в телефонній книзі?
Ми стверджували, що це був журнал п, і навіть якщо не знайомі або це
трохи туманно, що логарифм або показник був,
тільки пам'ятайте, що § п як правило, відноситься до процесу,
В цьому випадку ділення то в половині знову, і знову,
і знову, і знову, так що він отримує все менше і менше, як і ви, що.
>> Так увійти н стосується, звичайно, наприклад телефонної книги,
щоб бінарного пошуку в теорії, коли ми були віртуальні двері на борту,
або коли Шон був пошуках чогось.
Якщо він використовується бінарний пошук, увійдіть н буде верхня межа, скільки
час, що потрібно.
Але ці алгоритми, які бігли в § п передбачається, які ключові деталі?
Це список був відсортований, чи не так?
Ваш алгоритм помиляється, якщо ваш вклад не сортується,
і ще ви використовуєте щось на зразок бінарного пошуку
тому що ви можете стрибати прямо над елементом
, Не розуміючи, що це дійсно є.
>> Тепер, що це може означати, Big O одного?
Це не означає, що ваш алгоритм займає один і тільки один крок,
це просто означає, що вимагається постійне число кроків.
Може бути, це 1, може бути, це 10, може бути, це 1000,
але це залежить від розмір проблеми.
Незалежно від того, наскільки великий п, постійна алгоритм час
завжди має те ж саме число кроків.
Так що може бути алгоритм ми говорили про або просто
інтуїтивно, що приходить до вас, що завжди працює в так званій постійної часу?
Да?
>> АУДИТОРІЯ: Додати два числа.
СПІКЕР: Додати два числа, 2 плюс 2 дорівнює 4, зроблено.
Так що може працювати, що ще?
Як щодо більш реальному світі, так?
>> АУДИТОРІЯ: Пошук Перше, що в списку.
СПІКЕР: Пошук першим елемент у списку, звичайно.
Ми насправді говорив про масивах вже,
як ви отримаєте на Перший елемент в масиві,
незалежно від того, як довго масив на С?
Ви просто використовувати як кронштейн нульовий позначення, бац, ти там.
І дійсно масиви, як в сторону, підтримка щось відомо
як випадкового доступу, випадкового доступу пам'яті, тому що ви можете буквально
перейти в будь одному місці.
Ми можемо зробити це ще простіше ми можемо переміститися до нульової тижня
коли ми зробили нуля.
Скільки часу буде потрібно для кажуть блок в порожньому виконати?
Просто постійна часу, чи не так?
Скажи що-небудь, скажімо то, це не має значення
як великі подряпини світ, це завжди збирається взяти таку ж кількість часу
просто сказати щось.
>> Так ось постійна часу, але те, що зворотна сторона?
Якби це було верхня кордону, що, якщо ми хочемо
для опису нижні межі наших алгоритмів час роботи?
Майже кращому випадку потенційно, якщо хочете,
хоча ці терміни можна застосувати до кращих Випадки, гірших випадках середні випадки більше
взагалі, але давайте просто зосередитися на нижніх меж в цілому.
Що собою алгоритм, який має нижня межа п кроків,
або 2n кроків, або кроки 3n?
Деякі фактор п кроків, ось його нижньої межі.
Да?
>> АУДИТОРІЯ: Bubble роду?
>> СПІКЕР: Bubble роду бере Ви мінімально п кроків, то чому?
Чому це?
Чому, що почало приходити до вас інтуїтивно, навіть якщо це не так просто
ще?
Да?
>> АУДИТОРІЯ: [нерозбірливо].
СПІКЕР: Точно.
В кращому сценарії бульбашкового сортування, і багато алгоритмів
якщо я вручаю вам вісім осіб які вже відсортовані,
було б нерозумно для вас, алгоритм,
щоб йти вперед і назад більш ніж один раз, чи не так?
Тому що як тільки ви ходити по списку один раз,
ви повинні розуміти, о, я зробив немає свопи, цей список сортується, вихід.
Але що відбувається, щоб у вас н кроки.
>> І навпаки, те, що ще один спосіб думати про це?
Bubble роду є омега, так би мовити, з п,
бо якщо ви подивіться на менше, ніж п елементів, то, що
фундаментальне питання є?
Ви не знаєте, якщо це сортуються, право.
Ми люди могли погляд на восьми люди і бути як, о, це сортується,
що мене не взяли н кроки, але це зробив.
Твої очі, хоча вас вид від того, мають велике поле зору,
Ви дивилися на восьми елементів, Ви дивилися на вісім чоловік,
ось вісім кроків ефективно.
І тільки тоді, коли я йду через весь Список я розумію, так, відсортовано.
Якщо я зупинятися на півдорозі думати, все Право, це досить упорядковано досі,
які шанси, що це не Починаючи?
Що алгоритми НЕ буде правильним.
Може бути швидше, але неправильно.
>> Так що тепер у нас є спосіб описи нижні межі,
і те, що про постійне часу?
Що собою алгоритм, який має нижчий обмеження на час його роботи одного?
1 крок, 2 кроки, 10 кроків, але постійним, залежить від п,
розмір входу?
Так, в спину.
>> АУДИТОРІЯ: Printf?
СПІКЕР: Що це?
АУДИТОРІЯ: Printf?
СПІКЕР: Printf.
ОК, впевнений.
Таким чином, це займає фіксоване число кроків.
І я повинен now-- тепер, ми говоримо про C коду
а не до подряпин, то як скажімо, з Printf,
ми повинні почати, щоб отримати обережним.
Оскільки Е дійсно бере вхід, це рядок,
і струни у технічно мають довжину.
Так що, якщо ми зараз хочемо, щоб забрати на вас, якщо ви не заперечуєте,
технічно ми могли стверджувати, що Printf дійсно бере змінну довжину вхідний,
і, звичайно, це може зайняти більше Час надрукувати рядок так довго,
що так довго.
>> Так що, якщо ми розглядаємо тільки сортування та пошук прикладів?
Як щодо Майка Сміта в телефоні Книга, або бінарний пошук в більш загальному?
В кращому випадку, що може трапитися?
Я відкриваю телефонну книгу і, бац, є число Майка Сміта.
Я можу зателефонувати йому прямо зараз.
>> Взяв один крок, може бути, два кроки, але постійне число кроків
якщо мені пощастило.
І, чесно кажучи, ми бачили на Понеділок ваш однокласник
отримати дуже пощастило два рази поспіль.
І це було дійсно постійної час в нижніх меж
від алгоритму в питанні знаходження число 50 за тих, закрито
двері.
>> Тепер, як в сторону, якщо ви виявите, що і велика O, верхня межа,
і омега, нижня межа, один в тому ж, що
є та ж формула в дужки, ви також можете
сказати, просто бути незвичайним, щось не в тета
н або тета деякого іншого значення.
Це просто означає, коли більша Виводу і омега однакові.
Тепер щодо вибору роду?
Давайте використовувати цей новий словник.
У селекції роду, то, що ми були робити знову, і знову, і знову?
Я збирався туди і назад через список, шукає кого?
Найменше число.
>> Так як багато кроків, як багато порівнянь я теж
повинні зробити для того, щоб з'ясувати, хто найменший елемент у списку був?
н мінус 1, чи не так?
Тому що, якщо я просто почати з того, що я перебуваю враховуючи і я починаю порівнювати його або її,
то йому або їй, як він або їй, йому або їй, я
може тільки пару елементів разом н мінус 1 раз.
Так вибір роду ж бере н мінус 1 кроки в перший раз.
>> Скільки кроків потрібно, щоб я знайти другий найменший елемент?
н мінус 2, тому що я німий якщо я продовжую дивитися на ті ж люди,
знову, якщо я вже вибрали його або її і покласти їх на місце.
І третій крок, н мінус 3, то п мінус 4.
Ми бачили цю модель раніше, і насправді
Вибір роду аналогічно має верхню межу
н квадрат, якщо ми робимо до, що підсумовування.
Яка його нижньої межі, вибір роду?
Мінімально, скільки часу відбору повинні Сортувати прийняти, як ми визначили його в понеділок?
Пропоную два варіанти.
Може бути, це п, як і раніше.
Може бути, це н квадрат, як це Зараз як верхня грань.
>> АУДИТОРІЯ: н квадрат.
СПІКЕР: н квадрат.
Чому?
>> АУДИТОРІЯ: Тому що у вас є визначити [нерозбірливо].
>> СПІКЕР: Точно.
Принаймні, як я визначив вибір роду це було досить наївно, продовжувати йти,
знайти найменший елемент.
Верніться, знайти найменший елемент.
Там немає роду оптимізація в там, що
може дозвольте мені перервати після всього п або близько кроки.
Так дійсно, вибір сортувати, омега п квадрат.
>> Як щодо сортування вставками, де я взяв які мені дали, і тоді я гепнувся його
або її в потрібному місці?
Тоді я продовжив другої людини, шльопнувся його або її в потрібному місці.
Тоді наступна людина, гепнувся йому або їй в потрібному місці.
Зверніть увагу, що це дуже лінійний, так би мовити.
Я прямий, я не ходить взад і вперед,
Я ніколи не озираючись назад дійсно, але що відбувається, коли я вставляю його
або їй на початку Список, як ми зробили в понеділок?
Що відбувається?
Да?
АУДИТОРІЯ: [нерозбірливо].
СПІКЕР: Так, була заковика, чи не так?
Ви можете пригадати з Ваші однокласники, якщо вони
робили будь-який рух з їх ноги, що була операція.
Так що, якщо було три людини, тут і нова людина належав спосіб там,
на довгий етап, як це, впевнений, він або вона може просто піти до самого кінця.
Але якщо ми думаємо про Комп'ютер і масив пам'яті,
ці люди збираються доведеться перетасувати над
щоб звільнити місце для цієї людини.
І так, що п мінус 1 shufflings, н мінус 2 shufflings, п
мінус 3 shufflings є тільки почасти відбувається позаду мене, чи не переді мною
як і раніше, в деякому сенсі.
Тепер, як в сторону, і, як Ви, можливо, бачили онлайн
якщо ви починаєте колупатися про види, є так багато різних ті,
там, деякі з них краще, ніж інші.
Дійсно, bogosort є одним що забавно дивитися вгору.
Bogosort приймає набір цифри або сказати колоду карт,
змішає випадковим їх, і перевіряє, якщо вони відсортовані.
А якщо ні, робить це знову.
Якщо ні, робить це знову.
Неймовірно нерозумно.
>> І справді, якщо ви читаєте як статті Вікіпедії,
його прізвисько нерозумно роду.
Це в кінцевому рахунку спрацює, сподіваюся, достатньо часу,
але це кількість часу може зайняти досить багато часу.
Так що, якщо я міг, давайте прискорити речей в порівнянні з, наприклад Мері Бет раніше,
маючи ще кілька елементів, але більше двох процесорів.
Дві людини, якщо вам був би не проти приєднатися до мене.
Як щодо 1 тут, і давайте НЕ go-- нікого, он там?
Ніхто не там?
Добре.
Ви з чорними сорочка, да, давай вниз.
Гаразд, як тебе звуть?
>> АУДИТОРІЯ: Пітер.
>> СПІКЕР: Що це?
>> АУДИТОРІЯ: Пітер.
СПІКЕР: Питер, Девід, приємно познайомитися.
Добре, у нас є Петро тут, якщо вам хочу приїхати на стіл тут.
І як тебе звуть?
>> АУДИТОРІЯ: Олена.
СПІКЕР: Олена.
ОК, приємно познайомитися.
Олена зустрінете Пітера.
Пітер, Олена.
І ми повинні Ендрю тут також, будь ласка.
І ваше завдання буде бути впорядкувати колоду карт.
І якщо не знайомі, палуба карт повинні в кінцевому рахунку,
бути відсортовані дещо як це де ми зробимо клуби, то
лопати, то серця і діаманти, від туза як один,
все, аж до короля.
>> Карти я збираюся дати вам збираються бути 52 в кількості.
Ми збираємося аналогічним Час у вас, через хвилину.
Ми збираємося кинути Ендрю на екрані тут,
таким чином, щоб дивитися, як ви робите це.
І таким чином, що все це тим більше видно,
це карти, які я отримав на Амазонці.
Так вони вже випадково сортуються, і ми збираємося раз, коли ви.
І ми збираємося тримати його реальної на цей раз,
так що ми збираємося спробувати чинити тиск на вас бо інакше це буде отримати утомливо
швидко.
Якби ви могли приступити до впорядкувати 52 елементи разом через деякі засоби, зараз.
>> І знову, як ми дивимося ці хлопці роблять те, що, врешті-решт,
вироблятиме очевидно Результат, думаю, про дійсно
як вони кожен робить це, як Ви могли б описати його.
Бо знову ж таки, це всі процеси, алгоритми
що ми вважаємо само собою зрозумілим, як людина.
Але ви, напевно, давно інтуїція, задовго до вас, навіть
думав про взяття інформатика клас вам
можливо, мали інтуїцію з які вирішити подібні проблеми.
Але як тільки ви визнаєте патерни і почати
формалізувати дії, за допомогою яких ви вирішуєте ці проблеми,
Ви знайдете, що ви можете вирішити багато цікавішим і набагато складніше
проблеми швидко.
Так хто з глядачів, що є щонайменше, один елемент алгоритму
що вони використовують тут?
>> АУДИТОРІЯ: [нерозбірливо]
СПІКЕР: Що це?
АУДИТОРІЯ: По костюмі.
СПІКЕР: По костюмі.
Отже, спочатку вони кластеризації всі алмази разом
мабуть, все серця разом схоже,
і так далі, без дотримання для чисел на картах.
І тепер вони з'являються, наприклад, щоб бути їх сортування за номером.
Дуже добре.
>> Гаразд, так що буде бути останнім кроком, то тут?
Після того, як у нас є чотири відсортовані костюми, що нам потрібно зробити, щоб чотирьох паль
для досягнення однієї упорядковано палубу, досить просто?
Так що ми повинні об'єднати їх знову.
>> Таким чином, є цікава ідея, що знову, гадаю, дуже зрозумілий навіть
якщо ви ніколи б не вдарив що вид етикетки на ньому.
Це фундаментальне поняття ділення проблема не в половину цього часу,
але принаймні на чотири частини.
Рішення в значній мірі принципово ідентичні проблеми
ізольовано один від одного, , А потім об'єднати результати.
І, відмінно, зроблено.
Добре, велика кругла оплесків, якщо ми могли.
>> [Оплески]
>> СПІКЕР: Я поняття не маю, що ви будете робити з ними, але тут ви йдете.
Спасибо большое.
Отже, давайте подивимося, дві хвилини і вісім секунд,
якщо ви хочете, щоб битися зі своїми друзями.
Що ж тоді буде бути відняти від цього
що ми можемо використовувати більш загальному?
Ну, думаю, назад в Цей масив чисел,
і згадую зараз, щоб деякі з псевдокод ми написали в минулому,
і це було команд для вирішенні проблеми телефонної книги.
Причому в псевдокода I перерахував більш методичну шлях
описи того, як я зробив дуже інтуїтивний людина алгоритм ділення телефон
Книга в половині, повторіть, повторюю, повторюю, поки я не знайду така людина, як Майк Сміт,
якщо він дійсно перебуває в телефонній книзі.
>> Але я почасти звик, що я називаю дуже ітеративний підхід тут,
зокрема повідомлення лінія 8 і рядок 11.
Ті, є свідченням ітеративний підхід, перекручування підхід,
бо це саме поведінку вони викликають.
Ці лінії як би, йдуть в Лінія три, і ви можете роду
думати про те, що у вашому уявним поглядом як петля.
Це говорю вам, щоб повернутися до кроку три і повторюю, знову, і знову,
і знову.
>> Але що, якщо ми використовувати ключову ідею тут, що ми зробили не востаннє,
і спростити лінії 8 і рядок 11 і їхні сусіди
як тільки це, в жовтий колір.
Це не принципово скорочення псевдокод дуже багато,
але це в корені міняє природа мого алгоритму.
Те, що я зараз говорю в пункті 7, на етапі 10,
є пошук Mike в тому ж чином,
але тільки в лівій половина або права половина.
>> Таким чином, іншими словами, якщо Я починаю з кроком один,
підібрати телефонну книгу, відкритий до середини з телефонної книги, подивитися на імена,
якщо Сміт є одним звуть, телефонуйте Майк, ще
якщо Сміт раніше в книзі, крок сім шукати Майка в лівій половині книги.
Але що це за відчуття, це залишивши мене висить, чи не так?
В жовтий, є інструкція, але як я можу
шукати Майка в лівій половина телефонній книзі?
Де я повинен Алгоритм, з якою я
може шукати таку людину, як Майк Сміт?
Ну, це дивлячись нам в очі.
Я можу буквально використовувати точно такий же Програма ефективно, підійшовши до верхньої
знову і знову працює ті ж рядки коду.
>> Таким чином, навіть при тому, що це має почуватися як трохи циклічного визначення
де ви відповідаючи хто- Питання по тільки вид з проханням
те ж питання знову, як, чому, чому, чому?
Реальність така, тому що ми жорстко пару спеціальних ліній, крок 4,
що, якщо, і крок 12, які ефективно інша гілка,
тому що у нас ці заходи по усуненню вузьких, цей алгоритм буде припинена, якщо ми
знайти Майка, або якщо ми не робимо.
Але в кроці 7 і 10 тепер, у нас є що ми будемо називати рекурсивний алгоритм.
І рекурсія дійсно потужна ідея це трохи запаморочливим спочатку,
що тепер ми можемо застосувати такий спосіб.
>> Злиття роду буде останнім видом, який ми дивимося на, принаймні, в класі формально.
І це в корені відрізняється від тих трьох останніх, і, звичайно,
Останні чотири, якщо ми включимо bogosort.
Ось псевдокод для сортування злиттям.
Коли на вході п елементів, тому, враховуючи, масив розміру N, якщо N менше 2,
повернутися.
Так чому ж я, що розсудливість перевірити в першу чергу?
Що мається на увазі якщо зраджу тебе масив, довжина якого н менше 2?
Це вже відсортовані, очевидно, не так?
Оскільки список або має один елемент, який є тривіальним
сортуються, тому що це Єдине, що є.
Або, це через нульового розміру, що означає немає нічого, щоб розібратися, так за своєю природою
сортується.
Там просто нічого поганого там.
Так ось наша так звана базовий варіант.
>> Тобто близький по духу до того, що ми зробили з Майком.
Якщо Майк в телефонній книзі, зателефонуйте йому.
Якщо його там немає, здаватися.
Це так званий базовий варіант, щоб переконатися Цей алгоритм в кінці дня
зупиниться в певних обставинах.
>> Але ось стрибок віри зараз, інакше, сортувати ліву половину елементів,
потім відсортувати право половина елементів,
а потім об'єднати відсортовані половинки.
І ось, коли він відчуває себе як ми Copping з.
Я попросив вас розібратися п елементів, і я
кажучи, добре, зробіть це за допомогою сортування вліво і сортування право.
Але я говорю одне Інша справа, і це
є ключовою темою здається в інтуїції досі,
Тобто цей третій етап злиття.
Який хоча його здається настільки дурний в дусі,
як тільки об'єднати речі разом, здається,
є ключовим кроком на шляху збірка з двох проблем, які
в кінцевому рахунку, були розділені на дві частини.
>> Так сортування злиттям, давайте зробимо це, якщо ви будете гумор мене, ще одним демонстрації,
просто так, що у нас є деякі Номери працювати.
Чи можу я обміняти вісім стрес м'ячі для восьми осіб?
Гаразд, а як щодо вас три, ви чотири в цьому розділі, п'ять, шість, і давайте
у 7, 8, давай до.
ОК, да ОК.
Мінус 8, там ми йдемо, плюс 1.
Відмінно.
Гаразд давай, давайте швидко дати вам цифри.
Номер два, номер три, номер чотири, номер п'ять, шість, сім, вісім.
Я правильно зробив вісім на цей раз.
>> ОК, так що йти вперед, якби міг, і давайте сортувати в первісному порядку
що ми повинні були вчора який виглядав як це, якщо ви не заперечуєте.
І давайте зробимо це перед столом.
Гаразд, так сортування злиттям.
Це де це відбувається щоб отримати вид цікавого,
бо я, здається, даючи себе стільки менше інформації сьогодні.
>> Так сортування злиттям в першу чергу на вході п елементів,
і, очевидно, не менше двох, це вісім, так що я ще трохи попрацювати.
Так що тепер подумки ми як клас тепер в ще галузі,
що означає три кроки.
По-перше, у мене є для сортування Ліва половина елементів.
Так як же я йти про це?
Ну, я збираюся вид подумки розділити список тут,
Ви не повинні фізично рухатися, і я
збираюся зосередитися тільки на Ліва половина елементів тут.
Так як я можу йти про сортування Список тепер розміру чотири?
Що мій алгоритм?
Спочатку я перевірити це н менше двох, ні, так що я приступити до ще блок знову.
Сортувати залишив половину елементів.
>> Так що тепер знову, подумки, і це, коли
Ви повинні нараховуватися багато психічне історія, якщо ви будете.
Тепер я сортуванні ліву половина лівій половині.
Гаразд, так що тепер я називаю ж злиття алгоритм сортування, є н менше двох?
Ні, це два, так що я повинен розібратися ліва половина, а права половина.
Тому тут ми йдемо, сортувати ліву половину.
Чому б вам просто не зробіть один крок вперед.
Як тебе звуть?
>> АУДИТОРІЯ: Даррен.
>> СПІКЕР: Ден.
Ден вийшов вперед.
>> АУДИТОРІЯ: Даррен.
, Зроблено Даррен: СПІКЕР.
Ви сказали Даррен або Ден?
>> АУДИТОРІЯ: Даррен.
>> СПІКЕР: Даррен.
ОК, Даррен активізував вперед, і він тепер сортується.
І це майже безглуздим вимога, чи не так?
Я дійсно не здається, досягнення нічого, але давайте перейдемо.
Тепер дозвольте мені розібратися право половина елементів.
Як тебе звуть?
>> АУДИТОРІЯ: Люк.
>> СПІКЕР: Люк.
Давай, крок вперед.
Утрату, я упорядковано Луки.
Ліва половина тепер сортується та права половина тепер сортується,
але знову ж таки, є ключовий крок тут.
Що мені в наступному потрібно зробити?
Злиття відсортовані половинки.
Тепер ми збираємося просто все назад і вперед на цьому шляху,
бо я начебто потрібно деякі робочий простір.
Це майже як вони хлопці на столі,
і мені потрібна кімната переміщати їх на.
Так що я збираюся об'єднати ви, хлопці, подивившись
на лівій половині і в правій половині.
І який, очевидно, стоїть на першому місці, ліва половина або права половина?
Так права половина, так що давайте рухатися Луки над тут у вихідне положення Даррена.
І тепер, щоб об'єднати їх ліву половину в, Даррен збирається рухатися прямо там.
>> Так почувається майже бульбашкового сортування ефект,
але моє фундаментальне алгоритм, дуже різні на цей раз.
Але тепер, де речі стають трохи дратує, бо вас
повинні перемотати розумово звідки я зупинився.
Я щойно злив відсортовані половинки, який означає, що я, де в моєму алгоритмі?
Я повинен розібратися праву половину, чи не так?
>> Якщо ви перемотати, буквально на відео, ви будете
бачити, що ми дісталися до цього точка Луки і Дарреном
шляхом сортування лівий половина лівій половині.
Тоді ми об'єднали ті, відсортовані половинки, які
означає наступний крок є свого роду Права половина лівій половині.
Гаразд, так що давайте зробити це швидше.
Гаразд, шість, я збираюся стверджувати, Ви тепер сортуються, давай вперед.
Як тебе звуть?
>> АУДИТОРІЯ: Адріано.
>> СПІКЕР: Адріано.
Адріано тепер сортується.
І як тебе звуть?
>> АУДИТОРІЯ: Алекс.
>> СПІКЕР: Алекс тепер сортується.
Ліва половина, права половина, що останній крок?
Злиття.
Досить тривіально, так що я збирається об'єднати в шість,
зробити крок назад, вісім, зробити крок назад.
А тепер зверніть увагу, це корисно винос, що
Зараз правда про лівій половині Список, незалежно від того, як ми почали?
Це сортується.
>> Тепер це не відсортовані в великій схемі речей,
але це сортується незалежно один від одного з іншої половини.
Тепер те, що крок я на, якщо я продовжу перемотування, як історія почалася?
Тепер у мене є для сортування праву половину.
Так що тепер ми шлях назад в початок історії,
і давайте зробимо це швидше.
Так що я збираюся розібратися Права половина усього списку.
Який наступний крок?
Сортувати ліву половину правій половині.
Сортувати ліву половину Ліва половина правій половині.
І як тебе звуть?
>> АУДИТОРІЯ: Омар.
>> СПІКЕР: Омар, крок вперед, зробити.
Ліва половина сортується.
І як тебе звуть?
>> АУДИТОРІЯ: Кріс.
>> СПІКЕР: Кріс, зробити крок вперед, ви тепер сортуються.
Що ключовий крок зараз?
Злиття.
Так ніхто не збирається зливатися в місці тут, якби ви могли зробити крок назад,
і три збирається зробити крок назад, зливаються.
Так ліва половина Права половина, тепер сортується.
Чесно кажучи, цей алгоритм відчуває, як ми витрачаєте набагато більше часу, ніж раніше,
але якби ми зробили це в режимі реального часу, ми будемо бачити те, що їжі додому буде.
Отже, я тут, прямо половина правій половині,
дозвольте мені йти вперед і відсортувати ліву половину.
Крок вперед, як тебе звуть?
АУДИТОРІЯ: Ремсі.
СПІКЕР: Ремсі тепер сортується.
Як тебе звуть?
>> АУДИТОРІЯ: Марина.
>> СПІКЕР: Марина тепер сортується як добре, якщо ви берете один крок вперед.
Ключ крок тут тепер зливаються, я збирається зривати з моїх двох списків,
зліва і справа.
П'ять прийде першим, і сім прийде наступний.
І знову ж таки, це не випадково.
Той факт, що вони беруть кроки вперед і назад
призначена для представлення, що ми не можемо зробити цей алгоритм на місці, як легко
як бульбашкового сортування та відбору роду, і сортування вставками, де ми просто
зберігається заміни людей.
Я буквально потрібно свого роду з паперу для заміток, в яких
поставити цих людей в той час як я роблю злиття,
і тоді я можу покласти їх на місце.
І це ключовий момент, тому я використовую Новий ресурс, простір, не тільки час.
>> ОК, це дивно.
Ліва половина сортується, правій половині відсортоване, тепер, коли ключ злиття крок.
Як я буду об'єднати це?
Так що якщо ви будете слідувати моїм ліва рука і права рука,
Я збираюся вказати ліву руку в лівій половині, моя права рука
в правій половині, і тепер я повинен вирішити, крок за кроком, якого до злиття в.
Хто очевидно на першому місці?
Номер один.
Так йди сюди, ось наш сверхоперативной.
Так що тепер номер один, і повідомлення що я буду робити зі своєю правою рукою,
Я збираюся рухати правою рукою один переступити вказати номер три,
і тепер я повинен зробити те ж саме рішення.
А насправді коштують права в Фронт Луки тут, якби ви могли,
бо це наш сверхоперативной.
Так хто ж далі?
У нас є Луки з номер два або Кріс з номером три.
Очевидно Луки, число два, так що ви прийшли сюди.
>> Але моя ліва рука тепер збирається бути збільшено, щоб вказати на Даррена,
і ось ключ забрати з злиття, я збираюся продовжувати це робити,
очевидно, якщо вас вид з слідувати логіці.
Але мої руки ніколи не збирається йти у зворотному напрямку,
який означає, що я тільки коли перехід до зліва, з моєї процесу злиття,
і що буде ключем до наш аналіз через хвилину.
>> А тепер давайте закінчити це швидко.
Так три буде далі, потім чотири буде далі,
і тепер п'ять буде далі, то шість, і сім, і, нарешті, вісім.
За відчуттями самого повільного алгоритму поки немає, але не, якщо ми насправді
запустити його на такий же тактової частоти, таким чином, щоб
кажуть, з тим же цокає годинник, як і раніше.
Чому?
Ну, давайте подивитися на кінцевий результат.
>> Давайте повернемося сюди, хай мене підтягнути демонстрацію візуально
про те, що ми тільки що зробили.
Масштабування тут, на цьому сторінка тут, розповідаючи Firefox
що ми хочемо стояти в черзі в цій рамки, давайте
сказати бульбашкового сортування, з якою ми тепер добре знайомі,
Вибір роду, що є ще одним досить просто один,
і тепер сьогоднішня сортування злиттям, яка буде нашим кліматичні закінчення.
Причина це зайняло так багато більше тут з людьми і мені усно це,
Очевидно, я пояснюю кожен крок.
Але якщо ви просто виконати це, набагато як ми робили бульбашкового сортування та вибору
сортування не тільки візуально, годинники наскільки більш ефективно
це залучення в роботу поділ і завоювання
може бути при застосуванні до набору даних, це навіть не розмір вісім, але навіть багато,
набагато більше.
Я даю вам сортування злиттям, пліч-о стороні з цими іншими алгоритмами.
Це буде отримати боляче швидко, і кінцівка
не дуже кліматичні, вони просто в кінцевому підсумку сортуються.
Але ключ відняти те, що Подивіться, наскільки швидше сортування злиттям
було, якщо ви не думаєте, що я тільки почасти возитися з вами.
Якщо ми робимо це в останній раз, давайте Перезавантажити, давайте повернемося
і вибрати бульбашкового сортування, і тільки для ударів,
давайте виберемо вставку сортувати, для рівного рахунку.
І на цей раз знову, давайте вибрати сортування злиттям і давайте
реально працювати ці пліч-о-пліч.
>> І це не так, насправді, щаслива випадковість.
Те, що я ефективно зробити це у мене є розділив свій вклад в половині, знову,
і знову, і знову.
І є тільки так багато раз, ви можете розділити вхід навпіл, зліва
і право.
Що формула, що ми весь час бачу , Який описує поділ навпіл
знову, і знову, і знову, і знову?
>> АУДИТОРІЯ: Увійти н.
>> СПІКЕР: Увійти н.
Але тоді є ще один ключовий крок, цей алгоритм не ввійти п кроків.
Якби це було тільки увійти п кроків, ми були б у тій же проблеми
як і раніше, де ми не можемо бути що все в сортуються.
Ви повинні мінімально подивитися на п елементів щоб переконатися, що п елементів сортуються,
в іншому випадку це стрибок віри.
>> Так що це мінімально журнал п кроків, але що з цього приводу ключовою стадії злиття
де я злилися моя ліва половина і право половина і пройшовся по сцені?
Скільки кроків у тому, що для злиття?
Це п, але я не зробив усього об'єднати в останній раз.
На кожній з цих вкладених викликів, на кожному з тих, вкладених злиттів, я до сих пір сортуються.
Я об'єднані ці два хлопця, то ці два хлопці, то ці два хлопця і так далі.
>> Так що я злиття знову, і знову.
Скільки разів?
Так що кожен раз я розділив Список навпіл, я зробив злиття.
Розбийте список навпіл, зробити злиття.
Так що, якщо розділяє список можна зробити журнал п раз,
і злиття в кінцевому рахунку, приймає п кроки, що може бути зараз верхня
обмеження на працюючому Час нашого алгоритму?
н увійти н.
>> І справді, ось що ми досягли тут.
Так почуття, що ви бачите візуально, коли ці три речі працювати пліч-о-пліч
є н квадрат проти п квадрат проти н журналу п.
Які принципово ми побачимо, не тільки сьогодні, але в майбутньому,
набагато, набагато швидше.
Оплески для цих хлопців, Я винагородить їх зі стресом куль.
Давайте перервати тут сьогодні, і ми будемо бачити вас в понеділок.