数据结构与算法1-复杂度分析1

为什么需要复杂度分析?
有两种估算方法:1.事后统计法 2.大O复杂度表示法

  1. 事后统计法: 把代码跑一遍,通过统计、监控,就能得到算法执行的时间和占用的内存大小
  • 测试结果非常依赖测试环境
  • 测试结果受数据规模的影响很大
  1. 我们需要一个不用具体的测试数据来测试,就可以粗略的估计计算法的执行效率的方法——大O复杂度表示法
    从CPU角度看,代码的执行类似这种操作:读数据——运算——写数据。
    所有代码的执行时间T(n)与每行代码的执行次数n成正比。T(n)=O(f(n)),例:T(n)=O(2n+2),T(n)=O(2n²+2n+3)
    大O时间复杂度实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以也叫,渐进时间复杂度,简称时间复杂度。T(n) = O(n); T(n) = O(n²)。

时间复杂度分析

  1. 只关注循环执行次数最多的一段代码:核心代码执行次数的 n 的量级,就是整段要分析代码的时间复杂度
  2. 加法法则:总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

几种常见时间复杂度实例分析

常量阶O(1) 对数阶O(logn)  线性阶O(n) 线性对数阶O(nlogn)
指数阶O(2^n)       阶乘阶O(n!)

粗略分为两类:多项式量级和非多项式量级,非多项式量级只有两个:O(2^n)和O(n!)。