时间复杂度概述
- 时间复杂度是衡量算法随问题规模增大时，算法执行时间增长快慢的指标。
- 它是问题规模的函数，表示为T(n)。我们主要分析T(n)的数量级。
- 通常，T(n) = O(f(n))，其中f(n)是算法中基本运算的频度。我们一般考虑最坏情况下的时间复杂度。
计算时间复杂度的方法是，取算法中时间增长最快的函数项，并忽略它的系数。
空间复杂度简述
- 空间复杂度用于衡量算法随问题规模增大时，所需空间的增长快慢。
- 它也是问题规模的函数，表示为S(n) = O(g(n))。算法所需空间的增长率和g(n)的增长率相同。
从图表中可以看出，随着问题规模的增大（横坐标），所需时间的增长率（斜率）差异显著。而且，这种差距随着问题规模的增大而更加明显。
我们主要关注的是算法的增长规模速度。
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n²)＜Ο(n³)＜Ο(2n)。其中，log2n通常简写为logn，从左至右，时间性能依次降低。
示例算法分析
算法示例一：
int sum=0; 执行1次初始化。
for ( int i = 0 ; i <= n ; i++){ 循环体执行n+1次。
sum=sum+i; 执行n+1次累加操作。
时间分析：该算法共执行了3n+6个语句。假设每个语句执行时间一致，均为常数t，则总时间T =（3n+6)t。随着问题规模n的增大，总时间的增长率与n的增长率一致，因此复杂度为O(n)。
结论一：复杂度是关于增长率的，所以我们可以忽略常数项。
结论二：我们通常只需关注循环段基本操作语句的执行次数。
算法示例二：
for ( int i = 1 ; i <= n ; i=2i){ 循环体执行log2n次（以2为底）。
sum=sum+i; 每次循环累加操作。
该算法的时间复杂度为O(logn)。
乘法规则与加法规则：
示例三：两个独立循环体采用加法规则，如两个嵌套循环体采用乘法规则。
空间复杂度S(n)表示算法运行过程中所使用的辅助空间大小。记为：S(n) = O(f(n))。