Алгоритмы обработки строк и массивов — исследовательский практикум (12/21)

Исследование эффективности сжатия серий

Проведите вычислительный эксперимент: измерьте, как порядок одинаковых данных влияет на число серий и стоимость RLE.

Лаборатория

1. Для каждого набора найдите n и число серий r.
2. В учебной модели сравните исходную стоимость n и стоимость пар 2r.
3. Исследуйте длинные серии, чередование и все различные значения.
4. Сравните один набор до и после группировки, не забывая, что порядок изменился.
5. Для каждого опыта проверьте decode(encode(a))=a и сформулируйте вывод.

Гипотеза: RLE выгодно в принятой модели только при 2r<n; сортировка не является допустимым улучшением, если важен исходный порядок.

Выходной билет

a=[4,4,4,2,2,7] → r=3, n=6, 2r=6: выигрыша нет.

Pascal

После кодирования вычислите r и сравните 2*r с n для каждого экспериментального набора.