# Model 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).

## Referències

* ↑ «What is a Decision Tree | IBM» (en anglès americà). https://www.ibm.com.+[Consulta: 21 agost 2023].
* ↑ «1.10. Decision Trees» (en anglès). https://scikit-learn.+[Consulta: 21 agost 2023].
* ↑ Amer, Mustafa Adel. «Decision Tree Models using Python — Build, Visualize, Evaluate» (en anglès), 05-03-2022. [Consulta: 21 agost 2023].
* ↑ Ford, Lester R. Jr.; Johnson, Selmer M. The American Mathematical Monthly, 66, 5, 01-05-1959, pàg. 387–389. DOI: 10.1080/00029890.1959.11989306. ISSN: 0002-9890.