《数据结构与算法之美》学习笔记之复杂度

栏目: 编程工具 · 发布时间: 5年前

内容简介:本系列是极客时间中复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构与算法的内容基本上就掌握了一半数据结构和算法解决是

本系列是极客时间中 前 Google 工程师王争《数据结构与算法之美》专栏 的学习笔记,想加强数据结构及算法能力的同学可以直接购买此专栏,跳转链接在此

复杂度分析是整个算法学习的精髓,只要掌握了它,数据结构与算法的内容基本上就掌握了一半

什么是复杂度分析

数据结构和算法解决是 如何让计算机更快时间、更省空间的解决问题 ,因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。

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

如何进行复杂度分析

大 O 表示法

来源

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

特点

以时间复杂度为例,由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势,所以常量阶、低阶以及系数实际上对这种增长趋势不产生决定性影响,故在做时间复杂度分析时忽略这些项。

复杂度分析法则

只关注循环执行次数最多的一段代码

在分析一个算法、一段代码的时间复杂度的时候,也只关注循环执行次数最多的那一段代码就可以了

加法法则:总复杂度等于量级最大的那段代码的复杂度

如果 T1(n)=O(f(n)), T2(n)=O(g(n));

那么 T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n))) = O(max(f(n), g(n)))

乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

可以把乘法法则看成是嵌套循环:

如果 T1(n) = O(f(n)), T2(n) = O(g(n))

那么 T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))

总结

  1. 单段代码看高频:比如循环
  2. 多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度
  3. 嵌套代码求乘机:比如递归、多重循环等
  4. 多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加

常用复杂度级别

《数据结构与算法之美》学习笔记之复杂度
  1. 多项式阶:随着数据规模的增长,算法的执行时间和空间占用,按照多项式的比例增长。包括, O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n^2)(平方阶)、O(n^3)(立方阶)

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

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

最好时间复杂度

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

最坏时间复杂度

代码在最坏情况下执行的时间复杂度

平均时间复杂度

用代码在所有情况下执行的次数加权平均值表示

均摊时间复杂度

在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。 基本上均摊结果就等于低级别复杂度

声明

本文更多是本人学习笔记之用,更多详细的讲解及代码,请查看极客时间专栏《数据结构与算法之美》


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

敏捷项目管理

敏捷项目管理

马克·莱顿 / 人民邮电出版社 / 2015-12-1 / CNY 69.00

当你进行软件开发时,你一定需要一种更快捷、更灵活的方式。《敏捷项目管理》将通过手把手的方式帮你充分发挥你手中的所有可利用工具和技术,以一种非常有效的方式管理好你的项目。通过《敏捷项目管理》,你可以学到:在数周内而不是数月内完成你的软件开发;使用敏捷技术降低项目风险,并提升核心收益;将敏捷理论付诸实践;避免项目管理普遍存在的误区。一起来看看 《敏捷项目管理》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具