Two entropies of a generalized sorting problem

✍ Scribed by Akihiro Nozaki

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 248 KB
• Volume: 7
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(73)80038-8

✦ Synopsis

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 -log, n although its informational entropy is constantly equal to 1, independent of the number of items n.