1
00:00:00,000 --> 00:00:05,830

2
00:00:05,830 --> 00:00:07,910
>> בסדר, אז, המורכבות חישובית.

3
00:00:07,910 --> 00:00:10,430
רק קצת אזהרה
לפני שאנחנו צוללים במדי far--

4
00:00:10,430 --> 00:00:13,070
זה כנראה אהיה בין
הדברים הכי המתמטיקה-כבדה

5
00:00:13,070 --> 00:00:14,200
אנחנו מדברים על בCS50.

6
00:00:14,200 --> 00:00:16,950
אני מקווה שזה לא יהיה מכריע מדי
וננסה להדריך אותך

7
00:00:16,950 --> 00:00:19,200
בתהליך, אבל
רק קצת אזהרה הוגנת.

8
00:00:19,200 --> 00:00:21,282
יש קצת
של מתמטיקה מעורבת כאן.

9
00:00:21,282 --> 00:00:23,990
בסדר, זאת על מנת להפוך את
שימוש במשאבי המחשוב שלנו

10
00:00:23,990 --> 00:00:28,170
בworld-- האמיתי זה באמת
חשוב להבין אלגוריתמים

11
00:00:28,170 --> 00:00:30,750
ואיך הם לעבד את הנתונים.

12
00:00:30,750 --> 00:00:32,810
אם יש לנו באמת
אלגוריתם יעיל, אנחנו

13
00:00:32,810 --> 00:00:36,292
יכול למזער את כמות המשאבים
יש לנו זמין להתמודד עם זה.

14
00:00:36,292 --> 00:00:38,750
אם יש לנו אלגוריתם ש
הולך לקחת הרבה עבודה

15
00:00:38,750 --> 00:00:41,210
לעבד באמת
קבוצה גדולה של נתונים, זה

16
00:00:41,210 --> 00:00:44,030
הולך לדרוש יותר
ויותר משאבים, ש

17
00:00:44,030 --> 00:00:47,980
הוא כסף, זיכרון RAM, כל סוג כזה של דברים.

18
00:00:47,980 --> 00:00:52,090
>> אז, להיות מסוגל לנתח
אלגוריתם באמצעות סט כלי זה,

19
00:00:52,090 --> 00:00:56,110
בעצם, שואל question--
איך עושה בקנה מידה אלגוריתם זה

20
00:00:56,110 --> 00:00:59,020
כפי שאנו זורקים יותר ויותר נתונים על זה?

21
00:00:59,020 --> 00:01:02,220
בCS50, כמות הנתונים שאנחנו
עבודה עם היא די קטנה.

22
00:01:02,220 --> 00:01:05,140
בדרך כלל, התוכניות שלנו הולכים
לרוץ בשני או less--

23
00:01:05,140 --> 00:01:07,830
כנראה הרבה פחות
במיוחד בשלב מוקדם.

24
00:01:07,830 --> 00:01:12,250
>> אבל תחשוב על חברה שעוסקת
עם מאה מיליון לקוחות.

25
00:01:12,250 --> 00:01:14,970
והם צריכים לעבד
כי נתוני לקוחות.

26
00:01:14,970 --> 00:01:18,260
ככל שמספר לקוחות שהם
יש לי מקבל יותר ויותר גדול,

27
00:01:18,260 --> 00:01:21,230
זה הולך לדרוש
יותר ויותר משאבים.

28
00:01:21,230 --> 00:01:22,926
כמה יותר משאבים?

29
00:01:22,926 --> 00:01:25,050
ובכן, זה תלוי איך
אנחנו מנתחים את האלגוריתם,

30
00:01:25,050 --> 00:01:28,097
תוך שימוש בכלים בארגז כלים זה.

31
00:01:28,097 --> 00:01:31,180
כאשר אנו מדברים על המורכבות של
algorithm-- שלפעמים אתה

32
00:01:31,180 --> 00:01:34,040
לשמוע את זה מכונה זמן
מורכבות מורכבות או חלל

33
00:01:34,040 --> 00:01:36,190
אבל אנחנו פשוט הולכים
לקרוא complexity--

34
00:01:36,190 --> 00:01:38,770
אנחנו בדרך כלל מדברים על
התרחיש הגרוע ביותר.

35
00:01:38,770 --> 00:01:42,640
בהתחשב בערימה הגרועה ביותר המוחלטת של
נתונים שאנחנו יכולים להיות השלכה על זה,

36
00:01:42,640 --> 00:01:46,440
איך אלגוריתם זה הולך
לעבד או להתמודד עם נתונים ש?

37
00:01:46,440 --> 00:01:51,450
בדרך כלל אנחנו קוראים למקרה הגרוע ביותר
זמן ריצה של אלגוריתם גדול-O.

38
00:01:51,450 --> 00:01:56,770
אז אלגוריתם אפשר לומר ל
לרוץ בO של n או O של n בריבוע.

39
00:01:56,770 --> 00:01:59,110
ועוד על מה
אלה אומר בשניים.

40
00:01:59,110 --> 00:02:01,620
>> לפעמים, אם כי, אנחנו עושים טיפול
על המקרה הטוב.

41
00:02:01,620 --> 00:02:05,400
אם הנתונים הוא כל מה שרצינו
שזה יהיה, וזה היה פשוט מושלם

42
00:02:05,400 --> 00:02:09,630
ואנחנו שולחים את זה מושלם
קבוצה של נתונים באמצעות האלגוריתם שלנו.

43
00:02:09,630 --> 00:02:11,470
איך זה לטפל במצב זה?

44
00:02:11,470 --> 00:02:15,050
לפעמים אנחנו מתייחסים לזה כ
גדולה-אומגה, כך בניגוד לגדול-O,

45
00:02:15,050 --> 00:02:16,530
יש לנו גדולה-אומגה.

46
00:02:16,530 --> 00:02:18,880
Big-אומגה למקרה הטוב.

47
00:02:18,880 --> 00:02:21,319
Big-O לתרחיש הגרוע ביותר.

48
00:02:21,319 --> 00:02:23,860
בדרך כלל, כאשר אנו מדברים על
המורכבות של אלגוריתם,

49
00:02:23,860 --> 00:02:26,370
על אנחנו מדברים
במקרה הגרוע ביותר.

50
00:02:26,370 --> 00:02:28,100
אז לשמור את זה בחשבון.

51
00:02:28,100 --> 00:02:31,510
>> ובמעמד הזה, אנחנו בדרך כלל הולכים
לעזוב את הניתוח הקפדני בצד.

52
00:02:31,510 --> 00:02:35,350
יש מדעים ושדות
מוקדש לדברים מסוג זה.

53
00:02:35,350 --> 00:02:37,610
כאשר אנו מדברים על חשיבה
באמצעות אלגוריתמים,

54
00:02:37,610 --> 00:02:41,822
שאנחנו נעשה את החתיכה על ידי חתיכה-רבים
אלגוריתמים אנחנו מדברים על בכיתה.

55
00:02:41,822 --> 00:02:44,780
אנחנו באמת מדברים רק על
הנמקה דרכו עם שכל ישר,

56
00:02:44,780 --> 00:02:47,070
לא עם נוסחות, או הוכחות,
או משהו כזה.

57
00:02:47,070 --> 00:02:51,600
אז אל תדאגו, אנחנו לא יהיו
הופך לשיעור מתמטיקה גדול.

58
00:02:51,600 --> 00:02:55,920
>> אז אמרתי שאכפת לנו מורכבות
כי זה שואל את השאלה, כיצד

59
00:02:55,920 --> 00:03:00,160
אל האלגוריתמים שלנו להתמודד עם גדולים יותר ו
ערכות נתונים גדולות שהושלכו לעברם.

60
00:03:00,160 --> 00:03:01,960
ובכן, מה היא ערכת נתונים?

61
00:03:01,960 --> 00:03:03,910
מה שאני מתכוון כשאני אומר את זה?

62
00:03:03,910 --> 00:03:07,600
זה אומר כל מה שעושה את רוב
תחושה בהקשר, אם להיות כנה.

63
00:03:07,600 --> 00:03:11,160
אם יש לנו אלגוריתם,
תהליכי מייתרים: אנחנו כנראה

64
00:03:11,160 --> 00:03:13,440
מדבר על הגודל של המחרוזת.

65
00:03:13,440 --> 00:03:15,190
זה נתונים set--
הגודל, המספר

66
00:03:15,190 --> 00:03:17,050
תווים שמרכיבים את המחרוזת.

67
00:03:17,050 --> 00:03:20,090
על אם אנחנו מדברים
אלגוריתם שמעבד קבצים,

68
00:03:20,090 --> 00:03:23,930
אנחנו יכולים להיות מדברים על איך
קילו-רב מהווה קובץ ש.

69
00:03:23,930 --> 00:03:25,710
וזה ערכת הנתונים.

70
00:03:25,710 --> 00:03:28,870
על אלגוריתם אם אנחנו מדברים
שמטפל במערכים באופן כללי יותר,

71
00:03:28,870 --> 00:03:31,510
כמו אלגוריתמי מיון
או חיפוש אלגוריתמים,

72
00:03:31,510 --> 00:03:36,690
אנחנו כנראה מדברים על המספר
אלמנטים המרכיבים את מערך.

73
00:03:36,690 --> 00:03:39,272
>> עכשיו, אנחנו יכולים למדוד
algorithm-- בפרט,

74
00:03:39,272 --> 00:03:40,980
כשאני אומר שאנחנו יכולים
למדוד אלגוריתם, אני

75
00:03:40,980 --> 00:03:43,840
אומרים שאנחנו יכולים למדוד כמה
משאבים רבים שנדרש עד.

76
00:03:43,840 --> 00:03:48,990
אם משאבים אלה, כמה
בתים של RAM-- או מגה בייט של זיכרון RAM

77
00:03:48,990 --> 00:03:49,790
היא משתמשת.

78
00:03:49,790 --> 00:03:52,320
או כמה זמן שנדרש כדי להפעיל.

79
00:03:52,320 --> 00:03:56,200
ואנחנו יכולים לקרוא לזה
למדוד, באופן שרירותי, F של n.

80
00:03:56,200 --> 00:03:59,420
כאשר n הוא מספר
רכיבים בערכת נתונים.

81
00:03:59,420 --> 00:04:02,640
ו- F של n הוא ומשהו כמה.

82
00:04:02,640 --> 00:04:07,530
כמה יחידות של משאבים עושה
זה דורש לעבד נתונים ש.

83
00:04:07,530 --> 00:04:10,030
>> עכשיו, אנחנו באמת לא אכפת לי
על מה f של n הוא בדיוק.

84
00:04:10,030 --> 00:04:13,700
למעשה, אנחנו לעתים רחוקות מאוד will--
בהחלט לעולם לא באני class-- זה

85
00:04:13,700 --> 00:04:18,709
לצלול לתוך כל ממש עמוק
ניתוח של מה f של n הוא.

86
00:04:18,709 --> 00:04:23,510
אנחנו רק הולכים לדבר על מה f של
n הוא כ או מה הוא נוטה.

87
00:04:23,510 --> 00:04:27,600
והנטייה של אלגוריתם היא
מוכתב על ידי מונח הסדר הגבוה ביותר שלה.

88
00:04:27,600 --> 00:04:29,440
ואנחנו יכולים לראות מה אני
מתכוון בזה על ידי לקיחה

89
00:04:29,440 --> 00:04:31,910
יסתכל על דוגמא קונקרטית יותר.

90
00:04:31,910 --> 00:04:34,620
>> אז בואו נגיד שיש לנו
שלושה אלגוריתמים שונים.

91
00:04:34,620 --> 00:04:39,350
הראשון שבם לוקח n
קוביות, כמה יחידות של משאבים

92
00:04:39,350 --> 00:04:42,880
לעבד ערכת נתונים בגודל n.

93
00:04:42,880 --> 00:04:47,000
יש לנו אלגוריתם שני שלוקח
n קוביות בתוספת משאבים n בריבוע

94
00:04:47,000 --> 00:04:49,350
לעבד ערכת נתונים בגודל n.

95
00:04:49,350 --> 00:04:52,030
ויש לנו שליש
אלגוריתם שפועל in-- ש

96
00:04:52,030 --> 00:04:58,300
לוקח n 8N מינוס קוביות בריבוע
בתוספת 20 n יחידות של משאבים

97
00:04:58,300 --> 00:05:02,370
לעבד אלגוריתם
עם נתונים שנקבעו בגודל n.

98
00:05:02,370 --> 00:05:05,594
>> עכשיו שוב, אנחנו באמת לא הולכים
להיכנס לזה ברמה של פרט.

99
00:05:05,594 --> 00:05:08,260
אני באמת רק יש לי אלה עד
כאן כהמחשה של נקודה

100
00:05:08,260 --> 00:05:10,176
שאני הולך להיות
מה שהופך בשנייה, ש

101
00:05:10,176 --> 00:05:12,980
הוא שאנחנו רק באמת אכפת לי
על הנטייה של דברים

102
00:05:12,980 --> 00:05:14,870
כערכות נתונים גדולות יותר לקבל.

103
00:05:14,870 --> 00:05:18,220
אז אם ערכת הנתונים היא קטנה, יש
למעשה הבדל די גדול

104
00:05:18,220 --> 00:05:19,870
באלגוריתמים אלה.

105
00:05:19,870 --> 00:05:23,000
האלגוריתם השלישי יש
לוקח 13 פעמים יותר,

106
00:05:23,000 --> 00:05:27,980
13 פעמים הסכום של משאבים
כדי להפעיל ביחס לראשון.

107
00:05:27,980 --> 00:05:31,659
>> אם ערכת הנתונים שלנו היא בגודל 10, ש
הוא גדול יותר, אך לא בהכרח ענק,

108
00:05:31,659 --> 00:05:33,950
אנחנו יכולים לראות שיש
למעשה קצת הבדל.

109
00:05:33,950 --> 00:05:36,620
האלגוריתם השלישי
הופך יעיל יותר.

110
00:05:36,620 --> 00:05:40,120
זה בעצם על 40% -
או 60% יעילים יותר.

111
00:05:40,120 --> 00:05:41,580
זה לוקח 40% את כמות הזמן.

112
00:05:41,580 --> 00:05:45,250
זה יכול run-- זה יכול לקחת
400 יחידות של משאבים

113
00:05:45,250 --> 00:05:47,570
לעבד סט נתונים של גודל 10.

114
00:05:47,570 --> 00:05:49,410
בעוד הראשון
אלגוריתם, לעומת זאת,

115
00:05:49,410 --> 00:05:54,520
לוקח 1,000 יחידות של משאבים
לעבד סט נתונים של גודל 10.

116
00:05:54,520 --> 00:05:57,240
אבל תראה מה קורה כ
המספרים שלנו להגיע אפילו גדולים יותר.

117
00:05:57,240 --> 00:05:59,500
>> עכשיו, ההבדל
בין אלגוריתמים אלה

118
00:05:59,500 --> 00:06:01,420
מתחיל להיות קצת פחות נראית לעין.

119
00:06:01,420 --> 00:06:04,560
והעובדה שיש
נמוך-מנת terms-- או לייתר דיוק,

120
00:06:04,560 --> 00:06:09,390
מונחים עם exponents-- הנמוך
מתחיל להיות לא רלוונטי.

121
00:06:09,390 --> 00:06:12,290
אם ערכת נתונים היא בגודל
1,000 והאלגוריתם הראשון

122
00:06:12,290 --> 00:06:14,170
פועל במליארד שלבים.

123
00:06:14,170 --> 00:06:17,880
והאלגוריתם השני פועל ב
מיליארדים ומיליון צעדים.

124
00:06:17,880 --> 00:06:20,870
והאלגוריתם השלישי פועל
בפשוט ביישן של מיליארדים צעדים.

125
00:06:20,870 --> 00:06:22,620
זה די הרבה מיליארדים צעדים.

126
00:06:22,620 --> 00:06:25,640
אלה תנאים התחתון כדי להתחיל
כדי להפוך באמת לא רלוונטי.

127
00:06:25,640 --> 00:06:27,390
ורק כדי באמת
פטיש בית point--

128
00:06:27,390 --> 00:06:31,240
אם נתוני הקלט הוא בגודל
million-- כל שלושת אלה פחות או יותר

129
00:06:31,240 --> 00:06:34,960
לקחת quintillion-- אחד אם
המתמטיקה שלי היא צעדי correct--

130
00:06:34,960 --> 00:06:37,260
לעבד קלט נתונים
גודל מיליון.

131
00:06:37,260 --> 00:06:38,250
זה הרבה שלבים.

132
00:06:38,250 --> 00:06:42,092
והעובדה שאחד מהם עשויה
לקחת כמה 100,000, או לזוג 100

133
00:06:42,092 --> 00:06:44,650
מיליון אפילו פחות כאשר
על מספר אנחנו מדברים

134
00:06:44,650 --> 00:06:46,990
שbig-- זה סוג של לא רלוונטי.

135
00:06:46,990 --> 00:06:50,006
כולם נוטים לקחת
כ קוביות n,

136
00:06:50,006 --> 00:06:52,380
וכך היינו למעשה מתייחס
לכל אלגוריתמים אלה

137
00:06:52,380 --> 00:06:59,520
כמו להיות על סדר n
קוביות או גדול-O של קוביות n.

138
00:06:59,520 --> 00:07:03,220
>> הנה רשימה של כמה מיותר
כיתות מורכבות חישובית נפוצות

139
00:07:03,220 --> 00:07:05,820
שאנחנו נתקלים ב
אלגוריתמים, בדרך כלל.

140
00:07:05,820 --> 00:07:07,970
וגם באופן ספציפי בCS50.

141
00:07:07,970 --> 00:07:11,410
אלה מסודרות מ
בדרך כלל המהיר ביותר בחלק העליון,

142
00:07:11,410 --> 00:07:13,940
לבדרך כלל האיטי ביותר בתחתית.

143
00:07:13,940 --> 00:07:16,920
אז אלגוריתמי זמן קבוע נוטים
להיות המהיר ביותר, ללא קשר

144
00:07:16,920 --> 00:07:19,110
בגודל של
נתוני קלט שאתה עובר ב.

145
00:07:19,110 --> 00:07:23,760
הם תמיד לוקחים פעולה אחת או
יחידה אחת של משאבים כדי להתמודד עם.

146
00:07:23,760 --> 00:07:25,730
זה יכול להיות 2, אולי זה
להיות 3, זה יכול להיות 4.

147
00:07:25,730 --> 00:07:26,910
אבל זה מספר קבוע.

148
00:07:26,910 --> 00:07:28,400
זה לא ישתנה.

149
00:07:28,400 --> 00:07:31,390
>> אלגוריתמי זמן לוגריתמי
הם מעט טובים יותר.

150
00:07:31,390 --> 00:07:33,950
ודוגמא טובה באמת של
אלגוריתם זמן לוגריתמים

151
00:07:33,950 --> 00:07:37,420
ראית בוודאי על ידי החברה הוא
קורעת של ספר טלפונים

152
00:07:37,420 --> 00:07:39,480
למצוא מייק סמית בספר טלפונים.

153
00:07:39,480 --> 00:07:40,980
אנחנו חותכים את הבעיה במחצית.

154
00:07:40,980 --> 00:07:43,580
וכך ככל שיגדל
וגדול יותר וlarger--

155
00:07:43,580 --> 00:07:47,290
למעשה, בכל פעם שאתה להכפיל
n, זה לוקח רק עוד צעד אחד.

156
00:07:47,290 --> 00:07:49,770
אז זה הרבה יותר טוב
מאשר, למשל, זמן ליניארי.

157
00:07:49,770 --> 00:07:53,030
וזה אם אתה להכפיל n, זה
לוקח כפולות מספר הצעדים.

158
00:07:53,030 --> 00:07:55,980
אם אתה לשלש n, זה לוקח
לשלש את מספר הצעדים.

159
00:07:55,980 --> 00:07:58,580
צעד אחד ליחידה.

160
00:07:58,580 --> 00:08:01,790
>> אז דברים מקבלים קצת more--
קצת פחות גדול משם.

161
00:08:01,790 --> 00:08:06,622
יש לך זמן קצוב ליניארי, לפעמים
נקרא זמן ליניארי יומן או פשוט להיכנס n n.

162
00:08:06,622 --> 00:08:08,330
ואנחנו דוגמא
של אלגוריתם ש

163
00:08:08,330 --> 00:08:13,370
ריצות בn n יומן, שהוא עדיין טוב יותר
מ n time-- ריבועית בריבוע.

164
00:08:13,370 --> 00:08:17,320
או זמן פולינום, n שני
כל מספר גדול משני.

165
00:08:17,320 --> 00:08:20,810
או זמן מעריכי, ש
הוא אפילו C לworse-- n.

166
00:08:20,810 --> 00:08:24,670
אז כמה מספר קבוע העלה ל
כוחו של גודל הקלט.

167
00:08:24,670 --> 00:08:28,990
אז אם יש 1,000-- אם
נתוני קלט הוא בגודל 1,000,

168
00:08:28,990 --> 00:08:31,310
זה ייקח C לכח -1,000.

169
00:08:31,310 --> 00:08:33,559
זה הרבה יותר גרוע מאשר זמן פולינום.

170
00:08:33,559 --> 00:08:35,030
>> זמן עצרת הוא אפילו יותר גרוע.

171
00:08:35,030 --> 00:08:37,760
ואכן, יש באמת לעשות
קיימים אלגוריתמי זמן אינסופיים,

172
00:08:37,760 --> 00:08:43,740
sort-- טיפש שכמו, מה שנקרא כזה
עבודה היא דשדוש מערך באופן אקראי

173
00:08:43,740 --> 00:08:45,490
ולאחר מכן לבדוק
אם זה מסודרים.

174
00:08:45,490 --> 00:08:47,589
ואם זה לא, באופן אקראי
דשדוש המערך שוב

175
00:08:47,589 --> 00:08:49,130
ולבדוק אם זה מסודרים.

176
00:08:49,130 --> 00:08:51,671
וכמו שאתה יכול כנראה imagine--
אתה יכול לדמיין מצב

177
00:08:51,671 --> 00:08:55,200
שבו במקרה הגרוע ביותר, כי רצון
אף פעם לא באמת להתחיל עם המערך.

178
00:08:55,200 --> 00:08:57,150
האלגוריתם שירוץ לנצח.

179
00:08:57,150 --> 00:08:59,349
וכדי שיהיה
אלגוריתם זמן אינסופי.

180
00:08:59,349 --> 00:09:01,890
אני מקווה שאתה לא כותב
כל עת עצרת או אינסופית

181
00:09:01,890 --> 00:09:04,510
אלגוריתמים בCS50.

182
00:09:04,510 --> 00:09:09,150
>> אז, בואו ניקח קצת יותר
מבט בטון בכמה פשוט

183
00:09:09,150 --> 00:09:11,154
כיתות מורכבות חישובית.

184
00:09:11,154 --> 00:09:13,070
אז יש לנו example--
או שתי דוגמאות כאן--

185
00:09:13,070 --> 00:09:15,590
אלגוריתמים זמן קבועים,
שתמיד לוקחים

186
00:09:15,590 --> 00:09:17,980
פעולה אחת במקרה הגרוע ביותר.

187
00:09:17,980 --> 00:09:20,050
אז example-- הראשון
יש לנו פונקציה

188
00:09:20,050 --> 00:09:23,952
נקרא 4 בשבילך, ש
לוקח מערך של גודל 1,000.

189
00:09:23,952 --> 00:09:25,660
אבל אז, ככל הנראה,
לא ממש נראה

190
00:09:25,660 --> 00:09:29,000
בלא ממש אכפת מה it--
בתוכו, של מערך זה.

191
00:09:29,000 --> 00:09:30,820
תמיד רק חוזר ארבעה.

192
00:09:30,820 --> 00:09:32,940
אז, אלגוריתם ש,
למרות שזה

193
00:09:32,940 --> 00:09:35,840
לוקח 1,000 אלמנטים לא
לעשות שום דבר איתם.

194
00:09:35,840 --> 00:09:36,590
רק חוזר ארבעה.

195
00:09:36,590 --> 00:09:38,240
זה תמיד צעד אחד.

196
00:09:38,240 --> 00:09:41,600
>> למעשה, להוסיף 2 nums-- ש
ראינו לפני כ"תראה

197
00:09:41,600 --> 00:09:43,680
רק מעבד שני מספרים שלמים.

198
00:09:43,680 --> 00:09:44,692
זה לא צעד אחד.

199
00:09:44,692 --> 00:09:45,900
זה בעצם כמה צעדים.

200
00:09:45,900 --> 00:09:50,780
אתה מקבל, אתה מקבל ב, לך להוסיף אותם
יחד, ואתה פלט התוצאות.

201
00:09:50,780 --> 00:09:53,270
אז זה 84 צעדים.

202
00:09:53,270 --> 00:09:55,510
אבל זה תמיד קבוע,
ללא קשר לאו ב.

203
00:09:55,510 --> 00:09:59,240
אתה צריך לקבל, לקבל ב, להוסיף
אותם יחד, פלט התוצאה.

204
00:09:59,240 --> 00:10:02,900
אז זה אלגוריתם זמן קבוע.

205
00:10:02,900 --> 00:10:05,170
>> הנה דוגמא של
algorithm-- הזמן ליניארי

206
00:10:05,170 --> 00:10:08,740
אלגוריתם שgets-- שלוקח
צעד אחד נוסף, ואולי,

207
00:10:08,740 --> 00:10:10,740
כקלט שלך גדל ב -1.

208
00:10:10,740 --> 00:10:14,190
אז, נניח שאנחנו מחפשים
בתוך מספר 5 של מערך.

209
00:10:14,190 --> 00:10:16,774
אולי יש לך מצב שבו
אתה יכול למצוא אותו בשלב מוקדם למדי.

210
00:10:16,774 --> 00:10:18,606
אבל אתה יכול גם יש לי
מצב שבו

211
00:10:18,606 --> 00:10:20,450
יכול להיות האלמנט האחרון של המערך.

212
00:10:20,450 --> 00:10:23,780
במערך של גודל 5, אם
אנחנו מחפשים את המספר 5.

213
00:10:23,780 --> 00:10:25,930
זה ייקח 5 שלבים.

214
00:10:25,930 --> 00:10:29,180
ולמעשה, לדמיין שיש
לא 5 בכל מקום במערך זה.

215
00:10:29,180 --> 00:10:32,820
אנחנו עדיין ממש צריכים להסתכל על
כל אלמנט של המערך

216
00:10:32,820 --> 00:10:35,550
על מנת לקבוע
אם 5 הוא שם.

217
00:10:35,550 --> 00:10:39,840
>> אז במקרה הגרוע ביותר, והוא ש
האלמנט הוא אחרון במערך

218
00:10:39,840 --> 00:10:41,700
או לא קיימות בכלל.

219
00:10:41,700 --> 00:10:44,690
עדיין יש לנו לחפש ב
כל האלמנטים n.

220
00:10:44,690 --> 00:10:47,120
וכך אלגוריתם זה
פועל בזמן ליניארי.

221
00:10:47,120 --> 00:10:50,340
אתה יכול לאשר כי על ידי
אקסטרפולציה קצת באומרו,

222
00:10:50,340 --> 00:10:53,080
אם היו לנו מערך 6-יסוד ו
אנחנו מחפשים את המספר 5,

223
00:10:53,080 --> 00:10:54,890
זה עלול לקחת 6 שלבים.

224
00:10:54,890 --> 00:10:57,620
אם יש לנו מערך 7-יסוד ו
אנחנו מחפשים את המספר 5.

225
00:10:57,620 --> 00:10:59,160
זה עלול לקחת 7 שלבים.

226
00:10:59,160 --> 00:11:02,920
כפי שאנו מוסיפים אלמנט נוסף לנו
מערך, זה לוקח עוד צעד אחד.

227
00:11:02,920 --> 00:11:06,750
זה אלגוריתם ליניארי
במקרה הגרוע ביותר.

228
00:11:06,750 --> 00:11:08,270
>> כמה שאלות מהירות בשבילך.

229
00:11:08,270 --> 00:11:11,170
מה runtime-- מה
במקרה הגרוע ביותר, זמן הריצה

230
00:11:11,170 --> 00:11:13,700
של קטע המסוים הזה של קוד?

231
00:11:13,700 --> 00:11:17,420
אז יש לי לולאה 4 כאן הפועלת
מj שווה 0, כל הדרך עד למטר.

232
00:11:17,420 --> 00:11:21,980
ומה שאני רואה כאן הוא, ש
גוף של הלולאה פועל בזמן קבוע.

233
00:11:21,980 --> 00:11:24,730
זאת באמצעות הטרמינולוגיה ש
אנחנו כבר דיברנו על-- מה

234
00:11:24,730 --> 00:11:29,390
יהיה הגרוע ביותר
זמן ריצה של אלגוריתם זה?

235
00:11:29,390 --> 00:11:31,050
קח שני.

236
00:11:31,050 --> 00:11:34,270
החלק הפנימי של הלולאה
פועל בזמן קבוע.

237
00:11:34,270 --> 00:11:37,510
והחלק החיצוני של
הלולאה הולכת לרוץ פעמים מ '.

238
00:11:37,510 --> 00:11:40,260
אז מה הגרוע ביותר של זמן הריצה כאן?

239
00:11:40,260 --> 00:11:43,210
האם אתה מניח שגדול-הו מ '?

240
00:11:43,210 --> 00:11:44,686
אתה רוצה להיות תקין.

241
00:11:44,686 --> 00:11:46,230
>> מה דעתך על עוד אחד?

242
00:11:46,230 --> 00:11:48,590
הפעם יש לנו
לולאה בתוך לולאה.

243
00:11:48,590 --> 00:11:50,905
יש לנו לולאה חיצונית
שיוצא מאפס לp.

244
00:11:50,905 --> 00:11:54,630
ויש לנו לולאה פנימית הפועלת
מאפס עד עמ ', ובתוך כך,

245
00:11:54,630 --> 00:11:57,890
אני קובע כי הגוף
לולאה פועלת בזמן קבוע.

246
00:11:57,890 --> 00:12:02,330
אז מה הגרוע ביותר של זמן הריצה
של קטע המסוים הזה של קוד?

247
00:12:02,330 --> 00:12:06,140
ובכן, שוב, יש לנו
לולאה חיצונית שפועלת פעמים עמ '.

248
00:12:06,140 --> 00:12:09,660
וכל איטרציה time--
של לולאה ש, ולא.

249
00:12:09,660 --> 00:12:13,170
יש לנו לולאה פנימית
שגם מפעיל פעמים עמ '.

250
00:12:13,170 --> 00:12:16,900
ואז בתוך כך, יש
קטע קבוע time-- קטן שם.

251
00:12:16,900 --> 00:12:19,890
>> אז אם יש לנו לולאה חיצונית ש
פועל פעמים עמ בתוכה הוא

252
00:12:19,890 --> 00:12:22,880
לולאה פנימית ש
פועל עמ times-- מה הוא

253
00:12:22,880 --> 00:12:26,480
במקרה הגרוע ביותר, זמן הריצה
של קטע הקוד הזה?

254
00:12:26,480 --> 00:12:30,730
האם אתה מניח שגדול-O של p בריבוע?

255
00:12:30,730 --> 00:12:31,690
>> אני דאג לויד.

256
00:12:31,690 --> 00:12:33,880
זה CS50.

257
00:12:33,880 --> 00:12:35,622