1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [השמעת מוסיקה]

3
00:00:10,800 --> 00:00:13,500
דוד Malan: בסדר.

4
00:00:13,500 --> 00:00:14,670
בסדר, ברוך שובך.

5
00:00:14,670 --> 00:00:18,120
אז זה שבוע 4, בתחילת
ממנו, כבר.

6
00:00:18,120 --> 00:00:21,320
ואתה זוכר בשבוע שעבר את זה, אנחנו שמים את
קוד בצד לקצת

7
00:00:21,320 --> 00:00:24,240
והתחלנו לדבר קצת יותר
ברמה גבוהה על דברים, כמו

8
00:00:24,240 --> 00:00:28,130
חיפוש ומיון, אשר למרות
רעיונות פשוטים למדי, הם

9
00:00:28,130 --> 00:00:31,840
נציג של כיתה של בעיות
אתה תתחיל לפתור במיוחד

10
00:00:31,840 --> 00:00:34,820
כפי שאתה מתחיל לחשוב על גמר
פרויקטים ופתרונות מעניינים אותך

11
00:00:34,820 --> 00:00:36,760
אולי יש לך בעיות בעולם אמיתית.

12
00:00:36,760 --> 00:00:39,490
עכשיו מיון בועות היה אחד הפשוט
אלגוריתמים כאלה, וזה

13
00:00:39,490 --> 00:00:42,900
עבד על ידי כך המספרים הקטנים האלה
ברשימה או בסוג מערך של

14
00:00:42,900 --> 00:00:46,530
בועה עד לקצה את דרכם, ו
מספרים גדולים לעבור את דרכם אל

15
00:00:46,530 --> 00:00:47,930
סוף שהרשימה.

16
00:00:47,930 --> 00:00:50,650
>> ולהיזכר שאנחנו יכולים לדמיין
מיון בועות קטן

17
00:00:50,650 --> 00:00:52,310
משהו כזה.

18
00:00:52,310 --> 00:00:53,640
אז תן לי ללכת קדימה ולחץ על התחל.

19
00:00:53,640 --> 00:00:55,350
אני כבר נבחרתי מראש מיון בועות.

20
00:00:55,350 --> 00:00:58,920
ואם אתה זוכר שכחול יותר גבוה
קווים מייצגים מספרים גדולים, קטנים

21
00:00:58,920 --> 00:01:03,300
קווים כחולים מייצגים מספרים קטנים, כמו
אנחנו הולכים לעבור את זה שוב ושוב ו

22
00:01:03,300 --> 00:01:07,680
שוב, השוואה בין שני ברים ליד כל
השני באדום, אנחנו הולכים להחליף

23
00:01:07,680 --> 00:01:11,010
הגדול ביותר והקטן ביותר, אם
הם מקולקלים.

24
00:01:11,010 --> 00:01:14,150
>> כך זה יימשך ותלך ובללכת
ב, ואתה תראה שיותר גדול

25
00:01:14,150 --> 00:01:16,700
אלמנטים עושים את דרכם ל
נכון, והם המרכיבים הקטנים יותר

26
00:01:16,700 --> 00:01:17,900
עושה את דרכם לצד השמאל.

27
00:01:17,900 --> 00:01:21,380
אבל אנחנו התחלנו לכמת
יעיל,

28
00:01:21,380 --> 00:01:22,970
איכות של אלגוריתם זה.

29
00:01:22,970 --> 00:01:25,200
ואנחנו אמרו שבגרוע ביותר
מקרה, אלגוריתם זה לקח

30
00:01:25,200 --> 00:01:27,940
בערך כמה צעדים?

31
00:01:27,940 --> 00:01:28,980
>> אז n בריבוע.

32
00:01:28,980 --> 00:01:30,402
ומה היה n?

33
00:01:30,402 --> 00:01:31,650
>> קהל: מספר האלמנטים.

34
00:01:31,650 --> 00:01:32,790
>> דוד Malan: אז היה n
מספר האלמנטים.

35
00:01:32,790 --> 00:01:33,730
ולכן אנחנו נעשה את זה לעתים קרובות.

36
00:01:33,730 --> 00:01:36,650
בכל פעם שאנחנו רוצים לדבר על הגודל
של בעיה או בגודל של

37
00:01:36,650 --> 00:01:39,140
קלט, או את כמות הזמן שלוקח
כדי להפיק פלט, אנחנו פשוט

38
00:01:39,140 --> 00:01:41,610
מה כללי
הקלט הוא כn.

39
00:01:41,610 --> 00:01:45,970
אז בחזרה בשבוע 0, דפי המספר
בספר הטלפונים היה n.

40
00:01:45,970 --> 00:01:47,550
מספר התלמידים
בחדר היה n.

41
00:01:47,550 --> 00:01:49,630
אז הנה, גם אנחנו עוקבים
דפוס זה.

42
00:01:49,630 --> 00:01:52,800
>> עכשיו n בריבוע זה לא במיוחד
מהר, כל כך שניסינו לעשות טוב יותר.

43
00:01:52,800 --> 00:01:55,970
וכך אנו נראים בכמה
אלגוריתמים אחרים, ביניהם

44
00:01:55,970 --> 00:01:57,690
היה מיון בחירה.

45
00:01:57,690 --> 00:01:59,180
אז מיון בחירה היה
קצת שונה.

46
00:01:59,180 --> 00:02:03,130
זה היה כמעט יותר פשוט, אני מעז לומר,
לפיה התחלתי בתחילת

47
00:02:03,130 --> 00:02:06,740
רשימה של המתנדבים שלנו ואני פשוט שוב
והלכו שוב ושוב באמצעות

48
00:02:06,740 --> 00:02:10,060
הרשימה, תולשת הקטן ביותר
אלמנט בכל פעם ולשים אותו או

49
00:02:10,060 --> 00:02:13,040
שלה בתחילת הרשימה.

50
00:02:13,040 --> 00:02:16,410
>> אבל גם את זה, ברגע שהתחלנו לחשוב
דרך המתמטיקה וגדולה יותר

51
00:02:16,410 --> 00:02:19,860
תמונה, חשבה על כמה פעמים
אני הולך הלוך ושוב ושוב

52
00:02:19,860 --> 00:02:24,090
ושוב, שאמרנו במקרה הגרוע ביותר,
מיון בחירה, יותר מדי, היה מה?

53
00:02:24,090 --> 00:02:24,960
n בריבוע.

54
00:02:24,960 --> 00:02:27,490
עכשיו בעולם האמיתי, זה אולי
למעשה להיות שולי יותר מהר.

55
00:02:27,490 --> 00:02:30,620
כי שוב, אני לא צריך לשמור
הליכה לאחור ברגע שמסודר

56
00:02:30,620 --> 00:02:31,880
האלמנטים הקטנים ביותר.

57
00:02:31,880 --> 00:02:35,090
אבל אם אנחנו חושבים על n גדול מאוד, ו
אם אתה סוג של לעשות את המתמטיקה כ

58
00:02:35,090 --> 00:02:39,170
אני עשיתי על הלוח, עם ריבוע n
משהו מינוס, כל השאר

59
00:02:39,170 --> 00:02:41,850
חוץ מזה n בריבוע, ברגע שn
נהיה ממש גדול, לא

60
00:02:41,850 --> 00:02:42,850
באמת משנה כל כך הרבה.

61
00:02:42,850 --> 00:02:45,470
אז כפי שמדעני מחשב, אנחנו איכשהו
להעלים עין לקטנה יותר

62
00:02:45,470 --> 00:02:49,220
גורמים ולהתמקד רק בגורם ב
ביטוי שהולך לעשות

63
00:02:49,220 --> 00:02:50,330
ההבדל הגדול ביותר.

64
00:02:50,330 --> 00:02:52,840
>> ובכן, לבסוף, בדקנו
ב מסוג הכניסה.

65
00:02:52,840 --> 00:02:56,620
וזה היה דומה ברוחו, אבל
במקום לעבור וiteratively

66
00:02:56,620 --> 00:03:01,250
בחר המרכיב אחד הקטן ביותר ב
זמן, אני במקום לקחתי את היד שאני

67
00:03:01,250 --> 00:03:04,070
טופל, ואני החלטתי, כל
נכון, אתה שייך לכאן.

68
00:03:04,070 --> 00:03:06,160
לאחר מכן עברתי לאלמנט הבא
והחליט שהוא או

69
00:03:06,160 --> 00:03:07,470
היא שייכת לכאן.

70
00:03:07,470 --> 00:03:08,810
ולאחר מכן המשכתי הלאה והלאה.

71
00:03:08,810 --> 00:03:11,780
ואולי אני צריך, בדרך,
משמרת החבר 'ה האלה כדי

72
00:03:11,780 --> 00:03:13,030
לפנות מקום עבורם.

73
00:03:13,030 --> 00:03:16,880
אז זה היה סוג של ההיפוך הנפשי
של מיון בחירה שאנחנו

74
00:03:16,880 --> 00:03:18,630
נקרא סוג כניסה.

75
00:03:18,630 --> 00:03:20,810
>> אז הנושאים האלה להתרחש
בעולם האמיתי.

76
00:03:20,810 --> 00:03:23,640
רק לפני כמה שנים, כאשר מסוים
הסנטור רץ לנשיאות,

77
00:03:23,640 --> 00:03:27,160
אריק שמידט, בעת מנכ"ל
גוגל, למעשה הייתה לי ההזדמנות

78
00:03:27,160 --> 00:03:28,040
כדי לראיין אותו.

79
00:03:28,040 --> 00:03:32,010
ואנחנו חשבנו שזה חולק YouTube
קליפ לך כאן, אם אנחנו יכולים להפוך את

80
00:03:32,010 --> 00:03:32,950
את עוצמת הקול.

81
00:03:32,950 --> 00:03:39,360
>> [השמעת וידאו]

82
00:03:39,360 --> 00:03:44,620
>> , עכשיו, סנטור, אתה כאן בגוגל,
ואני רוצה לחשוב על הנשיאות

83
00:03:44,620 --> 00:03:46,042
כמו ראיון עבודה.

84
00:03:46,042 --> 00:03:47,770
>> [שחוק]

85
00:03:47,770 --> 00:03:50,800
>> -עכשיו זה קשה להשגה
עבודה כנשיא.

86
00:03:50,800 --> 00:03:52,480
ושאתם עוברים
בתלאות עכשיו.

87
00:03:52,480 --> 00:03:54,330
קשה גם לקבל עבודה בגוגל.

88
00:03:54,330 --> 00:03:59,610
יש לנו שאלות ואנחנו שואלים
שאלות המועמדים שלנו.

89
00:03:59,610 --> 00:04:02,250
ואת זה הוא מלארי שווימר.

90
00:04:02,250 --> 00:04:05,325
>> [שחוק]

91
00:04:05,325 --> 00:04:06,400
-אתם חושבים שאני צוחק?

92
00:04:06,400 --> 00:04:08,750
זה ממש כאן.

93
00:04:08,750 --> 00:04:12,110
מהי הדרך היעילה ביותר
למיין מיליון מספרים שלמים שתיים סיביות?

94
00:04:12,110 --> 00:04:15,810
>> [שחוק]

95
00:04:15,810 --> 00:04:18,260
>> -טוב, אה -

96
00:04:18,260 --> 00:04:19,029
>> -אני מצטער.

97
00:04:19,029 --> 00:04:19,745
אולי אנחנו צריכים -

98
00:04:19,745 --> 00:04:21,000
>> לא, לא, לא, לא, לא.

99
00:04:21,000 --> 00:04:21,470
>> -זה לא -

100
00:04:21,470 --> 00:04:22,185
אישור.

101
00:04:22,185 --> 00:04:25,328
>> אני חושב שהיית עושה-מיון הבועות
תהיה בדרך הלא נכונה ללכת אליו.

102
00:04:25,328 --> 00:04:26,792
>> [שחוק]

103
00:04:26,792 --> 00:04:28,510
>> [מריע ומחיאות כפות]

104
00:04:28,510 --> 00:04:31,211
>> -קדימה, שאמר לו את זה?

105
00:04:31,211 --> 00:04:32,155
אישור.

106
00:04:32,155 --> 00:04:33,350
>> [השמעת וידאו הסוף]

107
00:04:33,350 --> 00:04:35,070
>> דוד Malan: אז יש לך את זה.

108
00:04:35,070 --> 00:04:39,600
אז התחלנו לרוץ לכמת אלה
פעמים, כביכול, עם משהו

109
00:04:39,600 --> 00:04:43,480
קרא בסימון אסימפטוטי, שהוא
פשוט מתייחס לסוג של הפיכתנו

110
00:04:43,480 --> 00:04:47,420
עין עיוורת לגורמים קטנים יותר ואלה
רק הסתכלות בזמן הריצה,

111
00:04:47,420 --> 00:04:51,250
ביצועים של האלגוריתמים הללו,
כn נהיה ממש גדול לאורך זמן.

112
00:04:51,250 --> 00:04:55,110
וכך הצגנו O. הגדול והגדול O
משהו שייצג אותנו חשבנו

113
00:04:55,110 --> 00:04:57,000
כמגבול עליון.

114
00:04:57,000 --> 00:04:59,570
ולמעשה, בארי, אנו יכולים להוריד
מהמיקרופון קצת?

115
00:04:59,570 --> 00:05:01,040
>> אנחנו חשבנו על זה הוא גבול עליון.

116
00:05:01,040 --> 00:05:04,710
O גדול כל כך של אמצעי בריבוע n שב
במקרה הגרוע ביותר, משהו כמו

117
00:05:04,710 --> 00:05:07,780
מיון בחירה היה לוקח
n צעדים בריבוע.

118
00:05:07,780 --> 00:05:10,310
או משהו כמו סוג ההכנסה
הייתם שלבים בריבוע n.

119
00:05:10,310 --> 00:05:15,150
ועכשיו למשהו כמו החדרה
סוג שהוא, מה שהיה במקרה הגרוע ביותר?

120
00:05:15,150 --> 00:05:18,200
בהתחשב במערך, מה הכי גרוע
תרחיש אפשרי כי אתה עלול למצוא את

121
00:05:18,200 --> 00:05:20,650
את עצמך מתמודד עם?

122
00:05:20,650 --> 00:05:21,860
>> זה אחורה לחלוטין, נכון?

123
00:05:21,860 --> 00:05:24,530
מכיוון שאם זה אחורה לחלוטין,
אתה צריך לעשות המון עבודה.

124
00:05:24,530 --> 00:05:26,420
כי אם אתה לאחור לגמרי,
אתה הולך למצוא את

125
00:05:26,420 --> 00:05:28,840
המרכיב הגדול ביותר כאן, למרות
הוא שייך לשם.

126
00:05:28,840 --> 00:05:31,140
אז אתה הולך להגיד, בסדר, ב
רגע זה בזמן, שאתה שייך לכאן,

127
00:05:31,140 --> 00:05:32,310
אז אתה משאיר אותו לבד.

128
00:05:32,310 --> 00:05:35,425
>> אז אתה מבין, אה, לעזאזל, יש לי כדי
להעביר את האלמנט הזה לקצת יותר קטן

129
00:05:35,425 --> 00:05:36,470
בצד השמאל שלך.

130
00:05:36,470 --> 00:05:38,770
ואז אני צריך לעשות את זה שוב
ושוב ושוב.

131
00:05:38,770 --> 00:05:41,410
ואם הלכתי קדימה ואחורה, אתה
היה קצת מרגיש את הביצועים של

132
00:05:41,410 --> 00:05:45,540
אלגוריתם זה, כי אני כל הזמן
דשדוש כולם למטה ב

133
00:05:45,540 --> 00:05:46,510
מערך כדי לפנות מקום לזה.

134
00:05:46,510 --> 00:05:47,750
אז זה המקרה הגרוע ביותר.

135
00:05:47,750 --> 00:05:48,570
>> לעומת זאת -

136
00:05:48,570 --> 00:05:50,320
וזו הייתה הפעם האחרונה סחרור מסוכן -

137
00:05:50,320 --> 00:05:54,065
אנחנו אמרתי שסוג ההכנסה
הייתה אומגה של מה?

138
00:05:54,065 --> 00:05:57,530
מה הכי טוב במקרה הריצה
זמן של מיון הכנסה?

139
00:05:57,530 --> 00:05:58,520
אז זה בעצם n.

140
00:05:58,520 --> 00:06:00,980
שהיה ריק שעזבנו
על הלוח בפעם אחרונה.

141
00:06:00,980 --> 00:06:03,160
>> וזה אומגה של n, כי למה?

142
00:06:03,160 --> 00:06:06,630
ובכן, במקרה הטוב ביותר, מה
מיין ההכנסה הולך להימסר?

143
00:06:06,630 --> 00:06:09,830
ובכן, רשימה שמסודרת לחלוטין
כבר, עבודה מינימאלית לעשות.

144
00:06:09,830 --> 00:06:12,460
אבל מה שמדליק בסוג ההכנסה
האם זה בגלל שזה מתחיל כאן ו

145
00:06:12,460 --> 00:06:15,340
מחליט, הו, אתה המספר
אחד, אתה שייך לכאן.

146
00:06:15,340 --> 00:06:16,970
הו, איזה מזל טוב.

147
00:06:16,970 --> 00:06:17,740
>> אתה המספר שתיים.

148
00:06:17,740 --> 00:06:19,030
אתה גם שייך לכאן.

149
00:06:19,030 --> 00:06:21,010
מספר שלוש, אפילו טוב יותר,
אתה שייך לכאן.

150
00:06:21,010 --> 00:06:25,210
ברגע שהוא מגיע לסוף
pseudocode רשימה, לכניסתו של הסוג

151
00:06:25,210 --> 00:06:28,010
כי הלכנו דרך מילולי
בפעם האחרונה, זה נעשה.

152
00:06:28,010 --> 00:06:32,790
אבל מיון בחירה, לעומת זאת,
כל הזמן עושה את מה?

153
00:06:32,790 --> 00:06:35,260
>> המשיך ללכת דרך הרשימה
שוב ושוב ושוב.

154
00:06:35,260 --> 00:06:39,160
בגלל תובנה המרכזית הייתה רק
לאחר שחפשת בכל הדרך

155
00:06:39,160 --> 00:06:42,500
סוף הרשימה אתה יכול להיות בטוח
שהאלמנט שבחרת היה

156
00:06:42,500 --> 00:06:45,560
אכן היסוד הקטן ביותר ברגע זה.

157
00:06:45,560 --> 00:06:48,920
אז אלו דגמי קצה נפשי שונה
עד כמה מניב מאוד בעולם אמיתי

158
00:06:48,920 --> 00:06:53,130
הבדלים עבורנו, כמו גם אלה
הבדלים אסימפטוטיות תיאורטיים.

159
00:06:53,130 --> 00:06:56,910
>> אז רק כדי לסכם, אם כן, גדול O של n
בריבוע, שראינו כמה כגון

160
00:06:56,910 --> 00:06:58,350
אלגוריתמים עד כה.

161
00:06:58,350 --> 00:06:59,580
ביג O של n?

162
00:06:59,580 --> 00:07:02,870
מה אלגוריתם שיכול
להיות אמר להיות גדול O של n?

163
00:07:02,870 --> 00:07:06,930
במקרה הגרוע ביותר, זה לוקח
מספר יניארית של צעדים.

164
00:07:06,930 --> 00:07:07,810
>> בסדר, חיפוש לינארי.

165
00:07:07,810 --> 00:07:10,470
ובמקרה הגרוע ביותר, שבו הוא
אלמנט שאתה מחפש כש

166
00:07:10,470 --> 00:07:12,950
יישום חיפוש ליניארי?

167
00:07:12,950 --> 00:07:14,680
>> אוקיי, במקרה הגרוע ביותר,
זה אפילו לא שם.

168
00:07:14,680 --> 00:07:17,000
או במקרה הגרוע ביותר השני, זה
כל הדרך בסופו של הדבר, שהוא

169
00:07:17,000 --> 00:07:18,880
פלוס או מינוס הבדל אחד צעד.

170
00:07:18,880 --> 00:07:21,180
אז בסופו של היום,
אנחנו יכולים להגיד שזה ליניארי.

171
00:07:21,180 --> 00:07:23,910
ביג O של n יהיה החיפוש ליניארי,
משום שבמקרה הגרוע ביותר,

172
00:07:23,910 --> 00:07:26,610
אלמנט זה אפילו לא שם, או שזה
כל הדרך בסוף.

173
00:07:26,610 --> 00:07:29,370
>> ובכן, גדול O של יומן של n.

174
00:07:29,370 --> 00:07:32,760
לא דיבר בפירוט רב על
זה, אבל אנחנו כבר ראינו את זה קודם.

175
00:07:32,760 --> 00:07:36,840
מה רץ בלוגריתמים שנקרא
פעם, במקרה הגרוע ביותר?

176
00:07:36,840 --> 00:07:38,500
>> כן, כך חיפוש בינארי.

177
00:07:38,500 --> 00:07:42,930
וחיפוש בינארי במקרה הגרוע ביותר
אולי יש אלמנט אי שם ב

178
00:07:42,930 --> 00:07:45,640
באמצע, או במקום
בתוך המערך.

179
00:07:45,640 --> 00:07:48,040
אבל אתה מוצא את זה רק ברגע שאתה
לחלק את הרשימה לשתיים, ב

180
00:07:48,040 --> 00:07:48,940
מחצית, במחצית, במחצית.

181
00:07:48,940 --> 00:07:50,200
ואז זהו, זה שם.

182
00:07:50,200 --> 00:07:52,500
או שוב, במקרה הגרוע ביותר,
זה אפילו לא שם.

183
00:07:52,500 --> 00:07:56,770
אבל אתה לא יודע שזה לא שם
עד שאתה מגיע לסוג של שעבר

184
00:07:56,770 --> 00:08:00,470
מלמטה רוב האלמנטים של חצייה
וחצייה והחצייה.

185
00:08:00,470 --> 00:08:01,400
>> ביג O של 1.

186
00:08:01,400 --> 00:08:03,540
כך שיכולנו גדול O של 2, גדול O של 3.

187
00:08:03,540 --> 00:08:06,260
כל פעם שאתה רוצה רק מספר קבוע,
אנחנו פשוט למיין רק לפשט

188
00:08:06,260 --> 00:08:07,280
כי כגדול O של 1.

189
00:08:07,280 --> 00:08:10,440
למרות שאם באופן מעשי, זה לוקח
2 או אפילו 100 צעדים, אם זה

190
00:08:10,440 --> 00:08:13,680
מספר קבוע של צעדים,
אנחנו רק אומרים O הגדול של 1.

191
00:08:13,680 --> 00:08:15,930
מה זה אלגוריתם
בגדול O של 1?

192
00:08:15,930 --> 00:08:18,350
>> קהל: מציאת האורך
של משתנה.

193
00:08:18,350 --> 00:08:21,090
>> דוד Malan: מציאת
אורך משתנה?

194
00:08:21,090 --> 00:08:23,870
>> קהל: לא, אורך
אם זה כבר מסודר.

195
00:08:23,870 --> 00:08:24,160
>> דוד Malan: טוב.

196
00:08:24,160 --> 00:08:27,850
אוקיי, אז למצוא את האורך של משהו
אם אורכו של משהו, כמו

197
00:08:27,850 --> 00:08:30,020
מערך, מאוחסן בכמה משתנים.

198
00:08:30,020 --> 00:08:33,380
כי אתה פשוט יכול לקרוא משתנה,
או להדפיס משתנה, או

199
00:08:33,380 --> 00:08:34,960
רק בדרך כלל לגשת למשתנה זה.

200
00:08:34,960 --> 00:08:37,299
וזהו, זה לוקח זמן קבוע.

201
00:08:37,299 --> 00:08:38,909
>> לעומת זאת, חושב לחזור לגרד.

202
00:08:38,909 --> 00:08:42,460
היזכר בשבוע הראשון של C,
קוראים רק printf והדפסה

203
00:08:42,460 --> 00:08:46,240
משהו על המסך הוא לטעון
זמן קבוע, כי זה פשוט לוקח

204
00:08:46,240 --> 00:08:50,880
חלק מספר מחזורי CPU כדי להראות
טקסט שעל המסך.

205
00:08:50,880 --> 00:08:52,720
או לחכות - עושה את זה?

206
00:08:52,720 --> 00:08:56,430
אחרת, איך ייתכן שמודל
ביצועים של printf?

207
00:08:56,430 --> 00:09:00,420
האם מישהו רוצה שלא להסכים, כי
אולי זה לא זמן באמת קבוע?

208
00:09:00,420 --> 00:09:03,600
באיזה מובנת אולי printf פועל
זמן, בעצם מדפיס מחרוזת על

209
00:09:03,600 --> 00:09:05,580
המסך, יהיה משהו
מלבד קבוע.

210
00:09:05,580 --> 00:09:07,860
>> קהל: [לא ברור].

211
00:09:07,860 --> 00:09:08,230
>> דוד Malan: כן.

212
00:09:08,230 --> 00:09:09,300
כך שזה תלוי בנקודת המבט שלנו.

213
00:09:09,300 --> 00:09:13,390
אם אנחנו באמת חושבים על הקלט
printf כמחרוזת, ו

214
00:09:13,390 --> 00:09:16,380
לכן אנו מודדים את גודל ה
קלט באורכו - אז בואו לקרוא

215
00:09:16,380 --> 00:09:17,780
אורך n שכן -

216
00:09:17,780 --> 00:09:21,990
ניתן לטעון, printf הוא עצמו O הגדול של n
כי זה הולך לקחת לך n צעדים

217
00:09:21,990 --> 00:09:24,750
כדי להדפיס את כל אחד מאלה n
דמויות, סביר להניח.

218
00:09:24,750 --> 00:09:27,730
לפחות במידה שאנו מניחים
כי אולי זה שימוש עבור לולאה

219
00:09:27,730 --> 00:09:28,560
מתחת למכסת המנוע.

220
00:09:28,560 --> 00:09:30,860
>> אבל אנחנו צריכים להסתכל על זה
קוד כדי להבין את זה טוב יותר.

221
00:09:30,860 --> 00:09:33,650
ואכן, ברגע שהחבר 'ה מתחילה
ניתוח אלגוריתמים משלך, אתה

222
00:09:33,650 --> 00:09:34,900
פשוטו כמשמעו לעשות בדיוק את זה.

223
00:09:34,900 --> 00:09:37,765
סוג של גלגל העין וחושב שהקוד שלך
על - בסדר, יש לי את זה לולאה

224
00:09:37,765 --> 00:09:41,870
יש לי כאן או בלולאות מקוננות כאן,
שהולך לעשות דברים n n פעמים,

225
00:09:41,870 --> 00:09:46,050
ואתה יכול למיין של סיבה בדרך שלך
באמצעות הקוד, גם אם זה

226
00:09:46,050 --> 00:09:47,980
pseudocode ולא קוד עצמו.

227
00:09:47,980 --> 00:09:49,730
>> אז מה לגבי אומגה של n בריבוע?

228
00:09:49,730 --> 00:09:53,582
מה היה באלגוריתם שהכי הטוב
מקרה, עדיין לקח N צעדים בריבוע?

229
00:09:53,582 --> 00:09:54,014
כן?

230
00:09:54,014 --> 00:09:54,880
>> קהל: [לא ברור].

231
00:09:54,880 --> 00:09:55,900
>> דוד Malan: מיון בחירה אז.

232
00:09:55,900 --> 00:09:59,150
משום בבעיה שבאמת הקטין
לעובדה ששוב, אני לא יודע

233
00:09:59,150 --> 00:10:02,600
אני כבר נמצא הקטן ביותר נוכחי עד
בדקתי את כל האלמנטים לתקן.

234
00:10:02,600 --> 00:10:08,050
אז אומגה של, יניח, n, אנחנו
פשוט באו עם אחד.

235
00:10:08,050 --> 00:10:09,300
סוג הכניסה.

236
00:10:09,300 --> 00:10:12,370
אם הרשימה שקורה להיות מסודרת
כבר, במקרה הטוב אנחנו רק צריכים

237
00:10:12,370 --> 00:10:15,090
כדי להפוך את מעבר אחד דרכו,
בשלב בו אנחנו בטוחים.

238
00:10:15,090 --> 00:10:17,890
ואז אפשר לומר ש
להיות ליניארי, זה בטוח.

239
00:10:17,890 --> 00:10:20,570
>> מה לגבי אומגה של 1?

240
00:10:20,570 --> 00:10:23,790
מה, במקרה הטוב ביותר, עלול לקחת
מספר קבוע של צעדים?

241
00:10:23,790 --> 00:10:27,220
חיפוש כל כך ליניארי, אם יש מזל
והאלמנט שאתה מחפש

242
00:10:27,220 --> 00:10:31,000
נכון בתחילת הרשימה,
אם זה שבו אתה מתחיל שלך

243
00:10:31,000 --> 00:10:33,070
ליניארי חציית של אותה הרשימה.

244
00:10:33,070 --> 00:10:35,180
>> וזה נכון לגבי
מספר דברים.

245
00:10:35,180 --> 00:10:37,660
לדוגמה, אפילו בינארי
חיפוש הוא אומגה של 1.

246
00:10:37,660 --> 00:10:40,310
משום מה אם אתה מקבל באמת המעצבן הזה
מזל והרואין DAB-באמצע

247
00:10:40,310 --> 00:10:42,950
המערך שלך הוא המספר
שאתה מחפש?

248
00:10:42,950 --> 00:10:45,730
כך שאתה יכול לקבל מזל שם, גם כן.

249
00:10:45,730 --> 00:10:49,190
>> זה אחד, ולבסוף, אומגה של n log n.

250
00:10:49,190 --> 00:10:52,573
אז n log n, אנחנו לא ממש
לדבר על עדיין, אבל -

251
00:10:52,573 --> 00:10:53,300
>> קהל: מיזוג סוג?

252
00:10:53,300 --> 00:10:53,960
>> דוד Malan: מיון מיזוג.

253
00:10:53,960 --> 00:10:56,920
זה היה הסחרור המסוכן של הזמן האחרון,
שבו אנו מציעים, ואנו הראו

254
00:10:56,920 --> 00:10:58,600
מבחינה ויזואלית, כי יש אלגוריתמים.

255
00:10:58,600 --> 00:11:02,470
ולמזג מין רק אחד כזה
אלגוריתם שהוא ביסוד מהר יותר

256
00:11:02,470 --> 00:11:03,450
מכמה מהבחורים אחרים.

257
00:11:03,450 --> 00:11:07,800
למעשה, למזג קצר היא לא רק ב
מקרה טוב n n יומן, בגרוע ביותר

258
00:11:07,800 --> 00:11:09,460
מקרה n n יומן.

259
00:11:09,460 --> 00:11:14,540
וכאשר יש לך במקרה זה של
אומגה וגדול O להיות אותו הדבר?

260
00:11:14,540 --> 00:11:17,310
אנחנו יכולים למעשה מתארים את זה כמה
שם תטא, למרות שזה

261
00:11:17,310 --> 00:11:18,220
קצת פחות נפוץ.

262
00:11:18,220 --> 00:11:21,730
אבל זה רק אומר ששני הגבולות,
במקרה זה, הוא אותו הדבר.

263
00:11:21,730 --> 00:11:25,770
>> אז למזג מיון, מה שעושה את זה
באמת מסתכם עבורנו?

264
00:11:25,770 --> 00:11:27,000
ובכן, זוכר את המוטיבציה.

265
00:11:27,000 --> 00:11:30,340
תנו לי להרים את אנימציה אחרת ש
אנחנו לא מסתכלים על הזמן שעבר.

266
00:11:30,340 --> 00:11:33,390
זה אחד, אותו רעיון, אבל
זה קצת גדול יותר.

267
00:11:33,390 --> 00:11:36,160
ואני מתכוון להמשיך ולהצביע
ראשון - שיש לנו סוג הכנסה על

268
00:11:36,160 --> 00:11:39,410
השמאלי העליון, ולאחר מכן מיון בחירה,
מיון בועות, כמה סוגים אחרים -

269
00:11:39,410 --> 00:11:42,670
קליפה ומהירה - שלא דיברנו
עליו, והערימה ולמזג מיון.

270
00:11:42,670 --> 00:11:47,090
>> אז לפחות לנסות למקד את העיניים שלך על
למעלה שלושה בצד השמאל ולאחר מכן

271
00:11:47,090 --> 00:11:49,120
למזג מיון כשאני לוחץ
החץ הירוק הזה.

272
00:11:49,120 --> 00:11:51,900
אבל אני אתן את כולם לרוץ, רק כדי
נותן לך תחושה של הגיוון

273
00:11:51,900 --> 00:11:53,980
אלגוריתמים שקיימים בעולם.

274
00:11:53,980 --> 00:11:56,180
אני הולך לתת לזה לרוץ
רק כמה שניות.

275
00:11:56,180 --> 00:11:59,640
ואם למקד את העיניים שלך - להרים
אלגוריתם, להתמקד בו רק

276
00:11:59,640 --> 00:12:02,970
שניות - אתה מתחיל לראות את
דפוס שזה יישום.

277
00:12:02,970 --> 00:12:04,530
>> סוג מיזוג, הודעה מוקדמת, נעשה.

278
00:12:04,530 --> 00:12:06,430
מיון ערימה, מיון, קליפה מהירה -

279
00:12:06,430 --> 00:12:09,480
כך שזה נראה שאנחנו הצגנו את השלושה
האלגוריתמים הגרועים ביותר בשבוע שעבר.

280
00:12:09,480 --> 00:12:12,960
אבל זה טוב שאנחנו כאן היום כדי
להסתכל על סוג המיזוג, שהוא אחד

281
00:12:12,960 --> 00:12:16,500
כך קלים יותר אלה הוא להסתכל, אפילו
למרות שזה בטח יהיה לכופף את הראש שלך

282
00:12:16,500 --> 00:12:17,490
רק קצת.

283
00:12:17,490 --> 00:12:21,130
כאן אנו יכולים לראות עד כמה
מיון בחירה מבאס.

284
00:12:21,130 --> 00:12:24,600
>> אבל בצד השני של המטבע, זה
ממש קל ליישום.

285
00:12:24,600 --> 00:12:28,160
ואולי עבור P סט 3, זה אחד
אלגוריתמים שבחרתם ליישם

286
00:12:28,160 --> 00:12:28,960
למהדורה הסטנדרטית.

287
00:12:28,960 --> 00:12:30,970
בסדר גמור, נכון בצורה מושלמת.

288
00:12:30,970 --> 00:12:35,210
>> אבל שוב, כפי שמקבל n גדול, אם אתה
תבחר ליישם אלגוריתם מהיר יותר

289
00:12:35,210 --> 00:12:39,020
רוצים למזג מיון, סיכויים הם לגדולים יותר ו
תשומות גדולות יותר, הקוד שלך הוא רק

290
00:12:39,020 --> 00:12:39,800
הולך לרוץ מהר יותר.

291
00:12:39,800 --> 00:12:41,090
אתר האינטרנט שלך הולך לעבוד טוב יותר.

292
00:12:41,090 --> 00:12:42,650
המשתמשים שלך הולכים להיות יותר מאושר.

293
00:12:42,650 --> 00:12:45,280
ואז יש את ההשפעות הללו
של בעצם נותן

294
00:12:45,280 --> 00:12:47,350
לנו קצת יותר עמוקים חשבו.

295
00:12:47,350 --> 00:12:49,990
>> אז בואו נסתכל על מה שיתמזג
מיון הוא בעצם כל העניין.

296
00:12:49,990 --> 00:12:52,992
הדבר מגניב הוא שמיזוג
סוג הוא בדיוק את זה.

297
00:12:52,992 --> 00:12:56,300
זהו, שוב, מה שנקראנו
בן pseudocode, pseudocode

298
00:12:56,300 --> 00:12:57,720
תחביר דמוי אנגלית.

299
00:12:57,720 --> 00:12:59,890
והפשטות היא
סוג של מרתק.

300
00:12:59,890 --> 00:13:02,840
>> אז על קלט של n אלמנטים - כך
רק אומר, הנה מערך.

301
00:13:02,840 --> 00:13:04,000
יש בזה דברים n בו.

302
00:13:04,000 --> 00:13:05,370
זה כל מה שאנחנו אומרים שם.

303
00:13:05,370 --> 00:13:07,560
>> אם n הוא פחות מ 2, לחזור.

304
00:13:07,560 --> 00:13:08,640
אז זה בדיוק המקרה טריוויאלי.

305
00:13:08,640 --> 00:13:12,580
אם n הוא פחות מ 2, אז ברור שזה
1 או 0, ובמקרה זה הדבר

306
00:13:12,580 --> 00:13:14,780
כבר ממוין או לא קיים,
כל כך פשוט לחזור.

307
00:13:14,780 --> 00:13:15,900
אין מה לעשות.

308
00:13:15,900 --> 00:13:18,360
אז זה מקרה פשוט לתלוש.

309
00:13:18,360 --> 00:13:20,110
>> אחר, יש לנו שלושה שלבים.

310
00:13:20,110 --> 00:13:23,650
מיין המחצית השמאלית של האלמנטים, בערך
המחצית הימנית של האלמנטים,

311
00:13:23,650 --> 00:13:26,650
ולאחר מכן למזג את החצאים הממוינים.

312
00:13:26,650 --> 00:13:29,400
מה שמעניין כאן הוא ש
אני סוג של punting, נכון?

313
00:13:29,400 --> 00:13:32,300
יש סוג של הגדרה מעגלית
לאלגוריתם זה.

314
00:13:32,300 --> 00:13:35,986
באיזה מובנת הוא אלגוריתם של זה
חוזר הגדרה?

315
00:13:35,986 --> 00:13:37,850
>> קהל: [לא ברור].

316
00:13:37,850 --> 00:13:41,670
>> מלאן דוד: כן, אלגוריתם המיון שלי,
שניים מהצעדים שלה הם "מעין

317
00:13:41,670 --> 00:13:44,640
משהו. "וכך מעלה את
שאלה, טוב, מה אני הולך להשתמש

318
00:13:44,640 --> 00:13:46,460
כדי למיין את המחצית השמאלית
וחצי הנכון?

319
00:13:46,460 --> 00:13:49,600
וזה היופי כאן שלמרות
שוב, זה מוח כיפוף

320
00:13:49,600 --> 00:13:54,030
חלק פוטנציאלי, אתה יכול להשתמש באותו
אלגוריתם כדי למיין את המחצית השמאלית.

321
00:13:54,030 --> 00:13:54,700
>> אבל חכה רגע.

322
00:13:54,700 --> 00:13:57,070
כשאומר לך למיין
מחצית שמאלית, מה הן שתי

323
00:13:57,070 --> 00:13:58,240
צעדים הולכים להיות הבא בתור?

324
00:13:58,240 --> 00:14:00,550
אנחנו נסדר את חלקו השמאלי של
מחצית שמאלית והימנית

325
00:14:00,550 --> 00:14:01,420
המחצית ממחצית השמאלית.

326
00:14:01,420 --> 00:14:04,430
לעזאזל, איך אני יכול למיין את שני אלה
חצאים, או רבעים, עכשיו?

327
00:14:04,430 --> 00:14:05,260
>> אבל זה בסדר.

328
00:14:05,260 --> 00:14:07,830
יש לנו אלגוריתם מיון כאן.

329
00:14:07,830 --> 00:14:10,660
ואף על פי שאתה יכול לדאוג
הראשון הוא סוג של אינסופי

330
00:14:10,660 --> 00:14:12,780
לולאה, זה מעגל שאף פעם לא
הולך עד סוף - זה הולך

331
00:14:12,780 --> 00:14:15,770
בסופו פעם אחת מה קורה?

332
00:14:15,770 --> 00:14:16,970
ברגע n הוא פחות מ 2.

333
00:14:16,970 --> 00:14:19,180
שסופו של דבר עומד לקרות,
משום שאם ימשיך וחצייה

334
00:14:19,180 --> 00:14:23,020
חצייה בחציית חצאי אלה, בוודאי
סופו של דבר אתה הולך בסופו של

335
00:14:23,020 --> 00:14:25,350
עם רק 1 או 0 אלמנטים.

336
00:14:25,350 --> 00:14:28,500
בשלב, זה שהאלגוריתם
אומר שסיימת.

337
00:14:28,500 --> 00:14:31,020
>> אז הקסם אמיתי בזה
נראה אלגוריתם להיות ב

338
00:14:31,020 --> 00:14:33,470
שהשלב האחרון, מיזוג.

339
00:14:33,470 --> 00:14:37,190
רעיון פשוט שפשוט מתמזג שתיים
דברים, זה מה שסופו של דבר הולך

340
00:14:37,190 --> 00:14:40,920
כדי לאפשר לנו למיין מערך של,
נניח, שמונה אלמנטים.

341
00:14:40,920 --> 00:14:44,410
אז יש לי שמונה כדורים יותר מתח עד
כאן, שמונה חתיכות של נייר, ואחד

342
00:14:44,410 --> 00:14:45,500
גוגל זכוכית -

343
00:14:45,500 --> 00:14:46,140
שבו אני מקבל כדי לשמור.

344
00:14:46,140 --> 00:14:46,960
>> [שחוק]

345
00:14:46,960 --> 00:14:48,970
>> דוד Malan: אם אנחנו יכולים לקחת שמונה
מתנדבים, ובואו נראה אם ​​אנחנו יכולים

346
00:14:48,970 --> 00:14:51,430
לשחק את זה, כל כך.

347
00:14:51,430 --> 00:14:52,500
וואו, אוקיי.

348
00:14:52,500 --> 00:14:53,565
מדעי המחשב הוא מקבל כיף.

349
00:14:53,565 --> 00:14:54,320
בסדר.

350
00:14:54,320 --> 00:14:57,770
אז מה איתך שלוש,
היד הכי גדולה שם למעלה.

351
00:14:57,770 --> 00:14:58,580
ארבעה בחלק האחורי.

352
00:14:58,580 --> 00:15:02,220
ומה הדעה שנעשה לך
שלוש בשורה זו?

353
00:15:02,220 --> 00:15:03,390
וארבעה בחלק הקדמי.

354
00:15:03,390 --> 00:15:04,920
אז אתה שמונה, בחייו.

355
00:15:04,920 --> 00:15:12,060
>> [שחוק]

356
00:15:12,060 --> 00:15:13,450
>> דוד Malan: אני בעצם
לא בטוח מה זה.

357
00:15:13,450 --> 00:15:14,810
האם זה את כדורי לחץ?

358
00:15:14,810 --> 00:15:16,510
מנורות השולחן?

359
00:15:16,510 --> 00:15:18,650
החומר?

360
00:15:18,650 --> 00:15:19,680
האינטרנט?

361
00:15:19,680 --> 00:15:20,160
>> אישור.

362
00:15:20,160 --> 00:15:21,310
אז קדימה למעלה.

363
00:15:21,310 --> 00:15:22,310
מי הייתי רוצה -

364
00:15:22,310 --> 00:15:23,570
לשמור מתקרב.

365
00:15:23,570 --> 00:15:24,240
בואו נראה.

366
00:15:24,240 --> 00:15:26,460
וזה מכניס אותך במיקום -

367
00:15:26,460 --> 00:15:27,940
אתה במקום אחד.

368
00:15:27,940 --> 00:15:28,670
אוי לא, חכה רגע.

369
00:15:28,670 --> 00:15:30,760
1, 2, 3, 4, 5, 6, 7 - אה, טוב.

370
00:15:30,760 --> 00:15:31,310
בסדר, אנחנו טובים.

371
00:15:31,310 --> 00:15:35,130
יש לי בסדר, כך שכולם במושב,
אבל לא על זכוכית גוגל.

372
00:15:35,130 --> 00:15:36,475
תן לי לעמוד בתור אלה.

373
00:15:36,475 --> 00:15:37,115
מה שמך?

374
00:15:37,115 --> 00:15:37,440
>> מישל: מישל.

375
00:15:37,440 --> 00:15:38,090
>> דוד Malan: מישל?

376
00:15:38,090 --> 00:15:42,000
בסדר, אתה מקבל להיראות כמו
החנון, אם זה בסדר.

377
00:15:42,000 --> 00:15:44,625
ובכן, גם אני, אני מניח,
רק לרגע.

378
00:15:44,625 --> 00:15:45,875
בסדר, המתנה.

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
אנחנו מנסים לבוא עם
להשתמש במקרה של גוגל זכוכית, ואנחנו

381
00:15:50,950 --> 00:15:53,750
חשבתי שזה יהיה כיף, רק כדי לעשות
זה כאשר אנשים על הבמה.

382
00:15:53,750 --> 00:15:57,120
אנחנו תתעד את העולם
מנקודת המבט שלהם.

383
00:15:57,120 --> 00:15:58,410
בסדר.

384
00:15:58,410 --> 00:15:59,830
לא כנראה מה שגוגל התכוונה.

385
00:15:59,830 --> 00:16:02,260
בסדר, אם לא אכפת לך ללבוש
זה מביך עבור דקות הבאות,

386
00:16:02,260 --> 00:16:03,150
זה יהיה נפלא.

387
00:16:03,150 --> 00:16:08,620
>> בסדר, אז יש לנו כאן מערך של
אלמנטים, ומערך ה, כמו לכל

388
00:16:08,620 --> 00:16:11,480
פיסות נייר באנשים האלה "
ידי, הוא ללא מיון, ברגע זה.

389
00:16:11,480 --> 00:16:12,050
>> מישל: הו, זה כל כך מוזר.

390
00:16:12,050 --> 00:16:12,810
>> דוד Malan: זה פחות או יותר אקראי.

391
00:16:12,810 --> 00:16:15,760
ובעוד רגע, אנחנו הולכים לנסות
ליישם למזג סוג יחד

392
00:16:15,760 --> 00:16:17,950
ולראות לאן שתובנה היא מפתח.

393
00:16:17,950 --> 00:16:21,970
והטריק כאן עם סוג המיזוג הוא
משהו שלא הנחנו עדיין.

394
00:16:21,970 --> 00:16:24,030
אנחנו באמת צריכים קצת
שטח נוסף.

395
00:16:24,030 --> 00:16:26,650
אז מה הולך להיות במיוחד
מעניין בקשר לזה הוא כי אלה

396
00:16:26,650 --> 00:16:29,270
הבחורים הולכים להסתובב קצת
קצת, כי אני הולך להניח כי

397
00:16:29,270 --> 00:16:31,880
יש מערך נוסף של מרחב,
אומרים, ממש מאחוריהם.

398
00:16:31,880 --> 00:16:34,570
>> אז אם הם מאחורי הכיסא שלהם,
זה המערך משני.

399
00:16:34,570 --> 00:16:36,960
אם הם יושבים כאן, זה
המערך הראשוני.

400
00:16:36,960 --> 00:16:40,170
אבל זה משאב שיש לנו
לא למנף עד כה עם בועה

401
00:16:40,170 --> 00:16:42,040
סוג שהוא, עם מיון בחירה,
עם סוג הכניסה.

402
00:16:42,040 --> 00:16:44,600
כזכור, בשבוע שעבר, כולם פשוט
סוג של דשדש במקום.

403
00:16:44,600 --> 00:16:46,840
הם לא השתמשו בכל זיכרון נוסף.

404
00:16:46,840 --> 00:16:49,310
אנחנו פינינו מקום לאנשים על ידי
התנועה של אנשים מסביב.

405
00:16:49,310 --> 00:16:50,580
>> אז זו תובנה מרכזית, יותר מדי.

406
00:16:50,580 --> 00:16:53,410
יש תחלופה זו, באופן כללי ב
מדעי מחשב, של משאבים.

407
00:16:53,410 --> 00:16:55,800
אם אתה רוצה לזרז משהו
כמו פעם, שאתה הולך

408
00:16:55,800 --> 00:16:56,900
צריך לשלם מחיר.

409
00:16:56,900 --> 00:17:00,750
ואחד מהמחירים האלה הוא לעתים קרובות מאוד
המרחב, כמות הזיכרון או קשה

410
00:17:00,750 --> 00:17:01,700
שטח דיסק שאתה משתמש.

411
00:17:01,700 --> 00:17:03,640
או, למען האמת, את הסכום
זמן מתכנת.

412
00:17:03,640 --> 00:17:06,700
כמה זמן זה לוקח לך, האדם,
למעשה ליישם עוד קצת

413
00:17:06,700 --> 00:17:07,829
אלגוריתם מסובך.

414
00:17:07,829 --> 00:17:09,760
אבל היום, trade-off
הוא זמן ומרחב.

415
00:17:09,760 --> 00:17:11,930
>> אז אם אתם יכולים פשוט להחזיק אותך
מספרים כך שאנו יכולים לראות שאתה

416
00:17:11,930 --> 00:17:15,839
אכן התאמת 4, 2, 6, 1, 3, 7, 8.

417
00:17:15,839 --> 00:17:16,599
מצוין.

418
00:17:16,599 --> 00:17:19,520
אז אני הולך לנסות לתזמר
דברים, אם אתם יכולים פשוט

419
00:17:19,520 --> 00:17:21,800
בעקבות שלי כאן.

420
00:17:21,800 --> 00:17:26,650
>> אז אני הולך ליישם, ראשון,
צעד ראשון של pseudocode, שהוא

421
00:17:26,650 --> 00:17:29,440
על קלט של אלמנטי n, אם n הוא
פחות מ 2, ואז לחזור.

422
00:17:29,440 --> 00:17:31,370
ברור, שאינו
חלים, ולכן אנחנו ממשיכים הלאה.

423
00:17:31,370 --> 00:17:33,340
אז למיין את המחצית השמאלית של האלמנטים.

424
00:17:33,340 --> 00:17:36,220
אז זה אומר שאני הולך להתמקד
תשומת לב לרגע על אלה

425
00:17:36,220 --> 00:17:37,310
ארבע החבר 'ה כאן.

426
00:17:37,310 --> 00:17:39,774
בסדר, מה עליי לעשות הבא?

427
00:17:39,774 --> 00:17:40,570
>> קהל: מיין המחצית השמאלית.

428
00:17:40,570 --> 00:17:42,780
>> דוד Malan: אז עכשיו אני צריך למיין
המחצית השמאלית של החבר 'ה האלה.

429
00:17:42,780 --> 00:17:45,580
כי שוב, להניח לעצמך
מטרה היא כדי למיין את המחצית השמאלית.

430
00:17:45,580 --> 00:17:46,440
איך אתה עושה את זה?

431
00:17:46,440 --> 00:17:49,140
פשוט עקוב אחר ההוראות, גם
למרות שאנחנו עושים את זה שוב.

432
00:17:49,140 --> 00:17:50,160
אז למיין את המחצית השמאלית.

433
00:17:50,160 --> 00:17:52,030
עכשיו אני ממיין שני החבר 'ה האלה.

434
00:17:52,030 --> 00:17:53,563
מה הלאה?

435
00:17:53,563 --> 00:17:54,510
>> קהל: מיין המחצית השמאלית.

436
00:17:54,510 --> 00:17:55,460
>> דוד Malan: מיין המחצית השמאלית.

437
00:17:55,460 --> 00:18:00,680
אז עכשיו אלה, המושב הזה כאן,
רשימה של גודל 1.

438
00:18:00,680 --> 00:18:01,365
ואיך קוראים לך שוב?

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS דייזי: הנסיכה דייזי.

440
00:18:02,390 --> 00:18:03,690
>> דוד Malan: נסיכת דייזי הוא כאן.

441
00:18:03,690 --> 00:18:07,470
ואז היא כבר מסודרים, כי
הרשימה היא בגודל 1.

442
00:18:07,470 --> 00:18:09,490
מה שאני עושה הבא?

443
00:18:09,490 --> 00:18:13,680
אוקיי, תחזור, משום שהרשימה היא של
גודל 1, שהוא פחות מ 2.

444
00:18:13,680 --> 00:18:14,320
אז מה הצעד הבא?

445
00:18:14,320 --> 00:18:17,490
ועכשיו שיש לך סוג של
לסגת בראש שלך.

446
00:18:17,490 --> 00:18:19,340
>> מיין המחצית הימנית, שהיא -

447
00:18:19,340 --> 00:18:19,570
מה השם שלך?

448
00:18:19,570 --> 00:18:20,220
>> לינדה: לינדה.

449
00:18:20,220 --> 00:18:20,980
>> דוד Malan: לינדה.

450
00:18:20,980 --> 00:18:23,210
ולכן מה שאנחנו עושים עכשיו, כי
יש לנו רשימה של גודל 1?

451
00:18:23,210 --> 00:18:24,440
>> קהל: שבות.

452
00:18:24,440 --> 00:18:24,760
>> דוד Malan: זהירות.

453
00:18:24,760 --> 00:18:29,540
אנחנו חוזרים ראשון, ועכשיו שלישי
צעד - ואם אני סוג של מתאר אותו על ידי

454
00:18:29,540 --> 00:18:33,490
מחבק את שני המושבים עכשיו, עכשיו אני
צריך למזג את שני האלמנטים הללו.

455
00:18:33,490 --> 00:18:35,530
אז עכשיו למרבה הצער, את האלמנטים
הם מקולקלים.

456
00:18:35,530 --> 00:18:39,920
אבל זה מקום שבו תהליך המיזוג
מתחיל להיות משכנע.

457
00:18:39,920 --> 00:18:42,410
>> אז אם אתם יכולים לעמוד על של ממש
רגע, אני הולך צריך אותך, ב

458
00:18:42,410 --> 00:18:44,170
רגע, לצעד מאחורי הכיסא שלך.

459
00:18:44,170 --> 00:18:46,480
ואם לינדה, כי 2 הוא
קטן מ 4, למה לא

460
00:18:46,480 --> 00:18:48,130
אתה בא סביב ראשון?

461
00:18:48,130 --> 00:18:48,690
להישאר שם.

462
00:18:48,690 --> 00:18:50,520
אז לינדה, אתה בא סביב ראשון.

463
00:18:50,520 --> 00:18:53,820
>> עכשיו במציאות אם זה רק מערך
אנחנו רק יכולים להעביר אותה בזמן אמת

464
00:18:53,820 --> 00:18:55,360
מהכיסא הזה למקום הזה.

465
00:18:55,360 --> 00:18:57,770
אז דמיין שלקח חלק קבוע
מספר השלבים 1.

466
00:18:57,770 --> 00:18:58,480
ועכשיו -

467
00:18:58,480 --> 00:19:01,490
אבל אנחנו צריכים לשים אותך ב
המיקום הראשון כאן.

468
00:19:01,490 --> 00:19:03,930
>> ועכשיו אם אתה יכול לבוא מסביב,
וכן, אנחנו הולכים

469
00:19:03,930 --> 00:19:06,300
להיות במקום שני.

470
00:19:06,300 --> 00:19:09,120
ולמרות שזה מרגיש כאילו זה
לוקח זמן מה, מה שנחמד כרגע הוא

471
00:19:09,120 --> 00:19:14,710
כי במחצית השמאלית של
מחצית שמאלית כעת מסודרים.

472
00:19:14,710 --> 00:19:18,010
אז מה היה הצעד הבא, אם אנחנו עכשיו
להריץ אחורה עוד יותר בסיפור?

473
00:19:18,010 --> 00:19:18,980
>> קהל: מחצית ימנית.

474
00:19:18,980 --> 00:19:19,900
>> דוד Malan: מיין חצי הנכונה.

475
00:19:19,900 --> 00:19:21,320
אז אתם חייבים לעשות את זה, גם כן.

476
00:19:21,320 --> 00:19:23,510
אז אם אתה יכול לקום
רק לרגע?

477
00:19:23,510 --> 00:19:25,192
ואיך קוראים לך?

478
00:19:25,192 --> 00:19:25,540
>> JESS: ג'ס.

479
00:19:25,540 --> 00:19:25,870
>> דוד Malan: ג'ס.

480
00:19:25,870 --> 00:19:29,720
אוקיי, אז ג'ס הוא עכשיו השמאל
המחצית ממחצית הימנית.

481
00:19:29,720 --> 00:19:31,400
וכדי שהיא רשימה של גודל 1.

482
00:19:31,400 --> 00:19:32,380
זה ברור שהיא מסודרים.

483
00:19:32,380 --> 00:19:33,070
ואת השם שלך שוב?

484
00:19:33,070 --> 00:19:33,630
>> מישל: מישל.

485
00:19:33,630 --> 00:19:35,340
>> דוד Malan: מישל היא ללא ספק
רשימה של גודל 1.

486
00:19:35,340 --> 00:19:36,050
היא כבר מסודרת.

487
00:19:36,050 --> 00:19:38,690
אז עכשיו את הקסם קורה,
תהליך המיזוג.

488
00:19:38,690 --> 00:19:39,790
אז מי הולך לבוא קודם?

489
00:19:39,790 --> 00:19:41,560
ברור שמישל.

490
00:19:41,560 --> 00:19:43,280
אז אם אתה יכול לבוא בחזרה.

491
00:19:43,280 --> 00:19:47,090
המרחב שיש לנו זמין עבורה עכשיו
הוא בדיוק מאחורי הכיסא הזה כאן.

492
00:19:47,090 --> 00:19:51,580
ועכשיו אם אתה יכול לחזור, כמו גם,
עכשיו יש לנו, כדי שיהיו ברור, שתיים

493
00:19:51,580 --> 00:19:53,810
חצאים, כל אחד בגודל 2 -

494
00:19:53,810 --> 00:19:57,090
ורק למען התיאור, אם אתה
אפשר לעשות קצת מרחב -

495
00:19:57,090 --> 00:19:59,780
אחד השאיר חצי כאן, אחד
מחצית ממש כאן.

496
00:19:59,780 --> 00:20:01,160
>> להריץ אחורה עוד יותר בסיפור.

497
00:20:01,160 --> 00:20:02,270
מה הצעד בא?

498
00:20:02,270 --> 00:20:03,030
>> קהל: מיזוג.

499
00:20:03,030 --> 00:20:04,160
>> דוד Malan: אז עכשיו יש לנו מיזוג.

500
00:20:04,160 --> 00:20:07,490
אז אוקיי, אז עכשיו, תודה לאל, אנחנו
רק שחרר את ארבעה כיסאות.

501
00:20:07,490 --> 00:20:11,480
אז יש לנו בשימוש כפליים זיכרון, אבל
אנחנו יכולים לתת והתלבטות בין

502
00:20:11,480 --> 00:20:12,330
שני המערכים.

503
00:20:12,330 --> 00:20:14,190
אז איזה מספר הוא במקום ראשון?

504
00:20:14,190 --> 00:20:14,850
אז מישל, כמובן.

505
00:20:14,850 --> 00:20:16,680
אז לבוא ולקחת
המושב שלך כאן.

506
00:20:16,680 --> 00:20:19,120
ואז מספר 2 הוא ללא ספק
הבא, כך שאתה בא לכאן.

507
00:20:19,120 --> 00:20:21,520
מספר 4, מספר 6.

508
00:20:21,520 --> 00:20:23,390
ושוב, למרות שיש
קצת הליכה מעורבת,

509
00:20:23,390 --> 00:20:26,010
באמת, אלה יכולים לקרות באופן מיידי,
על ידי הזזת אחד -

510
00:20:26,010 --> 00:20:26,880
אוקיי, שיחק טוב.

511
00:20:26,880 --> 00:20:28,350
>> [שחוק]

512
00:20:28,350 --> 00:20:29,680
>> דוד Malan: ועכשיו אנחנו
במצב די טוב.

513
00:20:29,680 --> 00:20:34,910
המחצית השמאלית של כל
קלט כבר מסודרים עכשיו.

514
00:20:34,910 --> 00:20:37,370
בסדר, אז החבר 'ה האלה היה
היתרון שלי -

515
00:20:37,370 --> 00:20:40,340
איך זה בסופו של כל הבנות על
עזב את מקום ואת כל הבנים בצד ימין?

516
00:20:40,340 --> 00:20:42,450
>> אוקיי, אז חבר 'ה "תור עכשיו.

517
00:20:42,450 --> 00:20:44,680
אז אני לא תעבור
את השלבים הבאים.

518
00:20:44,680 --> 00:20:46,550
נצטרך לראות אם אנחנו יכולים להחיל מחדש
אותו pseudocode.

519
00:20:46,550 --> 00:20:50,050
אם אתה רוצה להמשיך ולקום,
וחבר 'ה, תן לי לתת לך את המיקרופון.

520
00:20:50,050 --> 00:20:52,990
תראה אם ​​אתה לא יכול לשכפל את מה
אנחנו פשוט עשינו כאן על

521
00:20:52,990 --> 00:20:53,880
קצה שני של הרשימה.

522
00:20:53,880 --> 00:20:59,530
מי צריך לדבר ראשון,
המבוסס על האלגוריתם?

523
00:20:59,530 --> 00:21:03,210
אז תסביר מה אתה עושה לפני
אתה עושה את כל תנועות ברגל.

524
00:21:03,210 --> 00:21:05,930
>> רמקול 1: בסדר, אז שכן
אני המחצית השמאלית של

525
00:21:05,930 --> 00:21:07,790
מחצית שמאלית, אני חוזר.

526
00:21:07,790 --> 00:21:08,730
נכון?

527
00:21:08,730 --> 00:21:09,250
>> דוד Malan: טוב.

528
00:21:09,250 --> 00:21:10,350
>> רמקול 1: ואז -

529
00:21:10,350 --> 00:21:11,800
>> דוד Malan: מי עושה
המיקרופון ללכת הלאה?

530
00:21:11,800 --> 00:21:12,920
>> רמקול 1: המספר הבא.

531
00:21:12,920 --> 00:21:14,720
>> רמקול 2: אז אני חצי נכון
של המחצית השמאלית של

532
00:21:14,720 --> 00:21:17,830
מחצית שמאלית, ואני חוזר.

533
00:21:17,830 --> 00:21:18,050
>> דוד Malan: טוב.

534
00:21:18,050 --> 00:21:18,550
אתה חוזר.

535
00:21:18,550 --> 00:21:21,855
אז עכשיו מה עד הבא לשניכם?

536
00:21:21,855 --> 00:21:23,740
>> רמקול 2: אנחנו רוצים לראות מי קטנים יותר.

537
00:21:23,740 --> 00:21:24,200
>> דוד Malan: בדיוק.

538
00:21:24,200 --> 00:21:24,940
אנחנו רוצים למזג.

539
00:21:24,940 --> 00:21:27,590
השטח שאנחנו הולכים להשתמש כדי למזג
אותך ל, למרות שהם

540
00:21:27,590 --> 00:21:30,250
ברור שמסודרים כבר, אנחנו הולכים
כדי לבצע את אותו האלגוריתם.

541
00:21:30,250 --> 00:21:31,560
אז מי הולך בגב הראשון?

542
00:21:31,560 --> 00:21:35,720
אז 3, ולאחר מכן 7.

543
00:21:35,720 --> 00:21:38,570
ועכשיו המיקרופון עובר
החבר 'ה האלה, בסדר?

544
00:21:38,570 --> 00:21:43,590
>> רמקול 3: אז אני מחצית מימין
מחצית שמאלית, וn שלי היא פחות מ

545
00:21:43,590 --> 00:21:45,048
1, אז אני פשוט הולך לעבור -

546
00:21:45,048 --> 00:21:46,380
>> דוד Malan: טוב.

547
00:21:46,380 --> 00:21:49,450
>> הרמקול 4: אני חצי מימין
מחצית ימנית של החצי הימני, ואני

548
00:21:49,450 --> 00:21:51,740
גם אדם אחד, ולכן אני
הולך לחזור.

549
00:21:51,740 --> 00:21:52,990
אז עכשיו אנחנו מיזוג.

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> רמקול 3: אז אנחנו הולכים אחורה.

552
00:21:56,150 --> 00:21:57,160
>> דוד Malan: אז אתה הולך לחלק האחורי.

553
00:21:57,160 --> 00:21:59,200
אז 5 הולך ראשונה, ולאחר מכן 8.

554
00:21:59,200 --> 00:22:01,240
ועכשיו קהל, שהוא
צעד שאנו צריכים עכשיו לחזור אחורה

555
00:22:01,240 --> 00:22:02,200
לגבות במוחנו?

556
00:22:02,200 --> 00:22:02,940
>> קהל: מיזוג.

557
00:22:02,940 --> 00:22:07,270
>> דוד Malan: מחצית שמאלית מיזוג ונכון
מחצית מהמחצית השמאלית המקורית.

558
00:22:07,270 --> 00:22:08,840
אז עכשיו -

559
00:22:08,840 --> 00:22:10,520
ורק כדי להבהיר זאת,
לעשות קצת שטח

560
00:22:10,520 --> 00:22:11,690
בינך שני בחורים.

561
00:22:11,690 --> 00:22:13,800
אז עכשיו זה שתי הרשימות,
משמאל ומימין.

562
00:22:13,800 --> 00:22:18,320
אז איך אנחנו עכשיו למזג אתכם לתוך
מושבי השורה הראשונה שוב?

563
00:22:18,320 --> 00:22:19,600
>> 3 הולך ראשונה.

564
00:22:19,600 --> 00:22:20,850
ואז 5, כמובן.

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
לאחר מכן 7, ועכשיו 8.

567
00:22:27,330 --> 00:22:28,710
אוקיי, ועכשיו אנחנו?

568
00:22:28,710 --> 00:22:29,650
>> קהל: לא נעשה.

569
00:22:29,650 --> 00:22:32,440
>> מלאן דוד: לא עשה, כי
ללא ספק, יש צעד אחד שנותר.

570
00:22:32,440 --> 00:22:35,720
אבל שוב, סיבה שאני משתמש בזה
ז'רגון כמו "אחורה בראש שלך",

571
00:22:35,720 --> 00:22:37,160
זה בגלל שזה באמת
מה קורה.

572
00:22:37,160 --> 00:22:39,610
אנחנו עוברים את כל השלבים האלה,
אבל אנחנו סוג של השהיית עבור

573
00:22:39,610 --> 00:22:42,480
רגע, צלילה עמוקה יותר אל תוך
אלגוריתם, עוצר לרגע,

574
00:22:42,480 --> 00:22:45,840
צלילה עמוקה לתוך האלגוריתם, ו
עכשיו אנחנו צריכים למיין מאחורה בנו

575
00:22:45,840 --> 00:22:49,430
מוחם ולבטל את כל השכבות האלה
שיש לנו סוג של להמתנה.

576
00:22:49,430 --> 00:22:51,790
>> אז עכשיו יש לנו שתי רשימות בגודל 4.

577
00:22:51,790 --> 00:22:54,790
אם אתם יכולים לעמוד בפעם האחרונה
ולעשות קצת מרחב לכאן

578
00:22:54,790 --> 00:22:57,230
להבהיר שזה השמאל
מחצית ממקורית,

579
00:22:57,230 --> 00:22:58,620
מחצית ימנית של המקור.

580
00:22:58,620 --> 00:23:01,060
מי המספר הראשון שאנחנו
צריך למשוך לחלק האחורי?

581
00:23:01,060 --> 00:23:01,870
מישל, כמובן.

582
00:23:01,870 --> 00:23:03,230
>> אז אנחנו שמים את מישל כאן.

583
00:23:03,230 --> 00:23:05,080
ומי שיש לי מספר 2?

584
00:23:05,080 --> 00:23:06,440
מספר 2 מגיע על גב גם כן.

585
00:23:06,440 --> 00:23:07,800
מספר 3?

586
00:23:07,800 --> 00:23:08,510
מצוין.

587
00:23:08,510 --> 00:23:16,570
מספר 4, מספר 5, מספר 6,
מספר 7, ואת מספר 8.

588
00:23:16,570 --> 00:23:18,850
>> אוקיי, אז זה הרגיש כמו הרבה
של צעדים, זה בטוח.

589
00:23:18,850 --> 00:23:22,390
אבל עכשיו בואו נראה אם ​​אנחנו לא יכולים לאשר
סוג של אופן אינטואיטיבי שזה

590
00:23:22,390 --> 00:23:26,190
אלגוריתם בסיסי, במיוחד כאשר
n נהיה ממש גדול, כפי שראינו

591
00:23:26,190 --> 00:23:29,170
עם האנימציות, הוא
ביסודו מהר יותר.

592
00:23:29,170 --> 00:23:33,400
אז אני טוען שאלגוריתם זה, במקרה הגרוע
מקרה ואפילו במקרה הטוב ביותר,

593
00:23:33,400 --> 00:23:36,160
הוא גדול O של n הפעמים log n.

594
00:23:36,160 --> 00:23:39,160
כלומר, יש היבט כלשהו של זה
אלגוריתם שלוקח צעדי n, אבל

595
00:23:39,160 --> 00:23:43,110
יש עוד היבט אי שם ב
איטרציה ש, לולאות ש, כי

596
00:23:43,110 --> 00:23:44,410
נוקט צעדי n יומן.

597
00:23:44,410 --> 00:23:49,154
האם אנחנו יכולים לשים את אצבענו על מה אלה
שני מספרים מתייחסים?

598
00:23:49,154 --> 00:23:51,320
ובכן, שבו -

599
00:23:51,320 --> 00:23:54,160
לאן הלך את המיקרופון?

600
00:23:54,160 --> 00:23:58,660
>> רמקול 1: האם להיכנס n להיות
לשבור אותנו לשניים -

601
00:23:58,660 --> 00:23:59,630
החלוקה לשתיים, למעשה.

602
00:23:59,630 --> 00:24:00,120
>> דוד Malan: בדיוק.

603
00:24:00,120 --> 00:24:03,000
בכל פעם שאנו רואים בכל אלגוריתם ובכך
כה, יש כבר את הדפוס הזה של

604
00:24:03,000 --> 00:24:04,200
החלוקה, החלוקה, חילוק.

605
00:24:04,200 --> 00:24:05,700
וזה בדרך כלל הוא מצטמצם
למשהו שהוא

606
00:24:05,700 --> 00:24:07,100
לוגריתמי, יומן בסיס 2.

607
00:24:07,100 --> 00:24:10,180
אבל זה באמת יכול להיות כל דבר,
אבל להיכנס בסיס 2.

608
00:24:10,180 --> 00:24:11,330
>> עכשיו מה עם n?

609
00:24:11,330 --> 00:24:14,550
אני יכול לראות שאנחנו סוג של מחולקים
חבר 'ה - חילק לך, חילק לך,

610
00:24:14,550 --> 00:24:15,910
חילק לך, חילק לך.

611
00:24:15,910 --> 00:24:18,760
איפה הסוף בא?

612
00:24:18,760 --> 00:24:19,810
>> אז זה המיזוג.

613
00:24:19,810 --> 00:24:20,610
כי תחשוב על זה.

614
00:24:20,610 --> 00:24:25,420
בעת מיזוג שמונה אנשים יחד,
לפי מחצית מהם היא סדרה של ארבעה

615
00:24:25,420 --> 00:24:27,770
ואת החצי השני הוא עוד
סט של ארבעה, איך אתה הולך

616
00:24:27,770 --> 00:24:28,820
על עושה את המיזוג?

617
00:24:28,820 --> 00:24:30,830
ובכן, אתם עשית את זה
למדי באופן אינטואיטיבי.

618
00:24:30,830 --> 00:24:34,140
>> אבל אם אני במקום עשיתי את זה קצת יותר
באופן שיטתי, שאולי הצביע על

619
00:24:34,140 --> 00:24:38,090
האדם השמאלי הראשון עם השמאל שלי
לעומת זאת, הצביע על האדם השמאלי ביותר

620
00:24:38,090 --> 00:24:42,080
של מחצית שעם יד הימין שלי, ו
רק לאחר מכן עברתי

621
00:24:42,080 --> 00:24:46,990
רשימה, מצביעה על האלמנט הקטן ביותר
בכל פעם, העברת האצבע שלי שוב ו

622
00:24:46,990 --> 00:24:48,970
על פי צורך בכל הרשימה.

623
00:24:48,970 --> 00:24:51,890
אבל מה לגבי זה מפתח מיזוג
תהליך הוא אני משווה זוגות אלה

624
00:24:51,890 --> 00:24:53,460
של אלמנטים.

625
00:24:53,460 --> 00:24:57,270
מהמחצית הימנית ומהשמאל
מחצית, אף פעם לא מנסה לשחזר את מסלול פעם אחת.

626
00:24:57,270 --> 00:25:00,570
>> אז הוא לוקח את עצמו המיזוג
לא יותר מ n צעדים.

627
00:25:00,570 --> 00:25:03,250
וכמה פעמים עשו לי
כדי לעשות את זה מיזוג?

628
00:25:03,250 --> 00:25:07,150
ובכן, לא יותר מ n, ואנחנו רק
ראיתי שעם המיזוג הסופי.

629
00:25:07,150 --> 00:25:13,120
ואז אם אתה עושה משהו שלוקח
היכנס צעדי n n פעמים, או להיפך,

630
00:25:13,120 --> 00:25:15,210
זה הולך לתת לנו פעמים n log n.

631
00:25:15,210 --> 00:25:16,310
>> ולמה זה טוב יותר?

632
00:25:16,310 --> 00:25:19,600
ובכן, אם אנחנו כבר יודעים שיומן
n הוא טוב יותר מאשר n - נכון?

633
00:25:19,600 --> 00:25:22,590
שראינו בחיפוש בינארי, ספר טלפונים
למשל, יומן n היה בהחלט

634
00:25:22,590 --> 00:25:23,760
טוב יותר מאשר ליניארי.

635
00:25:23,760 --> 00:25:28,420
אז זה אומר n פעמים יומן n הוא
בהחלט טוב יותר מn פעמים אחרת

636
00:25:28,420 --> 00:25:30,390
n, AKA N בריבוע.

637
00:25:30,390 --> 00:25:32,400
וזה מה שאנחנו מרגישים סופו של דבר.

638
00:25:32,400 --> 00:25:34,928
>> סיבוב כל כך גדול של מחיאות כפיים, אם
אנחנו יכולים, לאנשים האלה.

639
00:25:34,928 --> 00:25:38,920
>> [מחיאות כפות]

640
00:25:38,920 --> 00:25:41,550
>> דוד Malan: ומתנות הפרידה שלך -
אתה יכול לשמור את המספרים,

641
00:25:41,550 --> 00:25:44,010
אם ברצונך.

642
00:25:44,010 --> 00:25:45,620
ומתנת הפרידה שלך, כרגיל.

643
00:25:45,620 --> 00:25:47,290
אה, ואנו שולחים לך
את הסרט, מישל.

644
00:25:47,290 --> 00:25:48,343
תודה.

645
00:25:48,343 --> 00:25:49,250
בסדר.

646
00:25:49,250 --> 00:25:50,400
לעזור לעצמך לכדור לחץ.

647
00:25:50,400 --> 00:25:54,110
>> ובואו להרים אותי, בינתיים,
חבר רוב אודן להציע

648
00:25:54,110 --> 00:25:59,520
נקודת מבט קצת שונה על זה,
מאז שאתה יכול לחשוב על אלה

649
00:25:59,520 --> 00:26:01,280
צעדים שקורים במידה מסוימת
דרך אחרת.

650
00:26:01,280 --> 00:26:04,750
למעשה, הגדרה למה רוב של כ
כדי להראות לנו מניח שיש לנו

651
00:26:04,750 --> 00:26:09,030
עשה את החלוקה של כבר
רשימה גדולה לשמונה רשימות קטנות,

652
00:26:09,030 --> 00:26:10,570
כל אחד בגודל 1.

653
00:26:10,570 --> 00:26:13,350
>> אז אנחנו משנים את pseudocode
קצת רק כדי למיין של לקבל ב

654
00:26:13,350 --> 00:26:15,320
הרעיון מרכזי של כמה עבודות מיזוג.

655
00:26:15,320 --> 00:26:17,600
אבל זמן הריצה של מה
הוא עומד לעשות הוא עדיין

656
00:26:17,600 --> 00:26:19,110
הולך להיות אותו הדבר.

657
00:26:19,110 --> 00:26:23,540
ושוב, ההגדרה כאן היא שהוא
התחיל עם שמונה רשימות של גודל 1.

658
00:26:23,540 --> 00:26:27,730
אז אתה כבר פספסת את החלק שבו הוא
למעשה עשה את היומן n, log n, log n

659
00:26:27,730 --> 00:26:31,205
החלוקה של הקלט.

660
00:26:31,205 --> 00:26:32,120
>> [השמעת וידאו]

661
00:26:32,120 --> 00:26:33,615
>> -זה צעד אחד לזה.

662
00:26:33,615 --> 00:26:38,270
עבור שלב השני, שוב ושוב
למזג זוגות של רשימות.

663
00:26:38,270 --> 00:26:39,210
>> דוד Malan: הממ.

664
00:26:39,210 --> 00:26:41,270
אודיו בלבד מגיעים
מתוך המחשב שלי.

665
00:26:41,270 --> 00:26:42,520
בואו ננסה את זה שוב.

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>> באופן שרירותי, רק לבחור את -
עכשיו יש לנו ארבע רשימות.

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
למד בעבר.

670
00:26:52,120 --> 00:26:53,040
>> מלאן דוד: יש לנו ללכת.

671
00:26:53,040 --> 00:27:00,510
>> 108-מיזוג ו15, אנחנו בסופו
עם הרשימה 15, 108.

672
00:27:00,510 --> 00:27:07,170
מיזוג 50 ו -4, אנחנו
בסופו של דבר עם 4, 50.

673
00:27:07,170 --> 00:27:12,990
התמזגות 8 ו -42, אנחנו
בסופו של דבר עם 8, 42.

674
00:27:12,990 --> 00:27:19,970
ומיזוג של 23 ו -16, אנחנו
בסופו של דבר עם 16, 23.

675
00:27:19,970 --> 00:27:23,270
>> עכשיו כל הרשימות שלנו הן בגודל 2.

676
00:27:23,270 --> 00:27:26,690
שים לב שכל אחד מ
ארבע רשימות ממוינות.

677
00:27:26,690 --> 00:27:29,450
אז אנחנו יכולים להתחיל מיזוג
זוגות של רשימות שוב.

678
00:27:29,450 --> 00:27:38,420
מיזוג 15 ו108 ו 4 ו -50, אנחנו
הראשונה לקחת 4, אז 15, ולאחר מכן

679
00:27:38,420 --> 00:27:41,500
50, אז 108.

680
00:27:41,500 --> 00:27:50,610
התמזגות 8, 42 ו -16, 23, ראשון שאנחנו לוקחים
8, ולאחר מכן 16, ולאחר מכן 23,

681
00:27:50,610 --> 00:27:52,700
לאחר מכן 42.

682
00:27:52,700 --> 00:27:57,600
>> אז עכשיו יש לנו רק שתי רשימות של גודל
4, כל אחד מהם הוא מיון.

683
00:27:57,600 --> 00:28:01,170
אז עכשיו אנחנו למזג את שתי הרשימות האלה.

684
00:28:01,170 --> 00:28:11,835
ראשית, עלינו לקחת את 4, אז אנחנו לוקחים את
8, ולאחר מכן אנחנו לוקחים 15, ואז 16, ולאחר מכן

685
00:28:11,835 --> 00:28:19,456
23, אז 42, אז 50, אז 108.

686
00:28:19,456 --> 00:28:19,872
>> [השמעת וידאו הסוף]

687
00:28:19,872 --> 00:28:23,430
>> דוד Malan: שוב, שים לב, הוא מעולם לא
נגע בכוס נתנה יותר מפעם אחת

688
00:28:23,430 --> 00:28:24,860
לאחר ההתקדמות מעבר לו.

689
00:28:24,860 --> 00:28:26,200
אז הוא אף פעם לא חוזר.

690
00:28:26,200 --> 00:28:29,850
אז הוא תמיד זז לצד,
וזה שבו אנחנו חייבים n שלנו.

691
00:28:29,850 --> 00:28:33,290
>> למה לא לתת לי למשוך את אנימציה אחד
שראינו קודם לכן, אבל הפעם

692
00:28:33,290 --> 00:28:35,110
התמקדות רק על סוג המיזוג.

693
00:28:35,110 --> 00:28:38,030
תנו לי להמשיך ולהגדיל את התצוגה
על זה כאן.

694
00:28:38,030 --> 00:28:42,530
ראשית הרשו לי לבחור קלט אקראי,
להגדיל את זה, ואתה יכול למיין של לראות

695
00:28:42,530 --> 00:28:46,600
מה שאנחנו לקחנו כמובן מאליו, קודם לכן,
מיין למזג הוא עושה בפועל.

696
00:28:46,600 --> 00:28:50,330
>> אז שם לב שאתה מקבל את החצאים הללו או
רבעונים אלה או אלה של השמיניות

697
00:28:50,330 --> 00:28:53,140
בעיה שפתאום
מתחיל לקבל צורה טובה.

698
00:28:53,140 --> 00:28:57,070
ולבסוף, אתה רואה ב
ממש בסוף שבום,

699
00:28:57,070 --> 00:28:58,860
הכל התמזג יחד.

700
00:28:58,860 --> 00:29:01,690
>> אז אלה הם פשוט שונים שלושה
לוקח על אותו הרעיון.

701
00:29:01,690 --> 00:29:05,980
אבל תובנה המרכזית, בדיוק כמו פער
ולכבוש בכיתה הראשונה,

702
00:29:05,980 --> 00:29:10,640
היה שהחלטנו לחלק איכשהו
הבעיה למשהו גדול, ל

703
00:29:10,640 --> 00:29:14,760
משהו מעין זהה ברוחו,
אבל קטן יותר וקטן יותר ויותר

704
00:29:14,760 --> 00:29:15,660
וקטן יותר.

705
00:29:15,660 --> 00:29:18,420
>> עכשיו עוד דרך מהנה כדי למיין של חושב
על אלה, למרות שזה לא

706
00:29:18,420 --> 00:29:20,520
הולך לתת לך את אותו אינטואיטיבי
הבנה, היא

707
00:29:20,520 --> 00:29:21,640
האנימציה הבאה.

708
00:29:21,640 --> 00:29:25,400
אז זה מישהו וידאו להרכיב
שקשור שונה

709
00:29:25,400 --> 00:29:29,970
צלילים עם הפעולות השונות עבור
מיין הכנסה, לסוג המיזוג, ו

710
00:29:29,970 --> 00:29:31,150
לכמה אחרים.

711
00:29:31,150 --> 00:29:32,330
אז ברגע אחד, אני הולך להכות Play.

712
00:29:32,330 --> 00:29:33,600
זה עניין של דקות ארוכות.

713
00:29:33,600 --> 00:29:37,410
ולמרות שאתה עדיין יכול לראות את
דפוסים קורים, זה זמן שאתה יכול

714
00:29:37,410 --> 00:29:41,420
גם לשמוע איך האלגוריתמים האלה הם
ביצוע שונה ועם

715
00:29:41,420 --> 00:29:43,950
דפוסים שונים במקצת.

716
00:29:43,950 --> 00:29:45,830
>> זהו סוג כניסה.

717
00:29:45,830 --> 00:29:50,400
>> [TONES PLAYING]

718
00:29:50,400 --> 00:29:52,400
>> דוד Malan: זה שוב מנסה
להכניס כל רכיב

719
00:29:52,400 --> 00:29:52,900
לשם הוא שייך.

720
00:29:52,900 --> 00:29:54,628
זה מיון בועות.

721
00:29:54,628 --> 00:30:10,097
>> [TONES PLAYING]

722
00:30:10,097 --> 00:30:13,630
>> מלאן דוד: ואתה יכול למיין של תחושה
כמה מעט יחסית לעבוד הוא עושה

723
00:30:13,630 --> 00:30:15,834
על כל צעד ושעל.

724
00:30:15,834 --> 00:30:20,470
זה מה שנשמע כמו שעמום.

725
00:30:20,470 --> 00:30:21,472
>> [TONES PLAYING]

726
00:30:21,472 --> 00:30:25,222
>> דוד Malan: זהו מיון בחירה,
שבו אנו בוחרים את האלמנט שאנו רוצים על ידי

727
00:30:25,222 --> 00:30:28,845
עובר שוב ושוב ושוב
ולשים אותו בהתחלה.

728
00:30:28,845 --> 00:30:37,674
>> [TONES PLAYING]

729
00:30:37,674 --> 00:30:43,970
>> דוד Malan: זהו סוג המיזוג, אשר
באמת אתה יכול להתחיל להרגיש.

730
00:30:43,970 --> 00:30:51,810
>> [TONES PLAYING]

731
00:30:51,810 --> 00:30:54,770
>> [שחוק]

732
00:30:54,770 --> 00:30:58,395
>> דוד Malan: משהו שנקרא GNOME
סוג שהוא, שיש לנו לא הסתכל.

733
00:30:58,395 --> 00:31:13,630
>> [TONES PLAYING]

734
00:31:13,630 --> 00:31:17,910
>> דוד Malan: אז תן לי לראות, עכשיו,
הסיח את הדעה כמו שאתה מקווה שהם על ידי

735
00:31:17,910 --> 00:31:21,110
מוסיקה, אם אני יכול להחליק מעט
קצת מתמטיקה בכאן.

736
00:31:21,110 --> 00:31:24,850
אז יש דרך שנוכל רביעית
לחשוב על מה זה אומר אלה

737
00:31:24,850 --> 00:31:29,210
פונקציות להיות מהיר יותר מאשר אלה
שלא ראו קודם.

738
00:31:29,210 --> 00:31:32,470
ואם אתה בא בקורס מ
רקע במתמטיקה, אתה

739
00:31:32,470 --> 00:31:36,030
בעצם אולי כבר יודע שאתה
יכול לסטור טווח בטכניקה זו -

740
00:31:36,030 --> 00:31:40,400
כלומר רקורסיה, פונקציה
שאיכשהו קורא לעצמו.

741
00:31:40,400 --> 00:31:44,780
>> ושוב, תזכור שסוג המיזוג
pseudocode היה רקורסיבית במובן

742
00:31:44,780 --> 00:31:48,460
כי אחד מצעדיו של מיזוג המיון
היה קורא לסוג -

743
00:31:48,460 --> 00:31:49,740
כלומר, את עצמו.

744
00:31:49,740 --> 00:31:52,480
אבל לשמחתי, כי אנחנו כל הזמן
קוראים סוג שהוא, או למזג מיון,

745
00:31:52,480 --> 00:31:55,880
באופן ספציפי, על קטן יותר ויותר
ורשימה קטנה יותר, שסופו של דבר

746
00:31:55,880 --> 00:32:00,005
הודות לתחתית למה שאנחנו קוראים
מקרה בסיס, המקרה קשה המקודד ש

747
00:32:00,005 --> 00:32:04,270
אמר שאם הרשימה היא קטנה, פחות מ 2
במקרה כזה, פשוט לחזור באופן מיידי.

748
00:32:04,270 --> 00:32:07,550
אם לא היה לנו מקרה מיוחד זה,
אלגוריתם לעולם לא תחתון החוצה,

749
00:32:07,550 --> 00:32:11,010
ואכן היית מקבל לתוך
לולאה אינסופית באמת לנצח.

750
00:32:11,010 --> 00:32:14,330
>> אבל נניח שאנחנו רוצים עכשיו לשים
כמה מספרים על זה, שוב, תוך שימוש בחנקן

751
00:32:14,330 --> 00:32:15,660
כגודל הקלט.

752
00:32:15,660 --> 00:32:18,680
ואני רציתי לשאול אותך, מה זה
הזמן הכולל המעורבים

753
00:32:18,680 --> 00:32:19,800
פועל סוג מיזוג?

754
00:32:19,800 --> 00:32:22,960
או באופן כללי יותר, מה זה
העלות של זה בזמן?

755
00:32:22,960 --> 00:32:24,730
>> ובכן זה די קל למדוד את זה.

756
00:32:24,730 --> 00:32:29,010
אם n הוא פחות מ 2, הפעם מעורב
במיון אלמנטי n,

757
00:32:29,010 --> 00:32:30,480
כאשר n הוא 2, הוא 0.

758
00:32:30,480 --> 00:32:31,410
כי אנחנו פשוט לחזור.

759
00:32:31,410 --> 00:32:32,510
אין שום עבודה שצריך לעשות.

760
00:32:32,510 --> 00:32:35,660
כעת ניתן לטעון, אולי זה צעד אחד או שתיים
צעדים כדי להבין את כמות

761
00:32:35,660 --> 00:32:38,420
עובד, אבל זה קרוב מספיק כדי ש0
אני רק הולך להגיד לא עבודה היא

762
00:32:38,420 --> 00:32:40,940
נדרש אם הרשימה היא כל כך קטנה
להיות לא מעניין.

763
00:32:40,940 --> 00:32:42,580
>> אבל במקרה זה הוא מעניין.

764
00:32:42,580 --> 00:32:47,320
המקרה רקורסיבית היה הסניף של
pseudocode שאמר אחר, מעין

765
00:32:47,320 --> 00:32:52,000
המחצית השמאלית, למיין את הזכות
מחצית, למזג את שני החצאים.

766
00:32:52,000 --> 00:32:55,530
עכשיו למה עושה בביטוי זה
לייצג את ההוצאות האלה?

767
00:32:55,530 --> 00:32:58,690
ובכן, T של n רק אומר
זמן למיין אלמנטי n.

768
00:32:58,690 --> 00:33:03,070
ולאחר מכן בצד הימני של
סימן שווה שם, T של n מתחלק

769
00:33:03,070 --> 00:33:06,600
על ידי 2 מתייחס לעלות של מה?

770
00:33:06,600 --> 00:33:07,570
מיון המחצית השמאלית.

771
00:33:07,570 --> 00:33:10,990
T השני של n מחולק ב 2 הוא
ככל הנראה מתכוון לעלות

772
00:33:10,990 --> 00:33:12,390
למיין את החצי הימני.

773
00:33:12,390 --> 00:33:14,590
>> ולאחר מכן בתוספת n?

774
00:33:14,590 --> 00:33:15,420
האם המיזוג.

775
00:33:15,420 --> 00:33:19,120
כי אם יש לך שתי רשימות, האחת של
n גודל מעל 2 ועוד בגודל n

776
00:33:19,120 --> 00:33:22,580
מעל 2, יש לך בעצם לגעת
כל אחד מהאלמנטים האלה, בדיוק כמו רוב

777
00:33:22,580 --> 00:33:24,990
נגעתי בכל אחת מהכוסות, ורק
כפי שציינו בכל אחד מ

778
00:33:24,990 --> 00:33:26,310
מתנדב על במה.

779
00:33:26,310 --> 00:33:28,790
אז n הוא על חשבונו של מיזוג.

780
00:33:28,790 --> 00:33:31,780
>> עכשיו למרבה הצער, נוסחה זו
גם את עצמו רקורסיבית.

781
00:33:31,780 --> 00:33:36,390
אז אם שאל את השאלה, אם n הוא, למשל,
16, אם יש 16 אנשים על במה

782
00:33:36,390 --> 00:33:40,670
או, סך הכל 16 כוסות בוידאו כמה
צעדים נדרש כדי למיין אותם

783
00:33:40,670 --> 00:33:41,550
עם סוג המיזוג?

784
00:33:41,550 --> 00:33:45,790
זה ממש לא תשובה ברורה,
כי עכשיו אתה צריך למיין של

785
00:33:45,790 --> 00:33:48,500
באופן רקורסיבי לענות נוסחה זו.

786
00:33:48,500 --> 00:33:51,190
>> אבל זה בסדר, כי הרשו לי להציע
שאנחנו עושים את הדברים הבאים.

787
00:33:51,190 --> 00:33:56,670
הפעם מעורב למיין 16 אנשים או
16 כוסות הולכת להיות מיוצגות

788
00:33:56,670 --> 00:33:58,020
בדרך כלל כT של 16.

789
00:33:58,020 --> 00:34:01,400
אבל זה שווה, על פי
נוסחה קודמת, פי 2 את הכמות

790
00:34:01,400 --> 00:34:04,780
זמן שלוקח למיון
8 כוסות בתוספת 16.

791
00:34:04,780 --> 00:34:08,590
ושוב, בתוספת 16 היא הזמן למיזוג,
וT פי שניים של 8 הוא

792
00:34:08,590 --> 00:34:10,790
זמן למיין חצי שמאל וחצי נכון.

793
00:34:10,790 --> 00:34:11,989
>> אבל שוב, זה לא מספיק.

794
00:34:11,989 --> 00:34:13,210
יש לנו לצלול עמוק יותר.

795
00:34:13,210 --> 00:34:16,409
זה אומר שאנחנו צריכים לענות
שאלה, מהו T של 8?

796
00:34:16,409 --> 00:34:19,610
ובכן T של 8 הוא רק 2
הפעמים T של 4 ועוד 8.

797
00:34:19,610 --> 00:34:20,520
ובכן, מה T של 4?

798
00:34:20,520 --> 00:34:23,780
T של 4 הוא רק פעמים 2 T של 2 ועוד 4.

799
00:34:23,780 --> 00:34:25,489
ובכן, מה T של 2?

800
00:34:25,489 --> 00:34:29,030
T של 2 הוא רק פעמים 2 T של 1 ועוד 2.

801
00:34:29,030 --> 00:34:31,940
>> ושוב, אנחנו מקבלים סוג של
תקוע במעגל הזה.

802
00:34:31,940 --> 00:34:34,790
אבל זה עומד להכות כי
מה שנקרא מקרה בסיס.

803
00:34:34,790 --> 00:34:37,310
משום מה T של 1, שאנחנו טוענים?

804
00:34:37,310 --> 00:34:37,810
0.

805
00:34:37,810 --> 00:34:39,730
אז עכשיו סוף סוף, אנחנו יכולים לעבוד אחורה.

806
00:34:39,730 --> 00:34:44,290
>> אם T של 1 הוא 0, עכשיו אני יכול לחזור עד אחד
קו לבחור הזה כאן, ואני יכול

807
00:34:44,290 --> 00:34:46,330
תקע ב0 עבור T של 1.

808
00:34:46,330 --> 00:34:51,770
אז זה אומר שזה שווה 2 פעמים אפס,
הידוע גם ב0, בתוספת 2.

809
00:34:51,770 --> 00:34:53,739
וכדי שכל הביטוי הוא 2.

810
00:34:53,739 --> 00:34:58,740
>> עכשיו, אם אני לוקח T של 2, שהתשובה עליה
הוא 2, חבר אותו לקו האמצעי, T

811
00:34:58,740 --> 00:35:02,740
של 4, זה נותן לי 2 פעמים
2 בתוספת 4, אז 8.

812
00:35:02,740 --> 00:35:07,080
אם אני לאחר מכן חבר ב8 הקודמים
קו, זה נותן לי 2 פעמים 8, 16.

813
00:35:07,080 --> 00:35:12,470
ואם אנחנו לא אז נמשיך עם זה
24, והוסיף ב16, אנחנו סוף סוף מקבלים

814
00:35:12,470 --> 00:35:13,820
ערך של 64.

815
00:35:13,820 --> 00:35:18,480
>> עכשיו שבפני עצמו סוג של מדבר
מה סימון n,

816
00:35:18,480 --> 00:35:20,700
הגדול O, אומגה שיש לנו
כבר דיבר עליו.

817
00:35:20,700 --> 00:35:24,890
אבל מתברר כי 64 היא אכן
16, בגודל של הקלט,

818
00:35:24,890 --> 00:35:27,110
היכנס בסיס 2 של 16.

819
00:35:27,110 --> 00:35:30,200
ואם זה קצת לא מוכר, רק
חושב בחזרה, וזה יחזור

820
00:35:30,200 --> 00:35:30,700
אליך בסופו.

821
00:35:30,700 --> 00:35:33,775
אם זה יומן בסיס 2, זה כמו 2
העלה למה נותן לך 16?

822
00:35:33,775 --> 00:35:36,380
אה, זה 4, אז זה 16 פעמים 4.

823
00:35:36,380 --> 00:35:39,380
>> ושוב, זה לא עניין גדול אם זה
הוא סוג של זיכרון מעורפל עכשיו.

824
00:35:39,380 --> 00:35:43,720
אבל לעת עתה, לקחת על אמונה
16 שיומן הוא 16 64.

825
00:35:43,720 --> 00:35:46,590
וכך, אכן, עם שפיות פשוטה זו
לבדוק, אנחנו כבר אישר -

826
00:35:46,590 --> 00:35:48,250
אבל לא הוכיח באופן רשמי -

827
00:35:48,250 --> 00:35:52,800
שזמן הריצה של מיזוג
מיון הוא אכן n log n.

828
00:35:52,800 --> 00:35:53,790
>> אז לא רע.

829
00:35:53,790 --> 00:35:57,260
זה בהחלט טוב יותר מאשר
אלגוריתמים שראינו עד כה, ו

830
00:35:57,260 --> 00:36:00,710
זה בגלל שיש לנו למנף, אחד,
בטכניקה הנקראת רקורסיה.

831
00:36:00,710 --> 00:36:03,880
אבל יותר מעניין מזה, כי
רעיון של החלוקה וכובשת.

832
00:36:03,880 --> 00:36:07,460
שוב, דברים 0 באמת בשבוע ש
אפילו עכשיו הוא חוזר ומופיע ב

833
00:36:07,460 --> 00:36:08,740
דרך משכנעת יותר.

834
00:36:08,740 --> 00:36:11,750
>> עכשיו תרגיל קטן כיף, אם יש לך
אף פעם לא עשה את זה - ואתה כנראה

835
00:36:11,750 --> 00:36:14,660
לא היה, כי מין רגיל
אנשים לא חושבים לעשות את זה.

836
00:36:14,660 --> 00:36:20,650
אבל אם אני הולך ל-google.com ואם
אני רוצה ללמוד משהו על

837
00:36:20,650 --> 00:36:22,356
רקורסיה, Enter.

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [שחוק]

840
00:36:29,058 --> 00:36:32,030
[עוד שחוק]

841
00:36:32,030 --> 00:36:33,385
דוד Malan: בדיחה רעה מתפשטת לאט.

842
00:36:33,385 --> 00:36:34,450
[שחוק]

843
00:36:34,450 --> 00:36:36,970
דוד Malan: רק במקרה, שזה שם.

844
00:36:36,970 --> 00:36:38,710
אני לא כותב את זה לא נכון,
ויש בדיחה.

845
00:36:38,710 --> 00:36:40,810
בסדר.

846
00:36:40,810 --> 00:36:42,950
תסביר את זה לאנשים הקרובים לך אם
זה לא ממש לא לחץ פשוט עדיין.

847
00:36:42,950 --> 00:36:47,650
אבל רקורסיה, באופן כללי יותר, מתייחסת
לתהליך של פונקציה הקוראת

848
00:36:47,650 --> 00:36:51,430
עצמו, או באופן כללי יותר, החלוקה
בעיה למשהו שיכול להיות

849
00:36:51,430 --> 00:36:56,220
טיפין טיפין נפתרו על ידי פתרון זהה
בעיות נציג.

850
00:36:56,220 --> 00:36:58,400
>> ובכן, בואו הילוכים שינוי
רק לרגע.

851
00:36:58,400 --> 00:37:00,840
אנחנו רוצים לסיים בcliffhangers מסוים,
אז בואו נתחיל להגדיר

852
00:37:00,840 --> 00:37:05,870
במה, במשך כמה דקות,
על רעיון פשוט מאוד -

853
00:37:05,870 --> 00:37:07,620
שהחלפה של שני אלמנטים, נכון?

854
00:37:07,620 --> 00:37:10,040
כל האלגוריתמים האלה אנחנו כבר
מדבר על בני זוג מהעבר

855
00:37:10,040 --> 00:37:12,420
הרצאות כרוכות קצת
סוג של החלפה.

856
00:37:12,420 --> 00:37:14,630
היום זה היה דמיין ידי מקבל
קמתי מכיסאותיהם ו

857
00:37:14,630 --> 00:37:18,570
מסתובב, אבל בקוד, הייתי עושה זאת
פשוט לקחת את אלמנט ממערך אחד

858
00:37:18,570 --> 00:37:20,370
ומפיל אותם למשנו.

859
00:37:20,370 --> 00:37:21,880
>> אז איך ללכת על עושה את זה?

860
00:37:21,880 --> 00:37:24,850
ובכן, הרשה לי להמשיך ולכתוב
תכנית מהירה כאן.

861
00:37:24,850 --> 00:37:31,600
אני הולך להמשיך ולעשות
זה כבא.

862
00:37:31,600 --> 00:37:33,910
בואו נקראים לזה -

863
00:37:33,910 --> 00:37:38,070
מה אנחנו רוצים לקרוא לזה?

864
00:37:38,070 --> 00:37:38,650
>> למעשה, לא.

865
00:37:38,650 --> 00:37:39,420
תן לי להריץ אחורה.

866
00:37:39,420 --> 00:37:41,220
אני לא רוצה לעשות את זה
סחרור מסוכן עדיין.

867
00:37:41,220 --> 00:37:42,270
זה יקלקל את ההנאה.

868
00:37:42,270 --> 00:37:43,600
בואו נעשה את זה במקום.

869
00:37:43,600 --> 00:37:47,430
>> נניח שאני רוצה לכתוב קצת
תכנית ושעכשיו מחבקת את זה

870
00:37:47,430 --> 00:37:48,700
רעיון של רקורסיה.

871
00:37:48,700 --> 00:37:50,370
אני סוג של לי מקדים את המאוחר שם.

872
00:37:50,370 --> 00:37:51,420
אני הולך לבצע את הפעולות הבאות.

873
00:37:51,420 --> 00:38:00,220
>> ראשית, מהיר כוללים הסטנדרטי של io.h,
כמו גם כולל של cs50.h.

874
00:38:00,220 --> 00:38:03,200
ואז אני הולך קדימה
ולהכריז חלל עיקרי int

875
00:38:03,200 --> 00:38:04,360
בדרך הרגילה.

876
00:38:04,360 --> 00:38:07,920
הבנתי שאני כבר misnamed את הקובץ, ולכן
תנו לי רק להוסיף. ג סיומת כאן כל כך

877
00:38:07,920 --> 00:38:09,510
שאנחנו יכולים לעבד אותו כמו שצריך.

878
00:38:09,510 --> 00:38:10,970
התחל בפונקציה זו את.

879
00:38:10,970 --> 00:38:13,290
>> ואת הפונקציה שאני רוצה לכתוב, די
בפשטות, הוא אחד ששואל

880
00:38:13,290 --> 00:38:16,210
משתמש למספר ולאחר מכן מוסיף את
כל המספרים בין ש

881
00:38:16,210 --> 00:38:19,920
מספר ו, יניח, 0.

882
00:38:19,920 --> 00:38:22,510
אז קודם כל אני הולך קדימה
ולהכריז n int.

883
00:38:22,510 --> 00:38:24,760
אז אני מעתיק קצת קוד ש
אנחנו כבר בשימוש במשך זמן מה.

884
00:38:24,760 --> 00:38:26,660
בעוד משהו נכון.

885
00:38:26,660 --> 00:38:28,000
אני אחזור לזה באותו רגע.

886
00:38:28,000 --> 00:38:29,010
>> מה אני רוצה לעשות?

887
00:38:29,010 --> 00:38:33,460
אני רוצה לומר printf חיובי
שלם בבקשה.

888
00:38:33,460 --> 00:38:36,130
ולאחר מכן אני הולך
אומר N מקבל מקבל int.

889
00:38:36,130 --> 00:38:38,800
אז שוב, קוד מוכן מראש כמה
שאנחנו כבר השתמשנו בעבר.

890
00:38:38,800 --> 00:38:40,810
ואני הולך לעשות את זה
ואילו n הוא פחות מ 1.

891
00:38:40,810 --> 00:38:44,120
אז זה יבטיח שהמשתמש
נותן לי מספר שלם חיובי.

892
00:38:44,120 --> 00:38:45,490
>> ועכשיו אני הולך לעשות את הדברים הבאים.

893
00:38:45,490 --> 00:38:51,020
אני רוצה להוסיף את כל המספרים
בין 1 ו-n, או 0 ו n,

894
00:38:51,020 --> 00:38:52,570
באופן שקול, כדי לקבל את הסכום הכולל.

895
00:38:52,570 --> 00:38:55,100
אז הסמל הגדול סיגמא
שאולי אתה זוכר.

896
00:38:55,100 --> 00:38:59,050
אז אני הולך לעשות את זה על ידי השיחות ראשון
פונקציה שנקראת סיגמא,

897
00:38:59,050 --> 00:39:06,030
עובר אותו בN, ולאחר מכן אני הולך
אומר printf, התשובה היא ממש שם.

898
00:39:06,030 --> 00:39:08,180
>> אז בקיצור, אני מקבל ו
int מהמשתמש.

899
00:39:08,180 --> 00:39:09,280
אני מבטיח שזה חיובי.

900
00:39:09,280 --> 00:39:12,700
אני מצהיר בשם תשובה משתנה
סוג int וחנות בה את התשואה

901
00:39:12,700 --> 00:39:15,610
ערך של סיגמא, עובר בn כקלט.

902
00:39:15,610 --> 00:39:17,060
ואז להדפיס את התשובה הזו.

903
00:39:17,060 --> 00:39:19,550
>> למרבה הצער, למרות שנשמע סיגמא
כמו משהו שעשויה להיות ב

904
00:39:19,550 --> 00:39:24,040
קובץ math.h, ההצהרה שלו,
זה ממש לא.

905
00:39:24,040 --> 00:39:24,690
אז זה בסדר.

906
00:39:24,690 --> 00:39:26,170
אני יכול ליישם את זה בעצמי.

907
00:39:26,170 --> 00:39:29,160
אני הולך ליישם פונקציה הנקראת
סיגמא, וזה הולך לקחת

908
00:39:29,160 --> 00:39:29,900
פרמטר -

909
00:39:29,900 --> 00:39:32,100
בואו פשוט נקראים לזה מ ', רק
כך שזה שונה.

910
00:39:32,100 --> 00:39:35,910
ולאחר מכן עד כאן, אני הולך לומר,
ובכן, אם מ 'הוא פחות מ 1 - זה

911
00:39:35,910 --> 00:39:38,180
מאוד מעניין תכנית.

912
00:39:38,180 --> 00:39:41,700
אז אני הולך קדימה
להחזיר 0 באופן מיידי.

913
00:39:41,700 --> 00:39:45,920
זה פשוט לא הגיוני להוסיף את כל
המספרים בין 1 מ 'ואם מ'

914
00:39:45,920 --> 00:39:48,470
הוא עצמו 0 או שלילי.

915
00:39:48,470 --> 00:39:50,900
>> ואז אני הולך קדימה
ולעשות את זה iteratively מאוד.

916
00:39:50,900 --> 00:39:53,090
אני הולך לעשות את זה סוג של בית הספר ישן,
ואני הולך קדימה

917
00:39:53,090 --> 00:39:57,150
ולומר שאני הולך
להכריז על סכום להיות 0.

918
00:39:57,150 --> 00:39:59,630
ואז אני הולך יש לי
ללולאה של int -

919
00:39:59,630 --> 00:40:02,820
ותנו לי לעשות את זה כך שיתאים לשלנו
קוד הפצה, כך שאין לך עותק

920
00:40:02,820 --> 00:40:07,500
בבית. אני int מקבל 1 בעד
אני פחות או שווה ל מ '.

921
00:40:07,500 --> 00:40:09,430
אני ועוד תוספת.

922
00:40:09,430 --> 00:40:11,430
ואז בתוך זה ללולאה -

923
00:40:11,430 --> 00:40:12,440
אנחנו כמעט שם -

924
00:40:12,440 --> 00:40:15,810
סכום מקבל סכום 1 ועוד.

925
00:40:15,810 --> 00:40:17,670
ולאחר מכן אני הולך להחזיר את הסכום.

926
00:40:17,670 --> 00:40:19,420
>> אז עשיתי את זה במהירות,
די יש להודות.

927
00:40:19,420 --> 00:40:22,775
אבל שוב, עיקר התפקיד די
פשוט, המבוסס על קוד שיש לנו

928
00:40:22,775 --> 00:40:23,190
כתב עד כה.

929
00:40:23,190 --> 00:40:25,610
משתמש בלולאה הכפולה כדי לקבל חיובי
int מהמשתמש.

930
00:40:25,610 --> 00:40:29,870
אז אני עובר int כי לפונקציה חדשה
קרא סיגמא, וכינה אותו, שוב, n.

931
00:40:29,870 --> 00:40:33,100
ואני לאחסן את ערך התמורה, את התשובה
מהקופסה השחורה כרגע

932
00:40:33,100 --> 00:40:35,460
המכונה סיגמא, במשתנה
קרא תשובה.

933
00:40:35,460 --> 00:40:36,580
ואז להדפיס אותו.

934
00:40:36,580 --> 00:40:39,090
>> אם אנחנו עכשיו נמשיך את הסיפור,
איך Sigma מיושם?

935
00:40:39,090 --> 00:40:40,840
אני מציע ליישם באופן הבא.

936
00:40:40,840 --> 00:40:43,560
ראשית, קצת בדיקת שגיאות
כדי לוודא שהמשתמש לא

937
00:40:43,560 --> 00:40:46,480
להתעסק איתי ועובר ב
איזה ערך שלילי או 0.

938
00:40:46,480 --> 00:40:49,710
אז אני מכריז על משתנה בשם
לסכם ולהגדיר אותו ל -0.

939
00:40:49,710 --> 00:40:55,910
>> ועכשיו אני מתחיל לעבור מאני שווה
1 כל הדרך עד וכולל מ ',

940
00:40:55,910 --> 00:41:00,130
כי אני רוצה לכלול את כל
מספרים מאחד עד מ 'ועד בכלל.

941
00:41:00,130 --> 00:41:04,350
ובתוך זה ללולאה, רק שאני עושה
סכום מקבל כל מה שהוא עכשיו, בתוספת

942
00:41:04,350 --> 00:41:08,900
ערך שלי.

943
00:41:08,900 --> 00:41:10,370
בתוספת הערך של i.

944
00:41:10,370 --> 00:41:14,090
>> במאמר מוסגר, אם אתה לא ראית את זה
לפני כן, יש קצת סוכר תחבירי

945
00:41:14,090 --> 00:41:14,870
עבור קו זה.

946
00:41:14,870 --> 00:41:21,120
אני יכול לשכתב את זה כתוספת שווה לי,
רק כדי להציל את עצמי כמה הקשות

947
00:41:21,120 --> 00:41:22,570
ולהסתכל קצת קריר.

948
00:41:22,570 --> 00:41:23,140
אבל זה הכל.

949
00:41:23,140 --> 00:41:24,660
זה פונקציונלי אותו הדבר.

950
00:41:24,660 --> 00:41:26,710
>> למרבה הצער, את הקוד הזה של
לא הולך לקמפל עדיין.

951
00:41:26,710 --> 00:41:31,600
אם אני רץ לעשות 0 סיגמא, איך אני
אני הולך צועק עליי?

952
00:41:31,600 --> 00:41:33,473
מה זה הולך לא לאהוב?

953
00:41:33,473 --> 00:41:35,740
>> קהל: [לא ברור].

954
00:41:35,740 --> 00:41:37,800
>> מלאן דוד: כן, אני לא הכרזתי
הפונקציה למעלה, נכון?

955
00:41:37,800 --> 00:41:40,590
C היא סוג של טיפשים, בכך שהוא רק
עושה את מה שאתה אומר לו לעשות, ואתה

956
00:41:40,590 --> 00:41:41,880
צריך לעשות את זה לפי הסדר הזה.

957
00:41:41,880 --> 00:41:45,910
ולכן אם אני מכה הזן כאן, אני הולך
מקבל אזהרה על סיגמא משתמעת

958
00:41:45,910 --> 00:41:46,860
הכרזה.

959
00:41:46,860 --> 00:41:48,120
>> אה, לא בעיה.

960
00:41:48,120 --> 00:41:50,370
אני יכול ללכת עד לקצה, ושאני יכול
אומר, בסדר, חכה רגע.

961
00:41:50,370 --> 00:41:54,240
סיגמא הוא פונקציה המחזירה
int והיא מצפה

962
00:41:54,240 --> 00:41:56,620
int כקלט, פסיק.

963
00:41:56,620 --> 00:41:59,550
או שאני יכול לשים את כל הפונקציה
מעל ראשי, אבל באופן כללי, הייתי

964
00:41:59,550 --> 00:42:02,260
ממליץ על זה, כי זה
נחמד תמיד יש לי ראשי בחלק העליון כל כך

965
00:42:02,260 --> 00:42:06,310
אתה יכול לצלול ממש ויודע מה
התכנית עושה על ידי קריאה העיקרית הראשונה.

966
00:42:06,310 --> 00:42:07,930
>> אז עכשיו תן לי לנקות את המסך.

967
00:42:07,930 --> 00:42:09,330
מהדורה מחודשת סיגמא 0.

968
00:42:09,330 --> 00:42:10,340
הכל נראה לבדוק.

969
00:42:10,340 --> 00:42:11,970
תן לי לרוץ סיגמא 0.

970
00:42:11,970 --> 00:42:12,770
בין חיובי.

971
00:42:12,770 --> 00:42:15,580
אני אתן לו את המספר
3 כדי לשמור את זה פשוט.

972
00:42:15,580 --> 00:42:18,710
כך שצריך לתת לי 3
בתוספת 2 בתוספת 1, ולכן 6.

973
00:42:18,710 --> 00:42:20,750
הזן, ואכן אני מקבל 6.

974
00:42:20,750 --> 00:42:21,820
>> אני יכול לעשות משהו גדול יותר -

975
00:42:21,820 --> 00:42:24,080
50, 12, 75.

976
00:42:24,080 --> 00:42:27,690
בדיוק כמו משיק, אני הולך לעשות
משהו מגוחך כמו גדול באמת

977
00:42:27,690 --> 00:42:30,375
מספר, הו, זה באמת הסתדר -

978
00:42:30,375 --> 00:42:31,600
אה, אני לא חושב שזה נכון.

979
00:42:31,600 --> 00:42:32,810
בואו נראה.

980
00:42:32,810 --> 00:42:34,060
בואו באמת להתעסק עם זה.

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> זו בעיה.

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
מה קורה?

985
00:42:44,970 --> 00:42:46,050
הקוד לא כל כך נורא.

986
00:42:46,050 --> 00:42:48,470
זה עדיין ליניארי.

987
00:42:48,470 --> 00:42:50,810
שורק שהוא תוצאה טובה,.

988
00:42:50,810 --> 00:42:52,060
מה קורה?

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> לא בטוח אם שמעתי את זה.

991
00:42:55,620 --> 00:42:57,620
אז מתברר - ו
זה במאמר מוסגר.

992
00:42:57,620 --> 00:42:59,400
זה לא ליבה
רעיון של רקורסיה.

993
00:42:59,400 --> 00:43:02,480
מתברר, כי אני מנסה
לייצג מספר כזה גדול, רוב

994
00:43:02,480 --> 00:43:06,980
סביר להניח שזה שלא כהלכה
על ידי C כמו מספר לא חיובי,

995
00:43:06,980 --> 00:43:09,980
אבל מספר שלילי.

996
00:43:09,980 --> 00:43:12,690
>> לא דיברנו על זה, אבל זה
מסתבר שיש מספרים שליליים

997
00:43:12,690 --> 00:43:14,210
בעולם, בנוסף
למספרים חיוביים.

998
00:43:14,210 --> 00:43:16,290
ואת הכלי שבאמצעותו אתה יכול
מייצג מספר שלילי

999
00:43:16,290 --> 00:43:19,530
במהותה הוא, אתה משתמש באחד
קצת מיוחד כדי לציין

1000
00:43:19,530 --> 00:43:20,400
חיובי על שלילי.

1001
00:43:20,400 --> 00:43:22,950
זה קצת יותר מורכב מזה,
אבל זה הרעיון הבסיסי.

1002
00:43:22,950 --> 00:43:26,740
>> אז למרבה הצער, אם C היא מבלבלת אחד
מאותם ביטים כמו בעצם משמעות,

1003
00:43:26,740 --> 00:43:30,790
אה, זה הוא מספר שלילי, לולאתי
כאן, למשל, הוא למעשה לא

1004
00:43:30,790 --> 00:43:31,740
הולך לסיים.

1005
00:43:31,740 --> 00:43:33,850
אז אם אני ממש היה מדפיס משהו
שוב ושוב, הייתי עושה זאת

1006
00:43:33,850 --> 00:43:34,650
רואה הרבה.

1007
00:43:34,650 --> 00:43:36,220
אבל שוב, זו לא הנקודה.

1008
00:43:36,220 --> 00:43:38,590
זה באמת רק סוג של
סקרנות אינטלקטואלית שנבוא

1009
00:43:38,590 --> 00:43:39,550
לגבות לסופו של דבר.

1010
00:43:39,550 --> 00:43:43,400
אבל לעת עתה, זה נכון
יישום אם נניח כי

1011
00:43:43,400 --> 00:43:45,970
משתמש יספק ints
שיתאים לints.

1012
00:43:45,970 --> 00:43:49,370
>> אבל אני טוען שהקוד הזה, בכנות,
אפשר לעשות כל כך הרבה יותר פשוט.

1013
00:43:49,370 --> 00:43:54,060
אם המטרה בהישג היד היא לקחת מספר
כמו מ 'ולהוסיף את כל

1014
00:43:54,060 --> 00:43:59,510
מספרים בינו לבין 1, או לחלופין
בין 1 ואת זה, אני טוען

1015
00:43:59,510 --> 00:44:03,380
שאני יכול לשאול את הרעיון הזה שיתמזג
היה סוג, שהיה לוקח את הבעיה

1016
00:44:03,380 --> 00:44:05,660
בגודל זה וחלוקתו
למשהו קטן יותר.

1017
00:44:05,660 --> 00:44:09,875
אולי לא חצי, אבל קטן יותר, אבל
representatively את אותו הדבר.

1018
00:44:09,875 --> 00:44:12,130
אותו הרעיון, אבל בעיה קטנה יותר.

1019
00:44:12,130 --> 00:44:15,470
>> אז בעצם אני - תן לי לשמור קובץ זה
עם מספר גרסה שונה.

1020
00:44:15,470 --> 00:44:17,670
אנחנו קוראים לגרסה זו
1 במקום 0.

1021
00:44:17,670 --> 00:44:20,790
ואני טוען שאני יכול למעשה
reimplement זה בסוג זה של

1022
00:44:20,790 --> 00:44:22,160
מוח כיפוף דרך.

1023
00:44:22,160 --> 00:44:23,710
>> אני הולך להשאיר חלק ממנו לבד.

1024
00:44:23,710 --> 00:44:27,710
אני הולך לומר אם מ 'הוא פחות
מאו אפילו שווה - 0

1025
00:44:27,710 --> 00:44:29,280
אני רק הולך להיות קצת
אנאלי יותר הפעם

1026
00:44:29,280 --> 00:44:30,520
עם הבדיקה שלי השגיאה -

1027
00:44:30,520 --> 00:44:33,190
אני הולך קדימה ולהחזיר 0.

1028
00:44:33,190 --> 00:44:34,490
זה הוא שרירותי.

1029
00:44:34,490 --> 00:44:37,500
אני רק פשוט להחליט אם המשתמש
נותן לי מספר שלילי, אני

1030
00:44:37,500 --> 00:44:41,490
חוזר 0, והם היו צריכים לקרוא
התיעוד באופן הדוק יותר.

1031
00:44:41,490 --> 00:44:42,170
>> אחר -

1032
00:44:42,170 --> 00:44:44,070
שים לב למה שאני הולך לעשות.

1033
00:44:44,070 --> 00:44:49,260
עוד אני הולך לחזור מ 'בתוספת -

1034
00:44:49,260 --> 00:44:51,010
מה סיגמא של מ '?

1035
00:44:51,010 --> 00:44:56,710
ובכן, סיגמא של מ 'בתוספת מ' מינוס 1,
בתוספת 2 מ 'מינוס, פלוס מינוס 3 מ'.

1036
00:44:56,710 --> 00:44:58,030
אני לא רוצה לכתוב את כל זה החוצה.

1037
00:44:58,030 --> 00:44:59,120
למה לא לעשות אני פשוט הדוגית?

1038
00:44:59,120 --> 00:45:05,080
באופן רקורסיבי קורא לעצמי עם מעט
בעיה קטנה יותר, פסיק,

1039
00:45:05,080 --> 00:45:06,840
וקורא לזה היום?

1040
00:45:06,840 --> 00:45:07,040
>> נכון?

1041
00:45:07,040 --> 00:45:10,980
עכשיו גם כאן, אתה עלול להרגיש או לדאוג
כי מדובר בלולאה אינסופית שאני

1042
00:45:10,980 --> 00:45:15,450
התרמה, שבו אני מיישם
סיגמא על ידי התקשרות סיגמא.

1043
00:45:15,450 --> 00:45:20,342
אבל זה בסדר גמור, כי אני
חשב קדימה הוסיף אילו קווים?

1044
00:45:20,342 --> 00:45:22,600
>> קהל: [לא ברור].

1045
00:45:22,600 --> 00:45:25,430
>> דוד Malan: 23 עד 26, אשר
הוא אם המצב שלי.

1046
00:45:25,430 --> 00:45:28,390
כי מה שיפה
חיסור כאן, כי אני כל זמן

1047
00:45:28,390 --> 00:45:31,180
בעיות קטנות סיגמא מסירה, קטן יותר
בעיות, קטן יותר - זה לא

1048
00:45:31,180 --> 00:45:31,870
מחצית מגודלו.

1049
00:45:31,870 --> 00:45:34,380
זה רק צעד תינוק קטן יותר,
אבל זה בסדר.

1050
00:45:34,380 --> 00:45:38,050
כי סופו של דבר, אנחנו נעבוד
את דרכנו במורד עד 1 או 0.

1051
00:45:38,050 --> 00:45:41,630
וברגע שפגענו 0, סיגמא לא
הולך לקרוא את עצמו יותר.

1052
00:45:41,630 --> 00:45:43,590
זה הולך לחזור מייד 0.

1053
00:45:43,590 --> 00:45:47,960
>> כך למעשה, אם אתה הסוג של רוח זו
בראש שלך, הוא להוסיף מ 'בתוספת

1054
00:45:47,960 --> 00:45:52,740
1 מ 'מינוס, פלוס מינוס 2 מ', בתוספת מ 'מינוס
3, בתוספת נקודה, נקודה, נקודה, מ 'מינוס

1055
00:45:52,740 --> 00:45:57,820
מ ', סופו של דבר נותן לך 0, ו
השפעה היא סופו של דבר להוסיף את כל

1056
00:45:57,820 --> 00:45:59,070
הדברים האלה ביחד.

1057
00:45:59,070 --> 00:46:02,380
אז אנחנו לא צריכים, עם רקורסיה,
פתר את הבעיה שאנחנו

1058
00:46:02,380 --> 00:46:03,470
לא יכל לפתור בעבר.

1059
00:46:03,470 --> 00:46:06,840
ואכן, 0 גרסה של זה, ובכל
בעיה עד היום, כבר פתירה

1060
00:46:06,840 --> 00:46:09,980
עם רק באמצעות לולאות או בעת
לולאות או בונה דומה.

1061
00:46:09,980 --> 00:46:13,150
>> אבל רקורסיה, אני מעז לומר, נותן לנו
דרך לחשוב על שונה

1062
00:46:13,150 --> 00:46:17,010
בעיות, לפיה אם אנחנו יכולים לקחת
בעיה, לחלק אותו ממשהו

1063
00:46:17,010 --> 00:46:22,340
גדול במקצת למשהו קצת
קטן יותר, אני טוען שאנחנו יכולים לפתור את זה

1064
00:46:22,340 --> 00:46:26,040
אולי קצת יותר באלגנטיות במונחים
של העיצוב, עם פחות קוד,

1065
00:46:26,040 --> 00:46:30,980
ואולי אפילו לפתור את הבעיות שהיינו
יהיה קשה יותר, שכן אנו סופו של דבר

1066
00:46:30,980 --> 00:46:33,280
תראה, פתרון גרידא iteratively.

1067
00:46:33,280 --> 00:46:35,980
>> אבל הסחרור המסוכן שעשיתי
רוצה להשאיר אותנו על זה היה.

1068
00:46:35,980 --> 00:46:40,720
תן לי ללכת קדימה ולפתוח
את קובץ מ--

1069
00:46:40,720 --> 00:46:44,300
בעצם, תן לי ללכת ו
לעשות ממש מהר זה.

1070
00:46:44,300 --> 00:46:46,875
תן לי ללכת קדימה ולהציע
את הדברים הבאים.

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
בין הקוד של היום הוא בקובץ זה כאן.

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
זה אחד כאן, noswap.

1075
00:47:03,050 --> 00:47:06,260
>> אז זו היא תוכנה קטנה טיפשית ש
שלפתי את טענות כי לעשות

1076
00:47:06,260 --> 00:47:06,940
את הדברים הבאים.

1077
00:47:06,940 --> 00:47:10,140
בעיקרי, הוא מצהיר ראשון
קרא int x ומקצה לו

1078
00:47:10,140 --> 00:47:11,100
הערך של 1.

1079
00:47:11,100 --> 00:47:13,520
אז זה מצהיר y int ו
מקצה לו את הערך 2.

1080
00:47:13,520 --> 00:47:15,310
ואז זה מדפיס את מה שהוא X ו-Y.

1081
00:47:15,310 --> 00:47:17,781
אז זה אומר, החלפה, נקודת נקודת נקודה.

1082
00:47:17,781 --> 00:47:21,670
>> לאחר מכן הוא טוען להיות קורא לפונקציה
החלפת שם, עובר בx ו

1083
00:47:21,670 --> 00:47:24,290
Y, את הרעיון שלו הוא שאני מקווה
X ו-Y יחזרו

1084
00:47:24,290 --> 00:47:25,620
שונה, הפוך.

1085
00:47:25,620 --> 00:47:27,110
ואז זה טוען החליף!

1086
00:47:27,110 --> 00:47:28,420
עם סימן קריאה.

1087
00:47:28,420 --> 00:47:30,190
ואז זה מדפיס את X ו-Y.

1088
00:47:30,190 --> 00:47:33,480
>> אבל מתברר שזה מאוד
הפגנה פשוטה למטה

1089
00:47:33,480 --> 00:47:35,570
כאן הוא למעשה מרכבה.

1090
00:47:35,570 --> 00:47:38,870
למרות שאני מצהיר זמני
משתנה באופן זמני ולשים ב

1091
00:47:38,870 --> 00:47:42,010
את זה, אז אני הקצאה מחדש
ערך ב -

1092
00:47:42,010 --> 00:47:45,080
אשר מרגיש סביר, משום שיש לי
שמר עותק של בטמפ '.

1093
00:47:45,080 --> 00:47:48,410
אז אני מעדכן ב לשווה
כל מה שהיה בזמני.

1094
00:47:48,410 --> 00:47:51,610
זה סוג של משחק פגז של נע
לB ו-B לזו באמצעות

1095
00:47:51,610 --> 00:47:54,360
העמידה אדם בשם זמני מרגיש
בהחלט סביר.

1096
00:47:54,360 --> 00:47:57,270
>> אבל אני טוען שכאשר אני מפעיל את זה
קוד, כמו שאני עושה עכשיו -

1097
00:47:57,270 --> 00:47:59,490
תן לי ללכת קדימה ולהדביק בזה כאן.

1098
00:47:59,490 --> 00:48:01,995
אני אתקשר noswap.c זה.

1099
00:48:01,995 --> 00:48:05,630
וכפי שהשם מרמז, זה לא
הולך להיות תכנית נכונה.

1100
00:48:05,630 --> 00:48:09,460
הפוך noswap. / לא החלפה.

1101
00:48:09,460 --> 00:48:12,110
X הוא 1, 2 y הוא, להחליף, החליף.

1102
00:48:12,110 --> 00:48:14,220
X הוא 1, y הוא 2.

1103
00:48:14,220 --> 00:48:16,920
זו בטעות יסודה, אפילו
למרות שזה נראה מושלם

1104
00:48:16,920 --> 00:48:17,730
לי סביר.

1105
00:48:17,730 --> 00:48:21,330
ויש לכך סיבה, אבל אנחנו לא
הולך לחשוף את הסיבה עדיין.

1106
00:48:21,330 --> 00:48:24,610
>> לעת עתה סחרור המסוכן השני שאני רוצה
כדי להשאיר אותך עם זה,

1107
00:48:24,610 --> 00:48:27,120
הכרזה על מיני קודי קופון.

1108
00:48:27,120 --> 00:48:31,590
החדשנות שלנו עם ימים בסוף השנה
עורר מספר לא טריוויאלית

1109
00:48:31,590 --> 00:48:33,830
של שאלות, שהיה
אין בכוונתנו.

1110
00:48:33,830 --> 00:48:36,590
הכוונה של הקודים הללו קופון,
לפיה אם אתה עושה את חלק מהבעיה

1111
00:48:36,590 --> 00:48:39,850
מוקדם לקבוע, ובכך מקבל את יום נוסף,
היה באמת כדי לעזור לכם לעזור

1112
00:48:39,850 --> 00:48:42,420
את עצמך להתחיל מוקדם, בערך
על ידי תמריצים שלך.

1113
00:48:42,420 --> 00:48:44,880
עוזר לנו להפיץ את העומס על פני
שעתי עבודה טובה יותר כך שיישאר

1114
00:48:44,880 --> 00:48:45,740
זה סוג של win-win.

1115
00:48:45,740 --> 00:48:48,860
>> למרבה הצער, אני חושב שהוראות שלי
לא היה, עד כה, ברור מאוד, ולכן

1116
00:48:48,860 --> 00:48:52,230
חזרתי בסוף השבוע הזה ומעודכן
המפרט גדול יותר בטקסט, לנועז יותר

1117
00:48:52,230 --> 00:48:53,600
להסביר כדורים כאלה.

1118
00:48:53,600 --> 00:48:56,900
ורק כדי להגיד את זה יותר לציבור, על ידי
ברירת מחדל, ערכות הן בעייתיים בשל יום חמישי

1119
00:48:56,900 --> 00:48:58,400
בצהריים, לתכנית הלימודים.

1120
00:48:58,400 --> 00:49:02,030
אם אתה מתחיל מוקדם, מסיים את חלק
הבעיה להגדיר עד יום רביעי בשעה 12:00

1121
00:49:02,030 --> 00:49:05,170
בערב, חלק שמתייחס לקופון
קוד, הרעיון הוא שאתה יכול להאריך

1122
00:49:05,170 --> 00:49:07,710
המועד האחרון לקבלת
P נקבע עד ליום שישי.

1123
00:49:07,710 --> 00:49:10,890
כלומר, קצת מעל חלק קטן של P
נקבע ביחס למה שהוא בדרך כלל

1124
00:49:10,890 --> 00:49:13,200
בעיה גדולה יותר, ואתה קונה
את עצמך יום נוסף.

1125
00:49:13,200 --> 00:49:15,190
שוב, זה גורם לך לחשוב על
סט הבעיה, מקבל אותך

1126
00:49:15,190 --> 00:49:16,380
שעתי עבודה מוקדם יותר.

1127
00:49:16,380 --> 00:49:20,670
אבל הבעיה היא עדיין קוד קופון
נדרש, גם אם אתה לא להגיש אותו.

1128
00:49:20,670 --> 00:49:23,340
>> אבל יותר משכנע הוא זה.

1129
00:49:23,340 --> 00:49:26,520
(לחישה במה) והאנשים האלה עוזבים
מוקדם הולכים להצטער על כך.

1130
00:49:26,520 --> 00:49:28,620
וכך גם אנשים על המרפסת.

1131
00:49:28,620 --> 00:49:32,510
אני מתנצל מראש לאנשים על
מרפסת מסיבות שתהיינה

1132
00:49:32,510 --> 00:49:33,920
לנקות ברגע.

1133
00:49:33,920 --> 00:49:37,050
>> אז אנחנו ברי מזל שיש אחד
עמיתי הוראת הראש לשעבר של CS50 ב

1134
00:49:37,050 --> 00:49:39,302
חברה בשם dropbox.com.

1135
00:49:39,302 --> 00:49:45,500
הם תרמו בנדיבות מאוד
קוד קופון לכאן הרבה מקום זה,

1136
00:49:45,500 --> 00:49:48,180
אשר למעלה מ
2 ג'יגה הרגילה.

1137
00:49:48,180 --> 00:49:51,740
אז מה שחשבתי שאנחנו עושים על זה
הערה סופית היא לעשות קצת בגידה,

1138
00:49:51,740 --> 00:49:55,380
לפיה ברגע, אנו חושפים
יש המנצח ושהקופון

1139
00:49:55,380 --> 00:49:57,980
קוד שאתה יכול ואז ללכת להם
אתר אינטרנט, להקליד את זה, וזהו, יקבלו

1140
00:49:57,980 --> 00:50:01,370
Dropbox מקום שלך הרבה יותר
מכשיר ולקבצים האישיים שלך.

1141
00:50:01,370 --> 00:50:05,690
>> וראשון, שהייתי רוצה להשתתף
בציור זה?

1142
00:50:05,690 --> 00:50:09,630
אוקיי, עכשיו זה עושה את זה אפילו יותר כיף.

1143
00:50:09,630 --> 00:50:14,010
האדם שמקבל 25 ג'יגה זו
קוד קופון - וזה הרבה

1144
00:50:14,010 --> 00:50:16,150
יותר משכנע מאשר מאוחר
ימים עכשיו, אולי -

1145
00:50:16,150 --> 00:50:20,620
הוא אחד היושב על גבי
כרית מושב שמתחתיו יש

1146
00:50:20,620 --> 00:50:21,620
שהקוד קופון.

1147
00:50:21,620 --> 00:50:23,480
אתה יכול להסתכל עכשיו מתחת
כרית המושב שלך.

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [השמעת וידאו]

1150
00:50:29,680 --> 00:50:31,620
>> -אחת, שתיים, שלוש.

1151
00:50:31,620 --> 00:50:35,015
>> [צורח]

1152
00:50:35,015 --> 00:50:35,985
>> -אתה מקבל מכונית!

1153
00:50:35,985 --> 00:50:36,670
אתה מקבל מכונית!

1154
00:50:36,670 --> 00:50:37,970
>> דוד Malan: אנו רואים
שלך ביום רביעי.

1155
00:50:37,970 --> 00:50:38,904
>> -אתה מקבל מכונית!

1156
00:50:38,904 --> 00:50:39,371
אתה מקבל מכונית!

1157
00:50:39,371 --> 00:50:40,305
אתה מקבל מכונית!

1158
00:50:40,305 --> 00:50:41,706
אתה מקבל מכונית!

1159
00:50:41,706 --> 00:50:43,107
אתה מקבל מכונית!

1160
00:50:43,107 --> 00:50:45,530
>> דוד Malan: אנשים מרפסת, בוא
כאן למטה לחזית,

1161
00:50:45,530 --> 00:50:46,866
שבו יש לנו תוספות.

1162
00:50:46,866 --> 00:50:50,282
>> -כל אחד מקבל מכונית!

1163
00:50:50,282 --> 00:50:52,234
כל אחד מקבל מכונית!

1164
00:50:52,234 --> 00:50:52,722
>> [השמעת וידאו הסוף]

1165
00:50:52,722 --> 00:50:54,590
>> קריין: בCS50 הבא -

1166
00:50:54,590 --> 00:51:00,374
>> רמקול 5: אוי ואבוי אלוהים אלוהים אלוהים
אלוהים אלוהים אלוהים אלוהים אלוהים אלוהים -

1167
00:51:00,374 --> 00:51:02,106
>> [משחק ukelele]