1
00:00:00,000 --> 00:00:02,892
>> [Παίζει μουσική]

2
00:00:02,892 --> 00:00:05,347

3
00:00:05,347 --> 00:00:07,180
DOUG LLOYD: Γραμμική
Η αναζήτηση είναι ένας αλγόριθμος που

4
00:00:07,180 --> 00:00:09,840
μπορεί να χρησιμοποιήσει για να βρείτε ένα στοιχείο σε μια σειρά.

5
00:00:09,840 --> 00:00:11,990
Μια ανάκληση αλγόριθμος
είναι ένα βήμα-προς-βήμα σύνολο

6
00:00:11,990 --> 00:00:15,030
οδηγιών για την ολοκλήρωση μιας εργασίας.

7
00:00:15,030 --> 00:00:17,480
>> Η γραμμική αναζήτηση
αλγόριθμος λειτουργεί ως εξής.

8
00:00:17,480 --> 00:00:22,200
Επαναλάβει ολόκληρη τη σειρά από αριστερά προς τα
δεξιά, ψάχνει για ένα συγκεκριμένο στοιχείο.

9
00:00:22,200 --> 00:00:26,380
>> Σε ψευδοκώδικα, η οποία είναι μια πιο
αποσταγμένο έκδοση αυτής της πρότασης,

10
00:00:26,380 --> 00:00:29,840
αν το πρώτο στοιχείο είναι ό, τι
ψάχνετε, μπορείτε να σταματήσετε.

11
00:00:29,840 --> 00:00:33,930
Σε αντίθετη περίπτωση, να προχωρήσουμε στο επόμενο στοιχείο και
συνεχίζω ξανά και ξανά, μέχρι να βρείτε

12
00:00:33,930 --> 00:00:36,389
το στοιχείο, ή δεν το κάνετε.

13
00:00:36,389 --> 00:00:38,680
Έτσι, μπορούμε να χρησιμοποιήσουμε τη γραμμική
αλγόριθμος αναζήτησης, για παράδειγμα,

14
00:00:38,680 --> 00:00:42,330
να βρούμε την τιμή-στόχο
εννέα σε αυτόν τον πίνακα.

15
00:00:42,330 --> 00:00:43,870
Λοιπόν ξεκινάμε από την αρχή.

16
00:00:43,870 --> 00:00:45,970
Αν είναι αυτό που είμαστε
αναζητούν, μπορούμε να σταματήσουμε.

17
00:00:45,970 --> 00:00:47,890
Δεν είναι, δεν ψάχνουμε για 11.

18
00:00:47,890 --> 00:00:50,220
Έτσι, διαφορετικά, να προχωρήσουμε στο επόμενο στοιχείο.

19
00:00:50,220 --> 00:00:51,510
>> Έτσι θα δούμε 23.

20
00:00:51,510 --> 00:00:52,730
Είναι 23 αυτό που ψάχνετε;

21
00:00:52,730 --> 00:00:55,614
Λοιπόν όχι, έτσι ώστε να προχωρήσουμε στην επόμενη
στοιχείο, και το επόμενο στοιχείο,

22
00:00:55,614 --> 00:00:57,780
και συνεχίζουμε μέσω
αυτή η διαδικασία ξανά και ξανά

23
00:00:57,780 --> 00:01:01,030
και πάνω, μέχρι να προσγειωθεί
σε μια κατάσταση όπως αυτή.

24
00:01:01,030 --> 00:01:03,910
>> Εννέα είναι αυτό που ψάχνετε,
και αυτό το στοιχείο της συστοιχίας

25
00:01:03,910 --> 00:01:05,787
είναι αξία που είναι εννέα.

26
00:01:05,787 --> 00:01:08,120
Και έτσι βρήκαμε αυτό που είμαστε
αναζητούν, και μπορούμε να σταματήσουμε.

27
00:01:08,120 --> 00:01:11,910
Η γραμμική αναζήτηση έχει
ολοκληρώθηκε, με επιτυχία.

28
00:01:11,910 --> 00:01:15,370
>> Αλλά τι γίνεται αν ψάχνουμε
ένα στοιχείο που δεν είναι στην παράταξη μας.

29
00:01:15,370 --> 00:01:17,040
Μήπως γραμμική αναζήτηση ακόμη δουλειά;

30
00:01:17,040 --> 00:01:17,540
Καλά σίγουρος.

31
00:01:17,540 --> 00:01:19,947
Γι 'αυτό και επαναλάβετε αυτή τη διαδικασία
ξεκινώντας από το πρώτο στοιχείο.

32
00:01:19,947 --> 00:01:21,780
Αν είναι αυτό που είμαστε
αναζητούν, μπορούμε να σταματήσουμε.

33
00:01:21,780 --> 00:01:22,800
Δεν είναι.

34
00:01:22,800 --> 00:01:25,020
Διαφορετικά, θα προχωρήσουμε στο επόμενο στοιχείο.

35
00:01:25,020 --> 00:01:29,050
>> Αλλά μπορούμε να το επαναλαμβάνουμε αυτή τη διαδικασία,
εξετάζοντας κάθε στοιχείο με τη σειρά του,

36
00:01:29,050 --> 00:01:31,720
ελπίζοντας ότι θα βρούμε τον αριθμό 50.

37
00:01:31,720 --> 00:01:33,750
Αλλά δεν ξέρω αν θα
έχουμε διαπιστώσει τον αριθμό 50

38
00:01:33,750 --> 00:01:38,290
ή αν δεν το κάναμε, μέχρι να έχουμε ενισχυθεί
πάνω από κάθε στοιχείο του πίνακα.

39
00:01:38,290 --> 00:01:40,440
>> Μόνο όταν έχουμε κάνει
ότι και έρχονται απότομα,

40
00:01:40,440 --> 00:01:43,040
μπορούμε να συμπεράνουμε ότι
50 δεν είναι στη συστοιχία.

41
00:01:43,040 --> 00:01:46,410
Και έτσι η γραμμική αναζήτηση
αλγόριθμο, αλλά απέτυχε, per se.

42
00:01:46,410 --> 00:01:49,181
Αλλά όχι με την έννοια ότι
ήταν ανεπιτυχής σε κάνει ό, τι

43
00:01:49,181 --> 00:01:49,930
ζητήσαμε να κάνει.

44
00:01:49,930 --> 00:01:52,390
>> Ήταν ανεπιτυχής στην ως
όσο και αν δεν βρείτε 50,

45
00:01:52,390 --> 00:01:54,070
αλλά 50 δεν ήταν στη συστοιχία.

46
00:01:54,070 --> 00:01:57,310
Αλλά έχουμε εξαντλητικά αναζήτηση
μέσω κάθε στοιχείου

47
00:01:57,310 --> 00:02:00,550
και έτσι, ενώ δεν βρήκαμε
τίποτα, γραμμική αναζήτηση ακόμα

48
00:02:00,550 --> 00:02:05,230
καταφέρνει ακόμη και αν η
στοιχείο δεν είναι στη συστοιχία.

49
00:02:05,230 --> 00:02:07,507
>> Έτσι ποια είναι η χειρότερη περίπτωση
το σενάριο με τη γραμμική αναζήτηση;

50
00:02:07,507 --> 00:02:09,590
Λοιπόν έχουμε να δούμε μέσα
κάθε στοιχείο,

51
00:02:09,590 --> 00:02:14,590
είτε επειδή το στοιχείο στόχος
είναι το τελευταίο στοιχείο της συστοιχίας,

52
00:02:14,590 --> 00:02:18,510
ή το στοιχείο που ψάχνουμε δεν
πράγματι υπάρχουν στη συστοιχία καθόλου.

53
00:02:18,510 --> 00:02:19,760
Ποιο είναι το καλύτερο σενάριο;

54
00:02:19,760 --> 00:02:22,430
Λοιπόν θα μπορούσαμε να βρούμε το
στοιχείο αμέσως.

55
00:02:22,430 --> 00:02:24,360
Και πόσα στοιχεία
εμείς τότε πρέπει να εξετάσουμε

56
00:02:24,360 --> 00:02:26,859
στην στην καλύτερη περίπτωση,
αν ψάχνουμε για αυτό

57
00:02:26,859 --> 00:02:28,400
και θα το βρείτε στην αρχή;

58
00:02:28,400 --> 00:02:29,850
Μπορούμε να σταματήσουμε αμέσως.

59
00:02:29,850 --> 00:02:32,984
>> Τι μας λέει αυτό για το
πολυπλοκότητα της γραμμικής αναζήτησης;

60
00:02:32,984 --> 00:02:35,650
Λοιπόν, στη χειρότερη περίπτωση, έχουμε
να εξετάσει κάθε μεμονωμένο στοιχείο.

61
00:02:35,650 --> 00:02:38,930
Και γι 'αυτό τρέχει σε O του
n, στη χειρότερη περίπτωση.

62
00:02:38,930 --> 00:02:41,540
>> Στην καλύτερη περίπτωση, είμαστε Θα
βρείτε το στοιχείο αμέσως.

63
00:02:41,540 --> 00:02:44,750
Και έτσι λειτουργεί σε ωμέγα-1.

64
00:02:44,750 --> 00:02:45,780
>> Είμαι ο Νταγκ Lloyd.

65
00:02:45,780 --> 00:02:48,020
Αυτό είναι CS50.

66
00:02:48,020 --> 00:02:49,876