Κλάσεις πολυπλοκότητας χρόνου: ασυμπτωματική ανάλυση

Abstract

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