例子#xff1a;

算法效率是指算法在计算机上运行时所消耗的时间和资源。

这是衡量算法执行速度和资源利用情况的重要指标。

long

}这是一个斐波那契函数用的是递归的计算方法每次创建函数就会在栈区开辟一块空间递归次数越多开辟空间越多

时间复杂度时间复杂度描述了算法执行所需的时间随输入规模增加而增长的趋势。

常见的时间复杂度包括常数时间O(1)、线性时间O(n)、对数时间O(log

n)、平方时间O(n²)等。

通过分析算法中关键操作的执行次数来确定时间复杂度通常使用大O符号表示。

空间复杂度空间复杂度描述了算法在执行过程中所需的额外存储空间随输入规模增加而增长的趋势。

常见的空间复杂度包括常数空间O(1)、线性空间O(n)、对数空间O(log

n)等。

通过分析算法中使用的数据结构和辅助空间来确定空间复杂度。

评估算法效率时我们希望选择具有更低时间复杂度和空间复杂度的算法以提高程序的执行速度和资源利用率。

但需要注意的是时间复杂度和空间复杂度通常存在着一定的取舍关系有时需要在时间和空间之间做出权衡。

除了时间复杂度和空间复杂度还可以考虑一些实际情况下的算法效率问题如最坏情况、平均情况和最好情况下的执行时间以及算法在特定硬件环境下的性能等。

综合考虑这些因素可以更全面地评估算法的效率。

为了提高算法效率我们可以采用一些常见的优化方法如减少循环次数、使用合适的数据结构和算法、剪枝和缓存等。

同时也可以借助工具和框架来提升算法效率如并行计算、GPU加速、分布式计算等。

时间复杂度

在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。

一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。

但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。

一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。

void

在实际计算时间复杂度中我们其实不一定要精准的计算出执行的次数只需要大概的执行次数那么这里我们使用大O的渐进表示法

大O符号Big

notation是用于描述函数渐进行为的数学符号。

是一种用于衡量算法时间复杂度的渐进表示方法

推导大O阶方法

3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。

得到的结果就是大O阶。

N10时F(N)100

通过计算我们发现这样的表示方法去掉那些对结果影响不大的项简明了洁表示出执行次数

例如在一个长度为N数组中搜索一个数据x

}在这里M是一个常数项N是一个未知数所以我们可以先把常数项略去然后就只剩下2N通过计算规则,省去最高项的常数那么这个函数的时间复杂度为O(N);

void

}在这里M与N都是未知数且它们是同阶的所以对于这种情况就要分类讨论

M远大于N时间复杂度O(M)

}这是一个冒泡排序很明显这个两个循环在嵌套外循环执行1次内循环就得执行N次那么外循环执行N次总共就执行N^2次

时间复杂度O(N^2);

}这是一个二分查找函数也叫折半查找我们以最坏的情况去看每循环一次这个数组的长度就会减半假设以N表示数组的长度我们要在数组中寻找一个数那么假设寻找了x次那么通过计算2^xN;再通过换算就是xlog2

N;2是对数的底数由于底数不好表示所以对于这个函数的时间复杂度就是为O(logN);

long

}这是开头的例子斐波那契递归函数每次在函数中就会递归到两个函数中去

递归到最后会发现像个金字塔一样全部加起来F(N)1248……2(N-1),由数学的等比求和公式得F(N)2^N-1;

那么时间复杂度为F(N)2^N;

空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度

空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。

注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

void

}在这里函数所开辟的空间都是局部变量在栈区开辟的是已经确定下来的

long

}这里用了递归的方法每递归一次就会在栈帧中开辟一次空间总共开辟N次每次空间内为常数次大所以

空间复杂度O(N);

通过开辟额外空间将对应位置的数字进行放入新数组中最后再返回到原数组中

时间复杂度:O(N)

new(int*)malloc(sizeof(int)*numsSize);//当k长度超过数组长度时k%numsSize;memcpy(new,numsnumsSize-k,sizeof(int)*k);memcpy(new,nums,sizeof(int)*(numsSize-k));memcpy(nums,new,sizeof(int)*numsSize);free(new);}第三种

时间复杂度:O(N)

tmpsem[left];sem[left]sem[right];sem[right]tmp;left;right--;}}

void

k){k%numsSize;//如果k的长度大于numsize需要取余//利用部分数组倒置在全数组倒置的方法进行轮转reserve(nums,0,numsSize-k-1);reserve(nums,numsSize-k,numsSize-1);reserve(nums,0,numsSize-1);}