Рекуррентное отношение троичного поиска: T (n) = T (n / 3) + 4, How 4 находится в рекуррентном отношении, так как при троичном поиске это журнал для базы 3 N, поэтому там должно быть только 3 раздела.
Отношение повторения для троичного поиска составляет T(n) = T(n/3) + O(1) или даже T(n) = T(2n/3) + O(1).Константа, скрытая в этом O(1), зависит от конкретной реализации и того, как был проведен анализ.Это может быть 4 или 3, или какое-то другое значение.Применяя вариант 2 основной теоремы , у вас все еще есть O(log n).
T(n) = T(n/3) + O(1)
T(n) = T(2n/3) + O(1)
O(1)
4
3
O(log n)