Algorithm之时空复杂度

发表于 更新于 分类于 Waline：

时间复杂度

概念: 时间复杂度是用来衡量算法的执行时间上的效果。
计算方式：
1. 找出算法的基本语句

算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
eg: i++; //时间复杂度为O(1)

2. 计算语句执行的数量级

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。
eg: 

1
2
3
4
int sum=0;                //（一次）
for(int i=1;i<=n;i++)    //（n+1次）
    for(int j=1;j<=n;j++)    //（n²次）
      sum++;                 //（n²次）

因为
$\Theta(2n^2 +n+1)=n^2$（$\Theta$即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以$T(n)=O(n^2)$。

3. 时间复杂度表示格式
  • $O(1)$
  • $O(log(n))$
  • $O(n)$
  • $O(nlog(n))$
  • $O(n^2)$
  • $O(n^3)$
  • $O(2^n)$
  • $O(n!)$
  • $O(n^n)$