Modelo de árvore de decisão

Em complexidade computacional e complexidade de comunicação o modelo de árvore de decisão é o modelo de computação ou comunicação no qual um algoritmo ou processo de comunicação é considerado basicamente uma árvore de decisão, ou seja, uma sequência de operações ramificadas baseadas em comparações de quantidades, sendo as comparações atribuidas uma unidade de custo computacional. As operações ramificadas são chamadas de "testes" ou "pedidos". Nesta configuração, o algoritmo em questão pode ser visto como uma computação de uma onde a entrada é uma série de pedidos e a saída é uma decisão final. Cada pedido é dependente de pedidos anteriores. Várias variações de modelos de árvores de decisão podem ser utilizados dependendo da complexidade das operações permitidas na computação de uma única comparação e também pelo modelo de ramificação. Modelos de árvore de decisão são instrumentos de estabelecimento do limite inferior para a complexidade computacional de certas classes de problemas computacionais e algoritmos: o limite inferior para análise de pior caso é proporcional a maior profundidade das árvores de decisão para todas as entradas possíveis de um certo problema computacional. A complexidade computacional de um problema ou um algoritmo em termos da árvore de decisão é chamado de complexidade da árvore de decisão ou complexidade do pedido'.