算法运行时间分析

时间复杂度:O(n)

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

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

<caption> 常见的时间复杂度及对应典型算法 </caption>
描述 增长量级 典型代码 说明 举例
常数级别 1
a = b + c ;

 

普通语句 两数相加
对数级别
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
for(int i = 0;i < N; i++){
    
    a++;
    
}

 

循环 自增
线性对数级别
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. 均摊分析
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务