时间复杂度和空间复杂度

//原本打算昨天就更完的然而昨天在网上躺了一天


时间复杂度和空间复杂度是判断算法优劣的尺度

算法和程序并不能画上等号

程序只是实现算法的手段

所以要注意两者的区别

通常我们认为一个程序运行时间越短

运行过程中所占的内存越小

算法的运行效率越高

可以称之为一个好的算法

 

时间复杂度

一个程序的运行时间会受到设备性能的影响

并不能真实反映一个算法的用时

所以实际过程中我们往往会通过数学计算

来比较不同算法间运行时间的大小

//我们后面用到的clock()函数计算时间的方法的值也只是参考

//并不是这个算法真实的准确的运行时间

//完全准确的运行时间是不可能拿到的

基本操作执行次数

假设有一辆汽车三分钟走一公里

那么十公里的路就要走三十分钟

假如这条路长n公里,那就需要走3n分钟

就可以记作T(n)=3n

再举一个例子

我们都听过竹子日取其半取之不竭的谚语

假如有一根竹子长16m,每五分钟取其一半

剩下1m的时候花费的时间就是5*log2(16)

扩大到n就是5*log2(n)

假设汽车在一公里的路上行驶同时车上有人在砍竹子

那么汽车的行驶时间和砍竹子是没有关系的

也就是始终为1

假如汽车越开越慢,第一公里需要一分钟,第n公里需要n分钟

所以n公里根据高斯算法就可以得到总时间为n*(n+1)/2

把上面四个例子转换为算法问题就可以理解基本操作次数这个概念了

这四个例子分别对应了四种程序的执行方式

渐进时间复杂度

假如现在你知道了两个T(n)

一个是T(n)=100n

另一个是T(n)=5n^2

如果要比较两个T的大小就要看看他们的曲线

随着n的增长会变成什么样

  • 为了解决时间分析的难题,有了渐进时间复杂度的概念,
  • 其官方定义如下:
  • 若存在函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,
  • 则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称为O(f(n)),
  • O为算法的渐进时间复杂度,简称为时间复杂度。

说人话的话就是当n趋近于无穷大的时候

只保留最高次项并且去掉它的系数

例如第一个T的O(n)就是n

例如第一个T的O(n)就是n^2

如下列举了常用的几种时间复杂度,以及它们之间的大小关系:

O(1)常数阶 < O(log n)对数阶 < O(n)线性阶 < O(n2)平方阶 < O(n3)(立方阶) < O(2n) (指数阶)

注意,这里仅介绍了以最坏情况下的频度作为时间复杂度,而在某些实际场景中,还可以用最好情况下的频度和最坏情况下的频度的平均值来作为算法的时间复杂度。

所以我们平时在问一个算法的时间复杂度

是指它的渐进时间复杂度而不是基本操作次数

 

空间复杂度

数据存储是要消耗空间的

无论是代码本身所占的存储空间

还是输入输出所占的存储空间

对于算法所消耗的硬件上的性能其实影响不大

所以空间复杂度一般是指程序运行过程中调用的临时空间

因为这部分对于性能的影响比较大

空间复杂度的计算

  1. 假如算法内没有调用任何的临时空间,那么默认就都是1
  2. 当算法内存在一个一维数组,并且数组大小与n成正比,空间复杂度为O(n)
  3. 当算法内存在一个二维数组,并且数组大小与n成正比,空间复杂度为O(n^2)
  4. 当算法中出现了递归(例如栈),纯粹的递归空间复杂度也是线性的,所以记作O(n)

两者之间的取舍是需要精打细算的

有时候会空间换时间

有时候会时间换空间

不过在绝大多数情况下会为了算法的速度而去牺牲空间

毕竟时间就是生命嘛

 

参考文献
http://data.biancheng.net/view/272.html

 

发表评论

您的电子邮箱地址不会被公开。