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

В предыдущем посте мы познакомились с концепцией Big O и временной сложностью. Резюмируем:

  • Временная сложность не связана с синхронизацией с часами, сколько времени занимает алгоритм. Вместо этого, сколько операций выполнено.
  • На количество инструкций, выполняемых программой, влияет размер ввода (обычно обозначаемый как n) и расположение их элементов. .
  • Нотация Big O используется для классификации алгоритмов по наихудшему сценарию. Это функция размера ввода `n`. Например. O (n) или O (n²).

Вот шпаргалка по Big O и примеры, которые мы рассмотрим в этом посте.

А теперь давайте по порядку представим примеры кода!

O (1) - Постоянное время

O(1) описывает алгоритмы, для вычисления которых требуется одинаковое количество времени, независимо от размера входных данных.

Например, если функции требуется одинаковое время для обработки 10 элементов, а также 1 миллиона элементов, то мы говорим, что она имеет постоянную скорость роста или O(1). Давайте посмотрим на некоторые случаи.

Примеры алгоритмов выполнения с константой O (1):

  • Узнайте, четное или нечетное число.
  • Проверьте, является ли элемент массива нулевым.
  • Распечатайте первый элемент из списка.
  • Найдите значение на карте.

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

Нечетный или четный

Узнайте, четно или нечетно данное число.

Дополнительное примечание: вы также можете заменить n % 2 битовым оператором AND: n & 1. Если первый бит (LSB) равен 1, то он нечетный, в противном случае - четный.

Не имеет значения, равно ли n 10 или 10,001, строка 2 будет выполнена только один раз.

Не обманывайте однострочников. Они не всегда переводятся в постоянное время. Вы должны знать, как они реализованы.

Если у вас есть такой метод, как Array.sort(), или любой другой метод массива или объекта, вам нужно изучить реализацию, чтобы определить время его работы.

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

Если вы используете алгоритм длинного умножения из школьного учебника, для умножения двух чисел потребуется O(n^2). Однако большинство языков программирования ограничивают числа до максимального значения (например, в JS: Number.MAX_VALUE равно 1.7976931348623157e+308). Таким образом, вы не можете оперировать числами, которые дают результат больше, чем MAX_VALUE. Таким образом, примитивные операции должны выполняться с фиксированным количеством инструкций O(1) или вызывать ошибки переполнения (в JS, Infinity ключевое слово).

Этот пример был легким. Давай сделаем еще один.

Справочная таблица

По заданной строке найдите данные о частоте ее слов.

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

Только хеш-таблица с идеальной хеш-функцией будет иметь время выполнения O (1) в худшем случае. Идеальная хеш-функция непрактична, поэтому могут возникнуть некоторые коллизии и обходные пути, что приведет к наихудшему времени выполнения O (n) . Тем не менее, в среднем время поиска составляет O (1) .

O (n) - линейное время

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

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

Примеры алгоритмов линейного времени O (n):

  • Получить максимальное / минимальное значение в массиве.
  • Найдите данный элемент в коллекции.
  • Распечатайте все значения в списке.

Давайте реализуем первый пример.

Самый большой элемент в несортированном массиве

Допустим, вы хотите найти максимальное значение из несортированного массива.

Сколько операций выполнит функция findMax?

Что ж, он проверяет каждый элемент из n. Если текущий элемент больше max, он выполнит присвоение.

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

Если вы получите временную сложность, это будет примерно так:

  • Строка 2–3: 2 операции
  • Строка 4: петля размера n.
  • Строка 6–8: 3 операции внутри цикла for.

Итак, это дает нам 3(n) + 2.

Применяя асимптотический анализ, который мы узнали в предыдущем посте, мы можем оставить только наиболее значимый член, например: n. И, наконец, используя нотацию Big O, мы получаем: O(n).

Мы можем проверить это с помощью нашего counter. Если n имеет 3 элемента:

findMax([3, 1, 2]);
// n: 3, counter: 3

или если n имеет 9 элементов:

findMax([4,5,6,1,9,2,8,3,7])
// n: 9, counter: 9

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

O (n²) - квадратичное время

Функция с квадратичной временной сложностью имеет скорость роста n². Если размер входа 2, он выполнит 4 операции. Если входной размер 8, потребуется 64 и так далее.

Вот несколько примеров квадратичных алгоритмов O (n²):

  • Проверьте, есть ли в коллекции повторяющиеся значения.
  • Сортировка элементов в коллекции с помощью пузырьковой сортировки, сортировки вставкой или сортировки по выбору.
  • Найдите все возможные упорядоченные пары в массиве.

Давайте реализуем первые два.

Есть дубликаты

Вы хотите найти повторяющиеся слова в массиве. Наивным решением будет следующее:

Анализ временной сложности:

  • Строка 2–3: 2 операции
  • Строка 5–6: двойная петля размера n, поэтому n^2.
  • Строка 7–13: в двойном цикле ~ 3 операции.

Получаем 3n^2 + 2.

Опять же, когда у нас есть асимптотический анализ, мы отбрасываем все константы и оставляем наиболее значимый член: n^2. Итак, в нотации большой буквы O это будет O(n^2).

Мы используем переменную счетчика, чтобы помочь нам проверить. Функция hasDupliates имеет два цикла. Если мы введем 4 слова, он выполнит внутренний блок 16 раз. Если у нас 9, он выполнит счетчик 81 раз и так далее.

hasDuplicates([1,2,3,4]);
// n: 4, counter: 16

и с размером n 9:

hasDuplicates([1,2,3,4,5,6,7,8,9]);
// n: 9, counter: 81

Давайте посмотрим на другой пример алгоритма квадратичного времени.

Пузырьковая сортировка

Мы хотим отсортировать элементы в массиве. Один из способов сделать это - использовать пузырьковую сортировку следующим образом:

Кроме того, вы можете заметить, что для очень большого n время, необходимое для решения проблемы, значительно увеличивается. Можете ли вы определить взаимосвязь между вложенными циклами и временем выполнения? Когда функция имеет единственный цикл, это обычно переводится во временную сложность выполнения O (n). Теперь эта функция имеет 2 вложенных цикла и квадратичное время выполнения: O (n ^ 2).

O (n ^ c) - Полиномиальное время

Полиномиальный ход представлен как O (n ^ c), когда c ›1. Как вы уже видели, два внутренних цикла почти переводятся в O (n²), поскольку в большинстве случаев он должен проходить через массив дважды. Являются ли три вложенных цикла кубическими? В большинстве случаев да!

Обычно мы не хотим использовать полиномиальное время выполнения (квадратичное, кубическое, O (n ^ c)…), поскольку они требуют больше времени для вычисления, поскольку входные данные быстро растут. Однако они не самые плохие. Давайте что-нибудь еще медленнее.

Тройные вложенные петли

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

3x + 9y + 8z = 79

Эта наивная программа предоставит вам все решения, удовлетворяющие уравнению, где x, y и z ‹n.

Этот алгоритм имеет кубическое время выполнения: O(n^3).

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

O (log n) - логарифмическое время

Сложности с логарифмическим временем обычно применяются к алгоритмам, которые каждый раз делят задачи пополам.

Примеры алгоритмов O (log n):

  • Поиск слова в физическом словаре
  • Поиск человека в телефонной книге

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

Алгоритм А:

  • Начните с начала книги и идите по порядку, пока не найдете нужный контакт. Время выполнения: O(n)

Алгоритм B:

  • Откройте книгу посередине и проверьте имя на ней.
  • Если имя, которое вы ищете, в алфавитном порядке больше, посмотрите вправо. В противном случае посмотрите в левую половину.

Бинарный поиск

Найдите индекс элемента в отсортированном массиве.

Если мы реализуем (алгоритм A), перебирая все элементы в массиве, это займет время выполнения O(n). Можем ли мы сделать лучше? Можно попробовать использовать тот факт, что коллекция уже отсортирована. Позже мы сможем разделить пополам, ища рассматриваемый элемент.

Вычислить временную сложность функции functionindexOf не так просто, как в предыдущих примерах. Эта функция рекурсивная.

Есть несколько способов анализа рекурсивных алгоритмов. Ее можно решить с помощью Мастер-метода или с помощью замены, описанной в видео выше. По сути, алгоритм каждый раз делит ввод пополам, и оказывается, что log (n) - это функция, которая ведет себя подобным образом.

O (n log n) - Линейноарифмический

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

Примеры линейных алгоритмов:

  • Эффективные алгоритмы сортировки, такие как сортировка слиянием, быстрая сортировка и другие.

Сортировка слиянием

Как лучше всего отсортировать массив? Ранее мы предлагали решение с использованием пузырьковой сортировки с временной сложностью O (n²). Можем ли мы сделать лучше?

Мы можем использовать алгоритм под названием mergesort, чтобы улучшить его:

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

Вот код для сортировки слиянием:

Как видите, у него есть две функции sort и merge. Слияние - это вспомогательная функция, которая запускается один раз через коллекции a и b, поэтому время ее выполнения составляет O (n). Вы можете применить основной метод, чтобы получить время выполнения O (n log n).

O (2 ^ n) - экспоненциальное время

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

Примеры экспоненциальных алгоритмов выполнения:

  • Power Set: поиск всех подмножеств в наборе.
  • Фибоначчи.
  • Задача коммивояжера с использованием динамического программирования.

Давайте рассмотрим пример набора мощности.

Набор мощности

Чтобы понять набор мощности, представим, что вы покупаете пиццу. В магазине есть много начинок, которые вы можете выбрать, например, пепперони, грибы, бекон и ананас. Назовем каждую начинку A, B, C, D. Что вы выберете? Вы можете выбрать без начинки (вы на диете;), вы можете выбрать один топпинг, или комбинацию из двух, или комбинацию из трех, или все из них. Набор мощности дает вам все возможности (кстати, есть 16 комбинаций с 4 начинками, как вы увидите позже).

Давайте рассмотрим несколько базовых случаев и выясним тенденцию:

Вы заметили какой-нибудь узор?

  • Первые возвраты имеют пустой элемент.
  • Второй случай возвращает пустой элемент + 1-й элемент ввода.
  • Третий случай возвращает в точности результаты второго случая + тот же массив с добавленным к нему вторым элементом b.

Что, если вы хотите найти подмножества abc? Что ж, это будут именно подмножества «ab» и снова подмножества ab с c, добавленными в конце каждого элемента.

Как вы заметили, каждый раз, когда ввод становится длиннее, вывод становится вдвое длиннее предыдущего. Давайте запрограммируем это:

Если мы запустим эту функцию для пары случаев, мы получим:

Как и ожидалось, если вы построите n и f(n), вы заметите, что это будет в точности как функция 2^n. Этот алгоритм имеет время работы O(2^n).

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

O (n!) - Факторное время

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

5! = 5 x 4 x 3 x 2 x 1 = 120

Растет довольно быстро:

20! = 2,432,902,008,176,640,000

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

Примеры O (n!) факторных алгоритмов выполнения

  • Перестановки строки.
  • Решение проблемы коммивояжера перебором.

Разберем первый пример.

Перестановки

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

Как бы вы это решили?

Самый простой способ - проверить, имеет ли строка длину 1, если да, вернуть эту строку, так как вы не можете расположить ее по-другому.

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

Если мы распечатаем результат, он будет примерно таким:

Я пробовал со шнуром длиной 10. Это заняло около 8 секунд!

У меня есть для тебя небольшое домашнее задание ...

Можете ли вы попробовать перестановку из 11 символов? ;) Прокомментируйте ниже, что случилось с вашим компьютером!

Графики всех сложностей бега

Мы исследовали время работы наиболее распространенных алгоритмов на одном или двух примерах! Они должны дать вам представление о том, как рассчитать время работы при разработке проектов. Ниже вы можете найти диаграмму с графиком всех временных сложностей, которые мы рассмотрели:

Помните о своей временной сложности!

Дополнительные ресурсы

Первоначально опубликовано на сайте adrianmejia.com 5 апреля 2018 г.