一张思维导图带你入门算法与数据结构

当初面试华为鸿蒙OS，一切进展非常顺利，除了手写算法，没错，就因为算法，我被刷了，然后推荐我去 hms，什么意思呢？算法非常重要，编程语言可能千变万化，而算法几乎是不变的，算法只是解决问题的思路，它不止在编程中很重要，甚至各行各业都需要。我接下来将与算法杠上，关注我，带你一起走进算法的世界。

今天，我要讲的是算法基础与数据结构基础。具体请看下图：

什么是算法以及算法的用途，实属科普，这里不再赘述，你可以问问自己，它是什么以及用途是什么。我们直接说算法的复杂度，算法的复杂度包括时间复杂度以及空间复杂度，即该算法执行所需的时间与所占的内存。

算法的时间复杂度

算法的时间复杂度是渐进时间复杂度的简称，用大写O来表示，在理解时间复杂度之前，我们需要先了解算法执行所需的时间，举个例子，我去上班，每小时时速60KM，我距离公司12KM，请问我到公司需要多久，很简单，12/60 等于 0.2 小时，假设我距离公司是NKM，则我到公司需要 N/60 小时，我们可以记为 T(n) = n / 60，这里，T(n) 表示我到公司的时间，n 是总路程，假设T(n) 表示的是算法的执行时间，至于单位，我们忽略，n 是输入规模，则 T(n) = n / 60 可以理解为算法的执行时间，当 n 是无穷大时，n / 60 也是无穷大，该算法的复杂度可记为 T(n) = O(n)

算法的时间复杂度，你可以理解为当算法的输入规模是N时，该算法执行完毕需要的时间函数，而N是无穷大的。另外，算法的复杂度也可能因为输入规模不一样而不一样，比如输入规模很小时，性能很优，而输入规模变大时性能很差。

算法的空间复杂度则是该算法执行时所需的存储空间的大小。

数据结构 - 数组

数据结构可以理解为数据的存储与组织形式，我们平时用的最多的可能是数组，数组的优点也很明显：

通过下标直接读取，这使得数组具有很好的 读取、修改速度。修改肯定需要先读到。

而数组的缺点也很明显：

因为要通过下标直接读取数据，那么它在存储时需要一段连续的存储空间，且存储时是顺序的，即下标0后面是下标1，之后是下标2，那么新增时，假设在尾部新增，那么很简单，类似更新，而在中间新增时，比如最初数组存储的是：1、3、5、9 现在需要在5 和 9中间新增一个7，那么，我们需要把9向后移动，腾出空间存储7，可见，数组在新增时性能低下，无法使用零碎的内存空间去存储数据。

数据结构 - 链表

链表则和数组相反，它不要求内存空间连续，它要求每个数据存储一个指向下一个数据的指针，这时候，读取数据不方便，比如读取第是个数据，我们就需要从头指针开始找，由此带来的缺陷是查找慢、更新慢、删除慢，更新和删除之所以慢是因为查找慢，如果忽略查找慢，那么更新和删除很快，只需要将指针改下即可。如果我们同时存储了指向上一个数据的指针，则链表变成了双向链表，如果尾部指向头部，则变成了环。至于环，我们以后慢慢说。

数组的查找时间复杂度是T(n) = O(1)，更新也是T(n) = O(1),而删除与新增都是T(n) = O(n),链表的查找时间复杂度是T(n) = O(n)，而更新、删除、新增都是T(n) = O(1)

栈与队列

栈是先进后出，只能从栈顶放入或取出，而栈底是不能取出的，而队列是先进先出，从对头出，从队尾插入，队列可以扩展为双端队列，即对头队尾都可以插入与移除。另外，如果队列是按优先级出对，则变为了二叉堆，关于堆，我后面会再补充。

散列表 相关的知识，请待我下回讲解。