目录
算法的性能分析：时间复杂度和空间复杂度
时间复杂度：T(n) = O(f(n))
全称为算法的渐进时间复杂度，是算法执行的时间的度量，用来衡量算法执行的效率的高低。
在了解时间复杂度之前，应当知道一个程序运行的时间长短由每条语句的语句频度和每次执行的时间的乘积的和决定。软件对于每条语句执行的时间相对于不同的语句来说大差不差。因此衡量不同算法的执行时间即可看做衡量不同程序里的语句频度的大小。
例如：对于矩阵相乘，求其时间复杂度
算法语句 对应的语句频度
for(int i=0;i<n;i++) n+1
{
for(int j=0;j<n;j++) n*(n+1)
{
c[i][j]=0; n^2
for(int k=0;k<n;k++) n^2*(n+1)
{
c[i][j]+=a[i][k]*b[k][j]; n^3
}
}
}程序的总执行次数：T(n) = 2n^3+3n^2+2n+1
程序的时复杂度为：T(n) = O(n^3)
求解时间复杂度时的注意问题：
①对于语句执行次数为一个常数的程序，其时间复杂度为 O(1)。
②语句频度不相同时，时间复杂度可能相同。比如总的语句频度 T(n) = n^2+3n+4和 T(n) = 3n^2+n+4 的时间复杂度都为 T(n) = O(n^2)。
③时间复杂度的确定取语句频度的最高幂并且去掉系数。
④计算时间复杂度时，只需要找到语句频度最大的语句作为基本语句，计算基本语句的频度得到问题规模n的某个函数f(n)即可确定程序语句频度的最高次幂，得出时间复杂度。
提升例题：
1.
解题步骤：
①.找到语句频度最大的语句①作为基本语句
②.基本语句的语句频度的最高次幂即为程序的时间复杂度③.用T(n) = O(f(n))的方式表示时间复杂度：
T(n) =
=
= O(n^3).
for (int i = 0; i <= n; i++)
{
for (int k = 0; k <= i; k++)
{
for (int j = 0; j <= k; j++)
{
x++; //①
}
}
}2.
解题步骤：
①.找到语句频度最大的语句①作为基本语句
②.基本语句的语句频度的最高次幂即为程序的时间复杂度③a.第一次循环结束：i = 2^1;
b.第二次循环结束：i = 2^2;
…………
c.第三次循环结束：i = 2^x;
则有2^x <= n ——> x <= log2(n）(log 以2为底n的对数).
于是该算法的时间复杂度为 T(n) = O(log2(n)).
i = 1;
while(i <= n)
{
i *= 2;
}空间复杂度：S(n) = O(f(n))
全称为算法的渐进空间复杂度，是算法在计算机中执行所需要存储空间的度量，包括1.算法程序所占的空间，2.输入的初始数据所占的空间，3.算法执行过程中所需要的额外空间。
求解空间复杂度时注意的问题：
①若程序运行所需的额外空间相对于程序的输入量来说为长来常量时，则其空间复杂度S(n) = O(1),称此算法为“原地工作”。
②若程序在运行过程中所需存储量与特定的输入有关时，按最坏情况考虑。
提升例题：
1.
解题步骤：
①找到程序运行所需要的额外空间的数量。
②该程序运行过程中所需的额外空间的数量相对于输入数据来说为常数，于是时间复杂度 S(n) = O(1),称此算法为“原地工作”。
for (int i = 0; i < n / 2; i++)
{
temp = arr[i];
arr[i] = arr[n - 1 - i];
arr[n - 1 - i] = temp;
}2.
解题步骤：
①程序运行所需的额外空间与sz有关且是线性关系.
②S(n) = O(n).
for (int i = 0; i < n; i++)
{
temp[i] = arr[n - 1 - i];
}
//n：arr数组的元素个数