У реду, тако, рачунарска комплексност. Само мало упозорење пре него што зароните превише фар-- ово ће вероватно бити међу највише матх-тешких ствари говоримо о у ЦС50. Надам се да неће бити превише неодољив а ми ћемо покушати и водити вас кроз процес, али само мало фер упозорење. Има мало од математике укључени овде. У реду, тако да би се коришћење наших ресурса рачунарске у стварном ворлд-- је стварно важно разумети алгоритме и како они обрађују податке. Ако имамо заиста ефикасан алгоритам, ми може да смањи количину ресурса имамо на располагању да се носи са тим. Ако имамо алгоритам који ће потребно много рада за обраду стварно велики скуп података, то је ће захтевати више и више средстава, која је новац, РАМ-а, сви такве ствари. 

Дакле, бити у стању да анализира алгоритам користећи овај сет алата, у суштини, пита куестион-- како се овај алгоритам скалу као што бацају све више и више података на њега? У ЦС50, количину података смо рад са је прилично мали. Генерално, наши програми иду да ради у други или лесс-- вероватно много мање посебно рано. 

Али размислите фирма која се бави са стотинама милиона купаца. И они треба да обради да купац података. Како се број купаца су Имам постаје све већа и већа, то ће захтевати све више и више ресурса. Колико још ресурси? Па, то зависи од тога како анализирамо алгоритам, користећи алате у овој кутији за алат. Када говоримо о сложености алгоритхм-- који Понекад ћете Чуо сам да се назива време Сложеност или простор комплексност али ми ћемо само звати цомплекити-- ми углавном говоримо о најгори сценарио. С обзиром на апсолутно најгори гомила подаци које смо могли да бацају на њега, како је овај алгоритам ће обрадити или се баве тим подацима? Ми углавном зову у најгорем случају Рунтиме алгоритма биг-О. Дакле, алгоритам може се рећи да изводити у Ø Н или О од н на квадрат. И више о томе шта оне значе у секунди. 

Понекад, међутим, ми стало о најбољем сценарију. Ако су подаци све смо хтели да буде и било је апсолутно савршен и ми слали ово савршено сет података путем нашег алгоритма. Како би се носити у тој ситуацији? Понекад се односе на то како велики омега, тако да је у супротности са великом-О, имамо велику-Омега. Биг омега за најбољем сценарију. Биг О за најгори могући сценарио. Генерално, када говоримо о сложеност алгоритма, говоримо о најгори сценарио. Дакле, имајте то на уму. 

И у овој класи, ми углавном идемо да оставимо по страни ригорозну анализу. Постоје науке и поља посвећен овим стварима. Када говоримо о резоновања кроз алгоритама, што ћемо урадити комад-по-комад за многе алгоритми говоримо о у класи. Ми заправо само говори о образложење кроз њу са здравим разумом, не са формулама, или доказа, или нешто слично. Зато не брини, нећемо бити претвара у велику цасу математике. 

Зато сам рекао да је стало сложености јер се поставља питање, како наши алгоритми носити већи и већи скупови података који се баца на њих. Па, шта је скуп података? Шта сам мислио када сам то рекао? То значи да било шта што највише смисла у контексту, да будем искрен. Ако имамо алгоритам, на Процеси Стрингс-- смо вероватно говоримо о величини низа. То су подаци договорен-- величина, број знакова који чине низ. Ако говоримо о једној алгоритам који обрађује фајлове, можемо да причамо о томе како многи килобајта чине тај фајл. И то је скуп података. Ако говоримо о алгоритму да рукује низова генерално, као што су алгоритама сортирања или тражи алгоритме, вероватно говоримо о броју елемената који чине низ. 

Сада можемо да измерите алгоритхм-- посебно, кад кажем да можемо мерење алгоритам, ја значи можемо да измеримо колико многи извори заузима. Да ли ти ресурси су, колико бајтова РАМ-- или мегабајта РАМ-а користи. Или колико времена је потребно за покретање. И можемо назвати мерење, произвољно ф н. Где је Н број елементи у скупу података. И Ф н је колико Сометхингс. Колико јединица ресурса ради је потребно за обраду тих података. 

Сада, ми заправо не занима шта Ф од н је тачно. У ствари, ми смо веома ретко вилл-- сигурно никада неће у овом цласс-- И зарони у било заиста дубоко анализа онога м од н. Ми ћемо да причамо о томе шта Ф од н отприлике или шта тежи да. А тенденција алгоритма је диктирао свом највишем реда мандата. И можемо да видимо шта мислили да је узимање Поглед на много конкретан пример. 

Рецимо да имамо три различита алгоритми. Први од који узима Н кубикована, неке јединице ресурса обрадити скуп података величине н. Имамо другу алгоритам који траје Н коцки Плус Н квадрат ресурси обрадити скуп података величине н. И ми имамо трећи алгоритам који ради у-- да заузима Н куб минус 8Н квадрат плус 20 Н јединице ресурса да обради алгоритам са подацима наведеним у величине н. 

Сада опет, стварно не иде да се у овом нивоу детаља. Ја стварно само ово горе овде као илустрацију тачке да ћу бити одлука у секунди, што је да ми је стало само о тенденцији ствари јер су скупови података постају већи. Дакле, ако је скуп података је мала, нема заправо прилично велика разлика у ових алгоритама. Трећи алгоритам тамо узима 13 пута дуже, 13 пута износ средстава покренути у односу на први један. 

Ако је наш сет података је величина 10, која је већа, али не нужно огромна, видимо да постоји заправо помало разлике. Трећи алгоритам постаје ефикаснији. Ради се о заправо 40% - или 60% ефикаснији. Потребно је 40%, количина времена. То може рун-- може да потраје 400 јединица ресурса обрадити скуп података величине 10. Док је прва алгоритам, с друге стране, узима 1.000 јединица ресурса обрадити скуп података величине 10. Али погледајте шта се дешава као наш број бити још већи. 

Сада, разлика између ових алгоритама почну да постане мало мање очигледна. И чињеница да постоје нижа реда термс-- односно, термини са нижим екпонентс-- почињу да постају небитне. Ако скуп података величине 1.000 и први алгоритам ради у милијарду корака. И други алгоритам ради у а милијарду и милион корака. И трећи алгоритам ради у само мање од милијарду корака. То је прилично милијарду корака. Ови термини нижег реда старт да постане заиста небитно. И само да стварно чекић кући поента ако је унос података је величине А миллион-- све три од њих прилично узме један куинтиллион-- ако моја математика је цоррецт-- корака да процесуира унос података величине милиона. То је много корака. И чињеница да је један од њих могао потрајати неколико 100.000, или пар 100 милиона чак и мање када говоримо о броју да биг-- некако је небитно. Сви они имају тенденцију да око Н Цубед, па ми заправо би се односио на све ове алгоритама као по налогу н коцки или велики О на н куб. 

Ево листе неких више заједничке рачунарске класе сложености да ћемо наићи у алгоритми, генерално. Такође конкретно у ЦС50. То су наручени од генерално најбржи на врху, да се генерално Најспорији на дну. Дакле, константа време алгоритми имају тенденцију да буде најбржи, без обзира од величине унос података прођете у. Увек узети једну операцију или једна јединица ресурса да се бави. То би могло бити 2, могло би бити 3, могло би бити 4. Али то је исти број. Не варира. 

Логаритхмиц време алгоритми су нешто боље. И стварно добар пример логаритамска време алгоритам ви сте сигурно видели до сада је цепање именика да пронађе Мике Смитх у телефонском именику. Цут смо проблем на пола. И тако добија већи н и већи и ларгер-- У ствари, сваки пут кад удвостручити н потребно је само још један корак. Дакле, то је много боље него, рецимо, линеарно време. Који је ако Доубле Н, она узима двоструко број корака. Ако троструко н је потребно утростручити броја корака. Један корак по јединици. 

Онда су се ствари се мало море-- мало мање сјајно одатле. Имате линеарно ритмички времена, понекад зове дневник линеарно време или само н лог н. А ми ћемо један пример алгоритма која Ради у н лог н, што је још боље од квадратна времена-- готово Н квадрат. Или полином време, два н било који број већи од два. Или експоненцијално време, које је чак ворсе-- Ц на Н. Дакле, нека исти број подигнута на моћ величине улаза. Дакле, ако постоји 1,000-- ако је унос података је величине 1000, било би потребно Ц до 1,000тх власт. То је много горе него полинома време. 

Факторијел време је још горе. И, у ствари, ту стварно постоји бескрајно време алгоритми, као што су, такозвана глупа сорт-- чија посао је да насумично схуффле низ а затим проверите да ли да ли је то решено. А ако није, случајно поново промешати низ и проверите да ли је то решено. И као што вероватно можете имагине-- можете да замислите ситуацију где је у најгорем случају, то ће никада није почети са низом. То алгоритам ће покренути заувек. И тако то би био бесконачно време алгоритам. Надам се да нећу писати било факторијални или бесконачно време алгоритми у ЦС50. 

Дакле, узмимо мало бетон поглед на неке једноставније рачунарска комплексност класе. Дакле, имамо екампле-- или два примера овде- сталних временских алгоритама, који увек узимају једна операција у најгорем слуцају. Дакле, први екампле-- имамо функцију позвао 4 за вас, који заузима низ величине 1.000. Али онда очигледно уствари не изгледају у то-- не стварно брига шта је унутар ње, те низа. Увек само враћа четири. Дакле, то алгоритам, упркос чињеници да је узима 1.000 елементе не ништа са њима. Само се враћа четири. Увек је један корак. 

У ствари, дода се 2 нумс-- која Видели смо раније као па-- Само обрађује два броја. То није један корак. То је заправо пар корака. Добијате добијате б, да их додате заједно, а ви излазних резултата. Тако да је 84 корака. Али увек је константна, без обзира на А или Б. Мораш да добијем, да б, додајте их заједно, излаз резултат. Дакле, то је константа време алгоритам. 

Ево пример линеарно време алгоритхм-- алгоритам који гетс-- који траје један додатни корак, евентуално, као ваш унос расте 1. Тако, рецимо тражимо број 5 унутар низа. Можда ћете морати ситуацији у којој можете да пронађу је прилично рано. Али такође може имати ситуација у којој је можда последњи елемент низа. У низу величине 5, ако тражимо број 5. Било би потребно 5 корака. И у ствари, замислите да постоји Не 5 нигде у овом низу. Ми још увек у ствари да погледам сваки елемент низа у циљу одређивања ли или не 5 постоји. 

Дакле, у најгорем случају,-а то је да елемент је последња у низу или не постоји уопште. Ми још увек морамо да погледамо све н елемената. И тако овај алгоритам ради у линеарном времену. Можете потврдити да је екстраполирањем мало говорећи, ако смо имали низ 6-елемент и ми смо у потрази за број 5, то би могло потрајати 6 корака. Ако имамо низ од 7-елемент и тражимо број 5. То може трајати 7 корака. Као што смо додати још један елемент на нашу Арраи, потребно је још један корак. То је линеарна алгоритам у најгорем слуцају. 

Пар брзих питања за вас. Шта је оно што је рунтиме-- у најгорем случају рунтиме овог посебног фрагмент кода? Дакле, ја имам 4 петљу овде који ради од Ј једнако 0, па све до м. И шта ја видим овдје, јесте да тело петље тече у сталном времену. Дакле, користећи терминологију која већ смо причали шта о-- био би у најгорем случају Рунтиме овог алгоритма? Узмите мало. Унутрашњи део петље ради у сталном време. И спољни део од петља ће се покренути м пута. Дакле, шта је овде у најгорем случају рунтиме? Да ли сте погодили велики Ø м? Био би у праву. 

Како другом? Овај пут имамо петље унутар петље. Ми имамо спољашње петљу који ради од нуле до п. И имамо унутрашње петље који ради од нуле до п, и унутар тога, Тврдим да је орган којем петља ради у сталном време. Дакле, шта је у најгорем случају рунтиме овог посебног фрагмент кода? Па, опет, имамо Спољни петља која води стр пута. И сваки времена-- готово итерација те петље, а. Имамо унутрашњу петљу који такође води стр пута. И онда унутар тога, ту је и константа времена-- готово мало Преглед тамо. 

Дакле, ако имамо спољашње петље да ради стр пута унутар којих је унутрашња петља која ради п тимес-- шта је у најгорем случају рунтиме овог фрагмент кода? Да ли сте погодили велики о од п квадрат? 

Ја сам Доуг Лојд. Ово је ЦС50.