[Παίζει μουσική] DOUG LLOYD: Γραμμική Η αναζήτηση είναι ένας αλγόριθμος που μπορεί να χρησιμοποιήσει για να βρείτε ένα στοιχείο σε μια σειρά. Μια ανάκληση αλγόριθμος είναι ένα βήμα-προς-βήμα σύνολο οδηγιών για την ολοκλήρωση μιας εργασίας. 

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

Σε ψευδοκώδικα, η οποία είναι μια πιο αποσταγμένο έκδοση αυτής της πρότασης, αν το πρώτο στοιχείο είναι ό, τι ψάχνετε, μπορείτε να σταματήσετε. Σε αντίθετη περίπτωση, να προχωρήσουμε στο επόμενο στοιχείο και συνεχίζω ξανά και ξανά, μέχρι να βρείτε το στοιχείο, ή δεν το κάνετε. Έτσι, μπορούμε να χρησιμοποιήσουμε τη γραμμική αλγόριθμος αναζήτησης, για παράδειγμα, να βρούμε την τιμή-στόχο εννέα σε αυτόν τον πίνακα. Λοιπόν ξεκινάμε από την αρχή. Αν είναι αυτό που είμαστε αναζητούν, μπορούμε να σταματήσουμε. Δεν είναι, δεν ψάχνουμε για 11. Έτσι, διαφορετικά, να προχωρήσουμε στο επόμενο στοιχείο. 

Έτσι θα δούμε 23. Είναι 23 αυτό που ψάχνετε; Λοιπόν όχι, έτσι ώστε να προχωρήσουμε στην επόμενη στοιχείο, και το επόμενο στοιχείο, και συνεχίζουμε μέσω αυτή η διαδικασία ξανά και ξανά και πάνω, μέχρι να προσγειωθεί σε μια κατάσταση όπως αυτή. 

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

Αλλά τι γίνεται αν ψάχνουμε ένα στοιχείο που δεν είναι στην παράταξη μας. Μήπως γραμμική αναζήτηση ακόμη δουλειά; Καλά σίγουρος. Γι 'αυτό και επαναλάβετε αυτή τη διαδικασία ξεκινώντας από το πρώτο στοιχείο. Αν είναι αυτό που είμαστε αναζητούν, μπορούμε να σταματήσουμε. Δεν είναι. Διαφορετικά, θα προχωρήσουμε στο επόμενο στοιχείο. 

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

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

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

Έτσι ποια είναι η χειρότερη περίπτωση το σενάριο με τη γραμμική αναζήτηση; Λοιπόν έχουμε να δούμε μέσα κάθε στοιχείο, είτε επειδή το στοιχείο στόχος είναι το τελευταίο στοιχείο της συστοιχίας, ή το στοιχείο που ψάχνουμε δεν πράγματι υπάρχουν στη συστοιχία καθόλου. Ποιο είναι το καλύτερο σενάριο; Λοιπόν θα μπορούσαμε να βρούμε το στοιχείο αμέσως. Και πόσα στοιχεία εμείς τότε πρέπει να εξετάσουμε στην στην καλύτερη περίπτωση, αν ψάχνουμε για αυτό και θα το βρείτε στην αρχή; Μπορούμε να σταματήσουμε αμέσως. 

Τι μας λέει αυτό για το πολυπλοκότητα της γραμμικής αναζήτησης; Λοιπόν, στη χειρότερη περίπτωση, έχουμε να εξετάσει κάθε μεμονωμένο στοιχείο. Και γι 'αυτό τρέχει σε O του n, στη χειρότερη περίπτωση. 

Στην καλύτερη περίπτωση, είμαστε Θα βρείτε το στοιχείο αμέσως. Και έτσι λειτουργεί σε ωμέγα-1. 

Είμαι ο Νταγκ Lloyd. Αυτό είναι CS50.