算法的基本概念

16uni 2021年04月11日 708次浏览

算法(Algorithm) 就是用一条接一条的指令来解决给定的问题。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法分析

对于同一个问题,存在多个有效算法来解决它。算法分析能够帮助我们确定在时间和空间开销方面哪一种算法是有效的。
算法分析的目标 是根据运行时间及其他一些因素(如内存、开发者的工作量)来比较算法的优劣。

增长率

增长率 就是随着输入规模的增加,算法运行时间增加的速度,它使输入规模的函数。

  • 常用增长率
    time.png
  • 不同增长率之间的关系
    relation.png

算法分析的类型

算法分析有三种类型:

  • 最坏情况
  • 最好情况
  • 平均情况

复杂度分析方法

  1. O表示法

O表示法给出了函数f(n)的严格上限。一般来说,它可以表示为f(n)=O(g(n))。这表示当输入规模很大时,f(n)的上界是g(n)。

  1. Ω表示法

与大O表示法类似,Ω表示法给出了函数f(n)的严格下界,表示为f(n)=Ω(g(n))。

  1. Θ表示法

Θ表示法决定了给定算法的时间增长率的上界和下界是否相同,表示为f(n)=Θ(g(n))。

通常只关注算法时间复杂度的上界(*O*),因为下界(*Ω*)没有实际意义。当上界(*O*)和下界(*Ω*)相同时,则使用*Θ*表示法。
持续更新。。。