不容错过!计算机二级公共基础知识学习教程:算法的复杂度

发布于 2018-08-02 15:30  编辑:jokex
0
计算机等级考试题库 扫码微信刷题

小编所收集到的相关计算机二级公共基础知识学习教程:算法的复杂度的资料 大家要认真阅读哦!



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

1)时间复杂度

即实现该算法需要的计算工作量。算法的工作量用算法所执行的基本运算次数来计算。

同一个问题规模下,如果算法执行所需要的基本次数取决于某一特定输入时,可以用以下两种方法来分析算法的工作量:

算法工作量=f(n)

(1)平均性态

用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。

设x是某个可能输入中的某个特定输入,p(x)是x出现的概率,t(x)是算法在输入为x时所执行的基本运算次数,则算法的平均性态定义为:

Dn表示当规模为n时,算法执行时所有可能输入的集合。


(2)最坏情况复杂度

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

例如,在具有n个元素的数列中搜索一个数x。

平均性态:

即该数在数列中任何位置出现的数列是相同的,也有可能不存在,存在的概率为q。

如果有一半的机会存在,则概率q为1/2,平均性态:

如果查找的元素一定在数列中,则每个数存在的概率即为1,则平均性态为:

最坏情况分析:即要查找的元素X在数列的最后或不在数列中,显然,它的最坏情况复杂度为:



2)算法的空间复杂度

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





文字很枯燥,但内容却很丰富,小编在此祝大家都能考出让自己满意的成绩哦!

继续了解公共基础知识?点击下方链接,进入考无忧官方网站,更多精彩等你来!

小编特别推荐二级ms office可以了解一下噢! 毕竟这项科目着实相比其他科目比较容易啦!


文章推荐:

2018年全国计算机等级考试都有哪些科目?

2018年全国计算机考试报名为什么照片上传不成功?

2018年全国计算机等级考试一二三四级最新考试大纲汇总


温馨提示:

想要了解更多试题请点击查看>>>计算机二级考试题库

考试想拿高分吗?更多二级ms office试题请点击查看>>>二级ms office

想知道更多关于计算机等级考试的最新资讯吗?点击进入>>>计算机等级考试


本文网址:http://www.k51.com.cn/info/jsjdjks/1808/0242810.html
选择分享到: