Περιεχόμενο

• Περιεχόμενο: Διαφορά μεταξύ γραμμικής αναζήτησης και δυαδικής αναζήτησης
• Συγκριτικό διάγραμμα
• Δυαδική αναζήτηση
• Βασικές διαφορές
• συμπέρασμα
• Επεξηγηματικό βίντεο

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

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

Η γραμμική αναζήτηση είναι ένας πολύ περίπλοκος αλγόριθμος αν θέλετε να αναζητήσετε έναν αριθμό σε μια λίστα, να συγκρίνετε και να επαναλάβετε μερικές φορές τον αριθμό των τιμών στη λίστα. Ένα προς ένα, κάθε στοιχείο του καταλόγου ανακτάται και συγκρίνεται με το παρακείμενο στοιχείο. Όλα τα στοιχεία είναι προσβάσιμα και ελέγχουν και στη συνέχεια το σωστό στοιχείο βρίσκεται. Μπορεί να υπάρχει η χειρότερη περίπτωση αν ο τελευταίος αριθμός στη λίστα είναι ο αριθμός που πρόκειται να αναζητηθεί. Η γραμμική αναζήτηση είναι η μέθοδος με την οποία διασχίζεται ο πίνακας και θεμελιώνεται το στοιχείο προς αναζήτηση. Αν μιλάμε για την αποτελεσματικότητα, η αποτελεσματικότητα είναι ο αριθμός των φορών που το πρόγραμμα πρέπει να τρέξει για να βρει τον αριθμό. Εάν βρούμε τον αριθμό που ψάχνουμε στην πρώτη θέση τότε πρέπει να γίνει μόνο μία σύγκριση και τα πράγματα ταξινομούνται αλλά αν όχι τότε οι συγκρίσεις πρέπει να κάνουν ξανά και ξανά και η μνήμη σπαταλάται. Κατά μέσο όρο, ο αριθμός των συγκρίσεων θα είναι (n + 1/2). Και η χειρότερη περίπτωση απόδοσης αυτής της τεχνικής είναι το O (n) σημαίνει τη σειρά εκτέλεσης.

Σε σύγκριση με τη γραμμική αναζήτηση, η δυαδική αναζήτηση είναι πολύ αποδοτική. Σε αυτή τη μέθοδο, η συστοιχία χωρίζεται σε δύο μέρη και με αυτόν τον τρόπο ο αριθμός των συγκρίσεων είναι πολύ μικρότερος σε σύγκριση με τη δυαδική αναζήτηση. Ο χρόνος είναι επίσης μικρότερος στη δυαδική αναζήτηση σε σύγκριση με τη γραμμική αναζήτηση. Δυαδική εργασία αναζήτησης με τον τρόπο που βρίσκεται το μεσαίο στοιχείο της συστοιχίας και στη συνέχεια συγκρίνεται το μεσαίο στοιχείο με ένα τμήμα του πίνακα. Μπορούν να υπάρχουν τρεις δυνατότητες που είναι ο μεσαίος αριθμός μπορεί να είναι ο αριθμός που πρέπει να βρούμε ή ο αριθμός που είναι μικρότερος από τον μεσαίο αριθμό ή τον αριθμό που είναι μεγαλύτερος από το μέσο του μεσαίου αριθμού. Ο αριθμός των συγκρίσεων είναι το πολύ log (N + 1). Η δυαδική αναζήτηση σε σύγκριση με τη γραμμική αναζήτηση είναι ένας αποτελεσματικός αλγόριθμος σε σύγκριση με τη γραμμική αναζήτηση, αλλά ο πίνακας πρέπει να ταξινομηθεί πριν γίνει η δυαδική αναζήτηση.

Περιεχόμενο: Διαφορά μεταξύ γραμμικής αναζήτησης και δυαδικής αναζήτησης

• Συγκριτικό διάγραμμα
• Δυαδική αναζήτηση
• Βασικές διαφορές
• συμπέρασμα
• Επεξηγηματικό βίντεο

Συγκριτικό διάγραμμα

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

Η γραμμική αναζήτηση είναι ένας πολύ περίπλοκος αλγόριθμος αν θέλετε να αναζητήσετε έναν αριθμό σε μια λίστα, να συγκρίνετε και να επαναλάβετε κάποιες φορές τον αριθμό των τιμών στη λίστα. Ένα προς ένα, κάθε στοιχείο του καταλόγου ανακτάται και συγκρίνεται με το παρακείμενο στοιχείο. Όλα τα στοιχεία είναι προσπελάσιμα και ελέγχουν, και στη συνέχεια το σωστό στοιχείο βρίσκεται. Μπορεί να υπάρχει η χειρότερη περίπτωση αν ο τελευταίος αριθμός στη λίστα είναι ο αριθμός που πρόκειται να αναζητηθεί. Η γραμμική αναζήτηση είναι η μέθοδος με την οποία διασχίζεται ο πίνακας και θεμελιώνεται το στοιχείο προς αναζήτηση. Αν μιλάμε για την αποτελεσματικότητα, η αποτελεσματικότητα είναι ο αριθμός των φορών που το πρόγραμμα πρέπει να τρέξει για να βρει τον αριθμό. Εάν βρούμε τον αριθμό που ψάχνουμε στην πρώτη θέση τότε πρέπει να γίνει μόνο μία σύγκριση και τα πράγματα ταξινομούνται αλλά αν όχι τότε οι συγκρίσεις πρέπει να κάνουν ξανά και ξανά και η μνήμη σπαταλάται. Κατά μέσο όρο, ο αριθμός των συγκρίσεων θα είναι (n + 1/2). Και η χειρότερη περίπτωση απόδοσης αυτής της τεχνικής είναι το O (n) σημαίνει τη σειρά εκτέλεσης.

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

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

Μπορούν να υπάρχουν τρεις δυνατότητες που είναι ο μεσαίος αριθμός μπορεί να είναι ο αριθμός που πρέπει να βρούμε ή ο αριθμός που είναι μικρότερος από τον μεσαίο αριθμό ή τον αριθμό που είναι μεγαλύτερος από το μέσο του μεσαίου αριθμού. Ο αριθμός των συγκρίσεων είναι το πολύ log (N + 1). Η δυαδική αναζήτηση σε σύγκριση με τη γραμμική αναζήτηση είναι ένας αποτελεσματικός αλγόριθμος σε σύγκριση με τη γραμμική αναζήτηση, αλλά ο πίνακας πρέπει να ταξινομηθεί πριν γίνει η δυαδική αναζήτηση.

Βασικές διαφορές

1. Η γραμμική αναζήτηση κάθε στοιχείου ελέγχεται και συγκρίνεται και στη συνέχεια ταξινομείται ενώ η δυαδική αναζήτηση μιας λίστας που πρόκειται να ταξινομηθεί χωρίζεται σε δύο μέρη και στη συνέχεια ταξινομείται.
2. Η χρονική πολυπλοκότητα της γραμμικής αναζήτησης είναι 0 (N) ενώ η πολυπλοκότητα του χρόνου της δυαδικής αναζήτησης είναι O (log₂Ν).
3. Η γραμμική αναζήτηση είναι επαναληπτική, ενώ η δυαδική αναζήτηση είναι Διαίρει και κατακτά.
4. Σε γραμμική αναζήτηση, πρέπει να γράψουμε περισσότερους κώδικες ενώ στη δυαδική αναζήτηση πρέπει να γράψουμε λιγότερους κώδικες.

συμπέρασμα

Σε αυτό το άρθρο, βλέπουμε τη σαφή διαφορά μεταξύ γραμμικής αναζήτησης και δυαδικής αναζήτησης.

Επεξηγηματικό βίντεο