1
00:00:07,720 --> 00:00:10,950
[Powered by Google Translate] Siz yəqin ki, insanların sürətli və ya səmərəli alqoritm haqqında danışmaq duydum

2
00:00:10,950 --> 00:00:13,090
xüsusi tapşırığı yerinə ki,

3
00:00:13,090 --> 00:00:16,110
lakin bu sürətli və ya səmərəli olması üçün alqoritm üçün dəqiq nə deməkdir?

4
00:00:16,110 --> 00:00:18,580
Bəli, bu, real vaxt bir ölçü söhbət deyil

5
00:00:18,580 --> 00:00:20,500
saniyə və ya dəqiqə kimi.

6
00:00:20,500 --> 00:00:22,220
Çünki kompüter hardware

7
00:00:22,220 --> 00:00:24,260
və proqram kəskin dəyişir.

8
00:00:24,260 --> 00:00:26,020
Mənim proqram, sizin ləng run bilər

9
00:00:26,020 --> 00:00:28,000
Mən köhnə kompüter üzrə çalışan alıram çünki

10
00:00:28,000 --> 00:00:30,110
və ya bir online video oyun oynayan üçün baş, çünki

11
00:00:30,110 --> 00:00:32,670
eyni zamanda, bu, bütün yaddaş hogging olunur

12
00:00:32,670 --> 00:00:35,400
və ya müxtəlif proqram vasitəsilə mənim proqram çalışan bilər

13
00:00:35,400 --> 00:00:37,550
bir aşağı səviyyədə fərqli maşın ilə əlaqələndirir.

14
00:00:37,550 --> 00:00:39,650
Bu alma və portağal müqayisə kimi.

15
00:00:39,650 --> 00:00:41,940
Mənim yavaş kompüter uzun çəkir Məhz

16
00:00:41,940 --> 00:00:43,410
sizin cavab geri vermək çox

17
00:00:43,410 --> 00:00:45,510
Siz daha səmərəli alqoritm var demək deyil.

18
00:00:45,510 --> 00:00:48,830
>> Belə ki, biz birbaşa proqramları runtimes müqayisə bilməz ildən

19
00:00:48,830 --> 00:00:50,140
saniyə və ya dəqiqə,

20
00:00:50,140 --> 00:00:52,310
necə 2 müxtəlif alqoritmləri müqayisə yoxdur

21
00:00:52,310 --> 00:00:55,030
asılı olmayaraq, hardware və ya proqram ətraf mühit?

22
00:00:55,030 --> 00:00:58,000
Alqoritmik səmərəliliyinin qiymətləndirilməsi bir daha forma yol yaratmaq üçün

23
00:00:58,000 --> 00:01:00,360
kompüter alim və riyaziyyatçılar devised var

24
00:01:00,360 --> 00:01:03,830
bir proqram asimptotik mürəkkəblik ölçülməsi üçün anlayışlar

25
00:01:03,830 --> 00:01:06,110
və notation 'Big Ohnotation "adlı

26
00:01:06,110 --> 00:01:08,320
Bu təsvir.

27
00:01:08,320 --> 00:01:10,820
Rəsmi definition bir funksiyası f (x)

28
00:01:10,820 --> 00:01:13,390
g sifarişi (x) çalışır

29
00:01:13,390 --> 00:01:15,140
bəzi (x) dəyəri var, əgər x ₀ və

30
00:01:15,140 --> 00:01:17,630
bəzi daimi, C, üçün

31
00:01:17,630 --> 00:01:19,340
f (x)-dən az və ya bərabər

32
00:01:19,340 --> 00:01:21,230
ki, daimi dəfə g (x)

33
00:01:21,230 --> 00:01:23,190
x ₀ daha bütün x.

34
00:01:23,190 --> 00:01:25,290
>> Amma formal tərifi ilə üz qorxuram olmayın.

35
00:01:25,290 --> 00:01:28,020
Bu, həqiqətən, nəzəri baxımından az nə deməkdir?

36
00:01:28,020 --> 00:01:30,580
Bəli, bu əsasən təhlil yolu var

37
00:01:30,580 --> 00:01:33,580
bir proqramın iş asimptotik artır necə sürətli.

38
00:01:33,580 --> 00:01:37,170
Sizin vəsaitlərin həcmi sonsuzluğa doğru artır ki, edir

39
00:01:37,170 --> 00:01:41,390
söz, siz ölçüsü 10 bir sıra müqayisədə ölçüsü 1000 bir sıra çeşidlənməsi edirik.

40
00:01:41,390 --> 00:01:44,950
Sizin proqram iş necə inkişaf edir?

41
00:01:44,950 --> 00:01:47,390
Məsələn, simvol sayını hesablamaq təsəvvür

42
00:01:47,390 --> 00:01:49,350
simli ən sadə yolu

43
00:01:49,350 --> 00:01:51,620
 bütün cərgə ilə gəzinti ilə

44
00:01:51,620 --> 00:01:54,790
məktub-by-məktub və hər bir xarakter üçün counter 1 əlavə.

45
00:01:55,700 --> 00:01:58,420
Bu alqoritm Xətti zaman çalışır deyilir

46
00:01:58,420 --> 00:02:00,460
simvolların sayı ilə əlaqədar,

47
00:02:00,460 --> 00:02:02,670
Simli ildə 'n'.

48
00:02:02,670 --> 00:02:04,910
Qısa olaraq, O (n) çalışır.

49
00:02:05,570 --> 00:02:07,290
Niyə bu?

50
00:02:07,290 --> 00:02:09,539
Bəli, bu yanaşma istifadə edərək, zaman tələb

51
00:02:09,539 --> 00:02:11,300
bütün simli axır etmək

52
00:02:11,300 --> 00:02:13,920
simvolların sayını orantılıdır.

53
00:02:13,920 --> 00:02:16,480
20 xarakter string simvol sayı hesablanması

54
00:02:16,480 --> 00:02:18,580
edir kimi iki dəfə kimi uzun gedir

55
00:02:18,580 --> 00:02:20,330
10 xarakter string olan simvol saymaq,

56
00:02:20,330 --> 00:02:23,000
bütün simvol baxmaq, çünki

57
00:02:23,000 --> 00:02:25,740
və hər bir xarakter baxmaq eyni məbləği alır.

58
00:02:25,740 --> 00:02:28,050
Siz simvolların sayını artırmaq kimi,

59
00:02:28,050 --> 00:02:30,950
Runtime giriş uzunluğu xətti artacaq.

60
00:02:30,950 --> 00:02:33,500
>> Əgər xətti vaxt qərar varsa, təsəvvür

61
00:02:33,500 --> 00:02:36,390
O (n), yalnız kifayət qədər sürətli sizin üçün deyil?

62
00:02:36,390 --> 00:02:38,750
Bəlkə, böyük strings saxlanılması edirik

63
00:02:38,750 --> 00:02:40,450
və bunu görəcək əlavə vaxt ödəyə bilməz

64
00:02:40,450 --> 00:02:44,000
bir-bir hesablama onların simvol bütün axır etmək.

65
00:02:44,000 --> 00:02:46,650
Belə ki, fərqli bir cəhd qərar.

66
00:02:46,650 --> 00:02:49,270
Nə artıq simvolların sayını saxlamaq olur əgər

67
00:02:49,270 --> 00:02:52,690
simli ildə, 'len "adlı dəyişən, demək

68
00:02:52,690 --> 00:02:54,210
erkən proqram üzrə,

69
00:02:54,210 --> 00:02:57,800
Siz simli çox ilk xarakter saxlanılır əvvəl?

70
00:02:57,800 --> 00:02:59,980
Sonra bütün siz string uzunluğu tapmaq üçün indi nə etmək istiyorum

71
00:02:59,980 --> 00:03:02,570
dəyişən dəyəri nə kontrol edir.

72
00:03:02,570 --> 00:03:05,530
Siz, bütün simli özü baxmaq olmazdı

73
00:03:05,530 --> 00:03:08,160
və len kimi bir dəyişən dəyəri daxil hesab edilir

74
00:03:08,160 --> 00:03:11,100
bir asimptotik daimi dəfə əməliyyat,

75
00:03:11,100 --> 00:03:13,070
və ya O (1).

76
00:03:13,070 --> 00:03:17,110
Niyə bu? Yaxşı, asimptotik mürəkkəblik nə deməkdir xatırlayıram.

77
00:03:17,110 --> 00:03:19,100
Necə ölçüsü kimi iş dəyişiklik yoxdur

78
00:03:19,100 --> 00:03:21,400
Sizin giriş artır?

79
00:03:21,400 --> 00:03:24,630
>> Bir böyük simli simvol sayı almaq üçün çalışdıqlarını deyirlər.

80
00:03:24,630 --> 00:03:26,960
Bəli, bu, siz string etmək necə böyük məsələ deyil

81
00:03:26,960 --> 00:03:28,690
hətta bir milyon simvol uzun,

82
00:03:28,690 --> 00:03:31,150
bütün bu yanaşma ilə simli uzunluğu tapmaq üçün nə etmək istiyorum

83
00:03:31,150 --> 00:03:33,790
, dəyişən len dəyəri oxuyub üçün

84
00:03:33,790 --> 00:03:35,440
siz artıq təşkil edib.

85
00:03:35,440 --> 00:03:38,200
Ki, daxil uzunluğu tapa çalışdığınız simli uzunluğu,

86
00:03:38,200 --> 00:03:41,510
Proqram çalışır necə sürətli bütün təsir etmir.

87
00:03:41,510 --> 00:03:44,550
Proqram bu hissəsi bir xarakter string haqqında bərabər sürətli çalışır

88
00:03:44,550 --> 00:03:46,170
və min xarakter simli,

89
00:03:46,170 --> 00:03:49,140
Bu proqram sabit zaman çalışır kimi istinad olunacaq niyə və ki

90
00:03:49,140 --> 00:03:51,520
daxil ölçüsü ilə bağlı.

91
00:03:51,520 --> 00:03:53,920
>> Əlbəttə ki, bir günah yoxdur.

92
00:03:53,920 --> 00:03:55,710
Siz kompüter əlavə yaddaş alanı sərf

93
00:03:55,710 --> 00:03:57,380
dəyişən saxlanılması

94
00:03:57,380 --> 00:03:59,270
və sizi əlavə vaxt

95
00:03:59,270 --> 00:04:01,490
dəyişən faktiki storage etmək üçün,

96
00:04:01,490 --> 00:04:03,390
lakin baxımından hələ dayanır,

97
00:04:03,390 --> 00:04:05,060
sizin simli necə uzun tapmaq

98
00:04:05,060 --> 00:04:07,600
bütün simli müddəti asılı deyil.

99
00:04:07,600 --> 00:04:10,720
Belə ki, O (1) və ya daimi zaman çalışır.

100
00:04:10,720 --> 00:04:13,070
Bu, əlbəttə, demək yoxdur

101
00:04:13,070 --> 00:04:15,610
Sizin kodu, 1 addım çalışır

102
00:04:15,610 --> 00:04:17,470
amma nə qədər çox addımlar ki,

103
00:04:17,470 --> 00:04:20,019
bu vəsaitlərin ölçüsü dəyişə deyilsə,

104
00:04:20,019 --> 00:04:23,420
hələ biz O (1) kimi təmsil asimptotik daimi var.

105
00:04:23,420 --> 00:04:25,120
>> Yəqin ki, tapmaq kimi,

106
00:04:25,120 --> 00:04:27,940
ilə alqoritmlər ölçmək üçün bir çox müxtəlif böyük O runtimes var.

107
00:04:27,940 --> 00:04:32,980
O (n) ² alqoritmlər O (n) alqoritmlər çox asimptotik yavaş var.

108
00:04:32,980 --> 00:04:35,910
Elementlərinin sayı (n) artır ki, edir

109
00:04:35,910 --> 00:04:39,280
nəhayət O (n) ² alqoritmləri daha çox vaxt aparacaq

110
00:04:39,280 --> 00:04:41,000
O (n) alqoritmlər çalıştırmak üçün çox.

111
00:04:41,000 --> 00:04:43,960
Bu O (n) alqoritmlər həmişə daha sürətli run demək deyil

112
00:04:43,960 --> 00:04:46,410
O (n) ² alqoritmlərin çox, hətta eyni mühitdə,

113
00:04:46,410 --> 00:04:48,080
Eyni hardware.

114
00:04:48,080 --> 00:04:50,180
Bəlkə kiçik giriş ölçüləri üçün,

115
00:04:50,180 --> 00:04:52,900
 O (n) ² alqoritm əslində, daha sürətli iş bilər

116
00:04:52,900 --> 00:04:55,450
amma, nəhayət, giriş ölçüsü artırır

117
00:04:55,450 --> 00:04:58,760
sonsuzluğa doğru, O (n) ² alqoritm nin iş

118
00:04:58,760 --> 00:05:02,000
nəticədə O (n) alqoritmi Runtime geridə qoya edəcək.

119
00:05:02,000 --> 00:05:04,230
Hər hansı bir kvadrat riyazi funksiyası kimi

120
00:05:04,230 --> 00:05:06,510
 nəticədə hər linear function keçəcəyi təxmin edilir,

121
00:05:06,510 --> 00:05:09,200
nə qədər baş linear function başlamaq heç bir məsələ ilə off başlayır.

122
00:05:10,010 --> 00:05:12,000
Siz məlumatın böyük həcmdə iş edirsinizsə

123
00:05:12,000 --> 00:05:15,510
O çalışır ki, alqoritmlər (n) ² zaman, həqiqətən, proqram yavaşlatan başa bilər

124
00:05:15,510 --> 00:05:17,770
lakin kiçik giriş ölçüləri üçün,

125
00:05:17,770 --> 00:05:19,420
yəqin ki, qeyd belə deyil.

126
00:05:19,420 --> 00:05:21,280
>> Digər asimptotik mürəkkəblik edir

127
00:05:21,280 --> 00:05:24,420
logarithmic zaman, O (Giriş n).

128
00:05:24,420 --> 00:05:26,340
Tez bu çalışır ki, bir alqoritm nümunəsi

129
00:05:26,340 --> 00:05:29,060
, klassik ikili axtarış alqoritm edir

130
00:05:29,060 --> 00:05:31,850
elementlərinin artıq sıralaması siyahısında bir element tapmaq üçün.

131
00:05:31,850 --> 00:05:33,400
>> Siz ikili axtarış nə bilmirsinizsə,

132
00:05:33,400 --> 00:05:35,170
Mən, həqiqətən, tez sizin üçün izah edəcəyik.

133
00:05:35,170 --> 00:05:37,020
Deyək ki sayı 3 aradığınız demək

134
00:05:37,020 --> 00:05:40,200
integers bu sıra.

135
00:05:40,200 --> 00:05:42,140
Bu serialın orta element baxır

136
00:05:42,140 --> 00:05:46,830
və "Mən daha çox istədiyiniz element deyil, bərabər və ya bu az?" soruşur,

137
00:05:46,830 --> 00:05:49,150
O böyük, bərabər varsa. Siz element aşkar və siz tamamlayın.

138
00:05:49,150 --> 00:05:51,300
Daha çox varsa, onda siz element bilirik

139
00:05:51,300 --> 00:05:53,440
, serialın sağ tərəfində olmalıdır

140
00:05:53,440 --> 00:05:55,200
və yalnız gələcəkdə baxmaq olar

141
00:05:55,200 --> 00:05:57,690
bu kiçik varsa və sonra onu sol tərəfində olmalıdır bilirik.

142
00:05:57,690 --> 00:06:00,980
Bu proses sonra kiçik ölçülü array ilə təkrar olunur

143
00:06:00,980 --> 00:06:02,870
düzgün element aşkar qədər.

144
00:06:08,080 --> 00:06:11,670
>> Bu güclü alqoritmi hər əməliyyat yarısında array ölçüsü azalıb.

145
00:06:11,670 --> 00:06:14,080
Belə ki, ölçüsü 8-sıralanır array bir element tapmaq,

146
00:06:14,080 --> 00:06:16,170
ən çox (₂ 8 daxil)

147
00:06:16,170 --> 00:06:18,450
bu əməliyyatların və ya 3,

148
00:06:18,450 --> 00:06:22,260
orta element yoxlanılması, sonra yarısında array kəsmə, tələb olunacaq

149
00:06:22,260 --> 00:06:25,670
ölçüsü 16 bir sıra (₂ 16 daxil) alır, halbuki

150
00:06:25,670 --> 00:06:27,480
və ya 4 əməliyyatları.

151
00:06:27,480 --> 00:06:30,570
Bu yalnız bir iki dəfə ölçülü array üçün 1 daha əməliyyatı.

152
00:06:30,570 --> 00:06:32,220
Serialın ölçüsü katlama

153
00:06:32,220 --> 00:06:35,160
bu kodu yalnız 1 yığın tərəfindən uzunluğu artır.

154
00:06:35,160 --> 00:06:37,770
Yenə sonra bölünmə, siyahıda orta element yoxlanılması.

155
00:06:37,770 --> 00:06:40,440
Belə ki, o, logarithmic vaxt fəaliyyətə deyilir

156
00:06:40,440 --> 00:06:42,440
O (Giriş n).

157
00:06:42,440 --> 00:06:44,270
Lakin, demək, gözləyin

158
00:06:44,270 --> 00:06:47,510
siyahıda aradığınız element olduğu bu asılı deyil?

159
00:06:47,510 --> 00:06:50,090
Nə əgər baxmaq ilk element sağ olmaq olur?

160
00:06:50,090 --> 00:06:52,040
Sonra o, yalnız, 1 əməliyyat görür

161
00:06:52,040 --> 00:06:54,310
siyahısında nə qədər böyük olursa olsun.

162
00:06:54,310 --> 00:06:56,310
>> Kompüter alimləri daha baxımından niyə Yaxşı, ki

163
00:06:56,310 --> 00:06:58,770
ən yaxşı halda əks etdirən asimptotik mürəkkəbliyi üçün

164
00:06:58,770 --> 00:07:01,050
və ən pis halda bir alqoritm çıxışları.

165
00:07:01,050 --> 00:07:03,320
Daha düzgün, yuxarı və aşağı həddi

166
00:07:03,320 --> 00:07:05,090
Runtime haqqında.

167
00:07:05,090 --> 00:07:07,660
Binar axtarış üçün ən yaxşı halda, bizim element

168
00:07:07,660 --> 00:07:09,330
orada ortasında,

169
00:07:09,330 --> 00:07:11,770
və siz daimi vaxtında almaq

170
00:07:11,770 --> 00:07:14,240
serialın qalan nə qədər böyük olursa olsun.

171
00:07:15,360 --> 00:07:17,650
Bu istifadə rəmzi Ω edir.

172
00:07:17,650 --> 00:07:19,930
Belə ki, bu alqoritm Ω (1) çalışması edir.

173
00:07:19,930 --> 00:07:21,990
Ən yaxşı halda, o, tez element hesab

174
00:07:21,990 --> 00:07:24,200
serialın nə qədər böyük olursa olsun,

175
00:07:24,200 --> 00:07:26,050
amma ən pis halda,

176
00:07:26,050 --> 00:07:28,690
o (Giriş n) split çek çıxış edir

177
00:07:28,690 --> 00:07:31,030
serialın hüququ element tapa bilərsiniz.

178
00:07:31,030 --> 00:07:34,270
Ən pis halda yuxarı həddi artıq bilirəm ki, böyük "O" ilə aid edilir.

179
00:07:34,270 --> 00:07:38,080
Belə ki, O (Giriş n), lakin Ω (1) var.

180
00:07:38,080 --> 00:07:40,680
>> A xətti axtarış, əksinə,

181
00:07:40,680 --> 00:07:43,220
Siz array hər element vasitəsilə gəzmək olan

182
00:07:43,220 --> 00:07:45,170
istədiyiniz tapmaq,

183
00:07:45,170 --> 00:07:47,420
yaxşı Ω (1) edir.

184
00:07:47,420 --> 00:07:49,430
Yenə ilk element istədiyiniz.

185
00:07:49,430 --> 00:07:51,930
Belə ki, serialın nə qədər böyük əhəmiyyətli deyil.

186
00:07:51,930 --> 00:07:54,840
Ən pis halda, serialın son element var.

187
00:07:54,840 --> 00:07:58,560
Belə ki, siz tapmaq üçün array bütün n elementləri vasitəsilə gəzmək üçün

188
00:07:58,560 --> 00:08:02,170
siz 3 axtarır, əgər istəyirəm.

189
00:08:04,320 --> 00:08:06,030
Belə ki, O (n) zaman çalışır

190
00:08:06,030 --> 00:08:09,330
bu sıra elementlərinin sayına mütənasib hissəsi çünki.

191
00:08:10,800 --> 00:08:12,830
>> Istifadə daha bir simvolu Θ edir.

192
00:08:12,830 --> 00:08:15,820
Bu harada ən yaxşı və ən pis halda alqoritmlər təsvir etmək üçün istifadə edilə bilər

193
00:08:15,820 --> 00:08:17,440
eynidir.

194
00:08:17,440 --> 00:08:20,390
Bu əvvəllər danışdı string uzunluğu alqoritmlər olduğu.

195
00:08:20,390 --> 00:08:22,780
Biz əvvəl bir dəyişən bu saxlamaq əgər ki,

196
00:08:22,780 --> 00:08:25,160
biz simli saxlamaq və sonra sabit zaman daxil.

197
00:08:25,160 --> 00:08:27,920
Nə sayı olmayaraq

198
00:08:27,920 --> 00:08:30,130
biz dəyişən saxlanılması edirik, biz baxmaq lazımdır.

199
00:08:33,110 --> 00:08:35,110
Ən yaxşı halda, biz baxmaq

200
00:08:35,110 --> 00:08:37,120
və simli uzunluğu tapa bilərsiniz.

201
00:08:37,120 --> 00:08:39,799
Ω (1) və ya ən yaxşı halda daimi vaxt belə.

202
00:08:39,799 --> 00:08:41,059
Ən pis halda ki,

203
00:08:41,059 --> 00:08:43,400
biz baxmaq və simli uzunluğu tapa bilərsiniz.

204
00:08:43,400 --> 00:08:47,300
Belə ki, O (1) və ya ən pis halda daimi vaxt.

205
00:08:47,300 --> 00:08:49,180
Belə ki, ən yaxşı halda və ən pis hallarda ildən, eyni

206
00:08:49,180 --> 00:08:52,520
bu Θ (1) vaxt run deyilə bilər.

207
00:08:54,550 --> 00:08:57,010
>> Beləliklə, biz kodları səmərəliliyi haqqında səbəbdən yaxşı yolu var

208
00:08:57,010 --> 00:09:00,110
onlar run etmək üçün real dünya vaxt haqqında heç bir şey bilmədən,

209
00:09:00,110 --> 00:09:02,270
ki, kənar amillər çox təsir edir

210
00:09:02,270 --> 00:09:04,190
müxtəlif hardware, proqram, o cümlədən

211
00:09:04,190 --> 00:09:06,040
və ya kodu xüsusiyyətləri.

212
00:09:06,040 --> 00:09:08,380
Həmçinin, bu, bizə nə olacaq haqqında Səbəb imkan verir

213
00:09:08,380 --> 00:09:10,180
zaman giriş artır ölçüsü.

214
00:09:10,180 --> 00:09:12,490
>> Ey (n) ² alqoritmi, çalışan istəyirsinizsə

215
00:09:12,490 --> 00:09:15,240
və ya pis bir O (2 ⁿ) alqoritmi,

216
00:09:15,240 --> 00:09:17,170
ən sürətlə inkişaf edən növlərindən biridir,

217
00:09:17,170 --> 00:09:19,140
həqiqətən azalması qeyd başlamaq lazımdır

218
00:09:19,140 --> 00:09:21,220
siz məlumatın böyük məbləğlər ilə iş başlamaq zaman.

219
00:09:21,220 --> 00:09:23,590
>> Bu asimptotik mürəkkəblik var. Thanks.