这两个时间复杂度怎么计算？求指教

Question

如题所述

Answer 1

递归时间复杂度：
T(n) = T(n-1) + T(n-2)
=T(n-2) + T(n-3) + T(n-2)
>2*T(n-2)
=2*(T(n-3) + T(n-4))
=2*(T(n-4) + T(n-5) + T(n-4))
>2*2*T(n-4)
...
>2^(n/2)
T(n) = T(n-1) + T(n-2)
<T(n-1) + T(n-1)
=2*T(n-1)
=2*(T(n-2) +T(n-3))
<2*(T(n-2) + T(n-2))
<2*2*T(n-2)
...
<2^n
递归时间复杂度 2^(n/2) < T(n) < 2^n，O(2^n)。

非递归时间复杂度：
T(n) = 1 + T(n-1)
= 1 + 1 + T(n-2)
=n
非递归时间复杂度 O(n)。本回答被网友采纳

Answer 2

这是什么呀，看不懂，嘿嘿

Answer 3

递归算法 log2^n
非递归 n
对吧？追答

1
log2^n

追问

你给我写一个过程照过来吧，我就是不会