我正在搜索算法，以在O（log n）时间中找到n次2个线性函数的组合（其中n可以大到10 ^ 18）。我刚得到一个使用分而治之算法的包含2个函数的多项式组合的pdf文件。
我想知道我的n次线性函数合成问题是否也可以使用O（log n）复杂度的分治法来解决？
如果是，请说明算法。
提前致谢。
编辑1：函数f（x）的n次合成是fofof ... n次。在这里，该函数将被自身构成n次。没有2个功能。
您可以将线性函数f（x）= ax + b的应用表示为2×2矩阵乘以向量（x，1）。
(f(x)) = ( a b ) (x)
( 1 ) ( 0 1 ) (1)
将fn倍应用于x就是将矩阵乘以n倍于（x，1），或者等效地，将矩阵乘以n的幂乘以（x，1）。
(f^n(x)) = ( a b )^n (x)
( 1 ) ( 0 1 ) (1)
您可以通过平方运算使用幂运算来计算矩阵幂。
无论您是对实数，整数还是取模M进行模运算的整数，此方法都有效。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句