152
правки
Изменения
Нет описания правки
== Историческая справка ==
'''Алгоритм Блюма-Флойда-Пратта-Ривеста-Тарьяна''' (BFPRT-алгоритм) создан Мануэлем Блюмом(Manuel Blum), Робертом Флойдом(Robert Floyd), Воганом Рональдом Праттом(Vaughan Ronald Pratt), Роном Ривестом(Ron Rivest) и Рональдом Тарьяном(Robert Tarjan) в 1973 году.
== Анализ времени работы алгоритма ==
<tex>T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn </tex>
Тогда покажем, что для всех <tex> n </tex> выполняется неравенство <tex>T(n) \le 10Cn </tex>.
Докажем по индукции
# Очевидно, что <tex>T(n) \le 10Cn </tex> для малых <tex> n </tex>
# Для <tex>T(\frac{n}{5}) \le 2Cn</tex>, <tex> T(\frac{10n}{7}) \le 7Cn</tex>, тогда
<tex>T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + Cn = 2Cn + 7Cn + Cn = 10 \Rightarrow T(n) \le 10Cn</tex>
