斯特拉森的算法效率帮助

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））

复核后。