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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Предполагая, что время выполнения соответствует правилу мощности, t ≈ k n^а, коэффициент а можно найти ^[8] путем проведения эмпирических измерений времени выполнения ${\displaystyle \{t_{1},t_{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})}$. Другими словами, это измеряет наклон эмпирической линии на график – журнал времени выполнения по сравнению с размером проблемы, в какой-то момент. Если порядок роста действительно следует силовому правилу (и поэтому линия на графике логарифм – логарифм действительно прямая линия), эмпирическое значение а будет оставаться постоянным в разных диапазонах, а если нет, он изменится (а линия представляет собой изогнутую линию), но все же может служить для сравнения любых двух заданных алгоритмов относительно их эмпирические локальные порядки роста поведение. Применяется к приведенной выше таблице:

п (размер списка)	Компьютер Время выполнения (в наносекунды )	Местный порядок роста (п ^ _)	Время выполнения компьютера 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    получить положительное целое число n из ввода2    если n> 103 Распечатать «Это может занять некоторое время ...» 4 за я = 1 к n5 за j = 1 к i6 Распечатать я * j7 Распечатать "Выполнено!"

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}\\=&T_{5}\left[{\frac {1}{2}}(n^{2}+n)\right]+nT_{5}\\=&\left[{\frac {1}{2}}(n^{2}+3n)\right]T_{5}\end{aligned}}}$

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

${\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{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 быть константой, большей или равной [Т₁..Т₇]

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

Следовательно ${\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}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

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

• Седжвик, Роберт; Флажоле, Филипп (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.

внешняя ссылка

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