naturalCloud

记录精彩的程序人生

目录
复杂度分析
/  

复杂度分析

day 1

  1. 复杂度分析指标
    程序运行消耗的时间尺度
    程序运行消耗内存空间的大小
  2. 分析方法
    • 写完代码运行: 事后分析
      局限:
      1. 测试结果非常依赖测试环境
      2. 受数据规模影响较大
  3. 大O表示法
    CPU角度,每行代码基本都在做 读数据-运算-写数据。
    得出结论:代码的执行时间 T(n) 与每行代码的执行次数成正比。
  4. 时间复杂度分析方法
    • 关注循环执行次数最多的代码
    • 加法法则:总复杂度等于量级最大的那段代码复杂度
    • 乘法法则: 嵌套代码复杂度等于嵌套内外复杂度的乘积
  5. 常见的时间复杂度级别
    • O(1)
      代码中不存在循环,递归。
    • O(logn) O(nlogn)
      忽略系数
    • O(m+n) O(m*n)
      代码复杂度有两个数据规模决定
  6. 空间复杂度
    渐进空间复杂度:算法的存储空间和数据规模之间的增长关系

day2

  1. 最好情况时间复杂度(best case time complexity)
  2. 最坏情况时间复杂度(worst case time complexity)
  3. 平均情况时间复杂度(average case time complexity)
  4. 均摊时间复杂度(amortized time complexity


标题:复杂度分析
作者:naturalCloud
地址:https://yunqiblog.cn/articles/2019/11/25/1574686290199.html

评论