152
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''<tex>k</tex>-ой порядковой статистикой''' набора элементов линейно упорядоченного множества называется такой его элемент, который является <tex>k</tex>-ым элементом набора в порядке сортировки
}}
== Историческая справка ==
# Тогда по предположению индукции <tex>T(\frac{n}{5}) \le 10C(\frac{n}{5}) = 2Cn</tex> и <tex> T(\frac{10n}{7}) \le 10C(\frac{7n}{10}) = 7Cn</tex>, тогда
<tex>T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn = 2Cn + 7Cn + Cn = 10Cn \Rightarrow T(n) \le 10Cn</tex>
== Ссылки ==
* [http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Selection algorithm — Wikipedia]
* [http://people.csail.mit.edu/rivest/BlumFloydPrattRivestTarjan-TimeBoundsForSelection.pdf Time Bounds for Selection by Manual Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. Journal of Computer and System Sciences 7,4 August 1973, 448—460]
