算法的时间复杂度
文章目录
- 算法的时间复杂度
- 时间频度
- 举例说明-忽略常数项
- 举例说明-忽略低次项
- 举例说明-忽略系数
- 时间复杂度
- 常见的时间复杂度
- 常数阶O(1)
- 对数阶O(**log2n**)
- 线性阶O(n)
- 线性对数阶O(n**log2N**)
- 平方阶O(n^2^)
- 立方阶O(n^3^)、k次方阶O(n^k^)
- 平均时间复杂度和最坏时间复杂度
- 空间复杂度
- 基本介绍
度量一个程序（算法）执行时间的两种方法
- 事后统计的方法（这种方法可行，但是有两个问题：一是要想对设计的算法的运行性能进行测评，需要实际运行该程序；二是所的时间的统计量依赖于计算机的硬件，软件等环境因素，这种方法，要在同一台计算机的相同状态下运行，才能比较出哪个算法的速度比较快。）
- 事前估算的方法（通过分析某个算法的时间复杂度来判断哪个算法更优。）
时间频度
时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费的时间就多。一个算法中的语句执行次数称为语句频度或时间频度记为T(n)。
举例说明-基本案例
比如计算1-100所有数字之和，我们设计两种算法：
int total = 0;
int end = 100;
//使用for循环计算
for(int i = 1;i <= end;i ++) {
total += i;
}
如若计算100内数字的和，那么n为100，n+1=101，因为到101时，也需要对for循环进行判断。
T(n) = n + 1
//直接计算
total = (1 + end) * end / 2;
T(n) = 1
举例说明-忽略常数项
| T(n)=n2+20 | T(n)=2n | T(n)=3n+10 | T(n)=3n | |
|---|---|---|---|---|
| 1 | 22 | 2 | 13 | 3 |
| 2 | 24 | 4 | 16 | 6 |
| 5 | 30 | 10 | 25 | 15 |
| 8 | 36 | 16 | 34 | 24 |
| 15 | 50 | 30 | 55 | 45 |
| 30 | 80 | 60 | 100 | 90 |
| 100 | 220 | 200 | 310 | 300 |
| 300 | 620 | 600 | 910 | 900 |
结论：
- 2n+20 和 2n随着n变大，执行曲线无限接近，20可以忽略。
- 3n+10 和 3n随着n变大，执行曲线无限接近，30可以忽略。
举例说明-忽略低次项
| T(n)=2n2+3n+10 | T(n)=2n2 | T(n)=n2+5n+20 | T(n)=n2 | |
|---|---|---|---|---|
| 1 | 15 | 2 | 26 | 1 |
| 2 | 24 | 8 | 34 | 4 |
| 5 | 75 | 50 | 70 | 25 |
| 8 | 162 | 128 | 124 | 64 |
| 15 | 505 | 450 | 320 | 325 |
| 30 | 1900 | 1800 | 1070 | 900 |
| 100 | 20310 | 20000 | 10520 | 10000 |
结论：
- 2n2+3n+10 和 2n2 随着n变大，执行曲线无限接近，可以忽略3n+10
- n2+5n+20 和 n2 随着n变大，执行曲线无限接近，可以忽略5n+20
举例说明-忽略系数
| T(n)=3n2+2n | T(n)=5n2+7n | T(n)=n3+5n | T(n)=6n3+4n | |
|---|---|---|---|---|
| 1 | 5 | 12 | 6 | 10 |
| 2 | 16 | 34 | 18 | 56 |
| 5 | 85 | 160 | 150 | 770 |
| 8 | 208 | 376 | 552 | 3104 |
| 15 | 705 | 1230 | 3450 | 20310 |
| 30 | 2760 | 4710 | 27150 | 162120 |
| 100 | 30200 | 50700 | 1000500 | 60004000 |
结论：
- 随着n值变大，3n2+2n 和 5n2+7n，执行曲线重合，说明，这种情况下，5和2可以忽略。
- 而 n3+5n 和 6n3+4n，执行曲线分离，说明多少次方式关键
时间复杂度
- 一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)标识，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间辅助度，简称时间复杂度。
- T(n)不同，但时间复杂度可能相同。如T(n)=n2+7n+6 与 T(n)=3n2+2n+2 它们的T(n)不同，但是时间复杂度相同，都为O(n2)。
- 计算时间复杂度的方法
- 用常数1代替运行时间中所有的加法常数
- 修改后的运行次数函数中，只保留最高阶项
- 去除最高阶项的系数
常见的时间复杂度
- 常数阶O(1)
- 对数阶O(log2n)
- 线性阶O(n)
- 线性对数阶O(nlog2N)
- 平方阶O(n2)
- 立方阶O(n3)
- k次方阶O(nk)
- 指数阶O(2n)
说明：
- 常见的算法时间复杂度由小到大依次为：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(nk)<O(2n)，随着问题规模n的不断增大的，上述时间复杂度不断增大，算法的执行效率越低。
- 应该尽可能的避免使用指数阶的算法
常数阶O(1)
无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就是O(1)
int i = 1;
int j = 2;
++ i;
j ++;
int m = i + j;
上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万行，几十万行，都可以用O(1)来表示它的时间复杂度。
对数阶O(log2n)
int i = 1;
while (i < n)
{
i = i * 2;
}
说明： 在while循环里面，每次都将i乘以2，乘完之后，i 距离 n 就越来越近了。假设循环 x 次后，i 就大于 2 了，此时这个循环就退出了。也就是说 2 的 x次方等于 n ，那么 x =log2n 也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n ) 。O(log2n ) 的这个 2 时间上是根据代码变化的，i = i * 3 ，则是O(log3n ) 。
线性阶O(n)
for (i = 1;i <= n;++ i)
{
j = i;
j ++;
}
说明： 这段代码，for循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度
线性对数阶O(nlog2N)
for (m = 1;m < n;m ++)
{
i = 1;
while (u < n)
{
i = i * 2;
}
}
说明： 线性对数阶O(nlog2N)其实非常容易理解的，将时间复杂度为O(log2n)的代码循环n遍的话，那么它的时间复杂度就是 n * O(log2N)，也就是O(nlog2N)
平方阶O(n2)
for (x = 1;i <= n;x ++)
{
for (i = 1;i <= n;i ++)
{
j = i;
j ++;
}
}
说明： 平方阶O(n2)就更容易理解了，如果把平方阶O(n)的代码再嵌套循环一遍，它的时间复杂度就是O(n2)，这段代码其实就是嵌套了2层 n 循环，它的时间复杂度就是O(n*n)，即O(n2)，如果将其中一层循环的 n 改成 m ，那它的时间复杂度就变成了O(n*m)
立方阶O(n3)、k次方阶O(nk)
说明： 参考上面的O(n2)去理解就好了，O(n3)相当于三层 n 循环，其它的类似
平均时间复杂度和最坏时间复杂度
- 平均时间复杂度是指所有可能的输入实例均已等概率出现的情况下，该算法的运行时间。
- 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。
- 平均时间复杂度和最坏时间复杂度是否一致，和算法有关。
| 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
|---|---|---|---|---|---|
| 冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 交换 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 选择 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数(0-9),R是基数(个十百) |
| Shell | O(nlogn) | O(ns)1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时比较好 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
| 堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
空间复杂度
基本介绍
- 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
- 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。
- 在做算法的分析时，主要讨论的是时间复杂度。从用户使用的体验上看，更看重的程序执行的速度。一些缓存产品(redis,memcache)和算法(基数排序)本质就是用空间换时间。
毕竟编程我还是是初学者，如若有理解错误的地方，希望大家看完之后，发现错误可以评论出来，谢谢大家！
