性能优化（二）

本周是跟随李智慧老师学习架构师训练营的第八周，现将本周主要学习内容总结如下：

文件控制块：文件系统将硬盘空间划分为一个一个块，一个文件占用多个块，通过一个文件控制块系统 FCB 记录每个文件占用的块。一个块默认大小是 4K。

inode：记录文件大小、创建时间，所有者等信息，以及对应的文件数据块硬盘地址索引。inode 是固定结构，能够记录的数据块索引也是固定的只能是 15 个。一个 inode 最多能存储的数据块是：12+256+256*256+256*256*256，故一个文件大小最大为 70G。

RAID：独立硬盘冗余阵列。

RAID0：将一个文件分成多个部分存储在不同的硬盘上

RAID1：将一个文件存储在两个互为备份的硬盘上

RAID10：RAID0 和 RAID1 的组合

RAID5：N 块磁盘，将一个文件分成 N-1 份，一块磁盘存储校验信息（螺旋式记录校验信息），其余磁盘存储文件信息。通过异或的方式获取丢失信息。常用方式

RAID6：与 RAID5 相似，用两块磁盘备份记录校验信息

时间复杂度：粗略估计一个算法的执行效率

空间复杂度：程序运行占用的临时空间

常见的时间复杂度：

O(1)：map，set

O(n)：数组遍历，链表遍历

O(logn)：二分查找

O(n*logn)：快速排序，归并排序，堆排序

O(n^2)：冒泡排序，插入排序，选择排序

O(n!)、O(2^n)：非多项式，随数据量增大算法复杂度会急剧升高

常见数据结构：

数组

链表

栈

堆

hash

树

图

跳表

trie 树

并查集

红黑树特点：

1.所有的节点要么是黑色要么是红色

2.叶子节点是黑色并且是空节点

3.根节点是黑色

4.红色节点不能相邻

5.从任一节点到它的叶子节点经过的黑色节点的数目相同

常用算法：

穷举

递归

贪心：改进版：迪杰斯特拉算法

动态规划

启发式搜索

剪枝

分治

遗传算法：不一定能得到最优解，效率高

HTTP 响应的 5 中状态：

1XX 消息：请求已被服务器接收，继续处理

2XX 成功：请求已成功被服务器接收、理解、并接受

3XX 重定向：需要后续操作才能完成这次操作

4xx 请求错误：请求含有语法错误或无法被执行

5XX 服务器错误：服务器处理某个请求时发生错误

HTTP 版本：

1.0：1996 年发布，每次建立一个新的 TCP 连接

1.1：长连接，但每个连接任意时间点只能处理一个请求

2.0：引入 HTTP 流概念，允许复用 TCP 连接，但请求是有顺序的，有可能出现队头阻塞现象

3.0：QUIC，基于 UDP

BIO

NIO：多路复用，没有请求进来时，select 会阻塞

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也

可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下，

如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元

素。

请用代码（或伪代码）描述算法，并给出时间复杂度。

时间复杂度：max(O(m),O(n))

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { *         val = x; *         next = null; *     } * } */public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        Set<ListNode> set = new HashSet<>();        while(headA != null) {            set.add(headA);            headA = headA.next;        }        while(headB != null) {            if(set.contains(headB)) {                return headB;            }            headB = headB.next;        }        return null;    }}