Изменения

Объясняется оно просто: для того, чтобы найти произведение матриц <tex>M_{i..j}</tex> при i=j не нужно ничего делать — это и есть сама матрица <tex>M_i</tex>. При нетривиальном случае мы перебираем все точки разбиения матрицы <tex>M_{i..j}</tex> на матрицы <tex>M_{i..k}</tex> и <tex>M_{k+1..j}</tex>, ищем кол-во количество операций, необходимое чтобы их получить и затем перемножаем для получения матрицы <tex>M_{i..j}</tex>.(Оно будет равно кол-ву операций, потраченное на решение подзадач + стоимость умножения матриц <tex>M_{i..k}M_{k+1..j}</tex>). Считаем, что размеры матриц заданы в массиве <tex>p</tex> и размер матрицы <tex>M_i</tex> равен <tex>p_{i-1} \times p_i</tex>.

Однако, если применить этот алгоритм, то обнаружим, что он работает также медленно, как и наивный способ перебирания всех скобочных последовательностей! . Делается значительное количество ненужной работы. Например, в выше описанном алгоритме, осуществляется рекурсивный вызов, чтобы найти наилучшую стоимость для подсчета ''ABC'' и ''AB''. Но нахождение наилучшей стоимости для подсчета ''ABC'' так же требует нахождения лучшей стоимости для ''AB''. Так как рекурсия растет вглубь все больше и больше, то и число ненужных повторений увеличивается. Итоговая асимптотика, как было сказано выше, равняется ''n''–ому [http://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 числу Каталана], да плюс вычисление для каждой правильной скобочной последовательности ''затрат'' на перемножение (то есть <tex>O(n \cdot C_n)</tex>). <!--<tex>N</tex>­-ое число Каталана равняется <tex> \frac{1}{n+1}{2 n \choose n} </tex> или асимптотически <tex> \frac{4^n}{n^{3/2}\sqrt{\pi}} </tex>.-->