算法和数据结构基础知识分享（上）

有哪些常见的数据结构？基本操作是什么？常见的排序算法是如何实现的？各有什么优缺点？本文简要分享算法基础、常见的数据结构以及排序算法。

一 前言

1 为什么要学习算法和数据结构？

• 解决特定问题。
• 深度优化程序性能的基础。
• 学习一种思想：如何把现实问题转化为计算机语言表示。

2 业务开发要掌握到程度？

• 了解常见数据结构和算法，沟通没有障碍。
• 活学活用：遇到问题时知道要用什么数据结构和算法去优化。

二 数据结构基础

1 什么是数据结构？

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效的访问和修改数据。

数据结构是算法的基石。如果把算法比喻成美丽灵动的舞者，那么数据结构就是舞者脚下广阔而坚实的舞台。

2 物理结构和逻辑结构的区别？

物理结构就像人的血肉和骨骼，看得见，摸得着，实实在在，如数组、链表。

逻辑结构就像人的思想和精神，它们看不见、摸不着，如队列、栈、树、图。

3 线性存储结构和非线性存储结构的区别？

• 线性：元素之间的关系是一对一的，如栈、队列。
• 非线性：每个元素可能连接0或多个元素，如树、图。

三 算法基础

1 什么是算法？

• 数学：算法是用于解决某一类问题的公式和思想。
• 计算机：一系列程序指令，用于解决特定的运算和逻辑问题。

2 如何衡量算法好坏？

• 时间复杂度：运行时间长短。
• 空间复杂度：占用内存大小。

3 怎么计算时间复杂度？

大O表示法（渐进时间复杂度）：把程序的相对执行时间函数T(n)简化为一个数量级，这个数量级可以是n、n^2、logN等。

推导时间复杂度的几个原则：

• 如果运行时间是常数量级，则用常数1表示。
• 只保留时间函数中的最高阶项。
• 如果最高阶项存在，则省去最高项前面的系数。

时间复杂度对比：O(1) > O(logn) > O(n) > O(nlogn) > O(n^2)。

不同时间复杂度算法运行次数对比：

4 怎么计算空间复杂度？

常量空间 O(1)：存储空间大小固定，和输入规模没有直接的关系。

线性空间 O(n)：分配的空间是一个线性的集合，并且集合大小和输入规模n成正比。

二维空间 O(n^2)：分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模n成正比。

递归空间 O(logn)：递归是一个比较特殊的场景。虽然递归代码中并没有显式的声明变量或集合，但是计算机在执行程序时，会专门分配一块内存空间，用来存储“方法调用栈”。执行递归操作所需要的内存空间和递归的深度成正比。

5 如何定义算法稳定性？

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。

不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

6 有哪些常见算法？

首先要明确：特定算法解决特定问题。

• 字符串：暴力匹配、BM、KMP、Trie等。
• 查找：二分查找、遍历查找等。
• 排序：冒泡排序、快排、计数排序、堆排序等。
• 搜索：TFIDF、PageRank等。
• 聚类分析：期望最大化、k-meanings、k-数位等。
• 深度学习：深度信念网络、深度卷积神经网络、生成式对抗等。
• 异常检测：k最近邻、局部异常因子等。
• ......

其中，字符串、查找、排序算法是最基础的算法。

四 常见数据结构

1 数组

1）什么是数组？

数据是有限个相同类型的变量所组成的有序集合。数组中的每一个变量被称为元素。

2）数组的基本操作？

读取O(1)、更新O(1)、插入O(n)、删除O(n)、扩容O(n)。

2 链表

1）什么是链表？

链表是一种在物理上非连续、非顺序的数据结构，由若干个节点组成。

单向链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。

2）链表的基本操作？

读取O(n)、更新O(1)、插入O(1)、删除O(1)。

3）链表 VS 数组

数组：适合多读、插入删除少的场景。

链表：适用于插入删除多、读少的场景。

3 栈

1）什么是栈？

栈是一种线性逻辑数据结构，栈的元素只能后进先出。最早进入的元素存放的位置叫做栈底，最后进入的元素存放的位置叫栈顶。

一个比喻，栈是一个一端封闭一端的开放的中空管子，队列是两端开放的中空管子。

2）如何实现栈？

数组实现：

链表实现：

3）栈的基本操作

入栈O(1)、出栈O(1)。

4）栈的应用？

• 回溯历史，比如方法调用栈。
• 页面面包屑导航。

4 队列

1）什么是队列？

一种线性逻辑数据结构，队列的元素只能后进后出。队列的出口端叫做队头，队列的入口端叫做队尾。

2）如何实现队列？

数组实现：

链表实现：

3）队列的基本操作？

入队 O(1)、出队 O(1)。

4）队列的应用

• 消息队列
• 多线程的等待队列
• 网络爬虫的待爬URL队列

5 哈希表

1）什么是哈希表？

一种逻辑数据结构，提供了键（key）和值（value）的映射关系。