Efficacité de l'algorithme de Strassen

Question

Bonjour, J'essaie d'obtenir l'efficacité de l'algorithme de Strassen mais j'ai besoin d'aide. La relation de récurrence de l'algorithme est le suivant:

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

Je l'ai résolu au point où je

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

Est-ce que cela signifie l'efficacité de l'algorithme est O (7^log (n))?

Answer 1

Oui et non.

Comme vous l'avez trouvé,

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

où le 4^(log2 n) peut être mis au rebut, et 6 est juste un facteur constant, donc

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

qui est similaire à ce que vous obtenez. Cependant, la base 2 ici est importante car elle affecte l'exposant:

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

Je suis

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

revérifier plus tard .