What is a naive method?

Problem Detail: 

I was researching dynamic programming and read the following:

Often when using a more naive method, many of the subproblems are generated and solved many times.

What is a naive method?

Asked By : chopper draw lion4

Answered By : usul

It's not a technical term with a precise meaning, it is just the English word "naive". In a computer science context, the word usually means something like "one of the things you would think of first, but without realizing a less obvious but important fact".

For instance, if one knows the definition of Fibonacci numbers is $\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2)$, then a "naive" implementation would be

def Fib(n):   if n <= 1:     return 1   else:     return Fib(n-1) + Fib(n-2) 

What's the problem? That if we call, say, Fib(7), then we end up making many of the same calls over and over, such as Fib(4) (because Fib(7) calls Fib(6) and Fib(5), and Fib(6) calls Fib(5) and Fib(4), and both times we call Fib(5) it calls Fib(4) and Fib(3), and so on).

So here a more a more "sophisticated", as opposed to naive, solution would be like dynamic programming and avoid all the extras computations.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33914