时间复杂度

前言

作者：小蜗牛向前冲

名言：我可以接收失败，但我不能接收放弃

如果觉的博主的文章还不错的话，还请 点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正。

为了更好的学习数据结构，我们应该要好好的理解理解一下什么是时间复杂度？怎么去计算时间复杂度。

一算法运行时间

我们来看到下面这段代码，该代码到底会运行多少时间呢？

#include<stdio.h>
 
int main()
{
  int n = 100;
  int i = 0;
  for (i = 0;i < n;i++)
  {
    printf("hehe\n");
  }
  return 0;
}

不少小伙伴肯定认为，这不在计算机上跑一下不就知道呢？但我们知道在不同计算机是运行程序的速度是不一样的，那么这样认为就是算法跑的速度是不合理的。那我们又如何去思考这个问题呢？其实我们要抓住问题的本质，程序运行时间都花到哪里去了？

当电脑运行这段代码时，执行任何一条语句都要花费时间，这是时间主要的花费。

为了方便计算时间我们认为每条语句执行的时间都是相同的，记为一个时间单元。

那么我们下面来计算一下上面程序花费多少个时间单元。

• 黑色框中的4语句共花费四个时间单元
• 红色框中的1条语句共花费n+1个时间单元(最后还要比较)
• 蓝色框中的1条语句共花费n个时间单元

那么该程序一共花费2n+5个时间单元，可以看出程序消耗的时间和n成线性关系。

这咋还咋讲上数学了，是的在学习数据结构的过程中，我们还是要知道一些数学的基本常识的。那么上面程序运行的时间我们可以用T(n)=2n+5来表示。

下面主要讨论n和运行时间的关系，假定不同输入和运行时间基本无关

这样我们就可以用该函数来预测程序要跑的时间，但是这个函数我们看起来，我们还是觉的比较复杂，所以我们通常会对函数进行不失真处理（保留主要特征），那我们又如何简化呢？

二 时间复杂度  

对于T(n) = 2n+5来说，我们往往只要关注对函数结果影响最大的项。

通过上面的表格的对比，我们知道上什么才是函数的主要特征，我们一般会保留最高次项而忽略该项的系数下面我们对函数化简进行举例说明。

举例说明

T(n) = n+7~忽略常数项T(n)~n

T(n) = 2n~忽略最高次项T(n)~n

T(n) = n+n^2~忽略低阶项T(n)~n^2

那么什么又是低价项呢？

其实就是相对结果来说，当n的很大的时对函数的结果影响很小，可以忽略。

那么我们又该如何去判断低阶项呢？

我们可以通过数学知识来说明，简单点的话只要记住下面图中的大小关系就可以了。

当我们简化完后，得到的表达式就可以反应的函数的整体趋势了，我们是通过该函数来预测程序的运行速度的，也就是我们用化简后的函数同样可以表示程序的运行速度。

所以，这个简化的函数我们就称为程序算法的时间复杂度，记做O(f(n))。

拿刚刚的例子来说，T(n) = 2n+7~n，该程序的时间复杂度为O(n)。

我们知道的什么是时间复杂度，那我们又该如何去计算时间复杂度呢？

三 时间复杂度的计算

下面我们通过几个简单的例子来说明时间复杂度是这么计算的。

1常数阶

  int a = 10;
  printf("a = %d\n", a);//打印a

大家可以想想这段代码的时间复杂度这么算？

我们会想这段代码就是执行了二个语句吗？就是跑了2个时间单元。这里总没有什么低阶项了，所以时间复杂度妥妥的肯定是O(2)。

这样对吗？

哈哈，我这样问了肯定是有问题的啦！这其实跟大O阶的规定有关。

咦！大O阶又是个啥子呢？

其实就是大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

噢这样啊！

那他又有什么规则呢？

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

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

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

所以说常数阶的时间复杂度都是O(1)。

2 线性阶

  int n = 100;
  int i = 0;
  for ( i = 0;i < n;i++)
  {
    printf("language genius\n");//打印语言天赋
  }

根据上文的提示我们可以很快写出该程序算法的函数T(n) = 2n+4,那么这个函数的时间复杂度就是O(n)。其实主要是因为该for循环中的代码执行了n次，在for循环里面的所有时间复杂度为O(1)的语句总的时间复杂度都是O(n)。

3 对数阶

//对数阶
int BinaryLookup(int *ptr,int sz,int num)//数组首元素的地址，数组的大小，要查找的数
{
  int begin = 0;
  int end = sz - 1;
  int mid = (begin + end) / 2;
  while (begin < end)
  {
    if (ptr[mid] > num)
    {
      end = mid-1;
      mid = (begin + end) / 2;
    }
    if (ptr[mid] < num)
    {
      begin = mid+1;
      mid = (begin + end) / 2;
    }
    if (ptr[mid] == num)
    {
      return 1;//找到了
    }
  }
  return 0;//没找到
}

我们很容易理解影响一个算法的程序运行时间，一定是那个要运行最多次数的代码。

所以，我们我们要想算这个二分查找的时间复杂度，就要算while循环中语句的时间复杂度。

对于BinaryLookup函数来说，它存在

最好情况:执行1次

最坏情况:约执行logN次，这里的logN是以2为底，以N为对数

那这个时间复杂度是这么计算的呢？

我们假设最坏的结果查找了x次，数组有N个数。

第一次查找：在长度为N的数组中查找值，取中间值进行比较

第二次查找：在长度为N/2的数组中查找值，取中间值进行比较

第三次查找：在长度为N/(2^2)的数组中查找值，取中间值进行比较

所以：N = 2^x

我们在二边取对数

longN =x(log2^x)(log是以2为底)。

既然查找了logN次,也就是说while循环的时间复杂度为O(logN),即该函数的时间复杂度为O(logN)。

4 平方阶

  int i = 0;
  int j = 0;
  int n = 10;
  for (i = 0;i < n;i++)
  {
    for (j = 0;j < n;j++)
    {
      printf("traffic safety\n");
    }
  }

这是一个循环嵌套的语句，很明显内层循环的时间复杂度在讲到线性阶时就已经得知是O(n)，又经过了外层循环n次，那么这段算法的时间复杂度则为O(n²)。

这个很容易就可以看出来，我们换一个在试试。

void test(int n)
{
  int i = 0;
  int j = 0;
  for (i = 0;i < n;i++)
  {
    for (j = n;j >= i+1;j--);
    {
      printf("they violent actions in the movie revolt me\n");//电影里的暴力行为使我反感
    }
  }
}

那我们又该如何去计算得到呢？

我们还是要去计算printf语句到底执行了多少次，假设n=10

i = 0时执行了，10次，

i = 1时执行了，9次，

i =2时执行了，8次。

...............

i = 9时执行了，1次。

从中我们不然发现其实这是个等差数列，所以，printf执行的总次数为S(n)=n(n-1)/2。

根据大O的规则，该程序的时间复杂度为O(n^2)。

从中我们可以看出，计算时间复杂度最好准确的方法是自己去发现代码的内在运行的逻辑。

5 递归

这里我们就斐波那契函数来举例说明。

//斐波那契函数
long long Fibonacci(int N) 
{
  return N < 2 ? N : Fibonacci(N - 1) + Fibonacci(N - 2);
}

这里我们简单点，就令n  = 6。

从这个图中我们不难归纳出函数的调用次数为2^0+2^1+2^2+...+2^(n/2)...+2这里我们也可以理解为（2^0+2^1+2^2+...+2^(n-2))*2即是个等比数列求和。所以调用次数为：

所以该程序的时间复杂度为O(2^n)。

时间复杂度计算的总结

1简单的双重循环一般为O(2^n)(凭借经验)

2 写出程序执行次数的函数

3 画图理解计算