推导算法：大O推导法
1、用常数1取代运行时间中的所有加法常数 2、在修改后的运行次数函数中，只保留最高阶项 3、如果最高阶项存在且不是1，那么我们就去除于这个项相乘的常数。 时间复杂度
定义
在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n}=0(f(n))。它表示随问题规模n的增大，算法执行时间的埔长率和 f(n)的埔长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f( n)是问题规横n的某个函数。
常数阶
void main() {
func(); } void func() {
int i=0;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 } /* 共执行了4次，所以时间复杂度为O(4);根据大O推导法，略去常数，所以此函数的时间复杂度为O(1); */ //假如func变成如下结构 void func() {
int i=0;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 i++;//执行1次 } /* 共执行了13次，时间复杂度为O(13);根据大O推导法，略去常数，所以此函数的时间复杂度仍然为O(1); */ 线性阶
void main() {
for(int i=0;i<n;i++) {
func(); } } void func()//时间复杂度为O(1)的函数 {
printf("大O推导法");//执行1次 } /* 在main中，func共被执行了n次，所以main的时间复杂度为O(n); */ //加入main函数被修改成如下 void main() {
for(int i=0;i<n;i++) {
func(); func(); } } /* 在main中，func共被执行了2n次，main的时间复杂度为O(2n);根据大O推导法，略去常数系数，所以main的时间复杂度仍为为O(n); */ 对数阶
void main() {
for(int i=1;i<n;i++) {
func(); i=2i; } } void func()//时间复杂度为O(1)的函数 {
printf("大O推导法");//执行1次 } /* 在main中， 因为i每次被乘2，所以，执行的算法为 2的几次相乘 大于 n，即 2^x>n,--> x= log2n , 在推导对数时间复杂度时，一般都是以10作为对数的底数。 func共被执行了logn次，所以main的时间复杂度为O(logn); */ 平方阶
void main() {
for(int i=1;i<n;i++) {
for(int j=1;j<n;j++) {
func(); } } } void func()//时间复杂度为O(1)的函数 {
printf("大O推导法");//执行1次 } /* 在main中， func()共被执行了n^2,所以main的时间复杂度为O(n^2); */ //假如main被修改成 如下 void main() {
for(int i=1;i<n;i++) {
for(int j=i;j<n;j++) {
func(); } } } /* 那么， func() 执行的次数为 n+n-1+n-2+……--> n(n+1)/2 = n2/2 + n/2 根据大O推导方法，保留最高阶项，n2/2 ，然后去掉这个项相乘的常数，1/2， 所以main的时间复杂度为O(n2) */ 小结
时间复杂度所耗费的时间是：
O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)
参考 https://www.cnblogs.com/fanchangfa/p/3868696.html
空间复杂度
定义
参考 https://www.cnblogs.com/irenebbkiss/p/4243715.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/219380.html原文链接：https://javaforall.net
