6、下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）。
别灰心，再试一次！
💡 真题解析
【答案】C
【考纲知识点】算法复杂度的估计
【解析】
斐波那契递推式为:f(n)=f(n-1)+f(n-2),结合递归树，以最坏的情况考虑，f(n)每次减少1的问题规模需要变为两个分支，记为f(n)=21f(n-1)=2²f(n-2)=…=2n-1f(1)=2n-1，因此复杂度为O(2n)。
6、下面的代码片段用于计算斐波那契数列。该代码的时间复杂度是（ ）。
别灰心，再试一次！
【答案】C
【考纲知识点】算法复杂度的估计
【解析】
斐波那契递推式为:f(n)=f(n-1)+f(n-2),结合递归树，以最坏的情况考虑，f(n)每次减少1的问题规模需要变为两个分支，记为f(n)=21f(n-1)=2²f(n-2)=…=2n-1f(1)=2n-1，因此复杂度为O(2n)。