Γραμμική αναζήτηση
Γραμμική αναζήτηση (ή σειριακή αναζήτηση) ονομάζεται ένας αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο στοιχείο-κλειδί) σε μια δομή δεδομένων.[1][2] Ο αλγόριθμος χρησιμοποιεί τη μέθοδο της τυφλής αναζήτησης (brute-force), καθώς δεν επιλέγει με κάποια κριτήρια μια υπο-περιοχή αναζήτησης, αλλά στηρίζεται στο γεγονός ότι αν ελέγξει όλα τα στοιχεία της δομής δεδομένων ένα προς ένα, τότε αν υπάρχει το στοιχείο κλειδί στη δομή θα το βρει. Είναι ο πιο απλός αλγόριθμος αναζήτησης και ο λιγότερο αποδοτικός. Ωστόσο, είναι ο απαραίτητος, αν η δομή δεν είναι ταξινομημένη.
Αρχή λειτουργίας[Επεξεργασία | επεξεργασία κώδικα]
Σε αυτόν τον αλγόριθμο τα στοιχεία της δομής προσπελαύνονται το ένα μετά το άλλο μέχρι να βρεθεί το στοιχείο-κλειδί.
Αν αρκεί να βρεθεί μια φορά το στοιχείο-κλειδί, τότε ο αλγόριθμος μπορεί να σταματήσει όταν το βρει. Αν το στοιχείο-κλειδί δεν υπάρχει ή δε γνωρίζουμε πόσες φορές υπάρχει και θέλουμε να τα βρούμε όλα, τότε ο αλγόριθμος θα προσπελάσει αναγκαστικά όλα τα στοιχεία της δομής. Για αυτό η πολυπλοκότητά του είναι .[1]: Πρόταση 7.2
Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]
- ↑ 1,0 1,1 Τσίχλας, Κωνσταντίνος· Μανωλόπουλος, Ιωάννης· Γούναρης, Αναστάσιος (2015). Σχεδίαση και Ανάλυση Αλγορίθμων. ΣΕΑΒ. ISBN 978-960-603-465-7.
- ↑ Skiena, Steven S. (1998). The algorithm design manual. Santa Clara, CA: Springer. σελ. 441. ISBN 9780387948607.
 |
Αυτό το λήμμα σχετικά με έναν Αλγόριθμο χρειάζεται επέκταση. Μπορείτε να βοηθήσετε την Βικιπαίδεια επεκτείνοντάς το. |