Γραμμική αναζήτηση

Γραμμική αναζήτηση (ή σειριακή αναζήτηση) ονομάζεται ένας αλγόριθμος αναζήτησης ενός στοιχείου (το λεγόμενο στοιχείο-κλειδί) σε μια δομή δεδομένων. Ο αλγόριθμος χρησιμοποιεί τη μέθοδο της τυφλής αναζήτησης (brute-force), καθώς δεν επιλέγει με κάποια κριτήρια μια υπο-περιοχή αναζήτησης, αλλά στηρίζεται στο γεγονός ότι αν ελέγξει όλα τα στοιχεία της δομής δεδομένων ένα προς ένα, τότε αν υπάρχει το στοιχείο κλειδί στη δομή θα το βρει. Είναι ο πιο απλός αλγόριθμος αναζήτησης και ο λιγότερο αποδοτικός. Ωστόσο, είναι ο απαραίτητος, αν η δομή δεν είναι ταξινομημένη.

Αρχή λειτουργίας

Σε αυτόν τον αλγόριθμο τα στοιχεία της δομής προσπελαύνονται το ένα μετά το άλλο μέχρι να βρεθεί το στοιχείο-κλειδί.

Αν αρκεί να βρεθεί μια φορά το στοιχείο-κλειδί, τότε ο αλγόριθμος μπορεί να σταματήσει όταν το βρει. Αν το στοιχείο-κλειδί δεν υπάρχει ή δε γνωρίζουμε πόσες φορές υπάρχει και θέλουμε να τα βρούμε όλα, τότε ο αλγόριθμος θα προσπελάσει αναγκαστικά όλα τα στοιχεία της δομής. Για αυτό η πολυπλοκότητά του είναι .

 Παραπομπές 

Κατηγορία:Αλγόριθμοι αναζήτησης