152
правки
Изменения
Нет описания правки
Покажем, что для всех <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </tex>.
Докажем по индукции:
# Очевидно, что для малых <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </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>
Так как <tex>T(n) \le 10Cn </tex>, то время работы алгоритма <tex>O(n)</tex>
== Ссылки ==
* [http://en.wikipedia.org/wiki/BFPRT#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm Selection algorithm — Wikipedia]
