10
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Ever heard of "brute force"? $\endgroup$ – Raphael Dec 6 '14 at 8:59
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

In general, we can solve every problem in NP in time $2^{\text{poly}(n)}$ by brute force, meaning we explicitly enumerate all candidates for an NP-witness, which has length polynomial in the input size $n$. In this context, the method of "check every possible solution" can be considered naive.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Naive implementation is the solution where it looks straightforward and less tricky as possible.

In some cases, it may be not have good space or time behavior, like the naive implementation of the Fibonacci function (exponential rather than linear).

But in many cases, it can work well most of the time. So nothing is wrong with the naive approach, you can do it as 3 steps:

"Make it work" (as requested) -> "Make it elegant/beautiful" (refactoring, more readable) -> "Make it fast" (performance optimization)

For programming languages with traditions of "over-engineering" like Java, I would recommend "simplest solution" any day.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.