Эффективность алгоритма Штрассена помогает

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 ^ log (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

Я получил

A (n) = O (n ^ (15/4))

перепроверить позже.