A neural sorting network with O(1) time complexity

Neural network models have been shown to be able to find ``good solutions for some optimization problems in a short time. But, it can not guarantee to find the real optimal solution except by technique similar to simulated annealing. Under such circumstance, we have no systematic way to determine the annealing schedule and have no easy way to predict the time needed for convergence. The basic operation of each neuron is the summation of weighted inputs, which takes \(O(1)\) time. That is, it can sum any number of real values in constant time. We show that sorting can be accomplished using only such operations. We present a neural network architecture to solve the sorting problem. A multi-layer feed forward neural network is proposed to solve sorting problems. The network has \(O(n^ 3)\) neurons and \(O(n^ 3)\) links. No matter what the input size is, the number of layers is fixed. Thus, the computation time of the network is independent of input size, and the sorting network has time complexity of \(O(1)\).

Recommendations

Cites work

Cited in

(7)

This page was built for publication: A neural sorting network with O(1) time complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2365819)