====== 差别 ======
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
javascript_斐波那契数列优化 [2021/09/23 11:33] 若愚 创建 |
javascript_斐波那契数列优化 [2021/09/23 11:34] (当前版本) 若愚 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ```javascript | ```javascript | ||
| function fib(n) { | function fib(n) { | ||
| - | if(n === 0) return 0 | + | |
| if(n === 1) return 1 | if(n === 1) return 1 | ||
| return fib(n-1) + fib(n-2) | return fib(n-1) + fib(n-2) | ||
| 行 29: | 行 29: | ||
| let dict = [0n, 1n] | let dict = [0n, 1n] | ||
| for(let i=2; i<=n; i++) { | for(let i=2; i<=n; i++) { | ||
| - | dict[i] = dict[i-1] + dict[i-2] | + | |
| } | } | ||
| return dict[n] | return dict[n] | ||
| 行 41: | 行 41: | ||
| ```javascript | ```javascript | ||
| function fib(n) { | function fib(n) { | ||
| - | let [v1, v2] = [0n, 1n] | + | let [v1, v2] = [0n, 1n] // |
| for(let i=2; i<=n; i++) { | for(let i=2; i<=n; i++) { | ||
| - | [v1, v2] = [v2, v1+v2] | + | |
| } | } | ||
| return v2 | return v2 | ||
| 行 49: | 行 49: | ||
| console.log(fib(1000)) | console.log(fib(1000)) | ||
| ``` | ``` | ||
| - | 时间复杂度为O(n)，空间复杂度为2。完美。 | + | 时间复杂度为O(n)，空间复杂度为O(1)。完美。 |
若愚 · 2021/09/23 11:33 · javascript_斐波那契数列优化.1632368015.txt.gz
