算法

简介 里德-所罗门编码是一种纠错码，被广泛使用在通信领域。主要原理是在传输数据的同时，也传输一定量的校验信息，当传输出现少量错误时，可以用这些信息恢复出原信息。 必要知识 群，环，域 参考相关资料，不作详述。 线性分组码 所谓分组，就是将$$m$$长度待传输串分成$$N$$个$$k$$长度的串（$$m \leq Nk$$），将每个$$k$$长度的串分进行编码，得到$$n$$长度编码后的串（$$n […]

双调排序是一种并行排序算法，如果以串行的方式运行，其复杂度为$$O(n\log^2n)$$，相对地，如果有$$n$$个可同时运行的线程，则复杂度为$$O(\log^2n)$$。 首先介绍双调序列。所谓单调序列，就是指一个递减或者递增序列，而双调，就是将两个长度相同，单调性相反的序列连接起来的序列，如果画成图形就是以下两种序列： 对于这样一个序列，可以设计一个输入和输出个数为$$2^k$$的排序网络 […]

Earth Mover’s Distance，推土机距离，简称EMD，用来表示两个分布的相似程度，在计算机中经常用到。下面以计算机中常见的离散分布举例。 在$$k$$维空间中，某个分布由向量集合给定：$$\{<x_{i1},x_{i2},…,x_{ik},w_i>|1 \leq i \leq n\}$$。其中$$<x_{i1},x_{i2},… […]