博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
时间复杂度与空间复杂度
阅读量:4323 次
发布时间:2019-06-06

本文共 1193 字,大约阅读时间需要 3 分钟。

如果一个算法的执行次数是 T(n),那么只保留最高次项,同时忽略最高项的系数后得到函数 f(n),此时算法的时间复杂度就是 O(f(n))

void aFunc(int n) {    for (int i = 0; i < n; i++) {        for (int j = i; j < n; j++) {            printf("Hello World\n");        }    }}

当 i = 0 时,内循环执行 n 次运算,当 i = 1 时,内循环执行 n - 1 次运算……当 i = n - 1 时,内循环执行 1 次运算。

所以,执行次数 T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2。
此时时间复杂度为 O(n^2)。

算法的时间复杂度通常有 O(1)(常量阶)、O(n½) 、 O(n)(线性阶)、 O(logn)(对数阶)、 O(nlogn)、 O(n^2)(平方阶)、 O(n^3)、 O(2^n)(指数阶)、O(n!)等形式。

  当n大于一定的值后,各种不同的数量级对应的值存在着如下关系:

  O(logn)<O(n½)<O(n)< O(nlogn)< O(n^2)<O(n^3) <O(2^n)<O(n!)

通常除非特别指定,我们提到的运行时间都是最坏情况的运行时间。

算法的时间复杂度和空间复杂度是可以相互转化的。

谷歌浏览器相比于其他的浏览器,运行速度要快。是因为它占用了更多的内存空间,以空间换取了时间。

算法中,例如判断某个年份是否为闰年时,如果想以时间换取空间,算法思路就是:当给定一个年份时,判断该年份是否能被4或者400整除,如果可以,就是闰年。

如果想以空间换时间的话,判断闰年的思路就是:把所有的年份先判断出来,存储在数组中(年份和数组下标对应),如果是闰年,数组值是1,否则是0;当需要判断某年是否为闰年时,直接看对应的数组值是1还是0,不用计算就可以马上知道。

对于一个算法,其 时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。另外,算法的所有性能之间都存在着或多或少的相互影响。因此,当设计一个算法(特别是大型算法)时,要综合考虑算法的各项性能,算法的使用频率,算法处理的数据量的大小,算法描述语言的特性,算法运行的机器系统环境等各方面因素,才能够设计出比较好的算法。

算法的时间复杂度和空间复杂度合称为算法的复杂度。

转载于:https://www.cnblogs.com/baiyang2292/p/11283069.html

你可能感兴趣的文章
SCALA STEP BY STEP
查看>>
cocos2d-x学习笔记
查看>>
MySql中的变量定义
查看>>
Ruby数组的操作
查看>>
hdu1181暴搜
查看>>
解码字符串 Decode String
查看>>
json学习笔记
查看>>
工具:linux 性能监控工具-nmon
查看>>
fatal error C1853
查看>>
Ural 1001 - Reverse Root
查看>>
玩转webpack之webpack的entry output
查看>>
java 操作mongodb查询条件的常用设置
查看>>
黑马程序员_java基础笔记(02)...java语言基础组成
查看>>
关于缓存击穿
查看>>
对innodb 拷贝文件实现数据库的方式(转)
查看>>
python知识点 2014-07-09
查看>>
FloatingActionButton的一点学习感悟
查看>>
ABAP CDS ON HANA-(10)項目結合して一つ項目として表示
查看>>
网站地址信息
查看>>
产品经理 - 登录 注册
查看>>