SortB (A, N, M, B)

Для всех i от 1 до N с шагом 1 выполнить: M[i]=0; I[i]=0; B[i]=0

Для всех i от 1 до N с шагом 1 выполнить: M[A[i]*N+1] ++

Для всех i от 2 до N с шагом 1 выполнить: M[i] = M[i]+ M[i-1]

Для всех i от N до 2 с шагом -1 выполнить: M[i] = M[i-1]

M[0]=0

Для всех i от 1 до N с шагом 1 выполнить: B[M[i]+I[i]+A[i]*N+1]= A[i]; I[i]++

Для всех i от 1 до N с шагом 1 выполнить: Sort(B,M[i],I[i])

Для всех i от 1 до N с шагом 1 выполнить:

Для всех j от 1 до I[i] с шагом 1 выполнить: A[k]= B[ M[i]+j ]; k++

Во втором цикле алгоритма мы подсчитываем количество элементов, попавших в i -ый интервал. В третьем и четвертом циклах мы помещаем в M[i] индекс первого элемента части массива B, относящейся к контейнеру с номером i. В пятом цикле мы помещаем элементы в соответствующие контейнеры. В шестом цикле происходит сортировка элементов в контейнерах. Далее мы последовательно выбираем элементы в результирующий массив A.

Теорема. Алгоритм SortB работает за время O(N) в среднем, где N – количество сортируемых элементов.

Доказательство. Пусть p=1/N. Вероятность попадания в один контейнер k элементов равна p_k=С_N^k p^k (1-p)^N-k (биноминальное распределение). Время работы алгоритма сортировки в одном контейнере равно S O(k²), где k – количество элементов, попавших в i- ый контейнер.

Согласно свойствам биномиального распределения, среднее (математическое ожидание) количество элементов в контейнере равно M(k)= S_k p_kk=Np=1. Средне-квадратичное отклонение от среднего значения (дисперсия) количества элементов в контейнере равно D(k)= S _k p_k(k- M(k))²=S _k p_k(k-1)²=Np(1-p)=1-1/N.

D(k)=M(k²) – (M(k))² из чего сразу следует M(k²)=D(k) +(M(k))²=2-1/N. Итого, среднее время сортировки одного контейнера равно O(1), а среднее время сортировок N контейнеров равно O(N).

¢

Лекция 5

Алгоритмы. Сведение алгоритмов.

  Д.Кнут. Искусство программирования для ЭВМ. тт 1-3. Москва. Мир. 1996-1998 Т.Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы. Построение и анализ. Москва. МЦНМО. 1999. Препарата Ф., Шеймос М. Вычислительная геометрия. Москва. Мир. 1989  

---

Дата добавления: 2015-10-30