数据结构与算法(一):复杂度分析

什么是数据结构与算法

数据结构是指数据在内存中存储的结构,算法是操作数据的方法。

它们之间相辅相成,数据结构为算法提供服务,而算法依赖于特定的数据结构。

复杂度分析

评估一段代码的指标有两点:

  • 执行效率如何
  • 占用内存空间情况如何

评估这两点的行为称为复杂度分析,而我们不能把代码写完了然后再跑到机器上运行通过观察结果来评估代码质量,因为这样做会受到环境因素等影响很不科学,效率低下。

我们通常需要仅以肉眼就能粗略地估算出算法的执行效率以及内存空间的使用情况,因此诞生了大 O 复杂度表示法,它表示代码执行时间随着数据规模增长的变化趋势。

而复杂度分析包括两种分析:空间复杂度分析和时间复杂度分析。

如何进行复杂度分析

  1. 只关注循环执行次数最多的一段代码。
  2. 加法法则:总复杂度等于量级最大的那段代码复杂度。
  3. 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

时间复杂度分析

时间复杂度又叫做渐近时间复杂度,表示算法的执行时间与数据规模之间的增长关系。

时间复杂度又分为:最好情况时间复杂度、最坏情况时间复杂度、平均时间复杂度、均摊时间复杂度。

最好情况时间复杂度

在最理想的情况下,执行一段代码的时间复杂度。

最坏情况时间复杂度

最坏的情况下,执行一段代码的时间复杂度

平均时间复杂度

平均时间复杂度涉及到概率计算,也叫加权平均时间复杂度。

进行平均时间复杂度分析需要我们找出所有的情况及其发生的概率,然后计算平均值

均摊时间复杂度

均摊时间复杂度是种特殊的平均时间复杂度。

如果:在操作数据结构时,大多数情况下时间复杂度比较低,个别情况下时间复杂度比较高,而且这些操作之间存在操作连贯的时序关系,我们就尝试是否能将时间复杂度较高的那次操作,均摊到每一个时间复杂度较底的操作上,之后评估出的时间复杂度称之为:均摊时间复杂度。

能够应用均摊时间复杂度分析的场合,一般均摊时间复杂度就等于最好情况时间复杂度。

空间复杂度分析

空间复杂度又称渐近空间复杂度,表示算法的存储空间与数据规模之间的增长关系。

复杂度量级

在对时间或空间复杂度分析后,得出结果,用大 O 表示法表示复杂度量级。

复杂度量级又可以分为两类:多项式量级非多项式量级,非多项式量级的时间复杂度会随着 N 的越来越大,求解问题的时间会无限增长,一般不常见。。

它们之间的等级关系从高到底排序如图:

复杂度量级

O(1) 是复杂度最低的算法,一般情况下,只要算法中不出现循环语句、递归语句,即使有成千上万行代码复杂也是 O(1)。


 上一篇
数据结构与算法(三)链表 数据结构与算法(三)链表
什么是链表链表是通过指针将一些零散的内存块串起来使用的一种数据结构,支持数据的查找、插入、删除操作。 因为链表在内存中是不连续的,所以无法像数组那样可以根据首地址和下标通过寻址公式直接计算出第 K 个元素,而是需要遍历所有的节点通过计数获取
2019-03-28
下一篇 
Mac 上使用 Charles 抓包进行网络分析 Mac 上使用 Charles 抓包进行网络分析
近期想给 Chrome 编写一个关于 Github 插件,有一个地方通过 Github 现有的 API 不知道如何快速方便地拿到我需要的数据,但 OhMyStar 2 上可能会有相关的操作,我就想着去借鉴一下它是如何实现的,于是需要用到抓包
2019-02-24
  目录