АНАЛИТИЧЕСКАЯ ФУНКЦИЯ ТРУДОЁМКОСТИ В СРЕДНЕМ АЛГОРИТМА СОРТИРОВКИ ИНДЕКСАМИ НА ОСНОВЕ РАСПРЕДЕЛЕНИЯ РАЗМАХА ВАРЬИРОВАНИЯ

摘要

Рассматривается алгоритм сортировки методом индексов в аспекте его трудоёмкости в среднем. Для построения аналитической функции трудоёмкости исследуется дискретное распределение вероятностей размаха варьирования в целочисленном массиве, имеющее самостоятельный теоретический интерес. Полученное распределение является базой для исследования трудоёмкости алгоритма сортировки индексами, обладающего, в частных случаях, линейной сложностью по длине входа.