Как вычислить время выполнения алгоритма Карацубы?

#algorithm #karatsuba

#алгоритм #карацуба

Вопрос:

Я знаю, что формула равна T (n) = 3T (n / 2) O (n), и, используя основной метод, я могу получить T (n) = n ^ (log3), где 2 является основанием.

Но я до сих пор не знаю, как получить ответ без использования основного метода. Потому что результат, который я получаю из рекурсивной формулы, равен T (n) = 3 ^ (logn), где 2 является базовым.

Я был бы очень признателен, если кто-нибудь сможет мне помочь!

Ответ №1:

Ну, это потому, что вы оба правы одновременно.

 n^(log3) = 3^(logn)

Доказательство :

 y = 3^log(n)
log(y) = log(n)*log(3)
log(y)/log(n) = log(3)

 log<sub>n</sub>y = log(3)

 y = n^(log3)