计数法则 # 积法则 # 从两个不相集里选择有序对的方法数 假定任务 Task 可以分两步去解决，第一步有 \(n_1\) 种解决方法，第二步有 \(n_2\) 种解决方法，那么解决任务 Task 总共有 \(n_1 \times n_2\) 种方法 和法则 # 从两个不相交集里选一个元素的方法数 如果任务 Task 在条件一下有 \(n_1\) 种方法解决，在条件二下有 \(n_2\) 种方法解决，那么在两种条件都考虑的情况下，任务 Task 共有 \(n_1 + n_2\) 种解决方法 Permutations and Combinations # 排列组合 排列 # 有序 n 元集里的 r 排列： \[ n, r \in \mathbb{Z^{+}}, 1 \leq r \leq n ，P(n,r)=n(n-1)(n-2)…(n-r+1)= \frac{n!}{(n-r)!} \] 0 的阶乘为 1 组合 # 无序 ...
BNF # Backus-Naur form (BNF)，用于描述计算机编程语言的语法规则
指数 # 定义： \( b \in \mathbb{R^+}, n \in \mathbb{R^+} \), \(f_b(n) = b^n = b \cdot b \cdot b \cdot … \cdot b\)，n 个 b 相乘 定理： \(b^{x+y} = b^x \cdot b^y\) \((b^x)^y=b^{x \cdot y}\) 对数 # 定义： \(f = \log_b x \)，以 b 为底的 x 的对数值 \(b^x = a, x = \log_b a\) \(b^{\log_b a} = a\) 定理： \(\log_b (x \cdot y)=\log_b x + \log_b y\) \(\log_b (x^y)=y \cdot \log_b x\) \(\log_a x = \frac{\log_b x}{\log_b a}=\frac{1}{ \log_b a} \cdot \log_b x\)，（换底，常量值乘以 b 为底的对数） 在计算机领域，\(\log x\)，底省略时，通常指以 2 为底的对数
表设计 # KEY, INDEX # KEY, INDEX，是同义词，避免全表扫描，提高数据检索速度 PRIMARY, UNIQUE # 用来确保数据的唯一性（插入或更新时），即不能有两行一样的数据（某一列或几列一致），即列或组合列的值要唯一 unique index: 唯一索引， 可以有多个唯一索引, 可以用在空(NULL)列上 primary key: 主键，一个表最多只有一个主键，是唯一索引的特殊形式，用于唯一标识表里的某一行数据，只能用在非空列上 Table Name # Mysql 表名 数据库名大小写不敏感，在存储和查找时都会被转为小写 保留字 # 用保留字做表名或列名时，加 backticks e.g. ADD COLUMN `name` VARCHAR(191) NOT NULL Foreign key # 在 Relation 的一侧存储. Relation #
实现 # 归并排序，采用分治法，时间复杂度为 \(O(nlog n)\) /** * @param {number[]} arr 待合并原始数组 * @param {number} p 左索引，第一个元素的索引 * @param {number} q 中位索引 * @param {number} r 右索引，最后一个元素的索引 * * [p, q), [q, r] 均为已排序好的子数组 * * 将 [p,q), [q, r] 合并为一个排序好的数组 * */ const merge = (arr, p, q, r) => { // concat 的为哨兵节点 const arrLeft = arr.slice(p, q + 1).concat(Number.POSITIVE_INFINITY); const arrRight = arr.slice(q + 1, r + 1). ...
定义 # 分治：将 大问题 拆为 不相交 的 规模更小 的 子问题 ， 根据子问题的解求出原始问题的解 分：大问题拆为小问题 治：解决小问题 合：由小问题的解合为大问题的解 分治的复杂度分析 # Substitution method # 替换法 Recursion-tree method # 递归树方法 Master method # 主定理
Dynamic Programming # 动态规划: 由子问题的解推出最终问题的解，子问题重叠，即子问题共享子子问题 避免重复计算子问题 通常用于解决最优问题（最小，最大），求最优解 动态规划的基本元素 # Optimal Substructure # 最优子结构，通过子问题的最优解，求出最终的最优解 Overlapping Subproblem # 重叠子问题
草稿，待完善 Greedy # 贪心 每一步都求最优解
Rod-Cutting # 切钢条问题 钢条长度 i 和售价 P(i) 的对照表 Length i 1 2 3 4 5 6 7 8 9 10 Price P(i) 1 5 8 9 10 17 17 20 24 30 Cut ways 1 2 4 8 求给定长度 n 的钢条的最大销售额 R(n) ? 解： 设长度为 n 的钢条的最大销售额为 R(n) R(n) = Max {P(n), R(1) + R(n -1), R(2) + R(n - 2)}
定义 # 循环不变式： 循环的每次迭代中，始终为 true 的断言 \( (P \land condition) \{ S \} P \)，即 \(P\) 为循环不变式 证明循环语句正确的步骤 # 猜测 \(P\) 为循环不变式 证明 \(P\) 为循环不变式 证明程序会终止 证明程序终止时 \(P \land \neg condition \) 为 \( T \)