1
00:00:00,000 --> 00:00:11,904
>> [השמעת מוסיקה]

2
00:00:11,904 --> 00:00:12,910
>> פרופסור: בסדר.

3
00:00:12,910 --> 00:00:16,730
זה CS50 וזה
סוף השבוע שלושה.

4
00:00:16,730 --> 00:00:20,230
אז אנחנו כאן היום, לא בסנדרס
תיאטרון, במקום בספרייה ויידנר.

5
00:00:20,230 --> 00:00:23,170
בתוכה הוא סטודיו
ידוע כאוזר סטודיו,

6
00:00:23,170 --> 00:00:28,310
או שמא נאמר סטודיו H, או תקבע
אנחנו say-- אם אתה נהנה בדיחה ש,

7
00:00:28,310 --> 00:00:30,540
זה בעצם מ
כיתה, מארק, באינטרנט,

8
00:00:30,540 --> 00:00:32,420
שהציע באותה מידה באמצעות טוויטר.

9
00:00:32,420 --> 00:00:34,270
עכשיו מה זה מגניב על
להיות כאן באולפן

10
00:00:34,270 --> 00:00:38,410
הוא שאני מוקף בירוק אלה
קירות, מסך או chromakey ירוק,

11
00:00:38,410 --> 00:00:43,290
כביכול, מה שאומר שCS50 של
צוות הפקה, ללא ידיעתי

12
00:00:43,290 --> 00:00:47,380
עכשיו, יכול להיות לשים
שלי ביותר בכל מקום בעולם,

13
00:00:47,380 --> 00:00:48,660
לטוב או לרע.

14
00:00:48,660 --> 00:00:51,800
>> עכשיו מה שלפנינו, קבעה בעיה
שני הוא בידיים שלך לזה שבוע,

15
00:00:51,800 --> 00:00:53,830
אבל עם בעיה להגדיר
שלושה בשבוע הקרוב,

16
00:00:53,830 --> 00:00:56,600
אתה יהיה אתגר עם
המשחק כביכול של 15,

17
00:00:56,600 --> 00:00:58,960
לטובת צד ישנה ש
אולי אתה זוכר שקיבל

18
00:00:58,960 --> 00:01:02,030
כילד שיש לו כל חבורה
של מספרים שיכולים להחליק למעלה, למטה,

19
00:01:02,030 --> 00:01:05,790
שמאל וימין, ויש פער אחד
בתוך הפאזל, שאליו אתה

20
00:01:05,790 --> 00:01:07,840
למעשה יכול להחליק חלקי הפאזל אלו.

21
00:01:07,840 --> 00:01:11,150
סופו של דבר אתה מקבל את זה
חידה בקצת סדר אקראי למחצה,

22
00:01:11,150 --> 00:01:12,940
והמטרה היא
למיין אותו, מלמעלה למטה,

23
00:01:12,940 --> 00:01:16,310
משמאל לימין, מאחד
כל הדרך עד עד 15.

24
00:01:16,310 --> 00:01:19,360
>> למרבה הצער, היישום
יהיה לך ביד

25
00:01:19,360 --> 00:01:21,590
הולך להיות תוכנה
מבוסס, לא פיזי.

26
00:01:21,590 --> 00:01:25,280
למעשה, אתם תצטרכו לכתוב
קוד עם שפחית תלמיד או הוראות שימוש

27
00:01:25,280 --> 00:01:26,760
לשחק את המשחק של 15.

28
00:01:26,760 --> 00:01:29,030
ואכן, בהאקר
מהדורה של משחק של 15,

29
00:01:29,030 --> 00:01:32,155
אתה תהיה אתגר ליישם,
לא רק משחק של בית הספר הישן הזה

30
00:01:32,155 --> 00:01:35,010
משחק, אלא פתרון
שלו, יישום מצב האל,

31
00:01:35,010 --> 00:01:38,280
כביכול, שלמעשה
פותר את החידה לאדם,

32
00:01:38,280 --> 00:01:41,080
על ידי מתן אותם עם רמז,
לאחר רמז, לאחר רמז.

33
00:01:41,080 --> 00:01:42,280
אז עוד על כך בשבוע הבא.

34
00:01:42,280 --> 00:01:43,720
אבל זה מה שעומד לפנינו.

35
00:01:43,720 --> 00:01:47,610
>> לעת עתה זוכר שמוקדם יותר השבוע
היו לנו סחרור מסוכן זה, אם תרצה,

36
00:01:47,610 --> 00:01:52,560
לפי הכי טוב שאנחנו עושים מיון
החכם היה גבול עליון של גדול o של n

37
00:01:52,560 --> 00:01:53,210
בריבוע.

38
00:01:53,210 --> 00:01:56,520
במילים אחרות, מיון בועות,
מיון בחירה, מיון הכנסה,

39
00:01:56,520 --> 00:01:59,120
כולם, ואילו שונה
ביישומם,

40
00:01:59,120 --> 00:02:03,480
devolved לn בריבוע פועל
זמן במקרה הגרוע ביותר.

41
00:02:03,480 --> 00:02:06,010
ואנחנו בדרך כלל מניחים ש
המקרה הגרוע ביותר למיון

42
00:02:06,010 --> 00:02:08,814
הוא אחד שהתשומות שלך
הם לאחור לחלוטין.

43
00:02:08,814 --> 00:02:11,980
ואכן, זה לקח לא מעט צעדים
ליישם כל אחד מאלגוריתמים אלה.

44
00:02:11,980 --> 00:02:15,110
>> עכשיו ממש בסוף של כיתה
כזכור, השווינו מיון בועות

45
00:02:15,110 --> 00:02:19,390
נגד מיון בחירה נגד אחד אחר
שנקראים סוג מיזוג בזמן,

46
00:02:19,390 --> 00:02:22,120
ואני מציע שזה לוקח
יתרון של שיעור משבוע

47
00:02:22,120 --> 00:02:24,060
אפס, הפרד ומשול.

48
00:02:24,060 --> 00:02:28,810
ואיכשהו השיג איזשהו
לוגריתמי זמן ריצת סופו של דבר,

49
00:02:28,810 --> 00:02:31,024
במקום משהו
זה אך ורק ריבועית.

50
00:02:31,024 --> 00:02:33,440
וזה לא ממש לוגריתמים,
זה קצת יותר מזה.

51
00:02:33,440 --> 00:02:36,520
אבל אם אתה זוכר מכיתה,
זה היה הרבה, הרבה יותר מהר.

52
00:02:36,520 --> 00:02:38,210
בואו נסתכל בו הפסקנו.

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> מיון בועות לעומת בחירה
סוג לעומת סוג המיזוג.

55
00:02:45,370 --> 00:02:47,700
עכשיו כולם פועלים, ב
תאוריה, באותו הזמן.

56
00:02:47,700 --> 00:02:50,510
המעבד פועל באותה המהירות.

57
00:02:50,510 --> 00:02:54,990
אבל אתה יכול להרגיש איך זה משעמם
הוא הולך מהר מאוד להפוך ל,

58
00:02:54,990 --> 00:02:58,790
ורק כמה מהר, כאשר אנו מזריקים
קצת של השבוע אפס אלגוריתמים,

59
00:02:58,790 --> 00:03:00,080
אנחנו יכולים לזרז את העניינים.

60
00:03:00,080 --> 00:03:01,630
>> אז סוג הסימן נראה מדהים.

61
00:03:01,630 --> 00:03:05,220
איך אנחנו יכולים למנף אותו, כדי
כדי למיין מספרים במהירות רבים יותר.

62
00:03:05,220 --> 00:03:07,140
ובכן בואו נחשוב בחזרה
למרכיב ש

63
00:03:07,140 --> 00:03:10,380
היה בחזרה בשבוע אפס, כי ב
מחפש מישהו בספר טלפונים,

64
00:03:10,380 --> 00:03:12,380
וזוכר ש
פסאודו קוד שהצענו,

65
00:03:12,380 --> 00:03:14,560
באמצעותו אנו יכולים למצוא
מישהו כמו מייק סמית,

66
00:03:14,560 --> 00:03:16,310
נראה קצת משהו כזה.

67
00:03:16,310 --> 00:03:20,820
>> עכשיו תסתכל בפרט
בקו 7 ו -8, ו -10 ו -11,

68
00:03:20,820 --> 00:03:25,240
אשר יגרום ללולאה ש, לפיה המשכנו
חוזר לקו 3 שוב, ושוב,

69
00:03:25,240 --> 00:03:26,520
ושוב.

70
00:03:26,520 --> 00:03:31,790
אבל מתברר שאנחנו יכולים להציג
אלגוריתם זה, כאן בפסאודו קוד,

71
00:03:31,790 --> 00:03:33,620
קצת יותר הוליסטית.

72
00:03:33,620 --> 00:03:35,960
למעשה, מה שאני מחפש
בכאן על המסך,

73
00:03:35,960 --> 00:03:41,180
הוא אלגוריתם לחיפוש ל
מייק סמית בקרב חלק הקבוצה של דפים.

74
00:03:41,180 --> 00:03:45,520
ואכן, אנו יכולים לפשט את זה
אלגוריתם בקווים אלה 7 ו -8,

75
00:03:45,520 --> 00:03:49,860
ו -10 ו -11 לסתם אומרים את זה,
שאני כבר הצגתי כאן בצהוב.

76
00:03:49,860 --> 00:03:52,210
במילים אחרות, אם מייק
סמית 'היא קודם לכן בספר,

77
00:03:52,210 --> 00:03:55,004
אנחנו לא צריכים לציין צעד
צעד עכשיו איך ללכת למצוא אותו.

78
00:03:55,004 --> 00:03:56,920
אנחנו לא צריכים לציין
לחזור לקו 3,

79
00:03:56,920 --> 00:03:58,960
למה לא אנחנו רק במקום,
למשל, באופן כללי יותר,

80
00:03:58,960 --> 00:04:01,500
לחפש את מייק ב
מחצית השמאלית של הספר.

81
00:04:01,500 --> 00:04:03,960
>> לעומת זאת, אם מייק הוא
למעשה מאוחר יותר בספר,

82
00:04:03,960 --> 00:04:07,540
למה אנחנו לא רק לצטט חיפוש סוף ציטוט
למייק במחצית הימנית של הספר.

83
00:04:07,540 --> 00:04:11,030
במילים אחרות, למה לא אנחנו פשוט
סוג של הדוגית לעצמנו ואמר,

84
00:04:11,030 --> 00:04:13,130
לחפש את מייק בזה
משנה של הספר,

85
00:04:13,130 --> 00:04:16,279
ולהשאיר אותו לשלנו קיימת
אלגוריתם כדי לספר לנו

86
00:04:16,279 --> 00:04:18,750
איך לחפש את מייק ב
שמחצית השמאלית של הספר.

87
00:04:18,750 --> 00:04:20,750
במילים אחרות, שלנו
האלגוריתם עובד בין אם זה

88
00:04:20,750 --> 00:04:24,670
ספר טלפונים של עובי זה, זה
עובי, או כל עובי שהיא.

89
00:04:24,670 --> 00:04:27,826
אז אנחנו יכולים באופן רקורסיבי
להגדיר אלגוריתם זה.

90
00:04:27,826 --> 00:04:29,950
במילים אחרות, על
מסך כאן, הוא אלגוריתם

91
00:04:29,950 --> 00:04:33,130
לחיפוש למייק סמית
בין דפיו של ספר טלפונים.

92
00:04:33,130 --> 00:04:37,410
אז בשורת 7 ו -10, בואו
רק אומרים בדיוק את זה.

93
00:04:37,410 --> 00:04:40,250
ואני משתמש במונח זה רגע
לפני, ואכן, רקורסיה

94
00:04:40,250 --> 00:04:42,450
היא המילה האחרונה לעת עתה,
וזה תהליך זה

95
00:04:42,450 --> 00:04:47,210
לעשות משהו מחזורי על ידי איכשהו
באמצעות קוד שכבר יש לך,

96
00:04:47,210 --> 00:04:49,722
וקורא לזה שוב,
ושוב, ושוב.

97
00:04:49,722 --> 00:04:51,930
עכשיו זה הולך להיות חשוב
שאיכשהו תחתון

98
00:04:51,930 --> 00:04:53,821
החוצה, ולא עושה את זה לאין שיעור ארוך.

99
00:04:53,821 --> 00:04:56,070
אחרת אנחנו הולכים
יש אכן לולאה אינסופית.

100
00:04:56,070 --> 00:04:59,810
אבל בואו תראו אם אנחנו יכולים לשאול את הרעיון הזה
של רקורסיה, עושה משהו שוב

101
00:04:59,810 --> 00:05:03,600
ושוב ושוב, כדי לפתור
הבעיה המיון באמצעות מיזוג

102
00:05:03,600 --> 00:05:05,900
סוג, כל ביעילות רבה יותר.

103
00:05:05,900 --> 00:05:06,970
>> אז אני נותן לך למזג סוג.

104
00:05:06,970 --> 00:05:07,920
בואו נסתכל.

105
00:05:07,920 --> 00:05:10,850
אז הנה הוא פסאודו קוד, עם
שבו אנו יכולים ליישם מיון,

106
00:05:10,850 --> 00:05:12,640
באמצעות אלגוריתם זה נקרא סוג מיזוג.

107
00:05:12,640 --> 00:05:13,880
וזה די פשוט זה.

108
00:05:13,880 --> 00:05:15,940
על קלט של אלמנטי n,
במילים אחרות, אם אתה

109
00:05:15,940 --> 00:05:18,830
ניתנו n אלמנטים ומספרים ו
אותיות או מה שהקלט הוא,

110
00:05:18,830 --> 00:05:22,430
אם אתה נתון אלמנטי n, אם
n הוא פחות מ -2, רק לחזור.

111
00:05:22,430 --> 00:05:22,930
נכון?

112
00:05:22,930 --> 00:05:26,430
כי אם n הוא פחות מ -2, ש
משמעות הדבר היא שרשימת המרכיבים שלי

113
00:05:26,430 --> 00:05:30,446
הוא אחד מהגודל 0 או 1, ו
בשני המקרים האלה של מה בכך,

114
00:05:30,446 --> 00:05:31,570
הרשימה כבר ממוינת.

115
00:05:31,570 --> 00:05:32,810
אם אין רשימה, זה מסודרים.

116
00:05:32,810 --> 00:05:35,185
ואם יש רשימה של אורך
1, זה ברור שמסודר.

117
00:05:35,185 --> 00:05:38,280
אז האלגוריתם צריך רק
באמת לעשות משהו מעניין,

118
00:05:38,280 --> 00:05:40,870
אם יש לנו שניים או יותר
אלמנטים שניתנו לנו.

119
00:05:40,870 --> 00:05:42,440
אז בואו נסתכל בקסם אז.

120
00:05:42,440 --> 00:05:47,500
אחר למיין את המחצית השמאלית של האלמנטים,
אז למיין את המחצית הימנית של אלמנטים,

121
00:05:47,500 --> 00:05:49,640
לאחר מכן למזג את החצאים מסודרים.

122
00:05:49,640 --> 00:05:52,440
ומה סוג של מוח כיפוף
כאן, הוא שאני לא ממש

123
00:05:52,440 --> 00:05:56,190
נראה שיש לך
שום דבר עדיין, נכון?

124
00:05:56,190 --> 00:05:59,560
כל מה שאמרתי הוא, קבל רשימה של
n אלמנטים, למיין את החצי השמאלי,

125
00:05:59,560 --> 00:06:01,800
אז המחצית תקין, אז
למזג את החצאים מסודרים,

126
00:06:01,800 --> 00:06:03,840
אבל איפה הוא הרוטב הסודי בפועל?

127
00:06:03,840 --> 00:06:05,260
איפה האלגוריתם?

128
00:06:05,260 --> 00:06:09,150
ובכן מתברר ששני קווים אלה
ראשון, מחצית השאירה סוג של אלמנטים,

129
00:06:09,150 --> 00:06:13,970
וסוג נכון מחצית אלמנטים,
שיחות רקורסיבית, כביכול.

130
00:06:13,970 --> 00:06:16,120
>> אחרי הכל, בשלב זה
נקודת הזמן לעשות, יש לי

131
00:06:16,120 --> 00:06:18,950
אלגוריתם שבי ל
למיין את חבורה של אלמנטים שלמה?

132
00:06:18,950 --> 00:06:19,450
כן.

133
00:06:19,450 --> 00:06:20,620
זה ממש כאן.

134
00:06:20,620 --> 00:06:25,180
זה ממש כאן על המסך, ו
אז אני יכול להשתמש באותו סט של צעדים

135
00:06:25,180 --> 00:06:28,500
כדי למיין את החצי השמאלי,
שאני יכול חצי הנכון.

136
00:06:28,500 --> 00:06:30,420
ואכן, שוב, ושוב.

137
00:06:30,420 --> 00:06:34,210
אז איכשהו או אחר, ואנחנו בקרוב
רואה את זה, את הקסם מסוג המיזוג

138
00:06:34,210 --> 00:06:37,967
מוטבע שבמאוד סופי
קו, מיזוג החצאים הממוינים.

139
00:06:37,967 --> 00:06:39,300
וזה נראה די אינטואיטיבי.

140
00:06:39,300 --> 00:06:41,050
אתה לוקח שני חצאים, ואתה,
איכשהו, למזג אותם יחד,

141
00:06:41,050 --> 00:06:43,260
ואנו רואים את זה
באופן קונקרטי ברגע.

142
00:06:43,260 --> 00:06:45,080
>> אבל זה אלגוריתם מלא.

143
00:06:45,080 --> 00:06:46,640
ובואו לראות בדיוק למה.

144
00:06:46,640 --> 00:06:50,912
ובכן נניח שאנו נקבל אותו אלה
שמונה אלמנטים כאן על המסך, אחד

145
00:06:50,912 --> 00:06:53,120
דרך שמונה, אבל הם
כדי אקראי לכאורה.

146
00:06:53,120 --> 00:06:55,320
והמטרה בהישג היד היא
כדי למיין אלמנטים אלה.

147
00:06:55,320 --> 00:06:58,280
ובכן איך אני יכול ללכת על
עושה את זה באמצעות, שוב,

148
00:06:58,280 --> 00:07:00,407
מיון מיזוג, לפי פסאודו קוד זה?

149
00:07:00,407 --> 00:07:02,740
ושוב, זה להשריש ב
דעתך, רק לרגע.

150
00:07:02,740 --> 00:07:05,270
המקרה הראשון הוא די
טריוויאלי, אם זה פחות מ -2,

151
00:07:05,270 --> 00:07:07,060
רק לחזור, אין עבודה לעשות.

152
00:07:07,060 --> 00:07:09,290
אז באמת יש רק שלושה
צעדים באמת לזכור.

153
00:07:09,290 --> 00:07:11,081
שוב, ושוב, אני
הולך רוצה להיות

154
00:07:11,081 --> 00:07:13,980
כדי למיין את החצי השמאלי,
למיין את המחצית הימנית,

155
00:07:13,980 --> 00:07:15,890
ולאחר מכן פעם שלהם
שני חצאים מסודרים,

156
00:07:15,890 --> 00:07:18,710
אני רוצה למזג אותם יחד
לרשימה אחת ממוינת.

157
00:07:18,710 --> 00:07:19,940
אז לשמור את זה בחשבון.

158
00:07:19,940 --> 00:07:21,310
>> אז הנה הרשימה המקורית.

159
00:07:21,310 --> 00:07:23,510
בואו נתייחס לכך כ
מערך, שהתחלנו

160
00:07:23,510 --> 00:07:25,800
בשבוע שני, שהוא
גוש רציף של זיכרון.

161
00:07:25,800 --> 00:07:28,480
במקרה זה, המכיל שמונה
מספרים, גב אל גב אל גב.

162
00:07:28,480 --> 00:07:30,700
ובואו עכשיו להחיל סוג מיזוג.

163
00:07:30,700 --> 00:07:33,300
אז אני רוצה ראשון כדי למיין
המחצית השמאלית של רשימה זו,

164
00:07:33,300 --> 00:07:37,370
ובואו, ולכן,
להתמקד ב4, 8, 6, ו -2.

165
00:07:37,370 --> 00:07:41,000
>> עכשיו איך אני הולך על
מיון רשימה של גודל 4?

166
00:07:41,000 --> 00:07:45,990
ובכן, אני צריך לשקול עכשיו
מיון השמאלי של החצי השמאלי.

167
00:07:45,990 --> 00:07:47,720
שוב, בואו אחורה לרגע.

168
00:07:47,720 --> 00:07:51,010
אם פסאודו הקוד הוא זו,
ואני מקבל שמונה אלמנטים,

169
00:07:51,010 --> 00:07:53,230
8 הוא ללא ספק גדול יותר
או שווה ל 2.

170
00:07:53,230 --> 00:07:54,980
אז עם המקרה הראשון אינו חל.

171
00:07:54,980 --> 00:07:58,120
אז למיין שמונה אלמנטים, אני ראשון
למיין את המחצית השמאלית של אלמנטים,

172
00:07:58,120 --> 00:08:01,930
אז אני למיין את המחצית תקין, אז אני למזג
שני החצאים ממוינים, כל אחד מגודל 4.

173
00:08:01,930 --> 00:08:02,470
אוקיי.

174
00:08:02,470 --> 00:08:07,480
>> אבל אם יש לך רק אמר לי, למיין
מחצית השמאלית, שנמצא כעת בגודל 4,

175
00:08:07,480 --> 00:08:09,350
איך אני למיין את המחצית השמאלית?

176
00:08:09,350 --> 00:08:11,430
ובכן, אם יש לי
קלט של ארבעה יסודות,

177
00:08:11,430 --> 00:08:14,590
אני למיין את השמאל ראשון
שני, אז שני תקין,

178
00:08:14,590 --> 00:08:16,210
ואז אני למזג אותם יחד.

179
00:08:16,210 --> 00:08:18,700
אז שוב, זה הופך להיות קצת
של מוח כיפוף משחק כאן,

180
00:08:18,700 --> 00:08:21,450
כי אתה, סוג של, צריכים
זוכר איפה אתה בסיפור,

181
00:08:21,450 --> 00:08:23,620
אבל בסופו של היום,
ניתנו כל מספר של אלמנטים,

182
00:08:23,620 --> 00:08:25,620
אתה רוצה ראשון כדי למיין
מחצית השמאלית, אז חצי הנכון,

183
00:08:25,620 --> 00:08:26,661
אז למזג אותם יחד.

184
00:08:26,661 --> 00:08:28,630
בואו נתחיל לעשות בדיוק את זה.

185
00:08:28,630 --> 00:08:30,170
הנה הקלט של שמונה אלמנטים.

186
00:08:30,170 --> 00:08:31,910
עכשיו אנחנו מסתכלים על החצי השמאלי כאן.

187
00:08:31,910 --> 00:08:33,720
איך אוכל למיין את ארבעה יסודות?

188
00:08:33,720 --> 00:08:35,610
ובכן אני למיין את המחצית ראשונה עזבה.

189
00:08:35,610 --> 00:08:37,720
עכשיו איך אני למיין את המחצית השמאלית?

190
00:08:37,720 --> 00:08:39,419
ובכן כבר נתן לי שני אלמנטים.

191
00:08:39,419 --> 00:08:41,240
אז בואו למיין את שני האלמנטים הללו.

192
00:08:41,240 --> 00:08:44,540
2 גדול או
שווה ל 2, כמובן.

193
00:08:44,540 --> 00:08:46,170
כך שהמקרה הראשון אינו חל.

194
00:08:46,170 --> 00:08:49,010
>> אז עכשיו אני צריך למיין השמאל
מחציתם של שני אלמנטים אלה.

195
00:08:49,010 --> 00:08:50,870
המחצית השמאלית, כמובן, היא רק 4.

196
00:08:50,870 --> 00:08:54,020
אז איך אני למיין את הרשימה של אלמנט אחד?

197
00:08:54,020 --> 00:08:57,960
ובכן עכשיו, כי במקרה של בסיס מיוחד
למעלה, כביכול, חל.

198
00:08:57,960 --> 00:09:01,470
1 הוא פחות מ -2, ושלי
רשימה היא אכן בגודל 1.

199
00:09:01,470 --> 00:09:02,747
אז אני פשוט לחזור.

200
00:09:02,747 --> 00:09:03,580
אני לא עושה שום דבר.

201
00:09:03,580 --> 00:09:06,770
ואכן, להסתכל על מה שיש לי
נעשה, 4 כבר מסודרים.

202
00:09:06,770 --> 00:09:09,220
כמו שאני כבר
מוצלח באופן חלקי כאן.

203
00:09:09,220 --> 00:09:11,750
>> עכשיו זה נראה די טיפשי
לטעון, אבל זה נכון.

204
00:09:11,750 --> 00:09:13,700
4 רשימה של גודל 1.

205
00:09:13,700 --> 00:09:15,090
זה כבר מסודרים.

206
00:09:15,090 --> 00:09:16,270
זה המחצית השמאלית.

207
00:09:16,270 --> 00:09:18,010
עכשיו אני למיין את המחצית הימנית.

208
00:09:18,010 --> 00:09:22,310
הקלט שלי הוא אלמנט אחד, 8
באופן דומה, כבר מסודרים.

209
00:09:22,310 --> 00:09:25,170
טיפש, מדי, אבל שוב,
עיקרון בסיסי זה

210
00:09:25,170 --> 00:09:28,310
הוא הולך כדי לאפשר לנו לבנות החברה
על גבי זה בהצלחה.

211
00:09:28,310 --> 00:09:32,260
4 מסודרים, 8 ממוינים, עכשיו
מה זה היה השלב אחרון?

212
00:09:32,260 --> 00:09:35,330
אז השלב השלישי ואחרון, כל
זמן שאתה מיון רשימה, כזכור,

213
00:09:35,330 --> 00:09:38,310
היה למזג את שני חצאים,
השמאל והימין.

214
00:09:38,310 --> 00:09:39,900
אז בואו לעשות בדיוק את זה.

215
00:09:39,900 --> 00:09:41,940
המחצית השמאלית שלי היא, כמובן, 4.

216
00:09:41,940 --> 00:09:43,310
המחצית הימנית שלי היא 8.

217
00:09:43,310 --> 00:09:44,100
>> אז בואו נעשה את זה.

218
00:09:44,100 --> 00:09:46,410
ראשית אני הולך להקצות
כמה זיכרון נוסף,

219
00:09:46,410 --> 00:09:48,680
שאני מייצג כאן,
כפשוט מערך המשני,

220
00:09:48,680 --> 00:09:49,660
זה גדול מספיק כדי להתאים את זה.

221
00:09:49,660 --> 00:09:52,243
אבל אתה יכול לדמיין הארכה
מלבן שכל האורך,

222
00:09:52,243 --> 00:09:53,290
אם אנחנו צריכים יותר מאוחר.

223
00:09:53,290 --> 00:09:58,440
איך אני לוקח 4 ו -8, ולמזג
שתי רשימות של גודל 1 יחד אלה?

224
00:09:58,440 --> 00:10:00,270
גם כאן, די פשוט.

225
00:10:00,270 --> 00:10:03,300
4 מגיע ראשון, ואז מגיעים 8.

226
00:10:03,300 --> 00:10:07,130
כי אם אני רוצה למיין
מחצית השמאלית, אז חצי הנכון,

227
00:10:07,130 --> 00:10:09,900
ואז למזג את שני חצאים אלה
יחד, בסדר ממוינים,

228
00:10:09,900 --> 00:10:11,940
4 מגיע ראשון, ואז מגיעים 8.

229
00:10:11,940 --> 00:10:15,810
>> אז אנחנו נראים התקדמות, אפילו
אם כי לא עשיתי שום עבודה בפועל.

230
00:10:15,810 --> 00:10:17,800
אך יש לזכור איפה אנחנו בסיפור.

231
00:10:17,800 --> 00:10:19,360
אנחנו במקור לקחנו שמונה אלמנטים.

232
00:10:19,360 --> 00:10:21,480
אנחנו מסודרים במחצית השמאלית, שהוא 4.

233
00:10:21,480 --> 00:10:24,450
אז אנחנו מסודרים המחצית השמאלית
במחצית השמאלית, שהייתה 2.

234
00:10:24,450 --> 00:10:25,270
וכאן אנחנו הולכים.

235
00:10:25,270 --> 00:10:26,920
סיימנו עם צעד ש.

236
00:10:26,920 --> 00:10:29,930
>> אז אם אנחנו כבר מסודרים
השארנו מחצית 2, עכשיו אנחנו

237
00:10:29,930 --> 00:10:32,130
צריך למיין המחצית הימנית של 2.

238
00:10:32,130 --> 00:10:35,710
אז המחצית הימנית של 2 היא
שני ערכים אלה כאן, 6 ו -2.

239
00:10:35,710 --> 00:10:40,620
אז בואו עכשיו לקחת קלט בגודל
2, ולמיין את המחצית השמאלית, ולאחר מכן

240
00:10:40,620 --> 00:10:42,610
המחצית הימנית, ולאחר מכן
למזג אותם יחד.

241
00:10:42,610 --> 00:10:45,722
ובכן איך אני למיין את הרשימה של גודל
1, המכיל רק את המספר 6?

242
00:10:45,722 --> 00:10:46,430
אני כבר עשיתי.

243
00:10:46,430 --> 00:10:48,680
הרשימה של גודל 1 ממוינת.

244
00:10:48,680 --> 00:10:52,140
>> איך אוכל למיין את רשימה נוספת של
גודל 1, המחצית תקין כביכול.

245
00:10:52,140 --> 00:10:54,690
ובכן זה, גם הוא כבר מסודרים.

246
00:10:54,690 --> 00:10:56,190
המספר 2 הוא לבד.

247
00:10:56,190 --> 00:11:00,160
אז עכשיו יש לי שני חצאים, עזב ו
נכון, אני צריך למזג אותם יחד.

248
00:11:00,160 --> 00:11:01,800
תן לי לתת לעצמי קצת שטח נוסף.

249
00:11:01,800 --> 00:11:05,580
ולשים 2 שם,
אז יש 6 ב, ובכך

250
00:11:05,580 --> 00:11:10,740
מיון רשימה ש, שמאל וימין,
ומיזוג זה ביחד, בסופו.

251
00:11:10,740 --> 00:11:12,160
אז אני בכושר קצת יותר טוב.

252
00:11:12,160 --> 00:11:16,250
אני לא עשיתי, כי בבירור 4, 8, 2,
6 הוא לא ההזמנה הסופית שאני רוצה.

253
00:11:16,250 --> 00:11:20,640
אבל עכשיו יש לי שתי רשימות של גודל 2, ש
שניהם, בהתאמה, מוין.

254
00:11:20,640 --> 00:11:24,580
אז עכשיו אם אתה אחורה במוחו שלך
עין, איפה זה מעמיד אותנו?

255
00:11:24,580 --> 00:11:28,520
התחלתי עם שמונה אלמנטים, אז אני
גלף אותו למחצית השמאלית של 4,

256
00:11:28,520 --> 00:11:31,386
אז המחצית השמאלית של 2, ו
אז המחצית הימנית של 2,

257
00:11:31,386 --> 00:11:34,510
סיימתי, ולכן, מיון השמאל
מחצית 2, והמחצית הימנית של 2,

258
00:11:34,510 --> 00:11:37,800
אז מה הצעד השלישי והאחרון כאן?

259
00:11:37,800 --> 00:11:41,290
אני צריך למזג יחד
שתי רשימות של גודל 2.

260
00:11:41,290 --> 00:11:42,040
אז בואו נלך קדימה.

261
00:11:42,040 --> 00:11:43,940
ועל המסך כאן, לתת
לי זיכרון נוסף,

262
00:11:43,940 --> 00:11:47,170
למרות מבחינה טכנית, שם לב שיש לי
יש חבורה של ראש המרחב ריק עד כל

263
00:11:47,170 --> 00:11:47,670
שם.

264
00:11:47,670 --> 00:11:50,044
אם אני רוצה להיות במיוחד
מרחב יעיל חכם,

265
00:11:50,044 --> 00:11:52,960
אני יכול פשוט להתחיל לנוע האלמנטים
הלוך ושוב, עליון ותחתון.

266
00:11:52,960 --> 00:11:55,460
אבל רק לבהירות חזותית,
אני הולך לשים אותו בהמשך,

267
00:11:55,460 --> 00:11:56,800
כדי לשמור על דברים יפים ונקי.

268
00:11:56,800 --> 00:11:58,150
>> אז יש לי שתי רשימות של גודל 2.

269
00:11:58,150 --> 00:11:59,770
יש הרשימה הראשונה 4 ו -8.

270
00:11:59,770 --> 00:12:01,500
יש הרשימה השנייה 2 ו -6.

271
00:12:01,500 --> 00:12:03,950
בואו למזג אלה
יחד בסדר ממוין.

272
00:12:03,950 --> 00:12:09,910
2, כמובן, מגיע ראשון,
אז 4, ולאחר מכן 6, לאחר מכן 8.

273
00:12:09,910 --> 00:12:12,560
ועכשיו אנחנו נראים מקבלים
מעניין איפשהו.

274
00:12:12,560 --> 00:12:15,720
מחצית עכשיו אני כבר מסודרים של
רשימה, ומקרה, זה

275
00:12:15,720 --> 00:12:18,650
כל המספרים אפילו, אבל ש
הוא, אכן, רק צירוף מקרים.

276
00:12:18,650 --> 00:12:22,220
ויש לי עכשיו מסודרים מהשמאל
מחצית, כך שזה 2, 4, 6, ו -8.

277
00:12:22,220 --> 00:12:23,430
שום דבר לא מקולקל.

278
00:12:23,430 --> 00:12:24,620
זה מרגיש כמו התקדמות.

279
00:12:24,620 --> 00:12:26,650
>> עכשיו זה מרגיש כמו לי
דיבר לנצח עכשיו,

280
00:12:26,650 --> 00:12:29,850
אז מה נותר לראות אם זה
אלגוריתם הוא, אכן, יעיל יותר.

281
00:12:29,850 --> 00:12:31,766
אבל אנחנו עוברים
זה סופר באופן שיטתי.

282
00:12:31,766 --> 00:12:34,060
מחשב, כמובן,
יעשה את זה כמו ש.

283
00:12:34,060 --> 00:12:34,840
אז איפה אנחנו?

284
00:12:34,840 --> 00:12:36,180
התחלנו עם שמונה אלמנטים.

285
00:12:36,180 --> 00:12:37,840
אני מסודרים במחצית השמאלית של 4.

286
00:12:37,840 --> 00:12:39,290
נדמה לי שניתן לעשות עם זה.

287
00:12:39,290 --> 00:12:42,535
אז עכשיו השלב הבא הוא
למיין את המחצית הימנית של 4.

288
00:12:42,535 --> 00:12:44,410
והחלק הזה אנחנו יכולים ללכת
דרך קצת יותר

289
00:12:44,410 --> 00:12:47,140
במהירות, למרות שאתה
מוזמן להריץ אחורה או להשהות, רק

290
00:12:47,140 --> 00:12:49,910
חושב דרכו ב
קצב שלך, אבל מה ש

291
00:12:49,910 --> 00:12:53,290
יש לנו עכשיו הזדמנות
לעשות בדיוק את אותו האלגוריתם על ארבעה

292
00:12:53,290 --> 00:12:54,380
מספרים שונים.

293
00:12:54,380 --> 00:12:57,740
>> אז בואו נלך קדימה, ולהתמקד ב
המחצית תקין, שבו אנו נמצאים כאן.

294
00:12:57,740 --> 00:13:01,260
המחצית השמאלית של ש
מחצית תקין, ועכשיו

295
00:13:01,260 --> 00:13:04,560
מחצית השמאלית של השמאל
מחצית שמחצית ימנית,

296
00:13:04,560 --> 00:13:08,030
ואיך אני למיין את הרשימה של גודל
1 המכיל רק את המספר 1?

297
00:13:08,030 --> 00:13:09,030
זה כבר נעשה.

298
00:13:09,030 --> 00:13:11,830
איך אני עושה את אותו הדבר עבור רשימה
גודל 1 המכיל רק 7?

299
00:13:11,830 --> 00:13:12,840
זה כבר נעשה.

300
00:13:12,840 --> 00:13:16,790
שלב שלישי למחצית לאחר מכן
הוא למזג את שני אלמנטים אלה

301
00:13:16,790 --> 00:13:20,889
לרשימה חדשה של גודל 2, 1 ו -7.

302
00:13:20,889 --> 00:13:23,180
לא נראה שעשה את כל
כל כך הרבה עבודה מעניינת.

303
00:13:23,180 --> 00:13:24,346
בואו לראות מה קורה הלאה.

304
00:13:24,346 --> 00:13:29,210
אני פשוט מסודרים המחצית השמאלית של
מחצית ימנית של הקלט המקורי שלי.

305
00:13:29,210 --> 00:13:32,360
עכשיו בואו למיין תקין
מחצית, המכילה 5 ו -3.

306
00:13:32,360 --> 00:13:35,740
בואו נסתכל שוב בשמאל
מחצית, מסודרים, נכון מחצית, מסודרים,

307
00:13:35,740 --> 00:13:39,120
ולמזג את שני אלה יחד,
לכמה שטח נוסף,

308
00:13:39,120 --> 00:13:41,670
3 מגיע ראשון, ואז מגיעים 5.

309
00:13:41,670 --> 00:13:46,190
אז עכשיו, יש לנו מסודרים
מחצית השמאלית של החצי הימני

310
00:13:46,190 --> 00:13:49,420
הבעיה המקורית, ו
המחצית הימנית של החצי הימני

311
00:13:49,420 --> 00:13:50,800
של הבעיה המקורית.

312
00:13:50,800 --> 00:13:52,480
מה שלב השלישי ואחרון?

313
00:13:52,480 --> 00:13:54,854
ובכן למזג את שני חצאים אלה יחד.

314
00:13:54,854 --> 00:13:57,020
אז תן לי לקבל את עצמי כמה
שטח נוסף, אבל, שוב, אני

315
00:13:57,020 --> 00:13:58,699
יכול להיות שהשימוש בחלל העליון עד החילוף.

316
00:13:58,699 --> 00:14:00,490
אבל אנחנו הולכים לשמור
זה פשוט מבחינה ויזואלית.

317
00:14:00,490 --> 00:14:07,070
תן לי להתמזג בחברת 1, ו
לאחר מכן 3, ולאחר מכן 5, ולאחר מכן 7.

318
00:14:07,070 --> 00:14:10,740
וכך השאיר אותי עכשיו עם
מחצית ימנית של הבעיה המקורית

319
00:14:10,740 --> 00:14:12,840
זה מסודרים בצורה מושלמת.

320
00:14:12,840 --> 00:14:13,662
>> אז מה נשאר?

321
00:14:13,662 --> 00:14:16,120
אני מרגיש שאני חוזר ואומר
אותם דברים שוב, ושוב,

322
00:14:16,120 --> 00:14:18,700
אבל זה משקף את
עובדה שאנחנו משתמשים ברקורסיה.

323
00:14:18,700 --> 00:14:21,050
התהליך של שימוש
אלגוריתם שוב, ושוב,

324
00:14:21,050 --> 00:14:23,940
בתת קטן יותר של
הבעיה המקורית.

325
00:14:23,940 --> 00:14:27,580
אז יש לי עכשיו שמאל מסודרים
מחצית מהבעיה המקורית.

326
00:14:27,580 --> 00:14:30,847
יש לי מחצית ממוינת תקין
של הבעיה המקורית.

327
00:14:30,847 --> 00:14:32,180
מה השלב השלישי וסופי?

328
00:14:32,180 --> 00:14:33,590
הו, זה מיזוג.

329
00:14:33,590 --> 00:14:34,480
אז בואו נעשה את זה.

330
00:14:34,480 --> 00:14:36,420
בואו להקצות חלק נוסף
זיכרון, אבל אלוהים שלי, אנחנו

331
00:14:36,420 --> 00:14:37,503
יכול לשים את זה בכל מקום עכשיו.

332
00:14:37,503 --> 00:14:40,356
יש לנו כל כך הרבה שטח פנוי
לנו, אבל אנחנו נשמור את זה פשוט.

333
00:14:40,356 --> 00:14:42,730
במקום ללכת אחורה ו
שוב עם הזיכרון המקורי שלנו,

334
00:14:42,730 --> 00:14:44,480
בואו פשוט לעשות את זה
מבחינה ויזואלית כאן למטה למטה,

335
00:14:44,480 --> 00:14:47,240
כדי לסיים את המיזוג
מחצית השמאלית וחצי תקין.

336
00:14:47,240 --> 00:14:49,279
>> אז על ידי מיזוג, מה אני צריך לעשות?

337
00:14:49,279 --> 00:14:50,820
אני רוצה לקחת את האלמנטים לפי סדר.

338
00:14:50,820 --> 00:14:53,230
אז מסתכל על החצי השמאלי,
אני רואה את המספר הראשון הוא 2.

339
00:14:53,230 --> 00:14:55,230
אני מסתכל על המחצית הימנית,
אני רואה את המספר הראשון

340
00:14:55,230 --> 00:14:58,290
הוא 1, אז ברור ש
מספר אני רוצה לקטוף את,

341
00:14:58,290 --> 00:15:00,430
ולשים ראשון ברשימה הסופית שלי?

342
00:15:00,430 --> 00:15:01,449
כמובן, 1.

343
00:15:01,449 --> 00:15:02,990
עכשיו אני רוצה לשאול את אותה שאלה.

344
00:15:02,990 --> 00:15:05,040
במחצית השמאלית, לי
עדיין יש המספר 2.

345
00:15:05,040 --> 00:15:07,490
במחצית הימנית,
יש לי המספר 3.

346
00:15:07,490 --> 00:15:08,930
איזה מהם אני רוצה לבחור?

347
00:15:08,930 --> 00:15:11,760
כמובן, מספר 2 ו
עכשיו שמו לב המועמדים

348
00:15:11,760 --> 00:15:13,620
4 בצד השמאל, 3 בצד הימין.

349
00:15:13,620 --> 00:15:15,020
בואו, כמובן, לבחור 3.

350
00:15:15,020 --> 00:15:18,020
עכשיו המועמדים הם 4 ב
השמאל, 5 בצד הימין.

351
00:15:18,020 --> 00:15:19,460
אנחנו, כמובן, לבחור 4.

352
00:15:19,460 --> 00:15:21,240
6 משמאל, 5 בצד הימין.

353
00:15:21,240 --> 00:15:22,730
אנחנו, כמובן, לבחור 5.

354
00:15:22,730 --> 00:15:25,020
6 בצד השמאל, 7 בצד הימין.

355
00:15:25,020 --> 00:15:29,320
אנו בוחרים 6, ולאחר מכן אנחנו
לבחור 7, ולאחר מכן אנו בוחרים 8.

356
00:15:29,320 --> 00:15:30,100
וואלה.

357
00:15:30,100 --> 00:15:34,370
>> אז מספר עצום של מילות מאוחר יותר, אנחנו
יש מסודרים רשימה זו של שמונה אלמנטים

358
00:15:34,370 --> 00:15:38,450
לרשימה של אחד עד שמונה,
זה הולך וגדל עם כל צעד,

359
00:15:38,450 --> 00:15:40,850
אבל כמה זמן עשה
זה ייקח לנו לעשות את זה.

360
00:15:40,850 --> 00:15:43,190
ובכן יש לי במכוון
הנחנו את דברים באופן ציורי

361
00:15:43,190 --> 00:15:46,330
כאן, כך שנוכל סוג של
לראות או להעריך את החלוקה

362
00:15:46,330 --> 00:15:49,060
בכיבוש שכבר קורה.

363
00:15:49,060 --> 00:15:52,830
>> ואכן, אם אתה מסתכל אחורה על שרות,
אני כבר עזבתי את כל קווים מקווקווים אלה

364
00:15:52,830 --> 00:15:55,660
בבעלי המקום, שאתה יכול,
סוג של, לראות, בסדר הפוכים,

365
00:15:55,660 --> 00:15:58,800
אם אתה סוג של להסתכל אחורה ב
ההיסטוריה עכשיו, הרשימה המקורית שלי

366
00:15:58,800 --> 00:16:00,250
הוא, כמובן, בגודל 8.

367
00:16:00,250 --> 00:16:03,480
ולאחר מכן בעבר, הייתי
התמודדות עם שתי רשימות של גודל 4,

368
00:16:03,480 --> 00:16:08,400
ולאחר מכן ארבע רשימות של גודל 2,
ואז שמונה רשימות של גודל 1.

369
00:16:08,400 --> 00:16:10,151
>> אז מה עושה את זה,
סוג של, מזכיר לך?

370
00:16:10,151 --> 00:16:11,858
ובכן, אכן, כל אחד מ
האלגוריתמים יש לנו

371
00:16:11,858 --> 00:16:14,430
הביט בעד כה שבו אנחנו
פער, ופער, ופער,

372
00:16:14,430 --> 00:16:19,500
לשמור על ששוב דברים, ו
שוב, תוצאות ברעיון כללי זה.

373
00:16:19,500 --> 00:16:23,100
וכך יש משהו
לוגריתמים קורה כאן.

374
00:16:23,100 --> 00:16:26,790
וזה לא די יומן של n, אבל
יש רכיב לוגריתמים

375
00:16:26,790 --> 00:16:28,280
למה רק שעשינו.

376
00:16:28,280 --> 00:16:31,570
>> עכשיו בואו רואים כמה שהוא למעשה.

377
00:16:31,570 --> 00:16:34,481
אז להיכנס של n, שוב היה
זמן ריצה נהדר,

378
00:16:34,481 --> 00:16:36,980
כשעשינו משהו כמו
החיפוש בינארי, כמו עכשיו אנחנו קוראים לזה,

379
00:16:36,980 --> 00:16:40,090
אסטרטגית הפרד ומשול
באמצעותו אנו נמצאים מייק סמית.

380
00:16:40,090 --> 00:16:41,020
עכשיו מבחינה טכנית.

381
00:16:41,020 --> 00:16:43,640
זה יומן בסיס 2 של n, אפילו
אם כי ברוב שיעורי מתמטיקה,

382
00:16:43,640 --> 00:16:45,770
10 בדרך כלל הוא הבסיס שאתה מניח.

383
00:16:45,770 --> 00:16:48,940
אבל מדעני מחשב כמעט תמיד
לחשוב ולדבר במונחים של בסיס 2,

384
00:16:48,940 --> 00:16:52,569
ולכן אנחנו בדרך כלל רק לומר יומן של
n, במקום יומן בסיס 2 של n,

385
00:16:52,569 --> 00:16:55,110
אבל הם בדיוק אחד ו
אותו הדבר בעולם של מחשב

386
00:16:55,110 --> 00:16:57,234
מדע, וכמאמר מוסגר,
יש גורם קבוע

387
00:16:57,234 --> 00:17:01,070
הבדל בין שתיים, כך שזה
שנוי במחלוקת בכל מקרה, לעוד סיבות רשמיות.

388
00:17:01,070 --> 00:17:04,520
>> אבל לעת עתה, מה אכפת לנו
עליו היא דוגמא זו.

389
00:17:04,520 --> 00:17:08,520
אז בואו לא להוכיח על ידי דוגמא, אבל ב
לפחות להשתמש דוגמא של המספרים

390
00:17:08,520 --> 00:17:10,730
ביד כבדיקת שפיות, אם תרצה.

391
00:17:10,730 --> 00:17:14,510
אז בעבר הנוסחה הייתה בסיס יומן
2 של n, אבל מה הוא n במקרה זה.

392
00:17:14,510 --> 00:17:18,526
היה לי מספרי n מקוריים, או 8
במיוחד של מספר המקורי.

393
00:17:18,526 --> 00:17:20,359
עכשיו זה היה קצת
זמן, אבל אני די

394
00:17:20,359 --> 00:17:25,300
בטוח שיומן בסיס 2
של הערך 8 הוא 3,

395
00:17:25,300 --> 00:17:29,630
ואכן, מה שיפה שהוא
כי 3 הוא המספר בדיוק פעמים

396
00:17:29,630 --> 00:17:33,320
שאתה יכול לחלק את רשימה
אורך 8 שוב, ושוב,

397
00:17:33,320 --> 00:17:36,160
ושוב, עד שאתה נשאר
עם רשימות של רק גודל 1.

398
00:17:36,160 --> 00:17:36,660
נכון?

399
00:17:36,660 --> 00:17:40,790
8 הולכים ל4, הולך 2,
הולך עד 1, וזה

400
00:17:40,790 --> 00:17:43,470
רעיוני של בדיוק את זה
תמונה שהיו לנו רק לפני רגע.

401
00:17:43,470 --> 00:17:47,160
אז קצת שפיות לבדוק היכן
הלוגריתם מעורב בפועל.

402
00:17:47,160 --> 00:17:50,180
>> אז עכשיו, מה עוד הוא מעורב כאן? n.

403
00:17:50,180 --> 00:17:53,440
אז שם לב שכל
הזמן לפצל את הרשימה,

404
00:17:53,440 --> 00:17:58,260
אם כי בסדר הפוכים בהיסטוריה
כאן, אני עדיין עושה דברים n.

405
00:17:58,260 --> 00:18:02,320
כי צעד המיזוג הנדרש ש
אני נוגע בכל אחד מהמספרים,

406
00:18:02,320 --> 00:18:05,060
כדי להחליק אותו לתוך
המיקום המתאים שלה.

407
00:18:05,060 --> 00:18:10,760
אז למרות שהגובה של זה
תרשים הוא של n יומן הגודל של n או 3,

408
00:18:10,760 --> 00:18:13,860
במיוחד, במילים אחרות,
אני עשיתי שלוש חטיבות כאן.

409
00:18:13,860 --> 00:18:18,800
כמה עבודה שאני עושה באופן אופקי
לאורך תרשים זה כל זמן?

410
00:18:18,800 --> 00:18:21,110
>> ובכן, אני עשיתי את הצעדים של n
לעבוד, כי אם יש לי

411
00:18:21,110 --> 00:18:24,080
יש ארבעה יסודות וארבעה יסודות,
ואני צריך למזג אותם יחד.

412
00:18:24,080 --> 00:18:26,040
אני צריך לעבור
ארבעה אלה ואלה ארבעה,

413
00:18:26,040 --> 00:18:28,123
סופו של דבר לאחד אותם
בחזרה לשמונה אלמנטים.

414
00:18:28,123 --> 00:18:32,182
אם לעומת יש לי שמונה אצבעות
כאן, שאני לא, ושמונה

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry-- אם יש לי
יש ארבע אצבעות לכאן,

416
00:18:34,390 --> 00:18:37,380
שאני עושה, ארבע אצבעות
כאן, שאני עושה,

417
00:18:37,380 --> 00:18:40,590
אז זה אותו
דוגמא כמו קודם, אם אני עושה

418
00:18:40,590 --> 00:18:44,010
יש שמונה אצבעות אם כי ב
סך הכל, שאני יכול, סוג של, לעשות.

419
00:18:44,010 --> 00:18:47,950
אני יכול לעשות בדיוק כאן,
אז אני בהחלט יכול

420
00:18:47,950 --> 00:18:50,370
למזג את כל הרשימות האלה
גודל 1 יחד.

421
00:18:50,370 --> 00:18:54,050
אבל אני בהחלט צריך להסתכל
בכל אלמנט בדיוק פעם אחת.

422
00:18:54,050 --> 00:18:59,640
אז הגובה של תהליך זה הוא n יומן,
רוחבו של תהליך זה, אם אפשר לומר כך,

423
00:18:59,640 --> 00:19:02,490
הוא n, אז מה אנחנו נראים
יש, סופו של דבר, הוא

424
00:19:02,490 --> 00:19:06,470
זמן ריצה של גודל n פעמים להיכנס n.

425
00:19:06,470 --> 00:19:08,977
>> במילים אחרות, אנחנו מחולקים
הרשימה, יומן n פעמים,

426
00:19:08,977 --> 00:19:11,810
אבל בכל פעם שעשינו את זה, הייתה לנו
לגעת בכל אחד מהמרכיבים

427
00:19:11,810 --> 00:19:13,560
כדי למזג אותם
כולם ביחד, ש

428
00:19:13,560 --> 00:19:18,120
היה N צעד, כך שיש לנו n פעמים להיכנס n,
או כמדען מחשב הייתי אומר,

429
00:19:18,120 --> 00:19:20,380
אסימפטוטית, ש
יהיה המילה הגדולה

430
00:19:20,380 --> 00:19:22,810
כדי לתאר את העליון
מחויב בזמן ריצה,

431
00:19:22,810 --> 00:19:28,010
אנחנו פועלים בo גדולה
של יומן n זמן, אם אפשר לומר כך.

432
00:19:28,010 --> 00:19:31,510
>> עכשיו זה משמעותי, כי
זוכר מה היו הפעמים הריצה

433
00:19:31,510 --> 00:19:34,120
עם מיון בועות, ובחירה
סוג, ומיון הכנסה,

434
00:19:34,120 --> 00:19:38,200
ואפילו כמה אחרים שקיימות,
n בריבוע היה בו היינו ב.

435
00:19:38,200 --> 00:19:39,990
ואתה יכול, סוג של, רואה כאן זו.

436
00:19:39,990 --> 00:19:45,720
אם n בריבוע הוא כמובן n פעמים
n, אבל כאן יש לנו n פעמים להיכנס n,

437
00:19:45,720 --> 00:19:48,770
ואנחנו כבר יודעים משבוע
אפס, כי n היומן, הלוגריתמים,

438
00:19:48,770 --> 00:19:50,550
הוא טוב יותר מאשר ליניארי משהו.

439
00:19:50,550 --> 00:19:52,930
אחרי הכל, זוכר את התמונה
עם אדום והצהוב

440
00:19:52,930 --> 00:19:56,500
והקווים הירוקים שציירנו,
קו ירוק לוגריתמים היה נמוך בהרבה.

441
00:19:56,500 --> 00:20:00,920
ולכן, הרבה יותר טוב ויותר מהר
מהשורות הצהובות ואדומות ישר,

442
00:20:00,920 --> 00:20:05,900
n פעמים להיכנס N הוא, אכן, טוב יותר
מפי n n, או n בריבוע.

443
00:20:05,900 --> 00:20:09,110
>> אז אנחנו נראים לי
זיהה מיזוג אלגוריתם

444
00:20:09,110 --> 00:20:11,870
סוג זה פועל בהרבה
זמן מהיר יותר, ואכן,

445
00:20:11,870 --> 00:20:16,560
בגלל זה, מוקדם יותר השבוע, כש
ראינו תחרות שבין הבועה

446
00:20:16,560 --> 00:20:20,750
סוג, מיון בחירה, ולמזג
סוג, מיון מיזוג באמת, באמת זכה.

447
00:20:20,750 --> 00:20:23,660
ואכן, אפילו לא לחכות
למיון בועות ומיון בחירה

448
00:20:23,660 --> 00:20:24,790
לסיים.

449
00:20:24,790 --> 00:20:27,410
>> עכשיו בואו ניקח את מעבר אחד אחר
בשלב זה, ממעט יותר

450
00:20:27,410 --> 00:20:31,030
נקודת מבט רשמי, רק ב
מקרה, זה מהדהד טוב יותר

451
00:20:31,030 --> 00:20:33,380
מזה דיון ברמה גבוה יותר.

452
00:20:33,380 --> 00:20:34,880
אז הנה האלגוריתם שוב.

453
00:20:34,880 --> 00:20:36,770
בואו לשאול את עצמנו,
מה זמן הריצה

454
00:20:36,770 --> 00:20:39,287
הוא זאת אלגוריתמי צעדים שונים?

455
00:20:39,287 --> 00:20:41,620
בואו נחלק אותה לראשון
מקרה והמקרה השני.

456
00:20:41,620 --> 00:20:46,280
IF והאחר במקרה אם,
אם n הוא פחות מ -2, רק לחזור.

457
00:20:46,280 --> 00:20:47,580
מרגיש כמו זמן קבוע.

458
00:20:47,580 --> 00:20:50,970
זה, סוג של, כמו שני שלבים,
אם n הוא פחות מ -2, ואז לחזור.

459
00:20:50,970 --> 00:20:54,580
אבל כפי שאמרנו ביום שני,
זמן קבוע, או גדול o של 1,

460
00:20:54,580 --> 00:20:57,130
יכול להיות שני צעדים, שלוש
צעדים, אפילו 1,000 צעדים.

461
00:20:57,130 --> 00:20:59,870
מה שחשוב הוא שזה
מספר קבוע של צעדים.

462
00:20:59,870 --> 00:21:03,240
אז הצהוב מודגש פסאודו קוד
כאן פועל ב, אנחנו קוראים לזה,

463
00:21:03,240 --> 00:21:04,490
זמן קבוע.

464
00:21:04,490 --> 00:21:06,780
אז באופן רשמי יותר, ו
אנחנו הולכים צריכה-- זה

465
00:21:06,780 --> 00:21:09,910
תהיה המידה שבה אנחנו
למסד זכות זו now-- T של n,

466
00:21:09,910 --> 00:21:15,030
זמן הריצה של בעיה
שלוקח ומשהו n כקלט,

467
00:21:15,030 --> 00:21:19,150
שווה גדול o של אחד,
אם n הוא פחות מ -2.

468
00:21:19,150 --> 00:21:20,640
אז זה מותנה שב.

469
00:21:20,640 --> 00:21:24,150
אז כדי להיות ברור, אם n הוא פחות מ
2, יש לנו רשימה קצרה מאוד, ולאחר מכן

470
00:21:24,150 --> 00:21:29,151
זמן הריצה, T של n, כאשר n הוא
1 או 0, במקרה הספציפי הזה,

471
00:21:29,151 --> 00:21:30,650
זה פשוט הולך להיות זמן קבוע.

472
00:21:30,650 --> 00:21:32,691
זה הולך לקחת אחד
צעד, שני צעדים, מה ש.

473
00:21:32,691 --> 00:21:33,950
זה מספר קבוע של צעדים.

474
00:21:33,950 --> 00:21:38,840
>> אז החלק העסיסי בוודאי להיות ב
המקרה האחר בפסאודו הקוד.

475
00:21:38,840 --> 00:21:40,220
המקרה האחר.

476
00:21:40,220 --> 00:21:44,870
מיין מחצית השמאלית של אלמנטים, סוג תקין
מחצית מאלמנטים, למזג חצאים ממוינים.

477
00:21:44,870 --> 00:21:46,800
כמה זמן כל אחד מהצעדים האלה לוקח?

478
00:21:46,800 --> 00:21:49,780
ובכן, אם הריצה
זמן למיין אלמנטי n

479
00:21:49,780 --> 00:21:53,010
הוא, בואו נקראים לזה מאוד
הגנרי, T של n,

480
00:21:53,010 --> 00:21:55,500
אז מיון השמאל
מחצית מהאלמנטים

481
00:21:55,500 --> 00:21:59,720
הוא, סוג של, כמו לומר,
T של n מחולק 2,

482
00:21:59,720 --> 00:22:03,000
ובאופן דומה מיון המחצית תקין
אלמנטים הוא, סוג של, כמו לומר,

483
00:22:03,000 --> 00:22:06,974
T של n מחולק 2, ולאחר מכן
מיזוג החצאים מסודרים.

484
00:22:06,974 --> 00:22:08,890
ובכן, אם יש לי כמה
מספר האלמנטים כאן,

485
00:22:08,890 --> 00:22:11,230
כמו ארבעה, וחלק מספר
אלמנטים כאן, כמו ארבעה,

486
00:22:11,230 --> 00:22:14,650
ואני צריך למזג כל אחד מארבעה אלה
ב, וכל אחד מאלה ארבעה ב, אחד

487
00:22:14,650 --> 00:22:17,160
בזה אחר זה, כך ש
סופו של דבר יש לי שמונה אלמנטים.

488
00:22:17,160 --> 00:22:20,230
זה מרגיש כמו שזה גדול o צעדי n?

489
00:22:20,230 --> 00:22:23,500
אם יש לי n אצבעות וכל אחד מ
יש להם ימוזגו לתוך המקום,

490
00:22:23,500 --> 00:22:25,270
זה כמו צעדי n אחר.

491
00:22:25,270 --> 00:22:27,360
>> אז אכן פי נוסחה,
אנחנו יכולים לבטא את זה,

492
00:22:27,360 --> 00:22:29,960
אם כי קצת מבט מפחיד בהתחלה
מבט, אבל זה משהו

493
00:22:29,960 --> 00:22:31,600
הלוכד בדיוק היגיון ש.

494
00:22:31,600 --> 00:22:35,710
זמן הריצה, T של n, אם n
גדול או שווה ל 2.

495
00:22:35,710 --> 00:22:42,500
במקרה זה, המקרה האחר, הוא T של n
חלקי 2, בתוספת של T n מחולק 2,

496
00:22:42,500 --> 00:22:45,320
יתרון גדול של o n, כמה
מספר יניארי של צעדים,

497
00:22:45,320 --> 00:22:51,630
אולי בדיוק n, אולי 2 פעמים
n, אבל זה בערך, סדר n.

498
00:22:51,630 --> 00:22:54,060
אז גם את זה, הוא איך אנחנו יכולים
להביע פי נוסחה זו.

499
00:22:54,060 --> 00:22:56,809
עכשיו אתה לא יודע את זה, אלא אם כן
שהקלטת אותו בראש שלך,

500
00:22:56,809 --> 00:22:58,710
או לחפש את זה ב
אחורי של ספר לימוד, ש

501
00:22:58,710 --> 00:23:00,501
אולי יש לי קטן
רמות גיליון בסוף,

502
00:23:00,501 --> 00:23:03,940
אבל זה, אכן, הולך
לתת גדול o של n n יומננו,

503
00:23:03,940 --> 00:23:06,620
בגלל ההישנות ש
אתם רואים כאן על המסך,

504
00:23:06,620 --> 00:23:09,550
אם אתה באמת עשית את זה, עם
מספר אינסופי של דוגמאות,

505
00:23:09,550 --> 00:23:13,000
או שאתה עשית את זה פי נוסחה, שהיית
רואה שזה, כי נוסחה זו

506
00:23:13,000 --> 00:23:17,100
עצמו הוא רקורסיבית, עם לא של
n על משהו בצד הימין,

507
00:23:17,100 --> 00:23:21,680
ולא של N מעל בצד השמאל, זה יכול
למעשה לבוא לידי ביטוי, בסופו,

508
00:23:21,680 --> 00:23:24,339
דרכים גדולות כמו של n n יומן.

509
00:23:24,339 --> 00:23:26,130
אם לא השתכנע, זה
בסדר לעת עתה, רק

510
00:23:26,130 --> 00:23:28,960
לקחת על אמונה, שזה, אכן,
מה שמובילה לחזרה,

511
00:23:28,960 --> 00:23:31,780
אבל זה רק קצת יותר מ
גישה מתמטית למחפשים

512
00:23:31,780 --> 00:23:36,520
בזמן הריצה מסוג המיזוג
המבוסס על פסאודו הקוד שלה לבד.

513
00:23:36,520 --> 00:23:39,030
>> עכשיו בואו ניקח קצת
מנוחה קצרה מכל זה,

514
00:23:39,030 --> 00:23:41,710
ותסתכל ב
סנטור לשעבר מסוים, ש

515
00:23:41,710 --> 00:23:44,260
אולי נראה קצת מוכר,
שישב עם אריק של גוגל

516
00:23:44,260 --> 00:23:48,410
שמידט, לפני כמה זמן, לראיון
על במה, מול כל חבורה

517
00:23:48,410 --> 00:23:53,710
אנשים, מדבר סופו של דבר על
נושא, זה די מוכר עכשיו.

518
00:23:53,710 --> 00:23:54,575
בואו נסתכל.

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> אריק שמידט: עכשיו סנטור,
אתה כאן בגוגל,

521
00:24:03,890 --> 00:24:09,490
ואני אוהב לחשוב על
נשיאות כראיון עבודה.

522
00:24:09,490 --> 00:24:11,712
עכשיו זה קשה להשיג עבודה כנשיא.

523
00:24:11,712 --> 00:24:12,670
נשיא אובמה: ימין.

524
00:24:12,670 --> 00:24:13,940
אריק שמידט: ואתה
הולך לעשות [לא ברור] עכשיו.

525
00:24:13,940 --> 00:24:15,523
קשה גם למצוא עבודה בגוגל.

526
00:24:15,523 --> 00:24:17,700
נשיא אובמה: ימין.

527
00:24:17,700 --> 00:24:21,330
>> אריק שמידט: יש לנו שאלות,
ואנו שואלים שאלות המועמדים שלנו,

528
00:24:21,330 --> 00:24:24,310
ואת זה הוא מלארי שווימר.

529
00:24:24,310 --> 00:24:25,890
>> הנשיא אובמה: על אישור.

530
00:24:25,890 --> 00:24:27,005
>> אריק שמידט: מה?

531
00:24:27,005 --> 00:24:28,130
אתם חושבים שאני צוחק?

532
00:24:28,130 --> 00:24:30,590
זה ממש כאן.

533
00:24:30,590 --> 00:24:33,490
מהי הדרך היעילה ביותר ל
למיין את מספרים שלמים מיליון 32 ביט?

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> הנשיא אובמה: "תראה

536
00:24:38,979 --> 00:24:41,020
אריק שמידט: לפעמים,
אולי אני מצטער, maybe--

537
00:24:41,020 --> 00:24:42,750
הנשיא אובמה: לא, לא,
לא, לא, לא, אני חושב--

538
00:24:42,750 --> 00:24:43,240
אריק שמידט: זה לא it--

539
00:24:43,240 --> 00:24:45,430
נשיא אובמה: אני
חושב, אני חושב שהבועה

540
00:24:45,430 --> 00:24:46,875
סוג יהיה בדרך הלא נכונה ללכת.

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
בוא: אריק שמידט.

543
00:24:50,535 --> 00:24:52,200
מי אמר לו את זה?

544
00:24:52,200 --> 00:24:54,020
אוקיי.

545
00:24:54,020 --> 00:24:55,590
אני לא מדעי מחשב on--

546
00:24:55,590 --> 00:24:58,986
>> הנשיא אובמה: יש לנו
יש לנו מרגלים שביש.

547
00:24:58,986 --> 00:24:59,860
פרופסור: בסדר.

548
00:24:59,860 --> 00:25:03,370
בואו נשאיר מאחורינו עכשיו
עולם תיאורטי של אלגוריתמים

549
00:25:03,370 --> 00:25:06,520
בניתוח אסימפטוטי
שלו, ולחזור לכמה נושאים

550
00:25:06,520 --> 00:25:09,940
משבוע אפס ואחד, וההתחלה
כדי להסיר כמה גלגלים עזר,

551
00:25:09,940 --> 00:25:10,450
אם אתה.

552
00:25:10,450 --> 00:25:13,241
כך שאתה באמת מבין
סופו של דבר מהיסוד, מה

553
00:25:13,241 --> 00:25:16,805
קורה מתחת למכסת המנוע, כאשר אתה
לכתוב, לקמפל, ולבצע תוכניות.

554
00:25:16,805 --> 00:25:19,680
נזכיר בפרט, שזה היה
תכנית C הראשונה הסתכלנו,

555
00:25:19,680 --> 00:25:22,840
תכנית הקנונית, פשוט
של מיני, באופן יחסי,

556
00:25:22,840 --> 00:25:24,620
בי, הוא מדפיס, שלום עולם.

557
00:25:24,620 --> 00:25:27,610
ואזכיר כי אמרתי, התהליך
קוד המקור שעובר

558
00:25:27,610 --> 00:25:28,430
זה בדיוק זה.

559
00:25:28,430 --> 00:25:31,180
אתה לוקח את קוד המקור שלך, לעבור
זה דרך מהדר, כמו קלאנג,

560
00:25:31,180 --> 00:25:34,650
ואת מגיע קוד אובייקט, ש
עשוי להיראות כך, אפסים ואחדים

561
00:25:34,650 --> 00:25:37,880
כי המעבד של המחשב, מרכזי
יחידת עיבוד או מוח,

562
00:25:37,880 --> 00:25:39,760
סופו של דבר מבין.

563
00:25:39,760 --> 00:25:42,460
>> מתברר שזה
קצת פשטני,

564
00:25:42,460 --> 00:25:44,480
שאנחנו עכשיו ב
עמדה להפריד

565
00:25:44,480 --> 00:25:46,720
כדי להבין מה באמת היה
קורה מתחת למכסת המנוע

566
00:25:46,720 --> 00:25:48,600
בכל פעם שאתה מפעיל
צלצול, או באופן כללי יותר,

567
00:25:48,600 --> 00:25:53,040
בכל פעם שאתה עושה תכנית,
באמצעות הפוך וCF 50 IDE.

568
00:25:53,040 --> 00:25:56,760
בפרט, דברים כאלה
זה נוצר ראשון,

569
00:25:56,760 --> 00:25:58,684
כאשר אתה מהדר את התכנית הראשונה שלך.

570
00:25:58,684 --> 00:26:00,600
במילים אחרות, כשאתה
לקחת את קוד המקור שלך

571
00:26:00,600 --> 00:26:04,390
ולעבד אותו, מה ראשון
שישודר על ידי קלאנג

572
00:26:04,390 --> 00:26:06,370
הוא משהו שנקרא קוד הרכבה.

573
00:26:06,370 --> 00:26:08,990
ולמעשה, זה נראה בדיוק כמו זה.

574
00:26:08,990 --> 00:26:11,170
>> רצתי הפקודה ב
שורת הפקודה קודם לכן.

575
00:26:11,170 --> 00:26:16,260
hello.c של הון מקף צלצול,
וזה יצר קובץ

576
00:26:16,260 --> 00:26:19,490
לhello.s נקרא,
בתוכה היו בדיוק

577
00:26:19,490 --> 00:26:22,290
תכנים אלה, וקצת יותר
לעיל וקצת יותר למטה,

578
00:26:22,290 --> 00:26:25,080
אבל אני כבר לשים עסיסי
מידע כאן על המסך.

579
00:26:25,080 --> 00:26:29,190
ואם אתה מסתכל מקרוב, תראה
לפחות כמה מילות מפתח מוכרות.

580
00:26:29,190 --> 00:26:31,330
יש לנו עיקרי בחלק העליון.

581
00:26:31,330 --> 00:26:35,140
יש לנו printf למטה באמצע.

582
00:26:35,140 --> 00:26:38,670
ויש לנו גם שלום העולם
n הלוכסן האחורי בציטוטים למטה.

583
00:26:38,670 --> 00:26:42,450
>> וכל מה שכאן אחר
הוא הוראות רמה נמוכות מאוד

584
00:26:42,450 --> 00:26:45,500
כי המעבד של המחשב מבין.

585
00:26:45,500 --> 00:26:50,090
הוראות מעבד הנעות זיכרון
מסביב, שמייתרי העומס מהזיכרון,

586
00:26:50,090 --> 00:26:52,750
וסופו של דבר, הדפסה
דברים על המסך.

587
00:26:52,750 --> 00:26:56,780
עכשיו מה קורה אם כי לאחר
קוד הרכבה זה נוצר?

588
00:26:56,780 --> 00:26:59,964
סופו של דבר, אתה עושה, אכן,
עדיין ליצור קוד אובייקט.

589
00:26:59,964 --> 00:27:02,630
אבל הצעדים שיש באמת
כבר קורה מתחת למכסת המנוע

590
00:27:02,630 --> 00:27:04,180
נראה קצת יותר כמו זה.

591
00:27:04,180 --> 00:27:08,390
קוד המקור הופך קוד הרכבה,
אשר לאחר מכן הופך קוד אובייקט,

592
00:27:08,390 --> 00:27:11,930
והמילים האופרטיביות כאן הן ש,
כאשר אתה לקמפל קוד המקור שלך,

593
00:27:11,930 --> 00:27:16,300
את מגיע קוד הרכבה, ולאחר מכן
כאשר אתה להרכיב קוד ההרכבה שלך,

594
00:27:16,300 --> 00:27:17,800
את מגיע קוד אובייקט.

595
00:27:17,800 --> 00:27:20,360
>> עכשיו קלאנג הוא סופר מתוחכם,
כמו הרבה מהדרים,

596
00:27:20,360 --> 00:27:23,151
וזה עושה את כל פעולות הבאות
יחד, וזה לא בהכרח

597
00:27:23,151 --> 00:27:25,360
תפוקה כל ביניים
קבצים שאתה אפילו יכול לראות.

598
00:27:25,360 --> 00:27:28,400
זה פשוט הידור דברים,
שהוא המונח הכללי ש

599
00:27:28,400 --> 00:27:30,000
מתאר כל התהליך הזה.

600
00:27:30,000 --> 00:27:32,000
אבל אם אתה באמת רוצה
להיות מסוימים, יש

601
00:27:32,000 --> 00:27:34,330
הרבה יותר על הולכים לשם גם כן.

602
00:27:34,330 --> 00:27:38,860
>> אבל בואו גם לשקול כעת כי גם
כי תכנית סופר פשוטה, hello.c,

603
00:27:38,860 --> 00:27:40,540
נקרא פונקציה.

604
00:27:40,540 --> 00:27:41,870
זה נקרא printf.

605
00:27:41,870 --> 00:27:46,900
אבל אני לא כתבתי printf, אכן,
שמגיע עם ג, כביכול.

606
00:27:46,900 --> 00:27:51,139
זה זוכר פונקציה זה
הכריז בio.h הסטנדרטי, ש

607
00:27:51,139 --> 00:27:53,180
הוא קובץ כותרת, ש
הוא למעשה נושא אנחנו

608
00:27:53,180 --> 00:27:55,780
לצלול לתוך יותר לעומק לפני זמן רב.

609
00:27:55,780 --> 00:27:58,000
אבל קובץ כותרת הוא
מלווה בדרך כלל

610
00:27:58,000 --> 00:28:02,920
על ידי קובץ קוד, קובץ קוד מקור, כך
בדומה קיים io.h. הסטנדרטי

611
00:28:02,920 --> 00:28:05,930
>> לפני זמן מה, מישהו,
או של מישהו, גם כתב

612
00:28:05,930 --> 00:28:11,040
קובץ בשם io.c הסטנדרטי, ב
שההגדרות בפועל,

613
00:28:11,040 --> 00:28:15,220
או מימושים של printf,
וצרורות של פונקציות אחרות,

614
00:28:15,220 --> 00:28:16,870
נכתבים למעשה.

615
00:28:16,870 --> 00:28:22,140
אז בהתחשב בכך ש, אם ניקח בחשבון שיש
כאן בצד השמאל, hello.c, שכאשר

616
00:28:22,140 --> 00:28:26,250
הידור, נותן לנו hello.s, גם אם
צלצול לא מפריע חיסכון במקום

617
00:28:26,250 --> 00:28:31,360
אנחנו יכולים לראות את זה, ושקוד ההרכבה
מקבל התאסף לתוך hello.o, ש

618
00:28:31,360 --> 00:28:34,630
הוא, אכן, בשם ברירת המחדל
נתתי כל פעם שאתה לקמפל מקור

619
00:28:34,630 --> 00:28:39,350
קוד לקוד אובייקט, אך אינם
ממש מוכן לבצע את זה עדיין,

620
00:28:39,350 --> 00:28:41,460
כי צעד נוסף
צריך לקרות, ויש לו

621
00:28:41,460 --> 00:28:44,440
קורה לכמה האחרון
שבועות, אולי ללא ידיעתך.

622
00:28:44,440 --> 00:28:47,290
>> באופן ספציפי למקום
בCS50 IDE, וזה,

623
00:28:47,290 --> 00:28:49,870
מדי, יהיה קצת
פשטני לרגע,

624
00:28:49,870 --> 00:28:54,670
יש, או היה על זמן,
קובץ בשם io.c הסטנדרטי,

625
00:28:54,670 --> 00:28:58,440
שמישהו הידור ל
io.s סטנדרטי או שווה הערך,

626
00:28:58,440 --> 00:29:02,010
שמישהו אז התאסף
לio.o הסטנדרטי,

627
00:29:02,010 --> 00:29:04,600
או שמתברר ל
קובץ שונה מעט

628
00:29:04,600 --> 00:29:07,220
פורמט שיכול להיות שונה
סיומת קובץ לגמרי,

629
00:29:07,220 --> 00:29:11,720
אבל בתאוריה ומושגית, בדיוק
צעדים אלה היו צריכים לקרות בצורה כלשהי.

630
00:29:11,720 --> 00:29:14,060
כלומר, שעכשיו
כאשר אני כותב תכנית,

631
00:29:14,060 --> 00:29:17,870
hello.c, שרק אומר, שלום עולם,
ואני משתמש בקוד של מישהו אחר

632
00:29:17,870 --> 00:29:22,480
כמו printf, שהיה פעם על
זמן, בקובץ בשם io.c הסטנדרטי,

633
00:29:22,480 --> 00:29:26,390
אז איכשהו אני צריך לקחת אותי
קוד אובייקט, אפסים שלי ואלה,

634
00:29:26,390 --> 00:29:29,260
והאובייקט של האדם ש
קוד, או אפסים ואחדים,

635
00:29:29,260 --> 00:29:34,970
ואיכשהו לקשר אותם יחד ל
קובץ סופי אחד, בשם שלום, ש

636
00:29:34,970 --> 00:29:38,070
יש את כל האפסים ו
אלה מתפקידו העיקרי שלי,

637
00:29:38,070 --> 00:29:40,830
וכל האפסים
ואלה לprintf.

638
00:29:40,830 --> 00:29:44,900
>> ואכן, שהתהליך שעבר הוא
בשם, המקשר את קוד האובייקט שלך.

639
00:29:44,900 --> 00:29:47,490
הפלט של אשר
הוא קובץ הפעלה.

640
00:29:47,490 --> 00:29:49,780
אז בהגינות, ב
סופו של היום, שום דבר

641
00:29:49,780 --> 00:29:52,660
השתנה מאז שבוע אחד, כאשר אנו
התחיל קומפילציה של תוכניות.

642
00:29:52,660 --> 00:29:55,200
ואכן, כל זה היה
קורה מתחת למכסת המנוע,

643
00:29:55,200 --> 00:29:57,241
אבל עכשיו אנחנו בעמדה
שבו אנחנו יכולים למעשה

644
00:29:57,241 --> 00:29:58,794
להפריד אלה צעדים שונים.

645
00:29:58,794 --> 00:30:00,710
ואכן, בסופו של הדבר
שלו של היום, אנחנו עדיין

646
00:30:00,710 --> 00:30:04,480
נשאר עם אפסים ואחדים, ש
הוא למעשה segue גדול עכשיו

647
00:30:04,480 --> 00:30:08,620
ליכולת נוספת של C, ש
לא היו לנו למנף סביר ביותר

648
00:30:08,620 --> 00:30:11,250
עד היום, ידוע כמפעילים סיביים האופרטור.

649
00:30:11,250 --> 00:30:15,220
במילים אחרות, עד כה, בכל עת שיש לנו
עסק בנתונים ב- C או משתנה ב- C,

650
00:30:15,220 --> 00:30:17,660
היו לנו דברים כמו
תווים וצופו תוספות

651
00:30:17,660 --> 00:30:21,990
ומתגעגע וזוגות וכדומה, אבל
כל אלה הם לפחות שמונה סיביות.

652
00:30:21,990 --> 00:30:25,550
אנחנו אף פעם לא הצלחנו עדיין ל
לתפעל ביטים בודדים,

653
00:30:25,550 --> 00:30:28,970
למרות שקצת בודד, אנחנו
יודע, יכול לייצג 0 ו1.

654
00:30:28,970 --> 00:30:32,640
כעת מתברר כי ב- C, אתה
יכול לקבל גישה לרסיסים בודדים,

655
00:30:32,640 --> 00:30:35,530
אם אתה יודע את התחביר,
עם שכדי להגיע אליהם.

656
00:30:35,530 --> 00:30:38,010
>> אז בואו נסתכל
במפעילים סיביים האופרטור.

657
00:30:38,010 --> 00:30:41,700
אז בתמונה הנה כמה סימנים ש
אנחנו כבר, סוג של, סוג של, ראינו בעבר.

658
00:30:41,700 --> 00:30:45,580
אני רואה אמפרסנד, אנכי
בר, וכמה אחרים, כמו גם,

659
00:30:45,580 --> 00:30:49,430
וזוכר שאמפרסנד האמפרסנד
הוא משהו שראינו לפני.

660
00:30:49,430 --> 00:30:54,060
המפעיל ההגיוני, ומקום שיש לך
שניהם יחד, או לוגיים או

661
00:30:54,060 --> 00:30:56,300
מפעיל, שבו אתה
יש שני קווים אנכיים.

662
00:30:56,300 --> 00:31:00,550
מפעילים סיביים האופרטור, אשר נשלחה
רואה פועלים על ביטים בנפרד,

663
00:31:00,550 --> 00:31:03,810
פשוט להשתמש אמפרסנד יחיד,
קו אנכי יחיד, סמל תו

664
00:31:03,810 --> 00:31:06,620
השלב הבא, הקטן
טילדה, ולאחר מכן עזב

665
00:31:06,620 --> 00:31:08,990
תושבת עזבה הסוגר, או
ימין תושבת מסגרת ימנית.

666
00:31:08,990 --> 00:31:10,770
בכל אחד מאלה יש משמעויות שונות.

667
00:31:10,770 --> 00:31:11,950
>> למעשה, בואו נסתכל.

668
00:31:11,950 --> 00:31:16,560
בואו נלך בית הספר ישן היום, ושימוש
מסך מגע מפעם,

669
00:31:16,560 --> 00:31:18,002
ידוע כלוח לבן.

670
00:31:18,002 --> 00:31:19,710
והלוח הלבן הזה
הוא הולך כדי לאפשר לנו

671
00:31:19,710 --> 00:31:27,360
להביע כמה סימנים פשוטים למדי,
או לייתר דיוק כמה נוסחות פשוטות למדי,

672
00:31:27,360 --> 00:31:29,560
כי אז אנו יכולים סופו של דבר
מינוף, כדי

673
00:31:29,560 --> 00:31:33,230
כדי לגשת לאדם
ביטים בתוך תכנית C.

674
00:31:33,230 --> 00:31:34,480
במילים אחרות, בואו נעשיתי את זה.

675
00:31:34,480 --> 00:31:37,080
השיחה הראשונה בואו ל
רגע על אמפרסנד,

676
00:31:37,080 --> 00:31:39,560
אשר הוא הסיבי האופרטור ומפעיל.

677
00:31:39,560 --> 00:31:42,130
במילים אחרות, זה הוא
מפעיל המאפשר

678
00:31:42,130 --> 00:31:45,930
לי יש שמאלי משתנים
בדרך כלל, ויד ימין משתנה,

679
00:31:45,930 --> 00:31:50,640
או ערך בודד, שאם ו
אותם יחד, נותן לי תוצאה סופית.

680
00:31:50,640 --> 00:31:51,560
אז מה אני אומר?

681
00:31:51,560 --> 00:31:54,840
אם בתכנית, יש לך משתנה
שחנויות אחד מערכים אלה,

682
00:31:54,840 --> 00:31:58,000
או בואו נשמור את זה פשוט, ורק
לכתוב את אפסים ואחדים בנפרד,

683
00:31:58,000 --> 00:32:00,940
הנה איך מפעיל האמפרסנד עובד.

684
00:32:00,940 --> 00:32:06,400
0 אמפרסנד 0 הולך שווה 0.

685
00:32:06,400 --> 00:32:07,210
עכשיו למה זה?

686
00:32:07,210 --> 00:32:09,291
>> זה דומה מאוד ל
ביטויים בוליאנית,

687
00:32:09,291 --> 00:32:10,540
שאנחנו כבר דנו עד כה.

688
00:32:10,540 --> 00:32:15,800
אם אתה חושב שאחרי הכל, 0 הוא
שקר, 0 הוא שקר, שקר ושקר

689
00:32:15,800 --> 00:32:18,720
הוא, כפי שאמרנו
מבחינה לוגית, גם שקר.

690
00:32:18,720 --> 00:32:20,270
אז אנחנו מקבלים 0 גם כאן.

691
00:32:20,270 --> 00:32:24,390
אם אתה לוקח 0 אמפרסנד
1, גם כי, מדי,

692
00:32:24,390 --> 00:32:29,890
הולך להיות 0, כי לזה
שמאלי ביטוי להיות אמיתי או 1,

693
00:32:29,890 --> 00:32:32,360
זה היה צריך להיות נכון ואמיתי.

694
00:32:32,360 --> 00:32:36,320
אבל כאן יש לנו כוזב
ואמיתי, או 0 ו -1.

695
00:32:36,320 --> 00:32:42,000
עכשיו שוב, אם יש לנו אמפרסנד 1
0, שגם הוא הולך להיות 0,

696
00:32:42,000 --> 00:32:47,240
ואם יש לנו אמפרסנד 1 1,
לבסוף יש לנו קצת 1.

697
00:32:47,240 --> 00:32:50,340
אז במילים אחרות, אנחנו לא עושים
משהו מעניין עם מפעיל זה

698
00:32:50,340 --> 00:32:51,850
עדיין, מפעיל אמפרסנד זה.

699
00:32:51,850 --> 00:32:53,780
זה סיבי האופרטור ומפעיל.

700
00:32:53,780 --> 00:32:57,290
אבל אלה הם המרכיבים
באמצעותו אנו יכולים לעשות

701
00:32:57,290 --> 00:32:59,240
דברים מעניינים, כפי שאנו רואים בקרוב.

702
00:32:59,240 --> 00:33:02,790
>> עכשיו בואו נסתכל על רק אחת
בר אנכי כאן בצד הימין.

703
00:33:02,790 --> 00:33:06,710
אם יש לי 0 קצת ואני
או שזה עם, סיבי האופרטור

704
00:33:06,710 --> 00:33:11,030
או מפעיל, עוד 0 קצת,
זה הולך לתת לי 0.

705
00:33:11,030 --> 00:33:17,540
אם אני לוקח 0 קצת ואו שזה עם
קצת 1, אז אני הולך לקבל 1.

706
00:33:17,540 --> 00:33:19,830
ולמעשה, רק ל
בהירות, תן לי לחזור,

707
00:33:19,830 --> 00:33:23,380
כך שהקווים האנכיים שלי
הם לא טועים ל1 של.

708
00:33:23,380 --> 00:33:26,560
תן לי לכתוב מחדש את כל
1 קצת יותר

709
00:33:26,560 --> 00:33:32,700
ברור, כדי שלמחרת לראות, אם אני
יש 1 או 0, שהולך להיות 1,

710
00:33:32,700 --> 00:33:39,060
ואם יש לי 1 או 1 ש,
מדי, הולך להיות 1.

711
00:33:39,060 --> 00:33:42,900
אז אתה יכול לראות באופן הגיוני שOR
מפעיל מתנהג בצורה שונה מאוד.

712
00:33:42,900 --> 00:33:48,070
זה נותן לי 0 או 0 נותן לי 0, אבל
כל שילוב אחר נותן לי 1.

713
00:33:48,070 --> 00:33:52,480
כל עוד יש לי אחד 1 ב
נוסחה, התוצאה הולכת להיות 1.

714
00:33:52,480 --> 00:33:55,580
>> בניגוד ול
מפעיל, האמפרסנד,

715
00:33:55,580 --> 00:34:00,940
רק אם יש לי שני של 1 ב
משוואה, אני ממש מקבל את 1.

716
00:34:00,940 --> 00:34:02,850
עכשיו יש כמה אחר
מפעילים, כמו גם.

717
00:34:02,850 --> 00:34:04,810
אחד מהם הוא קצת יותר מעורב.

718
00:34:04,810 --> 00:34:07,980
אז תן לי ללכת קדימה ולמחוק
זה כדי לפנות קצת מקום.

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
ובואו נסתכל
סמל תו, רק לרגע.

721
00:34:16,460 --> 00:34:18,210
זה בדרך כלל
דמות תוכל להקליד

722
00:34:18,210 --> 00:34:21,420
על Shift החזקת המקלדת ו
אז אחד המספרים על גבי ארה"ב

723
00:34:21,420 --> 00:34:22,250
לוח מקשים.

724
00:34:22,250 --> 00:34:26,190
>> אז זה בלעדי
או מפעיל, בלעדי או.

725
00:34:26,190 --> 00:34:27,790
אז אנחנו פשוט ראינו את המפעיל או.

726
00:34:27,790 --> 00:34:29,348
זה בלעדי או מפעיל.

727
00:34:29,348 --> 00:34:30,639
מה בעצם ההבדל?

728
00:34:30,639 --> 00:34:34,570
ובכן בואו רק מסתכל על הנוסחה,
ולהשתמש בזה כמרכיבי סופו של דבר.

729
00:34:34,570 --> 00:34:37,690
0 XOR 0.

730
00:34:37,690 --> 00:34:39,650
אני הולך לומר הוא תמיד 0.

731
00:34:39,650 --> 00:34:41,400
זה ההגדרה של XOR.

732
00:34:41,400 --> 00:34:47,104
0 XOR 1 הולך להיות 1.

733
00:34:47,104 --> 00:34:58,810
XOR 1 0 הולך להיות 1,
וXOR 1 1 הולך להיות?

734
00:34:58,810 --> 00:34:59,890
לא בסדר?

735
00:34:59,890 --> 00:35:00,520
או ימין?

736
00:35:00,520 --> 00:35:01,860
אֲנִי לֹא יוֹדֵעַ.

737
00:35:01,860 --> 00:35:02,810
0.

738
00:35:02,810 --> 00:35:04,700
עכשיו מה קורה כאן?

739
00:35:04,700 --> 00:35:06,630
טוב לחשוב על
שמו של המפעיל.

740
00:35:06,630 --> 00:35:09,980
בלעדי או, באופן ש
שם, סוג של, מרמז,

741
00:35:09,980 --> 00:35:13,940
התשובה היא רק הולכת להיות
1 אם התשומות הן בלעדיות,

742
00:35:13,940 --> 00:35:15,560
שונה באופן בלעדי.

743
00:35:15,560 --> 00:35:18,170
אז הנה הן התשומות
אותו דבר, אז הפלט הוא 0.

744
00:35:18,170 --> 00:35:20,700
כאן התשומות
אותו דבר, אז הפלט הוא 0.

745
00:35:20,700 --> 00:35:25,640
הנה הפלטים שונים, הם
הם בלעדיים, וכן הפלט הוא 1.

746
00:35:25,640 --> 00:35:28,190
אז זה מאוד דומה ל
ו, זה דומה מאוד,

747
00:35:28,190 --> 00:35:32,760
או לייתר דיוק זה דומה מאוד ל
או, אבל רק באופן בלעדי.

748
00:35:32,760 --> 00:35:36,210
אחד זה כבר לא 1,
כי יש לנו שתי 1 של,

749
00:35:36,210 --> 00:35:38,621
ולא באופן בלעדי, רק אחד מהם.

750
00:35:38,621 --> 00:35:39,120
בסדר.

751
00:35:39,120 --> 00:35:40,080
מה לגבי האחרים?

752
00:35:40,080 --> 00:35:44,220
ובכן טילדה, בינתיים, היא
למעשה נחמד ופשוט, תודה לאל.

753
00:35:44,220 --> 00:35:46,410
וזה יונארית
מפעיל, מה שאומר ש

754
00:35:46,410 --> 00:35:50,400
זה מיושם רק קלט אחד,
האופרנד אחד, אם אפשר לומר כך.

755
00:35:50,400 --> 00:35:51,800
לא לשמאל וימין.

756
00:35:51,800 --> 00:35:56,050
במילים אחרות, אם אתה לוקח טילדה של
0, התשובה תהיה הפוכה.

757
00:35:56,050 --> 00:35:59,710
ואם אתה לוקח טילדה של 1,
תשובה תהיה הפוכה.

758
00:35:59,710 --> 00:36:02,570
אז מפעיל טילדה הוא
דרך של שלילה קצת,

759
00:36:02,570 --> 00:36:06,000
או מרפרף קצת מ
0 ל -1, או 1-0.

760
00:36:06,000 --> 00:36:09,820
>> וזה משאיר אותנו בסופו
רק עם שני מפעילים סופיים,

761
00:36:09,820 --> 00:36:13,840
מה שנקרא שינוי שמאלי, ו
מה שנקרא מפעיל משמרת תקין.

762
00:36:13,840 --> 00:36:16,620
בואו נסתכל על איך עבודה אלה.

763
00:36:16,620 --> 00:36:20,780
מפעיל המשמרת עזב, נכתב
עם שני סוגריים זווית כמו ש,

764
00:36:20,780 --> 00:36:22,110
פועל באופן הבא.

765
00:36:22,110 --> 00:36:27,390
אם הקלט שלי, או האופרנד שלי, לשמאל
מפעיל המשמרת הוא די פשוט 1.

766
00:36:27,390 --> 00:36:33,750
ואז אני אומר לי המחשב ל
עזב משמרת ש1, אומר שבעה מקומות,

767
00:36:33,750 --> 00:36:37,150
התוצאה היא כאילו אני
לקחת את זה 1, ולהעביר אותו

768
00:36:37,150 --> 00:36:40,160
שבעה מקומות מעל ל
שמאל, וברירת מחדל,

769
00:36:40,160 --> 00:36:42,270
אנחנו הולכים להניח ש
המרחב לימין

770
00:36:42,270 --> 00:36:44,080
הולך להיות מרופד באפסים.

771
00:36:44,080 --> 00:36:50,316
במילים אחרות, 1 עזב משמרת 7 הולכת
לתת לי כי 1, ואחריו 1, 2, 3,

772
00:36:50,316 --> 00:36:54,060
4, 5, 6, 7 אפסים.

773
00:36:54,060 --> 00:36:57,380
אז בדרך, זה מאפשר לך
לקחת מספר קטן כמו 1,

774
00:36:57,380 --> 00:37:00,740
וברור לעשות את זה הרבה
הרבה, הרבה יותר גדול בדרך זו,

775
00:37:00,740 --> 00:37:06,460
אבל אנחנו למעשה הולכים לראות
גישות חכמות יותר עבורו

776
00:37:06,460 --> 00:37:08,080
במקום, כמו גם,

777
00:37:08,080 --> 00:37:08,720
>> בסדר.

778
00:37:08,720 --> 00:37:10,060
זהו זה לשבוע שלושה.

779
00:37:10,060 --> 00:37:11,400
אנחנו אראה אותך בפעם הבאה.

780
00:37:11,400 --> 00:37:12,770
זה היה CS50.

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [השמעת מוסיקה]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1: הוא היה בחטיף
בר אכילת גלידה שוקולד חמה.

784
00:37:25,766 --> 00:37:28,090
היה לו את זה על כל פניו.

785
00:37:28,090 --> 00:37:30,506
הוא לובש שוקולד שכמו זקן

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2: מה אתה עושה?

787
00:37:31,756 --> 00:37:32,422
SPEAKER 3: המממ?

788
00:37:32,422 --> 00:37:33,500
מה?

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2: האם אתה פשוט לטבול כפול?

790
00:37:36,800 --> 00:37:38,585
אתה כפול טבל את השבב.

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3: תסלח לי.

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2: אתה טבל שבב,
נגס, ואתה טבל שוב.

793
00:37:44,440 --> 00:37:44,940
3 דובר:

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2: אז זה כמו לשים
זכותך כל הפה בטבילה.

795
00:37:48,440 --> 00:37:52,400
בפעם הבאה שאתה לוקח שבב,
רק לטבול אותו פעם אחת, ולסיים אותו.

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3: אתה יודע מה, דן?

797
00:37:53,890 --> 00:37:58,006
אתה טובל את הדרך שאתה רוצה לטבול.

798
00:37:58,006 --> 00:38:01,900
אני טובל את הדרך שאני רוצה לטבול.

799
00:38:01,900 --> 00:38:03,194