1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] בטח שמע אנשים מדברים על אלגוריתם מהיר או יעיל

2
00:00:10,950 --> 00:00:13,090
לביצוע המשימה הספציפית שלך,

3
00:00:13,090 --> 00:00:16,110
אבל מה בדיוק זה אומר לגבי אלגוריתם כדי להיות מהיר או יעיל?

4
00:00:16,110 --> 00:00:18,580
טוב, זה לא מדבר על מדידה בזמן אמת,

5
00:00:18,580 --> 00:00:20,500
כמו שניות או דקות.

6
00:00:20,500 --> 00:00:22,220
הסיבה לכך היא חומרת מחשב

7
00:00:22,220 --> 00:00:24,260
ותוכנה להשתנות באופן דרסטי.

8
00:00:24,260 --> 00:00:26,020
התכנית שלי אולי איטית יותר משלך,

9
00:00:26,020 --> 00:00:28,000
משום שאני מפעיל אותו במחשב ישן יותר,

10
00:00:28,000 --> 00:00:30,110
או כי אני במקרה יהיה משחק משחק וידאו מקוון

11
00:00:30,110 --> 00:00:32,670
באותו הזמן, המשתלט כל הזיכרון שלי,

12
00:00:32,670 --> 00:00:35,400
או שאני יכול להיות מפעיל התכנית שלי דרך תוכנות שונות

13
00:00:35,400 --> 00:00:37,550
אשר מתקשר עם מכונה אחרת ברמה נמוכה.

14
00:00:37,550 --> 00:00:39,650
זה כמו להשוות תפוחים ותפוזים.

15
00:00:39,650 --> 00:00:41,940
רק בגלל שהמחשב שלי האיטי לוקח יותר זמן

16
00:00:41,940 --> 00:00:43,410
יותר משלך להחזיר תשובה

17
00:00:43,410 --> 00:00:45,510
זה לא אומר שיש לך אלגוריתם היעיל יותר.

18
00:00:45,510 --> 00:00:48,830
>> לכן, מאז אנחנו לא יכולים להשוות ישירות את runtimes של תוכניות

19
00:00:48,830 --> 00:00:50,140
בשניות או דקות,

20
00:00:50,140 --> 00:00:52,310
איך אנחנו להשוות 2 אלגוריתמים שונים

21
00:00:52,310 --> 00:00:55,030
ללא קשר לחומרה שלהם או סביבת תוכנה?

22
00:00:55,030 --> 00:00:58,000
כדי ליצור צורה אחידה יותר של מדידת יעילות אלגוריתמית,

23
00:00:58,000 --> 00:01:00,360
מדעני מחשב ומתמטיקאים פתחו

24
00:01:00,360 --> 00:01:03,830
מושגים למדידת המורכבות אסימפטוטי של תכנית

25
00:01:03,830 --> 00:01:06,110
וסימון בשם 'Ohnotation הגדול'

26
00:01:06,110 --> 00:01:08,320
לתיאור זה.

27
00:01:08,320 --> 00:01:10,820
ההגדרה הרשמית היא שפונקציה f (x)

28
00:01:10,820 --> 00:01:13,390
פועל על מנת של g (x)

29
00:01:13,390 --> 00:01:15,140
אם קיים חלק (x) ערך, x ₀ ו

30
00:01:15,140 --> 00:01:17,630
חלק קבוע, C, שעבורו

31
00:01:17,630 --> 00:01:19,340
f (x) היא פחות או שווה ל

32
00:01:19,340 --> 00:01:21,230
שהזמנים הקבועים g (x)

33
00:01:21,230 --> 00:01:23,190
לכל x הגדול מ ₀ x.

34
00:01:23,190 --> 00:01:25,290
>> אבל אל תפחד משם על ידי ההגדרה פורמלית.

35
00:01:25,290 --> 00:01:28,020
מה זה בעצם אומר במונחים תיאורטיים פחות?

36
00:01:28,020 --> 00:01:30,580
ובכן, זה בעצם דרך של ניתוח

37
00:01:30,580 --> 00:01:33,580
כמה מהר זמן הריצה של תכנית גדל אסימפטוטית.

38
00:01:33,580 --> 00:01:37,170
כלומר, כגודלו של התשומות שלך מגביר לקראת אינסוף,

39
00:01:37,170 --> 00:01:41,390
תגיד, אתה ממיין מערך של 1000 בהשוואה לגודל מערך בגודל 10.

40
00:01:41,390 --> 00:01:44,950
איך זמן הריצה של התכנית שלך יגדל?

41
00:01:44,950 --> 00:01:47,390
לדוגמה, תניח לספור את מספר התווים

42
00:01:47,390 --> 00:01:49,350
במחרוזת הדרך הפשוטה

43
00:01:49,350 --> 00:01:51,620
 על ידי הליכה דרך כל השרשרת

44
00:01:51,620 --> 00:01:54,790
מכתב אחר מכתב והוספת 1 למונה לכל דמות.

45
00:01:55,700 --> 00:01:58,420
אלגוריתם זה אמר לרוץ בזמן ליניארי

46
00:01:58,420 --> 00:02:00,460
ביחס למספר התווים,

47
00:02:00,460 --> 00:02:02,670
'נ' במחרוזת.

48
00:02:02,670 --> 00:02:04,910
בקיצור, הוא פועל בO (n).

49
00:02:05,570 --> 00:02:07,290
מדוע זה קורה?

50
00:02:07,290 --> 00:02:09,539
ובכן, שימוש בגישה זו, הזמן הנדרש

51
00:02:09,539 --> 00:02:11,300
לכל אורך המחרוזת

52
00:02:11,300 --> 00:02:13,920
הוא פרופורציונלי למספר התווים.

53
00:02:13,920 --> 00:02:16,480
לספור את מספר התווים במחרוזת 20-אופי

54
00:02:16,480 --> 00:02:18,580
הוא הולך לקחת זמן כפול כפי שהוא לוקח

55
00:02:18,580 --> 00:02:20,330
כדי לספור את התווים במחרוזת 10-אופי,

56
00:02:20,330 --> 00:02:23,000
כי אתה צריך להסתכל על כל הדמויות

57
00:02:23,000 --> 00:02:25,740
וכל תו לוקח את אותה כמות הזמן להסתכל.

58
00:02:25,740 --> 00:02:28,050
ככל שתגדיל את מספר התווים,

59
00:02:28,050 --> 00:02:30,950
זמן הריצה יהיה להגדיל באופן ליניארי עם אורך הקלט.

60
00:02:30,950 --> 00:02:33,500
>> כעת, דמיינו אם אתה מחליט שזמן ליניארי,

61
00:02:33,500 --> 00:02:36,390
O (n), פשוט לא היה מהיר מספיק בשבילך?

62
00:02:36,390 --> 00:02:38,750
אולי אתה אחסון מחרוזות ענקיות,

63
00:02:38,750 --> 00:02:40,450
ואתה לא יכול להרשות את תוספת זמן זה ייקח

64
00:02:40,450 --> 00:02:44,000
לעבור את כל הדמויות שלהם נספרות אחד על אחד.

65
00:02:44,000 --> 00:02:46,650
אז, אתה מחליט לנסות משהו אחר.

66
00:02:46,650 --> 00:02:49,270
מה אם קורה כבר כדי לאחסן את מספר התווים

67
00:02:49,270 --> 00:02:52,690
במחרוזת, למשל, במשתנה שנקראה "לן, '

68
00:02:52,690 --> 00:02:54,210
בשלב המוקדם של התכנית,

69
00:02:54,210 --> 00:02:57,800
עוד לפני שאתה לאחסן את התו הראשון במחרוזת שלך?

70
00:02:57,800 --> 00:02:59,980
ואז, כל מה שהיית צריך לעשות עכשיו כדי לברר את אורך המחרוזת,

71
00:02:59,980 --> 00:03:02,570
הוא לבדוק מה הערך של המשתנה.

72
00:03:02,570 --> 00:03:05,530
לא היית צריך להסתכל על עצמו בכל המחרוזת,

73
00:03:05,530 --> 00:03:08,160
וגישת הערך של משתנה כמו len נחשבת

74
00:03:08,160 --> 00:03:11,100
פעולת זמן asymptotically מתמדת,

75
00:03:11,100 --> 00:03:13,070
או O (1).

76
00:03:13,070 --> 00:03:17,110
מדוע זה קורה? ובכן, זוכר מה מורכבות asymptotic אומרות.

77
00:03:17,110 --> 00:03:19,100
כיצד משתנה זמן הריצה כגודל

78
00:03:19,100 --> 00:03:21,400
התשומות שלך גדלה?

79
00:03:21,400 --> 00:03:24,630
>> לומר שניסיתם להשיג את מספר התווים במחרוזת גדולה יותר.

80
00:03:24,630 --> 00:03:26,960
ובכן, זה לא משנה כמה גדול אתה מבצע את המחרוזת,

81
00:03:26,960 --> 00:03:28,690
אפילו מיליון תווים,

82
00:03:28,690 --> 00:03:31,150
כל שהיית צריך לעשות כדי למצוא את האורך של המחרוזת עם גישה זו,

83
00:03:31,150 --> 00:03:33,790
הוא לקרוא את הערך של len משתנה,

84
00:03:33,790 --> 00:03:35,440
שכבר בצעת.

85
00:03:35,440 --> 00:03:38,200
אורך הקלט, כלומר, האורך של המחרוזת שאתה מנסה למצוא,

86
00:03:38,200 --> 00:03:41,510
אינו משפיע כלל כמה מהר התכנית שלך פועלת.

87
00:03:41,510 --> 00:03:44,550
חלק זה של התכנית שלך יהיה לרוץ באותה מהירות במחרוזת בתו אחד

88
00:03:44,550 --> 00:03:46,170
ומחרוזת אלף תווים,

89
00:03:46,170 --> 00:03:49,140
וזו הסיבה שתועבר לתכנית זו כריצה בזמן קבוע

90
00:03:49,140 --> 00:03:51,520
ביחס לגודל הקלט.

91
00:03:51,520 --> 00:03:53,920
>> כמובן, יש חסרון.

92
00:03:53,920 --> 00:03:55,710
אתה מבלה מרחב זיכרון נוסף במחשב שלך

93
00:03:55,710 --> 00:03:57,380
אחסון משתנה

94
00:03:57,380 --> 00:03:59,270
ותוספת הזמן זה לוקח לך

95
00:03:59,270 --> 00:04:01,490
לעשות אחסון הממשי של המשתנה,

96
00:04:01,490 --> 00:04:03,390
אבל הנקודה עדיין עומדת,

97
00:04:03,390 --> 00:04:05,060
לגלות כמה זמן המחרוזת שלך הייתה

98
00:04:05,060 --> 00:04:07,600
לא תלוי באורך החוט בכלל.

99
00:04:07,600 --> 00:04:10,720
אז, הוא פועל בO (1) או זמן קבוע.

100
00:04:10,720 --> 00:04:13,070
זה בהחלט לא אומר שצריך

101
00:04:13,070 --> 00:04:15,610
שהקוד שלך פועל בשלב 1,

102
00:04:15,610 --> 00:04:17,470
אבל לא משנה כמה צעדים שהוא,

103
00:04:17,470 --> 00:04:20,019
אם זה לא משתנה עם הגודל של התשומות,

104
00:04:20,019 --> 00:04:23,420
זה עדיין asymptotically מתמיד שאנו מייצגים כO (1).

105
00:04:23,420 --> 00:04:25,120
>> כפי שאתם יכולים לנחש,

106
00:04:25,120 --> 00:04:27,940
יש הרבה runtimes O הגדול שונה למדידה עם אלגוריתמים.

107
00:04:27,940 --> 00:04:32,980
O (n) ² אלגוריתמי asymptotically איטיים יותר מאלגוריתמי O (n).

108
00:04:32,980 --> 00:04:35,910
כלומר, ככל שמספר אלמנטים (n) גדל,

109
00:04:35,910 --> 00:04:39,280
סופו של דבר O (n) ² אלגוריתמים ייקחו יותר זמן

110
00:04:39,280 --> 00:04:41,000
מ O אלגוריתמים (n) כדי לברוח.

111
00:04:41,000 --> 00:04:43,960
זה לא אומר שאלגוריתמי O (n) תמיד לרוץ מהר יותר

112
00:04:43,960 --> 00:04:46,410
מ O (n) אלגוריתמי ², גם באותה הסביבה,

113
00:04:46,410 --> 00:04:48,080
באותה החומרה.

114
00:04:48,080 --> 00:04:50,180
אולי עבור גדלי קלט קטנים,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² אלגוריתם באמת עשוי לעבוד מהר יותר,

116
00:04:52,900 --> 00:04:55,450
אבל, בסופו, כגודל הקלט מגדיל

117
00:04:55,450 --> 00:04:58,760
לקראת אינסוף, O זמן הריצה (n) ² של האלגוריתם

118
00:04:58,760 --> 00:05:02,000
סופו של דבר להאפיל על זמן הריצה של אלגוריתם O (n).

119
00:05:02,000 --> 00:05:04,230
בדיוק כמו כל פונקציה מתמטית ריבועית

120
00:05:04,230 --> 00:05:06,510
 סופו של דבר להשתלט על כל פונקציה לינארית,

121
00:05:06,510 --> 00:05:09,200
לא משנה כמה מראש יתחיל הפונקציה לינארית מתחיל עם.

122
00:05:10,010 --> 00:05:12,000
אם אתה עובד עם כמויות גדולות של נתונים,

123
00:05:12,000 --> 00:05:15,510
אלגוריתמים שרצים בO (n) ² זמן באמת יכול בסופו של האטת התכנית שלך,

124
00:05:15,510 --> 00:05:17,770
אבל לגודל קלט קטן,

125
00:05:17,770 --> 00:05:19,420
אתה כנראה אפילו לא שמת לב.

126
00:05:19,420 --> 00:05:21,280
>> מורכבות נוספות היא אסימפטוטי,

127
00:05:21,280 --> 00:05:24,420
זמן לוגריתמים, O (logn).

128
00:05:24,420 --> 00:05:26,340
דוגמה לאלגוריתם שפועל זה במהירות

129
00:05:26,340 --> 00:05:29,060
הוא אלגוריתם החיפוש הבינארי הקלסי,

130
00:05:29,060 --> 00:05:31,850
למציאת אלמנט ברשימה ממוינת כבר של אלמנטים.

131
00:05:31,850 --> 00:05:33,400
>> אם אתה לא יודע מה עושה החיפוש בינארי,

132
00:05:33,400 --> 00:05:35,170
אני אסביר את זה בשבילך ממש מהר.

133
00:05:35,170 --> 00:05:37,020
בואו נגיד שאתה מחפש את המספר 3

134
00:05:37,020 --> 00:05:40,200
במערך זה של מספרים שלמים.

135
00:05:40,200 --> 00:05:42,140
זה נראה באלמנט אמצע המערך

136
00:05:42,140 --> 00:05:46,830
ושואל, "האם אני רוצה האלמנט גדול מ, שווה, פחות או יותר מזה?"

137
00:05:46,830 --> 00:05:49,150
אם זה שווה, אז נהדר. מצא את האלמנט, וסיימת.

138
00:05:49,150 --> 00:05:51,300
אם זה יותר, אז אתה יודע את האלמנט

139
00:05:51,300 --> 00:05:53,440
צריך להיות בצד הנכון של המערך,

140
00:05:53,440 --> 00:05:55,200
ואתה יכול רק להסתכל על זה בעתיד,

141
00:05:55,200 --> 00:05:57,690
ואם זה קטן יותר, אז אתה יודע שזה צריך להיות בצד השמאל.

142
00:05:57,690 --> 00:06:00,980
אז התהליך הזה חוזר על עצמו עם המערך בגודל קטן יותר

143
00:06:00,980 --> 00:06:02,870
עד האלמנט הנכון הוא נמצא.

144
00:06:08,080 --> 00:06:11,670
>> אלגוריתם חזק זה חותך את גודל המערך במחצית עם כל פעולה.

145
00:06:11,670 --> 00:06:14,080
לכן, כדי למצוא את רכיב במערך ממוין בגודל 8,

146
00:06:14,080 --> 00:06:16,170
לכל היותר (להתחבר ₂ 8),

147
00:06:16,170 --> 00:06:18,450
או 3 של פעולות אלה,

148
00:06:18,450 --> 00:06:22,260
בדיקת אלמנט האמצע, ואז לחתוך את המערך במחצית יידרש,

149
00:06:22,260 --> 00:06:25,670
ואילו מערך בגודל 16 לוקח (להתחבר ₂ 16),

150
00:06:25,670 --> 00:06:27,480
או 4 פעולות.

151
00:06:27,480 --> 00:06:30,570
זה רק מבצע נוסף 1 למערך בגודל כפול.

152
00:06:30,570 --> 00:06:32,220
הכפלת הגודל של המערך

153
00:06:32,220 --> 00:06:35,160
מגדיל את זמן הריצה על ידי גוש של קוד זה רק 1.

154
00:06:35,160 --> 00:06:37,770
שוב, בודק מרכיב אמצע הרשימה, ואז פיצול.

155
00:06:37,770 --> 00:06:40,440
אז, זה אומר לפעול בזמן לוגריתמים,

156
00:06:40,440 --> 00:06:42,440
O (logn).

157
00:06:42,440 --> 00:06:44,270
אבל הרגע, אתה אומר,

158
00:06:44,270 --> 00:06:47,510
לא זה תלוי איפה ברשימת האלמנט שאתה מחפש הוא?

159
00:06:47,510 --> 00:06:50,090
מה אם האלמנט הראשון אתה מסתכל קורה להיות נכון?

160
00:06:50,090 --> 00:06:52,040
ואז, זה לוקח מבצע 1 בלבד,

161
00:06:52,040 --> 00:06:54,310
לא משנה כמה גדול היא הרשימה.

162
00:06:54,310 --> 00:06:56,310
>> ובכן, זו הסיבה שמדעני מחשב יש יותר תנאים

163
00:06:56,310 --> 00:06:58,770
למורכבות אסימפטוטי המשקף את תמונת מצב

164
00:06:58,770 --> 00:07:01,050
ומקרה הגרוע ביותר הופעות של אלגוריתם.

165
00:07:01,050 --> 00:07:03,320
לייתר דיוק, את הגבול העליון ותחתון

166
00:07:03,320 --> 00:07:05,090
בזמן הריצה.

167
00:07:05,090 --> 00:07:07,660
במקרה הטוב ביותר לחיפוש בינארי, האלמנט שלנו הוא

168
00:07:07,660 --> 00:07:09,330
ממש שם באמצע,

169
00:07:09,330 --> 00:07:11,770
ואתה מקבל את זה בזמן קבוע,

170
00:07:11,770 --> 00:07:14,240
לא משנה כמה גדול את שאר המערך הוא.

171
00:07:15,360 --> 00:07:17,650
הסמל משמש לכך הוא Ω.

172
00:07:17,650 --> 00:07:19,930
לכן, אלגוריתם זה אמר לרוץ בΩ (1).

173
00:07:19,930 --> 00:07:21,990
במקרה הטוב ביותר, הוא מוצא את אלמנט מהירות,

174
00:07:21,990 --> 00:07:24,200
לא משנה כמה גדול הוא המערך,

175
00:07:24,200 --> 00:07:26,050
אבל במקרה הגרוע ביותר,

176
00:07:26,050 --> 00:07:28,690
יש לבצע (logn) בדיקות מפוצלות

177
00:07:28,690 --> 00:07:31,030
של המערך כדי למצוא את האלמנט הנכון.

178
00:07:31,030 --> 00:07:34,270
גבולות מקרה הגרוע ביותר העליונים מופנים לעם "O" הגדול שאתה כבר יודע.

179
00:07:34,270 --> 00:07:38,080
אז, זה O (logn), אבל Ω (1).

180
00:07:38,080 --> 00:07:40,680
>> חיפוש ליניארי, לעומת זאת,

181
00:07:40,680 --> 00:07:43,220
שבו אתה הולך בכל אלמנט של המערך

182
00:07:43,220 --> 00:07:45,170
כדי למצוא את זו שרצית,

183
00:07:45,170 --> 00:07:47,420
הוא בΩ הטוב ביותר (1).

184
00:07:47,420 --> 00:07:49,430
שוב, האלמנט הראשון שאתה רוצה.

185
00:07:49,430 --> 00:07:51,930
לכן, זה לא משנה כמה גדול הוא המערך.

186
00:07:51,930 --> 00:07:54,840
במקרה הגרוע ביותר, זה האלמנט האחרון במערך.

187
00:07:54,840 --> 00:07:58,560
אז, אתה צריך ללכת דרך כל אלמנטי n במערך כדי למצוא אותו,

188
00:07:58,560 --> 00:08:02,170
כמו שאם היה מחפש 3.

189
00:08:04,320 --> 00:08:06,030
אז, הוא פועל בזמן O (n)

190
00:08:06,030 --> 00:08:09,330
כי זה תלוי במספר האלמנטים במערך.

191
00:08:10,800 --> 00:08:12,830
>> עוד סמל אחד המשמש הוא Θ.

192
00:08:12,830 --> 00:08:15,820
זה יכול לשמש כדי לתאר אלגוריתמים בי המקרה הטוב והגרוע ביותר

193
00:08:15,820 --> 00:08:17,440
הם אותו הדבר.

194
00:08:17,440 --> 00:08:20,390
זה מקרה באלגוריתמי מחרוזת באורך שדברנו עליו קודם לכן.

195
00:08:20,390 --> 00:08:22,780
כלומר, אם אנחנו מאחסנים אותו במשתנה לפני

196
00:08:22,780 --> 00:08:25,160
אנו מאחסנים את המחרוזת ולגשת אליו מאוחר יותר בזמן קבוע.

197
00:08:25,160 --> 00:08:27,920
לא משנה מה מספר

198
00:08:27,920 --> 00:08:30,130
אנחנו אחסון שבמשתנים, יהיה לנו להסתכל על זה.

199
00:08:33,110 --> 00:08:35,110
המקרה הטוב ביותר הוא, שאנחנו מסתכלים על זה

200
00:08:35,110 --> 00:08:37,120
ולמצוא את אורך המחרוזת.

201
00:08:37,120 --> 00:08:39,799
אז Ω (1) או זמן קבוע הטוב ביותר במקרה.

202
00:08:39,799 --> 00:08:41,059
המקרה הגרוע ביותר הוא,

203
00:08:41,059 --> 00:08:43,400
אנחנו מסתכלים על זה ולמצוא את אורך המחרוזת.

204
00:08:43,400 --> 00:08:47,300
אז, O (1) זמן קבוע או במקרה הגרוע ביותר.

205
00:08:47,300 --> 00:08:49,180
לכן, מאז המקרה הטוב והמקרים הגרועים ביותר הם אותו הדבר,

206
00:08:49,180 --> 00:08:52,520
זה יכול להיות אמר לרוץ בזמן Θ (1).

207
00:08:54,550 --> 00:08:57,010
>> לסיכום, יש לנו דרכים טובות לסיבה על יעילות קודים

208
00:08:57,010 --> 00:09:00,110
בלי לדעת דבר על הזמן בעולם אמיתי הם לוקחים לרוץ,

209
00:09:00,110 --> 00:09:02,270
אשר מושפע על ידי הרבה גורמים חיצוניים,

210
00:09:02,270 --> 00:09:04,190
כולל חומרה שונה, תוכנה,

211
00:09:04,190 --> 00:09:06,040
או את הפרטים של הקוד שלך.

212
00:09:06,040 --> 00:09:08,380
כמו כן, היא מאפשרת לנו לחשוב בהיגיון גם על מה שיקרה

213
00:09:08,380 --> 00:09:10,180
כאשר הגודל של עליות תשומות.

214
00:09:10,180 --> 00:09:12,490
>> אם אתה מפעיל באלגוריתם O (n) ²,

215
00:09:12,490 --> 00:09:15,240
או יותר גרוע, O (2 ⁿ) אלגוריתם,

216
00:09:15,240 --> 00:09:17,170
אחד מסוגי הצמיחה המהירים ביותר,

217
00:09:17,170 --> 00:09:19,140
אתה באמת מתחיל לשים לב להאטה

218
00:09:19,140 --> 00:09:21,220
כשאתה מתחיל לעבוד עם כמויות גדולות יותר של נתונים.

219
00:09:21,220 --> 00:09:23,590
>> זה מורכבות אסימפטוטי. תודה.