0
已解决
高级天翼
请问递归的时间复杂度如何分析？
另外，我写了一个递归程序，它的时间复杂度是多少？
#include<iostream>
using namespace std;
int f(int x){
if(x==1)
return 1;
return f(x-1)+2*x-1;
}
int main(){
int x;
cin>>x;
cout<<f(x);
return 0;
}
注意：最好回答两个问题。如果有一个问题不会就回答另一个，至少回答一个问题。
李泽远在2020-02-15 18:25:24追加了内容
时间复杂度似乎是O(n)。
0
已采纳
初级启示者
递归中基本操作重复的次数（如你的代码中的n）就是针对n的某个函数f(n)之一，然后分析f(n)随n的变化情况并确定O(n)的数量级（如最好情况log(n),最坏情况n^2等等，或者是常数、定值)
例如你的代码中的f函数，它的时间复杂度理论上是O(n)，但是递归不完全是循环，因为考虑每次f(x)的调用寻址情况，递归一般是以算法空间单元进行线性辅助存贮元素的（如线性哈希表），这就要看实际辅助空间的大小了。针对你的函数，最好情况下应该是O(n)的时间复杂度，最差情况下大约是O(n^2)左右（O(n^2)-1-1划去常数项），普通情况下应该是O(f(n))的时间复杂度，f(n)不确定。
递归的时间复杂度随问题规模n的增大，算法的执行时间增长率和f（n）增长率成正比，这称作递归算法的渐进时间复杂度。而我们一般情况下讨论的是最坏的时间复杂度。
0
高级天翼
时间复杂度似乎是O(n)。
0
高级天翼
哈哈哈，问答这是怎么了？没有人回答正经问题？全去回复水贴去了？
发帖才1天，25次浏览有8次是我自己浏览的；只一个回答，还是我自己回答的。
0
中级光能
知否？知否？应是緑肥红瘦。
Sorry,sorry, I don't know.
此乃水贴。
这样吧，你到我这个回答下问吧
