How to speed up this DP?
Разница между en2 и en3, 3 символ(ов) изменены
I have the following recurrence:↵
↵
Let's say that I have 1 array f and 1 function g. ↵
A function call to g takes O(1) time.↵
I just want to compute the values in the f array using the recurrence given below:↵
↵
f[n] = summation(f[n — i]*g(i, n)) for i in [1, 2, 3, 4, ..., n — 1]↵
↵
Base Case: f(0) = 1.↵
↵
If we use the above recurrence, it will take O(n^2) time. ↵
Any way to reduce it to O(n*log(n)) ?↵
↵
Thanks in advance.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en8 Английский fakeac 2018-09-10 14:48:23 4 Tiny change: 'se Case: f(0) = 1.\n\nI' -> 'se Case: f[0] = 1.\n\nI'
en7 Английский fakeac 2018-09-10 14:46:04 303
en6 Английский fakeac 2018-09-10 14:37:22 10 Tiny change: 'mation(f[n — i]*g(i, n)' -> 'mation(f[n-i]*g(i, n)'
en5 Английский fakeac 2018-09-10 14:36:42 79
en4 Английский fakeac 2018-09-10 14:33:32 10 Tiny change: ' 4, ..., n — 1]\n\nBase ' -> ' 4, ..., n]\n\nBase '
en3 Английский fakeac 2018-09-10 14:32:55 3 Tiny change: ': f(0) = 1\nIf we us' -> ': f(0) = 1.\n\nIf we us'
en2 Английский fakeac 2018-09-10 14:32:23 108
en1 Английский fakeac 2018-09-10 13:57:22 443 Initial revision (published)