1
00:00:00,000 --> 00:00:11,904
>> [संगीत बजाना]

2
00:00:11,904 --> 00:00:12,910
>> प्रोफेसर: ठीक है।

3
00:00:12,910 --> 00:00:16,730
इस CS50 है और यह है
सप्ताह के अंत में तीन।

4
00:00:16,730 --> 00:00:20,230
इसलिए हम आज यहाँ हो, नहीं सैंडर्स में
बजाय Weidner लाइब्रेरी में थियेटर,।

5
00:00:20,230 --> 00:00:23,170
जो के अंदर एक स्टूडियो है
हौसर स्टूडियो के रूप में जाना जाता है,

6
00:00:23,170 --> 00:00:28,310
या हम स्टूडियो एच कहते हैं, या करेगा करेगा
आपको लगता है कि मजाक का आनंद लिया, तो हम say--,

7
00:00:28,310 --> 00:00:30,540
यह वास्तव में से है
सहपाठी, मार्क, ऑनलाइन,

8
00:00:30,540 --> 00:00:32,420
जो ट्विटर के माध्यम के रूप में ज्यादा का सुझाव दिया।

9
00:00:32,420 --> 00:00:34,270
अब के बारे में क्या अच्छा है
एक स्टूडियो में यहाँ किया जा रहा है

10
00:00:34,270 --> 00:00:38,410
मैं इन हरी से घिरा रहा है कि
दीवारों, एक हरे रंग की स्क्रीन या chromakey,

11
00:00:38,410 --> 00:00:43,290
इसलिए CS50 जिसका अर्थ है कि बात करने के लिए
मेरे लिए अनजान उत्पादन टीम,

12
00:00:43,290 --> 00:00:47,380
अभी, डाल सकता है
मुझे सबसे दुनिया में कहीं भी,

13
00:00:47,380 --> 00:00:48,660
बेहतर या बदतर के लिए।

14
00:00:48,660 --> 00:00:51,800
>> अब आगे क्या, समस्या सेट निहित है
दो, इस सप्ताह के लिए अपने हाथ में है

15
00:00:51,800 --> 00:00:53,830
लेकिन समस्या के साथ सेट
तीन यह आने वाले सप्ताह,

16
00:00:53,830 --> 00:00:56,600
आप के साथ चुनौती दी जाएगी
15 की तथाकथित खेल,

17
00:00:56,600 --> 00:00:58,960
एक पुरानी पार्टी के पक्ष कि
आप प्राप्त कर याद हो सकता है

18
00:00:58,960 --> 00:01:02,030
एक पूरी गुच्छा है कि एक बच्चे के रूप में
नीचे, ऊपर स्लाइड कर सकते हैं कि संख्या की,

19
00:01:02,030 --> 00:01:05,790
छोड़ दिया और सही, और एक अंतर है
पहेली, भीतर जो में आप

20
00:01:05,790 --> 00:01:07,840
वास्तव में उन लोगों के लिए पहेली टुकड़े स्लाइड कर सकते हैं।

21
00:01:07,840 --> 00:01:11,150
अंततः आप इस प्राप्त
कुछ अर्द्ध यादृच्छिक क्रम में पहेली,

22
00:01:11,150 --> 00:01:12,940
और लक्ष्य के लिए है
नीचे से ऊपर यह तरह,

23
00:01:12,940 --> 00:01:16,310
एक से, सही करने के लिए छोड़ दिया
15 के माध्यम से सभी तरह।

24
00:01:16,310 --> 00:01:19,360
>> दुर्भाग्य से, कार्यान्वयन
आप हाथ में होगा

25
00:01:19,360 --> 00:01:21,590
सॉफ्टवेयर होने जा रहा है
आधारित है, न कि शारीरिक रूप से।

26
00:01:21,590 --> 00:01:25,280
आप वास्तव में लिखने के लिए जा रहे हैं
कोड है, जो एक छात्र या उपयोगकर्ता कर सकते हैं साथ

27
00:01:25,280 --> 00:01:26,760
15 का खेल खेलते हैं।

28
00:01:26,760 --> 00:01:29,030
और वास्तव में, हैकर में
15 के खेल के संस्करण,

29
00:01:29,030 --> 00:01:32,155
आप एक चुनौती को लागू करने के लिए हो सकता है,
इस पुराने स्कूल की नहीं सिर्फ खेल

30
00:01:32,155 --> 00:01:35,010
खेल, बल्कि सुलझाने के
इसके बारे में, भगवान मोड को लागू करने,

31
00:01:35,010 --> 00:01:38,280
तो बात है, वास्तव में है कि
मानव के लिए पहेली को हल करती है,

32
00:01:38,280 --> 00:01:41,080
संकेत के साथ प्रदान करके,
संकेत के बाद, संकेत के बाद।

33
00:01:41,080 --> 00:01:42,280
कि अगले सप्ताह पर तो और अधिक।

34
00:01:42,280 --> 00:01:43,720
लेकिन यह है कि क्या आगे झूठ है।

35
00:01:43,720 --> 00:01:47,610
>> अभी के लिए याद करते हैं कि पहले इस सप्ताह
यदि आप होगा हम इस Cliffhanger था

36
00:01:47,610 --> 00:01:52,560
जिससे हम छंटाई कर रहे थे सबसे अच्छा
बुद्धिमान एन ओ बड़ा की एक ऊपरी बाध्य किया गया था

37
00:01:52,560 --> 00:01:53,210
चुकता।

38
00:01:53,210 --> 00:01:56,520
दूसरे शब्दों में, बुलबुला तरह,
चयन प्रकार, प्रविष्टि तरह,

39
00:01:56,520 --> 00:01:59,120
उन सभी को अलग करते हुए
उनके क्रियान्वयन में,

40
00:01:59,120 --> 00:02:03,480
चल चुकता एक n में न्यागत
बहुत बुरी स्थिति में समय।

41
00:02:03,480 --> 00:02:06,010
और हम आम तौर पर मानते हैं कि
छंटाई के लिए बहुत सबसे खराब स्थिति

42
00:02:06,010 --> 00:02:08,814
एक है कि आपकी जानकारी है
पूरी तरह से पीछे हैं।

43
00:02:08,814 --> 00:02:11,980
और वास्तव में, यह काफी कुछ कदम उठाए
उन एल्गोरिदम से प्रत्येक को लागू करने के लिए।

44
00:02:11,980 --> 00:02:15,110
>> अब वर्ग के बहुत अंत में
याद है, हम बुलबुले प्रकार की तुलना

45
00:02:15,110 --> 00:02:19,390
एक दूसरे के खिलाफ चयन प्रकार के खिलाफ
कि हम समय में मर्ज प्रकार बुलाया

46
00:02:19,390 --> 00:02:22,120
और मैं इसे ले जा रहा है कि प्रस्ताव
सप्ताह से सबक का लाभ

47
00:02:22,120 --> 00:02:24,060
शून्य, फूट डालो और राज।

48
00:02:24,060 --> 00:02:28,810
और किसी भी तरह की किसी तरह की प्राप्त करने
लघुगणक अंततः समय चल रहा है,

49
00:02:28,810 --> 00:02:31,024
बजाय कुछ का
कि विशुद्ध रूप से द्विघात है।

50
00:02:31,024 --> 00:02:33,440
और यह काफी लघुगणक नहीं है
यह उस की तुलना में थोड़ा अधिक है।

51
00:02:33,440 --> 00:02:36,520
लेकिन अगर आप वर्ग से याद करते हैं,
यह बहुत तेजी से, ज्यादा था।

52
00:02:36,520 --> 00:02:38,210
हम से दूर छोड़ दिया, जहां पर एक नज़र रखना।

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> चयन बनाम बुलबुला तरह
क्रमबद्ध मर्ज प्रकार बनाम।

55
00:02:45,370 --> 00:02:47,700
अब वे सभी में चला रहे हैं,
सिद्धांत, एक ही समय में।

56
00:02:47,700 --> 00:02:50,510
सीपीयू उसी गति से चल रहा है।

57
00:02:50,510 --> 00:02:54,990
लेकिन आप कैसे उबाऊ यह महसूस कर सकते हैं
बहुत जल्दी बनने जा रहा है,

58
00:02:54,990 --> 00:02:58,790
और बस कितनी तेजी से, हम जब इंजेक्षन
सप्ताह शून्य की एल्गोरिदम का एक सा है,

59
00:02:58,790 --> 00:03:00,080
हम चीजों को गति कर सकते हैं।

60
00:03:00,080 --> 00:03:01,630
>> तो मार्क तरह अद्भुत लग रहा है।

61
00:03:01,630 --> 00:03:05,220
हम कैसे क्रम में, यह उत्तोलन कर सकते हैं
और अधिक तेजी से संख्या से सुलझाने के लिए।

62
00:03:05,220 --> 00:03:07,140
खैर की पीठ में सोचते हैं
एक घटक के लिए है कि हम

63
00:03:07,140 --> 00:03:10,380
की है कि, सप्ताह शून्य में वापस था
एक फोन बुक में किसी के लिए खोज,

64
00:03:10,380 --> 00:03:12,380
और याद है कि
हम प्रस्तावित कि स्यूडोकोड,

65
00:03:12,380 --> 00:03:14,560
जो के माध्यम से हम पा सकते हैं
माइक स्मिथ की तरह किसी को,

66
00:03:14,560 --> 00:03:16,310
इस तरह एक छोटे से कुछ देखा।

67
00:03:16,310 --> 00:03:20,820
>> अब विशेष रूप से एक नज़र रखना
लाइन में 7 और 8, और 10 और 11,

68
00:03:20,820 --> 00:03:25,240
हम रखा जिससे है, जो कि पाश प्रेरित
फिर, और फिर वापस लाइन 3 जा रहा है,

69
00:03:25,240 --> 00:03:26,520
और फिर।

70
00:03:26,520 --> 00:03:31,790
लेकिन यह हम देख सकते हैं कि पता चला है
इस एल्गोरिथ्म, यहां स्यूडोकोड में,

71
00:03:31,790 --> 00:03:33,620
अधिक समग्रता एक छोटे से।

72
00:03:33,620 --> 00:03:35,960
वास्तव में, मैं क्या देख रहा हूँ
यहाँ स्क्रीन पर,

73
00:03:35,960 --> 00:03:41,180
के लिए खोज के लिए एक एल्गोरिथ्म है
पृष्ठों में से कुछ सेट के बीच में माइक स्मिथ।

74
00:03:41,180 --> 00:03:45,520
और वास्तव में, हम इस सरल सकता
उन पंक्तियों के 7 और 8 में एल्गोरिथ्म

75
00:03:45,520 --> 00:03:49,860
और 10 और 11 बस, यह कहने के लिए
जो मैं पीले रंग में यहाँ प्रस्तुत किया है।

76
00:03:49,860 --> 00:03:52,210
दूसरे शब्दों में, यदि माइक
स्मिथ, पहले की पुस्तक में है

77
00:03:52,210 --> 00:03:55,004
हम कदम निर्दिष्ट करने की जरूरत नहीं है
कदम से अब कैसे उसे खोजने के लिए जाना।

78
00:03:55,004 --> 00:03:56,920
हम निर्दिष्ट करने के लिए नहीं है
3 लाइन करने के लिए वापस जाने के लिए,

79
00:03:56,920 --> 00:03:58,960
यही कारण है कि हम सिर्फ बजाय नहीं करते हैं,
कहते हैं, आम तौर पर,

80
00:03:58,960 --> 00:04:01,500
में माइक के लिए खोज
किताब के बाईं आधा।

81
00:04:01,500 --> 00:04:03,960
>> इसके विपरीत, माइक है यदि
वास्तव में बाद में किताब में,

82
00:04:03,960 --> 00:04:07,540
यही कारण है कि हम सिर्फ गंदें शब्द बोलना खोज बोली नहीं
पुस्तक के ठीक आधे में माइक के लिए।

83
00:04:07,540 --> 00:04:11,030
दूसरे शब्दों में, हम सिर्फ क्यों नहीं करते
एक तरह से अपने आप को कह रही करने के लिए बाज़ी,

84
00:04:11,030 --> 00:04:13,130
इस में माइक के लिए खोज
पुस्तक के सबसेट,

85
00:04:13,130 --> 00:04:16,279
और हमारे मौजूदा करने के लिए इसे छोड़ दें
एल्गोरिथ्म हमें बताने के लिए

86
00:04:16,279 --> 00:04:18,750
में माइक के लिए खोज करने के लिए कैसे
किताब के उस बाईं आधा।

87
00:04:18,750 --> 00:04:20,750
दूसरे शब्दों में, हमारे
कलन विधि यह है कि क्या काम करता है

88
00:04:20,750 --> 00:04:24,670
इस के इस मोटाई के एक फोन की किताब,
मोटाई, या किसी भी मोटाई।

89
00:04:24,670 --> 00:04:27,826
इसलिए हम बारी बारी से कर सकते हैं
इस एल्गोरिथ्म परिभाषित करते हैं।

90
00:04:27,826 --> 00:04:29,950
दूसरे शब्दों में, पर
यहाँ स्क्रीन, एक एल्गोरिथ्म है

91
00:04:29,950 --> 00:04:33,130
माइक स्मिथ के लिए खोज के लिए
एक फोन की किताब के पन्नों के बीच में।

92
00:04:33,130 --> 00:04:37,410
तो लाइन 7 और 10 में, चलो
सिर्फ वही कहना है कि।

93
00:04:37,410 --> 00:04:40,250
और मैं इस शब्द का एक पल का उपयोग
पहले, और वास्तव में, प्रत्यावर्तन

94
00:04:40,250 --> 00:04:42,450
मूलमंत्र, अब के लिए है
और यह इस प्रक्रिया है

95
00:04:42,450 --> 00:04:47,210
किसी भी तरह से चक्रीय कुछ करने का
आप पहले से ही है कि कोड का उपयोग कर,

96
00:04:47,210 --> 00:04:49,722
और इसे फिर से बुला
और फिर, और फिर।

97
00:04:49,722 --> 00:04:51,930
अब यह महत्वपूर्ण होने जा रहा है
हम किसी भी तरह नीचे कि

98
00:04:51,930 --> 00:04:53,821
बाहर है, और असीम रूप से लंबे समय तक ऐसा नहीं करते।

99
00:04:53,821 --> 00:04:56,070
अन्यथा हम करने जा रहे हैं
वास्तव में एक अनंत लूप है।

100
00:04:56,070 --> 00:04:59,810
लेकिन हम इस विचार उधार ले सकते हैं, तो चलो देखते हैं
एक प्रत्यावर्तन की, फिर कुछ कर रही है

101
00:04:59,810 --> 00:05:03,600
और फिर और फिर, हल करने के लिए
मर्ज के माध्यम से छंटाई समस्या

102
00:05:03,600 --> 00:05:05,900
तरह, सभी को और अधिक कुशलता से।

103
00:05:05,900 --> 00:05:06,970
>> इसलिए मैं आप की तरह विलय दे।

104
00:05:06,970 --> 00:05:07,920
चलो एक नज़र डालते हैं।

105
00:05:07,920 --> 00:05:10,850
तो यहाँ स्यूडोकोड साथ है
हम छँटाई लागू कर सकता है, जो

106
00:05:10,850 --> 00:05:12,640
मर्ज प्रकार नामक इस कलन विधि का उपयोग।

107
00:05:12,640 --> 00:05:13,880
और यह काफी बस इस प्रकार है।

108
00:05:13,880 --> 00:05:15,940
N तत्वों के इनपुट पर,
दूसरे शब्दों में, अगर आप कर रहे

109
00:05:15,940 --> 00:05:18,830
दिए गए n तत्वों और संख्या और
इनपुट है या जो भी पत्र,

110
00:05:18,830 --> 00:05:22,430
आप n तत्वों, यदि दी रहे हैं
2 n से कम नहीं है, बस वापसी।

111
00:05:22,430 --> 00:05:22,930
है ना?

112
00:05:22,930 --> 00:05:26,430
N कि, 2 की तुलना में कम है क्योंकि अगर
इसका मतलब है कि तत्वों की सूची

113
00:05:26,430 --> 00:05:30,446
आकार 0 या 1 के दोनों है, और
उन तुच्छ मामलों की दोनों में,

114
00:05:30,446 --> 00:05:31,570
सूची में पहले से ही हल है।

115
00:05:31,570 --> 00:05:32,810
कोई सूची नहीं है, तो यह हल है।

116
00:05:32,810 --> 00:05:35,185
और लंबाई की एक सूची है कि अगर वहाँ
1, यह स्पष्ट रूप से हल है।

117
00:05:35,185 --> 00:05:38,280
तो एल्गोरिथ्म केवल करने की जरूरत है
वास्तव में दिलचस्प कुछ करते हैं,

118
00:05:38,280 --> 00:05:40,870
हम दो या दो से अधिक है, तो
तत्वों हमें दिया।

119
00:05:40,870 --> 00:05:42,440
तो चलो फिर जादू को देखो।

120
00:05:42,440 --> 00:05:47,500
वरना तत्वों के बाईं आधे से तरह,
तब तत्वों के ठीक आधे से तरह,

121
00:05:47,500 --> 00:05:49,640
तो छाँटे गए हिस्सों विलय।

122
00:05:49,640 --> 00:05:52,440
और झुकने मन की तरह क्या है
यहाँ, मैं वास्तव में नहीं है

123
00:05:52,440 --> 00:05:56,190
तुमसे कहा है लगता है
बस अभी तक कुछ भी, है ना?

124
00:05:56,190 --> 00:05:59,560
सभी मैं, की एक सूची दी गई है कहा है
n तत्वों, बाईं आधे से सुलझाने

125
00:05:59,560 --> 00:06:01,800
तो ठीक आधे, तो
छाँटे गए हिस्सों मर्ज

126
00:06:01,800 --> 00:06:03,840
लेकिन जहां वास्तविक गुप्त सॉस है?

127
00:06:03,840 --> 00:06:05,260
एल्गोरिथ्म कहां है?

128
00:06:05,260 --> 00:06:09,150
वैसे यह उन दो पंक्तियों पता चला है कि
पहले तत्वों की तरह छोड़ दिया आधा,

129
00:06:09,150 --> 00:06:13,970
और तत्वों की तरह ठीक आधे,
पुनरावर्ती कॉल कर रहे हैं, तो बात करो।

130
00:06:13,970 --> 00:06:16,120
>> सब के बाद, इस पर
समय में बिंदु, मैं क्या है

131
00:06:16,120 --> 00:06:18,950
जिसके साथ करने के लिए एक एल्गोरिथ्म
तत्वों की एक पूरी गुच्छा तरह?

132
00:06:18,950 --> 00:06:19,450
हाँ।

133
00:06:19,450 --> 00:06:20,620
यह ठीक यहाँ है।

134
00:06:20,620 --> 00:06:25,180
यह स्क्रीन पर यहीं है, और
इसलिए मैं इस कदम की है कि एक ही सेट का उपयोग कर सकते हैं

135
00:06:25,180 --> 00:06:28,500
बाईं आधे से सुलझाने के लिए,
ठीक आधे मैं कर सकता हूँ।

136
00:06:28,500 --> 00:06:30,420
और वास्तव में, फिर से, और फिर से।

137
00:06:30,420 --> 00:06:34,210
इसलिए किसी भी तरह या अन्य, और हम जल्द ही करेंगे
मर्ज की तरह जादू यह देखना

138
00:06:34,210 --> 00:06:37,967
कि बहुत फाइनल में अंतर्निहित है
लाइन, सॉर्ट हिस्सों विलय।

139
00:06:37,967 --> 00:06:39,300
और कहा कि काफी सहज लगता है।

140
00:06:39,300 --> 00:06:41,050
तुम्हें पता है, आप दो हिस्सों लेते हैं, और
किसी भी तरह, उन्हें एक साथ विलय,

141
00:06:41,050 --> 00:06:43,260
और हम इस देखेंगे
वस्तुतः एक पल में।

142
00:06:43,260 --> 00:06:45,080
>> लेकिन यह एक पूर्ण एल्गोरिथ्म है।

143
00:06:45,080 --> 00:06:46,640
और चलो ठीक से क्यों देखते हैं।

144
00:06:46,640 --> 00:06:50,912
खैर, हम ये वही दिया हो कि लगता है
स्क्रीन पर यहां आठ तत्वों, एक

145
00:06:50,912 --> 00:06:53,120
आठ के माध्यम से, लेकिन वे कर रहे हैं
मालूम होता है यादृच्छिक क्रम में।

146
00:06:53,120 --> 00:06:55,320
और हाथ में लक्ष्य है
इन तत्वों को सॉर्ट करने के लिए।

147
00:06:55,320 --> 00:06:58,280
वैसे मुझे लगता है के बारे में कैसे जा सकते हैं
फिर, का उपयोग करते हुए यह कर रही है,

148
00:06:58,280 --> 00:07:00,407
इस स्यूडोकोड के अनुसार, तरह विलय?

149
00:07:00,407 --> 00:07:02,740
और फिर, इस जमा हुआ
अपने मन, बस एक पल के लिए।

150
00:07:02,740 --> 00:07:05,270
पहले मामले में सुंदर है
तुच्छ, यह 2 की तुलना में कम है,

151
00:07:05,270 --> 00:07:07,060
सिर्फ कुछ किए जाने की कोई काम नहीं है, वापसी।

152
00:07:07,060 --> 00:07:09,290
तो सच में सिर्फ तीन है
कदम वास्तव में मन में रखने के लिए।

153
00:07:09,290 --> 00:07:11,081
फिर, और फिर, मैं कर रहा हूँ
के लिए करना चाहते हो जा

154
00:07:11,081 --> 00:07:13,980
बाईं आधे से सुलझाने के लिए,
ठीक आधे से तरह,

155
00:07:13,980 --> 00:07:15,890
और फिर एक बार उनके
दो हिस्सों हल कर रहे हैं

156
00:07:15,890 --> 00:07:18,710
मैं उन्हें एक साथ मर्ज करना चाहते हैं
एक हल सूची में।

157
00:07:18,710 --> 00:07:19,940
इसलिए इस बात का ध्यान रखें।

158
00:07:19,940 --> 00:07:21,310
>> तो यहाँ मूल सूची है।

159
00:07:21,310 --> 00:07:23,510
चलो एक के रूप में इस का इलाज करते हैं
सरणी, हम करने के लिए शुरू के रूप में

160
00:07:23,510 --> 00:07:25,800
दो सप्ताह में, जो एक है
स्मृति से सटे ब्लॉक।

161
00:07:25,800 --> 00:07:28,480
इस मामले में, आठ से युक्त
नंबर, वापस वापस करने के लिए वापस करने के लिए।

162
00:07:28,480 --> 00:07:30,700
और चलो अब मर्ज तरह लागू होते हैं।

163
00:07:30,700 --> 00:07:33,300
तो मैं पहले सॉर्ट करना चाहते हैं
इस सूची के बाईं आधा,

164
00:07:33,300 --> 00:07:37,370
और इसलिए, चलो
4, 8, 6, और 2 पर ध्यान केंद्रित।

165
00:07:37,370 --> 00:07:41,000
>> अब मुझे लगता है के बारे में कैसे जाना है
आकार 4 की एक सूची छँटाई?

166
00:07:41,000 --> 00:07:45,990
वैसे मैं अब विचार करना है
बाईं आधे के बाईं छँटाई।

167
00:07:45,990 --> 00:07:47,720
फिर, चलो बस एक पल के लिए उल्टा करते।

168
00:07:47,720 --> 00:07:51,010
स्यूडोकोड यदि यह है कि,
और मैं आठ तत्वों दिया हूँ,

169
00:07:51,010 --> 00:07:53,230
8 स्पष्ट रूप से अधिक है
से अधिक या 2 के बराबर।

170
00:07:53,230 --> 00:07:54,980
साथ तो पहला मामला लागू नहीं होता।

171
00:07:54,980 --> 00:07:58,120
तो आठ तत्वों से तरह, जब मैं पहली बार के लिए
तत्वों की बाईं आधे से सुलझाने

172
00:07:58,120 --> 00:08:01,930
तो मैं तो मैं मर्ज ठीक आधे से सुलझाने
दो सॉर्ट हिस्सों, आकार 4 से प्रत्येक।

173
00:08:01,930 --> 00:08:02,470
ठीक।

174
00:08:02,470 --> 00:08:07,480
>> तुम सिर्फ मुझे बता दिया है लेकिन, अगर सुलझाने के
अब आकार 4 की है जो बाईं आधा,

175
00:08:07,480 --> 00:08:09,350
कैसे मैं छोड़ दिया आधे से तरह करते हैं?

176
00:08:09,350 --> 00:08:11,430
वैसे मैं एक है, तो
चार तत्वों के इनपुट,

177
00:08:11,430 --> 00:08:14,590
जब मैं पहली बार बाएं से सुलझाने
दो, तो ठीक दो,

178
00:08:14,590 --> 00:08:16,210
और फिर मैं उन्हें एक साथ विलय।

179
00:08:16,210 --> 00:08:18,700
तो फिर, यह एक सा हो जाता है
एक मन की यहाँ खेल झुकने,

180
00:08:18,700 --> 00:08:21,450
तुम क्योंकि, एक तरह से करने के लिए है
आप कहानी में हैं जहां याद है,

181
00:08:21,450 --> 00:08:23,620
लेकिन दिन के अंत में,
तत्वों की किसी भी संख्या को देखते हुए

182
00:08:23,620 --> 00:08:25,620
जब आप पहली बार सॉर्ट करना चाहते हैं
बाईं आधा, तो ठीक आधे,

183
00:08:25,620 --> 00:08:26,661
फिर उन्हें एक साथ विलय।

184
00:08:26,661 --> 00:08:28,630
ठीक है कि ऐसा करने के लिए शुरू करते हैं।

185
00:08:28,630 --> 00:08:30,170
यहाँ आठ तत्वों के इनपुट है।

186
00:08:30,170 --> 00:08:31,910
अब हम यहां बाईं आधे पर देख रहे हैं।

187
00:08:31,910 --> 00:08:33,720
कैसे मैं चार तत्वों से तरह करते हैं?

188
00:08:33,720 --> 00:08:35,610
खैर मैं पहली बार वाम आधा तरह।

189
00:08:35,610 --> 00:08:37,720
अब मैं कैसे छोड़ दिया आधे से तरह करते हैं?

190
00:08:37,720 --> 00:08:39,419
वैसे मैं दो तत्वों को देखते हुए किया गया है।

191
00:08:39,419 --> 00:08:41,240
तो चलो इन दोनों तत्वों को सॉर्ट करते हैं।

192
00:08:41,240 --> 00:08:44,540
2 या उससे अधिक
2 के बराबर, बिल्कुल।

193
00:08:44,540 --> 00:08:46,170
तो यह है कि पहले मामले पर लागू नहीं होता।

194
00:08:46,170 --> 00:08:49,010
>> इसलिए मैं अब बाएं हल करना होगा
इन दोनों तत्वों का आधा।

195
00:08:49,010 --> 00:08:50,870
बाईं आधा, ज़ाहिर है, सिर्फ 4 है।

196
00:08:50,870 --> 00:08:54,020
तो मैं कैसे एक तत्व की एक सूची तरह करते हैं?

197
00:08:54,020 --> 00:08:57,960
खैर, अब है कि विशेष आधार के मामले
शीर्ष ऊपर है, तो बात करने के लिए लागू होता है।

198
00:08:57,960 --> 00:09:01,470
1 कम से कम 2 है, और मेरे
सूची वास्तव में आकार 1 का है।

199
00:09:01,470 --> 00:09:02,747
तो मैं बस वापसी।

200
00:09:02,747 --> 00:09:03,580
मैं कुछ भी नहीं है।

201
00:09:03,580 --> 00:09:06,770
और वास्तव में, मैं क्या देखो
किया, 4 पहले से ही हल है।

202
00:09:06,770 --> 00:09:09,220
जैसा कि मैंने पहले ही कर रहा हूँ
यहां आंशिक रूप से सफल।

203
00:09:09,220 --> 00:09:11,750
>> अब जब कि बेवकूफ की तरह लगती है
दावा है, लेकिन यह सच है।

204
00:09:11,750 --> 00:09:13,700
4 आकार 1 की एक सूची है।

205
00:09:13,700 --> 00:09:15,090
यह पहले से ही हल है।

206
00:09:15,090 --> 00:09:16,270
यही कारण है कि बाएं आधा है।

207
00:09:16,270 --> 00:09:18,010
अब मैं ठीक आधे तरह।

208
00:09:18,010 --> 00:09:22,310
मेरे इनपुट 8, एक तत्व है
इसी तरह, पहले से ही सुलझा लिया।

209
00:09:22,310 --> 00:09:25,170
बेवकूफ भी है, लेकिन फिर,
इस बुनियादी सिद्धांत

210
00:09:25,170 --> 00:09:28,310
हमें अब निर्माण करने की अनुमति देने के लिए जा रहा है
इस के शीर्ष पर सफलतापूर्वक।

211
00:09:28,310 --> 00:09:32,260
4 अब, 8 हल है, हल
कि अंतिम चरण के लिए क्या था?

212
00:09:32,260 --> 00:09:35,330
तो तीसरे और अंतिम चरण के लिए, किसी भी
बार जब आप एक सूची, याद छंटाई कर रहे हैं

213
00:09:35,330 --> 00:09:38,310
दो हिस्सों विलय करने के लिए था
छोड़ दिया और सही।

214
00:09:38,310 --> 00:09:39,900
तो चलो ठीक है कि ऐसा ही करे।

215
00:09:39,900 --> 00:09:41,940
मेरी बाईं आधा, बेशक, 4 है।

216
00:09:41,940 --> 00:09:43,310
मेरे ठीक आधे 8 है।

217
00:09:43,310 --> 00:09:44,100
>> तो चलो यह करते हैं।

218
00:09:44,100 --> 00:09:46,410
पहले मैं आवंटित करने के लिए जा रहा हूँ
कुछ अतिरिक्त स्मृति,

219
00:09:46,410 --> 00:09:48,680
, मैं यहाँ का प्रतिनिधित्व करेंगे कि
सिर्फ एक माध्यमिक सरणी के रूप में,

220
00:09:48,680 --> 00:09:49,660
कि इस फिट करने के लिए काफी बड़ा है।

221
00:09:49,660 --> 00:09:52,243
लेकिन अगर आप को विस्तार देने की कल्पना कर सकते
कि आयत पूरी लंबाई,

222
00:09:52,243 --> 00:09:53,290
हम और अधिक बाद में की जरूरत है।

223
00:09:53,290 --> 00:09:58,440
मैं 4 लेने के लिए और 8, और विलय कैसे करते हैं
एक साथ आकार 1 की उन दो सूचियों?

224
00:09:58,440 --> 00:10:00,270
यहां भी, बहुत आसान है।

225
00:10:00,270 --> 00:10:03,300
4 तो पहले आता है, 8 आता है।

226
00:10:03,300 --> 00:10:07,130
मैं सॉर्ट करना चाहते हैं क्योंकि अगर
बाईं आधा, तो ठीक आधे,

227
00:10:07,130 --> 00:10:09,900
और फिर उन दो हिस्सों विलय
एक साथ, सॉर्ट क्रम में,

228
00:10:09,900 --> 00:10:11,940
4 तो पहले आता है, 8 आता है।

229
00:10:11,940 --> 00:10:15,810
>> इसलिए हम भी, प्रगति बनाने लगते हैं
मैं किसी भी वास्तविक काम नहीं किया है, हालांकि।

230
00:10:15,810 --> 00:10:17,800
हम कहानी में हैं जहां लेकिन याद रखना।

231
00:10:17,800 --> 00:10:19,360
हम मूल रूप से आठ तत्वों ले लिया।

232
00:10:19,360 --> 00:10:21,480
हम 4 है जो बाईं आधा, हल।

233
00:10:21,480 --> 00:10:24,450
तो फिर हम बाईं आधा छाँटे गए
2 था जो बाईं आधा, के।

234
00:10:24,450 --> 00:10:25,270
और अब हम चले।

235
00:10:25,270 --> 00:10:26,920
हम उस कदम के साथ कर रहे हैं।

236
00:10:26,920 --> 00:10:29,930
>> हम हल किया है, तो अगर
अब हम 2 के आधे छोड़ा

237
00:10:29,930 --> 00:10:32,130
2 के ठीक आधे हल करना होगा।

238
00:10:32,130 --> 00:10:35,710
तो 2 के ठीक आधे है
यहां इन दोनों के मूल्यों, 6 और 2।

239
00:10:35,710 --> 00:10:40,620
तो चलो अब आकार का एक इनपुट ले चलो
2, और फिर बाईं आधा सॉर्ट करें, और

240
00:10:40,620 --> 00:10:42,610
ठीक आधे, और फिर
उन्हें एक साथ विलय।

241
00:10:42,610 --> 00:10:45,722
खैर, मैं कैसे आकार की एक सूची को सॉर्ट करना
1, बस संख्या 6 से युक्त?

242
00:10:45,722 --> 00:10:46,430
मैं पहले से ही काम कर रहा हूँ।

243
00:10:46,430 --> 00:10:48,680
आकार 1 की उस सूची में हल है।

244
00:10:48,680 --> 00:10:52,140
>> मैं की एक और सूची को सॉर्ट कैसे करते हैं
आकार 1, तथाकथित सही आधा।

245
00:10:52,140 --> 00:10:54,690
वैसे यह भी है, पहले से ही हल है।

246
00:10:54,690 --> 00:10:56,190
नंबर 2 अकेली है।

247
00:10:56,190 --> 00:11:00,160
तो अब मैं दो हिस्सों है, छोड़ दिया और
ठीक है, मैं उन्हें एक साथ विलय करने की जरूरत है।

248
00:11:00,160 --> 00:11:01,800
मुझे अपने आप को कुछ अतिरिक्त जगह दे देते हैं।

249
00:11:01,800 --> 00:11:05,580
और, वहाँ में 2 डाल
फिर 6 वहाँ में, जिससे

250
00:11:05,580 --> 00:11:10,740
उस सूची छँटाई, बाएँ और दाएँ
और अंत में, यह एक साथ विलय।

251
00:11:10,740 --> 00:11:12,160
इसलिए मैं थोड़ा बेहतर स्थिति में हूँ।

252
00:11:12,160 --> 00:11:16,250
मैं, किया क्योंकि नहीं कर रहा हूँ स्पष्ट रूप से 4, 8, 2,
6 मैं चाहता हूँ कि अंतिम आदेश नहीं है।

253
00:11:16,250 --> 00:11:20,640
लेकिन मैं अब, कि आकार 2 की दो सूचियों है
दोनों क्रमशः है, हल किया गया है।

254
00:11:20,640 --> 00:11:24,580
तो अब आप अपने मन में उल्टा यदि
आंख, जहां कि हमें छोड़ दिया?

255
00:11:24,580 --> 00:11:28,520
मैं तो आठ तत्वों के साथ शुरू कर दिया मैं
4 के बाईं आधा करने के लिए नीचे whittled

256
00:11:28,520 --> 00:11:31,386
फिर 2 के बाईं आधा, और
फिर 2 के ठीक आधे,

257
00:11:31,386 --> 00:11:34,510
मैं बाईं छँटाई, इसलिए, समाप्त
2 में से आधे, और 2 के ठीक आधे,

258
00:11:34,510 --> 00:11:37,800
इसलिए तीसरे और अंतिम चरण के लिए यहां क्या हो रहा है?

259
00:11:37,800 --> 00:11:41,290
मैं एक साथ विलय करने के लिए है
आकार 2 की दो सूचियों।

260
00:11:41,290 --> 00:11:42,040
तो चलो आगे चलते हैं।

261
00:11:42,040 --> 00:11:43,940
और यहाँ स्क्रीन पर, देना
मुझे कुछ अतिरिक्त स्मृति,

262
00:11:43,940 --> 00:11:47,170
तकनीकी रूप से हालांकि, मैं कि नोटिस
खाली स्थान को शीर्ष की एक पूरी गुच्छा मिला

263
00:11:47,170 --> 00:11:47,670
क्या आप वहां मौजूद हैं।

264
00:11:47,670 --> 00:11:50,044
मैं विशेष रूप से होना चाहते हैं
कुशल अंतरिक्ष बुद्धिमान,

265
00:11:50,044 --> 00:11:52,960
मैं सिर्फ तत्वों चलती शुरू कर सकता है
आगे और पीछे, ऊपर और नीचे।

266
00:11:52,960 --> 00:11:55,460
लेकिन सिर्फ दृश्य स्पष्टता के लिए,
मैं नीचे इसे नीचे रख करने जा रहा हूँ

267
00:11:55,460 --> 00:11:56,800
अच्छा है और चीजों को साफ रखने के लिए।

268
00:11:56,800 --> 00:11:58,150
>> तो मैं आकार 2 की दो सूचियां मिल गया है।

269
00:11:58,150 --> 00:11:59,770
पहली सूची 4 और 8 है।

270
00:11:59,770 --> 00:12:01,500
दूसरी सूची 2 और 6 है।

271
00:12:01,500 --> 00:12:03,950
उन विलय
एक साथ सॉर्ट क्रम में।

272
00:12:03,950 --> 00:12:09,910
2, ज़ाहिर है, सबसे पहले आता है
फिर 4, फिर 6, तो 8।

273
00:12:09,910 --> 00:12:12,560
और अब हम हो रही हैं
कहीं दिलचस्प।

274
00:12:12,560 --> 00:12:15,720
अब मैं हल किया है, आधा
सूची, और संयोग से, यह है

275
00:12:15,720 --> 00:12:18,650
सब भी संख्या, लेकिन लगता है कि
वास्तव में, सिर्फ एक संयोग है।

276
00:12:18,650 --> 00:12:22,220
और मैं अब बाएं हल किया है
आधा, यह 2, 4, 6, और 8 इतना है कि।

277
00:12:22,220 --> 00:12:23,430
कुछ भी नहीं आदेश से बाहर है।

278
00:12:23,430 --> 00:12:24,620
यही कारण है कि प्रगति की तरह लगता है।

279
00:12:24,620 --> 00:12:26,650
>> मैं अब ऐसा लगता है
अब हमेशा के लिए बात कर रहा है,

280
00:12:26,650 --> 00:12:29,850
तो क्या हुआ अगर यह देखने की बात है
एल्गोरिथ्म वास्तव में, और अधिक कुशल है।

281
00:12:29,850 --> 00:12:31,766
लेकिन हम के माध्यम से जा रहे हैं
यह सुपर विधिपूर्वक।

282
00:12:31,766 --> 00:12:34,060
एक कंप्यूटर, ज़ाहिर है,
लगता है कि जैसे यह करना होगा।

283
00:12:34,060 --> 00:12:34,840
तो हम कहाँ हैं?

284
00:12:34,840 --> 00:12:36,180
हम आठ तत्वों के साथ शुरू कर दिया।

285
00:12:36,180 --> 00:12:37,840
मैं 4 के बाईं आधा हल।

286
00:12:37,840 --> 00:12:39,290
मुझे लगता है कि के साथ किया जा करने लगते हैं।

287
00:12:39,290 --> 00:12:42,535
तो अब अगले कदम के लिए है
4 के ठीक आधे तरह।

288
00:12:42,535 --> 00:12:44,410
और इस हिस्से हम जा सकते हैं
एक छोटे से अधिक के माध्यम से

289
00:12:44,410 --> 00:12:47,140
जल्दी से, आप कर रहे हैं, हालांकि
बस, अतीत या थामने के लिए आपका स्वागत है

290
00:12:47,140 --> 00:12:49,910
पर यह माध्यम से लगता है
अपनी गति है, लेकिन क्या

291
00:12:49,910 --> 00:12:53,290
हम अब एक अवसर के लिए है
चार पर सटीक एक ही एल्गोरिथ्म करना

292
00:12:53,290 --> 00:12:54,380
अलग नंबरों।

293
00:12:54,380 --> 00:12:57,740
>> तो चलो आगे चलते हैं, और पर ध्यान केंद्रित
हम यहाँ कर रहे हैं जो सही आधा।

294
00:12:57,740 --> 00:13:01,260
उस के बाईं आधा
सही आधा है, और अब

295
00:13:01,260 --> 00:13:04,560
बाएं के बाईं आधा
सही है कि आधे से आधे से,

296
00:13:04,560 --> 00:13:08,030
और मैं आकार की एक सूची तरह कैसे करते हैं
एक बस संख्या 1 से युक्त?

297
00:13:08,030 --> 00:13:09,030
यह पहले से हो चुका है।

298
00:13:09,030 --> 00:13:11,830
मैं एक सूची के लिए एक ही कैसे करते हो
सिर्फ 7 युक्त आकार 1 की?

299
00:13:11,830 --> 00:13:12,840
यह पहले से हो चुका है।

300
00:13:12,840 --> 00:13:16,790
तो इस आधे के लिए तीन कदम
इन दोनों तत्वों को मर्ज करने के लिए है

301
00:13:16,790 --> 00:13:20,889
आकार 2, 1 और 7 की एक नई सूची में।

302
00:13:20,889 --> 00:13:23,180
सब कुछ किया है ऐसा नहीं लगता है
लगता है कि बहुत दिलचस्प काम करते हैं।

303
00:13:23,180 --> 00:13:24,346
की अगली देखो क्या होता है।

304
00:13:24,346 --> 00:13:29,210
मैं बस के बाईं आधा छाँटे गए
अपने मूल इनपुट के ठीक आधे।

305
00:13:29,210 --> 00:13:32,360
अब देखते हैं कि सही तरह चलो
5 और 3 होता है जो आधा।

306
00:13:32,360 --> 00:13:35,740
चलो फिर से छोड़ दिया पर एक नजर डालते हैं
आधा, हल, ठीक आधे, हल,

307
00:13:35,740 --> 00:13:39,120
और, एक साथ उन दो विलय
कुछ अतिरिक्त अंतरिक्ष में,

308
00:13:39,120 --> 00:13:41,670
3 तब पहले आता है, 5 आता है।

309
00:13:41,670 --> 00:13:46,190
और अब तो, हम हल किया है
ठीक आधे के बाईं आधा

310
00:13:46,190 --> 00:13:49,420
मूल समस्या के कारण, और
ठीक आधे के ठीक आधे

311
00:13:49,420 --> 00:13:50,800
मूल समस्या की।

312
00:13:50,800 --> 00:13:52,480
तीसरे और अंतिम चरण में क्या है?

313
00:13:52,480 --> 00:13:54,854
खैर एक साथ उन दो हिस्सों विलय करने के लिए।

314
00:13:54,854 --> 00:13:57,020
तो मुझे अपने आप को कुछ मिल जाने
फिर अतिरिक्त जगह है, लेकिन, मैं

315
00:13:57,020 --> 00:13:58,699
कि खाली स्थान को शीर्ष का उपयोग हो सकता है।

316
00:13:58,699 --> 00:14:00,490
लेकिन हम रखने के लिए जा रहे हैं
नेत्रहीन यह सरल।

317
00:14:00,490 --> 00:14:07,070
मुझे अब 1 में विलय करते हैं, और
उसके बाद 3, और फिर 5, और फिर 7।

318
00:14:07,070 --> 00:14:10,740
इस प्रकार से अब मुझे छोड़कर
मूल समस्या के ठीक आधे

319
00:14:10,740 --> 00:14:12,840
कि पूरी तरह से हल है।

320
00:14:12,840 --> 00:14:13,662
>> तो क्या रहता है?

321
00:14:13,662 --> 00:14:16,120
मैं कह रहा रखने लगता है जैसे मैं
फिर, और फिर वही बातें,

322
00:14:16,120 --> 00:14:18,700
लेकिन इस बात का चिंतनशील है
हम प्रत्यावर्तन का उपयोग कर रहे हैं कि इस तथ्य।

323
00:14:18,700 --> 00:14:21,050
एक उपयोग करने की प्रक्रिया
फिर, और फिर एल्गोरिथ्म,

324
00:14:21,050 --> 00:14:23,940
के छोटे सबसेट पर
मूल समस्या है।

325
00:14:23,940 --> 00:14:27,580
इसलिए मैं अब एक छोड़ दिया हल किया है
मूल समस्या का आधा।

326
00:14:27,580 --> 00:14:30,847
मैं एक सही सॉर्ट आधा है
मूल समस्या की।

327
00:14:30,847 --> 00:14:32,180
तीसरे और अंतिम चरण के लिए क्या है?

328
00:14:32,180 --> 00:14:33,590
ओह, यह विलय है।

329
00:14:33,590 --> 00:14:34,480
तो चलो करते हैं।

330
00:14:34,480 --> 00:14:36,420
चलो कुछ अतिरिक्त आवंटन के चलो
स्मृति, लेकिन मेरे भगवान, हम

331
00:14:36,420 --> 00:14:37,503
अब इसे कहीं भी डाल सकता है।

332
00:14:37,503 --> 00:14:40,356
हम इतनी जगह उपलब्ध है
हमें करने के लिए है, लेकिन हम इसे सरल रखने देंगे।

333
00:14:40,356 --> 00:14:42,730
इसके बजाय वापस जाने का और
आगे हमारे मूल स्मृति के साथ,

334
00:14:42,730 --> 00:14:44,480
सिर्फ यह करना है चलो
नेत्रहीन यहाँ से नीचे,

335
00:14:44,480 --> 00:14:47,240
विलय को खत्म करने के लिए
बाईं आधा और सही आधा।

336
00:14:47,240 --> 00:14:49,279
>> विलय से तो, मैं क्या करने की जरूरत है?

337
00:14:49,279 --> 00:14:50,820
मैं क्रम में तत्वों लेना चाहते हैं।

338
00:14:50,820 --> 00:14:53,230
तो बाईं आधे पर देख रहे हैं,
जब मैं पहली बार नंबर 2 है देखते हैं।

339
00:14:53,230 --> 00:14:55,230
मैं ठीक आधे को देखो,
जब मैं पहली बार नंबर देख

340
00:14:55,230 --> 00:14:58,290
तो जाहिर है, जो 1
नंबर, मैं बाहर बांधना चाहते हो

341
00:14:58,290 --> 00:15:00,430
और मेरा अंतिम सूची में पहले रखा है?

342
00:15:00,430 --> 00:15:01,449
बेशक, 1।

343
00:15:01,449 --> 00:15:02,990
अब मुझे लगता है कि एक ही सवाल पूछना चाहता हूँ।

344
00:15:02,990 --> 00:15:05,040
बाईं आधे पर, मैं
अभी भी 2 नंबर मिला है।

345
00:15:05,040 --> 00:15:07,490
ठीक आधे पर,
मैं 3 नंबर मिल गया है।

346
00:15:07,490 --> 00:15:08,930
जो एक मैं चयन करने के लिए करना चाहते हैं?

347
00:15:08,930 --> 00:15:11,760
बेशक, नंबर 2 और
अब उम्मीदवारों को नोटिस

348
00:15:11,760 --> 00:15:13,620
सही पर छोड़ दिया, 3 पर 4 हैं।

349
00:15:13,620 --> 00:15:15,020
की, बेशक, 3 का चयन करते हैं।

350
00:15:15,020 --> 00:15:18,020
अब उम्मीदवारों 4 पर हैं
सही पर छोड़ दिया, 5।

351
00:15:18,020 --> 00:15:19,460
हम, ज़ाहिर है, 4 चुनें।

352
00:15:19,460 --> 00:15:21,240
सही पर छोड़ दिया, 5 पर 6।

353
00:15:21,240 --> 00:15:22,730
हम, ज़ाहिर है, 5 चुनें।

354
00:15:22,730 --> 00:15:25,020
सही पर छोड़ दिया, 7 पर 6।

355
00:15:25,020 --> 00:15:29,320
हम 6 चुनते हैं, और फिर हम
7 चुनते हैं, और फिर हम 8 चुनें।

356
00:15:29,320 --> 00:15:30,100
देखा।

357
00:15:30,100 --> 00:15:34,370
>> शब्द का तो एक बड़ी संख्या बाद में, हम
आठ तत्वों की इस सूची में हल किया है

358
00:15:34,370 --> 00:15:38,450
आठ के माध्यम से एक की एक सूची में,
कि, हर कदम के साथ बढ़ती जा रही है

359
00:15:38,450 --> 00:15:40,850
लेकिन कितना समय किया था
यह करने के लिए हमें ले।

360
00:15:40,850 --> 00:15:43,190
वैसे मैं जानबूझ कर किया है
pictorially रखी चीजें बाहर

361
00:15:43,190 --> 00:15:46,330
यहाँ, इतना है कि हम कर सकते हैं प्रकार की
देखते हैं या विभाजन की सराहना

362
00:15:46,330 --> 00:15:49,060
जीतने में है कि क्या हो रहा है।

363
00:15:49,060 --> 00:15:52,830
>> तुम्हें जगा पर वापस देखो यदि वास्तव में,
मैं इन बिंदीदार लाइनों के सभी छोड़ दिया है

364
00:15:52,830 --> 00:15:55,660
जगह धारकों में, आप कर सकते हैं,
एक तरह से, रिवर्स क्रम में, देखो,

365
00:15:55,660 --> 00:15:58,800
आप की तरह में वापस देखो
इतिहास, अब अपने मूल सूची

366
00:15:58,800 --> 00:16:00,250
आकार 8 की, ज़ाहिर है, है।

367
00:16:00,250 --> 00:16:03,480
और फिर इससे पहले, मैं था
आकार 4 की दो सूचियों के साथ व्यवहार,

368
00:16:03,480 --> 00:16:08,400
और फिर आकार 2 के चार सूचियों,
और फिर आकार 1 के आठ सूचियों।

369
00:16:08,400 --> 00:16:10,151
>> तो यह क्या करता है,
एक तरह से, की याद दिलाने?

370
00:16:10,151 --> 00:16:11,858
खैर, वास्तव में, किसी भी
हम है एल्गोरिदम

371
00:16:11,858 --> 00:16:14,430
इस प्रकार अब तक देखा जहाँ हम
विभाजन, और विभाजन है, और विभाजन है,

372
00:16:14,430 --> 00:16:19,500
फिर से बातें कर रखना, और
फिर, यह सामान्य विचार में यह परिणाम है।

373
00:16:19,500 --> 00:16:23,100
और तो कुछ भी नहीं है
लघुगणक यहाँ पर जा रहा।

374
00:16:23,100 --> 00:16:26,790
और यह n के काफी लॉग इन करें, नहीं है, लेकिन
एक लघुगणक घटक है

375
00:16:26,790 --> 00:16:28,280
हम तो बस क्या किया है करने के लिए।

376
00:16:28,280 --> 00:16:31,570
>> अब देखते हैं कि वास्तव में कैसे होता है पर विचार करते हैं।

377
00:16:31,570 --> 00:16:34,481
तो फिर, एन लॉग था
एक महान समय चल रहा है,

378
00:16:34,481 --> 00:16:36,980
हम ऐसा कुछ किया जब
द्विआधारी खोज, अब हम इसे कहते हैं,

379
00:16:36,980 --> 00:16:40,090
फूट डालो और राज रणनीति
जो के माध्यम से हम माइक स्मिथ पाया।

380
00:16:40,090 --> 00:16:41,020
अब तकनीकी रूप से।

381
00:16:41,020 --> 00:16:43,640
यही कारण है कि यहां तक ​​कि, एन लॉग आधार 2 है
सबसे गणित वर्ग में हालांकि,

382
00:16:43,640 --> 00:16:45,770
10 आम तौर पर आप को लगता है कि पसंद है।

383
00:16:45,770 --> 00:16:48,940
लेकिन कंप्यूटर वैज्ञानिकों लगभग हमेशा
और लगता है कि आधार 2 के संदर्भ में बात करते हैं,

384
00:16:48,940 --> 00:16:52,569
तो हम आम तौर पर सिर्फ लॉग कहना
एन, बजाय एन लॉग आधार 2 की,

385
00:16:52,569 --> 00:16:55,110
लेकिन वे वास्तव में एक और हो
कंप्यूटर की दुनिया में एक ही

386
00:16:55,110 --> 00:16:57,234
विज्ञान, और एक अलग रूप में,
एक निरंतर कारक भी नहीं है

387
00:16:57,234 --> 00:17:01,070
दोनों के बीच का अंतर है, तो यह है
और अधिक औपचारिक कारणों के लिए, वैसे भी मूट।

388
00:17:01,070 --> 00:17:04,520
>> लेकिन अब के लिए, हम क्या परवाह
इस बारे में उदाहरण है।

389
00:17:04,520 --> 00:17:08,520
तो चलो उदाहरण से यह साबित नहीं करते हैं, लेकिन कम से
कम से कम संख्या का एक उदाहरण का उपयोग

390
00:17:08,520 --> 00:17:10,730
हाथ में एक मानसिक स्वास्थ्य की जांच के रूप में, अगर तुम जाएगा।

391
00:17:10,730 --> 00:17:14,510
तो पहले से सूत्र लॉग आधार था
N के 2, लेकिन इस मामले में n क्या है।

392
00:17:14,510 --> 00:17:18,526
मैं n मूल नंबर था, या 8
मूल संख्या से विशेष रूप से।

393
00:17:18,526 --> 00:17:20,359
अब यह एक छोटे से हो गया है
जबकि, लेकिन मैं कर रहा हूँ सुंदर

394
00:17:20,359 --> 00:17:25,300
सुनिश्चित करें कि लॉग आधार 2
8 3 मूल्य की,

395
00:17:25,300 --> 00:17:29,630
और वास्तव में, यह है कि क्या है के बारे में अच्छा है
3 बार है कि के बिल्कुल संख्या है

396
00:17:29,630 --> 00:17:33,320
आप एक सूची में विभाजित कर सकते हैं कि
फिर, और फिर लंबाई 8 की,

397
00:17:33,320 --> 00:17:36,160
और फिर, आप छोड़ रहे हैं जब तक
सिर्फ आकार 1 की सूची के साथ।

398
00:17:36,160 --> 00:17:36,660
है ना?

399
00:17:36,660 --> 00:17:40,790
8, 4 को जाता है 2 के लिए चला जाता है,
1 के लिए चला जाता है, और वह है

400
00:17:40,790 --> 00:17:43,470
वास्तव में इस बात का चिंतनशील
तस्वीर हम सिर्फ एक क्षण पहले था।

401
00:17:43,470 --> 00:17:47,160
तो एक छोटे से विवेक के रूप में जहाँ जाँच
लघुगणक वास्तव में शामिल किया गया है।

402
00:17:47,160 --> 00:17:50,180
>> तो अब, और क्या यहाँ शामिल है? एन।

403
00:17:50,180 --> 00:17:53,440
इसलिए हर उस नोटिस
बार मैं सूची में विभाजित

404
00:17:53,440 --> 00:17:58,260
इतिहास में रिवर्स क्रम में यद्यपि
यहाँ, मैं अभी भी एन बातें कर रहा था।

405
00:17:58,260 --> 00:18:02,320
यही कारण है कि विलय के कदम आवश्यक है कि
मैं नंबरों में से हर एक को छूने

406
00:18:02,320 --> 00:18:05,060
में स्लाइड करने के लिए
इसके उचित स्थान।

407
00:18:05,060 --> 00:18:10,760
तो भले ही इस की ऊंचाई
आरेख, एन या 3 के आकार लॉग n की है

408
00:18:10,760 --> 00:18:13,860
विशेष रूप से, दूसरे शब्दों में,
मैं यहाँ तीन प्रभागों किया था।

409
00:18:13,860 --> 00:18:18,800
कितना काम मैं क्षैतिज क्या किया
इस चार्ट प्रत्येक समय के साथ?

410
00:18:18,800 --> 00:18:21,110
>> खैर, मैं के एन कदम था
मैं, क्योंकि अगर काम

411
00:18:21,110 --> 00:18:24,080
चार तत्वों और चार तत्वों मिला
और मैं उन्हें एक साथ विलय करने की जरूरत है।

412
00:18:24,080 --> 00:18:26,040
मैं के माध्यम से जाने की जरूरत है
इन चार और इन चार,

413
00:18:26,040 --> 00:18:28,123
अंततः उन्हें मर्ज करने के लिए
वापस आठ तत्वों में।

414
00:18:28,123 --> 00:18:32,182
इसके विपरीत अगर मैं आठ उंगलियों मिल गया है
मैं नहीं जानता है, जो यहां से अधिक है, और आठ

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- मैं तो
यहाँ पर चार उंगलियों मिला

416
00:18:34,390 --> 00:18:37,380
मैं चार उंगलियों करते हैं
यहाँ पर, मुझे क्या करना है, जो

417
00:18:37,380 --> 00:18:40,590
तो यह है कि एक ही है
उदाहरण के रूप में पहले, अगर मैं ऐसा

418
00:18:40,590 --> 00:18:44,010
हालांकि आठ उंगलियों
मैं एक तरह से, जो कर सकते हैं, कुल।

419
00:18:44,010 --> 00:18:47,950
मैं वास्तव में, यहां क्या कर सकते हैं
तो मैं निश्चित रूप से कर सकते हैं

420
00:18:47,950 --> 00:18:50,370
इन सूचियों के सभी विलय
एक साथ आकार 1 की।

421
00:18:50,370 --> 00:18:54,050
लेकिन मैं निश्चित रूप से देखने के लिए है
प्रत्येक तत्व में वास्तव में एक बार।

422
00:18:54,050 --> 00:18:59,640
इसलिए इस प्रक्रिया की ऊंचाई, लॉग n है
इस प्रक्रिया की चौड़ाई, तो बात है,

423
00:18:59,640 --> 00:19:02,490
तो हम क्या लगता है, n है
अंत में, है, के लिए है

424
00:19:02,490 --> 00:19:06,470
आकार n समय की एक समय चल रहा लॉग n।

425
00:19:06,470 --> 00:19:08,977
>> दूसरे शब्दों में, हम विभाजित
सूची, लॉग n बार,

426
00:19:08,977 --> 00:19:11,810
लेकिन हम किया है कि हर बार हम था
तत्वों में से हर एक को छूने के लिए

427
00:19:11,810 --> 00:19:13,560
उन्हें मर्ज करने के लिए
सब एक साथ, जो

428
00:19:13,560 --> 00:19:18,120
कदम एन, तो हम n बार लॉग n किया गया था,
या एक कंप्यूटर वैज्ञानिक रूप में कहते हैं,

429
00:19:18,120 --> 00:19:20,380
asymptotically, जो
बड़ा शब्द होगा

430
00:19:20,380 --> 00:19:22,810
ऊपरी वर्णन करने के लिए
एक समय चल रहा है पर बाध्य,

431
00:19:22,810 --> 00:19:28,010
हम एक बड़ा ओ में चल रहे हैं
लॉग n समय की है, तो बात करने के लिए।

432
00:19:28,010 --> 00:19:31,510
>> अब इस वजह से महत्वपूर्ण है,
चल रहे थे बार क्या याद

433
00:19:31,510 --> 00:19:34,120
बुलबुला तरह, और चयन के साथ
प्रकार, और सम्मिलन तरह,

434
00:19:34,120 --> 00:19:38,200
और मौजूद है कि यहां तक ​​कि कुछ अन्य लोगों,
n हम पर थे जहां था चुकता।

435
00:19:38,200 --> 00:19:39,990
और अगर आप एक तरह से, यहाँ यह देख सकते हैं।

436
00:19:39,990 --> 00:19:45,720
N चुकता है, तो जाहिर है n बार है
एन, लेकिन यहाँ हम n बार लॉग n,

437
00:19:45,720 --> 00:19:48,770
और हम पहले से ही हफ्ते से पता
शून्य, कि लॉग n, लघुगणक,

438
00:19:48,770 --> 00:19:50,550
कुछ रैखिक की तुलना में बेहतर है।

439
00:19:50,550 --> 00:19:52,930
सब के बाद, चित्र याद
लाल और पीले रंग के साथ

440
00:19:52,930 --> 00:19:56,500
हम आकर्षित किया है कि और हरे रंग की लाइनों,
हरी लघुगणक लाइन बहुत कम थी।

441
00:19:56,500 --> 00:20:00,920
और इसलिए, ज्यादा बेहतर और तेज
सीधे पीले और लाल लाइनों की तुलना में,

442
00:20:00,920 --> 00:20:05,900
n बार वास्तव में, लॉग n, बेहतर
n बार की तुलना में एन, या एन चुकता।

443
00:20:05,900 --> 00:20:09,110
>> तो हम करने लगते हैं
एक एल्गोरिथ्म मर्ज की पहचान

444
00:20:09,110 --> 00:20:11,870
क्रमबद्ध ज्यादा में चलता है कि
तेजी से समय, और वास्तव में,

445
00:20:11,870 --> 00:20:16,560
यही कारण है कि इससे पहले इस सप्ताह, जब है
हम बुलबुले के बीच कि प्रतियोगिता को देखा

446
00:20:16,560 --> 00:20:20,750
प्रकार, चयन प्रकार, और विलय
तरह, की तरह वास्तव में, वास्तव में जीता विलय।

447
00:20:20,750 --> 00:20:23,660
और वास्तव में, हम भी इंतजार नहीं किया
बुलबुला तरह और चयन प्रकार के लिए

448
00:20:23,660 --> 00:20:24,790
खत्म करने के लिए।

449
00:20:24,790 --> 00:20:27,410
>> अब हम एक दूसरे के पास ले चलो
इस पर, एक से थोड़ा अधिक से

450
00:20:27,410 --> 00:20:31,030
औपचारिक परिप्रेक्ष्य में, बस में
मामला है, इस बेहतर प्रतिध्वनित

451
00:20:31,030 --> 00:20:33,380
कि उच्च स्तर की चर्चा से।

452
00:20:33,380 --> 00:20:34,880
तो यहाँ एल्गोरिथ्म फिर से है।

453
00:20:34,880 --> 00:20:36,770
के अपने आप से पूछना,
क्या चल रहा है समय

454
00:20:36,770 --> 00:20:39,287
इस विभिन्न चरणों एल्गोरिदम का है?

455
00:20:39,287 --> 00:20:41,620
की पहली में विभाजित करते हैं
मामला है और दूसरा मामला।

456
00:20:41,620 --> 00:20:46,280
अगर मामले में अगर और कुछ,
2 n से कम है तो, सिर्फ वापसी।

457
00:20:46,280 --> 00:20:47,580
लगातार समय की तरह लगता है।

458
00:20:47,580 --> 00:20:50,970
यह दो चरणों की तरह है, एक तरह से है,
2 n से कम नहीं है, तो फिर लौट आते हैं।

459
00:20:50,970 --> 00:20:54,580
लेकिन हम सोमवार को कहा था,
लगातार समय, या 1 के ओ बड़ा,

460
00:20:54,580 --> 00:20:57,130
दो कदम, तीन हो सकता है
कदम, यहां तक ​​कि 1000 कदम।

461
00:20:57,130 --> 00:20:59,870
क्या मायने रखता है कि यह है
कदम की एक निरंतर संख्या।

462
00:20:59,870 --> 00:21:03,240
तो पीले स्यूडोकोड पर प्रकाश डाला
यहाँ, हम यह कहते हैं, में चलाता है

463
00:21:03,240 --> 00:21:04,490
लगातार समय।

464
00:21:04,490 --> 00:21:06,780
इसलिए अधिक औपचारिक रूप से, और
हम इस है-- जा रहे हैं

465
00:21:06,780 --> 00:21:09,910
हद हो जाएगा, जो हम
n के टी now-- इस अधिकार को औपचारिक रूप,

466
00:21:09,910 --> 00:21:15,030
एक समस्या का समय चल रहा है
कि, इनपुट के रूप में एन somethings लेता है

467
00:21:15,030 --> 00:21:19,150
, एक की ओ बड़ा बराबर होती है
2 n की तुलना में कम है।

468
00:21:19,150 --> 00:21:20,640
तो यह है कि उस पर सशर्त है।

469
00:21:20,640 --> 00:21:24,150
N से कम है तो, अगर स्पष्ट होना
2, हम तो एक बहुत संक्षिप्त सूची है

470
00:21:24,150 --> 00:21:29,151
n है जहां समय चल रहा है n के, टी,
1 या 0, यह बहुत ही विशेष मामले में,

471
00:21:29,151 --> 00:21:30,650
यह सिर्फ लगातार समय होने जा रहा है।

472
00:21:30,650 --> 00:21:32,691
यह एक लेने के लिए जा रहा है
, जो भी, दो कदम कदम।

473
00:21:32,691 --> 00:21:33,950
यह कदम की एक निश्चित संख्या है।

474
00:21:33,950 --> 00:21:38,840
>> तो रसदार हिस्सा निश्चित रूप में होना चाहिए
स्यूडोकोड में अन्य मामले।

475
00:21:38,840 --> 00:21:40,220
और मामले।

476
00:21:40,220 --> 00:21:44,870
तत्वों का क्रमबद्ध बाईं आधा है, की तरह सही
तत्वों के आधे सॉर्ट हिस्सों विलय।

477
00:21:44,870 --> 00:21:46,800
उन कदमों में से प्रत्येक में कितना समय लगेगा?

478
00:21:46,800 --> 00:21:49,780
खैर, तो उनका प्रदर्शन
n तत्वों को सॉर्ट करने के लिए समय

479
00:21:49,780 --> 00:21:53,010
है, के लिए यह बहुत ही फोन करते हैं
सामान्य रूप से, टी एन की,

480
00:21:53,010 --> 00:21:55,500
फिर बाईं छँटाई
तत्वों के आधे

481
00:21:55,500 --> 00:21:59,720
है, की तरह, जैसे कह रही,
2 से विभाजित n के टी,

482
00:21:59,720 --> 00:22:03,000
और इसी तरह से ठीक आधे छँटाई
तत्वों की है, की तरह, जैसे कह रही,

483
00:22:03,000 --> 00:22:06,974
N के 2 टी विभाजित है, और फिर
छाँटे गए हिस्सों विलय।

484
00:22:06,974 --> 00:22:08,890
वैसे मुझे मिल गया है, तो कुछ
यहां तत्वों की संख्या,

485
00:22:08,890 --> 00:22:11,230
चार, और कुछ नंबर की तरह
यहां तत्वों की, चार की तरह,

486
00:22:11,230 --> 00:22:14,650
और मुझे लगता है कि इन चार में से प्रत्येक को मर्ज करने के लिए है
में, और इन चार में से प्रत्येक से एक में

487
00:22:14,650 --> 00:22:17,160
दूसरे के बाद, इतना है कि
अंत में मैं आठ तत्व है।

488
00:22:17,160 --> 00:22:20,230
ऐसा लगता है कि एन कदम की ओ बड़ा है की तरह लगता है?

489
00:22:20,230 --> 00:22:23,500
मैं उंगलियों और के प्रत्येक n मिल गया है
उन्हें जगह में विलय हो गया है,

490
00:22:23,500 --> 00:22:25,270
कि एक और एन कदम की तरह है।

491
00:22:25,270 --> 00:22:27,360
>> तो वास्तव में formulaically,
हम इस व्यक्त कर सकते हैं

492
00:22:27,360 --> 00:22:29,960
पहली बार में थोड़ा scarily यद्यपि
नज़र है, लेकिन यह कुछ है

493
00:22:29,960 --> 00:22:31,600
कहा कि वास्तव में उस तर्क को दर्शाता है।

494
00:22:31,600 --> 00:22:35,710
समय चल रहा है, टी एन की, यदि n
से अधिक या 2 के बराबर है।

495
00:22:35,710 --> 00:22:42,500
इस मामले, बाकी मामले में, n के टी है
2 से विभाजित एन की, प्लस टी 2 से विभाजित,

496
00:22:42,500 --> 00:22:45,320
प्लस n के ओ बड़ा, कुछ
कदम के रैखिक संख्या,

497
00:22:45,320 --> 00:22:51,630
शायद वास्तव में एन, शायद 2 बार
एन, लेकिन यह मोटे तौर n का आदेश है।

498
00:22:51,630 --> 00:22:54,060
तो यह है कि, भी, कैसे हम कर सकते है
formulaically इस व्यक्त करते हैं।

499
00:22:54,060 --> 00:22:56,809
अब आप जब तक यह पता नहीं होता
आप अपने मन में यह दर्ज की गई है

500
00:22:56,809 --> 00:22:58,710
या में इसे देखो
वापस एक पाठ्यपुस्तक की, कि

501
00:22:58,710 --> 00:23:00,501
एक छोटे से हो सकता है
अंत में पत्रक धोखा,

502
00:23:00,501 --> 00:23:03,940
लेकिन यह वास्तव में, करने के लिए जा रहा है
n लॉग एन ओ एक बड़ा हमें दे,

503
00:23:03,940 --> 00:23:06,620
पुनरावृत्ति कि क्योंकि
आप स्क्रीन पर यहाँ देख रहे हैं

504
00:23:06,620 --> 00:23:09,550
आप वास्तव में के साथ, यह पता था कि अगर
उदाहरण के एक अनंत संख्या

505
00:23:09,550 --> 00:23:13,000
या आप formulaically यह किया है, तुम होगा
, इस देखना है कि इस फार्मूले क्योंकि

506
00:23:13,000 --> 00:23:17,100
स्वयं की टी के साथ, पुनरावर्ती है
एन सही पर कुछ खत्म हो गया,

507
00:23:17,100 --> 00:23:21,680
बाईं तरफ के ऊपर एन के टी और, यह कर सकते हैं
वास्तव में व्यक्त किया जा, अंत में,

508
00:23:21,680 --> 00:23:24,339
n लॉग एन के रूप में बड़ा जाने।

509
00:23:24,339 --> 00:23:26,130
आश्वस्त नहीं हैं, तो वह है
अब के लिए ठीक है बस

510
00:23:26,130 --> 00:23:28,960
दरअसल, वह है कि, विश्वास पर ले,
कि पुनरावृत्ति की ओर जाता है,

511
00:23:28,960 --> 00:23:31,780
लेकिन यह एक की बस थोड़ा सा अधिक है
तलाश करने के लिए गणितीय दृष्टिकोण

512
00:23:31,780 --> 00:23:36,520
मर्ज की तरह चल रहा है समय पर
अकेले अपने स्यूडोकोड पर आधारित है।

513
00:23:36,520 --> 00:23:39,030
>> अब हम एक का एक सा लग जाने
उस का सब से सांस,

514
00:23:39,030 --> 00:23:41,710
और एक पर एक नज़र रखना
कुछ पूर्व सीनेटर, कौन

515
00:23:41,710 --> 00:23:44,260
एक छोटे से परिचित लग सकता है,
जो गूगल के एरिक के साथ बैठ गया

516
00:23:44,260 --> 00:23:48,410
एक साक्षात्कार के लिए कुछ समय पहले श्मिट,
मंच पर, एक पूरी गुच्छा के सामने

517
00:23:48,410 --> 00:23:53,710
लोगों की है, अंत के बारे में बात कर रही है
एक विषय है, सुंदर है कि अब परिचित है।

518
00:23:53,710 --> 00:23:54,575
चलो एक नज़र डालते हैं।

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> एरिक श्मिट: अब सीनेटर,
आप गूगल पर कर रहे हैं यहाँ

521
00:24:03,890 --> 00:24:09,490
और मैं के बारे में सोचना पसंद
एक नौकरी के साक्षात्कार के रूप में राष्ट्रपति पद के।

522
00:24:09,490 --> 00:24:11,712
अब यह राष्ट्रपति के रूप में एक नौकरी पाने के लिए मुश्किल है।

523
00:24:11,712 --> 00:24:12,670
राष्ट्रपति ओबामा: ठीक है।

524
00:24:12,670 --> 00:24:13,940
एरिक श्मिट: और आप कर रहे हैं
अब [सुनाई] क्या करने जा रही है।

525
00:24:13,940 --> 00:24:15,523
यह गूगल पर एक नौकरी पाने के लिए भी मुश्किल है।

526
00:24:15,523 --> 00:24:17,700
राष्ट्रपति ओबामा: ठीक है।

527
00:24:17,700 --> 00:24:21,330
>> एरिक श्मिट: हम प्रश्न हैं,
और हम अपने उम्मीदवारों सवाल पूछने,

528
00:24:21,330 --> 00:24:24,310
और इस एक लैरी श्विमर से है।

529
00:24:24,310 --> 00:24:25,890
>> राष्ट्रपति ओबामा: ठीक है।

530
00:24:25,890 --> 00:24:27,005
>> एरिक श्मिट: क्या?

531
00:24:27,005 --> 00:24:28,130
तुम लोगों को मैं मजाक कर रहा हूँ लगता है?

532
00:24:28,130 --> 00:24:30,590
यह ठीक यहाँ है।

533
00:24:30,590 --> 00:24:33,490
सबसे कारगर तरीका क्या है
एक लाख 32 बिट पूर्णांक तरह?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> राष्ट्रपति ओबामा: Well--

536
00:24:38,979 --> 00:24:41,020
एरिक श्मिट: कभी कभी,
शायद मैं माफी चाहता हूँ, maybe--

537
00:24:41,020 --> 00:24:42,750
राष्ट्रपति ओबामा: नहीं, नहीं,
नहीं, नहीं, नहीं, मैं think--

538
00:24:42,750 --> 00:24:43,240
एरिक श्मिट: यह it-- नहीं है

539
00:24:43,240 --> 00:24:45,430
राष्ट्रपति ओबामा: मैं
लगता है, मैं बुलबुला लगता है

540
00:24:45,430 --> 00:24:46,875
क्रमबद्ध जाने के लिए गलत तरीका होगा।

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
एरिक श्मिट: आओ।

543
00:24:50,535 --> 00:24:52,200
कौन उसे यह बताया था?

544
00:24:52,200 --> 00:24:54,020
ठीक।

545
00:24:54,020 --> 00:24:55,590
मैं कंप्यूटर विज्ञान नहीं किया on--

546
00:24:55,590 --> 00:24:58,986
>> राष्ट्रपति ओबामा: हम है
वहाँ में हमारे जासूसों को मिला है।

547
00:24:58,986 --> 00:24:59,860
प्रोफेसर: ठीक है।

548
00:24:59,860 --> 00:25:03,370
चलो अब हमारे पीछे छोड़ दो
एल्गोरिदम के सैद्धांतिक दुनिया

549
00:25:03,370 --> 00:25:06,520
asymptotic विश्लेषण में
क्या है, और कुछ विषयों पर लौटने

550
00:25:06,520 --> 00:25:09,940
सप्ताह शून्य और एक है, और शुरू से ही
कुछ प्रशिक्षण के पहियों को दूर करने के लिए,

551
00:25:09,940 --> 00:25:10,450
अगर आप करें तो।

552
00:25:10,450 --> 00:25:13,241
आप वास्तव में समझ सकें
अंततः जमीन से, क्या है

553
00:25:13,241 --> 00:25:16,805
, जब आप हुड के नीचे चल रहा है
लिखते हैं, संकलन, और कार्यक्रमों पर अमल।

554
00:25:16,805 --> 00:25:19,680
यह था कि, विशेष रूप में याद करते हैं
हम पर देखा पहली सी कार्यक्रम,

555
00:25:19,680 --> 00:25:22,840
एक विहित, सरल कार्यक्रम
एक तरह की, अपेक्षाकृत बोल,

556
00:25:22,840 --> 00:25:24,620
जिसमें, यह नमस्ते विश्व प्रिंट।

557
00:25:24,620 --> 00:25:27,610
और मैं इस प्रक्रिया ने कहा, याद है कि
उस स्रोत कोड के माध्यम से चला जाता है

558
00:25:27,610 --> 00:25:28,430
वास्तव में यह है।

559
00:25:28,430 --> 00:25:31,180
आप अपने स्रोत कोड ले, पारित
यह एक संकलक के माध्यम से, बजना जैसे,

560
00:25:31,180 --> 00:25:34,650
और बाहर, कि वस्तु कोड आता है
इस, शून्य और लोगों की तरह लग सकता है

561
00:25:34,650 --> 00:25:37,880
कंप्यूटर का सीपीयू, केंद्रीय कि
प्रोसेसिंग यूनिट या मस्तिष्क,

562
00:25:37,880 --> 00:25:39,760
अंततः समझता है।

563
00:25:39,760 --> 00:25:42,460
>> ऐसा लगता है कि एक है कि पता चला है
एक अति सरलीकरण का एक सा है,

564
00:25:42,460 --> 00:25:44,480
हम एक में अब कर रहे हैं कि
स्थिति के अलावा तंग करने के लिए

565
00:25:44,480 --> 00:25:46,720
सच हो गया है समझने के लिए क्या
हुड के नीचे चल रहा है

566
00:25:46,720 --> 00:25:48,600
आप चलाने के लिए हर समय
बजना, या अधिक आम तौर पर,

567
00:25:48,600 --> 00:25:53,040
हर बार जब आप एक कार्यक्रम बनाना
बनाओ और सीएफ 50 आईडीई का उपयोग कर।

568
00:25:53,040 --> 00:25:56,760
विशेष रूप से, सामान की तरह
यह पहली उत्पन्न होता है,

569
00:25:56,760 --> 00:25:58,684
जब आप पहली बार अपने कार्यक्रम संकलन।

570
00:25:58,684 --> 00:26:00,600
दूसरे शब्दों में, जब आप
अपने स्रोत कोड ले

571
00:26:00,600 --> 00:26:04,390
और क्या पहली बार है, यह संकलन
बजना द्वारा outputted जा रहा है

572
00:26:04,390 --> 00:26:06,370
विधानसभा कोड के रूप में जाना जाता है कुछ है।

573
00:26:06,370 --> 00:26:08,990
और वास्तव में, यह वास्तव में इस तरह दिखता है।

574
00:26:08,990 --> 00:26:11,170
>> मैं एक आदेश भागा
पहले कमांड लाइन।

575
00:26:11,170 --> 00:26:16,260
बजना पानी का छींटा राजधानी एस hello.c,
और यह एक फ़ाइल बनाया

576
00:26:16,260 --> 00:26:19,490
मुझे बुलाया hello.s के लिए,
जो के अंदर वास्तव में थे

577
00:26:19,490 --> 00:26:22,290
इन सामग्री, और एक छोटे से अधिक
ऊपर और अधिक नीचे एक छोटे से,

578
00:26:22,290 --> 00:26:25,080
लेकिन मैं juiciest रख दिया है
यहाँ स्क्रीन पर जानकारी।

579
00:26:25,080 --> 00:26:29,190
तुम करीब से देखो, तो आप देखेंगे
कम से कम कुछ परिचित खोजशब्दों।

580
00:26:29,190 --> 00:26:31,330
हम शीर्ष पर मुख्य है।

581
00:26:31,330 --> 00:26:35,140
हम बीच में नीचे printf है।

582
00:26:35,140 --> 00:26:38,670
और हम भी दुनिया नमस्कार है
नीचे नीचे उद्धरण में बैकस्लैश एन।

583
00:26:38,670 --> 00:26:42,450
>> यहाँ में और बाकी सब कुछ
बहुत कम स्तर निर्देश है

584
00:26:42,450 --> 00:26:45,500
कंप्यूटर का सीपीयू को समझता है कि।

585
00:26:45,500 --> 00:26:50,090
स्मृति कदम है कि सीपीयू निर्देश
चारों ओर, स्मृति से है कि लोड तार,

586
00:26:50,090 --> 00:26:52,750
और अंत में, प्रिंट
स्क्रीन पर बातें।

587
00:26:52,750 --> 00:26:56,780
अब क्या करने के बाद हालांकि होता
इस विधानसभा कोड उत्पन्न होता है?

588
00:26:56,780 --> 00:26:59,964
अंत में, आप वास्तव में, करते हैं,
अभी भी वस्तु कोड उत्पन्न करते हैं।

589
00:26:59,964 --> 00:27:02,630
लेकिन कदम वास्तव में है कि
हुड के नीचे चल रहा

590
00:27:02,630 --> 00:27:04,180
इस तरह एक छोटे से अधिक लग रही है।

591
00:27:04,180 --> 00:27:08,390
स्रोत कोड, विधानसभा कोड हो जाता है
जो तब ऑब्जेक्ट कोड हो जाता है,

592
00:27:08,390 --> 00:27:11,930
और यहाँ ऑपरेटिव शब्द हैं, कि
आप अपने स्रोत कोड संकलन करते हैं,

593
00:27:11,930 --> 00:27:16,300
बाहर तो विधानसभा कोड, और आता है
आप अपने विधानसभा कोड को इकट्ठा करते हैं,

594
00:27:16,300 --> 00:27:17,800
बाहर ऑब्जेक्ट कोड आता है।

595
00:27:17,800 --> 00:27:20,360
>> अब बजना, सुपर परिष्कृत है
compilers के एक बहुत पसंद है,

596
00:27:20,360 --> 00:27:23,151
और यह इन चरणों के सभी करता है
एक साथ, और यह जरूरी नहीं

597
00:27:23,151 --> 00:27:25,360
उत्पादन किसी भी मध्यवर्ती
आप भी देख सकते हैं कि फ़ाइलों।

598
00:27:25,360 --> 00:27:28,400
यह सिर्फ बातें compiles,
जो सामान्य शब्द है कि

599
00:27:28,400 --> 00:27:30,000
इस पूरी प्रक्रिया का वर्णन करता है।

600
00:27:30,000 --> 00:27:32,000
लेकिन क्या आप वास्तव में चाहते हैं
विशेष रूप से होना करने के लिए नहीं है,

601
00:27:32,000 --> 00:27:34,330
एक बहुत अधिक के रूप में अच्छी तरह से वहाँ चल रहा है।

602
00:27:34,330 --> 00:27:38,860
>> लेकिन हम यह भी है कि अब भी विचार करते हैं
कि सुपर सरल कार्यक्रम, hello.c,

603
00:27:38,860 --> 00:27:40,540
एक समारोह में कहा जाता है।

604
00:27:40,540 --> 00:27:41,870
यह printf बुलाया।

605
00:27:41,870 --> 00:27:46,900
लेकिन मुझे लगता है, वास्तव में, printf नहीं लिखा था
तो यह है कि बात करने के लिए, ग के साथ आता है।

606
00:27:46,900 --> 00:27:51,139
ऐसा लगता है कि एक समारोह में याद करते है
मानक io.h, में जो घोषणा की

607
00:27:51,139 --> 00:27:53,180
एक हेडर फाइल है, जो
एक विषय है कि हम वास्तव में जाएगा

608
00:27:53,180 --> 00:27:55,780
लंबे समय से पहले और अधिक गहराई में गोता।

609
00:27:55,780 --> 00:27:58,000
लेकिन एक हेडर फाइल है
आम तौर पर साथ

610
00:27:58,000 --> 00:28:02,920
एक कोड फ़ाइल, स्रोत कोड फ़ाइल है, तो द्वारा
मानक io.h. वहाँ मौजूद बहुत पसंद है

611
00:28:02,920 --> 00:28:05,930
>> कुछ समय पहले, किसी को,
या किसी भी लिखा था

612
00:28:05,930 --> 00:28:11,040
में, मानक io.c नामक एक फाइल
जो वास्तविक परिभाषा,

613
00:28:11,040 --> 00:28:15,220
या printf के कार्यान्वयन,
और अन्य कार्यों के गुच्छों,

614
00:28:15,220 --> 00:28:16,870
वास्तव में लिखा जाता है।

615
00:28:16,870 --> 00:28:22,140
हम होने पर विचार करें तो, अगर यह देखते हुए कि
यहाँ छोड़ दिया, hello.c पर, जब कि

616
00:28:22,140 --> 00:28:26,250
संकलित, भले ही, hello.s हमें देता है
बजना एक जगह में बचत परेशान नहीं करता है

617
00:28:26,250 --> 00:28:31,360
हम यह देखते हैं, और कहा कि विधानसभा कोड कर सकते हैं
hello.o, में इकट्ठे हो जाता है जो

618
00:28:31,360 --> 00:28:34,630
वास्तव में, डिफ़ॉल्ट नाम है
आप स्रोत संकलन जब भी दी

619
00:28:34,630 --> 00:28:39,350
वस्तु कोड में कोड, लेकिन नहीं कर रहे हैं
अभी तक इसे लागू करने के लिए पूरी तरह से तैयार,

620
00:28:39,350 --> 00:28:41,460
एक और कदम है क्योंकि
ऐसा करने के लिए है, और है

621
00:28:41,460 --> 00:28:44,440
पिछले कुछ के लिए हो रहा
सप्ताह, आप शायद अनजान।

622
00:28:44,440 --> 00:28:47,290
>> विशेष रूप से कहीं न कहीं
CS50 आईडीई में है, और यह,

623
00:28:47,290 --> 00:28:49,870
भी, एक की एक सा हो जाएगा
एक पल के लिए अति सरलीकरण,

624
00:28:49,870 --> 00:28:54,670
वहाँ है, या एक समय पर था,
मानक io.c नामक एक फाइल,

625
00:28:54,670 --> 00:28:58,440
किसी में संकलित किया है कि
मानक io.s या समकक्ष,

626
00:28:58,440 --> 00:29:02,010
किसी को तो इकट्ठे कि
मानक io.o में,

627
00:29:02,010 --> 00:29:04,600
या यह एक में पता चला है
थोड़ा अलग फ़ाइल

628
00:29:04,600 --> 00:29:07,220
एक अलग हो सकता है कि प्रारूप
कुल मिलाकर फ़ाइल एक्सटेंशन,

629
00:29:07,220 --> 00:29:11,720
सिद्धांत और धारणात्मक, वास्तव में, लेकिन
उन कदमों किसी न किसी रूप में तो होना ही था।

630
00:29:11,720 --> 00:29:14,060
कहते हैं, कि अब के लिए है जो
मैं एक कार्यक्रम लिख रहा हूँ, जब

631
00:29:14,060 --> 00:29:17,870
hello.c, बस का कहना है कि, दुनिया नमस्ते,
और मैं किसी और के कोड का उपयोग कर रहा हूँ

632
00:29:17,870 --> 00:29:22,480
एक पर एक बार गया था, जो printf की तरह
समय, मानक io.c नामक एक फाइल में,

633
00:29:22,480 --> 00:29:26,390
फिर किसी भी तरह मैं अपने लेने के लिए है
ऑब्जेक्ट कोड, मेरे शून्य और लोगों,

634
00:29:26,390 --> 00:29:29,260
और उस व्यक्ति की वस्तु
कोड, या शून्य और लोगों,

635
00:29:29,260 --> 00:29:34,970
और किसी भी तरह में उन्हें एक साथ लिंक
कि, हैलो कहा जाता है एक अंतिम फ़ाइल,

636
00:29:34,970 --> 00:29:38,070
है शून्य के सभी और
मेरी मुख्य समारोह से लोगों को,

637
00:29:38,070 --> 00:29:40,830
और शून्य के सभी
और printf के लिए लोगों को।

638
00:29:40,830 --> 00:29:44,900
>> और वास्तव में, कि अंतिम प्रक्रिया है
कहा जाता है, अपने उद्देश्य कोड जोड़ने।

639
00:29:44,900 --> 00:29:47,490
जिनमें से उत्पादन
एक निष्पादन योग्य फ़ाइल है।

640
00:29:47,490 --> 00:29:49,780
तो निष्पक्षता में, पर
दिन, कुछ भी नहीं के अंत

641
00:29:49,780 --> 00:29:52,660
एक सप्ताह के बाद से बदल गया है, जब हम
पहले कार्यक्रम के संकलन शुरू कर दिया।

642
00:29:52,660 --> 00:29:55,200
दरअसल, यह सब किया गया है
हुड के नीचे हो रहा है,

643
00:29:55,200 --> 00:29:57,241
लेकिन अब हम एक स्थिति में हैं
जहां हम वास्तव में कर सकते हैं

644
00:29:57,241 --> 00:29:58,794
इन विभिन्न चरणों के अलावा तंग।

645
00:29:58,794 --> 00:30:00,710
और वास्तव में, अंत में
दिन की है, हम अब भी कर रहे

646
00:30:00,710 --> 00:30:04,480
शून्य और लोगों के साथ छोड़ दिया है जो
एक महान segue अब वास्तव में है

647
00:30:04,480 --> 00:30:08,620
सी का एक और क्षमता के लिए, कि
हम सबसे अधिक संभावना का लाभ उठाने के लिए नहीं किया है

648
00:30:08,620 --> 00:30:11,250
आज तक, बिटवाइस ऑपरेटरों के रूप में जाना जाता है।

649
00:30:11,250 --> 00:30:15,220
दूसरे शब्दों में, इस प्रकार अब तक, कभी भी हम है
सी में सी या चर में डेटा के साथ निपटा,

650
00:30:15,220 --> 00:30:17,660
हम की तरह चीजों को मिला है
वर्ण और मंगाई और भारतीय नौसेना पोत

651
00:30:17,660 --> 00:30:21,990
और चाहता और युगल और पसंद है, लेकिन
उन सभी के कम से कम आठ टुकड़े कर रहे हैं।

652
00:30:21,990 --> 00:30:25,550
हम अभी तक करने में सक्षम नहीं किया गया है
व्यक्तिगत बिट्स हेरफेर,

653
00:30:25,550 --> 00:30:28,970
यहां तक ​​कि एक व्यक्ति बिट हालांकि, हम
एक 0 और 1 का प्रतिनिधित्व कर सकते हैं।

654
00:30:28,970 --> 00:30:32,640
अब यह सी में पता चला है कि, आप
व्यक्तिगत बिट्स के लिए उपयोग हो सकता है,

655
00:30:32,640 --> 00:30:35,530
आप वाक्य रचना अगर तुम्हें पता है,
जो के साथ उन पर पाने के लिए।

656
00:30:35,530 --> 00:30:38,010
>> तो चलो एक नजर डालते हैं
बिटवाइस ऑपरेटरों पर।

657
00:30:38,010 --> 00:30:41,700
तो यहाँ चित्र में कुछ प्रतीक हैं कि
हम, की तरह है, की तरह, पहले देखा है।

658
00:30:41,700 --> 00:30:45,580
मैं एक खड़ी एक एम्परसेंड देखना
बार, और साथ ही कुछ अन्य लोगों,

659
00:30:45,580 --> 00:30:49,430
और कहा कि एम्परसेंड एम्परसेंड याद
हम पहले देखा है कुछ है।

660
00:30:49,430 --> 00:30:54,060
तुम्हारे पास है, जहां तार्किक और ऑपरेटर
उनमें से दो को एक साथ, या तार्किक या

661
00:30:54,060 --> 00:30:56,300
ऑपरेटर, जहां आप
दो खड़ी सलाखों है।

662
00:30:56,300 --> 00:31:00,550
बिटवाइस ऑपरेटरों, जो हम करेंगे
व्यक्तिगत रूप से बिट्स पर काम देखना

663
00:31:00,550 --> 00:31:03,810
सिर्फ एक ही एम्परसेंड का उपयोग करें, एक
एकल खड़ी बार, कैरट प्रतीक

664
00:31:03,810 --> 00:31:06,620
अगले, छोटी सी बात आती है
टिल्ड, और फिर छोड़ दिया

665
00:31:06,620 --> 00:31:08,990
ब्रैकेट ब्रैकेट छोड़ दिया है, या
सही ब्रैकेट सही ब्रैकेट।

666
00:31:08,990 --> 00:31:10,770
इनमें से प्रत्येक अलग अलग अर्थ है।

667
00:31:10,770 --> 00:31:11,950
>> वास्तव में, एक नजर डालते हैं।

668
00:31:11,950 --> 00:31:16,560
के पुराने स्कूल आज, और उपयोग चलते हैं
पहल साल से एक टच स्क्रीन,

669
00:31:16,560 --> 00:31:18,002
एक सफेद बोर्ड के रूप में जाना जाता है।

670
00:31:18,002 --> 00:31:19,710
और इस सफेद बोर्ड
हमें अनुमति देने के लिए जा रहा है

671
00:31:19,710 --> 00:31:27,360
कुछ काफी सरल प्रतीकों को व्यक्त करने के लिए,
या यों कहें कि कुछ काफी सरल सूत्र,

672
00:31:27,360 --> 00:31:29,560
कि हम अंततः तो कर सकते हैं
का लाभ उठाने, क्रम में

673
00:31:29,560 --> 00:31:33,230
व्यक्तिगत उपयोग करने के लिए
एक सी कार्यक्रम के भीतर बिट्स।

674
00:31:33,230 --> 00:31:34,480
दूसरे शब्दों में, चलो यह करते हैं।

675
00:31:34,480 --> 00:31:37,080
एक के लिए चलो पहले बात
एम्परसेंड के बारे में पल,

676
00:31:37,080 --> 00:31:39,560
जो बिटवाइस और ऑपरेटर है।

677
00:31:39,560 --> 00:31:42,130
दूसरे शब्दों में, यह है
अनुमति देता है कि एक ऑपरेटर

678
00:31:42,130 --> 00:31:45,930
मुझे एक बाएं हाथ चर राशि के लिए
आम तौर पर, और एक दाएँ हाथ चर,

679
00:31:45,930 --> 00:31:50,640
या एक व्यक्ति के मूल्य, कि यदि हम और
उन्हें एक साथ, मुझे एक अंतिम परिणाम देता है।

680
00:31:50,640 --> 00:31:51,560
तो मैं क्या मतलब है?

681
00:31:51,560 --> 00:31:54,840
एक कार्यक्रम में, आप एक चर है, तो
इन मूल्यों की दुकानों से एक है कि,

682
00:31:54,840 --> 00:31:58,000
या सरल रखने के लिए, और सिर्फ दो
व्यक्तिगत रूप से शून्य और लोगों को लिखने,

683
00:31:58,000 --> 00:32:00,940
एम्परसेंड ऑपरेटर कैसे काम करता है।

684
00:32:00,940 --> 00:32:06,400
0 एम्परसेंड 0 0 बराबर करने के लिए जा रहा है।

685
00:32:06,400 --> 00:32:07,210
अब ऐसा क्यों है?

686
00:32:07,210 --> 00:32:09,291
>> यह करने के लिए समान है
बूलियन अभिव्यक्ति,

687
00:32:09,291 --> 00:32:10,540
कि हम इस प्रकार अब तक चर्चा की है।

688
00:32:10,540 --> 00:32:15,800
तुम सब के बाद लगता है, 0 है
झूठी, 0, झूठी झूठी और गलत है

689
00:32:15,800 --> 00:32:18,720
हम चर्चा की है, के रूप में है
तार्किक रूप से, यह भी गलत।

690
00:32:18,720 --> 00:32:20,270
इसलिए हम के रूप में अच्छी तरह से 0 यहाँ मिलता है।

691
00:32:20,270 --> 00:32:24,390
आप 0 एम्परसेंड लेते हैं
1, अच्छा है कि, भी,

692
00:32:24,390 --> 00:32:29,890
क्योंकि इस के लिए, 0 होने जा रहा है
बाएं हाथ की अभिव्यक्ति, सच है या एक होने के लिए

693
00:32:29,890 --> 00:32:32,360
यह सच है और सच करने के लिए की आवश्यकता होगी।

694
00:32:32,360 --> 00:32:36,320
लेकिन यहाँ हम झूठे हैं
और यह सच है, या 0 और 1।

695
00:32:36,320 --> 00:32:42,000
अब फिर से, हम एक एम्परसेंड है तो
0, भी, 0 होने जा रहा है कि,

696
00:32:42,000 --> 00:32:47,240
और हम एक एम्परसेंड एक है,
अंत में हम एक एक सा है।

697
00:32:47,240 --> 00:32:50,340
दूसरे शब्दों में, हम नहीं कर रहे हैं
इस ऑपरेटर के साथ कुछ रोचक

698
00:32:50,340 --> 00:32:51,850
बस अभी तक, यह एम्परसेंड ऑपरेटर।

699
00:32:51,850 --> 00:32:53,780
यह बिटवाइस और संचालक।

700
00:32:53,780 --> 00:32:57,290
लेकिन इन तत्व हैं
जो के माध्यम से हम क्या कर सकते हैं

701
00:32:57,290 --> 00:32:59,240
हम जल्द ही देखेंगे के रूप में दिलचस्प बातें।

702
00:32:59,240 --> 00:33:02,790
>> अब हम सिर्फ एक को देखो
यहाँ सही पर पर खड़ी बार।

703
00:33:02,790 --> 00:33:06,710
मैं एक 0 सा है और अगर मैं
या इसके साथ, बिटवाइस

704
00:33:06,710 --> 00:33:11,030
या ऑपरेटर, एक और शून्य सा है,
कि मुझे 0 देने के लिए जा रहा है।

705
00:33:11,030 --> 00:33:17,540
मैं एक 0 बिट और या यह अपने साथ ले तो
एक एक सा है, तो मैं एक पाने के लिए जा रहा हूँ।

706
00:33:17,540 --> 00:33:19,830
और वास्तव में, बस के लिए
स्पष्टता, मुझे वापस जाओ

707
00:33:19,830 --> 00:33:23,380
इतना है कि मेरी ऊर्ध्वाधर सलाखों
1 के लिए गलत नहीं कर रहे हैं।

708
00:33:23,380 --> 00:33:26,560
मुझे के सभी फिर से लिखना
मेरी एक एक छोटे से अधिक है

709
00:33:26,560 --> 00:33:32,700
मैं जाहिर है, अगर इतना है कि हम अगले देखते हैं,
1 या 0, कि एक एक होने जा रहा है है,

710
00:33:32,700 --> 00:33:39,060
और मैं 1 या 1 है कि एक है,
भी, एक एक होने जा रहा है।

711
00:33:39,060 --> 00:33:42,900
तो अगर आप तार्किक रूप से देखते हैं कि या जा सकता है
ऑपरेटर बहुत अलग ढंग से व्यवहार करता है।

712
00:33:42,900 --> 00:33:48,070
, इस 0 मुझे देता है या 0 मुझे 0 देता है, लेकिन
हर दूसरे संयोजन मुझे एक देता है।

713
00:33:48,070 --> 00:33:52,480
इतने लंबे समय मैं में एक 1 के रूप में
सूत्र, परिणाम एक होने जा रहा है।

714
00:33:52,480 --> 00:33:55,580
>> और इसी के साथ इसके विपरीत
ऑपरेटर, ampersand

715
00:33:55,580 --> 00:34:00,940
मैं में दो 1 तभी
समीकरण, मैं वास्तव में एक एक बाहर मिलता है।

716
00:34:00,940 --> 00:34:02,850
अब कुछ अन्य वहाँ
ऑपरेटर के रूप में अच्छी तरह से।

717
00:34:02,850 --> 00:34:04,810
उनमें से एक एक छोटे से अधिक शामिल है।

718
00:34:04,810 --> 00:34:07,980
तो मुझे आगे जाना है और मिटा दें
यह कुछ स्थान खाली करने के लिए।

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
और चलो पर एक नजर डालते हैं
बस एक पल के लिए कैरट प्रतीक,।

721
00:34:16,460 --> 00:34:18,210
यह आमतौर पर एक है
चरित्र आप टाइप कर सकते हैं

722
00:34:18,210 --> 00:34:21,420
अपने कीबोर्ड पकड़े शिफ्ट पर और
अपने अमेरिका के ऊपर संख्या में फिर से एक

723
00:34:21,420 --> 00:34:22,250
कुंजीपटल।

724
00:34:22,250 --> 00:34:26,190
>> तो यह विशेष है
या ऑपरेटर, अनन्य या।

725
00:34:26,190 --> 00:34:27,790
तो हम बस या ऑपरेटर देखा।

726
00:34:27,790 --> 00:34:29,348
इस अनन्य या ऑपरेटर है।

727
00:34:29,348 --> 00:34:30,639
वास्तव में क्या अंतर है?

728
00:34:30,639 --> 00:34:34,570
खैर चलो बस सूत्र को देखो,
और अंततः सामग्री के रूप में इस का उपयोग करें।

729
00:34:34,570 --> 00:34:37,690
0 XOR 0।

730
00:34:37,690 --> 00:34:39,650
मैं कहने जा रहा हूँ हमेशा 0 है।

731
00:34:39,650 --> 00:34:41,400
यही कारण है कि XOR की परिभाषा है।

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 1 होने जा रहा है।

733
00:34:47,104 --> 00:34:58,810
1 XOR 0, 1 होने जा रहा है
और एक XOR एक होने जा रहा है?

734
00:34:58,810 --> 00:34:59,890
गलत?

735
00:34:59,890 --> 00:35:00,520
या सुधारना?

736
00:35:00,520 --> 00:35:01,860
मुझे नहीं पता।

737
00:35:01,860 --> 00:35:02,810
0।

738
00:35:02,810 --> 00:35:04,700
अब यहाँ क्या हो रहा है?

739
00:35:04,700 --> 00:35:06,630
खैर के बारे में सोचते
इस ऑपरेटर का नाम।

740
00:35:06,630 --> 00:35:09,980
विशेष या, इतनी के रूप में
नाम, एक तरह से पता चलता है,

741
00:35:09,980 --> 00:35:13,940
जवाब केवल होने जा रहा है
एक 1 आदानों विशेष कर रहे हैं,

742
00:35:13,940 --> 00:35:15,560
विशेष रूप से अलग है।

743
00:35:15,560 --> 00:35:18,170
तो यहाँ निवेश कर रहे हैं
एक ही है, इसलिए उत्पादन 0 है।

744
00:35:18,170 --> 00:35:20,700
यहां निवेश कर रहे हैं
एक ही है, इसलिए उत्पादन 0 है।

745
00:35:20,700 --> 00:35:25,640
यहाँ outputs के वे अलग हैं, कर रहे हैं
अनन्य हैं, और इसलिए उत्पादन 1 है।

746
00:35:25,640 --> 00:35:28,190
तो यह करने के लिए समान है
और, यह बहुत समान है

747
00:35:28,190 --> 00:35:32,760
या यों कहें कि यह करने के लिए समान है
या, लेकिन केवल एक विशेष तरीके से।

748
00:35:32,760 --> 00:35:36,210
यह एक, अब एक एक है
हम दो एक के लिए है, क्योंकि

749
00:35:36,210 --> 00:35:38,621
और विशेष रूप से नहीं है, उनमें से सिर्फ एक।

750
00:35:38,621 --> 00:35:39,120
ठीक है।

751
00:35:39,120 --> 00:35:40,080
दूसरोँ का क्या?

752
00:35:40,080 --> 00:35:44,220
खैर टिल्ड, इस बीच, है
वास्तव में अच्छा और सरल है, शुक्र है।

753
00:35:44,220 --> 00:35:46,410
और यह एक एकल है
जिसका मतलब है कि ऑपरेटर,

754
00:35:46,410 --> 00:35:50,400
यह केवल एक इनपुट के लिए आवेदन किया है
एक संकार्य, तो बात करो।

755
00:35:50,400 --> 00:35:51,800
नहीं, एक को छोड़ दिया और एक सही करने के लिए।

756
00:35:51,800 --> 00:35:56,050
दूसरे शब्दों में, आप में से टिल्ड लेते हैं
0, जवाब विपरीत होगा।

757
00:35:56,050 --> 00:35:59,710
और तुम 1 के टिल्ड लेते हैं,
जवाब विपरीत हो जाएगा।

758
00:35:59,710 --> 00:36:02,570
तो टिल्ड ऑपरेटर है
एक सा नकार का एक तरीका है,

759
00:36:02,570 --> 00:36:06,000
या से थोड़ा flipping
0-1, या 1-0।

760
00:36:06,000 --> 00:36:09,820
>> और कहा कि अंत में हमें छोड़ देता है
सिर्फ दो अंतिम ऑपरेटरों के साथ,

761
00:36:09,820 --> 00:36:13,840
बाएं पारी तथाकथित, और
सही बदलाव ऑपरेटर तथाकथित।

762
00:36:13,840 --> 00:36:16,620
के कैसे उन काम पर एक नज़र रखना।

763
00:36:16,620 --> 00:36:20,780
लिखित छोड़ बदलाव ऑपरेटर,
लगता है कि जैसे दो कोण कोष्ठक के साथ,

764
00:36:20,780 --> 00:36:22,110
इस प्रकार के रूप में संचालित।

765
00:36:22,110 --> 00:36:27,390
तो बाईं ओर अपने इनपुट, या मेरे संकार्य,
बदलाव ऑपरेटर काफी बस एक 1 है।

766
00:36:27,390 --> 00:36:33,750
और मैं उसके बाद कंप्यूटर को बता
1, सात स्थानों का कहना है कि बदलाव के लिए छोड़ दिया,

767
00:36:33,750 --> 00:36:37,150
परिणाम हालांकि मैं के रूप में है
कि एक लेते हैं, और इसे स्थानांतरित

768
00:36:37,150 --> 00:36:40,160
खत्म करने के लिए सात स्थानों
छोड़ दिया, और डिफ़ॉल्ट रूप से,

769
00:36:40,160 --> 00:36:42,270
हम मानते हैं कि करने के लिए जा रहे हैं
सही करने के लिए अंतरिक्ष

770
00:36:42,270 --> 00:36:44,080
शून्य के साथ गद्देदार किया जा रहा है।

771
00:36:44,080 --> 00:36:50,316
दूसरे शब्दों में, एक पारी 7 जा रहा है छोड़ा
पीछा किया, एक है कि मुझे देने के लिए 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 शून्य।

773
00:36:54,060 --> 00:36:57,380
तो एक तरह से, यह करने के लिए आपको अनुमति देता है
1 की तरह एक छोटी संख्या में लेते हैं,

774
00:36:57,380 --> 00:37:00,740
और स्पष्ट रूप से ज्यादा यह कर
इस तरह से बहुत बड़ा, बहुत,

775
00:37:00,740 --> 00:37:06,460
लेकिन हम वास्तव में देखने के लिए जा रहे हैं
इसके लिए अधिक चतुर दृष्टिकोण

776
00:37:06,460 --> 00:37:08,080
इसके बजाय, के रूप में अच्छी तरह से,

777
00:37:08,080 --> 00:37:08,720
>> ठीक है।

778
00:37:08,720 --> 00:37:10,060
यही कारण है कि सप्ताह में तीन के लिए है।

779
00:37:10,060 --> 00:37:11,400
हम आपको अगली बार देखेंगे।

780
00:37:11,400 --> 00:37:12,770
यह CS50 था।

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [संगीत बजाना]

783
00:37:22,243 --> 00:37:25,766
>> स्पीकर 1: वह नाश्ते में था
एक गर्म हेराफेरी कुचले हुए फल खाने पट्टी।

784
00:37:25,766 --> 00:37:28,090
उन्होंने कहा कि उनके चेहरे पर यह सब किया था।

785
00:37:28,090 --> 00:37:30,506
उन्होंने कहा कि एक दाढ़ी की तरह है कि चॉकलेट पहने हुए है

786
00:37:30,506 --> 00:37:31,756
स्पीकर 2: तुम क्या कर रहे हो?

787
00:37:31,756 --> 00:37:32,422
अध्यक्ष 3: हममम?

788
00:37:32,422 --> 00:37:33,500
क्या?

789
00:37:33,500 --> 00:37:36,800
>> स्पीकर 2: आप बस डबल डुबकी किया था?

790
00:37:36,800 --> 00:37:38,585
आप डबल चिप डूबा हुआ है।

791
00:37:38,585 --> 00:37:39,460
अध्यक्ष 3: मुझे माफ करना।

792
00:37:39,460 --> 00:37:44,440
स्पीकर 2: आप चिप डूबा
एक काट लिया, और आप फिर से डूबा हुआ है।

793
00:37:44,440 --> 00:37:44,940
अध्यक्ष 3:

794
00:37:44,940 --> 00:37:48,440
स्पीकर 2: कि डालने की तरह है तो
डुबकी में अपने पूरे मुंह सही।

795
00:37:48,440 --> 00:37:52,400
अगली बार जब आप एक चिप लेने के लिए
सिर्फ एक बार डुबकी, और यह खत्म होता है।

796
00:37:52,400 --> 00:37:53,890
>> अध्यक्ष 3: आप, दान पता है क्या?

797
00:37:53,890 --> 00:37:58,006
आप डुबकी करना चाहते हैं कि जिस तरह डुबकी।

798
00:37:58,006 --> 00:38:01,900
मैंने सोचा कि मैं डुबकी करना चाहते हैं कि जिस तरह डुबकी करेंगे।

799
00:38:01,900 --> 00:38:03,194