我们把复杂度理解成基本操作的执行次数，例如赋值是一次操作之类的。复杂度本身的大 O 记号，就是一种渐进的表达，属于大概的定性分析，因此执行次数一般只考虑循环迭代所带来的基本操作执行次数。例如:
void f() { int m = 0; m=2; m=3; for(int i=0; i
在以上代码中前三条语句执行次数是3次，我可以直接估算称1次，因为f()函数被调用m次，前三条语句的执行次数是3m，那么
T(3m)=O(m)
递归算法时间复杂度求解和数学中求通项公式类似，递归基可以理解成是 a1 ，递归函数内部执行次数认为 an ，这里只是举一个例子，实际情况要根据递归算法具体来判定。如邓俊辉老师《数据结构》课程中递归版的数组倒置例子：
给定任意数组A[0,n)，将其倒置
void reverse(int *A, int lo, int hi) { if(lo
// 1次操作
reverse(A, lo+
1, hi-
1);
// a(n-2) }
else
return;
// 递归基 }
对于上面递归算法的时间复杂度计算，我可以认为，递归基是1次操作，swap()我们认为也是1次基本操作，那么第一次递归就是 an=an−1+1 。以此类推：
an=a(n−2)+1=a(n−4)+2=...=a1+n/2=O(n)
那么上面递归版的数组倒置算法的复杂度就是 O(n) 。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/206469.html原文链接：https://javaforall.net
