Эффективность алгоритма

В теоретическом анализе алгоритмов обычно оценивают их сложность в асимптотическом смысле. Наиболее распространён для этого нотация Большого O, введённая Кнутом, которая описывает поведение затрат ресурсов как функции от размера входа ${\displaystyle n}$. Запись ${\displaystyle O(g(n))}$ означает, что время работы алгоритма пропорционально ${\displaystyle g(n)}$, исключая члены меньшего порядка при больших ${\displaystyle n}$. Эта оценка может быть неточной для малых ${\displaystyle n}$, но считается точной при больших ${\displaystyle n}$ (асимптотика). Например, пузырьковая сортировка при малых объёмах данных может быть быстрее сортировки слиянием, но для больших данных предпочтительна последняя, поскольку лучше масштабируется.

Примеры использования O-нотации для асимптотической оценки временной сложности алгоритмов:

Нотация	Название	Примеры
${\displaystyle O(1)}$	константное	Нахождение медианы в отсортированном списке; использование таблицы поиска фиксированного размера; эффективный хеш-функция для поиска элемента.
${\displaystyle O(\log n)}$	логарифмическое	Поиск элемента в отсортированном массиве с помощью бинарного поиска или в сбалансированном дереве; все операции в биномиальной куче.
${\displaystyle O(n)}$	линейное	Поиск в неотсортированном списке, «битом» дереве (в худшем случае) или массиве; сложение двух n-битных чисел с помощью волнопереносного сумматора.
${\displaystyle O(n\log n)}$	логлинейное, квазилинейное	Быстрое преобразование Фурье; сортировка кучей, быстрая сортировка (в среднем и лучшем случае), сортировка слиянием.
${\displaystyle O(n^{2})}$	квадратичное	Умножение двух n-разрядных чисел простым методом; пузырьковая сортировка (в худшем случае), сортировка Шелла, быстрая сортировка (в худшем случае), сортировка выбором или соритировка вставками.
${\displaystyle O(c^{n}),\;c>1}$	экспоненциальное	Поиск оптимального (неприближённого) решения задачи коммивояжёра динамическим программированием; определение эквивалентности логических высказываний методом полного перебора.

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

Существуют бенчмарки, сравнивающие быстродействие компилируемых и интерпретируемых языков программирования^[4][5]. The Computer Language Benchmarks Game — это масштабный сравнительный проект эффективности решений типичных задач на различных языках программирования.

Даже простые «домашние» бенчмарки позволяют объективно сравнивать производительность языков по разным критериям.

На эффективность влияет язык и стиль программирования^[6], используемый компилятор, его параметры, операционная система. Часто интерпретируемые языки заметно медленнее компилируемых^[4] (см. JIT-компиляция, интерпретируемый язык).

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

В ряде ситуаций доступны векторные процессоры, позволяющие выполнять одну инструкцию сразу над несколькими элементами (SIMD). Для эффективного использования этих возможностей алгоритмы иногда приходится специально переписывать (см. параллельные вычисления, распределённые вычисления). Активно разрабатываются высокоуровневые API для параллельных вычислений — CUDA, TensorFlow, Hadoop, OpenMP, MPI.

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

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

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

Тестирование производительности чувствительно к аппаратной конфигурации и действию параллельных процессов (в среде мультипрограммирование и многозадачность).

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

Память используется под код, входные данные, выходные данные и рабочую область. Альгоритмы типа сортировки часто перестраивают данные «на месте» и не требуют отдельного массива для результата.

Также сюда включаются рабочие переменные и стек вызова.

В ЭВМ первых поколений рабочих областей памяти было крайне мало (ЭСАК — до 1024 слов по 17 бит, ZX80 — 1024 байта ОЗУ); в 2010-х на обычных ПК обычно 4–32 Гб ОЗУ, то есть прирост — более чем в 300 миллионов раз.

Современные компьютеры имеют множество уровней памяти с разной скоростью доступа:

• Регистры процессора — самый быстрый и самый ограниченный по объёму ресурс; все операции перед записью в память проходят через регистры, в которых параллельно выполняется обработка.
• Кэш-память — обычно второй уровень скорости (и размерности); кэши современных CPU и GPU иерархичны — L1, L2, L3, — где каждый уровень медленнее, но больше предыдущего. Операции в L1-кэше примерно в 2–10 раз медленнее регистров; промах кэша и обращение к L2 могут замедлить до 10 раз, к L3 — ещё на порядок.

Если требуется обращаться к основной памяти, задержки возрастают ещё в 10–100 раз. В 2018 году ОЗУ часто размещается на том же кристалле процессора (CPU/GPU).

• Память с подкачкой, как часть виртуальной памяти, располагается во внешних устройствах (дисках), обеспечивая большие объёмы хранения ценой задержек, в тысячу раз больших, чем доступ из RAM. Сегодня виртуальная память важна для баланса между пространством и временем и для виртуальных машин. Промахи кэширования из ОЗУ называются страничными ошибками и сильно замедляют работу программы.

Алгоритмы, помещающиеся в кэш, в разы быстрее алгоритмов, рассчитанных только на ОЗУ, а те — в разы быстрее обращающихся к дисковой подкачке. Поэтому замещение кэша, локальность данных и выравнивание памяти — краеугольные аспекты высокопроизводительных вычислений. В современных платформах до трёх уровней кэша с различной производительностью и объёмом. Проблемы адаптации крайне различны на разных архитектурах.

Ранее, если алгоритм не умещался в память, он был неприменим; сегодня виртуальная память позволяет работать программам, многократно превышающим объём физической памяти, ценой резкого падения скорости. Алгоритмы, оптимизированные по памяти, одновременно выигрывают и по времени.