算法分析
算法(algorithm)
是对特定问题求解步骤的一种描述,它是指令的有限序列。
算法分析
就是分析算法执行时占用计算机系统资源的多少。计算机资源主要是CPU时间和内存空间。分析算法的目的就是分析算法的时空性能以便改进算法。
时间复杂度分析
一个算法是由控制结构(循环、分支、顺序)和普通语句(a = 5、cout<<" "; 等)构成,所以算法的执行时间由这两者的综合效果决定。算法执行时间大致等于普通语句所需时间 * T(n)(该语句执行的次数,也叫频度)。
void fun(int n)
{
int i, j;
for (i = 0; i < n; i++) //语句 1
{
for (j = 0; j < n; j++) //语句 2
{
std::cout << i << j; //语句 3
}
}
}
忽略定义变量的语句,这个算法主要包括语句1、2、3。
语句1为外层循环,直到 i=n 时才会停止,因此语句1 的频度T(n) = n+1,但是他的循环体只执行n次;
语句2作为语句1 的循环体,只执行n次,但语句2本身要执行n+1次,故它的频度T(n)= n(n+1);
语句3作为内层循环的循环体,它要执行n^2次,因此T(n) = n^2。
频度之和 T(n)= ( n+1 ) + ( n*(n+1) ) + ( n^2 ) = 2n^2 + 2n + 1
所以这个算法的时间复杂度为 n^2。为什么是 n^2 呢?
T(n)用“O”表示,算法时间复杂度分析实际上是一种时间增长趋势分析
由于算法分析并不是计较绝对时间,通常在求出T(n)后,进一步用T(n)的数量级来表示时间复杂度,T(n) = O(f(n)),大写"O"意指数量级,找到f(n)的一个最高上界,忽略其它低阶项和常数项以简化T(n)的计算,且客观的反应当 n 很大时算法的时间性能。所以上边例子时间复杂度为O(n^2)。
一般在没有循环语句的算法,普通语句的执行次数与问题规模无关,可称为常数阶,算法中的每一个普通语句的执行时间都可以看做O(1)。不同的时间复杂度存在以下关系:
常数阶O(1),只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1)
int i = 1,m;
++i;
int m = i + 1;
对数阶O(log2^n) ,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。假设循环 x 次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2^n,也就是说当循环 log2^n 次以后,这个代码就结束了。
int i = 1;
while(i<n)
{
i = i * 2;
}
线性阶O(n)
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
线性对数阶O(n log2^n) ,将时间复杂度为O(logn)的代码循环N遍
for(m=1; m<n; m++)
{
i = 1;
while(i<n)
{
i = i * 2;
}
}
粘一个递归算法的时间复杂度算法分析:https://zhuanlan.zhihu.com/p/129887381 递归算法的时间复杂度本质上是要看: 递归的次数 * 每次递归中的操作次数
空间复杂度分析
一个算法的存储量包括输入数据所占的空间、程序本身所占空间、临时变量所占的空间,一般只考虑临时变量所占的空间(形参的空间会在调用该算法的算法中考虑)。算法空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度,S(n) = O(g(n))。
若需要临时空间相对于问题规模来说是常数,则称此算法为原地工作算法或就地工作算法。
递归算法的空间复杂度与所生成的最大递归树的深度成正比。如果递归算法的每个函数调用都占用 O(m) 空间,且递归树的最大深度为 n,则递归算法的空间复杂度将为 O(n*m)。