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

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

Η γραμμική αναζήτηση ελέγχει κάθε στοιχείο του καταλόγου διαδοχικά μέχρι να βρει τον στόχο ή να φτάσει στο τέλος. Ο αναμενόμενος αριθμός συγκρίσεων εξαρτάται από το αν ο στόχος είναι παρών και η θέση του στον κατάλογο.

Εάν ο κατάλογος περιέχει στοιχεία n και ο στόχος είναι εξίσου πιθανό να βρίσκεται σε οποιαδήποτε θέση, ο αναμενόμενος αριθμός συγκρίσεων είναι:

Αναμενόμενες συγκρίσεις = (n + 1) / 2

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

Δυαδική αναζήτηση

Δυαδική αναζήτηση λειτουργεί σε ταξινομημένες λίστες με την επαναλαμβανόμενη διαίρεση του διαστήματος αναζήτησης στο μισό. Η αποτελεσματικότητά του εξαρτάται από το μέγεθος της λίστας και τη θέση του στόχου.

Στην καλύτερη περίπτωση, ο στόχος βρίσκεται στο μέσο, απαιτώντας μόνο μία σύγκριση. Στη χειρότερη περίπτωση, χρειάζεται περίπου log2 n συγκρίσεις.

Αν υποθέσουμε ότι ο στόχος είναι εξίσου πιθανό να βρίσκεται σε οποιαδήποτε θέση, ο αναμενόμενος αριθμός συγκρίσεων είναι περίπου:

Αναμενόμενες συγκρίσεις ⁇ log2 n

Περίληψη Σύγκρισης

  • Η γραμμική αναζήτηση έχει αναμενόμενο αριθμό σύγκρισης (n + 1) / 2.
  • Η δυαδική αναζήτηση έχει αναμενόμενο αριθμό σύγκρισης περίπου log2 n.
  • Η δυαδική αναζήτηση απαιτεί γενικά λιγότερες συγκρίσεις για μεγάλες λίστες.
  • Η γραμμική αναζήτηση μπορεί να είναι προτιμότερη για μικρές ή μη ταξινομημένες λίστες.