数据结构与算法--时间空间复杂度（基础篇）

数据结构与算法--时间空间复杂度（基础篇）

作者: zhujunhua | 来源:发表于2019-07-15 14:01 被阅读0次

时间复杂度分析

大O复杂度表示法

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示算法的执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
表示： $T(n)=O(f(n))$
例如： $T(n)=O({n}^2)$ ，其中 $f(n)=n^2$

大O复杂度表示法，就是代码执行的次数，三个比较实用的方法：

只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
多段代码组成的代码的分析
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
循环内的方法调用

常见的复杂度量级

1. 多项式时间复杂度

常量阶 $O(1)$
对数阶 $O(logn)$
线性阶 $O(n)$
线性对数阶 $O(nlogn)$ 比如：归并排序、快速排序
平方阶 $O(n^2)$ ，立方阶 $O(n^3)$ ，...，k次方阶 $O(n^k)$

2. 指数型时间复杂度

指数阶 $O(2^n)$
阶乘阶 $O(n!)$

对数知识

$log_{3}n=log_{3}2*log_{2}n$ ，所以通常省略底数，计作 $O(logn)$

图片发自：极客时间《数据结构与算法》王争

空间复杂度分析

全称渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
就是看程序申请的内存空间与数据规模n的关系。
常见的空间复杂度就是 $O(1)$ 、 $O(n)$ 、 $O(n^2)$ 。

内容总结自：
极客时间：《数据结构与算法》王争

相关文章

网友评论

本文标题：数据结构与算法--时间空间复杂度（基础篇）

本文链接：https://www.haomeiwen.com/subject/jplnkctx.html

延伸阅读

深度阅读

您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

栏目导航

热点阅读

关于我们|服务条款|联系我们|数据结构与算法--时间空间复杂度（基础篇）|投稿指南|网站地图|RSS订阅|排版工具|手机版

提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网版权所有

备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！