Запоминаемая версия умножения цепочки матриц

Вот программа для запомненной версии программы умножения цепочек матриц из Введение в алгоритмы Кормена и т. Д.

MEMOIZED-MATRIX-CHAIN(p)

1 n  length[p] - 1   
2 for i = 1 to n
3      do for j = i to n
4             do m[i, j]  = infinity   
5 return LOOKUP-CHAIN(p, 1, n)

LOOKUP-CHAIN(p, i, j)

1 if m[i,j] < infinity
2    then return m[i, j]
3 if i = j
4    then m[i, j]  0
5    else for k =  i to j - 1
6             do q = LOOKUP-CHAIN(p, i, k) +
                     LOOKUP-CHAIN(p, k + 1, j) +
                     p(i - 1)* p(k) *p(j) 
7                if q < m[i, j]
8                   then m[i, j] = q
9 return m[i, j]

Это упоминается в описании, так как мы можем разделить вызовы LOOKUP-CHAIN ​​на два типа:

  1. вызовы, в которых m[i,j] = бесконечность, так что выполняются строки 3-9.
  2. вызовы, в которых m[i,j] меньше бесконечности, так что LOOKUP-CHAIN ​​просто возвращает в строке

Имеется n квадратных вызовов первого типа, по одному на запись в таблице. Все вызовы второго типа выполняются как рекурсивные вызовы вызовами первого типа. Всякий раз, когда данный вызов LOOKUP-CHAIN ​​делает рекурсивные вызовы, он делает их "n". Следовательно, всего имеется n вызовов куба второго типа. Каждый вызов второго типа занимает O(1) времени, а каждый вызов первого типа занимает O(n) времени плюс затраты на рекурсивные вызовы. Общее время равно O(n куб).

мой вопрос

  1. Что автор имеет в виду под «Все вызовы второго типа выполняются как рекурсивные вызовы вызовами первого типа»?
  2. Как автор придумал, что «данный вызов LOOKUP-CHAIN ​​делает рекурсивные вызовы, он делает «n» из них» в приведенном выше предложении?

Спасибо!


algorithm dynamic-programming
person venkysmarty    schedule 10.11.2011    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

  2. Цикл for в строке 5 функции LOOKUP-CHAIN выполняет не более n итераций (поскольку 1≤i≤j≤n), поэтому он может выполнять до 2n=O(n) рекурсивных вызовов.

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

  • Внутренний узел соответствует «типу 2», их не может быть больше n² (из-за мемоизации), и каждый из них выполняет O(n) операций.

  • Листья соответствуют «типу 1». Поскольку существует не более n² внутренних узлов с не более чем 2n дочерними узлами, поэтому у вас не может быть более 2n³ листьев, и каждый из них выполняет θ(1) операций.

person adl    schedule 11.11.2011