Complexity - online παζλ

Θεωρία της υπολογιστικής πολυπλοκότητας - ένα τμήμα της θεωρίας υπολογισμού του οποίου ο κύριος σκοπός είναι να προσδιορίσει το ποσό των πόρων που απαιτούνται για την επίλυση υπολογιστικών προβλημάτων. Οι πόροι που λαμβάνονται υπόψη είναι τιμές όπως χρόνος, μνήμη ή αριθμός επεξεργαστών.

Οι Juris Hartmanis και Richard Stearns θεωρούνται οι δημιουργοί αυτής της θεωρίας. Ως παραδείγματα του t.z.o. Μπορείτε να καθορίσετε το πρόβλημα συμμόρφωσης, το πρόβλημα της συντομότερης διαδρομής, το πρόβλημα παραγοντοποίησης και πολλά άλλα που είναι γνωστό ότι είναι υπολογιστικά. Η θεωρία υπολογιστικότητας, η οποία είναι ο δεύτερος σημαντικός κλάδος της θεωρίας υπολογισμού, ασχολείται με το ζήτημα της υπολογιστικότητας.

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

Πολυπλοκότητα αλγορίθμων

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