Divide&Conquer(D&C)解决方案和用于矩阵乘法的Naive解决方案都是使用C编程语言"就地"实现的.所以根本没有动态内存分配.
正如我们已经了解了两种解决方案,它们实际上具有相同的时间复杂度,即O(n ^ 3).现在它们共享相同的空间复杂性,因为它们都是就地实现的.那怎么可能比另一个快得多？
使用clock_gettime来获取时间.
凭借核心i7笔记本电脑的Windows 7上的Cygwin,D&C解决方案的运行速度比Naive解决方案(删除冗余日志)快得多:
编辑:
"algo0"表示Naive解决方案,而"algo1"表示D&C解决方案.
"len"表示矩阵的宽度和高度.矩阵是NxN矩阵.
"00:00:00:000:003:421"表示:"小时:分钟:秒:毫秒:微秒:纳赛克".
[alg0]time cost[0, len=00000002]: 00:00:00:000:003:421 (malloc_cnt=0)
[alg1]time cost[0, len=00000002]: 00:00:00:000:000:855 (malloc_cnt=0)
------------------------------------------------------
[alg0]time cost[1, len=00000004]: 00:00:00:000:001:711 (malloc_cnt=0)
[alg1]time cost[1, len=00000004]: 00:00:00:000:001:711 (malloc_cnt=0)
------------------------------------------------------
[alg0]time cost[2, len=00000008]: 00:00:00:000:009:408 (malloc_cnt=0)
[alg1]time cost[2, len=00000008]: 00:00:00:000:008:553 (malloc_cnt=0)
------------------------------------------------------
[alg0]time cost[3, len=00000016]: 00:00:00:000:070:134 (malloc_cnt=0)
[alg1]time cost[3, len=00000016]: 00:00:00:000:065:858 (malloc_cnt=0)
------------------------------------------------------
[alg0]time cost[4, len=00000032]: 00:00:00:000:564:066 (malloc_cnt=0)
[alg1]time cost[4, len=00000032]: 00:00:00:000:520:873 (malloc_cnt=0)
------------------------------------------------------
[alg0]time cost[5, len=00000064]: 00:00:00:004:667:337 (malloc_cnt=0)
[alg1]time cost[5, len=00000064]: 00:00:00:004:340:188 (malloc_cnt=0)
------------------------------------------------------
[alg0]time cost[6, len=00000128]: …