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

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

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

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

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