前言

真不太懂，小孩子不懂事写着玩的。就很不严谨的个人看法。

大O表示法

什么是大O表示法？

一种用于表示算法操作数的增速，运行时间的表示。

常见五种大O表示法

O(logn)<O(n)<O(n*logn)<O(n^2)<O(n!)

快 → 慢

数组和链表

什么是数组和链表？

假设你和你的哥哥与弟弟约着一起去看电影。

数组的情况

你和你的兄弟情比金坚一刻也不能分开，你们在电影院选座位只能选择三个连在一起的座位。如果没有三个连在一起的，这时候唯一的做法只有让已经选好座位的人让出座位，这就是数组。

数组的好处在于要单独寻找你们非常方便，比如我要找老大，那么只需要O(1)次操作就能找到哥哥。

数组的不便之处在于插入和删除。如果需要删除老三，则需要先遍历整体找到老三再删除，时间复杂度为O(n)。同理，如果你们的母亲再生了一个老四，如果老四想占据老二的位置，那么得先让原来的老二和老三向后整体挪动，生成空余地区，再加入老四。

然而数组的存储空间就像是你们的家，如果没有足够的空间，便没法容纳老四。因此，虽然现在只有三个孩子，但是考虑到以后的增减，我们一般在创建数组时候会刻意多生成几个空间。

链表的情况

你和兄弟们都很宽容，看电影不需要坐在一起。你们有空位就坐，虽然你们坐着分开了，但是你们同属于“兄弟”这个链表。

链表的好处在于增减元素十分方便。如果这时候你父母也想来和你们一起看电影，那么父母就随便找空位坐就好，只需要O(1)次操作，不需要像数组那样必须连在一起。

链表的不便之处在于查找。因为你们都坐分散开了，所以别人只能通过“血缘关系”的链查找你们每一个人。比如现在链表里有老大老二老三，老大知道老二坐哪里，老二知道老三坐哪里。那么我要找到老三，我必须先问老大，再问老二，最后找到老三。时间复杂度为O（n)

总结

数组元素挨在一起，读取速度很快，但是所有元素类型需要相同。

链表元素随机分散，每一个元素都存储了下一个元素的地址。链表插入和删除元素的速度很快。

在通常情况中，数组一般用的更多，因为它支持顺序访问和随机访问。

栈

什么是栈？

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。

假设我是蜜雪冰城的前台服务员。我有一个长钉子用来订我的订单。每当XX外卖为我自动接单了，我做完饮料就把打印出来的订单插入钉子中，这么一来钉子上就插了一堆单子。

这时候我想要找到其中某个单子，我就只能从表面的单子入手，把最外面的单子一张一张地取走。

把单子取走的过程叫做弹出(pop)，往钉子上插新单子的过程叫做压入(push)。

弹出：删除并读取

压入：插入

调用栈

计算机在内部使用被称为调用栈的栈。具体如何运行见下：

def greet1(name):
    print(f"Hello{name}")
    greet2(name)
    print("**long talking time passing**")
    bye()
    
def greet2(name):
    print(f"How are you {name}?")
def bye():
    print("bye")

当我们在运行greet1总体函数时，我们先把greet2压入（调用了greet2），然后greet2执行完毕之后弹出。压入bye，bye执行完成之后弹出。

可以看到的是，当greet2压入→弹出时候，greet1处于暂停未完成状态。此时的greet1并不是完全被抛弃了，而是作为在底下的单子默默地发挥作用。

队列

什么是队列？

相当于有两个出口的栈。就如同你在排队一般，先到公交站的人会先上车（大家都很有素质的情况下）。

队列遵循一种“先进先出”的理论，而栈则是“后进先出”。而无论是队列还是栈，你们都没法随机地访问里面的元素。

平均情况和最糟情况

一般来说在用大O表示法时，我们会简单地省略掉常量，比如O(3*n)与O(n/4)，实际上都会写为O(n)。常量对我们所耗时间的影响微乎其微，但有时影响很大。此时我们就会讨论到平均情况和最糟情况。

快速查找里的平均情况和最糟情况

假设此时输入的列表为[1,2,3,4,5,6,7,8]。

如果我们选择的基准值为第一个元素，那么调用栈的高度【层数】会高达8，因为我们要一层一层地拆分它。

但是如果我们的基准值从中间找，调用栈的高度会骤降到3。因为你每次都在对半拆开，所以就不会递归那么多次。

第一个示例演示的是最糟情况，调用栈的高度为O(n)；而第二个演示的是最佳情况【平均情况】，栈的高度为O(logn)

每一层栈涉及到的元素为n个，所以每一层耗时为O(n)。

那么，在平均情况下，整个算法的耗时也就是O(n)O(logn)=O(nlogn)

最糟情况下，就会变成O(n)*O(n)＝O(n^2)

散列表

也就是字典，键值对的形式，一对一。

比如说像电话簿，你输入一个人的名字得到的是一个专属于那个人的电话号码，这个电话本就是一个散列表。

同理，f(x)=1同样也是一种散列表，对同样的输入都返回同样的输出。

DNS解析同样也是一种散列表。无论你访问哪个网站，网址都会转为ip地址，也就是把“网页”映射到“地址”。

缓存

相当于我们大脑的记忆功能。当我们频繁调用某一类东西（比如网站的登录界面时），为了节省时间，网页会实现把这一部分进行缓存。缓存实际上也是散列表的一种。

例：有人想知道我家cp哪点好磕，此时我们在记忆的散列表里面搜索。如果有现成的之前已经写好的饭or经常被问起所以已经有印象的点，那我们就可以直接向对方发送；如果没有，那我们就需要动用脑子现编。

权，加权图，有向/无向图，环

我们知道图是怎么画的。例如：从杭州到北京有两种方法，可以杭州→北京，也可以杭州→上海→北京。

权可以理解为图内每条边的赋值。比如杭州→北京的路费是6k，杭州→上海是50，上海→北京是4000。这样就完成了加权的过程。

有向图是指边带有方向，例如杭州→北京就只能从杭州到达北京，而不能从北京到达杭州。

当出现杭州→杭州或者杭州←→北京时，就形成了一个环。

需要注意的是，权不一定是正数。如果公司报销路费，并且如果你去柬埔寨还倒贴你5k（现实生活遇到这种情况请辞职并报警），那么杭州→柬埔寨的权可以写为-5000。

以及，Dikstra算法并不支持负权边。

参考资料

《算法图解：像小说一样有趣的算法入门书》