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
>> Такім чынам, паколькі мы не можам напрамую параўнаць час працы праграмы

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
працуе на парадак д (х)

29
00:01:13,390 --> 00:01:15,140
калі існуе некаторы (х) значэнні х і ₀

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
што пастаяннае разы д (х)

33
00:01:21,230 --> 00:01:23,190
для ўсіх х больш х ₀.

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
'N' у радку.

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
Аб (п), проста не быў досыць хуткі для Вас?

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
і доступу да значэння зменнай, як лён лічыцца

74
00:03:08,160 --> 00:03:11,100
асімптатычна пастаяннае час аперацыі,

75
00:03:11,100 --> 00:03:13,070
або O (1).

76
00:03:13,070 --> 00:03:17,110
Чаму гэта адбываецца? Ну, памятаеце, што асімптатычнай складанасць азначае.

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
, Каб зачытаць значэнне зменнай даўжыня,

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
яна па-ранейшаму асімптатычна сталым, якую мы ўяўляем, як O (1).

105
00:04:23,420 --> 00:04:25,120
>> Як вы можаце здагадацца,

106
00:04:25,120 --> 00:04:27,940
Ёсць шмат розных вялікіх O вымераць час аўтаномнай працы алгарытмаў.

107
00:04:27,940 --> 00:04:32,980
Аб (п) ² алгарытмы асімптатычна павольней, чым O (N) алгарытмаў.

108
00:04:32,980 --> 00:04:35,910
Гэта значыць, як лік элементаў (N) расце,

109
00:04:35,910 --> 00:04:39,280
у канчатковым выніку O (п) ² алгарытмаў зойме больш часу

110
00:04:39,280 --> 00:04:41,000
чым O (N) алгарытмы для запуску.

111
00:04:41,000 --> 00:04:43,960
Гэта не азначае, O (п) алгарытмы заўсёды працаваць хутчэй

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
 Аб (п) ² алгарытм можа на самай справе працаваць хутчэй,

116
00:04:52,900 --> 00:04:55,450
але, у рэшце рэшт, у якасці ўваходных памер павялічваецца

117
00:04:55,450 --> 00:04:58,760
да бясконцасці, Аб (п) ² алгарытму выканання

118
00:04:58,760 --> 00:05:02,000
у канчатковым выніку зацямніць час працы O (п) алгарытм.

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 (п) ² Час сапраўды можа ў канчатковым выніку запавольвае працу праграмы,

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 (часопіс N).

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 (часопіс N).

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
ён павінен выканаць (§ п) раскол праверкі

177
00:07:28,690 --> 00:07:31,030
масіва, каб знайсці правільны элемент.

178
00:07:31,030 --> 00:07:34,270
Горшы верхняй мяжы называюць з вялікай "О", што вы ўжо ведаеце.

179
00:07:34,270 --> 00:07:38,080
Такім чынам, гэта O (часопіс N), але Ω (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
Такім чынам, вы павінны ісці праз усе п элементаў у масіве, каб знайсці яго,

188
00:07:58,560 --> 00:08:02,170
Напрыклад, калі вы шукалі 3.

189
00:08:04,320 --> 00:08:06,030
Такім чынам, ён працуе ў O (п)

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 (п) ² алгарытм,

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
>> Вось асімптатычнай складанасці. Дзякуй.