Two entropies of a generalized sorting problem

摘要

In this paper we introduce a class of generalized sorting (ordering) problems called “classifications.” To each “classification,” we associate two quantities: informational entropy (average information quantity) and operational entropy (measure of computational complexity, that is, number of comparisons necessary to “classify” a given sequence of items). The relationship between these quantities is discussed. For a certain classification involving n items, its operational entropy is shown to be approximately n·log2n although its informational entropy is constantly equal to 1, independent of the number of items n.