June 3, 2022
Time complexity # 时间复杂度
算法执行所需的操作数，而不是实际的运行时间
当输入 n 足够大时，低阶项可以被舍弃
RAM # Random Access Machine
单处理器 指令按序处理，无并发操作 仅包含常用指令，每个指令的执行占用常量操作时间 Average case # 对 size n 的 平均 输入，算法执行所需的操作数，（平均运行时间）
通常要用到概率分析的方法，取决于输入的分布，如果没有合理的输入分布，我们不能用概率去分析
Worst case # 对 size n 的任意输入，算法执行所需的最大操作数，即运行时间的 上界 (上限)
使算法执行时间最长的输入，例如对插入排序而言，待排序数组是已经反向排序好的
最常用
Best case # 使算法执行时间最短的输入，例如对插入排序而言，待排序数组是已经正向排序好的
\( \Theta \) notation # \( \Theta(g(n)) = \{f(n): \exists c_1, c_{2}, n_{0} \in \mathbb{R^{+}} , \forall n_{0} \leq n, 0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n) \} \)
...
June 3, 2022
Character Class # 字符类
字符 含义 \d 数字 \D 非数字 \s 空格，换行符，制表符 \S 非 \s \w 拉丁字母，数字，下划线 _ \W 非 \w . 除 \n 外的任意字符; 如果有 s flag，则为任意字符 Quantifiers # 量词，用于针对其前面的字符的数量的修饰
字符 含义 {n} n个 + 1或多，[1, +\(\infty\) ) * 0或多，[0, +\(\infty\) ) ?
...
June 3, 2022
Package # Module #
June 3, 2022
Reactor Pattern # 异步的底层原理 # 操作系统的 api
Callback # Generator # 被调用时返回一个 generator 对象，函数体不会立即执行, 通过 generator 对象控制函数体的执行
function* f() function *g() function * h() // 三种声明方式都可以， 第一种比较好 // as the star * denotes that it’s a generator function, it describes the kind, not the name, so it should stick with the function keyword Promise1 # Promise 对象表示异步操作的最终完成结果以及其值（或异常）
状态 # pending
...
June 3, 2022
SETS # 符号 含义 \(\mathbb{N}\) 自然数 \(\mathbb{Z}\) 整数 \(\mathbb{Z^+}\) 正整数 \(\mathbb{Q}\) 有理数 \(\mathbb{R}\) 实数
June 1, 2022
数学归纳和递归 # 数学归纳 # 证明：当 \( n \in \mathbb{Z^+} \) 时，\(P(n)\) 成立。
基础条件： 证明 \(P(1)\) 成立
归纳条件： 证明对 \(\forall k \in \mathbb{Z^+} \)， \(P(k) \rightarrow P(k+1) \) 成立
即可证原命题成立
推理公式： \( (P(1) \land \forall k (P(k) \rightarrow P(k+1))) \rightarrow \forall n P(n) \)，\(n,k \in \mathbb{Z^+}\)
递归 #
June 1, 2022
定义 # 树： 连接的 无向 无环图
Path # 路径： 节点和边的序列
路径长度； 路径里 边 的数量
Depth # 节点深度： 从根节点到当前节点的 路径 长度
Level # 节点层级：节点 depth + 1， （很少用）
树的层级：节点层级的最大值
Height # 节点高度： 从当前节点到 叶节点 的 最长 路径 长度
树的高度： 根节点的高度
Width # 树在深度 d 的宽度： 树在深度 d 的节点数量
树的宽度： 所有深度的最大宽
Binary Tree # 二叉树
Balanced # 平衡树的高度为 \(O(log n)\)
Height-Balanced # 高度平衡，对任意节点而言，其子树的高度差 最多 为 1，空子树的高度为 -1
...
June 1, 2022
Proof method # 证明方法
Theorem # 定理： 可证明为真的语句 （事实，真相）
Axioms # 公理： 假定为 true 的语句 (statements)
Lemma # 引理，辅助定理
Proof # 证明 p true， q 为 true
Direct proof # 直接证明
if p true, p -> q true, q true
Contraposition # ~q -> ~p
Contradiction # 矛盾法
June 1, 2022
Proposition Logic # Proposition # 命题： 描述性语句，要么真，要么假
Conditional Statements # 条件语句
if p, then q, i.e. \(p \rightarrow q\)
推理规则 # 例如：
假设 p 为 true 时 p 能推出 q，那么 q 为 true
即: \((p\land(p \rightarrow q)) \rightarrow q\)
p
\(p \rightarrow q\) (条件语句)
\(\therefore q\)
Argument Form # 推理方式，论证方式
June 1, 2022
三次握手 # client 发送 syn（Synchronize Sequence Number）到 server，表示想要建立 tcp 连接 Server 发送(syn+ ack) client 发送 ack 给 server，连接建立 四次挥手 # client 发送 FIN server 接收到 FIN，发送 ack server 发送 FIN client 发送 ack 网络分层 # TCP/IP 模型 # 应用层 传输层 网络层 链路层 OSI 模型 # 应用层 展示层 会话层 传输层 网络层 链接层 物理层 HTTP 1.1 # 缺点：
...