55
правок
Изменения
→Оценка минимальной и максимальной длины кода
L = \prod_{i=1}^l \frac{w_{\alpha_i}}{n+i-1}
</tex>
Знаменатель каждого следующего члена произведения будет увеличиваться на <tex>1</tex>, так как на каждом шаге увеличивается вес одного из символов алфавита.
Соответственно, чтобы минимизировать произведение, необходимо минимизировать числители его членов.
Этого можно достичь, если передать на вход алгоритму строку, состоящую из неповторяющихся символов.
В таком случае вес каждого из полученных символов будет равен <tex>1</tex>, а значение кода на каждом из шагов <tex>k=1, 2, \dots, l</tex> будет изменяться в <tex>\frac{1}{n+k-1}</tex> раз.
Соответственно, формула примет вид:
<tex>
Соответственно, формула будет иметь следующий вид:
<tex>
L_{max} = \prod_{i=1}^l \frac{i}{n+i-1} = \frac{l!(n-1)!}{(n+l-1)!}
