Эффективность алгоритма (ох, страшная фраза) — это грубая мера или эталон алгоритма, который требуется для выполнения во время выполнения в зависимости от размера входных данных (попробуйте сказать это в 3 раза быстрее). Другими словами, подумайте о скорости алгоритма по отношению к данным, которые он получает в качестве входных данных. Реальность такова, что эффективность алгоритма начинает действительно иметь значение, когда размер входных данных велик или когда мы ищем то, что известно как асимптотическая сложность нашего алгоритма (т.е. входные данные приближаются к бесконечности... если мы хотим получить с ними математику). На самом деле, когда наш размер входных данных мал, почти любой алгоритм будет быстрым. Только когда мы столкнемся с большими размерами входных данных, скорость алгоритмов начнет становиться значительно более заметной (т. е. вы увидите, что на некоторые вещи требуется время… как на самом деле требуется время). Эффективность алгоритма очень сильно влияет на реальный мир, помимо того, что она является концепцией информатики. Взятый в деловом контексте, старый том времени — это деньги, которые здесь держат. Представьте себе алгоритм, который работает за 5 миллисекунд, когда размер входных данных составляет десять тысяч элементов. А теперь представьте, если бы для того же алгоритма размер входных данных удвоился. Что тогда происходит со скоростью нашего программного обеспечения? Сколько времени уходит на бег? Проверяя его эффективность, мы можем решить проблему (или, по крайней мере, посмотреть, есть ли она у нас для начала) и сделать клиентов счастливыми.

Обозначение большого O

Скорость роста описывает, как сложность алгоритма изменяется по мере увеличения размера входных данных, и представлена ​​в виде нотации Big-O: формула, где n — размер входных данных. Предполагается, что переменная n является неизвестным значением и в зависимости от алгоритма может иметь тонкое определение. В некоторых случаях значение n может относиться к количеству элементов в массиве, который нужно оценить, или к количеству записей в хэш-таблице, или даже к количеству битов в типе данных.

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

Давайте определим количество операций над нашими входными данными. Как мы уже говорили, операция — это действие, выполняемое компьютером в реальном мире, которое каждый раз занимает одинаковое количество времени. В нашем массиве мы перебираем массив и для нашего текущего числа получаем сумму этого числа и числа непосредственно над ним (мы добавляем 1 к нашему текущему idx). Для каждой записи n операция, которую мы здесь выполняем, заключается в получении суммы текущего числа и числа над ним. Этот процесс состоит из n операций. Имейте в виду, что мы перебираем массив чисел, пока не дойдем до предпоследнего числа или n-1. Поэтому наша нотация BigO будет записана как O (n-1).

Но подождите горячую секунду………

Помните, что в нотации BigO мы имеем дело с действительно большими значениями. Реальность такова, что при действительно больших значениях разница между, скажем, n = 90 000 и n = 90 000–1 незначительна. Поэтому при написании BigO мы сохраняем все, кроме термина самого высокого порядка или термина, который имеет наибольшее значение, особенно когда n становится большим. Таким образом, в этом случае наш O (n-1) будет записан как O (n).

Вы также, вероятно, задаетесь вопросом о других строках кода. Они тоже не считаются? (ведь они должны, иначе я бы их не писал) В конце концов, мы объявляем и инициализируем три переменные NSUIntegers. Поэтому наша формула должна отражать это. Другими словами, разве это не должно быть O(n-1+3)? Неа. Опять же, здесь нас интересует только член высшего порядка. Итак, в заключение (наконец — сделайте глубокий вдох) наш метод findGreatestSumA имеет нотацию BigO O (n). Это известно как линейное время и означает, что время алгоритма увеличивается линейно по мере увеличения размера входных данных.

Давайте попробуем другой пример (и вы думали, что это длинное объяснение закончится... подумайте еще раз!)

Что касается нашего нового алгоритма, единственное, что изменилось, — это дополнительный цикл for, который выполняет n сравнений в обратном порядке. Итак, другими словами, вы получаете сумму, добавляя число из внешнего цикла и добавляя его к каждому числу во внутреннем цикле. Теперь разница здесь в том, что вы проходите дополнительный цикл n раз. Таким образом, наш алгоритм findGreatestSumB выполняет n * n операций и, следовательно, имеет нотацию Big O, равную O(n²). Это известно как экспоненциальное время, и количество операций увеличивается экспоненциально (что означает действительно большое) по мере роста размера ввода.

Другие соображения

Помните, что нотация Big O дает лишь приблизительное представление об эффективности алгоритма. Реальность такова, что для получения истинной оценки алгоритма его нужно запустить на реальной машине, а затем измерить его время выполнения. Есть также вопрос о лучших, худших и средних условиях, которые также дополнительно влияют на эффективность алгоритмов. Вообще говоря, когда мы сообщаем об обозначении Big O, мы говорим о наихудшем сценарии. Однако есть сценарии, в которых один и тот же алгоритм может быть O(n) в худшем случае и даже O(n²) в лучшем или среднем сценарии. Наконец, при попытке определить эффективность алгоритмов, если эффективность алгоритма оценивается как 1/2 от общего количества операций с входными данными, вы ожидаете, что это будет обозначено как O (n/2). Опять же, с нотацией Big O наивысшее значение термина всегда имеет приоритет, а постоянные множители отбрасываются, поэтому O (n/2) будет оцениваться как O (n) (ха… так волшебно).

Чтобы завершить процесс проверки эффективности наших алгоритмов и придумать правильную нотацию:

  1. Определите свой n по отношению к входу
  2. Определить количество операций, которые выполняются для каждого n входного значения
  3. Отбросить все термины, кроме термина с наивысшим порядком
  4. Отбросьте все постоянные факторы

Вот список различных анализов алгоритмов во время выполнения и их порядок от лучшего к худшему:

  • Константа O(1) — представляет алгоритм, в котором размер входных данных НЕ влияет на время, необходимое для запуска алгоритма (т. е. 1 может означает, что независимо от размера входных данных, который он может выполнять, он всегда будет выполняться в одно и то же время, будь то час или минута). Это в значительной степени сценарий эффективности единорога; часто пытаются, редко достигают.
  • Логарифмический O (log n) - алгоритм, время выполнения которого логарифмически увеличивается в зависимости от размера входных данных.
  • Линейный O(n) — представляет собой алгоритмическую сложность, при которой время выполнения увеличивается линейно по мере увеличения размера входных данных. Другими словами, скажем, алгоритму требуется 2 миллисекунды для обработки ввода размером 1 элемент, при таком понимании мы можем разумно оценить, что он будет выполнять 4 миллисекунды для 2 элементов.
    Полезный совет: они обычно идентифицируются с конструкциями циклов (т.е. для циклов)
  • Суперлинейный алгоритм O(n log n) — это что-то среднее между линейным алгоритмом и полиномиальным алгоритмом.
  • Полиномиальный алгоритм O(n) — время работы быстро растет в зависимости от размера входных данных.
  • Экспоненциальный алгоритм O(c^n) — растет даже быстрее, чем полиномиальный алгоритм; это похоже на полиномиальный алгоритм, за исключением того, что он любит отнимать еще больше времени
  • Факторный алгоритм O(n!) — растет быстрее всех алгоритмов и, следовательно, непригоден даже для небольших входных данных (womp womp womp)

Хорошей базой для алгоритма является суперлинейное время или лучше.