2
你能告诉我这个代码的渐近复杂吗？这个伪代码的渐近复杂度是什么？
f(n):
if (n<=2) then return 1;
else {
if (n>950) then { i=n/2; return f(i);}
else return f(n-2);
}
我想到了两种解决方案。
一）
O(1) when n<=2
T(n/2) + 1 when n > 950
T(n-2) + 1 when 950>=n>2
，解决复发：
O(1) when n<=2
Θ(log n) when n > 950
O(n^2) when 950>=n>2
二）但是我不那么肯定对最后两个语句的复杂性，因为如果n大于950运算器将调用f（i）直到i小于950，然后继续调用f（n-2）。 因此，其他的解决办法是这样的一个：
O(1) when n<=2
T(n/2) + T(n-2) + 1 otherwise
，解决复发：
O(1) when n<=2
O(n^2) otherwise
其实我觉得第二个是对的，但我不知道这一点。 感谢您的帮助。