>> [Музика Відтворення]
DAVID мала: Добре.
Гаразд, з поверненням.
Так що це 4-й тиждень, початок його, вже.
І ви пам'ятаєте, що минулого тижня, ми ставимо код відведених для тільки трохи
і ми почали говорити трохи більше високому рівні, про такі речі
пошук і сортування, яка хоча і кілька простих ідей, є
представник класу задач Ви почнете вирішувати особливо
як ви починаєте думати про остаточне проекти та цікаві рішення, які ви
можливо, доведеться реальних проблем.
Тепер бульбашкового сортування був одним з найпростіших такі алгоритми, і це
працював за наявності цих невеликих кількостях у вигляді списку або у вигляді масиву
Пузир їх шлях до вершини, і великі числа перемістити свій шлях до
До кінця цього списку.
>> І нагадати, що ми могли представляти бульбашкова сортування трохи
щось на зразок цього.
Отже, дозвольте мені йти вперед і натисніть кнопку Пуск.
Я попередньо бульбашкового сортування.
А якщо згадати, що вище синій лінії представляють великі номери, невеликі
Сині лінії являють собою невеликі номери, а ми проходимо через це знову і знову і
знову, порівнюючи два бари поруч один інші в червоному, ми збираємося, щоб поміняти
великий і мінімальним, якщо вони вийшли з ладу.
>> Так що це буде тривати і тривати і йти на, і ви побачите, що чим більше
елементи вносять свій шлях до вправо, а більш дрібні елементи є
пробираються вліво.
Але ми почали кількісно ефективністю,
Якість цього алгоритму.
І ми сказали, що в гіршому випадку, цей алгоритм взяв
приблизно скільки кроків?
>> Таким N квадраті.
І те, що було N?
>> АУДИТОРІЯ: число елементів.
>> DAVID мала: Так було N число елементів.
І тому ми будемо робити це часто.
Кожен раз, коли ми хочемо говорити про розміри проблема або розмір
вхід, або кількість часу, необхідне для отримання вихідних, ми просто
узагальненої всі вхід як н.
Отже, повернемося до тижня 0, кількість сторінок У телефонній книзі була N.
Кількість студентів в кімнаті с.
Так і тут, ми слідуємо цієї моделі.
>> Тепер н квадрат не є особливо швидко, так що ми спробували зробити краще.
І так ми дивилися на пару інші алгоритми, серед яких
були сортування вибором.
Так що вибір був Сортувати трохи по-іншому.
Це було майже простий, я наважуся сказати, якого я почав на початку
Список наших волонтерів, і я просто знову і знову і знову пройшов через
списку, вищипування найменшим елемента за один раз і покласти його або
її на початку списку.
>> Але і це, як тільки ми почали думати через математику і більше
картину, думав про те, скільки разів Я йшов назад і вперед і назад
і вперед, ми сказали, в гіршому випадку, Вибір роду теж було що?
N у квадрат.
В даний час в реальному світі, вона може насправді бути швидше.
Бо знову ж, у мене не було тримати відступає, як тільки я сортував
найдрібніших елементів.
Але якщо ми думаємо про дуже великих N, і Якщо ви як би зробити з математики як
Я зробив на борту, з N квадрат мінус щось, все інше
Крім того, N квадратів, як тільки N стає дійсно великим, що не
має великого значення, як багато.
Так як комп'ютерні вчені, ми ніби як закривати очі на менші
фактори і фокус тільки на фактор Вираз, який збирається зробити
Найбільша різниця.
>> Ну, нарешті, ми дивилися на сортування вставками.
І це було близькі за духом, але а не проходити через итеративно і
вибрати найменший елемент по одному час, я замість цього взяв руку, що я
було завдано, і я вирішила, все Добре, ти тут залишишся.
Потім я перейшов до наступного елементу і вирішив, що він або
вона належала тут.
А потім я переїхав далі й далі.
І я міг би, щоб, по шляху, перейти ці хлопці для того, щоб
звільнити місце для них.
Так, щоб був свого роду ментальний розворот відбору на зразок тих, що ми
називається сортування вставками.
>> Таким чином, ці теми виникають в реальному світі.
Всього кілька років тому, коли певні Сенатор був балотуватися на пост президента,
Ерік Шмідт, в той час генеральний директор Google, насправді мали можливість
взяти у нього інтерв'ю.
І ми подумали, що ми розділимо цю YouTube Затиск для вас тут, якби ми могли повернути вгору
гучності.
>> [ВІДТВОРЕННЯ ВІДЕО]
>> -Тепер, сенатор, ви тут, в Google, і мені подобається думати президентства
як співбесіда.
>> [Сміється]
>> -Тепер це важко отримати робота в якості президента.
І ви проходите суворості зараз.
Це також важко влаштуватися на роботу в Google.
У нас є питання, і ми просимо нашим кандидатам питання.
І на цей раз від Ларрі Швіммер.
>> [Сміється]
-Ви, хлопці, думаєте, я жартую?
Це прямо тут.
Що є найбільш ефективним способом сортувати мільйон двісті-розрядних цілих чисел?
>> [Сміється]
>> -Ну, ну -
>> -Пробач.
Може бути, ми повинні -
>> -Ні, ні, ні, ні, ні.
>> -Це не -
ОК.
>> -Я думаю, що бульбашкова сортування б бути неправильний шлях.
>> [Сміється]
>> [ВІТАННЯ І оплески]
>> -Давай, який сказав йому це?
ОК.
>> [КІНЕЦЬ відеовідтворення]
>> DAVID мала: Так що у вас є.
Таким чином, ми почали дати кількісну оцінку цим працює раз, так би мовити, з чимось
називається асимптотичним позначення, яке просто посилаючись на наш вид повороту
закривати очі на ці фактори і менше Тільки дивлячись на час роботи,
продуктивність цих алгоритмів, як н стає дійсно великим з плином часу.
І тому ми ввели велику О. І Big O представлене те, що ми думали,
як верхню межу.
А насправді, Баррі, ми можемо знизити , Ніж мікрофон трохи?
>> Ми думали про це є верхньою межею.
Так Big O п квадрат означає, що в гіршому випадку, щось на зразок
Вибір роду візьме п квадрат кроків.
Або щось на кшталт сортування вставками б квадрат N кроків.
Тепер за те, як вставки , Дивіться, яке було в гіршому випадку?
Дано масив, що найгірше можливі сценарії, які можуть виявитися
опинитеся перед?
>> Це абсолютно у зворотному напрямку, чи не так?
Тому що, якщо це абсолютно у зворотному напрямку, що вам потрібно зробити багато роботи.
Тому що, якщо ви абсолютно у зворотному напрямку, Ви збираєтеся знайти
найбільшим елементом тут, хоча він належить там.
Так що ви збираєтеся сказати, все правильно, по даний момент часу, ти тут залишишся,
так що ви залишити його в спокої.
>> Тоді ви розумієте, чорт забирай, я повинен перемістити цей трохи менший елемент
Зліва від вас.
Тоді я повинен зробити це знову і знову і знову.
І якби я ходив взад і вперед, ви владнає відчуваю продуктивність
, Що алгоритм, тому що я постійно перетасовування всі інші вниз у
масив, щоб звільнити місце для нього.
Так що це в гіршому випадку.
>> На відміну від цього -
і це було захоплюючим востаннє -
ми говорили, що сортування вставками був омега чого?
Який найкращий випадок хід час сортування вставками?
Так це насправді п.
Це був порожній, що ми залишили на дошці востаннє.
>> І це омега п, так чому?
Ну, в найкращому випадку, що сортування вставками буде переданий?
Ну, список, який все повністю відсортований вже, мінімальна робота.
Але те, що чарівне в тому, сортування вставкою є те, що, оскільки він починається тут і
вирішує, О, ти числа Один з них, ти тут залишишся.
Ой, яке щастя.
>> Ти номер два.
Ви також належать тут.
Номер три, ще краще, Вам варто до нас.
Як тільки він потрапляє в кінці Список, на сортування вставками у псевдокоді
, Що ми йшли у вербально Останній раз, це робиться.
Однак вибір виду, навпаки, продовжував робити те, що?
>> Продовжував йти за списком знову і знову і знову.
Оскільки ключове розуміння було тільки Як тільки ви дивилися всі шляхи до
кінці списку ви можете бути впевнені що елемент був обраний
Дійсно в даний час найменший елемент.
Таким чином, ці різні психічні моделях до отримання деяких дуже реальним
відмінності для нас, а також ці теоретичні асимптотичної відмінності.
>> Так просто, щоб резюмувати, то, Big O п квадрат, ми бачили кілька таких
алгоритмів досі.
Big O п?
Що алгоритм, здатний назвати Big O п?
У гіршому випадку, вона займає лінійний число кроків.
>> Добре, лінійний пошук.
А в гіршому випадку, коли це елемент, який ви шукаєте, коли
застосуванні лінійного пошуку?
>> Добре, в гіршому випадку, це навіть не там.
Або в другому гіршому випадку, це всі шляхи зрештою, який
плюс-мінус один крок різниці.
Отже, врешті-решт, ми можемо сказати, що це лінійна.
Big O п буде лінійний пошук, тому що в гіршому випадку,
Елемент навіть не там, або це всі шляхи в кінці.
>> Ну, Big O журналу н.
Ми не говорили дуже докладно про це, але ми бачили це раніше.
Що працює в так званий логарифмічний часу, в гіршому випадку?
>> Так, так що бінарний пошук.
І бінарного пошуку в гіршому випадку може мати елемент десь
середині, або в іншому в масиві.
Але ви тільки знайти його, як тільки ви розділити список в два рази, в
половина, навпіл, навпіл.
А потім вуаля, що вона є.
Або, знову ж, гіршому випадку, це навіть не там.
Але ви не знаєте, що це не є поки ніби не досягнете, що минулого
самий нижній елементів вдвічі і скорочення вдвічі і вдвічі.
>> Big O 1.
Можливо, ми можемо Big O 2, Big O 3.
У будь-який час ви хочете просто постійне число, ми просто начебто просто спростити
що Big O 1.
Хоча, якщо реально, вона займає 2 або навіть 100 кроків, якщо це
постійне число кроків ми просто скажемо Big O 1.
Що це алгоритм У Big O 1?
>> АУДИТОРІЯ: Визначення довжини змінної.
>> DAVID мала: Пошук Довжина змінної?
>> АУДИТОРІЯ: Ні, довжина якщо він вже відсортований.
>> DAVID мала: Добре.
ОК, так що знайти щось довжину якщо довжина що щось подібне
масив, зберігається в деякої змінної.
Тому що ви можете просто прочитати змінну, або роздрукувати змінної або
просто взагалі доступ до цієї змінної.
І вуаля, що вимагає постійного часу.
>> На відміну від цього, думаю, назад в хорошому стані.
Згадайте перший тиждень C, виклику просто Е і друку
щось на екрані, можливо, постійний час, так він просто приймає
деяке число циклів процесора, щоб показати , Що текст на екрані.
Або чекати - чи не так?
Як ще ми можемо моделювати продуктивність Е?
Хто-небудь хотів би не погодитися, що Може бути, це не зовсім постійний час?
У якому сенсі може Е біжить Час, фактично виводячи рядок на
екрані, будь то крім постійною.
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: Так.
Так що це залежить від нашої точки зору.
Якщо ми насправді думаємо про вхід Е як рядки, а
Тому ми вимірюємо розмір цього Введення його довжина - тому назвемо
що довжини N, а також -
Можна стверджувати, що Е є найбільшою O п тому що він збирається зробити кроки ви н
роздрукувати кожну з цих N символів, швидше за все.
Принаймні, в тій мірі, що ми припускаємо що, можливо, він використовує для петлі
під капотом.
>> Але ми повинні були б дивитися на це код краще зрозуміти його.
І дійсно, як тільки ви хлопці починають Аналізуючи власні алгоритми, ви будете
буквально зробити саме це.
Сортувати очного яблука код і думати Про нас - все в порядку, у мене є ця петля
Тут або у мене є вкладені цикли тут, що буде робити речі N N раз,
і ви можете сортувати розуму свій шлях через код, навіть якщо це
псевдокод, а не реальний код.
>> Так що про омега N квадратів?
Те, що було алгоритм, в кращому випадку, все ще взяв квадрат N кроків?
Так?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: Так Сортувати вибору.
Тому що в цьому проблема дійсно зменшений до того, що знову ж, я не знаю,
Я знайшов поточного меншому, поки Я перевірив всі прокляті елементів.
Так омега, скажімо, п тільки що прийшов з одним.
Сортування вставками.
Якщо список трапляється бути відсортовані вже, в кращому випадку ми просто повинні
щоб зробити один прохід через нього, і в цей момент ми впевнені.
І потім, що можна сказати лінійні, напевно.
>> Як щодо омега 1?
Що, в кращому випадку, може зайняти постійне число кроків?
Так лінійний пошук, якщо ви просто щастить і елемент, який ви шукаєте
знаходиться на самому початку списку, якщо це те, де ви починаєте вашу
лінійного обходу цього списку.
>> І це вірно для кілька речей.
Наприклад, навіть двійковий пошук омега 1.
Тому що, якщо ви отримуєте дійсно прокляте пощастило, і дотик смаку в середині
вашого масиву є число Ви шукаєте?
Таким чином, ви можете отримати пощастило там, а також.
>> Цей, нарешті, омега N § п.
Таким N журнал N, нам справді не говорити про поки немає, але -
>> АУДИТОРІЯ: Сортування злиттям?
>> DAVID мала: сортування злиттям.
Це було захоплюючим останнього часу, де ми запропонували, і ми показали
візуально, тобто алгоритми.
І сортування злиттям тільки одного такого Алгоритм, який принципово швидше
ніж деякі з цих інших хлопців.
Справді, злиття короткий не тільки в кращому випадку N журнал N, в гіршому
Випадок п § п.
І коли у вас є це збіг Омега і Big O є одне і те ж?
Ми можемо реально описати це як те, що називаються тета, хоча це
трохи рідше.
Але це просто означає, що два стрибки У цьому випадку ті ж самі.
>> Так сортування злиттям, що ж це дійсно зводяться до для нас?
Ну, згадайте мотивації.
Дозвольте мені підтягнути анімацію, яке Ми не дивилися на останній раз.
Це одне, та ж ідея, але це трохи більше.
І я збираюся йти вперед і відзначити, перше - у нас є на сортування вставками
лівому верхньому куті, а потім вибір роду, бульбашкова сортування, кілька інших видів -
оболонки і швидко, - що ми ще не говорили о, і купу і сортування злиттям.
>> Так принаймні спробувати зосередитися на ваших очах трійку на лівій, а потім
сортування злиттям, коли я натискаю цієї зеленою стрілкою.
Але я дозволю всі вони запускаються, просто щоб дати вам відчуття різноманітності
Алгоритми, які існують у світі.
Я збираюся дозволити цій перспективі всього за кілька секунд.
І якщо ви зосередитеся очі - вибрати Алгоритм, зосередитися на ньому протягом всього
секунд - ви починаєте бачити картина, що це здійснення.
>> Сортування злиттям, зауважте, робиться.
Купи сортування, швидкого сортування, Shell -
так що здається, ми ввели три найгірших алгоритмів минулого тижня.
Але це добре, що ми сьогодні тут, щоб подивитися на сортування злиттям, яке є одним з
більш легкі, щоб дивитися на, навіть хоча вона, ймовірно, буде згинатися ваш розум
тільки трохи.
Тут ми можемо бачити, як багато Вибір роду смокче.
>> Але, з іншого боку, це дійсно легко здійснити.
І може бути, для P набір 3, це одна з Алгоритми ви вирішили реалізувати
для стандартного видання.
Чудово підходить, абсолютно правильно.
>> Але знову ж, як н стає великим, якщо ви вибрати для реалізації більш швидкий алгоритм
подобається сортування злиттям, шанси у великих і більше входів, код є просто
збирається працювати швидше.
Ваш сайт буде працювати краще.
Ваші користувачі будуть щасливішими.
І так є ці ефекти фактично даючи
нам деякі глибокі думки.
>> Отже, давайте подивимося, що злиття Сортувати насправді все о.
Саме чудове в тому, що злиття роду є саме це.
Це, знову ж таки, те, що ми назвали псевдокод, псевдокод істота
Англійська-подібний синтаксис.
І простота роду захоплюючим.
>> Так на вході з п елементів - так, щоб просто означає, ось масив.
У цього є N речі в ньому.
Це все, що ми говоримо, що там.
>> Якщо N менше 2, повернутися.
Так що це просто тривіальний випадок.
Якщо N менше 2, то, очевидно, це 1 або 0, в цьому випадку річ
вже відсортований або неіснуючі, так що просто повернутися.
Там немає нічого, щоб зробити.
Так що це простий випадок, щоб обривати.
>> В іншому випадку, у нас є три етапи.
Сортувати ліву половину елементів, отсортируйте Права половина елементів
, А потім об'єднати відсортований половини.
Що цікаво тут те, що Я начебто понтіровавшего, вірно?
Там начебто кругової визначенню для цього алгоритму.
У якому сенсі цього алгоритму Визначення кругової?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: Так, мій алгоритм сортування, двох своїх кроків "вид
щось. "І так, що виникає Питання, ну, що я збираюся використовувати
для сортування лівої половини а права половина?
І краса в тому, що навіть при тому, знову ж, це галюциногенний
частина потенційно, ви можете використовувати той же Алгоритм для сортування лівій половині.
>> Але почекайте хвилину.
Коли ви сказали, щоб відсортувати Ліва половина, які дві
кроків буде далі?
Ми розберемося з лівої половини Ліва половина і право
половина лівої половини.
Блін, як мені впорядкувати ці два половини і чверті, в даний час?
>> Але це не страшно.
У нас є алгоритм сортування тут.
І хоча ви можете турбуватися Перше це начебто нескінченного
петлі, це цикл, який ніколи не скінчиться - він збирається
припиниться, як тільки те, що відбувається?
Після п менше 2.
Які в кінцевому підсумку відбудеться, тому що якщо ви продовжуйте ділити на два і
зниження в два рази скоротити вдвічі ці половини, безумовно, в кінці кінців ви будете в кінцевому
тільки з 1 або 0 елементів.
У цей момент, цей алгоритм говорить, що ви зробили.
>> Таким чином, справжня магія в цьому Алгоритм, здається, в
цей останній крок, зливаючись.
Це проста ідея просто злиття двох речі, це те, що в кінцевому рахунку буде
, Щоб дозволити нам відсортувати масив, скажімо, вісім елементів.
Так що у мене ще вісім куль до стресу Тут, вісім папірці, і один
Google скла -
які я отримую, щоб зберегти.
>> [Сміється]
>> DAVID мала: Якби ми могли прийняти вісім добровольців, і давайте подивимося, якщо ми можемо
грати в цю, таким чином.
Нічого собі, ОК.
Інформатика стає весело.
Добре.
Так, як ви троє найбільших руку там.
Чотири в спину.
А як щодо зробимо Вам три в цьому ряду?
І чотири в передній частині.
Таким чином, ви вісім, піднімайся.
>> [Сміється]
>> DAVID мала: Я насправді не впевнений, що це таке.
Це стрес куль?
Настільні лампи?
Матеріал?
В інтернеті?
>> ОК.
Так що приїжджайте і вище.
Хто хотів -
продовжують надходити.
Давайте подивимося.
І це ставить вас в місці -
Ви знаходитесь в одному розташування.
Ой, почекай хвилинку.
1, 2, 3, 4, 5, 6, 7 - о, добре.
Добре, що ми хороші.
Гаразд, у всіх є місце, але не на склі Google.
Дозвольте мені в чергу ці вгору.
Як тебе звуть?
>> МІШЕЛЬ: Мішель.
>> DAVID мала: Мішель?
Гаразд, ви отримуєте можливість виглядати Грайте і вигравайте, якщо це нормально.
Ну, я теж, я вважаю, на мить.
Всі права, в режимі очікування.
Ми намагаємося, щоб придумати випадки використання Google скла, і ми
думав, що це було б цікаво, щоб просто робити це коли люди на сцені.
Ми запишемо світі з їхньої точки зору.
Добре.
Не можливо, що Google призначене.
Гаразд, якщо ви не проти носити цьому протягом наступного незручний хвилин
це було б чудово.
>> Гаразд, так що ми маємо тут справу з масивом елементами і масиву, згідно
папірці в цих людей " руки, в даний час відсортовані.
>> МІШЕЛЬ: О, це так дивно.
>> DAVID мала: Це значною мірою випадковим.
І через хвилину, ми збираємося, щоб спробувати для реалізації сортування злиттям разом
і подивитися, де, що ключове розуміння є.
І трюк тут з сортування злиттям є те, що ми поки не передбачається.
Ми насправді потрібна додатковий простір.
Так що ж відбувається, що особливо цікаве в цьому те, що ці
хлопці, збираєтеся пересуватися трохи небагато, тому що я буду вважати, що
є додаткова масив просторі, скажімо, відразу за ними.
>> Так що якщо вони за свої крісла, це вторинне масиву.
Якщо вони сидять тут, це первинного масиву.
Але це ресурс, який ми маємо не використала досі з бульбашкою
сортування, з вибором виду, з сортування вставками.
Нагадаємо, минулого тижня, все просто вид перемішуються на місці.
Вони не використовували будь-якої додаткової пам'яті.
Ми створили місце для людей переміщення людей навколо.
>> Так що це ключове розуміння, теж.
Там є компроміс, в цілому в комп'ютерні науки, ресурсів.
Якщо ви хочете прискорити щось як час, ви збираєтеся
доведеться заплатити ціну.
І одна з цих цін дуже часто просторі, обсяг пам'яті або жорсткого
дискового простору, який ви використовуєте.
Або, якщо чесно, кількість програміст часу.
Скільки часу це займе у вас, людини, в цілях практичного здійснення ще кілька
складний алгоритм.
Але на сьогоднішній день, компроміс час і простір.
>> Так що, якщо ви, хлопці, могли б просто підніміть номери, щоб ми могли бачити, що Ви
Дійсно відповідний 4, 2, 6, 1, 3, 7, 8.
Відмінно.
Так що я збираюся спробувати, щоб організувати речі, якщо ви, хлопці, можете просто
Іди за мною тут.
>> Так що я збираюся здійснити, по-перше, Перший етап псевдокоду, який
на вході елементів п, якщо п менше 2, то повертається.
Очевидно, що ні застосовуються, тому ми рухатися далі.
Так відсортувати ліву половину елементів.
Значить, я збираюся зосередити свою увагу на мить на цих
четверо хлопців тут.
Добре, що я наступний робити?
>> АУДИТОРІЯ: Сортувати ліву половину.
>> DAVID мала: Так що тепер у мене є, щоб розібратися Ліва половина цих хлопців.
Бо знову ж, припустимо, до себе Мета полягає в сортуванні ліву половину.
Як ви це зробили?
Просто дотримуйтесь інструкцій, навіть хоча ми робимо це знову.
Так відсортувати ліву половину.
Тепер я сортування цих двох хлопців.
Що буде далі?
>> АУДИТОРІЯ: Сортувати ліву половину.
>> DAVID мала: Сортувати ліву половину.
Так що тепер це, це місце тут, наведено список розмір 1.
І те, що тебе звуть?
>> PRINCESS DAISY: Принцеса Дейзі.
>> DAVID мала: Принцеса Дейзі тут.
І ось вона вже відсортований, так як Список має розмір 1.
Що мені робити наступний?
OK, повернутися, тому що список з розмір 1, який складає менше 2.
Тоді в чому ж наступний крок?
І тепер ви повинні вид повернутися у вашому розумі.
>> Сортувати права половина, яка -
Як тебе звуть?
>> Лінда: Лінда.
>> DAVID мала: Лінда.
І так, що ж нам тепер робити, що у нас є список розміром 1?
>> АУДИТОРІЯ: Повернення.
>> DAVID мала: Обережно.
Повернемося першої, і тепер третій Крок - і якщо я ніби зобразити його
охоплює два місця, тепер я необхідно об'єднати ці два елементи.
Так що тепер, на жаль, елементи вийшли з ладу.
Але на цьому процес об'єднання починає ставати переконливими.
>> Так що, якщо ви, хлопці, могли постояти за просто момент, я буду мати потребу в вас, в
момент, щоб крок позаду стільця.
І якщо Лінда, оскільки 2 знаходиться менше, ніж 4, чому не
Вас приходять в першу чергу?
Залишайтеся там.
Так Лінда, ви приходите навколо першої.
>> Зараз насправді, якщо це просто масив ми могли б просто перемістити її в режимі реального часу
цієї кафедри в це місце.
Отже, уявіть, що було потрібно якийсь постійне число кроків 1.
А тепер -
але ми повинні поставити вас в першого місця тут.
>> І тепер, якщо ви могли б приходити, також, ми збираємося
Розміщення знаходиться в два.
І навіть якщо це відчуває, що це зайняти деякий час, те, що приємно зараз
що ліва половина Ліва половина тепер сортується.
Так що був наступний крок, якщо ми зараз перемотати далі в історію?
>> АУДИТОРІЯ: Права половина.
>> DAVID мала: Сортувати праву половину.
Таким чином, ви, хлопці, повинні зробити це, а також.
Так що якщо ви могли встати на мить?
А як тебе звати?
>> Джессі: Джесс.
>> DAVID мала: Джесс.
Отже, Джесс Тепер ліва половину правої половини.
І так вона список Розмір 1.
Вона, очевидно, сортують.
І ваше ім'я?
>> МІШЕЛЬ: Мішель.
>> DAVID мала: Мішель, очевидно, Перелік розмір 1.
Вона вже відсортований.
Так що тепер відбувається чарівництво, Процес злиття.
Так що, хто збирається прийти?
Очевидно Мішель.
Так що, якщо ви могли б приходити назад.
Просторі ми маємо в наявності для неї тепер Прямо за це крісло тут.
І тепер, якщо ви могли б повернутися, а також, у нас тепер є, щоб бути ясним, два
половин, кожна з розмір 2 -
і просто заради зображенням учасника, якщо Ви могли б зробити трохи простору -
однією лівою половині, по одному Права половина тут.
>> Перемотка далі в історію.
Який крок буде наступним?
>> АУДИТОРІЯ: Merge.
>> DAVID мала: Так що тепер у нас є для злиття.
Так добре, так що тепер, на щастя, ми просто звільнив чотирма стільцями.
Таким чином, ми використовували два рази більше пам'яті, але ми можемо дати фліп-флоп між
два масиви.
Так, число яких на першому місці?
Так Мішель, це очевидно.
Так приходять і беруть ваше місце тут.
А потім номер 2, очевидно, Далі, так що ви прийшли сюди.
Номер 4, номер 6.
І знову, незважаючи на те, що є трохи пішохідних прогулянок залученого,
дійсно, це може відбутися миттєво, шляхом переміщення одного -
Добре, добре грав.
>> [Сміється]
>> DAVID мала: А тепер ми в досить хорошій формі.
Ліва половина всього вхідного тепер сортуються.
Гаразд, ці хлопці були Перевага моєї -
як вона в кінцевому підсумку всі дівчата на наліво і всі хлопчики праворуч?
>> Добре, таким чином хлопців чергу.
Тому я не буду йти Ви через ці кроки.
Ми побачимо, якщо ми можемо повторно ж псевдокод.
Якщо ви хочете йти вперед і встати, і ви, хлопці, дозвольте мені дати вам мікрофон.
Дивіться, якщо ви не можете повторити те, що ми тільки що зробили тут, на
Інший кінець списку.
Хто повинен говорити першим, заснований на алгоритмі?
То поясніть, що ви робите, перш Ви робите будь нозі рухів.
>> Виступаючий 1: Ну, добре, так як Я лівої половини
Ліва половина, я повернуся.
Вірно?
>> DAVID мала: Добре.
>> Виступаючий 1: А потім -
>> DAVID мала: хто MIC перейти до наступного?
>> Виступаючий 1: Наступний номер.
>> Доповідач 2: Так що я права половина лівої половини
ліва половина, і я повернуся.
>> DAVID мала: Добре.
Ви повернетеся.
Так що тепер який наступний за вами двома?
>> Доповідач 2: Ми хочемо бачити, хто менше.
>> DAVID мала: Абсолютно вірно.
Ми хочемо об'єднати.
Простір ми збираємося використовувати для злиття Вас у, навіть якщо вони
Очевидно, вже відсортовані, ми збираємося піти по тому ж алгоритму.
Так хто йде в спині в першу чергу?
Таким 3, а потім 7.
А тепер йде мікрофон з цими хлопцями, добре?
>> Виступаючий 3: Так що я праву половину ліву половину, і мій N менше
1, так що я просто хочу, щоб пройти -
>> DAVID мала: Добре.
>> Виступаючий 4: Я права половина Права половина права половина, і я
Також одна людина, так що я збирається повернутися.
Так що тепер ми зливаємося.
>> Виступаючий 3: Отже, ми повертаємося.
>> DAVID мала: Так ви йдете в задню частину.
Так 5 йде в першу чергу, то 8.
А тепер аудиторії, який є кроку нам потрібно тепер перемотати
повернутися до в нашій свідомості?
>> АУДИТОРІЯ: Merge.
>> DAVID мала: об'єднання лівої і правої половини половину початкової ліву половину.
Так що тепер -
і просто, щоб було зрозуміліше, зробити трохи простору
між вами двома хлопцями.
Так що тепер це два списки, зліва і справа.
Так як же нам тепер злиття, ви хлопці в перший ряд місць знову?
>> 3 йде в першу чергу.
5 Тоді, очевидно.
Потім 7, і тепер 8.
ОК, а тепер ми?
>> АУДИТОРІЯ: не робиться.
>> DAVID мала: Не за те, що Очевидно, що тут один крок залишилося.
Але, знову ж, причина я використовую це жаргону, як "перемотування в своєму розумі,"
це тому, що насправді що відбувається.
Ми проходимо через всі ці кроки, але ми ж начебто зупиняючись на
момент, дайвінг глибше в Алгоритм, затримавшись на мить,
занурюватися глибше і глибше в алгоритм, і Тепер ми повинні розібратися перемотування в нашій
уми і скасувати всі ці шари що ми начебто припинене.
>> Так що тепер у нас є два списки розміру 4.
Якщо ви, хлопці, могли встати в останній раз і зробити трохи місця тут, щоб
дати зрозуміти, що це лівий половину початкової,
Права половина оригіналу.
Хто першим номером, що ми потрібно тягнути в спину?
Мішель, звичайно.
>> Так ми одягли Мішель тут.
І хто має номер 2?
Номер 2 приходить на спині, а також.
Номер 3?
Відмінно.
Номер 4, № 5, № 6, № 7, і № 8.
>> Добре, таким чином, було схоже на багато кроків, це точно.
Але тепер давайте подивимося, якщо ми не можемо підтвердити роду інтуїтивно, що це
Алгоритм принципово, зокрема, N стає дійсно великим, як ми бачили
з анімацією, є принципово швидше.
Тому я стверджую, цей алгоритм, в гіршому випадок і навіть у кращому випадку,
велика O п § п раз.
Тобто, є деякі аспекти цього алгоритм, який користується N кроків, але
є ще один аспект десь в що ітерації циклу, що, що
бере журнал N кроків.
Чи можемо ми вказати на те, що ці два числа мають на увазі?
Ну, і де -
Де мікрофон йти?
>> Виступаючий 1: Чи буде увійти п порушення нас на дві частини -
ділення на два, по суті.
>> DAVID мала: Абсолютно вірно.
Кожен раз, коли ми бачимо в будь-який алгоритм таким чином, далеко, там був цей зразок
поділ, ділення, ділення.
І це зазвичай відновлюють на те, що це
логарифмічні, логарифм за основою 2.
Але це дійсно може бути що завгодно, але ввійти основою 2.
>> Тепер те, що про росіян?
Я бачу, що ми як би розділило вас Хлопці - розділило вас, розділило вас,
розділило вас, розділений вас.
Де врешті-решт прийшли?
>> Так що це злиття.
Тому що думати про це.
При об'єднанні вісім осіб разом, за допомогою чого половина з них представляють собою набір з чотирьох
і інша половина інший набір з чотирьох, як ви йдете
про виконання злиття?
Ну, ви, хлопці, зробили це досить інтуїтивно.
>> Але якби я зробив це, а трохи більше методично, я б вказав на
лівий людина спочатку з моєю лівою боку, вказав на крайню ліву людини
що половина з своєю правою рукою, і тільки згодом йшли через
список, вказуючи на найменший елемент кожен раз, рухаючи пальцем по і
за які необхідні для створення списку.
Але те, що про цю ключовою злиття процес я порівнюю ці пари
елементів.
З правій половині і з лівого половину, я ніколи не відступає один раз.
>> Так злитися приймає не більше N кроків.
І скільки разів у мене є зробити це злиття?
Ну, не більше, ніж N, і ми просто побачив, що з остаточним злиттям.
І так, якщо ви робите те, що займає увійти N п кроків рази, або навпаки,
він збирається дати нам п раз журнал N.
>> І чому це краще?
Ну, якщо ми вже знаємо, що журнал N краще, ніж N - чи не так?
Ми бачили в бінарний пошук, телефонна книга Наприклад, журнал N був безперечно
краще, ніж лінійні.
Значить, раз журнал N п безперечно краще, ніж N раз інше
N, N AKA квадраті.
І це те, що ми в кінцевому підсумку відчувають.
>> Настільки великі оплески, якщо Ми могли б, цих хлопців.
>> [Оплески]
>> DAVID мала: І ваші подарунки Розставання - Ви можете зберегти номери,
Якщо ви хотіли б.
І ваш прощальний подарунок, як звичайно.
О, і ми надішлемо Вам кадри, Мішель.
Спасибо.
Добре.
Допомогти собі стрес м'яч.
>> І дозвольте мені підтягнути, в той же час, наш друг Роб Боуден запропонувати
Дещо інший погляд на це, так як ви можете думати про ці
кроків відбувається в кілька іншому.
Насправді, установка за те, що Роб про щоб показати нам, припускає, що ми
вже зробили поділ великий список на вісім невеликих списків,
кожна розміром 1.
>> Таким чином, ми міняємо псевдокод трохи тільки до виду отримати в
Основна ідея, як злиття робіт.
Але час роботи, що він збирається зробити, це як і раніше
буде тим же самим.
І знову, налаштування тут є те, що він почалося з вісьмома списки розміру 1.
Отже, ви пропустили частину, де він насправді зробили журнал N, N журнал, журнал N
поділ вхідного сигналу.
>> [ВІДТВОРЕННЯ ВІДЕО]
>> -Ось і все на першому кроці.
Для другого кроку, неодноразово об'єднує пару списків.
>> DAVID мала: Хм.
Тільки звук йде з мого комп'ютера.
Давайте спробуємо ще раз.
>> -Просто довільно вибрати, який - тепер у нас є чотири списку.
Дізнатися раніше.
>> DAVID мала: Там ми йдемо.
>> Злиття-108 і 15, ми врешті з списку 15, 108.
Злиття 50 і 4, ми в кінцевому підсумку з 4, 50.
Злиття 8 і 42, ми в кінцевому підсумку з 8, 42.
І злиття 23 і 16, ми в кінцевому підсумку з 16, 23.
>> Тепер всі наші списки розміру 2.
Слід зазначити, що кожен з чотири списки відсортовані.
Так ми можемо почати злиття пар списки.
Злиття 15 і 108, 4 і 50, ми спочатку взяти 4, то 15, то
50, то 108.
Злиття 8, 42 і 16, 23, ми спочатку 8, то 16, то 23,
то 42.
>> Так що тепер у нас є тільки два списки розмір 4, кожен з яких сортують.
Так що тепер ми об'єднати ці два списки.
По-перше, ми беремо 4, то візьмемо 8, то ми беремо 15, то 16, то
23, то 42, то 50, то 108.
>> [КІНЕЦЬ відеовідтворення]
>> DAVID НЕ мала: Знову ж, зауважте, він ніколи торкнувся даної чашки більше одного разу
після зростання за його межами.
Так він ніколи не повторюється.
Значить, він завжди рухається в бік, а от де ми отримали нашу н.
>> Чому б не дозволити мені підтягнути одну анімацію , Що ми бачили раніше, але на цей раз
орієнтуючись тільки на сортування злиттям.
Дозвольте мені йти вперед і збільшення на це тут.
Перш за все дозвольте мені вибрати випадковий введення, збільшити це, і ви можете сортувати, см.
те, що ми вважали само собою зрозумілим, раніше, сортування злиттям насправді робить.
>> Так помітите, що ви отримаєте ці половинки або цих кварталів або ці восьмих
проблема, яка раптом почати приймати хорошій формі.
І, нарешті, ви побачите в У самому кінці, що БАМ,
всі об'єднані разом.
>> Так що це просто три різних бере на себе ту ж ідею.
Але ключове розуміння, як і розриву і перемогти в першому класі,
було те, що ми вирішили якось розділити Проблема в щось більше, в
щось на зразок ідентичні за духом, але менше і менше
і менше.
>> Тепер інший цікавий спосіб сортувати думаю про це, хоча це не
збираюся дати вам те ж інтуїтивне розумінні,
Наступні анімації.
Так що це відео хтось поклав разом , Що пов'язано різних
звуків з різних операцій для сортування вставками, для сортування злиттям, і
на пару інших.
Таким чином, в даний момент, я вдарю Play.
Це близько хвилини завдовжки.
І навіть якщо ви все ще можете побачити моделі відбувається, цей час ви можете
також почути, як ці алгоритми виконання по-різному і з
кілька різних моделей.
>> Це сортування вставками.
>> [TONES композиція]
>> DAVID мала: Це знову намагається вставити кожен елемент
в якій вона належить.
Це бульбашкового сортування.
>> [TONES композиція]
>> DAVID мала: І ви можете сортувати, почуття як відносно мало працювати, що він робить
на кожному кроці.
Це те, що звучить як занудство.
>> [TONES композиція]
>> DAVID мала: Це вибір роду, де ми вибираємо елемент, який ми формуємо
проходячи знову і знову і знову і покласти його на самому початку.
>> [TONES композиція]
>> DAVID мала: Це сортування злиттям, яке Ви можете дійсно починаєш відчувати.
>> [TONES композиція]
>> [Сміється]
>> DAVID мала: Те, що називається GNOME сортування, яку ми не дивилися.
>> [TONES композиція]
>> DAVID мала: Так покажіть, в даний час, відволікатися, як ви, сподіваємося, по
музику, якщо я можу ковзати трохи трохи математики тут.
Так що є і четвертий шлях, що ми можемо думати про те, що це означає, що ці
функцій, які будуть швидше, ніж ті, що ми бачили раніше.
І, якщо ви приїжджаєте на курс від математика фоном, ви
насправді може бути, вже знаєте, що ви може ляпас строком на цій техніці -
а саме рекурсію, функції що так чи інакше викликає сам себе.
>> І знову ж, нагадати, що сортування злиттям псевдокод рекурсивної в тому сенсі,
що один із кроків сортування злиттям у було закликати роду -
тобто безпосередньо.
Але, на щастя, бо ми продовжували виклику сортування або сортування злиттям,
Зокрема, на менші і менші і менше список, ми в кінцевому рахунку
дна, завдяки чому ми будемо називати базовий варіант, жорстко випадку,
сказав, що якщо список невеликий, менше 2 У цьому випадку, просто негайно повернутися.
Якщо у нас не було, що особливий випадок, Алгоритм ніколи не буде нижньої межі,
і ви б дійсно потрапити в нескінченний цикл дійсно назавжди.
>> Але припустимо, що ми хотіли зараз поставлю деякі номери на цьому, знову ж таки, з використанням н
як розмір вхідних даних.
І я хотів би запитати вас, що загальний час, що витрачається на
працює сортування злиттям?
Або більш загальному сенсі, що вартість його в часі?
>> Ну, це досить легко виміряти це.
Якщо N менше 2, час, що витрачається У сортування N елементів,
де п дорівнює 2, 0.
Тому що ми просто повертаємо.
Там немає роботи, яку належить зробити.
Тепер, можливо, може бути, це один крок чи два кроки, щоб з'ясувати кількість
працювати, але це досить близько до 0, що Я просто хочу сказати, немає роботи
вимагається, якщо список настільки мала бути нецікавим.
>> Але цей випадок цікавий.
Рекурсивні випадок був філія псевдокод, сказав ще, отсортируйте
ліва половина, сортувати право половину, об'єднати дві половини.
Тепер чому це вираз заявляєте, що рахунок?
Ну, T п просто означає, що час, щоб розібратися N елементів.
А потім на правій стороні Знак рівності там, T п розділений
2 Мається на увазі вартість того, що?
Сортування ліву половину.
Інший T п поділене на 2 імовірно з посиланням на вартість
сортувати праву половину.
>> І тоді N Plus?
Це злиття.
Тому що, якщо у вас є два списки, один з Розмір п над 2 і іншим розміром N
більше 2, ви повинні торкнутися по суті кожного з цих елементів, як і Роб
торкнулася кожної з чашок, і тільки як вказувалося в кожному з
добровольців на сцені.
Так п за рахунок злиття.
>> Зараз, на жаль, ця формула Також сама рекурсивної.
Таким чином, якщо задано питання, якщо п, скажімо, 16, якщо є 16 осіб на сцені
або 16 чашок на відео, скільки всього кроки потрібно для того, щоб впорядкувати їх
з сортування злиттям?
Це насправді не очевидну відповідь, тому що тепер у вас є до виду
рекурсивно відповісти на це формулою.
>> Але це нормально, тому що то дозвольте мені висунути що ми робимо наступне.
Часу, необхідного для сортування або 16 осіб 16 чашок, які будуть представлені
взагалі як Т 16.
Але, рівний, за нашими попередній формулі, 2 рази кількість
Час, необхідний для сортування 8 чашок плюс 16.
І знову ж, плюс 16 самий час об'єднуватися, і два рази Т 8
час, щоб розібратися ліва половина і права половина.
>> Але знову ж, цього недостатньо.
Ми повинні зануритися в більш глибоких.
Це означає, що ми повинні відповісти питання, що таке Т 8?
Ну Т 8 знаходиться всього в 2 раз T 4 плюс 8.
Ну, що Т 4?
Т 4 знаходиться всього в 2 рази Т 2 плюс 4.
Ну, що Т 2?
Т 2 знаходиться всього в 2 рази Т 1 плюс 2.
>> І знову ж, ми начебто отримання застряг в цьому циклі.
Але мова йде про вдарити, що так званий базовий варіант.
Тому що те, Т 1, хіба ми стверджуємо?
0.
Так що тепер, нарешті, ми можемо працювати у зворотному напрямку.
>> Якщо Т 1 0, тепер я можу повернутися до одного лінії Ось цей хлопець, і я можу
підключіть 0 для T 1.
Значить, вона дорівнює нулю 2 рази, інакше відомий як 0, а також 2.
І так, щоб всі вираз 2.
>> Тепер, якщо я беру Т 2, відповідь на 2, підключити його до середньої лінії, T
4, то це дає мені 2 рази 2 плюс 4, тому 8.
Якщо я після цього підключити 8 до попереднього лінії, що дає мені 2 рази 8, 16.
І якщо ми будемо продовжувати те, що з 24, додавши в 16, ми, нарешті, отримати
значення 64.
>> Тепер, коли саме по собі говорить роду Нічого позначення N,
Big O, омега, які ми говорили.
Але виявляється, що насправді 64 16, розмір вхідного
логарифм за основою 2 з 16.
І якщо це трохи незнайомим, просто згадую, і повернуся
Вам зрештою.
Якщо це логарифм за основою 2, це як 2 зведене в те, що дає вам 16?
О, це 4, так що це 16 разів 4.
>> І знову ж, це не має великого значення, якщо це є свого роду туманний пам'яті зараз.
Але зараз, приймати на віру що 16 журнал 16 одно 64.
І так дійсно, за допомогою цього простого розсудливості перевірити, ми підтвердили -
але формально не доведена -
що час злиття Сортувати дійсно N N увійти.
>> Так не погано.
Це безперечно краще, ніж алгоритми, які ми бачили дотепер, і
це тому, що ми використовувала, один, методику, яка називається рекурсією.
Але що ще більш цікаво, ніж та, що Поняття поділу і завоювання.
Знову ж, по-справжньому тиждень 0 речі, які навіть зараз повторюється в
більш переконливим способом.
>> Тепер задоволення мало вправ, якщо у Вас є ніколи не робив цього, - і ви, ймовірно,
не буде, так як вид нормального люди не думають, щоб зробити це.
Але якщо я йду на google.com і якщо Я хочу дізнатися що-небудь про
рекурсію, Enter.
>> [Сміється]
[Сміх]
DAVID мала: поганий жарт поступово поширюється.
[Сміється]
DAVID мала: Про всяк випадок, що вона є.
Я не записати це неправильно, і є жарт.
Добре.
Поясніть це люди поруч з вами, якщо Це не зовсім натиснута тільки поки.
Але рекурсії, в цілому, відноситься в процесі виклику функції
собі, або в більш загальному, розділивши Проблема в те, що може бути
вирішити по частинах рішення ідентичних Представник проблем.
>> Ну, давайте передач зміни на мить.
Ми б закінчити на певних кульмінацій, так що давайте почнемо встановлювати
етап, протягом декількох хвилин на дуже простій ідеї -
перекачування, що два елементи, чи не так?
Всі ці алгоритми ми були Говорячи про останні декілька
Лекції включають деякі роду заміни.
Сьогодні було візуалізували їх отримання вгору зі свого стільця і
ходять, але в коді, ми б просто взяти елемент з одного масиву
і вставити його в інший.
>> Так як же нам йти про це?
Ну, дозвольте мені йти вперед і написати швидкий програму тут.
Я збираюся йти вперед і робити це як таке.
Давайте назвемо це -
Чого ми хочемо назвати це одна?
>> Взагалі-то, немає.
Дозвольте мені перемотування назад.
Я не хочу, щоб зробити це ще захоплюючим.
Це зіпсує задоволення.
Давайте зробимо це замість цього.
>> Припустимо, що я хочу написати трохи програма і що в даний час використовує цю
Ідея рекурсії.
Я б отримав попереду себе там.
Я збираюся зробити наступне.
>> По-перше, швидко включати стандартні io.h, а також включати в себе, cs50.h.
А потім я збираюся йти вперед і оголосити недійсним тап_п
у звичайному порядку.
Я зрозумів, я невірно названі файл, так що дозвольте мені додати. C розширенням ось так
що ми можемо скомпілювати його належним чином.
Почати цю функцію.
>> А функція Я хочу написати, досить Простіше кажучи, це той, який запитує
користувача число, а потім складає всі числа між цим
числа і, скажімо, 0.
Отже, спочатку я збираюся йти вперед і оголосити Int N.
Потім я копіюю код, який ми використовували на деякий час.
Хоча дещо вірно.
Я повернуся до цього трохи пізніше.
>> Що я хочу зробити?
Я хочу сказати, Е позитивної ціле будь ласка.
А потім я збираюся кажуть N отримує отримати Int.
Отже, ще раз, деякі шаблонний код що ми використовували раніше.
І я збираюся це зробити а п менше 1.
Так що це буде гарантувати, що користувач дає мені позитивне ціле число.
>> А тепер я збираюся зробити наступне.
Я хочу скласти всі числа від 1 і N, або від 0 до N,
те ж саме, щоб отримати загальну суму.
Так що найбільший символ Sigma що ви могли б згадати.
Так що я збираюся зробити це, першого скликання функція під назвою Sigma,
передаючи його по-російськи, а потім я збираюся Е сказати, відповідь тут же.
>> Коротше кажучи, я отримую і Int від користувача.
Я можу гарантувати, що це позитивно.
Я оголошую змінну відповідь цілого типу і зберігати в його повернення
Значення сигма, передаючи N якості вхідних даних.
І тоді я роздрукувати, що відповісти.
>> На жаль, хоча сигма звучить як щось, що може бути в
math.h файлу, його декларації, це насправді немає.
Так що це нормально.
Можна реалізувати це сам.
Я збираюся реалізувати функцію називають Sigma, і він збирається взяти
параметра -
Давайте просто називати це м, всього так все по-іншому.
А потім тут, я збираюся сказати, Ну, якщо м менше 1 - це
дуже нецікаві програми.
Так що я збираюся йти вперед і негайно повернути 0.
Це просто не має сенсу скласти всі числа від 1 м, якщо м
саме 0 або негативним.
>> А потім я збираюся йти вперед і робити це дуже итеративно.
Я збираюся робити такого роду старої школи, і я збираюся йти вперед
і сказати, що я збираюся оголосити суму рівним 0.
Тоді я буду мати для петлі Int -
і дозвольте мені зробити це у відповідності з нашими Розподіл коду, тому у вас є копія
будинку. INT I отримує 1 на до я менше або дорівнює м.
Я плюс плюс.
І тоді всередині цього циклу -
ми майже на місці -
сума потрапляє сума плюс 1.
А потім я збираюся повернути суму.
>> Так що я зробив це швидко, зовсім правда.
Але, знову ж, основна функція досить просто на основі коду, який ми
написано до цих пір.
Використовує подвійну петлю, щоб отримати позитивний Int від користувача.
Я потім передати десяткового до нової функції називається сигма, назвавши його, знову ж таки, з.
І я зберігання значення, що повертається, відповідь від чорного ящика даний час
відомий як сигма, в змінну називають відповіддю.
Тоді я роздрукувати його.
>> Якщо ми тепер продовжимо розповідь, яким сигма реалізовані?
Я пропоную реалізувати наступним чином.
По-перше, трохи перевірки помилок щоб переконатися, що користувач не
возитися зі мною і передавши деякі негативні або значення 0.
Тоді я оголошую змінну суму і встановити його в 0.
>> І тепер я починаю переходити від Я одно 1 все, аж до і включаючи м,
тому що я хочу, щоб включити всі числа від одного до М включно.
А всередині цього циклу, я просто Сума отримує те, що він є зараз, плюс
Значення я.
Крім того значення я.
>> Як осторонь, якщо ви не бачили цього і колись, є деякі синтаксичний цукор
для цієї лінії.
Я можу переписати це як плюс Я одно, просто щоб врятувати себе кілька натискань клавіш
і виглядати трохи прохолодніше.
Але от і все.
Це функціонально те ж саме.
>> На жаль, ця коду Чи не збираєтеся компілювати ще.
Якщо я запускаю зробити сигма 0, як же я Я збираюся отримати кричав на?
Як це буде, не подобається?
>> АУДИТОРІЯ: [нерозбірливо].
>> DAVID мала: Так, я не оголошував Функція нагорі, чи не так?
C почасти нерозумно, тим, що він тільки робить те, що ви скажете їй зробити, і ви
повинні зробити це в такому порядку.
І тому, якщо я вдарив Введіть тут, я збираюся отримати попередження про Sigma неявній
декларації.
>> О, не проблема.
Я можу піднятися на самий верх, і я можу кажуть, все в порядку, почекай хвилинку.
Sigma є функцією, яка повертає Цілочисельне і він очікує
ІНТАС входу, крапка з комою.
Або я міг би поставити весь функції над головною, але в цілому, я б
рекомендую проти цього, тому що це добре, щоб завжди мати основні нагорі, таким чином
Ви зможете зануритися в них і знаю, що Програма робить, читаючи основні першим.
>> Так що тепер дозвольте мені очистити екран.
Рімейк сигма 0.
Все, здається, щоб перевірити.
Дозвольте мені запустити сигма 0.
Позитивне в тому.
Я дам йому кількість 3 зберегти його простим.
Отже, що повинен дати мені 3 плюс два плюс один, так 6.
Введіть, та й взагалі я отримую 6.
>> Я можу зробити щось більше -
50, 12, 75.
Так само, як дотичній, я збираюся зробити щось смішне, як дійсно великий
число, О, це фактично вдалося -
Ех, я не думаю, що це правильно.
Давайте подивимося.
Давайте вже возитися з ним.
>> Це проблема.
Що відбувається?
Коду не так уже й погано.
Він як і раніше лінійно.
Свист є хорошим ефектом, однак.
Що відбувається?
>> Не впевнений, що я почув його.
Ось і виходить, - і це як в сторону.
Це не сердечника Ідея рекурсії.
Виявляється, тому, що я намагаюся представляють таку велику кількість, більшість
ймовірно, це неправильної інтерпретації на С, не позитивне число,
але негативне число.
>> Ми не говорили про це, але це Виявляється, є негативні числа
у світі на додаток на позитивні числа.
І кошти, за допомогою яких ви можете являють собою негативне число
по суті є, використовується один спеціальний біт, щоб вказати,
позитивні над негативними.
Це трохи складніше, ніж, але це основна ідея.
>> Тому, на жаль, тоді, коли З заплутаною один з тих бітів, насправді це означає,
о, це негативне число, мій цикл Тут, наприклад, немає фактично ніколи
збирається припинити.
Так що якщо я насправді були надрукувавши небудь знову і знову, ми,
см. багато.
Але знову ж, це, крім точки.
Це дійсно так, начебто інтелектуальне цікавість, що ми приїдемо
повернутися до зрештою.
Але зараз, це правильне реалізацію, якщо ми припускаємо, що
Користувач забезпечить цілих , Які вписуються в цілі.
>> Але я стверджую, що цей код, чесно кажучи, можна було б зробити набагато більше, просто.
Якщо мета під рукою прийняти ряд м, як і складіть всі
номери між ним і один або, навпаки між 1 і це, я стверджую,
що я можу зайняти цю ідею, які зливаються Сортувати мав, який брав проблеми
такого розміру і розділивши її в щось менше.
Може бути, не половина, але менше, але представницьки те ж саме.
Та ж сама ідея, але менші проблеми.
>> Так що я насправді - дозвольте мені зберегти цей файл з іншого номер версії.
Ми назвемо цю версію 1 замість 0.
І я стверджую, що я можу реально перевизначити цю в такого роду
галюциногенний шляху.
>> Я збираюся залишити частину його в спокої.
Я збирався сказати, якщо т менше ніж або дорівнює 0 -
Я просто хочу бути трохи Ще Анальний цей раз
з моєю перевірки помилок -
Я збираюся йти вперед і повертає 0.
Це довільне.
Я просто Просто вирішити, якщо користувач дає мені негативним числом, я
повертаємо 0, і вони повинні були прочитати документації більш уважно.
>> Решта -
помітити, що я збираюся робити.
Останнє я збираюся повернутися м плюс -
що сигма-му?
Ну, сигма-м плюс мінус 1 м, м плюс мінус 2, плюс мінус 3 м.
Я не хочу писати все це.
Чому б мені просто не плоскодонки?
Рекурсивний називаю себе зі злегка менша проблема, крапку з комою
і назвіть його день?
>> Вірно?
Тепер і тут, ви можете відчути або турбуватися що це нескінченний цикл, який я
викликають, в результаті чого я реалізую Sigma Sigma по телефону.
Але це абсолютно нормально, тому що я думав, попереду якої додані лінії?
>> АУДИТОРІЯ: [нерозбірливо].
>> Девід мала: від 23 до 26, які Якщо мій стан.
Тому що приємно про віднімання тут, тому що я тримаю
вручати сигма менше проблем менше проблеми, менше - це не
в два рази менше.
Це всього лише крок дитини менше, але це нормально.
Тому що в кінцевому підсумку, ми будемо працювати наш шлях вниз до 1 або 0.
І як тільки ми вразили 0, Sigma НЕ збираюся називати себе більше.
Це збирається негайно повернути 0.
>> Таким чином, ефект, якщо ви роду Вітер цьому в своєму розумі, є додавання м плюс
м мінус 1, плюс мінус 2 м, м плюс мінус 3, а також точка, точка, точка, М мінус
м, в кінцевому підсумку дає вам 0, а ефект в кінцевому рахунку, щоб додати всі
ці речі разом.
Так що ми не маємо з рекурсією, вирішена проблема, яку ми
не могли вирішити раніше.
Дійсно, версія 0 про це, і кожен Проблема на сьогоднішній день, були вирішувані
тільки з використанням для петлі або в той час як петлі або аналогічних конструкцій.
>> Але рекурсію, я вважаю, дає нам інший спосіб мислення про
проблеми, згідно з яким, якщо ми можемо взяти Проблема, розділіть його від чогось
дещо більшим в щось кілька менше, я стверджую, що ми можемо дозволити його
можливо, трохи більш елегантно, з точки конструкції, з меншою кількістю коду,
і може бути, навіть вирішити проблеми, які буде складніше, так як ми в кінцевому рахунку
см., вирішуючи чисто итеративно.
>> Але захоплюючим, що я зробив хочете, щоб залишити нас було на це.
Дозвольте мені йти вперед і відкрити до файлу з -
Насправді, мене відпустили і зробити це дуже швидко.
Дозвольте мені піти далі і запропонувати наступному.
Серед код сьогоднішня цей файл тут.
Ось ця ось, noswap.
>> Так що це дурна маленька програма, яка Я нашвидкуруч, що стверджує, що робити
наступному.
В основному, це спочатку заявляє десяткового називаються X і привласнює його
значення 1.
Тоді він оголошує Цілочисельне Y та присвоює їй значення 2.
Потім він видає які х і у.
Тоді він каже, заміна, точка точка точка.
>> Потім він стверджує, що виклик функції називається своп, переходячи в X і
у, ідея якого в тому, що, ми сподіваємося, х і у повернеться
інший, протилежний.
Тоді стверджують помінялися місцями!
зі знаком оклику.
Тоді вона виводить х і у.
>> Але виявляється, що це дуже Проста демонстрація вниз
Тут насправді дитяча коляска.
Навіть якщо я оголошую тимчасовий змінної і тимчасово покласти в
його, то я перепризначення значення б -
яка відчуває себе розумно, тому, що я збережені копії при темп.
Тоді я б поновлення на рівну все, що було при темп.
Така оболонка гра переміщення в В і В у За допомогою цієї
середньої людини по імені Temp відчуває цілком розумно.
>> Але я стверджую, що коли я запускаю цю коду, як я зроблю зараз -
Дозвольте мені йти вперед і вставте його тут.
Я буду називати цю noswap.c.
І як випливає з назви, це не буде правильною програмою.
Не робіть noswap. / Ні підкачки.
X = 1, Y = 2, заміна, помінятися місцями.
х дорівнює 1, у дорівнює 2.
Це в корені неправильно, навіть хоча це здається абсолютно
розумним мені.
І є причини, але ми не збираємося виявити причину тільки поки.
>> Поки другий захоплюючим я хотів залишить у вас є те,
Оголошення види на знижкових купонів.
Наші інновації з кінця днів у цьому році спровокував нетривіальне кількість
питань, який був У наші наміри не.
Метою цих купонів, згідно з яким, якщо ви частина проблеми
встановити рано, таким чином отримуючи додатковий день, було дійсно, щоб допомогти вам, хлопці, допоможіть
самі починають рано, отсортируйте побічних стимулювання вас.
Допомагає нам розподілити навантаження між Години роботи краще, щоб
це свого роду безпрограшна.
>> На жаль, я думаю, що мої інструкції не було, на сьогоднішній день, дуже ясно, так що
Я повернувся в ці вихідні і оновлюється У специфікації більше, сміливіше текст
поясніть кулі, як ці.
І просто сказати, що це більш відкрито, шляхом Типово, набори проблеми обумовлені четвер
опівдні, в навчальну програму.
Якщо ви починаєте рано, завершальна частина питання, поставлене середу о 12:00
PM, частина, яка відноситься до купон код, ідея в тому, що ви можете розширити
Вашої термін P не встановлена ​​до п'ятниці.
Тобто, відкусила крихітний частина р. встановлено щодо того, що зазвичай є
серйозніша проблема, і ви купуєте собі додатковий день.
Знову ж, він отримує вас думати про Поставлена ​​задача, отримує вас до
Години роботи раніше.
Але проблема купон на знижку і раніше потрібно, навіть якщо ви нічого не пишіть.
>> Але ще більш переконливо це.
(Пошепки) А тих людей, залишаючи рано збираються пошкодуєте.
Як ті люди, на балконі.
Прошу вибачення заздалегідь, щоб люди на балкон з причин, які будуть
очистити через хвилину.
>> Так що нам пощастило мати один з CS50 колишній глава навчання стипендіатів
Компанія під назвою dropbox.com.
Вони дуже щедро пожертвував купон на знижку тут для цього багато місця,
який в порівнянні з звичайна 2 гігабайти.
Так що те, що я думав, що ми могли б зробити на цьому Останнє зауваження зробити трохи піддавки,
при цьому в якусь мить ми розкриємо переможець і хто має купон
кодів, які можна потім перейти до їх Веб-сайт, введіть його в, і вуаля, отримати
набагато більше простору Dropbox для вашого прилад і для ваших особистих файлів.
>> І перший, хто хотів би взяти участь на цьому малюнку?
Добре, тепер, що робить його ще більш захоплюючим.
Людина, яка отримує цю 25-гігабайтний код купона - який далеко
більш переконливими, ніж пізно днів в даний час, можливо -
це той, хто сидить на вершині подушка сидіння під якою мається
що код купона.
Тепер ви можете дивитися під ваша подушка сидіння.
>> [ВІДТВОРЕННЯ ВІДЕО]
>> -Раз, два, три.
>> [Крики]
>> -Ви отримуєте автомобіль!
Ви отримуєте автомобіль!
>> DAVID мала: Ми побачимо Ви в середу.
>> -Ви отримуєте автомобіль!
Ви отримуєте автомобіль!
>> DAVID мала: Балкон люди, приходьте тут на передній план,
де у нас є додаткові послуги.
>> -Кожен отримує автомобіль!
Кожен отримує автомобіль!
>> [КІНЕЦЬ відеовідтворення]
>> Оповідач: Наступного CS50 -
>> SPEAKER 5: О боже мій Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша Гоша -
>> [Ukelele ІГРИ]