Definition of Fibonacci sequence
There are n stairs and you can climb one or two steps at a time. How many ways can you climb up n stairs? The problem is different from the Fibonacci sequence except for the initial conditions.
1. The recursive method
function fib1(n) {
if (n === 1 || n === 2) {
return 1;
}
return fib1(n - 1) + fib1(n - 2)}Copy the code
Recursion is easy to understand, but time is too complicated. So let’s say FIB of 10, fib of 10, fib of 10.
It can be seen from the above three formulas that FIB (8), FIB (7) FIB (8), FIB (7) FIB (8), fib(7) FIB (8), fib(7) FIB (8), fib(7)fib(8) are computed twice. When n is large, more subitems are computed multiple times, resulting in computational redundancy and time complexity as high as O(2n)O(2^n)O(2n).
2. Memo recursion
Since found fib (8), fib (7) fib (8), fib (7) fib (8), fib (7) be repeated computation, so we use the extra space for storage, their results if fib (8) fib (8) fib (8) has not been calculated, are calculated, and store it, The next time you encounter fib(8)fib(8)fib(8) fib(8), you get the fib(8) directly from the storage space, which saves a lot of time.
function fib2(n) {
let memory = new Array(n + 1).fill(0);
const memo = (memory, k) = > {
if (k === 1 || k === 2) return 1;
if (memory[k]) return memory[k];
memory[k] = memo(memory, k - 1) + memo(memory, k - 2);
return memory[k];
};
return memo(memory, n);
}
Copy the code
Time complexity O(n)O(n)O(n) O(n) space complexity O(n)O(n)O(n) O(n).
3. Bottom-up memos
Recursive method in computing fib fib (n) (n) fib (n), from the large number of calculations, until the fib (2), fib (1) fib (2), fib (1) fib (2), fib (1), since can from big to small, so can also grew up to fill the memo array.
function fib3(n) {
let memory = new Array(n + 1).fill(1);
for (let i = 2; i < n; i++) {
memory[i] = memory[i - 1] + memory[i - 2];
}
return memory[n - 1];
}
Copy the code
Here the memory [0] = > fib2 (1), the memory [I] = > fib (I + 1) memory [0] = > fib2 (1), Memory [I] = > fib (I + 1) memory [0] = > fib2 (1), the memory [I] = > fib (I + 1), so the fib (n) = > memory [n – 1) fib (n) = > Memory [n – 1) fib (n) = > memory [n – 1). Time complexity O(n)O(n)O(n) O(n) space complexity O(n)O(n)O(n) O(n).
4. Throw away the memo
You don’t really need extra space, remember the first two values with a variable, the current value is equal to the sum of the first two values, and then update the first two values, which reduces the space complexity to O(1)O(1)O(1).
function fib4(n) {
if(n === 1 || n === 2) return 1;
let pre = 1, cur = 1, sum = 2;
for(let i = 3; i <= n; i++) {
sum = pre + cur;
pre = cur;
cur = sum
}
return cur;
}
Copy the code
5. General term formula method
Dream back to high school! (If you’re in high school, forget it.)
function fib5(n) {
let sqrt5 = Math.sqrt(5);
return (Math.pow(1 + sqrt5, n) - Math.pow(1 - sqrt5, n)) / (sqrt5 * Math.pow(2, n));
}
Copy the code
We won’t deal with this for the moment because we may have to calculate decimals for accuracy reasons.
6. Time consuming tests
This section mainly compares fib4 and FIB5 time. Although FIB5 time complexity is O(1)O(1)O(1), it also needs to be calculated. Test code:
const test = [
1000000.10000000.100000000.1000000000
];
for (let i = 0; i < test.length; i++) {
let n = test[i];
t1 = new Date().getTime();
fib4(n);
t2 = new Date().getTime();
fib5(n);
t3 = new Date().getTime();
console.log("fib4", t2 - t1);
console.log("fib5", t3 - t2);
}
Copy the code
Test results Screenshot
1000000 | 10000000 | 10000000 | 1000000000 | |
---|---|---|---|---|
fib4 | 19 | 68 | 172 | 1607 |
fib5 | 0 | 0 | 0 | 0 |
O(1)O(1)O(1) O(1)