Анализ времени работы сортировки вычерпыванием через геометрическую интерпретацию

Одним из параметров карманной сортировки является количество поддиапазонов для разделения исходной выборки элементов, подлежащих сортировке (т.е. количество «карманов»). Пусть для сортировки каждого кармана будет использоваться алгоритм, работающий за O (n ²). Известно, что площадь правильного n-угольника связана с его периметром через прямую пропорциональность (S ~ P). Если зафиксировать количество сторон (в простейшем случае, n = 3), то пропорциональность может быть выражена через константу, которая несущественна для асимптотических оценок и может быть отброшена. Т.е. S = O (P).

В применяемой геометрической интерпретации размер входа алгоритма сортировки для каждого из карманов будет представляться периметром треугольника, а затраты процессорного времени – его площадью (рис. 2.11, (а)). Если количество карманов будет увеличено вдвое, то затраты процессорного времени будут складываться из затрат на сортировку в каждом из карманов вдвое меньшего размера (рис. 2.11, (б)) и так далее.

Обозначим количество карманов как B, периметр как P, а площадь – как S. Условимся также, что увеличение количества карманов не увеличивает периметр исходной фигуры (ведь размер входа не меняется), при этом площадь (т.е. расход процессорного времени) находится как сумма расходов на каждый карман (см. рис. 2.11).

Рисунок 2.11 – Геометрическая интерпретация затрат процессорного времени при различном количестве карманов сортировки вычерпыванием

(а) Один карман. (б) Два кармана. (в) Четыре кармана. (г) Восемь карманов.

Вычисление затрат процессорного времени на сортировку вычерпыванием при бесконечном количестве карманов сводиться к отысканию . Несложно заметить, что . Отсюда S = O (P), или T (n) = O (n), что и было доказано в предыдущем подразделе 2.8.2.