O que é um método ingênuo?

Eu estava pesquisando programação dinâmica e li o seguinte:

Muitas vezes, ao usar um método mais ingênuo, muitos dos subproblemas são gerados e resolvidos várias vezes.

O que é um método ingênuo?

Não é um termo técnico com um significado preciso, é apenas a palavra em inglês "ingênuo". No contexto da ciência da computação, a palavra geralmente significa algo como "uma das coisas em que você pensaria primeiro, mas sem perceber um fato menos óbvio, mas importante".

Por exemplo, se alguém souber que a definição de números de Fibonacci é $\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2)$, uma implementação "ingênua" seria

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

Qual é o problema? Que se chamam, por exemplo, Fib(7)e depois acabamos fazendo muitas das mesmas chamadas mais e mais, tais como Fib(4)(porque Fib(7)chamadas Fib(6)e Fib(5)e Fib(6)chamadas Fib(5)e Fib(4)e ambas as vezes chamamos Fib(5)chama Fib(4)e Fib(3), e assim por diante).

Portanto, aqui, uma solução mais sofisticada, em oposição à ingênua, seria como programação dinâmica e evitaria todos os cálculos extras.

Em geral, podemos resolver todos os problemas em NP a tempo$2^{\text{poly}(n)}$por força bruta , o que significa que enumeramos explicitamente todos os candidatos a uma testemunha NP, que possui polinômio de comprimento no tamanho da entrada$n$. Nesse contexto, o método de "verificar todas as soluções possíveis" pode ser considerado ingênuo.

A implementação ingênua é a solução em que parece mais direta e menos complicada possível.

Em alguns casos, pode não haver um bom comportamento no espaço ou no tempo, como a implementação ingênua da função Fibonacci (exponencial ao invés de linear).

Mas, em muitos casos, pode funcionar bem na maioria das vezes. Portanto, nada está errado com a abordagem ingênua, você pode fazer isso em três etapas:

"Faça funcionar" (conforme solicitado) -> "Faça elegante / bonito" (refatoração, mais legível) -> "Faça rápido" (otimização de desempenho)

Para linguagens de programação com tradições de "engenharia excessiva" como Java, eu recomendaria a "solução mais simples" a qualquer dia.