Para calcular la eficiencia de cualquier algoritmo de programación dinámica, primero debe determinar la cantidad de subproblemas que tiene y el tiempo que lleva resolver cada subproblema y este cálculo conduce directamente al tiempo de ejecución del algoritmo DP.
Considere los algoritmos DP clásicos para encontrar la subsecuencia creciente más larga. El pseudocódigo para este algoritmo se ve así:
para i = 1, 2, 3, … n:
L (j) = 1 + max {L (i): (i, j) ∈ E}
volver max_j L (j)
- Cómo detectar imágenes en un documento de Word escaneado
- ¿Es posible encontrar la distancia del vértice más alejada del vértice inicial mediante la solución iterativa de DFS para un árbol (NO un gráfico genérico)?
- Entrevista Street puzzle: ¿Pregunta de hormigas en la sección de matemáticas?
- ¿Se puede resolver un cubo de Rubik sin sus algoritmos?
- ¿El conocimiento de algoritmos codiciosos a veces influye en la forma de tomar decisiones?
Para aclarar, imponer la restricción [math] (i, j) \ en E [/ math] solo significa que el elemento [math] j ^ {th} [/ math] debe ser mayor que el [math] i ^ {th } [/ math] elemento. Entonces, en este ejemplo hay subproblemas [matemática] n [/ matemática] y cada subproblema toma [matemática] O (n) [/ matemática] tiempo para resolver en el peor de los casos. Por lo tanto, el tiempo total de ejecución de esta función es [matemática] O (n ^ 2) [/ matemática].
