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

Στην παράγραφο 3.6 μελετήσαμε την απλούστερη μέθοδο αναζήτησης, τη γραμμική ή σειριακή μέθοδο. Όταν αναζητούμε ένα κλειδί που πράγματι υπάρχει στον πίνακα, τότε λέμε ότι η αναζήτηση είναι επιτυχής (successful). Στην αντίθετη περίπτωση, λέμε ότι η αναζήτηση είναι ανεπιτυχής (unsuccessful). Το κόστος της αναζήτησης μετράται με τον αριθμό των συγκρίσεων κλειδιών. Έτσι το κόστος αυτό για την επιτυχή αναζήτηση συμβολίζεται με Ε, ενώ για την ανεπιτυχή αναζήτηση συμβολίζεται με Α.

Ας εξετάσουμε αρχικά, πως προκύπτει η πολυπλοκότητα της επιτυχούς αναζήτησης σε μη ταξινομημένο πίνακα που αποτελείται από n στοιχεία. Αν αναζητάται το πρώτο στοιχείο, τότε η επιτυχής αναζήτηση θα κοστίσει μία σύγκριση, ενώ αν αναζητάται το δεύτερο στοιχείο, τότε το κόστος είναι δύο συγκρίσεις. Με την ίδια λογική, αν αναζητάται το n-οστό στοιχείο, τότε θα εκτελεσθούν n συγκρίσεις κλειδιών μέχρι την περάτωση του αλγορίθμου. Έτσι κατά μέσο όρο, ο απαιτούμενος αριθμός συγκρίσεων κλειδιών για την επιτυχή αναζήτηση είναι: [pic]

Από τη σχέση αυτή, εύκολα καταλήγουμε στο συμπέρασμα ότι η επιτυχής αναζήτηση έχει πολυπλοκότητα της τάξης Ο(n), με την απαραίτητη προϋπόθεση ότι τα κλειδιά αναζητώνται ισοπίθανα. Η πολυπλοκότητα της ανεπιτυχούς αναζήτησης είναι επίσης τάξης Ο(n). Αυτό προκύπτει με βάση την απλή σκέψη ότι, όταν το αναζητούμενο κλειδί δεν υπάρχει στον πίνακα, τότε η αναζήτηση καταλήγει να εξετάσει ένα προς ένα όλα τα κλειδιά μέχρι το τέλος του πίνακα. Αν ο πίνακας είναι ταξινομημένος, τότε η διαδικασία της επιτυχούς και της ανεπιτυχούς αναζήτησης μπορεί να βελτιωθεί, ωστόσο και πάλι η πολυπλοκότητα θα είναι γραμμικής τάξης.

Πιν. 5.4. Πολυπλοκότητες μερικών αλγορίθμων Αλγόριθμος Πολυπλοκότητα Ώθηση-απώθηση σε στοίβα Ο(1) Εισαγωγή-εξαγωγή σε ουρά Ο(1) Fibonacci επαναληπτική Ο(n) Ταξινόμηση ευθείας ανταλλαγής O[pic] Σειριακή αναζήτηση O(n) Δυαδική αναζήτηση O(logn)