1
00:00:00,000 --> 00:00:00,990

2
00:00:00,990 --> 00:00:02,970
>> [عزف الموسيقى]

3
00:00:02,970 --> 00:00:10,400

4
00:00:10,400 --> 00:00:12,550
>> DAVID J. مالان: هذا هو CS50.

5
00:00:12,550 --> 00:00:14,612
وهذا هو بداية ثلاثة أسابيع.

6
00:00:14,612 --> 00:00:16,820
لذلك نحن قد حصلت على الكثير من مثيرة
أشياء لتغطية اليوم.

7
00:00:16,820 --> 00:00:20,160
وهناك الكثير من الفرص لل
المتطوعين على خشبة المسرح.

8
00:00:20,160 --> 00:00:22,780
وفي نهاية المطاف، واليوم هو
لا حول قانون على الإطلاق.

9
00:00:22,780 --> 00:00:24,820
لكنه حول الأفكار، و
ولكن عن الخوارزميات،

10
00:00:24,820 --> 00:00:28,420
وبذلك الواقع مرة أخرى بعض
الدروس المستفادة من الأسبوع الصفر،

11
00:00:28,420 --> 00:00:31,910
حيث تذكر، ونحن
قدم هذا المسخ.

12
00:00:31,910 --> 00:00:33,880
والإلهام الاقتراض
من ذلك، لبدء

13
00:00:33,880 --> 00:00:36,879
لحل أكثر تطورا من أي وقت مضى
المشاكل حسابيا.

14
00:00:36,879 --> 00:00:38,420
ولكن أولا، وزوجين من الإعلانات.

15
00:00:38,420 --> 00:00:42,020
حتى واحد، إذا كنت ترغب في الانضمام
الموظفين CS50 وزملاء الدراسة في الغداء

16
00:00:42,020 --> 00:00:44,670
هذا الجمعة، سواء هنا أو في
كامبريدج، ونيو هافن،

17
00:00:44,670 --> 00:00:48,060
يرجى زيارة بالطبع ل
على شبكة الإنترنت، حيث URL يمكن العثور عليها.

18
00:00:48,060 --> 00:00:50,390
محاضرة يوم الأربعاء سوف
لن يكون هنا في ساندرز.

19
00:00:50,390 --> 00:00:53,610
وسوف تكون على الانترنت فقط، لذلك
الاستماع في موقع CS50، و

20
00:00:53,610 --> 00:00:55,850
سواء هنا في كامبريدج
أو نيو هافن كذلك.

21
00:00:55,850 --> 00:00:58,110
>> والمشكلة قم بتعيين اثنين
هو بالفعل في يديك.

22
00:00:58,110 --> 00:01:03,067
إذا لم تكن قد ارتمى في ذلك، اسمحوا لي
لتقديم اقتراح شديد اللهجة

23
00:01:03,067 --> 00:01:05,150
ذلك، خصوصا الآن، كما
المشكلة تحدد مسبقا،

24
00:01:05,150 --> 00:01:08,669
هل حقا تريد أن تبدأ الآن، إن لم يكن
اشتغل قليلا في عطلة نهاية الأسبوع أو قبل

25
00:01:08,669 --> 00:01:10,710
عندما يذهبون لأول مرة على
الجمعة، لأنك سوف

26
00:01:10,710 --> 00:01:14,380
تجد أنهم ليسوا بالضرورة
الحصول على أطول أو أكثر تحديا في

27
00:01:14,380 --> 00:01:14,950
حد ذاتها.

28
00:01:14,950 --> 00:01:17,575
أعتقد أنك ستجد أنه في
عموما، فإنها تميل إلى اتخاذ تقريبا

29
00:01:17,575 --> 00:01:18,892
حول نفس المقدار من الوقت.

30
00:01:18,892 --> 00:01:20,850
ولكن ذلك يعتمد بالتأكيد
على الطالب، وذلك

31
00:01:20,850 --> 00:01:22,880
يعتمد على عقلية
والتي يمكنك التعامل معها.

32
00:01:22,880 --> 00:01:24,910
ولكن دائما، وأنت تسير
لتشغيل حتى ضد بعض الجدار،

33
00:01:24,910 --> 00:01:26,350
وأنت تسير لضرب
بعض الأخطاء، وكنت للتو

34
00:01:26,350 --> 00:01:27,950
لن تكون قادرة على
الحصول على أكثر من ذلك في بعض نقطة.

35
00:01:27,950 --> 00:01:31,380
وانها ذات قيمة كبيرة لتكون قادرة
على بعد خطوة، ويعود في اليوم التالي،

36
00:01:31,380 --> 00:01:35,286
انتقل إلى ساعات العمل، وظيفة على CS50 ناقش
أو ما شابه ذلك، للحصول على الافراج الواقع.

37
00:01:35,286 --> 00:01:36,160
حتى أن تبقي في الاعتبار.

38
00:01:36,160 --> 00:01:40,830
بدءا أقرب وقت ممكن
هو أفضل شيء يمكنك القيام به.

39
00:01:40,830 --> 00:01:44,160
حتى هنا حيث بدأنا
الطبقة، في أكثر من أسبوع الصفر.

40
00:01:44,160 --> 00:01:47,441
ويمكن أن نحصل على المتطوعين
هنا لمساعدتي في العثور ميكروفونات؟

41
00:01:47,441 --> 00:01:47,940
حسنا.

42
00:01:47,940 --> 00:01:48,900
الوقوف بالفعل.

43
00:01:48,900 --> 00:01:50,080
تأتي على ما يصل.

44
00:01:50,080 --> 00:01:53,707
اعتقد ان هذا كيف انها الذهاب الى العمل.

45
00:01:53,707 --> 00:01:54,415
ما اسمك؟

46
00:01:54,415 --> 00:01:55,570
ALAN إسترادا: آلان استرادا.

47
00:01:55,570 --> 00:01:56,778
DAVID J. مالان: آلان استرادا.

48
00:01:56,778 --> 00:01:57,910
تأتي على ما يصل.

49
00:01:57,910 --> 00:01:58,619
تشرفت بمقابلتك.

50
00:01:58,619 --> 00:01:59,910
ALAN استرادا: لطيف لمقابلتك.

51
00:01:59,910 --> 00:02:02,772
DAVID J. مالان: وكنت هنا
معنا في الأسبوع الصفر، بطبيعة الحال.

52
00:02:02,772 --> 00:02:03,028
ALAN إسترادا: كنت.

53
00:02:03,028 --> 00:02:03,160
انا كنت.

54
00:02:03,160 --> 00:02:05,868
>> DAVID J. مالان: إذن هل يمكن أن تذهب
إلى الأمام وإيجاد بالنسبة لنا مايك سميث،

55
00:02:05,868 --> 00:02:08,639
بأسرع ما يمكن؟

56
00:02:08,639 --> 00:02:10,639
بأسرع ما يمكن.

57
00:02:10,639 --> 00:02:13,756
تمزيق حرفيا المشكلة
في النصف كما كنت في حاجة إليها.

58
00:02:13,756 --> 00:02:15,130
>> ALAN إسترادا: أم.

59
00:02:15,130 --> 00:02:17,380
DAVID J. مالان: حرفيا
تمزيق مشكلة في النصف.

60
00:02:17,380 --> 00:02:20,210

61
00:02:20,210 --> 00:02:22,083
>> ALAN إسترادا: أوه.

62
00:02:22,083 --> 00:02:22,583
مم.

63
00:02:22,583 --> 00:02:23,300
جيد جدا.

64
00:02:23,300 --> 00:02:23,700
>> DAVID J. مالان: OK.

65
00:02:23,700 --> 00:02:24,200
جيد.

66
00:02:24,200 --> 00:02:24,701
شكرا.

67
00:02:24,701 --> 00:02:25,700
ALAN إسترادا: جيد جدا.

68
00:02:25,700 --> 00:02:26,210
حسنا.

69
00:02:26,210 --> 00:02:27,610
>> DAVID J. مالان: وهكذا الآن،
كنت قد تتفكك عليه

70
00:02:27,610 --> 00:02:29,320
إلى نصف حجم المشكلة.

71
00:02:29,320 --> 00:02:31,267
الآن، نحن لتصل إلى ربع النهائي.

72
00:02:31,267 --> 00:02:33,475
أنت تدفع الانتباه إلى
الجانب الذي نحن حفظ؟

73
00:02:33,475 --> 00:02:34,405
>> [يضحك]

74
00:02:34,405 --> 00:02:35,970
>> ALAN إسترادا: نعم، أنا think--

75
00:02:35,970 --> 00:02:37,594
>> DAVID J. مالان: ما هو أكثر قسم نحن في؟

76
00:02:37,594 --> 00:02:39,150
ALAN إسترادا: الخمارات، لذلك.

77
00:02:39,150 --> 00:02:39,941
>> DAVID J. مالان: OK.

78
00:02:39,941 --> 00:02:42,810
لكن مايك سميث يجري
ليكون بعد الخمارات.

79
00:02:42,810 --> 00:02:44,130
هكذا--

80
00:02:44,130 --> 00:02:48,180
>> [يضحك]

81
00:02:48,180 --> 00:02:48,742
>> حسنا.

82
00:02:48,742 --> 00:02:50,200
ALAN إسترادا: أين نحن تبحث؟

83
00:02:50,200 --> 00:02:52,049
DAVID J. مالان: مايك سميث.

84
00:02:52,049 --> 00:02:53,090
ALAN إسترادا: مايك سميث.

85
00:02:53,090 --> 00:02:54,760
DAVID J. مالان: الآن، نحن في العمليات الجراحية.

86
00:02:54,760 --> 00:02:57,840
الآن، والأطباء.

87
00:02:57,840 --> 00:02:58,340
Now--

88
00:02:58,340 --> 00:02:59,856
>> ALAN إسترادا: Let's- دعنا نذهب مع ريال مدريد.

89
00:02:59,856 --> 00:03:00,370
ريال مدريد.

90
00:03:00,370 --> 00:03:00,970
>> DAVID J. مالان: ريال.

91
00:03:00,970 --> 00:03:01,470
حسنا.

92
00:03:01,470 --> 00:03:03,700
اذا كنت بحاجة الى ريال مدريد.

93
00:03:03,700 --> 00:03:05,250
الآن، الطريق الذي هو مايك سميث؟

94
00:03:05,250 --> 00:03:06,250
>> ALAN إسترادا: بهذه الطريقة.

95
00:03:06,250 --> 00:03:07,333
>> DAVID J. مالان: ما هي الطريقة؟

96
00:03:07,333 --> 00:03:08,240
ALAN إسترادا: انتظر.

97
00:03:08,240 --> 00:03:08,790
M is-- أليس كذلك؟

98
00:03:08,790 --> 00:03:09,110
بدأنا with--

99
00:03:09,110 --> 00:03:10,090
>> DAVID J. مالان: نعم.

100
00:03:10,090 --> 00:03:10,650
كنت تركوا.

101
00:03:10,650 --> 00:03:11,430
لديك حق.

102
00:03:11,430 --> 00:03:11,710
>> ALAN إسترادا: نعم.

103
00:03:11,710 --> 00:03:13,126
>> DAVID J. مالان: في ذلك مايك هنا.

104
00:03:13,126 --> 00:03:13,990
ALAN إسترادا: ماذا؟

105
00:03:13,990 --> 00:03:14,665
>> [يضحك]

106
00:03:14,665 --> 00:03:17,365

107
00:03:17,365 --> 00:03:18,330
>> سيئة سبيل المثال، والرجال.

108
00:03:18,330 --> 00:03:18,830
آسف.

109
00:03:18,830 --> 00:03:21,610
DAVID J. مالان: هذا سيعلم
أنت للقفز من مقعده الخاص بك.

110
00:03:21,610 --> 00:03:22,318
>> ALAN إسترادا: أوه.

111
00:03:22,318 --> 00:03:22,890
اه.

112
00:03:22,890 --> 00:03:23,390
فهمتك.

113
00:03:23,390 --> 00:03:24,670
فهمتك.

114
00:03:24,670 --> 00:03:25,170
اه.

115
00:03:25,170 --> 00:03:25,669
اه.

116
00:03:25,669 --> 00:03:26,812
هذا is-- موافق، وحصلت لك.

117
00:03:26,812 --> 00:03:27,520
سميث هنا؟

118
00:03:27,520 --> 00:03:28,894
>> DAVID J. مالان: سميث، شكرا لك.

119
00:03:28,894 --> 00:03:30,535
ولذا فإنني سوف تبقى تبحث حتى سميث؟

120
00:03:30,535 --> 00:03:30,790
>> ALAN إسترادا: أوه، نعم.

121
00:03:30,790 --> 00:03:31,340
لا لا لا.

122
00:03:31,340 --> 00:03:31,600
اوه لا.

123
00:03:31,600 --> 00:03:31,940
هذا لي.

124
00:03:31,940 --> 00:03:32,580
>> DAVID J. مالان: أوه، كنت حصلت سميث.

125
00:03:32,580 --> 00:03:33,415
حسنا.

126
00:03:33,415 --> 00:03:34,040
>> ALAN إسترادا: نعم، أنا
حصل سميث هنا.

127
00:03:34,040 --> 00:03:34,700
آسف شباب.

128
00:03:34,700 --> 00:03:35,860
اعتقدت Michael-- نحن
كانوا يبحثون عن مايكل.

129
00:03:35,860 --> 00:03:36,550
آسف.

130
00:03:36,550 --> 00:03:37,550
>> DAVID J. مالان: لا بأس.

131
00:03:37,550 --> 00:03:39,950
كل الحق، والآن نحن
في Paccini وأولاده.

132
00:03:39,950 --> 00:03:41,242
>> ALAN إسترادا: Paccini والأبناء.

133
00:03:41,242 --> 00:03:43,158
DAVID J. مالان: أنت فقط
وأنا في في هذا الشأن.

134
00:03:43,158 --> 00:03:44,050
حسنا.

135
00:03:44,050 --> 00:03:45,130
تجدنا مايك سميث.

136
00:03:45,130 --> 00:03:45,830
سميث.

137
00:03:45,830 --> 00:03:46,310
>> ALAN إسترادا: سميث.

138
00:03:46,310 --> 00:03:46,750
>> DAVID J. مالان: سميث.

139
00:03:46,750 --> 00:03:47,728
نحن في R للقمامة.

140
00:03:47,728 --> 00:03:48,644
ALAN إسترادا: القمامة.

141
00:03:48,644 --> 00:03:50,096
اه.

142
00:03:50,096 --> 00:03:52,480
هذا يحدث لبعض الوقت.

143
00:03:52,480 --> 00:03:54,340
>> [يضحك]

144
00:03:54,340 --> 00:03:55,804

145
00:03:55,804 --> 00:03:56,720
DAVID J. مالان: أحذية.

146
00:03:56,720 --> 00:03:58,080
نحن في الأحذية.

147
00:03:58,080 --> 00:04:00,210
>> ALAN إسترادا: نحن الآن gonna--

148
00:04:00,210 --> 00:04:01,105
>> DAVID J. مالان: نيس.

149
00:04:01,105 --> 00:04:01,980
ALAN إسترادا: Which--

150
00:04:01,980 --> 00:04:03,620
[يضحك]

151
00:04:03,620 --> 00:04:05,440
أوه، هذا شيء عظيم.

152
00:04:05,440 --> 00:04:06,910
[يضحك]

153
00:04:06,910 --> 00:04:08,380

154
00:04:08,380 --> 00:04:09,390
>> DAVID J. مالان: لا بأس.

155
00:04:09,390 --> 00:04:11,365
>> ALAN إسترادا: أوه، هذا أمر جيد.

156
00:04:11,365 --> 00:04:14,425
أنا لا أعتقد أنني ذاهب ل
لدينا رفاقا PSAT بعد ذلك.

157
00:04:14,425 --> 00:04:15,300
DAVID J. مالان: جيد.

158
00:04:15,300 --> 00:04:16,078
الرياضية.

159
00:04:16,078 --> 00:04:17,036
ALAN إسترادا: الرياضية.

160
00:04:17,036 --> 00:04:18,668
أم، L، M، N، O، P.

161
00:04:18,668 --> 00:04:19,459
DAVID J. مالان: OK.

162
00:04:19,459 --> 00:04:21,600
لذلك دعونا المسيل للدموع في هذا الشوط.

163
00:04:21,600 --> 00:04:22,270
كل شيء على مايرام.

164
00:04:22,270 --> 00:04:25,606
هذا ينتهي سيئة على أي حال، لأن مايك
ويل سميث لن يكون في الصفحات الصفراء.

165
00:04:25,606 --> 00:04:26,430
>> ALAN إسترادا: فصيل عبد الواحد.

166
00:04:26,430 --> 00:04:27,140
>> DAVID J. مالان: لا، لا بأس.

167
00:04:27,140 --> 00:04:28,930
ولكن دعونا نتظاهر مثل
وقال انه على هذه الصفحة.

168
00:04:28,930 --> 00:04:33,260
وحتى الآن، وكنت قد تتفكك مشكلة أسفل
لصفحة واحدة، ووجدنا مايك سميث.

169
00:04:33,260 --> 00:04:35,180
>> [هتاف]

170
00:04:35,180 --> 00:04:35,757

171
00:04:35,757 --> 00:04:36,340
حسنا شكرا لك.

172
00:04:36,340 --> 00:04:40,700

173
00:04:40,700 --> 00:04:41,200
حسنا.

174
00:04:41,200 --> 00:04:43,646
كان ذلك رائعا.

175
00:04:43,646 --> 00:04:45,954
ولكنه كان لا يزال أسرع
من البحث الخطي،

176
00:04:45,954 --> 00:04:47,870
حيث نبدأ في
بداية الكتاب،

177
00:04:47,870 --> 00:04:51,210
ونحن نمضي في طريقنا من اليسار إلى اليمين،
في نهاية المطاف يبحث عن مايك سميث.

178
00:04:51,210 --> 00:04:53,540
وهكذا، إذا كان الكتاب الهاتف
كان ربما 1000 صفحات،

179
00:04:53,540 --> 00:04:56,300
ربما كان قد اتخذ
لنا 10 أو نحو ذلك الدموع الصفحة.

180
00:04:56,300 --> 00:04:59,380
>> ولكنك قد الاستدانة
تطرق افتراض

181
00:04:59,380 --> 00:05:03,602
خلال كل ذلك، وهو ما يعني
ان الكتاب الهاتف في وقت مبكر كان ماذا؟

182
00:05:03,602 --> 00:05:04,310
الحضور: الترتيب.

183
00:05:04,310 --> 00:05:05,000
DAVID J. مالان: هو مرتبة و.

184
00:05:05,000 --> 00:05:05,160
الصحيح؟

185
00:05:05,160 --> 00:05:07,909
لقد فرزها حسب الترتيب الأبجدي، لذلك
أن جميع تلك الأسماء وأرقام

186
00:05:07,909 --> 00:05:11,230
يتم فرز من A إلى
Z، وو أبجديا بينهما.

187
00:05:11,230 --> 00:05:13,100
ولكن اليوم، ونحن نسأل الآن
السؤال، حسنا،

188
00:05:13,100 --> 00:05:16,170
كيف فعلت فيريزون أو الهاتف
شركة الحصول عليه في تلك الحالة؟

189
00:05:16,170 --> 00:05:19,560
>> لأنه شيء واحد للاستفادة
هذا الافتراض، وبالتالي،

190
00:05:19,560 --> 00:05:22,570
حل مشكلة مع
خوارزمية أكثر كفاءة.

191
00:05:22,570 --> 00:05:24,900
لكننا أبدا حقا
طلب في الأسبوع الصفر، حسنا،

192
00:05:24,900 --> 00:05:27,790
كم تكبد هي تكلفة
فيريزون أو شخص آخر

193
00:05:27,790 --> 00:05:29,620
للحصول على هذا الكتاب الهاتف من أجل فرزها؟

194
00:05:29,620 --> 00:05:29,780
>> الصحيح؟

195
00:05:29,780 --> 00:05:31,529
لا يهم إذا
يبحث حتى مايك سميث

196
00:05:31,529 --> 00:05:35,190
هو بسرعة فائقة، إذا كان يأخذك
العام لفرز الصفحات في البداية.

197
00:05:35,190 --> 00:05:35,690
الصحيح؟

198
00:05:35,690 --> 00:05:38,620
بالاضافة الى انك قد نخل فقط
من خلال دليل الهاتف العشوائية،

199
00:05:38,620 --> 00:05:40,690
إذا أريد لها أن تكون فائقة
تكلفة لترتيب هذا الامر.

200
00:05:40,690 --> 00:05:42,350
إذا كان الأمر كذلك فإننا يمكن أن يكون متطوع آخر.

201
00:05:42,350 --> 00:05:46,350
دعونا نلقي نظرة هنا في
كيف يمكننا might-- هيا up-- كيف

202
00:05:46,350 --> 00:05:48,100
قد نذهب حول فرز هذه.

203
00:05:48,100 --> 00:05:51,990
>> وإذا استطاع الأردن الواقع
الانضمام إلينا هنا على خشبة المسرح.

204
00:05:51,990 --> 00:05:55,100
هيا حتى لمجرد لحظة.

205
00:05:55,100 --> 00:05:56,359
ما اسمك؟

206
00:05:56,359 --> 00:05:57,150
كارولين: كارولين.

207
00:05:57,150 --> 00:05:58,691
DAVID J. مالان: كارولين، وتأتي على ما يصل.

208
00:05:58,691 --> 00:06:02,070
وعليك أن تكون انضم
لي من قبل والاردن هنا.

209
00:06:02,070 --> 00:06:03,800
كارولين، وشكرا لكم.

210
00:06:03,800 --> 00:06:04,300
حسنا.

211
00:06:04,300 --> 00:06:08,330
ذلك ما لدينا هنا ل
كارولين هو 26 كتابا الزرقاء

212
00:06:08,330 --> 00:06:10,747
يستخدم لإدارة FAS
بعض الامتحانات النهائية.

213
00:06:10,747 --> 00:06:13,330
هذه هي الحصول من الصعب العثور على،
ولكن ما قمنا به مسبقا

214
00:06:13,330 --> 00:06:15,800
هو أننا قد وضعت اسم شخص ما
على واجهة كل من هذه،

215
00:06:15,800 --> 00:06:18,133
ولكن لدينا أبقاها بسيطة من قبل
ثم اخماد الأسماء الكاملة.

216
00:06:18,133 --> 00:06:22,720
لذلك نحن من شأنه أن يضع الشخص مع اسم
L، D، J، B، على طول الطريق من A إلى Z،

217
00:06:22,720 --> 00:06:24,090
ولكنهم في ترتيب عشوائي.

218
00:06:24,090 --> 00:06:26,890
وحتى لو تفضلتم، والحديث الخاص بك
الطريق من خلال المشكلة كما كنت

219
00:06:26,890 --> 00:06:31,620
تفعل ذلك، يمكنك ان تمضي قدما و
فرز هذه بالنسبة لنا، من الألف إلى الياء

220
00:06:31,620 --> 00:06:34,070
>> الحضور: حسنا، L هو مثل، والوسط.

221
00:06:34,070 --> 00:06:35,050
C هو بداية.

222
00:06:35,050 --> 00:06:42,410
B. J قبل L. B، Q.

223
00:06:42,410 --> 00:06:45,140
>> DAVID J. مالان: عقد أن
فكرت لثانية واحدة.

224
00:06:45,140 --> 00:06:48,910
لأن خلاف ذلك، وهذا هو فقط
مثيرة للاهتمام بالنسبة لك، لي، والأردن.

225
00:06:48,910 --> 00:06:49,724
هناك نذهب.

226
00:06:49,724 --> 00:06:50,640
الحضور: (غير مسموع).

227
00:06:50,640 --> 00:06:57,299
R.

228
00:06:57,299 --> 00:06:58,090
DAVID J. مالان: OK.

229
00:06:58,090 --> 00:06:59,310
ماذا تفعل؟

230
00:06:59,310 --> 00:07:01,730
>> كارولين: M يأتي بعد O.

231
00:07:01,730 --> 00:07:02,564
>> DAVID J. مالان: OK.

232
00:07:02,564 --> 00:07:03,064
>> كارولين: O.

233
00:07:03,064 --> 00:07:04,120
DAVID J. مالان: O، جيد.

234
00:07:04,120 --> 00:07:04,970
>> كارولين: E.

235
00:07:04,970 --> 00:07:06,730
>> DAVID J. مالان: E، F. نعم.

236
00:07:06,730 --> 00:07:07,620
>> كارولين: T، U، V.

237
00:07:07,620 --> 00:07:10,689
>> DAVID J. مالان: V، T، U، V. لذلك
يبدو أنك كنت making-- الاستمرار.

238
00:07:10,689 --> 00:07:12,730
يبدو أنك نحرز
كومة كبيرة هنا،

239
00:07:12,730 --> 00:07:13,910
ونوع من كومة كبيرة هناك.

240
00:07:13,910 --> 00:07:16,230
حتى النصف الأول من الأبجدية،
النصف الثاني من الأبجدية.

241
00:07:16,230 --> 00:07:16,460
حسنا.

242
00:07:16,460 --> 00:07:16,960
جيد.

243
00:07:16,960 --> 00:07:19,680
نوع من تقسيم المشكلة إلى قسمين.

244
00:07:19,680 --> 00:07:21,771
M، N، X. نعم.

245
00:07:21,771 --> 00:07:22,270
كارولين: K.

246
00:07:22,270 --> 00:07:22,980
DAVID J. مالان: OK.

247
00:07:22,980 --> 00:07:25,070
K. لذا كنت نوع من اختيار
واحدا تلو الآخر،

248
00:07:25,070 --> 00:07:27,620
وضعه إما اليمين أو اليسار،
أو Z يجري على الأرض.

249
00:07:27,620 --> 00:07:28,012
حسنا.

250
00:07:28,012 --> 00:07:29,190
>> كارولين: Z يجري على الأرض.

251
00:07:29,190 --> 00:07:29,360
>> DAVID J. مالان: OK.

252
00:07:29,360 --> 00:07:30,920
Y يجري على الأرض.

253
00:07:30,920 --> 00:07:31,735
الآن يمكننا وضع X.

254
00:07:31,735 --> 00:07:32,409
>> كارولين: G.

255
00:07:32,409 --> 00:07:33,700
DAVID J. مالان: الذهاب اليسار G.

256
00:07:33,700 --> 00:07:36,017
S يجري الصحيح.

257
00:07:36,017 --> 00:07:37,642
كل الحق، A تسير على طول الطريق اليسار.

258
00:07:37,642 --> 00:07:38,790
>> كارولين: A، B، C، D.

259
00:07:38,790 --> 00:07:39,873
>> DAVID J. مالان: الآن، وحسن.

260
00:07:39,873 --> 00:07:43,260
لدينا A، B، C. W في الذهاب الى هناك.

261
00:07:43,260 --> 00:07:45,566
كل الحق، T.

262
00:07:45,566 --> 00:07:46,611
>> كارولين: H، I، J.

263
00:07:46,611 --> 00:07:47,860
DAVID J. مالان: H، I، J. جيد.

264
00:07:47,860 --> 00:07:49,160
كارولين: في الوسط، أنا gonna--

265
00:07:49,160 --> 00:07:50,000
DAVID J. مالان: OK.

266
00:07:50,000 --> 00:07:52,375
وحتى الآن، ونحن في طريقنا إلى نوع
من دمج هذه الأكوام المختلفة.

267
00:07:52,375 --> 00:08:00,730
لذلك من خلال C، ثم أرى D، و
E، F و، وG، H و، وI. نيس.

268
00:08:00,730 --> 00:08:05,540
J، K. وبعد ذلك، وهذا هو كومة
رأسا على عقب، ولكن هذا موافق.

269
00:08:05,540 --> 00:08:06,040
بالتأكيد.

270
00:08:06,040 --> 00:08:07,240
يمكننا خفض بعض الزوايا.

271
00:08:07,240 --> 00:08:07,950
حسنا.

272
00:08:07,950 --> 00:08:10,530
ومن ثم نحتاج W، X، Y، Z.

273
00:08:10,530 --> 00:08:11,250
>> كارولين: نعم.

274
00:08:11,250 --> 00:08:11,880
>> DAVID J. مالان: ممتاز.

275
00:08:11,880 --> 00:08:14,122
لذلك شكرا جزيلا لك
كارولين لفرز هذه.

276
00:08:14,122 --> 00:08:15,030
>> [هتاف]

277
00:08:15,030 --> 00:08:17,287
>> شكرا.

278
00:08:17,287 --> 00:08:18,120
شكرا جزيلا.

279
00:08:18,120 --> 00:08:22,910
حتى الآن دعونا نتأمل لحظة
كيف ذهب كارولين عن فعل ذلك،

280
00:08:22,910 --> 00:08:26,040
وبالضبط نحن
تمكنوا to-- كيف يمكننا

281
00:08:26,040 --> 00:08:28,409
كانت قادرة على حل هذه
عندما كنا مجرد مشكلة

282
00:08:28,409 --> 00:08:29,950
نظرا مجموعة كاملة من المدخلات العشوائية.

283
00:08:29,950 --> 00:08:31,610
>> حسنا، يبدو أن هناك
كان نوعا من النظام هناك؟

284
00:08:31,610 --> 00:08:32,110
الصحيح.

285
00:08:32,110 --> 00:08:34,495
حتى الرسائل السابقة
في الأبجدية، وقالت انها

286
00:08:34,495 --> 00:08:37,120
كان وضع إلى اليسار، و
رسائل في وقت لاحق في الأبجدية،

287
00:08:37,120 --> 00:08:38,270
كانت تضع في الحق.

288
00:08:38,270 --> 00:08:40,500
وحالما وجدت
بعض الحروف الداني، منها

289
00:08:40,500 --> 00:08:43,124
التي تذهب بجوار بعضها البعض،
فإنها ستضع تلك الموجودة في النظام.

290
00:08:43,124 --> 00:08:46,750
ولذا فإننا النوع من كان هؤلاء الصغيرة
أكوام من المدخلات التي تم فرزها الحدوث.

291
00:08:46,750 --> 00:08:50,540
>> وحتى هذا تماما مثل ما
ومعظمنا يفعل البشر.

292
00:08:50,540 --> 00:08:53,530
كنا النوع من التدقيق من خلال ذلك،
وسيكون لدينا نوع من الآلية.

293
00:08:53,530 --> 00:08:56,930
ولكن قد يكون من الصعب الكتابة
عليه في صيغة في حد ذاته.

294
00:08:56,930 --> 00:08:59,010
ورأى أكثر قليلا العضوية من ذلك.

295
00:08:59,010 --> 00:09:02,560
لذلك دعونا نرى ما اذا كنا نستطيع الآن ملزمة
المشكلة مع عدد أقل من المدخلات.

296
00:09:02,560 --> 00:09:05,170
>> بدلا من 26، دعنا
نفعل شيئا أقل بكثير

297
00:09:05,170 --> 00:09:09,890
مع أن أقول، سبعة، وراء
هذه الأبواب، إذا جاز التعبير.

298
00:09:09,890 --> 00:09:11,300
هل هناك فقط سبعة أرقام؟

299
00:09:11,300 --> 00:09:15,240
وإذا كان الهدف الآن في
اليد لإيجاد قيمة،

300
00:09:15,240 --> 00:09:17,850
دعونا نرى كيف بكفاءة
يمكننا أن نذهب عن القيام بذلك.

301
00:09:17,850 --> 00:09:22,460
ودعونا نرى ما اذا كان يمكننا الآن
البدء في تطبيق بعض الأرقام،

302
00:09:22,460 --> 00:09:26,310
أو بعض الصيغ التي لوصف
كفاءة دفتر الهاتف لدينا

303
00:09:26,310 --> 00:09:31,060
الخوارزمية، لدينا خوارزمية كتاب الامتحان، و
بشكل عام، وإيجاد المعلومات.

304
00:09:31,060 --> 00:09:34,770
>> لذلك لهذا، اسمحوا لي أن المضي قدما، و
على شاشة تعمل باللمس أكثر من هنا،

305
00:09:34,770 --> 00:09:41,100
طرح متصفح الإنترنت الذي لديه
بالضبط هذه الأبواب السبعة.

306
00:09:41,100 --> 00:09:46,670
وإذا لم نتمكن من الحصول على واحدة أخرى
التطوع لتأتي على أكثر من هنا،

307
00:09:46,670 --> 00:09:48,480
لقد وضعت هذه نفس الأبواب أكثر من هنا.

308
00:09:48,480 --> 00:09:49,170
المتطوعين سريع.

309
00:09:49,170 --> 00:09:51,130
>> هذه العروض احدا-- تسير
إلى أسرع وأسرع الآن.

310
00:09:51,130 --> 00:09:51,600
تعال للأسفل.

311
00:09:51,600 --> 00:09:52,308
ما اسمك؟

312
00:09:52,308 --> 00:09:53,040
TREVOR: تريفور.

313
00:09:53,040 --> 00:09:53,998
>> DAVID J. مالان: تريفور؟

314
00:09:53,998 --> 00:09:55,770
كل الحق، تريفور، هيا إلى أسفل.

315
00:09:55,770 --> 00:09:59,212
لذلك فقد تطوع تريفور هنا ل
القيام مشكلة مماثلة، ولكن واحد وهذا

316
00:09:59,212 --> 00:10:02,170
أضيق نطاقا، والتي يجري
للسماح لنا في محاولة لإضفاء الطابع الرسمي الآن

317
00:10:02,170 --> 00:10:03,970
عملية الفرز هذه الأرقام.

318
00:10:03,970 --> 00:10:05,500
>> حتى تريفور، لطيف لمقابلتك.

319
00:10:05,500 --> 00:10:08,720
حتى هنا هو مجموعة، وذلك ل
الكلام، وقائمة من سبعة أبواب.

320
00:10:08,720 --> 00:10:10,327
المضي قدما وتجد لنا رقم 50.

321
00:10:10,327 --> 00:10:12,410
ثم بعد وقوعها،
تقول لنا كيف كنت وجدت.

322
00:10:12,410 --> 00:10:19,124

323
00:10:19,124 --> 00:10:20,040
يجب be-- كل الحق.

324
00:10:20,040 --> 00:10:21,945
نعم، وهذا هو واحد هنا؟

325
00:10:21,945 --> 00:10:24,680
اه اوه.

326
00:10:24,680 --> 00:10:25,560
حسنا.

327
00:10:25,560 --> 00:10:26,680
نقرت أن واحدا.

328
00:10:26,680 --> 00:10:28,690
جيد.

329
00:10:28,690 --> 00:10:29,780
>> و جيد.

330
00:10:29,780 --> 00:10:30,970
الآن يمكنك النقر أن واحدا.

331
00:10:30,970 --> 00:10:34,060
واسمحوا لي أن أقدم لكم الميكروفون،
بحيث يكون لديك في لحظة فقط.

332
00:10:34,060 --> 00:10:37,000
المضي قدما وانقر على
المجاور الذي تنوي.

333
00:10:37,000 --> 00:10:39,812
نعم جيد.

334
00:10:39,812 --> 00:10:41,020
TREVOR: هل يمكنني unclick الباب؟

335
00:10:41,020 --> 00:10:42,620
DAVID J. مالان: لا، لا يمكنك unclick.

336
00:10:42,620 --> 00:10:43,119
TREVOR: OK.

337
00:10:43,119 --> 00:10:43,974
هذا.

338
00:10:43,974 --> 00:10:45,640
DAVID J. مالان: أين تريد أن تذهب؟

339
00:10:45,640 --> 00:10:46,410
أي واحد؟

340
00:10:46,410 --> 00:10:47,230
>> TREVOR: هذا واحد.

341
00:10:47,230 --> 00:10:48,042
>> DAVID J. مالان: رقم

342
00:10:48,042 --> 00:10:48,450
>> TREVOR: OK.

343
00:10:48,450 --> 00:10:48,735
هذا.

344
00:10:48,735 --> 00:10:49,020
>> DAVID J. مالان: نعم.

345
00:10:49,020 --> 00:10:49,700
كان ذلك جيدا.

346
00:10:49,700 --> 00:10:50,380
حسنا.

347
00:10:50,380 --> 00:10:53,900
فما كان خوارزمية أو
الإجراء للقيام بذلك، تريفور؟

348
00:10:53,900 --> 00:10:56,149
>> TREVOR: أنا فقط ذهبت من خلال
الأبواب حتى وجدت 50.

349
00:10:56,149 --> 00:10:56,940
DAVID J. مالان: OK.

350
00:10:56,940 --> 00:10:58,150
خوارزمية ممتازة.

351
00:10:58,150 --> 00:10:59,540
لذلك فلا بأس.

352
00:10:59,540 --> 00:11:03,120
لأنه في الواقع، إذا أنا تكشف ما
خلف هذه الأبواب الأخريين، ما

353
00:11:03,120 --> 00:11:06,954
سنجد هنا هو أن
ليس لدينا سوى إدخال عشوائي.

354
00:11:06,954 --> 00:11:08,870
بحيث كان في الواقع كما
جيدة كما يمكن أن تحصل.

355
00:11:08,870 --> 00:11:12,509
وفي الواقع، كنت حصلت على أفضل من
البحث باستفاضة في مجموعة كاملة،

356
00:11:12,509 --> 00:11:15,300
لأنه يمكن أن يكون حقا
غير محظوظين إذا كنت قد تصل إلى العدد

357
00:11:15,300 --> 00:11:16,604
50 في الباب الأخير للغاية.

358
00:11:16,604 --> 00:11:18,520
ولكن ماذا لو أننا بدلا من ذلك
أعطاك هذا الافتراض.

359
00:11:18,520 --> 00:11:20,630
افترض نوع جميعا
هذه الأبواب حولها،

360
00:11:20,630 --> 00:11:23,500
بحيث يكون لديك ل
أرقام فرز هذه المرة،

361
00:11:23,500 --> 00:11:29,730
ولكن هذه المرة انها فعلا
وdifferent-- هذا الوقت،

362
00:11:29,730 --> 00:11:32,640
انها مرتبة في الواقع بالنسبة لك.

363
00:11:32,640 --> 00:11:35,380
والآن الهدف في متناول اليد
هو ضرب رقم 50.

364
00:11:35,380 --> 00:11:36,090
>> TREVOR: OK.

365
00:11:36,090 --> 00:11:37,670
>> DAVID J. مالان: ما هو
خوارزمية الخاص بك سيكون؟

366
00:11:37,670 --> 00:11:39,628
>> TREVOR: حسنا، إذا كان
مرتبة، فإنه إما الذهاب

367
00:11:39,628 --> 00:11:42,710
لbe-- إذا الأكبر لأكبر،
تنازلي، فإنه سوف يكون أول واحد،

368
00:11:42,710 --> 00:11:44,751
أو إذا كان العكس،
وسوف يكون آخر واحد.

369
00:11:44,751 --> 00:11:48,897
ولذا فإنني سوف مجرد استغلال هذا الباب، و
ثم فقط اضغط على الباب الأخير.

370
00:11:48,897 --> 00:11:49,980
DAVID J. مالان: ممتاز.

371
00:11:49,980 --> 00:11:50,270
حسنا.

372
00:11:50,270 --> 00:11:51,150
لذلك وجدنا عدد 50.

373
00:11:51,150 --> 00:11:52,970
ذلك في أقرب وقت كما كنت أعرف
تم فرزها، ونحن

374
00:11:52,970 --> 00:11:55,040
كانوا قادرين على الاستفادة من هذا الافتراض.

375
00:11:55,040 --> 00:11:57,040
حتى انهم مثل الكثير
على سبيل المثال دفتر الهاتف.

376
00:11:57,040 --> 00:11:59,540
بأسرع ما لديك، حتى مع
مشكلة صغيرة مثل هذه،

377
00:11:59,540 --> 00:12:02,380
إسهاماتكم مرتبة مسبقا، ما في وسعنا
تجد في الواقع قيمة يمكن القول

378
00:12:02,380 --> 00:12:03,130
أكثر كفاءة.

379
00:12:03,130 --> 00:12:05,800
>> وأنا لا أقول لكم إذا كان
فرز الصغيرة الى الكبيرة، أو كبيرة للمشاريع الصغيرة،

380
00:12:05,800 --> 00:12:08,080
وهكذا كان من المعقول جدا
أن تبدأ في نهاية واحدة أو أخرى

381
00:12:08,080 --> 00:12:09,750
لتجد في الواقع أن القيمة المستهدفة.

382
00:12:09,750 --> 00:12:11,400
لذا شكرا لتريفور كذلك.

383
00:12:11,400 --> 00:12:13,260
وسوف propose-- القيام به بشكل جيد.

384
00:12:13,260 --> 00:12:16,960
لدينا القليل من مقطع، في الواقع، أن
من بين اللحظات المفضلة لدينا في CS50،

385
00:12:16,960 --> 00:12:19,700
حيث في بعض الأحيان هذه العروض
لا تذهب تماما وفقا للخطة الموضوعة.

386
00:12:19,700 --> 00:12:22,050
والآن في الواقع الحق، وأنا
سحب ما يصل الواجهة غير صحيح

387
00:12:22,050 --> 00:12:23,508
مع الذي لاستخدام شاشة تعمل باللمس.

388
00:12:23,508 --> 00:12:24,660
لذلك كان هذا خطأي هناك.

389
00:12:24,660 --> 00:12:26,600
>> ولذلك فإن هذا سيجعل ل
مقطع العام المقبل كما

390
00:12:26,600 --> 00:12:28,570
لماذا كنت النقر على الشاشة الخاصة.

391
00:12:28,570 --> 00:12:31,390
ولكن دعونا نلقي نظرة سريعة
في ما حدث العام الماضي

392
00:12:31,390 --> 00:12:34,770
مع جاي، الذي جاء، والكثير
مثل تريفور هنا، تطوع،

393
00:12:34,770 --> 00:12:39,380
وهذا مقطع قصير، سترى
كيف هذا العرض نفسه ليس تماما

394
00:12:39,380 --> 00:12:41,074
كشف نفس الدروس المستفادة.

395
00:12:41,074 --> 00:12:41,740
[تشغيل الفيديو]

396
00:12:41,740 --> 00:12:45,360
-جميع أريدك أن نفعله الآن هو
للعثور بالنسبة لي، وبالنسبة لنا،

397
00:12:45,360 --> 00:12:51,674
حقا، عدد 50
خطوة واحدة في وقت واحد.

398
00:12:51,674 --> 00:12:52,450
>> -THE عدد 50؟

399
00:12:52,450 --> 00:12:53,190
>> -THE عدد 50.

400
00:12:53,190 --> 00:12:55,356
ويمكنك الكشف عما هو
وراء كل من هذه الأبواب

401
00:12:55,356 --> 00:12:58,540
ببساطة عن طريق لمسها بأصابعك.

402
00:12:58,540 --> 00:13:00,910
عليك اللعنة.

403
00:13:00,910 --> 00:13:02,870
>> [يضحك]

404
00:13:02,870 --> 00:13:03,806
>> [END قراءة]

405
00:13:03,806 --> 00:13:05,430
DAVID J. مالان: ولهذا سارت على ما يرام.

406
00:13:05,430 --> 00:13:06,796
كانت تلك الأبواب التي لم يتم فرزها.

407
00:13:06,796 --> 00:13:08,670
وجاي، بطبيعة الحال،
وجدت كل شيء بسرعة كبيرة جدا.

408
00:13:08,670 --> 00:13:12,910
لم تريفور بعمل أفضل بكثير
من حيث لحظة قابلة للتعليم،

409
00:13:12,910 --> 00:13:15,850
إذا جاز التعبير، وهذا العام في
يستغرق وقتا أطول للعثور عليه.

410
00:13:15,850 --> 00:13:17,950
وبطبيعة الحال، ثم أعطينا
جاي على فرصة ثانية،

411
00:13:17,950 --> 00:13:20,320
حيث قمنا بفرز الأبواب،
تماما كما فعلنا لتريفور،

412
00:13:20,320 --> 00:13:22,300
وفعل تريفور السوبر جيدا هذه المرة.

413
00:13:22,300 --> 00:13:26,124
ولكن جاي فعل ذلك نصف في أسرع وقت.

414
00:13:26,124 --> 00:13:26,790
[تشغيل الفيديو]

415
00:13:26,790 --> 00:13:29,650
-THE الهدف الآن هو أيضا
تجدنا عدد 50،

416
00:13:29,650 --> 00:13:33,030
ولكنها تفعل ذلك حسابيا، و
تخبرنا كيف وأنت تسير حول هذا الموضوع.

417
00:13:33,030 --> 00:13:33,660
>> -حسنا.

418
00:13:33,660 --> 00:13:35,604
>> -و إذا وجدت أنه، عليك أن تبقي الفيلم.

419
00:13:35,604 --> 00:13:37,228
إذا كنت لا تجد ذلك، ليعيدها.

420
00:13:37,228 --> 00:13:38,044
>> -man.

421
00:13:38,044 --> 00:13:38,860
>> أوه!

422
00:13:38,860 --> 00:13:40,800
>> - [غير مسموع] OK.

423
00:13:40,800 --> 00:13:46,236
لذلك أنا ذاهب للتحقق الغايات
أولا لتحديد ما إذا there's-- أوه.

424
00:13:46,236 --> 00:13:48,646
>> [تصفيق]

425
00:13:48,646 --> 00:13:53,948

426
00:13:53,948 --> 00:13:55,729
>> [END قراءة]

427
00:13:55,729 --> 00:13:56,520
DAVID J. مالان: OK.

428
00:13:56,520 --> 00:13:59,760
حتى فرز الأبواب بشكل واضح
يؤدي إلى زيادة الكفاءة.

429
00:13:59,760 --> 00:14:01,680
وهكذا، أسرع مرتين
ما قصدته هناك.

430
00:14:01,680 --> 00:14:03,270
وهكذا حصلت جاي محظوظا في كل الأوقات.

431
00:14:03,270 --> 00:14:06,685
وحصل أيضا محظوظا في ذلك الماضي
العام، وأمرت بعض أقراص بلو راي

432
00:14:06,685 --> 00:14:07,560
لإعطاء فعلا.

433
00:14:07,560 --> 00:14:09,768
أنا آسف لهذا العام، ونحن
لم يكن لديك واحدة، تريفور.

434
00:14:09,768 --> 00:14:11,540
ولكن الأفضل من ذلك كان قبل بضع سنوات.

435
00:14:11,540 --> 00:14:14,820
والبعض منكم قد تعرف هذا
زميل، شون، الذي عندما كان في CS50،

436
00:14:14,820 --> 00:14:17,780
وطعن مع الدقة
نفس المشكلة، وإن كان ذلك في SD،

437
00:14:17,780 --> 00:14:19,360
كما سترى قريبا، مرة في اليوم.

438
00:14:19,360 --> 00:14:22,622
وسوف تجد أن لا فعل فقط
انه يستغرق وقتا أطول قليلا من جاي،

439
00:14:22,622 --> 00:14:25,580
لفترة أطول قليلا من تريفور، كان عليه
في الواقع هذه الفرصة الرائعة

440
00:14:25,580 --> 00:14:29,820
لإشراك الجميع تقريبا في
الحشد على غرار السعر مناسبا، وتشجيع

441
00:14:29,820 --> 00:14:31,889
له للعثور على عدد كنا نسعى.

442
00:14:31,889 --> 00:14:32,930
دعونا. نلقي نظرة سريعة.

443
00:14:32,930 --> 00:14:33,320
>> [تشغيل الفيديو]

444
00:14:33,320 --> 00:14:33,820
>> -حسنا.

445
00:14:33,820 --> 00:14:36,680
لذلك مهمتك هنا،
شون، هو ما يلي.

446
00:14:36,680 --> 00:14:40,860
لقد خفية وراء هذه
أبواب الرقم سبعة.

447
00:14:40,860 --> 00:14:45,120
لكن مطوي بعيدا في بعض هذه الأبواب
كما هي أيضا الأرقام السلبية الأخرى.

448
00:14:45,120 --> 00:14:47,500
وهدفك هو التفكير
هذا الصف العلوي من الأرقام

449
00:14:47,500 --> 00:14:50,390
كمجرد صفيف، أو مجرد
تسلسل قطعة من الورق

450
00:14:50,390 --> 00:14:51,510
مع الأرقام التي تقف وراءها.

451
00:14:51,510 --> 00:14:55,540
وهدفك هو، فقط باستخدام أعلى
مجموعة هنا، تجد لي الرقم سبعة.

452
00:14:55,540 --> 00:14:58,570
ونحن بعد ذلك يذهب إلى نقد
كيف تذهب عن القيام بذلك.

453
00:14:58,570 --> 00:14:59,070
-حسنا.

454
00:14:59,070 --> 00:15:00,850
-Find لنا رقم سبعة، من فضلك.

455
00:15:00,850 --> 00:15:10,500

456
00:15:10,500 --> 00:15:11,000
لا.

457
00:15:11,000 --> 00:15:15,050

458
00:15:15,050 --> 00:15:18,550
خمسة و 19 و 13.

459
00:15:18,550 --> 00:15:22,240

460
00:15:22,240 --> 00:15:24,770
>> [يضحك]

461
00:15:24,770 --> 00:15:25,910
>> انها ليست مسألة خدعة.

462
00:15:25,910 --> 00:15:29,410

463
00:15:29,410 --> 00:15:29,910
واحدة.

464
00:15:29,910 --> 00:15:33,218

465
00:15:33,218 --> 00:15:34,695
>> [يضحك]

466
00:15:34,695 --> 00:15:37,861
في هذه المرحلة، والنتيجة ليست غاية
جيدة، لذلك قد واصلتم بالإضافة الذهاب.

467
00:15:37,861 --> 00:15:40,610

468
00:15:40,610 --> 00:15:41,110
ثلاثة.

469
00:15:41,110 --> 00:15:43,890

470
00:15:43,890 --> 00:15:45,378
>> [يضحك]

471
00:15:45,378 --> 00:15:46,370

472
00:15:46,370 --> 00:15:47,774
>> تابع.

473
00:15:47,774 --> 00:15:50,690
بصراحة، لا يسعني إلا أن أتساءل
ما كنت حتى التفكير، so--

474
00:15:50,690 --> 00:15:51,959
>> [يضحك]

475
00:15:51,959 --> 00:15:53,229

476
00:15:53,229 --> 00:15:55,020
فقط في الصف العلوي، لذلك
كنت قد حصلت على ثلاثة اليسار.

477
00:15:55,020 --> 00:15:56,200
لذلك تجد لي سبعة.

478
00:15:56,200 --> 00:15:59,700

479
00:15:59,700 --> 00:16:02,167
>> [يضحك]

480
00:16:02,167 --> 00:16:14,870

481
00:16:14,870 --> 00:16:15,370
17.

482
00:16:15,370 --> 00:16:25,675

483
00:16:25,675 --> 00:16:26,946
سبعة.

484
00:16:26,946 --> 00:16:28,780
>> [تصفيق]

485
00:16:28,780 --> 00:16:29,426
>> حسنا.

486
00:16:29,426 --> 00:16:30,360
>> [END قراءة]

487
00:16:30,360 --> 00:16:31,840
>> DAVID J. مالان: حتى يمكن لنا
مشاهدة هذه طوال اليوم.

488
00:16:31,840 --> 00:16:34,090
وبطبيعة الحال، بعض
العروض هذا العام ربما

489
00:16:34,090 --> 00:16:36,330
سينتهي الآن حتى في القادم
الفيديو العام كذلك.

490
00:16:36,330 --> 00:16:39,040
حتى الآن دعونا الواقع
التركيز على خوارزميات

491
00:16:39,040 --> 00:16:42,140
هنا، ونرى اذا كنا لا يمكن
نبدأ الآن لإضفاء الطابع الرسمي

492
00:16:42,140 --> 00:16:46,650
كيف يمكننا التوجه نحو الحصول على البيانات المتوفرة لدينا
في هذه الحالة وهذا ما فرزها،

493
00:16:46,650 --> 00:16:50,054
حتى أنه في نهاية المطاف، ويمكننا فعلا
بحث عنها بشكل أكثر كفاءة.

494
00:16:50,054 --> 00:16:52,470
وعلى الرغم من أننا ذاهبون
استخدام مجموعات البيانات صغيرة إلى حد ما،

495
00:16:52,470 --> 00:16:54,511
مثل نحن ثمانية أرقام
لدينا هنا على متن الطائرة،

496
00:16:54,511 --> 00:16:58,230
في نهاية المطاف يمكن أن تنطبق هذه الأفكار نفسها
إلى 1000 المدخلات، مليون المدخلات،

497
00:16:58,230 --> 00:17:02,100
4 مليارات المدخلات، لأن الخوارزميات
ستكون الأساس نفسه.

498
00:17:02,100 --> 00:17:05,359
>> وهكذا هذا هو موقفنا الأخير
فرصة للمتطوعين اليوم،

499
00:17:05,359 --> 00:17:09,790
ولكن ربما الأكثر انخراطا واحد،
التي نحتاج ثمانية متطوعين

500
00:17:09,790 --> 00:17:12,960
من أجل التوصل إلى والسير بنا من خلال
عملية الفرز ما قريبا

501
00:17:12,960 --> 00:17:15,212
يكون على هذه الموسيقى تقف هنا.

502
00:17:15,212 --> 00:17:16,170
اسمحوا لي أن أبدأ هنا مرة أخرى.

503
00:17:16,170 --> 00:17:19,692
>> حتى واحد في المنطقة الخضراء turquoise-- هو؟

504
00:17:19,692 --> 00:17:21,130
هل بارتكاب؟

505
00:17:21,130 --> 00:17:21,630
اثنين.

506
00:17:21,630 --> 00:17:23,069
تعال للأسفل.

507
00:17:23,069 --> 00:17:23,569
حسنا.

508
00:17:23,569 --> 00:17:24,420
ثلاثة.

509
00:17:24,420 --> 00:17:25,400
أربعة.

510
00:17:25,400 --> 00:17:27,247
السماح me-- OK، خمسة.

511
00:17:27,247 --> 00:17:28,830
كنت ترشيحهم من قبل صديقك.

512
00:17:28,830 --> 00:17:31,340
ستة، سبعة، وثمانية.

513
00:17:31,340 --> 00:17:32,130
تأتي على ما يصل.

514
00:17:32,130 --> 00:17:32,630
حسنا.

515
00:17:32,630 --> 00:17:33,190
شكرا جزيلا.

516
00:17:33,190 --> 00:17:33,689
تأتي على ما يصل.

517
00:17:33,689 --> 00:17:34,790
تأتي على ما يصل.

518
00:17:34,790 --> 00:17:35,330
>> حسنا.

519
00:17:35,330 --> 00:17:38,890
ذلك ما لدينا here-- وهذا
من بين تلك الأكثر حرج،

520
00:17:38,890 --> 00:17:42,390
لأن هذا سوف تتطلب منك النكتة
لي قليلا من الوقت.

521
00:17:42,390 --> 00:17:43,442
يجب أن تكون رقم واحد.

522
00:17:43,442 --> 00:17:44,150
ما اسمك؟

523
00:17:44,150 --> 00:17:44,610
>> عنان: عنان.

524
00:17:44,610 --> 00:17:45,526
>> DAVID J. مالان: عنان.

525
00:17:45,526 --> 00:17:46,092
ديفيد.

526
00:17:46,092 --> 00:17:46,800
ما اسمك؟

527
00:17:46,800 --> 00:17:47,140
>> يوسف: يوسف.

528
00:17:47,140 --> 00:17:49,190
>> DAVID J. مالان: يوسف
كنت رقم اثنين.

529
00:17:49,190 --> 00:17:52,260
>> سيرينا: سيرينا، رقم ثلاثة.

530
00:17:52,260 --> 00:17:53,722
ستيفان، رقم أربعة.

531
00:17:53,722 --> 00:17:54,430
CYNTHIA: سينثيا.

532
00:17:54,430 --> 00:17:57,548
DAVID J. مالان: سينثيا، رقم خمسة.

533
00:17:57,548 --> 00:17:58,452
(غير مسموع)

534
00:17:58,452 --> 00:17:59,618
DAVID J. مالان: (غير مسموع).

535
00:17:59,618 --> 00:18:00,391
ديفيد، رقم ستة.

536
00:18:00,391 --> 00:18:00,890
مات: مات.

537
00:18:00,890 --> 00:18:02,160
DAVID J. مالان: مات الرقم سبعة.

538
00:18:02,160 --> 00:18:02,850
و؟

539
00:18:02,850 --> 00:18:03,210
>> WAVERLY: يفرلي.

540
00:18:03,210 --> 00:18:04,470
>> DAVID J. مالان: يفرلي، رقم ثمانية.

541
00:18:04,470 --> 00:18:04,970
حسنا.

542
00:18:04,970 --> 00:18:06,510
إذا كنت could-- يصيح.

543
00:18:06,510 --> 00:18:08,820
إذا كنت فقط، كما لديك
التحدي الأول، هناك

544
00:18:08,820 --> 00:18:10,820
هي ثمانية وتقف والموسيقى
تواجه هنا للجمهور.

545
00:18:10,820 --> 00:18:14,200
إذا كنت قد وضعت الأرقام الخاصة بك على
هذه الموسيقى يقف في مثل هذه الطريقة

546
00:18:14,200 --> 00:18:16,560
أنهم يصطف مع
نفس الأرقام على لوحة.

547
00:18:16,560 --> 00:18:19,560
وهكذا جعل أنفسكم تبدو مثل هذا من قبل
وضع الأرقام الخاصة بك على هذه الموسيقى

548
00:18:19,560 --> 00:18:21,960
تقف هنا.

549
00:18:21,960 --> 00:18:25,980
ممتاز حتى الآن.

550
00:18:25,980 --> 00:18:26,600
>> ممتاز.

551
00:18:26,600 --> 00:18:26,890
حسنا.

552
00:18:26,890 --> 00:18:29,556
وحتى الآن، ونحن في طريقنا لمطالبة
السؤال في عدة طرق مختلفة.

553
00:18:29,556 --> 00:18:31,610
كيف يمكن أن نذهب حول فرز
هؤلاء الناس هنا؟

554
00:18:31,610 --> 00:18:34,500
لأنه كان لدينا عدد قليل من النهج
في وقت سابق، حيث كنا

555
00:18:34,500 --> 00:18:36,360
نوع من جعل دلوين مختلفة.

556
00:18:36,360 --> 00:18:38,842
ثم كنا عموما
التفكيك الأشياء معا.

557
00:18:38,842 --> 00:18:41,050
في أقرب وقت كما رأينا رقمين
التي تنتمي معا،

558
00:18:41,050 --> 00:18:41,975
وضعنا لهم معا.

559
00:18:41,975 --> 00:18:43,350
رسالتين التي تنتمي معا.

560
00:18:43,350 --> 00:18:45,058
>> ولكن دعونا نرى ما اذا كنا
لا يمكن إضفاء الطابع الرسمي على هذا،

561
00:18:45,058 --> 00:18:48,044
حتى يكون لدينا في نهاية المطاف
بعض الزائفة رمز شئت،

562
00:18:48,044 --> 00:18:49,710
والتي يمكنك حل هذه المشاكل.

563
00:18:49,710 --> 00:18:51,870
وحتى الآن، وأنا أبحث خارج
في هذه الأرقام هنا.

564
00:18:51,870 --> 00:18:55,030
وأرى في مجمله مجموعة من الأخطاء.

565
00:18:55,030 --> 00:18:57,750
في النهاية، أريد واحدة على
اليسار وثمانية على اليمين.

566
00:18:57,750 --> 00:19:00,650
>> وهكذا أنا أبحث في
هذين، أربعة واثنين.

567
00:19:00,650 --> 00:19:02,930
وما هي المشكلة، من الواضح؟

568
00:19:02,930 --> 00:19:04,261
نعم.

569
00:19:04,261 --> 00:19:04,760
هكذا.

570
00:19:04,760 --> 00:19:07,160
ومن الواضح أن اثنين من يأتي قبل
أربعة، لذلك أنت تعرف لماذا؟

571
00:19:07,160 --> 00:19:10,210
اسمحوا لي أولا أن تتخذ نهجا الجشع،
اذا صح التعبير، والكثير مشكلة مثل

572
00:19:10,210 --> 00:19:13,790
تعيين احدا-- إذا كنت تذكر من
الإصدار القياسي من مشكلة مجموعة واحدة،

573
00:19:13,790 --> 00:19:16,820
حيث أنا فقط حل المشكلة محليا
هذا صحيح هنا أمامي

574
00:19:16,820 --> 00:19:17,690
ونرى أين يقودني.

575
00:19:17,690 --> 00:19:17,870
>> حسنا.

576
00:19:17,870 --> 00:19:20,161
حتى اثنين وأربعة، واسمحوا لي ان اذهب
قبل وبعد مبادلة لكم اثنين.

577
00:19:20,161 --> 00:19:22,400
إذا كنت تستطيع التحرك جسديا
أنفسكم والورق،

578
00:19:22,400 --> 00:19:25,040
يبدو لي أن حصلت على
قائمة في حالة أفضل.

579
00:19:25,040 --> 00:19:26,330
>> الآن، انهم جيدة.

580
00:19:26,330 --> 00:19:28,480
انا ذاهب للمضي قدما،
أربعة وستة، تبدو جيدة.

581
00:19:28,480 --> 00:19:29,110
ليست مشكلة.

582
00:19:29,110 --> 00:19:30,440
ستة وثمانية، OK.

583
00:19:30,440 --> 00:19:31,860
ثمانية واحد، مشكلة أخرى.

584
00:19:31,860 --> 00:19:34,750
لأن ما هو صحيح حوالي ثمانية واحد؟

585
00:19:34,750 --> 00:19:36,990
واحد يأتي قبل ثمانية،
وذلك ما ينبغي أن نفعله؟

586
00:19:36,990 --> 00:19:38,090
دعونا مبادلة هذين.

587
00:19:38,090 --> 00:19:39,316
واحد وثمانية.

588
00:19:39,316 --> 00:19:40,690
والآن، انا ذاهب الى الاستمرار.

589
00:19:40,690 --> 00:19:42,030
انا ذاهب للحفاظ على استشراف المستقبل.

590
00:19:42,030 --> 00:19:42,840
ودعونا نرى ما سيحدث.

591
00:19:42,840 --> 00:19:44,680
ثمانية وثلاثة من
بطبيعة الحال، للخروج من النظام.

592
00:19:44,680 --> 00:19:45,815
دعونا المبادلة.

593
00:19:45,815 --> 00:19:46,940
ثمانية وسبعة، بطبيعة الحال.

594
00:19:46,940 --> 00:19:47,481
من النظام.

595
00:19:47,481 --> 00:19:48,280
دعونا المبادلة.

596
00:19:48,280 --> 00:19:49,940
ثمانية وخمسة، وبطبيعة الحال، دعونا المبادلة.

597
00:19:49,940 --> 00:19:50,560
حسنا.

598
00:19:50,560 --> 00:19:51,880
يتم فرز القائمة.

599
00:19:51,880 --> 00:19:53,060
نعم؟

600
00:19:53,060 --> 00:19:54,280
>> OK، من الواضح أن لا.

601
00:19:54,280 --> 00:19:55,860
ولكن من الأفضل قليلا، أليس كذلك؟

602
00:19:55,860 --> 00:19:57,270
لأن إشعار ما حدث.

603
00:19:57,270 --> 00:20:01,749
في كل مرة أجرينا المبادلة أصغر
عدد النوع من يسيل بهذه الطريقة،

604
00:20:01,749 --> 00:20:03,790
وعدد أكبر
يسيل بهذه الطريقة، أو أننا سوف

605
00:20:03,790 --> 00:20:06,880
بدء قائلا فقاعات ل
اليسار أو فقاعات إلى اليمين.

606
00:20:06,880 --> 00:20:10,080
>> الآن، فإنه لا يكفي، لأن
في أحسن الأحوال قد عدد

607
00:20:10,080 --> 00:20:11,990
تحركت بقعة واحدة
إلى الأمام، أو في أسوأ الأحوال،

608
00:20:11,990 --> 00:20:13,880
عدد قد يكون
انتقل بقعة واحدة أبعد من ذلك.

609
00:20:13,880 --> 00:20:16,369
حتى تعرف ما، وهذا النوع
من عملت بشكل جيد جدا حتى الآن.

610
00:20:16,369 --> 00:20:17,410
اسمحوا لي انها مجرد محاولة مرة أخرى.

611
00:20:17,410 --> 00:20:18,880
اثنين وأربعة، وانهم موافق.

612
00:20:18,880 --> 00:20:20,180
أربعة وستة، وانهم موافق.

613
00:20:20,180 --> 00:20:21,790
ستة واحد، خارج الترتيب.

614
00:20:21,790 --> 00:20:23,007
لذلك دعونا مبادلة لكم اثنين.

615
00:20:23,007 --> 00:20:25,840
والآن، لاحظ للمشكلة
بدءا من الحصول على أفضل قليلا مرة أخرى.

616
00:20:25,840 --> 00:20:27,006
ستة وثلاثة، خارج الترتيب.

617
00:20:27,006 --> 00:20:28,100
دعونا مبادلة لكم اثنين.

618
00:20:28,100 --> 00:20:29,730
ستة وسبعة، كنت جيدة.

619
00:20:29,730 --> 00:20:32,230
سبعة وخمسة، بطبيعة الحال، للخروج من النظام.

620
00:20:32,230 --> 00:20:33,920
سبعة وثمانية في النظام.

621
00:20:33,920 --> 00:20:36,470
والآن، وأنا قد تحتاج إلى
القيام بذلك عدة مرات.

622
00:20:36,470 --> 00:20:39,830
وفي الواقع، أعتقد أن لأنفسكم
ربما كم مرة الحد الأقصى

623
00:20:39,830 --> 00:20:41,330
قد لدي على المشي ذهابا وإيابا؟

624
00:20:41,330 --> 00:20:42,390
>> سوف نعود إلى ذلك.

625
00:20:42,390 --> 00:20:43,700
حتى اثنين وأربعة لا تزال موافق.

626
00:20:43,700 --> 00:20:44,940
أربعة واحد، كلا.

627
00:20:44,940 --> 00:20:45,747
لذا، دعونا المبادلة.

628
00:20:45,747 --> 00:20:47,830
ومرة أخرى، لاحظ بصريا
واحد هو نوع من السطح

629
00:20:47,830 --> 00:20:49,163
إلى اليسار، حيث يجب أن تكون.

630
00:20:49,163 --> 00:20:50,010
أربعة وثلاثة المبادلة.

631
00:20:50,010 --> 00:20:51,330
أربعة وستة.

632
00:20:51,330 --> 00:20:53,100
ستة وخمسة المبادلة.

633
00:20:53,100 --> 00:20:53,959
ستة وسبعة.

634
00:20:53,959 --> 00:20:55,000
سبعة وثمانية جيدة.

635
00:20:55,000 --> 00:20:55,500
>> جيد.

636
00:20:55,500 --> 00:20:58,460
نحن نحصل على أفضل.

637
00:20:58,460 --> 00:20:59,130
لذلك دعونا نرى.

638
00:20:59,130 --> 00:21:00,940
الآن، لدينا اثنين واحد.

639
00:21:00,940 --> 00:21:02,520
وبطبيعة الحال، مبادلة.

640
00:21:02,520 --> 00:21:07,520
اثنين وثلاثة، وثلاثة وأربعة، وأربعة و
خمسة وستة وسبعة، السابع والثامن.

641
00:21:07,520 --> 00:21:08,020
جيد.

642
00:21:08,020 --> 00:21:08,730
وأنت تعرف لماذا؟

643
00:21:08,730 --> 00:21:11,190
لأنني تغييرا واحدا هناك،
اسمحوا لي أن تفعل الاختيار التعقل واحد.

644
00:21:11,190 --> 00:21:13,023
اسمحوا لي أن يذهب كل في طريقه
العودة إلى البداية.

645
00:21:13,023 --> 00:21:13,680
حسنا.

646
00:21:13,680 --> 00:21:14,750
واحد، two-- نعم، ترى؟

647
00:21:14,750 --> 00:21:15,870
شيئا ما كان خطأ.

648
00:21:15,870 --> 00:21:18,420
ثلاثة، أربعة، خمسة، ستة، سبعة، ثمانية.

649
00:21:18,420 --> 00:21:21,920
وفي هذا المرور الماضي، هي
كنت مرتاحا مع بلدي الآن

650
00:21:21,920 --> 00:21:23,830
مدعية يتم فرز ذلك؟

651
00:21:23,830 --> 00:21:24,330
حسنا.

652
00:21:24,330 --> 00:21:25,880
بصريا، وهذا صحيح تماما.

653
00:21:25,880 --> 00:21:28,410
ولكن وظيفيا، ما
أيضا لم يحدث فقط

654
00:21:28,410 --> 00:21:31,870
في هذا الممر الأخير الذي يسمح لك
للتأكد من أن هذه القائمة هي في الواقع

655
00:21:31,870 --> 00:21:32,660
مرتبة؟

656
00:21:32,660 --> 00:21:34,477
>> ماذا أفعل أو لا تفعل هذا المرور الماضي؟

657
00:21:34,477 --> 00:21:35,810
الحضور: لم تكن هناك تغييرات.

658
00:21:35,810 --> 00:21:36,120
DAVID J. مالان: عذرا؟

659
00:21:36,120 --> 00:21:37,070
الجمهور: لا تغييرات.

660
00:21:37,070 --> 00:21:38,653
DAVID J. مالان: كانت هناك أية تغييرات.

661
00:21:38,653 --> 00:21:41,947
لذلك سيكون من الغباء لي ل
فعل ذلك الخوارزمية نفسها مرة أخرى

662
00:21:41,947 --> 00:21:43,780
إذا لم تقم بإجراء أية
التغييرات في المرة الأولى.

663
00:21:43,780 --> 00:21:45,160
والدولة لم يتغير.

664
00:21:45,160 --> 00:21:47,576
بالتأكيد، أنا لا أذهب إلى جعل
أي تغيير للمرة الثانية.

665
00:21:47,576 --> 00:21:49,820
وهكذا، انها آمنة الآن
أن أقول، يتم فرز القائمة.

666
00:21:49,820 --> 00:21:52,069
>> والواقع، وهذا هو الآن
شيء سنقوم عموما

667
00:21:52,069 --> 00:21:56,900
الدعوة من نوع فقاعة، حيث زوجيا،
يمكنك تصحيح الأخطاء مرة أخرى،

668
00:21:56,900 --> 00:22:00,210
ومرة أخرى، ومرة ​​أخرى، وكنت
الاستمرار ذهابا وإيابا،

669
00:22:00,210 --> 00:22:03,370
وذهابا وإيابا، حتى
جعل جود مثل هذه المقايضات، وعند هذه النقطة

670
00:22:03,370 --> 00:22:07,089
يمكنك أن تكون على ثقة، نعم، وأنا
الانتهاء من إصلاح جميع الأخطاء.

671
00:22:07,089 --> 00:22:08,630
دعونا إعادة تعيين ومحاولة مقاربة أخرى.

672
00:22:08,630 --> 00:22:11,590
إذا يا رفاق يمكن أن تذهب مرة أخرى إلى
النظام الذي كان قبل لحظة،

673
00:22:11,590 --> 00:22:13,780
التي بدت مثل هذا.

674
00:22:13,780 --> 00:22:17,640
الآن، دعونا نلقي النهج ل
أكثر قليلا مثل كتاب الامتحان،

675
00:22:17,640 --> 00:22:21,122
حيث كنا باستمرار
اختيار حرف من الأبجدية

676
00:22:21,122 --> 00:22:22,830
أننا نوع من أراد
للتعامل مع القادم.

677
00:22:22,830 --> 00:22:26,420
ربما كان بريد إلكتروني عالية،
مثل A، أو بريد إلكتروني Z. منخفض

678
00:22:26,420 --> 00:22:28,170
>> لذلك الجميع مرة أخرى في هذا النظام.

679
00:22:28,170 --> 00:22:29,800
والآن اسمحوا لي أن تفعل هذا.

680
00:22:29,800 --> 00:22:34,880
دعونا نرى أنا أعرف أن لدي
ثمانية أرقام هنا.

681
00:22:34,880 --> 00:22:37,410
انا ذاهب الى المضي قدما و
ما عليك سوى اختيار عمدا

682
00:22:37,410 --> 00:22:38,520
أصغر العناصر.

683
00:22:38,520 --> 00:22:38,760
الصحيح؟

684
00:22:38,760 --> 00:22:39,801
هذا يبدو بديهية جدا.

685
00:22:39,801 --> 00:22:42,560
لماذا لا أجد أصغر
عنصر، ووضعها حيث ينتمي،

686
00:22:42,560 --> 00:22:45,280
ثم الحصول على أصغر عنصر المقبل، وطرح
ذلك المكان الذي ينتمي إليه، ومجرد تكرار.

687
00:22:45,280 --> 00:22:46,820
>> لأن حدسي،
التي يجب أن تعمل أيضا.

688
00:22:46,820 --> 00:22:48,441
حتى أربعة، وهذا عدد قليل جدا.

689
00:22:48,441 --> 00:22:49,940
أنا ذاهب لنتذكر فيها هذا.

690
00:22:49,940 --> 00:22:50,523
إنتظر دقيقه.

691
00:22:50,523 --> 00:22:51,577
الثاني هو أصغر.

692
00:22:51,577 --> 00:22:53,910
اسمحوا لي أن أتذكر الآن حيث اثنين
هو، ونسيان الأربعة.

693
00:22:53,910 --> 00:22:55,050
نحن سنتعامل مع ذلك لاحقا.

694
00:22:55,050 --> 00:22:56,460
ستة، أنا غير مهتم.

695
00:22:56,460 --> 00:22:57,810
ثمانية، وأنا لست مهتما.

696
00:22:57,810 --> 00:22:59,780
واحد هو رقم هاتفي صغيرة جديدة.

697
00:22:59,780 --> 00:23:01,470
لذلك أنا ذاهب لنتذكر فيها واحد هو.

698
00:23:01,470 --> 00:23:02,534
ثلاثة، ليست مهتمة.

699
00:23:02,534 --> 00:23:03,450
سبعة، ليست مهتمة.

700
00:23:03,450 --> 00:23:04,530
خمسة، ليست مهتمة.

701
00:23:04,530 --> 00:23:07,390
>> ذلك دون السقوط
المرحلة هذا العام،

702
00:23:07,390 --> 00:23:09,890
انا ذاهب الى الاستيلاء على عدد احدا--
وماذا كان اسمك مرة أخرى؟

703
00:23:09,890 --> 00:23:10,150
>> عنان: عنان.

704
00:23:10,150 --> 00:23:11,220
>> DAVID J. مالان: عنان.

705
00:23:11,220 --> 00:23:13,540
وإذا كنت قد ينضم لي في
في بداية القائمة،

706
00:23:13,540 --> 00:23:14,870
دعونا نضع لك أين كنت تنتمي.

707
00:23:14,870 --> 00:23:16,080
Unfortunately-- ما اسمك؟

708
00:23:16,080 --> 00:23:16,650
>> STEFAN: ستيفان.

709
00:23:16,650 --> 00:23:18,191
>> DAVID J. مالان: ستيفان هو في الطريق.

710
00:23:18,191 --> 00:23:23,490
حتى قبل ستيفان يحل هذا
المشكلة، ماذا علينا أن نفعل؟

711
00:23:23,490 --> 00:23:25,412
ماذا نفعل مع ستيفان؟

712
00:23:25,412 --> 00:23:27,269
>> الحضور: (غير مسموع).

713
00:23:27,269 --> 00:23:28,060
DAVID J. مالان: OK.

714
00:23:28,060 --> 00:23:28,850
حتى نتمكن من فعل ذلك.

715
00:23:28,850 --> 00:23:31,730
يمكننا أن نوعا من اتخاذ ستيفان وله
أربعة، ومجرد وضعها في متغير

716
00:23:31,730 --> 00:23:33,530
وعقد لذلك ل
بعض مقدار الوقت،

717
00:23:33,530 --> 00:23:35,220
مما يجعل مجالا لرقم واحد.

718
00:23:35,220 --> 00:23:36,280
وهذا ليس سيئا.

719
00:23:36,280 --> 00:23:39,270
ويمكنني أن أقترح، لماذا لا
نحن مجرد وضع ستيفان هنا؟

720
00:23:39,270 --> 00:23:41,610
لماذا هذا قد تنتهك واحدة
من الأفكار بدأنا

721
00:23:41,610 --> 00:23:44,830
الحديث عن المرة السابقة، في الأسبوع الماضي؟

722
00:23:44,830 --> 00:23:45,330
نعم؟

723
00:23:45,330 --> 00:23:45,740
>> الحضور: (غير مسموع).

724
00:23:45,740 --> 00:23:46,860
>> DAVID J. مالان: لا يوجد أي مؤشر لذلك.

725
00:23:46,860 --> 00:23:49,735
إذا كنت تفكر في ذلك، في الواقع، بوصفه
مجموعة، وهذا هو مثل واحد سلبي،

726
00:23:49,735 --> 00:23:52,900
لذلك ليس هناك ذاكرة الواقع
هنا إذا كان هذا هو في الواقع مجموعة،

727
00:23:52,900 --> 00:23:55,090
كما أعلنا الأسبوع الماضي في محاضرة.

728
00:23:55,090 --> 00:23:56,250
لذلك لا ينبغي لنا أن نفعل ذلك.

729
00:23:56,250 --> 00:23:57,340
ونحن قد تخزينه في متغير.

730
00:23:57,340 --> 00:23:57,820
>> أو أنت تعرف لماذا؟

731
00:23:57,820 --> 00:23:59,153
سمعت شخص آخر تشير إلى ذلك.

732
00:23:59,153 --> 00:24:01,020
ماذا يمكن أن نفعل مع ستيفان؟

733
00:24:01,020 --> 00:24:03,770
لماذا لا يتم فقط إقصائه و
وضعه فوق، حيث كان رقم واحد.

734
00:24:03,770 --> 00:24:05,170
حتى إذا كنت تريد أن تذهب إلى هناك.

735
00:24:05,170 --> 00:24:07,300
والواقع، وهذا هو
حل جيد جدا.

736
00:24:07,300 --> 00:24:10,480
الآن من ناحية، لقد النوع
من جعل المشكلة أكثر سوءا.

737
00:24:10,480 --> 00:24:13,650
أربعة هو الآن بعيدا
من حيث ينبغي أن يكون.

738
00:24:13,650 --> 00:24:14,900
وينبغي أن يكون نحو هذا الشوط.

739
00:24:14,900 --> 00:24:16,100
>> ولكن هل تعرف لماذا؟

740
00:24:16,100 --> 00:24:17,630
كان يمكن أن يكون أن سوء الحظ.

741
00:24:17,630 --> 00:24:18,822
ربما كان عدد ثمانية هنا.

742
00:24:18,822 --> 00:24:20,530
وهكذا، ربما لو كنا
وقد حصلت محظوظ،

743
00:24:20,530 --> 00:24:22,460
ودفعت ثمانية أقرب إلى النهاية.

744
00:24:22,460 --> 00:24:24,710
وذلك في نهاية اليوم،
انها نوع من جميع المتوسطات.

745
00:24:24,710 --> 00:24:26,085
نحن لسنا بحاجة لرعاية حوالي أربعة.

746
00:24:26,085 --> 00:24:29,400
كل ما يهمني الآن هو
اختيار أصغر عنصر.

747
00:24:29,400 --> 00:24:32,030
>> والآن، ما أنا ذاهب ل
القيام به هو نسيان رقم واحد

748
00:24:32,030 --> 00:24:35,160
بشكل دائم، لأنني أعرف
يتم فرز الآن قائمة ورائي.

749
00:24:35,160 --> 00:24:36,720
لذلك كانت قائمتي سابقا حجم الثمانية.

750
00:24:36,720 --> 00:24:37,720
الآن، انها من حجم سبعة.

751
00:24:37,720 --> 00:24:40,340
ذلك هو الحصول على مشكلتي
أصغر، وإن كان ذلك خطيا.

752
00:24:40,340 --> 00:24:43,022
وحتى الآن، وانا ذاهب لتحديد
أصغر عنصر الحالي، وهما.

753
00:24:43,022 --> 00:24:46,520
ستة، ثمانية، أربعة، ثلاثة، سبعة، خمسة.

754
00:24:46,520 --> 00:24:47,770
وهذا هو أصغر عنصر.

755
00:24:47,770 --> 00:24:49,416
ذلك ما أنا ذاهب الى القيام به with--
ما كان اسمك مرة أخرى؟

756
00:24:49,416 --> 00:24:49,760
>> يوسف: يوسف.

757
00:24:49,760 --> 00:24:50,085
>> DAVID J. مالان: جوزيف؟

758
00:24:50,085 --> 00:24:52,000
ونحن في طريقنا لمغادرة يوسف في المكان.

759
00:24:52,000 --> 00:24:54,842
الآن، انا ذاهب الى التظاهر
أن هؤلاء الرجال are-- جيدا،

760
00:24:54,842 --> 00:24:56,550
وأنا أعلم أن هذين
يتم فرز بالفعل.

761
00:24:56,550 --> 00:24:58,424
دعونا نركز الآن على
تبقى قائمة.

762
00:24:58,424 --> 00:25:00,080
ستة هو أصغر الحالي.

763
00:25:00,080 --> 00:25:01,190
ثمانية هو أكبر.

764
00:25:01,190 --> 00:25:02,970
أربعة هي الآن أصغر الحالي.

765
00:25:02,970 --> 00:25:04,762
ثلاثة هي الآن أصغر الحالي.

766
00:25:04,762 --> 00:25:07,720
وحتى الآن، وانا ذاهب لتحديد ثلاثة،
الذين is-- ما اسمك مرة أخرى؟

767
00:25:07,720 --> 00:25:08,190
سيرينا: سيرينا.

768
00:25:08,190 --> 00:25:10,620
DAVID J. مالان: سيرينا، إذا كنت تستطيع
الاستيلاء على رقمك وتبادل with--

769
00:25:10,620 --> 00:25:11,550
KALSANG: Kalsang.

770
00:25:11,550 --> 00:25:12,940
DAVID J. مالان: Kalsang.

771
00:25:12,940 --> 00:25:15,220
هيا إلى الوراء، ونحن
الذهاب لمبادلة هذين.

772
00:25:15,220 --> 00:25:17,360
والآن، دعونا نضع هذا على الطيار الآلي.

773
00:25:17,360 --> 00:25:21,589
انا ذاهب الى الذهاب وترك الأمر ليا رفاق
لتحديد العناصر التالية أصغر.

774
00:25:21,589 --> 00:25:22,380
كميت، كميت، كميت، كميت.

775
00:25:22,380 --> 00:25:24,560
رقم أربعة، ماذا يجب ان تفعل؟

776
00:25:24,560 --> 00:25:26,261
ممتاز.

777
00:25:26,261 --> 00:25:27,760
الآن، وانا ذاهب لجعل مسار آخر.

778
00:25:27,760 --> 00:25:28,590
كميت، كميت، كميت، كميت.

779
00:25:28,590 --> 00:25:31,465
أرى خمسة هو أصغر المقبل.

780
00:25:31,465 --> 00:25:32,840
الآن، وانا ذاهب اتخاذ مسار آخر.

781
00:25:32,840 --> 00:25:33,631
كميت، كميت، كميت، كميت.

782
00:25:33,631 --> 00:25:34,880
ستة هو أصغر.

783
00:25:34,880 --> 00:25:35,520
جيد.

784
00:25:35,520 --> 00:25:36,585
سبعة هو أصغر.

785
00:25:36,585 --> 00:25:37,085
لا تغيير.

786
00:25:37,085 --> 00:25:38,630
ثمانية هو أصغر.

787
00:25:38,630 --> 00:25:39,170
فعله.

788
00:25:39,170 --> 00:25:43,900
>> وذلك ما فعلناه فقط عن طريق تكراري
اختيار عنصر واحد تلو الآخر

789
00:25:43,900 --> 00:25:47,230
تم تنفيذ شيء نحن
الذهاب إلى إضفاء الطابع الرسمي على النحو اختيار نوع.

790
00:25:47,230 --> 00:25:49,120
وانها ربما
بساطة لشرح،

791
00:25:49,120 --> 00:25:51,310
في هذا حرفيا كل ما
تريد القيام به هو الحفاظ فقط

792
00:25:51,310 --> 00:25:54,700
ذهابا وإيابا عبر قائمة
اختيار، أصغر عنصر المقبل،

793
00:25:54,700 --> 00:25:55,720
حتى الانتهاء من ذلك.

794
00:25:55,720 --> 00:25:58,650
>> لذلك فمن أبسط، وربما
حدسي، من الماضي.

795
00:25:58,650 --> 00:26:00,020
دعونا نحاول واحد آخر واحد.

796
00:26:00,020 --> 00:26:03,060
إذا يا رفاق يمكن إعادة أنفسكم
في المواقف التالية

797
00:26:03,060 --> 00:26:08,600
مرة واحدة نهائية، دعونا نرى إذا كنا لا نستطيع
إضفاء الطابع الرسمي الآن النهج الآخر.

798
00:26:08,600 --> 00:26:12,857
في الواقع، فإن أي شخص
هناك ترغب في اقتراح

799
00:26:12,857 --> 00:26:14,440
وإلا كيف يمكننا أن تذهب عن القيام بذلك؟

800
00:26:14,440 --> 00:26:17,439
دون القذف من العبارات الطنانة أو فرز
من الأجوبة التي أضحت معروفة،

801
00:26:17,439 --> 00:26:19,689
فقط بشكل حدسي، ماذا يمكن أن نفعل؟

802
00:26:19,689 --> 00:26:21,635
>> الحضور: (غير مسموع).

803
00:26:21,635 --> 00:26:22,510
DAVID J. مالان: نعم.

804
00:26:22,510 --> 00:26:24,620
لذلك هناك بعض الحدس كبيرة هناك.

805
00:26:24,620 --> 00:26:28,020
الأشياء الجيدة يبدو أن يحدث حتى الآن
في علوم الكمبيوتر عندما نقسم

806
00:26:28,020 --> 00:26:30,832
وقهر مشكلة تقسيم
في نصف ونصف ونصف.

807
00:26:30,832 --> 00:26:32,540
وهكذا في الواقع، ونحن
يمكن أن تبدأ في فعل ذلك.

808
00:26:32,540 --> 00:26:35,754
في واقع الأمر، وهذا سوف يكون، ونحن سوف
ترى، واحدة من أفضل الحلول لدينا حتى الان.

809
00:26:35,754 --> 00:26:37,420
ولكن دعونا نعود إلى ذلك قبل فترة طويلة.

810
00:26:37,420 --> 00:26:40,500
في الواقع، ونحن في طريقنا للقيام
في وقت لاحق قليلا هذا الاسبوع.

811
00:26:40,500 --> 00:26:42,180
ماذا يمكن أن نفعل لحل هذا؟

812
00:26:42,180 --> 00:26:44,647
لذلك الجميع هنا في
لكي تبدو عشوائية.

813
00:26:44,647 --> 00:26:45,230
أتعلم؟

814
00:26:45,230 --> 00:26:48,320
بدلا من الذهاب ذهابا وإيابا،
ذهابا وإيابا، ذهابا وإيابا

815
00:26:48,320 --> 00:26:50,624
في كل مرة، وهذا يشعر وكأنه
أنا أفعل الكثير من المشي.

816
00:26:50,624 --> 00:26:52,790
لماذا لا أستطيع مجرد بداية في
في بداية القائمة،

817
00:26:52,790 --> 00:26:54,960
وضعت للتو أربعة حيث تنتمي؟

818
00:26:54,960 --> 00:26:59,680
لذلك اسمحوا لي نفترض للحظة أن
قائمتي هي فقط هذا العنصر الأول.

819
00:26:59,680 --> 00:27:04,937
يتم فرز أربعة في هذه اللحظة في الوقت المناسب،
إذا كان كل ما يهمني هو كل شيء هنا؟

820
00:27:04,937 --> 00:27:06,520
هذا هو نوع من صحيح مسلي، أليس كذلك؟

821
00:27:06,520 --> 00:27:10,000
مثل قائمة تحتوي على رقم واحد، و
يتم فرز هذا العدد أربعة واضح.

822
00:27:10,000 --> 00:27:13,070
>> لذلك اسمحوا لي تنص فقط
التي تم فرزها هذه القائمة.

823
00:27:13,070 --> 00:27:15,090
ولكن الآن لدي بقية من هذه القائمة.

824
00:27:15,090 --> 00:27:17,240
وحتى الآن، واجهت اثنين.

825
00:27:17,240 --> 00:27:21,690
أين اثنين من الواضح
تنتمي فيما يتعلق الأربعة؟

826
00:27:21,690 --> 00:27:22,580
قبل أربعة.

827
00:27:22,580 --> 00:27:23,862
لذلك ماذا يمكنني أن أفعل هنا؟

828
00:27:23,862 --> 00:27:24,820
ما أسمك مرة أخرى؟

829
00:27:24,820 --> 00:27:25,090
>> يوسف: يوسف.

830
00:27:25,090 --> 00:27:26,030
>> DAVID J. مالان: يوسف
إذا كنت قد خطوة إلى الوراء

831
00:27:26,030 --> 00:27:27,790
لمجرد لحظة مع رقمك.

832
00:27:27,790 --> 00:27:31,130
والآن ما الذي يجب القيام به ستيفان هنا؟

833
00:27:31,130 --> 00:27:33,720
دعونا نقل ستيفان أكثر من هنا.

834
00:27:33,720 --> 00:27:35,520
والآن، دعونا جوزيف تأتي في هنا.

835
00:27:35,520 --> 00:27:39,660
والآن، اسمحوا لي أن الادعاء بأن
يتم فرز كل شيء هنا.

836
00:27:39,660 --> 00:27:42,474
لذلك، نتيجة مماثلة، ولكن
مقاربة مختلفة جذريا.

837
00:27:42,474 --> 00:27:44,140
أنا لم ينظر حتى ما هو موجود هناك.

838
00:27:44,140 --> 00:27:46,310
أنا فقط تبقى مع العناصر
كما انهم سلم لي،

839
00:27:46,310 --> 00:27:47,240
والتعامل معهم.

840
00:27:47,240 --> 00:27:48,330
>> وحتى الآن، وأرى رقم ستة.

841
00:27:48,330 --> 00:27:51,110
أين رقم ستة تنتمي؟

842
00:27:51,110 --> 00:27:53,250
لدينا اثنين، أربعة، ستة.

843
00:27:53,250 --> 00:27:54,800
بالضبط أين هي الآن.

844
00:27:54,800 --> 00:27:57,750
لذلك دعونا نترك هذا وحده، والآن
يدعون أن هذا الجزء من القائمة

845
00:27:57,750 --> 00:27:58,772
يتم فرز الآن.

846
00:27:58,772 --> 00:28:01,230
وهكذا، وهذا يشعر الأساس
يختلف في ذلك أنا فقط

847
00:28:01,230 --> 00:28:05,230
تتحرك من خلال قائمة هنا
خطيا، وأنا أبدا مضاعفة الظهر.

848
00:28:05,230 --> 00:28:05,730
نعم.

849
00:28:05,730 --> 00:28:06,230
حسنا.

850
00:28:06,230 --> 00:28:08,190
حتى ثمانية، حيث تنتمي؟

851
00:28:08,190 --> 00:28:08,730
هنا.

852
00:28:08,730 --> 00:28:09,310
الكمال.

853
00:28:09,310 --> 00:28:10,210
وحتى الآن، واحد.

854
00:28:10,210 --> 00:28:10,900
اه اوه.

855
00:28:10,900 --> 00:28:13,010
هذا يبدو وكأنه هو
ستكون مكلفة.

856
00:28:13,010 --> 00:28:15,690
الآن، في الخوارزمية السابقة،
تبادلت أنا مجرد مجموعة من الناس.

857
00:28:15,690 --> 00:28:18,648
لذلك أنا قد وضعت له على طول الطريق في
في البداية، ولكن بعد ذلك انتقل يوسف.

858
00:28:18,648 --> 00:28:21,450
ولكن إذا انتقلت يوسف الآن
ما يحدث أن أكون مخطئا؟

859
00:28:21,450 --> 00:28:24,250
>> الآن، لقد نوعا من undone-- لدي
اتخذت خطوة واحدة إلى الأمام ثم

860
00:28:24,250 --> 00:28:26,300
خطوة واحدة إلى الوراء، لأنه الآن
أن جوزيف تكون خارج الترتيب.

861
00:28:26,300 --> 00:28:26,830
لذلك دعونا نفعل هذا.

862
00:28:26,830 --> 00:28:29,150
اذا كنت قد يستغرق رقم واحد
وخطوة إلى الوراء لمجرد لحظة.

863
00:28:29,150 --> 00:28:30,490
كيف يمكننا put-- ما
كان اسمك مرة أخرى؟

864
00:28:30,490 --> 00:28:31,130
>> عنان: عنان.

865
00:28:31,130 --> 00:28:32,610
>> DAVID J. مالان: عنان في المكان؟

866
00:28:32,610 --> 00:28:36,091
ما يجب أن يحدث مع الاحترام
لاثنين، أربعة، ستة، وثمانية؟

867
00:28:36,091 --> 00:28:37,570
انهم جميعا بحاجة إلى تغيير.

868
00:28:37,570 --> 00:28:42,590
إذا كان الأمر كذلك ثمانية ترغب في التحول
أولا، ثم ستة، ثم أربعة، ثم اثنين.

869
00:28:42,590 --> 00:28:45,380
ثم أنان، إذا كنت
تحب أن تأتي إلى هنا، وحسن.

870
00:28:45,380 --> 00:28:47,760
ولكن هنا، لدينا فقط
نوع من دفع ثمنا

871
00:28:47,760 --> 00:28:49,510
في وجهة نظر مختلفة في الخوارزمية.

872
00:28:49,510 --> 00:28:52,550
في حين أن آخر مرة مع اختيار
نوع، وحتى نوع فقاعة،

873
00:28:52,550 --> 00:28:54,700
أنا أمشي ذهابا و
إيابا، ذهابا وإيابا،

874
00:28:54,700 --> 00:28:58,360
ويضيف بالتأكيد ما يصل
في الوقت الحكمة، ومتدرج حرفيا.

875
00:28:58,360 --> 00:29:00,660
>> الإدراج النوع، في البداية
وهلة، يبدو انها

876
00:29:00,660 --> 00:29:05,150
السوبر أكثر ذكاء، في أنني فقط
جعل بطيئا، التقدم التدريجي،

877
00:29:05,150 --> 00:29:07,120
ولكن أنا لن هذا ذهابا وإيابا.

878
00:29:07,120 --> 00:29:09,410
ولكن اذا كان شخص ما هو في الواقع
من النظام، وإشعار

879
00:29:09,410 --> 00:29:10,840
كل من عمل أنا فقط كان علي القيام به.

880
00:29:10,840 --> 00:29:14,750
واضطررت الى نقل نصف القائمة
فقط لإفساح المجال لعدد واحد.

881
00:29:14,750 --> 00:29:16,790
لذلك هو نفس المبلغ
بعيدا من العمل وبالتالي فإنه

882
00:29:16,790 --> 00:29:18,690
يشعر، مجرد نوع مختلف من العمل.

883
00:29:18,690 --> 00:29:19,370
>> فلنتابع.

884
00:29:19,370 --> 00:29:22,657
حتى الآن نحن نعلم أن الجميع
بين واحد وثمانية يتم فرز.

885
00:29:22,657 --> 00:29:23,740
هنا، لا بد لي رقم ثلاثة.

886
00:29:23,740 --> 00:29:25,864
إذا كنت ترغب في التقاط
رقم ثلاثة، خطوة واحدة الى الوراء.

887
00:29:25,864 --> 00:29:28,260
وماذا يا رفاق تحتاج إلى القيام به؟

888
00:29:28,260 --> 00:29:28,760
نعم.

889
00:29:28,760 --> 00:29:33,070
بحيث واحد آخر، اثنان، ثلاث خطوات.

890
00:29:33,070 --> 00:29:36,010
ثلاث وحدات من الوقت الذي تكلف فقط
لي، لذلك أن ثلاثة يمكن أن يصلح الآن.

891
00:29:36,010 --> 00:29:37,460
وأخيرا، سبعة.

892
00:29:37,460 --> 00:29:39,730
>> دعونا نمضي قدما ولها
كنت تأخذ خطوة إلى الوراء.

893
00:29:39,730 --> 00:29:42,780
هذا لن يؤدي الا الى يكلفنا
وحدة واحدة من الزمن، ولكن هذا موافق.

894
00:29:42,780 --> 00:29:44,170
والآن، والذهاب خمسة ل
يكون قليلا أكثر تكلفة.

895
00:29:44,170 --> 00:29:45,340
إذا كنت ترغب في التراجع.

896
00:29:45,340 --> 00:29:48,380
نحن بحاجة إلى التحرك ثمانية،
وسبعة، وستة.

897
00:29:48,380 --> 00:29:50,749
وبعد ذلك يتم فرز الآن الجميع.

898
00:29:50,749 --> 00:29:52,290
حتى يد كبيرة للمتطوعين لدينا هنا.

899
00:29:52,290 --> 00:29:53,554
شكرا جزيلا.

900
00:29:53,554 --> 00:29:56,220
>> [تصفيق]

901
00:29:56,220 --> 00:29:56,860
>> شكرا لكم جميعا.

902
00:29:56,860 --> 00:29:57,520
شكرا لكم جميعا.

903
00:29:57,520 --> 00:30:02,940
لذلك دعونا نرى الآن كيف
تكلفة كل ذلك كان.

904
00:30:02,940 --> 00:30:06,210
دعونا النظر ربما
أبسط من هذه، نوع فقاعة.

905
00:30:06,210 --> 00:30:09,950
وأنا أقول أبسط، فقط ل
يمكنك حلها فقط عن طريق بشراهة

906
00:30:09,950 --> 00:30:11,660
حل المشكلة البشرى هنا.

907
00:30:11,660 --> 00:30:13,720
حل المشكلة البشرى
هنا، مرارا وتكرارا

908
00:30:13,720 --> 00:30:17,680
ومرة أخرى، وتكرار ما يصل
الأوقات التي تحتاج إلى الواقع.

909
00:30:17,680 --> 00:30:21,050
>> هكذا اتضح أن
مع نوع فقاعة، حسنا،

910
00:30:21,050 --> 00:30:25,820
كم عدد الخطوات التي يجب أن تأخذ على
مرور الأول من أن الخوارزمية؟

911
00:30:25,820 --> 00:30:30,850
أنا قد take-- دعونا see-- واحد،
اثنان، ثلاثة، أربعة، خمسة، ستة، سبعة.

912
00:30:30,850 --> 00:30:32,190
وهناك ثمانية عناصر هنا.

913
00:30:32,190 --> 00:30:35,280
لذلك فمن مثل ن ناقص 1 خطوات ل
الحصول عليها من بداية القائمة

914
00:30:35,280 --> 00:30:36,380
إلى نهاية القائمة.

915
00:30:36,380 --> 00:30:41,350
>> ولكن مع اختيار النوع، أذكر أنني
اختيار العناصر مرارا وتكرارا

916
00:30:41,350 --> 00:30:44,590
ومرة أخرى هذا هو أصغر،
أنا وضعه في المكان،

917
00:30:44,590 --> 00:30:46,616
ولكن بعد ذلك أنا لست
أبحث رائي مرة أخرى.

918
00:30:46,616 --> 00:30:49,490
لذلك اعتقد انها قليلا أكثر وضوحا
ثم أن المرة الأولى، وأنا قد

919
00:30:49,490 --> 00:30:52,680
يجب أن تتخذ جميع الخطوات ن ناقص 1
العثور على أصغر عنصر.

920
00:30:52,680 --> 00:30:55,920
ثم وضعت لهم في المكان، وأنا
طرد كل من كان هنا سابقا.

921
00:30:55,920 --> 00:30:57,500
>> ولكن بعد ذلك لم يكن لديك ل
مواصلة البحث في هذا العنصر،

922
00:30:57,500 --> 00:30:59,040
لأنني أعلم أنها ل
بالفعل أصغر.

923
00:30:59,040 --> 00:31:01,581
وحتى الآن، ويمكنني أن ننظر فقط سبعة
العناصر، ثم ستة عناصر،

924
00:31:01,581 --> 00:31:03,290
ثم خمسة عناصر، ثم أربعة عناصر.

925
00:31:03,290 --> 00:31:06,900
وحتى رياضيا، إذا كان n هو
عدد العناصر أو أرقام

926
00:31:06,900 --> 00:31:11,990
التي بدأنا مع، يمكنك أن تتخيل
أن هذا هو نفس ن ناقص 1،

927
00:31:11,990 --> 00:31:14,250
بالإضافة إلى ن ناقص 2 خطوات،
بالإضافة إلى ن ناقص 3 خطوات،

928
00:31:14,250 --> 00:31:16,780
بالإضافة إلى ن ناقص 4 خطوات، كل
الطريق إلى خطوة واحدة فقط.

929
00:31:16,780 --> 00:31:18,160
وأنا في بلدي الماضي شخص.

930
00:31:18,160 --> 00:31:20,650
>> وإذا كنت أذكر أن الكثير
احصائيات الكتب أو كتب الرياضيات

931
00:31:20,650 --> 00:31:24,730
لديك تلك الصيغ على
غلاف الخلفي أو الأمامي منها،

932
00:31:24,730 --> 00:31:27,690
اتضح أن هذه السلسلة
يمكن التعبير ببساطة أكثر

933
00:31:27,690 --> 00:31:28,857
مرات ن ن ناقص 1 على 2.

934
00:31:28,857 --> 00:31:31,273
وأنها على ما يرام إذا كان هذا لا
في طليعة من عقلك.

935
00:31:31,273 --> 00:31:32,420
ولكن هذا هو الواقع الحقيقي.

936
00:31:32,420 --> 00:31:34,449
هذا هو مجرد وسيلة أبسط من كتابة هذا التقرير.

937
00:31:34,449 --> 00:31:36,240
ثم إذا كنت تعتقد
العودة إلى المدارس الابتدائية،

938
00:31:36,240 --> 00:31:38,698
عند بدء تشغيل فقط بضرب
الامور، وهذا بطبيعة الحال،

939
00:31:38,698 --> 00:31:41,820
هو مجرد ن مربع ناقص ن مقسوما على 2.

940
00:31:41,820 --> 00:31:44,772
كل ما قمت به هو توسيع
التعبيرات هناك.

941
00:31:44,772 --> 00:31:46,730
وذلك دعونا إعادة كتابة هذا
بشكل مختلف قليلا.

942
00:31:46,730 --> 00:31:49,780
وهذا ما ن التربيعية مقسوما على 2 ناقص ن / 2.

943
00:31:49,780 --> 00:31:53,270
>> ذلك مرة أخرى، أنا مجرد نوع من تطبيق
قواعد ببعض العمليات الحسابية هناك.

944
00:31:53,270 --> 00:31:57,140
ولكن لاحظ الآن أن مصطلح أكبر
في هذا التعبير، إذا جاز التعبير،

945
00:31:57,140 --> 00:31:58,540
غير أن ن تربيع.

946
00:31:58,540 --> 00:32:02,910
لذلك نعم، انها ن التربيعية
مقسوما على 2، ناقص ن / 2.

947
00:32:02,910 --> 00:32:05,080
>> ولكن بصفة عامة، إذا كان n هو
ستكون قيمة كبيرة،

948
00:32:05,080 --> 00:32:08,740
انا ذاهب الى الادعاء بأن ن تربيع
سيكون العامل المهيمن.

949
00:32:08,740 --> 00:32:10,490
انها مجرد سيكون
المساهم الأكبر

950
00:32:10,490 --> 00:32:12,877
إلى عدد من الخطوات من ن / 2.

951
00:32:12,877 --> 00:32:13,960
فماذا يعني هذا؟

952
00:32:13,960 --> 00:32:16,795
دعونا نحاول مثال بسيط، حتى
على الرغم من أن الرياضيات يحصل على القليل كبيرة.

953
00:32:16,795 --> 00:32:20,210
>> لذلك افترض كان لدينا 1000000 الناس
على خشبة المسرح، أو 1000000 الأمور

954
00:32:20,210 --> 00:32:21,320
أننا نريد لفرز.

955
00:32:21,320 --> 00:32:23,730
دعونا سد مليون
إلى ذلك بالضبط صيغة

956
00:32:23,730 --> 00:32:27,230
لمعرفة عدد الخطوات التي تتخذها مجموعه
فرز مليون العناصر باستخدام يقول،

957
00:32:27,230 --> 00:32:28,560
اختيار نوع.

958
00:32:28,560 --> 00:32:30,760
>> لذلك سيكون لدينا نفس الصيغة كما كان من قبل.

959
00:32:30,760 --> 00:32:34,120
فما استقاموا لكم فاستقيموا سد مليون، بحيث أحصل
مليون التربيعية مقسوما على 2،

960
00:32:34,120 --> 00:32:35,990
ناقص مليون مقسوما على 2.

961
00:32:35,990 --> 00:32:40,180
إذا فعلت ذلك الرياضيات مقدما
هنا، لدينا 500 مليار

962
00:32:40,180 --> 00:32:47,460
ناقص 500،000، التي
يعطينا 499999500000،

963
00:32:47,460 --> 00:32:49,270
وهي جميلة كبيرة الرتق.

964
00:32:49,270 --> 00:32:54,370
>> في الواقع، إذا ما قورنت الآن
499000000000، 999000000،

965
00:32:54,370 --> 00:33:01,210
500،000 ضد لدينا القيمة الأصلية،
500 مليار، حتى انها لعنة وثيق.

966
00:33:01,210 --> 00:33:06,850
الصحيح؟ ن التربيعية مقسوما على 2 يعطي
us-- أو بالأحرى، ن التربيعية مقسوما على 2

967
00:33:06,850 --> 00:33:08,370
قدم لنا 500 مليار.

968
00:33:08,370 --> 00:33:13,510
هذا الرتق جميلة قريبة
ل499999500000،

969
00:33:13,510 --> 00:33:17,970
وهو ما يعني طرح من 500،000،
أو بصورة أعم، طرح قبالة

970
00:33:17,970 --> 00:33:20,010
ن التربيعية، وليس حقا صفقة كبيرة.

971
00:33:20,010 --> 00:33:22,490
ن تربيع يجعل هذه
تنمو الأرقام بسرعة حقا.

972
00:33:22,490 --> 00:33:25,790
>> الآن، وهذا هو المهم فقط بقدر
ونحن كعلماء الكمبيوتر،

973
00:33:25,790 --> 00:33:29,350
عموما لن تهتم كثيرا
حول الفروق الدقيقة في هذه الصيغ

974
00:33:29,350 --> 00:33:31,400
وبالضبط ما
إجابات دقيقة و.

975
00:33:31,400 --> 00:33:33,390
نحن نهتم ذلك فحسب، وأنت تعرف لماذا؟

976
00:33:33,390 --> 00:33:37,810
في نهاية اليوم، وهذه الصيغة
هو بناء على أمر من ن المربعة.

977
00:33:37,810 --> 00:33:39,350
>> نعم، نحن قسمة 2 في هناك.

978
00:33:39,350 --> 00:33:41,360
نعم، نحن طرح قبالة ن ناقص 2.

979
00:33:41,360 --> 00:33:46,860
ولكن في نهاية المطاف، فإن مصطلح
هذا يؤلمنا حقا ويكلفنا

980
00:33:46,860 --> 00:33:48,995
الكثير من الخطوات هو أن مصطلح مربع.

981
00:33:48,995 --> 00:33:51,370
وماذا في ذلك عالم الكمبيوتر
وتنوي القيام به بشكل عام

982
00:33:51,370 --> 00:33:54,160
وتجاهل كل تلك
شروط أجل الصغيرة،

983
00:33:54,160 --> 00:33:56,900
ومجرد إلقاء نظرة على واحد
تساهم أكثر من غيرها في التكلفة.

984
00:33:56,900 --> 00:34:00,530
>> وهذا هو لطيف، لأننا يمكن
الحديث الآن في أكبر بكثير عمومية

985
00:34:00,530 --> 00:34:02,470
حول الخوارزميات، ويمكن مقارنتها.

986
00:34:02,470 --> 00:34:04,550
والحقيقة أنني
باستخدام هذه O غير المتعمد.

987
00:34:04,550 --> 00:34:06,680
عندما أقول على النظام
من، وأنا على وجه التحديد

988
00:34:06,680 --> 00:34:09,560
في اشارة الى شيء
دعا كبير O. وكبير O

989
00:34:09,560 --> 00:34:14,090
هو تدوين أن الكمبيوتر
عالم يستخدم لوصف

990
00:34:14,090 --> 00:34:16,710
الحد الأعلى على شيء.

991
00:34:16,710 --> 00:34:21,150
>> حتى إذا كنت أقول إن خوارزمية
في O كبير من ن تربيع،

992
00:34:21,150 --> 00:34:23,380
كما اقترحت مجرد
لحظة قبل، وهذا يعني

993
00:34:23,380 --> 00:34:27,710
هذا من حيث تسييرها
الوقت أو كفاءته،

994
00:34:27,710 --> 00:34:30,090
فإنه يأخذ على النظام
ن مربع الخطوات.

995
00:34:30,090 --> 00:34:31,420
ربما أكثر من ذلك، وربما أقل من ذلك.

996
00:34:31,420 --> 00:34:33,435
ولكن هذا بناء على أمر من ن تربيع.

997
00:34:33,435 --> 00:34:34,560
وهذا هو الحد الأعلى.

998
00:34:34,560 --> 00:34:36,530
انها لن تكون
أكثر إيلاما من ذلك.

999
00:34:36,530 --> 00:34:40,800
انها لن تكون ن مكعبة، أو 2
لن، أو شيء أكبر من ذلك بكثير.

1000
00:34:40,800 --> 00:34:43,800
هذا هو الحد الأعلى
على أي ان التكلفة.

1001
00:34:43,800 --> 00:34:46,150
فنظرا لهذا، دعونا
النظر في مجرد أمثلة قليلة.

1002
00:34:46,150 --> 00:34:49,820
وهذا هو مجرد قائمة محدودة
أوقات شائعة جدا تشغيل

1003
00:34:49,820 --> 00:34:52,870
لالخوارزميات التي من المفترض أن تكون
توضيحية لبعض الأشياء التي قمت

1004
00:34:52,870 --> 00:34:53,600
رأينا بالفعل.

1005
00:34:53,600 --> 00:34:58,060
>> هكذا على سبيل المثال، في حالة
اختيار نوع، ما أنا مدعيا هنا

1006
00:34:58,060 --> 00:35:02,250
يشغل هذا النوع اختيار ل
الوقت هو بناء على أمر من ن تربيع.

1007
00:35:02,250 --> 00:35:06,260
في أسوأ الحالات، وانا ذاهب ل
مجموعة كاملة من أرقام عشوائية هنا.

1008
00:35:06,260 --> 00:35:08,600
وكما رأينا رياضيا،
إذا كنت الحفاظ على المشي

1009
00:35:08,600 --> 00:35:11,310
من خلال القائمة، من خلال
قائمة، واختيار بجوار أصغر

1010
00:35:11,310 --> 00:35:14,410
العنصر مرة أخرى ومرة ​​أخرى، إذا أنا
إرسال الواقع أسفل كل الخطوات

1011
00:35:14,410 --> 00:35:18,750
أنا أخذ كما اقترحت formulaically
قبل ذلك، هو بناء على أمر من ن التربيعية

1012
00:35:18,750 --> 00:35:20,370
الخطوات التي أنا أخذ.

1013
00:35:20,370 --> 00:35:24,520
>> واتضح أن فقاعة
نوع ونوع الإدراج

1014
00:35:24,520 --> 00:35:27,370
مثلما هي بطيئة في أسوأ الحالات.

1015
00:35:27,370 --> 00:35:32,040
تنظر، على سبيل المثال، الإدراج النوع،
الخوارزمية الأخيرة جدا تعاملنا مع،

1016
00:35:32,040 --> 00:35:35,500
والتي كان لنا أن ننظر في العنصر،
ثم أدخله حيث تنتمي.

1017
00:35:35,500 --> 00:35:38,720
ثم نظرنا إلى العنصر التالي،
وإدراجها حيث تنتمي.

1018
00:35:38,720 --> 00:35:40,990
>> حتى النظر في أفضل سيناريو ممكن.

1019
00:35:40,990 --> 00:35:45,590
لنفترض أنني قد المتطوعين بلدي يصطف
حرفيا مثل هذا، واحد من خلال ثمانية،

1020
00:35:45,590 --> 00:35:47,440
فرز بالفعل.

1021
00:35:47,440 --> 00:35:51,300
عدد الخطوات هي نوع الإدراج
يجري اتخاذها لفرز ثمانية أشخاص،

1022
00:35:51,300 --> 00:35:55,640
إذا وصولهم على خشبة المسرح
يبحث مثل هذا؟

1023
00:35:55,640 --> 00:35:57,410
>> ثمانية أشخاص فرز بالفعل.

1024
00:35:57,410 --> 00:35:58,760
وأنا أستخدم الإدراج النوع.

1025
00:35:58,760 --> 00:36:02,180
أن آخر من الخوارزميات.

1026
00:36:02,180 --> 00:36:03,640
حسنا، دعونا يعيدون تمثيل بسرعة حقيقية.

1027
00:36:03,640 --> 00:36:05,504
حتى لو كنت تبدأ هنا، أرى واحدة.

1028
00:36:05,504 --> 00:36:06,420
حيث يمكن للمرء تنتمي؟

1029
00:36:06,420 --> 00:36:07,730
وهو ينتمي هنا.

1030
00:36:07,730 --> 00:36:08,330
أرى اثنين.

1031
00:36:08,330 --> 00:36:09,660
أين اثنين تنتمي؟

1032
00:36:09,660 --> 00:36:10,260
هنا.

1033
00:36:10,260 --> 00:36:10,900
أرى أن هناك ثلاثة.

1034
00:36:10,900 --> 00:36:11,920
أين الثلاثة تنتمي؟

1035
00:36:11,920 --> 00:36:12,480
هنا.

1036
00:36:12,480 --> 00:36:13,100
>> أرى الأربعة.

1037
00:36:13,100 --> 00:36:13,600
هنا.

1038
00:36:13,600 --> 00:36:15,660
خمسة، ستة، سبعة، ثمانية.

1039
00:36:15,660 --> 00:36:17,320
ليس هناك سبب لتكرار نفسي.

1040
00:36:17,320 --> 00:36:21,260
وهكذا، كيف خطوات كثيرة
غير أنه من حيث ن؟

1041
00:36:21,260 --> 00:36:23,870
انها بناء على أمر من ن
الخطوات، أليس كذلك؟ ن ناقص 1.

1042
00:36:23,870 --> 00:36:27,567
ولكن أخذت عددا الخطي
من الخطوات، والآن أنا فعلت.

1043
00:36:27,567 --> 00:36:28,900
ولهذا أفضل الأحوال، وإن كان.

1044
00:36:28,900 --> 00:36:29,983
ماذا عن أسوأ الحالات؟

1045
00:36:29,983 --> 00:36:32,730
ما ثمانية كانوا هناك،
وسبعة كانوا هناك،

1046
00:36:32,730 --> 00:36:35,840
وكان واحد واثنين أكثر من هنا، لذلك
أن القائمة تم عكس حقا؟

1047
00:36:35,840 --> 00:36:38,300
>> حسنا، ما يحدث في الواقع
إذا كان هذا هو العدد؟

1048
00:36:38,300 --> 00:36:41,300
ونحن سوف نفعل مجرد بضعة أمثلة.

1049
00:36:41,300 --> 00:36:49,300
ماذا لو، في الواقع، وعدد ثمانية
هنا، ويصيح number--.

1050
00:36:49,300 --> 00:36:52,660

1051
00:36:52,660 --> 00:36:56,430
ولكن ماذا لو، في الواقع، فإن عدد
ثمانية هو كل وسيلة أكثر من هنا،

1052
00:36:56,430 --> 00:36:57,790
وأنا باستخدام الإدراج الفرز؟

1053
00:36:57,790 --> 00:36:58,290
>> حسنا.

1054
00:36:58,290 --> 00:37:00,280
أزعم في هذه اللحظة انها في المكان.

1055
00:37:00,280 --> 00:37:03,152
ولكن الآن، seven-- أين سبعة تذهب؟

1056
00:37:03,152 --> 00:37:04,360
بطبيعة الحال، فإنه يذهب أكثر من هنا.

1057
00:37:04,360 --> 00:37:06,760
لذلك يجب أن تتحرك ثمانية على مكان واحد.

1058
00:37:06,760 --> 00:37:08,554
الآن ستة، أين تذهب؟

1059
00:37:08,554 --> 00:37:09,220
حسنا، كل الحق.

1060
00:37:09,220 --> 00:37:13,150
الآن، لا بد لي من نقل أكثر من ثمانية
مكان، وسبعة على المكان،

1061
00:37:13,150 --> 00:37:14,440
وبعد ذلك صوت نزول المطر بانخفاض ستة.

1062
00:37:14,440 --> 00:37:16,870
>> لذا في المرة الأولى، فإنه التكلفة
لي خطوة واحدة لاصلاح الامور،

1063
00:37:16,870 --> 00:37:18,570
ثم كلفني ذلك خطوتين لإصلاح الأمور.

1064
00:37:18,570 --> 00:37:20,370
عدد الخطوات هو عليه
يجري اتخاذها لإصلاح

1065
00:37:20,370 --> 00:37:22,720
الأشياء لوضع خمسة في المكان المناسب؟

1066
00:37:22,720 --> 00:37:23,340
ثلاثة.

1067
00:37:23,340 --> 00:37:29,520
لأنه الآن لا بد لي من
نقل واحد، اثنان، ثلاثة.

1068
00:37:29,520 --> 00:37:32,430
عدد الخطوات هو الذهاب الى اتخاذ
لوضع أربعة في المكان المناسب؟

1069
00:37:32,430 --> 00:37:36,040
4 + 5، بالإضافة إلى 6، بالإضافة إلى 7.

1070
00:37:36,040 --> 00:37:40,260
>> وحتى انها متطابقة رياضيا ل
ما وصفنا لاختيار نوع.

1071
00:37:40,260 --> 00:37:42,130
لدينا هذه السلسلة
هذا ما المتزايد فقط.

1072
00:37:42,130 --> 00:37:45,650
1 زائد 2 زائد 3 زائد 4،
أو على العكس، 7 زائد 6

1073
00:37:45,650 --> 00:37:52,610
بالإضافة إلى 5 زائد 4 يصل لهذا اليوم
التربيعية الأغراض بناء على أمر من ن.

1074
00:37:52,610 --> 00:37:57,640
>> لذلك اسمحوا لي أيضا أن تنص
فقاعة النوع هو أيضا في ن تربيع.

1075
00:37:57,640 --> 00:38:01,340
لأنه مع فقاعة نوع، كل
مرة أذهب من خلال القائمة،

1076
00:38:01,340 --> 00:38:03,100
أنا أخذ تقريبا كيف العديد من الخطوات؟

1077
00:38:03,100 --> 00:38:06,260
في كل مرة أنا حرفيا
المشي من هناك إلى هناك؟

1078
00:38:06,260 --> 00:38:07,960
تقريبا ن الخطوات.

1079
00:38:07,960 --> 00:38:12,650
ولكن كم مرة قد I
بحاجة للذهاب من خلال القائمة؟

1080
00:38:12,650 --> 00:38:13,920
>> حسنا، تقريبا ن الوقت.

1081
00:38:13,920 --> 00:38:15,680
ربما ن ناقص 1، ولكن تقريبا ن مرات.

1082
00:38:15,680 --> 00:38:16,430
حسنا، لماذا؟

1083
00:38:16,430 --> 00:38:19,560
حسنا، مع فقاعة نوع، إذا
نبدأ مع فقاعة نوع،

1084
00:38:19,560 --> 00:38:23,570
مع قائمة في أسوأ ممكن
الوضع الذي هو مرة أخرى تماما

1085
00:38:23,570 --> 00:38:25,550
الى الوراء، ما الذي سيحدث؟

1086
00:38:25,550 --> 00:38:28,830
ذهبت من خلال القائمة، وعدد
واحد ينتمي كل وسيلة هناك.

1087
00:38:28,830 --> 00:38:33,280
>> ولكن مع فقاعة النوع، إلى أي مدى لا أحد
الانتقال الأول تمريرة بلدي من خلال القائمة؟

1088
00:38:33,280 --> 00:38:36,620
كم عدد البقع انه لا يحصل
أقرب إلى المكان الصحيح؟

1089
00:38:36,620 --> 00:38:37,240
واحد فقط.

1090
00:38:37,240 --> 00:38:40,281
حتى إذا كنت نوع العقل من خلال هذا،
في كل مرة من خلال هذه الخوارزمية،

1091
00:38:40,281 --> 00:38:41,880
أخذ تقريبا ن الخطوات داود.

1092
00:38:41,880 --> 00:38:44,940
ولكن كيف عدة تمريرات
من خلال القائمة عليه

1093
00:38:44,940 --> 00:38:49,060
ذاهب الى اتخاذ لأحد أن فقاعة
إلى اليسار حيث تنتمي؟

1094
00:38:49,060 --> 00:38:51,840
>> وقد حصل على التحرك مثل،
ن المساحات بهذه الطريقة.

1095
00:38:51,840 --> 00:38:57,960
حتى لمجرد القيام فرز القائمة،
لا بد لي من المشي ذهابا وإيابا ن مرات.

1096
00:38:57,960 --> 00:39:01,540
وفي كل مرة، وأنا
أبحث في ن العناصر.

1097
00:39:01,540 --> 00:39:05,410
حتى لا ن ن الأشياء مرات على
ترتيب ن تربيع.

1098
00:39:05,410 --> 00:39:07,220
>> الآن، وسنرى في بعض
من السراويل التي

1099
00:39:07,220 --> 00:39:10,440
هي جزء لا يتجزأ في المشكلة القادمة CS50 ل
مجموعة، نهج آخر في هذه،

1100
00:39:10,440 --> 00:39:13,490
لكنه الآن، دعونا النظر فقط
في بعض الأحيان الأخرى على التوالي،

1101
00:39:13,490 --> 00:39:16,840
خصوصا إذا تأخذ تلك الفرز
قليلا من الوقت لتغرق في.

1102
00:39:16,840 --> 00:39:21,790
ما هو خوارزمية رأيناه بالفعل
أن يأخذ على ترتيب ن الخطوات؟

1103
00:39:21,790 --> 00:39:27,560
>> ما ينبغي أن تتخذ عددا الخطي
من الخطوات التي شهدناها حتى الآن؟

1104
00:39:27,560 --> 00:39:29,350
ما هذا؟

1105
00:39:29,350 --> 00:39:30,480
البحث في دليل الهاتف.

1106
00:39:30,480 --> 00:39:31,390
الخوارزمية الأولى.

1107
00:39:31,390 --> 00:39:31,560
الصحيح؟

1108
00:39:31,560 --> 00:39:33,650
حيث نحن خطيا
البحث عن مايك سميث؟

1109
00:39:33,650 --> 00:39:34,150
في الواقع.

1110
00:39:34,150 --> 00:39:37,180
من أسبوع الصفر، وعندما بدأت
تحويل صفحة واحدة في وقت واحد،

1111
00:39:37,180 --> 00:39:40,095
حتى وقلت أنه كان من نوع
خوارزمية الشعور الخطية،

1112
00:39:40,095 --> 00:39:42,720
وكان لدينا تلك الصورة على
المجلس مع الخط الأحمر على التوالي

1113
00:39:42,720 --> 00:39:44,678
والأصفر على التوالي
الخط، كانت تلك في الواقع

1114
00:39:44,678 --> 00:39:46,810
الخوارزميات التي هي في O كبير من ن.

1115
00:39:46,810 --> 00:39:50,680
>> لأن للعثور على مايك سميث في الهاتف
كتاب صفحات ن، في أسوأ الأحوال،

1116
00:39:50,680 --> 00:39:52,422
قد يأخذني ن الخطوات.

1117
00:39:52,422 --> 00:39:53,630
ماذا عن أخذ الحضور؟

1118
00:39:53,630 --> 00:39:55,790
واحد اثنان ثلاثة اربعة خمسة ستة.

1119
00:39:55,790 --> 00:39:59,420
ما هو وقت تشغيل هذه
خوارزمية لأخذ الحضور؟

1120
00:39:59,420 --> 00:40:03,070
O كبير من ن، لأنه في نظرية I
يجب أن نشير الجميع في الغرفة.

1121
00:40:03,070 --> 00:40:05,861
>> الآن بوصفها جانبا، ماذا عن
الأمثل آخرين من الأسبوع الصفر؟

1122
00:40:05,861 --> 00:40:08,117
اثنين، أربعة، ستة، ثمانية، 10، 12.

1123
00:40:08,117 --> 00:40:10,200
عالم الكمبيوتر سوف
ندرك، انتظر لحظة،

1124
00:40:10,200 --> 00:40:12,320
وهذا بناء على أمر من
تنقسم ن من قبل اثنين من الخطوات.

1125
00:40:12,320 --> 00:40:12,820
الصحيح؟

1126
00:40:12,820 --> 00:40:14,444
لأنني أقوم بعمل شخصين في وقت واحد.

1127
00:40:14,444 --> 00:40:17,015
ولكن ونحن في طريقنا إلى تجاهل
هذه المصطلحات أجل الدنيا،

1128
00:40:17,015 --> 00:40:19,140
ونحن ذاهبون لمجرد
رمي بعيدا القسمة على 2،

1129
00:40:19,140 --> 00:40:21,830
ونقول فقط يا كبير من ن
لذلك خوارزمية كذلك.

1130
00:40:21,830 --> 00:40:22,760
>> مذا عن هذه؟

1131
00:40:22,760 --> 00:40:26,170
سنقوم تخطي بعض من هذه، ولكن ما
وكانت خوارزمية الذي كان سجل من ن؟

1132
00:40:26,170 --> 00:40:29,900
أن أخذت ما يقرب من تسجيل ن الخطوات؟

1133
00:40:29,900 --> 00:40:30,870
وفرق تسد.

1134
00:40:30,870 --> 00:40:31,369
بالضبط.

1135
00:40:31,369 --> 00:40:33,900
كما في المثال دليل الهاتف في
الأسبوع صفر و في وقت سابق اليوم،

1136
00:40:33,900 --> 00:40:36,191
حيث قسمنا المشكلة
مرة أخرى، ومرة ​​أخرى ومرة ​​أخرى.

1137
00:40:36,191 --> 00:40:39,070
تعادلنا على المجلس في الأسبوع
الصفر بمثابة الخط الأخضر المنحني،

1138
00:40:39,070 --> 00:40:41,460
وقال لنا أنه كان في ذلك اليوم
خوارزمية لوغاريتمي.

1139
00:40:41,460 --> 00:40:44,970
>> وبالفعل، فإن عدد من الخطوات التي
يلزم لأداء فرق تسد،

1140
00:40:44,970 --> 00:40:48,610
أو البحث الثنائي كما سنبدأ
الدعوة إليها، كما هو الحال في دفتر الهاتف،

1141
00:40:48,610 --> 00:40:50,680
هو بناء على أمر من السجل والخطوات.

1142
00:40:50,680 --> 00:40:52,470
وهذا هو قليلا من واحد غريب.

1143
00:40:52,470 --> 00:40:54,910
>> ما يأخذ خطوة واحدة،
أو بشكل أكثر تحديدا

1144
00:40:54,910 --> 00:40:56,240
عدد ثابت من الخطوات؟

1145
00:40:56,240 --> 00:40:58,865
ربما حان اثنين، وربما انها الثلاث،
ولكن عالم الكمبيوتر فقط

1146
00:40:58,865 --> 00:41:01,423
يبسط أنها O كبيرا من 1،
بعض عدد ثابت من الخطوات.

1147
00:41:01,423 --> 00:41:04,256
ما هو شيء يمكن أن تفعل ذلك
يأخذ عدد ثابت من الخطوات؟

1148
00:41:04,256 --> 00:41:08,030

1149
00:41:08,030 --> 00:41:10,930
>> ما هو وقت تشغيل التصفيق؟

1150
00:41:10,930 --> 00:41:11,920
وقت ثابت.

1151
00:41:11,920 --> 00:41:12,420
الصحيح؟

1152
00:41:12,420 --> 00:41:15,490
مثل، ما هو وقت تشغيل
فعل أي شيء يأخذ واحد فقط

1153
00:41:15,490 --> 00:41:18,570
العملية، مثل طباعة F مرحبا العالم.

1154
00:41:18,570 --> 00:41:24,110
يمكن القول أن ذلك وقت ثابت،
ما لم أقل حالة الزاوية مع الطباعة F،

1155
00:41:24,110 --> 00:41:28,260
ما قد إدارة الوقت
الطباعة F يكون في الواقع؟

1156
00:41:28,260 --> 00:41:28,790
ولماذا؟

1157
00:41:28,790 --> 00:41:30,550
ما هو ن القياس في هذه الحالة؟

1158
00:41:30,550 --> 00:41:32,251
>> الحضور: (غير مسموع).

1159
00:41:32,251 --> 00:41:33,250
DAVID J. مالان: بالضبط.

1160
00:41:33,250 --> 00:41:34,900
عدد الأحرف
نريد للطباعة.

1161
00:41:34,900 --> 00:41:36,191
لذلك فمن حساسة للسياق ذاته.

1162
00:41:36,191 --> 00:41:39,910
اليوم، لقد تم التركيز كثيرا على
الحروف والأرقام هنا على متن الطائرة.

1163
00:41:39,910 --> 00:41:43,540
ولكن قد يكون أيضا
الأحرف في سلسلة الفعلية.

1164
00:41:43,540 --> 00:41:46,420
هكذا اتضح هناك أخرى
الإجراء الذي سيبدأ مبالين،

1165
00:41:46,420 --> 00:41:48,530
وهذا هو عكس ذلك
من يا كبير، إذا جاز التعبير.

1166
00:41:48,530 --> 00:41:50,120
>> هذا التدوين أوميغا.

1167
00:41:50,120 --> 00:41:53,380
في حين O الكبير يعني ما هو، و
الحد الأعلى في الوقت المحدد الجري؟

1168
00:41:53,380 --> 00:41:55,580
الحد الأقصى، وكم من الوقت
قد يستغرق شيئا؟

1169
00:41:55,580 --> 00:41:59,250
آسف Omega-- هذا يبقي القادمة
up-- هو العكس من ذلك،

1170
00:41:59,250 --> 00:42:02,960
حيث انها الأدنى على
مقدار الوقت شيئا ما قد تتخذ.

1171
00:42:02,960 --> 00:42:10,480
>> هكذا. على سبيل المثال، ما هو خوارزمية
أن تتخذ خطوات دائما مربع ن؟

1172
00:42:10,480 --> 00:42:15,600
حسنا، واحدة من خوارزميات رأيناه
اليوم، في الواقع، قد يكون ذلك أيضا.

1173
00:42:15,600 --> 00:42:16,720
اختيار نوع.

1174
00:42:16,720 --> 00:42:18,270
اختيار هو نوع من الغباء جدا.

1175
00:42:18,270 --> 00:42:21,760
حتى لو كان algorithm-- آسف، حتى
إذا تم فرز مجموعة بالفعل،

1176
00:42:21,760 --> 00:42:24,150
اختيار النوع هو الذهاب الى
الحفاظ على المشي من خلال قائمة

1177
00:42:24,150 --> 00:42:28,907
للتأكد من أنها أصغر
العنصر مرة أخرى ومرة ​​أخرى ومرة ​​أخرى.

1178
00:42:28,907 --> 00:42:31,740
وعلى الرغم من أن البشر في
جمهور يعرفون ذلك، انتظر لحظة،

1179
00:42:31,740 --> 00:42:33,948
مررت بالفعل
أصغر عنصر، الكمبيوتر

1180
00:42:33,948 --> 00:42:37,300
لا يعرف أن حتى يبدو
على طول الطريق من خلال القائمة.

1181
00:42:37,300 --> 00:42:40,240
وبالمثل، فإن الأدنى أن
ويمكن أيضا أن تؤخذ بعين الاعتبار

1182
00:42:40,240 --> 00:42:42,000
قد يكون الزمن الخطي.

1183
00:42:42,000 --> 00:42:48,260
>> كم من الوقت يستغرق ل
عناصر نوع ن في أفضل

1184
00:42:48,260 --> 00:42:52,420
حالة استخدام شيء مثل فقاعة الفرز؟

1185
00:42:52,420 --> 00:42:54,280
لنفترض يتم فرز قائمتك بالفعل.

1186
00:42:54,280 --> 00:42:56,696
قلنا فقاعة نوع يأخذ على
ترتيب ن تربيع الخطوات.

1187
00:42:56,696 --> 00:42:59,640
ولكن ما اذا كان تم فرزها بالفعل؟

1188
00:42:59,640 --> 00:43:02,310
ماذا لو كنت أدرك بعد
مرور واحد من خلال مجموعة

1189
00:43:02,310 --> 00:43:03,540
التي قمت بها لا مقايضة؟

1190
00:43:03,540 --> 00:43:05,970
هل تحتاج إلى الحفاظ على صنع أكثر يمر؟

1191
00:43:05,970 --> 00:43:06,470
>> لا.

1192
00:43:06,470 --> 00:43:10,340
لذلك الأدنى على فقاعة الفرز
قد يقال أن تكون خطية.

1193
00:43:10,340 --> 00:43:11,830
أوميغا ن.

1194
00:43:11,830 --> 00:43:14,450
ويمكننا أن ننظر في
البعض الآخر من هذه كذلك.

1195
00:43:14,450 --> 00:43:17,990
لذلك دعونا نلقي نظرة سريعة
في مجرد التصور هنا

1196
00:43:17,990 --> 00:43:20,790
لنرى كيف يمكن لهذه يميزوا أنفسهم.

1197
00:43:20,790 --> 00:43:24,592
انا ذاهب الى النزول هنا في هذا
الصفحة التي تتوفر على موقع C50، و

1198
00:43:24,592 --> 00:43:27,550
لكنه لن يكون الألم للحصول على العمل،
لأنه يستخدم تقنية تسمى

1199
00:43:27,550 --> 00:43:30,560
تطبيقات جافا، وهو
معتمد بشكل كبير هذه الأيام،

1200
00:43:30,560 --> 00:43:32,730
على الأقل الكروم وبعض الآخرين.

1201
00:43:32,730 --> 00:43:37,070
>> واسمحوا لي أن المضي قدما وتسريع هذا
حتى وشرح ما يحدث.

1202
00:43:37,070 --> 00:43:40,840
وهذا دليل فقاعة
النوع، الخوارزمية الأولى ونحن ننظر في.

1203
00:43:40,840 --> 00:43:43,950
وانها التصور في أن كل
من هذه القضبان تمثل عددا.

1204
00:43:43,950 --> 00:43:45,710
وأكبر شريط،
وأكبر عدد.

1205
00:43:45,710 --> 00:43:47,520
أصغر شريط،
أصغر رقم.

1206
00:43:47,520 --> 00:43:50,353
وماذا يمكن أن ترى بالعين المجردة، حتى
رغم أن هذا يجري بسرعة فائقة،

1207
00:43:50,353 --> 00:43:53,699
غير أن شريط أحمر هو مثلي،
المشي ذهابا وإيابا تحديد المشاكل.

1208
00:43:53,699 --> 00:43:56,740
يمكنك أن ترى أن العناصر أكبر
ومحتدما بالفعل ما يصل إلى الحق،

1209
00:43:56,740 --> 00:43:59,650
والعناصر الصغيرة
السبب تظهر على السطح إلى اليسار.

1210
00:43:59,650 --> 00:44:01,870
وإلى هنا، واذا كنا
ننظر في الواقع عن كثب،

1211
00:44:01,870 --> 00:44:04,330
نستطيع أن نعول الواقع
عدد من المقارنات ومقايضة

1212
00:44:04,330 --> 00:44:05,350
التي تبذل.

1213
00:44:05,350 --> 00:44:07,360
>> ولكن بدلا من ذلك، دعونا ننظر
في الخوارزمية الثانية

1214
00:44:07,360 --> 00:44:11,240
ونحن ننظر في وقت سابق مع دينا
المتطوعين، واختيار نوع.

1215
00:44:11,240 --> 00:44:13,500
بصريا، لديها
تأثير مختلف جدا.

1216
00:44:13,500 --> 00:44:16,820
لكنه، مرة أخرى، بديهية جدا، في
أن نبقي اختيار بجوار أصغر

1217
00:44:16,820 --> 00:44:18,660
عنصر، وحصلنا على الحظ قليلا.

1218
00:44:18,660 --> 00:44:20,110
ورأى أن الأساس أسرع.

1219
00:44:20,110 --> 00:44:22,840
ولكن إذا هربنا هذا مرارا وتكرارا
ومرة أخرى مع الكثير من المدخلات،

1220
00:44:22,840 --> 00:44:26,680
كنا نرى أنه من الواقع
لا يزال في O كبير من ن المربعة.

1221
00:44:26,680 --> 00:44:29,920
>> دعونا نفعل واحد آخر واحد
هنا، الإدراج النوع،

1222
00:44:29,920 --> 00:44:33,180
التي كانت الخوارزمية الثالثة
ونحن ننظر في واستدعاء

1223
00:44:33,180 --> 00:44:36,700
أن هذا واحد يتعامل مع
العناصر كما أنه واجه لهم،

1224
00:44:36,700 --> 00:44:39,290
ولكن بعد ذلك ربما التحولات
الأمور لجعل غرفة،

1225
00:44:39,290 --> 00:44:41,660
إدراج العناصر التي تنتمي إليها.

1226
00:44:41,660 --> 00:44:45,330
>> وهذا ينتهي جدا حتى إعطاء
النتيجة النهائية. الآن كل ثلاثة من هذه

1227
00:44:45,330 --> 00:44:46,490
شعر سريعة جدا.

1228
00:44:46,490 --> 00:44:48,740
وبالفعل، ركضت لهم
في مقطع جيدة.

1229
00:44:48,740 --> 00:44:52,510
لكن في الأساس، انهم جميعا
فظيع جدا، أن نكون صادقين.

1230
00:44:52,510 --> 00:44:56,960
الآن كل هذه الخوارزميات وبالتالي
التي تعمل في O كبير من ن تربيع

1231
00:44:56,960 --> 00:44:59,270
تأخذ قدرا كبيرا من
الوقت لتشغيل في نهاية المطاف.

1232
00:44:59,270 --> 00:45:01,920
>> وبالفعل، يمكننا أن نرى
ويشعر هذا أخيرا

1233
00:45:01,920 --> 00:45:04,090
إذا كنت سحب ما يصل هذا العرض الثالث والأخير.

1234
00:45:04,090 --> 00:45:05,840
هذا هو آخر
تصور ما يجري

1235
00:45:05,840 --> 00:45:08,500
لإظهار فقاعة فرز على اليسار،
نوع التحديد في الوسط

1236
00:45:08,500 --> 00:45:13,410
وشيء، باعتبارها واحدة من لدينا
ومن ناحية تثير اقترحت في وقت سابق،

1237
00:45:13,410 --> 00:45:15,020
دمج النوع على اليمين.

1238
00:45:15,020 --> 00:45:16,937
A فرق تسد
استراتيجية على اليمين.

1239
00:45:16,937 --> 00:45:19,520
وهذا هو، في الواقع، ما نحن
سوف ننظر في يوم الاربعاء.

1240
00:45:19,520 --> 00:45:21,990
ولكن لندع الوقت هذه بالتوازي.

1241
00:45:21,990 --> 00:45:26,765
انها تقريبا نفس العدد من
العناصر، كل يعمل في نفس الوقت.

1242
00:45:26,765 --> 00:45:30,940

1243
00:45:30,940 --> 00:45:34,440
فقاعة نوع مقابل اختيار
نوع مقابل دمج النوع.

1244
00:45:34,440 --> 00:45:36,760
>> الآن، انهم جميعا تشغيل
من الناحية النظرية في نفس الوقت.

1245
00:45:36,760 --> 00:45:39,830
هو وحدة المعالجة المركزية على التوالي في
بنفس السرعة، ولكنك

1246
00:45:39,830 --> 00:45:44,014
يمكن أن نرى كيف مملة هذا هو
بسرعة جدا سوف تصبح،

1247
00:45:44,014 --> 00:45:45,930
ومدى سرعة عندما
نحن حقن قليلا من أسبوع

1248
00:45:45,930 --> 00:45:49,330
خوارزميات الصفر ويمكن
نحن تسريع الامور.

1249
00:45:49,330 --> 00:45:51,760
>> والآن دعونا نقارن
هذه في شكل آخر واحد.

1250
00:45:51,760 --> 00:45:55,710
انا ذاهب الى المضي قدما
إلى موقع الويب CS50، حيث

1251
00:45:55,710 --> 00:45:59,020
لدينا هذا الرابط النهائي لهذا اليوم،
حيث شخص ما على شبكة الإنترنت

1252
00:45:59,020 --> 00:46:03,960
يرجى وضع معا شريط فيديو
يلتقط ما الفرز مختلفة

1253
00:46:03,960 --> 00:46:07,510
خوارزميات الصوت مثل.

1254
00:46:07,510 --> 00:46:09,577
هذا هو الإدراج النوع.

1255
00:46:09,577 --> 00:46:12,072
>> [تنبيه]

1256
00:46:12,072 --> 00:46:13,070

1257
00:46:13,070 --> 00:46:16,850
>> حيث كنت التقدم بطلب تردد
استنادا إلى ارتفاع شريط شريط.

1258
00:46:16,850 --> 00:46:19,826
هذا هو فقاعة النوع.

1259
00:46:19,826 --> 00:46:21,822
>> [تنبيه مشوه]

1260
00:46:21,822 --> 00:46:33,299

1261
00:46:33,299 --> 00:46:45,774
>> الخروج المقبل is-- القادمة
يصل المقبل الفرز اختيار is--،

1262
00:46:45,774 --> 00:46:48,820
حيث مرة أخرى، ونحن اختيار
أصغر عنصر المقبل،

1263
00:46:48,820 --> 00:46:51,820
ويمكننا أن نرى ذلك تزايد
من اليسار الى اليمين.

1264
00:46:51,820 --> 00:47:01,120

1265
00:47:01,120 --> 00:47:04,000
>> دمج النوع، بعيدا الفائز لدينا بذلك اليوم.

1266
00:47:04,000 --> 00:47:09,659

1267
00:47:09,659 --> 00:47:12,450
لاحظ كيف انها تقسيم الأشياء
إلى (غير مسموع) نصف وأرباع.

1268
00:47:12,450 --> 00:47:17,510

1269
00:47:17,510 --> 00:47:21,660
نوع غنوم، التي لدينا لا
تحدث عن ويخلق بصريا

1270
00:47:21,660 --> 00:47:24,450
وaudally قليلا من
شكل مختلف والصوت.

1271
00:47:24,450 --> 00:47:27,060

1272
00:47:27,060 --> 00:47:30,160
ذهابا وإيابا،
تنظيف الامور.

1273
00:47:30,160 --> 00:47:32,230
كما تحقق heapsort
على موقع الويب هذا الرجل.

1274
00:47:32,230 --> 00:47:36,100

1275
00:47:36,100 --> 00:47:36,810
>> وهذا كل شيء.

1276
00:47:36,810 --> 00:47:38,210
سوف نرى لك في المرة القادمة.

1277
00:47:38,210 --> 00:47:42,647

1278
00:47:42,647 --> 00:47:48,334
>> [الرنين AND MUSIC]

1279
00:47:48,334 --> 00:50:24,839