Анализ алгоритмов

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

Термин «анализ алгоритмов» был придуман Дональдом Кнутом . ^[1] Анализ алгоритмов является важной частью более широкой теории вычислительной сложности , которая дает теоретические оценки ресурсов, необходимых любому алгоритму, решающему заданную вычислительную задачу . Эти оценки дают представление о разумных направлениях поиска эффективных алгоритмов .

В теоретическом анализе алгоритмов принято оценивать их сложность в асимптотическом смысле, т. е. оценивать функцию сложности для произвольно больших входных данных. Для этой цели используются нотации Big O , Big-omega и Big-theta . ^[2] Например, говорят, что двоичный поиск выполняется за количество шагов, пропорциональное логарифму размера $n$ отсортированного списка, в котором выполняется поиск, или за $O (log n)$ , в разговорной речи «за логарифмическое время ». Обычно используются асимптотические оценки, поскольку различные реализации одного и того же алгоритма могут отличаться по эффективности. Однако эффективности любых двух «разумных» реализаций данного алгоритма связаны постоянным мультипликативным множителем, называемым скрытой константой .

Иногда можно вычислить точные (не асимптотические) меры эффективности, но обычно они требуют определенных предположений относительно конкретной реализации алгоритма, называемой моделью вычисления . Модель вычисления может быть определена в терминах абстрактного компьютера , например, машины Тьюринга , и/или постулированием того, что определенные операции выполняются за единицу времени. Например, если отсортированный список, к которому мы применяем бинарный поиск, имеет $n$ элементов, и мы можем гарантировать, что каждый поиск элемента в списке может быть выполнен за единицу времени, то для возврата ответа потребуется максимум $log 2 (n) + 1 единиц времени.$

Модели затрат

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

Обычно используются две модели затрат: ^[3]^[4]^[5]^[6]^[7]

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

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

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

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

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

Недостатки эмпирических показателей

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

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

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

Компьютер A, запускающий линейную программу поиска, демонстрирует линейную скорость роста. Время выполнения программы прямо пропорционально размеру ее входных данных. Удвоение размера входных данных удваивает время выполнения, учетверение размера входных данных учетверяет время выполнения и т. д. С другой стороны, компьютер B, запускающий программу двоичного поиска, демонстрирует логарифмическую скорость роста. Учетверение размера входных данных увеличивает время выполнения только на постоянную величину (в этом примере 50 000 нс). Несмотря на то, что компьютер A, по-видимому, более быстрая машина, компьютер B неизбежно превзойдет компьютер A по времени выполнения, поскольку он запускает алгоритм с гораздо более медленной скоростью роста.

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

Неформально можно сказать, что алгоритм демонстрирует темп роста порядка математической функции , если за пределами определенного размера входных данных $n$ функция $f (n),$ умноженная на положительную константу, обеспечивает верхнюю границу или предел для времени выполнения этого алгоритма. Другими словами, для заданного размера входных данных $n ,$ большего некоторого $n$ ₀ , и константы $c$ , время выполнения этого алгоритма никогда не будет больше, чем $c \times f (n)$ . Эта концепция часто выражается с помощью нотации Big O. Например, поскольку время выполнения сортировки вставкой растет квадратично с увеличением размера входных данных, можно сказать, что сортировка вставкой имеет порядок $O (n 2)$ .

Обозначение «О большое» — это удобный способ выражения наихудшего сценария для данного алгоритма, хотя его также можно использовать для выражения среднего случая — например, наихудший сценарий для быстрой сортировки равен $O (n 2)$ , но среднее время выполнения равно $O (n log n)$ .

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

Предполагая, что время выполнения следует правилу мощности, $t \approx kn a$ , коэффициент $a$ может быть найден ^[9] путем проведения эмпирических измерений времени выполнения ${t 1, t 2$ } в некоторых точках размера проблемы ${n 1, n 2$ } и вычисления $t 2 / t 1 = (n 2 / n 1) a$ так, что $a = log(t 2 / t 1)/log(n 2 / n 1)$ . Другими словами, это измеряет наклон эмпирической линии на графике в логарифмическом масштабе времени выполнения против размера входных данных в некоторой точке размера. Если порядок роста действительно следует правилу мощности (и поэтому линия на графике в логарифмическом масштабе действительно является прямой линией), эмпирическое значениеостанется постоянным в разных диапазонах, а если нет, то изменится (и линия будет кривой) — но все равно может служить для сравнения любых двух заданных алгоритмов относительно их эмпирических локальных порядков поведения роста. Применительно к таблице выше:

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

Оценка сложности выполнения

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

1 получить положительное целое число n из входного значения
2, если n > 103 принта "Это может занять некоторое время..."4 для i = от 1 до n5 для j = 1 для i6 печатать i * j7 печать "Готово!"

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

В алгоритме выше шаги 1, 2 и 7 будут выполнены только один раз. Для оценки наихудшего случая следует предположить, что шаг 3 также будет выполнен. Таким образом, общее время выполнения шагов 1-3 и шага 7 составляет:

T_{1}+T_{2}+T_{3}+T_{7}.\,

Циклы на шагах 4, 5 и 6 сложнее оценить. Внешний цикл проверки на шаге 4 будет выполнен ( n + 1) раз, ^[10] что потребляет T ₄ ( n + 1) времени. Внутренний цикл, с другой стороны, регулируется значением j, которое выполняет итерации от 1 до i . При первом проходе через внешний цикл j выполняет итерации от 1 до 1: Внутренний цикл выполняет один проход, поэтому выполнение тела внутреннего цикла (шаг 6) потребляет T ₆ времени, а проверка внутреннего цикла (шаг 5) потребляет 2 T ₅ времени. Во время следующего прохода через внешний цикл j выполняет итерации от 1 до 2: внутренний цикл выполняет два прохода, поэтому выполнение тела внутреннего цикла (шаг 6) потребляет 2 T ₆ времени, а проверка внутреннего цикла (шаг 5) потребляет 3 T ₅ времени.

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

T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}

который может быть разложен ^[11] как

\left[1+2+3+\cdots +(n-1)+n\right]T_{6}=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}

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

{\begin{align}&2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}\\=\ &T_{5}+2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}-T_{5}\end{align}}

что можно разложить на множители

{\begin{aligned}&T_{5}\left[1+2+3+\cdots +(n-1)+n+(n+1)\right]-T_{5}\\=&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+(n+1)T_{5}-T_{5}\\=&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{5}+nT_{5}\\=&\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}\end{aligned}}

Таким образом, общее время выполнения этого алгоритма составляет:

f(n)=T_{1}+T_{2}+T_{3}+T_{7}+(n+1)T_{4}+\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}

что сводится к

f(n)=\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}

В качестве практического правила можно предположить, что член наивысшего порядка в любой заданной функции доминирует над ее скоростью роста и, таким образом, определяет ее порядок времени выполнения. В этом примере n ² является членом наивысшего порядка, поэтому можно заключить, что $f (n) = O (n 2)$ . Формально это можно доказать следующим образом:

Докажите, что $\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},\ n\geq n_{0}$

${\begin{aligned}&\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\\\leq &(n^{2}+n)T_{6}+(n^{2}+3n)T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\ ({\text{for }}n\geq 0)\end{aligned}}$

Пусть k будет константой, большей или равной [ T ₁ .. T ₇ ]. Поэтому

${\begin{aligned}&T_{6}(n^{2}+n)+T_{5}(n^{2}+3n)+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq k(n^{2}+n)+k(n^{2}+3n)+kn+5k\\=&2kn^{2}+5kn+5k\leq 2kn^{2}+5kn^{2}+5kn^{2}\ ({\text{for }}n\geq 1)=12kn^{2}\end{aligned}}$

$\left[{\frac {1}{2}}(n^{2}+n)\right]T_{6}+\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}+T_{7}\leq cn^{2},n\geq n_{0}{\text{ for }}c=12k,n_{0}=1$

Более элегантный подход к анализу этого алгоритма состоял бы в том, чтобы объявить, что [ T ₁ .. T ₇ ] все равны одной единице времени, в системе единиц, выбранной так, чтобы одна единица была больше или равна фактическому времени для этих шагов. Это означало бы, что время выполнения алгоритма распадается следующим образом: ^[12]

$4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}n\geq 1)=O(n^{2}).$

Анализ темпов роста других ресурсов

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

пока  файл все еще открыт:  пусть n = размер файла  на  каждые 100 000 килобайт увеличения размера файла  удваивают объем зарезервированной памяти

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

Релевантность

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

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

Анализ алгоритмов обычно фокусируется на асимптотической производительности, особенно на элементарном уровне, но в практических приложениях важны постоянные факторы, а реальные данные на практике всегда ограничены по размеру. Пределом обычно является размер адресуемой памяти, поэтому на 32-битных машинах 2 ³² = 4 GiB (больше, если используется сегментированная память ), а на 64-битных машинах 2 ⁶⁴ = 16 EiB. Таким образом, учитывая ограниченный размер, порядок роста (времени или пространства) можно заменить постоянным фактором, и в этом смысле все практические алгоритмы являются $O (1)$ для достаточно большой константы или для достаточно малых данных.

Эта интерпретация в первую очередь полезна для функций, которые растут чрезвычайно медленно: (двоичный) итеративный логарифм (log ^* ) меньше 5 для всех практических данных (2 ⁶⁵⁵³⁶ бит); (двоичный) логарифм-логарифм (log log n ) меньше 6 для практически всех практических данных (2 ⁶⁴ бита); и двоичный логарифм (log n ) меньше 64 для практически всех практических данных (2 ⁶⁴ бита). Алгоритм с непостоянной сложностью может, тем не менее, быть более эффективным, чем алгоритм с постоянной сложностью на практических данных, если накладные расходы алгоритма постоянного времени приводят к большему постоянному множителю, например, можно иметь так долго, как и . $K>k\log \log n$ $K/k>6$ $n<2^{2^{6}}=2^{64}$

Для больших данных линейные или квадратичные факторы не могут быть проигнорированы, но для малых данных асимптотически неэффективный алгоритм может быть более эффективным. Это особенно используется в гибридных алгоритмах , таких как Timsort , которые используют асимптотически эффективный алгоритм (здесь сортировка слиянием , с временной сложностью ), но переключаются на асимптотически неэффективный алгоритм (здесь сортировка вставкой , с временной сложностью ) для малых данных, поскольку более простой алгоритм быстрее на малых данных. $n\log n$ $n^{2}$

Смотрите также

Амортизированный анализ
Анализ параллельных алгоритмов
Асимптотическая вычислительная сложность
Лучший, худший и средний случай
Обозначение «Большое О»
Теория сложности вычислений
Основная теорема (анализ алгоритмов)
NP-полный
Численный анализ
Полиномиальное время
Оптимизация программы
Профилирование (компьютерное программирование)
Масштабируемость
Сглаженный анализ
Анализ завершения — подзадача проверки того, завершится ли программа вообще.
Временная сложность — включает таблицу порядков роста для распространенных алгоритмов
Сложность, основанная на информации

Примечания

^ "Knuth: Recent News". 28 августа 2016 г. Архивировано из оригинала 28 августа 2016 г.
^ Кормен, Томас Х., ред. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. стр. 44–52. ISBN 978-0-262-03384-8. OCLC 311310321.
^ Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Ульман (1974). Разработка и анализ компьютерных алгоритмов . Addison-Wesley Pub. Co. ISBN 9780201000290., раздел 1.3
^ Юрай Громкович (2004). Теоретическая информатика: введение в автоматы, вычислимость, сложность, алгоритмику, рандомизацию, связь и криптографию. Springer. С. 177–178. ISBN 978-3-540-14015-3.
^ Джорджио Аусиелло (1999). Сложность и аппроксимация: комбинаторные задачи оптимизации и их аппроксимативные свойства. Springer. С. 3–8. ISBN 978-3-540-65431-5.
^ Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов, Берлин, Нью-Йорк: Springer-Verlag , стр. 20, ISBN 978-3-540-21045-0
^ Роберт Эндре Тарьян (1983). Структуры данных и сетевые алгоритмы. SIAM. С. 3–7. ISBN 978-0-89871-187-5.
^ Примеры цены абстракции?, cstheory.stackexchange.com
^ Как избежать злоупотреблений и взяток в О-образном порядке. Архивировано 08.03.2017 на Wayback Machine , в блоге "Gödel's Lost Letter and P=NP" Р. Дж. Липтона, профессора компьютерных наук в Технологическом институте Джорджии, излагающего идею Роберта Седжвика.
^ Для завершения цикла for требуется дополнительный шаг, поэтому выполняется n + 1, а не n операций
^ Можно доказать по индукции , что $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$
^ Этот подход, в отличие от подхода, описанного выше, не учитывает постоянное время, затрачиваемое на циклические тесты, которые завершают соответствующие циклы, но легко доказать , что такое упущение не влияет на конечный результат.

Ссылки

Седжвик, Роберт ; Флажоле, Филипп (2013). Введение в анализ алгоритмов (2-е изд.). Эддисон-Уэсли. ISBN 978-0-321-90575-8.
Грин, Дэниел А.; Кнут, Дональд Э. (1982). Математика для анализа алгоритмов (второе изд.). Биркхойзер. ISBN 3-7643-3102-X.
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. & Stein, Clifford (2001). Введение в алгоритмы . Глава 1: Основы (Второе издание). Cambridge, MA: MIT Press и McGraw-Hill. стр. 3–122. ISBN 0-262-03293-7.
Седжвик, Роберт (1998). Алгоритмы в C, части 1-4: основы, структуры данных, сортировка, поиск (3-е изд.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-31452-6.
Кнут, Дональд . Искусство программирования . Эддисон-Уэсли.
Goldreich, Oded (2010). Computational Complexity: A Conceptual Perspective . Cambridge University Press . ISBN 978-0-521-88473-0.

Внешние ссылки

Медиа, связанные с Анализ алгоритмов на Wikimedia Commons