浅谈时间复杂度
在此之前，先了解他们是如何产生的。学习数据结构与算法本身就是为了让代码可以高效运行，更省存储空间。而考究算法的质量就用到了时间、空间复杂度。
一、时间复杂度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或「时间频度」。记为T(n)。
时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此我们引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量，记作：T(n) = O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称「时间复杂度」。
这种表示方法我们称为「 大O符号表示法」，又称为渐进符号，是用于描述函数渐进行为的数学符号
T(n)不同，但时间复杂度可能相同。如：T(n) = n2+3n+2，T(n) = n2+5n+8 ，T(n)不同，但时间复杂度都为O(n2)
计算时间复杂度的方法
- 用常数1(代表常数项的复杂度为O(1))来代替运行时间中的所有加法常数
- 修改后的运行次数函数中，只保留了最高阶项
- 去除最高阶项的系数
常见的的时间复杂度(按照按照耗费的时间由低到高排序)：
| 描述 | 时间复杂度 |
|---|---|
| 常数阶 | O(1) |
| 对数阶 | O(logn) |
| 线性阶 | O(n) |
| 线性对数阶 | O(nlogn) |
| 平方阶 | O(n²) |
| 立方阶 | O(n³) |
| k次方阶 | O(nk) |
| 指数阶 | O(2n) |
| 阶乘阶 | O(n!) |
解析
O(1)
O(1)表示常量阶时间复杂度，并非只执行一行代码。代码的的执行时间不是随着n的增大而增大的，这样的代码的时间复杂度都为O(1)。一般来讲算法中不存在循环、递归，即使代码有很多行，时间复杂度依然为O(1)。
public static void main(String[] args){ int a = 2;//执行一次 int b = 3;//执行一次 int sum = a+b;//执行一次}哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
O(n)
O(n)表示线性阶时间复杂度,大部分遍历就是线性级算法。
public static void main(String[] args){int sum = 0;//执行1次int n = 100;//1次for(int i =1; i<=100 ; i++){sum +=i; //执行n次}}O(log2n)
O(log2n)表示对数阶时间复杂度,如下代码，在while循环里面，每次都将 count 乘以 2，乘完之后，count 距离 n 就越来越近了。假设循环x次之后，count 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，count = count * 3 ，则是 O(log2n) 。
int count = 1;while (count < n){ count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */}O(nlog2n)
线性对数阶O(nlogN) 其实就是将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)
for(i = 1 ; i < n ; i++){ int j = 1; while(j < n){ j = j * 2 ; }}O(n²)
表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话，算法的性能将会变为立方阶O(n3)、O(n4)、O(nk)以此类推
for(int i=0;i<n;i++){ // 循环次数为 n for(int j=0;j<n;i++){// 循环次数为 n //复杂度为O(1)的算法 ... } }O(2n)
表示一个算法的性能会随着输入数据的每次增加而增大两倍，典型的方法就是裴波那契数列的递归计算实现
public int getFbnqNum(int n){ if (n <= 1){ return n; } return getFbnqNum(n-1)+getFbnqNum(n-2);}
二、常用排序算法对比
| 排序算法 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 |
| 插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
| 希尔排序 | O(nlog2n) | O(nlog2n) | O(n2) | O(1) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
| 快速排序 | O(nlog2n) | O(nlog2n) | O(n2) | O(nlog2n) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n) | O(n2) | O(n+k) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
(k:代表桶)
©著作权归作者所有：来自51CTO博客作者惜的原创作品，如需转载，请注明出处，否则将追究法律责任更多相关文章
- 双十一中，阿里如何将数据库性能提升100%、响应时间减少80%？
- [白话解析] Flink的Watermark机制
- nginx开启日志，指定格式，查看执行时间
- 更改时间、时区
- (lintcode)第24题 LFU缓存
- JavaScript:时间对象，实例演示右下角广告图
- MySQL字符类型datetime与timestamp
- 如何在Mac上为自己设置“屏幕使用时间”呢？
- 痞子衡嵌入式：恩智浦i.MX RT1xxx系列MCU启动那些事（8.A）- SEMC NAND