What is a "naive" algorithm, and what is a "closed - form" solution?

I have a few开发者_JS百科 questions regarding the semantics of terminology used when describing algorithms.

Firstly, what is meant by a 'naive' algorithm? How does this differ from other solutions to a given problem? What other forms can solutions take?

Secondly, I have heard much reference to having a 'closed - form' solution. I have no idea what this means either - but often it appears when trying to solve recurrence relations...

Thanks for your time

A Naive algorithm is usually the most obvious solution when one is asked a problem. It may not be a smart algorithm but will probably get the job done (...eventually.)

Eg. Trying to search for an element in a sorted array. A Naive algorithm would be to use a Linear Search. A Not-So Naive Solution would be to use the Binary Search.

A better example, would be in case of substring search Naive Algorithm is far less efficient than Boyer–Moore or Knuth–Morris–Pratt Algorithm

A Closed Form Solution is a simple Solution that works instantly without any loops,functions etc..

Eg: Iterative Algorithm for sum of integer from 1 to n

s= 0
for i in 1 to n
s = s + i
end for
print s

Closed Form (for the same problem)

s = n * (n + 1 ) /2

Naive algorithm is a very simple algorithm, one with very simple rules. Sometimes the first one that comes to mind. It may be stupid and very slow, it may not even solve the problem. It may sometimes be the best possible. Here's an example of a problem and "naive" algorithms:

Problem: You are in a (2-dimensional) maze. Find your way out. (meaning: to a spot with an "EXIT" sign :)

Naive algorithm 1: Start walking and choose the right one in every intersection you meet (until you find "EXIT").

Naive algorithm 2: Start walking and choose a random one in every intersection you meet (until you find "EXIT").

Algorithm 1 will not even get you out of some mazes!

Algorithm 2 will get you out of all mazes (although this is rather hard to prove).

Closed form means you can give the one expression as solution, that does solve it without recurrence/recursive. Here one should remark, that it is not always possible to find such a closed form.

Naive means just that what it says: A first, stupid solution to the problem, that solves it, but maybe not very time-/space efficient. What one really considers 'naive' depends on the speaker, the context, and the weather of the next day. Often it is used to distinguish a very sophisticated solution (that uses some kind of trick) from the obvious implementation.