Model d'arbre de decisió

Exemple d'arbre de decisió.

En complexitat computacional, el model d'arbre de decisió és el model de càlcul en el qual un algorisme es considera bàsicament un arbre de decisió, és a dir, una seqüència de consultes o proves que es fan de manera adaptativa, de manera que el resultat de les proves anteriors pot influir en les proves realitzades a continuació.

Normalment, aquestes proves tenen un nombre reduït de resultats (com ara una pregunta sí-no) i es poden realitzar ràpidament (per exemple, amb un cost computacional unitari), de manera que la complexitat temporal en el pitjor dels casos d'un algorisme en el model d'arbre de decisions correspon a la profunditat de l'arbre de decisió corresponent. Aquesta noció de complexitat computacional d'un problema o algorisme en el model d'arbre de decisió s'anomena complexitat de l'arbre de decisió o complexitat de la consulta.

Els models d'arbres de decisió són fonamentals per establir límits inferiors per a la teoria de la complexitat per a determinades classes de problemes computacionals i algorismes. S'han introduït diverses variants dels models d'arbre de decisió, depenent del model computacional i del tipus d'algorismes de consulta que es permeten realitzar.

Per exemple, s'utilitza un argument d'arbre de decisions per mostrar que una comparació $n$ els elements han de prendre $n\log(n)$ comparacions. Per a classificacions de comparació, una consulta és una comparació de dos elements $a,\,b$, amb dos resultats (suposant que cap element sigui igual): tampoc $a<b$ o $a>b$. Les ordenacions de comparació es poden expressar com un arbre de decisió en aquest model, ja que aquests algorismes d'ordenació només realitzen aquest tipus de consultes.

Arbres de comparació i límits inferiors per ordenar

Sovint s'utilitzen arbres de decisió per entendre algorismes d'ordenació i altres problemes similars; això el van fer per primera vegada Ford i Johnson.

Per exemple, molts algorismes d'ordenació són ordenacions de comparació, el que significa que només obtenen informació sobre una seqüència d'entrada $x_{1},x_{2},\ldots ,x_{n}$ mitjançant comparacions locals: provant si $x_{i}<x_{j}$, $x_{i}=x_{j}$, o $x_{i}>x_{j}$ . Suposant que els elements a ordenar són tots diferents i comparables, això es pot reformular com una pregunta de sí o no: és $x_{i}>x_{j}$ ?

Aquests algorismes es poden modelar com a arbres de decisió binaris, on les consultes són comparacions: un node intern correspon a una consulta, i els fills del node corresponen a la següent consulta quan la resposta a la pregunta és sí o no. Per als nodes fulla, la sortida correspon a una permutació $\pi$ que descriu com es va codificar la seqüència d'entrada de la llista d'elements totalment ordenada. (La inversa d'aquesta permutació, $\pi ^{-1}$, reordena la seqüència d'entrada).