TS数据结构与算法之求斐波那契数列的第n值

需求

  • 用JS计算斐波那契数列的第n个值
  • 注意时间复杂度
  • 0 1 1 2 3 5 8 13 21 34...

公式

  • f(0) = 0
  • f(1) = 1
  • f(n) = f(n-1) + f(n-2)

功能实现-递归方式

/**
 * @description 斐波那契数列 - 递归方式实现
 */
export const fibonacci = (n: number): number => {
  if (n <= 0) return 0;
  if (n === 1) return 1;

  return fibonacci(n - 1) + fibonacci(n - 2);
}

递归分析

  • 大量的重复计算
  • 时间复杂度是 O(2^n)
  • 递归方式完全不可用

优化

  • 不用递归,用循环
  • 记录中间结果
  • 时间复杂度为 O(n)

功能实现 - 循环方式

 0   1  1    2   3   5   8   13   21   34
 |   |  |
 n2  n1 res

每次循环 n1 n2 整体后移

/**
 * @description 斐波那契数列 - 循环方式实现
 */
export const fibonacciLoop = (n: number): number => {
  if (n <= 0) return 0;
  if (n === 1) return 1;

  let n1 = 1; // 记录 n - 1 的结果
  let n2 = 0; // 记录 n - 2 的结果
  let res = 0;

  for (let i = 2; i <= n; i++) {
    res = n1 + n2;

    // 记录中间结果
    n2 = n1;
    n1 = res;
  }

  return res;
}

功能测试

export const fibonacciFunctionalTest = () => {
  console.log(fibonacciLoop(0)); // 0
  console.log(fibonacciLoop(3)); // 2
  console.log(fibonacciLoop(6)); // 8
  console.log(fibonacciLoop(9)); // 34
}

单元测试

/**
 * @description 斐波那契数列单元测试
 */
import { fibonacciLoop } from '../src/utils/fibonacci';

describe('斐波那切数列', () => {
  test('0 和 1', () => {
    expect(fibonacciLoop(0)).toBe(0);
    expect(fibonacciLoop(1)).toBe(1);
  });

  test('正常情况', () => {
    expect(fibonacciLoop(2)).toBe(1);
    expect(fibonacciLoop(3)).toBe(2);
    expect(fibonacciLoop(6)).toBe(8);
  });

  test('n 小于 0', () => {
    expect(fibonacciLoop(-1)).toBe(0);
  });
});

运行 yarn jest:

 PASS  tests/fibonacci.test.ts
  斐波那切数列
    √ 0 和 1 (2 ms)
    √ 正常情况 (1 ms)
    √ n 小于 0

动态规划

  • 把一个大问题,拆解为多个小问题,逐级向下拆解
  • 用递归的思路分析问题,再改为循环来实现
  • 算法三大思维:贪心、二分、动态规划

动态规划(dynamic programming,DP)是运筹学的一个分支,是求解决策过程最优化的数学方法。动态规划是对某类问题的解决方法,重点在于如何鉴定一类问题是动态规划可解的而不是纠结用什么解决方法。动态规划中状态是非常重要的,它是计算的关键,通过状态的转移来实现问题的求解。当尝试使用动态规划解决问题时,其实就是要思考如何将这个问题表达成状态以及如何在状态间转移。动态规划总是假设当前已取得最好结果,再依据此结果去推导下一步行动。递归法将大问题分解为小问题,调用自身。而动态规划从小问题推导到大问题,推导过程的中间值要缓存起来,这个推导过程称为状态转移。

动态规划代码是迭代,比递归代码简洁不少,不像递归版本算法,它减少了栈的使用。但要意识到,能为一个问题写递归解决方案并不意味着它就是最好的的解决方案。

递归费栈,容易爆内存。动态规划则不好找准转移规则和起始条件,而这两点又是必须的,所以动态规划好用,不好理解,代码很简单,理解很费劲儿。同样的问题,有时递归和动态规划都能解决,比如斐波那契数列问题,用两者都能解决。

注意,能用递归解决的,用动态规划不一定都能解决。因为这两者本身就是不同的方法,动态规划需要满足的条件,递归时不一定能满足。这一点一定牢记,不要为了动态规划而动态规划。

所有递归算法都必须要满足三定律,递归在某些情况下可以代替迭代,但迭代不一定能替代递归。递归算法通常可以自然地映射到所解决的问题的表达式,看起来很直观简洁。递归并不总是好的方案,有时递归解决方案可能比迭代算法在计算上更昂贵。尾递归是递归的优化形式,能一定程度上减少栈资源使用。动态规划可用于解决最优化问题,通过小问题逐步构建大问题,而递归是通过分解大问题为小问题来逐步解决。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 225,641评论 6 525
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 96,754评论 3 408
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 173,075评论 0 370
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 61,369评论 1 303
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 70,386评论 6 402
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 53,800评论 1 317
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 42,122评论 3 431
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 41,130评论 0 281
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 47,689评论 1 327
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 39,693评论 3 348
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 41,804评论 1 356
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 37,399评论 5 351
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 43,128评论 3 341
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 33,528评论 0 25
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 34,705评论 1 278
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 50,409评论 3 383
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 46,878评论 2 368

推荐阅读更多精彩内容