本文共 2006 字，大约阅读时间需要 6 分钟。
时间复杂度
➢ 时间复杂度概述
- 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)表示， 若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n) /f(n)的极限值为不等于零的常数，则称f(n)是 T(n)的同数量级函数。记作T(n)=O(f(n)),称0(f(n))为算法的渐进时间复杂度，简称时间复杂度。
- T(n)不同， 但时间复杂度可能相同。如: T(n)=n2+7n+6 与T(n)=3n2+2n+2它们的T(n)不同，但时间复杂度相同，都为0(n2)。
- 计算时间复杂度的方法:
- 用常数1代替运行时间中的所有加法常数
- 修改后的运行次数函数中，只保留最高阶项
- 去除最高阶项的系数
➢基本介绍
时间频度: -个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)➢常见的时间复杂度
1. 常数阶 无论代码执行了多少行，只要没有复杂的循环结构，那这个代码的时间复杂度就都是O(1)
// 常数阶 int i = 1; int j = 1; i++; j++; System.out.println(i + j);
上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用O(1)来表示它的时间复杂度。
2. 对数阶
// 对数阶 int i = 1; while (i < n) { i = i * 2; } 说明:在while 循环里面，每次都将 i 乘以2,乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于2了，此时这个循环就退出了，也就是说2的 x次方等于n ,那么x = log2 n也就是说当循环log2n次以后，这个代码就结束了。因此这个代码的时间复杂度为:O(log2n)。Ologxn) 的这个2时间上是根据代码变化的，i = i * 3， 则是O(log3n)。
如果N= a^x( a > 0,a != 1),即的x次方鄂于N (a > 0,且a != 1) ,那么数叫做以为底N的对数 ,记作 x= log2N,其中,叫做对数的底数, N做真数,x叫做以a底N的对数。3. 线性阶
for (int i = 0; i < n; i++) { int j = i; i++; } 以上代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。
4. 线性对数阶
for (int m = 1; m < n; m++) { int i = 1; while (i < n) { i = i * 2; } } 如上代码所示：将时间复杂度为O(logn)的（对数阶）代码循环N遍的话，那么它的时间复杂度就是n* O(log2N),也就是了O(n log2N)
5. 平方阶
for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { i++; j++; } } 如果把O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n),这段代码其实就是嵌套了2层n循环，它的时间复杂度就是O(n*n),即O(n^2) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了O(m * n)
6. 立方阶
相当于3层for循环代码，时间复杂度为 O( n ^3)
7. k次方阶
同上，循环k次，时间复杂度为O(n ^ k)
➢ 平均时间复杂度和最坏时间复杂度
- 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。
- 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
- 平均时间复杂度和最坏时间复杂度是否一致，和算法有关。
空间复杂度
➢ 基本介绍
- 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
- 空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况
- 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存 产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.
转载地址：http://eemzi.baihongyu.com/