Modelo de árvore de decisão

Modelo de árvore de decisão é um modelo de computação em que um algoritmo é considerado uma árvore de decisão, isto é, uma sequência de operações que ramificam a execução baseadas em comparações de dados. Assume-se que cada comparação possui um custo unitário de computação. Diversas variações desse modelo podem ser consideradas, dependendo da complexidade das operações permitidas.

Esse modelo é usado em provas dos limites mínimos de complexidade em problemas algorítmicos, para certas classes de problemas. O limite mínimo do pior caso em complexidade de certo problema é proporcional a maior profundidade da árvore de decisão, para qualquer entrada possível do problema.

Uma variação do modelo são as árvores de decisão simples, em que cada decisão é baseada na comparação de dois números num tempo constante. Ela foi introduzida para a definição de complexidade computacional de algoritmos de ordenação e de busca.

Ver também

• Árvore de decisão
• Modelo de computação
• Máquina abstrata