Есть ли алгоритм, чтобы найти n-й член в серии, где мы добавляем предыдущие три элемента, чтобы получить n-й элемент со сложностью меньше, чем O (n)

Question

Сериал звучит так: 1, 2, 4, 7, 13, 24 .... и т. Д. Чтобы получить 4-й член, мы добавляем 1, 2 и 4: 1 + 2 + 4 = 4

Это можно решить с помощью цикла for со сложностью O (n), вот код для этого

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

Здесь первая ссылка описывает вашу проблему.А также добавлены другие ссылки экспоненты матрицы для деталей.