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

159

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

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

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

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

Рафаэль
источник
3
Спасибо авторам StackEdit за удобство написания таких длинных постов, а также моим бета-читателям FrankW , Juho , Gilles и Sebastian за помощь в устранении ряда недостатков, возникших в предыдущих проектах.
Рафаэль
1
Эй @ Рафаэль, это замечательные вещи. Я думал, что я бы предложил собрать его в формате PDF для распространения? Подобные вещи могут стать действительно полезной ссылкой.
пропал
1
@hadsed: Спасибо, я рад, что это полезно для тебя! На данный момент я предпочитаю, чтобы ссылка на этот пост была распространена вокруг. Тем не менее, пользовательский контент SE «лицензирован по cc by-sa 3.0 с обязательным указанием авторства» (см. Нижний колонтитул страницы), поэтому любой может создать PDF-файл из него при условии указания авторства.
Рафаэль
2
Я не особенно компетентен в этом, но нормально ли, что в какой-либо теме нет ссылки на теорему Мастера?
Бабу
1
@babou Я не знаю, что здесь означает "нормальный". С моей точки зрения, основная теорема здесь не годится: речь идет об анализе алгоритмов, основная теорема - очень специфический инструмент для решения (некоторых) повторений (и очень грубо при этом). Поскольку математика была рассмотрена в другом месте (например, здесь ), я решил охватить здесь только часть от алгоритма до математики. Я даю ссылки на посты, которые касаются работы по математике в моем ответе.
Рафаэль

Ответы:

134

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

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

Пример: сравнения в 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, только от его длины . Таким образом, мы можем буквально перевести (вложенные) циклы в (вложенные) суммы; переменная цикла становится переменной суммирования, и диапазон переносится. Мы получили:nfor

Ccmp(n)=i=0n2j=0ni21==n(n1)2=(n2) ,

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

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

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

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

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

Cswaps(A)=i=0n2j=0ni2C5,9(A(i,j)) .

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

Обратите внимание, что я использую вместо качестве параметра; мы скоро увидим почему. Я не добавляю и качестве параметров поскольку затраты здесь не зависят от них (то есть в модели однородных затрат ); в общем, они просто могут.AnijC5,9

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

C5,9(A(i,j))=C5(A(i,j))+{1,A(i,j)[j]>A(i,j)[j+1]0,else .

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

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

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

    Cswaps(A)i=0n2j=0ni21=n(n1)2=(n2) .

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

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

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

    Cswaps(A)i=0n2j=0ni20=0 .

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

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

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

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

    E[Cswaps]=1n!Ai=0n2j=0ni2C5,9(A(i,j))

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

    E[Cswaps]=1n!Ainv(A) .

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

    E[Cswaps]=12(n2)

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


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

Общий метод

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

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

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

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

  • Выражения

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

    CE(ψ)=c+CE1(ψ)+CE2(ψ) .

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

    • стоимость операции может быть не постоянной, а зависеть от значений и иcE1E2
    • оценка выражений может изменить состояние на многих языках,

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

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

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

    CP(ψ)=CQ(ψ)+CR(ψ/Q) .

  • Conditionals

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

    CP(ψ)=CA(ψ)+{CQ(ψ/A),A evaluates to true under ψCR(ψ/A),else

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

  • Для петель

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

    CP(ψ)=cinit_for+i=1kcstep_for+CQ(ψi{x:=xi})

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

    Обратите внимание на дополнительные константы для обслуживания цикла; переменная цикла должна быть создана ( ) и присвоена ее значениям ( ). Это актуально сcinit_forcstep_for

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

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

    CP(ψ) =CA(ψ)+{0,A evaluates to false under ψCQ(ψ/A)+CP(ψ/A;Q), else

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

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

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

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

    C1,4({i:=i0;x:=x0}) =c<+{0,x00c+=+c/+C1,4({i:=i0+1;x:=x0/2}), else

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

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

    C1,4(x)={c>,x0c>+c+=+c/+C1,4(x/2), else

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

    C1,4(ψ)=log2ψ(x)(c>+c+=+c/)+c> ,

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

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

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

    CP(ψ)=ccall+CM(ψglob{p:=x}) .

    Еще раз обратите внимание на дополнительную константу (которая на самом деле может зависеть от !). Вызовы процедур дороги из-за того, как они реализованы на реальных машинах, и иногда даже доминируют во время выполнения (например, наивно оценивая повторяемость числа Фибоначчи).ccallψ

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

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

    Cfac({n:=n0})=C1,5({n:=n0})=c+{C2({n:=n0}),n01C4({n:=n0}), else=c+{creturn,n01creturn+c+ccall+Cfac({n:=n01}), else

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

    Cfac(ψ)=ψ(n)(c+creturn)+(ψ(n)1)(c+ccall)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рафаэль
источник
1
может быть, некоторые ссылки и примеры к основной теореме (и ее расширениям ) для асимптотического анализа
Никос М.
@NikosM Здесь это выходит за рамки (см. Также комментарии к вопросу выше). Обратите внимание, что я ссылаюсь на наш справочный пост по решению рецидивов, в котором приведена основная теорема и др.
Рафаэль
@ Никос М: мои $ 0,02: хотя основная теорема работает для нескольких повторений, она не будет для многих других; Существуют стандартные методы решения рецидивов. И есть алгоритмы, для которых у нас даже не будет повторения, дающего время выполнения; некоторые передовые методы подсчета могут быть необходимы. Для тех, кто хорошо разбирается в математике, я предлагаю замечательную книгу Седжвика и Флаоджета «Анализ алгоритмов», в которой есть главы, такие как «рекуррентные отношения», «порождающие функции» и «асимптотические приближения». Структуры данных приводятся в качестве случайных примеров, и основное внимание уделяется методам!
Jay
@ Рафаэль Я не могу найти упоминания в Интернете об этом методе «Перевод кода в математику», основанном на операционной семантике. Можете ли вы предоставить какую-либо ссылку на книгу, статью или статью, которая имеет дело с этим более формально? Или, если это было разработано вами, у вас есть что-то более глубокое?
Wyvern666
1
@ Wyvern666 К сожалению, нет. Я сделал это сам, насколько любой может утверждать, что придумал что-то вроде этого. Может быть, я сам напишу процитированную работу в какой-то момент. Тем не менее, весь корпус работы вокруг аналитической комбинаторики (Flajolet, Sedgewick и многие другие) является основой этого. Они не занимаются формальной семантикой «кода» большую часть времени, но они обеспечивают математику для решения аддитивных издержек «алгоритмов» в целом. Я, честно говоря, думаю, что изложенные здесь концепции не очень глубоки - хотя математика, в которую вы можете вникнуть, такова.
Рафаэль
29

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

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

Метод

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

  1. Присвойте каждому заявлению имя / номер.
  2. Присвойте каждому утверждению некоторую стоимость .SiCi
  3. Определите для каждого оператора его количество выполнений .Siei
  4. Подсчитать общую стоимость

    C=ieiCi .

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

Помните, что шаг 3 может быть сколь угодно сложным. Обычно там, чтобы получить результаты, вам нужно работать с (асимптотическими) оценками, такими как « ».e77O(nlogn)

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

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

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,,n1}m

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

i123456789eiAABBBB+CCB1C

В частности, поскольку каждый рекурсивный вызов в строке 8 вызывает вызов в строке 3 (а один вызывается исходным вызовом из ). Кроме того, потому что условие должно проверяться один раз за итерацию, а затем еще раз, чтобы выйти из него.e8=e31foodfse6=e5+e7while

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

i123456789ei11nnn2m+n2mn12m

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

C(n,m)=(C1+C2C8)+ n(C3+C4+C5+C6+C8)+ 2m(C6+C7+C9).

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

i123456789Cin00110101

и получить

Cmem(n,m)=3n+4m .

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

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

Рафаэль
источник
8

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

  1. Используйте методы, которые мы знаем из существующих анализов, такие как нахождение границ на основе повторений, которые мы понимаем, или сумм / интегралов, которые мы можем вычислить.
  2. Измените алгоритм на то, что мы умеем анализировать.
  3. Придумайте совершенно новый подход.
Ари Трахтенберг
источник
1
Я думаю, я не вижу, как это добавляет что-нибудь полезное и новое, помимо других ответов. Методы уже описаны в других ответах. Это выглядит как комментарий, а не как ответ на вопрос.
DW
1
Я полагаю, что другие ответы доказывают, что это не искусство. Возможно, вы не сможете это сделать (например, математика), и может потребоваться некоторая креативность (в том, как применять известную математику), даже если вы это делаете, но это верно для любой задачи. Я предполагаю, что мы не стремимся создавать новую математику здесь. (На самом деле, этот вопрос или его ответы были предназначены для демистификации всего процесса.)
Рафаэль
4
@ Рафаэль Ари говорит о том, чтобы придумать распознаваемую функцию в качестве границы, а не «количество инструкций, выполненных программой» (к чему относится ваш ответ). Общий случай - искусство - нет алгоритма, который мог бы придумать нетривиальную оценку для всех алгоритмов. Общий случай, однако, представляет собой набор известных методов (таких как основная теорема).
Жиль
@ Жиль Если бы все, для чего не существует алгоритма, было искусством, мастерам (в частности, программистам) платили бы хуже.
Рафаэль
1
@AriTrachlenberg делает важный момент, хотя существует множество способов оценить сложность алгоритма. Определения обозначений Big O намекают или прямо указывают на их теоретическую природу в зависимости от автора. «Наихудший сценарий развития событий» явно оставляет место для догадок и / или новых фактов среди любого количества людей, обсуждающих эту комнату. Не говоря уже о самой природе асимптотических оценок, являющихся чем-то ... ну, конечно, неточным.
Брайан Огден,