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--時にはあなた'LL

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
だから、このアルゴリズムは、に言ったことがあります
乗n個のNまたはOのOで実行されます。

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
>> 今、我々は測定することができます
特に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
そして、我々はこれを呼び出すことができます
n個のfを、任意に、測定します。

80
00:03:56,200 --> 00:03:59,420
nが数である場合、
データセット内の要素。

81
00:03:59,420 --> 00:04:02,640
そして、n個のfが何代です。

82
00:04:02,640 --> 00:04:07,530
どのように多くのリソースの単位ありません
そのデータを処理するために必要とします。

83
00:04:07,530 --> 00:04:10,030
>> 今、私たちは実際には気にしません
ちょうどnのFものですについて。

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
我々はかかる第2のアルゴリズムを持っています
乗プラスの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
そこに第3のアルゴリズム
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
第3のアルゴリズム
より効率的になります。

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
そして、第2のアルゴリズムがで実行されます
億100万ステップ。

124
00:06:17,880 --> 00:06:20,870
そして、第3のアルゴリズムが実行されます
億ステップのちょうど内気インチ

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
データ入力は、サイズAである場合
million--これらの3つのすべてのほとんどを

129
00:06:31,240 --> 00:06:34,960
場合は、1つ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個のオーダーであるとして
キューブまたはn個の立方体のビッグO。

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
彼らは、常に1つの動作を取りますか
に対処するためのリソースの1単位。

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
あなたはN二重かどうかは、どちらが
ステップ数の2倍になります。

158
00:07:53,030 --> 00:07:55,980
あなたは、nを3倍にする場合は、とり
ステップ数を3倍に。

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、で実行されます
二次time--よりN乗。

164
00:08:13,370 --> 00:08:17,320
あるいは多項式時間、N 2
2より大きい任意の数。

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--があるかどうか
データ入力は、サイズ1000であり、

168
00:08:28,990 --> 00:08:31,310
それは第千パワーにCを取るだろう。

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と呼ばれます
サイズ千の配列を受け取ります。

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
常にわずか4を返します。

192
00:09:30,820 --> 00:09:32,940
だから、そのアルゴリズム、
それという事実にもかかわらず、

193
00:09:32,940 --> 00:09:35,840
千の要素を取りません
彼らと何を行います。

194
00:09:35,840 --> 00:09:36,590
ただ、4を返します。

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
ちょうど2つの整数を処理します。

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
あなたが得る、あなたはBを取得し、あなたがそれらを追加
一緒に、あなたの出力結果。

201
00:09:50,780 --> 00:09:53,270
だから、84ステップです。

202
00:09:53,270 --> 00:09:55,510
しかし、それは、常に一定です
かかわらず、またはBの。

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
>> ここでの例です
線形時間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
私たちは、1つ以上の要素を追加します
アレイは、それはもう一つのステップを取ります。

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
との外側部分
ループがm回実行しようとしています。

238
00:11:37,510 --> 00:11:40,260
そこでここでは、最悪の場合の実行時間は何ですか？

239
00:11:40,260 --> 00:11:43,210
あなたはメートルのビッグOを推測しましたか？

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
そして、我々は実行され、内側のループを持っています
ゼロからpまで、その内、

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
さて、もう一度、私たちは持っています
p回を実行します外側のループ。

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
その内側のループ
何であるかtimes-- Pを実行します

253
00:12:22,880 --> 00:12:26,480
最悪の場合の実行時間
このコードのスニペットの？

254
00:12:26,480 --> 00:12:30,730
あなたは、pのビッグOの二乗と思いましたか？

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