Naïve algorithm


Naïve algorithm

A naïve algorithm is typically a very simple solution to a problem, which represents the intuitive approach taken by one unfamiliar with the problem domain. It is meant to describe a suboptimal algorithm compared to a "clever" (but less simple) algorithm. Naïve algorithms usually consume larger amounts of resources (time, space, memory accesses, ...), but are simple to devise and implement.

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

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

Another sense of the term implies an algorithm which may have certain bugs, or fail to account for corner cases; for instance, the naïve implementations of various operations on linked lists and binary trees either leak memory or corrupt data based on incorrect pointer arithmetic.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Naive (disambiguation) — Naive or Naïve indicates having or showing a lack of experience, understanding or sophistication. Naive or Naïve may also refer to: Naïve (album), a 1990 album by KMFDM Naïve (song), a 2006 song by The Kooks Naïve Records, a French record label… …   Wikipedia

  • Naïve — may refer to:*a French loanword (adjective, form of naïf ) indicating having or showing a lack of experience, understanding or sophistication*Naïve art, art created by untrained artists, or artists aspiring to naïve realisations *Naïve realism, a …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Schönhage-Strassen algorithm — The Schönhage Strassen algorithm is an asymptotically fast multiplication algorithm for large integers. It was developed by Arnold Schönhage and Volker Strassen in 1971. [A. Schönhage and V. Strassen, Schnelle Multiplikation großer Zahlen ,… …   Wikipedia

  • Freivald's algorithm — is a randomized algorithm used to verify matrix multiplication. Given three n x n matrices A , B , and C , a general problem is to verify whether A x B = C . A naïve algorithm would compute the product A x B explicitly and compare term by term… …   Wikipedia

  • Kahan summation algorithm — In numerical analysis, the Kahan summation algorithm (also known as compensated summation) significantly reduces the numerical error in the total obtained by adding a sequence of finite precision floating point numbers, compared to the obvious… …   Wikipedia

  • Rete algorithm — The Rete algorithm is an efficient pattern matching algorithm for implementing production rule systems. The Rete algorithm was designed by Dr Charles L. Forgy of Carnegie Mellon University, first published in a working paper in 1974, and later… …   Wikipedia

  • String searching algorithm — String searching algorithms, sometimes called string matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. Let Σ be… …   Wikipedia

  • XOR swap algorithm — In computer programming, the XOR swap is an algorithm that uses the XOR bitwise operation to swap distinct values of variables having the same data type without using a temporary variable.The algorithmStandard swapping algorithms require the use… …   Wikipedia

  • Rabin-Karp string search algorithm — The Rabin Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find a substring in a text. It is used for multiple pattern matching rather than single pattern matching. For… …   Wikipedia