小编所收集到的相关公共基础知识考点分析之数据结构与算法的资料 大家要认真阅读哦！
考点2 算法的复杂度
1算法的时间复杂度
算法的时间复杂度，是指执行算法所需要的计算工作量。同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行，效率均不同。这表明使用绝对的时间单位衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模(通常用整数n表示)，它是问题的规模函数。即
算法的工作量=f(n)
例如，在N×N矩阵相乘的算法中，整个算法的执行时间与该基本操作(乘法)重复执行的次数n3成正比，也就是时间复杂度为n3，即
f(n)=O(n3)
在有的情况下，算法中的基本操作重复执行的次数还随问题的输入数据集不同而不同。例如在起泡排序的算法中，当要排序的数组a初始序列为自小至大有序时，基本操作的执行次数为氏当初始序列为自大至小有序时，基本操作的执行次数为n(n- 1)/2。对这类算法的分析，可以采用以下两种方法来分析。
(1)平均性态(Average Behavior)
所谓平均性态是指各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。
设x是所有可能输入中的某个特定输入，p(x)是x出现的概率(即输入为x的概率)，t(x)是算法在输入为x时所执行的基本运算次数，则算法的平均性态定义为
其中Dn表示当规模为n时，算法执行的所有可能输入的集合。
(2)最坏情况复杂性(Worst-case Complexity)
所谓最坏情况分析，是指在规模为n时，算法所执行的基本运算的最大次数。
2算法的空间复杂度
算法的空间复杂度是指执行这个算法所需要的内存空间。
一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，则称该算法是原地(in place)工作的。在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
文字很枯燥，但内容却很丰富，小编在此祝大家都能考出让自己满意的成绩哦！
继续了解公共基础知识？点击下方链接，进入考无忧官方网站，更多精彩等你来！
小编特别推荐二级ms office可以了解一下噢！ 毕竟这项科目着实相比其他科目比较容易啦！
文章推荐：
温馨提示：
想要了解更多试题请点击查看>>>计算机二级考试题库
考试想拿高分吗？更多二级ms office试题请点击查看>>>二级ms office
想知道更多关于计算机等级考试的最新资讯吗？点击进入>>>计算机等级考试
