是否有任何算法可以找到系列中的第 n 项，我们添加前三个元素以获得第 n 个元素，复杂度小于 O(n)

Question

这个系列是这样的： 1、2、4、7、13、24……等等 为了得到第 4 项，我们将 1、2 和 4 相加：1+2+4 = 4

可以使用复杂度为 O(n) 的 for 循环来解决，这是其代码

static int fib(int n) 
    { 
        int a = 1, b = 2, c = 4, d; 
        if (n == 1) 
            return a;
        if (n == 2) 
            return b;
        if (n == 3) 
            return c;
        for (int i = 4; i <= n; i++) 
        { 
            d = a + b + c; 
            a = b; 
            b = c; 
            c = d; 
        } 
        return d; 
    }

Answer 1

是的，可以使用矩阵指数算法求解。矩阵指数算法适用于 O(logn) 复杂度。

链接：

https://www.geeksforgeeks.org/matrix-exponentiation/
https://www.hackerearth.com/ja/practice/notes/matrix-exponentiation-1/
https://riptutorial.com/algorithm/example/24256/matrix-exponentiation-to-solve-example-problems
http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html

这里先link描述你的问题。并且还添加了其他 link 的矩阵指数以获取详细信息。