Добро, па, компјутерската комплексност. Само малку на предупредување Пред да се нурне во премногу far-- ова веројатно ќе биде меѓу најмногу математика-тешки работи ние зборуваме во CS50. Се надевам дека тоа нема да биде премногу големо и ќе се обидеме и да ви помогнеме во текот на процесот, но само малку на фер предупредување. Таму е малку на математика вклучени тука. Добро, па со цел да се направи употреба на нашите пресметковни ресурси во реалниот world-- тоа е навистина важно да се разбере алгоритми и како тој ги обработува. Ако имаме навистина ефикасен алгоритам, ние може да се намали износот на ресурси имаме на располагање да се справи со неа. Ако имаме алгоритам што се случува да се земе многу на работа да обработиме навистина голем сет на податоци, тоа е случува да бараат повеќе и повеќе ресурси, кои е пари, RAM меморија, сите тој вид на работи. 

Значи, да се биде во можност да се анализира една алгоритам користење на оваа алатка во собата, во основа, го прашува question-- како го прави ова алгоритам скала како што се фрли повеќе и повеќе податоци во неа? Во CS50, износот на податоци ние сме работат со е прилично мал. Општо земено, нашите програми се случува да се кандидира во една секунда или less-- веројатно многу помалку особено на почетокот. 

Но, мислам за една компанија која се занимава со стотици милиони клиенти. И тие треба да се процесира дека податоците за клиентите. Како и бројот на клиенти тие имаат добива поголеми и поголеми, тоа се случува да се бара се повеќе и повеќе ресурси. Колку повеќе ресурси? Па, тоа зависи од тоа колку ние анализираме алгоритам, со користење на алатки во овој алатникот. Кога зборуваме за комплексноста на една algorithm-- кои понекогаш ќе чуете дека се нарекува време комплексност или простор комплексност но ние сме само ќе за да го повикате complexity-- ние сме генерално зборувам за на најлошото сценарио. Со оглед на апсолутна најлош куп податоци што би можеле да се фрла во неа, како е ова се случува да алгоритам обработува или се занимаваат со тие податоци? Ние обично го нарекуваме најлош случај траење на алгоритам големи-О. Па еден алгоритам може да се рече да работи во O на n или O од n квадрат. И повеќе за тоа што тие значат во една секунда. 

Понекогаш, сепак, тоа го правиме за нега сценарио за најдобро сценарио. Ако податоците се се што сакавме тоа да биде и тоа беше апсолутно совршен и ни беше испраќање на оваа совршена поставени на податоци преку нашиот алгоритам. Како ќе се справи со неа во таква ситуација? Ние понекогаш се однесуваат на тоа како големи Омега, па за разлика од големите-О имаме големи Омега. Биг-Омега сценарио за најдобро сценарио. Биг-O за најлош случај. Општо земено, кога зборуваме за сложеноста на алгоритмот, ние зборуваме за најлошото сценарио. Па задржи дека во умот. 

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

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

Сега, може да се мери со algorithm-- особено, кога велам ние можеме мерење алгоритам, јас значи дека ние може да се измери колку многу ресурси потребни се. Дали тие ресурси се, колку бајти на RAM-- или мегабајти RAM меморија го користи. Или колку време е потребно за да се кандидира. И ние може да се јавите на оваа мерење, произволно, ѓ на n. Каде што n е бројот на елементи во група на податоци. И ѓ на n е колку somethings. Колку единици на ресурси не го бара тоа да се процесира податоците. 

Сега, ние всушност не ми е гајле за тоа што ѓ на n е точно. Всушност, ние многу ретко will-- сигурно никогаш нема во овој class-- јас нурне во било навистина длабоко анализа на она што ѓ на n е. Ние сме само ќе да се зборува за она што на F n е околу или она што се стреми да се. А трендот на алгоритам е диктиран од својата највисока цел мандат. И ние може да се види она што можам велам тоа со преземање Еден поглед на поконкретен пример. 

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

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

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

Сега, разликата помеѓу овие алгоритми почнуваат да стануваат малку помалку очигледни. Како и фактот дека постојат понизок ред terms-- или подобро, однос со пониски exponents-- почнуваат да стануваат ирелевантни. Ако еден сет на податоци е на големината 1000 и првиот алгоритам работи во една милијарда чекори. А вториот алгоритам работи во една милијарда и милиони чекори. А третиот алгоритам тече во само срамежливи од една милијарда чекори. Тоа е доста милијарда чекори. Тие термини од понизок ред да почне да стане навистина ирелевантни. И само навистина да чекан дома point-- ако внесување на податоци е на големината на million-- сите три од овие доста земе една quintillion-- ако мојата математика е correct-- чекори за обработка на внесување на податоци на големината на еден милион. Тоа е многу чекори. И фактот дека еден од нив може да земе неколку 100.000 или неколку 100 милиони уште помалку кога ние зборуваме за голем број big-- дека тоа е вид на ирелевантни. Сите тие имаат тенденција да се земе приближно n коцки, и така ние, всушност, ќе се однесуваат на сите овие алгоритми како да бидат од редот на n коцки или големи-О од n коцки. 

Еве листа на некои од повеќе заеднички компјутерската комплексност класи дека ќе се сретне во алгоритми, генерално. А исто така и конкретно во CS50. Овие се нарача од генерално најбрз на врвот, да се генерално најспоро на дното. Па постојано време алгоритми имаат тенденција да биде најбрз, без оглед на големината на внес на податоци да помине во. Тие секогаш се земе една операција или една единица на ресурси за да се справи со. Тоа би можело да биде 2, тоа би можело да биде 3, тоа би можело да биде 4. Но, тоа е постојан број. Тоа не се разликува. 

Логаритамски алгоритми време се малку подобро. И навистина добар пример за логаритамска алгоритам време сигурно сте виделе до сега е распарчување на именик да се најде Мајк Смит во книгата на телефонот. Ние се намали проблемот на половина. И така како n добива поголеми и поголеми и larger-- Всушност, секој пат кога ќе се удвои n, тоа трае само уште еден чекор. Така што е многу подобро отколку, да речеме, линеарното време. Што е, ако се зголеми двојно n, тоа го удвои бројот на чекори. Ако тројно n, што е потребно тројно зголемување на бројот на чекори. Еден чекор по единица. 

Тогаш работите се малку more-- малку помалку голем од таму. Имаш линеарни ритмичка време, понекогаш наречен најавите линеарно време или само n log n. И ние ќе пример на алгоритам што работи во n log n, што е уште подобро од квадратните time-- n квадрат. Или полином време, н две било кој број поголем од два. Или експоненцијална време, што е дури worse-- C до n. Па некои константен број се зголеми на моќта на големината на инпутот. Па ако има 1,000-- ако влезни податоци е со големина од 1.000, дека ќе бидат потребни C до 1000-та моќ. Тоа е многу полошо од полином време. 

Факториел времето е уште полоша. И всушност, навистина направи постојат бесконечен алгоритми време, како на пример, т.н. глупави sort-- чија работа е да се случајно се влага низа а потоа се провери да се види дали тоа се подредени. А ако тоа не е, по случаен избор shuffle на низа повторно и да се провери да се види дали тоа се подредени. И како што веројатно може да се imagine-- можете да се замисли ситуација каде што во најлош случај, со кој всушност никогаш не се започне со низа. Тој алгоритам ќе работи засекогаш. И така што ќе биде бесконечна алгоритам време. Се надевам дека нема да се пишува било факториел или бесконечно време алгоритми во CS50. 

Значи, ајде да потрае малку повеќе бетон погледнеме некои поедноставни пресметковни класи комплексност. Значи имаме example-- или два примери here-- на постојана алгоритми време, кој секогаш се една операција во најлош случај. Така, првиот example-- имаме функција наречен 4 за вас, кои го низа од големината 1.000. Но, тогаш, очигледно всушност не ја гледам во it-- не навистина се грижат што е во него, на таа низа. Секогаш се враќа само четири. Значи, тоа алгоритам, и покрај фактот дека тоа зема 1.000 елементи не направи ништо со нив. Само четири се враќа. Тоа е секогаш еден чекор. 

Всушност, додадете 2 nums-- која видовме пред како well-- само процеси два цели броја. Тоа не е еден чекор. Тоа е всушност неколку чекори. Ќе добиете, ќе добие б, ќе им додадете заедно, и излез на резултатите. Така, тоа е во 84 чекори. Но тоа е секогаш константна, без оглед на a или b. Што треба да се добие, да добијат б, се додаваат нив заедно, излезен резултат. Значи тоа е постојана алгоритам време. 

Еве еден пример на линеарно време algorithm-- алгоритам што gets-- кој трае еден дополнителен чекор, можеби, бидејки вашите расте за 1. Значи, да речеме дека ние сме во потрага по бројот 5 во внатрешноста на низа. Можеби сте во ситуација каде што можете да го најдете прилично рано. Но вие исто така може да има ситуација во која може да биде последен елемент од низата. Во низа на големина 5, ако ние сме во потрага за бројот 5. Тоа ќе бидат потребни 5 чекори. И всушност, замисли дека има 5 не било каде во оваа низа. Ние се уште се всушност треба да се погледне во секој елемент од низата со цел да се утврди дали или не 5 е таму. 

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

Неколку брзи прашања за вас. Што е runtime-- што е најлош случај траење на овој особено програмка на код? Па имам 4 јамка тука што тече од ѕ еднакво на 0, по целиот пат до м. И она што го гледам тука, е во тоа што органот на јамка работи во временска константа. Па со користење на терминологија, која Ние веќе разговаравме about-- што ќе биде најлош случај траење на овој алгоритам? Се земе втора. Внатрешниот дел од циклусот работи во временска константа. И на надворешниот дел на јамка ќе работи м пати. Значи, што е најлош случај траење тука? Ми го погоди голема-О на м? Ќе бидете во право. 

Како за уште еден? Овој пат имаме јамка внатрешноста на јамка. Имаме надворешниот циклус која се протега од нула до стр. А ние имаме внатрешниот циклус што тече од нула до p и внатре во тоа, Изјавувам дека на телото на јамка работи во временска константа. Значи, што е најлош случај траење на овој особено програмка на код? Па, повторно, имаме надворешниот циклус што тече стр пати. И секоја итерација time-- од тој циклус, наместо. Имаме внатрешниот циклус кој исто така води стр пати. А потоа внатре во тоа, тука е и постојана time-- малку програмка таму. 

Значи, ако имаме надворешниот циклус кои тече стр пати во внатрешноста на кој е внатрешниот циклус кој тече стр times-- она ​​што е најлош случај траење на овој код? Ми го погоди голема-О на стр квадрат? 

Јас сум Даг Лојд. Ова е CS50.