定义 # 有序元素集，整数子集到另一个集合的映射 例: \( \{a_{n}\} \)， \(a_n = \frac {1}{n}\)，\(n \in \mathbb{Z^+} \) 等比级数 # \(a, ar, ar^2,…,ar^n\), (\(a,r \in R\))，r 为 公比 等差数列 # \(a, a+d, a+2d, … ,a+nd, …\), d 为 公差 Fibonacci sequence # 斐波那契数列 \(f_0 = 0, f_1 = 1, f_n = f_{n-1} + f_{n-2}, ( n \geq 2, n \in \mathbb{Z^+} ) \)
定义 #
定义 # 一个特殊的二叉树结构 用数组表示时，对于数组中索引位置为 i 的元素，其对应树表示中，父节点，左右子节点的索引满足以下关系： Parent(i) = Math.floor(i/2) Left(i) = 2*i Right(i) = 2*i + 1 Max heap # 最大堆 除了根节点 A[i] <= A[parent(i)] Min heap # 最小堆 除了根节点，A[i] >= A[parent(i)] 通常用来实现优先队列 维持堆属性 # 构造最大堆 # 堆排序 # 优先队列 #
思想 # 分治 + 递归 步骤 # 选定参考元素 p (例如最右侧元素) 遍历数组，将比参考元素小的元素都挪到左边，并记录元素数量 遍历结束，数组分为 <= p | >p | p 将 p 移到中间 <=p | p | >p 返回中间的索引 递归处理 <=p 部分 递归处理 >p 部分 排序结束 实现 # /** * 数组分割 */ const partition = (arr, p, r) => { // 选数组最后一个元素为分割点 const pivot = arr[r]; let i = p - 1; // 遍历，将比分割点小的元素都挪到左边 for (let j = p; j < r; j++) { if (arr[j] <= pivot) { i++; let tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } // 将分割点的元素挪到左右数组中间 const tmp = arr[i + 1]; arr[i + 1] = pivot; arr[r] = tmp; // 返回分割点的索引 return i + 1; }; /** * 快速排序 */ const quickSort = (arr, p, r) => { // p < r 时，数组中不止一个元素，需要排序，否则无需排序 if (p < r) { // 数组分割，找出分割点索引，分割点左侧的值都不大于分割点，右侧的值都大于分割点 const pivotIdx = partition(arr, p, r); // 快排左右两侧的子数组，注意这俩子数组里均不包含 pivotIdx // 左数组快排 quickSort(arr, p, pivotIdx - 1); // 右数组快排 quickSort(arr, pivotIdx + 1, r); } return arr; }; const arr = [2, 8, 7, 1, 3, 5, 6, 4]; export { quickSort }; 分析 # 时间复杂度： O(nlogn)
定义 # 不同 对象（元素）的 无序 集合 允许包含相同元素的集合称为 multiset（多集） 表示 # Roster method # 花名册法，枚举集合里的每个元素 Set builder notation # 集合构造器表示法 例如： \( O = \{x \mid x 为奇数 \} \) 或 \( O = \{x: x 为奇数 \} \) 集合的操作 # 差集 # A - B = {x: \(x \in A \) and \( x \not\in B \) } 交集 # 并集 # 子集 # Cardinality # 集的势 (size)，集合里元素的数量,表示为 |S| ...
硬件设计理念 # 并不绝对，都是权衡（trade-off） 越小越快 时钟周期 # CPU 时钟一个周期的时间 Register # 寄存器 在 RISC-V 架构里，一个寄存器的大小是 64 bit，64 bit 又称为 双字 ，32 bit 称为 字 ，通常只有 32 个寄存器 寄存器数量过多会增加时钟周期（电子信号走的远就更耗时） 1 Byte = 8 bits Procedure # 程序 x10-x17，8个参数寄存器，用来传参和返回值 x1，返回地址寄存器 执行过程 # 把参数放到程序能访问到的地方 控制权转移给待执行程序 分配程序执行需要的存储空间 程序执行 把返回值放在调用者能访问到的地方 转移控制权给调用方 返回地址 # 程序执行完后需要返回到的 调用方 的地址
实现 # 时间复杂度 \( O(n^2 \) const insertSort = (arr) => { const len = arr.length // 从第二个元素开始遍历 for (let i = 1; i < len; i ++ ) { const ele = arr[i] // 索引i位置的值依次跟前面的元素比 for (let j = i - 1; j >= 0; j --) { const cur = arr[j] const next = arr[j + 1] if(cur < ele) { break } arr[j] = next arr[j+1] = cur } } return arr } 分析 #
头文件 # 用于将函数，变量声明放在同一个文件里，便于被其他文件引用 仅包含声明，不包含定义，定义在 linker 阶段链接到程序里 如下图 #include "something.h" /*当前目录下找*/ #include <iostream> /*在系统环境里找, include directory*/
预处理 # C: C 或 C++ 程序编译前的转换过程，不修改源文件，仅在内存中完成转换 preprocessor 不理解 C 的语法 指令在编译前被解析 参考 预处理指令 # 以 #symbol 开头（symbol为指令字符），以换行符结尾; 常用指令 指令 含义 #include 引入头文件 #define 宏定义 #ifdef, #ifndef, #endif. 条件编译指令 #if 0 不编译某些代码块 Object-like Macros # 类对象宏 #define PRINT_JOE /* 用于条件编译 */#define MY_NAME "Alex" /* 用于常量定义, 老代码里用到 */
概率 # 抽样实验 # 从可能的结果集里取值的过程 取样空间 # 可能的结果集 抽样事件 # 取样空间的子集 定义 # 如果 \( S \) 为有限的非空的等概率的取样空间，\(E\) 为抽样事件，那么 \(E\) 的概率为 \(p(E) = \frac{\vert E \vert}{\vert S \vert}\) 定理 # 抽样事件 \(E\) 的补集 \(\bar E\) 的概率为 \(p(\bar E)= 1 - p(E)\)