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
其實我覺得第二個是對的，但我不知道這一點。 感謝您的幫助。