1
00:00:00,000 --> 00:00:04,419
>> [عزف الموسيقى]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG لويد: OK، ولذلك فإن دمج
النوع هو بعد خوارزمية أخرى

4
00:00:08,460 --> 00:00:11,200
التي يمكننا استخدامها لفرز
عناصر صفيف.

5
00:00:11,200 --> 00:00:14,480
ولكن كما سنرى، انها حصلت على
الفرق الأساسي جدا

6
00:00:14,480 --> 00:00:17,850
من اختيار نوع، فقاعة
النوع، والإدراج الفرز

7
00:00:17,850 --> 00:00:20,280
التي تجعل حقا ذكي جدا.

8
00:00:20,280 --> 00:00:24,290
>> الفكرة الأساسية وراء دمج
النوع غير لفرز صفائف أصغر

9
00:00:24,290 --> 00:00:27,430
ثم تجمع تلك المصفوفات
معا، أو دمج them--

10
00:00:27,430 --> 00:00:31,440
وبالتالي name-- من أجل فرزها.

11
00:00:31,440 --> 00:00:34,230
الطريقة التي دمج النوع الذي
هذا هو من خلال الاستفادة من أداة

12
00:00:34,230 --> 00:00:37,290
دعا العودية، وهو ما
ونحن في طريقنا إلى أن نتحدث عن وقت قريب،

13
00:00:37,290 --> 00:00:39,720
لكننا لم نتحدث في الحقيقة عن بعد.

14
00:00:39,720 --> 00:00:43,010
>> وهنا الفكرة الأساسية وراء دمج النوع.

15
00:00:43,010 --> 00:00:46,320
فرز النصف الأيسر من المصفوفة،
على افتراض ن أكبر من 1.

16
00:00:46,320 --> 00:00:49,980
وما أعنيه عندما أقول
على افتراض ن أكبر من 1 هو،

17
00:00:49,980 --> 00:00:53,970
وأعتقد أننا يمكن أن نتفق أنه إذا كان مجموعة
يتكون فقط من عنصر واحد،

18
00:00:53,970 --> 00:00:54,680
لقد فرزها.

19
00:00:54,680 --> 00:00:56,560
نحن لسنا بحاجة فعلا
لفعل أي شيء لها.

20
00:00:56,560 --> 00:00:58,059
يمكن أن نعلن فقط ليتم فرزها.

21
00:00:58,059 --> 00:01:00,110
انها ليست سوى عنصر واحد.

22
00:01:00,110 --> 00:01:03,610
>> وبالتالي فإن شبة الكود، مرة أخرى، هو
فرز النصف الأيسر من المصفوفة،

23
00:01:03,610 --> 00:01:08,590
ثم فرز النصف الأيمن للمجموعة،
ثم دمج شطري معا.

24
00:01:08,590 --> 00:01:11,040
الآن، وبالفعل قد يكون
التفكير، انها نوع من مجرد

25
00:01:11,040 --> 00:01:14,080
يبدو أنك تأجيل the--
كنت في الواقع لا تفعل أي شيء.

26
00:01:14,080 --> 00:01:16,330
تقوله فرز اليسار
نصف فرز النصف الأيمن،

27
00:01:16,330 --> 00:01:19,335
ولكن كنت لا أقول
لي كيف كنت أفعل ذلك.

28
00:01:19,335 --> 00:01:22,220
>> ولكن تذكر أنه ما دامت
مجموعة هو عنصر واحد،

29
00:01:22,220 --> 00:01:23,705
يمكن أن نعلن أنه تم فرزها.

30
00:01:23,705 --> 00:01:25,330
وبعد ذلك يمكننا مجرد الجمع بينهما معا.

31
00:01:25,330 --> 00:01:27,788
وهذا هو الواقع
الفكرة الأساسية وراء دمج النوع،

32
00:01:27,788 --> 00:01:31,150
هو كسرها نزولا بحيث
المصفوفات الخاصة بك من حجم واحد.

33
00:01:31,150 --> 00:01:33,430
ثم إعادة بناء من هناك.

34
00:01:33,430 --> 00:01:35,910
>> دمج النوع هو بالتأكيد
خوارزمية معقدة.

35
00:01:35,910 --> 00:01:38,210
وانها أيضا قليلا
تعقيدا لتصور.

36
00:01:38,210 --> 00:01:41,870
لذلك نأمل، تصور أنني
لدينا هنا سوف تساعدك على متابعة طول.

37
00:01:41,870 --> 00:01:45,640
وسأحاول قصارى جهدي ليروي أشياء
والمضي قدما من خلال هذا أكثر قليلا

38
00:01:45,640 --> 00:01:49,180
أبطأ من تلك الأخرى
فقط نأمل في الحصول على رأسك

39
00:01:49,180 --> 00:01:51,800
حول الأفكار وراء دمج النوع.

40
00:01:51,800 --> 00:01:54,680
>> لذلك لدينا نفس مجموعة باسم
أخرى الفرز الفيديو خوارزمية

41
00:01:54,680 --> 00:01:57,120
إذا كنت قد رأيت them--
مجموعة ستة العنصر.

42
00:01:57,120 --> 00:02:02,110
ورمز شبة الكود لدينا هنا هو نوع
النصف الأيسر، فرز النصف الأيمن،

43
00:02:02,110 --> 00:02:03,890
دمج شطري معا.

44
00:02:03,890 --> 00:02:09,770
لذلك دعونا نلقي هذا الطوب الأحمر الداكن جدا
مجموعة وفرز نصف تبقى منها.

45
00:02:09,770 --> 00:02:13,380
>> حتى في الوقت الحاضر، ونحن في طريقنا
تجاهل الأشياء على اليمين.

46
00:02:13,380 --> 00:02:15,740
انها هناك، ولكن نحن
ليس في هذه الخطوة حتى الان.

47
00:02:15,740 --> 00:02:18,220
نحن لسنا في فرز
النصف الأيمن من مجموعة.

48
00:02:18,220 --> 00:02:21,037
نحن في نوع اليسار
نصف المصفوفة.

49
00:02:21,037 --> 00:02:22,870
وفقط من أجل
من كونها أكثر قليلا

50
00:02:22,870 --> 00:02:26,480
واضح، حتى أتمكن من الرجوع
لماذا نحن على خطوة،

51
00:02:26,480 --> 00:02:29,800
انا ذاهب للتبديل
لون من هذه المجموعة إلى اللون البرتقالي.

52
00:02:29,800 --> 00:02:33,190
الآن، ونحن ما زلنا نتحدث عن
نفس النصف الأيسر من المجموعة الأصلية.

53
00:02:33,190 --> 00:02:38,520
ولكن أنا على أمل أن تكون قادرة على
الرجوع إلى الألوان من مختلف الأصناف،

54
00:02:38,520 --> 00:02:40,900
انها سوف جعلها أكثر قليلا
من الواضح ما الذي يحدث هنا.

55
00:02:40,900 --> 00:02:43,270
>> حسنا، الآن لدينا
ثلاثة مجموعة العنصر.

56
00:02:43,270 --> 00:02:46,420
كيف يمكننا فرز النصف الأيسر من هذا
مجموعة، التي لا تزال هذه الخطوة؟

57
00:02:46,420 --> 00:02:49,400
نحاول فرز اليسار
نصف array-- الأحمر الطوب

58
00:02:49,400 --> 00:02:52,410
النصف الأيسر منها
لقد الملونة الآن البرتقال.

59
00:02:52,410 --> 00:02:54,840
>> حسنا، يمكننا أن نبذل و
كرر هذه العملية مرة أخرى.

60
00:02:54,840 --> 00:02:56,756
لذلك نحن ما زلنا في
وسط محاولة لفرز

61
00:02:56,756 --> 00:02:58,700
النصف الأيسر من مجموعة كاملة.

62
00:02:58,700 --> 00:03:00,450
النصف الأيسر من
مجموعة، انا فقط

63
00:03:00,450 --> 00:03:03,910
لاتخاذ قرار تعسفي إلى أن النصف الأيسر
سيكون أصغر من النصف الأيمن،

64
00:03:03,910 --> 00:03:06,550
لأن هذا يحدث ل
تتكون من ثلاثة عناصر.

65
00:03:06,550 --> 00:03:11,260
>> وحتى وأنا ذاهب إلى القول بأن
النصف الأيسر من النصف الأيسر المصفوفة

66
00:03:11,260 --> 00:03:14,050
هو مجرد عنصر خمسة.

67
00:03:14,050 --> 00:03:18,360
خمسة، لكونها عنصر واحد
مجموعة، ونحن نعرف كيفية ترتيب هذا الامر.

68
00:03:18,360 --> 00:03:21,615
وهكذا يتم فرز الخمسة.

69
00:03:21,615 --> 00:03:22,990
نحن ذاهبون لمجرد أن تعلن.

70
00:03:22,990 --> 00:03:24,890
انها مجموعة عنصر واحد.

71
00:03:24,890 --> 00:03:29,015
>> لذلك قمنا فرز الآن
النصف الأيسر من نصفها- اليسار

72
00:03:29,015 --> 00:03:33,190
أو بالأحرى، لقد فرز
النصف الأيسر من البرتقال.

73
00:03:33,190 --> 00:03:37,970
وحتى الآن، من أجل تزال كاملة
نصف مجموعة شاملة الأيسر،

74
00:03:37,970 --> 00:03:43,481
نحن بحاجة إلى فرز النصف الأيمن
من البرتقال، أو هذه الأشياء.

75
00:03:43,481 --> 00:03:44,230
كيف لنا أن نفعل ذلك؟

76
00:03:44,230 --> 00:03:45,930
حسنا، لدينا مجموعة واثنين من العنصر.

77
00:03:45,930 --> 00:03:50,470
حتى نتمكن من فرز نصف اليسار
في المصفوفة، التي هي سنتان.

78
00:03:50,470 --> 00:03:52,090
الثاني هو عنصر واحد.

79
00:03:52,090 --> 00:03:55,890
حتى انها مرتبة بشكل افتراضي.
وبعد ذلك يمكننا فرز النصف الأيمن

80
00:03:55,890 --> 00:03:58,530
ذلك جزء من مجموعة واحدة.

81
00:03:58,530 --> 00:04:00,210
هذا النوع من افتراضيا.

82
00:04:00,210 --> 00:04:03,610
>> هذا هو الآن أول مرة
لقد وصلت خطوة الدمج.

83
00:04:03,610 --> 00:04:06,135
أكملنا، على الرغم من
نحن الآن نوع من تداخل down--

84
00:04:06,135 --> 00:04:08,420
وهذا النوع من صعبة
الشيء مع العودية هو،

85
00:04:08,420 --> 00:04:10,930
تحتاج للحفاظ على
يتوجه نحو ما نحن فيه.

86
00:04:10,930 --> 00:04:15,560
لذلك قمنا النوع من اليسار
نصف الجزء البرتقالي.

87
00:04:15,560 --> 00:04:21,280
>> والآن، نحن في منتصف الفرز
النصف الأيمن من الجزء البرتقالي.

88
00:04:21,280 --> 00:04:25,320
وفي هذه العملية، ونحن
الآن على وشك أن يكون على هذه الخطوة،

89
00:04:25,320 --> 00:04:27,850
دمج شطري معا.

90
00:04:27,850 --> 00:04:31,700
عندما ننظر إلى نصفين اثنين
من مجموعة، ونحن نرى اثنين واحد.

91
00:04:31,700 --> 00:04:33,880
العنصر الذي هو أصغر؟

92
00:04:33,880 --> 00:04:35,160
واحدة.

93
00:04:35,160 --> 00:04:36,760
>> ثم العنصر الذي هو أصغر؟

94
00:04:36,760 --> 00:04:38,300
حسنا، انها اثنين أو لا شيء.

95
00:04:38,300 --> 00:04:39,910
لذلك فمن اثنين.

96
00:04:39,910 --> 00:04:43,690
وحتى الآن، فقط لتأطير مرة أخرى
أين نحن في السياق،

97
00:04:43,690 --> 00:04:48,230
لقد فرز
النصف الأيسر من البرتقال

98
00:04:48,230 --> 00:04:49,886
والنصف الأيمن من الأصل.

99
00:04:49,886 --> 00:04:52,510
وأنا أعلم أنني قمت بتغيير الألوان
مرة أخرى، ولكن هذا ما كنا عليه.

100
00:04:52,510 --> 00:04:54,676
والسبب في أنني فعلت هذا
لأن هذه العملية

101
00:04:54,676 --> 00:04:57,870
الذهاب الى الاستمرار، بالتكرار أسفل.

102
00:04:57,870 --> 00:05:00,500
لقد فرز اليسار
نصف من البرتقال السابق

103
00:05:00,500 --> 00:05:02,590
والنصف الأيمن من البرتقال السابق.

104
00:05:02,590 --> 00:05:05,620
>> الآن، نحن بحاجة إلى دمج تلك
نصفين معا أيضا.

105
00:05:05,620 --> 00:05:07,730
هذا هو خطوة نحن على.

106
00:05:07,730 --> 00:05:11,440
لذلك نحن نعتبر كل من
العناصر التي هي الآن الأخضر،

107
00:05:11,440 --> 00:05:12,972
النصف الأيسر من مجموعة الأصلي.

108
00:05:12,972 --> 00:05:14,680
ونحن دمج تلك
باستخدام نفس العملية

109
00:05:14,680 --> 00:05:18,660
فعلنا لدمج اثنين
ومنذ واحد فقط لحظة.

110
00:05:18,660 --> 00:05:23,080
>> النصف الأيسر، أصغر
عنصر في النصف الأيسر هو خمسة.

111
00:05:23,080 --> 00:05:25,620
أصغر عنصر في
النصف الأيمن هو واحد.

112
00:05:25,620 --> 00:05:27,370
أي من هؤلاء هو أصغر؟

113
00:05:27,370 --> 00:05:29,260
واحدة.

114
00:05:29,260 --> 00:05:32,250
>> أصغر عنصر في
النصف الأيسر هو خمسة.

115
00:05:32,250 --> 00:05:35,540
أصغر عنصر في
النصف الأيمن هو اثنين.

116
00:05:35,540 --> 00:05:36,970
ما هو أصغر؟

117
00:05:36,970 --> 00:05:38,160
اثنين.

118
00:05:38,160 --> 00:05:41,540
ثم أخيرا خمسة و
لا شيء، نستطيع أن نقول خمسة.

119
00:05:41,540 --> 00:05:43,935
>> OK، الصورة الكبيرة لذلك، دعونا
أخذ قسط من الراحة لثانية واحدة

120
00:05:43,935 --> 00:05:46,080
ومعرفة ما نحن فيه.

121
00:05:46,080 --> 00:05:48,580
إذا بدأنا من
في البداية، ونحن

122
00:05:48,580 --> 00:05:51,640
أكملت الآن ل
مجموعة شاملة فقط

123
00:05:51,640 --> 00:05:53,810
خطوة واحدة من قانون شبة الكود هنا.

124
00:05:53,810 --> 00:05:56,645
لقد فرز
النصف الأيسر من مجموعة.

125
00:05:56,645 --> 00:05:59,490
>> أذكر أن الأصل
وكان ترتيب الخمسة، اثنان، واحد.

126
00:05:59,490 --> 00:06:02,570
عن طريق الذهاب من خلال هذه العملية
وتعشش أسفل وتكرار،

127
00:06:02,570 --> 00:06:05,990
الاستمرار في كسر المشكلة
إلى أجزاء أصغر وأصغر،

128
00:06:05,990 --> 00:06:09,670
أكملنا الآن
خطوة واحدة من شبة الكود

129
00:06:09,670 --> 00:06:13,940
لمجموعة انطلاق بأكملها.

130
00:06:13,940 --> 00:06:16,670
لقد تم فرزها النصف الأيسر.

131
00:06:16,670 --> 00:06:18,670
>> حتى الآن دعونا تجميد هناك.

132
00:06:18,670 --> 00:06:23,087
والآن دعونا فرز الحق
نصف المصفوفة الأصلية.

133
00:06:23,087 --> 00:06:25,670
ونحن في طريقنا للقيام بذلك من قبل
يمر نفس متكررة

134
00:06:25,670 --> 00:06:30,630
عملية كسر الأشياء أسفل
ومن ثم دمجها معا.

135
00:06:30,630 --> 00:06:34,290
>> حتى النصف الأيسر من
أحمر، أو النصف الأيسر

136
00:06:34,290 --> 00:06:38,830
من النصف الأيمن من الأصل
مجموعة، انا ذاهب الى قوله هو ثلاثة.

137
00:06:38,830 --> 00:06:40,312
مرة أخرى، أنا أكون متسقا هنا.

138
00:06:40,312 --> 00:06:42,020
إذا كان لديك الغريب
عدد من العناصر، فإنه

139
00:06:42,020 --> 00:06:44,478
لا يهم حقا ما إذا كان
عليك ان تجعل اليسار واحد أصغر

140
00:06:44,478 --> 00:06:45,620
أو الحق واحد أصغر.

141
00:06:45,620 --> 00:06:49,230
>> ما يهم هو أن كلما
واجهت هذه المشكلة في إجراء

142
00:06:49,230 --> 00:06:51,422
دمج، تحتاج إلى أن تكون متسقة.

143
00:06:51,422 --> 00:06:53,505
تحتاج إما دائما ل
جعل الجانب الأيسر أصغر

144
00:06:53,505 --> 00:06:55,421
أو تحتاج دائما لجعل
الجانب الأيمن أصغر.

145
00:06:55,421 --> 00:06:57,720
هنا، وأنا اخترت دائما
جعل الجانب الأيسر أصغر

146
00:06:57,720 --> 00:07:04,380
عندما بلدي مجموعة، أو بلدي
مجموعة فرعية، هي من حجم الغريب.

147
00:07:04,380 --> 00:07:07,420
>> الثلاثة هو عنصر واحد،
وهكذا يتم فرز عليه.

148
00:07:07,420 --> 00:07:10,860
لقد الاستدانة هذا الافتراض
في جميع أنحاء عمليتنا كامل حتى الآن.

149
00:07:10,860 --> 00:07:15,020
حتى الآن دعونا فرز الحق
نصف النصف الأيمن،

150
00:07:15,020 --> 00:07:18,210
أو النصف الأيمن من الحمراء.

151
00:07:18,210 --> 00:07:20,390
>> مرة أخرى، نحن بحاجة إلى هذا الانقسام إلى أسفل.

152
00:07:20,390 --> 00:07:21,910
هذه ليست مجموعة عنصر واحد.

153
00:07:21,910 --> 00:07:23,970
ونحن لا يمكن أن نعلن ذلك فرزها.

154
00:07:23,970 --> 00:07:27,060
وأول ذلك، ونحن في طريقنا
لفرز النصف الأيسر.

155
00:07:27,060 --> 00:07:31,620
>> النصف الأيسر هو عنصر واحد،
لذلك نوع من افتراضيا.

156
00:07:31,620 --> 00:07:34,840
ثم نحن في طريقنا لفرز الحق
نصف، وهو عنصر واحد.

157
00:07:34,840 --> 00:07:41,250
لقد تم فرزها بشكل افتراضي. والان،
يمكننا دمج هذين معا.

158
00:07:41,250 --> 00:07:45,820
أربعة أصغر، و
ثم ستة هو أصغر.

159
00:07:45,820 --> 00:07:48,870
>> مرة أخرى، ماذا فعلنا في هذه المرحلة؟

160
00:07:48,870 --> 00:07:52,512
لقد فرز اليسار
نصف النصف الأيمن.

161
00:07:52,512 --> 00:07:54,720
أو العودة إلى الأصل
الألوان التي كانت هناك،

162
00:07:54,720 --> 00:07:57,875
لقد فرز اليسار
نصف الحمراء أكثر ليونة.

163
00:07:57,875 --> 00:08:00,416
كان في الأصل لبنة الظلام
الأحمر والآن حان ليونة الأحمر،

164
00:08:00,416 --> 00:08:02,350
أو أنه كان أحمر ليونة.

165
00:08:02,350 --> 00:08:05,145
>> وبعد ذلك قمنا فرز
النصف الأيمن من الحمراء أكثر ليونة.

166
00:08:05,145 --> 00:08:08,270
الآن، حسنا، انهم الأخضر مرة أخرى، فقط
لأننا في طريقنا من خلال عملية.

167
00:08:08,270 --> 00:08:10,720
وعلينا أن نكرر
هذا مرارا وتكرارا.

168
00:08:10,720 --> 00:08:14,695
>> وحتى الآن يمكننا دمج تلك
نصفين معا.

169
00:08:14,695 --> 00:08:15,820
وهذا ما نقوم به هنا.

170
00:08:15,820 --> 00:08:17,653
وبالتالي فإن خط أسود فقط
تنقسم النصف الأيسر

171
00:08:17,653 --> 00:08:19,690
والنصف الأيمن من هذا الجزء النوع.

172
00:08:19,690 --> 00:08:24,310
>> قارنا أصغر قيمة
على الجانب الأيسر من array--

173
00:08:24,310 --> 00:08:26,710
أو عفوا، أصغر
قيمة النصف الأيسر

174
00:08:26,710 --> 00:08:30,790
إلى أصغر قيمة الحق
نصف وتجد أن ثلاثة هي أصغر.

175
00:08:30,790 --> 00:08:32,530
والآن قليلا من التحسين، أليس كذلك؟

176
00:08:32,530 --> 00:08:35,175
هناك في الواقع شيئا
تركت على الجانب الأيسر.

177
00:08:35,175 --> 00:08:37,440
>> لا يوجد شيء المتبقية
على الجانب الأيسر،

178
00:08:37,440 --> 00:08:40,877
حتى نتمكن من كفاءة
فقط move-- يمكن أن نعلن

179
00:08:40,877 --> 00:08:42,960
ما تبقى منه هو في الواقع
فرزها وفقط تك ذلك

180
00:08:42,960 --> 00:08:45,126
على، أنه لا يوجد شيء
آخر لمقارنة ضد.

181
00:08:45,126 --> 00:08:49,140
ونحن نعلم أن الجانب الأيمن
من الجانب الأيمن تم فرزها.

182
00:08:49,140 --> 00:08:52,770
>> حسنا، الآن دعونا مرة أخرى وتجميد
معرفة أين نحن في القصة.

183
00:08:52,770 --> 00:08:56,120
في مجموعة الشاملة،
ما أنجزناه؟

184
00:08:56,120 --> 00:08:58,790
لقد إنجاز فعلا
الخطوات الآن واحدة وخطوتين.

185
00:08:58,790 --> 00:09:03,300
نحن فرز النصف الأيسر، و
نحن فرز النصف الأيمن.

186
00:09:03,300 --> 00:09:08,210
>> وحتى الآن، كل ما تبقى هو بالنسبة لنا
لدمج تلك نصفين اثنين معا.

187
00:09:08,210 --> 00:09:11,670
لذلك نحن نقارن أدنى قيمة
عنصر من كل شوط من مجموعة

188
00:09:11,670 --> 00:09:13,510
بدوره والمضي قدما.

189
00:09:13,510 --> 00:09:16,535
واحد هو أقل من ثلاثة، لذلك يذهب واحد.

190
00:09:16,535 --> 00:09:19,770
>> الثاني هو أقل من ثلاثة، لذلك يذهب اثنين.

191
00:09:19,770 --> 00:09:22,740
ثلاثة أقل من 5، لذلك ثلاثة يذهب.

192
00:09:22,740 --> 00:09:25,820
أربعة أقل من 5، لذلك أربعة يذهب.

193
00:09:25,820 --> 00:09:30,210
ثم خمسة هو أقل من ستة،
وستة هو كل ما تبقى.

194
00:09:30,210 --> 00:09:31,820
>> الآن، وأنا أعلم، وكان ذلك الكثير من الخطوات.

195
00:09:31,820 --> 00:09:33,636
ولقد ترك الكثير
من الذاكرة في أعقاب لدينا.

196
00:09:33,636 --> 00:09:35,260
وهذا ما هي تلك الساحات الرمادية.

197
00:09:35,260 --> 00:09:40,540
وربما شعرت أن أخذت
الكثير أطول من الإدراج النوع، فقاعة

198
00:09:40,540 --> 00:09:42,660
نوع، أو اختيار نوع.

199
00:09:42,660 --> 00:09:45,330
>> ولكن في الواقع، لأن
الكثير من هذه العمليات

200
00:09:45,330 --> 00:09:48,260
ويحدث في الوقت نفسه time--
وهو ما سنقوم مرة أخرى،

201
00:09:48,260 --> 00:09:51,100
الحديث عن عندما نتحدث عن
العودية في المستقبل video--

202
00:09:51,100 --> 00:09:53,799
هذه الخوارزمية في الواقع
ومن الواضح أن الأساس

203
00:09:53,799 --> 00:09:55,590
يختلف عن أي شيء
رأينا من قبل

204
00:09:55,590 --> 00:09:58,820
وإنما هو أيضا بشكل ملحوظ
أكثر فعالية.

205
00:09:58,820 --> 00:09:59,532
>> لماذا هذا؟

206
00:09:59,532 --> 00:10:01,240
حسنا، في أسوأ
سيناريو، لدينا

207
00:10:01,240 --> 00:10:04,830
لتقسيم ن عناصر ما يصل
ومن ثم إعادة تجميع لهم.

208
00:10:04,830 --> 00:10:06,680
ولكن عندما وتتحد
منها، ما نقوم به

209
00:10:06,680 --> 00:10:11,110
يتضاعف الأساس
حجم صفائف أصغر.

210
00:10:11,110 --> 00:10:14,260
لدينا مجموعة من عنصر واحد
صفائف أننا فعال

211
00:10:14,260 --> 00:10:16,290
الجمع بين اثنين من صفائف إلى عنصر.

212
00:10:16,290 --> 00:10:18,590
ثم نأخذ تلك
اثنين من صفائف عنصر

213
00:10:18,590 --> 00:10:21,890
والجمع بينهما معا في
أربعة صفائف عنصر، وهلم جرا،

214
00:10:21,890 --> 00:10:26,130
وهلم جرا، وهلم جرا، حتى نحن
لديهم واحدة مجموعة العنصر n.

215
00:10:26,130 --> 00:10:29,910
>> ولكن كيف العديد من الأضعاف
يستغرق للوصول الى ن؟

216
00:10:29,910 --> 00:10:31,460
فكر في العودة إلى المثال دفتر الهاتف.

217
00:10:31,460 --> 00:10:34,490
كم مرة يجب علينا أن المسيل للدموع
دليل الهاتف في نصف، كم من

218
00:10:34,490 --> 00:10:38,370
مرات هل لدينا لتمزيق دفتر الهاتف
في النصف، وإذا كان حجم دفتر الهاتف

219
00:10:38,370 --> 00:10:39,680
الضعف؟

220
00:10:39,680 --> 00:10:41,960
هناك واحد فقط، أليس كذلك؟

221
00:10:41,960 --> 00:10:45,360
>> لذلك هناك نوعا من
عنصر لوغاريتمي هنا.

222
00:10:45,360 --> 00:10:48,590
ولكننا أيضا لا تزال لديها على الأقل
ننظر في كل من العناصر ن.

223
00:10:48,590 --> 00:10:53,860
حتى في أسوأ سيناريو،
دمج يدير الفرز في ن سجل ن.

224
00:10:53,860 --> 00:10:56,160
علينا أن ننظر في
كل عناصر ن،

225
00:10:56,160 --> 00:11:02,915
وعلينا أن الجمع بينهما
معا في سجل ن مجموعات من الخطوات.

226
00:11:02,915 --> 00:11:05,290
في أحسن الأحوال،
يتم فرز مجموعة تماما.

227
00:11:05,290 --> 00:11:06,300
هذا عظيم.

228
00:11:06,300 --> 00:11:09,980
ولكن استنادا إلى خوارزمية لدينا هنا،
لا يزال لدينا لتقسيم وإعادة تجميع.

229
00:11:09,980 --> 00:11:13,290
على الرغم من أن في هذه الحالة،
إعادة توحيد هو نوع من غير فعالة.

230
00:11:13,290 --> 00:11:14,720
لا حاجة لذلك.

231
00:11:14,720 --> 00:11:17,580
ولكن ما زلنا تمر
العملية برمتها على أي حال.

232
00:11:17,580 --> 00:11:21,290
>> حتى في أفضل الأحوال
وفي أسوأ الحالات،

233
00:11:21,290 --> 00:11:24,970
هذه الخوارزمية يعمل في ن ن سجل الزمن.

234
00:11:24,970 --> 00:11:29,130
دمج النوع هو بالتأكيد اصعب قليلا
من غيرها من خوارزميات الفرز الرئيسية

235
00:11:29,130 --> 00:11:33,470
لقد تحدثنا عن CS50 ولكن
إلى حد كبير أكثر قوة.

236
00:11:33,470 --> 00:11:35,400
>> وحتى إذا وجدت من أي وقت مضى
مناسبة لحاجة إليها

237
00:11:35,400 --> 00:11:38,480
أو لاستخدامها لفرز
مجموعة كبيرة من البيانات، والحصول على

238
00:11:38,480 --> 00:11:41,940
رأسك حول فكرة العودية
ستكون قوية حقا.

239
00:11:41,940 --> 00:11:45,270
وانها تسير لجعل حياتك
برامج حقا أكثر كفاءة

240
00:11:45,270 --> 00:11:48,700
باستخدام دمج النوع مقابل أي شيء آخر.

241
00:11:48,700 --> 00:11:49,640
أنا دوغ ويد.

242
00:11:49,640 --> 00:11:51,970
هذا هو CS50.

243
00:11:51,970 --> 00:11:53,826