鱼C论坛

 找回密码
 立即注册
查看: 2880|回复: 0

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

[复制链接]
发表于 2017-8-12 17:27:55 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

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

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

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:49

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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