你能告诉我这个代码的复杂程度吗？
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
B）然而，我对前两个语句的复杂性不太确定，因为如果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
我真的认为第二个是对的，但我不确定。
谢谢你的帮助。
最佳答案
好吧，先想想如果n真的很大会发生什么。最终n将足够大，它将主宰一切。果然，在n=950之前，得到o（lgn），其中“lg”表示对数基2。（为什么我会马上知道？因为n的大小每次迭代都会减小2倍。）
一旦n降到950，那么它每次都会减少2，所以从950降到2就是O（n），因为你基本上达到了值的一半，1/2消失在常数中。
但观察到，存在Ln n＞950/2的n值。因此，lg n项将主导于n.o（lgn）的某些值。