csp2021提高初赛的第 12 题是递归求斐波那契数列的复杂度。只能选非多项式的 $O(2^n)$。

然而，如果关注该函数的总调用次数 $g(x)$，在调用 $g(x)$ 时调用 $g(x-1)$ 和 $g(x-2)$ 各一次，因此 $g(x)=g(x-1)+g(x+2)+1$，其中 $g(1)=g(2)=1$。该数列形如 $1,1,3,5,9,15$，为A001595,等于 $2F_{n+1}-1$，所以复杂度应该为 $O(2F_{n+1}-1)=O(F_{n+1})=O((\frac{\sqrt5+1}2)^n)$，与 $O(2^n)$ 不同阶。

是我的做法出错了，还是题目出错了？

PS： 我一会儿还要上课，可能无法及时回复，请见谅。