架构师训练营 - 学习总结 第 8 周

本周三的课程，主要讲解了算法基础

• 时间复杂度

指算法的执行时间情况，通常按循环次数 与 输入数据量的是否呈线性关系，以及该关系的函数来表示，

例如 O(N)，表示有N个输入，则运算需要计算N次

O(2N)，则表示有N个输入，运算需要计算2倍的N次

O(log2(N))，表示有N个输入，运算次数需要 log2(N)次，比如红黑树

O(1)，表示计算次数是一个固定的常数，与输入个数无关

需要注意的是：有些同学说自己的时间复杂度是 O(2)，因为要计算2次，实际上没有O(2)的说法，只要是固定的常数，都用O(1)表示。



• 空间复杂度

指算法执行时的空间占用情况，跟时间复杂度类似，按元素占用的临时空间数 与 输入数据量的线性关系来表示。



• 数组和链表

一种是线性空间，一种是通过指针相关联。

数组读取快速，插入慢。

链表则相反，读取要遍历，插入快。



• 堆栈

一种后进先出的数据结构，通常用于函数调用，保存现场用。



• Hash结构

读取快速，插入也快速的一种数据结构。

存在Hash冲突，但是如果Hash算法一般都比较均匀，冲突概率较低

Java8的HashMap基于红黑树实现



• 跳表

一种相对简化的类二分查找算法，Redis主要使用这种算法。



• 背包算法

重点讲解了背包算法，以及几个解决背包算法的思路。



• 网络七层协议和TCP/IP的四层协议讲解

TCP协议的建立连接需要3次握手，断开连接需要4次挥手。

比较常见的问题，是半连接，可能导致服务器大量连接异常，从而拒绝服务；

以及断开连接，只做了2次挥手，导致本地处于CLOSE_WAIT状态，从而出现内存问题。



• HTTP协议

常用的METHOD：GET/POST/PUT/DELETE/OPTION等。

以及响应状态： 1xx/2xx/3xx/4xx/5xx



• Java的NIO：New IO处理过程。



• 数据库优化过程

注：这里老师讲解有些问题，MySQL并不建议使用查询缓存，以及预编译缓存对性能的优化也是比较小的，MySQL8.0甚至都取消了查询缓存功能，并且官方建议，使用客户端缓存，不要依赖MySql缓存。