Добре, така, изчислителна сложност. Само малко на предупреждение преди да се потопите в твърде far-- Това най-вероятно ще бъде сред най-тежки неща математика говорим за в CS50. Надяваме се, че няма да бъде твърде преобладаващото и ние ще се опитаме да ви води чрез процеса, но малко на справедлив предупреждение. Там е малко по- на математиката, участващи тук. Добре, така че, за да се направи използване на нашите изчислителни ресурси в реалния world-- това е наистина важно да се разбере алгоритми и как те да обработва данни. Ако имаме наистина ефикасен алгоритъм, ние може да се намали количеството на ресурсите които са на разположение, за да се справят с него. Ако имаме алгоритъм, който ще отнеме много работа да обработи един наистина голям набор от данни, това е ще изисква по- и повече ресурси, които е пари, RAM, всички такива неща. 

Така че, е в състояние да анализира един алгоритъм използването на този инструмент набор, основно, моли question-- как този алгоритъм мащаб тъй като ние се хвърлят все повече и повече данни в него? В CS50, количеството данни, ние сме работа с е доста малка. Като цяло, нашите програми вървят да тичам в секунда или less-- вероятно много по-малко особено в началото на деня. 

Но мисля, че за една компания, която се занимава със стотици милиони потребители. И те трябва да се обработи този клиент данни. Тъй като броят на клиентите им Трябва стане по-голям и по-голям, това ще изисква все повече и повече ресурси. Колко повече ресурси? Е, това зависи от това как ние анализираме алгоритъм, използване на инструментите в този инструментариум. Когато говорим за сложността на един algorithm-- които Понякога ще чуете, че по-нататък време сложност или комплексност пространство но ние просто ще да се обадя complexity-- ние обикновено говорим за на най-лошия сценарий. Като се има предвид абсолютната лошия купчината данни, че бихме могли да се хвърлят в него, как е този алгоритъм ще обработват или се справят с тези данни? Ние обикновено наричаме най-лошия случай по време на работа на алгоритъм голям O. Така че един алгоритъм може да се каже, тичам в O от п или O на п квадрат. И повече за това, тези, означава в секунда. 

Понякога, обаче, ние правим грижи за в най-добрия случай. Ако данните са всичко, което искахме тя да бъде и това беше абсолютно перфектно и ние бяхме изпращане на тази перфектна набор от данни чрез нашия алгоритъм. Как ще се справи в тази ситуация? Ние понякога се позовават на нея като голям Omega, така че за разлика от големите O, ние имаме голям Omega. Big-Omega за в най-добрия случай. Big-O за най-лошия случай. Обикновено, когато говорим за сложността на алгоритъм, ние не говорим за най-лошия случай. Така че имайте това предвид. 

И в този клас, което обикновено се случва, ние да напусне взискателен анализ настрана. Има науки и области посветен на този вид неща. Когато говорим за разсъждения чрез алгоритми, което ние ще направим парче по парче за мнозина алгоритми говорим за в класа. Ние сме наистина само се говори за размишлявате през него със здравия разум, не с формули или доказателства, или нещо подобно. Така че не се притеснявайте, ние няма да се превръща в голям клас по математика. 

Така че аз казах ние се грижим за сложност защото той задава въпроса, как да ни алгоритми справят по-големи и по-големи масиви от данни се хвърлят към тях. Е, какво е набор данни? Какво имам предвид, когато казах, че? Това означава, каквото прави най-много разум в контекст, за да бъдем честни. Ако имаме алгоритъм, на Процеси Strings-- ние сме вероятно говорим за размера на низа. Ето данните set-- размера, броя на героите, които изграждат низа. Ако ние говорим за един алгоритъм, който обработва файлове, ние може да се говори за това как много килобайта съдържат този файл. И това е набор от данни. Ако ние говорим за един алгоритъм който обработва масиви по-общо, като алгоритми за сортиране или търсите алгоритми, ние сме най-вероятно става дума за броя на елементи, които съдържат масив. 

Сега, ние можем да се измери algorithm-- по-специално, когато казвам, ние можем измерване на алгоритъм, I означава да можем да се измери колко много ресурси, които то предприема нагоре. Дали тези ресурси са, колко байта RAM-- или мегабайта RAM тя използва. Или колко време е необходимо, за да работи. И ние можем да наречем това измерване, произволно, е на п. Където п е броят на елементи в масива от данни. И е на п е колко Нещо. Колко единици ресурс прави тя изисква да обработват тези данни. 

Сега, ние всъщност не ми пука за това, което е на п е точно. В действителност, ние много рядко will-- със сигурност никога няма в тази class-- I потопите в някоя наистина дълбоко анализ на това, което е на п е. Ние просто ще говорим за това, което е на п е приблизително или това, което има тенденция да. И тенденцията на алгоритъм е продиктувано от най-високото си мандат ред. И ние можем да видим това, което съм кажеш с това, като се вземат Един поглед към един по-конкретен пример. 

Така че нека да кажем, че имаме три различни алгоритми. Първият от който се п кубчета, някои единици ресурс да обработи набор данни от размера п. Ние имаме втори алгоритъм, който отнема п кубчета плюс п квадрат ресурси да обработи набор данни от размера п. И ние имаме една трета алгоритъм, който работи in-- че заема п кубчета минус 8п квадрат плюс 20 п единици ресурс да обработва алгоритъм с данните, определени от размера на п. 

Сега отново, ние наистина не се случва да влязат в това ниво на детайлност. Аз съм наистина просто трябва тези нагоре тук като илюстрация на точка че аз отивам да бъде вземане в секунда, което е, че ние само ми пука за склонността на нещата като масивите от данни стават по-големи. Така че, ако наборът данни е малък, има всъщност е доста голяма разлика в тези алгоритми. Третият алгоритъм има отнема 13 пъти по-дълго, 13 пъти размера на ресурсите, да тече по отношение на първия. 

Ако нашият набор от данни е размер 10, което е по-голям, но не е задължително огромен, можем да видим, че има всъщност е доста голяма разлика. Третият алгоритъм става по-ефективно. Става дума за реално 40% - или 60% по-ефективен. Това отнема 40% за период от време. Тя може да run-- може да отнеме 400 единици ресурс да обработва на набор от данни с размер 10. Като има предвид, първият алгоритъм, за разлика от това, взема 1000 единици ресурс да обработва на набор от данни с размер 10. Но вижте какво се случва, тъй като нашите номера стават още по-големи. 

Сега, разликата между тези алгоритми започнете да стане малко по-слабо забележими. А фактът, че има долния ред terms-- или по-скоро, условия с по-ниска exponents-- започнете да стане без значение. Ако един набор от данни е с размер 1000 и първата алгоритъм работи в един милиард стъпки. И вторият алгоритъм работи в един милиард и един милион стъпки. И третият алгоритъм работи само срамежлив от един милиард стъпки. Това е доста много милиард стъпки. Тези условия по-нисък ред започват да стане наистина неуместен. И само за наистина чук дома на point-- ако въведените данни е с размер на million-- всички три от тях до голяма степен вземете една quintillion-- ако ми по математика е correct-- стъпки за обработка на данни вход с размер на един милион. Това е много стъпки. А фактът, че един от тях може отнеме няколко 100,000, или двойка 100 още по-малко, когато милиона ние не говорим за редица че big-- това е вид без значение. Всички те са склонни да вземат приблизително п кубчета, и така ние всъщност ще сезира на всички тези алгоритми като по нареждане на п нарязан на кубчета или големи O на п кубчета. 

Ето списък на някои от по- общи изчислителни класове сложност че ние ще се сблъскате в алгоритми, като цяло. А също и по-специално в CS50. Те са поръчани от обикновено най-бързо в горната част, да обикновено най-бавния в долната част. Така постоянно време алгоритми са склонни да бъде най-бързият, независимо от размера на въвеждане на данни се преминава инча Те винаги да бъде в една операция или една единица от ресурси, за да се справят с. Тя може да бъде 2, тя може да да бъде 3, може да е 4. Но това е постоянно число. Той не се променя. 

Логаритмични алгоритми време са малко по-добро. И наистина добър пример за логаритмична алгоритъм време вие със сигурност сте виждали до сега е най- Разкъсва на телефонния указател да се намери Майк Смит в телефонния указател. Ние намаляване на проблема на половина. И така, като п получава по-голям и по-големи и larger-- Всъщност, всеки път, когато се удвои п, че отнема само още една стъпка. Така че това е много по-добре отколкото, да речем, на линейното време. Което е, ако се удвои п, тя отнема двойно броя на стъпките. Ако се утрои п, това отнема утрои броя на стъпките. Една стъпка на един дял. 

След това нещата стават малко MORE- малко по-малко велик от там. Имате линейно ритмично време, понякога наречена дневник линейното време или просто влезте п п. И ние ще пример на алгоритъм, който писти в п п дневник, който все още е по-добре от квадратното time-- п квадрат. Или полином време, п двама всяко число по-голямо от две. Или експоненциално време, което е дори worse-- C до п. Така че някои постоянен брой нараства на силата на размера на входа. Така че, ако има 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 е там. 

Така че в най-тежък случай, което е, че елементът е последен в масива или не съществува изобщо. Ние все още трябва да разгледаме Всички N елементи. И така, този алгоритъм работи в линейното време. Можете да потвърдите, че от екстраполиране малко с думите: ако имахме 6-масив и търсим номер 5, той може да отнеме 6 етапа. Ако имаме 7-масив и ние не търсим номер 5. Може да отнеме 7 стъпки. Като прибавим още един елемент в нашия масив, това отнема още една стъпка. Това е един линеен алгоритъм в най-лошия случай. 

Двойка следните въпроси към вас. Какво е това, което е runtime-- най-лошият време на работа на този конкретен фрагмент от кода? Така че аз имам 4 линия тук, която работи от к е равна на 0, по целия път до м. И това, което аз виждам тук, е, че тялото на цикъла се изпълнява в константно време. Така че, като се използва терминология, ние вече говорихме какво about-- ще бъде най-лошия случай по време на работа на този алгоритъм? Вземете една секунда. Вътрешната част на контура работи в постоянна време. И външната част на линия ще избяга м пъти. Така че това, което е най-лошият време на работа тук? Знаете ли, предполагам голям O на м? Вие искате да бъде прав. 

Какво ще кажете за още една? Този път ние имаме линия вътре в една линия. Имаме външен контур която тече от нула до р. И ние имаме вътрешна линия, която работи от нула до р, и в това, Заявявам, че тялото на линия минава в постоянна време. Така че това, което е най-лошият време на работа на този конкретен фрагмент от кода? Е, пак, имаме външен контур, която тече р пъти. И всеки time-- итерация на тази линия, по-скоро. Ние имаме една вътрешна линия че също работи стр пъти. И тогава вътре в това, там е най- постоянно time-- малко фрагмент там. 

Така че, ако имаме външен контур, че тече р пъти вътре от които е вътрешна линия, която тече р times-- това, което е най-лошият време на работа на този фрагмент от кода? Знаете ли, предполагам, че голяма-О р квадрат? 

Аз съм Дъг Лойд. Това е CS50.