数据结构与算法学习笔记之 复杂度分析

前言:

大家都知道数据结构和英语,就如同程序员的两条腿一样;只有不断的积累,学习,拥有了健壮的“双腿”才能越走越远;在数据结构和算法的领域,不得不承认自己就是一只菜鸟;需要不断的学习;在学习过程中,经常会有一些自己的看法,和别人独特的见解;我都会一一做好笔记,以便进步;

正文:复杂度分析

 一、什么是复杂度分析?

1.数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”,而时间、空间复杂度做为数据结构和算法的精髓,很直观说明了代码”多快“”多省“。

2.我们可以从执行时间和占用空间来评估数据结构和算法的性能,也就空间复杂度、时间复杂度,统称为复杂度。

3.复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

二、为什么要进行复杂度分析?

1.测试环境的不稳定因素(如同样的代码,i7比i3快得多),测试规模对测试结果影响很大(有些算法更适用于大规模数据),复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。

2.掌握复杂度分析,将能编写出性能更优的代码,有利于降低系统开发和维护成本。

三、如何进行复杂度分析?

1.大O表示法

1)所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比

  T(n) = O(f(n))

其中T(n)表示算法执行总时间,f(n)表示每行代码执行总次数,而n往往表示数据的规模。

大 O 时间复杂度并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,也叫作渐进时间复杂度,简称时间复杂度,

常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响,所以在做时间复杂度分析时忽略这些项。

2.复杂度分析法则

1)单段代码看高频:比如循环。

2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。

3)嵌套代码求乘积:比如递归、多重循环等

4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。

四、常用的复杂度级别?

多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括, O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)

非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,这类算法性能极差。包括, O(2^n)(指数阶)、O(n!)(阶乘阶)

五、如何掌握好复杂度分析方法?

复杂度分析关键在于多练,所谓孰能生巧。

六、最好、最坏、平均、均摊时间复杂度

一、概念:

1.最坏情况时间复杂度:代码在最理想情况下执行的时间复杂度。 2.最好情况时间复杂度:代码在最坏情况下执行的时间复杂度。 3.平均时间复杂度:用代码在所有情况下执行的次数的加权平均值表示。 4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

二、为什么要引入这4个概念?

1.同一段代码在不同情况下时间复杂度会出现量级差异,为了更全面,更准确的描述代码的时间复杂度,所以引入这4个概念。 2.代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下,是不需要区别分析它们的。

三、如何分析平均、均摊时间复杂度?

1.平均时间复杂度 代码在不同情况下复杂度出现量级差别,则用代码所有可能情况下执行次数的加权平均值表示。 2.均摊时间复杂度 两个条件满足时使用:1)代码在绝大多数情况下是低级别复杂度,只有极少数情况是高级别复杂度;2)低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

 有人说,我们项目之前都会进行性能测试,再做代码的时间复杂度、空间复杂度分析,是不是多此一举呢?

每段代码都分析一下时间复杂度、空间复杂度,是不是很浪费时间呢?

我不认为是多此一举,渐进时间,空间复杂度分析为我们提供了一个很好的理论分析的方向,并且它是宿主平台无关的,能够让我们对我们的程序或算法有一个大致的认识,让我们知道,比如在最坏的情况下程序的执行效率如何,同时也为我们交流提供了一个不错的桥梁,我们可以说,算法1的时间复杂度是O(n),算法2的时间复杂度是O(logN),这样我们立刻就对不同的算法有了一个“效率”上的感性认识。 当然,渐进式时间,空间复杂度分析只是一个理论模型,只能提供给粗略的估计分析,我们不能直接断定就觉得O(logN)的算法一定优于O(n), 针对不同的宿主环境,不同的数据集,不同的数据量的大小,在实际应用上面可能真正的性能会不同,个人觉得,针对不同的实际情况,进而进行一定的性能基准测试是很有必要的,比如在统一一批手机上(同样的硬件,系统等等)进行横向基准测试,进而选择适合特定应用场景下的最有算法。 综上所述,渐进式时间,空间复杂度分析与性能基准测试并不冲突,而是相辅相成的,但是一个低阶的时间复杂度程序有极大的可能性会优于一个高阶的时间复杂度程序,所以在实际编程中,时刻关心理论时间,空间度模型是有助于产出效率高的程序的,同时,因为渐进式时间,空间复杂度分析只是提供一个粗略的分析模型,因此也不会浪费太多时间,重点在于在编程时,要具有这种复杂度分析的思维。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

Excel简化办公系列之一 | VLOOKUP代替IF函数

本文为CDA作者青菜原创文章,转载请注明来源 编者按:CDA作者青菜将在近期发布「Excel简化办公」系列文章,本文是第一篇;更多精彩请持续关注~ 在日常工作...

31490
来自专栏趣学算法

数据结构 第10讲 好玩贪吃蛇——数字矩阵

12130
来自专栏smy

海量数据相似度计算之simhash短文本查找

在前一篇文章 《海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理,大家应该感觉到了算法的魅力。但是随着业务的增长 simhash的数据...

38840
来自专栏怀英的自我修炼

Java漫谈5

吴军老师有在他的《硅谷来信》中分享过他对于人工智能的看法,吴老师就认为,人工智能不会发展成黑客帝国的那种恐怖境地,原因是当初科学家在创立计算机之前先把人类要解决...

37490
来自专栏极客猴

用 Python 学习数据结构, 有它就不用愁

数据结构,我们对它已经是耳熟能详。对于计算机相关专业的大学生来说,它是一门专业必修课。从事软件开发的人员则把它作为谋生必备技能。这充分体现数据结构的重要性。因此...

8320
来自专栏数据结构与算法

洛谷2017 5月月赛R1

我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

29050
来自专栏数据结构与算法

√n求单值欧拉函数

基本定理: ? 首先看一下核心代码: 核心代码 ? 原理解析: 当初我看不懂这段代码,主要有这么几个问题: 1.定理里面不是一开始写了一个n*xxx么?为什么代...

39070
来自专栏大数据文摘

手把手:四色猜想、七桥问题…程序员眼里的图论,了解下?(附大量代码和手绘)

69940
来自专栏量化投资与机器学习

【干货分享】Python数据结构与算法设计总结篇

1.Python数据结构篇 数据结构篇主要是阅读[Problem Solving with Python](http://interactivepython.o...

45550
来自专栏美团技术团队

函数式编程在Redux/React中的应用

本文简述了软件复杂度问题及应对策略:抽象和组合;展示了抽象和组合在函数式编程中的应用;并展示了Redux/React在解决前端状态管理的复杂度方面对上述理论的实...

37490

扫码关注云+社区

领取腾讯云代金券