如何理解时间复杂度和空间复杂度
我们经常可以看到这样的描述:软件=数据结构+算法,可见算法基础对于一个程序员的重要性。算法中,有两个基本概念:时间复杂度和空间复杂度。
- 时间复杂度:描述算法执行消耗的时间,时间越短,时间复杂度越低,算法越优秀;
- 空间复杂度:描述算法执行所占用的内存空间,占用内存越少,空间复杂度越低,算法越优秀;
因此,时间复杂度和空间复杂度是评价一个算法性能的主要指标。那么如何计算一个算法的时间复杂度和空间复杂度呢?
简单理解,计算时间复杂度就是评估一个算法完成后执行了多少行代码,也就是算法所消耗的时间,但是该如何用数学的方式其表示出来呢?
假设现在有个一个算法需要执行n次运算,我们用T(n)表示,n即表示算法的规模(比如n=10时,循环输出10次Hello World;n=100时,循环输出100次Hello World)。如果假设存在一个函数f(n),表示随着n的变化,算法需要执行的次数,当T(n)=O(f(n)),那么O(f(n))即为算法的时间复杂度。
比如,一个普通的循环:
public int calc(int n) { int total = 0; for (int i = 0; i < n; i++) { total += i; } return total; }
当n越大,循环的次数越多,那么耗费的时间也就越大,也就是f(n)随着n线性增长。那么该算法的执行时间T(n)=O(n),即时间复杂度为O(n)。
再比如,一个双层循环:
public int calc(int n) { int total = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { total += j; } } return total; }
外层循环每循环一次,内层循环就循环了n次,那么代码总循环次数就是n*n。那么该算法的执行时间T(n)=O(n^2) ,即时间复杂度为O(n^2)。
一般来说,时间复杂度是用来评估随着n的增大,算法执行需要消耗时间的增速,而不是精确计算消耗的时间,事实上也无法精确计算。既然是评估,那么f(n)函数我们只需要保留对消耗时间影响最大的因子即可。
例如,有一个f(n)=2*n^3函数,系数2对f(n)函数的增速影响就不大,所以该算法的时间复杂度T(n)=O(n^3),即忽略常量系数对增速的影响。
再比如,在一个没有循环的代码块里,只有三行输出代码:
public void print() { System.out.println("Hello 河先森"); System.out.println("Hello 河先森"); System.out.println("Hello 河先森"); }
即T(n)=3,是一个常数,而常数对增速的影响是可以忽略的,那么该代码块的时间复杂度就是O(1)。
再来看一个例子,计算下面代码块的时间复杂度:
public void print(int n) { for (int i = 0; i < n; i++) { for (int j = i; j < n; j++) { System.out.println("Hello 河先森"); } } }
当i=0时,内层循环了n次,当i=1时,内层循环了n-1次,以此内推,当i=n-1时,内层循环了1次。那么总的循环次数T(n)=n+(n-1)+(n-1)+...+1=n(n+1)/2=n^n/2+n/2,忽略常数项和对增速影响不大的因子,只保留影响最大的因子,那么该算法的时间复杂度即为O(n^2)。
常见的时间复杂度量级:
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
以上算法时间复杂度中,随着n的增大,f(n)增速越快,说明算法的效率越低。即算法耗费的时间O(1) < O(logN) < O(n) < O(nlogN) < O(n²) < O(n³) < O(n^k) < O(2^n)。
如果想在一个数组中找到一个数,最简单的方法就是循环遍历:
public boolean search(int m) { int[] arr = new int[]{3, 5, 7, 1, 2, 6, 4, 9}; for (int i = 0; i < arr.length; i++) { if (m == arr[i]) { return true; } } return false; }
如果要查找的是数是数组的第一个数(本例子中的3),那么只需要一次循环就能找到,时间复杂度为O(1)。但是如果要查找的数在数组最后位置(本例中的9),那么必须要经过arr.length次循环,时间复杂度为O(n),n为数组的长度。那么这段代码代码块的时间复杂度到底是多少呢?
一般在没有特殊说明的情况下,时间复杂度都是指最坏的时间复杂度,因为没有比这更坏的情况了。所以这段代码块的时间复杂度为O(n)。
时间复杂度描述的是算法消耗时间趋势,同理,空间复杂度则是描述算法在运行时临时内存消耗的趋势,一般用 S(n) 来定义,记作S(n)=O(fn)。
至于评价算法的具体好坏,就要具体情况具体分析了。有时我们会拿时间换空间,有时会去拿空间换时间,有时则需要同时考虑时间和空间复杂度。
总之,具体问题具体分析,但是我们一定要理解时间复杂度和空间复杂度的分析过程。
原文链接:如何理解时间复杂度和空间复杂度

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
回顾 Android 11 中的存储机制更新
Android 10 引入了对 外部存储权限的更改,旨在更好地保护用户数据以及降低应用的存储空间。在 Android 11 开发者预览版 的时候也加入了很多改进,以帮助开发者更好地适应这些权限修改。 在 Google Play 上发布的大部分应用都会 请求 (READ_EXTERNAL_STORAGE) 存储权限,来做一些诸如在 SD 卡中存储文件或者读取多媒体文件等常规操作。这些应用可能会在磁盘中存储大量文件,即使应用被卸载了还会依然存在。另外,这些应用还可能会读取其他应用的一些敏感文件数据。 在 Android 10 中,我们调整了存储权限的工作方式,仅为应用提供其所需的访问权限。这也是在鼓励应用在指定目录下进行文件存储以限制文件混乱。当应用被卸载后,这些相关的目录也会被删除。 Android 10 所带来的关于存储上的变更遵循了以下三个基本原则 更好的从属性: 系统知道哪些文件属于哪些应用,这可以让用户更方便地管理他们的文件。当应用被卸载后,除非用户需要,否则应用之前所创建的文件也不应该保留在设备上; 保护应用数据: 当一个应用将 它所属的文件 写入外部存储时,这些文件是不应该被...
- 下一篇
Mysql高级-sql分析及优化(二)
三、优化SQL步骤 1、查看SQL执行频率 MySQL 客户端连接成功后,通过 show [session|global] status 命令可以提供服务器状态信息。show [session|global] status 可以根据需要加上参数“session”或者“global”来显示 session 级(当前连接)的计结果和global 级(自数据库上次启动至今)的统计结果。如果不写,默认使用参数是“session”。 下面的命令显示了当前 session 中所有统计参数的值: show status like 'Com_______'; /** Com_xxx 表示每个 xxx 语句执行的次数,我们通常比较关心的是以下几个统计参数。 Com_select 执行 select 操作的次数,一次查询只累加 1。 Com_insert 执行 INSERT 操作的次数,对于批量插入的 INSERT 操作,只累加一次。 Com_update 执行 UPDATE 操作的次数。 Com_delete 执行 DELETE 操作的次数。 Com_*** : 这些参数对于所有存储引...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- SpringBoot2初体验,简单认识spring boot2并且搭建基础工程
- SpringBoot2全家桶,快速入门学习开发网站教程
- CentOS8编译安装MySQL8.0.19
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- CentOS关闭SELinux安全模块
- Eclipse初始化配置,告别卡顿、闪退、编译时间过长
- CentOS7设置SWAP分区,小内存服务器的救世主
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS8安装MyCat,轻松搞定数据库的读写分离、垂直分库、水平分库