算法的时间复杂度和空间复杂度

1.算法效率

1.1如何衡量一个算法的好坏

long long Fib(int N)
{
  if(N<3)
  {
    return 1;
  }
  return Fib(N-1)+Fib(N-2);
}

斐波那契数列的递归实现方式非常简洁，但是简洁一定好吗？那应该如何衡量其好与坏呢？

1.2算法的复杂度

衡量一个算法的好坏，一般是从时间和空间上来衡量的，即时间复杂度和空间复杂度

时间复杂度：主要是衡量一个算法运行速度的快慢

空间复杂度：主要是衡量一个算法运行所需要的额外空间

2.时间复杂度

2.1时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间，一个算法执行所耗费的时间，从理论上说是不能计算出来的，只有你把你的程序放在机器上跑起来，才能知道。但这样很麻烦，所以才有了时间复杂度这个分析方式，一个算法所花费的时间与其中语句的执行次数成正比，算法的基本操作的执行次数，为算法的时间复杂度。

即：找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度

//请计算Fun1中++count语句总共执行了多少次？
void Fun1(int N)
{
  int count=0;
  for(int i=0;i<N;++i)
  {
    for(int j=0;i<N;j++)
    {
      ++count;
    }
  }
  for(int k=0;k<2*N;++k)
  {
    ++count;
  }
  int M=10;
  while(M--)
  {
    ++count;
  }
  printf("%d\n",count);
}

准确次数：F(N)=N*N+2*N+10(时间复杂度的函数式)

• N=10     F(N)=130
• N=100    F(N)=10210
• N=1000   F(N)=1002010
• 发现：N越大，函数式后两项对结果的影响越来越小
• 实际中我们计算时间复杂度时，我们其实并不一定要计算精准的执行次数，而只需要大概的执行次数，那么这里我们使用大O的渐进表示法
• 时间复杂度：O(N^2)

大O的渐进表示法

大O符号：是用于描述函数渐进行为的数学符号

推导大O阶方法：

1.用常数1取代运行时间中的所有加法常数

2.在修改后的运行次数函数中，只保留最高阶项

3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶

举例：

void Fun2(int t)
{
  int count++;
  for(int k=0;k<2*N;++k)
  {
    ++count;
  }
  int M=10;
  while(M--)
  {
    ++count;
  }
  printf("%d\n",count);
}

准确复杂度：2*N+10 

F(N)=N           O(N)