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
डौग लॉयड: रैखिक
खोज के लिए एक एल्गोरिथ्म हम है

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
और तो रैखिक खोज
एल्गोरिथ्म, यह विफल रहा है, ठीक है, दर असल।

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
और तो यह हे में चलता है
एन, सबसे खराब स्थिति में।

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
>> मैं डौग लॉयड हूँ।

65
00:02:45,780 --> 00:02:48,020
इस CS50 है।

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