Добра, так, вылічальная складанасць. Проста трохі папярэджанне Перш чым мы паглыбімся ў занадта 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 для вас, якія прымае масіў памеру 1000. Але тое, мабыць, на самай справе не выглядаюць у 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.