Изменения
Нет описания правки
Рассмотрим матрицу R. Так как отрезки <tex> i..j </tex>, где <tex> i > j </tex> мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что <tex> R[i][i] = i </tex>(так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента <tex> R[i][j] </tex> его значения лежат между <tex> R[i][j-1] </tex> (левый элемент в матрице) и <tex> R[i+1][j] </tex> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем R для отрезков длины 2, затем 3, и так далее до n. Фактически, мы будем обходить диагонали матрицы, количество которых равно n.
Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] <= \le R[i][j] <= \le R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать - <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] <= \le R[i+1][j+1] <= \le R[i+2][j+1] </tex>. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику <tex> O(n^2) </tex>.
== Использованные материалы ==
[http://www.cs.ust.hk/mjg_lib/Library/Tut_BST.pdf S.V. Nagaraj - Tutorial: Optimal binary search trees]
