斯特拉森的算法效率幫助

Question

您好，我正在努力獲得Strassen算法的效率，但需要一些幫助。 該算法的遞推關係如下：

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

我

A（N）= O（N ^（15/4））

複覈後。