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

1、时间复杂度和空间复杂度的意义

算法的时间复杂度和空间复杂度就是一种对算法优劣进行衡量的标准，前者反映了算法的执行时间，后者反映了算法所需要的内存空间。

2、时间频度

其实算法之间的比较不需要每次都将每个算法上机测试，以求出其执行时间再做比较。只需要知道两相比较之下，哪一个算法花费的时间多，哪一个花费的时间少就可以了。而一个算法的执行时间的多少是依据其语句执行次数的，执行的次数越多，相应算法需要的时间就越多。而一个算法的执行次数就叫做语句频度或者时间频度，记为T(n)

3、时间复杂度

提到的T(n)中的n，表示的是问题的规模，T(n)随着问题规模n的增长而不断变化，但是这只是提供了一个非常直观的数据结果。当我们想要知道T(n)在变化过程中呈现一个什么样的规律时，就提出了时间复杂度的概念。一般情况下，算法基本操作的执行次数是问题规模n的某个函数，用T(n)表示。当有某一个辅助函数f(n)，当n趋近于无穷大的时候，T(n)/f(n)的极限值是一个不为0的常数，那么f(n)就是T(n)的同数量级函数，写作T(n) = O(f(n)),那么O(f(n))就是时间复杂度

4、时间复杂度的计算方法

上面提到的T(n)=O(f(n)),其实是T(n)<=C*f(n)，也就是当算法规模n接近于无穷大的时候，T(n)的上顶界限就是C*f(n)。另一个就是说，T(n)最大也就是跟f(n)差不多大，那么就可以用f(n)来代替T(n)，去描述算法的复杂度。虽然没有对f(n)做什么界定，但是尽可能的取比较简单的数，比方说O(2n2+n +1) = O (3n2+n+3) = O (7n2 + n) = O ( n2 )。也就是直接用O ( n2 )表示就可以了，记住，大O符号里面有一个系数C，所以一般不给f(n)加系数。

5、常见时间复杂度的大小排序

如果算法的执行次数是一个常数，那么它的时间复杂度就是O(1),一般常见的时间复杂度的大小排序规则如下：

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

一般一类问题选择一种基本操作就可以了，如果比较复杂，则需要设置不同的维度，并且为不同的维度设置权值，最后计算出最终的复杂度。

6、那么如何找到某个算法的时间复杂度呢？

（1）找出算法的基本执行语句：

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体

（2）计算基本语句的执行次数的幂级

（3）用大O记号表示算法的时间性能

如果算法中包含嵌套的循环，则基本语句通常是最内层的循环体，如果算法包含并列的循环，则将并列循环的时间复杂度想加。例如：

for(I=1;i<=n;i++)

    x++

for(I=1;i<=n;i++)

    for(j=1;j<=n;j++)

        x++

第一个循环的复杂度是O(n),第二个是O(n2),那么整个算法的时间复杂度就是O(n+n2)=O(n2).

7、什么是有效算法

O(1)表示基本语句的执行次数是一个常数，一般来说如果算法里面没有循环语句，那么它的算法复杂度就是O(1),其中O(log2n),O(n),O(nlog2n),O(n2),O(n3)称为多项式时间，而O(2n)和O(n!)称为指数时间，前者被认为是有效算法

8、下面分别对几个常见的时间复杂度进行示例说明：

（1）、O(1)

temp=I;i=j;j=temp

上面几条语句都是被执行了一次，与问题规模n无关，所以算法的时间复杂度为常数阶，记作T(n)=O(1)

注意⚠️：如果程序执行时间不随问题规模n的增加而增长，不论程序中有多少条语句，他的算法复杂度都是O(1)

（2）、O(n2)

2.1、交换I和j的内容

sum = 0(一次)

for(I=1;i<=n;i++)（n+1次）（n+1次）

for(j=1;j<=n;j++) (n2)

sum++; (n2次)

最后O(2n2+n+1)=n2

2.2 

for (I=1;i

 {  

    y=y+1;(1)

    for(j=0;j<=(2*n);j++)

        x++;    (2)

}    

语句（1）的频度是n-1,语句2的频度是(n-1)*(2n+1)=2n2-n-1, f(n)=2n2-n-1+(n-1)=2n2-2,所以时间复杂度是T(n)=O(n2)

（3）、O(n)

a=0;

b=1;(1)

for(I=1;i<=n;i++)(2)

{

    s=a+b;(3)

    b=a;(4)

    a=s;(5)

}

(1)的频度是1，（2）是n，（3）是n-1，（4）是n-1（5）是n-1，T(n)=O(n)

（4）、O(log2n)

while循环是O(log2n)

(5)、O(n3) 

For循环3层嵌套

9、算法的空间复杂度

空间复杂度包括输入输出数据所占用的存储空间，算法本身占用的存储空间，以及算法在运行过程中需要的存储空间

参考链接：http://blog.csdn.net/zolalad/article/details/11848739