1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [القسم 3 - أكثر راحة]

2
00:00:02,570 --> 00:00:05,070
[روب بودين - جامعة هارفارد]

3
00:00:05,070 --> 00:00:07,310
>> [هذا CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> بحيث يتم صياغتها بشكل غريب على السؤال الأول.

5
00:00:12,700 --> 00:00:17,480
GDB يتيح لك "تصحيح" برنامج، ولكن، وبشكل أكثر تحديدا، ماذا لك أن تفعل؟

6
00:00:17,480 --> 00:00:22,590
أنا سأجيب أن واحد، وأنا لا أعرف بالضبط ما هو متوقع،

7
00:00:22,590 --> 00:00:27,910
لذلك أنا التخمين انها شيء على غرار فإنه يتيح لك خطوة خطوة

8
00:00:27,910 --> 00:00:31,540
المشي من خلال برنامج والتفاعل معها، والمتغيرات التغيير، تفعل كل هذه الأشياء -

9
00:00:31,540 --> 00:00:34,270
في الأساس السيطرة تماما تنفيذ برنامج

10
00:00:34,270 --> 00:00:38,410
وتفقد أي جزء معين من تنفيذ البرنامج.

11
00:00:38,410 --> 00:00:43,030
حتى تلك الميزات تسمح لك تصحيح الأمور.

12
00:00:43,030 --> 00:00:44,830
حسنا.

13
00:00:44,830 --> 00:00:50,520
لماذا البحث الثنائية تتطلب أن يتم فرز مجموعة؟

14
00:00:50,520 --> 00:00:53,360
الذي يريد أن تجيب على ذلك؟

15
00:00:56,120 --> 00:01:00,070
[طالب] لأنه لا يعمل إذا لم يكن تم الفرز عليه. نعم >>. [ضحك]

16
00:01:00,070 --> 00:01:04,910
وإذا ما غير مصنفة ذلك، ثم أنه من المستحيل أن تقسيمه إلى نصفين

17
00:01:04,910 --> 00:01:07,850
ويعرف أن كل شيء على يسار أقل وكل شيء إلى اليمين

18
00:01:07,850 --> 00:01:10,490
أكبر من القيمة الوسطى.

19
00:01:10,490 --> 00:01:12,790
لذلك لا بد من فرزها.

20
00:01:12,790 --> 00:01:14,170
حسنا.

21
00:01:14,170 --> 00:01:17,570
لماذا هو نوع من فقاعة في O ن التربيعية؟

22
00:01:17,570 --> 00:01:23,230
لا أحد أريد أولا لإعطاء سريعة جدا على مستوى عال محة عامة عن ما هو نوع فقاعة؟

23
00:01:25,950 --> 00:01:33,020
[طالب] تذهب أساسا من خلال كل عنصر من عناصر وعليك مراجعة العناصر القليلة الأولى.

24
00:01:33,020 --> 00:01:37,150
لو انهم من المكان الذي مقايضتهم، ثم قمت بفحص العناصر القليلة المقبلة، وهلم جرا.

25
00:01:37,150 --> 00:01:40,770
عندما تصل إلى نهاية، ثم انت تعرف ان يتم وضع أكبر عنصر في النهاية،

26
00:01:40,770 --> 00:01:42,750
لذلك أنت تتجاهل أن واحدا ثم عليك أن تبقي على الذهاب من خلال،

27
00:01:42,750 --> 00:01:48,490
وفي كل مرة كان لديك للتحقق من عنصر واحد أقل حتى قمت بإجراء أية تغييرات. نعم >>.

28
00:01:48,490 --> 00:01:58,470
انه دعا نوع فقاعة لأنه إذا كنت الوجه الصفيف على جانبها لذلك فمن صعودا وهبوطا، العمودي،

29
00:01:58,470 --> 00:02:03,100
ثم سوف القيم الكبيرة تنزل الى القاع والقيم الصغيرة سوف فقاعة يصل إلى الأعلى.

30
00:02:03,100 --> 00:02:05,210
تلك هي الكيفية التي حصلت على اسمها.

31
00:02:05,210 --> 00:02:08,220
ونعم، كنت مجرد الذهاب من خلال.

32
00:02:08,220 --> 00:02:11,190
واصلتم يمر الصفيف، مبادلة قيمة أكبر

33
00:02:11,190 --> 00:02:14,040
للحصول على أكبر القيم إلى أسفل.

34
00:02:14,040 --> 00:02:17,500
>> لماذا هو O ن التربيعية؟

35
00:02:18,690 --> 00:02:24,620
أولا، لا أحد يريد أن يقول لماذا هو O ن التربيعية؟

36
00:02:24,620 --> 00:02:28,760
[طالب] لأن لكل تشغيله مرة يذهب ن.

37
00:02:28,760 --> 00:02:32,100
فقط يمكنك أن تكون على يقين من أن كنت قد اتخذت أكبر عنصر على طول الطريق،

38
00:02:32,100 --> 00:02:35,230
ثم لديك لتكرار ذلك لأنه كما العديد من العناصر. نعم >>.

39
00:02:35,230 --> 00:02:41,800
حتى تبقي في الاعتبار ما يعني وكبيرة O ما الوسائل أوميغا كبيرة.

40
00:02:41,800 --> 00:02:50,560
وO كبيرة مثل الحد الأعلى حول كيفية بطيئة يمكن تشغيلها فعليا.

41
00:02:50,560 --> 00:02:58,990
ذلك بالقول انها O ن التربيعية، فإنه ليس من غير O وإلا فإنه سيكون قادرا على تشغيل

42
00:02:58,990 --> 00:03:02,640
في الوقت الخطية، وإنما هو من مكعبة O ن

43
00:03:02,640 --> 00:03:06,390
لأن يحدها من مكعبة O ن.

44
00:03:06,390 --> 00:03:12,300
وإذا ما يحدها O ن التربيعية، ثم انها يحدها أيضا مكعبة ن.

45
00:03:12,300 --> 00:03:20,280
ذلك أنه هو ن مربع، وفي حال الأسوأ علي الاطلاق تكنولوجيا المعلومات لا تستطيع أن تفعل أفضل من N مربع،

46
00:03:20,280 --> 00:03:22,830
وهذا هو السبب انها O ن المربعة.

47
00:03:22,830 --> 00:03:31,200
ذلك أن نرى الرياضيات طفيف في كيفية يتعلق الأمر إلى أن تكون ن مربع،

48
00:03:31,200 --> 00:03:40,530
اذا كان لدينا خمسة أشياء في قائمتنا، وهي المرة الأولى كيف يمكن مقايضة العديد نحن بحاجة لجعل يحتمل

49
00:03:40,530 --> 00:03:47,170
من أجل الحصول على هذا؟ دعونا فقط في الواقع -

50
00:03:47,170 --> 00:03:52,040
عدد التبادل نحن ذاهبون الى ان تجعل في الجولة الأولى من نوع فقاعة من خلال مجموعة؟

51
00:03:52,040 --> 00:03:53,540
[طالب] ن - 1. نعم >>.

52
00:03:53,540 --> 00:03:58,340
>> إذا كان هناك 5 عناصر، ونحن بحاجة الى الذهاب الى جعل ن - 1.

53
00:03:58,340 --> 00:04:01,100
ثم في ثانية واحدة كم عدد التبادل نحن ذاهبون الى ان تجعل؟

54
00:04:01,100 --> 00:04:03,440
[طالب] ن - 2. نعم >>.

55
00:04:03,440 --> 00:04:11,640
والثالثة ستكون N - 3، ومن ثم لراحة سأكتب الماضيين

56
00:04:11,640 --> 00:04:15,270
كما ثم نحن بحاجة الى الذهاب الى جعل 2 التبادل والمقايضة 1.

57
00:04:15,270 --> 00:04:19,899
أعتقد أن آخر قد أو قد لا تحتاج في الواقع أن يحدث.

58
00:04:19,899 --> 00:04:22,820
هل هو مبادلة؟ لا أعرف.

59
00:04:22,820 --> 00:04:26,490
لذلك فان هذه هي إجمالي مبالغ عمليات مقايضة أو على الأقل مقارنات لديك لجعل.

60
00:04:26,490 --> 00:04:29,910
حتى لو كنت لا تبديل، لا تزال تحتاج لمقارنة القيم.

61
00:04:29,910 --> 00:04:33,910
لذلك هناك ن - 1 مقارنات في الجولة الأولى من خلال مجموعة.

62
00:04:33,910 --> 00:04:42,050
إذا كنت إعادة ترتيب هذه الأمور، دعونا نجعل فعلا ستة أشياء من الأشياء كومة طيف،

63
00:04:42,050 --> 00:04:44,790
ومن ثم سأفعل 3، 2، 1.

64
00:04:44,790 --> 00:04:49,910
حتى إعادة ترتيب هذه المبالغ فقط، نريد أن نرى كيف العديد من المقارنات التي نتخذها

65
00:04:49,910 --> 00:04:52,700
في الخوارزمية بأكمله.

66
00:04:52,700 --> 00:04:56,550
إذا كان الأمر كذلك نأتي إلى هنا هؤلاء الرجال،

67
00:04:56,550 --> 00:05:07,470
ثم نحن لا تزال مجرد تلخيص مقارنات كثيرة ولكن كانت هناك.

68
00:05:07,470 --> 00:05:13,280
ولكن إذا كنا تلخيص هذه الخلاصة هذه، ونحن ونحن جمع هذه،

69
00:05:13,280 --> 00:05:18,130
انها لا تزال نفس المشكلة. خلاصة القول أننا فقط تلك الجماعات خاصة.

70
00:05:18,130 --> 00:05:22,400
>> لذلك نحن الآن تلخيص 3 في ن. انها ليست مجرد 3 N في.

71
00:05:22,400 --> 00:05:27,650
انها دائما ما يكون ن / 2 ن ل.

72
00:05:27,650 --> 00:05:29,430
لذلك نحن هنا يحدث لدينا 6.

73
00:05:29,430 --> 00:05:34,830
إذا كان لدينا 10 أشياء، ثم يمكن أن نفعل هذا التجمع لمدة 5 أزواج مختلفة من الأشياء

74
00:05:34,830 --> 00:05:37,180
وينتهي مع ن ن + + + ن + ن ن.

75
00:05:37,180 --> 00:05:45,840
لذلك كنت دائما ما تحصل ن / 2 ن، وحتى هذا سنقوم بها الذرة إلى n مربع / 2.

76
00:05:45,840 --> 00:05:48,890
وذلك على الرغم من انها عامل النصف، والذي يحدث أن تأتي في

77
00:05:48,890 --> 00:05:54,190
بسبب حقيقة أنه من خلال كل تكرار خلال مجموعة قارنا 1 أقل

78
00:05:54,190 --> 00:05:58,040
هذا كيف نحصل على أكثر من 2، ولكن لا يزال هو ن مربع.

79
00:05:58,040 --> 00:06:01,650
نحن لا نهتم عاملا ثابتا من النصف.

80
00:06:01,650 --> 00:06:07,760
لذلك الكثير من الاشياء الكبيرة مثل O هذا يعتمد على مجرد نوع من يفعل هذا النوع من الرياضيات،

81
00:06:07,760 --> 00:06:12,260
القيام مبالغ الحساب وهندسية الاشياء السلسلة،

82
00:06:12,260 --> 00:06:17,750
ولكن معظمها في هذه الدورة هي جميلة واضحة.

83
00:06:17,750 --> 00:06:19,290
حسنا.

84
00:06:19,290 --> 00:06:24,430
لماذا هو نوع أوميغا الإدراج في ن؟ ماذا يعني أوميغا؟

85
00:06:24,430 --> 00:06:27,730
[طالبين التحدث في آن واحد - غير مفهومة] نعم >>.

86
00:06:27,730 --> 00:06:30,630
يمكن أوميغا تفكر في مثل الحد الأدنى.

87
00:06:30,630 --> 00:06:36,550
>> ذلك بغض النظر عن مدى كفاءة خوارزمية الترتيب الخاص بك الإدراج،

88
00:06:36,550 --> 00:06:41,810
بغض النظر عن القائمة التي مرت في، فإنه دائما لمقارنة الأشياء على الأقل ن

89
00:06:41,810 --> 00:06:44,620
أو أنه لا يوجد تكرار عبر الأشياء.

90
00:06:44,620 --> 00:06:47,280
لماذا؟

91
00:06:47,280 --> 00:06:51,190
[طالب] لأنه إذا تم فرزها بالفعل في القائمة، ثم من خلال التكرار الأول

92
00:06:51,190 --> 00:06:54,080
يمكنك فقط أن تضمن العنصر الأول هو الأقل جدا،

93
00:06:54,080 --> 00:06:56,490
والتكرار الثاني يمكنك ضمان فقط الأولين هي

94
00:06:56,490 --> 00:07:00,010
لأنك لا تعلم أن يتم فرز باقي القائمة. نعم >>.

95
00:07:00,010 --> 00:07:08,910
إذا كنت تمر في القائمة التي تم فرزها تماما، على الأقل عليك أن تذهب على جميع العناصر

96
00:07:08,910 --> 00:07:12,180
أن نرى أن لا شيء يجب أن يتم نقل حولها.

97
00:07:12,180 --> 00:07:14,720
يمر ذلك عبر قائمة ويقول أوه، يتم فرز هذا بالفعل،

98
00:07:14,720 --> 00:07:18,240
انه من المستحيل بالنسبة لك أن تعرف فإنه يتم فرز حتى تحقق كل عنصر من عناصر

99
00:07:18,240 --> 00:07:20,660
للتأكد من أنهم في ترتيب فرزها.

100
00:07:20,660 --> 00:07:25,290
وبالتالي فإن الحد الأدنى على نوع أوميغا الإدراج ن.

101
00:07:25,290 --> 00:07:28,210
ما هو أسوأ حالة تشغيل وقت نوع الدمج،

102
00:07:28,210 --> 00:07:31,390
أسوأ الحالات يجري O كبيرة مرة أخرى؟

103
00:07:31,390 --> 00:07:37,660
حتى في أسوأ الحالات، كيف يمكن دمج النوع تشغيل؟

104
00:07:42,170 --> 00:07:43,690
[طالب] N ن سجل. نعم >>.

105
00:07:43,690 --> 00:07:49,990
أسرع خوارزميات الفرز العامة .. ن ن سجل. لا يمكنك أن تفعل أفضل.

106
00:07:51,930 --> 00:07:55,130
>> هناك حالات خاصة، واذا كان لدينا وقت اليوم - ولكننا مقتبل ربما -

107
00:07:55,130 --> 00:07:59,330
يمكننا أن نرى واحد أن يفعل أفضل من ن ن سجل.

108
00:07:59,330 --> 00:08:04,050
ولكن في حالة عامة، لا يمكنك أن تفعل أفضل من ن ن سجل.

109
00:08:04,050 --> 00:08:09,680
ودمج النوع يحدث لتكون واحدة يجب أن نعرف أن لهذه الدورة هو ن ن سجل.

110
00:08:09,680 --> 00:08:13,260
ولذا فإننا سوف يتم تنفيذ ذلك في الواقع اليوم.

111
00:08:13,260 --> 00:08:18,070
وأخيرا، في ما لا يزيد عن ثلاث جمل، كيف اختيار نوع العمل؟

112
00:08:18,070 --> 00:08:20,370
لا شخص الرغبة في الرد، وسوف نعول جملك

113
00:08:20,370 --> 00:08:22,390
لأنه إذا ذهبت أكثر من 3 -

114
00:08:25,530 --> 00:08:28,330
لا أحد يتذكر نوع الاختيار؟

115
00:08:31,280 --> 00:08:37,809
نوع الاختيار عادة ما يكون من السهل جدا أن نتذكر فقط من الاسم.

116
00:08:37,809 --> 00:08:45,350
كنت تكرار ما يزيد قليلا على مجموعة، والعثور على كل ما هو أكبر قيمة أو أصغر -

117
00:08:45,350 --> 00:08:47,290
مهما كنت أمر الفرز فيها.

118
00:08:47,290 --> 00:08:50,750
لذلك دعونا نقول اننا الفرز من الأصغر إلى الأكبر.

119
00:08:50,750 --> 00:08:55,250
كنت تكرار عبر مجموعة، وتبحث عن كل ما هو العنصر الحد الأدنى،

120
00:08:55,250 --> 00:08:59,750
تحديده، ومن ثم مبادلة فقط كل ما هو في المقام الأول.

121
00:08:59,750 --> 00:09:04,090
ومن ثم على مرور الثاني على مجموعة، والبحث عن العنصر الحد الأدنى مرة أخرى،

122
00:09:04,090 --> 00:09:07,490
تحديده، ثم مبادلتها مع ما هو في المرتبة الثانية.

123
00:09:07,490 --> 00:09:10,650
لذلك نحن فقط في اختيار واختيار القيم الدنيا

124
00:09:10,650 --> 00:09:16,050
وإدراجها في الجزء الأمامي من مجموعة حتى يتم فرز ذلك.

125
00:09:19,210 --> 00:09:21,560
الأسئلة على ذلك؟

126
00:09:21,560 --> 00:09:25,710
>> هذه تظهر حتما في أشكال لديك لملء عندما كنت تقديم pset.

127
00:09:29,010 --> 00:09:32,360
تلك هي أساسا إجابات لتلك.

128
00:09:32,360 --> 00:09:34,230
حسنا، لذلك الترميز الآن مشاكل.

129
00:09:34,230 --> 00:09:40,140
أنا أرسلت بالفعل عبر البريد الإلكتروني - هل أي شخص لا تحصل على هذا البريد الإلكتروني؟ حسنا.

130
00:09:40,140 --> 00:09:46,630
أنا أرسلت بالفعل عبر البريد الإلكتروني المساحة التي نحن ذاهبون إلى استخدام،

131
00:09:46,630 --> 00:09:52,120
وإذا نقرت على اسمي - لذلك أعتقد أنني ذاهب ليكون في أسفل

132
00:09:52,120 --> 00:09:57,170
بسبب R الوراء - ولكن إذا نقرت على اسمي سوف انظر 2 التنقيحات.

133
00:09:57,170 --> 00:10:02,650
التنقيح 1 سوف يتم نسخها بالفعل أنا ولصق الشفرة في الفراغات

134
00:10:02,650 --> 00:10:06,900
البحث عن الشيء وأنت تسير لدينا لتنفيذها.

135
00:10:06,900 --> 00:10:10,540
وسوف التنقيح 2 أن يكون الشيء النوع الذي ننفذ بعد ذلك.

136
00:10:10,540 --> 00:10:15,770
لذلك يمكنك النقر على مراجعة بلدي (1) والعمل من هناك.

137
00:10:17,350 --> 00:10:22,060
والآن نريد أن تنفيذ بحث ثنائية.

138
00:10:22,060 --> 00:10:26,470
>> لا أحد يريد ان يعطي مجرد شبة الكود رفيع المستوى التفسير

139
00:10:26,470 --> 00:10:31,440
ما نحن ذاهبون الى القيام به للبحث؟ نعم.

140
00:10:31,440 --> 00:10:36,170
[طالب] أنت تأخذ فقط وسط مجموعة ومعرفة ما اذا ما كنت تبحث عن

141
00:10:36,170 --> 00:10:38,650
هو أقل من ذلك أو أكثر من ذلك.

142
00:10:38,650 --> 00:10:41,080
وإذا كان أقل من ذلك، تذهب إلى النصف وهذا أقل،

143
00:10:41,080 --> 00:10:44,750
وإذا كان أكثر من ذلك، تذهب إلى النصف وهذا أكثر ولكم أن أكرر حتى تحصل على شيء واحد فقط.

144
00:10:44,750 --> 00:10:46,570
[بودين] نعم.

145
00:10:46,570 --> 00:10:51,320
تلاحظ أن يتم فرز الأرقام لدينا بالفعل مجموعة،

146
00:10:51,320 --> 00:10:57,190
وبحيث يعني أننا يمكن أن نستفيد من ذلك وأننا يمكن أن تحقق الأولى،

147
00:10:57,190 --> 00:11:00,390
حسنا، أنا أبحث عن عدد 50.

148
00:11:00,390 --> 00:11:03,720
حتى أتمكن من الذهاب الى وسطها.

149
00:11:03,720 --> 00:11:07,380
الأوسط من الصعب تحديد عندما يكون عدد زوجي من الأشياء،

150
00:11:07,380 --> 00:11:10,820
ولكن دعنا نقول فقط أننا سوف اقتطاع دائما إلى الوسط.

151
00:11:10,820 --> 00:11:14,420
حتى هنا لدينا 8 الأشياء، لذلك سيكون منتصف 16.

152
00:11:14,420 --> 00:11:17,330
أنا أبحث عن 50، حتى 50 هو أكبر من 16.

153
00:11:17,330 --> 00:11:21,310
حتى الآن لا أستطيع علاج أساسا مجموعة بصفتي هذه العناصر.

154
00:11:21,310 --> 00:11:23,450
ويمكنني أن نرمي كل شيء من أكثر من 16.

155
00:11:23,450 --> 00:11:27,440
الآن مجموعة بلدي هو مجرد هذه العناصر 4، وأكرر.

156
00:11:27,440 --> 00:11:31,910
حتى ذلك الحين أريد أن أجد منتصف مرة أخرى، والتي ستكون 42.

157
00:11:31,910 --> 00:11:34,730
42 هو أقل من 50، حتى أتمكن من رمي بعيدا هذين العنصرين.

158
00:11:34,730 --> 00:11:36,890
هذا هو بلدي مجموعة المتبقية.

159
00:11:36,890 --> 00:11:38,430
انا ذاهب الى العثور على منتصف مرة أخرى.

160
00:11:38,430 --> 00:11:42,100
اعتقد 50 تم مثالا سيئا لأنني كنت دائما رمي الأشياء بعيدا إلى اليسار،

161
00:11:42,100 --> 00:11:48,280
ولكن عن طريق هذا الإجراء نفسه، إذا أنا أبحث عن شيء

162
00:11:48,280 --> 00:11:52,100
وانها أقل من العنصر أنا أبحث حاليا في،

163
00:11:52,100 --> 00:11:55,080
ثم أنا ذاهب لرمي بعيدا كل شيء إلى اليمين.

164
00:11:55,080 --> 00:11:58,150
حتى الآن نحن بحاجة لتنفيذ ذلك.

165
00:11:58,150 --> 00:12:02,310
لاحظت أننا في حاجة لتمرير في الحجم.

166
00:12:02,310 --> 00:12:06,730
يمكننا أيضا لا تحتاج إلى رمز يصعب الحجم.

167
00:12:06,730 --> 00:12:11,640
إذا كان الأمر كذلك نتخلص من أن تعريف # -

168
00:12:19,630 --> 00:12:21,430
حسنا.

169
00:12:21,430 --> 00:12:27,180
كيف يمكنني معرفة ما لطيف حجم مجموعة الأعداد حاليا؟

170
00:12:27,180 --> 00:12:30,950
>> كم عدد العناصر في الصفيف الأرقام؟

171
00:12:30,950 --> 00:12:33,630
[طالب] أرقام، بين قوسين،. طول؟

172
00:12:33,630 --> 00:12:36,600
[بودين] وهذا غير موجود في C.

173
00:12:36,600 --> 00:12:38,580
تحتاج إليها. طول.

174
00:12:38,580 --> 00:12:42,010
صفائف لم يكن لديك الخصائص، لذلك ليس هناك خاصية طول صفائف

175
00:12:42,010 --> 00:12:45,650
والتي تعطي فقط لأنك مهما طال يحدث أن تكون.

176
00:12:48,180 --> 00:12:51,620
[طالب] انظر مقدار الذاكرة لديه والقسمة على مدى - نعم >>.

177
00:12:51,620 --> 00:12:55,810
فكيف نرى مقدار الذاكرة لديها؟ >> [طالب] Sizeof. نعم >>، sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof هي المشغل أن يحدث لإرجاع حجم الصفيف الأرقام.

179
00:13:01,680 --> 00:13:10,060
والتي ستكون صحيحة ولكن هناك العديد من أضعاف حجم عدد صحيح

180
00:13:10,060 --> 00:13:14,050
منذ ذلك مقدار الذاكرة يستغرق وقتا فعليا حتى.

181
00:13:14,050 --> 00:13:17,630
إذا كان الأمر كذلك أريد عدد من الأشياء في الصفيف،

182
00:13:17,630 --> 00:13:20,560
ثم أنا تريد الذهاب الى تقسيم حسب حجم عدد صحيح.

183
00:13:22,820 --> 00:13:26,010
حسنا. بحيث يتيح لي تمر في الحجم هنا.

184
00:13:26,010 --> 00:13:29,430
لماذا أحتاج لتمرير في حجم على الإطلاق؟

185
00:13:29,430 --> 00:13:38,570
لماذا لا يمكن أن أفعل للتو هنا حجم كثافة العمليات = sizeof (كومة قش) / sizeof (الباحث)؟

186
00:13:38,570 --> 00:13:41,490
لماذا لا تعمل هذه؟

187
00:13:41,490 --> 00:13:44,470
[طالب] انها ليست متغير عمومي.

188
00:13:44,470 --> 00:13:51,540
كومة التبن [بودين] موجود ونحن تمرير في الأرقام كما كومة قش،

189
00:13:51,540 --> 00:13:54,700
وهذا هو نوع من ينذر من ما يأتي. نعم.

190
00:13:54,700 --> 00:14:00,170
[طالب] كومة التبن هو مجرد الإشارة إلى ذلك، لذلك فإنه يعود كيف الكبيرة التي المرجع.

191
00:14:00,170 --> 00:14:02,150
نعم.

192
00:14:02,150 --> 00:14:09,000
أشك في أن محاضرة كنت قد رأيت كومة حتى الآن حقا، أليس كذلك؟

193
00:14:09,000 --> 00:14:11,270
تحدثنا فقط عن ذلك.

194
00:14:11,270 --> 00:14:16,090
ذلك هو المكان المكدس جميع المتغيرات الخاصة بك سوف تكون مخزنة.

195
00:14:16,090 --> 00:14:19,960
>> أي الذاكرة التي خصصت لانها المتغيرات المحلية تسير في المكدس،

196
00:14:19,960 --> 00:14:24,790
ويحصل كل وظيفة الفضاء الخاصة بها على المكدس، إطاره كومة الخاصة هو ما يطلق عليه.

197
00:14:24,790 --> 00:14:31,590
الرئيسية بحيث يحتوي إطاره المكدس، وداخل منه هو الذهاب الى وجود أعداد هذه المجموعة،

198
00:14:31,590 --> 00:14:34,270
وسيكون من sizeof حجم (أرقام).

199
00:14:34,270 --> 00:14:38,180
انها ستكون لدينا حجم الأرقام مقسوما على حجم العناصر،

200
00:14:38,180 --> 00:14:42,010
ولكن أن كل حياة داخل إطار مكدس الرئيسي.

201
00:14:42,010 --> 00:14:45,190
عندما ندعو البحث، البحث إطاره يحصل كومة الخاصة،

202
00:14:45,190 --> 00:14:48,840
الفضاء الخاصة بها لتخزين كافة المتغيرات المحلية الخاصة به.

203
00:14:48,840 --> 00:14:56,420
ولكن هذه الحجج - حتى كومة قش ليست نسخة من هذه المجموعة بأكملها.

204
00:14:56,420 --> 00:15:00,990
نحن لا تمر في مجموعة كاملة كنسخة في البحث.

205
00:15:00,990 --> 00:15:04,030
يمر مجرد الإشارة إلى أن مجموعة.

206
00:15:04,030 --> 00:15:11,470
لذلك يمكن الوصول إلى هذه الأرقام البحث من خلال هذا المرجع.

207
00:15:11,470 --> 00:15:17,100
انها لا تزال الحصول على الأشياء التي تعيش داخل الإطار الرئيسي لمكدس،

208
00:15:17,100 --> 00:15:22,990
ولكن في الأساس، عندما نصل إلى المؤشرات، التي ينبغي أن تكون في وقت قريب،

209
00:15:22,990 --> 00:15:24,980
هذا هو ما هي المؤشرات.

210
00:15:24,980 --> 00:15:29,400
مؤشرات ليست سوى إشارات إلى الأشياء، ويمكنك استخدام المؤشرات للوصول إلى الأشياء

211
00:15:29,400 --> 00:15:32,030
التي هي في إطارات المكدس أمور أخرى ".

212
00:15:32,030 --> 00:15:37,660
ذلك على الرغم من الأرقام المحلي إلى الرئيسية، يمكننا الوصول إلى أنها لا تزال من خلال هذا المؤشر.

213
00:15:37,660 --> 00:15:41,770
ولكن منذ انها مجرد مؤشر وانها مجرد إشارة،

214
00:15:41,770 --> 00:15:45,040
sizeof (كومة قش) بإرجاع فقط من الحجم الإشارة نفسها.

215
00:15:45,040 --> 00:15:47,950
فإنه لا يرجع حجم الشيء انها تشير الى.

216
00:15:47,950 --> 00:15:51,110
فإنه لا يرجع الحجم الفعلي من الأرقام.

217
00:15:51,110 --> 00:15:55,660
وحتى هذه ليست الذهاب الى العمل لأننا نريد أن.

218
00:15:55,660 --> 00:15:57,320
>> الأسئلة على ذلك؟

219
00:15:57,320 --> 00:16:03,250
ستزول مؤشرات إلى حد كبير بالتفصيل أكثر دموية في الأسابيع المقبلة.

220
00:16:06,750 --> 00:16:13,740
وهذا هو السبب في الكثير من الأشياء التي تراها، أكثر الأشياء أو الأشياء نوع البحث،

221
00:16:13,740 --> 00:16:16,990
انهم جميعا تقريبا بحاجة الى الذهاب الى اتخاذ الحجم الفعلي للمجموعة،

222
00:16:16,990 --> 00:16:20,440
لأنه في C، ليس لدينا أي فكرة عما حجم الصفيف.

223
00:16:20,440 --> 00:16:22,720
تحتاج إلى تمرير يدويا فيه.

224
00:16:22,720 --> 00:16:27,190
وأنت لا تستطيع تمرير يدويا في مجموعة كاملة لأنك مجرد مرور في المرجع

225
00:16:27,190 --> 00:16:30,390
وأنه لا يمكن الحصول على حجم من المرجع.

226
00:16:30,390 --> 00:16:32,300
حسنا.

227
00:16:32,300 --> 00:16:38,160
حتى الآن نحن نريد لتنفيذ ما تم شرح من قبل.

228
00:16:38,160 --> 00:16:41,530
يمكنك العمل على ذلك لمدة دقيقة،

229
00:16:41,530 --> 00:16:45,250
وكنت لا داعي للقلق حول الحصول على كل شيء تماما 100٪ العمل.

230
00:16:45,250 --> 00:16:51,410
الكتابة للتو في pseudocode نصف لكيفية كنت تعتقد أنه يجب أن تعمل.

231
00:16:52,000 --> 00:16:53,630
حسنا.

232
00:16:53,630 --> 00:16:56,350
لا تحتاج إلى القيام به تماما مع هذا الموضوع حتى الآن.

233
00:16:56,350 --> 00:17:02,380
ولكن لا أحد يشعر بالراحة مع ما لديهم حتى الآن،

234
00:17:02,380 --> 00:17:05,599
وكأنه شيء يمكن أن نعمل معا مع؟

235
00:17:05,599 --> 00:17:09,690
لا أحد يريد أن يتطوع؟ أو سوف يختار بشكل عشوائي.

236
00:17:12,680 --> 00:17:18,599
فإنه ليس من الضروري أن يكون على حق بكل المقاييس ولكن شيء لا يمكن تعديل في حالة عمل.

237
00:17:18,599 --> 00:17:20,720
[طالب] بالتأكيد. حسنا >>.

238
00:17:20,720 --> 00:17:27,220
بحيث تقوم بحفظ مراجعة عن طريق النقر على أيقونة حفظ قليلا.

239
00:17:27,220 --> 00:17:29,950
كنت راميا، أليس كذلك؟ >> [طالب] نعم. >> [بودين] حسنا.

240
00:17:29,950 --> 00:17:35,140
حتى الآن لا أستطيع مراجعة عرض الخاص بك ويمكن سحب ما يصل الجميع إلى مراجعة.

241
00:17:35,140 --> 00:17:38,600
وهنا لدينا - حسنا.

242
00:17:38,600 --> 00:17:43,160
حتى ذهب راميا مع حل العودية، الذي هو بالتأكيد الحل صحيح.

243
00:17:43,160 --> 00:17:44,970
هناك طريقتان يمكنك القيام به هذه المشكلة.

244
00:17:44,970 --> 00:17:48,060
يمكنك أن تفعل ذلك إما تكراري أو بشكل متكرر.

245
00:17:48,060 --> 00:17:53,860
ويمكن أيضا معظم المشاكل التي تواجه الذي يمكن القيام به بشكل متكرر أن يتم تكرارا.

246
00:17:53,860 --> 00:17:58,510
حتى هنا فعلناه ذلك بشكل متكرر.

247
00:17:58,510 --> 00:18:03,730
>> لا شخص تريد تعريف ما يعنيه أن تكون وظيفة العودية؟

248
00:18:07,210 --> 00:18:08,920
[طالب] عندما يكون لديك وظيفة الكلمة نفسها

249
00:18:08,920 --> 00:18:13,470
وثم استدعاء نفسها حتى يخرج مع صحيح وحقيقي. نعم >>.

250
00:18:13,470 --> 00:18:17,680
وظيفة العودية هو مجرد وظيفة التي تطلق على نفسها.

251
00:18:17,680 --> 00:18:24,140
هناك ثلاثة أشياء كبيرة أن وظيفة العودية يجب أن يكون.

252
00:18:24,140 --> 00:18:27,310
الأول هو واضح، فإنه يطلق على نفسه.

253
00:18:27,310 --> 00:18:29,650
والثاني هو الحالة الأساسية.

254
00:18:29,650 --> 00:18:33,390
حتى في مرحلة ما وظيفة يحتاج إلى وقف تطلق على نفسها،

255
00:18:33,390 --> 00:18:35,610
وهذا ما هو الحال للقاعدة.

256
00:18:35,610 --> 00:18:43,860
حتى هنا ونحن نعلم أننا يجب أن يتوقف، يجب أن نتخلى في بحثنا

257
00:18:43,860 --> 00:18:48,150
عندما يساوي بداية النهاية - وسنذهب على ما يعنيه ذلك.

258
00:18:48,150 --> 00:18:52,130
ولكن في النهاية، وآخر شيء هذا أمر مهم لوظائف العودية:

259
00:18:52,130 --> 00:18:59,250
يجب الاقتراب وظائف على نحو ما الحالة الأساسية.

260
00:18:59,250 --> 00:19:04,140
مثل إذا كنت لا تحديث اي شيء في الواقع عند إجراء المكالمة الثانية عودي،

261
00:19:04,140 --> 00:19:07,880
إذا كنت حرفيا فقط وظيفة الدعوة مرة أخرى مع نفس الحجج

262
00:19:07,880 --> 00:19:10,130
وتغيرت أي المتغيرات العالمية أو أي شيء،

263
00:19:10,130 --> 00:19:14,430
وأنك لن تصل إلى الحالة الأساسية، وفي هذه الحالة فهذا أمر سيئ.

264
00:19:14,430 --> 00:19:17,950
فسوف تكون لالعودية لانهائية وتجاوز سعة مكدس.

265
00:19:17,950 --> 00:19:24,330
ولكن هنا نرى أن التحديث يحدث منذ بدء نقوم بتحديث + نهاية / 2،

266
00:19:24,330 --> 00:19:28,180
نحن تحديث حجة نهاية هنا، نحن تحديث الحجة بداية هنا.

267
00:19:28,180 --> 00:19:32,860
حتى في كل المكالمات العودية نقوم بتحديث شيء. حسنا.

268
00:19:32,860 --> 00:19:38,110
هل ترغب في السير بنا من خلال الحل؟ بالتأكيد >>.

269
00:19:38,110 --> 00:19:44,270
أنا باستخدام SearchHelp بحيث في كل مرة أقوم هذه الدعوة وظيفة

270
00:19:44,270 --> 00:19:47,910
لدي بداية حيث أنا أبحث عن في مجموعة والنهاية

271
00:19:47,910 --> 00:19:49,380
من حيث أنا أبحث الصفيف.

272
00:19:49,380 --> 00:19:55,330
>> في كل خطوة حيث انها تقول انها عنصر الأوسط، والذي هو بداية نهاية + / 2،

273
00:19:55,330 --> 00:19:58,850
هو أن يساوي ما تبحث عنه؟

274
00:19:58,850 --> 00:20:04,650
وإذا كان، ثم تبين لنا ذلك، وأعتقد أن يحصل على تمرير لأعلى مستويات العودية.

275
00:20:04,650 --> 00:20:12,540
وإذا كان هذا غير صحيح، ثم نتحقق ما إذا كان هذا القيمة الوسطى للصفيف كبير جدا،

276
00:20:12,540 --> 00:20:19,320
وفي هذه الحالة ننظر إلى النصف الأيسر من مجموعة من خلال الذهاب من البداية للمؤشر الأوسط.

277
00:20:19,320 --> 00:20:22,710
وإلا فإننا نفعل النصف النهائي.

278
00:20:22,710 --> 00:20:24,740
[بودين] حسنا.

279
00:20:24,740 --> 00:20:27,730
فكرة جميلة.

280
00:20:27,730 --> 00:20:36,640
حسنا، لذلك بضعة أشياء، والواقع، وهذا هو الشيء رفيع المستوى

281
00:20:36,640 --> 00:20:41,270
أن وأنك لن تحتاج إلى معرفته لهذه الدورة، ولكن كان صحيحا.

282
00:20:41,270 --> 00:20:46,080
وظائف متكررة، تسمع دائما انهم صفقة سيئة

283
00:20:46,080 --> 00:20:51,160
لأنه إذا كان استدعاء متكرر نفسك في كثير من الأحيان، وتحصل على تجاوز سعة مكدس

284
00:20:51,160 --> 00:20:54,990
منذ ذلك الحين، كما قلت من قبل، كل وظيفة يحصل إطاره كومة الخاصة.

285
00:20:54,990 --> 00:20:59,500
لذلك كل دعوة من وظيفة العودية يحصل إطاره كومة الخاصة.

286
00:20:59,500 --> 00:21:04,140
إذا كان الأمر كذلك إجراء المكالمات العودية 1000، وتحصل على إطارات المكدس 1،000،

287
00:21:04,140 --> 00:21:08,390
والسرعة التي تؤدي إلى وجود عدد كبير جدا من إطارات المكدس وتحطيم الأشياء فقط.

288
00:21:08,390 --> 00:21:13,480
ولهذا السبب ظائف عودي سيئة عموما.

289
00:21:13,480 --> 00:21:19,370
ولكن هناك ما يسمى مجموعة فرعية لطيفة من وظائف عودي عودي وظائف الذيل،

290
00:21:19,370 --> 00:21:26,120
وهذا يحدث ليكون مثالا واحدا حيث يلاحظ إذا كان المترجم هذا

291
00:21:26,120 --> 00:21:29,920
وينبغي، على ما أعتقد - في ضجيج إذا كنت تمر عليها-O2 العلم

292
00:21:29,920 --> 00:21:33,250
بعد ذلك سوف تلاحظ هذا هو الذيل العودية وجعل الامور جيدة.

293
00:21:33,250 --> 00:21:40,050
>> فإنه سيتم إعادة استخدام الإطار مكدس نفسه مرارا وتكرارا عن كل مكالمة العودية.

294
00:21:40,050 --> 00:21:47,010
وذلك منذ كنت تستخدم نفس الإطار مكدس، لا داعي للقلق بشأن

295
00:21:47,010 --> 00:21:51,690
كومة من أي وقت مضى تفيض، وفي الوقت نفسه، قال مثلك من قبل،

296
00:21:51,690 --> 00:21:56,380
حيث بمجرد العودة الحقيقية، ثم عليه أن يعود عن كل من هذه الأطر مكدس

297
00:21:56,380 --> 00:22:01,740
والدعوة إلى 10 SearchHelp لديه للعودة إلى 9، وللعودة إلى 8.

298
00:22:01,740 --> 00:22:05,360
بحيث لا يحتاج أن يحدث عندما ظائف الذيل العودية.

299
00:22:05,360 --> 00:22:13,740
وذلك ما يجعل هذا الذيل هو دالة العودية لاحظ أن أي دعوة إلى إعطاء searchHelp

300
00:22:13,740 --> 00:22:18,470
الدعوة التي العودية انها ما جعل انها العائدين.

301
00:22:18,470 --> 00:22:25,290
حتى في المكالمة الأولى لSearchHelp، ونحن إما العودة فورا كاذبة،

302
00:22:25,290 --> 00:22:29,590
العودة فورا صحيح، أو أننا إجراء مكالمة عودي إلى SearchHelp

303
00:22:29,590 --> 00:22:33,810
حيث ما نقوم العودة هو ما تعود تلك الدعوة.

304
00:22:33,810 --> 00:22:51,560
ونحن لا يمكن أن تفعل ذلك إذا فعلنا شيئا مثل الباحث س = SearchHelp، وعودة 2 * X،

305
00:22:51,560 --> 00:22:55,440
فقط بعض التغيير عشوائي.

306
00:22:55,440 --> 00:23:01,470
>> حتى الآن هذه الدعوة متكررة، وهذا الباحث س = SearchHelp دعوة متكررة،

307
00:23:01,470 --> 00:23:05,740
لم يعد الذيل العودية لأنه في الواقع لا يجب أن تعود

308
00:23:05,740 --> 00:23:10,400
العودة إلى إطار المكدس السابق بحيث أن الدعوة السابقة إلى وظيفة

309
00:23:10,400 --> 00:23:13,040
ويمكن بعد ذلك القيام بشيء ما مع قيمة الإرجاع.

310
00:23:13,040 --> 00:23:22,190
وهذا ليس الذيل متكررة، ولكن ما كان لدينا هو لطيف قبل الذيل العودية. نعم.

311
00:23:22,190 --> 00:23:27,000
[وينبغي أن الطالب] لا يمكن التحقق من الحالة الأساسية الثانية الأولى

312
00:23:27,000 --> 00:23:30,640
لأنه يمكن أن يكون هناك حالة حيث أنه عند تمرير الوسيطة

313
00:23:30,640 --> 00:23:35,770
كنت قد تبدأ نهاية =، ولكنها قيمة الإبرة.

314
00:23:35,770 --> 00:23:47,310
كان يمكن للمسألة لا ندير في الحالة التي يكون فيها هو القيمة نهاية الإبرة

315
00:23:47,310 --> 00:23:52,000
أو اضافة = النهاية، بشكل مناسب، تبدأ نهاية =

316
00:23:52,000 --> 00:23:59,480
وكنت قد لا محددا في الواقع أن قيمة خاصة حتى الآن،

317
00:23:59,480 --> 00:24:03,910
ثم تبدأ نهاية + / 2 هو الذهاب لمجرد أن يكون نفس القيمة.

318
00:24:03,910 --> 00:24:07,890
ولكن لقد عدنا بالفعل كاذبة ونحن لم التحقق في الواقع قيمة.

319
00:24:07,890 --> 00:24:14,240
لذلك على أقل تقدير، في أول دعوة، إذا كان حجم 0، ثم نريد أن عودة كاذبة.

320
00:24:14,240 --> 00:24:17,710
ولكن إذا كان حجم هو 1، ثم بدء هو لن ينتهي على قدم المساواة،

321
00:24:17,710 --> 00:24:19,820
وسنقوم على الأقل تحقق من عنصر واحد.

322
00:24:19,820 --> 00:24:26,750
ولكن أعتقد أنك على حق في أننا يمكن في نهاية المطاف في حالة حيث تبدأ نهاية + / 2،

323
00:24:26,750 --> 00:24:31,190
بدء ينتهي به الأمر في نفس بداية نهاية + / 2،

324
00:24:31,190 --> 00:24:35,350
لكننا في الواقع أبدا فحص هذا العنصر.

325
00:24:35,350 --> 00:24:44,740
>> إذا كان الأمر كذلك فإننا أولا التحقق هو العنصر الأوسط القيمة نحن نبحث عن،

326
00:24:44,740 --> 00:24:47,110
ثم يمكننا العودة فورا صحيح.

327
00:24:47,110 --> 00:24:50,740
والا اذا انهم على قدم المساواة، ثم ليس هناك نقطة في مواصلة

328
00:24:50,740 --> 00:24:58,440
منذ ونحن في طريقنا لمجرد تحديث لحالة ما نحن فيه على مجموعة واحدة العنصر.

329
00:24:58,440 --> 00:25:01,110
إذا كان هذا عنصر واحد ليست واحدة ونحن نبحث عن،

330
00:25:01,110 --> 00:25:03,530
ثم كل شيء من الخطأ. نعم.

331
00:25:03,530 --> 00:25:08,900
[طالب] الشيء هو أنه منذ حجم أكبر في الواقع من عدد العناصر في الصفيف،

332
00:25:08,900 --> 00:25:13,070
هناك بالفعل إزاحة - >> فهل المطاطية -

333
00:25:13,070 --> 00:25:19,380
[طالب] قل لو كان حجم الصفيف 0، ثم سوف تحقق فعلا SearchHelp كومة قش من 0

334
00:25:19,380 --> 00:25:21,490
على المكالمة الأولى.

335
00:25:21,490 --> 00:25:25,300
مجموعة لديها حجم 0، وبالتالي فإن 0 هو - نعم >>.

336
00:25:25,300 --> 00:25:30,750
هناك شيء آخر أن - أنه قد يكون من الجيد. دعنا نفكر.

337
00:25:30,750 --> 00:25:40,120
إذا كان الأمر كذلك كان لمجموعة 10 عناصر والمتوسطة واحدة ونحن في طريقنا للتحقق هو مؤشر 5،

338
00:25:40,120 --> 00:25:45,700
لذلك نحن فحص 5، ودعونا نقول أن القيمة هي أقل من ذلك.

339
00:25:45,700 --> 00:25:50,720
لذلك نحن رمي كل شيء بعيدا في الفترة من 5 إلى الأمام.

340
00:25:50,720 --> 00:25:54,030
حتى يبدأ نهاية + / 2 ستكون نهايتنا جديدة،

341
00:25:54,030 --> 00:25:57,450
لذا نعم، انه سيكون دائما على البقاء إلى ما بعد نهاية الصفيف.

342
00:25:57,450 --> 00:26:03,570
لو كان الحال لو كان غريبا أو حتى، ثم نتحقق، ويقول، 4،

343
00:26:03,570 --> 00:26:05,770
ولكننا لا يزال بعيدا رمي -

344
00:26:05,770 --> 00:26:13,500
لذا نعم، نهاية دائما ما يكون إلى ما بعد نهاية الفعلية للمجموعة.

345
00:26:13,500 --> 00:26:18,350
وبالتالي فإن العناصر فإننا نركز على، نهاية دائما ما تكون واحدة بعد ذلك.

346
00:26:18,350 --> 00:26:24,270
وحتى إذا كان من أي وقت مضى لا نهاية بداية متساوية، ونحن في مجموعة من حجم 0.

347
00:26:24,270 --> 00:26:35,600
>> والشيء الآخر كنت أفكر هو أننا نقوم بتحديث بداية أن تبدأ نهاية + / 2،

348
00:26:35,600 --> 00:26:44,020
لذلك هذا هو الحال أن أواجه مشكلة مع، حيث تبدأ نهاية + / 2

349
00:26:44,020 --> 00:26:46,820
هو العنصر أننا التحقق.

350
00:26:46,820 --> 00:26:58,150
دعنا نقول كان لدينا هذه المجموعة 10-العنصر. أيا كان.

351
00:26:58,150 --> 00:27:03,250
حتى يبدأ نهاية + / 2 سيكون شيئا مثل هذا واحد،

352
00:27:03,250 --> 00:27:07,060
واذا كان هذا لا قيمة، ويقول نحن نريد لتحديث.

353
00:27:07,060 --> 00:27:10,060
قيمة أكبر، لذلك نحن نريد أن ننظر إلى هذا النصف من الصفيف.

354
00:27:10,060 --> 00:27:15,910
فكيف ونحن نقوم بتحديث بداية، نحن تحديث البداية وحتى الآن يكون هذا العنصر.

355
00:27:15,910 --> 00:27:23,790
ولكن هذا قد لا تزال تعمل، أو على أقل تقدير، يمكنك القيام به بداية نهاية + / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[طالب] أنت لا تحتاج إلى أن تبدأ نهاية + [غير مسموع] >> نعم.

357
00:27:27,850 --> 00:27:33,240
لقد بحثنا بالفعل هذا العنصر وأعلم أنها ليست تلك التي كنا نبحث عنها.

358
00:27:33,240 --> 00:27:36,800
لذلك نحن لسنا في حاجة لبدء التحديث أن يكون هذا العنصر.

359
00:27:36,800 --> 00:27:39,560
يمكننا تخطي فقط وبدء التحديث أن يكون هذا العنصر.

360
00:27:39,560 --> 00:27:46,060
وهناك قضية من أي وقت مضى، دعنا نقول، أن هذا كان الهدف،

361
00:27:46,060 --> 00:27:53,140
حتى تبدأ بعد ذلك سيكون هذا، بدء نهاية + / 2 يكون هذا شأنه،

362
00:27:53,140 --> 00:28:00,580
بدء نهاية + - نعم، وأعتقد أنه يمكن أن ينتهي بهم المطاف في العودية لانهائية.

363
00:28:00,580 --> 00:28:12,690
دعنا نقول انها مجرد مجموعة من حجم 2 أو مجموعة من حجم 1. وأعتقد أن هذا سوف يعمل.

364
00:28:12,690 --> 00:28:19,490
ذلك في الوقت الحالي، هو أن بداية ونهاية العنصر هو 1 الى ابعد من ذلك.

365
00:28:19,490 --> 00:28:24,110
ذلك العنصر الذي نحن في طريقنا للتحقق من هذا واحد،

366
00:28:24,110 --> 00:28:29,400
وبعد ذلك عندما نقوم بتحديث بداية، نحن تحديث البداية وحتى تكون 0 + 1/2،

367
00:28:29,400 --> 00:28:33,160
التي سوف تنتهي بنا إلى الوراء مع بداية يجري هذا العنصر.

368
00:28:33,160 --> 00:28:36,210
>> لذلك نحن فحص العنصر نفسه مرارا وتكرارا.

369
00:28:36,210 --> 00:28:43,310
لذلك هذا هو الحال حيث كل مكالمة العودية يجب تحديث في الواقع شيئا.

370
00:28:43,310 --> 00:28:48,370
لذلك نحن بحاجة للقيام بداية نهاية + / 2 + 1، وإلا هناك حالة

371
00:28:48,370 --> 00:28:50,710
حيث أننا لا تحديث فعلا البداية.

372
00:28:50,710 --> 00:28:53,820
الجميع يرى ذلك؟

373
00:28:53,820 --> 00:28:56,310
حسنا.

374
00:28:56,310 --> 00:29:03,860
هل لديها أسئلة حول هذا الحل أو أية تعليقات أخرى؟

375
00:29:05,220 --> 00:29:10,280
حسنا. هل هناك حل تكرارية أننا يمكن أن ننظر في جميع؟

376
00:29:17,400 --> 00:29:20,940
فعلنا كل ما في ومتكرر؟

377
00:29:20,940 --> 00:29:25,950
أو كما أعتقد إذا فتحت لها، ثم قد يكون لديك لديك واحدة تجاوز السابقة.

378
00:29:25,950 --> 00:29:28,810
هل حفظ تلقائيا؟ أنا لست إيجابية.

379
00:29:35,090 --> 00:29:39,130
هل لديها متكررة؟

380
00:29:39,130 --> 00:29:42,430
يمكننا المشي من خلال ذلك معا إن لم يكن.

381
00:29:46,080 --> 00:29:48,100
فكرة سوف تكون هي نفسها.

382
00:30:00,260 --> 00:30:02,830
تكرارية الحل.

383
00:30:02,830 --> 00:30:07,140
ونحن في طريقنا إلى تريد أن تفعل نفس الفكرة في الأساس

384
00:30:07,140 --> 00:30:16,530
حيث أننا نريد أن تتبع نهاية الجديد للمجموعة وبداية جديدة لمجموعة

385
00:30:16,530 --> 00:30:18,510
وفعل ذلك مرارا وتكرارا.

386
00:30:18,510 --> 00:30:22,430
وإذا كان ما نقوم تتبع وبداية ونهاية تتقاطع من أي وقت مضى،

387
00:30:22,430 --> 00:30:29,020
ثم لم نجد ذلك، ونحن يمكن أن عودة كاذبة.

388
00:30:29,020 --> 00:30:37,540
فكيف أفعل ذلك؟ أي شخص لديك اقتراحات أو رمز بالنسبة لي لسحب ما يصل؟

389
00:30:42,190 --> 00:30:47,450
[طالب] هل حلقة من الوقت. نعم >>.

390
00:30:47,450 --> 00:30:49,450
كنت تريد الذهاب الى القيام حلقة.

391
00:30:49,450 --> 00:30:51,830
>> هل لديك رمز أتمكن من سحب ما يصل، أو ما كنت ذاهب الى توحي؟

392
00:30:51,830 --> 00:30:56,340
[طالب] أعتقد ذلك. حسنا >>. وهذا يجعل الأمور أسهل. ما هو اسمك؟

393
00:30:56,340 --> 00:30:57,890
[طالب] لوكاس.

394
00:31:00,140 --> 00:31:04,190
مراجعة 1. حسنا.

395
00:31:04,190 --> 00:31:13,200
المنخفض هو ما أسميناه تبدأ قبل.

396
00:31:13,200 --> 00:31:17,080
متروك تماما ليس ما كنا نسميها قبل نهاية.

397
00:31:17,080 --> 00:31:22,750
في الواقع، الآن داخل نهاية الصفيف. انها عنصر لا بد أن ننظر.

398
00:31:22,750 --> 00:31:26,890
منخفضة جدا 0، هو ما يصل حجم الصفيف - 1،

399
00:31:26,890 --> 00:31:34,780
ونحن الآن حلقات، ونحن فحص و-

400
00:31:34,780 --> 00:31:37,340
أعتقد يمكنك المشي من خلال ذلك.

401
00:31:37,340 --> 00:31:41,420
ما هو التفكير الخاص بك من خلال هذا؟ المشي لنا من خلال التعليمات البرمجية.

402
00:31:41,420 --> 00:31:49,940
[طالب] بالتأكيد. ننظر إلى قيمة كومة قش في الوسط، وذلك لمقارنة الإبرة.

403
00:31:49,940 --> 00:31:58,520
حتى لو كان أكبر من الإبرة الخاص بك، فإنك ترغب في - أوه، في الواقع، ينبغي أن يكون الوراء.

404
00:31:58,520 --> 00:32:05,180
كنت تريد الذهاب الى رمي بعيدا النصف الأيمن، وهكذا نعم، هذا يجب أن يكون الطريق.

405
00:32:05,180 --> 00:32:08,830
[بودين] لذلك ينبغي أن يكون هذا أقل؟ هل هذا ما قال لك؟ >> [طالب] نعم.

406
00:32:08,830 --> 00:32:10,390
[بودين] حسنا. أقل.

407
00:32:10,390 --> 00:32:15,700
إذا كان الأمر كذلك ما نحن نبحث في أصغر من ما نريد،

408
00:32:15,700 --> 00:32:19,410
ثم نعم، نحن نريد أن نرمي النصف الأيسر،

409
00:32:19,410 --> 00:32:22,210
وهو ما يعني أننا نقوم بتحديث كل ما تفكر

410
00:32:22,210 --> 00:32:26,610
عن طريق تحريك الأقل إلى الحق من الصفيف.

411
00:32:26,610 --> 00:32:30,130
هذا يبدو جيدا.

412
00:32:30,130 --> 00:32:34,550
اعتقد انه لديه نفس المشكلة ان قلنا على واحد السابقة،

413
00:32:34,550 --> 00:32:49,760
حيث إذا منخفضة هو 0 ويرجع 1، ثم منخفضة تصل + / 2 هو الذهاب الى وضع ليكون الشيء نفسه مرة أخرى.

414
00:32:49,760 --> 00:32:53,860
>> وحتى لو كان هذا ليس هو الحال، فإنه لا يزال أكثر كفاءة على أقل تقدير

415
00:32:53,860 --> 00:32:57,630
لمجرد رمي بعيدا العنصر نظرنا فقط الذي نعرفه هو خطأ.

416
00:32:57,630 --> 00:33:03,240
منخفضة جدا + لأعلى / 2 + 1 - >> [طالب] وهذا ينبغي أن يكون في الاتجاه الآخر.

417
00:33:03,240 --> 00:33:05,900
[بودين] أو هذا ينبغي أن يكون - 1، والآخر يجب أن يكون + 1.

418
00:33:05,900 --> 00:33:09,580
[طالب] ويجب أن يكون هناك علامة يساوي مزدوجة. >> [بودين] نعم.

419
00:33:09,580 --> 00:33:11,340
[طالب] نعم.

420
00:33:14,540 --> 00:33:15,910
حسنا.

421
00:33:15,910 --> 00:33:21,280
وأخيرا، الآن أن لدينا هذا 1 + - 1 الشيء،

422
00:33:21,280 --> 00:33:31,520
هل هو - أنه قد لا يكون - هل من الممكن من أي وقت مضى لانخفاض في نهاية المطاف مع قيمة أكبر من يصل؟

423
00:33:35,710 --> 00:33:40,320
أعتقد أن الطريقة الوحيدة التي يمكن أن يحدث - هل من الممكن؟ >> [طالب] أنا لا أعرف.

424
00:33:40,320 --> 00:33:45,220
ولكن إذا كان يحصل على اقتطاع ومن ثم يحصل أن 1 ناقص ومن ثم - نعم >>.

425
00:33:45,220 --> 00:33:47,480
[طالب] وربما الحصول على وعابث.

426
00:33:49,700 --> 00:33:53,940
وأعتقد أنه يجب أن تكون جيدة فقط ل

427
00:33:53,940 --> 00:33:58,800
لذلك ينتهي بهم الأمر إلى انخفاض أنها يجب أن تكون على قدم المساواة، على ما أعتقد.

428
00:33:58,800 --> 00:34:03,070
ولكن إذا كانوا على قدم المساواة، ثم ونحن لن فعلت حلقة حين لتبدأ

429
00:34:03,070 --> 00:34:06,670
وكنا قد عادوا للتو القيمة. لذلك أعتقد نحن في حالة جيدة الآن.

430
00:34:06,670 --> 00:34:11,530
لاحظت أنه على الرغم من هذه المشكلة لم تعد متكررة،

431
00:34:11,530 --> 00:34:17,400
نفس النوع من الأفكار تنطبق حيث يمكننا أن نرى كيف أن هذا يفسح المجال بسهولة

432
00:34:17,400 --> 00:34:23,659
عودي إلى حل من حقيقة أننا مجرد تحديث مؤشرات مرارا وتكرارا،

433
00:34:23,659 --> 00:34:29,960
نحن جعل المشكلة أصغر وأصغر، ونحن نركز على مجموعة فرعية من مجموعة.

434
00:34:29,960 --> 00:34:40,860
[طالب] إذا منخفضة هو 0 وحتى 1، وكلاهما يكون 0 + 1/2، التي من شأنها أن تذهب إلى 0،

435
00:34:40,860 --> 00:34:44,429
ومن ثم يمكن لأحد أن يكون + 1، فإن للمرء أن يكون - 1.

436
00:34:47,000 --> 00:34:50,870
[طالب] أين نحن فحص المساواة؟

437
00:34:50,870 --> 00:34:55,100
مثل إذا واحد هو في الواقع الأوسط إبرة؟

438
00:34:55,100 --> 00:34:58,590
نحن لا نقوم حاليا ذلك؟ أوه!

439
00:35:00,610 --> 00:35:02,460
إذا it's -

440
00:35:05,340 --> 00:35:13,740
نعم. يمكننا القيام به وليس فقط اختبار إلى هنا لأن دعونا نقول منتصف الأولى -

441
00:35:13,740 --> 00:35:16,430
[طالب] انها في الواقع ليست مثل رمي بعيدا محدد.

442
00:35:16,430 --> 00:35:20,220
حتى إذا كنت رمي ​​بعيدا محدد، لديك للتحقق من ذلك الأول أو أيا كان.

443
00:35:20,220 --> 00:35:23,350
ه. نعم. >> [طالب] نعم.

444
00:35:23,350 --> 00:35:29,650
حتى الآن لقد وضعنا بعيدا واحدة ونحن ننظر حاليا في،

445
00:35:29,650 --> 00:35:33,260
وهو ما يعني أننا في حاجة الآن لدينا أيضا

446
00:35:33,260 --> 00:35:44,810
إذا كان (كومة قش [(الأقل حتى +) / 2] == إبرة)، ثم يمكننا العودة الحقيقية.

447
00:35:44,810 --> 00:35:52,070
وعما إذا كان أضع آخر أو كما لو أنه يعني حرفيا الشيء نفسه

448
00:35:52,070 --> 00:35:57,110
لأن عادوا هذا صحيح.

449
00:35:57,110 --> 00:36:01,450
وهكذا لن أضع الا اذا، ولكن لا يهم.

450
00:36:01,450 --> 00:36:10,440
>> آخر حتى إذا كان آخر، هذا هذا، وهذا هو الشيء المشترك أفعل

451
00:36:10,440 --> 00:36:14,340
حيث حتى لو كان هو الحالة التي يكون فيها كل شيء جيد هنا،

452
00:36:14,340 --> 00:36:22,780
مثل انخفاض لا يمكن أبدا أن تكون أكبر من يصل، انها ليست حول ما إذا كان يستحق التفكير هذا صحيح.

453
00:36:22,780 --> 00:36:28,010
لذلك قد كذلك يقول بينما هو انخفاض أقل من أو يساوي

454
00:36:28,010 --> 00:36:30,720
أو أثناء المنخفض أقل من

455
00:36:30,720 --> 00:36:35,300
حتى إذا كانت تساوي أو منخفضة من أي وقت مضى يحدث لتمرير ما يصل،

456
00:36:35,300 --> 00:36:40,130
ثم يمكننا الخروج من هذه الحلقة.

457
00:36:41,410 --> 00:36:44,630
الأسئلة والشواغل والتعليقات؟

458
00:36:47,080 --> 00:36:49,270
حسنا. هذا يبدو جيدا.

459
00:36:49,270 --> 00:36:52,230
الآن نريد أن نفعله الفرز.

460
00:36:52,230 --> 00:37:04,030
إذا ذهبنا إلى مراجعة بلدي الثاني، ونحن نرى نفس هذه الأرقام،

461
00:37:04,030 --> 00:37:07,550
ولكن الآن أنها لم تعد من أجل فرزها.

462
00:37:07,550 --> 00:37:12,840
ونحن نريد لتنفيذ الفرز باستخدام أي خوارزمية في O ن ن سجل.

463
00:37:12,840 --> 00:37:17,240
ذلك الذي خوارزمية هل أعتقد أننا ينبغي أن تنفذ هنا؟ >> [طالب] الترتيب دمج.

464
00:37:17,240 --> 00:37:23,810
[بودين] نعم. دمج النوع هو O (N سجل ن)، بحيث ما نحن بصدد القيام به.

465
00:37:23,810 --> 00:37:26,680
والمشكلة ستكون مشابهة جدا،

466
00:37:26,680 --> 00:37:31,920
حيث يضفي نفسها بسهولة إلى حل العودية.

467
00:37:31,920 --> 00:37:35,580
يمكننا تأتي أيضا مع حل تكرارية إذا كنا نريد،

468
00:37:35,580 --> 00:37:42,540
ولكن سوف يكون من الأسهل العودية وهنا ينبغي لنا أن نفعل العودية.

469
00:37:45,120 --> 00:37:49,530
أعتقد أننا سوف يسير من خلال دمج النوع الأول،

470
00:37:49,530 --> 00:37:54,280
على الرغم من أن هناك فيديو جميل على دمج النوع بالفعل. [ضحك]

471
00:37:54,280 --> 00:37:59,780
دمج النوع حتى هناك - وأنا إضاعة الكثير لهذه الورقة.

472
00:37:59,780 --> 00:38:02,080
أوه، هناك واحدة فقط من الزمن.

473
00:38:02,080 --> 00:38:03,630
دمج ذلك.

474
00:38:08,190 --> 00:38:12,470
أوه، 1، 3، 5.

475
00:38:26,090 --> 00:38:27,440
حسنا.

476
00:38:29,910 --> 00:38:33,460
دمج يأخذ اثنين صفائف منفصلة.

477
00:38:33,460 --> 00:38:36,780
على حد سواء بشكل فردي مصنفة تلك المصفوفات اثنين.

478
00:38:36,780 --> 00:38:40,970
لذلك هذه المجموعة، 1، 3، 5، فرزها. هذه المجموعة، 0، 2، 4، فرزها.

479
00:38:40,970 --> 00:38:46,710
الآن ما يجب عليك فعله هو دمج الجمع بينها في مجموعة واحدة التي هي في حد ذاتها فرزها.

480
00:38:46,710 --> 00:38:57,130
لذلك نحن نريد مجموعة من حجم 6 التي ستكون لدينا هذه العناصر داخل منه

481
00:38:57,130 --> 00:38:59,390
من أجل فرزها.

482
00:38:59,390 --> 00:39:03,390
>> وحتى نتمكن من الاستفادة من حقيقة أن يتم تصنيف هذه صفيفين

483
00:39:03,390 --> 00:39:06,800
للقيام بذلك في الوقت الخطية،

484
00:39:06,800 --> 00:39:13,510
معنى الخطية إذا كانت هذه المرة هي مجموعة X الحجم وهذا هو حجم Y،

485
00:39:13,510 --> 00:39:20,970
ثم يجب أن تكون الخوارزمية مجموع O (X + Y). حسنا.

486
00:39:20,970 --> 00:39:23,150
حتى اقتراحات.

487
00:39:23,150 --> 00:39:26,030
[طالب] هل يمكن أن نبدأ من اليسار؟

488
00:39:26,030 --> 00:39:30,150
لذلك عليك وضع ال 0 إلى أسفل أولا ثم 1 ثم هنا كنت في ال 2.

489
00:39:30,150 --> 00:39:33,320
لذلك نوع من مثل لديك علامة التبويب التي تتحرك إلى اليمين. >> [بودين] نعم.

490
00:39:33,320 --> 00:39:41,070
لكل من هذه المصفوفات إذا ركزنا فقط على العنصر الموجود في أقصى اليسار.

491
00:39:41,070 --> 00:39:43,530
لأن كل من يتم فرز المصفوفات، ونحن نعلم أن هذه الأركان 2

492
00:39:43,530 --> 00:39:46,920
هي أصغر العناصر في أي مجموعة.

493
00:39:46,920 --> 00:39:53,500
وهذا يعني أن 1 من هذه العناصر 2 يجب أن يكون أصغر عنصر في مجموعتنا المدمجة.

494
00:39:53,500 --> 00:39:58,190
انها مجرد أن ذلك يحدث أصغر هي واحد على هذا هو الوقت المناسب.

495
00:39:58,190 --> 00:40:02,580
لذلك نحن نأخذ 0، أدخله على اليسار لأن 0 أقل من 1،

496
00:40:02,580 --> 00:40:08,210
حتى تأخذ 0، أدخلها في موقفنا أولا، ثم نقوم بتحديث هذه

497
00:40:08,210 --> 00:40:12,070
لنركز الآن على العنصر الأول.

498
00:40:12,070 --> 00:40:14,570
والآن نكرر.

499
00:40:14,570 --> 00:40:20,670
حتى الآن ما قارنا 2 و 1. 1 هو أصغر، لذلك سنقوم بإدراج 1.

500
00:40:20,670 --> 00:40:25,300
نقوم بتحديث هذا المؤشر للإشارة إلى هذا الرجل.

501
00:40:25,300 --> 00:40:33,160
الآن نحن نفعل ذلك مرة أخرى، لذلك 2. وهذا التحديث، قارن هذه 2، 3.

502
00:40:33,160 --> 00:40:37,770
هذه التحديثات، ثم 4 و 5.

503
00:40:37,770 --> 00:40:42,110
بحيث يتم الدمج.

504
00:40:42,110 --> 00:40:49,010
>> وينبغي أن يكون واضحا جدا أن الوقت قد حان منذ الخطية نذهب فقط عبر كل عنصر مرة واحدة.

505
00:40:49,010 --> 00:40:55,980
وهذا هو أكبر خطوة لتنفيذ دمج النوع يقوم به هذا.

506
00:40:55,980 --> 00:40:59,330
وانها ليست بالأمر الصعب.

507
00:40:59,330 --> 00:41:15,020
بضعة أشياء ما يدعو للقلق هو دعونا نقول كنا دمج 1، 2، 3، 4، 5، 6.

508
00:41:15,020 --> 00:41:30,930
في هذه الحالة نحن في نهاية المطاف في السيناريو هذا واحد حيث سيكون أصغر حجما،

509
00:41:30,930 --> 00:41:36,160
ثم نقوم بتحديث هذا المؤشر، هذا واحد سيكون أصغر حجما وتحديث هذا،

510
00:41:36,160 --> 00:41:41,280
هذا واحد من أصغر، والآن عليك أن تعترف

511
00:41:41,280 --> 00:41:44,220
عندما كنت فعلا نفدت عناصر للمقارنة مع.

512
00:41:44,220 --> 00:41:49,400
منذ أننا استنفدنا بالفعل هذه المجموعة بأكملها،

513
00:41:49,400 --> 00:41:55,190
الآن كل شيء في هذه المجموعة للتو بإدراجه في هنا.

514
00:41:55,190 --> 00:42:02,040
إذا كان الأمر كذلك فإننا نتعرض إلى أي وقت مضى إلى النقطة التي يتم دمج تماما لدينا واحدة من صفائف بالفعل،

515
00:42:02,040 --> 00:42:06,510
ثم نأخذ فقط كل عناصر مجموعة أخرى وإدراجها في نهاية الصفيف.

516
00:42:06,510 --> 00:42:13,630
حتى نتمكن من مجرد إدراج 4، 5، 6. حسنا.

517
00:42:13,630 --> 00:42:18,070
وهذا هو شيء واحد لمشاهدة ل.

518
00:42:22,080 --> 00:42:26,120
تنفيذ ذلك يجب أن يكون الخطوة 1.

519
00:42:26,120 --> 00:42:32,600
دمج فرز ثم بناء على ذلك، فإنه من 2 خطوات، 2 الخطوات سخيفة.

520
00:42:38,800 --> 00:42:42,090
دعونا نعطي هذه المجموعة فقط.

521
00:42:57,920 --> 00:43:05,680
دمج النوع حتى، هو الخطوة 1 لكسر متكرر الصفيف الى نصفين.

522
00:43:05,680 --> 00:43:09,350
تقسيم هذه المجموعة حتى الى نصفين.

523
00:43:09,350 --> 00:43:22,920
لدينا الآن 4، 15، 16، 50 و 8، 23، 42، 108.

524
00:43:22,920 --> 00:43:25,800
والآن نحن نفعل ذلك مرة أخرى ويمكننا تقسيم هذه الى نصفين.

525
00:43:25,800 --> 00:43:27,530
أنا فقط تفعل ذلك في هذا الجانب.

526
00:43:27,530 --> 00:43:34,790
SO 4 و 15 و 16 و 50.

527
00:43:34,790 --> 00:43:37,440
ونحن نفعل نفس الشيء هنا.

528
00:43:37,440 --> 00:43:40,340
وتقسيم ونحن الآن مرة أخرى إلى نصفين.

529
00:43:40,340 --> 00:43:51,080
ونحن لدينا 4، 15، 16، 50.

530
00:43:51,080 --> 00:43:53,170
بحيث هو قضيتنا الأساسية.

531
00:43:53,170 --> 00:44:00,540
مرة واحدة في المصفوفات ذات حجم 1، ثم نتوقف مع تنقسم الى نصفين.

532
00:44:00,540 --> 00:44:03,190
>> الآن ماذا نفعل مع هذا؟

533
00:44:03,190 --> 00:44:15,730
نحن في نهاية المطاف سوف كسر هذا أيضا أسفل إلى 8، 23، 42، و 108.

534
00:44:15,730 --> 00:44:24,000
حتى الآن أننا في هذه المرحلة، الخطوة الآن اثنين من نوع الدمج ودمج أزواج فقط للقوائم.

535
00:44:24,000 --> 00:44:27,610
لذلك نحن نريد لدمج هذه. ندعو فقط الدمج.

536
00:44:27,610 --> 00:44:31,410
نحن نعرف دمج هذه سيعود من أجل فرزها.

537
00:44:31,410 --> 00:44:33,920
4، 15.

538
00:44:33,920 --> 00:44:41,440
الآن نريد أن دمج هذه، والتي سيعود قائمة مع تلك من أجل فرزها،

539
00:44:41,440 --> 00:44:44,160
16، 50.

540
00:44:44,160 --> 00:44:57,380
نحن دمج تلك - لا أستطيع أن أكتب - 8، 23 و 42 و 108.

541
00:44:57,380 --> 00:45:02,890
لذلك لدينا أزواج المدمجة مرة واحدة.

542
00:45:02,890 --> 00:45:05,140
الآن نحن فقط دمج مرة أخرى.

543
00:45:05,140 --> 00:45:10,130
تلاحظ أن يتم فرز كل من هذه القوائم في حد ذاته،

544
00:45:10,130 --> 00:45:15,220
وبعد ذلك يمكننا دمج هذه القوائم فقط للحصول على قائمة من حجم 4 التي تم فرزها

545
00:45:15,220 --> 00:45:19,990
ودمج هاتين القائمتين للحصول على قائمة من حجم 4 التي تم فرزها.

546
00:45:19,990 --> 00:45:25,710
وأخيرا، يمكننا دمج هاتين القائمتين من حجم 4 للحصول على قائمة واحدة من حجم 8 التي تم فرزها.

547
00:45:25,710 --> 00:45:34,030
ذلك أن نرى أن هذا هو العام ن ن السجل، رأينا بالفعل أن الدمج هو الخطية،

548
00:45:34,030 --> 00:45:40,390
لذلك عندما نتعامل مع دمج هذه، لذلك مثل التكلفة الإجمالية للدمج

549
00:45:40,390 --> 00:45:43,410
لهذه القائمتين هو 2 فقط لأنه -

550
00:45:43,410 --> 00:45:49,610
أو جيدا، انها O ن، ن ولكن هنا هو مجرد هذه العناصر 2، لذلك فمن 2.

551
00:45:49,610 --> 00:45:52,850
وسوف تكون هذه 2 2 و 2 سوف تكون هذه 2 و 2 سيكون هذه 2،

552
00:45:52,850 --> 00:45:58,820
لذلك عبر كل من دمج أننا بحاجة إلى القيام به، نلجأ إلى القيام ن.

553
00:45:58,820 --> 00:46:03,210
مثل 2 + 2 + 2 + 2 هو 8، وهو ن،

554
00:46:03,210 --> 00:46:08,060
ذلك هو ن تكلفة دمج في هذه المجموعة.

555
00:46:08,060 --> 00:46:10,810
ثم نفس الشيء هنا.

556
00:46:10,810 --> 00:46:16,980
سنقوم دمج هذه 2، ثم هذه 2، وحدة الدمج هذه سوف يستغرق أربع عمليات،

557
00:46:16,980 --> 00:46:23,610
وهذا الدمج اتخاذ أربع عمليات، ولكن مرة أخرى، وبين كل هذه،

558
00:46:23,610 --> 00:46:29,030
نحن في نهاية المطاف دمج ن مجموع الأشياء، وهكذا يأخذ هذه الخطوة ن.

559
00:46:29,030 --> 00:46:33,670
وهكذا يأخذ كل مستوى العناصر التي اندمجت ن.

560
00:46:33,670 --> 00:46:36,110
>> وكيف العديد من المستويات هناك؟

561
00:46:36,110 --> 00:46:40,160
على كل مستوى، لدينا مجموعة ينمو حسب حجم 2.

562
00:46:40,160 --> 00:46:44,590
هنا لدينا هي صفائف من حجم 1، هنا انهم من حجم 2، هنا انهم من حجم 4،

563
00:46:44,590 --> 00:46:46,470
وأخيرا، وانهم من حجم 8.

564
00:46:46,470 --> 00:46:56,450
منذ ذلك يتضاعف، وهناك سيكون ما مجموعه سجل ن من هذه المستويات.

565
00:46:56,450 --> 00:47:02,090
حتى مع دخول ن المستويات، المستوى الفردي مع كل ن إجمالي العمليات،

566
00:47:02,090 --> 00:47:05,720
نحصل على السجل ن ن الخوارزمية.

567
00:47:05,720 --> 00:47:07,790
الأسئلة؟

568
00:47:08,940 --> 00:47:13,320
لقد جعل الناس بالفعل تقدما بشأن كيفية تنفيذ ذلك؟

569
00:47:13,320 --> 00:47:18,260
هو أي شخص بالفعل في حالة حيث يمكنني سحب للتو التعليمات البرمجية الخاصة بهم؟

570
00:47:20,320 --> 00:47:22,260
وأستطيع أن أعطي لمدة دقيقة.

571
00:47:24,770 --> 00:47:27,470
هذا واحد سيكون لفترة أطول.

572
00:47:27,470 --> 00:47:28,730
أنا أوصي تتكرر -

573
00:47:28,730 --> 00:47:30,510
لم يكن لديك للقيام العودية لدمج

574
00:47:30,510 --> 00:47:33,750
لأن القيام العودية لدمج، وأنت تسير لدينا لتمرير مجموعة من مختلف الأحجام.

575
00:47:33,750 --> 00:47:37,150
يمكنك، لكنه مزعج.

576
00:47:37,150 --> 00:47:43,720
ولكن العودية لنوع نفسه من السهل جدا.

577
00:47:43,720 --> 00:47:49,190
كنت للتو دعوة حرفيا النوع على النصف الأيسر، النصف الأيمن على نوع. حسنا.

578
00:47:51,770 --> 00:47:54,860
أي شخص لديه أي شيء أستطيع سحب ما يصل بعد؟

579
00:47:54,860 --> 00:47:57,540
وإلا سوف أعطي لمدة دقيقة.

580
00:47:58,210 --> 00:47:59,900
حسنا.

581
00:47:59,900 --> 00:48:02,970
أي شخص يحصل شيء يمكننا العمل معها؟

582
00:48:05,450 --> 00:48:09,680
وإلا سوف نعمل فقط مع هذا ومن ثم التوسع من هناك.

583
00:48:09,680 --> 00:48:14,050
>> أي شخص لديها أكثر من هذا أستطيع أن سحب ما يصل؟

584
00:48:14,050 --> 00:48:17,770
[طالب] نعم. يمكنك سحب ما يصل الألغام. حسنا >>.

585
00:48:17,770 --> 00:48:19,730
نعم!

586
00:48:22,170 --> 00:48:25,280
[طالب] كان هناك الكثير من الشروط. أوه >>، واطلاق النار. يمكنك -

587
00:48:25,280 --> 00:48:28,110
[طالب] لدي لحفظه. نعم >>.

588
00:48:32,420 --> 00:48:35,730
وكذلك فعل نقوم به الدمج بشكل منفصل.

589
00:48:35,730 --> 00:48:38,570
أوه، ولكنها ليست سيئة لهذه الدرجة.

590
00:48:39,790 --> 00:48:41,650
حسنا.

591
00:48:41,650 --> 00:48:47,080
لذلك هو في حد ذاته نوع فقط يدعو mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
يشرح لنا ما mergeSortHelp لا.

593
00:48:49,530 --> 00:48:55,700
[طالب] MergeSortHelp جميلة لا بكثير الخطوات الرئيسيتين،

594
00:48:55,700 --> 00:49:01,270
وهو لفرز كل شوط من الصفيف ثم دمج كل منهما.

595
00:49:04,960 --> 00:49:08,050
[بودين] حسنا، حتى تعطي لي الثانية.

596
00:49:10,850 --> 00:49:13,210
وأعتقد أن هذا - >> [طالب] ولست بحاجة ل-

597
00:49:17,100 --> 00:49:19,400
نعم. أنا في عداد المفقودين شيئا.

598
00:49:19,400 --> 00:49:23,100
في الدمج، وأنا أدرك أنني بحاجة إلى إنشاء مجموعة جديدة

599
00:49:23,100 --> 00:49:26,530
لأن أنا لا يمكن أن تفعل ذلك في المكان. نعم >>. لا يمكنك. تصحيح.

600
00:49:26,530 --> 00:49:28,170
[طالب] لذلك أنا خلق مجموعة جديدة.

601
00:49:28,170 --> 00:49:31,510
لقد نسيت في نهاية دمج لإعادة تغيير.

602
00:49:31,510 --> 00:49:34,490
حسنا. نحن بحاجة إلى مجموعة جديدة.

603
00:49:34,490 --> 00:49:41,000
في دمج النوع، وهذا هو دائما تقريبا صحيح.

604
00:49:41,000 --> 00:49:44,340
جزء من تكلفة خوارزمية أفضل وقت الحكيم

605
00:49:44,340 --> 00:49:47,310
هو دائما تقريبا التي تحتاج لاستخدام الذاكرة أكثر قليلا.

606
00:49:47,310 --> 00:49:51,570
حتى هنا، بغض النظر عن كيفية القيام دمج النوع،

607
00:49:51,570 --> 00:49:54,780
قد تحتاج حتما إلى استخدام بعض الذاكرة الإضافية.

608
00:49:54,780 --> 00:49:58,240
هو أو هي إنشاء مجموعة جديدة.

609
00:49:58,240 --> 00:50:03,400
ثم يقول في النهاية نحن بحاجة فقط لنسخ مجموعة جديدة في مجموعة الأصلي.

610
00:50:03,400 --> 00:50:04,830
[طالب] أعتقد ذلك، نعم.

611
00:50:04,830 --> 00:50:08,210
أنا لا أعرف ما اذا كان يعمل من حيث العد بالرجوع أو أيا كان -

612
00:50:08,210 --> 00:50:11,650
نعم، أنه سوف يعمل. >> [طالب] حسنا.

613
00:50:20,620 --> 00:50:24,480
هل جربت تشغيل هذا؟ >> [طالب] لا، ليس بعد. حسنا >>.

614
00:50:24,480 --> 00:50:28,880
حاول تشغيل، ثم سأتحدث عن ذلك لثانية واحدة.

615
00:50:28,880 --> 00:50:35,200
[طالب] أنا بحاجة إلى كل النماذج الدالة وكل شيء، على الرغم من، أليس كذلك؟

616
00:50:37,640 --> 00:50:40,840
وظيفة النماذج. أوه، كنت تعني مثل - نعم.

617
00:50:40,840 --> 00:50:43,040
نوع تدعو mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> لذلك من أجل ترتيب لدعوة mergeSortHelp، يجب إما mergeSortHelp تم تعريفها

619
00:50:47,390 --> 00:50:56,370
قبل الفرز أو نحن فقط في حاجة إلى النموذج. مجرد نسخ ولصق ذلك.

620
00:50:56,370 --> 00:50:59,490
وبالمثل، mergeSortHelp تدعو دمج،

621
00:50:59,490 --> 00:51:03,830
ولكن لم يتم دمج تحدد بعد، حتى نتمكن من مجرد السماح mergeSortHelp تعرف

622
00:51:03,830 --> 00:51:08,700
أن هذا ما يجري دمج لتبدو وكأنها، وانتهى الأمر.

623
00:51:09,950 --> 00:51:15,730
حتى mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
لدينا مشكلة هنا حيث لدينا قاعدة بأي حال من الأحوال.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp هو عودي، عودي حتى أي وظيفة

626
00:51:38,110 --> 00:51:42,610
سوف تحتاج الى بعض النوع من الحالة الأساسية أن تعرف متى تتوقف بشكل متكرر يدعو نفسه.

627
00:51:42,610 --> 00:51:45,590
ما حالتنا ستكون قاعدة هنا؟ نعم.

628
00:51:45,590 --> 00:51:49,110
[طالب] إذا كان حجم هو 1؟ >> [بودين] نعم.

629
00:51:49,110 --> 00:51:56,220
مثل ذلك رأينا هناك حق، توقفنا صفائف تقسيم

630
00:51:56,220 --> 00:52:01,850
عندما وصلنا إلى صفائف حجم 1، والذي حتما يتم تصنيف أنفسهم.

631
00:52:01,850 --> 00:52:09,530
حتى إذا كان حجم يساوي 1، ونحن نعلم بالفعل يتم فرز الصفيف،

632
00:52:09,530 --> 00:52:12,970
حتى نتمكن من العودة فقط.

633
00:52:12,970 --> 00:52:16,880
>> تلاحظ أن هذا الفراغ، لذلك نحن لا يعودون أي شيء خاص، نعود فقط.

634
00:52:16,880 --> 00:52:19,580
حسنا. بحيث لقضيتنا الأساسية.

635
00:52:19,580 --> 00:52:27,440
أعتقد حالتنا قاعدة يمكن أيضا أن يكون إذا كان لنا أن يحدث ليكون دمج مجموعة من حجم 0،

636
00:52:27,440 --> 00:52:30,030
ربما نريد التوقف عند نقطة ما،

637
00:52:30,030 --> 00:52:33,610
لذلك يمكننا القول فقط حجم أقل من 2 أو أقل من أو يساوي 1

638
00:52:33,610 --> 00:52:37,150
بحيث هذا العمل لأي مجموعة الآن.

639
00:52:37,150 --> 00:52:38,870
حسنا.

640
00:52:38,870 --> 00:52:42,740
بحيث لقضيتنا الأساسية.

641
00:52:42,740 --> 00:52:45,950
الآن تريد أن المشي من خلال دمج لنا؟

642
00:52:45,950 --> 00:52:49,140
ماذا يعني كل هذه الحالات؟

643
00:52:49,140 --> 00:52:54,480
هنا، نقوم به مجرد فكرة نفسها، -

644
00:52:56,970 --> 00:53:02,470
[طالب] I تحتاج إلى تمرير جميع المكالمات مع حجم mergeSortHelp و.

645
00:53:02,470 --> 00:53:10,080
أضفت حجم باعتبارها الأولية إضافية وانها ليست هناك، مثل حجم / 2.

646
00:53:10,080 --> 00:53:16,210
[بودين] أوه، حجم / 2، وحجم / 2. >> [طالب] نعم، وأيضا في وظيفة أعلاه أيضا.

647
00:53:16,210 --> 00:53:21,320
[بودين] هنا؟ >> [طالب] فقط الحجم. >> [بودين] أوه. الحجم، حجم؟ >> [طالب] نعم.

648
00:53:21,320 --> 00:53:23,010
[بودين] حسنا.

649
00:53:23,010 --> 00:53:26,580
اسمحوا لي أن التفكير للحظة.

650
00:53:26,580 --> 00:53:28,780
لا اجهتنا مشكلة؟

651
00:53:28,780 --> 00:53:33,690
نحن دائما علاج اليسار ك 0. >> [طالب] رقم

652
00:53:33,690 --> 00:53:36,340
وهذا خطأ أيضا. آسف. ينبغي أن يكون البداية. نعم.

653
00:53:36,340 --> 00:53:39,230
[بودين] حسنا. أود أن أفضل.

654
00:53:39,230 --> 00:53:43,880
ونهاية. حسنا.

655
00:53:43,880 --> 00:53:47,200
حتى الآن لا تريد السير بنا من خلال دمج؟ >> [طالب] حسنا.

656
00:53:47,200 --> 00:53:52,150
أنا مجرد المشي من خلال هذه المجموعة الجديدة التي قمت بإنشائه.

657
00:53:52,150 --> 00:53:57,420
حجمه هو حجم ذلك الجزء من مجموعة أننا نريد أن يكون فرز

658
00:53:57,420 --> 00:54:03,460
ومحاولة للعثور على العناصر التي ينبغي لي أن وضعت في خطوة مجموعة جديدة.

659
00:54:03,460 --> 00:54:10,140
حتى للقيام بذلك، أولا أنا التحقق إذا كان النصف الأيسر من مجموعة عناصر ما زالت تعاني من أي أكثر من ذلك،

660
00:54:10,140 --> 00:54:14,260
وإذا لم يحدث ذلك، ثم تذهب الى هذا الشرط آخر، والتي تقول فقط

661
00:54:14,260 --> 00:54:20,180
حسنا، يجب أن يكون الحق في الصفيف، ونحن سوف أضع ذلك في الفهرس الحالي من newArray.

662
00:54:20,180 --> 00:54:27,620
>> ثم خلاف ذلك، وأنا التحقق إذا تم الانتهاء أيضا الجانب الأيمن من الصفيف،

663
00:54:27,620 --> 00:54:30,630
في هذه الحالة أنا فقط وضعت في اليسار.

664
00:54:30,630 --> 00:54:34,180
قد لا يكون في الواقع أن الضرورة. لست متأكدا.

665
00:54:34,180 --> 00:54:40,970
ولكن على أي حال، والآخران الاختيار أي من هما أصغر في اليسار أو اليمين.

666
00:54:40,970 --> 00:54:49,770
وأيضا في كل حالة، وأنا تزايد أيهما نائب I زيادة.

667
00:54:49,770 --> 00:54:52,040
[بودين] حسنا.

668
00:54:52,040 --> 00:54:53,840
التي تبدو جيدة.

669
00:54:53,840 --> 00:54:58,800
هل لديها تعليقات أو أسئلة أو مخاوف؟

670
00:55:00,660 --> 00:55:07,720
وبالتالي فإن أربع حالات التي لدينا لتحقيق الأشياء إلى الوجود فقط - أو يبدو الخمس -

671
00:55:07,720 --> 00:55:13,100
ولكن علينا أن ننظر ما إذا كان اليسار ومجموعة ينفد من الاشياء ونحن بحاجة لدمج،

672
00:55:13,100 --> 00:55:16,390
ما إذا كان قد تشغيل مجموعة الحق في الخروج من الأشياء التي تحتاج إلى دمج -

673
00:55:16,390 --> 00:55:18,400
أنا لافتا في شيء.

674
00:55:18,400 --> 00:55:21,730
حتى ما إذا كانت مجموعة اليسار قد نفد من الأشياء أو مجموعة الحق قد نفد من الأشياء.

675
00:55:21,730 --> 00:55:24,320
تلك هي حالتين.

676
00:55:24,320 --> 00:55:30,920
نحن بحاجة أيضا حالة ما إذا كانت تافهة من الصواب أقل من الصواب.

677
00:55:30,920 --> 00:55:33,910
ثم نريد أن اختيار الصواب.

678
00:55:33,910 --> 00:55:37,630
تلك هي الحالات.

679
00:55:37,630 --> 00:55:40,990
لذلك كان هذا الحق، لذلك هذا هو ذلك.

680
00:55:40,990 --> 00:55:46,760
ترك مجموعة. انها 1، 2، 3. حسنا. لذا نعم، تلك هي الأمور الأربعة أننا قد ترغب في القيام به.

681
00:55:50,350 --> 00:55:54,510
ونحن لن نذهب أكثر تكرارية الحل.

682
00:55:54,510 --> 00:55:55,980
لا أنصح -

683
00:55:55,980 --> 00:56:03,070
دمج النوع هو مثال على وظيفة في آن معا لا ذيل متكررة،

684
00:56:03,070 --> 00:56:07,040
انها ليست سهلة لجعله ذيل متكررة،

685
00:56:07,040 --> 00:56:13,450
ولكن أيضا ليس من السهل جدا أن تجعل من تكرارية.

686
00:56:13,450 --> 00:56:16,910
هذا من السهل جدا.

687
00:56:16,910 --> 00:56:19,170
هذا النوع من تنفيذ الدمج،

688
00:56:19,170 --> 00:56:22,140
دمج، بغض النظر عن ما تفعله، وأنت تسير لبناء الدمج.

689
00:56:22,140 --> 00:56:29,170
>> دمج النوع حتى بنيت على رأس الدمج بشكل متكرر فقط هذه الخطوط الثلاثة.

690
00:56:29,170 --> 00:56:34,700
تكراري، هو أكثر مزعج وأكثر صعوبة للتفكير.

691
00:56:34,700 --> 00:56:41,860
ولكن لاحظ أنه ليس من الذيل متكررة منذ mergeSortHelp - عندما تطلق على نفسها -

692
00:56:41,860 --> 00:56:46,590
ما زال يحتاج إلى فعل الأشياء بعد هذه المكالمة عوائد متكررة.

693
00:56:46,590 --> 00:56:50,830
لذلك يجب أن هذا الإطار مكدس لا تزال موجودة حتى بعد استدعاء هذا.

694
00:56:50,830 --> 00:56:54,170
ثم عند استدعاء هذا، يجب أن الإطار مكدس لا تزال موجودة

695
00:56:54,170 --> 00:56:57,780
لأنه حتى بعد هذا النداء، ونحن لا تزال بحاجة إلى الدمج.

696
00:56:57,780 --> 00:57:01,920
ومن غير بديهي لجعل هذا الذيل العودية.

697
00:57:04,070 --> 00:57:06,270
الأسئلة؟

698
00:57:08,300 --> 00:57:09,860
حسنا.

699
00:57:09,860 --> 00:57:13,400
الذهاب حتى العودة لفرز - أوه، هناك شيئان اريد ان تظهر. حسنا.

700
00:57:13,400 --> 00:57:17,840
العودة للترتيب، سوف نفعل ذلك بسرعة.

701
00:57:17,840 --> 00:57:21,030
أو البحث. نوع؟ الفرز. نعم.

702
00:57:21,030 --> 00:57:22,730
العودة إلى بدايات الفرز.

703
00:57:22,730 --> 00:57:29,870
نريد لإنشاء خوارزمية فرز الصفيف باستخدام أي خوارزمية

704
00:57:29,870 --> 00:57:33,660
في O ن.

705
00:57:33,660 --> 00:57:40,860
فكيف يكون هذا ممكنا؟ هل لديها أي نوع من ال -

706
00:57:40,860 --> 00:57:44,300
I لمح قبل في -

707
00:57:44,300 --> 00:57:48,300
إذا نحن على وشك تحسين سجل من لا يوجد لO ن،

708
00:57:48,300 --> 00:57:51,450
فقد قمنا بتحسين خوارزمية وقتنا الحكيم،

709
00:57:51,450 --> 00:57:55,250
وهو ما يعني ما نحن ذاهبون إلى القيام به للتعويض عن ذلك؟

710
00:57:55,250 --> 00:57:59,520
[طالب] الفضاء. نعم >>. ونحن في طريقنا إلى استخدام مساحة أكبر.

711
00:57:59,520 --> 00:58:04,490
وليس حتى مجرد مساحة أكبر، انها مساحة أكثر أضعافا مضاعفة.

712
00:58:04,490 --> 00:58:14,320
لذلك أعتقد أن هذا النوع من الخوارزمية هو شيء زائف، زائف polynom -

713
00:58:14,320 --> 00:58:18,980
الزائفة - لا أستطيع تذكر. الزائفة شيء.

714
00:58:18,980 --> 00:58:22,210
ولكن هذا لأننا في حاجة إلى استخدام الكثير من الفضاء

715
00:58:22,210 --> 00:58:28,610
أن هذا يمكن تحقيقه ولكن واقعية لا.

716
00:58:28,610 --> 00:58:31,220
>> وكيف يمكننا تحقيق ذلك؟

717
00:58:31,220 --> 00:58:36,810
يمكننا تحقيق ذلك إذا نحن نضمن أن أي عنصر معين في مجموعة

718
00:58:36,810 --> 00:58:39,600
أقل من حجم معين.

719
00:58:42,070 --> 00:58:44,500
لذلك دعونا نقول فقط أن حجم هو 200،

720
00:58:44,500 --> 00:58:48,130
أي عنصر في صفيف أقل من حجم 200.

721
00:58:48,130 --> 00:58:51,080
وهذا هو في الواقع واقعية جدا.

722
00:58:51,080 --> 00:58:58,660
يمكنك بسهولة جدا من مجموعة أن تعرف كل شيء فيه

723
00:58:58,660 --> 00:59:00,570
سيكون أقل من عدد بعض.

724
00:59:00,570 --> 00:59:07,400
إذا كان لديك مثل ناقلات ضخمة للغاية بعض أو شيء

725
00:59:07,400 --> 00:59:11,810
لكنك تعلم كل شيء سيكون بين 0 و 5،

726
00:59:11,810 --> 00:59:14,790
ثم انها سوف تكون أسرع بكثير للقيام بذلك.

727
00:59:14,790 --> 00:59:17,930
وربط على أي من العناصر هو 5،

728
00:59:17,930 --> 00:59:21,980
لذلك هذا محدد، وهذا هو مقدار الذاكرة وأنت تسير إلى استخدام.

729
00:59:21,980 --> 00:59:26,300
وبالتالي فإن المربوطة 200.

730
00:59:26,300 --> 00:59:32,960
من الناحية النظرية هناك دائما عدد صحيح محدد منذ لا يمكن إلا أن تصل إلى 4 مليار دولار،

731
00:59:32,960 --> 00:59:40,600
ولكن هذا غير واقعي ومنذ ذلك الحين ونحن سنكون باستخدام الفضاء

732
00:59:40,600 --> 00:59:44,400
بناء على أمر من 4 مليار دولار. ولهذا غير واقعي.

733
00:59:44,400 --> 00:59:47,060
ولكن هنا سوف نقوله منضم لدينا هو 200.

734
00:59:47,060 --> 00:59:59,570
خدعة لفعل ذلك في O n هو من جعل آخر ونحن مجموعة تسمى تهمة حجم محدد.

735
00:59:59,570 --> 01:00:10,470
في الواقع كذلك، وهذا هو اختصار ل- أنا في الواقع لا أعرف إذا كان ضجيج يفعل ذلك.

736
01:00:11,150 --> 01:00:15,330
ولكن في دول مجلس التعاون الخليجي على أقل تقدير - أنا على افتراض أنه لا ضجيج أيضا -

737
01:00:15,330 --> 01:00:18,180
وهذا مجرد تهيئة مجموعة بالكامل لتكون 0S.

738
01:00:18,180 --> 01:00:25,320
حتى لو كنت لا تريد أن تفعل ذلك، ثم ما يمكن القيام به بشكل منفصل عن (كثافة العمليات ط = 0؛

739
01:00:25,320 --> 01:00:31,500
ط <BOUND، وأنا + +) وتعول [أنا] = 0؛

740
01:00:31,500 --> 01:00:35,260
حتى الآن كل شيء يتم تهيئة إلى 0.

741
01:00:35,260 --> 01:00:39,570
I تكرار عبر مجموعة بلدي،

742
01:00:39,570 --> 01:00:51,920
وما أفعله هو أنني أعول عدد كل - دعنا نذهب الى هنا.

743
01:00:51,920 --> 01:00:55,480
لدينا 4، 15، 16، 50، 8، 23، 42، 108.

744
01:00:55,480 --> 01:01:00,010
ما أنا العد هو عدد تكرارات كل من هذه العناصر.

745
01:01:00,010 --> 01:01:03,470
دعونا نضيف فعلا أكثر زوجين في هنا مع بعض يكرر.

746
01:01:03,470 --> 01:01:11,070
وبالتالي فإن قيمة لدينا هنا، وقيمة ذلك ستكون مجموعة [ط].

747
01:01:11,070 --> 01:01:14,850
لذلك يمكن أن تكون فال 4 أو 8 أو أيا كان.

748
01:01:14,850 --> 01:01:18,870
والآن أنا أعول عدد من تلك القيمة رأيت،

749
01:01:18,870 --> 01:01:21,230
حتى التهم [فال] + +؛

750
01:01:21,230 --> 01:01:29,430
بعد ذلك، المهم في الأمر هو الذهاب الى تبدو شيء مثل 0001.

751
01:01:29,430 --> 01:01:42,190
دعونا نفعل التهم [فال] - ملزمة + 1.

752
01:01:42,190 --> 01:01:48,230
>> الآن هذا مجرد لحساب لحقيقة أننا بدأنا من 0.

753
01:01:48,230 --> 01:01:50,850
حتى إذا 200 هو سيكون لدينا عدد أكبر،

754
01:01:50,850 --> 01:01:54,720
0 حتي 200 ثم 201 الأشياء.

755
01:01:54,720 --> 01:02:01,540
حتى التهم، وأنها سوف تبدو وكأنها 00001 لأننا واحد 4.

756
01:02:01,540 --> 01:02:10,210
ثم سيكون لدينا 0001 حيث ستكون لدينا 1 في مؤشر 8 من العد.

757
01:02:10,210 --> 01:02:14,560
سيكون لدينا مؤشر 2 في 23 من العد.

758
01:02:14,560 --> 01:02:17,630
سيكون لدينا مؤشر 2 في 42 من العد.

759
01:02:17,630 --> 01:02:21,670
حتى نتمكن من استخدام العد.

760
01:02:34,270 --> 01:02:44,920
حتى num_of_item = التهم [أنا].

761
01:02:44,920 --> 01:02:52,540
وإذا كان الأمر كذلك num_of_item هو 2، وهذا يعني أننا نريد لادخال عدد 2 من أنا

762
01:02:52,540 --> 01:02:55,290
في مجموعتنا فرزها.

763
01:02:55,290 --> 01:03:02,000
لذلك نحن بحاجة لتتبع مدى نحن في الصفيف.

764
01:03:02,000 --> 01:03:05,470
= ذلك مؤشر 0.

765
01:03:05,470 --> 01:03:09,910
مجموعة - أنا أكتب فقط.

766
01:03:16,660 --> 01:03:18,020
التهم -

767
01:03:19,990 --> 01:03:28,580
مجموعة [مؤشر + +] = ط؛

768
01:03:28,580 --> 01:03:32,490
هو أن ما أريد؟ أعتقد أن هذا ما أريد.

769
01:03:35,100 --> 01:03:38,290
نعم، هذا يبدو جيدا. حسنا.

770
01:03:38,290 --> 01:03:43,050
حتى لا يفهم الجميع ما هو الغرض من مجموعة التهم بلدي؟

771
01:03:43,050 --> 01:03:48,140
فإنه يعول على عدد من الأحداث من كل من هذه الأرقام.

772
01:03:48,140 --> 01:03:51,780
ثم أنا بالتكرار عبر مجموعة التهم التي،

773
01:03:51,780 --> 01:03:57,190
وموقف إيث في مجموعة التهم

774
01:03:57,190 --> 01:04:01,930
هو عدد من أنا التي يجب أن تظهر في مجموعة بي فرزها.

775
01:04:01,930 --> 01:04:06,840
هذا هو السبب في التهم من 4 سوف يكون 1

776
01:04:06,840 --> 01:04:11,840
وتعول من 8 سيكون 1، التهم من 23 ستكون 2.

777
01:04:11,840 --> 01:04:16,900
ولهذا كم منهم أريد أن تضاف الى مجموعة بلدي فرزها.

778
01:04:16,900 --> 01:04:19,200
ثم أفعل ذلك تماما.

779
01:04:19,200 --> 01:04:28,960
أنا أنا هو إدخال num_of_item في مجموعة بي فرزها.

780
01:04:28,960 --> 01:04:31,670
>> الأسئلة؟

781
01:04:32,460 --> 01:04:43,100
وذلك مرة أخرى، وهذا هو الوقت الخطية بما أننا بالتكرار ما يزيد قليلا على هذا مرة واحدة،

782
01:04:43,100 --> 01:04:47,470
لكنه أيضا خطية في هذا العدد ما يحدث أن تكون،

783
01:04:47,470 --> 01:04:50,730
وذلك يعتمد بشكل كبير على ما منضم الخاصة بك.

784
01:04:50,730 --> 01:04:53,290
مع متجهة من 200، وهذا ليس سيئا.

785
01:04:53,290 --> 01:04:58,330
إذا منضم الخاص سيكون 10،000، ثم هذا هو أسوأ قليلا،

786
01:04:58,330 --> 01:05:01,360
ولكن إذا منضم الخاص بك هو الذهاب إلى 4 مليار دولار، وهذا غير واقعي تماما

787
01:05:01,360 --> 01:05:07,720
وهذه المجموعة ستكون لدينا لتكون من حجم 4 مليار وهو غير واقعي.

788
01:05:07,720 --> 01:05:10,860
ولهذا ذلك. الأسئلة؟

789
01:05:10,860 --> 01:05:13,270
[رد الطالب غير مسموع] >> حسنا.

790
01:05:13,270 --> 01:05:15,710
أدركت شيئا واحدا أخرى عندما كنا يمر بها.

791
01:05:17,980 --> 01:05:23,720
أعتقد أن المشكلة كانت في لوكاس، وربما كل واحد رأيناه.

792
01:05:23,720 --> 01:05:26,330
لقد نسيت تماما.

793
01:05:26,330 --> 01:05:31,040
الشيء الوحيد الذي كنت أريد أن أعلق عليه هو أنه عندما كنت تتعامل مع أشياء مثل مؤشرات،

794
01:05:31,040 --> 01:05:38,320
أنت لا ترى حقا هذا عندما كنت تكتب لحلقة،

795
01:05:38,320 --> 01:05:41,120
لكن من الناحية الفنية، كلما كنت تتعامل مع هذه المؤشرات،

796
01:05:41,120 --> 01:05:45,950
يجب عليك دائما جميلة كثيرا التعامل مع الأعداد الصحيحة غير الموقعة.

797
01:05:45,950 --> 01:05:53,850
والسبب في ذلك هو عندما كنت تتعامل مع الأعداد الصحيحة وقعت،

798
01:05:53,850 --> 01:05:56,090
إذا كان الأمر كذلك لديك 2 أعداد صحيحة وقعت إضافتها معا

799
01:05:56,090 --> 01:06:00,640
وأنهم في نهاية المطاف كبير جدا، ثم ينتهي بك الأمر مع رقم سالب.

800
01:06:00,640 --> 01:06:03,410
بحيث تجاوز عدد صحيح ما هو.

801
01:06:03,410 --> 01:06:10,500
>> إذا كنت تضيف 2 مليار و 1 مليار دولار، في نهاية المطاف مع I 1 مليار السلبية.

802
01:06:10,500 --> 01:06:15,480
هذه هي الطريقة الصحيحة تعمل على أجهزة الكمبيوتر.

803
01:06:15,480 --> 01:06:17,510
وبالتالي فإن المشكلة مع استخدام -

804
01:06:17,510 --> 01:06:23,500
هذا شيء طيب إلا إذا كان يحدث أن تكون منخفضة 2 مليار و يحدث حتى تكون 1 مليار

805
01:06:23,500 --> 01:06:27,120
ثم وهذا سيكون سلبيا 1 مليار و بعد ذلك نحن ذاهبون الى تقسيم هذا بنسبة 2

806
01:06:27,120 --> 01:06:29,730
وينتهي مع 500 مليون السلبية.

807
01:06:29,730 --> 01:06:33,760
لذلك هذا هو فقط مسألة إذا كنت يحدث ليكون البحث من خلال مجموعة

808
01:06:33,760 --> 01:06:38,070
المليارات من الأشياء.

809
01:06:38,070 --> 01:06:44,050
ولكن إذا حدث انخفاض + حتى تجاوز، ثم وهذا هو المشكلة.

810
01:06:44,050 --> 01:06:47,750
بأسرع ما جعلها غير الموقعة، ثم 2 بليون نسمة 1000000000 هو 3 مليار دولار.

811
01:06:47,750 --> 01:06:51,960
3000000000 مقسوما على 2 هو 1.5 مليار دولار.

812
01:06:51,960 --> 01:06:55,670
وذلك في أقرب وقت انهم غير موقعة، كل شيء على ما يرام.

813
01:06:55,670 --> 01:06:59,900
وحتى هذا أيضا مسألة عندما كنت أكتب رأيك عن الحلقات،

814
01:06:59,900 --> 01:07:03,940
وفعلا، فإنه من المحتمل أن تلقائيا.

815
01:07:09,130 --> 01:07:12,330
فإنه في الواقع مجرد الصراخ عليك.

816
01:07:12,330 --> 01:07:21,610
حتى إذا كان هذا الرقم هو أكبر من أن يكون صحيحا في مجرد أنه من المناسب ولكن في عدد صحيح غير الموقعة،

817
01:07:21,610 --> 01:07:24,970
سوف يصيح في لكم، لذلك هذا هو السبب في أنك لن تشغيل حقا في هذه القضية.

818
01:07:29,150 --> 01:07:34,820
يمكنك أن ترى أن مؤشر انها لن تكون سلبية،

819
01:07:34,820 --> 01:07:39,220
وحتى عندما كنت بالتكرار عبر صفيف،

820
01:07:39,220 --> 01:07:43,970
يمكنك دائما تقريبا يقول الباحث غير الموقعة الأول، ولكن لم يكن لديك حقا.

821
01:07:43,970 --> 01:07:47,110
الامور تسير على العمل الى حد كبير فقط كذلك.

822
01:07:48,740 --> 01:07:50,090
حسنا. [همس] ما هو الوقت؟

823
01:07:50,090 --> 01:07:54,020
آخر شيء كنت أرغب في إظهار - وسأفعل ذلك فقط سريعة حقا.

824
01:07:54,020 --> 01:08:03,190
تعرف كيف قمنا # تعريف حتى نتمكن من تحديد # MAX إلى 5 أو شيء؟

825
01:08:03,190 --> 01:08:05,940
دعونا لا تفعل MAX. # تعريف ملزمة إلى 200. هذا ما فعلناه من قبل.

826
01:08:05,940 --> 01:08:10,380
أن يعرف ثابت، الذي هو مجرد الذهاب ليتم نسخها ولصقها

827
01:08:10,380 --> 01:08:13,010
أينما كنا يحدث أن يكتب ملزمة.

828
01:08:13,010 --> 01:08:18,189
>> حتى نتمكن من القيام به في الواقع أكثر مع تعريف #.

829
01:08:18,189 --> 01:08:21,170
يمكننا تعريف # الوظائف.

830
01:08:21,170 --> 01:08:23,410
انهم حقا لا وظائف، ولكننا سوف ندعو لهم وظائف.

831
01:08:23,410 --> 01:08:36,000
مثال سيكون شيئا مثل MAX (س، ص) هو الذي يعرف بأنه (X <Y Y:؟ خ). حسنا.

832
01:08:36,000 --> 01:08:40,660
لذلك يجب أن تعتاد على بناء جملة المشغل الثلاثي،

833
01:08:40,660 --> 01:08:49,029
ولكن هو أقل من X Y؟ العودة Y، X العودة آخر.

834
01:08:49,029 --> 01:08:54,390
حتى تستطيع أن ترى يمكنك ان تجعل هذه الوظيفة منفصلة،

835
01:08:54,390 --> 01:09:01,399
ويمكن أن تكون وظيفة مثل BOOL MAX يأخذ 2 الحجج، والعودة هذه.

836
01:09:01,399 --> 01:09:08,340
هذه هي واحدة من أكثرها شيوعا أرى به مثل هذا. نحن ندعو لهم وحدات الماكرو.

837
01:09:08,340 --> 01:09:11,790
هذا هو الماكرو.

838
01:09:11,790 --> 01:09:15,859
هذا هو مجرد بناء الجملة من أجل ذلك.

839
01:09:15,859 --> 01:09:18,740
يمكنك كتابة ماكرو لتفعل ما تريد.

840
01:09:18,740 --> 01:09:22,649
ترى في كثير من الأحيان وحدات الماكرو من أجل التصحيح printfs والاشياء.

841
01:09:22,649 --> 01:09:29,410
ذلك نوع لل printf، وهناك ثوابت خاصة في مثل C تؤكد خط تسطير،

842
01:09:29,410 --> 01:09:31,710
2 يؤكد خط تسطير،

843
01:09:31,710 --> 01:09:37,550
وهناك أيضا أعتقد 2 يؤكد ظائفه. التي قد تكون عليه. شيء من هذا القبيل.

844
01:09:37,550 --> 01:09:40,880
سيتم استبدال تلك الأشياء مع اسم الدالة

845
01:09:40,880 --> 01:09:42,930
أو عدد السطر الذي كنت على.

846
01:09:42,930 --> 01:09:48,630
في كثير من الأحيان، كنت أكتب هنا أن التصحيح printfs أسفل ثم أتمكن من الكتابة فقط

847
01:09:48,630 --> 01:09:54,260
تصحيح وأنها سوف طباعة رقم السطر وظيفة أنني يحدث ليكون في

848
01:09:54,260 --> 01:09:57,020
أنه واجه هذا البيان DEBUG.

849
01:09:57,020 --> 01:09:59,550
ويمكنك أيضا طباعة أمور أخرى.

850
01:09:59,550 --> 01:10:05,990
ذلك شيء واحد يجب أن احترس من هو إذا كنت يحدث لتعريف # DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
شيء من هذا القبيل كما 2 * 2 * Y و X.

852
01:10:11,380 --> 01:10:14,310
ذلك لسبب كان، كنت يحدث لفعل ذلك كثيرا.

853
01:10:14,310 --> 01:10:16,650
حتى جعله ماكرو.

854
01:10:16,650 --> 01:10:18,680
يتم تقسيم هذا الواقع.

855
01:10:18,680 --> 01:10:23,050
ويمكنني أن أسمي ذلك عن طريق القيام شيء من هذا القبيل DOUBLE_MAX (3، 6).

856
01:10:23,050 --> 01:10:27,530
ذلك ما ينبغي أن تعاد؟

857
01:10:28,840 --> 01:10:30,580
[طالب] 12.

858
01:10:30,580 --> 01:10:34,800
نعم، ينبغي أن تعاد 12، وعاد 12.

859
01:10:34,800 --> 01:10:43,350
يحصل استبدال 3 لX، ويحصل على استبدال 6 لY، ونعود 2 * 6، الذي هو 12.

860
01:10:43,350 --> 01:10:47,710
الآن ماذا عن هذا؟ ماذا يجب أن تعاد؟

861
01:10:47,710 --> 01:10:50,330
[طالب] 14. ومن الناحية المثالية >>، 14.

862
01:10:50,330 --> 01:10:55,290
المسألة هي ان تعرف كيف تجزئة العمل، وتذكر انها نسخة حرفية ولصق

863
01:10:55,290 --> 01:11:00,160
من كل شيء الى حد كبير، لذلك هذا ما سوف يتم تفسيره على أنه

864
01:11:00,160 --> 01:11:11,270
هو 3 أقل من 1 زائد 6، 2 مرات (1) مع 6، 2 3 مرات.

865
01:11:11,270 --> 01:11:19,780
>> لذلك لهذا السبب كنت دائما تقريبا التفاف كل شيء بين قوسين.

866
01:11:22,180 --> 01:11:25,050
أي متغير كنت دائما تقريبا بين قوسين التفاف.

867
01:11:25,050 --> 01:11:29,570
هناك حالات حيث لم يكن لديك ل، مثل وأنا أعلم أنني لست بحاجة إلى أن تفعل ذلك هنا

868
01:11:29,570 --> 01:11:32,110
لأن أقل مما هو الى حد كبير دائما مجرد الذهاب للعمل،

869
01:11:32,110 --> 01:11:34,330
على الرغم من أن قد لا يكون صحيحا حتى.

870
01:11:34,330 --> 01:11:41,870
إذا كان هناك شيء مثير للسخرية مثل DOUBLE_MAX (1 == 2)،

871
01:11:41,870 --> 01:11:49,760
ثم أن يحدث للحصول على استبدال مع 3 أقل من 1 يساوي يساوي 2،

872
01:11:49,760 --> 01:11:53,460
وحتى ذلك الحين انها سوف تفعل 3 أقل من 1، لا أن 2 على قدم المساواة،

873
01:11:53,460 --> 01:11:55,620
وهو ما لا نريده.

874
01:11:55,620 --> 01:12:00,730
وذلك من أجل منع أي مشغل مشاكل الأسبقية،

875
01:12:00,730 --> 01:12:02,870
التفاف دائما بين قوسين.

876
01:12:03,290 --> 01:12:07,700
حسنا. وهذا كل شيء، 5:30.

877
01:12:08,140 --> 01:12:12,470
إذا كان لديك أي أسئلة على pset، واسمحوا لنا أن نعرف.

878
01:12:12,470 --> 01:12:18,010
ينبغي أن يكون متعة، والطبعة القراصنة أيضا أكثر واقعية

879
01:12:18,010 --> 01:12:22,980
من طبعة القراصنة من العام الماضي، لذلك نحن نأمل أن الكثير من محاولة ذلك.

880
01:12:22,980 --> 01:12:26,460
وكان العام الماضي الساحق للغاية.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]