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

算法的时间复杂度和空间复杂度合称为算法的复杂度。

一、时间复杂度

1.时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

2.时间复杂度

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

3.最坏时间复杂度和平均时间复杂度

最坏时间复杂度是指在最坏情况下的时间复杂度。
一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。 这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。
在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例,该算法的运行时间不可能大于O(n)。
平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。
指数阶O(2^n)， 显然，时间复杂度为指数阶O(2^n)的算法效率极低，当n值稍大时就无法应用。

4.时间复杂度的计算

步骤：

1）找出算法中的基本语句
     算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
2）计算基本语句执行次数的数量级
     只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
3）用大O记号表示算法的时间性能
     将基本语句执行次数的数量级放入大Ο记号中。

示例：

int i,j,n;
int x = 0;
for (i=1; i<=n; i++)
    x++;
for (i=1; i<=n; i++) {
    for (j=1; j<=n; j++)
            x++;
}

上面程序中，第一个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n^2)，则整个算法的时间复杂度为Ο(n + n^2) = Ο(n^2)。

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

程序分析法则：

• 对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间;
• 对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
  求和法则：是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)));
  特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n));
• 对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间;
• 对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则";
  乘法法则：是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1 * T2=O(f(n) * g(n))
• 对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度;
• 另外还有以下2个运算法则:
  (1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；
  (2) O(Cf(n)) = O(f(n)),其中C是一个正常数;

空间复杂度

是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。记作：S(n)=O(f(n))其中：n为问题的规模(或大小)

存储空间一般分为：
1）指令常数变量所占用的存储空间;
2）输入数据所占用的存储空间;
3）程序运行时，临时的辅助(存储)空间；
一般地，算法的空间复杂度指的是辅助空间。

例如：
一维数组a[n]：空间复杂度O(n)
二维数组a[n][m]：空间复杂度O(n*m)

时间复杂度和空间复杂度的关系

对于一个算法，其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时，可能会使空间复杂度的性能变差，即可能导致占用较多的存储空间；反之，当追求一个较好的空间复杂度时，可能会使时间复杂度的性能变差，即可能导致占用较长的运行时间。另外，算法的所有性能之间都存在着或多或少的相互影响。因此，当设计一个算法(特别是大型算法)时，要综合考虑算法的各项性能，算法的使用频率，算法处理的数据量的大小，算法描述语言的特性，算法运行的机器系统环境等各方面因素，才能够设计出比较好的算法。