时间复杂度与空间复杂度整理

1. 算法复杂度初认

1. 你循环的次数写成 n 的表达式，就是时间复杂度
2. 你申请的变量数量写成 n 的表达式，就是空间复杂度
3. 例如计算 1 到 n 的和，输入为 n

• 如果你用循环来计算，那么循环次数是 n 次，于是时间复杂度为 O (n )。 不管 n 是多大，变量最多也就不超过 5 个，于是空间复杂度为 O (5 )，也就是 O (1 )，常数全变成 1 就对了
• 如果你用前 n 项和的公式来计算，只要一次计算即可： n(n+1 )/2 ，并没有循环，于是时间复杂度为 O (3 )[此处进行了三次计算：+，，/]，常数变为 1 就是 O (1 )，变量数量这里可能只需要两个，于是空间复杂度也为 O (1 )

2. 时间复杂度

1. 时间复杂度

1. 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。
2. 计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，它考察当输入值大小趋近无穷时的情况。
3. 算法复杂度分为时间复杂度和空间复杂度。其作用：时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。（算法的复杂性体现在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间（即寄存器）资源，因此复杂度分为时间和空间复杂度）。

2. 计算方法

1. 1.一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))，称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
2. 2. 在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))

3. demo

for(i=1; i<=n; ++i) { 
    for(j=1; j<=n; ++j) { 
        c[i][j] = 0;//该步骤属于基本操作执行次数：n的平方次 
        for(k=1; k<=n; ++k){ 
            c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数：n的三次方次
        }
    } 
}

1. 则有 T(n) = n 的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级
2. 则有 f(n) = n的三次方，然后根据 T(n)/f(n) 求极限可得到常数c
3. 则该算法的时间复杂度：T(n) = O(n^3)

4. 总结

1. 时间复杂度比较简单的计算方法是：看看有几重for循环，只有一重则时间复杂度为O(n)，二重则为O(n^2)，依此类推，如果有二分则为O(logn)，二分例如快速幂、二分查找，如果一个for循环套一个二分，那么时间复杂度则为O(nlogn)。

3. 空间复杂度

1. 一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。
2. 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面
3. 一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。
4. 算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)。若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

4. 时间与空间复杂度比较

1. 对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。
2. 另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法（特别是大型算法）时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。算法的时间复杂度和空间复杂度合称为算法的复杂度。
3. 有两个算法A1和A2求解同一问题，时间复杂度分别是T1(n)=100n2，T2(n)=5n3。（1）当输入量n＜20时，有T1(n)＞T2(n)，后者花费的时间较少。（2）随着问题规模n的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

5. 案例

1. 如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

x=91;
y=100;
while(y>0) {
    if(x>100) {
        x=x-10;
        y--;
    } else{
         x++;
    }
}

解答： T(n)=O(1)，
这个程序看起来有点吓人，总共循环运行了1100次，但是我们看到n没有?
没。这段程序的运行是和n无关的，
就算它再循环一万年，我们也不管他，只是一个常数阶的函数

2. 当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

 x=1; 
for(i=1;i<=n;i++){
    for(j=1;j<=i;j++){
        for(k=1;k<=j;k++){
            x++; 　
        }
    }
} 

该程序段中频度最大的语句是(x++)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(x++)的执行次数： 则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)

参考
http://blog.csdn.net/booirror/article/details/7707551/
http://www.cnblogs.com/xiaxianfei/p/5385081.html