Гаразд, так, обчислювальна складність. Просто трохи попередження Перш ніж ми заглибимося в занадто far-- це, ймовірно, буде серед найбільш математики важких речей ми говоримо про в CS50. Сподіваюся, це не буде занадто переважною і ми постараємося і направляти вас в процесі, але просто трохи справедливе попередження. Там є трохи математики бере участь тут. Гаразд, так, щоб зробити Використання наших обчислювальних ресурсів в реальному world-- це дійсно Важливо розуміти алгоритми і як вони обробки даних. Якщо у нас є дійсно ефективний алгоритм, ми може звести до мінімуму кількість ресурсів ми маємо в розпорядженні, щоб впоратися з нею. Якщо у нас є алгоритм, який збирається зайняти багато роботи обробляти дійсно великий набір даних, то буде вимагати більш і більше ресурсів, які гроші, пам'ять, все в такому ж роді. 

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

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

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

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

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

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

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

Так що давайте говорити, що у нас є трьох різні алгоритми. Перший з яких займає п кубі, деякі підрозділи ресурсів для обробки набору даних розміру N. У нас є другий алгоритм, який приймає п кубі плюс п квадраті ресурси для обробки набору даних розміру N. І у нас є третій алгоритм, який працює in--, що займає п кубі мінус 8л квадрат плюс 20 п одиниць ресурсів для обробки алгоритм з встановленим розміром п даних. 

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

Якщо наш набір даних розмір 10, більше, але не обов'язково величезні, ми бачимо, що є насправді трохи різниці. Третій алгоритм стає більш ефективним. Це насправді про 40% - або 60% ефективніше. Вона займає 40%, то кількість часу. Це може run-- це може зайняти 400 одиниць ресурсів для обробки набору даних розміром 10. У той час як перший Алгоритм, навпаки, займає 1000 одиниць ресурсів для обробки набору даних розміром 10. Але подивіться, що відбувається, наші номери отримати ще більше. 

Тепер, різниця між цими алгоритмами почати, щоб стати трохи менш очевидно. І той факт, що є нижчого порядку terms-- або, скоріше, члени з більш низькою exponents-- почати, щоб стати не має значення. Якщо набір даних має розмір 1000 і перший алгоритм працює в мільярд кроків. І другий алгоритм працює в мільярд і мільйон кроків. І третій алгоритм працює в просто соромляться мільярда кроків. Це в значній мірі мільярда кроки. Ці терміни нижчого порядку почати щоб стати дійсно не має значення. І тільки по-справжньому молоток додому point-- Якщо вхідні дані розміру A million-- всі три з них у значній мірі взяти один quintillion-- якщо моя математика correct-- кроки для обробки введення даних розмір мільйона. Це багато кроків. І той факт, що один з них може взяти пару 100,000, або пару 100 млн, навіть менше, коли ми говоримо про ряд що big-- це начебто не має значення. Всі вони, як правило, приймають приблизно п кубі, і тому ми насправді відносяться на всі ці алгоритми як порядку п в кубі або великий-O н кубі. 

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

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

Тоді все стає трохи more-- трохи менше велика звідти. Ви повинні лінійний ритмічне час, іноді називається журнал лінійне час, або просто п п увійти. І ми будемо приклад алгоритму, який працює в н п журналу, який ще краще ніж квадратична time-- н квадраті. Або за поліноміальний час, п двох будь-яке число, більше двох. Або експонентний час, який навіть worse-- С к п. Таким чином, деякі постійне число піднятий до сила розміру вхідних даних. Так що якщо є 1,000-- якщо Вхідні дані розміру +1000, це займе C 1000-влади. Це набагато гірше, ніж поліноміальний час. 

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

Так, давайте ще трохи бетон погляд на деякі простіше обчислювальні класи складності. Тому у нас є example-- або два приклади here-- постійних алгоритмів час, який завжди беру одна операція в гіршому регістрі. Таким чином, перший example-- у нас є функція називається 4 для вас, які приймає масив розміру 1 000. Але то, мабуть, насправді не виглядають в it-- не хвилює те, що всередині нього, з цього масиву. Завжди просто повертає чотири. Так, що алгоритм, незважаючи на той факт, що займає 1000 елементів не зробити що-небудь з ними. Просто повертає чотири. Це завжди один крок. 

Насправді, додати 2 nums-- які ми бачили раніше, як well-- просто обробляє два цілих числа. Це не один крок. Це насправді пару кроків. Ви отримуєте, ви отримуєте б, ви додаєте їх разом, і ви виводите результати. Так що це 84 кроків. Але це завжди постійна, незалежно від А або В. Ви повинні отримати, отримати б, додати їх разом, виведення результату. Так що це постійна алгоритм разів. 

Ось приклад лінійний час algorithm-- алгоритм, який gets--, який приймає один додатковий крок, ймовірно, а ваш внесок росте на 1. Так, скажімо, ми шукаємо кількість 5 всередині масиву. Ви, можливо, ситуація, коли ви можете знайти його досить рано. Але ви могли б також ситуація, коли його може бути останнім елементом масиву. У масиві розміром 5, якщо ми шукаємо число 5. Це займе 5 кроків. І справді, уявіть собі, що є не де-небудь 5 в цьому масиві. Ми як і раніше насправді потрібно дивитися на кожен елемент масиву для того, щоб визначити або не існує 5. 

Таким чином, в гіршому випадку-, що, що елемент є останнім в масиві або не існує взагалі. Ми як і раніше повинні дивитися на всі п елементів. І так цей алгоритм працює в лінійному часу. Ви можете підтвердити, що, екстраполяції небагато, сказавши, якби ми мали масив 6-елементний і ми шукали номер 5, це може зайняти 6 кроків. Якщо у нас є масив 7-елемент і ми шукаємо число 5. Це може зайняти 7 кроків. Як додати ще один елемент до нашого Масив, вона займає ще один крок. Це лінійний алгоритм в гіршому випадку-. 

Пара простих запитань для вас. Що runtime--, що це в гіршому випадку виконання цього конкретного фрагмента коду? Так що в мене 4 петлі тут, який працює від J дорівнює 0, все, аж до м. І те, що я бачу тут, є те, що Тіло циклу виконується за константне час. Таким чином, використовуючи термінологію, що ми вже говорили about-- що буде найгірший виконання цього алгоритму? Візьміть другий. Внутрішня частина циклу працює в постійному часі. І зовнішньою частиною Цикл буде виконуватися, т разів. Так що в гіршому випадку виконання тут? Ви здогадалися великий-О м? Ви були б праві. 

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

Так що, якщо у нас є зовнішній контур, що працює р раз, всередині якого є внутрішній цикл, який працює стор times-- що в гіршому випадку виконання з цього фрагмента коду? Ви здогадалися велика-O р квадрат? 

Я Дуг Ллойд. Це CS50.