Επεξηγούνται αλγόριθμοι γραμμικής & δυαδικής αναζήτησης

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

Οι αλγόριθμοι επιστρέφουν ένα boolean αποτέλεσμα (true ή false) σε ένα ερώτημα αναζήτησης. Μπορούν επίσης να τροποποιηθούν για να δώσουν τη σχετική θέση της τιμής που βρέθηκε.

Για αυτό το άρθρο, οι αλγόριθμοι θα επικεντρωθούν στον προσδιορισμό της ύπαρξης τιμής.

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

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

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

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

Ψευδής και θα αλλάξει σε Αληθής όταν βρεθεί η επιθυμητή τιμή.

Δείτε την εφαρμογή Python παρακάτω ως παράδειγμα:

def linearSearch (mylist, item):

βρέθηκε = Λάθος

δείκτης = 0

ενώ ευρετήριο

εάν η λίστα μου [index] == στοιχείο:

βρέθηκε = Αλήθεια

αλλού:

index = index+1

επιστροφή βρέθηκε

Ανάλυση αλγορίθμων

Το καλύτερο σενάριο εμφανίζεται όταν το επιθυμητό στοιχείο είναι το πρώτο στη λίστα. Η χειρότερη περίπτωση συμβαίνει όταν το επιθυμητό στοιχείο είναι το τελευταίο στη λίστα (το ένατο στοιχείο). Επομένως, η χρονική πολυπλοκότητα για γραμμική αναζήτηση είναι O (n).

Το μέσο σενάριο περίπτωσης στον παραπάνω αλγόριθμο είναι n/2.

Σχετίζεται με: Τι είναι το Big-O Notation;

Τροποποιημένη Γραμμική Αναζήτηση

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

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

Πάρτε ένα παράδειγμα αναζήτησης 19 στη δεδομένη λίστα: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Αφού φτάσει τα 23, θα καταστεί σαφές ότι το αντικείμενο που αναζητείται δεν υπάρχει στη λίστα. Επομένως, δεν θα είναι πλέον σημαντικό να συνεχίσετε την αναζήτηση στα υπόλοιπα στοιχεία της λίστας.

Αλγόριθμοι δυαδικής αναζήτησης

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

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

Εάν είναι λιγότερο, τότε δεν χρειάζεται να ελέγξετε το κάτω μισό της λίστας. Διαφορετικά, εάν είναι μεγαλύτερο, τότε προχωρά στο επάνω μισό της λίστας.

Σχετίζεται με: Τι είναι το Recursion και πώς το χρησιμοποιείτε;

Ανεξάρτητα από την επιλεγμένη δευτερεύουσα λίστα (αριστερά ή δεξιά), η μεσαία τιμή θα καθοριστεί ξανά. Η τιμή ελέγχεται ξανά εάν είναι η απαιτούμενη τιμή. Εάν δεν είναι, ελέγχεται αν είναι μικρότερη ή μεγαλύτερη από την ζητούμενη τιμή.

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

Η παρακάτω εφαρμογή Python αφορά τον δυαδικό αλγόριθμο αναζήτησης.

def binarySearch (λίστα μου, στοιχείο):

χαμηλό = 0

high = len (mylist) - 1

βρέθηκε = Λάθος

ενώ χαμηλή <= υψηλή και δεν βρέθηκε:

μέση = (χαμηλή + υψηλή) // 2

εάν η λίστα μου [mid] == στοιχείο:

βρέθηκε = Αλήθεια

elif item

υψηλή = μέση - 1

αλλού:

χαμηλή = μέση + 1

επιστροφή βρέθηκε

Ανάλυση αλγορίθμων

Το καλύτερο σενάριο εμφανίζεται όταν το επιθυμητό στοιχείο διαπιστωθεί ότι είναι το μεσαίο στοιχείο. Το χειρότερο σενάριο δεν είναι όμως τόσο απλό. Ακολουθήστε την παρακάτω ανάλυση:

Μετά την πρώτη σύγκριση, θα μείνουν n/2 στοιχεία. Μετά το δεύτερο, θα μείνουν n/4 στοιχεία. Μετά το τρίτο, n/8.

Παρατηρήστε ότι ο αριθμός των στοιχείων συνεχίζει να μειώνεται στο μισό μέχρι να φτάσουν στο n/2i όπου i είναι ο αριθμός των συγκρίσεων. Μετά από όλα τα χωρίσματα, καταλήγουμε μόνο με 1 στοιχείο.

Αυτό υπονοεί:

n/2i = 1

Επομένως, η δυαδική αναζήτηση είναι O (log n).

Προχωράμε στην ταξινόμηση

Στην δυαδική αναζήτηση, εξετάσαμε μια περίπτωση όπου ο συγκεκριμένος πίνακας είχε ήδη παραγγελθεί. Αλλά ας υποθέσουμε ότι είχατε ένα μη ταξινομημένο σύνολο δεδομένων και θέλετε να εκτελέσετε δυαδική αναζήτηση σε αυτό. Τι θα έκανες?

Η απάντηση είναι απλή: ταξινομήστε το. Υπάρχουν πολλές τεχνικές ταξινόμησης στην επιστήμη των υπολογιστών που έχουν ερευνηθεί καλά. Μία από αυτές τις τεχνικές που μπορείτε να αρχίσετε να μελετάτε είναι ο αλγόριθμος ταξινόμησης επιλογής, ενώ έχουμε πολλούς οδηγούς που σχετίζονται και με άλλους τομείς.

Πώς να χρησιμοποιήσετε την ταξινόμηση επιλογής

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

Διαβάστε Επόμενο

Σχετικά με τον Συγγραφέα