Διαφορά μεταξύ γραμμικής αναζήτησης και δυαδικής αναζήτησης
Περιεχόμενο
Γραμμική αναζήτηση και δυαδική αναζήτηση είναι οι δύο μέθοδοι που χρησιμοποιούνται σε συστοιχίες για ερευνητικός τα στοιχεία. Η αναζήτηση είναι μια διαδικασία εύρεσης ενός στοιχείου μέσα στη λίστα στοιχείων που αποθηκεύονται με οποιαδήποτε σειρά ή τυχαία.
Η κύρια διαφορά μεταξύ της γραμμικής αναζήτησης και της δυαδικής αναζήτησης είναι ότι η δυαδική αναζήτηση διαρκεί λιγότερο χρόνο για την αναζήτηση ενός στοιχείου από την ταξινομημένη λίστα στοιχείων. Επομένως, συνάγεται ότι η αποτελεσματικότητα της δυαδικής μεθόδου αναζήτησης είναι μεγαλύτερη από την γραμμική αναζήτηση.
Μια άλλη διαφορά μεταξύ των δύο είναι ότι υπάρχει προϋπόθεση για τη δυαδική αναζήτηση, δηλ. Τα στοιχεία πρέπει να είναι ταξινομημένο ενώ σε γραμμική αναζήτηση δεν υπάρχει τέτοια προϋπόθεση. Παρόλο που και οι δύο μέθοδοι αναζήτησης χρησιμοποιούν διαφορετικές τεχνικές που συζητούνται παρακάτω.
- Συγκριτικό διάγραμμα
- Ορισμός
- Βασικές διαφορές
- συμπέρασμα
Συγκριτικό διάγραμμα
Βάση σύγκρισης | Γραμμική αναζήτηση | Δυαδική αναζήτηση |
---|---|---|
Χρόνος Πολυπλοκότητα | ΕΠΙ) | Ο (log 2 Ν) |
Η καλύτερη περίπτωση | Πρώτο Στοιχείο O (1) | Κέντρο Στοιχείου O (1) |
Προϋπόθεση για έναν πίνακα | Δεν απαιτείται | Η σειρά πρέπει να είναι ταξινομημένη |
Χειρότερη περίπτωση για τον αριθμό N στοιχείων | Οι συγκρίσεις N απαιτούνται | Μπορεί να ολοκληρωθεί μετά από μόνο καταγραφή2 N συγκρίσεις |
Μπορεί να εφαρμοστεί την | Λίστα πίνακα και συνδεδεμένη | Δεν είναι δυνατή η απευθείας εφαρμογή σε συνδεδεμένη λίστα |
Εισαγωγή λειτουργίας | Εισάγεται εύκολα στο τέλος της λίστας | Απαίτηση επεξεργασίας για να εισαγάγετε στη σωστή θέση για να διατηρήσετε μια λίστα ταξινομημένων. |
Αλγόριθμος τύπου | Επαναληπτική στη φύση | Διαχωρίστε και κατακτήστε τη φύση |
Χρησιμότητα | Εύκολο στη χρήση και χωρίς ανάγκη για παραγγελθέντα στοιχεία. | Οποιοσδήποτε δύσκολος αλγόριθμος και στοιχεία θα πρέπει να οργανώνονται στη σειρά. |
Γραμμές κώδικα | Πιο λιγο | Περισσότερο |
Ορισμός της γραμμικής αναζήτησης
Σε μια γραμμική αναζήτηση, κάθε στοιχείο μιας συστοιχίας ανακτάται ένα προς ένα με λογική σειρά και ελέγχεται εάν είναι επιθυμητό στοιχείο ή όχι. Μια αναζήτηση θα είναι ανεπιτυχής εάν έχουν πρόσβαση σε όλα τα στοιχεία και δεν έχει βρεθεί το επιθυμητό στοιχείο. Στη χειρότερη περίπτωση, ο αριθμός μιας μέσης περίπτωσης ίσως χρειαστεί να σαρώσουμε το μισό μέγεθος του πίνακα (n / 2).
Επομένως, η γραμμική αναζήτηση μπορεί να οριστεί ως η τεχνική που διασχίζει τη συστοιχία διαδοχικά για να εντοπίσει το δεδομένο στοιχείο. Το παρακάτω πρόγραμμα παρουσιάζει την αναζήτηση ενός στοιχείου της συστοιχίας χρησιμοποιώντας την αναζήτηση.
Αποδοτικότητα της γραμμικής αναζήτησης
Η κατανάλωση χρόνου ή ο αριθμός των συγκρίσεων που έγιναν κατά την αναζήτηση μιας εγγραφής σε έναν πίνακα αναζήτησης καθορίζει την αποτελεσματικότητα της τεχνικής. Εάν η επιθυμητή εγγραφή υπάρχει στην πρώτη θέση του πίνακα αναζήτησης, τότε γίνεται μόνο μία σύγκριση. Όταν η επιθυμητή εγγραφή είναι η τελευταία, πρέπει να γίνουν συγκρίσεις. Εάν η εγγραφή πρόκειται να παρουσιαστεί κάπου στον πίνακα αναζήτησης, κατά μέσο όρο, ο αριθμός των συγκρίσεων θα είναι (n + 1/2). Η χειρότερη περίπτωση απόδοσης αυτής της τεχνικής είναι το Ο (n) σημαίνει τη σειρά εκτέλεσης.
C Πρόγραμμα για να αναζητήσετε ένα στοιχείο με τεχνική γραμμικής αναζήτησης.
#περιλαμβάνω Η δυαδική αναζήτηση είναι ένας εξαιρετικά αποτελεσματικός αλγόριθμος. Αυτή η τεχνική αναζήτησης καταναλώνει λιγότερο χρόνο στην αναζήτηση του δεδομένου αντικειμένου σε ελάχιστες δυνατές συγκρίσεις. Για να γίνει η δυαδική αναζήτηση, πρώτα, πρέπει να ταξινομήσουμε τα στοιχεία συστοιχίας. Η λογική πίσω από αυτή την τεχνική δίνεται παρακάτω: Μπορεί να προκύψουν τρεις περιπτώσεις: Επαναλάβετε τα ίδια βήματα μέχρι να βρεθεί ή εξαντληθεί ένα στοιχείο στην περιοχή αναζήτησης. Σε αυτόν τον αλγόριθμο, κάθε φορά που μειώνεται η περιοχή αναζήτησης. Επομένως ο αριθμός των συγκρίσεων είναι το πολύ log (N + 1). Ως αποτέλεσμα, είναι ένας αποτελεσματικός αλγόριθμος σε σύγκριση με τη γραμμική αναζήτηση, αλλά ο πίνακας πρέπει να ταξινομηθεί πριν γίνει η δυαδική αναζήτηση. C Πρόγραμμα για να βρει ένα στοιχείο με δυαδική τεχνική αναζήτησης. #περιλαμβάνω Τόσο οι γραμμικοί όσο και οι δυαδικοί αλγόριθμοι αναζήτησης μπορούν να είναι χρήσιμοι ανάλογα με την εφαρμογή. Όταν ένας πίνακας είναι η δομή δεδομένων και τα στοιχεία διατάσσονται σε ταξινομημένη σειρά, τότε προτιμάται η δυαδική αναζήτηση γρήγοραερευνητικός. Εάν η συνδεδεμένη λίστα είναι η δομή δεδομένων ανεξάρτητα από τον τρόπο με τον οποίο τα στοιχεία είναι διευθετημένα, η γραμμική αναζήτηση υιοθετείται λόγω της έλλειψης άμεσης εφαρμογής του δυαδικού αλγορίθμου αναζήτησης. Ο τυπικός δυαδικός αλγόριθμος αναζήτησης δεν μπορεί να χρησιμοποιηθεί στη συνδεδεμένη λίστα, επειδή η συνδεδεμένη λίστα είναι δυναμική στη φύση και δεν είναι γνωστό πού ανατίθεται στην πραγματικότητα το μεσαίο στοιχείο. Ως εκ τούτου, υπάρχει η απαίτηση να σχεδιαστεί η παραλλαγή του δυαδικού αλγορίθμου αναζήτησης που μπορεί να λειτουργήσει σε συνδεδεμένη λίστα επίσης διότι η δυαδική αναζήτηση είναι ταχύτερη στην εκτέλεση από μια γραμμική αναζήτηση.Ορισμός της δυαδικής αναζήτησης
συμπέρασμα