Я хочу решить этот повтор с точностью до 0: T (n) = T (n/5) + T (7n/10) + Θ (n)Решая рекуррентность T (n) = T (n/5) + T (7n/10) + Θ (n)
Я могу решить типичный рецидив, но я не знаю, что с ним делать, поскольку это не соответствует ни одному случаю основной теоремы.
Любая помощь или подсказка?
Вы можете использовать обобщение основной теоремы Akra-Bazzi.
Если в этом случае термин Theta (n) был заменен чем-то меньшим, например Theta (1) или Theta (sqrt (n)), вы могли бы просто найти значение alpha так, чтобы n^alpha = (n/5)^alpha + (7n/10)^alpha путем разложения n^alpha. Однако, если вы это сделаете, вы получите альфа = 0.84, а n^0.84 асимптотически меньше, чем Theta (n), поэтому вклад от тета (n) будет доминировать, если вы повторите рекурсию до тех пор, пока аргументы не будут малы. В результате T (n) является Theta (n), хотя и с разными константами, чем Theta (n) в рекурсии.