2.8.2 Вероятностный анализ времени работы сортировки вычерпыванием

Проанализируем время работы алгоритма. Операции во всех строках, кроме пятой, требуют общего времени О(п). Просмотр всех ящиков также занимает время О(п). Таким образом, остаётся только оценить время сортировки вставками внутри ящиков.

Пусть в ящик В[i] попало n_i чисел n_i – случайная величина). Поскольку сортировка вставками работает за квадратичное время, математическое ожида­ние времени сортировки чисел в ящике номер i есть O(М[n_i²]), а математическое ожидание суммарного времени сортировки во всех ящиках есть

Найдём функцию распределения случайных величин n. Поскольку числа распределены равномерно, а длины всех отрезков равны, вероятность того, что данное число попадет в ящик номер i, равна 1/n. Стало быть, мы находимся в ситуации примера с шарами и урнами: имеется п шаров-чисел, п урн-ящиков, и вероятность попадания данного шара в данную урну равна р = 1/n. Поэтому числа n_i распределены биномиально: вероятность того, что n_i = k, равна , математическое ожидание равно , и дисперсия равна .

Отсюда математическое ожидание сум­марного времени сортировки содержимого всех ящиков есть О(п), так что ма­тематическое ожидание времени работы алгоритма сортировки вычерпыванием в самом деле линейно зависит от количества чисел.