Qual è il modo più efficace per trovare il primo elemento della riga di ith quando A [i, j] = j * (A [i-1, j + 1] -A [i-1, j])?

Question

Quando la prima riga è 1, 1/2, 1/3 .... Ecco un'immagine per supportare la domanda. image for better description. http://s23.postimg.org/9k5w5h88b/algos.png

Esiste un approccio più efficiente rispetto all'approccio ingenuo O (n^2)?

Mi sono imbattuto in questo quando studio i numeri di Bernoulli e quindi di conseguenza nel raggiungere "l'algoritmo di Akiyama-Tanigawa".

Uno dei modi potrebbe essere semplice precomputing dei risultati e memorizzarli in una tabella. Dal momento che i numeri di Bernoulli crescono molto rapidamente, per la maggior parte degli scopi pratici non avremmo bisogno dei numeri di Bernoulli per n molto più grandi. Considera Bernoulli (400) - il suo intorno - (10^550).

Ma guardando solo algoritmicamente, c'è un approccio migliore rispetto a quello di O (n^2)?

Answer 1

I primi elementi formano la sequenza di Bernoulli numbers. I numeratori e denominatori per i numeri di Bernoulli si trovano utilizzando la sequenza A027641 e la sequenza A027642, rispettivamente. Entrambe le sequenze hanno somme di forma chiusa sulle rispettive pagine che possono essere utilizzate per calcolare i loro termini.