Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Орфографическая ошибка)
м (Заменил ссылку; заменил дефисы на тире;взял переменные и константы в Тех; исправил знаки неравенств; оформил источники информации)
Строка 3: Строка 3:
 
{{Определение  
 
{{Определение  
 
| definition =
 
| definition =
[[Оптимальный префиксный код]] с сохранением порядка(англ. ''order-preserving code'', ''alphabetic code'').
+
[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка (англ. ''order-preserving code'', ''alphabetic code'').
 
   
 
   
Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка(алфавитным), если соблюдаются:
+
Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
# Условие порядка - <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
+
# Условие порядка {{---}} <tex> \forall i, j : c_i < c_j \iff p_i < p_j </tex>. То есть, если символ <tex>c_i </tex> лексикографически меньше символа <tex> c_j </tex>, его код также будет [[лексикографический порядок | лексикографически]] меньше, и наоборот.
# Условие оптимальности - <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> - минимально, где <tex> f_i </tex> - частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> - длина его кода.
+
# Условие оптимальности {{---}} <tex> \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| </tex> {{---}} минимально, где <tex> f_i </tex> {{---}} частота встречаемости символа <tex> c_i </tex> в тексте, а <tex> |p_i| </tex> {{---}} длина его кода.
 
}}
 
}}
  
 
== Алгоритм ==
 
== Алгоритм ==
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от i до j.
+
Решим задачу, используя ДП на подотрезках. Пусть в ячейке <tex> D[i][j] </tex> хранится минимальная стоимость кодового дерева для отрезка алфавита от <tex> i </tex> до <tex> j </tex>.
  
 
Тогда пересчет <tex> D[i][j] </tex> будет происходить так:
 
Тогда пересчет <tex> D[i][j] </tex> будет происходить так:
Строка 21: Строка 21:
 
Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1.
 
Добавочный член <tex>w[i][j] = \sum\limits_{t = i}^{j} f_t </tex> возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов <tex> c_i .. c_j </tex> также увеличиваются на 1.
  
Тогда такое ''наибольшее'' k, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.
+
Тогда такое ''наибольшее'' <tex> k </tex>, на котором достигается этот минимум, называется точкой разреза для отрезка <tex> i..j </tex>. Пусть в ячейке <tex> R[i][j] </tex> хранится точка разреза на отрезке <tex> i..j </tex>.
  
 
Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.
 
Если разрез происходит по какому-то определенному индексу <tex> q </tex> , такой разрез обозначим <tex> D_q[i][j] </tex>.
  
Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмена - обходом по построенному дереву.
+
Таким образом, получили алгоритм, работающий за <tex> O(n^3) </tex>. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана {{---}} обходом по построенному дереву.
  
 
Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.
 
Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до <tex> O(n^2) </tex>.
Строка 34: Строка 34:
 
{{Определение
 
{{Определение
 
| definition=
 
| definition=
Функция a удовлетворяет '''неравенству четырехугольника(quadrangle inequation)''', если
+
Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если
: <tex>\forall i \le i' \le j \le j' : a[i][j] + a[i'][j'] \le a[i'][j] + a[i][j']</tex>
+
: <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j']</tex>
 
}}
 
}}
  
Строка 41: Строка 41:
 
{{Лемма
 
{{Лемма
 
| statement=
 
| statement=
w удовлетворяет неравенству четырехугольника.
+
<tex> w </tex> удовлетворяет неравенству четырехугольника.
 
| proof=
 
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> - простая арифметическая сумма. Тогда:
+
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> {{---}} простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \le w[i'][j] + w[i][j']</tex>
+
: <tex> w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j']</tex>
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \le (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
+
: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leq 0 </tex>, что является верным. Лемма доказана.
+
Получили <tex> 0 \leqslant 0 </tex>, что является верным. Лемма доказана.
 
}}
 
}}
  
Строка 52: Строка 52:
 
{{Лемма
 
{{Лемма
 
| statement=
 
| statement=
Если w удовлетворяет неравенству четырехугольника, то D также удовлетворяет неравенству четырехугольника, то есть:
+
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </tex> также удовлетворяет неравенству четырехугольника, то есть:
  
<tex>\forall i \le i' \le j \le j' : D[i][j] + D[i'][j'] \le D[i'][j] + D[i][j'] </tex>
+
<tex>\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] </tex>
 
| proof=
 
| proof=
 
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
 
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
Строка 61: Строка 61:
 
# <tex> i' = j </tex>
 
# <tex> i' = j </tex>
 
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к:
 
#: <tex> i < i' = j < j' </tex>. Тогда неравенство четырехугольника сводится к:
#: <tex> D[i][j] + D[j][j'] \le D[i][j'] </tex>
+
#: <tex> D[i][j] + D[j][j'] \leqslant D[i][j'] </tex>
 
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая:
 
#: Пусть <tex> k = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> k \le j </tex>
+
## <tex> k \leqslant j </tex>
##: <tex> D[i][j] + D[j][j'] \le w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - по определению <tex> D[i][j] </tex>
+
##: <tex> D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} по определению <tex> D[i][j] </tex>
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - так как <tex> w[i][j'] >= w[i][j] </tex>
+
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> {{---}} так как <tex> w[i][j'] \geqslant w[i][j] </tex>
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j'] </tex> - по индукционному предположению для D
+
##: <tex> \leqslant w[i][j'] + D[i][k-1] + D[k][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \le D[i][j'] </tex> - по определению <tex> D[i][j'] </tex>
+
##: <tex> \leqslant D[i][j'] </tex> {{---}} по определению <tex> D[i][j'] </tex>
## <tex> k \ge j </tex> - аналогичный предыдущему случай.
+
## <tex> k \geqslant j </tex> {{---}} аналогичный предыдущему случай.
 
# <tex> i' < j </tex>
 
# <tex> i' < j </tex>
 
#: <tex> i < i' < j < j' </tex>  
 
#: <tex> i < i' < j < j' </tex>  
 
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая:
 
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два симметричных случая:
## <tex> z \le y </tex>
+
## <tex> z \leqslant y </tex>
##: Получили <tex> i \le z \le y \le j </tex>. Запишем:
+
##: Получили <tex> i \leqslant z \leqslant y \leqslant j </tex>. Запишем:
##: <tex> D[i'][j'] + D[i][j] \le D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
+
##: <tex> D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
##: <tex> \le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> - по неравенству четырехугольника для <tex> w </tex>
+
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> {{---}} по неравенству четырехугольника для <tex> w </tex>
##: <tex> \le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> - по индукционному предположению для D
+
##: <tex> \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> {{---}} по индукционному предположению для <tex> D </tex>
##: <tex> \le D[i][j'] + D[i'][j] </tex> - по определению D
+
##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex>
## <tex> z \ge y </tex> доказывается аналогично.
+
## <tex> z \geqslant y </tex> доказывается аналогично.
 
Лемма доказана.
 
Лемма доказана.
 
}}
 
}}
Строка 87: Строка 87:
 
Монотонность точки разреза
 
Монотонность точки разреза
 
| statement=
 
| statement=
Если w удовлетворяет неравенству четырехугольника, то:
+
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:
  
<tex> \forall i \le j : R[i][j] \le R[i][j+1] \le R[i+1][j+1] </tex>   
+
<tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex>   
 
| proof=
 
| proof=
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \le R[i][j+1] </tex>(вторая часть доказывается аналогично):
+
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \leqslant R[i][j+1] </tex>(вторая часть доказывается аналогично):
  
Так как <tex> R[i][j] </tex> - максимальный индекс, в котором достигается минимум, достаточно показать, что:
+
Так как <tex> R[i][j] </tex> {{---}} максимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \le k' \le j: [D_{k'}[i][j] \le D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \le D_k[i][j+1]] </tex> - фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
+
: <tex> \forall i < k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] </tex> {{---}} фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
 
Докажем более сильное неравенство:
 
Докажем более сильное неравенство:
: <tex> \forall i < k \le k' \le j: D_k[i][j] - D_{k'}[i][j] \le D_k[i][j+1] - D_{k'}[i][j+1] </tex>
+
: <tex> \forall i < k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] </tex>
  
: <tex> D_k[i][j] + D_{k'}[i][j+1] \le D_k[i][j+1] + D_{k'}[i][j] </tex>
+
: <tex> D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] </tex>
  
: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \le (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> - по определению D
+
: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> {{---}} по определению <tex> D </tex>
  
: <tex> D[k][j] + D[k'][j+1] \le D[k][j+1] + D[k'][j] </tex> - получили неравенство четырехугольника для <tex> k \le k' \le j \le j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
+
: <tex> D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] </tex> {{---}} получили неравенство четырехугольника для <tex> k \leqslant k' \leqslant j \leqslant j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
 
}}
 
}}
  
 
== Объяснение квадратичной асимптотики ==
 
== Объяснение квадратичной асимптотики ==
Рассмотрим матрицу 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 </tex>. Так как отрезки <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> (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем <tex> R </tex> для отрезков длины 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>.
+
Рассмотрим элемент <tex> R[i][j] </tex>. Для него выполняется <tex> R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] </tex>. Следующий элемент, который мы будем пересчитывать {{---}} <tex> R[i+1][j+1] </tex>. Для него выполняется <tex> R[i+1][j] \leqslant R[i+1][j+1] \leqslant 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]
+
[http://www.cs.ust.hk/mjg_lib/Library/Tut_BST.pdf S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees]
  
Д. Э. Кнут - Искусство программирования: Сортировка и поиск, Том 3
+
''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005.
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Динамическое программирование]]
 
[[Категория:Динамическое программирование]]

Версия 22:11, 5 января 2017

Определение

Определение:
Оптимальный префиксный код с сохранением порядка (англ. order-preserving code, alphabetic code).

Пусть у нас есть алфавит [math] \Sigma [/math]. Каждому символу [math]c_i [/math] сопоставим его код [math] p_i [/math]. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:

  1. Условие порядка — [math] \forall i, j : c_i \lt c_j \iff p_i \lt p_j [/math]. То есть, если символ [math]c_i [/math] лексикографически меньше символа [math] c_j [/math], его код также будет лексикографически меньше, и наоборот.
  2. Условие оптимальности — [math] \sum\limits_{i = 1}^{|\Sigma|} f_i \cdot |p_i| [/math] — минимально, где [math] f_i [/math] — частота встречаемости символа [math] c_i [/math] в тексте, а [math] |p_i| [/math] — длина его кода.


Алгоритм

Решим задачу, используя ДП на подотрезках. Пусть в ячейке [math] D[i][j] [/math] хранится минимальная стоимость кодового дерева для отрезка алфавита от [math] i [/math] до [math] j [/math].

Тогда пересчет [math] D[i][j] [/math] будет происходить так:

[math] D[i][j] = \min\limits_{k = i}^{j - 1} \left ( D[i][k] + D[k + 1][j] \right ) + w[i][j][/math]

Базой динамики будет [math] D[i][i] = 0 [/math]

Добавочный член [math]w[i][j] = \sum\limits_{t = i}^{j} f_t [/math] возникает от того что каждым объединением двух подотрезков мы увеличиваем высоту дерева на 1, а значит, и длины всех кодов символов [math] c_i .. c_j [/math] также увеличиваются на 1.

Тогда такое наибольшее [math] k [/math], на котором достигается этот минимум, называется точкой разреза для отрезка [math] i..j [/math]. Пусть в ячейке [math] R[i][j] [/math] хранится точка разреза на отрезке [math] i..j [/math].

Если разрез происходит по какому-то определенному индексу [math] q [/math] , такой разрез обозначим [math] D_q[i][j] [/math].

Таким образом, получили алгоритм, работающий за [math] O(n^3) [/math]. Коды каждого символа можно легко получить так же, как в алгоритме Хаффмана — обходом по построенному дереву.

Если доказать монотонность точки разреза, то можно уменьшить асимптотику алгоритма до [math] O(n^2) [/math].

Монотонность точки разреза

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


Определение:
Функция [math] a [/math] удовлетворяет неравенству четырехугольника (англ. quadrangle inequation), если
[math]\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[i][j'][/math]


Лемма:
[math] w [/math] удовлетворяет неравенству четырехугольника.
Доказательство:
[math]\triangleright[/math]

Заметим, что [math] w[i][j] = w[i][t] + w[t+1][j] [/math], так как [math] w[i][j] [/math] — простая арифметическая сумма. Тогда:

[math] w[i][j] + w[i'][j'] \leqslant w[i'][j] + w[i][j'][/math]
[math] (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) [/math]
Получили [math] 0 \leqslant 0 [/math], что является верным. Лемма доказана.
[math]\triangleleft[/math]


Лемма:
Если [math] w [/math] удовлетворяет неравенству четырехугольника, то [math] D [/math] также удовлетворяет неравенству четырехугольника, то есть: [math]\forall i \leqslant i' \leqslant j \leqslant j' : D[i][j] + D[i'][j'] \leqslant D[i'][j] + D[i][j'] [/math]
Доказательство:
[math]\triangleright[/math]

При [math] i = i' [/math] или [math] j = j' [/math], очевидно, неравенство выполняется.

Рассмотрим два случая:

  1. [math] i' = j [/math]
    [math] i \lt i' = j \lt j' [/math]. Тогда неравенство четырехугольника сводится к:
    [math] D[i][j] + D[j][j'] \leqslant D[i][j'] [/math]
    Пусть [math] k = R[i][j'] [/math]. Получили два симметричных случая:
    1. [math] k \leqslant j [/math]
      [math] D[i][j] + D[j][j'] \leqslant w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] [/math] — по определению [math] D[i][j] [/math]
      [math] \leqslant w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] [/math] — так как [math] w[i][j'] \geqslant w[i][j] [/math]
      [math] \leqslant w[i][j'] + D[i][k-1] + D[k][j'] [/math] — по индукционному предположению для [math] D [/math]
      [math] \leqslant D[i][j'] [/math] — по определению [math] D[i][j'] [/math]
    2. [math] k \geqslant j [/math] — аналогичный предыдущему случай.
  2. [math] i' \lt j [/math]
    [math] i \lt i' \lt j \lt j' [/math]
    Пусть [math] y = R[i'][j] [/math] и [math] z = R[i][j'] [/math]. Получили два симметричных случая:
    1. [math] z \leqslant y [/math]
      Получили [math] i \leqslant z \leqslant y \leqslant j [/math]. Запишем:
      [math] D[i'][j'] + D[i][j] \leqslant D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] [/math]
      [math] \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] [/math] — по неравенству четырехугольника для [math] w [/math]
      [math] \leqslant w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] [/math] — по индукционному предположению для [math] D [/math]
      [math] \leqslant D[i][j'] + D[i'][j] [/math] — по определению [math] D [/math]
    2. [math] z \geqslant y [/math] доказывается аналогично.
Лемма доказана.
[math]\triangleleft[/math]


Теорема (Монотонность точки разреза):
Если [math] w [/math] удовлетворяет неравенству четырехугольника, то: [math] \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] [/math]
Доказательство:
[math]\triangleright[/math]

В случае [math] i = j [/math] неравенство, очевидно, выполняется. Рассматриваем случай [math] i \lt j [/math] и только случай [math] R[i][j] \leqslant R[i][j+1] [/math](вторая часть доказывается аналогично):

Так как [math] R[i][j] [/math] — максимальный индекс, в котором достигается минимум, достаточно показать, что:

[math] \forall i \lt k \leqslant k' \leqslant j: [D_{k'}[i][j] \leqslant D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \leqslant D_k[i][j+1]] [/math] — фактически, это означает что если на отрезке [math] i..j [/math] разрез оптимальнее по [math] k' [/math], чем по [math] k [/math], то он также будет оптимальнее и на отрезке [math] i..j+1 [/math].

Докажем более сильное неравенство:

[math] \forall i \lt k \leqslant k' \leqslant j: D_k[i][j] - D_{k'}[i][j] \leqslant D_k[i][j+1] - D_{k'}[i][j+1] [/math]
[math] D_k[i][j] + D_{k'}[i][j+1] \leqslant D_k[i][j+1] + D_{k'}[i][j] [/math]
[math] (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \leqslant (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) [/math] — по определению [math] D [/math]
[math] D[k][j] + D[k'][j+1] \leqslant D[k][j+1] + D[k'][j] [/math] — получили неравенство четырехугольника для [math] k \leqslant k' \leqslant j \leqslant j+1 [/math], что является верным из предыдущей леммы. Теорема доказана.
[math]\triangleleft[/math]

Объяснение квадратичной асимптотики

Рассмотрим матрицу [math] R [/math]. Так как отрезки [math] i..j [/math], где [math] i \gt j [/math] мы не рассматриваем, она будет верхнетреугольной. Вначале она будет заполнена так, что [math] R[i][i] = i [/math](так как для отрезка, состоящего из одного элемента, он же и является точкой разреза). Далее, для любого элемента [math] R[i][j] [/math] его значения лежат между [math] R[i][j-1] [/math] (левый элемент в матрице) и [math] R[i+1][j] [/math] (нижний элемент в матрице). Так как мы используем динамику по подотрезкам, то сначала мы рассчитаем [math] R [/math] для отрезков длины 2, затем 3, и так далее до n. Фактически, мы будем обходить диагонали матрицы, количество которых равно n.

Рассмотрим элемент [math] R[i][j] [/math]. Для него выполняется [math] R[i][j-1] \leqslant R[i][j] \leqslant R[i+1][j] [/math]. Следующий элемент, который мы будем пересчитывать — [math] R[i+1][j+1] [/math]. Для него выполняется [math] R[i+1][j] \leqslant R[i+1][j+1] \leqslant R[i+2][j+1] [/math]. Таким образом, заполняя одну диагональ, алгоритм сделает не более n шагов, а так как диагоналей n, получили асимптотику [math] O(n^2) [/math].

Источники информации

S.V. Nagaraj — Tutorial: Optimal binary search trees

Кнут Д.Э. — Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005.