学弟学妹别看教材了,时间复杂度这篇看不懂找我要红包

苦逼的码农

共 1296字,需浏览 3分钟

 ·

2021-10-01 23:41

时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度

一、刻画算法的运行时间

某日,慧能叫来了一尘打算给他补习补习一下基础知识,只见克写了一段非常简单的代码









一尘看老师有点生气,开始虚心请教了

i


为了方便讨论,这里我们把每一条语句的执行时间都看做是一样的,记为一个时间单元




① 蓝色框的两条语句,花费两个时间单元

②黑色框的一条语句,花费n+1个时间单元

③红色框的两条语句,花费2*n个时间单元


这不是数学吗,一尘心里想到


其中的n被我们称为问题的规模,其实就是你处理问题的大小

慧能顺手画了这个函数的图


本文主要讨论问题规模和运行时间的关系,假定不同输入和运行时间基本无关






二、时间复杂度


比如说:T(n)=3n+3, 当n非常大的时候常数3和n的系数3对函数结果的影响就很小了



比如:

T(n)=n+1 忽略常数项 T(n)~n

T(n)=n+n^2 忽略低阶项 T(n)~n^2

T(n)=3n 忽略最高阶的系数 T(n)~n






还好不用掌握那头疼的数学,一尘心中想到


一尘把话题又拉了回来




更准确地说O代表了运行时间函数的一个渐进上界,即T(n)在数量级上小于等于f(n)


三、时间复杂度的计算


一、得出运行时间的函数               
二、对函数进行简化

①用常数1来取代运行时间中所有加法常数

②修改后的函数中,只保留最高阶项      ③如果最高阶项存在且不是1,则忽略这个项的系数




O(1)也被称为常数阶






一尘随手写了一段嵌套循环的代码






接着,慧能又写了一段时间复杂度为对数的代码




一向数学不太好的一尘此时有点懵







总结


算法的学习,第一步就是得先知道啥是时间复杂度,啥是空间复杂度,其实你懂了时间复杂度,也就懂了空间复杂度,建议各位还在校的小伙伴,一定要把数据结构和算法这门课学好。

END

最后,欢迎大家加入帅地的知识星球,星球里有很多热爱学习的小伙伴,一群人一起学习不孤单。

并且你有任何学习上的疑问,帅地都会指导你应该如何学习,根据你的情况为你量身定制,在星球会提供如下服务:

1、【一对一咨询服务】48 小时以内详细回答你的任何问题,包括写作等等,这是知识星球最重要的功能。最近一周就回答了十几个 offer 选择,校招等学习路线问题。

2、【学习攻略】校招这方面比较有经验,帅地会提供完整的学习攻略,小白跟着帅地说的学习就行,这块会在最近出。

3、简历修改,项目等学习资源,offer 收割机嘉宾分享等等。

目前星球是专注于校招,在校生学习指导这块,一定可以让你少走弯路,已经有 490+ 位小伙伴加入,这里还有一些 20 元的优惠卷,如果你信的过帅地,那么欢迎你的加入。


想具体了解可以看这篇文章:我的四年大学


浏览 24
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报