1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [دمج فرز]

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

3
00:00:04,000 --> 00:00:07,000
[هذا CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
دعونا نتحدث عن نوع الدمج.

5
00:00:09,000 --> 00:00:14,000
حتى الآن كنت قد رأيت نوع فقاعة، نوع الإدراج، ونوع الاختيار.

6
00:00:14,000 --> 00:00:17,000
على الرغم من أنني سوف نوع من موجة يدي إلى ما أعنيه أفضل،

7
00:00:17,000 --> 00:00:21,000
دمج النوع يؤدي عموما أفضل من أي من هذه الأنواع 3.

8
00:00:22,000 --> 00:00:27,000
>> ولكن قبل الحديث عن نوع الدمج، دعونا نتحدث عن دمج 2 قائمة فرزها.

9
00:00:27,000 --> 00:00:31,000
سوف نطلق عليه عملية اتخاذ 2 قائمة فرزها، مثل هذه،

10
00:00:31,000 --> 00:00:35,000
ووضع قائمة واحدة للخروج منها مصنفة - دمج القوائم.

11
00:00:35,000 --> 00:00:37,750
كيف يمكننا أن نفعل هذا؟

12
00:00:37,750 --> 00:00:41,290
حسنا، فكرة واحدة هي مجرد عصا لائحة واحدة على نهاية قائمة أخرى

13
00:00:41,290 --> 00:00:43,830
ثم فرز القائمة الناتجة.

14
00:00:43,830 --> 00:00:47,220
>> في حين أن هذا يعمل، انها هناك الكثير من العمل لا لزوم لها.

15
00:00:47,220 --> 00:00:49,900
يمكننا القيام بذلك بشكل أسرع من الفرز فقط.

16
00:00:49,900 --> 00:00:54,100
لاحظت أن فكرة واحدة المشكلة تكمن في أخذ كوب فقط من كل قائمة بالتناوب.

17
00:00:54,100 --> 00:00:56,460
في حين أن ذلك قد يبدو أن يعمل في البداية،

18
00:00:56,460 --> 00:01:05,760
فعل ذلك نحن في نهاية المطاف مع 4، 8، 15، 23، 16 - لاحظ أن 16 و 23 هي خارج المكان.

19
00:01:05,760 --> 00:01:09,380
هذا هو لأن 2 العناصر التي يجب أن تظهر على التوالي في القائمة المدمجة

20
00:01:09,380 --> 00:01:11,720
في قائمة الأولية نفسها.

21
00:01:11,720 --> 00:01:14,850
كلا 15 و 16 في القائمة على اليسار.

22
00:01:14,850 --> 00:01:19,810
هو خدعة للاستفادة من حقيقة أن يتم تصنيف بالفعل كلا القائمتين.

23
00:01:19,810 --> 00:01:23,320
هذا يعني أنه إذا نظرنا إلى العناصر الأولى من كلتا القائمتين -

24
00:01:23,320 --> 00:01:29,580
هنا و 4 و 8 - يجب أن يكون واحد منهم أيضا العنصر الأول من القائمة المدمجة.

25
00:01:29,580 --> 00:01:31,620
حسنا، لماذا؟

26
00:01:31,620 --> 00:01:33,520
يتم تصنيف بالفعل كل من هذه القوائم،

27
00:01:33,520 --> 00:01:38,410
ولذا يجب إما 4 أو 8 يكون أصغر عنصر عند الجمع بين القوائم 2.

28
00:01:38,410 --> 00:01:41,770
في هذه الحالة، هو أصغر 4،

29
00:01:41,770 --> 00:01:46,370
حتى نتمكن من إخراج 4 و جعله العنصر الأول من قائمتنا المدمجة.

30
00:01:46,370 --> 00:01:50,710
الآن نحن نواصل دمج ما تبقى من 3 عناصر القائمة الأولى

31
00:01:50,710 --> 00:01:52,920
و 4 عناصر من القائمة الثانية.

32
00:01:52,920 --> 00:01:57,150
>> مرة أخرى، نحن بحاجة فقط للنظر في العنصر الأول من كلتا القائمتين.

33
00:01:57,150 --> 00:02:01,060
يجب أصغر من 2 يكون العنصر الثاني من قائمتنا المدمجة.

34
00:02:01,060 --> 00:02:05,440
هذه المرة، ما بين 8 و 15 أصغر هو 8، وإدراج ذلك نحن أن

35
00:02:05,440 --> 00:02:09,240
باعتبارها العنصر الثاني من قائمتنا فرزها.

36
00:02:09,240 --> 00:02:12,180
يمكننا أن نواصل مقارنة العناصر الأولى من كلتا القائمتين

37
00:02:12,180 --> 00:02:14,420
وإزالة أصغر من 2.

38
00:02:14,420 --> 00:02:19,460
مقارنة 15 و 23 15، وأصغر بحيث لدينا العنصر الثالث.

39
00:02:21,000 --> 00:02:23,910
مقارنة الآن 16 و 23 و 16 هو أصغر.

40
00:02:23,910 --> 00:02:26,820
لذلك هذا هو العنصر الرابع.

41
00:02:26,820 --> 00:02:30,390
>> تلاحظ أن 2 العناصر جاءت من نفس القائمة في صف واحد.

42
00:02:30,390 --> 00:02:34,400
هذا هو السبب في أن قائمة العناصر المدمجة لا يمكن مجرد بديل من القوائم 2.

43
00:02:34,400 --> 00:02:40,020
مقارنة 50 و 23، 23 هو أصغر، لذلك اخترنا ذلك.

44
00:02:40,770 --> 00:02:44,070
ما بين 50 و 42 و 42 هو أصغر.

45
00:02:44,070 --> 00:02:48,290
ما بين 50 و 108، 50 هو أصغر.

46
00:02:48,290 --> 00:02:52,330
وأخيرا، لدينا فقط 108، لذلك يجب أن تذهب في نهاية قائمتنا.

47
00:02:53,750 --> 00:02:56,180
لاحظت أن لدينا لطيفة، قائمة تم فرزها.

48
00:02:56,180 --> 00:02:59,040
في كل مرة نقوم بالمقارنة أول 2 العناصر من القوائم 2

49
00:02:59,040 --> 00:03:02,730
كنا قادرين على تحديد العنصر التالي في قائمة مدمجة.

50
00:03:02,730 --> 00:03:08,070
هذا يعني أنه إذا كان يحتوي على أرقام القائمة النهائية n، حيث n هو هنا 8،

51
00:03:08,070 --> 00:03:12,610
ثم نحن بحاجة في معظم المقارنات ن للحصول على كل هذه الأرقام في المكان الصحيح.

52
00:03:13,230 --> 00:03:16,230
وقالت ان مثل خوارزمية لتشغيل في وقت الخطية،

53
00:03:16,230 --> 00:03:18,090
ولكن لا تقلق بشأن ذلك هنا.

54
00:03:18,570 --> 00:03:22,810
>> باستخدام خوارزمية لدينا لدمج، يمكننا أن نجعل نوع الدمج السريع الخوارزمية.

55
00:03:22,810 --> 00:03:25,170
لذلك، دعونا إعادة تعيين قوائمنا.

56
00:03:35,210 --> 00:03:37,750
هناك 2 خطوات كبيرة في عملية فرز الدمج.

57
00:03:37,750 --> 00:03:41,500
أولا، تقسيم باستمرار لائحة أكواب الى نصفين

58
00:03:41,500 --> 00:03:44,860
حتى نحصل على مجموعة من القوائم مع 1 كوب فقط في نفوسهم.

59
00:03:44,860 --> 00:03:47,350
لا تقلق إذا كانت قائمة تحتوي على عدد فردي

60
00:03:47,350 --> 00:03:49,880
ويمكنك أن تجعل خفض نظيفة تماما بينهما.

61
00:03:49,880 --> 00:03:53,750
فقط اختيار تعسفي لتشمل قائمة التي الكأس إضافية فيها.

62
00:03:53,750 --> 00:03:56,240
لذلك، دعونا تقسيم هذه القوائم.

63
00:03:58,140 --> 00:04:01,310
الآن لدينا 2 القوائم.

64
00:04:04,120 --> 00:04:06,570
الآن لدينا 4 قوائم.

65
00:04:10,350 --> 00:04:13,870
>> والآن لدينا 8 قوائم مع فنجان واحد في كل قائمة.

66
00:04:13,870 --> 00:04:16,630
هذا كل شيء حتى عن الخطوة 1.

67
00:04:16,630 --> 00:04:22,230
الخطوة 2 ل، ونحن دمج مرارا أزواج من القوائم باستخدام خوارزمية الدمج تعلمنا من قبل.

68
00:04:22,230 --> 00:04:29,160
دمج 108 و 15، نحن في نهاية المطاف مع قائمة 15، 108.

69
00:04:30,330 --> 00:04:36,250
دمج 50 و 4، نحن في نهاية المطاف مع 50، 4.

70
00:04:36,960 --> 00:04:41,400
دمج 8 و 42، نحن في نهاية المطاف مع 8 و 42.

71
00:04:42,790 --> 00:04:48,130
ودمج 23 و 16، نحن في نهاية المطاف مع 16 و 23.

72
00:04:49,740 --> 00:04:52,450
الآن لدينا جميع القوائم من حجم 2.

73
00:04:53,020 --> 00:04:56,180
تلاحظ أن يتم فرز كل من القوائم 4.

74
00:04:56,180 --> 00:04:59,160
>> حتى نتمكن من بدء دمج أزواج من القوائم مرة أخرى.

75
00:04:59,160 --> 00:05:03,240
دمج 15 و 108 و 4 و 50 -

76
00:05:03,240 --> 00:05:11,170
تأخذ أولا 4، ثم 15، ثم 50، ثم 108.

77
00:05:11,170 --> 00:05:15,120
دمج 8 و 42 و 16 و 23،

78
00:05:15,120 --> 00:05:22,440
نأخذ أولا 8، ثم 16، ثم 23، ثم 42.

79
00:05:22,440 --> 00:05:27,370
حتى الآن لدينا فقط 2 قوائم حجم 4، يتم فرز كل منها.

80
00:05:27,370 --> 00:05:30,980
حتى الآن نحن دمج هذه القوائم 2.

81
00:05:30,980 --> 00:05:33,440
أولا نأخذ 4.

82
00:05:33,440 --> 00:05:36,580
ثم أخذنا 8.

83
00:05:36,580 --> 00:05:50,700
ثم نأخذ 15 و 16، ثم 23، ثم 42، ثم 50، ثم 108.

84
00:05:50,700 --> 00:05:52,220
وننتهي.

85
00:05:52,220 --> 00:05:54,900
لدينا الآن قائمة فرزها.

86
00:05:54,900 --> 00:05:57,890
فكيف كان هذا بسرعة، بالضبط؟

87
00:05:57,890 --> 00:06:02,000
من الناحية التقنية، دمج النوع هو O (N سجل ن)،

88
00:06:02,000 --> 00:06:07,380
في حين أن كل من نوع فقاعة، نوع الإدراج، واختيار نوع O هي (ن ²).

89
00:06:07,380 --> 00:06:11,120
في الواقع، وكما ستعرف قريبا، فلن تكون قادرة على الخروج مع نوع

90
00:06:11,120 --> 00:06:14,820
التي تنفذ أفضل من O (ن سجل ن) في الحالة العامة.

91
00:06:14,820 --> 00:06:19,120
مرة أخرى، لا تقلق بشأن هذا التدوين O كبيرة إذا كنت لم أر حتى الآن.

92
00:06:19,120 --> 00:06:23,490
>> أعرف فقط أن هذا يعني إذا كنا نريد لفرز قائمة كبيرة حقا

93
00:06:23,490 --> 00:06:26,820
يمكن فرز الفقاعة، نوع الإدراج، واختيار نوع يحتمل أن

94
00:06:26,820 --> 00:06:29,500
لفترة أطول كثيرا من دمج النوع.

95
00:06:29,500 --> 00:06:33,210
وهذا لا يعني أن دمج النوع سيكون أسرع لجميع القوائم

96
00:06:33,210 --> 00:06:36,220
أو حتى لأي قائمة واحدة تحت حجم معين.

97
00:06:36,220 --> 00:06:41,950
على سبيل المثال، قد يكون نوع الإدراج أسرع الفرز لجميع القوائم أصغر من 5 عناصر.

98
00:06:41,950 --> 00:06:47,360
في الممارسة العملية، دمج النوع عادة ما يكون أسرع لقوائم صغيرة مثل 50 عنصرا.

99
00:06:47,360 --> 00:06:51,120
>> ولكن هذه السرعة لا تأتي من خارج دون ثمن.

100
00:06:51,120 --> 00:06:54,770
على عكس أنواع أخرى لدينا، والتي تأخذ قائمة وتعديل قائمة في المكان

101
00:06:54,770 --> 00:06:58,740
حتى نحصل على قائمة تم فرزها، دمج النوع يحتاج إلى بعض مساحة إضافية

102
00:06:58,740 --> 00:07:00,900
لدمج 2 قوائم معا.

103
00:07:00,900 --> 00:07:04,690
لا يمكننا استخدام على الفور القوائم التي يجري دمجها لتخزين قائمة المدمجة

104
00:07:04,690 --> 00:07:08,880
ونحن قد تجاوز منذ العناصر التي لا تزال بحاجة إلى دمجها.

105
00:07:08,880 --> 00:07:13,540
هذا الفضاء هو جزء من الثمن، ولكن عادة ما يكون من غير المعقول.

106
00:07:13,540 --> 00:07:15,330
وهذا كل شيء عن نوع الدمج.

107
00:07:15,330 --> 00:07:18,490
>> اسمي روب بودين، وهذا هو CS50.

108
00:07:18,490 --> 00:07:20,500
[CS50.TV]

109
00:07:20,500 --> 00:07:24,000
- واختيار نوع.

110
00:07:24,000 --> 00:07:25,880
[يضحك]

111
00:07:25,880 --> 00:07:31,480
أوه، حصلت على اتخاذ أنه من اللازم لأنني تحولت كيف كنت عرضه.

112
00:07:31,480 --> 00:07:35,680
القائمة على اليسار. كان ذلك خطأ مطبعي.

113
00:07:35,680 --> 00:07:39,290
[اخطأ] I ثمل -

114
00:07:39,290 --> 00:07:41,190
[يضحك]

115
00:07:41,190 --> 00:07:44,190
أنا لا أعرف ما -