时间复杂度和空间复杂度的计算方法

124 阅读 0 评论 82 点赞

我是靠谱客的博主怕黑电灯胆，最近开发中收集的这篇文章主要介绍时间复杂度和空间复杂度的计算方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

面试一问计算复杂度竟然给我问懵了QAQ，才突然发现一直没有注意过复杂度的计算。在这里写一写复杂度的计算。包括时间复杂度和空间复杂度。

时间复杂度

时间复杂度是衡量算法效率的基本方法，或者说是程序运行的时间长短。
《大话数据结构》一书中对时间复杂度的定义：
算法语句总的执行次数 T(n) 是关于问题规模 n 的函数，进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n) = O(f(n)) 它表示随问题规模 n 的增大，算法执行时间的增长率和f(n) 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。”
以一个从1加到100的例子来说，如果用叠加的方法算起来，写出一下代码。

int sum=0,n=100;//执行了1次
for(int i=1;i<n;i++)//执行了n+1次
{
    sum += i;执行了n次
}
cout<<"sum="<<sum<<endl;//执行了1次

这个算法所用的时间（也就是执行的总次数）可以表示为：
1 + ( n + 1 ) + n + 1 = 2n + 3
这个算法所用时间会随着n增大而增大，但是在for循环以外的时候只执行了一次，所以上述算法的所用时间可以简单记做2n或者简单记为n。这样我们得到了上述算法中的时间复杂度，记为O(n)。
但对于同一个问题，能使用的方法并不唯一，例如高斯对这个问题的解决方法:凑出50个101，加得5050。类似于等差数列求和。算法实现如下

int n=100,sum=0;//执行1次
sum=(n*(n+1))/2;//执行1次
cout<<"sum="<<sum<<endl;//执行1次

这样的话时间复杂度为O(3)，一般记做O(1)。
很显然这种算法的效率更高，也就是O(1)>O(n)。
这种用大写O来代表算法时间复杂度的方法专业名词叫“大O阶”，一般推导步骤如下：

1、用常数 1 取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是 1，则去除与这个项相乘的常数。

看下面这个例子：

int n = 100000;        //执行了 1 次
for (int i = 0; i < n; i++)//执行了 n + 1 次
{
    for (int j = 0; j < n; j++)//执行了 n*(n+1) 次
        cout<<"i="<<i<<" "<<"j="<<j<<endl;//执行了 n*n 次
}
for (int i = 0; i < n; i++)//执行了 n + 1 次
    cout<<"i="<<i<<endl;//执行了n次
cout<<"Done"//执行了 1 次

严格讲这个算法没有什么卵用，先不去管它能实现什么，来看下它的“大O阶”如何推倒：
先算出总次数：
执行总次数 = 1 + (n + 1) + n*(n + 1) + n*n + (n + 1) + 1 = 2n^2 + 3n + 3
第一步：用常数 1 取代运行时间中的所有加法常数。
执行总次数 = 2n^2 + 3n + 1
第二部：在修改后的运行次数函数中，只保留最高阶项。
执行总次数 = 2n^2
第三部：如果最高阶项存在且不是 1，则去除与这个项相乘的常数。
执行总次数 = n^2
因此最后所得的时间复杂度表示为O(n^2)
再举一个例子：

int i=1,n=10000;//执行1次
while(i<=n)
{
    i=i*2;//假设执行了x次
}

可以看出，2^x<=n，得到x<=log2n，即时间复杂度记为O(log2n)。
最后附上常见的复杂度以及他门效率上的排序：

O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < O(2^n) < O(n!) < O(n^n)

注意加粗的三个，非常不实用，若最后推导出时间复杂度是这三个中的一个，最好换一种算法。

空间复杂度

一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地”进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

概括来说，一个程序的空间复杂度可以分为两部分：固定不变的部分和可变的部分。
（1）固定不变的部分：部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。
（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。
一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))　　其中n为问题的规模，S(n)表示空间复杂度。