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

Материал из wikixw
Перейти к навигации Перейти к поиску
Для поиска заданной записи в заданном упорядоченном списке можно использовать как бинарный, так и линейный алгоритм поиска (который игнорирует порядок). Анализ первого и второго алгоритмов показывает, что он принимает не более log 2 ( n ) и n шагов проверки, соответственно, для списка длины n . В изображенном списке примеров длиной 33, поиск "Morin, Arthur" занимает 5 и 28 шагов с бинарным (показанным в cyan ) и линейным ( пурпурным ) поиском соответственно

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

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

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

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

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

Модели затрат[править]

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

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

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

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

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

Анализ времени выполнения[править]

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

Недостатки эмпирических метрик[править]

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

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

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

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

n (размер списка) Компьютер a время выполнения(в наносекундах) Время выполнения компьютера 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 × 1012 31,536 × 10 12 НС,или 1 год 1,375 000 НС,или 1,375 миллисекунды

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

Порядки роста[править]

Основная статья: Big O notation

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

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

Эмпирические порядки роста[править]

Предполагая, что время выполнения следует степенному правилу, t ≈ k n a, коэффициент a может быть найден путем эмпирических измерений времени выполнения { 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 ) ). Другими словами, это измеряет наклон эмпирической линии на логарифмическом графике времени выполнения и размера задачи в некоторой точке размера. Если порядок роста действительно следует степенному правилу (и поэтому линия на логарифмическом графике действительно прямая), эмпирическое значение 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

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

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

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

  1. 1 получите положительное целое число n из входных данных
  2. 2 Если n > 10
  3. 3 печать " это может занять некоторое время..."
  4. 4 для i = 1-n
  5. 5 для j = 1 к i
  6. 6 печать i * j
  7. 7 печать " сделано!"

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

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

  • T 1 + T 2 + T 3 + T 7 .

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

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

  • T 6 + 2 T 6 + 3 T 6 + ⋯ + ( n − 1 ) T 6 + n T 6

который может быть учтен [10] как

  • T 6 [ 1 + 2 + 3 + ⋯ + ( n − 1 ) + n ] = T 6 [ 1 2 ( n 2 + n ) ]

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

  • 2 T 5 + 3 T 5 + 4 T 5 + ⋯ + ( n − 1 ) T 5 + n T 5 + ( n + 1 ) T 5 = T 5 + 2 T 5 + 3 T 5 + 4 T 5 + ⋯ + ( n − 1 ) T 5 + n T 5 + ( n + 1 ) T 5 − T 5

которые могут быть учтены как

  • T 5 [ 1 + 2 + 3 + ⋯ + ( n − 1 ) + n + ( n + 1 ) ] − T 5 = [ 1 2 ( n 2 + n ) ] T 5 + ( n + 1 ) T 5 − T 5 = T 5 [ 1 2 ( n 2 + n ) ] + n T 5 = [ 1 2 ( n 2 + 3 n ) ] T 5

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

  • f ( n ) = T 1 + T 2 + T 3 + T 7 + ( n + 1 ) T 4 + [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5

что сводится к следующему:

  • f ( n ) = [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7

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

  • Доказать это [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 , n ≥ n 0


  • [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ ( n 2 + n ) T 6 + ( n 2 + 3 n ) T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ( for n ≥ 0 )
  1. Пусть k-константа, большая или равная [ T 1 ..Т 7]
  • T 6 ( n 2 + n ) + T 5 ( n 2 + 3 n ) + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ k ( n 2 + n ) + k ( n 2 + 3 n ) + k n + 5 k = 2 k n 2 + 5 k n + 5 k ≤ 2 k n 2 + 5 k n 2 + 5 k n 2 ( for n ≥ 1 ) = 12 k n 2 выровнено}}}
  • Следовательно [ 1 2 ( n 2 + n ) ] T 6 + [ 1 2 ( n 2 + 3 n ) ] T 5 + ( n + 1 ) T 4 + T 1 + T 2 + T 3 + T 7 ≤ c n 2 , n ≥ n 0 for c = 12 k , n 0 = 1

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

  • 4 + ∑ i = 1 n i ≤ 4 + ∑ i = 1 n n = 4 + n 2 ≤ 5 n 2 ( for n ≥ 1 ) = O ( n 2 ) .

Анализ темпов роста прочих ресурсов[править]

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

пока файл все еще открыт:

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

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

Релевантность[править]

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

Постоянные факторы[править]

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

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

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

Смотрите также[править]

Источник — https://wikixw.ru/index.php?title=Анализ_алгоритмов&oldid=11115