Modelo de árbol de decisión

---

En complejidad computacional el modelo de árbol de decisión es el modelo de computación en el que un algoritmo se considera básicamente un árbol de decisión , es decir, una secuencia de consultas o pruebas que se realizan de forma adaptativa, por lo que el resultado de las pruebas anteriores puede influir en la prueba es realizado a continuación.

Por lo general, estas pruebas tienen una pequeña cantidad de resultados (como una pregunta de sí o no) y se pueden realizar rápidamente (por ejemplo, con un costo computacional unitario), por lo que la complejidad temporal de un algoritmo en el peor de los casos en el modelo de árbol de decisión corresponde a la profundidad del árbol de decisión correspondiente. Esta noción de complejidad computacional de un problema o un algoritmo en el modelo de árbol de decisión se denomina complejidad del árbol de decisión o complejidad de consulta .

Los modelos de árboles de decisión son fundamentales para establecer límites inferiores para la teoría de la complejidad para ciertas clases de problemas y algoritmos computacionales. Se han introducido varias variantes de modelos de árboles de decisión, según el modelo computacional y el tipo de algoritmos de consulta que se les permite realizar.

Por ejemplo, un argumento de árbol de decisión se usa para mostrar que un tipo de elementos de comparación debe aceptar comparaciones. Para las clasificaciones de comparación, una consulta es una comparación de dos elementos , con dos resultados (suponiendo que ningún elemento sea igual): o bien . Las clasificaciones de comparación se pueden expresar como un árbol de decisión en este modelo, ya que dichos algoritmos de clasificación solo realizan este tipo de consultas.${\ estilo de visualización n}$${\ estilo de visualización n \ registro (n)}$${\ estilo de visualización a, \, b}$${\displaystyle a<b}$${\displaystyle a>b}$

Los árboles de decisión a menudo se emplean para comprender los algoritmos de clasificación y otros problemas similares; esto fue hecho por primera vez por Ford y Johnson. ^[1]

Por ejemplo, muchos algoritmos de clasificación son clasificaciones de comparación , lo que significa que solo obtienen información sobre una secuencia de entrada a través de comparaciones locales: prueban si , o . Suponiendo que los elementos a clasificar son todos distintos y comparables, esto se puede reformular como una pregunta de sí o no: ¿es ?${\displaystyle x_{1},x_{2},\ldots ,x_{n}}$${\displaystyle x_{i}<x_{j}}$${\displaystyle x_{i}=x_{j}}$${\displaystyle x_{i}>x_{j}}$${\displaystyle x_{i}>x_{j}}$

---