A low-cost neural sorting network with O(1) time complexity

Shun Shii Lin, Shen Hsuan Hsu

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

In this paper, we present an O(1) time neural network with O(n(1+ε)) neurons and links to sort n data, ε > O. For large-size problems, it is desirable to have low-cost hardware solutions. In order to solve the sorting problem in constant time and with less hardware-cost, we adopt Leighton's column sort [5] as the main architecture. Then we use Chen and Hsieh's neural network [3] with O(n3) complexity as the lowest-level sub-networks. By using recursive techniques properly, we are able to explore constant-time, low-complexity neural sorting networks.

Original languageEnglish
Pages (from-to)289-299
Number of pages11
JournalNeurocomputing
Volume14
Issue number3
DOIs
Publication statusPublished - 1997 Feb 28

Keywords

  • Complexity
  • Neural network
  • Parallel processing
  • Sorting

ASJC Scopus subject areas

  • Computer Science Applications
  • Cognitive Neuroscience
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A low-cost neural sorting network with O(1) time complexity'. Together they form a unique fingerprint.

  • Cite this