Θεωρία πολυπλοκότητας: Διαφορά μεταξύ των αναθεωρήσεων

Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Addbot (συζήτηση | συνεισφορές)
μ Ρομπότ: Μεταφέρω 34 σύνδεσμους interwiki, που τώρα παρέχονται από τα Wikidata στο d:q205084
Γραμμή 1:
Η '''θεωρία πολυπλοκότητας''' είναι το μέρος εκείνο της [[Θεωρία υπολογισμού|θεωρίας υπολογισμού]], το οποίο ασχολείται με την κοστολόγηση των πόρων που απαιτούνται για την [[αλγόριθμος|αλγοριθμική]] επίλυση ενός προβλήματος. Επομένως η θεωρία πολυπλοκότητας αποτελεί βασικό δομικό λίθο της [[Ανάλυση αλγορίθμων|ανάλυσης αλγορίθμων]] και κεντρικό γνωστικό πεδίο της [[επιστήμη υπολογιστών|επιστήμης υπολογιστών]].
 
Οι συνηθέστεροι πόροι για τους οποίους ενδιαφερόμαστε είναι ο ''χρόνος'', οπότε μιλάμε για τη χρονική πολυπλοκότητα του αλγορίθμου, δηλαδή πόσα «βήματα» χρειάζεται να εκτελέσει ο αλγόριθμος συναρτήσει της [[είσοδος|εισόδου]] του, και ο ''χώρος'', οπότε μιλάμε για τη χωρική πολυπλοκότητα, δηλαδή πόσο χώρο ([[μνήμη υπολογιστή|μνήμη]]) χρειάζεται ο αλγόριθμος συναρτήσει της εισόδου του. Εκτός από αυτούς τους πόρους, κατά περίπτωση, μπορεί να ενδιαφερόμαστε και για άλλους, όπως για παράδειγμα πόσοι [[παράλληλα και κατανεμημένα συστήματα|παράλληλοι επεξεργαστές]] χρειάζονται για να λυθεί ένα πρόβλημα παράλληλα. H Ζήνα δεν χρειάζεται να λύσει το πρόβλημα, γιατί δεν λύνεται.
 
== Επισκόπηση ==