GESP 四级 · GESP 202512 C++ 四级 第 21 题

考虑用如下递推方式计算斐波那契数列，时间复杂度是 $O(n)$。

int n = 10;
int f[20];
f[0] = 0;
f[1] = 1;
for (int i = 2; i <= n; i++)
    f[i] = f[i - 1] + f[i - 2];

答案A。在循环中遍历数组并累积结果时，注意累加变量的初始值和每次循环的更新方式。

for循环体可能一次都不执行！这是和while循环一样的"先判断后执行"机制。

【考点】斐波那契数列｜迭代算法｜时间复杂度

GESP四级常考数列与递推，命题人专挑定义细节下手。

看到$f[i]=f[i-1]+f[i-2]$就该反应：这是标准递推公式，数组赋初值$f[0]=0,f[1]=1$完全对版。循环从$i=2$开始，每次只依赖已算出的前两项，$O(n)$加法操作，时间复杂度确实$O(n)$。选项B的陷阱在于诱导你怀疑数组下标越界或循环起点错误——但f[20]完全够用，循环从2开始才是递推逻辑的正确起点。命题人就是想卡住那些死记"斐波那契前两项是1,1"的考生，他们容易忽略数学定义里$f[0]=0$这个关键设定。

若把$f[1]$改成2，所有后续值都会翻倍；若循环写到$n+1$，会多算一项。刷到这类题先问："递推公式是不是标准形式？数组下标有没有越界风险？"别被"看起来差不多"蒙蔽。