算法的时间复杂度和空间复杂度.docx

算法的时间复杂度和空间复杂度-总结
通常，对于一个给定的算法，我们要做两项分析。第一是从数学上证明算法的正确 性，这一步主要用到形式化证明的方法及相关推理模式，如循环不变式、数学归纳法等。而 在证明算法是正确的基础上，第二部就是分析算法的可能选用多项式阶。(nk)的算法，而不希望用指教阶的算法。
常见的算法时间复杂度由小到大依次为：O (1)v O (log2n) v O (n)v O (nlog2n) v
O (n2) v O (n3)v …v O (2n) v O (n!)
一般情况下，对一个问题(或一类算法)只需选择一种基本操作来讨论算法的时间 复杂度即可，有时也需要同时考虑凡种基本操作，甚至可以对不同的操作赋予不同的权值， 以反映执行不同操作所需的相对时间，这种做法便于综合比较解决同一问题的两种完全不同 的算法。
求解算法的时间复杂度的具体步骤是：
⑴找出算法中的基本语句；
算法中执行次数最多的那条语句就是基本语句，通常是最层循环的循环体。
⑵计算基本语句的执行次数的数量级；
只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中 的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并 且使注意力集中在最重要的一点上：增长率。
⑶ 用大0记号表示算法的肘间性能。
将基本语句执行次数的数量级放入大0记号中。
如果算法中包含嵌套的循环，则基本语句通常是最层的循环体，如果算法中包含并列的 循环，则将并列循环的肘间复杂度相加。例如：
[java] view plaincopy
1.
for
(i = 1; i<=n; i++)
2.
x++;
3.
for
(i = 1; i<=n; i++)
4.
for (j = 1; j< = n; j++)
5.
x++;
第一个for循环的肘间复杂度为0(n)，第二个for循环的肘间复杂度为0(n2)，则整个 算法的肘间复杂度为0(n+n2)=0(n2)。
。⑴表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句， 其肘间复杂度就是0(1)。其中0(log2n)、0(n)、 0(nlog2n)、0(n2)和0(n3)称为多项式 肘间，而0(2n)和0(n!)称为指教时间。计算机科学家普遍认为前者(即多项式肘间复杂度 的算法」是有效算法，把这类问题称为P(Polynomial,多项式)类问题，而把后者(即指数 肘间复杂度的算法」称为NP(Non-Deterministic Polynomial,非确定多项式)问题。
一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是 说，这样的问题，对于一个规模是口的输入，在n人k的肘间得到结果，称为P问题。有些 问题要复杂些，没有多项式肘间的解，但是可以在多项式肘间里验证某个猜测是不是正确。 比如问4294967297是不是质数？如果要直接入手的话，那么要把小于4294967297的平 方根的所有素数都拿出来，看看能不能整除。还好欧拉告诉我们，这个数等于641和6700417 的乘积，不是素数，很好验证的，顺使麻烦转告费马他的猜想不成立。大数分解、Hamilton 回路之类的问题，都是可以多项式肘间验证一个“解”是否正