加载中…
个人资料
教师说
教师说
  • 博客等级:
  • 博客积分:0
  • 博客访问:108,670
  • 关注人气:6
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

时间复杂度和空间复杂度

(2019-09-04 19:45:09)
标签:

教育

暑期复习马上接近尾声了相信很多同学已经过了一遍专业课知识点。只有当我们熟练掌握了基础知识,才能更好复习备考的你是否开始做题巩固知识点了呢今天给大家整理了数据结构课程时间复杂度和空间复杂度的知识点,希望对大家有所帮助!以下是相关知识点。

一、算法的时间复杂度

算法的时间量度指的是算法中基本操作重复执行的次数。

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))通常称为时间复杂度,其中O的形式定义为:若f(n)是正整数n的一个函数,则xn=O(f(n))表示存在一个正的常数M,使得当nn0时都满足|xn|M|f (n)|

注意:基本操作是其重复执行的次数和算法的执行时间成正比的原操作,多数情况下它是最深层循环内的语句中的原操作,它的执行次数和包含它的语句的频度是相同的。语句的频度指的是该语句重复执行的次数。

算法的时间复杂度

类似于算法的时间复杂度,以空间复杂度作为算法所需存储空间的量度,记作S(n)=O(f(n))其中n为问题的规模。一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外,也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。若输入数据所占空间只取决于问题本身,和算法无关,则只需要分析除输入和程序之外的额外空间。

算法原地工作指的是额外空间相对于输入数据量来说是常数。

接下来我们以一个简单的小程序段来分析时间复杂度和空间复杂度,例如将一维数组中的元素逆置存放

分析该算法,由于基本语句就是循环内的交换语句,共执行了n/2次,所以T(n) = n/2 = O(n)。又因为算法的辅助空间只是ijt3个临时变量的空间,所以S(n) = 3 = O(1)。而因为这里使用的辅助空间,不会随着问题的规模变化而变化,简而言之,就是常量级别的,我们就称其为原地工作。

暑期虽然是考研黄金备考期,但是由于暑期天气炎热,学校放假等,暑期备考承受很多的艰辛和压力,但是相信大家都坚持下来了。接下来的备考也是非常艰难的一段时光,希望同学们都能放平心态,不忘初心,抓住黄金备考期!

相关信息可点击陕西研招网

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有