什么是算法的时间复杂度
一个高级语言编写的程序的运行时间主要取决于三个因素：算法的方法、策略（复杂度），问题的输入规模，计算机执行指令的速度。问题的输入规模是客观的、限定的，要加快算法的效率绝不能影响问题的输入规模；计算机执行指令的速度虽然可以有显著提升，但其发展时间较长，也不是确定的，总不能终日盼着计算机性能的提升。所以提高算法的效率，减少程序运行时间，改进算法的策略是至关重要的。
在讲解时间复杂度之前，需先引入一个概念——时间频度。时间频度代表一个算法中的语句执行次数，其又称为语句频度。显然，时间频度越高的算法运行的时间越长。
时间频度也可被记为 T ( n )，其中 n 为问题的规模，即输入值的规模。当 n 不断变化时，时间频度 T ( n )也会不断变化。为了探究自变量 n 和因变量 T ( n )变化的关系，我们引入时间复杂度这个概念。不同于时间频度，时间复杂度考察的是当输入规模趋于无穷时，时间频度的渐近情况。时间复杂度的具体定义为：若有某个辅助函数 f ( n )，使得 的极限值（当 n 趋近于无穷大时）为不等于 0的常数，则称 f ( n )是 T ( n )的同数量级函数。记作
T ( n )= O ( f ( n ))
O ( f ( n ))称为算法的渐进时间复杂度，简称时间复杂度。在数学上， O 符号（Landau符号）用来描述一个函数数量级的渐近上界。因为 O 符号表示法并不是真实代表算法的执行时间，而是表示代码执行时间的增长变化趋势。
什么是算法的空间复杂度
一个算法在计算机存储器上所占用的存储空间，包括算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间，算法在运行过程中临时占用的存储空间三个方面。
算法本身所占用的存储空间由算法本身的长度决定。在大多数情况下，算法自身占用的空间对算法整体的空间复杂度的影响有限。毕竟一个手写的算法的长度是有限的，而代码用字符串的方式存储，不会占用过多空间。在绝大多数情况下，算法的输入、输出数据所占用的存储空间是由要解决的问题决定的，它不随算法的不同而改变。算法在运行过程中临时占用的存储空间随算法的不同而异。有的算法只需要占用少量的临时工作单元，而且这些临时工作单元不随问题规模的大小而改变。有的算法需要占用的临时工作单元数量与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元，例如快速排序和归并排序就属于这种情况。
而空间复杂度就是对一个算法所需存储空间的量度，但其并不考虑算法本身所占用的存储空间。若算法的输入、输出数据所占用的存储空间只取决于问题本身，则也不列入考虑范围中。因为后两个因素并不能精准地体现一个算法的优劣。类似于时间复杂度，空间复杂度也是自变量为输入规模 n 的函数，并考察输入规模趋于无穷时所占用空间的渐近情况，所以空间复杂度也用 O 符号来表示，记作
S ( n )= O ( f ( n ))
直接插入排序的时间复杂度是 O ( 2 n )，而空间复杂度是 O (1)，因为插入排序只是在已存储好的数组或列表上进行排序，不需要额外存储临时变量。一般的递归算法就要有 O ( ) n 的空间复杂度了，因为每次递归都要存储返回信息，否则大部分递归运算都在做无用功。
时间复杂度和空间复杂度往往是相互制约、相互影响的。在解决同一个问题的时候，当追求降低时间复杂度时，可能会不可避免地提高空间复杂度，即可能导致占用较多的存储空间；反之，当追求降低空间复杂度时，可能会不可避免地提高时间复杂度，即可能导致占用较长的运行时间。所以在设计一个算法的同时，要综合考虑算法的各项性能，从而更有效地提高效率。
