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
オーダーg（x）の上で動作する

29
00:01:13,390 --> 00:01:15,140
いくつかの（x）の値が存在する場合は、x₀と

30
00:01:15,140 --> 00:01:17,630
いくつかの定数A、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
発言は、サイズ10の配列と比較して、サイ​​ズ1000の配列をソートしています。

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
それが取るように2倍の時間がかかるために起こっている

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
文字列で、 'は、len'という変数に、言う

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
漸近的に一定時間操作、

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
、変数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
あなたのプログラムのこの部分は、1文字の文字列でも同じように速く走るでしょう

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）の²のアルゴリズムは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
（n）は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（log 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
Let 'sは、あなたが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 log）が最大で、

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
配列のサイズを2倍に

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（log 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
あなたが見て最初の要素は右に1であることを起こる場合は？

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
それは（log n）のスプリット·チェックを実行する必要があります

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（log 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
だから、あなたは、それを見つけるために、アレイ内のすべての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
>> それは漸近複雑だ。ありがとうございます。