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
>> דאג LLOYD: אוקיי, אז מיזוג
סוג הוא עדיין אלגוריתם אחר

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
מיין את המחצית השמאלית של המערך,
בהנחת n היא גדולה מ -1.

16
00:00:46,320 --> 00:00:49,980
ולמה אני מתכוון כשאני אומר
בהנחת n היא גדולה מ 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
נשמע כמו שאתה דוחה את כל--
אתה לא באמת עושה שום דבר.

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
>> אז יש לנו עכשיו מסודרים
מחצית השמאלית של half-- השמאל

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
הולך להמשיך, iterating למטה.

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
>> אישור, תמונה כל כך גדולה, בואו
לקחת הפסקה לשנייה

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
לפצל n אלמנטים עד
ולאחר מכן לשלב מחדש אותם.

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
>> אבל כמה הכפלות
זה לוקח להגיע לn?

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
אבל אנחנו גם עדיין צריכים לפחות
להסתכל על כל אלמנטי n.

223
00:10:48,590 --> 00:10:53,860
אז במקרה הגרוע ביותר,
מיון מיזוג פועל בn n יומן.

224
00:10:53,860 --> 00:10:56,160
אנחנו צריכים להסתכל על
כל האלמנטים n,

225
00:10:56,160 --> 00:11:02,915
ואנחנו צריכים לשלב אותם
יחד ביומן n סטים של צעדים.

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
אלגוריתם זה פועל ביומן n n זמן.

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