1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [סעיף 3 - יותר נוח]

2
00:00:02,570 --> 00:00:05,070
[רוב אודן - אוניברסיטת הרווארד]

3
00:00:05,070 --> 00:00:07,310
>> [זה CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> אז השאלה הראשונה מנוסחת באופן מוזר.

5
00:00:12,700 --> 00:00:17,480
GDB מאפשר לך "באגים" בתכנית, אבל, באופן ספציפי יותר, מה זה ייתן לך לעשות?

6
00:00:17,480 --> 00:00:22,590
אני אענה על השאלה הזו, ואני לא יודע מה בדיוק צפוי,

7
00:00:22,590 --> 00:00:27,910
אז אני מנחש שזה משהו בסגנון שלו מאפשר לך צעד אחר צעד

8
00:00:27,910 --> 00:00:31,540
ללכת דרך התכנית, אינטראקציה עימו, משתנה שינוי, לעשות את כל הדברים האלה -

9
00:00:31,540 --> 00:00:34,270
בעצם לשלוט ביצוע של תכנית לחלוטין

10
00:00:34,270 --> 00:00:38,410
ולבדוק כל חלק נתון של ביצוע התכנית.

11
00:00:38,410 --> 00:00:43,030
אז התכונות האלה תיתנה לך באגים דברים.

12
00:00:43,030 --> 00:00:44,830
אוקיי.

13
00:00:44,830 --> 00:00:50,520
מדוע החיפוש בינארי דורש שמערך יהיה מסודר?

14
00:00:50,520 --> 00:00:53,360
מי רוצה לענות על זה?

15
00:00:56,120 --> 00:01:00,070
[תלמיד] כי זה לא יעבוד אם זה לא מיון. >> כן. [שחוק]

16
00:01:00,070 --> 00:01:04,910
אם זה לא מיון, אי אפשר לפצל אותו לשניים

17
00:01:04,910 --> 00:01:07,850
ולדעת כל מה שמצד שמאל יש פחות והכל בצד הימין

18
00:01:07,850 --> 00:01:10,490
הוא גדול מהערך האמצעי.

19
00:01:10,490 --> 00:01:12,790
כך זה צריך להיות מסודר.

20
00:01:12,790 --> 00:01:14,170
אוקיי.

21
00:01:14,170 --> 00:01:17,570
למה הוא מיון בועות ב O של n בריבוע?

22
00:01:17,570 --> 00:01:23,230
האם מישהו רוצה 1 לתת סקירה מהירה מאוד ברמה גבוהה ממה שמיון בועות הוא?

23
00:01:25,950 --> 00:01:33,020
[תלמיד] אתה בעצם עובר כל רכיב ותקיש את מספר האלמנטים 1.

24
00:01:33,020 --> 00:01:37,150
אם הם יצאו משם להחליף אותם, ואחר כך בודקים כמה האלמנטים הבאים וכך הלאה.

25
00:01:37,150 --> 00:01:40,770
כשאתה מגיע לסוף, אז אתה יודע שהמרכיב הגדול ביותר ממוקם בסוף,

26
00:01:40,770 --> 00:01:42,750
כך שאתה מתעלם מכך כי אחד אז אתה ממשיך בדרכו,

27
00:01:42,750 --> 00:01:48,490
ובכל פעם שיש לך כדי לבדוק פחות אלמנט אחד עד שלא בצע שום שינוי. >> כן.

28
00:01:48,490 --> 00:01:58,470
זה נקרא מיון בועות כי אם להפוך את המערך על צידו כך שזה למעלה ולמטה, אנכי,

29
00:01:58,470 --> 00:02:03,100
אז את הערכים הגדולים ישקעו לקרקעית ואת הערכים הקטנים מבעבעים לראש.

30
00:02:03,100 --> 00:02:05,210
ככה זה קבל את שמה.

31
00:02:05,210 --> 00:02:08,220
וכן, אתה פשוט לעבור.

32
00:02:08,220 --> 00:02:11,190
אתה כל הזמן עובר על המערך, החלפת הערך הגדול יותר

33
00:02:11,190 --> 00:02:14,040
כדי לקבל את הערכים הגדולים ביותר לתחתית.

34
00:02:14,040 --> 00:02:17,500
>> למה זה O של n בריבוע?

35
00:02:18,690 --> 00:02:24,620
ראשית, האם מישהו רוצה לומר למה זה ריבוע O של n?

36
00:02:24,620 --> 00:02:28,760
[תלמיד] כי לכל ריצה זה הולך n פעמים.

37
00:02:28,760 --> 00:02:32,100
אתה יכול להיות בטוח שאתה כבר לקחת את האלמנט הכי הגדול כל הדרך למטה בלבד,

38
00:02:32,100 --> 00:02:35,230
אז אתה צריך לחזור על זה כלאלמנטים רבים. >> כן.

39
00:02:35,230 --> 00:02:41,800
אז קח בחשבון את מה שגדול O אומר ומה אמצעי אומגה גדולים.

40
00:02:41,800 --> 00:02:50,560
הגדול O הוא כמו החסם העליון על כמה איטי זה יכול לרוץ ממש.

41
00:02:50,560 --> 00:02:58,990
אז באומרה של O של n בריבוע, זה לא O של n או אחר זה יהיה מסוגל לרוץ

42
00:02:58,990 --> 00:03:02,640
בזמן ליניארי, אבל זה O של n קוביות

43
00:03:02,640 --> 00:03:06,390
כי זה מתוחם בO של n לקוביות.

44
00:03:06,390 --> 00:03:12,300
אם זה מתוחם בO של n בריבוע, אז זה מתוחם גם על ידי n לקוביות.

45
00:03:12,300 --> 00:03:20,280
אז זה הוא n בריבוע, ובמקרה הגרוע ביותר המוחלט הוא לא יכול לעשות יותר טוב מn בריבוע,

46
00:03:20,280 --> 00:03:22,830
וזו הסיבה שזה O של n בריבוע.

47
00:03:22,830 --> 00:03:31,200
אז לראות מתמטיקה קלה על איך זה יוצא להיות n בריבוע,

48
00:03:31,200 --> 00:03:40,530
אם יש לנו חמישה דברים ברשימה שלנו, בפעם הראשונה כמה החלפות יכולנו פוטנציאלית צריכות לעשות

49
00:03:40,530 --> 00:03:47,170
כדי לקבל את זה? בואו בעצם רק -

50
00:03:47,170 --> 00:03:52,040
כמה החלפות אנחנו הולכים צריכים לעשות בהרצה הראשונה של מיון בועות במערך?

51
00:03:52,040 --> 00:03:53,540
[התלמיד] n - 1. >> כן.

52
00:03:53,540 --> 00:03:58,340
>> אם יש 5 אלמנטים, אנחנו הולכים צריכים לעשות n - 1.

53
00:03:58,340 --> 00:04:01,100
אז בשנייה אחת כמה החלפות אנחנו הולכים צריכים לעשות?

54
00:04:01,100 --> 00:04:03,440
[התלמיד] n - 2. >> כן.

55
00:04:03,440 --> 00:04:11,640
והשלישי הולך להיות n - 3, ולאחר מכן לנוחות אני אכתוב את שני האחרונים

56
00:04:11,640 --> 00:04:15,270
כמו אז אנחנו הולכים צריכים לעשות 2 חילופים והחלפה 1.

57
00:04:15,270 --> 00:04:19,899
אני מניח שהאחרון יכול או לא יכול בעצם צריך לקרות.

58
00:04:19,899 --> 00:04:22,820
האם זה החלפה? אני לא יודע.

59
00:04:22,820 --> 00:04:26,490
אז אלו הם סכומים הכוללים של עסקות חלף או לפחות השוואות אתה צריך לעשות.

60
00:04:26,490 --> 00:04:29,910
גם אם אתה לא מחליף, אתה עדיין צריך להשוות את הערכים.

61
00:04:29,910 --> 00:04:33,910
אז יש n - 1 השוואות בהרצה הראשונה במערך.

62
00:04:33,910 --> 00:04:42,050
אם אתה משנה את סדר הדברים האלה, בואו נעשה אותו שישה דברים כך דברים להיערם יפה,

63
00:04:42,050 --> 00:04:44,790
ואז אני אעשה 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
אז פשוט סדרנו את הסכומים הללו, אנחנו רוצים לראות כמה השוואות שאנחנו עושים

65
00:04:49,910 --> 00:04:52,700
בכל האלגוריתם.

66
00:04:52,700 --> 00:04:56,550
אז אם אנחנו מביאים החבר 'ה האלה כאן למטה,

67
00:04:56,550 --> 00:05:07,470
אז אנחנו עדיין רק סיכום זאת השוואות רבות נמצאים בה.

68
00:05:07,470 --> 00:05:13,280
אם נסכם אלה ונסכם אלה ונסכם אלה אבל,

69
00:05:13,280 --> 00:05:18,130
זה עדיין אותה הבעיה. אנחנו פשוט לסכם את אותן קבוצות מסוימות.

70
00:05:18,130 --> 00:05:22,400
>> אז עכשיו אנחנו מסכמים n 3 של. זה לא רק 3 של n.

71
00:05:22,400 --> 00:05:27,650
זה תמיד הולך להיות n / 2 של n.

72
00:05:27,650 --> 00:05:29,430
אז הנה אנחנו במקרה יש 6.

73
00:05:29,430 --> 00:05:34,830
אם היה לנו 10 דברים, אז אנחנו יכולים לעשות את זה לקיבוץ 5 זוגות שונים של דברים

74
00:05:34,830 --> 00:05:37,180
וסופו של דבר עם n + n + n + n + n.

75
00:05:37,180 --> 00:05:45,840
אז אתה תמיד הולך לקבל n / 2 n של, ואז זה נעשה לרשום אותו לריבוע n / 2.

76
00:05:45,840 --> 00:05:48,890
וכך למרות שזה הפקטור של חצי, וזה קורה לבוא

77
00:05:48,890 --> 00:05:54,190
בגלל העובדה שדרך כל איטרציה על המערך נשווה 1 פחות

78
00:05:54,190 --> 00:05:58,040
אז ככה אנחנו מקבלים יותר מ 2, אבל זה עדיין הוא n בריבוע.

79
00:05:58,040 --> 00:06:01,650
לא אכפת לנו על הגורם הקבוע של מחצית.

80
00:06:01,650 --> 00:06:07,760
אז הרבה דברי O גדולים כמו זו מסתמכת על פשוט סוג של עושה את זה סוג של מתמטיקה,

81
00:06:07,760 --> 00:06:12,260
עושה סיכומים בחשבון וכאלה סדרה גיאומטריים,

82
00:06:12,260 --> 00:06:17,750
אבל רובם בקורס הזה הם די פשוטים.

83
00:06:17,750 --> 00:06:19,290
אוקיי.

84
00:06:19,290 --> 00:06:24,430
למה הוא מעין כניסה באומגה של n? מה האומגה מתכוונת?

85
00:06:24,430 --> 00:06:27,730
[שני תלמידים שמדברים בו פעם אחת - סתומים] כן. >>

86
00:06:27,730 --> 00:06:30,630
האומגה אתה יכול לחשוב עליו כחסם תחתון.

87
00:06:30,630 --> 00:06:36,550
>> אז לא משנה כמה יעיל אלגוריתם מיון ההכנסה שלך הוא,

88
00:06:36,550 --> 00:06:41,810
ללא קשר לרשימה שחלף ב, תמיד יש להשוות לפחות n דברים

89
00:06:41,810 --> 00:06:44,620
או שיש לו לחזר על דברי n.

90
00:06:44,620 --> 00:06:47,280
מדוע זה כך?

91
00:06:47,280 --> 00:06:51,190
[תלמיד] כי אם הרשימה כבר מיון, דרך החזרה הראשונה

92
00:06:51,190 --> 00:06:54,080
אתה יכול להבטיח רק שהאלמנט הראשון הוא לפחות,

93
00:06:54,080 --> 00:06:56,490
והחזרה השנייה אתה יכול להבטיח רק את שני הראשונות הן

94
00:06:56,490 --> 00:07:00,010
כי אתה לא יודע ששאר הרשימה ממוינת. >> כן.

95
00:07:00,010 --> 00:07:08,910
אם אתה עובר ברשימה ממוינת לחלוטין, לפחות יש לך לעבור על כל המרכיבים

96
00:07:08,910 --> 00:07:12,180
כדי לראות ששום דבר לא צריך להיות עבר בסביבה.

97
00:07:12,180 --> 00:07:14,720
אז עובר על הרשימה ואומר אה, זה כבר מסודר,

98
00:07:14,720 --> 00:07:18,240
זה בלתי אפשרי בשבילך יודע שזה מסודר עד שתבדוק את כל רכיב

99
00:07:18,240 --> 00:07:20,660
כדי לראות שהם מסודרים במטרה.

100
00:07:20,660 --> 00:07:25,290
אז החסם התחתון על מיון הכנסה הוא אומגה של n.

101
00:07:25,290 --> 00:07:28,210
מה המקרה הגרוע ביותר של זמן ריצה מסוג המיזוג,

102
00:07:28,210 --> 00:07:31,390
מקרה הגרוע ביותר להיות גדול O שוב?

103
00:07:31,390 --> 00:07:37,660
אז במקרה הכי הגרוע, איך מעין מיזוג לרוץ?

104
00:07:42,170 --> 00:07:43,690
[תלמיד] N log n. >> כן.

105
00:07:43,690 --> 00:07:49,990
אלגוריתמי המיון הכלליים הם המהירים ביותר n log n. אתה לא יכול לעשות יותר טוב.

106
00:07:51,930 --> 00:07:55,130
>> יש מקרים מיוחדים, ואם יש לנו זמן היום - אבל אנחנו כנראה לא מוכנים -

107
00:07:55,130 --> 00:07:59,330
אנחנו יכולים לראות אחד שעושה טובים יותר מn log n.

108
00:07:59,330 --> 00:08:04,050
אבל במקרה הכללי, אתה לא יכול לעשות יותר טוב מn log n.

109
00:08:04,050 --> 00:08:09,680
וסוג למזג קורה להיות אחד שאתה צריך לדעת על קורס זה שהוא n log n.

110
00:08:09,680 --> 00:08:13,260
ואז אנחנו בעצם להיות יישום זה היום.

111
00:08:13,260 --> 00:08:18,070
ולבסוף, בלא יותר משלושה משפטים, איך עושה את עבודת מיון בחירה?

112
00:08:18,070 --> 00:08:20,370
האם מישהו רוצה לענות, ואני אספור את המשפטים שלך

113
00:08:20,370 --> 00:08:22,390
כי אם אתה הולך על 3 -

114
00:08:25,530 --> 00:08:28,330
מישהו זוכר מיון בחירה?

115
00:08:31,280 --> 00:08:37,809
מיון בחירה הוא בדרך כלל די קל לזכור רק משם.

116
00:08:37,809 --> 00:08:45,350
אתה פשוט לחזר על המערך, למצוא מה הערך הגדול ביותר או קטן ביותר הוא -

117
00:08:45,350 --> 00:08:47,290
מה מטרה שאתה ממיין פנימה

118
00:08:47,290 --> 00:08:50,750
אז בואו נאמר שאנו ממיינים מקטנים ביותר לגדולים ביותר.

119
00:08:50,750 --> 00:08:55,250
אתה לחזר על המערך, מחפש כל האלמנט המינימאלי הוא,

120
00:08:55,250 --> 00:08:59,750
בחר אותו, ואז פשוט להחליף אותו מה שנמצא במקום הראשון.

121
00:08:59,750 --> 00:09:04,090
ולאחר מכן במעבר שני על המערך, לחפש את האלמנט המינימאלי שוב,

122
00:09:04,090 --> 00:09:07,490
בחר אותו, ולאחר מכן להחליף אותו עם מה שיש בעמדה 2.

123
00:09:07,490 --> 00:09:10,650
אז אנחנו רק לקטוף ובחירה בערכי המינימום

124
00:09:10,650 --> 00:09:16,050
והחדרתם לחלק הקדמי של המערך עד שהוא ממוין.

125
00:09:19,210 --> 00:09:21,560
שאלות על זה?

126
00:09:21,560 --> 00:09:25,710
>> אלה בהכרח מופיעים בטפסים שצריכים למלא בזמן שאת הגשת pset.

127
00:09:29,010 --> 00:09:32,360
אלה הם בעצם את התשובות לאלה.

128
00:09:32,360 --> 00:09:34,230
אוקיי, אז עכשיו קידוד בעיות.

129
00:09:34,230 --> 00:09:40,140
אני כבר שלחתי בדוא"ל - האם מישהו לא מקבל דוא"ל ש? אוקיי.

130
00:09:40,140 --> 00:09:46,630
אני כבר שלחתי בדוא"ל את המרחב שאנחנו הולכים להיות באמצעות,

131
00:09:46,630 --> 00:09:52,120
ואם תלחץ על השם שלי - אז אני חושב שאני הולך להיות בתחתית

132
00:09:52,120 --> 00:09:57,170
בגלל r לאחור - אבל אם אתה לוחץ על השם שלי תראה 2 תיקונים.

133
00:09:57,170 --> 00:10:02,650
הגרסה 1 הולכת אני כבר להעתיק ולהדביק את הקוד לתוך החללים

134
00:10:02,650 --> 00:10:06,900
לחיפוש הדבר אתה תצטרך ליישם.

135
00:10:06,900 --> 00:10:10,540
וגרסה 2 תהיה דבר הסוג שאנחנו ליישם לאחר מכן.

136
00:10:10,540 --> 00:10:15,770
אז אתה יכול ללחוץ על גרסת 1 שלי ולעבוד משם.

137
00:10:17,350 --> 00:10:22,060
ועכשיו אנחנו רוצים ליישם חיפוש בינארי.

138
00:10:22,060 --> 00:10:26,470
>> האם מישהו רוצה רק כדי לתת הסבר pseudocode ברמה גבוהה

139
00:10:26,470 --> 00:10:31,440
של מה שאנחנו הולכים לעשות לחיפוש? כן.

140
00:10:31,440 --> 00:10:36,170
[תלמיד] אתה פשוט לקחת את אמצע המערך ולראות אם מה שאתה מחפש

141
00:10:36,170 --> 00:10:38,650
הוא פחות מזה או יותר מזה.

142
00:10:38,650 --> 00:10:41,080
ואם זה פחות, אתה הולך למחצית זה פחות,

143
00:10:41,080 --> 00:10:44,750
ואם זה יותר, אתה הולך למחצית זה יותר ואתה חוזר ואומר שעד שאתה מקבל רק דבר אחד.

144
00:10:44,750 --> 00:10:46,570
[אודן] כן.

145
00:10:46,570 --> 00:10:51,320
שים לב שמערך המספרים שלנו כבר מסודר,

146
00:10:51,320 --> 00:10:57,190
ואז זה אומר שאנחנו יכולים לנצל את זה ואנחנו ראשונים יכולים לבדוק,

147
00:10:57,190 --> 00:11:00,390
בסדר, אני מחפש את המספר 50.

148
00:11:00,390 --> 00:11:03,720
אז אני יכול להיכנס לאמצע.

149
00:11:03,720 --> 00:11:07,380
מזרח קשה להגדיר מתי זה מספר זוגי של דברים,

150
00:11:07,380 --> 00:11:10,820
אבל בואו נגיד שתמיד לחתוך לאמצע.

151
00:11:10,820 --> 00:11:14,420
אז הנה יש לנו 8 דברים, אז באמצע יהיה 16.

152
00:11:14,420 --> 00:11:17,330
אני מחפש 50, ולכן 50 הם יותר מ 16.

153
00:11:17,330 --> 00:11:21,310
אז עכשיו אני יכול בעצם לטפל במערך שלי כרכיבים אלה.

154
00:11:21,310 --> 00:11:23,450
אני יכול לזרוק הכל מ16 מעל.

155
00:11:23,450 --> 00:11:27,440
עכשיו המערך שלי הוא רק 4 האלמנטים האלה, ואני חוזר ואומר.

156
00:11:27,440 --> 00:11:31,910
אז אני רוצה למצוא שוב באמצע, שהוא הולך להיות 42.

157
00:11:31,910 --> 00:11:34,730
42 הם פחות מ 50, אז אני יכול לזרוק את שני היסודות האלה.

158
00:11:34,730 --> 00:11:36,890
זה המערך שנותר לי.

159
00:11:36,890 --> 00:11:38,430
אני הולך למצוא שוב באמצע.

160
00:11:38,430 --> 00:11:42,100
אני מניח 50 היה דוגמה רעה כי אני תמיד זורק דברים לשמאל,

161
00:11:42,100 --> 00:11:48,280
אך באותה המידה, אם אני מחפש משהו

162
00:11:48,280 --> 00:11:52,100
וזה פחות מהאלמנט אני כרגע מסתכל,

163
00:11:52,100 --> 00:11:55,080
אז אני הולך לזרוק את הכל בצד ימין.

164
00:11:55,080 --> 00:11:58,150
אז עכשיו אנחנו צריכים ליישם את זה.

165
00:11:58,150 --> 00:12:02,310
שים לב שאנו צריכים לעבור בגודלו.

166
00:12:02,310 --> 00:12:06,730
אנחנו יכולים גם לא צריכים לגודל שקשה קוד.

167
00:12:06,730 --> 00:12:11,640
אז אם אנחנו להיפטר מזה # להגדיר -

168
00:12:19,630 --> 00:12:21,430
אוקיי.

169
00:12:21,430 --> 00:12:27,180
איך אני יפה יכול להבין מה הגודל של מערך המספרים כיום הוא?

170
00:12:27,180 --> 00:12:30,950
>> כמה אלמנטים במערך המספרים?

171
00:12:30,950 --> 00:12:33,630
[סטודנטים] במדבר, מסגרות ו. האורך?

172
00:12:33,630 --> 00:12:36,600
[אודן] זה לא מקיים ב C.

173
00:12:36,600 --> 00:12:38,580
זקוקים. אורך.

174
00:12:38,580 --> 00:12:42,010
מערכים אין לי נכסים, כך שאין מאפיין אורך של מערכים

175
00:12:42,010 --> 00:12:45,650
שרק ייתן לך עוד עם זאת זה קורה להיות.

176
00:12:48,180 --> 00:12:51,620
[תלמיד] ראה כמה זיכרון יש לו ולחלק בכמה - כן. >>

177
00:12:51,620 --> 00:12:55,810
אז איך אנחנו יכולים לראות כמה זיכרון יש לו? >> [תלמיד] sizeof. >> כן, sizeof.

178
00:12:55,810 --> 00:13:01,680
Sizeof הוא המפעיל שהולך להחזיר את הגודל של מערך המספרים.

179
00:13:01,680 --> 00:13:10,060
וזה הולך להיות שלמים עם זאת יש פעמים רבות בגודל של מספר שלם

180
00:13:10,060 --> 00:13:14,050
מכיוון שזה כמה זיכרון זה באמת תופס.

181
00:13:14,050 --> 00:13:17,630
אז אם אני רוצה מספר דברים במערך,

182
00:13:17,630 --> 00:13:20,560
אז אני הולך לרוצה לחלק בגודל של מספר שלם.

183
00:13:22,820 --> 00:13:26,010
אוקיי. אז זה מאפשר לי לעבור בגודל כאן.

184
00:13:26,010 --> 00:13:29,430
למה אני צריך לעבור בגודל בכלל?

185
00:13:29,430 --> 00:13:38,570
למה אני לא יכול פשוט לעשות כאן גודל int = sizeof (ערימת שחת) / sizeof (int)?

186
00:13:38,570 --> 00:13:41,490
למה זה לא עובד?

187
00:13:41,490 --> 00:13:44,470
[תלמיד] זה לא משתנה גלובלי.

188
00:13:44,470 --> 00:13:51,540
[אודן] שחת קיים ואנחנו עוברים במספרים כערימת שחת,

189
00:13:51,540 --> 00:13:54,700
וזה סוג של בשר על הבאות. כן.

190
00:13:54,700 --> 00:14:00,170
[תלמיד] שחת הוא רק ההתייחסות אליו, כך שהוא יחזור כמה גדול היא שההתייחסות.

191
00:14:00,170 --> 00:14:02,150
כן.

192
00:14:02,150 --> 00:14:09,000
אני בספק אם בהרצאה שראית ערימה עדיין באמת, נכון?

193
00:14:09,000 --> 00:14:11,270
שמנו רק דברתי על זה.

194
00:14:11,270 --> 00:14:16,090
אז הערימה היא שבו כל המשתנים שלך הולכת להיות מאוחסנים.

195
00:14:16,090 --> 00:14:19,960
>> כל זיכרון שהוא הוקצה למשתנים מקומיים הולך במחסנית,

196
00:14:19,960 --> 00:14:24,790
וכל פונקציה מקבלת מקום משלו במחסנית, מסגרתו של המחסנית היא מה זה נקרא.

197
00:14:24,790 --> 00:14:31,590
אז ראשי יש מסגרת המחסנית שלו, ובתוכו הולך להתקיים מערך מספרים זה,

198
00:14:31,590 --> 00:14:34,270
וזה הולך להיות בגודל sizeof (מספרים).

199
00:14:34,270 --> 00:14:38,180
זה הולך להיות גודל של מספרים מחולקים בגודל של אלמנטים,

200
00:14:38,180 --> 00:14:42,010
אבל שכל החיים בתוך המסגרת של המחסנית הראשית.

201
00:14:42,010 --> 00:14:45,190
כאשר אנו קוראים חיפוש, חיפוש מקבל מסגרתו של המחסנית,

202
00:14:45,190 --> 00:14:48,840
מרחב משלו כדי לאחסן את כל המשתנים המקומיים שלה.

203
00:14:48,840 --> 00:14:56,420
אבל טיעונים אלה - כך ערימת השחת הוא לא עותק של כל המערך הזה.

204
00:14:56,420 --> 00:15:00,990
אנחנו לא עוברים בכל המערך כעותק לחיפוש.

205
00:15:00,990 --> 00:15:04,030
הוא רק עובר להתייחסות שהמערך.

206
00:15:04,030 --> 00:15:11,470
אז חיפוש יכול לגשת למספרים אלה באמצעות הפניה זו.

207
00:15:11,470 --> 00:15:17,100
זה עדיין גישה לדברים שחיים בתוך המסגרת של המחסנית הראשית,

208
00:15:17,100 --> 00:15:22,990
אבל בעצם, כשנגיע למצביעים, שאמור להיות בקרוב,

209
00:15:22,990 --> 00:15:24,980
זה מה שהמצביעים הם.

210
00:15:24,980 --> 00:15:29,400
מצביעים הם רק התייחסויות לדברים, ואתה יכול להשתמש במצביעים לגשת לדברים

211
00:15:29,400 --> 00:15:32,030
שנמצאים במסגרות הערימה 'דברים אחרים.

212
00:15:32,030 --> 00:15:37,660
אז למרות שהמספרים הם מקומיים לעיקרי, אנחנו עדיין יכולים לגשת אליה דרך מצביע זה.

213
00:15:37,660 --> 00:15:41,770
אבל מאחר שזה רק מצביע וזה רק הפניה,

214
00:15:41,770 --> 00:15:45,040
sizeof (ערימת שחת) פשוט מחזיר את הגודל של ההתייחסות עוצמה.

215
00:15:45,040 --> 00:15:47,950
זה לא יחזיר את הגודל של דבר זה מצביע.

216
00:15:47,950 --> 00:15:51,110
זה לא יחזיר את הגודל האמיתי של מספרים.

217
00:15:51,110 --> 00:15:55,660
וכך זה לא הולך לעבוד כמו שאנחנו רוצים אותו.

218
00:15:55,660 --> 00:15:57,320
>> שאלות על זה?

219
00:15:57,320 --> 00:16:03,250
מצביעים יהיו הושקעו בפירוט מזוויע יותר באופן משמעותי בשבועות קרובים.

220
00:16:06,750 --> 00:16:13,740
ובגלל זה הרבה דברים שאתה רואה, דברי חיפוש רוב או דברי מיון,

221
00:16:13,740 --> 00:16:16,990
הם כמעט כולם הולכים צריכים לקחת את גודלו האמיתי של המערך,

222
00:16:16,990 --> 00:16:20,440
כי ב-C, אין לנו מושג מה הגודל של המערך הוא.

223
00:16:20,440 --> 00:16:22,720
אתה צריך לעבור באופן ידני את זה פנימה

224
00:16:22,720 --> 00:16:27,190
ואתה לא יכול לעבור באופן ידני בכל המערך כי אתה פשוט עובר בהתייחסות

225
00:16:27,190 --> 00:16:30,390
והיא לא יכולה לקבל את הגודל מההפניה.

226
00:16:30,390 --> 00:16:32,300
אוקיי.

227
00:16:32,300 --> 00:16:38,160
אז עכשיו אנחנו רוצים ליישם את מה שהסביר קודם.

228
00:16:38,160 --> 00:16:41,530
אתה יכול לעבוד על זה לרגע,

229
00:16:41,530 --> 00:16:45,250
ואתה לא צריך לדאוג מקבל הכל באופן מושלם 100% עובדים.

230
00:16:45,250 --> 00:16:51,410
פשוט לכתוב את pseudocode החצי איך אתה חושב שזה צריך לעבוד.

231
00:16:52,000 --> 00:16:53,630
אוקיי.

232
00:16:53,630 --> 00:16:56,350
לא צריך לעשות עם זה לחלוטין עדיין.

233
00:16:56,350 --> 00:17:02,380
אבל, האם מישהו מרגיש בנוח עם מה שיש להם עד כה,

234
00:17:02,380 --> 00:17:05,599
כמו משהו שאנחנו יכולים לעבוד עם ביחד?

235
00:17:05,599 --> 00:17:09,690
האם מישהו רוצה להתנדב? או שאני אאסוף אקראי.

236
00:17:12,680 --> 00:17:18,599
זה לא חייב להיות צודק בכל קנה מידה, אבל משהו שאנחנו יכולים לשנות את מצב עבודה.

237
00:17:18,599 --> 00:17:20,720
[תלמיד] בטח. >> אוקיי.

238
00:17:20,720 --> 00:17:27,220
אז אתה יכול לשמור את השינוי על ידי לחיצה על הסמל השמור הקטן.

239
00:17:27,220 --> 00:17:29,950
אתה Ramya, נכון? >> [תלמיד] כן. >> [אודן] אוקיי.

240
00:17:29,950 --> 00:17:35,140
אז עכשיו אני יכול להציג הגרסה שלך וכל אחד יכול למשוך את התיקון.

241
00:17:35,140 --> 00:17:38,600
וכאן יש לנו - אוקיי.

242
00:17:38,600 --> 00:17:43,160
אז Ramya הלך עם הפתרון רקורסיבית, שהוא בהחלט פתרון חוקי.

243
00:17:43,160 --> 00:17:44,970
יש שתי דרכים שאתה יכול לעשות את הבעיה הזו.

244
00:17:44,970 --> 00:17:48,060
אתה יכול גם לעשות את זה או ערוך את אופן רקורסיבי.

245
00:17:48,060 --> 00:17:53,860
רוב הבעיות שאתה נתקל כי ניתן לעשות זאת באופן רקורסיבי יכולות להיעשות גם ערוך את.

246
00:17:53,860 --> 00:17:58,510
אז הנה אנחנו כבר עשינו את זה באופן רקורסיבי.

247
00:17:58,510 --> 00:18:03,730
>> האם מישהו רוצה להגדיר מה זה אומר לעשות פונקציה רקורסיבית?

248
00:18:07,210 --> 00:18:08,920
[תלמיד] כאשר יש לך פונקציה קורא לעצמו

249
00:18:08,920 --> 00:18:13,470
ולאחר מכן לקרוא על עצמו עד שהוא יוצא עם אמיתי ונכון. >> כן.

250
00:18:13,470 --> 00:18:17,680
פונקציה רקורסיבית היא רק פונקציה שקוראה לעצמו.

251
00:18:17,680 --> 00:18:24,140
יש שלושה דברים גדולים שפונקציה רקורסיבית חייבת להיות.

252
00:18:24,140 --> 00:18:27,310
הראשון הוא כמובן, שהיא ממכנת את עוצמה.

253
00:18:27,310 --> 00:18:29,650
השני הוא מקרה הבסיס.

254
00:18:29,650 --> 00:18:33,390
אז בשלב מסוים הפונקציה צריכה להפסיק לקרוא לעצמו,

255
00:18:33,390 --> 00:18:35,610
וזה מה שמקרה הבסיס הוא עבור.

256
00:18:35,610 --> 00:18:43,860
אז הנה אנחנו יודעים שאנחנו צריכים להפסיק, אנחנו צריכים לוותר בחיפוש שלנו

257
00:18:43,860 --> 00:18:48,150
כאשר תחילת הסוף שווה - ואנחנו מתכוונים לעבור על מה שאומרים.

258
00:18:48,150 --> 00:18:52,130
אבל לבסוף, הדבר האחרון שחשוב לי פונקציות רקורסיביות:

259
00:18:52,130 --> 00:18:59,250
הפונקציות איכשהו צריכות להתקרב למקרה הבסיס.

260
00:18:59,250 --> 00:19:04,140
כמו שאם אתה לא ממש מעדכן כל דבר בעת ביצוע השיחה השנייה רקורסיבית,

261
00:19:04,140 --> 00:19:07,880
אם אתה ממש רק להתקשר לפונקציה שוב באותם טיעונים

262
00:19:07,880 --> 00:19:10,130
ואין משתנים גלובליים השתנו או משהו,

263
00:19:10,130 --> 00:19:14,430
אתה לעולם לא להגיע למקרה בסיס, ובמקרה זה לא טוב.

264
00:19:14,430 --> 00:19:17,950
זה יהיה רקורסיה אינסופית והצפת ערימה.

265
00:19:17,950 --> 00:19:24,330
אבל כאן אנחנו רואים שהעדכון שקורה מאז אנחנו מעדכנים להתחיל + סוף / 2,

266
00:19:24,330 --> 00:19:28,180
אנחנו מעדכנים את טיעון הסוף כאן, אנו מעדכנים את הוויכוח מתחיל כאן.

267
00:19:28,180 --> 00:19:32,860
אז בכל השיחות רקורסיבית אנו מעדכנים משהו. אוקיי.

268
00:19:32,860 --> 00:19:38,110
האם אתה רוצה ללכת אלינו באמצעות הפתרון שלך? >> בטח.

269
00:19:38,110 --> 00:19:44,270
אני משתמש SearchHelp כך שכל זמן אני עושה קריאה לפונקציה זו

270
00:19:44,270 --> 00:19:47,910
יש לי התחלה של איפה אני מחפש במערך וסופו של דבר

271
00:19:47,910 --> 00:19:49,380
למקום בו אני מחפש את המערך.

272
00:19:49,380 --> 00:19:55,330
>> בכל השלב שבו הוא אומר שזה האלמנט האמצעי, שהוא התחילה + הסוף / 2,

273
00:19:55,330 --> 00:19:58,850
הוא ששווה למה שאנחנו מחפשים?

274
00:19:58,850 --> 00:20:04,650
ואם כן, אז מצאנו אותה, ואני מניח שזה יעבור את הרמות של רקורסיה.

275
00:20:04,650 --> 00:20:12,540
ואם זה לא נכון, ואז תבדקו אם זה ערך אמצע המערך הוא גדול מדי,

276
00:20:12,540 --> 00:20:19,320
ובמקרה כזה אנו מסתכלים על חיצו השמאלי של המערך על ידי הולך מהתחלה למדד האמצע.

277
00:20:19,320 --> 00:20:22,710
ואחרת אנו עושים סוף המחצית.

278
00:20:22,710 --> 00:20:24,740
[אודן] אוקיי.

279
00:20:24,740 --> 00:20:27,730
זה נשמע טוב.

280
00:20:27,730 --> 00:20:36,640
אוקיי, אז כמה דברים, ובעצם, זה דבר מאוד ברמה גבוהה

281
00:20:36,640 --> 00:20:41,270
כי אתה לעולם לא צריך לדעת לקורס זה, אבל זה נכון.

282
00:20:41,270 --> 00:20:46,080
פונקציות רקורסיבית, אתה תמיד שומעים שהם עסקה גרועה

283
00:20:46,080 --> 00:20:51,160
כי אם אתה קורא לעצמך באופן רקורסיבי פעמים רבות מדי, אתה מקבל הצפת ערימה

284
00:20:51,160 --> 00:20:54,990
מאז, כמו שאמרתי קודם, כל פונקציה מקבלת מסגרתו של המחסנית.

285
00:20:54,990 --> 00:20:59,500
אז כל שיחה של הפונקציה רקורסיבית מקבלת מסגרתו של המחסנית.

286
00:20:59,500 --> 00:21:04,140
אז אם אתה עושה 1000 שיחות רקורסיבית, אתה מקבל 1,000 מסגרות מחסנית,

287
00:21:04,140 --> 00:21:08,390
ומהר אתה להוביל שיש יותר מדי מסגרות מחסנית ודברים פשוט לשבור.

288
00:21:08,390 --> 00:21:13,480
אז בגלל זה פונקציות רקורסיביות הן בדרך כלל רעות.

289
00:21:13,480 --> 00:21:19,370
למרות זאת, קיימת תת קבוצה נחמדה של פונקציות רקורסיביות נקראת פונקציות זנב רקורסיבית,

290
00:21:19,370 --> 00:21:26,120
וזה קורה להיות דוגמה לאחד שבו אם למהדר מבחין זו

291
00:21:26,120 --> 00:21:29,920
ושהוא צריך, אני חושב - בקלאנג, אם תעבור אותו הדגל-O2

292
00:21:29,920 --> 00:21:33,250
אז זה יבחין זה זנב רקורסיבית ולעשות דברים טובים.

293
00:21:33,250 --> 00:21:40,050
>> זה יהיה שימוש חוזר באותה מסגרת מחסנית שוב ושוב עבור כל שיחה רקורסיבית.

294
00:21:40,050 --> 00:21:47,010
וכך מאז שאתה משתמש באותה מסגרת מחסנית, אתה לא צריך לדאוג

295
00:21:47,010 --> 00:21:51,690
אי מחסנית עולה על גדותיו, ובו בזמן, כמו שאמרת קודם,

296
00:21:51,690 --> 00:21:56,380
ברגע שאתה שם החזר אמיתי, אז זה חייב להחזיר את כל המסגרות הללו המחסנית

297
00:21:56,380 --> 00:22:01,740
והשיחה 10 לSearchHelp יש לחזור ל9, יש לחזור ל8.

298
00:22:01,740 --> 00:22:05,360
אז גם זה לא צריך לקרות כאשר פונקציות הן זנב רקורסיבית.

299
00:22:05,360 --> 00:22:13,740
וכן מה שעושה את זנב פונקציה רקורסיבית זה היא הודעה שניתנה לכל קריאה לsearchHelp

300
00:22:13,740 --> 00:22:18,470
השיחה רקורסיבית שהוא עושה מה שהוא חוזר.

301
00:22:18,470 --> 00:22:25,290
אז בקריאה הראשונה לSearchHelp, או שאנחנו בתמורת שווא באופן מיידי,

302
00:22:25,290 --> 00:22:29,590
לחזור מייד אמיתי, או שאנחנו עושים שיחה רקורסיבית לSearchHelp

303
00:22:29,590 --> 00:22:33,810
שבו מה שאנחנו חוזרים הוא מה קריאה שחוזרת.

304
00:22:33,810 --> 00:22:51,560
ואנחנו לא יכולים לעשות את זה אם אנחנו עושים משהו כזה int x = SearchHelp, תשואת x * 2,

305
00:22:51,560 --> 00:22:55,440
רק כמה שינוי אקראי.

306
00:22:55,440 --> 00:23:01,470
>> אז עכשיו שיחה רקורסיבית זה, זה int x = שיחה רקורסיבית SearchHelp,

307
00:23:01,470 --> 00:23:05,740
כבר לא זנב רקורסיבית משום שהוא בעצם אינו צריך לחזור

308
00:23:05,740 --> 00:23:10,400
חזרה למסגרת מחסנית קודמת כך שהשיחה הקודמת לפונקציה

309
00:23:10,400 --> 00:23:13,040
אז יכול לעשות משהו עם ערך ההחזרה.

310
00:23:13,040 --> 00:23:22,190
אז זה לא זנב רקורסיבית, אבל מה שהיינו לנו לפני שהוא יפה זנב רקורסיבית. כן.

311
00:23:22,190 --> 00:23:27,000
[תלמיד] האם אין מקרה הבסיס השני ייבדק 1

312
00:23:27,000 --> 00:23:30,640
כיוון שיכול להיות מצב שבו בעת שתעבור אותו בטענה

313
00:23:30,640 --> 00:23:35,770
יש לך להתחיל = סוף, אבל הם ערך המחט.

314
00:23:35,770 --> 00:23:47,310
השאלה הייתה אנחנו לא יכולים נתקלנו במקרה שבו הסוף הוא ערך המחט

315
00:23:47,310 --> 00:23:52,000
או להתחיל = הסוף, כראוי, תתחיל = הסוף

316
00:23:52,000 --> 00:23:59,480
ואתה לא ממש בדקת כי ערך מסוים עדיין,

317
00:23:59,480 --> 00:24:03,910
אז תתחיל + הסוף / 2 היא רק הולך להיות אותו הערך.

318
00:24:03,910 --> 00:24:07,890
אבל כבר חזרתי כוזב ואנחנו אף פעם לא ממש בדקנו את הערך.

319
00:24:07,890 --> 00:24:14,240
אז לכל הפחות, בקריאה הראשונה, אם גודל הוא 0, אז אנחנו רוצים לחזור שווא.

320
00:24:14,240 --> 00:24:17,710
אבל אם גודל הוא 1, אז ההתחלה היא לא הולכת לסוף שווה,

321
00:24:17,710 --> 00:24:19,820
ואנחנו לפחות לבדוק אלמנט אחד.

322
00:24:19,820 --> 00:24:26,750
אבל אני חושב שאתה צודק בכך שאנו יכולים בסופו של מקרה שבו מתחילים + סוף / 2,

323
00:24:26,750 --> 00:24:31,190
תחילת סופו להיות זהה להתחלה + הסוף / 2,

324
00:24:31,190 --> 00:24:35,350
אבל אנחנו אף פעם לא ממש בדקנו את המרכיב הזה.

325
00:24:35,350 --> 00:24:44,740
>> אז אם אנחנו בודקים ראשונים הוא אלמנט אמצע הערך שאנחנו מחפשים,

326
00:24:44,740 --> 00:24:47,110
אז אנחנו יכולים לחזור אמיתיים באופן מיידי.

327
00:24:47,110 --> 00:24:50,740
אחר אם הן זהות, אז אין טעם להמשיך

328
00:24:50,740 --> 00:24:58,440
מאז אנחנו רק הולכים לעדכן למקרה שבו אנחנו נמצאים במערך בודד רכיב.

329
00:24:58,440 --> 00:25:01,110
אם כי אלמנט היחיד הוא לא זה שאנחנו מחפשים,

330
00:25:01,110 --> 00:25:03,530
אז הכל בסדר. כן.

331
00:25:03,530 --> 00:25:08,900
[תלמיד] העניין הוא שמאז גודל הוא למעשה גדול יותר ממספר האלמנטים במערך,

332
00:25:08,900 --> 00:25:13,070
יש כבר קיזוז - >> כך גם גודל -

333
00:25:13,070 --> 00:25:19,380
[תלמיד] תגיד אם המערך היה בגודל 0, אז SearchHelp יהיה למעשה לבדוק את ערימת שחת של 0

334
00:25:19,380 --> 00:25:21,490
בשיחה הראשונה.

335
00:25:21,490 --> 00:25:25,300
המערך יש גודל 0, אז 0 הם - >> כן.

336
00:25:25,300 --> 00:25:30,750
יש עוד דבר ש-- זה יכול להיות טוב. בואו נחשוב.

337
00:25:30,750 --> 00:25:40,120
אז אם המערך היה 10 אלמנטים והאחד באמצע שאנחנו הולכים לבדוק הוא מדד 5,

338
00:25:40,120 --> 00:25:45,700
כך אנחנו בודקים 5, ונניח שהערך הוא פחות.

339
00:25:45,700 --> 00:25:50,720
אז אנחנו זורקים הכל מ5 ואילך.

340
00:25:50,720 --> 00:25:54,030
אז תתחיל + הסוף / 2 הולך להיות הסוף החדש שלנו,

341
00:25:54,030 --> 00:25:57,450
אז כן, זה תמיד הולך להישאר מעבר לסוף המערך.

342
00:25:57,450 --> 00:26:03,570
אם זה מקרה, אם זה היה אפילו מוזר או, אז היינו בודק, יניח, 4,

343
00:26:03,570 --> 00:26:05,770
אבל אנחנו עדיין זורקים -

344
00:26:05,770 --> 00:26:13,500
אז כן, בסוף הוא תמיד יהיה מעבר לסוף בפועל של המערך.

345
00:26:13,500 --> 00:26:18,350
אז האלמנטים שאנו מתמקדים ב, הסוף הוא תמיד יהיה זה שאחריו.

346
00:26:18,350 --> 00:26:24,270
ולכן אם עושה תחילת הסוף שווה אי פעם, אנחנו נמצאים במערך בגודל 0.

347
00:26:24,270 --> 00:26:35,600
>> הדבר השני שחשבתי הוא שאנחנו מעדכנים מתחילים להיות מתחילים + הסוף / 2,

348
00:26:35,600 --> 00:26:44,020
אז זה מקרה שאני מתקשה עם, שבו מתחיל + הסוף / 2

349
00:26:44,020 --> 00:26:46,820
הוא האלמנט אנחנו בודקים.

350
00:26:46,820 --> 00:26:58,150
בואו נגיד שיש לנו מערך זה 10-אלמנט. לא משנה מה.

351
00:26:58,150 --> 00:27:03,250
אז תתחיל + הסוף / 2 הולך להיות משהו דומה לזה,

352
00:27:03,250 --> 00:27:07,060
ואם זה לא הערך, שאנו רוצים לעדכן.

353
00:27:07,060 --> 00:27:10,060
הערך הוא גדול יותר, ולכן אנחנו רוצים להסתכל על מחצית זו של המערך.

354
00:27:10,060 --> 00:27:15,910
אז איך אנחנו מעדכנים את ההתחלה, אנו מעדכנים את התחילה עכשיו להיות האלמנט הזה.

355
00:27:15,910 --> 00:27:23,790
אבל זה עדיין יכול לעבוד, או לכל הפחות, אתה יכול לעשות את תחילת הסוף + / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[תלמיד] אתה לא צריך להפעיל את + הסוף [לא ברור] >> כן.

357
00:27:27,850 --> 00:27:33,240
כבר בדקנו את האלמנט הזה ויודעים שזה לא זה שאנחנו מחפשים.

358
00:27:33,240 --> 00:27:36,800
אז אנחנו לא צריכים לעדכן את ההתחלה להיות האלמנט הזה.

359
00:27:36,800 --> 00:27:39,560
אנחנו פשוט יכולים לדלג על זה ולעדכן להתחיל להיות האלמנט הזה.

360
00:27:39,560 --> 00:27:46,060
והאם יש בכלל מקרה, בואו נגיד, שזה היה סוף,

361
00:27:46,060 --> 00:27:53,140
כן אז להתחיל יהיה זה, יתחיל + הסוף / 2 יהיו זה,

362
00:27:53,140 --> 00:28:00,580
+ להתחיל סוף - כן, אני חושב שזה יכול בסופו הלולאה אינסופית.

363
00:28:00,580 --> 00:28:12,690
בואו נגיד שזה רק מערך של 2 או גודל מערך בגודל 1. אני חושב שזה יעבוד.

364
00:28:12,690 --> 00:28:19,490
אז כרגע, ההתחלה היא שרכיב וסופו של דבר הוא 1 מעבר לו.

365
00:28:19,490 --> 00:28:24,110
אז האלמנט שאנחנו הולכים לבדוק את זה הוא אחת,

366
00:28:24,110 --> 00:28:29,400
ואז, כשלעדכן התחלה, אנו מעדכנים את ההתחלה להיות 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
שהוא הולך לסיים אותנו בחזרה עם התחילה להיות האלמנט הזה.

368
00:28:33,160 --> 00:28:36,210
>> אז אנחנו בודקים אותו היסוד שוב ושוב.

369
00:28:36,210 --> 00:28:43,310
אז זה מקרה שבו כל קריאה רקורסיבית חייבת בעצם לעדכן משהו.

370
00:28:43,310 --> 00:28:48,370
אז אנחנו צריכים לעשות התחלה + הסוף / 2 + 1, אחרת יש עילה לתביעה

371
00:28:48,370 --> 00:28:50,710
לאן אנחנו לא ממש מעדכנים התחלה.

372
00:28:50,710 --> 00:28:53,820
כולם רואים את זה?

373
00:28:53,820 --> 00:28:56,310
אוקיי.

374
00:28:56,310 --> 00:29:03,860
האם יש למישהו שאלות על פתרון זה או כל עוד הערות?

375
00:29:05,220 --> 00:29:10,280
אוקיי. האם יש למישהו פתרון איטרטיבי שכולנו יכול להסתכל?

376
00:29:17,400 --> 00:29:20,940
האם כולנו עושים את זה באופן רקורסיבי?

377
00:29:20,940 --> 00:29:25,950
או גם אני מניח שאם אתה פתחת, אז אתה יכול לדרוס הקודם שלך.

378
00:29:25,950 --> 00:29:28,810
האם זה לשמור באופן אוטומטי? אני לא חיובי.

379
00:29:35,090 --> 00:29:39,130
האם מישהו היה איטרטיבי?

380
00:29:39,130 --> 00:29:42,430
אנחנו יכולים לעבור את זה ביחד אם לא.

381
00:29:46,080 --> 00:29:48,100
הרעיון הולך להיות אותו הדבר.

382
00:30:00,260 --> 00:30:02,830
איטרטיבי פתרון.

383
00:30:02,830 --> 00:30:07,140
אנחנו הולכים לרוצים בעצם לעשות את אותו הרעיון

384
00:30:07,140 --> 00:30:16,530
לאן אנחנו רוצים לעקוב אחר הסיום החדש של המערך וההתחלה החדשה של המערך

385
00:30:16,530 --> 00:30:18,510
ולעשות את זה שוב ושוב.

386
00:30:18,510 --> 00:30:22,430
ואם מה שאנחנו עוקבים אחרי כהתחלה והסוף תמיד מצטלב,

387
00:30:22,430 --> 00:30:29,020
אז אנחנו לא מוצאים אותו ואנחנו יכולים לחזור שווא.

388
00:30:29,020 --> 00:30:37,540
אז איך אני עושה את זה? למישהו יש הצעות או קוד לי למשוך את?

389
00:30:42,190 --> 00:30:47,450
[תלמיד] האם לולאה בזמן. >> כן.

390
00:30:47,450 --> 00:30:49,450
אתה הולך רוצה לעשות לולאה.

391
00:30:49,450 --> 00:30:51,830
>> האם יש לך קוד שאני יכול למשוך למעלה, או מה שאתה הולך להציע?

392
00:30:51,830 --> 00:30:56,340
[תלמיד] אני חושב שכן. >> בסדר. זה עושה את הדברים יותר קלים. מה היה השם שלך?

393
00:30:56,340 --> 00:30:57,890
[תלמיד] לוקאס.

394
00:31:00,140 --> 00:31:04,190
גרסות 1. אוקיי.

395
00:31:04,190 --> 00:31:13,200
נמוך הוא מה שאנחנו מכנים נתחיל לפני.

396
00:31:13,200 --> 00:31:17,080
למעלה זה לא ממש מה שקראנו לפני הסוף.

397
00:31:17,080 --> 00:31:22,750
למעשה, סופו הוא כעת במערך. זה אלמנט שצריך לשקול.

398
00:31:22,750 --> 00:31:26,890
כל כך נמוך הוא 0, הוא עד הגודל של המערך - 1,

399
00:31:26,890 --> 00:31:34,780
ועכשיו אנחנו לופים, ואנחנו בודקים -

400
00:31:34,780 --> 00:31:37,340
אני מניח שאתה יכול לעבור אותו.

401
00:31:37,340 --> 00:31:41,420
מה הייתה החשיבה שלך בכל זה? תראה לנו את הקוד שלך.

402
00:31:41,420 --> 00:31:49,940
[תלמיד] בטח. תראה את ערך ערימת השחת באמצע והשווית אותו למחט.

403
00:31:49,940 --> 00:31:58,520
אז אם זה גדול מהמחט שלך, אז אתה רוצה - אה, בעצם, זה צריך להיות הפוך.

404
00:31:58,520 --> 00:32:05,180
אתה הולך רוצה לזרוק המחצית הימנית, ואז כן, זה צריך להיות בדרך.

405
00:32:05,180 --> 00:32:08,830
[אודן] אז זה צריך להיות פחות? האם זה מה שאמרת? >> [תלמיד] כן.

406
00:32:08,830 --> 00:32:10,390
[אודן] אוקיי. פחות.

407
00:32:10,390 --> 00:32:15,700
אז אם מה שאנחנו מחפשים בהוא קטן יותר ממה שאנחנו רוצים,

408
00:32:15,700 --> 00:32:19,410
אז כן, אנחנו רוצים לזרוק את חיצו השמאלי,

409
00:32:19,410 --> 00:32:22,210
שאומרים שאנחנו מעדכנים את כל מה שאנחנו שוקלים

410
00:32:22,210 --> 00:32:26,610
על ידי ההעברה נמוכה בצד הימין של המערך.

411
00:32:26,610 --> 00:32:30,130
זה נראה טוב.

412
00:32:30,130 --> 00:32:34,550
אני חושב שיש לו את אותה בעיה שאמרנו על קודמו,

413
00:32:34,550 --> 00:32:49,760
שבו אם נמוך הוא 0 ועד הוא 1, אז נמוך + עד / 2 הולכים להגדיר להיות אותו הדבר שוב.

414
00:32:49,760 --> 00:32:53,860
>> וגם אם זה לא המקרה, הוא עדיין יעיל יותר לפחות

415
00:32:53,860 --> 00:32:57,630
רק כדי לזרוק את האלמנט פשוט הסתכלנו בו אנו יודעים הוא שגוי.

416
00:32:57,630 --> 00:33:03,240
כל כך נמוך עד + / 2 + 1 - >> [תלמיד] זה צריך להיות דרך האחרת.

417
00:33:03,240 --> 00:33:05,900
[אודן] או שזה צריך להיות - 1 והשני צריך להיות + 1.

418
00:33:05,900 --> 00:33:09,580
[תלמיד] ולא צריך להיות כפול סימן שוויון. >> [אודן] כן.

419
00:33:09,580 --> 00:33:11,340
[תלמיד] כן.

420
00:33:14,540 --> 00:33:15,910
אוקיי.

421
00:33:15,910 --> 00:33:21,280
וסוף סוף, עכשיו שיש לנו + 1 זה - דבר 1,

422
00:33:21,280 --> 00:33:31,520
זה - זה לא יכול להיות - האם זה בכלל אפשרי לנמוך כדי לגמור עם ערך גדול יותר מאשר עד?

423
00:33:35,710 --> 00:33:40,320
אני חושב שהדרך היחידה שיכול לקרות - האם זה אפשרי? >> [תלמיד] אני לא יודע.

424
00:33:40,320 --> 00:33:45,220
אבל אם זה יגיע חתוך ואז הוא מקבל מינוס ש1 ולאחר מכן - >> כן.

425
00:33:45,220 --> 00:33:47,480
[תלמיד] זה יהיה אולי מסתבך.

426
00:33:49,700 --> 00:33:53,940
אני חושב שזה צריך להיות טוב רק בגלל

427
00:33:53,940 --> 00:33:58,800
כדי שזה בסופו נמוך הם היו צריכים להיות שווים, אני חושב.

428
00:33:58,800 --> 00:34:03,070
אבל אם הם שווים, אז לא היה עושים את הלולאה בזמן כדי להתחיל עם

429
00:34:03,070 --> 00:34:06,670
ואנחנו רק היו מחזירים את הערך. אז אני חושב שאנחנו טובים עכשיו.

430
00:34:06,670 --> 00:34:11,530
שים לב שלמרות שבעיה זו היא כבר לא רקורסיבית,

431
00:34:11,530 --> 00:34:17,400
אותו הסוג של רעיונות חל בו אנו יכולים לראות איך זה כל כך בקלות משאיל את עצמו

432
00:34:17,400 --> 00:34:23,659
לפתרון רקורסיבית על ידי העובדה שאנחנו רק מעדכנים את המדדים שוב ושוב,

433
00:34:23,659 --> 00:34:29,960
אנחנו עושים את הבעיה קטנה יותר ויותר, אנחנו מתמקדים בקבוצת משנה של המערך.

434
00:34:29,960 --> 00:34:40,860
[תלמיד] אם נמוך הוא 0 ועד הוא 1, שניהם יהיו 0 + 1/2, שהייתי הולכים ל0,

435
00:34:40,860 --> 00:34:44,429
ואז אחד תהיה + 1, אחד יהיה - 1.

436
00:34:47,000 --> 00:34:50,870
[תלמיד] איפה אנחנו בודקים שוויון?

437
00:34:50,870 --> 00:34:55,100
כמו שאם האמצעי הוא למעשה מחט?

438
00:34:55,100 --> 00:34:58,590
כרגע אנחנו לא עושים את זה? הו!

439
00:35:00,610 --> 00:35:02,460
אם זהו -

440
00:35:05,340 --> 00:35:13,740
כן. אנחנו לא יכולים פשוט לעשות את הבדיקה לכאן, כי נניח האמצע הראשון -

441
00:35:13,740 --> 00:35:16,430
[תלמיד] הם ממש כמו לא לזרוק מאוגדים.

442
00:35:16,430 --> 00:35:20,220
אז אם אתה זורק כרוך, אתה צריך לבדוק את זה ראשון או משהו כזה.

443
00:35:20,220 --> 00:35:23,350
אה. כן. >> [תלמיד] כן.

444
00:35:23,350 --> 00:35:29,650
אז עכשיו יש לנו לזרוק אותנו כרגע הסתכלנו,

445
00:35:29,650 --> 00:35:33,260
מה שאומר שעכשיו אנחנו צריכים גם שנהיה לי

446
00:35:33,260 --> 00:35:44,810
אם (ערימת שחת [(נמוך + עד) / 2] == מחט), ואז אנחנו יכולים לחזור אמיתיים.

447
00:35:44,810 --> 00:35:52,070
ואם אני שם אחר או סתם אם, זה אומר פשוטו כמשמעו אותו הדבר

448
00:35:52,070 --> 00:35:57,110
בגלל זה היה חוזר נכון.

449
00:35:57,110 --> 00:36:01,450
אז אני אשים אחר אם, אבל זה לא משנה.

450
00:36:01,450 --> 00:36:10,440
>> אז אם זה אחר, זה אחר, וזה דבר שכיח שאני עושה

451
00:36:10,440 --> 00:36:14,340
שבו גם אם זה המקרה שבו הכל טוב כאן,

452
00:36:14,340 --> 00:36:22,780
כמו נמוך לא יכול להיות גדולה מלמעלה, זה לא שווה את החשיבה לגבי שאלה אם זה נכון.

453
00:36:22,780 --> 00:36:28,010
אז אתה יכול גם לומר אילו נמוך הוא פחות או שווה ל

454
00:36:28,010 --> 00:36:30,720
או בזמן נמוך הוא פחות מ

455
00:36:30,720 --> 00:36:35,300
כך שאם הם אי פעם שווים או נמוכים קורה לוותר,

456
00:36:35,300 --> 00:36:40,130
אז אנחנו יכולים לצאת מהלולאה הזו.

457
00:36:41,410 --> 00:36:44,630
שאלות, חששות, הערות?

458
00:36:47,080 --> 00:36:49,270
אוקיי. זה נראה טוב.

459
00:36:49,270 --> 00:36:52,230
עכשיו אנחנו רוצים לעשות את זה.

460
00:36:52,230 --> 00:37:04,030
אם נלך לגרסה השנייה שלי, אנחנו רואים את אותם מספרים אלה,

461
00:37:04,030 --> 00:37:07,550
אבל עכשיו הם כבר לא במטרת מיון.

462
00:37:07,550 --> 00:37:12,840
ואנחנו רוצים ליישם את סוג שימוש בכל אלגוריתם ב O של n log n.

463
00:37:12,840 --> 00:37:17,240
אז איזה אלגוריתם אתה חושב שאנחנו צריכים ליישם כאן? >> [תלמיד] מיון מיזוג.

464
00:37:17,240 --> 00:37:23,810
[אודן] כן. סוג המיזוג הוא O (n log n), כך שזה מה שאנחנו הולכים לעשות.

465
00:37:23,810 --> 00:37:26,680
והבעיה הולכת להיות די דומה,

466
00:37:26,680 --> 00:37:31,920
שבו בקלות משאילה את עצמו לפתרון רקורסיבית.

467
00:37:31,920 --> 00:37:35,580
אנחנו גם יכולים לבוא עם פתרון איטרטיבי אם אנחנו רוצים,

468
00:37:35,580 --> 00:37:42,540
אבל רקורסיה תהיה יותר קלה כאן ואנחנו צריכים לעשות רקורסיה.

469
00:37:45,120 --> 00:37:49,530
אני מניח שהוא יעבור סוג המיזוג ראשון,

470
00:37:49,530 --> 00:37:54,280
למרות שיש וידאו מקסים במיון מיזוג כבר. [שחוק]

471
00:37:54,280 --> 00:37:59,780
אז למזג מיון יש - אני מבזבז כל כך הרבה של מאמר זה.

472
00:37:59,780 --> 00:38:02,080
אה, יש רק כדור אחד.

473
00:38:02,080 --> 00:38:03,630
אז מיזוג.

474
00:38:08,190 --> 00:38:12,470
אה, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
אוקיי.

476
00:38:29,910 --> 00:38:33,460
המיזוג לוקח שני מערכים נפרדים.

477
00:38:33,460 --> 00:38:36,780
בנפרד שני המערכים האלה שניהם מסודרים.

478
00:38:36,780 --> 00:38:40,970
אז מערך זה, 1, 3, 5, מיון. מערך זה, 0, 2, 4, ממוין.

479
00:38:40,970 --> 00:38:46,710
עכשיו מה שצריך לעשות הוא מיזוג לשלב אותם לתוך מערך בודד שבעצמו מיון.

480
00:38:46,710 --> 00:38:57,130
אז אנחנו רוצים מערך בגודל 6 שהוא הולך להיות האלמנטים הללו בתוכו

481
00:38:57,130 --> 00:38:59,390
כדי למיין.

482
00:38:59,390 --> 00:39:03,390
>> וכדי שנוכל לנצל את העובדה ששני המערכים האלה מסודרים

483
00:39:03,390 --> 00:39:06,800
לעשות את זה בזמן ליניארי,

484
00:39:06,800 --> 00:39:13,510
משמעות של זמן ליניארי אם מערך זה הוא x גודל וזה y גודל,

485
00:39:13,510 --> 00:39:20,970
אז האלגוריתם הכולל צריך להיות O (x + y). אוקיי.

486
00:39:20,970 --> 00:39:23,150
אז הצעות.

487
00:39:23,150 --> 00:39:26,030
[תלמיד] האם אנו יכולים להתחיל מהשמאל?

488
00:39:26,030 --> 00:39:30,150
אז אתה תשים 0 למטה ראשון ולאחר מכן 1 ולאחר מכן כאן אתה נמצא בבית 2.

489
00:39:30,150 --> 00:39:33,320
אז זה כמו סוג של יש לך כרטיסייה שנעה לצד ימין. >> [אודן] כן.

490
00:39:33,320 --> 00:39:41,070
עבור שני המערכים האלה אם רק להתמקד באלמנט השמאלי ביותר.

491
00:39:41,070 --> 00:39:43,530
מפני ששני המערכים מסודרים, אנחנו יודעים ש2 האלמנטים הללו

492
00:39:43,530 --> 00:39:46,920
הם המרכיבים הקטנים ביותר במערך אחד.

493
00:39:46,920 --> 00:39:53,500
אז זה אומר ש1 מתוך 2 האלמנטים הללו חייב להיות האלמנט הקטן ביותר במערך הממוזג שלנו.

494
00:39:53,500 --> 00:39:58,190
זה פשוט כל כך קורה כי הקטן ביותר הוא האחד מצד ימין הפעם.

495
00:39:58,190 --> 00:40:02,580
לכן אנחנו לוקחים 0, להכניס אותו בצד השמאל, כי 0 הן פחות מ 1,

496
00:40:02,580 --> 00:40:08,210
אז קח 0, להכניס אותו למקומו הראשון שלנו, ואז אנחנו מעדכנים את זה

497
00:40:08,210 --> 00:40:12,070
עכשיו להתמקד בשלישייה הראשונה.

498
00:40:12,070 --> 00:40:14,570
ועכשיו אנחנו חוזרים.

499
00:40:14,570 --> 00:40:20,670
אז עכשיו אנו משווים 2 ו 1. 1 הוא קטן יותר, ולכן נכניס 1.

500
00:40:20,670 --> 00:40:25,300
אנו מעדכנים מצביע זה כדי להצביע על הבחור הזה.

501
00:40:25,300 --> 00:40:33,160
עכשיו אנחנו עושים את זה שוב, ולכן 2. זה יעדכן, להשוות אלה 2, 3.

502
00:40:33,160 --> 00:40:37,770
זה עדכונים, ולאחר מכן 4 ו 5.

503
00:40:37,770 --> 00:40:42,110
אז זה מיזוג.

504
00:40:42,110 --> 00:40:49,010
>> זה צריך להיות די ברור שזה הזמן ליניארי מאז אנחנו פשוט ללכת על פני כל רכיב פעם אחת.

505
00:40:49,010 --> 00:40:55,980
וזה הצעד הגדול ביותר ליישום סוג המיזוג עושה את זה.

506
00:40:55,980 --> 00:40:59,330
וזה לא כל כך קשה.

507
00:40:59,330 --> 00:41:15,020
כמה דברים צריכים להדאיג אותנו הם, בואו נאמר שהיו המיזוג 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
במקרה זה אנו בסופו של התרחיש שבו זה הולך להיות יותר קטן,

509
00:41:30,930 --> 00:41:36,160
אז לעדכן מצביע זה, זה הולך להיות יותר קטן, עדכון זה,

510
00:41:36,160 --> 00:41:41,280
זה נראה קטן יותר, ועכשיו יש לך להכיר

511
00:41:41,280 --> 00:41:44,220
כשאתה כבר ממש נגמר של אלמנטים להשוות עם.

512
00:41:44,220 --> 00:41:49,400
מכיוון שאנו כבר השתמשנו בכל המערך הזה,

513
00:41:49,400 --> 00:41:55,190
הכל במערך זה עכשיו רק מוכנס כאן.

514
00:41:55,190 --> 00:42:02,040
אז אם אי פעם נתקלו במצב שבו אחד מהמערכים שלנו ממוזג כבר לגמרי,

515
00:42:02,040 --> 00:42:06,510
אז פשוט לקחת את כל האלמנטים של מערך האחר ולהכניס אותם לתוך סוף המערך.

516
00:42:06,510 --> 00:42:13,630
אז אנחנו פשוט יכולים להוסיף 4, 5, 6. אוקיי.

517
00:42:13,630 --> 00:42:18,070
זה דבר אחד שצריך להיזהר.

518
00:42:22,080 --> 00:42:26,120
יישום שצריך להיות שלב 1.

519
00:42:26,120 --> 00:42:32,600
מיזוג למיין אז בהתבסס על זה, זה 2 שלבים, 2 צעדים מטופשים.

520
00:42:38,800 --> 00:42:42,090
בואו רק לתת מערך זה.

521
00:42:57,920 --> 00:43:05,680
אז למזג מיון, שלב 1 הוא באופן רקורסיבי לשבור את המערך לחצי.

522
00:43:05,680 --> 00:43:09,350
אז לפצל מערך זה לחצי.

523
00:43:09,350 --> 00:43:22,920
עכשיו יש לנו 4, 15, 16, 50 ו 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
ועכשיו אנחנו עושים את זה שוב ונפרדנו אלה לחצי.

525
00:43:25,800 --> 00:43:27,530
אני פשוט אעשה את זה בצד זה.

526
00:43:27,530 --> 00:43:34,790
אז 4, 15 ו 16, 50.

527
00:43:34,790 --> 00:43:37,440
היינו עושה את אותו דבר שוב כאן.

528
00:43:37,440 --> 00:43:40,340
ועכשיו אנחנו לפצל אותו לשני חצאים שוב.

529
00:43:40,340 --> 00:43:51,080
ויש לנו 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
אז זה מקרה הבסיס שלנו.

531
00:43:53,170 --> 00:44:00,540
ברגע שהמערכים הם בגודל 1, אז אנחנו מפסיקים עם פיצול לחצי.

532
00:44:00,540 --> 00:44:03,190
>> עכשיו מה עושים עם זה?

533
00:44:03,190 --> 00:44:15,730
אנחנו בסופו של זה יהיה גם להתפרק 8, 23, 42, ו 108.

534
00:44:15,730 --> 00:44:24,000
אז עכשיו שאנחנו בשלב זה, עכשיו לשלב 2 מסוג המיזוג היא פשוט מתמזגים זוגות לרשימות.

535
00:44:24,000 --> 00:44:27,610
אז אנחנו רוצים למזג אלה. אנחנו רק קוראים מיזוג.

536
00:44:27,610 --> 00:44:31,410
אנחנו יודעים מיזוג יחזור אלה כדי למיין.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
עכשיו אנחנו רוצים למזג אלה, ושיחזירו רשימה עם אלה כדי למיין,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
אנו משלבים אלה - אני לא יכול לכתוב - 8, 23 ו 42, 108.

541
00:44:57,380 --> 00:45:02,890
אז יש לנו זוגות ממוזגים פעם אחת.

542
00:45:02,890 --> 00:45:05,140
עכשיו אנחנו רק למזג שוב.

543
00:45:05,140 --> 00:45:10,130
שימו לב שכל אחת מהרשימות אלה מסודרים בעצמו,

544
00:45:10,130 --> 00:45:15,220
ואז אנחנו יכולים רק למזג רשימות אלו כדי לקבל רשימה של גודל 4 אשר מסודרת

545
00:45:15,220 --> 00:45:19,990
ולמזג שתי רשימות אלו כדי לקבל רשימה של גודל 4 שממוינות.

546
00:45:19,990 --> 00:45:25,710
ולבסוף, אנו יכולים למזג שתי רשימות אלה בגודל 4 כדי לקבל רשימה של גודל 8 אחד שהיא מסודר.

547
00:45:25,710 --> 00:45:34,030
אז כדי לראות שזה הוא כללי n log n, אנחנו כבר ראינו שמיזוג הוא ליניארי,

548
00:45:34,030 --> 00:45:40,390
ולכן כאשר יש לנו עסק עם המיזוג אלה, דומים כל כך את העלות הכוללת של מיזוג

549
00:45:40,390 --> 00:45:43,410
לשתי רשימות אלה הם רק 2 כי -

550
00:45:43,410 --> 00:45:49,610
או טוב, זה O של n, אבל n כאן הוא רק 2 האלמנטים הללו, כך שזה 2.

551
00:45:49,610 --> 00:45:52,850
ו 2 אלה יהיו 2 ו 2 אלה יהיו 2 ו 2 אלה יהיו 2,

552
00:45:52,850 --> 00:45:58,820
כך על פני כל המיזוגים שאנחנו צריכים לעשות, אנחנו בסופו של הדבר עושים n.

553
00:45:58,820 --> 00:46:03,210
כמו 2 + 2 + 2 + 2 הם 8, שהוא n,

554
00:46:03,210 --> 00:46:08,060
לכן העלות של מיזוג בקבוצה זו היא n.

555
00:46:08,060 --> 00:46:10,810
ואז אותו הדבר כאן.

556
00:46:10,810 --> 00:46:16,980
אנחנו למזג 2 האלה, אז אלה 2, ובנפרד מיזוג זה ייקח ארבע פעולות,

557
00:46:16,980 --> 00:46:23,610
מיזוג זה ייקח ארבע פעולות, אבל שוב, בין כל אלה,

558
00:46:23,610 --> 00:46:29,030
אנחנו בסופו מתמזגים n דברים כלל, ולכן צעד זה לוקח n.

559
00:46:29,030 --> 00:46:33,670
וכך כל רמה לוקחת אלמנטים n שהתמזגו.

560
00:46:33,670 --> 00:46:36,110
>> וכמה רמות יש?

561
00:46:36,110 --> 00:46:40,160
בכל רמה, המערך שלנו גדל בגודל 2.

562
00:46:40,160 --> 00:46:44,590
הנה המערכים שלנו הם בגודל 1, כאן הם בגודל 2, כאן הם בגודל 4,

563
00:46:44,590 --> 00:46:46,470
ולבסוף, הם בגודל 8.

564
00:46:46,470 --> 00:46:56,450
אז מכיוון שהוא הכפלה, יש הולך להיות כולל של יומן n של רמות אלו.

565
00:46:56,450 --> 00:47:02,090
אז עם היומן n רמות, כל רמת פרט לוקח n פעולות כלל,

566
00:47:02,090 --> 00:47:05,720
אנחנו מקבלים יומן n אלגוריתם n.

567
00:47:05,720 --> 00:47:07,790
שאלות?

568
00:47:08,940 --> 00:47:13,320
יש אנשים שכבר עשו התקדמות על איך ליישם את זה?

569
00:47:13,320 --> 00:47:18,260
האם מישהו כבר במצב שבו אני פשוט לא יכול למשוך את הקוד שלהם?

570
00:47:20,320 --> 00:47:22,260
אני יכול לתת לי דקה.

571
00:47:24,770 --> 00:47:27,470
זה הולך להיות ארוך יותר.

572
00:47:27,470 --> 00:47:28,730
אני מאוד ממליץ ישנתי -

573
00:47:28,730 --> 00:47:30,510
אתה לא צריך לעשות רקורסיה למיזוג

574
00:47:30,510 --> 00:47:33,750
כי לעשות רקורסיה למיזוג, אתה הולך צריך לעבור חבורה של גדלים שונים.

575
00:47:33,750 --> 00:47:37,150
אתה יכול, אבל זה מעצבן.

576
00:47:37,150 --> 00:47:43,720
אבל רקורסיה למיון עצמו היא די קלה.

577
00:47:43,720 --> 00:47:49,190
אתה פשוט קורא ממש סוג של מחצית שמאל, סוג של מחצית ימין. אוקיי.

578
00:47:51,770 --> 00:47:54,860
למישהו יש משהו שאני יכול למשוך את עדיין?

579
00:47:54,860 --> 00:47:57,540
או שאני אתן לי דקה.

580
00:47:58,210 --> 00:47:59,900
אוקיי.

581
00:47:59,900 --> 00:48:02,970
למישהו יש משהו שאנחנו יכולים לעבוד איתו?

582
00:48:05,450 --> 00:48:09,680
או שאנחנו פשוט לעבוד עם זה ולאחר מכן להרחיב משם.

583
00:48:09,680 --> 00:48:14,050
>> למישהו יש יותר מזה שאני יכול להעלות?

584
00:48:14,050 --> 00:48:17,770
[תלמיד] כן. אתה יכול למשוך אותי. >> בסדר.

585
00:48:17,770 --> 00:48:19,730
כן!

586
00:48:22,170 --> 00:48:25,280
[תלמיד] היו הרבה תנאים. >> אה, לירות. האם אתם יכולים -

587
00:48:25,280 --> 00:48:28,110
[תלמיד] אני צריך לשמור אותו. >> כן.

588
00:48:32,420 --> 00:48:35,730
אז עשית את המיזוג בנפרד.

589
00:48:35,730 --> 00:48:38,570
אה, אבל זה לא כל כך רע.

590
00:48:39,790 --> 00:48:41,650
אוקיי.

591
00:48:41,650 --> 00:48:47,080
אז מיון הוא עצם רק להתקשר mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
תסביר לנו מה עושה mergeSortHelp.

593
00:48:49,530 --> 00:48:55,700
[תלמיד] MergeSortHelp די הרבה האם שני השלבים העיקריים,

594
00:48:55,700 --> 00:49:01,270
אשר הוא למיין כל מחצית של המערך ולאחר מכן למזג את שניהם.

595
00:49:04,960 --> 00:49:08,050
[אודן] אוקיי, אז תן לי שני.

596
00:49:10,850 --> 00:49:13,210
אני חושב שזה - >> [תלמיד] אני צריך -

597
00:49:17,100 --> 00:49:19,400
כן. חסר לי משהו.

598
00:49:19,400 --> 00:49:23,100
במיזוג, אני מבין שאני צריך ליצור מערך חדש

599
00:49:23,100 --> 00:49:26,530
כי אני לא יכול לעשות אותו במקום. >> כן. אתה לא יכול. לתקן.

600
00:49:26,530 --> 00:49:28,170
[תלמיד] אז אני יוצר מערך חדש.

601
00:49:28,170 --> 00:49:31,510
שכחתי בסוף יתמזגו מחדש לשנות.

602
00:49:31,510 --> 00:49:34,490
אוקיי. אנו זקוקים למערך חדש.

603
00:49:34,490 --> 00:49:41,000
במיון מיזוג, זה כמעט תמיד נכון.

604
00:49:41,000 --> 00:49:44,340
חלק מהעלות של אלגוריתם טוב יותר זמן מבחינת

605
00:49:44,340 --> 00:49:47,310
כמעט תמיד הוא את הצורך להשתמש בקצת יותר זיכרון.

606
00:49:47,310 --> 00:49:51,570
אז הנה, לא משנה כמה אתה עושה למזג מיון,

607
00:49:51,570 --> 00:49:54,780
היית בהכרח צריכים להשתמש בכמה זיכרון נוסף.

608
00:49:54,780 --> 00:49:58,240
הוא או היא יצר מערך חדש.

609
00:49:58,240 --> 00:50:03,400
ואז אתה אומר בסוף, אנחנו פשוט צריכים להעתיק מערך חדש למערך המקורי.

610
00:50:03,400 --> 00:50:04,830
[תלמיד] אני חושב שכן, כן.

611
00:50:04,830 --> 00:50:08,210
אני לא יודע אם זה עובד במונחים של ספירה בהתייחסות או מה -

612
00:50:08,210 --> 00:50:11,650
כן, זה יעבוד. >> [תלמיד] אוקיי.

613
00:50:20,620 --> 00:50:24,480
האם אתה מנסה לרוץ בזה? >> [תלמיד] לא, עדיין לא. >> אוקיי.

614
00:50:24,480 --> 00:50:28,880
נסה להריץ אותו, ולאחר מכן אני אדבר על זה לרגע.

615
00:50:28,880 --> 00:50:35,200
[תלמיד] אני אף צריך לקבל את כל אבות הטיפוס לפונקציות והכילו,, נכון?

616
00:50:37,640 --> 00:50:40,840
אבות הטיפוס של הפונקציות. אה, אתה מתכוון כמו - כן.

617
00:50:40,840 --> 00:50:43,040
מיין קורא mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> אז כדי לקרוא לסוג mergeSortHelp, mergeSortHelp עליך הוגדר

619
00:50:47,390 --> 00:50:56,370
לפני המיון או שאנחנו פשוט צריכים אב טיפוס. פשוט להעתיק ולהדביק את זה.

620
00:50:56,370 --> 00:50:59,490
ובאופן דומה, mergeSortHelp קורא מיזוג,

621
00:50:59,490 --> 00:51:03,830
אבל המיזוג לא הוגדר עדיין, ולכן אנחנו יכולים פשוט לתת mergeSortHelp יודע

622
00:51:03,830 --> 00:51:08,700
שזה מה שהוא הולך להתמזג ייראה, וזהו זה.

623
00:51:09,950 --> 00:51:15,730
אז mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
יש לנו בעיה כאן איפה שאין לנו מקרה בסיס.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp הוא רקורסיבי, ולכן כל פונקציה רקורסיבית

626
00:51:38,110 --> 00:51:42,610
הולך צריך איזה מקרה בסיס לדעת מתי להפסיק באופן רקורסיבי קורא את עצמו.

627
00:51:42,610 --> 00:51:45,590
מה מקרה הבסיס שלנו הולך להיות כאן? כן.

628
00:51:45,590 --> 00:51:49,110
[תלמיד] אם הגודל הוא 1? >> [אודן] כן.

629
00:51:49,110 --> 00:51:56,220
אז כמו שראינו שם, עצרו מערכי פיצול

630
00:51:56,220 --> 00:52:01,850
ברגע שנכנסנו למערכים בגודל 1, אשר בהכרח ממוינים עצמם.

631
00:52:01,850 --> 00:52:09,530
אז אם גודל שווה 1, אנחנו יודעים שהמערך כבר ממוין

632
00:52:09,530 --> 00:52:12,970
אז אנחנו פשוט יכולים לחזור.

633
00:52:12,970 --> 00:52:16,880
>> שים לב שזה מבוטל, ולכן אנחנו לא נחזור בשום דבר מיוחד, פשוט לחזור.

634
00:52:16,880 --> 00:52:19,580
אוקיי. אז זה מקרה הבסיס שלנו.

635
00:52:19,580 --> 00:52:27,440
אני מניח שמקרה הבסיס שלנו יכול להיות גם אם יקרו לך להיות מיזוג מערך בגודל 0,

636
00:52:27,440 --> 00:52:30,030
אנחנו כנראה רוצים לעצור בנקודה מסוימת,

637
00:52:30,030 --> 00:52:33,610
אז אנחנו יכולים רק להגיד גודל פחות מ 2 או קטן או שווה ל 1

638
00:52:33,610 --> 00:52:37,150
כדי שזה יעבוד עבור כל מערך עכשיו.

639
00:52:37,150 --> 00:52:38,870
אוקיי.

640
00:52:38,870 --> 00:52:42,740
אז זה מקרה הבסיס שלנו.

641
00:52:42,740 --> 00:52:45,950
עכשיו אתה רוצה ללכת אלינו באמצעות מיזוג?

642
00:52:45,950 --> 00:52:49,140
מה כל המקרים האלה מתכוונים?

643
00:52:49,140 --> 00:52:54,480
עד כאן, אנחנו רק עושים אותו הרעיון, -

644
00:52:56,970 --> 00:53:02,470
[תלמיד] אני צריך להיות גודל עובר עם כל שיחות mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
הוספתי גודל כמו עיקרי נוספת וזה לא שם, כמו גודל / 2.

646
00:53:10,080 --> 00:53:16,210
[אודן] הו, גודל / 2, גודל / 2. >> [תלמיד] כן, וגם בפונקציה הנ"ל גם כן.

647
00:53:16,210 --> 00:53:21,320
[אודן] כאן? >> [תלמיד] רק גודל. >> [אודן] הו. גודל, גודל? >> [תלמיד] כן.

648
00:53:21,320 --> 00:53:23,010
[אודן] אוקיי.

649
00:53:23,010 --> 00:53:26,580
תן לי לחשוב לרגע.

650
00:53:26,580 --> 00:53:28,780
האם אנו נתקלנו בבעיה?

651
00:53:28,780 --> 00:53:33,690
אנחנו תמיד מתייחסים אל השמאל כמו 0. >> [תלמיד] מס

652
00:53:33,690 --> 00:53:36,340
זה לא נכון גם. סליחה. זה צריך להיות התחלה. כן.

653
00:53:36,340 --> 00:53:39,230
[אודן] אוקיי. אני אוהב את זה יותר טוב.

654
00:53:39,230 --> 00:53:43,880
וסופו של דבר. אוקיי.

655
00:53:43,880 --> 00:53:47,200
אז עכשיו אתה רוצה שתראה לנו את המיזוג? >> [תלמיד] אוקיי.

656
00:53:47,200 --> 00:53:52,150
אני רק הולך במערך החדש שיצרתי.

657
00:53:52,150 --> 00:53:57,420
הגודל שלו הוא בגודל של החלק מהמערך שאנחנו רוצים להיות מסודרים

658
00:53:57,420 --> 00:54:03,460
ומנסה למצוא את האלמנט שאני צריך לשים בשלב המערך החדש.

659
00:54:03,460 --> 00:54:10,140
אז כדי לעשות את זה, קודם אני בודק אם את חלקו השמאלי של המערך ממשיך יש לך עוד אלמנטים,

660
00:54:10,140 --> 00:54:14,260
ואם לא, אז אתה יורד למצב שאחר, שפשוט אומר

661
00:54:14,260 --> 00:54:20,180
בסדר, זה חייב להיות במערך הנכון, ואנחנו נשים את זה במדד הנוכחי של newArray.

662
00:54:20,180 --> 00:54:27,620
>> ואז אחרת, אני בודק אם בצד ימין של המערך הוא גם סיים,

663
00:54:27,620 --> 00:54:30,630
במקרה כזה אני פשוט לשים בצד השמאל.

664
00:54:30,630 --> 00:54:34,180
שאולי הוא לא הכרחי. אני לא בטוח.

665
00:54:34,180 --> 00:54:40,970
אבל בכל מקרה, שני סימון האחר שמשתיים קטנים בצד השמאל או הימין.

666
00:54:40,970 --> 00:54:49,770
וגם בכל מקרה, אני הגדלה לפי מציין מיקום אני לעלות.

667
00:54:49,770 --> 00:54:52,040
[אודן] אוקיי.

668
00:54:52,040 --> 00:54:53,840
זה נראה טוב.

669
00:54:53,840 --> 00:54:58,800
האם יש למישהו הערות או חששות או שאלות?

670
00:55:00,660 --> 00:55:07,720
אז בארבעת המקרים שיש לנו להביא את דברים לפשוט להיות - או שזה נראה כמו חמש -

671
00:55:07,720 --> 00:55:13,100
אבל יש לנו לשקול אם מערך השמאל נגמר של דברים שאנחנו צריכים למזג,

672
00:55:13,100 --> 00:55:16,390
אם מערך ימין נגמר של דברים שאנחנו צריכים למזג -

673
00:55:16,390 --> 00:55:18,400
אני מצביע על כלום.

674
00:55:18,400 --> 00:55:21,730
אז אם מערך השמאל נגמר של דברים או מערך ימין נגמר של דברים.

675
00:55:21,730 --> 00:55:24,320
אלה שני מקרים.

676
00:55:24,320 --> 00:55:30,920
אנחנו גם צריכים מקרה טריוויאלי של הדבר אם השמאל הוא פחות מהדבר הנכון.

677
00:55:30,920 --> 00:55:33,910
אז אנחנו רוצים לבחור את דבר השמאל.

678
00:55:33,910 --> 00:55:37,630
אלה התיקים.

679
00:55:37,630 --> 00:55:40,990
אז זה היה נכון, אז זהו זה.

680
00:55:40,990 --> 00:55:46,760
מערך עזב. זה 1, 2, 3. אוקיי. אז כן, אלו הם הארבעה הדברים שייתכן שירצו לעשות.

681
00:55:50,350 --> 00:55:54,510
ואנחנו לא הולכים על פתרון איטרטיבי.

682
00:55:54,510 --> 00:55:55,980
לא הייתי ממליץ -

683
00:55:55,980 --> 00:56:03,070
סוג המיזוג הוא דוגמה לפונקציה שהוא גם לא זנב רקורסיבית,

684
00:56:03,070 --> 00:56:07,040
זה לא קל לעשות את זה זנב רקורסיבית,

685
00:56:07,040 --> 00:56:13,450
אבל גם זה לא כל כך קל לעשות את זה איטרטיבי.

686
00:56:13,450 --> 00:56:16,910
זה קל מאוד.

687
00:56:16,910 --> 00:56:19,170
יישום זה מסוג המיזוג,

688
00:56:19,170 --> 00:56:22,140
מיזוג, לא משנים מה אתה עושה, אתה הולך לבנות מיזוג.

689
00:56:22,140 --> 00:56:29,170
>> אז למזג מיון נבנה על גבי מיזוג רקורסיבי הוא רק שלוש שורות אלה.

690
00:56:29,170 --> 00:56:34,700
ערוך את, זה יותר מעצבן וקשה יותר לחשוב עליו.

691
00:56:34,700 --> 00:56:41,860
אבל שם לב שזה לא זנב רקורסיבית מאז mergeSortHelp - כאשר היא ממכנת את עוצמה -

692
00:56:41,860 --> 00:56:46,590
זה עדיין צריך לעשות את הדברים לאחר שיחה חוזרת רקורסיבית זה.

693
00:56:46,590 --> 00:56:50,830
אז ערימת מסגרת זו חייבת להמשיך להתקיים גם אחרי שקרא את זה.

694
00:56:50,830 --> 00:56:54,170
ואז כשאתה קורא את זה, את מסגרת המחסנית להמשיך להתקיים

695
00:56:54,170 --> 00:56:57,780
כי גם אחרי שהשיחה, אנחנו עדיין צריכים מיזוג.

696
00:56:57,780 --> 00:57:01,920
וזה משימה קל להפוך את הזנב זה רקורסיבית.

697
00:57:04,070 --> 00:57:06,270
שאלות?

698
00:57:08,300 --> 00:57:09,860
בסדר.

699
00:57:09,860 --> 00:57:13,400
אז חוזר למיון - הו, יש שני דברים שאני רוצה להראות. אוקיי.

700
00:57:13,400 --> 00:57:17,840
חוזרים למיון, אנחנו נעשה את זה במהירות.

701
00:57:17,840 --> 00:57:21,030
או חיפוש. מיין? מיון. כן.

702
00:57:21,030 --> 00:57:22,730
אם אחזור לתחילתו של מיון.

703
00:57:22,730 --> 00:57:29,870
אנחנו רוצים ליצור אלגוריתם שממיין את המערך באמצעות כל אלגוריתם

704
00:57:29,870 --> 00:57:33,660
ב O של n.

705
00:57:33,660 --> 00:57:40,860
אז איך זה אפשרי? האם יש למישהו כל סוג של -

706
00:57:40,860 --> 00:57:44,300
שרמזתי קודם ב--

707
00:57:44,300 --> 00:57:48,300
אם אנחנו עומדים לשפר מn log n לO של n,

708
00:57:48,300 --> 00:57:51,450
יש לנו שיפור האלגוריתם שלנו זמן, החכם,

709
00:57:51,450 --> 00:57:55,250
מה שאומר שאנחנו הולכים צריכים לעשות כדי לכפר על זה?

710
00:57:55,250 --> 00:57:59,520
[תלמיד] חלל. >> כן. אנחנו הולכים להיות באמצעות יותר מקום.

711
00:57:59,520 --> 00:58:04,490
ואפילו לא רק יותר מקום, זה מקום אקספוננציאלית יותר.

712
00:58:04,490 --> 00:58:14,320
אז אני חושב שזה סוג של אלגוריתם הוא משהו מדומה, polynom פסאודו -

713
00:58:14,320 --> 00:58:18,980
פסאודו - אני לא זוכר. משהו מדומה.

714
00:58:18,980 --> 00:58:22,210
אבל זה בגלל שאנחנו צריכים להשתמש בכל כך הרבה מקום

715
00:58:22,210 --> 00:58:28,610
שזה הוא בר השגה, אך לא מציאותי.

716
00:58:28,610 --> 00:58:31,220
>> ואיך אנחנו משיגים את זה?

717
00:58:31,220 --> 00:58:36,810
אנחנו יכולים להשיג את זה, אם אנו מבטיחים שכל אלמנט מסוים במערך

718
00:58:36,810 --> 00:58:39,600
הוא מתחת לגודל מסוים.

719
00:58:42,070 --> 00:58:44,500
אז בואו רק נאמר שגודל הוא 200,

720
00:58:44,500 --> 00:58:48,130
כל אלמנט במערך הוא מתחת הגודל 200.

721
00:58:48,130 --> 00:58:51,080
וזה דווקא מאוד מציאותי.

722
00:58:51,080 --> 00:58:58,660
אתה יכול בקלות יש מערך שאתה יודע הכל בזה

723
00:58:58,660 --> 00:59:00,570
הולך להיות נמוך ממספר מסוים.

724
00:59:00,570 --> 00:59:07,400
כמו שאם יש לך קצת וקטור או משהו ענקי ממש

725
00:59:07,400 --> 00:59:11,810
אבל אתה יודע מה הולך להיות בין 0 ל 5,

726
00:59:11,810 --> 00:59:14,790
אז זה הולך להיות משמעותי יותר מהר לעשות את זה.

727
00:59:14,790 --> 00:59:17,930
והכרוך בכל אחד מהמרכיבים הם 5,

728
00:59:17,930 --> 00:59:21,980
אז זה כרוך, כלומר כמה זיכרון אתה הולך להיות משתמש.

729
00:59:21,980 --> 00:59:26,300
אז הכבול הוא 200.

730
00:59:26,300 --> 00:59:32,960
בתאוריה יש תמיד כרוך מאז מספר שלם יכול להיות עד ל -4 מיליארדים בלבד,

731
00:59:32,960 --> 00:59:40,600
אבל זה לא מציאותי שכן אז הייתי שימוש בשטח

732
00:59:40,600 --> 00:59:44,400
על הסדר של 4 מיליארדים. אז זה לא מציאותי.

733
00:59:44,400 --> 00:59:47,060
אבל הנה אנחנו נגיד כרוכים הוא 200.

734
00:59:47,060 --> 00:59:59,570
הטריק כדי לעשות את זה ב O של n הוא שאנחנו עושים מערך אחר שנקרא סעיפים של גודל מחויבים.

735
00:59:59,570 --> 01:00:10,470
כך שלמעשה, זה קיצור ל-- אני באמת לא יודע אם קלאנג עושה זאת.

736
01:00:11,150 --> 01:00:15,330
אבל בGCC לכל הפחות - קלאנג בהנחה אני עושה את זה יותר מדי -

737
01:00:15,330 --> 01:00:18,180
זה יהיה פשוט לאתחל את כל המערך להיות 0s.

738
01:00:18,180 --> 01:00:25,320
אז אם אני לא רוצה לעשות את זה, אז אני יכול לעשות בנפרד עבור (אני int = 0;

739
01:00:25,320 --> 01:00:31,500
i <Bound; i + +) וספירה [i] = 0;

740
01:00:31,500 --> 01:00:35,260
אז עכשיו הכל מאותחל ל 0.

741
01:00:35,260 --> 01:00:39,570
אני לחזר על המערך שלי,

742
01:00:39,570 --> 01:00:51,920
ומה שאני עושה הוא שאני סופר את כל - בוא ארד כאן.

743
01:00:51,920 --> 01:00:55,480
יש לנו 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
מה אני סומך הוא מספר מופעים של כל אחד מהאלמנטים האלה.

745
01:01:00,010 --> 01:01:03,470
בואו בעצם להוסיף עוד כמה לכאן עם כמה חזרות.

746
01:01:03,470 --> 01:01:11,070
אז יש לנו כאן הערך, הערך שהוא הולך להיות מערך [i].

747
01:01:11,070 --> 01:01:14,850
אז val יכול להיות 4 או 8 או לא משנה מה.

748
01:01:14,850 --> 01:01:18,870
ועכשיו אני סופר כמה שערך שאני ראיתי,

749
01:01:18,870 --> 01:01:21,230
כך ספירה [val] + +;

750
01:01:21,230 --> 01:01:29,430
אחרי שזה נעשה, ספירה עומדת להיראות משהו כמו 0001.

751
01:01:29,430 --> 01:01:42,190
בואו נעשה ספירה [val] - מחויב + 1.

752
01:01:42,190 --> 01:01:48,230
>> עכשיו זה רק כדי להסביר את העובדה שאנחנו מתחילים מ 0.

753
01:01:48,230 --> 01:01:50,850
אז אם 200 הולכים להיות המספר הגדול ביותר שלנו,

754
01:01:50,850 --> 01:01:54,720
אז 0-200 הם 201 דברים.

755
01:01:54,720 --> 01:02:01,540
אז ספירה, זה ייראה כמו 00001 כי יש לנו אחד 4.

756
01:02:01,540 --> 01:02:10,210
אז יהיה לנו 0001 בו תהיה לנו 1 במדד ה -8 של ספירה.

757
01:02:10,210 --> 01:02:14,560
תהיה לנו 2 במדד ה -23 של ספירה.

758
01:02:14,560 --> 01:02:17,630
תהיה לנו 2 במדד 42 של ספירה.

759
01:02:17,630 --> 01:02:21,670
אז אנחנו יכולים להשתמש בספירה.

760
01:02:34,270 --> 01:02:44,920
אז num_of_item = ספירה [i].

761
01:02:44,920 --> 01:02:52,540
ולכן אם num_of_item הוא 2, זה אומר שאנחנו רוצים להכניס 2 לספרה

762
01:02:52,540 --> 01:02:55,290
למערך המיון שלנו.

763
01:02:55,290 --> 01:03:02,000
אז אנחנו צריכים לעקוב אחר כמה רחוקים אנחנו לתוך המערך.

764
01:03:02,000 --> 01:03:05,470
אז = מדד 0.

765
01:03:05,470 --> 01:03:09,910
מערך - אני פשוט אכתוב אותו.

766
01:03:16,660 --> 01:03:18,020
ספירות -

767
01:03:19,990 --> 01:03:28,580
מערך [ראשים + +] = i;

768
01:03:28,580 --> 01:03:32,490
האם זה מה שאני רוצה? אני חושב שזה מה שאני רוצה.

769
01:03:35,100 --> 01:03:38,290
כן, זה נראה טוב. אוקיי.

770
01:03:38,290 --> 01:03:43,050
אז לכולם להבין מה המטרה של מערך הספירות שלי היא?

771
01:03:43,050 --> 01:03:48,140
הוא סופר את מספר מופעים של כל אחד מהמספרים האלה.

772
01:03:48,140 --> 01:03:51,780
אז אני iterating על מערך ספירות ש,

773
01:03:51,780 --> 01:03:57,190
ועמדת ה-i במערך הספירות

774
01:03:57,190 --> 01:04:01,930
הוא מספר שזה שאמור להופיע במערך המיון שלי.

775
01:04:01,930 --> 01:04:06,840
זו הסיבה שהסעיפים של 4 הולכים להיות 1

776
01:04:06,840 --> 01:04:11,840
והספירה של 8 הולכת להיות 1, סעיפים של 23 הולכים להיות 2.

777
01:04:11,840 --> 01:04:16,900
אז ככה רבים מהם אני רוצה להכניס לתוך המערך הממוין שלי.

778
01:04:16,900 --> 01:04:19,200
אז אני פשוט עושה את זה.

779
01:04:19,200 --> 01:04:28,960
אני מכניס num_of_item אני זה למערך המיון שלי.

780
01:04:28,960 --> 01:04:31,670
>> שאלות?

781
01:04:32,460 --> 01:04:43,100
וכך שוב, זה זמן ליניארי מאז אנחנו רק iterating על זה פעם אחת,

782
01:04:43,100 --> 01:04:47,470
אבל זה גם מה יניארי במספר זה קורה להיות,

783
01:04:47,470 --> 01:04:50,730
ואז זה תלוי במידה רבה על מה שהכרוך הוא.

784
01:04:50,730 --> 01:04:53,290
עם כפות של 200, זה לא כל כך נורא.

785
01:04:53,290 --> 01:04:58,330
אם הכבול שלך הולך להיות 10000, אז זה קצת יותר גרוע,

786
01:04:58,330 --> 01:05:01,360
אבל אם הכריכה שלך הולכת להיות 4 מליארד דולרים, זה לגמרי לא מציאותי

787
01:05:01,360 --> 01:05:07,720
ומערך זה הולך להיות בגודל 4 מליארד דולרים, שאינו מציאותי.

788
01:05:07,720 --> 01:05:10,860
אז זהו זה. שאלות?

789
01:05:10,860 --> 01:05:13,270
[תגובת תלמיד לא נשמעה] >> אוקיי.

790
01:05:13,270 --> 01:05:15,710
הבנתי דבר אחד כאשר היינו עובר.

791
01:05:17,980 --> 01:05:23,720
אני חושב שהבעיה הייתה בלוקאס וכנראה כל אחד ואחד שראינו.

792
01:05:23,720 --> 01:05:26,330
שכחתי לגמרי.

793
01:05:26,330 --> 01:05:31,040
הדבר היחיד שאני רוצה להגיב על זה שכאשר אתה מתעסק עם דברים כמו מדדים,

794
01:05:31,040 --> 01:05:38,320
אתה לא באמת רואה את זה כשאתה כותב ללולאה,

795
01:05:38,320 --> 01:05:41,120
אבל מבחינה טכנית, בכל פעם שאתה מתעסק עם מדדים אלה,

796
01:05:41,120 --> 01:05:45,950
אתה צריך פחות או יותר תמיד להתמודד עם מספרים שלמים שאינם חתומים.

797
01:05:45,950 --> 01:05:53,850
הסיבה לכך היא כאשר אתה מתעסק עם מספרים שלמים שנחתמו,

798
01:05:53,850 --> 01:05:56,090
כך שאם יש לך 2 מספרים שלמים שנחתמו ואתה מוסיף אותם יחד

799
01:05:56,090 --> 01:06:00,640
והם בסופו גדול מדי, אז אתה בסופו של דבר עם מספר שלילי.

800
01:06:00,640 --> 01:06:03,410
אז זה מה שהצפה היא מספר שלמה.

801
01:06:03,410 --> 01:06:10,500
>> אם אני מוסיף 2 מיליארדים 1 מליארד, שאתקע עם 1000000000 שליליים.

802
01:06:10,500 --> 01:06:15,480
ככה מספרים שלמים לעבוד במחשבים.

803
01:06:15,480 --> 01:06:17,510
אז הבעיה בשימוש -

804
01:06:17,510 --> 01:06:23,500
זה בסדר אלא אם נמוך קורה להיות 2 מיליארדים ועד קורה להיות 1 מיליארדים,

805
01:06:23,500 --> 01:06:27,120
אז זה הולך להיות שלילי 1 מיליארדים ואז אנחנו הולכים לחלק את זה על ידי 2

806
01:06:27,120 --> 01:06:29,730
וסופו של דבר עם 500,000,000 שליליים.

807
01:06:29,730 --> 01:06:33,760
אז זה רק בעיה אם קורים לך להיות מחפש דרך מערך

808
01:06:33,760 --> 01:06:38,070
של מליארד דברים.

809
01:06:38,070 --> 01:06:44,050
אבל אם + נמוך עד שקורה להצפה, אז זה בעיה.

810
01:06:44,050 --> 01:06:47,750
ברגע שאנחנו עושים אותם לא חתומים, אז 2000000000 פלוס 1 מליארד ש"ח הנם 3 מליארד דולרים.

811
01:06:47,750 --> 01:06:51,960
3000000000 חלקים 2 הם 1.5 מליארד דולרים.

812
01:06:51,960 --> 01:06:55,670
אז ברגע שהם לא חתומים, הכל מושלם.

813
01:06:55,670 --> 01:06:59,900
ואז זה גם בעיה כשאתה כותב ללולאות,

814
01:06:59,900 --> 01:07:03,940
ובעצם, זה כנראה עושה את זה באופן אוטומטי.

815
01:07:09,130 --> 01:07:12,330
זה באמת פשוט לצעוק עליך.

816
01:07:12,330 --> 01:07:21,610
אז אם מספר זה הוא גדול מדי כדי להיות בפשוט שלם אבל זה יתאים בשלם חתום,

817
01:07:21,610 --> 01:07:24,970
הוא צעק עליך, כך שזו הסיבה שאף פעם לא באמת נתקלה בבעיה.

818
01:07:29,150 --> 01:07:34,820
ניתן לראות שמדד לא הולך להיות שלילי,

819
01:07:34,820 --> 01:07:39,220
ואז כשאתם iterating על מערך,

820
01:07:39,220 --> 01:07:43,970
אתה כמעט תמיד יכול להגיד int חתום אני, אבל אתה לא באמת צריך.

821
01:07:43,970 --> 01:07:47,110
דברים הולכים לעבוד די הרבה באותה מידה.

822
01:07:48,740 --> 01:07:50,090
אוקיי. [לוחש] מה השעה?

823
01:07:50,090 --> 01:07:54,020
הדבר האחרון שרציתי להראות - ואני פשוט אעשה את זה ממש מהר.

824
01:07:54,020 --> 01:08:03,190
אתה יודע כמה יש לנו ולכן אנחנו מגדירים # # יכולים להגדיר כמקס 5 או משהו?

825
01:08:03,190 --> 01:08:05,940
בואו לא נעשה את המקסימום. # Define הכפות 200. זה מה שעשינו בעבר.

826
01:08:05,940 --> 01:08:10,380
שמגדיר מתמיד, שרק הולך להעתיק ולהדביק

827
01:08:10,380 --> 01:08:13,010
כל מקום שאנחנו קורים לכתוב מאוגדים.

828
01:08:13,010 --> 01:08:18,189
>> אז אנחנו באמת יכולים לעשות יותר עם # מגדיר.

829
01:08:18,189 --> 01:08:21,170
אנו יכולים להגדיר פונקציות #.

830
01:08:21,170 --> 01:08:23,410
הם לא באמת פונקציות, אבל אנחנו קוראים להם פונקציות.

831
01:08:23,410 --> 01:08:36,000
דוגמה תהיה משהו כמו מקס (x, y) מוגדר (x <y y:? X). אוקיי.

832
01:08:36,000 --> 01:08:40,660
אז אתה צריך להתרגל לתחביר מפעיל משולש,

833
01:08:40,660 --> 01:08:49,029
אך הוא פחות מ x y? תשואת y, אחר לחזור x.

834
01:08:49,029 --> 01:08:54,390
אז אתה יכול לראות שאתה יכול לעשות זה פונקציה נפרדת,

835
01:08:54,390 --> 01:09:01,399
והפונקציה יכולה להיות כמו bool מקס לוקח 2 טענות, להחזיר את זה.

836
01:09:01,399 --> 01:09:08,340
זה אחד מאלה הנפוצים ביותר שאני רואה שנעשו כזה. אנו קוראים להם פקודות מאקרו.

837
01:09:08,340 --> 01:09:11,790
זה מאקרו.

838
01:09:11,790 --> 01:09:15,859
זה רק תחביר לזה.

839
01:09:15,859 --> 01:09:18,740
אתה יכול לכתוב מאקרו לעשות מה שאתה רוצה.

840
01:09:18,740 --> 01:09:22,649
לעתים קרובות אתה רואה פקודות מאקרו לאיתור באגים printfs וכאלה.

841
01:09:22,649 --> 01:09:29,410
אז סוג של printf, יש קבועים מיוחדים בC כמו מדגישים את הקו תחתון,

842
01:09:29,410 --> 01:09:31,710
2 מדגישים קו תחתון,

843
01:09:31,710 --> 01:09:37,550
ויש גם אני חושב 2 מדגיש FUNC. זה יכול להיות אותו. משהו כזה.

844
01:09:37,550 --> 01:09:40,880
אלה דברים יוחלפו עם השם של הפונקציה

845
01:09:40,880 --> 01:09:42,930
או מספר הקו שאתה נמצא.

846
01:09:42,930 --> 01:09:48,630
לעתים קרובות, אתה כותב printfs איתור הבאגים שכאן אני יכול אז פשוט לכתוב

847
01:09:48,630 --> 01:09:54,260
DEBUG וזה יהיה להדפיס את מספר הקו והפונקציה שאני במקרה ב

848
01:09:54,260 --> 01:09:57,020
שהיא נתקלה באמירת DEBUG.

849
01:09:57,020 --> 01:09:59,550
ואתה יכול גם להדפיס דברים אחרים.

850
01:09:59,550 --> 01:10:05,990
אז דבר אחד אתה צריך להיזהר הוא אם אני במקרה # להגדיר DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
משהו כמו 2 * 2 * y וx.

852
01:10:11,380 --> 01:10:14,310
אז מה סיבה, קורה לך לעשות את זה הרבה.

853
01:10:14,310 --> 01:10:16,650
אז לעשות את זה במאקרו.

854
01:10:16,650 --> 01:10:18,680
זה בעצם שבור.

855
01:10:18,680 --> 01:10:23,050
אני הייתי קורא לזה על ידי עושה משהו כמו DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
אז מה יש להחזיר?

857
01:10:28,840 --> 01:10:30,580
[תלמיד] 12.

858
01:10:30,580 --> 01:10:34,800
כן, יש להחזיר 12, ו 12 הוא חזר.

859
01:10:34,800 --> 01:10:43,350
3 מתחלפים עבור x, 6 מתחלפים עבור y, ואנחנו חוזרים 2 * 6, שהוא 12.

860
01:10:43,350 --> 01:10:47,710
עכשיו מה לגבי זה? מה יש להחזיר?

861
01:10:47,710 --> 01:10:50,330
[תלמיד] 14. >> באופן אידיאלי, 14.

862
01:10:50,330 --> 01:10:55,290
הבעיה היא שכמה חשיש מגדיר עבודה, זכור שזה העתק ודבק מילולי

863
01:10:55,290 --> 01:11:00,160
של כל דבר די הרבה, אז מה זה הולך להתפרש כ

864
01:11:00,160 --> 01:11:11,270
הוא 3 פחות מ 1 ועוד 6, 2 1 פעמים בתוספת 6, 2 3 פעמים.

865
01:11:11,270 --> 01:11:19,780
>> הנה, זו סיבה שכמעט תמיד לעטוף הכל בסוגריים.

866
01:11:22,180 --> 01:11:25,050
כל משתנה שכמעט תמיד לעטוף בסוגריים.

867
01:11:25,050 --> 01:11:29,570
יש מקרים שבו אתה לא צריך, כמו שאני יודע שאני לא צריך לעשות את זה כאן

868
01:11:29,570 --> 01:11:32,110
כי פחות מזה די הרבה זמן רק הולך לעבודה,

869
01:11:32,110 --> 01:11:34,330
למרות שאפילו לא יכול להיות אמיתי.

870
01:11:34,330 --> 01:11:41,870
אם יש משהו מגוחך כמו DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
אז זה הולך לקבל החליף עם 3 פחות מ 1 שווה שווה 2,

872
01:11:49,760 --> 01:11:53,460
וכן אז זה הולך לעשות 3 פחות מ 1, האם זה שווה 2,

873
01:11:53,460 --> 01:11:55,620
וזה לא מה שאנחנו רוצים.

874
01:11:55,620 --> 01:12:00,730
אז כדי למנוע בעיות קדימות מפעיל,

875
01:12:00,730 --> 01:12:02,870
תמיד לעטוף בסוגריים.

876
01:12:03,290 --> 01:12:07,700
אוקיי. וזהו, 5:30.

877
01:12:08,140 --> 01:12:12,470
אם יש לך שאלות כלשהן על pset, יידע אותנו.

878
01:12:12,470 --> 01:12:18,010
זה צריך להיות כיף, ומהדורת ההאקר גם היא הרבה יותר מציאותי

879
01:12:18,010 --> 01:12:22,980
ממהדורת ההאקר של השנה שעברה, אז אנחנו מקווים שהרבה מכם לנסות את זה.

880
01:12:22,980 --> 01:12:26,460
בשנה שעברה הייתה מאוד מכרעת.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]