АНАЛИТИЧЕСКАЯ ФУНКЦИЯ ТРУДОЁМКОСТИ В СРЕДНЕМ АЛГОРИТМА СОРТИРОВКИ ИНДЕКСАМИ НА ОСНОВЕ РАСПРЕДЕЛЕНИЯ РАЗМАХА ВАРЬИРОВАНИЯстатья
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
Аннотация:Рассматривается алгоритм сортировки методом индексов в аспекте его трудоёмкости в среднем. Для построения аналитической функции трудоёмкости исследуется дискретное распределение вероятностей размаха варьирования в целочисленном массиве, имеющее самостоятельный теоретический интерес. Полученное распределение является базой для исследования трудоёмкости алгоритма сортировки индексами, обладающего, в частных случаях, линейной сложностью по длине входа.