Предлагается переупорядочить члены моделируемого ряда распределений по убыванию вероятностей pj.
После упорядочивания ряд распределения будет выглядеть следующим образом:
Таблица 1.1
| j
|
|
| …
| n-1
| n-1
|
| Х
| хk
| хl
| …
| хr
| хS
|
| Р(X=xi)
| pk
| pl
| …
| pr
| pS
|
где Pk ³ Pl ³ … ³ PS.
Здесь j можно рассматривать как возможные значения случайной величины «числа, производимых в процессе работы алгоритма сравнений». Необходимо обратить внимание, что для последних двух разрядов переупорядоченного ряда значения j совпадают и равны n: если условие сравнения не выполняется для предпоследнего разряда, то оно с очевидностью выполнится для последнего разряда. Вероятности этих значений равны соответствующим вероятностям переупорядоченного ряда распределения. Среднее число сравнений определяется соотношением:
(1.2)
Так как в переупорядоченном ряде большим значениям вероятностей Pj соответствуют меньшие значения j, то среднее число сравнений для переупорядоченного ряда по сравнению с исходным уменьшится.
