0
Это проблема домашней работы. Не ожидая решения .. Просто ищите подталкивание в правильном направлении!Рекурсия с логарифмической сложностью времени
Разработать быстрый алгоритм с логарифмической сложностью времени для вычисления тройки (N (n), N (n-1), N (n-2)). Напишите рекурсивную функцию, которая на входе n> 3 возвращает указанную выше тройку. При достаточно большом n подпрограмма должна использовать значительно меньше операций, чем очевидный метод вычисления N (n).
Дано:
N(0) = 0
N(1) = N(2) = N(3) = 1
N(n) = N(n-1) + N(n-3)
N(2k) = N(k)N(k) + 2N(k)N(k−2) + N(k−1)N(k−1) and
N(2k−1) = N(k)N(k) + 2N(k−1)N(k−2)
** Очевидный способ вычисления значений в последовательности N (0), N (1) .. N (N) и, следовательно, возможность использовать предварительно вычисленные значения , Это берет O (n).
Мой первый инстинкт должен был бы увидеть, достаточно ли [memoizing it] (http://en.wikipedia.org/wiki/Memoization). – user2357112
Я отредактировал вопрос для уточнения. Как было сказано, я тоже подпрыгнул в Memoization. Но, сразу же очевидно, что он никогда не может быть меньше линейного в расходе (времени). – user2116243
Воспоминание не вычисляло бы все значения до n. Он вычислил бы значительно меньше этого, и моим первым инстинктом было бы проверить, будет ли количество необходимых значений логарифмическим по n. – user2357112