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

Для поиска заданной записи в заданном упорядоченном списке как двоичный , так и алгоритм линейного поиска можно использовать (который игнорирует порядок). Анализ первого и второго алгоритма показывает, что требуется не более log ₂ n и n для списка размера n шагов проверки соответственно . В приведенном примере списка размером 33 поиск «Морен, Артур» занимает 5 и 28 шагов в двоичном формате (показано на рисунке). голубой ) и линейный ( пурпурный ) поиск соответственно.

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

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

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

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

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

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

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

Обычно используются две модели затрат:

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

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

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

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

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

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

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

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

n (размер списка)	Компьютер (в наносекундах )	Время выполнения компьютера B (в наносекундах )
16	8	100,000
63	32	150,000
250	125	200,000
1,000	500	250,000

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

n (размер списка)	Компьютер (в наносекундах )	Время выполнения компьютера B (в наносекундах )
16	8	100,000
63	32	150,000
250	125	200,000
1,000	500	250,000
...	...	...
1,000,000	500,000	500,000
4,000,000	2,000,000	550,000
16,000,000	8,000,000	600,000
...	...	...
63,072 × 10 12	31,536 × 10 12 нс, или 1 год	1 375 000 нс, или 1,375 миллисекунды

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

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

Основная статья: обозначение Big O

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

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

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

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

n (размер списка)	Компьютер (в наносекундах )	Локальный порядок роста (н^_)	Время выполнения компьютера B (в наносекундах )	Локальный порядок роста (н^_)
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
...	...		...

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

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

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

1    get a positive integer n from input2    if n > 103        print "This might take a while..."4    for i = 1 to n5        for j = 1 to i6            print i * j7    print "Done!"

Данному компьютеру потребуется дискретное количество времени для выполнения каждой инструкции, связанной с выполнением этого алгоритма. Скажем, считается, что действия, выполняемые на шаге 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 ).раз, что потребует времени 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}$

который можно факторизовать как

$\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}$

Как правило , можно предположить, что член высшего порядка в любой заданной функции доминирует над скоростью ее роста и, таким образом, определяет ее порядок во время выполнения. В этом примере н ² является членом высшего порядка, поэтому можно заключить, что f ( n ) = O ( 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}\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 ₇ ] равны одной единице времени в системе единиц, выбранной так, чтобы одна единица была больше или равна фактическому времени для эти шаги. Это будет означать, что время выполнения алгоритма разбивается следующим образом:

$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}).$

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

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

while file is still open:    let n = size of file    for every 100,000 kilobytes of increase in file size        double the amount of memory reserved

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

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

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

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

Анализ алгоритмов обычно фокусируется на асимптотической производительности, особенно на элементарном уровне, но в практических приложениях важны постоянные факторы, а размер реальных данных на практике всегда ограничен. Обычно ограничением является размер адресуемой памяти, поэтому на 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-полный
• Численный анализ
• Полиномиальное время
• Оптимизация программы
• Профилирование (компьютерное программирование)
• Масштабируемость
• Сглаженный анализ
• Анализ завершения - подзадача проверки того, завершится ли программа вообще.
• Временная сложность — включает таблицу порядков роста для распространенных алгоритмов.
• Информационная сложность

Ссылки

• Седжвик, Роберт ; Флажоле, Филипп (2013). Введение в анализ алгоритмов (2-е изд.). Аддисон-Уэсли. ISBN  978-0-321-90575-8 .
• Грин, Дэниел А.; Кнут, Дональд Э. (1982). Математика для анализа алгоритмов (второе изд.). Биркхойзер. ISBN  3-7643-3102-Х .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. и Стейн, Клиффорд (2001). Введение в алгоритмы . Глава 1: Фонды (второе изд.). Кембридж, Массачусетс: MIT Press и McGraw-Hill. стр. 3–122. ISBN  0-262-03293-7 .
• Седжвик, Роберт (1998). Алгоритмы на языке C, части 1–4: основы, структуры данных, сортировка, поиск (3-е изд.). Ридинг, Массачусетс: Addison-Wesley Professional. ISBN  978-0-201-31452-6 .
• Кнут, Дональд . Искусство компьютерного программирования . Аддисон-Уэсли.
• Гольдрейх, Одед (2010). Вычислительная сложность: концептуальная перспектива . Издательство Кембриджского университета . ISBN  978-0-521-88473-0 .

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

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