计算机二级考试公共基础知识章节知识点-算法复杂度

　　算法的复杂度包括时间复杂度和空间复杂度
　　1）时间复杂度

　　即实现该算法需要的计算工作量。算法的工作量用算法所执行的基本运算次数来计算
　　同一个问题规模下，如果算法执行所需要的基本次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：

　　算法工作量=f(n)

　　（1）平均性态

　　用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量
　　设x是某个可能输入中的某个特定输入，p(x)是x出现的概率，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为：

　　Dn表示当规模为n时，算法执行时所有可能输入的集合
　　（2）最坏情况复杂度

　　指在规模为n时，算法所执行的基本运算的最大次数。它定义为：

　　2）算法的空间复杂度

　　指要执行该算法所需要的内存空间。算法所占用的内存空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，如执行过程中工作单元以及某种数据结构所需要的附加存储空间等。