algorithm - 这个伪代码的渐近复杂度是多少？

Question

你能告诉我这段代码的渐近复杂度吗？

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

我实际上认为第二个是正确的，但我不确定。谢谢你的帮助。

score 2 · Accepted Answer

好的，所以首先要考虑如果 n真的很大会发生什么。最终 n 将足够大，它将支配其他一切。果然，直到你降到 n=950，你将得到 O(lg n)，其中“lg”表示以 2 为底的对数。（为什么我马上就知道这一点？因为 n 的大小减小了一个幂每次迭代两个。）

一旦 n 下降到 950，那么它每次都会减少 2，所以从 950 到 2 是 O(n)——因为你基本上达到了一半的值，而 1/2 消失在常数中。

但是请注意，存在一个 lg n > 950/2 的 n 值。因此，对于某些 n 值，lg n 项将占主导地位。O(lg n)。

score 2 · Accepted Answer

对于 n<=2，O(1)。

O(1) for 2 < n <= 950 - 它需要恒定的时间 (950/2)。

对于 n>950，T(n/2)。

所以你得到：T(n) = T(n/2) + 0(1)。

总复杂度 = O(log n)。

score 0 · Accepted Answer

渐近行为是对复杂性增长的描述，它不是一个可以将n的单个值插入的函数。因此，对于n的不同值有两个或三个不同的语句是没有意义的。

考虑到n -> 无穷大，n < 950 的行为变得可以忽略不计。

3 回答 3