Анализ алгоритмов - Analysis of algorithms

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1    get a positive integer n from input
2    if n > 10
3        print "This might take a while..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Done!"

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

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

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

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

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

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

который можно разложить на множители как

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

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

${\ displaystyle {\ 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} \ конец {выровнено}}}$

который можно разложить на множители как

${\ Displaystyle {\ begin {align} & T_ {5} \ left [1 + 2 + 3 + \ cdots + (n-1) + n + (n + 1) \ right] -T_ {5} \\ = & \ слева [{\ frac {1} {2}} (n ^ {2} + n) \ right] T_ {5} + (n + 1) T_ {5} -T_ {5} \\ = & T_ {5} \ left [{\ frac {1} {2}} (n ^ {2} + n) \ right] + nT_ {5} \\ = & \ left [{\ frac {1} {2}} (n ^ {2} + 3n) \ right] T_ {5} \ end {align}}}$

Следовательно, общее время работы этого алгоритма составляет:

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

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

${\ displaystyle 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 ² ). Формально это можно доказать следующим образом:

Докажи это ${\ displaystyle \ 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}}$

${\ displaystyle {\ begin {align} & \ 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 {align}}}$

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

${\ displaystyle {\ begin {align} & 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 {выровнено}} }$

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

${\ displaystyle 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 EiB. Таким образом, учитывая ограниченный размер, порядок роста (время или пространство) может быть заменен постоянным множителем, и в этом смысле все практические алгоритмы равны O (1) для достаточно большой константы или для достаточно малых данных.

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

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

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

• Амортизированный анализ
• Анализ параллельных алгоритмов
• Асимптотическая вычислительная сложность
• Лучший, худший и средний случай
• Обозначение Big O
• Теория вычислительной сложности
• Основная теорема (анализ алгоритмов)
• NP-Complete
• Численный анализ
• Полиномиальное время
• Оптимизация программы
• Профилирование (компьютерное программирование)
• Масштабируемость
• Сглаженный анализ
• Анализ завершения - подзадача проверки того, завершится ли программа вообще
• Сложность времени - включает таблицу порядков роста для общих алгоритмов
• Информационная сложность

Заметки

Рекомендации

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

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

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