Сложность и нотация Big O: The Ultimate Guide

“Почти в каждом вычислении возможны различные варианты организации процесса. Важно выбрать тот вариант, который минимизирует время, необходимое для вычисления”.

0) Введение

Представьте, что мы пишем очень простую программу для сортировки списка элементов. Мы заканчиваем писать наше приложение на любом языке программирования, с которым нам удобнее всего работать, и выполняем его на случайно сгенерированном списке из N чисел, считая время, необходимое для его выполнения, и получая результат 100 мс.

Мы пробуем на разных списках размера N и получаем средний результат, аналогичный первому: 100 мс. Теперь мы удваиваем размер нашего списка до 2N и делаем то же самое. Однако, когда мы получаем результат, он занимает в среднем не 200 мс (вдвое больше предыдущего), а больше, в среднем 250 мс. Более того, мы снова удваиваем количество элементов до 4N, и время не удваивается по сравнению с предыдущим, что составило бы 500 мс, а скорее 600 мс.

Что же здесь происходит?

Чтобы понять это, нам нужно знать, что такое вычислительная сложность, и взглянуть на связанную с ней нотацию Big O. В этой заметке мы четко объясним эти понятия, рассмотрим некоторые примеры вычислительной сложности и нотации Big O, а также получим некоторое представление о том, почему важно учитывать сложность наших алгоритмов при кодировании.

В заключение мы также упомянем, почему вычислительная сложность актуальна в мире машинного обучения и больших данных.

TLDR:

1. Что такое вычислительная сложность?
2. Объяснение нотации Big O
3. Избегайте экспоненциалов
4. Вычислительная сложность в машинном обучении
5. Заключение и дополнительные ресурсы

1) Что такое вычислительная сложность?

Когда мы пишем программу для выполнения определенной задачи, логика, лежащая в основе нашего программирования (структура и поток кода, функции, которые мы используем, и т.д.), заставляет наш код выполнять определенное количество операций.

Эти операции, в свою очередь, занимают определенное время, поэтому, как правило, чем больше операций выполняет наша программа, тем больше времени ей потребуется на выполнение.

Вычислительная сложность, в одной из своих форм, относится к взаимосвязи между увеличением времени, которое требуется алгоритму или программе для выполнения, и увеличением размера входных данных алгоритма или программы. Примером такой зависимости является как раз то, что мы видели в примере, проиллюстрированном в начале этой заметки.

Этот вид сложности известен как временная сложность, и мы рассчитываем ее, учитывая время, необходимое для выполнения наших алгоритмов, в зависимости от размера входных данных. Важно подчеркнуть это, потому что пространственная сложность или сложность памяти (которая представляет собой объем физического пространства или памяти, занимаемый алгоритмами в памяти компьютера, еще одно возможное узкое место) также существует, но в этой статье мы будем говорить о вычислительной сложности в терминах времени.

Размер входных данных, однако, не единственная характеристика наших данных, которая может повлиять на операции и, следовательно, на время работы алгоритма: сами данные тоже имеют значение. Представьте себе алгоритм сортировки, о котором мы говорили во введении. Если данные, которые мы ему подаем, уже отсортированы, то на выполнение алгоритма уйдет меньше времени, чем если бы данные были расположены в совершенно случайном порядке.

Поэтому, говоря о временной сложности, мы можем иметь три разных точки зрения:

• Наилучший сценарий: когда информация во входном объеме делает так, что алгоритму требуется минимальное количество шагов для выполнения и достижения своих целей.
• Средний сценарий: относится к среднему количеству операций, необходимых для ввода данных данного размера.
• Наихудший сценарий : относится к максимальному количеству операций, необходимых для выполнения задачи при заданном размере входных данных.

Наихудший сценарий – это, как правило, тот, который мы должны рассматривать и пытаться улучшить, поскольку в этом случае существует установленный порог, который можно использовать в качестве эталона.

Давайте рассмотрим пару примеров сложности алгоритмов сортировки, чтобы все стало более понятно. Сначала мы оценим сложность алгоритма сортировки Selection Sort, увидев, как по мере увеличения размера входных данных время, необходимое для его выполнения, увеличивается нелинейно.

Код для сортировки массива с помощью этого алгоритма выглядит следующим образом:

В нем мы видим, что сортировка с выбором использует два цикла: внешний цикл для прохождения по каждому элементу массива и внутренний цикл для прохождения по элементам массива, которые находятся впереди элемента из внешнего цикла.

Этот внешний цикл выполняется n-1 раз и делает две операции за проход, одно присваивание ( min_index = i) и одну подстановку (array[i], array[min_index] = array[min_index], array[i]), в результате чего получается 2n-2 операции.

Внутренний цикл выполняется n-1 раз, затем n-2, затем n-3 и так далее. Солнце всех этих прогонов можно выразить в виде следующей серии:

Формула для прогонов внутреннего цикла алгоритма сортировки выбором

In the worst case (the scenario which we have to consider which we saw before) the if condition is always met, so this inner loop executes 2 operations, a comparison ( if array[min_index] > array[j] ) и присваивание ( min_index = j ), что дает в сумме n²- n операций.

Всего, с учетом внутреннего и внешнего цикла, алгоритм затрачивает 2n-2 операции для внешнего цикла плюс n²- n для внутреннего цикла, в результате чего общее количество операций и, соответственно, временная сложность T(n) = n²+ n-2.

Видя эту формулу, давайте оценим, что произойдет, если мы перейдем от 100 элементов в списке к 200.

T(100) = 10000+ 10 0-2 = 10098

T(200) = 40000+ 20 0-2 = 40198

T(200)/T(100) = 40198/10098 = 3.98

Отсортировать 200 предметов в 3,98 раза больше, чем отсортировать 100 предметов! Также, видите, что это число очень близко к 4? По мере увеличения размера входных данных, которые мы сравниваем, это число становится все ближе и ближе к 4. Это означает, что сортировка 2 миллионов элементов займет в 4 раза больше времени, чем сортировка 1 миллиона элементов.

Давайте проверим это в коде. Следующий сценарий использует ранее показанную функцию selection_sort_func для сортировки элементов двух случайно созданных целочисленных массивов, один размером 1000, другой – 1000.

В большинстве случаев вместо того, чтобы рассматривать все уравнение сложности (T(n) = n²+ n-2), мы сохраняем член высшего порядка, так как он обычно доминирует над остальными, особенно по мере роста размера входных данных n.

Учитывая всю эту предыдущую информацию, мы можем сказать, что вычислительная сложность (по времени) алгоритма Selection Sort составляет T(n) = n².

На следующем рисунке показано сравнение роста сложности различных типов при увеличении размера входных данных.

В легенде есть небольшой спойлер о нотации Big O, но просто останьтесь со мной на секунду и подумайте пока о T(1), T(log(n)) и так далее.

Мы можем увидеть здесь некоторые интересные вещи:

T(1) означает, что вычислительная сложность постоянна: она не зависит от размера входных данных. Если вы посмотрите на наиболее распространенные операции в Python и их временную сложность (здесь), вы увидите, что такие операции, как добавление элемента в конец списка, имеют подобную сложность.

Для больших размеров входных данных, вплоть до линейного T(n), время увеличивается контролируемым образом.

Для линейных и выше (все линии слева от зеленой диагонали) временная сложность резко возрастает по мере увеличения размера входных данных.

• Кубическая и квадратичная сложность кажутся невероятно высокими, но есть и другие злые сложности, которые мы рассмотрим в следующих разделах, которые намного, намного хуже: экспоненциальная и факториальная.
• Другие алгоритмы сортировки, такие как знаменитая пузырьковая сортировка, имеют такую же временную сложность, как и сортировка выбором, что приводит к аналогичному увеличению времени выполнения при увеличении размера выборки. Код для пузырьковой сортировки можно найти здесь:
• Если мы выполним оба алгоритма сортировки на одинаковых массивах размером 1000 и 2000, мы получим следующие результаты, которые очень похожи, с немного лучшей производительностью для сортировки выбора.
• Selection Sort Для входа размером 1000 алгоритму потребовалось 0,130644 мс Для входа размером 2000 алгоритму потребовалось 0,517642 мс Bubble Sort Для входа размером 1000 алгоритму потребовалось 0,136633 мс Для входа размером 2000 алгоритму потребовалось 0,551555 мс.

Наконец, давайте рассмотрим Quicksort, прежде чем мы перейдем к объяснению того, что такое нотация Big O, чтобы вы могли увидеть, как другая и лучшая временная сложность может оказать огромное влияние на производительность наших алгоритмов.

Quicksort – это рекурсивный алгоритм сортировки, который имеет вычислительную сложность в среднем T(n) = nlog(n), поэтому для малых размеров входных данных он должен давать схожие или даже немного худшие результаты, чем Selection Sort или Bubble Sort, но для больших входных данных разница должна быть очень заметной.

Код алгоритма Quicksort выглядит следующим образом: как вы видите, нам нужно реализовать вспомогательную функцию для разбиения массива. Вы можете узнать все о Quicksort здесь.

Посмотрим, какие результаты мы получим для массивов с размером входных данных 1000 и 2000, как и раньше:

Selection Sort Для массива размером 1000 алгоритму потребовалось 0.1226947 мс Для массива размером 2000 алгоритму потребовалось 0.4907164 мс Bubble Sort Для массива размером 1000 алгоритму потребовалось 0.1326408 мс Для массива размером 2000 алгоритму потребовалось 0.5295898 мс Быстрая сортировка Для массива размером 1000 алгоритму потребовалось 0.0169501 мс Для массива размером 2000 алгоритму потребовалось 0.0388991 мс.

Мы видим, что для размера 1000 она немного хуже, чем две другие, но для вдвое большего размера, 2000, она имеет лучшую производительность, что делает очевидным, что она лучше масштабируется с размером, чем Bubble Sort и Selection Sort. Эта разница становится еще более заметной, если мы еще больше увеличиваем размер входных данных. Давайте посмотрим!

Посмотрите, что происходит, когда мы используем 5000 и 10000 в качестве входных размеров наших массивов:

Selection Sort Для входа размером 5000 алгоритму потребовалось 3,0628 мс Для входа размером 10000 алгоритму потребовалось 12,8446 мс Для выполнения Bubble Sort Для входа размером 5000 алгоритму потребовалось 3,4507 мс Для входа размером 10000 алгоритму потребовалось 13,9834 мс Для выполнения Quick Sort Для входа размером 5000 алгоритму потребовалось 0,16954 мс Для входа размером 10000 алгоритму потребовалось 0,42389 мс.

Удивительная разница, правда? В таких задачах, где размер определенно имеет значение, выбор правильных алгоритмов очень важен.

Надеюсь, эти примеры наглядно продемонстрировали, почему важно учитывать сложность алгоритмов при создании реальных приложений, использующих значительные объемы данных.

В следующем разделе мы объясним, как все это связано с нотацией Big O, что такое сложность Big O и как все это складывается в удивительную аналитическую структуру, о которой нужно думать при разработке программного обеспечения.

2) Объяснение нотации Big O

Как мы видели в предыдущем разделе, одним из наиболее важных вопросов, которые мы должны рассмотреть при оценке конкретного алгоритма для приложения, является его масштабирование или рост: как на его производительность влияет изменение размера входных данных.

Эта концепция роста – то, что количественно описывает нотация Big O. Это нотация, которая определяет наиболее доминирующий член во временной сложности алгоритма (временная сложность наихудшего сценария), и, следовательно, то, как на время его выполнения влияет изменение размера входных данных.

Также известная как нотация Big Oh или Big Omega, она является стандартной информацией для поиска при проведении анализа сложности алгоритма или приложения. Рассматривая в нотации Big O сложность различных выполняемых операций, мы можем сделать вывод о временной сложности всей системы и получить представление о том, насколько хорошо наше приложение будет масштабироваться при увеличении объема данных.

Знание нотации Big O может помочь нам выбрать лучшие фрагменты кода для основы нашего программного обеспечения, помочь нам построить более эффективные программы и привести нас к хорошей практике кодирования, например, стараться избегать использования чрезмерного количества циклов или вложенных фрагментов кода, которые значительно увеличивают сложность.

Ниже перечислены наиболее распространенные нотации Big O:

Для большинства языков программирования существует документация о временной сложности операций наиболее распространенных функций, таких как вставка или удаление элементов из списка, поиск значений в словарях и т.д., которые мы должны учитывать при создании нашего программного обеспечения.

Ниже показана временная сложность для наиболее распространенных операций, используемых в списках Python. Вы можете

Нотация Big O очень полезна при разработке программного обеспечения, поскольку она позволяет нам выбрать лучшие варианты практически в каждом аспекте, который мы должны оценить.

Это очень важно и при хранении данных, поскольку некоторые форматы данных требуют больше времени для обновления и извлечения информации, чем другие. Если мы хотим создавать приложения, работающие в режиме реального времени (RT), то временная сложность – это то, что мы всегда должны учитывать, поскольку нам, возможно, придется отказаться от удобного и хорошо известного табличного формата хранения данных в обмен на более высокую производительность.

Теперь, когда мы знаем, что такое Big O, и почему это важно, давайте рассмотрим некоторые из наиболее нежелательных временных сложностей, и какие операции могут привести к ним.

3) Избегайте экспоненциалов

После того как мы поняли, что такое нотация Big O, есть две основные сложности, которых мы всегда должны стараться избегать, поскольку если в наших приложениях есть операции с такими сложностями, они будут очень плохо масштабироваться даже на умеренных объемах данных.

Это печально известный экспоненциал (2^n) и, что еще хуже, факториал (2!). Алгоритмы с подобными сложностями растут так быстро, что их можно использовать только для определенных типов входных данных, и даже тогда они требуют очень большого количества времени для выполнения.

На следующем рисунке сравнивается рост некоторых наиболее распространенных сложностей с размером входных данных. Как мы видим, экспоненциальная сложность имеет гораздо больший рост, чем квадратичная или квадратичная сложность ( T(n) = n²), которую мы видели ранее, и которая уже была быстрорастущей.

Из-за этого выполнение программ, имеющих экспоненциальную или, что еще хуже, факториальную сложность, практически нецелесообразно. В этих случаях даже огромных вычислительных мощностей будет недостаточно, и проблему, вероятно, придется решать другим способом, чтобы избежать безумно высокого времени выполнения.

Примерами проблем с экспоненциальной сложностью являются:

Проблемы Power Set: поиск всех подмножеств на множестве.

Вычисление последовательности Фибоначчи.

Решение задачи о путешествующем продавце с помощью динамического программирования.

Потрясающе, теперь, когда мы знаем, каких сложностей нам следует избегать, давайте закончим этот пост сладкой щепоткой одного из наших любимых кусков пирога в мире компьютерных наук: Машинное обучение и наука о данных.

4) Вычислительная сложность в машинном обучении

• Как большинство из нас знает, машинное обучение – это все о данных. Возможно, много данных. Большие данные. В связи с этим при разработке приложений машинного обучения необходимо проявлять особую осторожность, поскольку даже такие простые действия, как форматирование данных или объединение таблиц, могут занять очень много времени на данных такого размера, на которых обучаются алгоритмы ML.
• Более того, каждая модель машинного обучения имеет свои особенности (процедура обучения и механизмы предсказания), что приводит к определенной временной сложности. В зависимости от объема данных, имеющихся у вас на момент обучения, вам следует рассмотреть возможность использования одного алгоритма над другим. Временная сложность прогнозирования также имеет значение, если вы планируете прогнозировать сразу на больших массивах новых данных или работать в режиме реального времени.
• Кроме того, модели машинного обучения имеют свою особенность: сложность зависит не только от размера входных данных n, но и от количества признаков наших данных d . Используя эти два параметра, мы должны тщательно выбирать, какие модели использовать, поскольку при высоких значениях этих параметров обучение некоторых моделей займет запредельное количество времени даже на мощных графических процессорах.

В следующей таблице показана сложность времени обучения для некоторых наиболее популярных моделей машинного обучения:

Как мы видим, логистическая регрессия имеет линейный рост в зависимости от количества точек данных и признаков. Деревья решений имеют линейный рост в зависимости от объема данных и логарифмический в зависимости от количества признаков. В случайном лесу и K-Nearest Neighbour, k относится к количеству деревьев в лесу в первом случае, и к количеству соседей во втором.

Из таблицы также видно, что сложность SVM квадратично зависит от размера входных данных n, что означает, что их, вероятно, не следует использовать для обучения на очень больших объемах данных, однако количество признаков этих данных не столь важно. Это происходит потому, что увеличение временной сложности по отношению к размеру входных данных доминирует над ростом настолько, что количество признаков почти не имеет значения для временной сложности обучения модели.

Это означает, что они хорошо работают для небольших сложных наборов данных, то есть там, где количество обучающих выборок не очень велико, но которые могут иметь большое количество признаков (см. Geron, “Hands on Machine Learning with Scikit-Learn, Tensorflow, and Keras”, Chapter 5: Support Vector Machines).

Знание о сложности наших алгоритмов как специалиста по анализу данных или инженера машинного обучения может помочь нам принять решение, помимо технических: Если мы обучаем классификатор логистической регрессии на некоторых данных, мы можем пойти выпить кофе, вернуться и, вероятно, все будет готово.

Если мы выбираем SVM или искусственную нейронную сеть (не на столе, но тоже семейство моделей, на обучение которых уходит много времени), мы можем пойти прогуляться, пообедать, немного почитать, поработать над другим проектом, пойти домой, поужинать, лечь спать, проснуться, вернуться к работе, чтобы проверить, как работает наш алгоритм, и он все еще будет обучаться.

Если у нас есть сроки, которые мы должны выполнить за определенное время, то, вероятно, хорошей идеей будет получить базовую модель, которая работает быстро, даже настроить эту модель, чтобы извлечь из нее наилучшую возможную производительность, и избегать использования моделей, которые требуют много времени для обучения, так как настройка этих моделей, даже с небольшим перебором сетки гиперпараметров, может занять много времени.

Потрясающе! Я надеюсь, что с помощью этого последнего небольшого обзора вы смогли увидеть другие области компьютерных наук, где сложность очень актуальна, и, в частности, как она должна быть тем, что всегда находится в нашем инструментарии для принятия решений в сфере программного обеспечения.

5) Заключение и дополнительные ресурсы

В этой статье мы рассмотрели, что такое вычислительная сложность, как она выражается с помощью нотации Big O, и почему так важно учитывать ее при создании программных приложений, входные данные которых могут расти или масштабироваться.

Цитата Ады Лавлейс, с которой началась эта статья, говорит очень ясно: при создании программных приложений мы должны проектировать их таким образом, чтобы получить наиболее эффективный код и наименьшее количество вычислений, а для этого мы должны знать о сложности и нотации Big O.

Вот некоторые дополнительные ресурсы на случай, если вы захотите углубиться в какую-либо из тем, затронутых в этой статье, например, в алгоритмы сортировки, более подробную информацию о сложности или о том, как она влияет на машинное обучение.

Кроме того, вы можете найти весь код, использованный для примеров в этой статье, на моем GitHub, в следующем репозитории. Для получения дополнительной информации о машинном обучении, программировании на Python и компьютерных науках, ознакомьтесь со статьей Как изучить машинное обучение.