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

ПРОФЕСОР: Все правильно. Це CS50, і це кінець тижні три. Так що ми тут сьогодні, а не в Сандерс Театр, натомість в Weidner бібліотеки. Усередині якого є студія відомий як Hauser Studio, або, скажімо, студія H, або повинні ми say-- якщо вам сподобалося, що жарт, це насправді від однокласник, Марк, онлайн, який запропонував стільки за допомогою Twitter. Тепер те, що це круто про будучи тут в студії є те, що я оточений ці зелені стіни, зелений екран або кольоровості, так сказати, що означає, що CS50-х Виробництво команда, без мого відома Прямо зараз, може бути покласти мене більше ніде в світі, на краще чи на гірше. 

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

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

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

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

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

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

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

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

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

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

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

Так от початковий список. Давайте ставитися до цього як Масив, як ми почали в тиждень два, який є безперервний блок пам'яті. У цьому випадку, що містить восьмій номери, спина до спини до спини. І нехай тепер застосуємо сортування злиттям. Так що я спочатку хочу, щоб відсортувати ліва половина цього списку, І давайте, отже, зосередитися на 4, 8, 6, і 2. 

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

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

Так що я тепер повинен розібратися ліву половина з цих двох елементів. Ліва половина, звичайно, знаходиться всього в 4. Так як мені відсортувати список одного елемента? Ну, що спеціальна база випадок нагорі, так би мовити, відноситься. 1 менше, ніж 2, і моя Список дійсно розміру 1. Так що я просто повернутися. Я нічого не робити. І справді, подивіться на те, що я зроблено, 4 вже відсортовані. Як Я вже частково успішними тут. 

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

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

Таким чином, ми, здається, робить успіхи, навіть хоча я не зробив ніякого фактичну роботу. Але пам'ятайте, де ми знаходимося в історії. Ми спочатку взяли вісім елементів. Ми відсортували ліву половину, яка 4. Тоді ми відсортували ліву половину в лівій половині, яка була 2. І тут ми йдемо. Ми зробили з цим кроком. 

Так що, якщо ми упорядковано ліва половина 2, тепер ми є для сортування праву половину 2. Таким чином, права половина 2 ці два значення тут, 6 і 2. Так тепер давайте вхід розміру 2, і сортувати ліву половину, а потім права половина, а потім об'єднати їх разом. Ну, як мені відсортувати список розмірів 1, який містить лише номер 6? Я вже зробив. Це список розмірі 1 сортується. 

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

Так що я отримав два списки розміру 2. Перший список містить 4 і 8. Другий список має 2 і 6. Давайте об'єднувати тих, разом в певному порядку. 2, звичайно, на першому місці, потім 4, потім 6, потім 8. І тепер ми, здається, стають де цікаво. Тепер я упорядковано половина список, і за збігом, це всі парні числа, а що це, дійсно, просто збіг. І я тепер упорядковано вліво половина, так що це 2, 4, 6 і 8. Нічого не в порядку. Це відчуває, як прогрес. 

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

Так що давайте йти вперед, а зосередитися на права половина, яку ми тут. Ліва половина того, що Права половина, і в даний час ліва половина зліва половина цього правій половині, і як мені відсортувати список розмірів 1, який містить лише номер 1? Це вже зроблено. Як зробити те ж саме для списку розмір 1, що містить всього 7? Це вже зроблено. Крок трьох для половини, то є об'єднати ці два елементи в новий список розмірів 2, 1 і 7. Є, здається, не зробили все що багато чого цікава робота. Давайте подивимося, що станеться далі. Я просто упорядковано ліву половину з Права половина моєї початкової вхід. Тепер давайте розберемося право половина, яка містить 5 і 3. Давайте раз поглянути на лівій половина, сортується, права половина, сортувати, і об'єднати ці два разом, в якійсь додатковий простір, 3 приходить першим, а потім приходить 5. І ось тепер, ми відсортовані ліва половина правій половині вихідної задачі і права половина правій половині вихідної задачі. Що третій і останній крок? Ну, щоб об'єднати ці дві половинки разом. Отже, дозвольте мені отримати собі деякі додатковий простір, але, знову ж, я може бути за допомогою цього вільний простір нагорі. Але ми збираємося, щоб тримати це просто візуально. Дозвольте мені тепер зливаються в 1, і Потім 3, а потім 5, потім 7. Таким чином, залишивши мене тепер з Права половина вихідної задачі Це абсолютно відсортовані. 

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

Так шляхом злиття, те, що мені потрібно робити? Я хочу, щоб взяти елементи в порядку. Так, дивлячись на лівій половині, Я бачу, що перше число 2. Я дивлюся на правій половині, Я бачу перший номер 1, так що, очевидно, яка Кількість я хочу вирвати, і поставити першим у моєму остаточний список? Звичайно, 1. Тепер я хочу запитати, що ж питання. На лівій половині, у мене ще є номер 2. На правій половині, Я отримав номер 3. Якою я хочу, щоб вибрати? Звичайно, число 2 і Тепер зверніть увагу на кандидатів є 4 ліворуч, 3 праворуч. Давайте, звичайно, вибрати 3. Тепер кандидати на 4 ліва, 5 праворуч. Ми, звичайно, вибрати 4. 6 зліва, 5 праворуч. Ми, звичайно, вибрати 5. 6 ліворуч, 7 праворуч. Ми вибираємо 6, а потім ми вибрати 7, а потім ми вибираємо 8. Вуаля. 

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

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

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

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

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

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

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

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

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

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

Тепер давайте ще один прохід При цьому з дещо більш формальний перспективі, тільки в випадок, цей відгук краще ніж цього вищого рівня обговорення. Так от алгоритм знову. Давайте запитаємо себе, те, що час роботи є це алгоритми різні кроки? Давайте розділимо його на перше Корпус і другий випадок. ПЧ і ще в тому випадку, якщо, Якщо N менше, ніж 2, тільки повертатися. За відчуттями постійної часу. Це, свого роду, як два етапи, Якщо N менше, ніж 2, а потім повернутися. Але, як ми сказали, в понеділок, постійна часу, або Big O 1, може бути два, три кроки кроки, навіть 1000 кроків. Важливо те, що це постійне число кроків. Таким чином, жовтий виділений псевдокод тут працює в, ми будемо називати його, постійна часу. Так більш формально, і ми збираємося, метою яких це буде ступінь, в якій ми оформити це право now-- Т п, час роботи завдання який приймає п щось в якості вхідних, дорівнює Big O з одного, Якщо N менше, ніж 2. Так що це обумовлено, що. Таким чином, щоб бути ясним, якщо п менше 2, у нас є дуже короткий список, то час працює, Т п, де п 1 або 0, в цьому дуже конкретному випадку, це просто буде постійна часу. Це займе один крок, два кроки, що завгодно. Це фіксоване число кроків. 

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

Так дійсно formulaically, ми можемо висловити це, хоча трохи лякаюче спочатку погляд, але це щось що захоплює саме цю логіку. Час роботи, Т п, якщо п більше або дорівнює 2. У цьому випадку, у разі ELSE, Т п ділиться на 2, плюс Т N ділиться на 2, плюс Big O п, деякі лінійний ряд кроків, можливо рівно п, може бути, в 2 рази п, але це приблизно, порядок п. Так що, теж, як ми можемо виразити це formulaically. Тепер ви не знали б, це, якщо ви записали його в своєму розумі, або подивитися його в назад підручника, що може мати трохи шпаргалку зрештою, але це, дійсно, збирається дати нам Big O н журналу п бо рецидив Ви бачите тут, на екрані, якщо ви насправді це, з нескінченне число прикладів, або ви зробили це formulaically, ви б бачити, що це, тому що цій формулі саме по собі є рекурсивним, з т п над чимось праворуч, і т п над ліворуч, це може фактично бути виражена, в підсумку, як великий йдуть н журналу п. Якщо не переконаний, що це добре зараз, просто прийняти на віру, що це, справді, що це рецидив призводить до, але це всього лише трохи більше Математичний підхід до пошуку на часі роботи сортування злиттям на підставі його псевдокоду у спокої. 

Тепер давайте трохи перепочинок від усього цього, і прийняти поглянемо на упевнений колишній сенатор, який може виглядати трохи знайомі, хто сів з Еріком від Google Шмідт, деякий час назад, для інтерв'ю на сцені, перед цілим букетом з людей, в кінцевому рахунку, про говорити тема, це досить вже знайомі. Давайте поглянемо. 

Ерік Шмідт: Тепер сенатор, Ви тут Google, і я хотів би думати про Головування у співбесіді. Тепер це важко отримати роботу в якості президента. ПРЕЗИДЕНТ ОБАМА: Добре. Ерік Шмідт: І ти збирається робити [нерозбірливо] в даний час. Це також важко отримати роботу в Google. ПРЕЗИДЕНТ ОБАМА: Добре. 

Ерік Шмідт: У нас є питання, і ми просимо наших кандидатів питання, і це одне з Ларрі Швіммер. 

ПРЕЗИДЕНТ ОБАМА: Добре. 

Ерік Шмідт: Що? Ви, хлопці, думаєте, що я жартую? Це прямо тут. Що є найбільш ефективним способом сортувати мільйон 32 бітні цілі? 

ПРЕЗИДЕНТ ОБАМА: Well-- Ерік Шмідт: Іноді, може бути, мені шкода, maybe-- ПРЕЗИДЕНТ ОБАМА: Ні, ні, ні, ні, ні, я think-- Ерік Шмідт: Це не it-- ПРЕЗИДЕНТ ОБАМА: Я думаю, я думаю, що міхур Сортувати б неправильний шлях. Ерік Шмідт: Ну. Хто сказав йому це? ДОБРЕ. Я не зробив інформатика on-- 

ПРЕЗИДЕНТ ОБАМА: Ми вже отримали наші шпигуни там. ПРОФЕСОР: Все правильно. Давайте залишимо позаду нас тепер Теоретична світ алгоритмів в асимптотичного аналізу їх, і повернутися до деяких темах від тижня нулем і одиницею, і почала видалити деякі навчальні колеса, якщо ви будете. Так що ви дійсно розумієте, в кінцевому рахунку, від початку до кінця, що відбувається під капотом, коли ви писати, компілювати і виконувати програми. Нагадаємо, зокрема, що це було перша програма З ми дивилися на, канонічний, проста програма роду, умовно кажучи, де вона друкує, Hello World. І згадую, що я сказав, то процес що вихідний код проходить через є саме це. Ви берете вихідний код, пройти це через компілятор, як Clang, і прибуває об'єктний код, що може виглядати як це, нулів і одиниць що процесор комп'ютера, центральне Блок обробки або головного мозку, в кінцевому рахунку, розуміє. 

Виявляється, що це трохи спрощенням, що ми тепер в Положення дражнити один від одного щоб зрозуміти, що дійсно був відбувається під капотом кожен раз, коли ви запустите Брязкіт, або в більш загальному, кожен раз, коли ви робите програму, за допомогою Марка і CF 50 IDE. Зокрема, такі речі, як Це перший генерується, коли ви вперше скомпілювати програму. Іншими словами, коли ви прийняти ваш вихідний код і скомпілювати його, то, що перший час виведений Clang щось відомий як асемблері. І справді, це виглядає саме так. 

Я побіг команди на командного рядка раніше. Брязкіт Dash великої літери hello.c, і це створило файл для мене, званих hello.s, всередині якого були точно це зміст, і трохи більше вище, і трохи більше нижче, але я поставив соковиті Інформація тут на екрані. І якщо ви уважно подивитеся, ви побачите, принаймні, кілька знайомих ключові слова. У нас є головний у верхній. Ми PRINTF посередині. І ми також маємо привіт світ Обернена коса риска н в лапки вниз нижче. 

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

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

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

Деякий час назад, хтось, або комусь, також написав файл називається стандартним io.c, в які фактичні визначення, або реалізації Printf, і грона інших функцій, насправді написано. Тому, враховуючи, що, якщо ми вважаємо, маючи тут, на лівому, hello.c, що, коли складений, дає нам hello.s, навіть якщо Clang не турбує збереження в місці ми можемо побачити його, і що збірка код отримує зібрані в hello.o, який це, дійсно, ім'я за замовчуванням враховуючи при компіляції джерело код в об'єктний код, але не цілком готові виконати його ще, бо ще один крок має статися, і має що відбувалося протягом останніх кількох тижні, можливо, без відома до вас. 

Зокрема десь в CS50 IDE, а це, теж буде чимось на зразок спрощення на мить, є, або був на той час, файл називається стандартним io.c, що хтось зібрані в Стандартні io.s або еквівалент, що хтось потім зібрані в стандартній io.o, або виявляється в трохи інший файл Формат, який може мати різні розширення файлу в цілому, але в теорії і концептуально, точно ці кроки були відбутися в якійсь формі. Що й казати, що в даний час коли я пишу програму, hello.c, що просто говорить, привіт світ, і я за допомогою коду чужий як Printf, який був давним Час, у файлі під назвою стандарт io.c, потім якось я повинен прийняти мої об'єктного коду, мої нулі і одиниці, і об'єкт цієї людини код, або нулі і одиниці, і якось зв'язати їх разом в один останній файл, називається привіт, що має всі нулі і ті з моєю головною функції, і всі нулі і ті, для Printf. 

І справді, що минулого процес називається, пов'язуючи свій об'єктний код. Вихід якого являє собою виконуваний файл. Таким чином, в справедливості, на Кінець дня, нічого не змінилося з одного тижня, коли ми вперше почав компіляції програми. Дійсно, все це вже було відбувається під капотом, але тепер ми в змозі де ми можемо насправді дражнити один від одного ці різні кроки. І справді, в кінці в день, ми як і раніше залишилося нулів і одиниць, які насправді велика переходити в даний час іншому можливістю C, що у нас не було, щоб використовувати, швидше за все, на сьогоднішній день, відомий як побітові оператори. Іншими словами, до цих пір, ми в будь-який час справу з даними в C або змінних в C, у нас було щось подібне символи і поплавці і модулі і жадає і двомісних і т.п., але всі ті, принаймні вісім біт. Ми ніколи ще не був у стані маніпулювати окремих бітів, навіть якщо окремий біт, ми Знаєте, може представляти 0 і 1. Тепер з'ясовується, що в C, ви може отримати доступ до окремих бітам, якщо ви знаєте синтаксис, з якою, щоб дістатися до них. 

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

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

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

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

На відміну від AND Оператор, амперсанд, тільки якщо у мене є два 1-х років в Рівняння, я насправді вийти на 1. Тепер є кілька інших оператори, а також. Одним з них є трохи складніше. Отже, дозвольте мені йти вперед і стерти це, щоб звільнити простір. І давайте поглянемо на вставки символів, на мить. Як правило, це характер можна ввести На клавіатурі Утримання SHIFT і то одне з чисел на вершині вашого США клавіатура. 

Таким чином, це є ексклюзивним Оператор АБО, виключає АБО. Таким чином, ми тільки що бачили оператор або. Це виняткове АБО оператор. Що насправді різниця? Ну давайте подивимося на формулу, і використовувати це в якості інгредієнтів в кінцевому рахунку. 0 XOR 0. Я хочу сказати, завжди 0. Це визначення XOR. 0 XOR 1 буде 1. 1 XOR 0 буде 1, і 1 XOR 1 буде? Неправильно? Або не так? Не знаю. 0. Тепер те, що тут відбувається? Ну думаю про найменування цього оператора. Виключає АБО, оскільки ім'я, вид, пропонує, відповідь тільки буде 1, якщо входи ексклюзивні, виключно відрізняється. Так от входи є те ж саме, тому вихід дорівнює 0. Ось входи є те ж саме, тому вихід дорівнює 0. Ось виходи різні, вони є винятковими, і тому вихід 1. Так що це дуже схоже на І, це дуже схоже, або, скоріше, це дуже схоже на АБО, але тільки в ексклюзивному чином. Чи не Це один більше не 1, тому що у нас є два 1-х, і не виключно, тільки один з них. Добре. Що можна сказати про інших? Ну тильди, тим часом, насправді просто і красиво, на щастя. І це унарний Оператор, який означає він застосовується тільки до одного входу, один операнд, так сказати. Чи не лівої і правої. Іншими словами, якщо ви берете тильди з 0, відповідь буде навпаки. А якщо взяти тильди з 1, Відповідь буде навпаки. Таким чином, оператор тильда спосіб заперечення небагато, чи гортати трохи від Від 0 до 1 або від 1 до 0. 

І, нарешті, залишає нас тільки з двома операторами кінцевих, так званий зсув вліво, і так званий оператор зсуву вправо. Давайте поглянемо на те, як ці роботи. Лівий оператор зсуву, написана з двома кутовими дужками, як, що, працює таким чином. Якщо мій вклад, або мій операнд, ліворуч Оператор зсуву досить просто 1. І я тоді скажу комп'ютер в зсув вліво, що 1, кажуть сім місць, результат, як якщо б я прийняти, що 1 і перемістити його сім місць у більш лівий, і за замовчуванням, ми будемо вважати, що простір праворуч збирається бути нулями. Іншими словами, 1 зрушення вліво 7 буде щоб дати мені, що 1, потім 1, 2, 3, 4, 5, 6, 7 нулів. Таким чином, в певному сенсі, це дозволяє взяти невелику кількість, як 1, і чітко зробити це набагато набагато більше, таким чином але насправді ми побачимо більш розумні підходи до нього замість цього, а також, 

Добре. Ось це для трьох тижні. Ми побачимо вас наступного разу. Це було CS50. 

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

СПІКЕР 1: Він був на закуску бар їсть гарячу вигадки морозиво. Він був все це на його обличчі. Він одягнений, що шоколад, як бородою СПІКЕР 2: Що ви робите? СПІКЕР 3: Хм? Що? 

СПІКЕР 2: Ти тільки подвійне падіння? Ви двічі опустив чіп. СПІКЕР 3: Вибачте. СПІКЕР 2: Ви змоченою чіп, ви відкусив, і ви знову занурюють. СПІКЕР 3: СПІКЕР 2: Так от, як покласти вся ваша рот прямо в провал. Наступного разу ви берете чіп, просто занурити його один раз, і кінець. 

СПІКЕР 3: Ви знаєте, що, Ден? Ви опустите шлях, який ви хочете зануритися. Я опустіть так, що я хочу, щоб зануритися.