网站建设优化公司招聘,绵阳企业品牌网站建设,wordpress响应速度太慢,wordpress商城 中文站1.算法效率
如何衡量一个算法的好坏#xff1f;从两个维度#xff0c;时间和空间#xff08;算法运行的快慢#xff0c;消耗的空间大不大#xff09;。因为计算机硬件领域的高速发展#xff0c;如今计算机的存储量已经达到了一个很高的程度#xff0c;所以现在我们一般…1.算法效率
如何衡量一个算法的好坏从两个维度时间和空间算法运行的快慢消耗的空间大不大。因为计算机硬件领域的高速发展如今计算机的存储量已经达到了一个很高的程度所以现在我们一般重点关注时间复杂度空间复杂度也就不那么被重视了。
2.时间复杂度
时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数表达式数学意义上的函数。时间复杂度描述的不是算法运行的具体时间因为一个程序的时间是没有标准的他跟计算机的硬件有很大的关系而一个算法的运行时间与其中语句的执行次数是成正比例的所以时间复杂度描述的是算法中的基本操作的执行次数。
找到某条基本语句和问题规模N之间的数学表达式就是算出了该算法的时间复杂度。比如下面这段代码
void test(int N)
{int i 0;int j 0;for (i 0; i N; i){for (j 0; j i; j){printf(* );}printf(\n);}
}
这个算法的基本语句就是循环中的打印星号和打印换行打印星号的执行的次数是012……N-1NN-1/2而打印换行的执行次数为N次所以这个算法的时间复杂度为N(N1)/2。但是我们一般不需要准确的执行次数只需要知道大概的次数就行了于是就有了一种大O的渐进表示法。比如这个算法我们一般描述它的时间复杂度就是ON^2
大O的渐进表示法的规则
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数追踪只保留最高阶
3.如果最高阶项系数存在且不为1则去除这个项的常数系数。
如果表达式结果是常数那就是O(1)
就比如上面的算法准确的运行次数是N^2/2N/2,首先去除加法常数因为没有所以不用管。如何只保留最高阶也就是N^2/2,最高阶地系数为1/2把系数去除得到的就是N^2时间复杂度就是ON^2。
只保留最高项是因为这个最高项是对结果产生决定性影响就比如N^2N当N接近无穷大时N^2的结果才是决定最终结果的关键因素而N在这里起到的效果几乎可以忽略不记。
为什么最高项常数系数要去除呢还是因为N趋近无穷大时由于这个常数系数不管多大他都是远小于无穷大的不会对最终结果产生太大影响至少不会在量级上产生大的影响。
再比如下面这个算法:
int fib(int n)
{if (n 1 || n 2){return 1;}else{return fib(n - 1) fib(n - 2);}
}我们可以把这个递归的图给画出来 右边的肯定是要比左边递归的深度要小的但是我们只用算大概的执行次数就行了我们假设这个三角形是完整的他的执行次数总数和就是 ( 124……2^n-2),最终结果的最高项肯定是2^n,所以这个算法的时间复杂度就是O(N)
int fib(int n)
{if (n 1 || n 2){return 1;}int a 1;int b 1;int ret 1;while (n2){ret a b; a b;b ret;n--;}return ret;
}
这个算法的时间复杂度就是O(N)
我们还可以知道一些常用的算法的时间复杂度比如冒泡排序的时间复杂度就是O(N^2),二分查找的时间复杂度就是logN注意我们在时间复杂度中的log都是默认以2为底的。
3.空间复杂度
时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。 空间复杂度也是一个函数表达式是对一个算法在运行过程中临时额外占用存储空间的大小。但是我们关注的也不是具体的内存的大小还是因为硬件的原因比如同一段代码一个int类型的变量在有的机器上他只占两个字节而在有的机器上占四个字节所以这个所占空间的具体的大小也是没有意义的。空间复杂度算的是变量的个数或者函数调用建立栈帧的次数或者层数递归。
就比如我们递归求斐波那契数的函数 我们可以将上面的每一个方块看成一个函数栈帧但是我们要记住一点我们调用fib(n-1)fib(n-2)时不是同时为这两个函数创建栈帧而是会在fib(n-1)返回后再去调用fib(n-2)所以计算这个递归的空间复杂度看的不是调用的次数而是递归的深度同时因为每次创建栈帧时栈帧的空间就已经是固定的了也就是一个常数在大O的渐进表示法中加法的常数和系数的常数都是会删掉的所以这个算法的空间复杂度就是O(N)。
在之前我们学完函数栈帧的时候就能发现一个变量生命周期结束后它的空间就还给了操作系统如果我们在后面创建变量时是有可能会重复利用这块空间的。
要记住空间是可以重复利用的不累积。而是就是一去不复返的是累积的。在写算法的时候我们尤其要注意算法的时间复杂度必要时我们要采取以空间换时间的策略。
