财金

• 参数说明

  • pv：现值
  • fv：未来值
  • when：期初或期末付款
    • 0/end
    • 1/begin
  • pmt：Payment，每期付款
  • ppmt：Principle of Payment，每期付款中本金
  • ipmt：Interest of Payment，每期付款中利息

• 值说明

  • 正值：收入
  • 负值：支出

Histogram

Set

Operation

Unique

集合

势

• 等势：若集合 $X, Y$ 之间存在双射 $\phi: X \rightarrow Y$，则称 $X, Y$ 等势
• 可数/可列集合：与自然数集合、其子集等势的集合称为可数集合，否则称为不可数集合

• 等势构成集合之间的等价关系
  • 集合 $X$ 的等势类记为 $|X|$
  • 若存在单射 $\phi: X \rightarrow Y$，则记为 $|X| \leq |Y|$
• 一些基本结论
  • 自然数集 $N = {0, 1, 2, 3, \cdots}$ 和闭区间 $[0,1]$ 不等势

• https://zhuanlan.zhihu.com/p/34097692

序

• 偏序集：若集合 $A$ 上有二元关系 $\leq$ 满足以下性质，则称集合 $A$ 为偏序集，关系 $\leq$ 称为偏序关系

  • 反身性：$\forall x \in A, x \leq x$
  • 传递性：$(x \leq y) \wedge (y \leq z) \Rightarrow x \leq z$
  • 反称性：$(x \leq y) \wedge (y \leq x) \Rightarrow x = y$

• 全序集：若 $\leq$ 是集合上的偏序关系，若对每个$x, y \in A$，必有 $x\leq y$ 或 $y \leq x$，则称集合 $A$ 为全序集，关系 $\leq$ 为全序关系

• 良序集：若集合 $A$ 每个自己都有极小元，则称为良序集

• 特点
  • 偏序指集合中只有部分成员之间可比较
  • 全序指集合全体成员之间均可比较
  • 良序集则是不存在无穷降链的全序集（可有无穷升链）

序数

• 序数：若集合 $A$ 中每个元素都是 $A$ 的子集，则称 $A$ 是传递的。而 $A$ 对于关系 $\in$ 构成良序集，则称 $A$ 为序数

• 满足如下形式的集合即为序数

  $$\{\phi, \{\phi\}, \{\phi, \{\phi\}\}, \{\phi, \{\phi\}, \{\phi, \{\phi\}\}\} \}, \cdots$$

• 序数的性质（引理）

  • 若 $\alpha$ 为序数，$\beta \in \alpha$，则 $\beta$ 也是序数
  • 对任意序数 $\alpha, \beta$，若 $\alpha \subset \beta$，则 $\alpha \in \beta$
  • 对任意序数 $\alpha, \beta$，必有 $\alpha \subseteq \beta$ 或 $\beta \subseteq \alpha$

• 由以上，序数性质的解释

  • 序数是唯一的，都满足上述形式
  • 序数都是由自己之前的所有序数构造而来
  • 对任意序数 $\alpha$，有 $\alpha = {\beta: \beta < \alpha }$ （$ < $ 表示偏序关系）

• 将 $0, 1, 2, \cdots$ 依次对应上述序数，即给出自然数和序数

  $$0 := \phi, 1 := \{phi\}, 2 := \{\phi, \{phi\}\}, \cdots$$

• https://zh.wikipedia.org/wiki/%E5%BA%8F%E6%95%B0
• 自然数可用于描述集合大小（势，基数）、序列中元素的位置（序，序数）

良序定理

• Zermelo 良序定理：任何集合 $P$ 都能被赋予良序

• Zermelo 良序定理和 ZFC 选择公理等价，可以由选择公理证明
  • 由选择公理，可以一直从集合中选择元素，建立偏序关系
  • 而集合有限，则集合和序数之间可以建立双射

基

基数

• 基数：序数 $k$ 为基数，若对任意序数 $\lambda < k$，都有 $|\lambda| < |k|$
• Counter 定理：设 $A$ 为集合，$P(A)$ 为 $A$ 的幂集，则有 $|A| \leq |P(A)|$

• 基数是集合势的标尺

• 数的集合的基数

  • 自然数集合基数 $\aleph_0$：最小的无限基数
  • 实数集集合基数称为 continuum 连续统

• 连续统假设：不存在一个集合，基数在自然数集和连续统之间

  • 哥德尔证明：连续统假设与公理化集合论体系 Zermelo-Fraenkel set theory with the axiom of choice 中不矛，即不能再 ZFC 中被证伪
  • 科恩证明：连续统假设和 ZFC 彼此独立，不能在 ZFC 公理体系内证明、证伪

• https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0_(%E6%95%B0%E5%AD%A6)

集合

集合：互不相同项的无序组合

• 要么指出集合的特殊属性，只有集合中元素才满足的特性
• 要么显式列出集合的所有成员

存储映像

位向量存储表示

位串表示法

• 每个集合S使用一个位串表示，位串中每位代表全集U的一个元素
• 当且仅当全集$U$中第i个元素被包含在子集$S$中时，位向量 第i个元素为1

1

typedef int BitSet[MAX_SET_SIZE/sizeof(int)];

• 可以实现快速的标准集合运算
• 以使用大量存储空间为代价的

线性表存储表示

线性表表示法

• 每个集合使用一个线性表表示，线性表中存储集合元素

1
2
3
4

typedef SqList SLSet;
	// 顺序表表示集合
typedef LinkList LLSet;
	// 链表表示集合

• 集合不能包含相同元素，列表可以

  • 可以引入multiset、bag绕过对唯一性的要求
  • 多重集和包是可重复项的无序组合

• 集合是元素的组合，而列表是集合的有序组合

  • 用线性表表示集合时，不必维护线性表的有序排列

集合运算

• 检查元素是否属于集合
• 集合的并集
• 集合的交集

Disjoint Set/Union Find

不相交集/并查集：由某个有限集的一系列不相交子集，及相应 操作构成

• 通常假设集合中元素为整数，或可以映射为整数
• 主要包括find、union操作

存储映像

• 实现应该对find、union有特殊优化

  • 按秩合并：将包含较少结点的集合合并到含有较多结点集合
  • 路径压缩：将每个结点都直接指向根节点

• 大多数实现会使用集合某个元素作为该集合代表

  • 有些对代表没有特殊约定
  • 有的要求代表为子集中最小元素等

树双亲表存储表示

双亲表示法

• 使用树的双亲表示法作存储结构

1

typedef PTree MFSet;

• 以集合中某个元素作为树根、集合名，其余所有结点都作为根 的孩子结点

• 每个结点只能有一个双亲结点，即只能属于一个集合，适合存储 不相交集

应用

• 生成不相交集
  • 求解无向图中连通分量数量
  • 求解等价问题：两两等价元素作为一类，求解每类元素
• 集合归并
  • 生成迷宫：连通入口、出口连通分量

Map/Dictionary

映射/字典：能查找给定元素、增加新元素、删除元素的集合

• 需要处理的是动态内容的查找，因此需要在查找效率和其他两种 操作中达到平衡

• 数组、散列法、平衡查找树都可以实现字典

  ||散列表|平衡查找树| |——-|——-|———| |渐进时间效率|平均$\in \Theta(1)；最坏$\in \Theta(n)$|$\in \Theta(logn)| |有序性保留|不假定键有序，不保证，不适合按序遍历、按范围查询|保证|

应用

• Extendible Hashing：可扩充散列，用于存储磁盘上大型字典
  • 查找时先计算可能包含查找键K的存储段磁盘地址
  • 然后从磁盘中读取段中所有键，从中查找K
  • 因为存取主存开销较磁盘小很多，宁可多次存取主存