【数据结构与算法】六 █算法复杂度█ 二 时间复杂度 递归算法

【数据结构与算法】六 █算法复杂度█ 二 时间复杂度 递归算法

递归算法

以我们上一篇中介绍的兔子算法为例
C++

#include <iostream>

using namespace std; 

int  rabbit(int i){
if(i<2){
return 1 ;
    }else{
return rabbit(i-1) + rabbit(i-2);
    }
}

int main(){
cout << rabbit(12) << endl;
}

---

---

---

---

自然归纳法估算

对于递归算法的时间复杂度我们也用递归的时间复杂度来解释(ps:似乎提起来很绕),让我们来用公式来解释下.
T(n−1)+T(n−2)+O(1)
ps: O(1)为T(n-1) + T(n-2)相加的复杂度
下面我们用自然归纳法来表示
当n=0 , 1 时间复杂度为 O(1)≤O(2n)
T(n−1)≤O(2n)
T(n)≈O(2n−1)+O(2n−2)+O(1)
O(2n−1)≈O(2n−2)∗1.618
T(n)≤2O(2n−1)+O(1)
T(n)≤O(2n)

---

---

---

---

最后

通过上面一些简单的讲解，
相信朋友们已经知道其原理及特性了。
本人能力有限,
如发现错误或不合理欢迎指正…

---

---

---

---