算法复杂度分析，是从理论角度衡量一个算法的性能指标，包括时间复杂度和空间复杂度

大 O 表示法：渐进时间（空间）复杂度，表示代码运行时间（占用空间）随问题规模增长的变化趋势

时间复杂度

$O(\log n)$代码示例：

1
2
3
4

let i=1;
while (i <= n)  {
   i = i * 2;
}

常见时间复杂度大小关系：

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

时间复杂度分类：

1. 最好情况时间复杂度
2. 最坏情况时间复杂度
3. 平均情况时间复杂度
4. 均摊时间复杂度：基本不用，略过

一般说时间复杂度，都指最坏情况时间复杂度

空间复杂度

我们常见的空间复杂度就是 $O(1)、O(n) 、O(n^2)$

基本概念

线性表是一对一关系的抽象，包括链表，队列，字符串等

1. 栈：对线性表先进后出操作的限制
2. 队列：先进先出的限制
3. 字符串：元素只能是字符

基本概念

树，表示一对多的关系模型，比如父母和子女的关系，班级和学生的关系等

存储结构

1. 双亲表示法，节点存储双亲，找父母容易，找孩子难
2. 孩子表示法，节点存储孩子，找孩子容易，找父母难
3. 孩子兄弟表示法，节点存储孩子和自己的兄弟，找孩子和兄弟容易，找父母难

二叉树

二叉树包括：

1. 斜树，退化为一对一关系，此时为线性表
2. 满二叉树，所有节点都有左子树和右子树，且所有叶子节点都在最下面一层
3. 完全二叉树，按照从上到下，从左到右编号，不出现空档

二叉树的存储：对于完全二叉树，由于其定义严格，可用层序编号顺序存储，对于一般二叉树，可用孩子表示法：二叉链表存储

二叉树的遍历：

1. 前序遍历：访问根节点，然后前序遍历左子树，和右子树
2. 中序遍历：中序遍历左子树，访问根节点，中序遍历右子树
3. 后序遍历：后序遍历左子树，和右子树，访问根节点
4. 层序遍历：其实就是广度优先遍历

通过不同遍历方法，可以得到二叉树的次序，同样，通过特定遍历方法的次序，可以确定一棵树
二叉树的遍历本质上是将一个复杂的非线性结构转换为线性结构

树、森林和二叉树的转换

待研究

特殊的树

1. 二叉查找树

定义：每个节点的值都大于左子树任意节点，且小于右子树任意节点

删除操作：

• 叶子节点：直接删除
• 只有左子树或右子树：子树向上移动
• 同时有左子树和右子树：将右子树中最小的节点移动到删除节点

平均情况：插入和查找性能都是$O(\log n)$
最坏情况：如果按照顺序或者逆序插入，会退化为链表，插入和查找性能都变为$O(n)$

性质：中序遍历结果为从小到大排列的序列

2. 平衡二叉树（AVL）

定义：在二叉排序树之上，限制任意节点的左右子树高度差最大为 1

为解决二叉查找树最坏情况退化为链表的性能问题，引入平衡二叉树，只要保持树的高始终小于$\log n$，则就能保证查找在最坏情况依然为$O(\log n)$

最小失衡树：在新插入节点向上查找，第一个不能平衡的子树

通过对最小失衡树的左旋或者右旋操作使树重新平衡。

2. 红黑树（AVL）

2-3 树：有两种节点，2-节点和 3-节点
2-节点：包含一个元素和两个子节点
3-节点：包含两个元素和三个子节点

插入操作：
2-节点，2-节点直接变为 3-节点，树的高度不变
3-节点，多余节点向父节点移动，如果父节点是 2-节点，则父节点变为 3-节点，高度不变

当原来的树中所有元素都为 3-节点时，由上可知，根节点由一个 3-节点分化为 3 个 2-节点子树，树的高度加 1

由此可见，2-3 树是向上增长，插入操作最坏情况性能是$O(\log n)$，而且始终保持平衡，因此，查找性能依然为$O(\log n)$

红黑树：本质就是 2-3 树，用颜色代替 3-节点的功能，便于代码操作

所有的 3-节点拆分为 2 个 2-节点，用红色标注 2 个中较小的那个节点

红黑树的性质：

1. 保持根节点为黑色
2. 如果一个节点是红色的，则它的子节点必须是黑色的

插入操作：通过左旋、右旋和颜色变换，实现平衡

五种情况：

• 插入到一个 2-节点，且节点小于该 2-节点
• 插入到一个 2-节点，且节点大于该 2-节点
• 插入到一个 3-节点，且插入节点小于 3-节点的两个节点
• 插入到一个 3-节点，且插入节点大于 3-节点的两个节点
• 插入到一个 3-节点，且插入节点在 3-节点的两个节点之间

红黑树和平衡二叉树比较：
增删方面：红黑树性能优于平衡二叉树，红黑树任何不平衡，都能在 3 次旋转内得到解决
查找方面：平衡二叉树优于红黑树，因为平衡二叉树是严格平衡的，而红黑树在最坏情况下（红黑相间的斜树），查找性能是$O(2\log n)$

3. 红黑树

4) 线索二叉树
线索二叉树：由于二叉链表存储的二叉树，有很多空指针的空间浪费，所以利用这些空指针存储节点的前驱或者后继，此时二叉树实际就变为一个双向链表

1. 二叉树
2. 二叉查找树
3. 平衡二叉树
   3.1 平衡查找树之 AVL 树
   3.2 平衡二叉树之红黑树
4. B 树
5. B+树
6. B*树
7. Trie 树

图的概述

图是一种很重要且很普遍的数学模型，现实生活当中很多问题都可以用图来刻画，然后利用图的相关算法加以解决，比如：

1. 路径规划，城市之间的公路网，寻找 A 城市到 B 城市之间的最短路径
2. 社交网络，分析共同爱好等

图的存储结构

三种存储结构：邻接矩阵，邻接表，边集数组

无向图

单点连通性，找出与目标顶点所有连接的顶点
思路：DFS 遍历，用顶点数组变量标记是否访问

单点路径查找，找出与目标顶点的路径
思路：DFS 遍历，用顶点数组变量标记每个顶点的父顶点，然后从终止顶点向上查找直到找到起始节点

单点最短路径
思路：队列实现 BFS 遍历，其他跟路径查找一样

连通分量，求一幅图中所有的连通分量，可判断任意两点是否连通，常数时间的查询
思路：DFS 遍历，用顶点数组变量标记每个顶点所属的连通分量

判断是否有环
思路：DFS 遍历，一个顶点被访问 2 次，则有环

二分图（双色问题）
思路：DFS 遍历，每个顶点染相反的颜色

有向图

与无向图中的问题类似
单点可达性、多点可达性、单点路径查找、单点最短路径

DAG，检测有向图是否有环，并打印环

DFS 遍历的顶点排序：前序排列，后序排列，逆后序排列

拓扑排序定义：给定一副有向图，将所有顶点排序，使得所有的有向边均从排在前面的元素指向后面的元素
拓扑排序，就是 DFS 的逆后序排列
当且仅当有向图是有向无环图时，才有拓扑排序，所以需注意拓扑排序前检测是否有环

强连通性：如果两顶点互相可达，则为强连通的，一幅图中任意两点都是强连通的，则有向图也是强连通的
强连通分量：有向图中被分为几个子图，每个子图中的顶点均为强连通的
求强连通分量：kosaraju 算法，待研究

顶点对的可达性：判断任意两顶点是否可达，要求常数时间的查询
传递闭包算法，待研究

最小生成树（加权无向图）

生成树：包含所有顶点的无环连通子图
加权无向图：权值最小的生成树为最小生成树
加权有向图：有向图的最小生成树为最小树形图，不研究

求最小生成树的算法

切分定理：在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。

1. Prim 算法，加点法，每次选择跟树最近（权值最小）的非树顶点加入树中
2. Kruskal 算法，加边法，所有边按权值排序，每次选择权值最小的边，并且边的两个顶点不属于同一棵树，添加到树中，直到 n-1 条边或所有边都属于同一颗树

最短路径（加权有向图）

最短路径树：给定起点，到其他所有顶点最短路径的树

1. dijkstra 算法，同 prim 算法，每次选择跟树最近的边加入，一个数组保存起点到其他点的最短距离，一个数组保存当前顶点最短距离的边的信息，一个队列保存访问过的顶点
2. 拓扑排序最短路径算法，按照拓扑排序的顺序添加边，得到拓扑排序中第一个顶点到其他顶点的最短路径，对于给定的起点的最短路径，拓扑排序中起点前的顶点都是不可达的。
3. bellman-ford 算法，待研究

最长路径：权值取反求最短路径

优先级限制下的任务调度问题：
单处理器：有向图无环图的拓扑排序
多处理器：关键路径法，求有向图中的最长路径

dijkstra 算法只适用权值非负的有向图
拓扑排序最短路径算法 适用于无环有向图，可处理负权值
bellman-ford 算法，不能存在负权重环

以上为算法（第 4 版）读书笔记
算法 4 官网
课本代码和习题代码
git 地址

基本概念

1. 工作区（working tree）
2. 暂存区（stage, 或 index）
3. 仓库（repository）

基本操作

1. 创建仓库
   git init
   git clone

2. 工作区 <—> 暂存区
   git add: 在工作区添加文件或者修改文件后，执行 git add 将更新 暂存区
   git rm –cached ： 从暂存区删除文件，工作区不变
   git checkout – ： 用暂存区的文件覆盖工作区文件，危险

3. 暂存区 <—> 仓库
   git commit： 暂存区里的改动提交到本地的版本库
   git reset HEAD – ： 暂存区被仓库中的覆盖，工作区不变

4. 工作区 <— 仓库
   git checkout HEAD : 仓库中的文件替换暂存区和工作区

5. 本地仓库 <—> 远程仓库
   git push origin master: 本地仓库到远程仓库
   git fetch origin master: 远程 origin 的 master 替换到本地仓库，工作区不变
   git merge origin/master: 合并内容到本地 master 分支
   git pull: 远程仓库到本地仓库和本地工作区

6. 比较不同
   git diff: 比较工作区和暂存区
   git diff –staged: 比较暂存区和仓库
   git diff HEAD: 比较工作区和仓库区别

7. 查看状态
   git status -s: 文件状态的简写（M - 修改， A - 添加， D - 删除， R - 重命名，?? - 未追踪）

数据库

ECMAScript 是语言标准，javascript 是对 ECMAScript 的实现，js 还包括 BOM，DOM 部分

es6 是 ECMAScript2015，标准文档：http://www.ecma-international.org/ecma-262/6.0/index.html

可通过以下网站查看各宿主环境对 es6 的支持情况：

https://kangax.github.io/compat-table/es6/

http://ruanyf.github.io/es-checker/index.cn.html

javascript 语言特性：动态语言，动态类型，解释执行

1. 数据类型
   原始类型：boolean、number、string、undefined、null
   引用类型：object 和（es6 新增类型）symbol、bigint
   注：引用类型变量里存储的是指针

2. 执行环境和作用域
   js 函数执行环境是一个对象，此对象包含了这个函数中声明的变量或函数，函数的执行环境串联起来组成了类似 c 语言中的调用堆栈。
   理解执行环境，也便理解变量作用域，也就明白所谓变量或者函数提升。
   在浏览器中，最外层的执行环境就是 windows 对象

3. new 和 this
   this 是动态变化的，始终指向调用此函数的对象
   new 先创建一个空对象，然后在空对象上调用构造函数

   1 2 3 4 5 6

   function test() { console.log(this); } var t2 = new test(); t2.aa = 3; test();

   调用 test()，在全局对象上，所以 this 指向 windows 对象
   而使用 new test()，在新创建的 t2 对象，所以 this 指向 t2 对象

4. 构造函数，原型对象，实例的关系
   通过 new 调用的函数就是构造函数，如果没有通过 new 操作符来调用的，就是普通函数
   原型对象和实例的关系如图，此图来自于 JavaScript 高级编程
   
   Person 是定义的函数对象，默认有一个原型对象，所有通过 new Person 构造的对象实例内部也有原型对象，共享 Person 函数的原型对象。

5. 两个操作符
   typeof 操作符，区别原生类型或者 Object 类型，但如果想具体分辨是 Array 还是 Number 等引用类型，则需要 instanceof 操作符。
   instanceof 原理：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   function _instanceof(L, R) { //L为instanceof左表达式，R为右表达式 let Ro = R.prototype; //原型 L = L.__proto__; //隐式原型 while (true) { if (L === null) { //当到达L原型链顶端还未匹配，返回false return false; } if (L === Ro) { //全等时，返回true return true; } L = L.__proto__; } }

js 手册：
MDN 手册

glibc 库封装了 linux 系统调用，并提供 c 语言接口
所以学习 linux 系统编程，主要参考 glibc 库系统调用相关 api

一、进程控制

二、文件系统控制

1、文件读写操作

2、文件系统操作

三、系统控制

四、内存管理

五、网络管理

六、socket 控制

七、用户管理

八、进程间通信

1、信号

2、消息

3、管道

4、信号量

5、共享内存

文档参考：

1. glibc 库的官方手册：标准库和系统调用都有讲解，地址：https://www.gnu.org/software/libc/manual/html_mono/libc.html

2. linux man page：第 2 节是系统调用，第 3 节是 glibc 库函数，地址：https://www.kernel.org/doc/man-pages/

3. 相关书籍：unix 环境高级编程，The Linux Programming Interface（作者是 linux kernel man page 维护者）

引用备注：

以上分类来自于 ibm 社区：https://www.ibm.com/developerworks/cn/linux/kernel/syscall/part1/appendix.html

软件工程之美：
https://blog.csdn.net/EllieYaYa/article/details/90692766

待完成