Изменения

Карманная сортировка

Нет изменений в размере, 20:24, 12 июня 2012

→‎Асимптотика

<tex> T(n) = \theta(n) + \sum\limits_{i = 1}^k O(n_i</tex> <tex> \log n_i) + \theta(k)</tex>

Тоесть, если <tex> n \sim k </tex>

<tex> M(E[T(n)) ] = \theta(n) </tex>

Если, <tex> n = o(k) </tex>

<tex> M(E[T(n)) ] = \theta(k) </tex>

Из приведенных выше формул, видно, что в среднем "карманная сортировка" работает за линейное время.

Анонимный участник