时间/空间复杂度

算法效率

算法效率分析有两种: 时间效率与空间效率. 时间效率被称为时间复杂度, 空间效率被称为空间复杂度

时间复杂度衡量的是一个算法的运行速度, 空间复杂度衡量的是一个算法所需要的额外空间

大O渐进表示法

大O符号: 用于描述函数渐进行为的数学符号

推导方法

  1. 用常数1取代运行时间中的所有加法常数
  2. 在修改后的运行次数函数中, 只保留最高阶项
  3. 如果最高阶项存在且不是1, 则去除与这个项目相乘的常数. 得到的结果就是大O阶

最坏情况: 任意输入规模的最大运行次数

平均情况: 任意输入规模的期望运行次数

最好情况: 任意输入规模的最小运行次数

一般情况关注的是算法的最坏运行情况

时间复杂度

算法中基本操作的执行次数, 为算法的时间复杂度

空间复杂度

对一个算法在运行过程中临时占用存储空间大小的度量, 空间复杂度算的是变量的个数

 


我们的征途是星辰大海!