单选题 适中
#22017

斐波那契数列定义为F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2),使用朴素递归方法计算F(n)的时间复杂度是指数级的,而使用动态规划(或迭代)…

斐波那契数列定义为F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2),使用朴素递归方法计算F(n)的时间复杂度是指数级的,而使用动态规划(或迭代)方法的时间复杂度是线性的,造成这种差异的根本原因是?

未登录也能判分,登录后才会记录
答案与解析
正确答案:C
解析

朴素递归会重复计算大量重叠子问题(如计算F(5)需算F(4)和F(3),算F(4)又需算F(3)和F(2)),动态规划通过存储子问题结果避免重复计算。