算法笔记(一)——简述时间、空间复杂度分析
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记(一)——简述时间、空间复杂度分析,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2018字,纯文字阅读大概需要3分钟。
内容图文
前段时间通过小詹随笔分享的链接在极客时间购买了王争老师的《数据结构与算法之美》的课程,小詹学长果真是一个很靠谱的学长,凡是通过他的链接购买的课程,之后建有微信群,相互监督学习并分享学习笔记打卡。因此,在此,为表示对小詹学长的感谢,也简单介绍一下“小詹学Python”公众号,小詹学长是一名双一流高校在读研究生,专研c++,python,主要研究图像处理、计算机视觉和机器学习相关知识,定期带你打卡刷leetcode,锻炼编程能力。有兴趣的可以关注他哦~~
下面就开始本次的正题啦~~
首先,我们需要明白数据结构与算法的大致概念。通俗讲,数据结构就是数据的一种存储结构,而算法就是操作这些数据的方法。数据结构为算法服务,算法作用在数据结构之上。那么,论及数据结构与算法,就离不开对时间、空间的复杂度分析了。
其次,我们为什么要进行复杂度分析呢?简单讲,那肯定是用户体验和对数据本身处理的优化咯。毕竟,如果数据库里面如果有几百万条数据,挨个搜索查找,这样的等待时间是会让用户崩溃的。所以,复杂度分析当然需要重点分析。
最后,复杂度分析包含哪几个点呢?
空间、时间复杂度统一使用大O阶表示法,所有代码的执行时间T(n)均与数据规模成正比:T(n)=O(f(n))。
(一)时间复杂度:
时间复杂度即为运行一个程序的时间,大致可分为:多项式量级、非多项式(NP)量级。
1.多项式量级——随着数据规模的增长,算法的执行时间和空间占用统一呈多项式规律增长:
常数阶O(1)、对数阶O(logn)、线性阶O(n)、线性对数阶O(n*logn)、幂次阶(平方阶O(n.^2)、立方阶O(n.^3)、四次方O(n.^4)...)
2.非多项式量级——随着数据量n的增长,时间复杂度急剧增长,执行时间无限增加:
指数阶O(2.^n)、阶乘阶O(n!)
图形比较就为如下:
- 下面再说说时间复杂度的计算法则:
1.单段代码看高频:比如循环。
2.多段代码取最大:比如单循环+双循环,那么就取复杂度最大的双循环作为该程序的复杂度。
3.嵌套代码用乘法:一个函数中嵌套另一个函数,那么他们之间的复杂度=O(f(n1))*O(f(n2)),例如递归等。
4.多个规模用加法:比如两个参数利用了两个循环函数,那么他们程序的复杂度O(n)=O(n1)+O(n2)。
(二)空间复杂度:
空间复杂度即占用某个存储空间的大小,例如:
void print(int n) { int i = 0; int[] a = new int[n]; for(i;i<n;++i){ a[i] = i*i; } }
上面的空间复杂度就为O(n)了。
总体来说,时间复杂度分析较为繁琐,需要着重掌握一下,空间复杂度就显得较为简单啦。
内容总结
以上是互联网集市为您收集整理的算法笔记(一)——简述时间、空间复杂度分析全部内容,希望文章能够帮你解决算法笔记(一)——简述时间、空间复杂度分析所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。