Временная сложность умножения матричной цепочки

Question

Решена проблема в «Введение в алгоритмы», Cormen, et. и др. Ch. 15, раздел 15.2: Умножение матричной цепочки. Pg. 373.

Цель состоит в том, чтобы заключить в скобки матричный цепной продукт A1.A2.A3 ..... A, так что существует минимальное количество скалярных умножений.
Для Ai.Ai + 1 .... Ak.Ak + 1 ..... Аж,
матрица Ai имеет размерность пи-1xpi Автор приходит с рекурсией

m[i,j] = 0 if i=j 
     = min {m[i,k] + m[k+1] + pi-1.pk.pj} where i goes from k to (j-1) if i<j 

(m [i, j] - минимальное число скалярных умножений, требуемых для произведения Ai .... Aj)

До сих пор я понял, но тогда сложность времени, которую он говорит, равна O (n^3) ,
Когда я смотрю на псевдокод, для петель есть 3, поэтому он правильный. Но я не понимаю этого интуитивно, глядя на рекурсию.

Может ли кто-нибудь помочь?

Answer 1

Окончательное решение - рассчитать m[0,N]. Но все значения m[i,j] должны быть рассчитаны до m[0,N]. Это делает его O(N^2).

Из формулы рекурсии вы можете увидеть каждый из m[i,j] потребностей расчета O(N) сложности.

Так O(N^3) для полного решения.

Answer 2

Для любой заданной задачи MCM могут существовать уникальные подзадачи O (n^2), и для каждой такой подзадачи может быть возможно разбиение O (n).

Таким образом, это O (n^3).