Μοντέλο δέντρου απόφασης

Στην υπολογιστική πολυπλοκότητα, το μοντέλο δέντρου απόφασης είναι το μοντέλο υπολογισμού στο οποίο ένας αλγόριθμος αντιμετωπίζεται ως ένα δέντρο αποφάσεων, δηλαδή μια ακολουθία ερωτημάτων ή δοκιμών που γίνονται προσαρμοστικά, οπότε το αποτέλεσμα των προηγούμενων δοκιμών / ελέγχων μπορεί να επηρεάσει τη δοκιμή που πρόκειται να εκτελεστεί στη συνέχεια.

Συνήθως, αυτές οι δοκιμές έχουν μικρό αριθμό αποτελεσμάτων (όπως μια ερώτηση ναι-όχι ) και μπορούν να εκτελεστούν γρήγορα (ας πούμε, με υπολογιστικό κόστος μονάδας), επομένως η χρονική πολυπλοκότητα στη χειρότερη περίπτωση ενός αλγορίθμου στο μοντέλο δέντρου αποφάσεων αντιστοιχεί στο βάθος του αντίστοιχου δέντρου αποφάσεων. Αυτή η έννοια της υπολογιστικής πολυπλοκότητας ενός προβλήματος ή ενός αλγορίθμου στο μοντέλο δέντρου αποφάσεων ονομάζεται πολυπλοκότητα του δέντρου αποφάσεων ή πολυπλοκότητα ερωτήματος (query complexity) .

Τα μοντέλα δέντρων αποφάσεων είναι καθοριστικά για τον καθορισμό κατώτερων ορίων για τη θεωρία πολυπλοκότητας για ορισμένες κατηγορίες υπολογιστικών προβλημάτων και αλγορίθμων. Πλέον υπάρχουν αρκετές παραλλαγές μοντέλων δέντρων αποφάσεων, ανάλογα με το υπολογιστικό μοντέλο και τον τύπο των αλγορίθμων ερωτημάτων που μπορούν να εκετλέσουν.

Δείτε επίσης

• Ταξινόμηση σύγκρισης
• Δέντρο απόφασης
• Εικασία Aanderaa–Karp–Rosenberg
• Ελάχιστο δέντρο κάλυψης#Δέντρα απόφασης