19
правок
Изменения
м
Лемма доказана.
Исправил замечания
{{Определение
| definition =
'''[[Оптимальный префиксный код с длиной кодового слова не более L бит|Оптимальный префиксный код]] с сохранением порядка ''' (англ. ''order-preserving code'', ''alphabetic code'').
Пусть у нас есть алфавит <tex> \Sigma </tex>. Каждому символу <tex>c_i </tex> сопоставим его код <tex> p_i </tex>. Кодирование называется оптимальным префиксным с сохранением порядка (алфавитным), если соблюдаются:
| definition=
Функция <tex> a </tex> удовлетворяет '''неравенству четырехугольника''' (англ. ''quadrangle inequation''), если
: <tex>\forall i \leqslant i' \leqslant j \leqslant j' : a[i][j] + a[i'][j'] \leqslant a[i'][j] + a[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']) \leqslant (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leqslant 0 </tex>, что является верным. Лемма доказана.
}}
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то <tex> D </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=
При <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
##: <tex> \leqslant D[i][j'] + D[i'][j] </tex> {{---}} по определению <tex> D </tex>
## <tex> z \geqslant y </tex> доказывается аналогично.
}}
Если <tex> w </tex> удовлетворяет неравенству четырехугольника, то:
<tex> \forall i \leqslant j : R[i][j] \leqslant R[i][j+1] \leqslant R[i+1][j+1] </tex> .
| proof=
В случае <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 </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] \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.sciencedirect.com/science/article/pii/S0304397596003209 S.V. Nagaraj {{---}} Tutorial: Optimal binary search trees] * ''Кнут Д.Э.'' {{---}} Искусство программирования, том 3. Сортировка и поиск. — М.: «Вильямс», 2005.
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Динамическое программирование]]
[[Категория:Способы оптимизации методов динамического программирования]]
