Department of Computer Science, Memorial University of Newfoundland, St. John's, Nfld., Canada A1C 5S7.
IEEE Trans Pattern Anal Mach Intell. 1984 Jan;6(1):69-73. doi: 10.1109/tpami.1984.4767476.
Day [3] describes an analytical model of minimum-length sequence (MLS) metrics measuring distances between partitions of a set. By selecting suitable values of model coordinates, a user may identify within the model that metric most appropriate to his classification application. Users should understand that within the model similar metrics may nevertheless exhibit extreme differences in their computational complexities. For example, the asymptotic time complexities of two MLS metrics are known to be linear in the number of objects being partitioned; yet we establish below that the computational problem for a closely related MLS metric is NP-complete.
第 3 天描述了一个最小长度序列（MLS）度量的分析模型，用于测量集合划分之间的距离。通过选择合适的模型坐标值，用户可以在模型中确定最适合他的分类应用的度量。用户应该明白，在模型中，相似的度量在计算复杂度上可能存在极端差异。例如，两个 MLS 度量的渐近时间复杂度已知是被划分对象数量的线性函数；然而，我们在下面证明了一个密切相关的 MLS 度量的计算问题是 NP 完全的。
