判断题
偏易
#19832
以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为为O(n)。 int fib ( int n ) { i…
以下 fib 函数计算第 n 项斐波那契数( fib(0)=0 , fib(1)=1 ),其时间复杂度为为O(n)。
答案与解析
正确答案:错
解析
分析函数的递归调用结构,识别是否存在重复计算。若函数使用循环或递归但未优化,需统计每层递归或每次迭代的执行次数。考察输入n与基本操作执行频次的关系,确定时间复杂度是否随n线性增长。检查是否有记忆化机制或动态规划思想减少冗余计算。对比标准O(n)实现方式,确认其状态转移是否仅依赖前两项且每个状态仅计算一次。