为什么用矩阵乘法算斐波那契数比较快 和用f n f n-1 f n-2 的时间复杂度有差(斐波那契矩阵乘法)

为什么用矩阵乘法算斐波那契数比较快 和用f n f n-1 f n-2 的时间复杂度有差(斐波那契矩阵乘法)

首页维修大全综合更新时间:2024-12-03 04:39:03

为什么用矩阵乘法算斐波那契数比较快 和用f n f n-1 f n-2 的时间复杂度有差

直接用线性递推来求f[n]复杂度是O(n),更适合求所有的f[1]到f[n]如果用矩阵乘法来算的话计算K^n只有O(log n)的复杂度,只需要求出某个特定的f[n]时就占优了

大家还看了
也许喜欢
更多栏目

© 2021 3dmxku.com,All Rights Reserved.