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
هنگامی که ما در مورد پیچیدگی صحبت
الگوریتم که گاهی اوقات شما

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
بزرگ امگا برای بهترین حالت.

47
00:02:18,880 --> 00:02:21,319
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
اگر ما یک الگوریتم،
فرآیندهای Strings-- ما احتمالا

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
>> در حال حاضر، ما می توانیم یک اندازه گیری
الگوریتم به طور خاص،

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-- و یا مگابایت رم

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
>> در حال حاضر، ما در واقع نمی
در مورد آنچه از از n است که دقیقا.

84
00:04:10,030 --> 00:04:13,700
در واقع، ما بسیار به ندرت will--
قطعا هرگز در این class-- من

85
00:04:13,700 --> 00:04:18,709
شیرجه رفتن به هر واقعا عمیق
تجزیه و تحلیل آنچه از از 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 نفر واحد از منابع

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
و بنابراین به عنوان n بزرگتر می شود
و بزرگتر و 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
که است که اگر شما دو نفر، آن
طول می کشد دو برابر تعدادی از مراحل.

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 log n است.

162
00:08:06,622 --> 00:08:08,330
و ما به عنوان مثال
از یک الگوریتم است که

163
00:08:08,330 --> 00:08:13,370
اجرا می شود در n log n استفاده، که هنوز هم بهتر
از time-- درجه دوم N مربع.

164
00:08:13,370 --> 00:08:17,320
یا زمان چند جمله ای، N دو
هر تعداد بیشتر از دو.

165
00:08:17,320 --> 00:08:20,810
و یا زمان نمایی که
حتی worse-- C به 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 به قدرت 1000 است.

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--
یا دو مثال here--

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-- که
ما قبل از به عنوان well-- دیده ام

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
شما باید برای به دست آوردن، دریافت B، اضافه کردن
آنها را با هم، خروجی نتیجه.

204
00:09:59,240 --> 00:10:02,900
به طوری که یک الگوریتم زمان ثابت است.

205
00:10:02,900 --> 00:10:05,170
>> در اینجا یک مثال از یک است
الگوریتم زمان خطی

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
بنابراین با استفاده از اصطلاحات که
ما در حال حاضر about-- چه صحبت

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
آیا شما حدس می زنم بزرگ-O از M؟

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
ما یک حلقه بیرونی
اجرا می شود که از صفر تا ص

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
ما یک حلقه داخلی
که بار P نیز اجرا می شود.

250
00:12:13,170 --> 00:12:16,900
و سپس در داخل از آن، وجود دارد را
ثابت قطعه کمی time-- وجود دارد.

251
00:12:16,900 --> 00:12:19,890
>> بنابراین اگر ما یک حلقه بیرونی که
P بار که در داخل آن است اجرا می شود

252
00:12:19,890 --> 00:12:22,880
یک حلقه درونی که
P 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