Qu'est-ce qu'une méthode naïve?

Je recherchais une programmation dynamique et j'ai lu ce qui suit:

Souvent, lorsque vous utilisez une méthode plus naïve, de nombreux sous-problèmes sont générés et résolus plusieurs fois.

Qu'est-ce qu'une méthode naïve?

Ce n'est pas un terme technique avec une signification précise, c'est juste le mot anglais "naive". Dans un contexte informatique, le mot signifie généralement quelque chose comme "l'une des choses auxquelles vous pensez en premier, mais sans réaliser un fait moins évident mais important".

Par exemple, si l'on sait que la définition des nombres de Fibonacci est , alors une implémentation "naïve" serait être$\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2)$

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

Quel est le problème? Que si nous appelons, disons, Fib(7)nous finissons par faire plusieurs fois les mêmes appels, comme Fib(4)(parce que les Fib(7)appels Fib(6)et Fib(5), et les Fib(6)appels Fib(5)et Fib(4), et les deux fois nous l'appelons Fib(5)appels Fib(4)et Fib(3), et ainsi de suite).

Voici donc une solution plus "sophistiquée", par opposition à naïve, qui serait comme une programmation dynamique et éviterait tous les extras de calculs.

En général, nous pouvons résoudre tous les problèmes de NP dans le temps par force brute , ce qui signifie que nous énumérons explicitement tous les candidats pour un témoin NP, qui a un polynôme de longueur dans la taille d'entrée . Dans ce contexte, la méthode de «vérifier toutes les solutions possibles» peut être considérée comme naïve.$2^{\text{poly}(n)}$$n$

L'implémentation naïve est la solution où elle semble simple et moins compliquée que possible.

Dans certains cas, il peut ne pas avoir un bon comportement d'espace ou de temps, comme l'implémentation naïve de la fonction de Fibonacci (exponentielle plutôt que linéaire).

Mais dans de nombreux cas, cela peut bien fonctionner la plupart du temps. Donc, rien de mal à l'approche naïve, vous pouvez le faire en 3 étapes:

"Make it work" (comme demandé) -> "Make it elegant / beautiful" (refactoring, plus lisible) -> "Make it fast" (optimisation des performances)

Pour les langages de programmation avec des traditions de «suringénierie» comme Java, je recommanderais «la solution la plus simple» tous les jours.