.
αγγλικά : Analysis of algorithms
γαλλικά : Analyse de la complexité des algorithmes
γερμανικά :
Στην επιστήμη των υπολογιστών, η ανάλυση των αλγορίθμων είναι η διαδικασία εύρεσης της υπολογιστικής πολυπλοκότητας των αλγορίθμων - του χρόνου, της αποθήκευσης ή άλλων πόρων που απαιτούνται για την εκτέλεσή τους. Συνήθως, αυτό περιλαμβάνει τον προσδιορισμό μιας συνάρτησης που συσχετίζει το μέγεθος της εισόδου ενός αλγορίθμου με τον αριθμό των βημάτων που κάνει (τη χρονική του πολυπλοκότητα) ή τον αριθμό των τοποθεσιών αποθήκευσης που χρησιμοποιεί (την πολυπλοκότητα του χώρου του). Ένας αλγόριθμος λέγεται ότι είναι αποτελεσματικός όταν οι τιμές αυτής της συνάρτησης είναι μικρές ή μεγαλώνουν αργά σε σύγκριση με την αύξηση του μεγέθους της εισόδου. Διαφορετικές είσοδοι του ίδιου μεγέθους μπορεί να προκαλέσουν διαφορετική συμπεριφορά στον αλγόριθμο, επομένως οι περιγραφές καλύτερης, χειρότερης και μέσης περίπτωσης μπορεί να έχουν πρακτικό ενδιαφέρον. Όταν δεν ορίζεται διαφορετικά, η συνάρτηση που περιγράφει την απόδοση ενός αλγορίθμου είναι συνήθως ένα άνω όριο, που καθορίζεται από τις εισόδους στη χειρότερη περίπτωση στον αλγόριθμο.
Ο όρος «ανάλυση αλγορίθμων» επινοήθηκε από τον Donald Knuth.[1] Η ανάλυση αλγορίθμων είναι ένα σημαντικό μέρος μιας ευρύτερης υπολογιστικής θεωρίας πολυπλοκότητας, η οποία παρέχει θεωρητικές εκτιμήσεις για τους πόρους που χρειάζονται οποιοσδήποτε αλγόριθμος που επιλύει ένα δεδομένο υπολογιστικό πρόβλημα. Αυτές οι εκτιμήσεις παρέχουν μια εικόνα για λογικές κατευθύνσεις αναζήτησης αποτελεσματικών αλγορίθμων.
Στη θεωρητική ανάλυση των αλγορίθμων είναι σύνηθες να εκτιμάται η πολυπλοκότητά τους με την ασυμπτωτική έννοια, δηλαδή να εκτιμάται η συνάρτηση πολυπλοκότητας για αυθαίρετα μεγάλες εισροές. Για το σκοπό αυτό χρησιμοποιούνται σημειογραφία Big O, Big-omega και Big-theta. Για παράδειγμα, η δυαδική αναζήτηση λέγεται ότι εκτελείται σε έναν αριθμό βημάτων ανάλογα με τον λογάριθμο του μεγέθους n της ταξινομημένης λίστας που αναζητείται, ή σε O(log n), καθομιλουμένη "σε λογαριθμικό χρόνο". Συνήθως χρησιμοποιούνται ασυμπτωτικές εκτιμήσεις επειδή διαφορετικές υλοποιήσεις του ίδιου αλγορίθμου μπορεί να διαφέρουν ως προς την αποτελεσματικότητα. Ωστόσο, οι αποδόσεις οποιωνδήποτε δύο «λογικών» υλοποιήσεων ενός δεδομένου αλγορίθμου σχετίζονται με έναν σταθερό πολλαπλασιαστικό παράγοντα που ονομάζεται κρυφή σταθερά.
Μερικές φορές μπορούν να υπολογιστούν ακριβή (όχι ασυμπτωτικά) μέτρα απόδοσης, αλλά συνήθως απαιτούν ορισμένες υποθέσεις σχετικά με τη συγκεκριμένη εφαρμογή του αλγορίθμου, που ονομάζεται μοντέλο υπολογισμού. Ένα μοντέλο υπολογισμού μπορεί να οριστεί με όρους ενός αφηρημένου υπολογιστή, π.χ. Μηχανή Turing ή/και με την υπόθεση ότι ορισμένες λειτουργίες εκτελούνται σε μονάδα χρόνου. Για παράδειγμα, εάν η ταξινομημένη λίστα στην οποία εφαρμόζουμε τη δυαδική αναζήτηση έχει n στοιχεία και μπορούμε να εγγυηθούμε ότι κάθε αναζήτηση ενός στοιχείου στη λίστα μπορεί να γίνει σε μονάδα χρόνου, τότε χρειάζονται το πολύ log2(n) + 1 μονάδες χρόνου για να επιστρέψει μια απάντηση.
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
