Jump to content

Naïve algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Tomerfiliba (talk | contribs) at 11:47, 31 December 2006 (Created page with 'A naïve algorithm is a very simple solution to a problem, that has a very high time- or memory- complexity. It is meant...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

A naïve algorithm is a very simple solution to a problem, that has a very high time- or memory- complexity. It is meant to describe a suboptimal algorithm compared to a "clever" (non-naïve) algorithm, that consumes larger amounts of resources, but is simple to devise and implement.

An example of a naïve algorithm is bubble sort. This algorithm is only a few lines long and easy to understand, but has a Θ(n2) complexity. A more "clever" algorithm is quicksort, which, although being considerably more complicated than bubble sort, has a Θ(n log n) average complexity. Sorting a list of 100 items with bubble sort requires 10000 iterations, while sorting the same list with quicksort requires approximately 110 iterations, making quicksort a much faster algorithm than bubble sort.

As shown above, naïve algorithms are mostly used for prototyping purposes, as it is often not acceptable in production-level software products.