1、通过递归,实现斐波那契数列第n项值的计算图示,如果n为1或者n为2时,直接返回,否则返回第n-1项和第n-2项序列值的和。
2、普通递归算法计算斐波那契数列值的时间复杂度分析图示,通过递归树来分析上述算法的时间复杂度,可以看出其时间复杂度为 O(2ⁿ),这是指数级别的时间复杂度,即非多项式时间复杂度。
3、普通递归算法改进版图示,在上述分析时间复杂度的递归树中,我们可以看出在计算斐波那契数列的过程中,有些值是被重复计算的,因此算法改进版中通过引入一个 Map 来记录已计算的值,当下次需要时,直接获取即可,减少了重复计算的工作量。
4、编写测试方法图示,主方法中,分别调用普通算法和改进算法计算获取多个斐波那契数列值,并记录算法执行时间。
5、测试运行图示,从控制台输出,可以看出两个算法都能正确执行,但普通算法耗时是改进版算法的几千倍。