并行算法与Blob码的编码解码

### 并行算法与Blob码的编码解码 #### 1. EH算法复杂度分析 在一些算法流程中，涉及到对配置的处理和序列的应用，其时间复杂度的分析如下： - **查询步骤**：查询过程会返回相交对 ⟨bk, bl−1⟩，此步骤需 O(log n) 时间。 - **配置扩展**：若配置已满（无开放门），进行类型 2 的充分扩展。对配置中每个循环的每对黑边查询排列树，直到找到与某对相交的循环。由于最多有 24 对黑边，此步骤也需 O(log n) 时间。 - **序列应用**：使用排列树的转置过程应用 11/8 - 序列，需 O(log n) 时间。 以下是 EH 算法各步骤复杂度的相关引理： |引理编号|引理内容|证明依据| | ---- | ---- | ---- | |引理 10|EH 算法步骤 5 的 while 循环可在 O(n log n) 时间内实现|循环最多迭代 n 次，每次迭代根据引理 8 和 9 需 O(log n) 时间| |引理 11|EH 算法步骤 20 可在 O(n log n) 时间内实现|应用 11/8 - 序列每次需 O(log n) 时间，此步骤最多迭代 O(n) 次| |引理 12|EH 算法步骤 21 可在 O(n log n) 时间内实现|应用 (3,2) - 序列相当于应用 3 次转置，至少 2 次为 2 - 移动。每次转置最多需 O(log n) 时间，且最多有 n 个 3 - 循环| |引理 13|EH 算法步骤 22 可在 O(n log n) 时间内实现| - | 根据上述结果，可得定理：使用排列树实现的 EH 算法运行时间为 O(n log n)。 #### 2. 树编码与 Bijective 码介绍 - **标记 n - 树**：标记 n - 树是具有 n 个节点的无根树，每个节点有唯一标签，标签选自集合 [0, n - 1]。可通过节点标签字符串对其编码，这种数据结构在遗传算法、随机均匀分布树生成、故障字典存储和分布式生成树维护等实际应用中很有用。 - **简单编码方法**：将标记 n - 树 T 视为以固定节点（如节点 0）为根，将每个节点 x 与其父节点 p(x) 关联，得到字符串 C，其第 i 个元素为 p(i)。C 的长度为 n - 1，因为根节点无父节点可省略。但长度为 n - 1 的任意字符串不一定对应树，可能表示有环或不连通的图。 - **Bijective 码**：定义标记 n - 树集合与 [0, n - 1] 上字符串集合之间的双射。由于 Cayley 证明了 n ≥ 2 个节点的标记树数量为 n^(n - 2)，这种一一映射要求字符串长度为 n - 2。例如 Prüfer 码，递归删除树中标签最小的叶子节点，每次删除时将其父节点标签添加到码字中。多年来，还有许多类似 Prüfer 码的编码，以及基于不同思想的其他编码，如 ϑn 双射、Kreweras–Moszkowski 码、Chen 码、Blob 码等。 以下是一些已知 Bijective 码的并行算法成本对比： |编码类型|编码|解码| | ---- | ---- | ---- | |Prüfer - 类|Prüfer：O(n) EREW<br>2nd Neville：O(n√log n) EREW<br>3rd Neville：O(n) EREW<br>Stack - Queue：O(n√log n) EREW|Prüfer：O(n log n) EREW<br>2nd Neville：O(n√log n) EREW<br>3rd Neville：O(n√log n) EREW<br>Stack - Queue：O(n√log n) EREW| |Dandelion - 类|Dandelion：O(n) EREW<br>ϑn 双射：O(n) EREW<br>Happy：O(n) EREW<br>MHappy：O(n) EREW|Dandelion：O(n log n) CREW<br>ϑn 双射：O(n log n) CREW<br>Happy：O(n log n) CREW<br>MHappy：O(n log n) CREW| #### 3. Blob 码介绍 Blob 码由 Picciotto 在