Observations on the Complexity of Generating Quasi-Gray Codes
Observations on the Complexity of Generating Quasi-Gray Codes
复制标题
对生成准格雷码复杂性的观察
DOI：
10.1137/0207012
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
M. Fredman
中科院分区：
文献类型：
--
作者：
M. Fredman
本文的目的是开发一种类似决策树的模型，用于定义和测量生成组合对象的算法的在线复杂性。为了便于说明，我们考虑生成格雷码以及格雷码的简单推广问题。我们包含了一些与某些特殊码的生成有关的结果，此外，我们还提出了一个权衡定理。我们的模型是信息论的，并且我们强调复杂性的两个方面：必须收集的信息量以及为生成给定码字的后继所需要的数据结构更新量。
The purpose of this paper is to develop a decision tree-like model for defining and measuring the on-line complexity of algorithms for generating combinatorial objects. For the purpose of illustration, we consider the problem of generating Gray codes and simple generalizations of Gray codes. We include some results pertaining to the generation of certain special codes and, in addition, we present a trade-off theorem. Our model is information theoretical and we emphasize two aspects of complexity; the amount of information that must be gathered and the amount of data structure update required to generate the successor to a given codeword.