Введение

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

В информатике анализ алгоритмов — это процесс определения вычислительной сложности алгоритмов, то есть количества времени, памяти или других ресурсов, необходимых для их выполнения. Обычно это включает в себя определение функции, связывающей размер входных данных алгоритма с количеством выполняемых им шагов (его временная сложность) или объемом используемой памяти (его пространственная сложность). Алгоритм считается эффективным, если значения этой функции малы или растут медленно по сравнению с ростом размера входных данных. Различные входные данные одного размера могут приводить к разному поведению алгоритма, поэтому описания наилучшего, наихудшего и среднего случаев могут представлять практический интерес. Если не указано иное, функция, описывающая производительность алгоритма, обычно является верхней границей, определяемой на основе наихудших входных данных. Термин «анализ алгоритмов» был введен Дональдом Кнутом. Анализ алгоритмов является важной частью более широкой теории вычислительной сложности, которая предоставляет теоретические оценки ресурсов, необходимых любому алгоритму для решения конкретной вычислительной задачи. Эти оценки дают представление о разумных направлениях поиска эффективных алгоритмов. В теоретическом анализе алгоритмов обычно оценивают их сложность в асимптотическом смысле, то есть оценивают функцию сложности для произвольно больших входных данных. Для этого используются нотации «Большое O», «Большое Омега» и «Большое Тета». Например, считается, что бинарный поиск выполняется за количество шагов, пропорциональное логарифму размера n сортируемого списка, или в O(log n), что в разговорной речи называют «в логарифмическое время». Асимптотические оценки обычно используются, поскольку различные реализации одного и того же алгоритма могут различаться по эффективности. Однако эффективность любых двух «разумных» реализаций данного алгоритма связана постоянным множительным фактором, называемым скрытой константой. Точные (не асимптотические) оценки эффективности иногда можно вычислить, но для этого обычно требуются определенные предположения относительно конкретной реализации алгоритма, называемой моделью вычислений. Модель вычислений может быть определена с точки зрения абстрактного компьютера, например, машины Тьюринга, и/или путем постулирования, что определенные операции выполняются за единицу времени. Например, если сортируемый список, к которому применяется бинарный поиск, содержит n элементов и мы можем гарантировать, что каждый поиск элемента в списке может быть выполнен за единицу времени, то для получения ответа потребуется не более log2(n) + 1 единиц времени.

Анализ времени выполнения

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

Порядок роста

Неформально, можно сказать, что алгоритм демонстрирует скорость роста, сопоставимую с математической функцией, если начиная с некоторого размера входных данных n, произведение этой функции f(n) на положительную константу является верхней границей или пределом времени работы алгоритма. Иными словами, для заданного размера входных данных n, большего некоторого n0, и константы c, время работы алгоритма никогда не превысит c × f(n). Эта концепция часто выражается с помощью нотации «Большое O». Например, поскольку время работы сортировки вставками растет квадратично с увеличением размера входных данных, можно сказать, что сортировка вставками имеет порядок O(n²). Нотация «Большое O» – удобный способ выразить наихудший сценарий для данного алгоритма, хотя её также можно использовать для выражения среднего случая – например, наихудший сценарий для быстрой сортировки – O(n²), а среднее время работы – O(n log n).

Эмпирические порядки роста

Предполагая, что время выполнения подчиняется степенному закону, t ≈ kn^a, коэффициент a можно найти, измерив эмпирически время выполнения {t1, t2} для некоторых размеров задачи {n1, n2} и вычислив 1 = t2/t1 = (n2/n1)^a, откуда 1 = a = log(t2/t1)/log(n2/n1). Иными словами, это измеряет наклон эмпирической линии на логарифмическом графике зависимости времени выполнения от размера входных данных в некоторой точке. Если порядок роста действительно подчиняется степенному закону (и, следовательно, линия на логарифмическом графике действительно является прямой), эмпирическое значение a будет оставаться постоянным в разных диапазонах, а если нет, то оно будет меняться (и линия будет изогнутой), но все равно может служить для сравнения эмпирических локальных порядков роста двух алгоритмов. Применим это к приведенной выше таблице:

n (размер списка) Время выполнения компьютера A (в наносекундах) Локальный порядок роста (n^ ) Время выполнения компьютера B (в наносекундах) Локальный порядок роста (n^ ) 15 7 100,000 65 32 1.04 150,000 0.28 250 125 1.01 200,000 0.21 1,000 500 1.00 250,000 0.16 1,000,000 500,000 1.00 500,000 0.10 4,000,000 2,000,000 1.00 550,000 0.07 16,000,000 8,000,000 1.00 600,000 0.06

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

Актуальность

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

Постоянные факторы

Анализ алгоритмов обычно фокусируется на асимптотической производительности, особенно на элементарном уровне, но в практических приложениях важны постоянные факторы, а реальные данные на практике всегда ограничены по размеру. Ограничение обычно определяется размером адресуемой памяти, так что на 32-битных машинах 2<sup>32</sup> = 4 GiB (больше, если используется сегментированная память), а на 64-битных машинах 2<sup>64</sup> = 16 EiB. Таким образом, при ограниченном размере порядок роста (времени или пространства) может быть заменен постоянным фактором, и в этом смысле все практические алгоритмы являются O(1) для достаточно большой константы или для достаточно малых данных. Эта интерпретация особенно полезна для функций, растущих чрезвычайно медленно: (бинарный) итерированный логарифм (log*) меньше 5 для всех практических данных (2<sup>65536</sup> бит); (бинарный) логарифм логарифма (log log n) меньше 6 для практически всех практических данных (2<sup>64</sup> бит); и бинарный логарифм (log n) меньше 64 для практически всех практических данных (2<sup>64</sup> бит). Алгоритм с неконстантной сложностью тем не менее может быть более эффективным, чем алгоритм с константной сложностью на практических данных, если накладные расходы алгоритма с константным временем приводят к большему постоянному фактору, например, можно иметь при условии, что и . Для больших данных линейные или квадратичные факторы нельзя игнорировать, но для малых данных асимптотически неэффективный алгоритм может оказаться более эффективным. Это особенно используется в гибридных алгоритмах, таких как Timsort, которые используют асимптотически эффективный алгоритм (здесь сортировка слиянием, с временной сложностью O(n log n)), но переключаются на асимптотически неэффективный алгоритм (здесь сортировка вставками, с временной сложностью O(n<sup>2</sup>)) для малых данных, поскольку более простой алгоритм быстрее на малых объемах данных.