1
00:00:00,000 --> 00:00:11,100
>> [音楽再生]

2
00:00:11,100 --> 00:00:11,490
>> DAVID J.マラン：すべての権利。

3
00:00:11,490 --> 00:00:12,170
だから戻って歓迎します。

4
00:00:12,170 --> 00:00:15,180
これは、CS50であり、である
週3の終わり。

5
00:00:15,180 --> 00:00:17,770
>> だから、過去数週間でリコール
我々はかなりの出費してきた

6
00:00:17,770 --> 00:00:20,820
Cで、プログラミングの、構文上の時間。

7
00:00:20,820 --> 00:00:24,680
もしまだなら、それは、かなり普通のこと
であるためには、問題のセット2に苦しんで

8
00:00:24,680 --> 00:00:25,950
壁に頭を強打。

9
00:00:25,950 --> 00:00:28,310
それは不可解に見えるエラーメッセージだ
あなたこととバグ

10
00:00:28,310 --> 00:00:29,220
かなり追いかけることはできません。

11
00:00:29,220 --> 00:00:32,310
なぜなら、安心、という点で、まさに
数週間の時間あなたに戻って見てみましょう

12
00:00:32,310 --> 00:00:35,930
カエサルのようなもの、と[？ V-genair、？]
多分キズ、

13
00:00:35,930 --> 00:00:40,050
あなたが来てどれだけ遠くに実現
短時間である。

14
00:00:40,050 --> 00:00:43,670
それはどんな慰めだのであれば、
今のところそこにハングアップ。

15
00:00:43,670 --> 00:00:46,610
>> 今日は、しかし、我々は移行し始める
ものより高いレベルに。

16
00:00:46,610 --> 00:00:49,820
そして、私たちは当たり前のように始めること
君たちは、プログラムする方法を知っている、またはで

17
00:00:49,820 --> 00:00:52,090
少なくとも始まりの
その快適さのレベル。

18
00:00:52,090 --> 00:00:56,520
そして、我々はどのように我々ができる考​​慮することから始めましょう
複数のプログラムを設計に取り掛かる

19
00:00:56,520 --> 00:00:57,440
効果的に。

20
00:00:57,440 --> 00:01:01,090
私たちは、最適化に取り掛かることができますか
我々のアルゴリズムの効率化、

21
00:01:01,090 --> 00:01:03,110
一般的に、よりを解く
興味深い問題。

22
00:01:03,110 --> 00:01:06,850
と、という当たり前のように開始
我々がしたい場合、我々は、任意のをコーディングすることができ

23
00:01:06,850 --> 00:01:08,350
我々は心を持っている例。

24
00:01:08,350 --> 00:01:11,430
今日のように、我々は、キーボードに触れないでください
コー​​ドの任意の形式のために。

25
00:01:11,430 --> 00:01:15,150
これは、はるかに高いレベルにあり、よ
最終的には、問題解決について。

26
00:01:15,150 --> 00:01:20,490
>> だから、その点に到達するために、私が提案してみましょう
その次の7つの

27
00:01:20,490 --> 00:01:24,290
長方形は後ろ、7扉を表す
の全体の束である

28
00:01:24,290 --> 00:01:26,340
数字は、その中に数50です。

29
00:01:26,340 --> 00:01:30,470
私は、この上でこれを投影してみましょう
同様にここに画面が表示されます。

30
00:01:30,470 --> 00:01:36,770
そして、我々はにボランティアを必要とすることを提案する
私の前の数字を見つけるのを助ける

31
00:01:36,770 --> 00:01:38,140
見るためにここにインターネット。

32
00:01:38,140 --> 00:01:40,755
ピンクで、上昇に来る。

33
00:01:40,755 --> 00:01:43,050
わかりました。

34
00:01:43,050 --> 00:01:43,930
あなたの名前は？

35
00:01:43,930 --> 00:01:44,850
>> JENNIFER：[聞こえない]

36
00:01:44,850 --> 00:01:45,170
>> DAVID J.マラン：申し訳ありませんが？

37
00:01:45,170 --> 00:01:45,860
>> JENNIFER：ジェニファー。

38
00:01:45,860 --> 00:01:46,390
>> DAVID J.マラン：ジェニファー。

39
00:01:46,390 --> 00:01:46,980
すべての権利、ジェニファー。

40
00:01:46,980 --> 00:01:47,630
よろしくね。

41
00:01:47,630 --> 00:01:48,370
までさあ。

42
00:01:48,370 --> 00:01:52,430
したがって、これらはここで7の扉であり、どのような
私はあなたがここに私たちのためにやりたい、

43
00:01:52,430 --> 00:01:56,560
クラスメートのすべての前に、
私達に数、50を見つけることです。

44
00:01:56,560 --> 00:02:00,860
番号を見つけるためには、後ろにのぞくことができます
単にタップして、これらのドアのいずれか

45
00:02:00,860 --> 00:02:03,030
扉の1つに、それ
その番号を明らかにする。

46
00:02:03,030 --> 00:02:06,080
そして、どのように迅速に見てみましょう
私達に数、50を見つけることができます。

47
00:02:06,080 --> 00:02:09,979

48
00:02:09,979 --> 00:02:11,229
>> 15。

49
00:02:11,229 --> 00:02:13,110

50
00:02:13,110 --> 00:02:14,360
16。

51
00:02:14,360 --> 00:02:16,270

52
00:02:16,270 --> 00:02:16,530
50。

53
00:02:16,530 --> 00:02:17,350
うまく行って。

54
00:02:17,350 --> 00:02:18,040
わかりました。

55
00:02:18,040 --> 00:02:19,906
ジェニファーのために拍手。

56
00:02:19,906 --> 00:02:21,530
>> [拍手]

57
00:02:21,530 --> 00:02:22,320
>> わかりました。

58
00:02:22,320 --> 00:02:25,254
だから、あなたのための戦略は何だった
、50の番号を見つける？

59
00:02:25,254 --> 00:02:27,222
>> JENNIFER：うーん、私は多分あればと思った - 

60
00:02:27,222 --> 00:02:27,714
[聞こえない]

61
00:02:27,714 --> 00:02:28,206
>> DAVID J.マラン：ああ。

62
00:02:28,206 --> 00:02:29,630
それを一秒を与える。

63
00:02:29,630 --> 00:02:32,420
だから、あなたのための作戦のようだった
、50の番号を見つける？

64
00:02:32,420 --> 00:02:34,760
>> JENNIFER：だから私はちょうどで始まる
見始めて何を最初の番号

65
00:02:34,760 --> 00:02:38,590
多分あれば、あった、そして私は思った
それらをソートしている、私はしておこう

66
00:02:38,590 --> 00:02:39,970
上位にタップ？

67
00:02:39,970 --> 00:02:40,140
>> DAVID J.マラン：OK。

68
00:02:40,140 --> 00:02:42,910
そして、私たちは発見したように見える
このケースのように。

69
00:02:42,910 --> 00:02:45,670
が、裏のレイヤーをしてみましょう
少しだけ、あなたが行きたい

70
00:02:45,670 --> 00:02:47,640
先に他のドアを明かす
あなたが選択しただろうか？

71
00:02:47,640 --> 00:02:50,400

72
00:02:50,400 --> 00:02:51,712
>> JENNIFER：ああ、親愛なる。

73
00:02:51,712 --> 00:02:53,128
>> DAVID J.マラン：ああ。

74
00:02:53,128 --> 00:02:54,280
>> JENNIFER：だから私はただ幸運。

75
00:02:54,280 --> 00:02:55,270
>> DAVID J.マラン：だからあなたは幸運。

76
00:02:55,270 --> 00:02:55,710
わかりました。

77
00:02:55,710 --> 00:02:56,795
そんなに悪くない。

78
00:02:56,795 --> 00:02:58,750
しかし、それは興味深い
洞察力、右？

79
00:02:58,750 --> 00:03:01,870
あなたが想定し、あなたは手に入れた場合は、
そこに確かに、ちょっとラッキー。

80
00:03:01,870 --> 00:03:05,350
しかし、あなたは数字があったと仮定した場合
ソートされた、あなたは、より正確にすることができます

81
00:03:05,350 --> 00:03:08,750
それが影響を受けた方法として
あなたの行動？

82
00:03:08,750 --> 00:03:11,715
>> JENNIFER：だから彼らがソートされた場合、I
小さい方から大きい方へ多分思った。

83
00:03:11,715 --> 00:03:11,970
>> DAVID J.マラン：OK。

84
00:03:11,970 --> 00:03:15,260
>> JENNIFER：それともこれが終わった場合であること
最小にその後最大、本当に大きい。

85
00:03:15,260 --> 00:03:15,540
>> DAVID J.マラン：OK。

86
00:03:15,540 --> 00:03:18,170
だから最小に最大、または
小さい方から大きい方へ。

87
00:03:18,170 --> 00:03:21,990
しかし、あなたが持っていたと仮定し、私は提案してみましょう
不運得、そして彼らと仮定

88
00:03:21,990 --> 00:03:26,840
、実際には、並べ替えられていなかった、どのように多くの
あなたは覗きにそれらの扉を持っていたかもしれない

89
00:03:26,840 --> 00:03:28,590
その最悪の場合には後ろに？

90
00:03:28,590 --> 00:03:29,860
>> JENNIFER：それらのすべて。

91
00:03:29,860 --> 00:03:30,420
>> DAVID J.マラン：それらのすべて。

92
00:03:30,420 --> 00:03:31,740
それでは、nとそれを一般化することができます。

93
00:03:31,740 --> 00:03:34,790
そこに7であることを起こるが、レッツより
一般にn個のドアがあると言う

94
00:03:34,790 --> 00:03:35,650
ここに画面が表示されます。

95
00:03:35,650 --> 00:03:40,110
だから、最悪の場合には、あなたが持っているでしょう
7ドア、またはnドアの後ろに見えるように。

96
00:03:40,110 --> 00:03:44,140
そしてこれは実際にそれがのビットです、です
運は、今日、それは本当に線形だ

97
00:03:44,140 --> 00:03:46,440
ある種のアルゴリズム、たとえあなた
周りのスキップの親切でした。

98
00:03:46,440 --> 00:03:47,080
その公正ですか？

99
00:03:47,080 --> 00:03:47,500
>> JENNIFER：うん。

100
00:03:47,500 --> 00:03:50,000
>> DAVID J.マラン：まあ、私はあなたの場合を見てみましょう
私は私たちに移動する場合の戦略の変化

101
00:03:50,000 --> 00:03:52,190
ここで私たちの第二の例
7種類のドア。

102
00:03:52,190 --> 00:03:55,240
同じ数字が、この
時間は、それらが並べ替えられています。

103
00:03:55,240 --> 00:03:58,350
になるだろうここにあなたの戦略は何ですか
あなたの心の外に置くことをしようとして何

104
00:03:58,350 --> 00:03:59,310
他の番号であった - 

105
00:03:59,310 --> 00:03:59,930
>> JENNIFER：OK。

106
00:03:59,930 --> 00:04:02,290
>> DAVID J.マラン： - 以前の？

107
00:04:02,290 --> 00:04:03,180
>> JENNIFER：レッツスタート
最初のものである。

108
00:04:03,180 --> 00:04:03,540
>> DAVID J.マラン：すべての権利。

109
00:04:03,540 --> 00:04:05,190
最初の1で始まる。

110
00:04:05,190 --> 00:04:05,960
4。

111
00:04:05,960 --> 00:04:08,810
今、どこに行くつもり、なぜ？

112
00:04:08,810 --> 00:04:10,040
>> JENNIFER：4は本当に小さいです。

113
00:04:10,040 --> 00:04:12,500
彼らはソート多分最小いるのであれば
最大にするには、すべき

114
00:04:12,500 --> 00:04:13,290
 - 二度あること、となる。

115
00:04:13,290 --> 00:04:13,670
>> DAVID J.マラン：OK。

116
00:04:13,670 --> 00:04:15,990
あなたが考えている、見てみましょう？

117
00:04:15,990 --> 00:04:19,050
>> JENNIFER：最後の1をお試しください。

118
00:04:19,050 --> 00:04:19,500
ニース。

119
00:04:19,500 --> 00:04:20,880
>> DAVID J.マラン：非常にうまくやった。

120
00:04:20,880 --> 00:04:21,860
わかりました。

121
00:04:21,860 --> 00:04:23,010
>> [拍手]

122
00:04:23,010 --> 00:04:24,310
>> DAVID J.マラン：OK。

123
00:04:24,310 --> 00:04:26,790
だから、実際にこれをやっている
恐ろしく、あなただから

124
00:04:26,790 --> 00:04:27,700
非常によくそれをやって。

125
00:04:27,700 --> 00:04:31,150
どちらにできない私たちを残し
特定のポイントを作る。

126
00:04:31,150 --> 00:04:32,565
だからここにロールバックしてみましょう。

127
00:04:32,565 --> 00:04:34,560
>> JENNIFER：OK。

128
00:04:34,560 --> 00:04:35,980
>> DAVID J.マラン：非常によく
それにもかかわらず、行って。

129
00:04:35,980 --> 00:04:39,060
だから、初めに開始
それは、その後、あなた4だったことを見た

130
00:04:39,060 --> 00:04:40,240
最後に移動。

131
00:04:40,240 --> 00:04:42,320
しかし、あなたは幸運取得していないと仮定し
、そこにあるとし50

132
00:04:42,320 --> 00:04:42,890
どこか別の場所だった。

133
00:04:42,890 --> 00:04:46,190
何があなたの第三段階であった？

134
00:04:46,190 --> 00:04:47,680
>> JENNIFER：先頭に戻ります。

135
00:04:47,680 --> 00:04:48,320
>> DAVID J.マラン：戻る
先頭に。

136
00:04:48,320 --> 00:04:51,320
[OK]を、ので、あなたが触れただろう
8だったこのドア、。

137
00:04:51,320 --> 00:04:51,660
わかりました。

138
00:04:51,660 --> 00:04:52,650
だから、50ではありません。

139
00:04:52,650 --> 00:04:55,380
どこで次のを見たでしょう？

140
00:04:55,380 --> 00:04:56,720
>> JENNIFER：私はしませんでした場合
それらがソートを知っています。

141
00:04:56,720 --> 00:04:57,005
>> DAVID J.マラン：正しい。

142
00:04:57,005 --> 00:04:58,490
さて、あなたはやったかどうかを知る
それらはソートされた - 

143
00:04:58,490 --> 00:04:58,700
>> JENNIFER：ああ、ええ、知っていた。

144
00:04:58,700 --> 00:05:00,910
>> DAVID J.マラン： - しかし、あなたはしませんでした
50はまだだったどこに知っていますか？

145
00:05:00,910 --> 00:05:01,785
>> JENNIFER：ちょうど続ける。

146
00:05:01,785 --> 00:05:02,130
>> DAVID J.マラン：すべての権利。

147
00:05:02,130 --> 00:05:02,520
OK。

148
00:05:02,520 --> 00:05:03,800
続ける。

149
00:05:03,800 --> 00:05:05,270
OK、その私が扱うことができます。

150
00:05:05,270 --> 00:05:05,610
>> JENNIFER：OK。

151
00:05:05,610 --> 00:05:07,210
>> DAVID J.マラン：今、あなただけなら
続けるために行く、あなたは何ですか

152
00:05:07,210 --> 00:05:09,680
にバックアップ委譲アルゴリズム。

153
00:05:09,680 --> 00:05:10,740
>> JENNIFER：リニア - 。

154
00:05:10,740 --> 00:05:11,820
>> DAVID J.マラン：それは線形の一種である。

155
00:05:11,820 --> 00:05:13,480
しかしせ、私が提案してみましょう
私はその場に置く。

156
00:05:13,480 --> 00:05:14,900
私はページをリフレッシュしてみましょう。

157
00:05:14,900 --> 00:05:17,120
同じ番号、同じ配列、
同じドア。

158
00:05:17,120 --> 00:05:21,350
しかしのその最初の日に戻ると思います
我々は電話帳を引き裂いたクラス

159
00:05:21,350 --> 00:05:25,480
半分、のソート、何だった
そこに私たちの戦略？

160
00:05:25,480 --> 00:05:26,450
>> JENNIFER：中央にスタート。

161
00:05:26,450 --> 00:05:26,690
>> DAVID J.マラン：OK。

162
00:05:26,690 --> 00:05:27,610
だから途中から始まります。

163
00:05:27,610 --> 00:05:28,790
それでは、先に行くとそれをシミュレートしてみましょう。

164
00:05:28,790 --> 00:05:30,720
半ばまでに開始
そのドアを明らかに。

165
00:05:30,720 --> 00:05:31,660
だから数16。

166
00:05:31,660 --> 00:05:35,290
だから強い男は何をしただろう、
誰が、半分に電話帳を引き裂いた

167
00:05:35,290 --> 00:05:38,450
次の推測に取得するには？

168
00:05:38,450 --> 00:05:39,400
>> JENNIFER：この半分に移動します。

169
00:05:39,400 --> 00:05:41,700
>> DAVID J.マラン：なぜ右に？

170
00:05:41,700 --> 00:05:43,900
>> JENNIFER：彼らは最小の一種だったら
最大にし、50は次のようになります

171
00:05:43,900 --> 00:05:44,720
その終わりに。

172
00:05:44,720 --> 00:05:44,920
>> DAVID J.マラン：良い。

173
00:05:44,920 --> 00:05:45,390
完全に合理的。

174
00:05:45,390 --> 00:05:48,380
だから、電話帳のように、あなたがに行く
右、左とは対照的に、ここで

175
00:05:48,380 --> 00:05:49,500
キー持ち帰りです。

176
00:05:49,500 --> 00:05:53,930
これで、捨てる、またははがすことができます
この問題の半分は、あなたをしないまま

177
00:05:53,930 --> 00:05:55,970
7ドア付きますが、本当にただ3。

178
00:05:55,970 --> 00:05:57,870
の約半分である
問題の大きさ。

179
00:05:57,870 --> 00:05:58,350
わかりました。

180
00:05:58,350 --> 00:06:01,890
だから今、あなたが持っている何
あなたが右に行く後に行う？

181
00:06:01,890 --> 00:06:05,870
>> JENNIFER：だから16は、まだかなり小さいです
50に対してので、多分私は、試してみます

182
00:06:05,870 --> 00:06:06,700
このいずれか、のような。

183
00:06:06,700 --> 00:06:07,890
>> DAVID J.マラン：すべての権利。

184
00:06:07,890 --> 00:06:08,720
42。

185
00:06:08,720 --> 00:06:10,830
ので、今大丈夫、あなたは何ですか
本能はあなたを伝える？

186
00:06:10,830 --> 00:06:12,100
>> JENNIFER：私は捨てることができます
この後、ただ - 

187
00:06:12,100 --> 00:06:12,360
>> DAVID J.マラン：OK。

188
00:06:12,360 --> 00:06:14,212
良い、あなたは離れて投げることができる
そこに左半分。

189
00:06:14,212 --> 00:06:14,890
>> JENNIFER： - この一つを選ぶ。

190
00:06:14,890 --> 00:06:15,530
>> DAVID J.マラン：そして右。

191
00:06:15,530 --> 00:06:15,760
>> JENNIFER：うん。

192
00:06:15,760 --> 00:06:17,820
>> DAVID J.マラン：だからそれが難しい場合でも、
のみがあるときは、おそらく見て

193
00:06:17,820 --> 00:06:21,320
7ドア、今、考える、
の一貫性

194
00:06:21,320 --> 00:06:22,620
あなただけ適用されたアルゴリズム。

195
00:06:22,620 --> 00:06:24,510
以前のケースでは、あなたがした
偉大だった、幸運を得る。

196
00:06:24,510 --> 00:06:26,540
しかし、あなたは、ヒューリスティックを使用していたのか
私は言うでしょう。

197
00:06:26,540 --> 00:06:29,150
あなたの本能のようなものを使用し、
それはかなりの場合、それは、並べ替えを知る

198
00:06:29,150 --> 00:06:31,600
初めに小さな、明らかに、我々はしました
右にもっと行くようになった。

199
00:06:31,600 --> 00:06:34,990
しかし、いくつかの意味で、あなたは幸運
多分これは、100番だったので、

200
00:06:34,990 --> 00:06:36,220
そして多分50は途中で以上であった。

201
00:06:36,220 --> 00:06:37,910
多分50はこっちでもあった。

202
00:06:37,910 --> 00:06:40,960
>> しかし、あなたは少し異なるものでした
この時間は、あなたが同じ事をしただった

203
00:06:40,960 --> 00:06:42,150
何度も何度も。

204
00:06:42,150 --> 00:06:45,310
そして、私は何をあなただけのことを主張するだろう
電話での影響を受けながらも、やった

205
00:06:45,310 --> 00:06:48,100
本例では、ずっと何か
より多くのアルゴリズム、および大いに

206
00:06:48,100 --> 00:06:49,930
少ない特殊で同棲。

207
00:06:49,930 --> 00:06:51,620
はるかに少ない本能。

208
00:06:51,620 --> 00:06:57,160
だから一日の終わりに、どのようにだろう
あなたの効率を記述する

209
00:06:57,160 --> 00:07:00,530
あなたが行った最初のアルゴリズム、
左から右へ、対

210
00:07:00,530 --> 00:07:03,430
ここで第2のアルゴリズム？

211
00:07:03,430 --> 00:07:06,460
>> JENNIFER：こちらは、多分、好きなはず
時間を半減、あるいはそれ以上、うん。

212
00:07:06,460 --> 00:07:07,320
>> DAVID J.マラン：OK、多分もっと。

213
00:07:07,320 --> 00:07:10,150
その上で少しハードにプッシュしてみましょう。

214
00:07:10,150 --> 00:07:13,030
本当に何が、我々はこれを継続する場合
ロジックは、我々は間違いなく半減

215
00:07:13,030 --> 00:07:15,830
この第2のアルゴリズムとの時間を実行している
の半分を捨てることによって

216
00:07:15,830 --> 00:07:18,470
数字が、我々は次の何をした
ジェニファーは明らかに繰り返し、

217
00:07:18,470 --> 00:07:20,615
二番目の数字？

218
00:07:20,615 --> 00:07:22,830
>> 我々は再びドアの数を半減。

219
00:07:22,830 --> 00:07:25,270
そして我々は、その後何をした場合
一緒にプレイするより多くのドアがあった？

220
00:07:25,270 --> 00:07:27,520
我々は、それらを再度半減し、なる
そして再び、再び。

221
00:07:27,520 --> 00:07:30,420
そして、これはすべてただ皆さんのようだった
の最初の週に立っ

222
00:07:30,420 --> 00:07:33,000
クラス、座ってあなたの半分、半分
あなたの、あなたの半分を座っ

223
00:07:33,000 --> 00:07:35,440
1単独まで、座っ
魂が立っていた。

224
00:07:35,440 --> 00:07:39,050
そして、私たちによるとの実行時間
こと、それがかかったステップ数だった

225
00:07:39,050 --> 00:07:40,430
何のために？

226
00:07:40,430 --> 00:07:41,230
>> SPEAKER 1：[聞こえない]

227
00:07:41,230 --> 00:07:43,970
>> DAVID J.マラン：だから、ログベースのn 2、
またはちょうどより簡単に、n個のログ。

228
00:07:43,970 --> 00:07:45,060
対数だから何か。

229
00:07:45,060 --> 00:07:48,380
とグラフが直線ではなかった
ただ悪化し、悪化したこと、それがあった

230
00:07:48,380 --> 00:07:52,490
しませんでしたこの興味深い曲線
時間をかけてそんなに悪く得る。

231
00:07:52,490 --> 00:07:53,910
それでは、このアイデアを保持しましょう​​。

232
00:07:53,910 --> 00:07:54,690
ジェニファーに感謝しましょう​​。

233
00:07:54,690 --> 00:07:56,150
アップ時に来て本当にありがとうございました。

234
00:07:56,150 --> 00:07:57,400
と、1秒。

235
00:07:57,400 --> 00:08:00,170

236
00:08:00,170 --> 00:08:02,925
いいえデスクランプない今日が、私たち
CS50ストレスボールを持っている。

237
00:08:02,925 --> 00:08:03,420
>> JENNIFER：イェーイ。

238
00:08:03,420 --> 00:08:04,410
>> DAVID J.マラン：すべての権利、ここに。

239
00:08:04,410 --> 00:08:06,545
負担していただきありがとうございます
ここでストレスまで。

240
00:08:06,545 --> 00:08:07,350
わかりました。

241
00:08:07,350 --> 00:08:10,620
だから我々は今、できないかどうかを確認してみましょう
もう少しこれを正式なもの。

242
00:08:10,620 --> 00:08:14,820
だからもう一度、私たちがちょうどやっていた
我々がしたように本質的には同じこと

243
00:08:14,820 --> 00:08:16,660
その最初の週である。

244
00:08:16,660 --> 00:08:23,780
しかし、だけではなく、直線で終わる
私たちが描かれたアルゴリズム、

245
00:08:23,780 --> 00:08:27,210
以前にこの直線として、
それによって、我々は上の1つ以上のドアを置けば

246
00:08:27,210 --> 00:08:29,610
画面には、その後ジェニファーはでしょう
、潜在的に、見てきた

247
00:08:29,610 --> 00:08:30,600
もう一つのドアの後ろに。

248
00:08:30,600 --> 00:08:33,490
我々は、さらに2つのドアを置く場合は、彼女が持っているかもしれません
さらに2つのドアの後ろに見えるように。

249
00:08:33,490 --> 00:08:35,990
>> そして、この直線があった
のサイズの関係

250
00:08:35,990 --> 00:08:39,059
x軸、言う、上の問題と、
それに要する時間

251
00:08:39,059 --> 00:08:40,440
Y上解決する。

252
00:08:40,440 --> 00:08:43,330
しかし、私はをほのめかしていた絵
以前この緑色のラインがあった。

253
00:08:43,330 --> 00:08:45,970
なぜなら、故意にグリーン
それはちょうど良い感じ。

254
00:08:45,970 --> 00:08:49,790
我々はそれをやった理論的には、アルゴリズム、
電話帳で、ときに我々はそれをやった

255
00:08:49,790 --> 00:08:52,420
君たちはお互いを数えると、と
後者の場合に、時だけジェニファー

256
00:08:52,420 --> 00:08:55,250
ここでそれをやった、それがものだった
根本的に良いの。

257
00:08:55,250 --> 00:08:57,180
それはちょうど倍の速さではなかったので。

258
00:08:57,180 --> 00:08:58,870
それも、高速の4倍ではなかった。

259
00:08:58,870 --> 00:09:03,290
それは何に完全に依存していた
入力の大きさはどのように多くのように、だった

260
00:09:03,290 --> 00:09:05,220
それが最終的に取った手順。

261
00:09:05,220 --> 00:09:08,040
>> そして、我々はすべてのかかったように、このシンプルなアイデア
電話帳で付与するため、

262
00:09:08,040 --> 00:09:10,200
同様に適用することができる
このような何かに。

263
00:09:10,200 --> 00:09:12,380
そして、これはもっとさりげなくあるかもしれない
あなたかもしれませんが、として知られている

264
00:09:12,380 --> 00:09:13,940
分割統治、想像してみてください。

265
00:09:13,940 --> 00:09:16,390
ではない私たちがやったこととは違って、もちろん、
電話帳と。

266
00:09:16,390 --> 00:09:18,300
>> しかし、擬似コード、リコールは、これだった。

267
00:09:18,300 --> 00:09:21,800
だから我々は再びこれを行うが、思い出すことはありません
最初の週に、私たちのすべてが立ち​​上がっていること

268
00:09:21,800 --> 00:09:25,140
その後、あなたの半分は半分の、座っ
あなたの半分は座って、座った。

269
00:09:25,140 --> 00:09:29,280
そのアルゴリズムで実装されました
それ、で不正行為の方法のビット、

270
00:09:29,280 --> 00:09:32,870
私のひとつは、カウントされませんでした
基本的に、より効率的に。

271
00:09:32,870 --> 00:09:35,830
その場合は、私が活用していた
セカンダリリソース。

272
00:09:35,830 --> 00:09:39,470
並べ替え、複数のCPU、複数の脳、
で複数のスマートな人々

273
00:09:39,470 --> 00:09:42,740
部屋には何かから私が得る助けた
何かに線形

274
00:09:42,740 --> 00:09:45,190
何かから、対数
緑色の何かに赤。

275
00:09:45,190 --> 00:09:48,650
>> しかし、このケースでは、一人でジェニファーができます
根本的に改良

276
00:09:48,650 --> 00:09:52,370
彼女の最初のアルゴリズムの性能によって、
再び、ほんの少し難しく考える。

277
00:09:52,370 --> 00:09:56,650
そして今、それを実装するための時間が来るとき
これらの事を、考え出す

278
00:09:56,650 --> 00:10:00,670
何がそのような書くことができますコードの行
あなたはそれらを再度繰り返し、できること

279
00:10:00,670 --> 00:10:03,350
再び、再び、ソートの
ループのファッションである。

280
00:10:03,350 --> 00:10:06,370
あなたが持ってするつもりはないので
ジェニファーのような贅沢は、するために、最初はなかった

281
00:10:06,370 --> 00:10:10,460
ただ、IFSの全体の束を持っていると言う
うーん、もしこの最初の数字が4である、

282
00:10:10,460 --> 00:10:11,800
私は最後まですべての方法をジャンプしてみましょう。

283
00:10:11,800 --> 00:10:14,180
その数が大きすぎる場合には、ああ、
私は勝手に戻って移動することができ

284
00:10:14,180 --> 00:10:15,220
二番目の要素に。

285
00:10:15,220 --> 00:10:18,210
あなたはそれがたくさんになるだろうことがわかります
難しく正式に私たち人間

286
00:10:18,210 --> 00:10:21,270
非常に合理的なように当たり前の
ヒューリスティックが、コンピュータがあるだけで

287
00:10:21,270 --> 00:10:23,260
あなたがしなければ、それを言うことをするつもり。

288
00:10:23,260 --> 00:10:25,280
>> さて、これは非常に興味深いものがある
意味合い。

289
00:10:25,280 --> 00:10:29,950
このグラフは、ソートの一種のことを意図している
視覚的に圧倒、しかし予告、どこ

290
00:10:29,950 --> 00:10:32,230
このグラフの直線のですか？

291
00:10:32,230 --> 00:10:35,330
線形グラフはどこです
我々はnを呼んでいる？

292
00:10:35,330 --> 00:10:37,580
まあ、それは下の方にソートのだ
この写真の、右？

293
00:10:37,580 --> 00:10:40,500
だから私たちがやったすべては、我々は一種のをしましたです
x軸とにズームアウト

294
00:10:40,500 --> 00:10:44,780
何の感覚を取得しようとするために、y軸
曲線の他のタイプのように見える。

295
00:10:44,780 --> 00:10:47,760
>> と数学の仕様
今日はそう問題ではないでしょう表現

296
00:10:47,760 --> 00:10:52,440
多くの、しかし、多くのがあることに気付く
よりもはるかに悪化しているアルゴリズム

297
00:10:52,440 --> 00:10:53,470
リニアだもの。

298
00:10:53,470 --> 00:10:55,410
確かに、乗nがかなり悪い見える。

299
00:10:55,410 --> 00:10:58,400
2 nにはかなり悪いよう。
乗nがかなり悪い見える。

300
00:10:58,400 --> 00:11:01,630
そして、私たちはそれらのどのようないくつか表示されます
現実には今日かもしれない。

301
00:11:01,630 --> 00:11:05,430
およびログnが悪いように感じるのではなく、
nより良いnのログベース2です。

302
00:11:05,430 --> 00:11:08,080
しかし、あなたが知っている、それもあったであろう
ジェニファー場合、あるいは我々であればもっと素晴らしい、

303
00:11:08,080 --> 00:11:12,910
その最初の週、思い付くしていた
n個のログのログですか。

304
00:11:12,910 --> 00:11:15,880
>> だから、他の言葉で、この全体はあり
への可能な解決策の範囲

305
00:11:15,880 --> 00:11:18,570
問題は、しかし、ここでも、予告
何が起こるだろう。

306
00:11:18,570 --> 00:11:22,910
これらの曲線の私がズームアウトすると、その
絶対であることを証明するために起こっている

307
00:11:22,910 --> 00:11:26,630
今、画面上のものの最悪？

308
00:11:26,630 --> 00:11:28,680
だからN乗がきれいに見える
現時点では悪い。

309
00:11:28,680 --> 00:11:32,470
しかし、我々はズームアウトするとの詳細を参照する場合
ために起こっているxとy軸、

310
00:11:32,470 --> 00:11:34,550
最終的に支配する？

311
00:11:34,550 --> 00:11:37,120
だから、実際にはその2が判明
nと、あなただけのことで、これを把握することができます

312
00:11:37,120 --> 00:11:39,990
一部ますます大に差し込む
数字、あなたはわかりますその2〜

313
00:11:39,990 --> 00:11:42,070
nは、確かに、大きくはるかに速くなります。

314
00:11:42,070 --> 00:11:45,530
私たちは本当にに、2をズームアウトする場合
nのアルゴリズムでは、絶対に吸う。

315
00:11:45,530 --> 00:11:48,170
私はこれがかかるとしていることを意味
ためにかなりの時間

316
00:11:48,170 --> 00:11:49,460
を通じて解約するコンピュータ。

317
00:11:49,460 --> 00:11:52,500
>> しかし、あなたは特に、時間をかけて表示されます
将来の問題セットを持つとさえ

318
00:11:52,500 --> 00:11:55,600
最後のプロジェクトは、あなたのデータであり、
セットには、すべての権利を大きくなる？

319
00:11:55,600 --> 00:11:58,300
でも、フェイスブックの最初のバージョンで、
友人の数、など

320
00:11:58,300 --> 00:12:01,840
登録ユーザー数は、大規模だ
あなたは、携帯電話でのそれを並べ替えることができますし、

321
00:12:01,840 --> 00:12:05,530
、線形探索で何かを実装する
または非常に単純なソート

322
00:12:05,530 --> 00:12:07,030
今日我々が見るようにアルゴリズム。

323
00:12:07,030 --> 00:12:09,280
あなたが難しく考え始めなければならない
これらの問題について難しい。

324
00:12:09,280 --> 00:12:12,070
そして問題の場所の種類のような
フェイスブック、およびGoogleとMicrosoft、

325
00:12:12,070 --> 00:12:16,350
とで動作する他の人はこれらの正確です
質問のビッグデータソートのソート

326
00:12:16,350 --> 00:12:18,530
ますます、これらの日。

327
00:12:18,530 --> 00:12:18,900
>> わかりました。

328
00:12:18,900 --> 00:12:23,800
その第二にジェニファーの成功だから
アルゴリズムは、率直に言って、彼女は驚くほどでした

329
00:12:23,800 --> 00:12:26,110
よく初めて、しかしみましょう
それは運のように書いているので、

330
00:12:26,110 --> 00:12:27,000
このポイントを作ることができます。

331
00:12:27,000 --> 00:12:30,970
第二のケースでは、彼女が活用
再び繰り返されるとアルゴリズム

332
00:12:30,970 --> 00:12:34,670
再び、彼女は当たり前のかかった
我々は許可されている一定の前提

333
00:12:34,670 --> 00:12:39,370
彼女が、彼女はいくつかの詳細を悪用し
彼女が持っていなかった二度目

334
00:12:39,370 --> 00:12:39,840
初めて。

335
00:12:39,840 --> 00:12:41,800
何がどのようでしたか？

336
00:12:41,800 --> 00:12:43,050
>> リストがソートされている。

337
00:12:43,050 --> 00:12:46,350
だから、すぐにリストがソートされたとして、我々
ジェニファーは行うことができたと主張している

338
00:12:46,350 --> 00:12:47,480
根本的に良い。

339
00:12:47,480 --> 00:12:51,450
7ドア、はい、その興味深いものではありません、
しかし、それは我々が700万扉だと仮定します。

340
00:12:51,450 --> 00:12:54,080
n個のログは間違いなく起こっている
、はるかを実行する

341
00:12:54,080 --> 00:12:55,610
長期的にはより速く。

342
00:12:55,610 --> 00:12:58,880
しかし、彼女は持っていた
ドアは彼女のために並べ替え。

343
00:12:58,880 --> 00:13:02,320
今、私はそれを行うための自由を取った
コンピュータ画面上で、事前に

344
00:13:02,320 --> 00:13:05,160
ここが、そのジェニファーと仮定
彼女自身それを行う必要があった？

345
00:13:05,160 --> 00:13:10,120
と仮定し、その質問にドア
表され、データベース内のデータ、または

346
00:13:10,120 --> 00:13:14,260
フェイスブックに登録され、または友人
インターネット上の任意のWebページにその

347
00:13:14,260 --> 00:13:16,880
様々なウェブサイトでは、必要があるかもしれません
インデックス以上検索する。

348
00:13:16,880 --> 00:13:20,940
>> あなただけの生データを持っていたと仮定し
設定し、それがあなたに残された、またはする

349
00:13:20,940 --> 00:13:23,010
ジェニファーはそのソートを行うには？

350
00:13:23,010 --> 00:13:26,950
むしろ、我々は答えを必要とすることに、
質問、まあ、どのくらいの時間

351
00:13:26,950 --> 00:13:31,080
ジェニファー、あるいは私を、かかったでしょう
事前にこれらの数字をソートするので、

352
00:13:31,080 --> 00:13:32,680
彼女はそれを活用することができること？

353
00:13:32,680 --> 00:13:32,880
右？

354
00:13:32,880 --> 00:13:36,620
もちろん含意は、、であるため
それは、並べ替えることが私にかなり時間がかかる場合

355
00:13:36,620 --> 00:13:40,800
一体あなたのことを気に数字、
50のような数が非常に速く見つけることができる、

356
00:13:40,800 --> 00:13:44,850
ジェニファーの場合のように、我々は以上の場合
合計時間の量を圧倒

357
00:13:44,850 --> 00:13:46,920
それは、事前に物事をソートした？

358
00:13:46,920 --> 00:13:49,320
>> だから我々はできないかどうかを確認してみましょう
ここで絵を描く。

359
00:13:49,320 --> 00:13:51,370
私は全体の束より多くのストレスを持っている
ボール、場合に役立ちます

360
00:13:51,370 --> 00:13:52,270
ここで氷を砕く。

361
00:13:52,270 --> 00:13:55,690
そして、あなたは気にしないならば、我々
7ボランティアを必要とする - 

362
00:13:55,690 --> 00:13:57,060
OK、上に。

363
00:13:57,060 --> 00:13:57,240
うわー。

364
00:13:57,240 --> 00:13:59,250
だから私たちは費やす必要はありません
デスクランプに、それは思われる。

365
00:13:59,250 --> 00:13:59,690
わかりました。

366
00:13:59,690 --> 00:14:01,530
それでは、どのように前にあなたについて2。

367
00:14:01,530 --> 00:14:04,160
あなたはどう後ろに二人。

368
00:14:04,160 --> 00:14:04,870
だから4だ。

369
00:14:04,870 --> 00:14:09,890
いかがでしょうか前に
5、6と7。

370
00:14:09,890 --> 00:14:10,320
すぐそこ。

371
00:14:10,320 --> 00:14:13,260
あなたの友人は、あなたを指している
ので、あなたは賞金を得る。

372
00:14:13,260 --> 00:14:13,700
>> わかりました。

373
00:14:13,700 --> 00:14:14,410
までさあ。

374
00:14:14,410 --> 00:14:17,120
そして、なぜ私たちはあなたの持っていない
みんなこっちに来る。

375
00:14:17,120 --> 00:14:18,960
私はあなたに、それぞれの番号を与えるつもりです。

376
00:14:18,960 --> 00:14:22,150
と先に行くと自分をアレンジ
同じだもの

377
00:14:22,150 --> 00:14:25,180
画面に描かれた。

378
00:14:25,180 --> 00:14:26,530
>> [介在VOICES]

379
00:14:26,530 --> 00:14:28,160
>> DAVID J.マラン：OOP、申し訳ありません。

380
00:14:28,160 --> 00:14:30,210
バグ。

381
00:14:30,210 --> 00:14:32,180
わかりました。

382
00:14:32,180 --> 00:14:32,750
さて、ここで私達は行く。

383
00:14:32,750 --> 00:14:34,180
番号5。

384
00:14:34,180 --> 00:14:35,136
番号6。

385
00:14:35,136 --> 00:14:37,770
一つ、二つ、三つ、四つ、
5、6、7。

386
00:14:37,770 --> 00:14:39,410
ああ、これは厄介です。

387
00:14:39,410 --> 00:14:41,210
>> SPEAKER 2：私はちょうど買ってあげる - 。

388
00:14:41,210 --> 00:14:41,900
>> DAVID J.マラン：良い取引。

389
00:14:41,900 --> 00:14:43,130
わかりました。

390
00:14:43,130 --> 00:14:44,611
参加していただきありがとうございます。

391
00:14:44,611 --> 00:14:47,200
>> [拍手]

392
00:14:47,200 --> 00:14:48,580
>> OK。

393
00:14:48,580 --> 00:14:48,860
わかりました。

394
00:14:48,860 --> 00:14:51,970
だから我々は、4、2、6を持って
オン、3個、7、5。

395
00:14:51,970 --> 00:14:56,010
私たちは7人のボランティアを持っているので、パーフェクト
ここまで幅が等しい人

396
00:14:56,010 --> 00:14:57,430
私たちが演奏していることを配列
以前と。

397
00:14:57,430 --> 00:14:59,470
そして、私は理由のために7を選んだ
それはちょうどになります

398
00:14:59,470 --> 00:15:00,840
少しで便利。

399
00:15:00,840 --> 00:15:04,400
そして、私はそれを最初に提案するつもりです
私たちは、これら7つのボランティアを並べ替える。

400
00:15:04,400 --> 00:15:06,786
あなたは、最初に、ご希望の場合
でも挨拶する。

401
00:15:06,786 --> 00:15:08,970
これがあることを行っているので、
ぎこちない数分。

402
00:15:08,970 --> 00:15:10,370
自己紹介を。

403
00:15:10,370 --> 00:15:10,980
>> GRACE：こんにちは、私はグレースだ。

404
00:15:10,980 --> 00:15:14,190
私はLeverettハウス年生だ。

405
00:15:14,190 --> 00:15:14,620
>> BRANSON：こんにちは。

406
00:15:14,620 --> 00:15:15,620
私はブランソンだ。

407
00:15:15,620 --> 00:15:16,920
私は溶接で新入生だ。

408
00:15:16,920 --> 00:15:19,755

409
00:15:19,755 --> 00:15:20,230
>> GABE：こんにちは。

410
00:15:20,230 --> 00:15:21,040
私はゲイブだ。

411
00:15:21,040 --> 00:15:22,300
私はカボットで後輩だ。

412
00:15:22,300 --> 00:15:24,826

413
00:15:24,826 --> 00:15:25,980
>> NEIL：私はニールだ。

414
00:15:25,980 --> 00:15:29,090
私はマシューズで新入生だ。

415
00:15:29,090 --> 00:15:29,550
>> JASON：私はジェイソンだ。

416
00:15:29,550 --> 00:15:32,816
私はグリーノーで新入生だ。

417
00:15:32,816 --> 00:15:33,700
>> MIKE：私はマイクだ。

418
00:15:33,700 --> 00:15:37,360
私はグレーで新入生だ。

419
00:15:37,360 --> 00:15:37,990
>> JESS：私はジェスだ。

420
00:15:37,990 --> 00:15:40,313
私はLeverett 2年生だ。

421
00:15:40,313 --> 00:15:41,300
>> DAVID J.マラン：エクセレント。

422
00:15:41,300 --> 00:15:41,850
わかりました。

423
00:15:41,850 --> 00:15:44,190
さて、私たちのすべてに感謝
これまでここでボランティア。

424
00:15:44,190 --> 00:15:47,110
そして今、手元に挑戦は起こっている
これらの人のようなものになるが、そのために

425
00:15:47,110 --> 00:15:50,250
我々は少し考える必要があるとしている
どのように効率的に我々実際には約ハード

426
00:15:50,250 --> 00:15:51,110
それらを並べ替え。

427
00:15:51,110 --> 00:15:52,580
それでは、最初にこれを試してみましょう。

428
00:15:52,580 --> 00:15:55,970
君たちはお互いの数字を見ることができます
ただコーナーの周りに置くことによって。

429
00:15:55,970 --> 00:15:59,380
先に行くと、数秒かかる、と
上の小さいものから自分自身を並べ替える

430
00:15:59,380 --> 00:16:01,240
右側に最大に残しました。

431
00:16:01,240 --> 00:16:02,490
行く。

432
00:16:02,490 --> 00:16:07,010

433
00:16:07,010 --> 00:16:07,530
>> OK。

434
00:16:07,530 --> 00:16:08,030
グッド。

435
00:16:08,030 --> 00:16:09,370
それは本当にくそ速かった。

436
00:16:09,370 --> 00:16:14,040
今ここに誰か、アルゴリズムは何だった
これらの人は適用した？

437
00:16:14,040 --> 00:16:14,900
>> SPEAKER 1：最大の少ない。

438
00:16:14,900 --> 00:16:15,000
>> DAVID J.マラン：OK。

439
00:16:15,000 --> 00:16:18,070
最大の少ない、本当にのようなものです
客観的な、私はだとわからないんだけど

440
00:16:18,070 --> 00:16:18,890
本当にアルゴリズム。

441
00:16:18,890 --> 00:16:21,810
少なくとも最大に教えてくれない
私は何をすべきかをステップ·バイ·ステップ。

442
00:16:21,810 --> 00:16:22,833
うん？

443
00:16:22,833 --> 00:16:24,083
>> SPEAKER 1：[聞こえない]

444
00:16:24,083 --> 00:16:26,010

445
00:16:26,010 --> 00:16:26,280
>> DAVID J.マラン：OK。

446
00:16:26,280 --> 00:16:28,920
ですから、より小さい人を見たら
あなたの番号、その後に移動

447
00:16:28,920 --> 00:16:29,680
それらの右側。

448
00:16:29,680 --> 00:16:32,800
だから今では、より表現になってきている
あなたのために、アルゴリズムのようなより

449
00:16:32,800 --> 00:16:35,410
その、これであれば、言うことができます。

450
00:16:35,410 --> 00:16:37,050
だから我々はいくつかの種類を持っている
条件付き構造。

451
00:16:37,050 --> 00:16:39,700
そして、これらの人は、いくつかのことを行うように見えた
回、あなたのいくつかのビットを移動したため

452
00:16:39,700 --> 00:16:40,420
距離の。

453
00:16:40,420 --> 00:16:43,410
だから、おそらくいくつかの種類のがあった
彼らの心で起こってループ。

454
00:16:43,410 --> 00:16:44,610
>> しかし、それを形式化してみましょう。

455
00:16:44,610 --> 00:16:47,540
君たちが戻ってリセットすることができれば
この配置に。

456
00:16:47,540 --> 00:16:50,650
我々はこの定式化ができないかどうかを確認してみましょう
少ししてから、質問をする、

457
00:16:50,650 --> 00:16:51,580
これがどのように効率的ですか？

458
00:16:51,580 --> 00:16:54,220
もちろん、我々はよりゆっくりとこれを行う際に、
それはのように良い感じになるだろう

459
00:16:54,220 --> 00:16:57,210
アルゴリズムが、私達ができれば見てみましょう
正確なステップに私たちの指を置く。

460
00:16:57,210 --> 00:16:58,670
>> だから二人には4つのと2つです。

461
00:16:58,670 --> 00:17:01,020
または、正しいか正しくないため？

462
00:17:01,020 --> 00:17:01,900
明らかに間違った。

463
00:17:01,900 --> 00:17:02,710
だからスワップ。

464
00:17:02,710 --> 00:17:05,170
今、私は脇に移動するつもりです
ここと六から四、言う。

465
00:17:05,170 --> 00:17:06,240
あなたは、正しいか間違っている？

466
00:17:06,240 --> 00:17:06,599
>> GABE：正しい。

467
00:17:06,599 --> 00:17:07,180
>> DAVID J.マラン：正しい。

468
00:17:07,180 --> 00:17:08,300
六一？

469
00:17:08,300 --> 00:17:08,609
いや。

470
00:17:08,609 --> 00:17:09,630
スワップ。

471
00:17:09,630 --> 00:17:10,490
だから2スワップだ。

472
00:17:10,490 --> 00:17:11,710
六三？

473
00:17:11,710 --> 00:17:11,980
いや。

474
00:17:11,980 --> 00:17:13,000
スワップ。

475
00:17:13,000 --> 00:17:13,930
6と7？

476
00:17:13,930 --> 00:17:14,630
よさそうだ。

477
00:17:14,630 --> 00:17:15,396
七と5？

478
00:17:15,396 --> 00:17:16,150
>> JESS：[聞こえない]

479
00:17:16,150 --> 00:17:17,089
>> DAVID J.マラン：OK、交換。

480
00:17:17,089 --> 00:17:19,770
と並べ替え。

481
00:17:19,770 --> 00:17:19,980
わかりました。

482
00:17:19,980 --> 00:17:21,440
だから、明らかにしない、右？

483
00:17:21,440 --> 00:17:22,470
だから、もっと上があるつもりだった。

484
00:17:22,470 --> 00:17:24,920
しかし、確かに、これらの人も、
ただ本能的に。

485
00:17:24,920 --> 00:17:25,450
移動保管。

486
00:17:25,450 --> 00:17:27,710
彼らはちょうど彼らに一度、停止しませんでした
一つの問題を修正しました。

487
00:17:27,710 --> 00:17:27,839
だから。

488
00:17:27,839 --> 00:17:29,390
確かに、私が持っているつもりです
同じことを行う。

489
00:17:29,390 --> 00:17:32,720
私は戻って巻き戻しのようなものする必要がありますするつもりです
この問題の先頭に、

490
00:17:32,720 --> 00:17:35,630
この配列の先頭または
人々は、それらを呼び出しましょう​​。

491
00:17:35,630 --> 00:17:38,366
>> そして今、何をすべき私のアルゴリズム
番目のパス上にある？

492
00:17:38,366 --> 00:17:39,220
>> SPEAKER 1：同じこと。

493
00:17:39,220 --> 00:17:39,940
>> DAVID J.マラン：同じこと。

494
00:17:39,940 --> 00:17:41,460
そして、これは、私は右の、好きになり始めている？

495
00:17:41,460 --> 00:17:44,720
あなた自身がやって見つけることができるとすぐに
何度も何度も同じこと、だ

496
00:17:44,720 --> 00:17:47,890
、より多くのアルゴリズムのようになってき
と少ない人間の本能。

497
00:17:47,890 --> 00:17:48,680
>> だから今、ここに私達は再度行く。

498
00:17:48,680 --> 00:17:49,870
2〜4？

499
00:17:49,870 --> 00:17:50,220
いいえ。

500
00:17:50,220 --> 00:17:51,050
四一？

501
00:17:51,050 --> 00:17:53,380
ああ、いくつかのは確かにあった
行われるように、まだ働いています。

502
00:17:53,380 --> 00:17:53,620
用と3？

503
00:17:53,620 --> 00:17:54,572
グッド。

504
00:17:54,572 --> 00:17:56,000
4〜6？

505
00:17:56,000 --> 00:17:58,380
六と5？

506
00:17:58,380 --> 00:17:59,470
6と7？

507
00:17:59,470 --> 00:18:00,970
[OK]を、今、行って。

508
00:18:00,970 --> 00:18:01,550
いや、OK。

509
00:18:01,550 --> 00:18:02,710
私は戻って行かなければならない。

510
00:18:02,710 --> 00:18:05,130
>> だから今、再び、我々はこれをやっている
もう少し慎重に。

511
00:18:05,130 --> 00:18:08,700
そして今、一つの脳はあり
このアルゴリズムを実行する。

512
00:18:08,700 --> 00:18:10,290
つのCPU、可能ならば。

513
00:18:10,290 --> 00:18:13,090
と率直に言って、それが唯一の資源だ
私たちは、へのアクセス権を持っているつもりです。

514
00:18:13,090 --> 00:18:16,280
そして、かつて私たちは、キーボードに戻って行くのですか
と私たちにCのような何かを持って

515
00:18:16,280 --> 00:18:19,600
処分、我々は唯一のプログラムを書いている
それは、一度に一つのことを行うことができます。

516
00:18:19,600 --> 00:18:22,900
一瞬前にこれらの人、一方で、我々
彼らの集団的知力レバレッジ

517
00:18:22,900 --> 00:18:24,180
あなたのように人は、0週目になりました。

518
00:18:24,180 --> 00:18:24,980
だから、これをやり続けるみましょう。

519
00:18:24,980 --> 00:18:26,260
>> 二一。

520
00:18:26,260 --> 00:18:26,945
二、三。

521
00:18:26,945 --> 00:18:27,460
3と4。

522
00:18:27,460 --> 00:18:28,310
4および5。

523
00:18:28,310 --> 00:18:28,620
五六。

524
00:18:28,620 --> 00:18:30,510
6と7。

525
00:18:30,510 --> 00:18:31,880
完了？

526
00:18:31,880 --> 00:18:34,560
だから私は、しかし、私が遊ばせて
悪魔の代弁者。

527
00:18:34,560 --> 00:18:37,950
私は、コンピュータのようなものだけで行う
この配列を通過しました

528
00:18:37,950 --> 00:18:40,225
人々は、私が行ってることを知っている？

529
00:18:40,225 --> 00:18:40,670
>> SPEAKER：1号

530
00:18:40,670 --> 00:18:41,050
>> DAVID J.マラン：なぜ？

531
00:18:41,050 --> 00:18:46,900
私は何をするためにしなければならないでしょう
私が行っているということ決定的に結論？

532
00:18:46,900 --> 00:18:48,230
おそらく1つ以上のパス。

533
00:18:48,230 --> 00:18:48,430
右？

534
00:18:48,430 --> 00:18:51,760
すべての私はその前から知っているので、
パスは、私は間違いを訂正したことである。

535
00:18:51,760 --> 00:18:53,920
そして、その手段が、多分そこだ
まだ別の間違い

536
00:18:53,920 --> 00:18:54,840
私は修正する必要がある。

537
00:18:54,840 --> 00:18:58,680
したがって、僕は唯一の巻き戻しすることにより確認することやすることができ
その後、チェックを一から二、2と

538
00:18:58,680 --> 00:19:00,940
3、3と4、4、5、
5と6、6と7。

539
00:19:00,940 --> 00:19:02,510
[OK]を、今、私は仕事もしなかった。

540
00:19:02,510 --> 00:19:05,990
>> 私は確かに私がしたないことを覚えていることはできません
変数のようなものとの仕事、

541
00:19:05,990 --> 00:19:06,975
int型が好きです。

542
00:19:06,975 --> 00:19:12,490
それはスワップと呼び、スワップは私一度0である場合
ここで取得し、それはその後、0から開始

543
00:19:12,490 --> 00:19:15,520
私はちょうど続けるために愚かなことでしょう
前後に、再度チェック、および

544
00:19:15,520 --> 00:19:16,450
再び、再び、右？

545
00:19:16,450 --> 00:19:18,450
あなたは、いくつかにはまり込むので
無限ループのようなもの。

546
00:19:18,450 --> 00:19:21,250
0スワップは、ありそうとすぐに
我々はこのことを主張することができます

547
00:19:21,250 --> 00:19:23,810
アルゴリズムは確かに完了です。

548
00:19:23,810 --> 00:19:25,400
>> それでは、これに名前を入れてみましょう。

549
00:19:25,400 --> 00:19:28,930
私はちょうど私たちを提案するアルゴリズム
実装バブルと呼ばれるものです。

550
00:19:28,930 --> 00:19:32,800
その意味でそのように知られている並べ替え、
大きな種のある数字

551
00:19:32,800 --> 00:19:37,990
までトップにバブル自分の道を、または最大
数値の配列の末尾に。

552
00:19:37,990 --> 00:19:40,270
しかし、このアルゴリズムは、どのように効率的でしたか？

553
00:19:40,270 --> 00:19:44,600
私は物理的にどのように多くの手順を持っていなかった
これらを並べ替えるには、例えば、取る

554
00:19:44,600 --> 00:19:45,850
7人間？

555
00:19:45,850 --> 00:19:48,560

556
00:19:48,560 --> 00:19:49,550
>> 四つに5？

557
00:19:49,550 --> 00:19:51,420
[OK]を、あまりにも多く、最終的にはある
答えになるだろう。

558
00:19:51,420 --> 00:19:54,960
しかし、その後、具体的な数
とても面白くないです。

559
00:19:54,960 --> 00:19:56,670
それnは一般化してみましょう。

560
00:19:56,670 --> 00:20:00,520
だから私はここで人々をn、およびそれらいた場合
にランダムな順序で、ソートのあった

561
00:20:00,520 --> 00:20:02,180
その元の順序で、始まる。

562
00:20:02,180 --> 00:20:04,910
さて、どのように多くの手順を私は持っていなかった
最初のパスで取るには？

563
00:20:04,910 --> 00:20:09,810
それは1つ、2つ、3つ、4つ、5つであった
そう6、彼らは7人だ、

564
00:20:09,810 --> 00:20:13,670
それが、6 7だ - 、Nだそう
マイナス1のステップは初めて。

565
00:20:13,670 --> 00:20:16,280
>> さて、どのように多くの手順を私は持っていなかった
私は巻き戻したときに取るには？

566
00:20:16,280 --> 00:20:19,310
さて、私たちは実際に倍増する可能性のある場合
私たちは、本当にしたかったが、今のところ、私はよ

567
00:20:19,310 --> 00:20:22,300
ただ、すべての権利を言おうとしてい
別のnはマイナス1。

568
00:20:22,300 --> 00:20:25,240
nはマイナス1が取得する予定ですので、
を追跡するのが面倒なので、してみましょう

569
00:20:25,240 --> 00:20:26,400
わずかに切り上げます。

570
00:20:26,400 --> 00:20:27,770
だから、2n個のステップ。

571
00:20:27,770 --> 00:20:29,310
だから14ステップ、与えるか、または取る。

572
00:20:29,310 --> 00:20:31,930
>> 私は何回かかりました
ステップ次回？

573
00:20:31,930 --> 00:20:33,740
まあ、それは3Nです。

574
00:20:33,740 --> 00:20:34,510
本当に。

575
00:20:34,510 --> 00:20:37,920
そして今、最悪の場合には、用
例えば、何回私が持っているでしょう

576
00:20:37,920 --> 00:20:41,730
、前後に、前後に行っ
スワッピング、このアルゴリズムを実行する

577
00:20:41,730 --> 00:20:44,620
各パス上の人、大体？

578
00:20:44,620 --> 00:20:47,720

579
00:20:47,720 --> 00:20:50,010
それは、右実際にN乗のですか？

580
00:20:50,010 --> 00:20:53,000
>> 最悪のケースでは、種類ができるので
直感的にこれについて考えるの、

581
00:20:53,000 --> 00:20:54,800
それは少しかかることがありますにもかかわらず、
インチシンクする時間のビット

582
00:20:54,800 --> 00:20:57,590
最悪の場合には、何だろう、これらの
7人中、ように見えた

583
00:20:57,590 --> 00:21:00,230
契約の条件
その数の？

584
00:21:00,230 --> 00:21:01,460
完全に後方、右？

585
00:21:01,460 --> 00:21:02,815
そして、ちょうど、それをシミュレートする
あなたの名前は再び何でしたか？

586
00:21:02,815 --> 00:21:03,360
>> MIKE：マイク。

587
00:21:03,360 --> 00:21:03,640
>> DAVID J.マラン：マイク？

588
00:21:03,640 --> 00:21:08,100
OK、マイク、あなただけの私を参加することができます
ここだけ1秒？

589
00:21:08,100 --> 00:21:08,880
実際には、ない。

590
00:21:08,880 --> 00:21:10,150
申し訳ありませんマイク、巻き戻してみましょう。

591
00:21:10,150 --> 00:21:10,910
あなたの名前は何です再び？

592
00:21:10,910 --> 00:21:11,180
>> NEIL：ニール。

593
00:21:11,180 --> 00:21:11,640
>> DAVID J.マラン：ニール。

594
00:21:11,640 --> 00:21:13,750
OK、ニール、あなたは付属している
私、あなたが気にしない場合。

595
00:21:13,750 --> 00:21:17,150
だから、僕はのために、提案するつもりだ
ニールは彼に今あるシンプルさ、

596
00:21:17,150 --> 00:21:18,510
最悪のケース。

597
00:21:18,510 --> 00:21:20,720
しかし、私はどのように実装さ思い出す
私のアルゴリズム。

598
00:21:20,720 --> 00:21:24,530
私は、比較の比較、比較しています、
ああ、比較、比較。

599
00:21:24,530 --> 00:21:26,640
今、これらの人が出ている
オーダーのため、私が修正してください。

600
00:21:26,640 --> 00:21:27,980
だからみんなスワップ。

601
00:21:27,980 --> 00:21:31,630
しかし、どのくらい遠く、今考える
ニールは、行かなければならないのでしょうか？

602
00:21:31,630 --> 00:21:32,690
それは大体Nだ。

603
00:21:32,690 --> 00:21:33,570
あなたはそれが実際にNはないが、知っている。

604
00:21:33,570 --> 00:21:36,040
それはのように、n個から1を引いた値だが、私は取得しています
少しのイライラを追跡

605
00:21:36,040 --> 00:21:37,550
数は、そうちょうどそれがn個呼び出してみましょう。

606
00:21:37,550 --> 00:21:42,860
>> ニールは、最大限にそれぞれ一歩を動かすのであれば
時間、ニール一歩を移動するには、

607
00:21:42,860 --> 00:21:46,580
私はこれは本当に退屈なパスをしなければならない
前後に、これはおおよそである

608
00:21:46,580 --> 00:21:52,080
、、nステップ、n回の合計はこれをやって
それは私を取るために起こっているので、

609
00:21:52,080 --> 00:21:55,820
多くの手順はニールすべてを取得すること
彼が属している場所への道。

610
00:21:55,820 --> 00:21:58,620
君たちなら皆おろか
すべて同様に誤発注された。

611
00:21:58,620 --> 00:22:01,100
>> それでは、バブルソートnの二乗を呼び出してみましょう。

612
00:22:01,100 --> 00:22:04,860
このアルゴリズムの実行時間、
このアルゴリズムの性能は、

613
00:22:04,860 --> 00:22:07,120
このアルゴリズムの効率性
私達はちょうどより多くを記述しなければならない

614
00:22:07,120 --> 00:22:08,800
一般的にnの二乗。

615
00:22:08,800 --> 00:22:11,650
私は可能性があるため、どちらが、いいです
8人、9と同じ例

616
00:22:11,650 --> 00:22:15,450
人、万人、その
答えは変更するつもりはない。

617
00:22:15,450 --> 00:22:18,870
>> 皆さんが気にしないならばそう、みましょう
あなたが始めるところにあなたをリセットします。

618
00:22:18,870 --> 00:22:22,510
と他の2つのアプローチを試してみましょうと
我々は根本的に行うことができないかどうかを確認

619
00:22:22,510 --> 00:22:23,820
これよりも良い。

620
00:22:23,820 --> 00:22:27,130
今回だから、私が提案するつもりです
異なるアルゴリズムの一種。

621
00:22:27,130 --> 00:22:29,950
つまり、前回の私たちの非常に巧妙だった
そして皆さんが持って正しかった

622
00:22:29,950 --> 00:22:32,470
だけの種類の右側の本能
ペアを入れ替えるの。

623
00:22:32,470 --> 00:22:36,500
しかし、私は本当にこれをアプローチしたい場合
単に、私の目標は、移動させることである

624
00:22:36,500 --> 00:22:39,800
少し数字この方法のすべて、および
その大きな数字のすべてをプッシュする

625
00:22:39,800 --> 00:22:43,030
方法、なぜ私はただでそれをしないでください
可能な限り最も素朴な方法と私かどうかを確認

626
00:22:43,030 --> 00:22:45,730
だったものよりも良い行うことができます
かなり複雑なアルゴリズム？

627
00:22:45,730 --> 00:22:46,620
>> それでは見てみましょう。

628
00:22:46,620 --> 00:22:48,940
四つはかなり数が少ないですので、私はよ
そこに瞬間あなたを残そう。

629
00:22:48,940 --> 00:22:50,610
ああ、ナンバー2は、さらに良いです。

630
00:22:50,610 --> 00:22:52,230
だから、あなただけ踏み出すことができます
一瞬のために？

631
00:22:52,230 --> 00:22:55,670
これは現在、私の最も小さい番号が付けられています
候補者、と私は覚えているつもりです

632
00:22:55,670 --> 00:22:57,000
変数、のように、とのこと。

633
00:22:57,000 --> 00:22:57,930
しかし、私はチェックし続けるつもりです。

634
00:22:57,930 --> 00:22:59,890
その誰かがありますか
数字が小さくなる？

635
00:22:59,890 --> 00:23:00,460
六、ない。

636
00:23:00,460 --> 00:23:01,390
ああ、再びニールあり。

637
00:23:01,390 --> 00:23:04,050
>> だから私はあなたをプッシュバックするつもりです
概念的には、一種の。

638
00:23:04,050 --> 00:23:05,120
ニールは、前方に来るでしょう。

639
00:23:05,120 --> 00:23:08,440
そして今、私が使用していることを変数
最小を持っている人を追跡

640
00:23:08,440 --> 00:23:11,390
番号が含まれるように更新される
ニールの位置。

641
00:23:11,390 --> 00:23:12,110
まあ、見てみましょう。

642
00:23:12,110 --> 00:23:13,960
三、七、五。

643
00:23:13,960 --> 00:23:15,590
[OK]を、私はニールが最小だった知っている。

644
00:23:15,590 --> 00:23:18,110
最も簡単な方法は何ですか
私のために今何をするか？

645
00:23:18,110 --> 00:23:21,410
私はちょうどで私の時間を無駄にするつもりはない
左にニール一つの場所をバブリングする。

646
00:23:21,410 --> 00:23:25,350
ここで彼はなぜただニールを入れてはいけません
もちろん、どこにある、所属？

647
00:23:25,350 --> 00:23:26,160
>> 初めにすべての方法。

648
00:23:26,160 --> 00:23:27,720
ニールだから、私と一緒に来る。

649
00:23:27,720 --> 00:23:28,910
そして、あなたの名前は再び何でしたか？

650
00:23:28,910 --> 00:23:29,310
>> GRACE：グレース。

651
00:23:29,310 --> 00:23:29,710
>> DAVID J.マラン：グレース。

652
00:23:29,710 --> 00:23:29,920
OK。

653
00:23:29,920 --> 00:23:32,490
グレースだから、残念ながら、あなたがしている
方法での一種。

654
00:23:32,490 --> 00:23:34,290
では、どのようにこの問題を解決するのですか？

655
00:23:34,290 --> 00:23:34,490
右？

656
00:23:34,490 --> 00:23:37,500
これが配列の場合、そこ
わずか7箇所。

657
00:23:37,500 --> 00:23:40,830
ロブとのことを思い出して、私たちの話
年齢を宣言し、我々は唯一持っていた

658
00:23:40,830 --> 00:23:41,740
年齢の有限数？

659
00:23:41,740 --> 00:23:42,535
ここで同じ考え。

660
00:23:42,535 --> 00:23:44,300
我々は唯一のintの有限の数を持っている。

661
00:23:44,300 --> 00:23:47,590
グレースは、私たちのようなものである
方法は、我々はそうする方法を修正するのですか？

662
00:23:47,590 --> 00:23:49,555
>> 最も簡単な方法は、のようです
グレース、申し訳ありません。

663
00:23:49,555 --> 00:23:51,870
あなたが上に行くために必要があるとしている
私たちは部屋をそこにすることができます。

664
00:23:51,870 --> 00:23:55,290
さて、あなたは多分、これを考えれば
我々だけで、問題が悪化させた。

665
00:23:55,290 --> 00:23:58,510
そして多分私達は、何をしたかであれば理由
グレースは、適切な場所にあった？

666
00:23:58,510 --> 00:24:01,730
しかし、我々は彼女がいないと知っている、なぜなら
そうしないと、彼女はあったであろう

667
00:24:01,730 --> 00:24:03,980
前方に立っているではなく、
この時ニール、右？

668
00:24:03,980 --> 00:24:05,550
我々はすでに彼女の電話番号をチェックアウト。

669
00:24:05,550 --> 00:24:05,770
>> わかりました。

670
00:24:05,770 --> 00:24:09,110
だから今、ニールは、適切な場所でだと、
私は若干の最適化を行うことができます。

671
00:24:09,110 --> 00:24:11,740
次の分のために、私は無視するつもりです
すべて一緒にニール、ないように

672
00:24:11,740 --> 00:24:15,280
彼の時間を無駄にしたり、誤って
間違った場所に彼をスワップ。

673
00:24:15,280 --> 00:24:17,805
だから今、どのように私は次のを見つけるのですか
最小の要素？

674
00:24:17,805 --> 00:24:18,480
二つ。

675
00:24:18,480 --> 00:24:20,225
場合には、かなり良い番号だ
あなたは、前進したいと

676
00:24:20,225 --> 00:24:21,100
私はあなたを覚えているだろう。

677
00:24:21,100 --> 00:24:21,980
六、ダメ。

678
00:24:21,980 --> 00:24:24,820
フォー、3、7、5、ダメ。

679
00:24:24,820 --> 00:24:26,800
だから私はあなたに移動してみましょう
あなたの右の場所。

680
00:24:26,800 --> 00:24:28,470
そして、私たちはちょうどこの時間は幸運。

681
00:24:28,470 --> 00:24:31,350
>> さて、私はこれらを無視するつもりです
二人の男、そして今もう一つの操作を行い

682
00:24:31,350 --> 00:24:32,260
これを通過します。

683
00:24:32,260 --> 00:24:33,490
六、そのかなり少数。

684
00:24:33,490 --> 00:24:34,300
前進さあ。

685
00:24:34,300 --> 00:24:35,220
あ、ごめん。

686
00:24:35,220 --> 00:24:37,640
グレースの数は、優れている
とても楽しみに踏む。

687
00:24:37,640 --> 00:24:38,260
四つ。

688
00:24:38,260 --> 00:24:39,120
申し訳ありませんが、グレース。

689
00:24:39,120 --> 00:24:39,950
再び戻る。

690
00:24:39,950 --> 00:24:41,550
3番が良いです。

691
00:24:41,550 --> 00:24:42,290
七。

692
00:24:42,290 --> 00:24:42,720
ファイブ。

693
00:24:42,720 --> 00:24:43,550
そして今、あなたの名前は再び何ですか？

694
00:24:43,550 --> 00:24:44,000
>> JASON：ジェイソン。

695
00:24:44,000 --> 00:24:44,420
>> DAVID J.マラン：ジェイソン。

696
00:24:44,420 --> 00:24:47,050
だからジェイソンは現在、最小で
要素私が選択した。

697
00:24:47,050 --> 00:24:49,160
彼はどこへ行くのだろう？

698
00:24:49,160 --> 00:24:50,380
だからここで6です。

699
00:24:50,380 --> 00:24:51,210
そして、あなたの名前が再び？

700
00:24:51,210 --> 00:24:51,710
>> GABE：ゲイブ。

701
00:24:51,710 --> 00:24:52,340
>> DAVID J.マラン：ゲイブ。

702
00:24:52,340 --> 00:24:53,220
ゲイブは道であります。

703
00:24:53,220 --> 00:24:54,640
行うための最も簡単なものは何ですか？

704
00:24:54,640 --> 00:24:58,390
この二人を入れ替えて続行します。

705
00:24:58,390 --> 00:24:59,020
だから今見てみましょう。

706
00:24:59,020 --> 00:25:00,170
誰が最も小さいのですか？

707
00:25:00,170 --> 00:25:01,030
四つ。

708
00:25:01,030 --> 00:25:01,990
チートだけの種類、私をしましょう​​。

709
00:25:01,990 --> 00:25:03,090
ファイブは、最小になるだろう。

710
00:25:03,090 --> 00:25:05,220
は、ステップ実行したい場合、私は、次を見つける
前方に、私はをどうするかがありますか

711
00:25:05,220 --> 00:25:06,820
ゲイブとこれらの人、？

712
00:25:06,820 --> 00:25:08,450
再び交換します。

713
00:25:08,450 --> 00:25:10,740
だから今は、まだわずかに注文。

714
00:25:10,740 --> 00:25:14,140
私は、ゲイブが最小であることが判明
私はあなたたちを上を移動、彼を飛び出す。

715
00:25:14,140 --> 00:25:15,190
およびdone。

716
00:25:15,190 --> 00:25:17,200
>> だから、答えは同じです。

717
00:25:17,200 --> 00:25:18,600
最終的な結果は同じです。

718
00:25:18,600 --> 00:25:22,730
これら二つのアルゴリズムのどちら
良いですか？

719
00:25:22,730 --> 00:25:23,500
もう一つは、私が聞いた。

720
00:25:23,500 --> 00:25:24,252
なぜですか？

721
00:25:24,252 --> 00:25:25,900
>> SPEAKER 3：それはステップをNさん[聞こえない]。

722
00:25:25,900 --> 00:25:27,600
>> DAVID J.マラン：それはせいぜいnステップだ。

723
00:25:27,600 --> 00:25:28,490
興味深い。

724
00:25:28,490 --> 00:25:30,610
だから、にもかかわらずです？

725
00:25:30,610 --> 00:25:33,630
だから私はどのように見つけた
最小の要素？

726
00:25:33,630 --> 00:25:37,060
どのように多くのステップ私が取らなければならなかった
最小の要素を見つける？

727
00:25:37,060 --> 00:25:39,220
私はすべての道を見ていた
最後に、右？

728
00:25:39,220 --> 00:25:41,530
その最悪の場合には、どのようなので、
ニールはここで終わった場合はどうなりますか？

729
00:25:41,530 --> 00:25:45,700
だから最小の要素を見つける
私nステップ、またはnマイナス1をとります。

730
00:25:45,700 --> 00:25:46,100
しかし、OK。

731
00:25:46,100 --> 00:25:46,980
だからニールを修正。

732
00:25:46,980 --> 00:25:48,740
つまり、分ほど前に覚えておいてください。

733
00:25:48,740 --> 00:25:51,680
>> しかし、どのように私は次のを見つけました
最小の要素？

734
00:25:51,680 --> 00:25:54,830
それは、本当にNから1を引いた値、またはnマイナス2だ
ステップ数から。

735
00:25:54,830 --> 00:25:55,440
それでOK。

736
00:25:55,440 --> 00:25:57,390
だから私は、nマイナス2しました。

737
00:25:57,390 --> 00:25:57,600
わかりました。

738
00:25:57,600 --> 00:25:59,130
だから少し良い感じ。

739
00:25:59,130 --> 00:25:59,730
わかりました。

740
00:25:59,730 --> 00:26:03,270
次回はどのように多くの手順
3番を見つけるには？

741
00:26:03,270 --> 00:26:04,420
だからnはマイナス4。

742
00:26:04,420 --> 00:26:07,670
だから、少ないものを減少だ
各反復でのステップ。

743
00:26:07,670 --> 00:26:08,740
だから、これは正しい、良い感じでしょうか？

744
00:26:08,740 --> 00:26:13,450
最後の時間なら、それは、およそn回Nだった
今回はそれがnマイナス1、プラスNマイナスだ

745
00:26:13,450 --> 00:26:16,500
2、プラスNマイナス3、プラスN
マイナス4、ドット、ドット、ドット。

746
00:26:16,500 --> 00:26:18,750
しかし、あなたはあなたの高校を思い出した場合
教科書、少しチート

747
00:26:18,750 --> 00:26:24,380
数式を持って背面にシート、もし
あなたには、数字のこのシリーズを追加

748
00:26:24,380 --> 00:26:31,280
総ステップ数は何ですか
私はここで取ることになるだろう？

749
00:26:31,280 --> 00:26:36,580
>> これは、それらの一つであるように、n個のマイナス
2で割った1回N、。

750
00:26:36,580 --> 00:26:39,040
だから私は引っ張ることができるなら、私は見てみましょう
ちょっとこれまで。

751
00:26:39,040 --> 00:26:42,230
そして再び、私はいくつかの丸めのようなものだ
数字だけで私たちの生活をシンプルに保つため、

752
00:26:42,230 --> 00:26:47,830
しかし、私は思い出すように、それは、ifのようなものだ
私はその後、Nから1を引いた値のことを行うnのマイナス

753
00:26:47,830 --> 00:26:53,570
次いで2、nはマイナス3は、略だ
2の上にこのような何か、と私なら

754
00:26:53,570 --> 00:26:55,510
これを掛けて、そのう
実際にnの二乗。

755
00:26:55,510 --> 00:26:58,940
それはあまりにも良い感じていない。
2以上nを引いたN。

756
00:26:58,940 --> 00:27:00,350
>> しかし、ここでは、ことだ。

757
00:27:00,350 --> 00:27:03,720
コンピュータサイエンス、問題で
面白くするために起動したときにnが

758
00:27:03,720 --> 00:27:04,700
本当に大きくなる。

759
00:27:04,700 --> 00:27:08,110
、nが本当に大きくなったとき、そのうちの
これらの値はすべてを支配しようとしている

760
00:27:08,110 --> 00:27:09,750
他人の？

761
00:27:09,750 --> 00:27:10,990
それは右、乗、nのようなものだ？

762
00:27:10,990 --> 00:27:13,340
はい、2で割ると、かなり良いです。

763
00:27:13,340 --> 00:27:16,740
しかし、あなたは何十億の話をしている場合
データの断片、あるいは数兆の

764
00:27:16,740 --> 00:27:18,700
データの部分は、[OK]を、ので、
あなたには、倍の速度です。

765
00:27:18,700 --> 00:27:22,440
しかし、誰が本当に、その大きな数あれば気
この要因は、取得するのかである場合

766
00:27:22,440 --> 00:27:23,040
どんどん大きく。

767
00:27:23,040 --> 00:27:25,990
そして確かに、それはより多くを作る
この男より違い。

768
00:27:25,990 --> 00:27:29,120
だから君たちは右であるにもかかわらず、
第2のアルゴリズムは、我々はそれを呼ぶことにします

769
00:27:29,120 --> 00:27:32,970
選択ソート、現実の世界では、ある
少し速く潜在的に、私はいるので

770
00:27:32,970 --> 00:27:35,360
服用少なく
毎回繰り返します。

771
00:27:35,360 --> 00:27:37,340
>> それは本当に根本的に速くはありません。

772
00:27:37,340 --> 00:27:41,430
なぜなら私たちは実際にこれを外に再生する場合
の終わりに、nの値が大きい、

773
00:27:41,430 --> 00:27:44,750
日は、十分に大きなnに対して、それはまだだ
かなり遅い感じになるだろう。

774
00:27:44,750 --> 00:27:46,770
さて、私が1つをみましょう
その時点で最後のパス。

775
00:27:46,770 --> 00:27:48,920
それは私が呼ぶようなものだ
選択ソート。

776
00:27:48,920 --> 00:27:51,040
君たちは、自分自身をリセットすることができます
最後にもう一度？

777
00:27:51,040 --> 00:27:53,550
そして、この最後のケースでは、私は行くよ
何かを提案する

778
00:27:53,550 --> 00:27:54,970
挿入ソートと呼ばれる。

779
00:27:54,970 --> 00:27:57,470
という挿入ソート、概念的に、
少し異なる。

780
00:27:57,470 --> 00:28:00,980
>> 前後に行くというより
最小の要素を選択し、私は私

781
00:28:00,980 --> 00:28:05,030
ただこれらのそれぞれに対処するつもり
私は彼らに遭遇して、挿入すると男

782
00:28:05,030 --> 00:28:06,850
それらを正しい場所に。

783
00:28:06,850 --> 00:28:10,160
だから、僕は、グレースで開始するつもりだ
と私は彼女が4番だということを参照してください。

784
00:28:10,160 --> 00:28:11,720
4番はどこに属しているのでしょうか？

785
00:28:11,720 --> 00:28:14,940
私は、何も選別開始していない
そうグレースはすぐそこに滞在することを得る。

786
00:28:14,940 --> 00:28:18,355
そして今、私は、あなたができれば、請求するつもりです
これは、あなたの右に一歩を踏み出す

787
00:28:18,355 --> 00:28:21,650
私のソートされたリストは、これは私のです
ソートされていない残りのリスト。

788
00:28:21,650 --> 00:28:23,260
だから今、私は、次の続行するつもりです
そしてあなたの名前は何です再び？

789
00:28:23,260 --> 00:28:23,700
>> BRANSON：ブランソン。

790
00:28:23,700 --> 00:28:24,150
>> DAVID J.マラン：ブランソン。

791
00:28:24,150 --> 00:28:25,375
だからブランソンはナンバー2である。

792
00:28:25,375 --> 00:28:27,490
だから私はあなたを取るつもりです
一瞬外。

793
00:28:27,490 --> 00:28:30,940
そして今、あなたはどこに属しますか
この配列内の？

794
00:28:30,940 --> 00:28:32,360
だからグレースの右側に。

795
00:28:32,360 --> 00:28:35,670
だからもう一度、我々は作るの一種だ
グレースは、ここで多くの作業を行う。

796
00:28:35,670 --> 00:28:37,290
私たちはあなたをどこに置けばいい？

797
00:28:37,290 --> 00:28:40,120
だから我々は、にあなたをスライドさせるつもりだ
左、そこブランソンを挿入します。

798
00:28:40,120 --> 00:28:41,680
しかし、今私はそれを主張する
君たちが行われています。

799
00:28:41,680 --> 00:28:43,240
しかし、通知は、私は余分なスペースを使用していないよ。

800
00:28:43,240 --> 00:28:45,130
それはまだ2つの要素だ
ここで、こっち5。

801
00:28:45,130 --> 00:28:47,910
合計配列のサイズは7ですので、私はよ
すべての権利、浮気しない？

802
00:28:47,910 --> 00:28:51,950
>> だから今我々は、ここでゲイブと、持っている
番号6、あなたが属していますか？

803
00:28:51,950 --> 00:28:52,650
あなたは再び幸運。

804
00:28:52,650 --> 00:28:53,820
だから、すぐそこにとどまることを得る。

805
00:28:53,820 --> 00:28:57,210
ちょうど右にわずかな一歩を踏み出す
ただあなたがソートしていることを明確にする。

806
00:28:57,210 --> 00:29:00,520
そして今、我々は、再び数をニールを持って
1、あなたはどこに行くのですか？

807
00:29:00,520 --> 00:29:03,540
我々はそれを見ることから始めましょうどことなりました
しかし最初にこのアルゴリズム、

808
00:29:03,540 --> 00:29:05,950
一目では、かなりスマートな感じ、見
起こることを約何。

809
00:29:05,950 --> 00:29:07,370
あなたは前進することができれば。

810
00:29:07,370 --> 00:29:09,260
>> どこに私たちはニールを入れたいですか？

811
00:29:09,260 --> 00:29:11,830
だから、明らかにここにいるので、どのように
我々はそこにニールを得るのですか？

812
00:29:11,830 --> 00:29:12,970
このステップバイステップを実行してみましょう。

813
00:29:12,970 --> 00:29:15,620
あなたが行く必要があるかゲイブ、？

814
00:29:15,620 --> 00:29:19,590
うん、そう、一つの大きな一歩を踏み出す
または2つのハーフの手順が作る

815
00:29:19,590 --> 00:29:20,820
あそこに一歩。

816
00:29:20,820 --> 00:29:21,750
あなたが行くグレース、？

817
00:29:21,750 --> 00:29:22,510
グッド。

818
00:29:22,510 --> 00:29:23,500
だから、もう一歩。

819
00:29:23,500 --> 00:29:24,960
そして最後に、ブランソン？

820
00:29:24,960 --> 00:29:25,460
もう一つのステップ。

821
00:29:25,460 --> 00:29:27,190
そして今、我々は場所にニールを置くことができます。

822
00:29:27,190 --> 00:29:28,440
>> だから今、このロジックを続ける。

823
00:29:28,440 --> 00:29:32,420
我々はニールをシフトされていないにもかかわらず、
以上、過、および彼を配置するには、上

824
00:29:32,420 --> 00:29:36,420
どこに彼が行く、最悪の場合、
我々は、発生する可能性のある次の番号でし

825
00:29:36,420 --> 00:29:42,220
数である、と言う、数があった
ゼロ、次に我々は、すべてをシフトするつもりだ

826
00:29:42,220 --> 00:29:42,730
これらの人。

827
00:29:42,730 --> 00:29:44,950
負の、番号があると仮定
一方は、次に我々はシフトする必要があります

828
00:29:44,950 --> 00:29:46,080
これらの人のすべて。

829
00:29:46,080 --> 00:29:48,500
だから、私たちは本当に反転だけの種類だ
私たちがしていることなど、周りの問題

830
00:29:48,500 --> 00:29:52,620
から経費を転送
選択プロセスそう挿入

831
00:29:52,620 --> 00:29:56,930
君たちがちょうど持っていたようなプロセス、
大体nのマイナス何かを移動する

832
00:29:56,930 --> 00:29:57,940
ステップ数。

833
00:29:57,940 --> 00:30:01,200
そしてステップその数だけ起こっている
私は以上の数字を選択すると、増加する

834
00:30:01,200 --> 00:30:04,730
私はあなたたちを無理に勧め維持する必要がある場合
バック、バック、バック。

835
00:30:04,730 --> 00:30:08,320
>> とても悲しい事は今やこれらの全てです
アルゴリズムは乗nです。

836
00:30:08,320 --> 00:30:10,570
のは、先に行くと、これらのおかげでみましょう
みんな、これらのビットを可視化

837
00:30:10,570 --> 00:30:11,090
異なる。

838
00:30:11,090 --> 00:30:12,312
非常によくやった。

839
00:30:12,312 --> 00:30:14,120
>> [拍手]

840
00:30:14,120 --> 00:30:15,030
>> わかりました。

841
00:30:15,030 --> 00:30:16,280
そこに行く。

842
00:30:16,280 --> 00:30:18,390

843
00:30:18,390 --> 00:30:18,470
ありがとうございました - 

844
00:30:18,470 --> 00:30:19,190
>> BRANSON：[聞こえない]数字を維持。

845
00:30:19,190 --> 00:30:21,990
>> DAVID J.マラン：いいえ、あなたは可能性があり
同様の数字を維持。

846
00:30:21,990 --> 00:30:23,440
わかりました。

847
00:30:23,440 --> 00:30:24,100
うまく行って。

848
00:30:24,100 --> 00:30:25,300
わかりました。

849
00:30:25,300 --> 00:30:30,510
だから我々は今、まとめることができないかどうかを確認してみましょう
より迅速に、そしてより多くの視覚的、

850
00:30:30,510 --> 00:30:33,410
ただ何が起こったかを正確に
ここでは、次のとおり。

851
00:30:33,410 --> 00:30:36,510

852
00:30:36,510 --> 00:30:38,770
私が先に行くつもりです
とFirefoxをプルアップ。

853
00:30:38,770 --> 00:30:41,310
私たちは、このデモをリンクします
もちろんのウェブサイトで。

854
00:30:41,310 --> 00:30:43,870
Javaは動作させるために少し迷惑です
一部のブラウザでは、これらの日。

855
00:30:43,870 --> 00:30:46,760
あなたは自宅でこれで遊んでないのであれば、
Firefoxを使用する必要があるかもしれません実現

856
00:30:46,760 --> 00:30:47,990
それが動作して取得する。

857
00:30:47,990 --> 00:30:50,440
そして、私はこれをやろうとしているもの
デモは以下の通りです。

858
00:30:50,440 --> 00:30:54,875
>> 下部には、私は全体の束を持っている
スタートを含むメニューオプション、

859
00:30:54,875 --> 00:30:55,840
ボタンを停止します。

860
00:30:55,840 --> 00:30:59,450
また、余談として、があるように思われる
これらのプログラムのバグは、それによって

861
00:30:59,450 --> 00:31:03,720
実際にスタートを参照するか、または停止することはできません
ボタン[コマンドまたはAltキーを保持していない限り

862
00:31:03,720 --> 00:31:06,560
プラスとズームで、不思議なことに
あなたに複数のボタンを示しています。

863
00:31:06,560 --> 00:31:09,090
あなたがプレイする場合だからFYI
これで自宅で。

864
00:31:09,090 --> 00:31:12,870
今、私はちょうどにスタートをクリックするつもりです
瞬間、の遅延を指定した後、

865
00:31:12,870 --> 00:31:16,810
ただ、ここでは200ミリ秒、のような
従って我々は何が起こるかを見ることができます。

866
00:31:16,810 --> 00:31:20,180
>> だから私は、これが可視化であることを主張する
最初のアルゴリズムの

867
00:31:20,180 --> 00:31:23,730
これらの人は、それによって、バブルソートをした
我々は人々のペアワイズスワップ。

868
00:31:23,730 --> 00:31:27,490
この可視化するための鍵の洞察
ことは、バーの高さ

869
00:31:27,490 --> 00:31:30,510
数字のサイズを表す。

870
00:31:30,510 --> 00:31:32,210
だから、バー背
大きな数字。

871
00:31:32,210 --> 00:31:33,680
短いバー、少数。

872
00:31:33,680 --> 00:31:38,630
あなたが気づくならば、我々は通過しています
このアルゴリズムの最初の反復、

873
00:31:38,630 --> 00:31:42,620
大小の数字を入れ替えるので、
少数は最初に来ると

874
00:31:42,620 --> 00:31:44,280
大きな数字が右に行く。

875
00:31:44,280 --> 00:31:48,770
>> そしてできるだけ早く我々は配列の最後を得るよう
7よりも多くの数字から、我々はしている

876
00:31:48,770 --> 00:31:49,900
先頭に戻って行く。

877
00:31:49,900 --> 00:31:51,140
これを期待しています。

878
00:31:51,140 --> 00:31:54,860
左端に、その小さな男は起こっている
側にスワップし、これに

879
00:31:54,860 --> 00:31:56,010
プロセスが繰り返されます。

880
00:31:56,010 --> 00:31:59,450
今、この可視化はすぐに取得する
退屈なので、私が先に行くと停止させ

881
00:31:59,450 --> 00:32:04,170
それは、はるかに遅れ何かを変更
速いだけで、今の感触を得るために

882
00:32:04,170 --> 00:32:05,060
このアルゴリズム。

883
00:32:05,060 --> 00:32:07,840
>> 私はそれをスピードアップしましたので、あっても、これは
私のプロセッサをアップグレードするように、購入

884
00:32:07,840 --> 00:32:08,580
新しいコンピュータ。

885
00:32:08,580 --> 00:32:12,980
私は根本的に変わっていない私
アルゴリズムが、あなたは確かに多くを見ることができます

886
00:32:12,980 --> 00:32:16,800
明らかに人間と比べて、その大きな
数字は、一番上までバブリングさ

887
00:32:16,800 --> 00:32:20,900
と小さな数字はバブリングさ
ダウンの下へ。

888
00:32:20,900 --> 00:32:22,390
そして今、このことはここで並べ替え。

889
00:32:22,390 --> 00:32:25,260
そして余談として、正方形で、そこ
そこにはいくつかの簿記

890
00:32:25,260 --> 00:32:28,010
、あなたはどのように多くの比較を数える役立つ
またはどのように多くのスワップは、持っている

891
00:32:28,010 --> 00:32:28,950
実際に行われて。

892
00:32:28,950 --> 00:32:30,750
>> まあ、のはのいずれかを試してみましょう
我々が見た他​​の人。

893
00:32:30,750 --> 00:32:37,116
私はここでバブルソートをクリックしてみましょう、と
私が選択させ、そしてこの全体のWebページ

894
00:32:37,116 --> 00:32:38,936
少しバグがある。

895
00:32:38,936 --> 00:32:41,155
リスクを受け入れてみましょう
し、再度実行してください。

896
00:32:41,155 --> 00:32:44,560

897
00:32:44,560 --> 00:32:45,030
そうしよう。

898
00:32:45,030 --> 00:32:47,180
だから選択ソートを行うてみましょう。

899
00:32:47,180 --> 00:32:49,140
私にはわからない理由メニュー
そこの上に表示されます。

900
00:32:49,140 --> 00:32:54,070
ことを修正するためにズームしてみましょう
バグは、50に変更。

901
00:32:54,070 --> 00:32:56,020
ああ、実際に行うみましょう
そのはるかに高速。

902
00:32:56,020 --> 00:32:59,160
5ミリ秒かそ​​こら、とスタート。

903
00:32:59,160 --> 00:33:00,470
>> だから、これは選択ソートです。

904
00:33:00,470 --> 00:33:03,070
だからもう一度、私たちを考える
ここまで人間とやった。

905
00:33:03,070 --> 00:33:08,490
私たちは、配列を経て、選択
再び最小要素、

906
00:33:08,490 --> 00:33:09,250
そして再び、再び。

907
00:33:09,250 --> 00:33:11,110
今私はまだかなり悪かったと主張。

908
00:33:11,110 --> 00:33:15,010
それは、与えるか、または取る、まだN乗であった
しかし、それは、現実の世界では、ビットだった

909
00:33:15,010 --> 00:33:18,280
速く、私は確かに取っていたので、
やや少ない手順毎回。

910
00:33:18,280 --> 00:33:19,800
しかし、我々は唯一の何を話している？

911
00:33:19,800 --> 00:33:21,830
ここで多分40かそこらのバー？

912
00:33:21,830 --> 00:33:23,200
我々は4000万話していない。

913
00:33:23,200 --> 00:33:27,430
だから、と私には全く明らかではない
確かにかなりの利益であった。

914
00:33:27,430 --> 00:33:32,530
>> 私は今、戻って我々に変更してみましょう
選択された第三のアルゴリズム、

915
00:33:32,530 --> 00:33:33,180
挿入ソート。

916
00:33:33,180 --> 00:33:36,380
そして今、それは本当にバグだから
メニューには、実際にそこにあってはならない。

917
00:33:36,380 --> 00:33:40,840
だから今我々はここに戻って上にスクロールします
このアルゴリズムを開始します。

918
00:33:40,840 --> 00:33:43,270
叫び声を上げる、起動と停止。

919
00:33:43,270 --> 00:33:47,160
だから、この一種類のはかなりパターンを持ってい
そこに、それによって我々は再びだ

920
00:33:47,160 --> 00:33:50,240
ヒトの挿入、またはで
この場合、棒状に

921
00:33:50,240 --> 00:33:52,620
彼らの適切な場所。

922
00:33:52,620 --> 00:33:55,430
そしてそれはすでに前に行っている
私が振り向く。

923
00:33:55,430 --> 00:33:58,940
しかし、このいずれも、理論的には、
まだ乗nです。

924
00:33:58,940 --> 00:34:01,430
>> だから我々はまとめることができないかどうかを確認してみましょう
これらは以下の通り。

925
00:34:01,430 --> 00:34:04,750
私が先に行くようにとだけ与えるつもりだ
私たち話の一般的な方法のようなもの

926
00:34:04,750 --> 00:34:08,489
これらのことについて、私が紹介させて
ここに表記の少しだけ。

927
00:34:08,489 --> 00:34:12,480
あなたは大きなと呼ばれるものを参照しようとしている
O、それは文字通りですので、大きな

928
00:34:12,480 --> 00:34:16,320
O.そして、これは、そのコンピュータの方法です
科学者や数学者でも使用してい

929
00:34:16,320 --> 00:34:19,230
実行時間を記述する
いくつかのアルゴリズムの。

930
00:34:19,230 --> 00:34:21,400
それは実際にどのように多くの手順がかかりますか？

931
00:34:21,400 --> 00:34:25,080
>> 今私は自分自身を困らせるつもり
一瞬でここに私の手書き。

932
00:34:25,080 --> 00:34:29,020
しかし、私が先に行くとのことを言わせて
これはここに大きなOになります。

933
00:34:29,020 --> 00:34:33,610
そして、私は、他のものをご紹介しましょう
シンボル、資本オメガ。

934
00:34:33,610 --> 00:34:37,080
オメガは、反対であることを行っている
本質的に、ビッグO一方ビッグOの

935
00:34:37,080 --> 00:34:40,790
最悪の場合の手段、、どのくらいの時間
いくつかのアルゴリズムは、かかるかもしれませんで

936
00:34:40,790 --> 00:34:43,480
nは、オメガの用語はに起こっている
どのくらいの時間が場合がございます

937
00:34:43,480 --> 00:34:45,409
最良のケースで取る。

938
00:34:45,409 --> 00:34:48,090
そして、我々は何を意味わかります
一瞬で最高のケース。

939
00:34:48,090 --> 00:34:49,940
>> だから、単純な何かを始めましょう。

940
00:34:49,940 --> 00:34:54,719
私は線形探索から始めましょう。

941
00:34:54,719 --> 00:34:55,679
だからソートしない。

942
00:34:55,679 --> 00:34:58,000
私たちは、この線形探索と呼ぶことにします。

943
00:34:58,000 --> 00:35:01,140
そして今、少し作る
この外のテーブル。

944
00:35:01,140 --> 00:35:06,600
そして今、線形探索の場合には、
最悪の場合には、どのように多くのステップである

945
00:35:06,600 --> 00:35:11,770
それを見つけるために私を連れて行く
任意の選択肢の数は？

946
00:35:11,770 --> 00:35:14,540
そして、そこのnの合計ドア
またはn総数。

947
00:35:14,540 --> 00:35:15,940
最悪のケース。

948
00:35:15,940 --> 00:35:18,800
どのように多くのステップ私がする必要がありますするつもりです
配列内の数字50を見つけるために取る

949
00:35:18,800 --> 00:35:20,830
n個のドアの？

950
00:35:20,830 --> 00:35:21,410
そして、なぜ？

951
00:35:21,410 --> 00:35:23,680
それはすべての可能性があるため
末尾にオーバー方法。

952
00:35:23,680 --> 00:35:27,120
そんなにジェニファーが遭遇のように、
番号50はそうで、上のすべての方法であった

953
00:35:27,120 --> 00:35:30,760
最悪の場合、線形探索
nは大きなOであり、我々は言うでしょう。

954
00:35:30,760 --> 00:35:33,430
>> 最良の場合はどうでしょう、
あなたは本当にラッキー得れば？

955
00:35:33,430 --> 00:35:36,200
それはちょうど、1歩を踏み出すことになるだろう
ステップまたは定数。

956
00:35:36,200 --> 00:35:37,830
だから我々は、1としてあることを説明します。

957
00:35:37,830 --> 00:35:39,010
だから、これはかなり良いです。

958
00:35:39,010 --> 00:35:41,210
今、我々は何かをやっている場合
バイナリ検索を好きですか？

959
00:35:41,210 --> 00:35:43,860

960
00:35:43,860 --> 00:35:47,846
最悪でだからバイナリ検索、
場合、どのくらいの時間がかかった？

961
00:35:47,846 --> 00:35:49,250
>> [介在VOICES]

962
00:35:49,250 --> 00:35:51,310
>> DAVID J.マラン：だから実際に、私は
カップルの場所でそれを聞いた。

963
00:35:51,310 --> 00:35:56,390
だから、それは実際に、n個のログを与えるか、または取ることだ
我々は半分にリストを分割するようなので、

964
00:35:56,390 --> 00:36:00,730
再び、再び、再び、我々はできるだ
、最終的には、値を見つけるために、

965
00:36:00,730 --> 00:36:04,750
それはありますが、キャッチがあれば。

966
00:36:04,750 --> 00:36:08,590
我々が持っているという仮定は何ですか
バイナリ検索に当たり前？

967
00:36:08,590 --> 00:36:09,700
それは、ソートする必要があります。

968
00:36:09,700 --> 00:36:12,770
これは、ソートされていないです、あなたはものを分割することができます
何度も何度も半分にし、

969
00:36:12,770 --> 00:36:15,490
左に行くことができ、あなたが右に行くことができ、
あなたには、左と右に行くことができますが、している

970
00:36:15,490 --> 00:36:18,070
要素を検索する場合に行っていない
リストがソートされていない、なぜなら

971
00:36:18,070 --> 00:36:18,790
あなたはそれを見逃す可能性があります。

972
00:36:18,790 --> 00:36:22,120
あなたのヒューリスティックので、左に行くために
または右にそれがあれば欠陥であることを行っている

973
00:36:22,120 --> 00:36:23,420
確かにソートされません。

974
00:36:23,420 --> 00:36:26,110
だから隠れたコストのようなものはあり
このようなものを使用する。

975
00:36:26,110 --> 00:36:29,250
>> それでは、我々のソートに手放す
アルゴリズムは、検索しない - 

976
00:36:29,250 --> 00:36:31,140
ああ、実際のこの空白で手放す。

977
00:36:31,140 --> 00:36:33,190
最良のケースでのバイナリ検索？

978
00:36:33,190 --> 00:36:36,290
それだけであるために発生した場合にも1である
配列の非常に途中で、または

979
00:36:36,290 --> 00:36:37,810
電話帳の真ん中。

980
00:36:37,810 --> 00:36:39,710
今、バブルソートを行うてみましょう。

981
00:36:39,710 --> 00:36:42,570
だから、もう一度、今、私たちは、入力している
並べ替えではなく、検索します。

982
00:36:42,570 --> 00:36:47,220
>> 最悪の場合には、どのように多くの手順は、我々をしました
請求バブルソートは、取るために起こっている？

983
00:36:47,220 --> 00:36:48,410
nの2乗。

984
00:36:48,410 --> 00:36:49,200
だから私はそれを描くつもりです。

985
00:36:49,200 --> 00:36:51,710
ああ、私の筆跡はさらに悪く見える
それがあの大きな投影いるときに。

986
00:36:51,710 --> 00:36:52,510
わかりました。

987
00:36:52,510 --> 00:36:53,570
だからですnの二乗。

988
00:36:53,570 --> 00:36:59,460
とバブルソートの最良のケースで、
どのように多くのステップには、取るために起こっている？

989
00:36:59,460 --> 00:37:00,980
1、私は聞いた。

990
00:37:00,980 --> 00:37:01,760
>> SPEAKER 1：N。

991
00:37:01,760 --> 00:37:03,286
>> DAVID J.マラン：nは、私が聞いた。

992
00:37:03,286 --> 00:37:04,200
>> SPEAKER：1 2。

993
00:37:04,200 --> 00:37:05,010
>> DAVID J.マラン：2、私は聞いた。

994
00:37:05,010 --> 00:37:06,670
私は3つのを聞くのですか？

995
00:37:06,670 --> 00:37:07,080
わかりました。

996
00:37:07,080 --> 00:37:11,390
だから私は、n、2、1を聞いてきましたが、ピックましょう
それらの離れて少なくとも最初

997
00:37:11,390 --> 00:37:12,330
提案、1。

998
00:37:12,330 --> 00:37:15,370
それがあるため、悪い本能ではありません
の種類は、ここでパターンに従います。

999
00:37:15,370 --> 00:37:19,670
しかし、どのように、それは、1歩を踏み出している場合にのみ
世界は私が主張することができ、そのリスト

1000
00:37:19,670 --> 00:37:22,900
私が唯一許されている場合はどうするため、ソートされている
1歩を踏み出すことを、どのように多くの要素

1001
00:37:22,900 --> 00:37:25,230
私は実際にことを確認してくださいだろうか？

1002
00:37:25,230 --> 00:37:28,270
nがあることを意味まあ、ただ1、
の外になる可能性がマイナス1の要素

1003
00:37:28,270 --> 00:37:31,310
順序、および私はちょうど後信仰に行くよ
その1要素を見て

1004
00:37:31,310 --> 00:37:31,850
ものがソートされます。

1005
00:37:31,850 --> 00:37:33,930
だから1はここで正解ではありません。

1006
00:37:33,930 --> 00:37:35,710
だから最低限、どのように多くの
私が見なければならないのですか？

1007
00:37:35,710 --> 00:37:36,680
>> [介在VOICES]

1008
00:37:36,680 --> 00:37:40,160
>> DAVID J.マラン：本当にNから1を引いた値、または、
nは、私はすべてを見てする必要があるため

1009
00:37:40,160 --> 00:37:42,190
ことを確認する要素
それは、順不同ではありません。

1010
00:37:42,190 --> 00:37:44,750
しかし、再び、私たちは波のようなものでしょう
小さい数字で、手や

1011
00:37:44,750 --> 00:37:47,100
nが大きくなるように、彼らがしている、と仮定する
とにかく面白くない。

1012
00:37:47,100 --> 00:37:48,380
だからバブルソートです。

1013
00:37:48,380 --> 00:37:49,830
そして今、最後の2つを行うてみましょう。

1014
00:37:49,830 --> 00:37:53,520
選択ソートしてから、我々はよ
挿入ソートを行う。

1015
00:37:53,520 --> 00:37:57,160
そして、我々はあなたを爆破する
ずっと何か心

1016
00:37:57,160 --> 00:37:58,926
これらのすべてのよりも良い。

1017
00:37:58,926 --> 00:38:00,410
わかりました。

1018
00:38:00,410 --> 00:38:04,700
>> 最悪の場合は何を実行している
選択ソートの時間？

1019
00:38:04,700 --> 00:38:05,680
>> SPEAKER 4：nの二乗。

1020
00:38:05,680 --> 00:38:06,710
>> DAVID J.マラン：nの正方形は、私が聞いている。

1021
00:38:06,710 --> 00:38:09,790
しかし、なぜnは直感的に、乗？

1022
00:38:09,790 --> 00:38:11,170
>> SPEAKER 4：我々はただそれをやっているので。

1023
00:38:11,170 --> 00:38:12,260
>> DAVID J.マラン：我々はただそれをやっているので。

1024
00:38:12,260 --> 00:38:12,550
OK。

1025
00:38:12,550 --> 00:38:13,380
答えはグッド。

1026
00:38:13,380 --> 00:38:16,660
しかし、直感的に、なぜ選択がある
ソートnの二乗？

1027
00:38:16,660 --> 00:38:18,980
我々は何をすべきかを持っていなかった
何度も何度も？

1028
00:38:18,980 --> 00:38:22,570
我々は、を通してスキャン続けなければならなかった
あなた最小、あなたは

1029
00:38:22,570 --> 00:38:24,020
最小は、最小である。

1030
00:38:24,020 --> 00:38:27,480
と付与、我々は、nを取ることができました
その後のステップ、その後Nマイナス1、nはマイナス2。

1031
00:38:27,480 --> 00:38:30,700
しかし、あなたはどのようなものすべてを追加した場合、
または、私が追加した信仰にそれを取る

1032
00:38:30,700 --> 00:38:34,810
事前にそれらまで、我々は、n大体得る
いくつかのより小さい数字マイナス乗。

1033
00:38:34,810 --> 00:38:36,730
だから私は、このnが乗呼ぶつもりです。

1034
00:38:36,730 --> 00:38:39,530
しかし、最良の選択ソートと
場合、それがどのように多くのステップである

1035
00:38:39,530 --> 00:38:40,632
私を取るつもり？

1036
00:38:40,632 --> 00:38:41,840
>> SPEAKER 5：[聞こえない]

1037
00:38:41,840 --> 00:38:44,350
>> DAVID J.マラン：それは残念なことだ
まだN乗、右？

1038
00:38:44,350 --> 00:38:49,590
私は最小を選択している場合があるため
要素、そして我々は、ここで7人を持っていた

1039
00:38:49,590 --> 00:38:53,280
私が唯一知っている、かつて私は、非常に得る
私は最小のを見つけたことを終わり、

1040
00:38:53,280 --> 00:38:55,670
数字、どこ彼または
彼女はあったかもしれない。

1041
00:38:55,670 --> 00:38:58,820
しかし、どのように私は次を見つけるのですか
最小数？

1042
00:38:58,820 --> 00:39:00,160
私は別のパスをしなければならない。

1043
00:39:00,160 --> 00:39:04,810
だから、最良の場合で、何か
選択ソートへの入力？

1044
00:39:04,810 --> 00:39:07,830
それは、すでにソートリスト、ナンバーワンだ
ナンバー2、ナンバー3、4番。

1045
00:39:07,830 --> 00:39:08,600
しかし、私はコンピュータです。

1046
00:39:08,600 --> 00:39:10,190
私は唯一の1を見ることができます
時のもの。

1047
00:39:10,190 --> 00:39:12,465
私は一歩を踏み出すに並べ替えることはできません
背中人間と言うように、

1048
00:39:12,465 --> 00:39:14,030
oohのは、これは正しく見える。

1049
00:39:14,030 --> 00:39:17,580
>> 私だけで正当性を裁くことができます
選択することにより、選択ソート

1050
00:39:17,580 --> 00:39:18,370
最小数。

1051
00:39:18,370 --> 00:39:21,390
しかし、私はナンバーワンが最初に見つけたとしても、
私は約何がわからない場合

1052
00:39:21,390 --> 00:39:24,460
私はしない他の数字、すべてのI
私は配列を渡してきたことを知っている

1053
00:39:24,460 --> 00:39:27,930
である背後のドアまたは一連
数字、私はその1つを知っている唯一の方法

1054
00:39:27,930 --> 00:39:28,680
最小でしたか？

1055
00:39:28,680 --> 00:39:32,440
私はここにすべての方法を取得し、実現した場合、
いまいましい、1は確かに最も小さかった。

1056
00:39:32,440 --> 00:39:34,870
>> しかし、どのように私はそのことを決定しない
二人は次の最小である？

1057
00:39:34,870 --> 00:39:38,350
同じ非効率を実行して、
何度も何度も。

1058
00:39:38,350 --> 00:39:42,210
だから最終的には、挿入ソートと、
どのように、最悪の場合には、

1059
00:39:42,210 --> 00:39:44,990
我々はそれが実行すると言ったのですか？

1060
00:39:44,990 --> 00:39:49,100
それはあまりにも乗nです。

1061
00:39:49,100 --> 00:39:53,020
そして、どのようにについての最もよいケース付き？

1062
00:39:53,020 --> 00:39:56,282
私たちは、クリフハンガーとしてそれを残しておきます。

1063
00:39:56,282 --> 00:40:00,090
我々は、その空白次回に記入します
しかし、最初に私たちことを提案させて

1064
00:40:00,090 --> 00:40:02,620
根本的によりよくする
これらすべて、大丈夫？

1065
00:40:02,620 --> 00:40:05,220
>> だから、自分のために何を考えて挿入
ソートは、になるだろう。

1066
00:40:05,220 --> 00:40:06,910
まあ、それは、非常に劇的ではなかった
私は一人ですので、

1067
00:40:06,910 --> 00:40:08,970
それは変化を見た。

1068
00:40:08,970 --> 00:40:09,620
うわー。

1069
00:40:09,620 --> 00:40:10,420
OK。

1070
00:40:10,420 --> 00:40:12,615
そこでここでは多少持っている
別のデモ。

1071
00:40:12,615 --> 00:40:16,580
私はここにズームインした場合は、その上を見ることができます
で、我々はバブルソートを持って左

1072
00:40:16,580 --> 00:40:20,740
我々は選択ソートを持って中間、上
右端に、我々は何かを持って我々

1073
00:40:20,740 --> 00:40:23,380
まだ見ていない
マージソートと呼ばれる。

1074
00:40:23,380 --> 00:40:26,080
しかし、我々がしてきたかを検討
今日はこれまでここでやって。

1075
00:40:26,080 --> 00:40:29,200
ジェニファーは、最初のステージに上がってきたとき、
私たちは、数値の配列を経て

1076
00:40:29,200 --> 00:40:33,750
再び、再び、線形探索と、
そして我々は大きなO、線形実行時間を得た

1077
00:40:33,750 --> 00:40:35,100
nは、いわば。

1078
00:40:35,100 --> 00:40:41,000
>> 我々は現在の最初の週を考えると
クラス、我々は分割統治していたとき、

1079
00:40:41,000 --> 00:40:43,740
そして我々は、涙の電話帳を持っていた
とジェニファー、そして我々をまとめて

1080
00:40:43,740 --> 00:40:47,500
にあったキー洞察、そのレバレッジ
で何度も何度も自分自身を繰り返す

1081
00:40:47,500 --> 00:40:50,930
何とか、捨て、捨て
、捨て問題の半分、または

1082
00:40:50,930 --> 00:40:55,320
一般に、半分に分割する問題を、
その後の小さい部分を治療する

1083
00:40:55,320 --> 00:40:59,630
概念的には同等の問題
他に、我々は何とかやった

1084
00:40:59,630 --> 00:41:00,910
根本的に良い。

1085
00:41:00,910 --> 00:41:04,720
しかし、バブルソートと、選択に
ソートは、挿入ソートで、我々は可能性をしました

1086
00:41:04,720 --> 00:41:06,560
ジェニファーがやっていることはそのような洞察力はありません。

1087
00:41:06,560 --> 00:41:10,220
我々はかなりちょうど戻って歩いて、
等倍の全体の束、そして我々

1088
00:41:10,220 --> 00:41:12,650
微調整のものは少し、スワッピング
この順序で、多分

1089
00:41:12,650 --> 00:41:13,730
挿入または選択する。

1090
00:41:13,730 --> 00:41:16,950
しかし、一日の終わりに、私は多くのことをやった
ぎこちないウォーキングの前後に。

1091
00:41:16,950 --> 00:41:21,160
私たちは本当に活用する何かをしなかった
ジェニファーのようにスマートでは分割のようでした

1092
00:41:21,160 --> 00:41:22,040
と征服。

1093
00:41:22,040 --> 00:41:25,620
>> だからソートマージ、対照的に、その我々
来週までは表示されません、それが起こっている

1094
00:41:25,620 --> 00:41:29,540
レバレッジ割ってそのキーアイデアへ
入力した後、半分にしてから、

1095
00:41:29,540 --> 00:41:30,580
半減、その後半減。

1096
00:41:30,580 --> 00:41:34,590
そして、そのループの各反復で、
左半分をソートし、右

1097
00:41:34,590 --> 00:41:38,200
半分、左半分のその後左半分、
次に左の右半分、

1098
00:41:38,200 --> 00:41:40,990
右半分の左半分、および
右半分の右半分。

1099
00:41:40,990 --> 00:41:42,840
と何度も何度も繰り返す。

1100
00:41:42,840 --> 00:41:46,170
>> だから、視覚的にこれを見るが、このよ
来週私たちを待っているものです。

1101
00:41:46,170 --> 00:41:49,760
一般的に、ときに我々は少し考える
そのような問題で少し難しい。

1102
00:41:49,760 --> 00:41:52,435

1103
00:41:52,435 --> 00:41:57,970
我々は左側に乗N、Nた
中間の二乗であり、n

1104
00:41:57,970 --> 00:41:59,400
右側にn個を記録。

1105
00:41:59,400 --> 00:42:00,590
だからあなたの本当の接戦はあり。

1106
00:42:00,590 --> 00:42:02,040
私たちは、月曜日にお会いしましょう​​。

1107
00:42:02,040 --> 00:42:05,163
>> [拍手]