Эффективность алгоритма Strassen's help

Question

Здравствуйте, я пытаюсь получить эффективность для алгоритма Штрассена, но вам нужна помощь. Рецидив соотношение для алгоритма заключается в следующем:

A(n) = 7A(n/2)+18(n/2)^2, for n>1, A(1) = 0. 

Я решил его до точки, где у меня есть

a(n) = 6(7^(log base(2) n) - 4^(log base(2) n)) 

Означает ли это эффективность алгоритма O (7^журнал (n))?

Answer 1

Да и нет.

Как вы нашли,

a(n) = 6(7^(log₂ n) - 4^(log₂ n)), 

где 4^(log2 n) может быть отброшен, и 6 это просто постоянный множитель, так

Complexity = O(7^(log₂ n)) 

, который похож на то, что вы получите. Однако, база 2 здесь очень важно, поскольку это влияет на показатель:

7^(log₂ n) = n^(log₂ 7) = n^2.80735 
// 7^(log n) = n^(log 7) = n^1.94591 
// 7^(log₇ n) = n^(log₇ 7) = n 

Answer 2

я получил

А (п) = O (N^(15/4))

перепроверки позже ,