文章编目算法的时间复杂度和空间复杂度分析1 .时间维后验统计法预分析估计方法时间复杂度(1)时间频率(2)时间复杂度大o码表示法常见的时间复杂度量级o(1)线性量级o(n )线性对数量级o(nlogn )平方量级
算法的时间复杂度和空间复杂度
首先让我们了解什么是算法。 算法(Algorithm )是一组用于处理数据和解决程序问题的方法。 但是，针对同一个问题，我们试着使用不同的算法，结果可能会是一样的，不同的地方是你在所用算法上花费的资源和时间。 这个博客被用来衡量不同算法的优劣。
复杂度分析衡量不同算法的优劣，主要基于算法所占的3358www.Sina.com/和空间两个维度来考虑。 但是，世界上不存在完美的代码。 不消耗最多的时间和空间。 鱼和熊掌不能兼得。 那么，你需要取得平衡，写出更完美的代码。
一.时间维度是指执行当前算法所需的时间，通常用时间描述。
算法的执行时间是根据该算法制作的程序在计算机上执行时所消耗的时间来测量的。 测量程序的执行时间通常有两种方法
事后统计法这个方法是可能的，但不是好方法。 这个方法有两个缺点。 一是要评估所设计算法的运行性能，必须首先基于算法编制相应的程序并实际运行； 二是得到的时间统计量取决于计算机的硬件、软件等环境因素，容易掩盖算法本身的优势。
先验分析估计的方法由于后验统计的方法多依赖于计算机硬件、软件等环境因素，往往容易掩盖算法本身的优劣。 因此，经常采用事先分析和估算的方法。
编制程序前，根据统计方法估算算法。 程序在计算机上运行的时间取决于以下因素：
(1)算法采用的策略、方法； (2) .编译代码质量)3)输入问题的规模)4)机器执行命令的速度。
时间复杂度)1)时间频率运行一个算法所需的时间，理论上无法计算，必须在机上运行测试才能知道。 但是，没有必要测试所有的算法。 你只需要知道哪个算法需要时间，哪个算法不需要时间。 另外，一个算法所需的时间与算法中语句的执行次数成比例，任何算法中语句的执行次数多都会花费时间。 算法中语句的执行次数称为语句频率或时间频率。 记为t(n )。
)时间复杂度在刚才提到的时间频率中，n称为问题的规模，当n不断变化时，时间频率t(n )也不断变化。 但有时我们想知道它在变化时呈现出什么规律。 为此，我们引入了时间复杂度的概念。 一般来说，算法中基本操作的重复次数是问题规模n的某个函数，用t(n )表示，如果有某个辅助函数f ) n，则在n接近无限大时，为时间复杂度
大o符号表示法先看一个例子
for(I=1； i=n； I () j=I； j； }根据“大o符号表示法”，该代码的时间复杂度为o(n )。 为什么会这样呢？
在大o符号表示法中，时间复杂度的公式是t(n )=o(f ) n。 这里，f ) n表示各行的代码执行次数之和，o表示正比关系。 该公式的全称是算法的渐进时间复杂度。
请看上面的例子。 假设每行代码的执行时间相同。 用1粒子时间表示。 本例中，第一行的时间为1粒子时间，第三行的执行时间为n粒子时间，第四行的执行时间也为n粒子时间。 (第2行和第5行是符号，所以暂时忽略。 )于是，总时间为1粒子时间n粒子时间。 即，(1 2n )个粒子时间，即t(n )=) 1 2n )粒子时间，根据该结果可知，该算法时间随着n的变化而变化，因此，该算法的时间复杂度为t(n )。
为什么能这样简化呢，因为大o符号表示法并不是为了实际表示算法的执行时间，而是为了表示代码的执行时间的增加倾向。
因此，在上述例子中，在n无限大的情况下，t(n )=time )1) 2n )的常数1没有意义，倍数2也没有什么意义。 因此，直接简化为t(n )=o ) n )即可。
一般时间复杂度订单常数阶o(1) )。
对数步长o(logn ) )
线性阶数o(n )
对数阶数o(nlogn )
平方层o(N2 ) ) ) ) ) )。
立方o(N3 ) )。
k次幂阶o(NK ) )。
指数步长(2n )
从上到下依次增加了时间复杂度，降低了执行的效率。
选择几个一般的说明吧
无论执行了多少次o(1)代码，对于没有循环等的复杂结构，该代码的时间复杂度都为o ) 1，如下所示：
int i=1； int j=2； I； j； int m=i
+ j;上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。
线性阶O(n)这个在最开始的代码示例中就讲解过了，如：
for(i=1; i<=n; ++i){ j = i; j++;}这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。
对数阶O(logN) int i = 1;while(i<n){ i = i * 2;}从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n
也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)
线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。
就拿上面的代码加一点修改来举例：
for(m=1; m<n; m++){ i = 1; while(i<n) { i = i * 2; }} 平方阶O(n2)平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。
举例：
这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)
如果将其中一层循环的n改成m，即：
那它的时间复杂度就变成了 O(m*n)
立方阶O(n³)、K次方阶O(n^k)参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。
除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。
二、空间维度类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。
空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：
空间复杂度O(1)如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)
举例：
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)
空间复杂度O(n) int[] m = new int[n]for(i=1; i<=n; ++i){ j = i; j++;}这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)