数据结构~时间复杂度和空间复杂度-阿里云开发者社区

开发者社区> mcy247> 正文

数据结构~时间复杂度和空间复杂度

简介:
+关注继续查看

同一问题可用不同算法解决,而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。

算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是度量算法执行的时间长短;而空间复杂度是度量算法所需存储空间的大小。

时间复杂度

1.时间频度

一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

2.计算方法

1. 一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n)) 分析:随着模块n的增大,算法执行的时间的增长率和f(n)的增长率成正比,所以f(n)越小,算法的时间复杂度越低,算法的效率越高。 2. 在计算时间复杂度的时候,先找出算法的基本操作,然后根据相应的各语句确定它的执行次数,再找出T(n)的同数量级(它的同数量级有以下:1,Log2n ,n ,nLog2n ,n的平方,n的三次方,2的n次方,n!),找出后,f(n)=该数量级,若T(n)/f(n)求极限可得到一常数c,则时间复杂度 T(n)=O(f(n)) 例:算法: for(i=1;i<=n;++i) { for(j=1;j<=n;++j) { c[ i ][ j ]=0; //该步骤属于基本操作 执行次数:n的平方 次 for(k=1;k<=n;++k) c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数:n的三次方 次 } } 则有 T(n)= n的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级 则有f(n)= n的三次方,然后根据T(n)/f(n)求极限可得到常数c 则该算法的 时间复杂度:T(n)=O(n的三次方)

3.分类

按数量级递增排列,常见的时间复杂度有: 常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。

本文转自博客园张占岭(仓储大叔)的博客,原文链接:数据结构~时间复杂度和空间复杂度,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【算法与数据结构】关于代码运行时间复杂度的计算方法
(转载请注明出处:http://blog.csdn.net/buptgshengod) 1.背景知识        大O标记就不用我说了吧。O(n)这种时间复杂度的意义自己google吧。这里简单讲下从代码推算。 2.具体案例  (1)案例一   int a=0; //第一行 for(int i=0;i&lt;=N;i++)//第二行
642 0
时间序列数据的处理
随着云计算和IoT的发展,时间序列数据的数据量急剧膨胀,高效的分析时间序列数据,使之产生业务价值成为一个热门话题。阿里巴巴数据库事业部的HiTSDB团队为您分享时间序列数据的计算分析的一般方法以及优化手段。
4437 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9199 0
重磅|阿里云HBase Ganos全新升级,推空间、时空、遥感一体化基础云服务
Ganos是阿里云时空PaaS服务的自研核心引擎。Ganos已作为云数据库时空引擎与数据库平台融合,建立了以自研云原生数据库POALRDB为基础,联合NoSQL大数据平台(Ali-HBASE和X-Pack Spark)的完整时空地理信息云化管理解决方案。
2097 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10762 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
12901 0
利用Clion对几种排序算法进行时间复杂度与空间复杂度的分析
算法 利用算法解决问题的步骤: 1、将问题模型化 2、找到一个合适的算法 3、这个算法足够快吗?对空间友好吗 4、如果不是,找出为什么 5、找到一个方法解决这个问题 6、一直迭代直到这个问题被解决 ...
1011 0
+关注
mcy247
做自己的太阳 无需凭借谁的光
1070
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载