《算法与数据结构》揭秘：什么是算法？

发表时间: 2022-03-17 16:05

1、什么是算法

算法(algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

mark：我们可以把所有的算法想象为一本“菜谱”，特定的算法比如菜谱中的的一道“老醋花生米”的制作流程，只要按照菜谱的要求制作老醋花生米，那么谁都可以做出一道好吃的老醋花生米。so，这个做菜的步骤就可以理解为：“解决问题的步骤”

2、算法的意义

假设计算机无限快，并且计算机存储容器是免费的，我们还需要各种乱七八糟的算法吗？如果计算速度无限快，那么对于某一个问题来说，任何一个都可以解决他的正确方法都是可以的！

当然，计算机可以做到很快，但是不能做到无限快，存储也可以很便宜但是不能做到免费。

那么问题就来了效率：解决同一个问题的各种不同算法的效率相差非常大，这种效率上的差距的影响往往比硬件和软件方面的差距还要大。

3、如何选择算法

第一要保证算法的正确性

一个算法对其每一个输入的实例，都能输出正确的结果并停止，则称它是正确的，我们说一个正确的算法解决了给定的计算问题。不正确的算法对于某些输入来说，可能根本不会停止，或者停止时给出的不是预期的结果。然而，与人们对不正确算法的看法相反，如果这些算法的错误率可以得到控制的话，它们有时候也是有用的。但是一般而言，我们还是仅关注正确的算法！

第二分析算法的时间复杂度

算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，在很大程度上能很好反映出算法的好坏

数据结构与算法思维导图

详细教程资料+课件关注+后台私信；资料；两个字可以免费视频领取+文档+各大厂面试题资料内容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，嵌入式等。

1 算法的复杂度

1.1大O复杂度表示法

公式:

T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示每行代码执行的次数总和。因为这是一个公式，所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。

所以，第一个例子中的T(n) = O(2n+2)，第二个例子中的T(m) = 0(2n2 +2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫作渐进时间复杂度(asymptotic time complexity)，简称时间复杂度。

当n很大时，你可以把它想象成10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势,所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大O表示法表示刚讲的那两段代码的时间复杂度,就可以记为: T(n) = O(n); T(n)= 0(n2)。

1.2.复杂度分析法则

1）单段代码看高频：比如循环。

2）多段代码取最大：比如一段代码中有单重循环和多重循环，那么取多重循环的复杂度。

3）嵌套代码求乘积：比如递归、多重循环等

4）多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

1.3 时间复杂度分析

只关注循环执行次数最多的一段代码

加法法则：总复杂度等于量级最大的那段代码的复杂度

乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

1.4 几种常见事件复杂度实例分析

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

O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2)（平方阶）、O(n^3)（立方阶）

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

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

O(1) :

常量级时间复杂度,只要代码的执行时间不随 n 的增大而增长，这样代码的时间复杂度我们都记作 O(1)。

O(logn)、O(nlogn)

i=1;while(i<=n) {    i = i*2;}

x=log2n，所以，这段代码的时间复杂度就是 O(log2n)

O(m+n)、O(m*n)

int cal(int m, int n) {      int sum_1=0;      int i=1;      for(;i<m;++i){         sum_1 = sum_1 + i;      }      int sum_2 = 0;      int j=1;      for (;j<n;++j){         sum_2 = sum_2 + j;      }      return sum_1 + sum_2;   }

从代码中可以看出，m和n是表示两个数据规模。我们无法事先评估m和n谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。所以，上面代码的时间复杂度就是0(m+n)。

针对这种情况，原来的加法法则就不正确了，我们需要将加法规则改为: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法则继续有效: T1(m)*T2(n) = O(f(m) * f(n))。

1.5 空间复杂度分析

表示算法的存储空间与数据规模之间的增长关系

void print(int n) {    inti=0;    int[] a = new int[n];    for (i; i <n; ++i) {        a[i] =i* i;    }    for(i=n-1;i>=0;--i){        print out a[i]    }}

跟时间复杂度分析一样，我们可以看到，第2行代码中，我们申请了一个空间存储变量i,但是它是最低阶的，跟数据规模n没有关系，所以我们可以忽略。第3行申请了一个大小为n的int类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是O(n)。

我们常见的空间复杂度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。所以，对于空间复杂度，掌握刚才我说的这些内容已经足够了。

1.6 复杂度增长趋势图:

最好情况时间复杂度、最坏时间复杂度、平均情況时间复杂度、均摊时间复杂度。

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

1.最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。

2.最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。

3.平均时间复杂度：代码在所有情况下执行的次数的加权平均值。

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

二、为什么要引入这4个概念？

1.同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确地描述代码的时间复杂度，所以引入这4个概念。

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

三、如何分析平均、均摊时间复杂度？

1.平均时间复杂度

代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。

2.均摊时间复杂度

两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。

1、数组

线性表: 线性表就是数据排成像一条线一样的结构.每个线性表上的数据最多只有前和后两个方向.常见的线性表结构：数组，链表、队列、栈等。详细教程资料+课件关注+后台私信；资料；两个字可以免费视频领取+文档+各大厂面试题资料内容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，嵌入式等。

什么是数组:

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

连续的内存空间和相同类型的数据(随机访问的前提)。

优点：两限制使得具有随机访问的特性缺点：删除，插入数据效率低。

对内存空间要求高，需要一块连续的内存空间。

数组怎么根据下标随机访问的？

通过寻址公式：a[i]_address = base_address + i * data_type_size

其中data_type_size表示数组中每个元素的大小,base_address 是首元素地址,i数组下标。

为何数组插入和删除低效：

插入：

若有一元素想往int[n]的第k个位置插入数据，需要在k-n的位置往后移。

最好情况时间复杂度 O(1)

如果数组中的数据不是有序的，也就是无规律的情况下，可以直接把第k个位置上的数据移到最后，然后将插入的数据直接放在第k个位置上。

最坏情况复杂度为O(n)

平均负责度为O(n)

2. 低效的插入和删除

1）插入：从最好O(1) 最坏O(n) 平均O(n)

2）插入：数组若无序，插入新的元素时，可以将第K个位置元素移动到数组末尾，把心的元素，插入到第k个位置，此处复杂度为O(1)。

3）删除：从最好O(1) 最坏O(n) 平均O(n)

4）多次删除集中在一起，提高删除效率

记录下已经被删除的数据，每次的删除操作并不是搬移数据，只是记录数据已经被删除，当数组没有更多的存储空间时，再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。

2、链表详细教程资料+课件关注+后台私信；资料；两个字可以免费视频领取+文档+各大厂面试题资料内容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，嵌入式等。

什么是链表

1.和数组一样，链表也是一种线性表。

2.从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。

3.链表中的每一个内存块被称为节点Node。节点除了存储数据外，还需记录链上下一个节点的地址，即后继指针next。

链表的特点
详细教程资料+课件关注+后台私信；资料；两个字可以免费视频领取+文档+各大厂面试题资料内容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，嵌入式等。

1.插入、删除数据效率高O(1)级别（只需更改指针指向即可），随机访问效率低O(n)级别（需要从链头至链尾进行遍历）。

2.和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

常用链表

1.单链表

1）每个节点只包含一个指针，即后继指针。
2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。
3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。

2.循环链表

1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。
2）适用于存储有循环特点的数据，比如约瑟夫问题。

3.双向链表

1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。

2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。

3）性能特点：

和单链表相比，存储相同的数据，需要消耗更多的存储空间。

插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。

对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

4.双向循环链表：

首节点的前驱指针指向尾节点，尾节点的后继指针指向首节点。

选择数组还是链表？

1.插入、删除和随机访问的时间复杂度
数组：插入、删除的时间复杂度是O(n)，随机访问的时间复杂度是O(1)。
链表：插入、删除的时间复杂度是O(1)，随机访问的时间复杂端是O(n)。

2.数组缺点

1）若申请内存空间很大，比如100M，但若内存空间没有100M的连续空间时，则会申请失败，尽管内存可用空间超过100M。

2）大小固定，若存储空间不足，需进行扩容，一旦扩容就要进行数据复制，而这时非常费时的。

3.链表缺点

1）内存空间消耗更大，因为需要额外的空间存储指针信息。

2）对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，还可能会造成频繁的GC（自动垃圾回收器）操作。

4.如何选择？

数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。

如果代码对内存的使用非常苛刻，那数组就更适合。

应用

1.如何分别用链表和数组实现LRU缓冲淘汰策略？

1）什么是缓存？

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的CPU缓存、数据库缓存、浏览器缓存等等。

2）为什么使用缓存？即缓存的特点

缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要用到缓存淘汰策略。

3）什么是缓存淘汰策略？

指的是当缓存被用满时清理数据的优先顺序。

4）有哪些缓存淘汰策略？

常见的3种包括先进先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。

5）链表实现LRU缓存淘汰策略

当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。

6）数组实现LRU缓存淘汰策略

方式一：首位置保存最新访问数据，末尾位置优先清理

当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。

方式二：首位置优先清理，末尾位置保存最新访问数据

当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1)；当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）

2.如何通过单链表实现“判断某个字符串是否为水仙花字符串”？（比如上海自来水来自海上）

1）前提：字符串以单个字符的形式存储在单链表中。

2）遍历链表，判断字符个数是否为奇数，若为偶数，则不是。

3）将链表中的字符倒序存储一份在另一个链表中。

4）同步遍历2个链表，比较对应的字符是否相等，若相等，则是水仙花字串，否则，不是。

六、设计思想

时空替换思想：“用空间换时间” 与 “用时间换空间”

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高，时间复杂度小相对较低的算法和数据结构，缓存就是空间换时间的例子。如果内存比较紧缺，比如代码跑在手机或者单片机上，这时，就要反过来用时间换空间的思路。

3、队列

什么是队列:

队列是一种受限的线性表数据结构,只支持两个操作:入栈push()和出栈pop0,队列跟非常相似,支持的操作也 ,很有限,最基本的操作也是两个:入队enqueue(),放一个数据到队列尾部;出队dequeue0),从队列头部取一个元素。

特点:

1 . 队列跟栈一样,也是一种抽象的数据结构。

2. 具有先进先出的特性,支持在队尾插入元素,在队头删除元素。

实现:

队列可以用数组来实现,也可以用链表来实现。

用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列。

基于数组的队列:

实现思路:

实现队列需要两个指针:一个是head指针,指向队头;一个是tail指针,指向队尾。你可以结合下面这幅图来理解。当a,b,c,d依次入队之后,队列中的head指针指向下标为0的位置, tail指针指向下标为4的位置。

当我们调用两次出队操作之后,队列中head指针指向下标为2的位置, tail指针仍然指向下标为4的位置.

随着不停地进行入队、出队操作, head和tail都会持续往后移动。当tail以 . ,动到最右边,即使数组中还有空闲空间,也无法继续往队列中添加数据了。这个问题该如何解决呢?

在出队时可以不用搬移数据。如果没有空闲空间了,我们只需要在入队时,再集中出发 ,发一次数据的搬移操作。

当队列的tail指针移动到数组的最右边后,如果有新的数据入队,我们可以将 head到tail之间的数据,整体搬移到数组中0到tail-head的位置。

基于链表的实现:

需要两个指针: head指针和tail指针,它们分别指向链表的第一个结,点和最后一个结点。

如图所示,入队时, tail->next= new node, tail = tail->next:出队时, head = head->next.

《算法与数据结构》揭秘：什么是算法？

数据结构与算法思维导图

1 算法的复杂度

1.1大O复杂度表示法

总结;

热门阅读

推荐阅读