1.2 算法时间复杂度

时间复杂度

算法 + 数据结构 = 程序。

算法和数据结构是息息相关的，他们俩是分不开的，算法要满足5个重要特性：

有穷性、确定性、可行性、输入、输出。这五个重要特性，但我个人认为，没有什么用，概念上的东西往往假大空。

算法的执行效率，也称作时间复杂度O，T(n) = O(f(n)),随着问题规模n的增大，算法执行时间和增长率和f(n)增长率成正比。

程序运行的总时间主要和两点有关，一是执行每条语句的耗时，二是每条语句的执行频率。

例如，下面的这个for循环执行了多少次？

for(int i=1; i<=n; i++)
{

}

我们能轻易地知道执行了N+1次，那么下面的for循环执行了多少次？

for(int i=1; i<=n; i++) //n+1次
{
  for(int j = 1; j<=n;j++) //n*（n+1）次
  {
   c[i][j] = 0; // n*n次
  for(int k=1;k<=n; k++) //n*n*（n+1）次
  {
  c[i][j] = c[i][j] + a[i][k]*b[k][j]; // n*n*n次
  }
  }
 }

我们知道第一层for循环，能够实际执行第二层for循环的次数是n次（第n+1次只判断而不进入第二层for循环），所以第二层for循环执行的次数应该是n*（n+1）次，同理，我们就可以得到其他语句的执行次数。

我们把所有的次数加到一起，就是f(n)，f(n)= 2n³+3n²+2n+1。

这个f(n)就是我们要的执行效率吗？也不是，他还是有一个自己的套路和规则的：

那就是，在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数，可以简化算法分析。

所以f(n)= 2n³+3n²+2n+1就被简化成了n³，即T(n) = O(n³)。

再深入思考一下，如果你的算法中的循环是一个确定的常数的话，那么不论这个常数有多大，那么他的时间复杂度恒为O(1)。

空间复杂度

空间复杂度主要用来描述某个算法对应的程序想在计算机上执行，除了用来存储代码和输入数据的内存空间外，还额外需要的空间，S(n) = O(f(n))。

不过我们都是以时间复杂度来作为对算法优劣的衡量指标，空间复杂度大多数时候不用在意，当然，后续我们会使用MCU，MCU的空间往往并不是那么充足，值得注意一下。

练习

思考下面的代码的时间复杂度是多少？

for(int i = 1; i<=n;i = i*2)
{
 x++；
 s = 0;
}