数据结构与算法 - 时间复杂度与空间复杂度

前言

通常,对于一个给定的算法,我们首先要验证算法的正确性,
其次主要从算法的执行时间和所需要占用的存储空间两个方面衡量一个算法的优劣。

时间复杂度:时间复杂度的计算并不是计算程序具体运行的时间,而是算法执行语句的最大次数。 空间复杂度:类似于时间复杂度的讨论,一个算法的空间复杂度为该算法所耗费的存储空间。往往跟为最大创建次数。

几类常见时间复杂度的示例解析

求解算法的时间复杂度的具体步骤是:

【1】找出算法中的基本语句; 算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。 【2】计算基本语句的执行次数的数量级; 只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析。 【3】 用大Ο记号表示算法的时间性能。

1、常数阶
int sum = 0, n = 100;       /*执行一次*/
sum = (1 + n) * n / 2;      /*执行一次*/
printf("%d",sum);           /*执行一次*/

执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶。
对于分支结构而言,无论是真,还是假,执行的次数都是恒定的,
不会随着n 的变大而发生变化,所以单纯的分支结构(不包含在循环结构中),其时间复杂度也是0(1)。
2、线性阶
int i;      
for(i = 0; i < n; i++){
    /*时间复杂度为O(1)的程序步骤序列*/
}

线性阶的循环结构会复杂很多。要确定某个算法的阶次,我们常常需要确定某个特定语句或某个语句集运行的次数。
因此,我们要分析算法的复杂度,关键就是要分析循环结构的运行情况。
上面这段代码,它的循环的时间复杂度为O(n), 因为循环体中的代码须要执行n次。
3、对数阶
int count = 1;      
while (count < n){
   count = count * 2;
  /*时间复杂度为O(1)的程序步骤序列*/
}
 由于每次count乘以2之后,就距离n更近了一分。 也就是说,有多少个2相乘后大于n,
 则会退出循环。 由2^x=n 得到x=logn。 所以这个循环的时间复杂度为O(logn)。
4、平方阶
下面例子是一个循环嵌套,它的内循环刚才我们已经分析过,时间复杂度为O(n)。

int i, j;      
for(i = 0; i < n; i++){
    for(j = 0; j < n; j++){
        /*时间复杂度为O(1)的程序步骤序列*/
    }
}
而对于外层的循环,不过是内部这个时间复杂度为O(n)的语句,再循环n次。 所以这段代码的时间复杂度为O(n^2)。
如果外循环的循环次数改为了m,时间复杂度就变为O(mXn)。 
所以我们可以总结得出,循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。
5、立方阶
下面例子是一个三重循环嵌套。

int i, j;      
for(i = 1; i < n; i++)
    for(j = 1; j < n; j++)
        for(j = 1; j < n; j++){
            /*时间复杂度为O(1)的程序步骤序列*/
 
        }

这里循环了(1^2+2^2+3^2+……+n^2) = n(n+1)(2n+1)/6次,按照上述大O阶推导方法,时间复杂度为O(n^3)。
6、指数阶
long aFunc(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}
显然运行次数,T(0) = T(1) = 1,同时 T(n) = T(n - 1) + T(n - 2) + 1,这里的 1 是其中的加法算一次执行。
显然 T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列,通过归纳证明法可以证明,当 n >= 1 时 T(n) < (5/3)^n,
同时当 n > 4 时 T(n) >= (3/2)^n。
所以该方法的时间复杂度可以表示为 O((5/3)^n),简化后为 O(2^n)。

常见的时问复杂度如表所示:

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

  常见的算法时间复杂度由小到大依次为:Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

从图中可见,当n取不同值的时候,不同算法的时间复杂度优劣表现不同。我们应该根据实际情况和n的取值来选择最优的算法!

空间复杂度

我们在写代码时,完全用空间来换取时间.

比如说,要判断某某年是不是闰年,
你可能会花一点心思写了一个算法,而且由于是一个算法,也就意味着,每次给一个年份,
都是要通过计算得到是否是闰年的结果。 还有另一个办法就是,
事先建立一个有2050个元素的数组(年数略比现实多一点),然后把所有的年份按下标的数字对应,
如果是闰年,此数组项的值就是1,如果不是值为0。这样,所谓的判断某一年是否是闰年,
就变成了查找这个数组的某一项的值是多少的问题。此时,我们的运算是最小化了,
但是硬盘上或者内存中需要存储这2050个0和1。
这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好,其实要看你用在什么地方。

一个算法在计算机存储器上所占用的存储空间,包括 【1】存储算法本身所占用的存储空间, 【2】算法的输入输出数据所占用的存储空间。 【3】算法在运行过程中临时占用的存储空间这三个方面。

 算法的输入输出数据所占用的存储空间是由要解决的问题决定的,
 是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。

 存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。

  算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,
  而且不随问题规模的大小而改变,我们称这种算法是“就地\"进行的,是节省存储的算法;
  有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,
  当n较大时,将占用较多的存储单元。

如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1); 当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n); 当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n)。

二分查找时,每次都在原有查找内容进行二分,所以时间复杂度为O(log2 n) 
因为变量值创建一次,所以空间复杂度为O(1)

时间复杂度为O(log2 n) 
每进行一次递归都会创建变量,所以空间复杂度为O(log2 n)

时间复杂度O(n) 
空间复杂度为O(1)

时间复杂度为O(2^n) 
空间复杂度为O(n)

总结

下面贴出一个常用排序算法中的时间复杂度和空间复杂度的分析图:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老九学堂

【学习】Java微课堂之switch语句

知识点: ? ? 扩展知识介绍 Java随机数类Random介绍 Java实用工具类库中的类java.util.Random提供了产生各种类型随机数的方法。它可...

3585
来自专栏钟绍威的专栏

矩阵的基本知识构造重复矩阵的方法——repmat(xxx,xxx,xxx)构造器的构造方法单位数组的构造方法指定公差的等差数列指定项数的等差数列指定项数的lg等差数列sub2ind()从矩阵索引==》

要开始学Matlab了,不然就完不成任务了 java中有一句话叫作:万物皆对象 在matlab我想到一句话:万物皆矩阵 矩阵就是Java中的数组 ...

27210
来自专栏ATYUN订阅号

NumPy中einsum的基本介绍

einsum函数是NumPy的中最有用的函数之一。由于其强大的表现力和智能循环,它在速度和内存效率方面通常可以超越我们常见的array函数。但缺点是,可能需要一...

5103
来自专栏数据结构与算法

P3382 【模板】三分法

题目描述 如题,给出一个N次函数,保证在范围[l,r]内存在一点x,使得[l,x]上单调增,[x,r]上单调减。试求出x的值。 输入输出格式 输入格式: 第一行...

3439
来自专栏机器学习和数学

[ Tensorflow]Tensorflow Reduction operations

reduce系列在平时工程中是经常使用的,其中reduce_sum是使用最频繁的一个。主要用在计算loss的时候,当我们定义好loss之后,我们一般要求loss...

3614
来自专栏和蔼的张星的图像处理专栏

138. 子数组之和 map存储加规律

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置。 假定一定存在这样的字数组。 样例 给出 [-3, 1, 2,...

1151
来自专栏机器学习从入门到成神

2013百度校招笔试真题以及解析(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

951
来自专栏小L的魔法馆

新疆大学ACM-ICPC程序设计竞赛五月月赛(同步赛)--B-杨老师的游戏

4219
来自专栏Petrichor的专栏

python: random模块

  在numpy 和 tensorflow 中有 相同功能 的实现, 见 《tensorflow: Constants, Sequences, and Ra...

1691
来自专栏技术总结

算法(2)

2319

扫码关注云+社区

领取腾讯云代金券