Θεωρία Πολυπλοκότητας
Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Η Θεωρία Πολυπλοκότητας είναι το μέρος εκείνο της Θεωρίας Υπολογισμού, το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την αλγοριθμική επίλυση ενός προβλήματος.
Οι συνηθέστεροι πόροι για τους οποίους ενδιαφερόμαστε είναι ο χρόνος, οπότε μιλάμε για τη χρονική πλοκή του αλγορίθμου, δηλαδή πόσα βήματα χρειάζεται ο αλγόριθμος, και ο χώρος, οπότε μιλάμε για τη χωρική πλοκή, δηλαδή πόσο χώρο (μνήμη) χρειάζεται ο αλγόριθμος. Εκτός από αυτούς τους πόρους, κατά περίπτωση, μπορεί να ενδιαφερόμαστε και για άλλους, όπως για παράδειγμα πόσοι παράλληλοι επεξεργαστές χρειάζονται για να λυθεί ένα πρόβλημα παράλληλα.
Πίνακας περιεχομένων |
[Επεξεργασία] Γενικά
[Επεξεργασία] Προβλήματα και Αλγόριθμοι
[Επεξεργασία] Συμβολισμός
[Επεξεργασία] Κλάσεις πολυπλοκότητας
[Επεξεργασία] Το ζήτημα P=NP
