【数据结构与算法 10】算法的时间复杂度和空间复杂度
（1）找出算法中的基本语句
算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
（2）计算基本语句的执行次数的数量级
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，?可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
（3）用大 O 记号表示算法的时间性能
将基本语句执行次数的数量级放入大 O 记号中
如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。
Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。其中Ο(log_2n_)、Ο(n)、 Ο(nlog2n**)、Ο(_n_2)和Ο(_n_3)**称为多项式时间，而Ο(_2_n)和Ο(n!)称为指数时间。?计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法。把这类问题称为 P（Polynomial，多项式）类问题；而后者（即指数时间复杂度的算法）称为 NP（Non-Deterministic Polynomial，非确定多项式）问题。
一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是 n 的输入，在 n^k 的时间内得到结果，称为 P 问题。
有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。比如问 4294967297 是不是质数？如果要直接入手的话，那么要把小于 4294967297 的平方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于 641 和 6700417 的乘积，不是素数，很好验证的，顺便麻烦转告费马他的猜想不成立。大数分解、Hamilton 回路之类的问题，都是可以多项式时间内验证一个“解”是否正确，这类问题叫做 NP 问题。
（4）在计算算法时间复杂度时有以下几个简单的程序分析法则：
对于一些简单的输入输出语句或赋值语句,近似认为需要 O(1)时间
对于顺序结构,需要依次执行一系列语句所用的时间可采用大 O 下"求和法则"
对于选择结构,如 if 语句,它的主要时间耗费是在执行 then 字句或 else 字句所用的时间,需注意的是检验条件也需要 O(1)时间
对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大 O 下"乘法法则"
对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
（5）下面分别对几个常见的时间复杂度进行示例说明
O(1)
Temp=i; i=j; j=temp;?
以上三条单个语句的频度均为 1，该程序段的执行时间是一个与问题规模 n 无关的常数。算法的时间复杂度为常数阶，记作 T(n)=O(1)。
注意：如果算法的执行时间不随问题规模 n 的增长而增长，即使算法中有成千上万条语句，其执行时间也不过是一个较大的常数，此类算法的时间复杂度是 O(1)。
O(_n_2)
sum=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
sum++;
}
}
因为Θ(2_n_2+n+1)=_n_2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以 T(n)= =O(_n_2)；
一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加 1、终值判别、控制转移等成分，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度 f(n)决定的。?
??O(n)?
a=0;
b=1;
for (i=1;i<=n;i++)
{
s=a+
b;
b=a;
a=s;
}
解： 语句 1 的频度：2,???????
语句 2 的频度： n,???????
语句 3 的频度： n-1,???????
语句 4 的频度：n-1,???
语句 5 的频度：n-1,?????????????????????????????????
T(n)=2+n+3(n-1)=4n-1=O(n)。
O(log_2n_)
i=1; ①
while (i<=n){
i=i*2; ②
}
解析：语句 1 的频度是 1；
语句 2 的频度是 f(n)，则 2^f(n)<=n;f(n)<=?log_2n_
取最大值 f(n)=log_2n_,
T(n)=O(log_2n_?)
O(_n_3)?
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
{
for(k=0;k<j;k++)
x=x+2;
}
}
4、常见算法的时间复杂度和空间复杂度
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论