各位学弟学妹,别再看教材了,时间复杂度看这篇就好了[通俗易懂]

各位学弟学妹,别再看教材了,时间复杂度看这篇就好了[通俗易懂]时间复杂度是学习算法的基石,今天我们来聊聊为什么要引入时间复杂度,什么是时间复杂度以及如何去算一个算法的时间复杂度一、刻画算法的运行时间某日,慧能叫来了一尘打算给他补习补习一下基础知识,只见克写了一段非常简单的代码一尘看老师有点生气,开始虚心请教了为了方便讨论,这里我们把每一条语句的执行时间都看做是一样的,记为一个时间单元①蓝色框的两条语句,花费两个时间单元②黑色框的一条语句,花费n+1个时间单元③红色框的两条语句,花费2*n个时间单元这不是.

大家好,又见面了,我是你们的朋友全栈君。

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

一、刻画算法的运行时间

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

图片

image-20210426023110170

image-20210426023130801

image-20210426023148555

image-20210426023211105

图片

image-20210426023246693

image-20210426023310271

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

image-20210426023342540

图片

image-20210426023414239

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

image-20210426023526558

图片

image-20210426023557995

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

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

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

image-20210426023628861

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

image-20210426023704277

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

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

图片

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

image-20210426023934437

image-20210426024024167

image-20210426024046867

image-20210426024103613

image-20210426024120916

二、时间复杂度

image-20210426024201373

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

图片

image-20210426024250558

比如:

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

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

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

image-20210426024423010

image-20210426024443197

image-20210426024500918

image-20210426024528079

图片

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

image-20210426024617355

一尘把话题又拉了回来

image-20210426024648521

图片

image-20210426024740873

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

image-20210426024822915

三、时间复杂度的计算

image-20210426150816680

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

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

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

image-20210426151026142

图片

image-20210426151057711

O(1)也被称为常数阶

image-20210426152505884

image-20210426151148761

图片

image-20210426151218373

image-20210426151246271

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

图片

image-20210426151329834

image-20210426151350040

image-20210426151412651

图片

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

图片

image-20210426151716075

image-20210426151749173

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

image-20210426151639851

图片

image-20210426151926308

image-20210426151945634

image-20210426152009959

image-20210426152029236

image-20210423191506418

总结

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

无论是面试还是提升自己的内容,算法学习基本少不了,我这里给大家推荐一份某 BAT 大佬总结的 Leetcode 刷题笔记:BAT 大佬分类总结的 Leetcode 刷题模版,助你搞定 90% 的面试

另外,帅地也把排序算法系列文章用漫画写好了,这里直接贴出链接吧,你们负责收藏就好了,嘿嘿。不过这里只给出了 7 种必须掌握的排序算法,像桶排序,基数排序这些,了解即可,后期也会写出来滴。

漫画:什么是冒泡排序算法?

漫画:什么是选择排序算法?

漫画:什么是插入排序算法?

漫画:什么是希尔排序算法?

漫画:什么是归并排序算法?

漫画:什么是快速排序算法?

漫画:什么是堆排序算法?

当然,也欢迎大家来帅地的个人网站玩耍:https://www.iamshuaidi.com,从 0 到 1 总结了帅地的个人学习。

作者简洁

作者:大家好,我是帅地,从大学、自学一路走来,深知算法计算机基础知识的重要性,公众号「帅地玩编程」10万粉丝作者,专业于写这些底层知识,提升我们的内功,帅地期待你的关注,和我一起学习,点击了解我四年大学学 习之路 转载说明:未获得授权,禁止转载

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/146506.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号