2022年下半年软件测评师知识点锦集：算法的复杂度

•时间复杂度

是指程序运行从开始到结束所需要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的问题来说是基本运算的操作，以该操作重复执行的次数作为算法的时间度量

•空间复杂度

是指对一个算法在运行过程中临时占用存储空间大小的度量。一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小

•3种常用的标准方法

O记号：定义为：给定一个函数g（n），O（g（n））={f（n）：存在正常数c和n₀，使得对所有的n≥n₀，有0≤f（n）≤cg（n）}，O（g（n））表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界。

Ω记号：定义为：给定一个函数g（n），Ω（g（n））={f（n）：存在正常数c和n₀，使得对所有的n≥n₀，有0≤cg（n）≤f（n）}，Ω（g（n））表示一个函数集合，往往用该记号给出一个算法运行时间的渐进下界。

Θ记号：定义为：给定一个函数g（n），Θ（g（n））={f（n）：存在正常数c₁，c₂和n₀，使得对所有的n≥n₀，有0≤c₁g（n）≤f（n）≤c₂g（n）}，Θ（g（n））表示一个函数集合，往往用该记号给出一个算法运行时间的渐进上界和渐进下界，即渐进紧致界。

•算法分析的3种情况

（以算法的时间复杂度为例）

最佳情况：使算法执行时间最少的输入。一般情况下，不进行算法在最佳情况下的时间复杂度分析。如：比较的排序算法的时间复杂度下限为：Ω（nlgn）。

最坏情况：使算法执行时间最多的输入。最坏情况是在任何输入下运行时间的一个上限，给提供一个保障不会出现更糟糕的情况。

平均情况：算法的平均运行时间，一般来说，这种情况很难分析。

•排序算法的复杂度

•常见的对算法执行所需时间的度量

O（1）<O（log₂n）<O（n）<O（nlog₂n）<O（n²）<O（n³）<O（2ⁿ）