Strassen의 알고리즘 효율 도움말

Question

안녕하세요 저는 Strassen의 알고리즘에 대한 효율성을 얻으려고하고 있지만 도움이 필요합니다. 알고리즘에 대한 재발 관계는 다음과 같다 : 나는이 알고리즘의 효율성을 의미 하는가

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

을 가지고있는 점을 해결 한

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

되는 O (7^로그 (n))?

Answer 1

예 아니요. 당신이 발견 한 것처럼

의 4^(log2 n)가 폐기 될 수

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

, 6 단지 일정한 요인이다, 당신이 무엇을 얻을 비슷합니다 그래서

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

. (N^(4분의 15))

재확인 후

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

제가

(n)을 얻었다 = O : 그것은 지수에 영향을주기 때문에 그러나베이스 여기 2 중요 .