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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предполагая, что время выполнения соответствует правилу степени, $t \approx kn a$ , коэффициент $a$ можно найти ^[8] путем проведения эмпирических измерений времени выполнения ${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 print "Это может занять некоторое время..."4 для я = от 1 до n5 для j = от 1 до i6 распечатать я * 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 ) раз, ^[9] что потребует времени T ₄ ( n + 1 ). С другой стороны, внутренний цикл управляется значением j, которое повторяется от 1 до i . При первом проходе внешнего цикла j выполняет итерацию от 1 до 1: внутренний цикл выполняет один проход, поэтому выполнение тела внутреннего цикла (шаг 6) занимает время T ₆ , а проверка внутреннего цикла (шаг 5) занимает 2 T. ₅ раз. Во время следующего прохода по внешнему циклу j выполняет итерацию от 1 до 2: внутренний цикл делает два прохода, поэтому выполнение тела внутреннего цикла (шаг 6) занимает 2 T ₆ времени, а проверка внутреннего цикла (шаг 5) занимает 3 Т ₅ раз.

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

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

который можно факторизовать ^[10] как

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

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

{\begin{aligned}&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{aligned}}

который можно расценивать как

{\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 ₇ ] равны одной единице времени в системе единиц, выбранной так, чтобы одна единица была больше или равна фактическому времени для эти шаги. Это означало бы, что время выполнения алгоритма разбивается следующим образом: ^[11]

$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 ГиБ (больше, если используется сегментированная память ), а на 64-битных машинах 2 ⁶⁴ = 16 ЭйБ. Таким образом, при ограниченном размере порядок роста (время или пространство) может быть заменен постоянным коэффициентом, и в этом смысле все практические алгоритмы равны $O (1)$ для достаточно большой константы или для достаточно малых данных.

Эта интерпретация в первую очередь полезна для функций, которые растут очень медленно: (двоичный) повторный логарифм (log ^* ) меньше 5 для всех практических данных (2 ⁶⁵⁵³⁶ бит); (двоичный) log-log (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-полный
Численный анализ
Полиномиальное время
Оптимизация программы
Профилирование (компьютерное программирование)
Масштабируемость
Сглаженный анализ
Анализ завершения - подзадача проверки того, завершится ли программа вообще.
Временная сложность — включает таблицу порядков роста для распространенных алгоритмов.
Информационная сложность

Примечания

^ «Кнут: Последние новости». 28 августа 2016 г. Архивировано из оригинала 28 августа 2016 г.
^ Альфред В. Ахо; Джон Э. Хопкрофт; Джеффри Д. Уллман (1974). Разработка и анализ компьютерных алгоритмов . Паб Аддисон-Уэсли. ISBN компании 9780201000290., раздел 1.3
^ Юрай Хромкович (2004). Теоретическая информатика: введение в автоматы, вычислимость, сложность, алгоритмика, рандомизация, связь и криптография. Спрингер. стр. 177–178. ISBN 978-3-540-14015-3.
^ Джорджио Аузиелло (1999). Сложность и аппроксимация: задачи комбинаторной оптимизации и их свойства аппроксимации. Спрингер. стр. 3–8. ISBN 978-3-540-65431-5.
^ Вегенер, Инго (2005), Теория сложности: исследование пределов эффективных алгоритмов, Берлин, Нью-Йорк: Springer-Verlag , стр. 20, ISBN 978-3-540-21045-0
^ Роберт Эндре Тарьян (1983). Структуры данных и сетевые алгоритмы. СИАМ. стр. 3–7. ISBN 978-0-89871-187-5.
^ Примеры цены абстракции?, cstheory.stackexchange.com
^ Как избежать O-злоупотреблений и взяток. Архивировано 8 марта 2017 г. в Wayback Machine , в блоге «Потерянное письмо Гёделя и P = NP» Р. Дж. Липтона, профессора компьютерных наук Технологического института Джорджии, рассказывающего об идее Роберта Седжвика.
^ для завершения цикла for требуется дополнительный шаг, следовательно, n + 1, а не n выполнений
^ По индукции можно доказать, что $1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}$
^ Этот подход, в отличие от описанного выше подхода, пренебрегает постоянным временем, затрачиваемым на тесты цикла, завершающие соответствующие циклы, но доказать, что такое упущение не влияет на конечный результат, тривиально .

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

СМИ, связанные с анализом алгоритмов, на Викискладе?