1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> ठीक है, तो, कम्प्यूटेशनल जटिलता।

3
00:00:07,910 --> 00:00:10,430
एक चेतावनी का सिर्फ एक बिट
हम भी far-- में गोता लगाने से पहले

4
00:00:10,430 --> 00:00:13,070
यह शायद के बीच हो जाएगा
सबसे गणित भारी चीजें

5
00:00:13,070 --> 00:00:14,200
हम CS50 में के बारे में बात करते हैं।

6
00:00:14,200 --> 00:00:16,950
उम्मीद है कि यह बहुत भारी नहीं होगा
और हम कोशिश करते हैं और आपका मार्गदर्शन करेंगे

7
00:00:16,950 --> 00:00:19,200
प्रक्रिया के माध्यम से, लेकिन
एक निष्पक्ष चेतावनी का सिर्फ एक सा है।

8
00:00:19,200 --> 00:00:21,282
एक छोटा सा है
गणित के यहां शामिल किया गया।

9
00:00:21,282 --> 00:00:23,990
ठीक है, आदेश में ऐसा करने के लिए
हमारे कम्प्यूटेशनल संसाधनों का उपयोग

10
00:00:23,990 --> 00:00:28,170
वास्तविक world-- में यह सच है
एल्गोरिदम समझने के लिए महत्वपूर्ण

11
00:00:28,170 --> 00:00:30,750
और कैसे वे डेटा की प्रक्रिया।

12
00:00:30,750 --> 00:00:32,810
अगर हमारे पास है एक सच
कुशल एल्गोरिथ्म, हम

13
00:00:32,810 --> 00:00:36,292
संसाधनों की मात्रा को कम कर सकते हैं
हम इसके साथ सौदा करने के लिए उपलब्ध है।

14
00:00:36,292 --> 00:00:38,750
हम एक एल्गोरिथ्म है, तो उस
काम का एक बहुत ले जा रहा है

15
00:00:38,750 --> 00:00:41,210
वास्तव में एक प्रक्रिया के लिए
डेटा के बड़े सेट, यह है

16
00:00:41,210 --> 00:00:44,030
अधिक आवश्यकता होती जा रही
अधिक संसाधनों, और जो

17
00:00:44,030 --> 00:00:47,980
सामान का पैसा, रैम, है कि सभी तरह की है।

18
00:00:47,980 --> 00:00:52,090
>> तो, सक्षम होने के एक विश्लेषण करने के लिए
एल्गोरिथ्म, इस उपकरण सेट का उपयोग

19
00:00:52,090 --> 00:00:56,110
असल में, question-- पूछता
इस एल्गोरिथ्म पैमाने कैसे करता है

20
00:00:56,110 --> 00:00:59,020
हम उस पर अधिक से अधिक डेटा फेंक के रूप में?

21
00:00:59,020 --> 00:01:02,220
CS50 में, हम डेटा की मात्रा हो
के साथ काम करने में बहुत छोटा है।

22
00:01:02,220 --> 00:01:05,140
आम तौर पर, हमारे कार्यक्रमों जा रहे हैं
एक दूसरे या less-- में चलाने के लिए

23
00:01:05,140 --> 00:01:07,830
शायद बहुत कम
विशेष रूप से जल्दी पर।

24
00:01:07,830 --> 00:01:12,250
>> लेकिन यह है कि सौदों एक कंपनी के बारे में सोचते हैं
ग्राहकों के लाखों लोगों के सैकड़ों के साथ।

25
00:01:12,250 --> 00:01:14,970
और वे इस प्रक्रिया की जरूरत है
कि ग्राहक डेटा।

26
00:01:14,970 --> 00:01:18,260
ग्राहकों की संख्या के रूप में वे
है, बड़ा और बड़ा हो जाता है

27
00:01:18,260 --> 00:01:21,230
यह आवश्यकता होती जा रही है
अधिक से अधिक संसाधनों।

28
00:01:21,230 --> 00:01:22,926
कितने अधिक संसाधनों?

29
00:01:22,926 --> 00:01:25,050
खैर, उस पर निर्भर करता है
हम एल्गोरिथ्म विश्लेषण,

30
00:01:25,050 --> 00:01:28,097
इस उपकरण बॉक्स में उपकरण का उपयोग कर।

31
00:01:28,097 --> 00:01:31,180
हम की जटिलता के बारे में बात करते हैं
एक algorithm-- जो कभी कभी आप हूँ

32
00:01:31,180 --> 00:01:34,040
यह समय के रूप में भेजा सुनना
जटिलता या अंतरिक्ष जटिलता

33
00:01:34,040 --> 00:01:36,190
लेकिन हम अभी जा रहे हैं
complexity-- फोन करने के लिए

34
00:01:36,190 --> 00:01:38,770
हम आम तौर पर के बारे में बात कर रहे हैं
सबसे खराब स्थिति।

35
00:01:38,770 --> 00:01:42,640
निरपेक्ष बुरी ढेर को देखते हुए
हम उस पर फेंक हो सकता है कि डेटा,

36
00:01:42,640 --> 00:01:46,440
कैसे इस एल्गोरिथ्म के लिए जा रहा है
प्रक्रिया या कि डेटा के साथ सौदा?

37
00:01:46,440 --> 00:01:51,450
हम आम तौर पर सबसे ज्यादा मामले फोन
एक एल्गोरिथ्म बड़े-ओ का क्रम।

38
00:01:51,450 --> 00:01:56,770
तो एक एल्गोरिथ्म के लिए कहा जा सकता है
चुकता n या एन हे हे में चलाते हैं।

39
00:01:56,770 --> 00:01:59,110
के बारे में और अधिक क्या
उन एक दूसरे में मतलब है।

40
00:01:59,110 --> 00:02:01,620
>> कभी कभी, हालांकि, हम परवाह करना
सबसे अच्छी स्थिति के बारे में।

41
00:02:01,620 --> 00:02:05,400
डेटा सब कुछ है, तो हम चाहते थे
यह हो सकता है और यह बिल्कुल सही था

42
00:02:05,400 --> 00:02:09,630
और हम यह सही भेज रहे थे
हमारे एल्गोरिथ्म के माध्यम से डेटा का सेट।

43
00:02:09,630 --> 00:02:11,470
कैसे यह उस स्थिति में संभालना होगा?

44
00:02:11,470 --> 00:02:15,050
हम कभी कभी के रूप में है कि करने के लिए देखें
बड़े-ओमेगा, बड़े-ओ के साथ इसके विपरीत में तो,

45
00:02:15,050 --> 00:02:16,530
हम बड़ी-ओमेगा है।

46
00:02:16,530 --> 00:02:18,880
सबसे अच्छी स्थिति के लिए बिग-ओमेगा।

47
00:02:18,880 --> 00:02:21,319
सबसे खराब स्थिति के लिए बिग-हे।

48
00:02:21,319 --> 00:02:23,860
आम तौर पर, हम के बारे में जब बात
एक एल्गोरिथ्म की जटिलता,

49
00:02:23,860 --> 00:02:26,370
हम के बारे में बात कर रहे हैं
सबसे खराब मामले की पृष्ठभूमि।

50
00:02:26,370 --> 00:02:28,100
इसलिए इस बात का ध्यान रखें।

51
00:02:28,100 --> 00:02:31,510
>> और इस वर्ग में, हम आम तौर पर जा रहे हैं
एक तरफ कठोर विश्लेषण छोड़ने के लिए।

52
00:02:31,510 --> 00:02:35,350
विज्ञान और क्षेत्रों रहे हैं
इस तरह की चीजें करने के लिए समर्पित कर दिया।

53
00:02:35,350 --> 00:02:37,610
हम तर्क के बारे में बात करते हैं
एल्गोरिदम के माध्यम से,

54
00:02:37,610 --> 00:02:41,822
हम कई के लिए टुकड़ा-दर-टुकड़े कर देंगे जो
एल्गोरिदम हम वर्ग में के बारे में बात करते हैं।

55
00:02:41,822 --> 00:02:44,780
हम वास्तव में बस के बारे में बात कर रहे हैं
आम भावना के साथ के माध्यम से यह तर्क,

56
00:02:44,780 --> 00:02:47,070
नहीं सूत्र, या सबूत के साथ,
या ऐसा कुछ।

57
00:02:47,070 --> 00:02:51,600
तो चिंता मत करो, हम नहीं होगा
एक बड़ा गणित वर्ग में तब्दील हो रही।

58
00:02:51,600 --> 00:02:55,920
>> इसलिए मुझे लगता है कि हम जटिलता के बारे में परवाह कहा
यह सवाल, कैसे पूछता है क्योंकि

59
00:02:55,920 --> 00:03:00,160
हमारे एल्गोरिदम बड़ा संभाल करते हो और
बड़े डेटा सेट उन पर फेंक दिया जा रहा है।

60
00:03:00,160 --> 00:03:01,960
खैर, एक डेटा सेट क्या है?

61
00:03:01,960 --> 00:03:03,910
मुझे लगता है कि जब मैंने कहा कि क्या मतलब था?

62
00:03:03,910 --> 00:03:07,600
यह सबसे अधिक करता है जो कुछ भी मतलब है
संदर्भ में समझ, ईमानदार हो।

63
00:03:07,600 --> 00:03:11,160
हम एक एल्गोरिथ्म है, तो
प्रक्रियाओं Strings-- हम शायद रहे हैं

64
00:03:11,160 --> 00:03:13,440
स्ट्रिंग के आकार के बारे में बात कर।

65
00:03:13,440 --> 00:03:15,190
यही कारण है कि डेटा है set--
आकार, संख्या

66
00:03:15,190 --> 00:03:17,050
स्ट्रिंग को बनाने वाले पात्रों की।

67
00:03:17,050 --> 00:03:20,090
हम एक के बारे में बात कर रहे हैं
फ़ाइलें प्रक्रियाओं कि एल्गोरिथ्म,

68
00:03:20,090 --> 00:03:23,930
हम कैसे के बारे में बात की जा सकती है
कई किलोबाइट उस फ़ाइल को शामिल।

69
00:03:23,930 --> 00:03:25,710
और उस डेटा सेट है।

70
00:03:25,710 --> 00:03:28,870
हम एक एल्गोरिथ्म के बारे में बात कर रहे हैं
कि, और अधिक आम तौर पर सरणियों संभालती

71
00:03:28,870 --> 00:03:31,510
ऐसे छँटाई एल्गोरिदम के रूप में
या एल्गोरिदम खोज,

72
00:03:31,510 --> 00:03:36,690
हम शायद संख्या के बारे में बात कर रहे हैं
एक सरणी शामिल है कि तत्वों की।

73
00:03:36,690 --> 00:03:39,272
>> अब, हम एक उपाय कर सकते हैं
algorithm-- विशेष रूप से,

74
00:03:39,272 --> 00:03:40,980
मैं कहना है कि जब हम कर सकते हैं
मैं एक एल्गोरिथ्म के उपाय

75
00:03:40,980 --> 00:03:43,840
हम कैसे उपाय कर सकते हैं मतलब
कई संसाधनों यह लेता है।

76
00:03:43,840 --> 00:03:48,990
उन संसाधनों रहे हैं, कितने
RAM-- के बाइट्स या राम की मेगाबाइट

77
00:03:48,990 --> 00:03:49,790
यह उपयोगकर्ता है।

78
00:03:49,790 --> 00:03:52,320
या कितना समय इसे चलाने के लिए लेता है।

79
00:03:52,320 --> 00:03:56,200
और हम इस कॉल कर सकते हैं
n के च, मनमाने ढंग से, को मापने।

80
00:03:56,200 --> 00:03:59,420
जहाँ n की संख्या है
डेटा सेट में तत्वों।

81
00:03:59,420 --> 00:04:02,640
और एन के च कितने somethings है।

82
00:04:02,640 --> 00:04:07,530
कितने संसाधनों की इकाइयों करता है
यह उस डेटा को संसाधित करने की आवश्यकता है।

83
00:04:07,530 --> 00:04:10,030
>> अब, हम वास्तव में परवाह नहीं है
बिल्कुल n के च क्या है के बारे में।

84
00:04:10,030 --> 00:04:13,700
वास्तव में, हम बहुत कम ही will--
निश्चित रूप से कभी नहीं होगा इस class-- मैं में

85
00:04:13,700 --> 00:04:18,709
किसी भी वास्तव में गहरी में गोता
च n है क्या का विश्लेषण।

86
00:04:18,709 --> 00:04:23,510
हम बस क्या च के बारे में बात करने जा रहे हैं
एन लगभग या क्या यह करने के लिए जाता है।

87
00:04:23,510 --> 00:04:27,600
और एक एल्गोरिथ्म की प्रवृत्ति है
अपने उच्चतम आदेश अवधि तय करती।

88
00:04:27,600 --> 00:04:29,440
और हम देख सकते हैं क्या मैं
लेने से मतलब

89
00:04:29,440 --> 00:04:31,910
एक एक और अधिक ठोस उदाहरण देखो।

90
00:04:31,910 --> 00:04:34,620
>> तो चलो हम है कि हम कहते हैं
तीन अलग अलग एल्गोरिदम।

91
00:04:34,620 --> 00:04:39,350
जिनमें से पहले n लेता है
संसाधनों की घन, कुछ इकाइयों

92
00:04:39,350 --> 00:04:42,880
आकार n के एक डेटा सेट की प्रक्रिया करने के लिए।

93
00:04:42,880 --> 00:04:47,000
हम लेता है कि एक दूसरे एल्गोरिथ्म है
घन प्लस n चुकता संसाधनों n

94
00:04:47,000 --> 00:04:49,350
आकार n के एक डेटा सेट की प्रक्रिया करने के लिए।

95
00:04:49,350 --> 00:04:52,030
और हम एक-तिहाई है
कि in-- चलता है कि एल्गोरिथ्म

96
00:04:52,030 --> 00:04:58,300
ऊपर लेता एन घन घटा 8N चुकता
संसाधनों की प्लस 20 एन इकाइयों

97
00:04:58,300 --> 00:05:02,370
एक एल्गोरिथ्म पर कार्रवाई करने के लिए
आकार n का सेट डेटा के साथ।

98
00:05:02,370 --> 00:05:05,594
>> अब फिर से, हम वास्तव में नहीं जा रहे हैं
विस्तार के इस स्तर में मिलता है।

99
00:05:05,594 --> 00:05:08,260
मैं तो बस इन ऊपर है वास्तव में कर रहा हूँ
एक बात यहाँ का एक उदाहरण के रूप में

100
00:05:08,260 --> 00:05:10,176
मैं जा रहा हूँ कि
एक दूसरे में कर रही है, जो

101
00:05:10,176 --> 00:05:12,980
हम केवल वास्तव में परवाह है कि
चीजों की प्रवृत्ति के बारे में

102
00:05:12,980 --> 00:05:14,870
डेटा सेट बड़ा हो जाता है।

103
00:05:14,870 --> 00:05:18,220
डेटा सेट छोटा है तो, अगर वहाँ है
वास्तव में एक बहुत बड़ा अंतर

104
00:05:18,220 --> 00:05:19,870
इन एल्गोरिदम में।

105
00:05:19,870 --> 00:05:23,000
वहाँ तीसरे एल्गोरिथ्म
13 गुना ज्यादा समय लेता है

106
00:05:23,000 --> 00:05:27,980
संसाधनों का 13 गुना राशि
पहले एक रिश्तेदार को चलाने के लिए।

107
00:05:27,980 --> 00:05:31,659
>> हमारे डेटा सेट आकार 10 है, तो जो
, बड़ा है, लेकिन जरूरी नहीं कि बहुत बड़ा नहीं है

108
00:05:31,659 --> 00:05:33,950
हम देखते है कि देख सकते हैं
वास्तव में एक अंतर का एक सा।

109
00:05:33,950 --> 00:05:36,620
तीसरे एल्गोरिथ्म
और अधिक कुशल हो जाता है।

110
00:05:36,620 --> 00:05:40,120
यह वास्तव में 40% के बारे में है -
या 60% अधिक कुशल है।

111
00:05:40,120 --> 00:05:41,580
यह 40% समय की राशि लेता है।

112
00:05:41,580 --> 00:05:45,250
यह ले जा सकते हैं run-- कर सकते हैं
संसाधनों की 400 इकाइयों

113
00:05:45,250 --> 00:05:47,570
आकार 10 के एक डेटा सेट की प्रक्रिया करने के लिए।

114
00:05:47,570 --> 00:05:49,410
पहला जबकि
एल्गोरिथ्म, इसके विपरीत,

115
00:05:49,410 --> 00:05:54,520
संसाधनों की 1,000 इकाइयों लेता है
आकार 10 के एक डेटा सेट की प्रक्रिया करने के लिए।

116
00:05:54,520 --> 00:05:57,240
लेकिन जैसे देखो क्या होता है
हमारी संख्या भी बड़ा हो।

117
00:05:57,240 --> 00:05:59,500
>> अब, अंतर
इन एल्गोरिदम के बीच

118
00:05:59,500 --> 00:06:01,420
एक छोटे से कम स्पष्ट बनने के लिए शुरू करते हैं।

119
00:06:01,420 --> 00:06:04,560
देखते हैं कि और तथ्य
निचले क्रम terms-- या यों कहें,

120
00:06:04,560 --> 00:06:09,390
कम exponents-- के साथ शब्दों
अप्रासंगिक बनने के लिए शुरू करते हैं।

121
00:06:09,390 --> 00:06:12,290
एक डेटा सेट के आकार का है
1000 और पहले एल्गोरिथ्म

122
00:06:12,290 --> 00:06:14,170
एक अरब चरणों में चलाता है।

123
00:06:14,170 --> 00:06:17,880
और दूसरा एल्गोरिथ्म में चलाता है
एक अरब डॉलर और एक लाख कदम।

124
00:06:17,880 --> 00:06:20,870
और तीसरा एल्गोरिथ्म चलाता
एक अरब कदम की शर्मीली में।

125
00:06:20,870 --> 00:06:22,620
यह बहुत ज्यादा एक अरब कदम है।

126
00:06:22,620 --> 00:06:25,640
उन निचले क्रम के लिहाज से शुरू
वास्तव में अप्रासंगिक हो जाते हैं।

127
00:06:25,640 --> 00:06:27,390
और सिर्फ सच करने के लिए
घर हथौड़ा point--

128
00:06:27,390 --> 00:06:31,240
डेटा इनपुट आकार एक की है, तो
million-- इन तीनों बहुत ज्यादा

129
00:06:31,240 --> 00:06:34,960
एक quintillion-- तो ले
मेरी गणित correct-- कदम है

130
00:06:34,960 --> 00:06:37,260
एक डेटा निवेश की प्रक्रिया को
आकार एक लाख का।

131
00:06:37,260 --> 00:06:38,250
यही कारण है कि कदम की एक बहुत कुछ है।

132
00:06:38,250 --> 00:06:42,092
और सच तो यह है कि उनमें से एक हो सकता है
एक जोड़ी 100,000, या एक जोड़े को ले 100

133
00:06:42,092 --> 00:06:44,650
लाख भी कम जब
हम एक संख्या के बारे में बात कर रहे हैं

134
00:06:44,650 --> 00:06:46,990
कि यह एक तरह से अप्रासंगिक है big--।

135
00:06:46,990 --> 00:06:50,006
वे सब ले जाते हैं
लगभग एन घन,

136
00:06:50,006 --> 00:06:52,380
और इसलिए हम वास्तव में उल्लेख होगा
इन एल्गोरिदम के सभी के लिए

137
00:06:52,380 --> 00:06:59,520
n के आदेश पर किया जा रहा है के रूप में
घन या एन घन के बड़े-हे।

138
00:06:59,520 --> 00:07:03,220
>> यहाँ और अधिक से कुछ की एक सूची है
आम कम्प्यूटेशनल जटिलता कक्षाएं

139
00:07:03,220 --> 00:07:05,820
हम में मुठभेड़ हूँ कि
एल्गोरिदम, आम तौर पर।

140
00:07:05,820 --> 00:07:07,970
और भी विशेष रूप से CS50 में।

141
00:07:07,970 --> 00:07:11,410
इन से आदेश दिए हैं
आम तौर पर शीर्ष पर सबसे तेजी से,

142
00:07:11,410 --> 00:07:13,940
निचले भाग में आम तौर पर धीमी करने के लिए।

143
00:07:13,940 --> 00:07:16,920
तो लगातार समय एल्गोरिदम करते हैं
की परवाह किए बिना, तेजी से हो

144
00:07:16,920 --> 00:07:19,110
के आकार का
डेटा इनपुट आप में से गुजरती हैं।

145
00:07:19,110 --> 00:07:23,760
वे हमेशा एक ऑपरेशन ले या
साथ सौदा करने के लिए संसाधनों की एक इकाई।

146
00:07:23,760 --> 00:07:25,730
यह 2 हो सकता है, यह हो सकता है
3 हो सकता है, यह 4 हो सकता है।

147
00:07:25,730 --> 00:07:26,910
लेकिन यह एक निरंतर संख्या है।

148
00:07:26,910 --> 00:07:28,400
यह भिन्न नहीं है।

149
00:07:28,400 --> 00:07:31,390
>> लघुगणक समय एल्गोरिदम
थोड़ा बेहतर हैं।

150
00:07:31,390 --> 00:07:33,950
और का एक बहुत अच्छा उदाहरण
एक लघुगणक समय एल्गोरिथ्म

151
00:07:33,950 --> 00:07:37,420
आप निश्चित रूप से अब तक देखा है किया है
फोन की किताब के अलावा फाड़

152
00:07:37,420 --> 00:07:39,480
फोन की किताब में माइक स्मिथ खोजने के लिए।

153
00:07:39,480 --> 00:07:40,980
हम आधे में समस्या काटा।

154
00:07:40,980 --> 00:07:43,580
और एन बड़ा हो जाता है तो के रूप में
और बड़ा और larger--

155
00:07:43,580 --> 00:07:47,290
वास्तव में, हर बार जब आप दोगुना
एन, यह केवल एक और कदम लेता है।

156
00:07:47,290 --> 00:07:49,770
कि एक बहुत बेहतर है तो
की तुलना में, कहते हैं, रैखिक समय।

157
00:07:49,770 --> 00:07:53,030
आप n दोगुना करता है, तो यह कौन सा है,
कदम की संख्या दोगुनी लेता है।

158
00:07:53,030 --> 00:07:55,980
आप n ट्रिपल हैं, तो यह लगता है
चरणों की संख्या तीन गुना।

159
00:07:55,980 --> 00:07:58,580
प्रति यूनिट एक कदम है।

160
00:07:58,580 --> 00:08:01,790
>> तब एक छोटी चीजें more-- मिल
छोटे से कम महान वहाँ से।

161
00:08:01,790 --> 00:08:06,622
आप कभी-कभी, रैखिक लयबद्ध समय है
लॉग रैखिक समय कहा जाता है या सिर्फ n लॉग एन।

162
00:08:06,622 --> 00:08:08,330
और हम एक उदाहरण हूँ
एक एल्गोरिथ्म की है कि

163
00:08:08,330 --> 00:08:13,370
अभी भी बेहतर है, जो एन लॉग n, में रन
से द्विघात time-- n चुकता।

164
00:08:13,370 --> 00:08:17,320
या बहुपद समय, एन दो
दो से अधिक से अधिक किसी भी संख्या।

165
00:08:17,320 --> 00:08:20,810
या घातीय समय, जो
यहां तक ​​कि worse-- सी n करने के लिए है।

166
00:08:20,810 --> 00:08:24,670
तो कुछ निरंतर संख्या के लिए उठाया
इनपुट के आकार की शक्ति।

167
00:08:24,670 --> 00:08:28,990
तो अगर 1,000-- अगर वहाँ
डेटा इनपुट, आकार 1000 की है

168
00:08:28,990 --> 00:08:31,310
यह 1000 में सत्ता में सी लग जाएगा।

169
00:08:31,310 --> 00:08:33,559
यह बहुपद समय की तुलना में बहुत खराब है।

170
00:08:33,559 --> 00:08:35,030
>> भाज्य समय और भी बदतर है।

171
00:08:35,030 --> 00:08:37,760
और वास्तव में, वास्तव में वहां क्या
अनंत समय एल्गोरिदम मौजूद हैं,

172
00:08:37,760 --> 00:08:43,740
जिसका ऐसे तथाकथित, के रूप में बेवकूफ sort--
नौकरी के बेतरतीब ढंग से एक सरणी फेरबदल करने के लिए है

173
00:08:43,740 --> 00:08:45,490
और फिर देखने के लिए जाँच
कि क्या यह हल है।

174
00:08:45,490 --> 00:08:47,589
और यह बेतरतीब ढंग से, अगर नहीं है
फिर सरणी फेरबदल

175
00:08:47,589 --> 00:08:49,130
और यह हल है या नहीं यह देखने के लिए जाँच करें।

176
00:08:49,130 --> 00:08:51,671
और जैसा कि आप शायद imagine-- कर सकते हैं
आप एक स्थिति की कल्पना कर सकते हैं

177
00:08:51,671 --> 00:08:55,200
जहां सबसे ज्यादा मामले में, कि इच्छा
वास्तव में सरणी के साथ शुरू करते हैं कभी नहीं।

178
00:08:55,200 --> 00:08:57,150
एल्गोरिथ्म है कि हमेशा के लिए चला जाएगा।

179
00:08:57,150 --> 00:08:59,349
और इतना है कि एक होगा
अनंत समय एल्गोरिथ्म।

180
00:08:59,349 --> 00:09:01,890
उम्मीद है कि आप लिख नहीं की जाएगी
किसी भी भाज्य या अनंत समय

181
00:09:01,890 --> 00:09:04,510
CS50 में एल्गोरिदम।

182
00:09:04,510 --> 00:09:09,150
>> तो, चलो ले चलो एक छोटे से अधिक
कुछ सरल पर ठोस नज़र

183
00:09:09,150 --> 00:09:11,154
कम्प्यूटेशनल जटिलता वर्गों।

184
00:09:11,154 --> 00:09:13,070
इसलिए हम एक example-- है
या दो उदाहरण here--

185
00:09:13,070 --> 00:09:15,590
लगातार समय एल्गोरिदम के,
जो हमेशा के लिए ले

186
00:09:15,590 --> 00:09:17,980
सबसे ज्यादा मामले में एक ही आपरेशन।

187
00:09:17,980 --> 00:09:20,050
पहले example-- तो
हम एक समारोह है

188
00:09:20,050 --> 00:09:23,952
आप के लिए 4 कहा जाता है जो
आकार 1,000 के एक सरणी लेता है।

189
00:09:23,952 --> 00:09:25,660
लेकिन तब जाहिरा तौर पर
वास्तव में नहीं लगती है

190
00:09:25,660 --> 00:09:29,000
it-- वास्तव में क्या परवाह नहीं करता पर
, इसके अंदर उस सरणी की।

191
00:09:29,000 --> 00:09:30,820
हमेशा सिर्फ चार रिटर्न।

192
00:09:30,820 --> 00:09:32,940
तो, कि एल्गोरिथ्म,
यह है कि इस तथ्य के बावजूद

193
00:09:32,940 --> 00:09:35,840
1,000 तत्व नहीं है लेता है
उनके साथ कुछ भी कर।

194
00:09:35,840 --> 00:09:36,590
बस चार रिटर्न।

195
00:09:36,590 --> 00:09:38,240
यह हमेशा एक ही कदम है।

196
00:09:38,240 --> 00:09:41,600
>> वास्तव में, 2 nums-- जो जोड़ने
हम के रूप में well-- पहले देखा है

197
00:09:41,600 --> 00:09:43,680
सिर्फ दो पूर्णांकों प्रक्रियाओं।

198
00:09:43,680 --> 00:09:44,692
यह एक भी कदम नहीं है।

199
00:09:44,692 --> 00:09:45,900
यह वास्तव में एक दो कदम है।

200
00:09:45,900 --> 00:09:50,780
आप एक मिलता है, तुम ख मिलता है, तो आप उन्हें जोड़ने
एक साथ, और तुम उत्पादन का परिणाम है।

201
00:09:50,780 --> 00:09:53,270
तो यह 84 कदम है।

202
00:09:53,270 --> 00:09:55,510
लेकिन यह हमेशा स्थिर है
की परवाह किए बिना एक या बी की।

203
00:09:55,510 --> 00:09:59,240
आप एक पाने के लिए है, ख मिलता है, जोड़ने
उन्हें एक साथ, उत्पादन परिणाम।

204
00:09:59,240 --> 00:10:02,900
तो यह है कि एक निरंतर समय एल्गोरिथ्म है।

205
00:10:02,900 --> 00:10:05,170
>> यहाँ एक का एक उदाहरण है
रैखिक समय algorithm--

206
00:10:05,170 --> 00:10:08,740
कि लेता gets-- कि एक एल्गोरिथ्म
एक अतिरिक्त कदम है, संभवतः,

207
00:10:08,740 --> 00:10:10,740
अपने इनपुट 1 से बढ़ता है।

208
00:10:10,740 --> 00:10:14,190
तो, चलो हम देख रहे हैं हम कहते हैं
एक सरणी की संख्या 5 के अंदर।

209
00:10:14,190 --> 00:10:16,774
आप एक स्थिति जहां हो सकता है
आप के लिए यह काफी जल्दी मिल सकता है।

210
00:10:16,774 --> 00:10:18,606
लेकिन आप यह भी हो सकता था
एक स्थिति जहां यह

211
00:10:18,606 --> 00:10:20,450
सरणी के अंतिम तत्व हो सकता है।

212
00:10:20,450 --> 00:10:23,780
आकार 5 की एक सरणी, यदि में
हम नंबर 5 के लिए देख रहे हैं।

213
00:10:23,780 --> 00:10:25,930
यह 5 कदम उठाएगी।

214
00:10:25,930 --> 00:10:29,180
और वास्तव में, यह है कि वहाँ की कल्पना
इस सरणी में नहीं 5 कहीं।

215
00:10:29,180 --> 00:10:32,820
हम अभी भी वास्तव में देखने की जरूरत
सरणी के हर एक तत्व

216
00:10:32,820 --> 00:10:35,550
निर्धारित करने के लिए
या नहीं, 5 है।

217
00:10:35,550 --> 00:10:39,840
>> तो यह है कि जो सबसे ज्यादा मामले में
तत्व सरणी में पिछले है

218
00:10:39,840 --> 00:10:41,700
या सब पर मौजूद नहीं है।

219
00:10:41,700 --> 00:10:44,690
हम अभी भी देखने के लिए है
n तत्वों के सभी।

220
00:10:44,690 --> 00:10:47,120
और इसलिए इस एल्गोरिथ्म
रैखिक समय में चलाता है।

221
00:10:47,120 --> 00:10:50,340
आप से है कि पुष्टि कर सकते हैं
कह कर एक छोटा सा Extrapolating,

222
00:10:50,340 --> 00:10:53,080
हम एक 6-तत्व सरणी था और अगर
हम नंबर 5 के लिए देख रहे थे

223
00:10:53,080 --> 00:10:54,890
यह 6 कदम ले सकता है।

224
00:10:54,890 --> 00:10:57,620
हम एक 7-तत्व सरणी है और
हम नंबर 5 के लिए देख रहे हैं।

225
00:10:57,620 --> 00:10:59,160
यह 7 चरणों में ले सकता है।

226
00:10:59,160 --> 00:11:02,920
हम एक और तत्व को जोड़ने के रूप में हमारे
सरणी, यह एक और कदम लेता है।

227
00:11:02,920 --> 00:11:06,750
यही कारण है कि एक रेखीय एल्गोरिथ्म है
सबसे खराब स्थिति में।

228
00:11:06,750 --> 00:11:08,270
>> युगल आप के लिए जल्दी सवाल।

229
00:11:08,270 --> 00:11:11,170
क्या runtime-- क्या है
सबसे ज्यादा मामले क्रम

230
00:11:11,170 --> 00:11:13,700
कोड के इस विशेष टुकड़ा की?

231
00:11:13,700 --> 00:11:17,420
तो मैं चलता है कि यहां एक 4 पाश
जे 0, एम के लिए सभी तरह के बराबर होती है।

232
00:11:17,420 --> 00:11:21,980
और क्या मैं यहाँ देख रहा हूँ, यह है कि
लूप के शरीर लगातार समय में चलाता है।

233
00:11:21,980 --> 00:11:24,730
इसलिए शब्दावली प्रयोग है कि
हम पहले से ही क्या about-- बात की है

234
00:11:24,730 --> 00:11:29,390
सबसे ज्यादा मामले की जाएगी
इस एल्गोरिथ्म के क्रम?

235
00:11:29,390 --> 00:11:31,050
एक दूसरा ले लो।

236
00:11:31,050 --> 00:11:34,270
पाश के भीतरी भाग
लगातार समय में चलाता है।

237
00:11:34,270 --> 00:11:37,510
और के बाहरी भाग
पाश मीटर बार चलाने के लिए जा रहा है।

238
00:11:37,510 --> 00:11:40,260
तो सबसे ज्यादा मामले क्रम यहां क्या हो रहा है?

239
00:11:40,260 --> 00:11:43,210
आप मीटर के बड़े-ओ लगता था?

240
00:11:43,210 --> 00:11:44,686
तुम सही होगा।

241
00:11:44,686 --> 00:11:46,230
>> कैसे एक दूसरे के बारे में?

242
00:11:46,230 --> 00:11:48,590
हम एक है इस बार
एक लूप के अंदर पाश।

243
00:11:48,590 --> 00:11:50,905
हम एक बाहरी पाश है
कि शून्य से पी करने के लिए चलाता है।

244
00:11:50,905 --> 00:11:54,630
और हम चलता है कि एक आंतरिक पाश
शून्य से पी करने के लिए है, और उस के अंदर,

245
00:11:54,630 --> 00:11:57,890
मैं राज्य शरीर कि
पाश निरंतर समय में चलाता है।

246
00:11:57,890 --> 00:12:02,330
तो सबसे ज्यादा मामले क्रम क्या है
कोड के इस विशेष टुकड़ा की?

247
00:12:02,330 --> 00:12:06,140
खैर, फिर से, हम एक हैं
पी बार चलता है कि बाहरी पाश।

248
00:12:06,140 --> 00:12:09,660
और प्रत्येक time-- चलना
कि पाश की, बल्कि।

249
00:12:09,660 --> 00:12:13,170
हम एक आंतरिक पाश
यह भी कहा कि पी बार चलाता है।

250
00:12:13,170 --> 00:12:16,900
उस के अंदर और फिर, वहाँ
वहाँ लगातार time-- छोटा सा टुकड़ा।

251
00:12:16,900 --> 00:12:19,890
>> हम एक बाहरी पाश है, तो यह है कि
जो की है अंदर पी बार चलाता है

252
00:12:19,890 --> 00:12:22,880
एक आंतरिक पाश कि
क्या गुना पी चलाता

253
00:12:22,880 --> 00:12:26,480
सबसे ज्यादा मामले क्रम
कोड के इस टुकड़ा की?

254
00:12:26,480 --> 00:12:30,730
आप पी के बड़े-ओ चुकता लगता था?

255
00:12:30,730 --> 00:12:31,690
>> मैं डौग लॉयड हूँ।

256
00:12:31,690 --> 00:12:33,880
इस CS50 है।

257
00:12:33,880 --> 00:12:35,622