Ладно, так, вычислительная сложность. Просто немного предупреждение Прежде чем мы углубимся в слишком 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.