🎈今日心语：你所看到的惊艳，都曾被平庸所历练。

数据结构指的是“一组数据的存储结构”，算法指的是“操作数据的一组方法”。

数据结构是为算法服务的，算法是要作用在特定的数据结构上的。

目录：

• 一、算法的复杂度

• 1. 时间复杂度
• 1.1 大O的复杂度表示法
• 1.2常见时间复杂度实例分析
• 2.空间复杂度

• 结语：

一、算法的复杂度

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

1. 时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。

// 请计算一下Func1中++count语句总共执行了多少次？
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
    for (int j = 0; j < N ; ++ j)
    {
        ++count;
    }
}//这里嵌套了两个for循环，
for (int k = 0; k < 2 * N ; ++ k)
{
    ++count;
}
int M = 10;
while (M--)
{
    ++count;
}
    printf("%d\n", count);
}

可以看到上面代码中共出现了4个循环：

第一个for循环与第二个循环嵌套，所以执行次数为N²;

第三个循环执行次数为2*N；

第四个循环执行次数为10；

Func1 执行的基本操作次数 ：

f(N) = N² + 2*N + 10

• N = 10 时 F(N) = 130
• N = 100 时 F(N) = 10210
• N = 1000 时 F(N) = 1002010

我们发现N越大，后面系数和常量对整体f（n）的影响越小。

实际上现在，10和100000次，相差的时间都很小，这主要依赖于cpu的强大：

#include<stdio.h>
#include<time.h>
int main()
{
  size_t begin = clock();//开始计时
  size_t n = 0;
  for (size_t i = 0; i < 10; ++i)
  {
    ++n;
  }
  size_t  end = clock();//结束计时
  printf("%d毫秒\n", end - begin);//差为时间，单位是毫秒
  return 0;
}

执行0次结果：

执行100000次结果：

上面我们是在Debug环境下的测试，但是如果在Release环境下，即使是执行一亿次时间都是0毫秒！

所以实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。

1.1 大O的复杂度表示法

大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

当n无限大时，公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略，所以只需要记录一个最大量级就可以了。

即推导大O阶方法：

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

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

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

使用大O的渐进表示法以后，Func1的时间复杂度为：

O(N^2)

• N = 10 F(N) = 100
  
• N = 100 F(N) = 10000
  
• N = 1000 F(N) = 1000000
  

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，只保留了最大量级，简洁明了的表示出了执行次数，而且对精确计算影响不大。

另外有些算法的复杂度存在最好、平均和最坏情况：

一、复杂度分析的4个概念

1.最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度，即任意输入规模的最大运行次数(上界)。

2.最好情况时间复杂度：代码在最理想情况下执行的时间复杂度，即任意输入规模的最小运行次数(下界)。

3.平均时间复杂度：代码在所有情况下执行的次数的加权平均值，即任意输入规模的期望运行次数。

4.均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。

例如：在一个长度为N数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

代码复杂度在不同情况下出现量级差别时才需要区别这四种复杂度。大多数情况下，是不需要区别分析它们的。

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

1.2常见时间复杂度实例分析

多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。包括，

O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n²) （平方阶）(n³)（立方阶）

非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。包括，

O(2ⁿ)（指数阶）、O(n!)（阶乘阶）

2.空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

如果还是不理解，请看下一篇内容 时间复杂度与空间复杂度练习题，通过习题，相信你会有进一步的理解！

这里我们关于【数据结构复杂度】的内容就介绍完了，文章中某些内容我们之前有介绍，所以只是一笔带过，还请谅解。下一篇文章，我们来通过例题来分析时间复杂度和空间复杂度
希望以上内容对大家有所帮助👀，如有不足望指出🙏

前路漫漫！努力变强💪💪 吧！！