数据结构和算法

数据结构和算法

数据结构是为算法服务的,算法要作用在特定的数据结构。

10个数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树;

10个算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

时间复杂度和空间复杂度分析

数据结构和算法本身就是为了解决“快”和“省”的问题。让代码运行更快,更省储存空间。那首先我们就要先了解自己写的代码复杂度,这里就需要用到时间复杂度和空间复杂度分析。

时间复杂度

表示代码执行时间随数据规模增长的变化趋势

空间复杂度

表示算法的存储空间与数据规模之间的增长关系

大O复杂度表示法:

分析技巧:

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

T(n)代码执行时间,O(f(n))表示代码执行次数

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

常用的复杂度级别

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

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

复杂度分析的四个概念

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

本文分享自微信公众号 - 分母为零(gmg1014)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-25

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏无道编程

正则表达式工具上线【附正则相关知识】

迷思雨工具站( https://tool.misiyu.cn/ ),工具还是太少了。

6200
来自专栏无道编程

Jetbrains-PhpStorm2019.2中文乱码问题

Jetbrains家的产品基本上一年会发布两次重大更新,并分别命名为20xx.1 和 20xx.2,其余小更新就是在其基础上在“.x”,也即:2019.1 算是...

9100
来自专栏无道编程

Linux[CentOS]下编译安装Mysql5.7 步骤

以后可以使用那些一键的脚本,但是要明白一些底层的操作,以后才能更得心应手。一味的用那些面板、一键安装脚本,并不是一个很好的选择。

12600
来自专栏无道编程

关于ES6中的模块化的规范:export与import

其实对我个人来说,开始的时候对于export 与 import 用法挺模糊的。到现在为止也终于清楚一点了。

7900
来自专栏中科院渣渣博肆僧一枚

The Effects of Super-Resolution on Object Detection Performance in Satellite Imagery

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

10200
来自专栏无道编程

Laravel5.8 共享视图变量

通常我们使用Laravel开发项目,一般情况下都会把公共区域分离,比如我的博客网站的侧边栏:

4700
来自专栏无道编程

Laravel开发微信公众号【订阅号】后台的一些事情

对电脑这方面感兴趣的童鞋可能很清楚有一些“套路”,那就是回复某个关键词,获取某些素材、软件的下载地址。

4400
来自专栏可能是东半球最正规的API社区

继续搞【附近】系列---MySQL搞LBS(二)

考虑到在座的各位...都是泥腿子,唯一会做的就是用PHP CRUD,而且即便是只会搞CRUD,也还是离不开MySQL。

9700
来自专栏无道编程

Windows下的Maven安装与配置【附Idea设置默认】

Maven是一个项目管理和综合工具。Maven提供了开发人员构建一个完整的生命周期框架。开发团队可以自动完成项目的基础工具建设,Maven使用标准的目录结构和默...

9600
来自专栏无道编程

【学习笔记】ES6新的语法

5900

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励