Есть ли система за магией анализа алгоритма?

Существует множество вопросов о том, как анализировать время выполнения алгоритмов (см., Например, анализ времени выполнения и анализ алгоритма ). Многие из них похожи, например, те, которые запрашивают анализ затрат на вложенные циклы или алгоритмы «разделяй и властвуй», но большинство ответов, похоже, сделаны специально.

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

Существует ли структурированный общий метод анализа стоимости алгоритмов? Стоимость может быть временем выполнения (сложность времени) или какой-либо другой мерой стоимости, такой как количество выполненных сравнений, сложность пространства или что-то еще.

^{Предполагается, что это станет справочным вопросом, на который можно указать новичкам; следовательно, его более широкий, чем обычно, объем. Пожалуйста, позаботьтесь о том, чтобы дать общие, дидактически представленные ответы, которые иллюстрируются хотя бы одним примером, но тем не менее охватывают многие ситуации. Спасибо!}

Перевод кода в математику

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

Пример: сравнения в Bubblesort

Рассмотрим этот алгоритм, который сортирует данный массив A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

Допустим, мы хотим выполнить обычный анализ алгоритма сортировки, то есть посчитать количество сравнений элементов (строка 5). Сразу отметим, что эта величина не зависит от содержимого массива A, только от его длины . Таким образом, мы можем буквально перевести (вложенные) циклы в (вложенные) суммы; переменная цикла становится переменной суммирования, и диапазон переносится. Мы получили:$n$for

$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$ ,

где - стоимость каждого исполнения строки 5 (которую мы считаем).$1$

Пример: свопы в Bubblesort

Я обозначу через подпрограмма , которая состоит из линий до и по расходы на выполнение этой подпрограммы (один раз). C i , $P_{i,j}$ij$C_{i,j}$

Теперь предположим, что мы хотим считать свопы , то есть как часто выполняется . Это «базовый блок», то есть подпрограмма, которая всегда выполняется атомарно и имеет некоторую постоянную стоимость (здесь, ). Заключение таких блоков является одним из полезных упрощений, которое мы часто применяем, не задумываясь и не говоря об этом.$P_{6,8}$$1$

С переводом, аналогичным приведенному выше, мы приходим к следующей формуле:

$\qquad\displaystyle C_{\text{swaps}}(A) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$ .

( i , j ) P 5 , $A^{(i,j)}$ обозначает состояние массива перед -й итерацией .$(i,j)$$P_{5,9}$

Обратите внимание, что я использую вместо качестве параметра; мы скоро увидим почему. Я не добавляю и качестве параметров поскольку затраты здесь не зависят от них (то есть в модели однородных затрат ); в общем, они просто могут.$A$$n$$i$$j$$C_{5,9}$

Очевидно, что затраты на зависят от содержания (значения и , в частности), поэтому мы должны это учитывать. Теперь перед нами стоит задача: как нам «развернуть» ? Ну, мы можем сделать зависимость от содержимого явной:$P_{5,9}$$A$A[j]A[j+1]$C_{5,9}$$A$

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) + \begin{cases} 1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]} \\ 0 &, \text{else} \end{cases}$ .

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

1. Худший случай

   Просто взглянув на сумму и заметив, что , мы можем найти тривиальную верхнюю оценку стоимости:$C_{5,9}(A^{(i,j)}) \in \{0,1\}$

   $\qquad\displaystyle C_{\text{swaps}}(A) \leq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \frac{n(n-1)}{2} = \binom{n}{2}$ .

   Но может ли это произойти , то есть есть ли для этой верхней границы? Как оказалось, да: если мы вводим отсортированный в обратном порядке массив попарно различных элементов, каждая итерация должна выполнять свопинг. Таким образом, мы вывели точное число наихудших вариантов свопов Bubblesort.$A$

2. Лучший случай

   И наоборот, существует тривиальная нижняя граница:

   $\qquad\displaystyle C_{\text{swaps}}(A) \geq \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0 = 0$ .

   Это также может произойти: в массиве, который уже отсортирован, Bubblesort не выполняет ни одного обмена.

3. Средний случай

   В худшем и лучшем случае откроется довольно большой разрыв. Но каково типичное количество свопов? Чтобы ответить на этот вопрос, нам нужно определить, что означает «типичный». Теоретически, у нас нет причин предпочитать один вход другому, поэтому мы обычно предполагаем равномерное распределение по всем возможным входам, то есть каждый вход одинаково вероятен. Мы ограничимся массивами с попарно различными элементами и, таким образом, примем модель случайной перестановки .

   Затем мы можем переписать наши расходы следующим образом²:

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

   Теперь нам нужно выйти за рамки простых манипуляций с суммами. Рассматривая алгоритм, мы отмечаем, что каждый своп удаляет ровно одну инверсию в (мы всегда обмениваем только соседей3). То есть, число свопов , выполненных на именно число инверсий из . Таким образом, мы можем заменить внутренние две суммы и получить$A$$A$$\operatorname{inv}(A)$$A$

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$ .

   К счастью для нас, среднее число инверсий было определено как

   $\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

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

1. Обратите внимание, что алгоритм был тщательно сформулирован, так что «последняя» итерация i = n-1внешнего цикла, который ничего не делает, не выполняется.
2. « » - это математическое обозначение «ожидаемого значения», которое здесь является просто средним.$\mathbb{E}$
3. Таким образом, мы узнаем, что ни один алгоритм, который меняет местами только соседние элементы, не может быть асимптотически быстрее, чем Bubblesort (даже в среднем) - число инверсий является нижней границей для всех таких алгоритмов. Это относится, например , к Вставки Сортировка и выбора Сортировка .

Общий метод

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

Мы обозначаем текущее состояние (представьте его как набор переменных). Когда мы выполняем программу, начинающуюся в состоянии , мы в состоянии (при условии, что завершается).$\psi$P$\psi$$\psi / \mathtt{P}$P

• Индивидуальные заявления

  Учитывая только одно утверждение S;, вы назначаете его стоит . Обычно это будет постоянная функция.$C_S(\psi)$

• Выражения

  Если у вас есть выражение Eформы E1 ∘ E2(скажем, арифметическое выражение, где ∘может быть сложение или умножение, вы рекурсивно складываете расходы:

  $\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$ .

  Обратите внимание, что

  • стоимость операции может быть не постоянной, а зависеть от значений и и$c_{\circ}$$E_1$$E_2$
  • оценка выражений может изменить состояние на многих языках,

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

• Последовательность

  Учитывая программу Pкак последовательность программ Q;R, вы добавляете затраты к

  $\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$ .

• Conditionals

  Учитывая программу Pвида if A then Q else R end, расходы зависят от состояния:

  $\qquad\displaystyle C_P(\psi) = C_A(\psi) + \begin{cases} C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\ C_R(\psi/\mathtt{A}) &, \text{else} \end{cases}$

  В целом, оценка Aможет очень хорошо изменить состояние, отсюда и обновление стоимости отдельных филиалов.

• Для петель

  Учитывая программу Pформы for x = [x1, ..., xk] do Q end, назначьте расходы

  $\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

  где - это состояние до обработки значения , т. е. после итерации с установленным значением , ..., .$\psi_i$Qxixx1xi-1

  Обратите внимание на дополнительные константы для обслуживания цикла; переменная цикла должна быть создана ( ) и присвоена ее значениям ( ). Это актуально с$c_{\text{init_for}}$$c_{\text{step_for}}$

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

• В то время как-Loops

  Учитывая программу Pформы while A do Q end, назначьте расходы

  $\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) + \begin{cases} 0 &, \mathtt{A} \text{ evaluates to false under } \psi \\ C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else} \end{cases}$

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

  Пример: рассмотрим этот короткий алгоритм:

  while x > 0 do    1
    i += 1          2
    x = x/2         3
  end               4
  

  Применяя правило, мы получаем

  $\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< + \begin{cases} 0 &, x_0 \leq 0 \\ c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else} \end{cases}$

  с некоторыми постоянными затратами для отдельных утверждений. Мы неявно предполагаем, что они не зависят от состояния (значения и ); это может или не может быть правдой в «реальности»: подумайте о переполнении!$c_{\dots}$ix

  Теперь мы должны решить эту повторяемость для . Отметим, что ни количество итераций, ни стоимость тела цикла не зависят от значения , поэтому мы можем его отбросить. Мы остались с этим повторением:$C_{1,4}$i

  $\qquad\displaystyle C_{1,4}(x) = \begin{cases} c_> &, x \leq 0 \\ c_> + c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else} \end{cases}$

  Это решает с элементарными средствами для

  $\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> + c_{+=} + c_/) + c_>$ ,

  повторное введение полного состояния символически; если , то .$\psi = \{ \dots, x := 5, \dots\}$$\psi(x) = 5$

• Процедурные вызовы

  Учитывая программу Pвида M(x)для некоторого параметра (ов), xгде Mесть процедура с (именованным) параметром p, назначьте затраты

  $\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$ .

  Еще раз обратите внимание на дополнительную константу (которая на самом деле может зависеть от !). Вызовы процедур дороги из-за того, как они реализованы на реальных машинах, и иногда даже доминируют во время выполнения (например, наивно оценивая повторяемость числа Фибоначчи).$c_{\text{call}}$$\psi$

  Я затушевываю некоторые семантические проблемы, которые у вас могут возникнуть с состоянием здесь. Вы захотите различать глобальное состояние и такие локальные для вызовов процедур. Давайте просто предположим, что мы передаем только глобальное состояние и Mполучаем новое локальное состояние, инициализируемое установкой значения pto x. Кроме того, это xможет быть выражение, которое мы (обычно) предполагаем оценить перед его передачей.

  Пример: рассмотрим процедуру

  fac(n) do                  
    if ( n <= 1 ) do         1
      return 1               2
    else                     3
      return n * fac(n-1)    4
    end                      5
  end                        
  

  Согласно правилу (ам), мы получаем:

  $\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\}) &= C_{1,5}(\{n := n_0\}) \\ &= c_{\leq} + \begin{cases} C_2(\{n := n_0 \}) &, n_0 \leq 1 \\ C_4(\{n := n_0 \}) &, \text{ else} \end{cases} \\ &= c_{\leq} + \begin{cases} c_{\text{return}} &, n_0 \leq 1 \\ c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\}) &, \text{ else} \end{cases} \end{align*}$

  Обратите внимание, что мы игнорируем глобальное состояние, поскольку facявно не имеет доступа к любому. Это конкретное повторение легко решить

  $\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}}) + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

Мы рассмотрели языковые возможности, с которыми вы столкнетесь, в типичном псевдокоде. Остерегайтесь скрытых затрат при анализе псевдокода высокого уровня; если сомневаешься, развернись. Запись может показаться громоздкой и, безусловно, является вопросом вкуса; перечисленные понятия нельзя игнорировать. Однако, имея некоторый опыт, вы сможете сразу увидеть, какие части штата имеют значение для какого показателя стоимости, например, «размер проблемы» или «количество вершин». Остальное можно отбросить - это значительно упрощает вещи!

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

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

Примечание об асимптотической стоимости

То, что вы обычно найдете в литературе и на веб-сайтах, это «анализ Big-Oh». Подходящим термином является асимптотический анализ, который означает, что вместо получения точных затрат, как мы делали в примерах, вы даете затраты только до постоянного фактора и в пределе (грубо говоря, «для больших »).$n$

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

Вот как асимптотический анализ относится к этому подходу.

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

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

2. Выполните анализ, используя количество выполнений этой операции в качестве стоимости.
3. При упрощении допускайте оценки. Позаботьтесь о том, чтобы оценки допускались только в том случае, если ваша цель - верхняя граница ( ) соответственно. снизу, если вы хотите нижние границы ( ).$O$$\Omega$

Убедитесь, что вы понимаете значение символов Ландау . Помните, что такие границы существуют для всех трех случаев ; использование не подразумевает анализ наихудшего случая.$O$

дальнейшее чтение

Есть много других проблем и приемов в анализе алгоритмов. Вот некоторые рекомендуемые чтения.

• Как придумать время выполнения алгоритмов?
  Как описать алгоритмы, доказать и проанализировать их?
• Зачем использовать сравнения вместо времени выполнения для сравнения двух алгоритмов?
  Как мы можем предположить, что основные операции над числами занимают постоянное время?
  Что составляет одну единицу времени в анализе времени выполнения?
• Решение или аппроксимация рекуррентных отношений для последовательностей чисел
• Основы амортизированного анализа

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

Количество выполненных заявлений

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

Метод

Это довольно просто в принципе:

1. Присвойте каждому заявлению имя / номер.
2. Присвойте каждому утверждению некоторую стоимость .$S_i$$C_i$
3. Определите для каждого оператора его количество выполнений .$S_i$$e_i$

4. Подсчитать общую стоимость

   $\qquad\displaystyle C = \sum_{i} e_i \cdot C_i$ .

Вы можете вставить оценки и / или символические величины в любой точке, ослабляя соотв. обобщая результат соответственно.

Помните, что шаг 3 может быть сколь угодно сложным. Обычно там, чтобы получить результаты, вам нужно работать с (асимптотическими) оценками, такими как « ».$e_{77} \in O(n \log n)$

Пример: поиск в глубину

Рассмотрим следующий алгоритм обхода графа:

dfs(G, s) do
  // assert G.nodes contains s
  visited = new Array[G.nodes.size]     1
  dfs_h(G, s, visited)                  2
end 

dfs_h(G, s, visited) do
  foo(s)                                3
  visited[s] = true                     4

  v = G.neighbours(s)                   5
  while ( v != nil ) do                 6
    if ( !visited[v] ) then             7
      dfs_h(G, v, visited)              8
    end
    v = v.next                          9
  end
end

Мы предполагаем, что (неориентированный) граф задается списками смежности на узлах . Пусть будет количеством ребер.$\{0,\dots,n-1\}$$m$

Просто взглянув на алгоритм, мы увидим, что некоторые операторы выполняются так же часто, как и другие. Мы вводим некоторые заполнители , и для счетчиков выполнения :$A$$B$$C$$e_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & A & A & B & B & B & B+C & C & B-1 & C \end{array}$

В частности, поскольку каждый рекурсивный вызов в строке 8 вызывает вызов в строке 3 (а один вызывается исходным вызовом из ). Кроме того, потому что условие должно проверяться один раз за итерацию, а затем еще раз, чтобы выйти из него.$e_8 = e_3-1$foodfs$e_6 = e_5 + e_7$while

Понятно, что . Теперь во время доказательства корректности мы покажем, что он выполняется ровно один раз для каждого узла; то есть . Но затем мы перебираем каждый список смежности ровно один раз, и каждое ребро подразумевает всего две записи (по одной для каждого инцидентного узла); мы получаем итераций в общей сложности. Используя это, мы выводим следующую таблицу:$A=1$foo$B = n$$C = 2m$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline e_i & 1 & 1 & n & n & n & 2m + n & 2m & n-1 & 2m \end{array}$

Это приводит нас к общей стоимости точно

$\qquad\begin{align*} C(n,m) = (C_1 + C_2 - C_8) &+\ n \cdot (C_3 + C_4 + C_5 + C_6 + C_8) \\ &+\ 2m \cdot (C_6 + C_7 + C_9) \;. \end{align*}$

Создавая подходящие значения для мы можем получить более конкретные затраты. Например, если мы хотим посчитать доступ к памяти (за слово), мы бы использовали$C_i$

$\qquad\begin{array}{c|ccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline C_i & n & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$

и получить

$\qquad\displaystyle C_{\text{mem}}(n,m) = 3n + 4m$ .

дальнейшее чтение

Смотрите внизу моего другого ответа .

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

1. Используйте методы, которые мы знаем из существующих анализов, такие как нахождение границ на основе повторений, которые мы понимаем, или сумм / интегралов, которые мы можем вычислить.
2. Измените алгоритм на то, что мы умеем анализировать.
3. Придумайте совершенно новый подход.