.
Στην επιστήμη των υπολογιστών, η υπολογιστική πολυπλοκότητα ή απλώς η πολυπλοκότητα ενός αλγορίθμου είναι η ποσότητα των πόρων που απαιτούνται για την εκτέλεσή του. Ιδιαίτερη έμφαση δίνεται στον υπολογιστικό χρόνο (γενικά μετρούμενο από τον αριθμό των απαραίτητων στοιχειωδών λειτουργιών) και στις απαιτήσεις αποθήκευσης μνήμης. Η πολυπλοκότητα ενός προβλήματος είναι η πολυπλοκότητα των καλύτερων αλγορίθμων που επιτρέπουν την επίλυση του προβλήματος.
Η μελέτη της πολυπλοκότητας ρητά δεδομένων αλγορίθμων ονομάζεται ανάλυση αλγορίθμων, ενώ η μελέτη της πολυπλοκότητας των προβλημάτων ονομάζεται θεωρία υπολογιστικής πολυπλοκότητας. Και οι δύο τομείς σχετίζονται σε μεγάλο βαθμό, καθώς η πολυπλοκότητα ενός αλγορίθμου είναι πάντα ένα ανώτερο όριο στην πολυπλοκότητα του προβλήματος που επιλύεται από αυτόν τον αλγόριθμο. Επιπλέον, για το σχεδιασμό αποτελεσματικών αλγορίθμων, είναι συχνά θεμελιώδες να συγκρίνουμε την πολυπλοκότητα ενός συγκεκριμένου αλγορίθμου με την πολυπλοκότητα του προβλήματος που πρέπει να λυθεί. Επίσης, στις περισσότερες περιπτώσεις, το μόνο που είναι γνωστό για την πολυπλοκότητα ενός προβλήματος είναι ότι είναι χαμηλότερη από την πολυπλοκότητα των πιο αποτελεσματικών γνωστών αλγορίθμων. Επομένως, υπάρχει μεγάλη επικάλυψη μεταξύ της ανάλυσης αλγορίθμων και της θεωρίας πολυπλοκότητας.
Καθώς η ποσότητα των πόρων που απαιτούνται για την εκτέλεση ενός αλγορίθμου ποικίλλει γενικά ανάλογα με το μέγεθος της εισόδου, η πολυπλοκότητα εκφράζεται συνήθως ως συνάρτηση n → f(n), όπου n είναι το μέγεθος της εισόδου και f(n) είναι είτε το πολυπλοκότητα στη χειρότερη περίπτωση (το μέγιστο της ποσότητας των πόρων που απαιτούνται για όλες τις εισροές μεγέθους n) ή η πολυπλοκότητα της μέσης περίπτωσης (ο μέσος όρος της ποσότητας πόρων σε όλες τις εισροές μεγέθους n). Η χρονική πολυπλοκότητα εκφράζεται γενικά ως ο αριθμός των απαιτούμενων στοιχειωδών πράξεων σε μια είσοδο μεγέθους n, όπου οι στοιχειώδεις λειτουργίες υποτίθεται ότι χρειάζονται σταθερό χρόνο σε έναν δεδομένο υπολογιστή και αλλάζουν μόνο κατά έναν σταθερό παράγοντα όταν εκτελούνται σε διαφορετικό υπολογιστή. Η πολυπλοκότητα του χώρου εκφράζεται γενικά ως η ποσότητα μνήμης που απαιτείται από έναν αλγόριθμο σε μια είσοδο μεγέθους n.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
