QQ登录

只需一步,快速开始

搜索
查看: 143|回复: 0

[学习笔记] 数据结构(三)时间复杂度与空间复杂度

[复制链接]
最佳答案
0 
累计签到:21 天
连续签到:1 天
发表于 2017-8-12 17:27:55 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

本学习笔记由《大话数据结构》第二章学习整理而来,本学习笔记里涉及的程序是基于C语言的
运行时间是度量时间复杂度的指标,而测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数,运行时间与这个计数成正比。算法时间复杂度的定义:在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况,并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)=O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f(n)是问题规模n的某个函数。

这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。例如O(n),O(1)。

下面给出分析一个算法时间复杂度大O阶的方法:
推导大O阶:
1.计算出此算法总共的操作执行次数T(n)。
2.用常数1取代运行时间中的所有加法常数。
3.在修改后的运行次数函数中,只保留最高阶项。
4.如果最高阶项存在且不是1,则去除与这个项相乘的常数。
得到的结果就是大O阶。


评分

参与人数 1鱼币 +2 收起 理由
小甲鱼 + 2

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-10-17 15:36 Powered by Discuz! X2.5 Theme by dreambred

快速回复 返回顶部 返回列表