算法运行时间分析

时间复杂度：O(n)

注意Ｏ(n)是用估计的方式,涉及极限的定义,假设摸个程序的语句执行次数为,则其时间复杂度为中较大的影响最大的增量函数

例如:其时间复杂度 O(n) = 

<caption> 常见的时间复杂度及对应典型算法 </caption>

描述	增长量级	典型代码	说明	举例
常数级别	1	1 a = b + c ;	普通语句	两数相加
对数级别		1 2 3 4 5 6 7 8 9 10 11 while(lo<=hi){     int mid = lo+(hi-lo)/2;          if(key<a[mid]) hi = mid+1;          else if(key>a[mid]) lo = mid-1;          else return mid; }	二分策略	二分查找
线性级别	N	1 2 3 4 5 for(int i = 0;i < N; i++){          a++;      }	循环	自增
线性对数级别		1 2 3 4 5 6 7 8 9 10 11 void sort(int[] a,int lo,int hi){     if(hi<=lo) return;     int mid  = lo +(hi -lo)/2;     sort(a,lo,hi);          sort(a,mid+1,hi); }	分治 （固定次数内部出现二分策略）	归并排序
平方级别		二重循环,懒得写了	二重循环	二维数组的遍历
立方级别		三重循环,懒得写了	三层嵌套	三维数组的遍历
指数级别		穷举算法,基本暴力算法都是,最典型的是RSA大数因式分解,到了这个级别的基本就GG了,但很多问题似乎只能用这个	穷举查找	RSA质因数分解

 

其他评估：

1. 可行性（先进行算法评估，能否实现，运行时间是否满足要求）
2. 计算机本身性能（尽量使用更快的计算机）
3. 大常数（因为O(n)是极限的思想，但算法的运行时间必须有限，这时候有可能出现常数对算法的影响不亚于高阶增长，不能舍弃,其他项亦然）
4. 非决定性的内循环（存取数据需要时间等等）
5. 指令时间
6. 系统因素（多任务）
7. 应用场景（不同的场景，不同算法优劣性不同）
8. 输入输出依赖（因为输入输出耗时）
9. 多问题参量（还有其他额外条件限制）

 

其他：

1. 最坏情况和最好情况（上下界）
2. 随机化算法
3. 操作序列
4. 均摊分析

 

引自：https://blog.nowcoder.net/n/2abdda44940e4cbfab83c192876bc9ad