概述

计算机程序是一组计算机能识别和执行的指令，运行于电子计算机上，满足人们某种需求的信息化工具。即程序是一个指令序列。

程序的本身有数据和逻辑构成，而数据本身又有数据元素和数据结构组成，逻辑（逻辑的经典组合）也可成为算法。

衡量算法性能的标准

衡量算法性能的标准：时间复杂度和空间复杂度，值越小越好。

• 时间复杂度：不是计算程序具体的运行时间，而是算法执行语句的次数。

• 空间复杂度：一个算法在运行过程中临时占用存储空间大小的量度。O(n)表示需要临时存储n个数据

NP问题

P问题：能在多项式时间复杂度内解决的问题。

NP问题：能在多项式时间复杂度内验证答案正确与否的问题。

NP-hard问题

比NP问题更难的问题(NP问题的解法可以规约到NP-hard问题)，解决了一个NP-hard问题，也就解决了一类NP问题。

NP完全问题

是一个NP-hard问题，也是一个NP问题



数独，这是一个NP问题，不是一个P问题。因为我们无法在多项式的时间内把这些数字都填正确了。

算法儿只能是暴力拆解，穷举的方式来计算，这个显然不是一个P问题。

但这个数独的某个答案是可以在多项式时间内可以验证的，所以它是一个NP问题。



数据结构

常见的数据结构



数组：创建数组必须要内存中的一块连续的空间, 数组中必须存放同一种数据类型。随机快速读写，根据下标访问数据，时间复杂度为O(1)，属于线性表



链表：可以使用零散的内存空间存储数据，所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。要查找一个数据，只能遍历链表，遍历时间复杂度O(n),空间不连续 ，也属于线性表

数组链表结合，实现快速查找和快速增删，比如hash表



栈：数组和链表都被称为线性表，后进先出的特点



队列：先进先出的特点，典型应用场景：生产者消费者；阻塞等待的线程被放入队列。

hash表：快速访问数据，快速增删数据。解决hash冲突-开放寻址法，链表法



树

树遍历-组合模式编写



二叉树：

类型：安全二叉树和满二叉树

遍历：前序、中序、后序遍历

二叉排序树：左子树上所有结点的值均小于或等于它的根结点的值。右子树上所有结点的值均大于或等于它的根终点的值。分不平衡的二叉排序树和平衡的二叉排序树。左右子树也分别为二叉排序树。此时查询时间取决于树高，平均时间复杂度是O(lgn)。然而BST可能长歪而变得不平衡，如下图所示，此时BST退化为链表，时间复杂度退化为O(n)。

解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；



为了解决这个问题，引入了平衡二叉树（AVL）。

左、右子树也分别为二叉排序树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。平衡的二叉排序树它的时间复杂度是O(logN)

旋转来实现二叉树的平衡

插入时，最多只需要两次旋转就会重新恢复平衡。删除时，需要维护从被删节点到根节点这条路径上所有节点的平衡性，时间复杂度O(logN)

由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

总之，通过旋转解决了平衡的问题，但是旋转操作效率太低；

红黑树



特点：

1. 每个节点自由两种颜色：红色和黑色。

2. 根节点是黑色的。

3. 每个叶子节点(NIL)都是黑色的空节点。

4. 从根节点到叶子节点，不会出现两个连续的红色节点。

5. 从任何一个节点出发，到叶子节点，这条路径上都有相同数目的黑色节点。

与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。



红黑树最多只需3次旋转就会重新达成红黑平衡，时间复杂度O(1)

在大量增删的情况下，红黑树的效率更高，红黑树的平衡性不如平衡二叉树，查找效率要差一些。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

显著缺点是：树太高，IO次数太多

总之，通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多；



B树：

B树也称B-树(其中-不是减号)，是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。 因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

总之，通过将二叉树改为多路平衡查找树，解决了树过高的问题；



B+树

B+树也是多路平衡查找树，其与B树的区别主要在于：

• B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。

• B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现——一定会在叶节点出现，也可能在非叶节点重复出现。

• B+树的叶节点之间通过双向链表链接。

• B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。



总之，在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。



堆：是一颗安全二叉树，堆中的每一个节点的值都必须大于等于（或小于等于）其中书中的每个节点的值。堆是所有线程共享的



应用场景：优化队列、利用堆求TopN、 求中位数

图

概念：

存储方式

六度分割理论

搜索算法：深度优先搜索和广度优先搜索



算法



算法是指对某些问题的严格的解释方法，一般的，一个算法拥有以下特点：

1. 有穷性：算法必须保证在执行有限步骤后结束。

2. 可行性：算法是确切可行的，即使在数学中，该算法可行，但若在实际应用中，程序不可以被执行，那么 ，该算法也是不具有可行性的。

3. 确切性：算法的每一个步骤必须具有明确的意义。

4. 输入：一个算法必须要有0个或多个输入。

5. 输出：一个算法必须要有1个或多个输出。



基本思想：贪心算法、分治算法、动态规划、回溯算法、枚举算法

常用算法：递归、排序、二分查找、搜索、哈希、贪心、分治、回溯、动态规划、字符串匹配算法、、



1.穷举算法

此中算法只是把所有的可能性都列举出来，然后进行处理。它只能适用于小的数据，大一点儿规模的数据就不行了，比如1000的阶乘，这个数字就很大了。

2.递归算法

有一个出口，然后自己调用自己。

3.贪心算法

定义：每一步都找一个当前的最优解，注意当前的最优解不见得是整体的最优解，它只能近似得得到一个较优解。

改进贪心算法-迪杰斯特拉算法(最快路径)



算法核心：找到起点到每个节点的最快路径



• 动态规划算法解决背包问题

通过找到合适的角度，讲所求解的目标值在某（几）个维度上展开，将一个大问题拆解为若干个小问题，小问题的最优解，寻找大问题的最优解。

• 遗传算法解决背包问题

遗传算法 是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

5.动态规划

定义：把一个复杂问题分解成若干个子问题，并且寻找最优子问题的一种思想，而不是一种特定的算法。



网络基础原理



网络通信的过程

DNS；域名解析服务

CDN：内容分发网络，请求、运营商机房、骨干网络、目的地，缓存服务器、静态资源

HTTP：

TCP：

• 网络底层通讯协议

• 如何建立连接



七层模型与四层模型对比



三次握手



1.App先发送SYN=1,Seq=X的报文，表示请求建立连接，X是一个随机函数；

2.服务器收到这个报文后，应答SYN=1,ACK=X+1，Seq=Y的报文，表示同意建立连接；

3.App收到这个报文后，检查ACK的值为自己发送的Seq值+1，确认建立连接，并发送ACK=Y+1的报文给服务器；服务器收到这个报文后检查ACK值为自己发送的Seq值+1，确认建立连接。至此，App和服务器建立起TCP连接，就可以进行数据传输了。



TCP关闭连接要进行4次挥手

1.客户端向服务器端发送一个FIN，请求关闭数据传输

2.当服务器接受到客户端的 FIN时，向客户端发送一个 ACK，其中ACK的值等于FIN+SEQ.

3.然后服务器向客户端发送一个FIN,告诉客户端应用程序关闭

4.当客户端收到服务端的FIN时，回复一个ACK给服务器端。其中ACK的值等于FIN+SEQ.



LB

• lvs

• DNS

• Nginx

• F5



思考

无论作为程序员还是架构师对基本的数据结构原理要懂，要锻炼成本能。算法也可以多看看，这是架构师做架构的理论基础，在程序或架构设计上都会用到算法的理论，算法其实也是一种架构方案，从微观上讲是一个解决某类问题的方案，从宏观上也可以指导架构设计-分而治之等思想的运用。



听课，我感觉知识还是次要的，主要听经历得到的认知和学习方法，跟自己有什么区别，这是为以后学习，长久地学习，获得更好成长的参考。具体的知识从书本和网上可以找到，静下心来可以去获得，但要有选择的学习，知识如浩瀚的海洋，我们只需做个海绵，取其所需即可。



孩子的学习也一样，上课和培训班，训练的是习惯和思维，当然好的老师教授的知识的方法论和知识本身都很有保证，然而所传达的深层次的理念认知可能会有一些独到的见解，更能让我们少走些弯路。



之前我面试我不怎么爱问算法，最近2年才有所改观，这也是择优而取的一个途径，从老师的授课理解上让我更认识到了另一点这也是一个人成长所必需的掌握的技能之一。若面试中有时一般的算法都不清楚，这样看来”你不是不努力，这就是你努力的样子“……



算法在实际工作中用到的情景不多，但面试也要问，因为你的认知和思维的深度要有，学习能力也要有一定的高度。这就是个人的发展潜力，至少在面试官来说他的成长暂时是没有瓶颈的。



前端也会面算法，对计算机的认知深度要有。

在大厂我们都是拧螺丝的，不拧螺丝的时候，也能够把握机会，一鸣惊人。这就是通过在平时的日积月累，天生我材必有用的见证。时刻为成功做准备的人才能脱颖而出！



https://mp.weixin.qq.com/s/9d7blEnIHmgbTd7YpmccfQ