1
00:00:00,000 --> 00:00:00,990

2
00:00:00,990 --> 00:00:02,970
>> [音楽再生]

3
00:00:02,970 --> 00:00:10,400

4
00:00:10,400 --> 00:00:12,550
>> DAVID J.マラン：これはCS50です。

5
00:00:12,550 --> 00:00:14,612
そして、これを週に3回の開始です。

6
00:00:14,612 --> 00:00:16,820
だから我々はエキサイティングなをたくさん持っています
今日カバーするもの。

7
00:00:16,820 --> 00:00:20,160
多くの機会のための
ステージに上がっボランティア。

8
00:00:20,160 --> 00:00:22,780
そして最終的に、今日は、
ないコードに関するすべてで。

9
00:00:22,780 --> 00:00:24,820
しかし、それは、アイデアについてですと
それはアルゴリズムについてです、

10
00:00:24,820 --> 00:00:28,420
実際の一部を戻します
週ゼロから学んだ教訓、

11
00:00:28,420 --> 00:00:31,910
前記リコール、我々
この極悪非道を導入しました。

12
00:00:31,910 --> 00:00:33,880
また、借入のインスピレーション
それから、スタートへ

13
00:00:33,880 --> 00:00:36,879
これまで以上に洗練された解決するために
アルゴリズム的な問題。

14
00:00:36,879 --> 00:00:38,420
しかし、最初に、お知らせのカップル。

15
00:00:38,420 --> 00:00:42,020
だから1、あなたが参加したい場合
昼食時CS50のスタッフとクラスメート

16
00:00:42,020 --> 00:00:44,670
今週の金曜日、両方こことで
ケンブリッジ、ニューヘブンで、

17
00:00:44,670 --> 00:00:48,060
コー​​スのをご覧ください。
URLは見つけることができるウェブサイト。

18
00:00:48,060 --> 00:00:50,390
この水曜日ます講義します
サンダースここなりません。

19
00:00:50,390 --> 00:00:53,610
それはとても、オンラインでのみとなります
CS50のウェブサイトでで曲、

20
00:00:53,610 --> 00:00:55,850
ここでケンブリッジのか
またはニューヘブンにも。

21
00:00:55,850 --> 00:00:58,110
>> そして、問題は2セット
あなたの手の中に既にあります。

22
00:00:58,110 --> 00:01:03,067
あなたはまだで潜っていない場合は、私を許可します
強い言葉で表現の提案を提供します

23
00:01:03,067 --> 00:01:05,150
特に今、として、その
問題は、事前に設定し、

24
00:01:05,150 --> 00:01:08,669
あなたは本当に、今そうでない場合は起動しますか
週末に少し手を出すか、前

25
00:01:08,669 --> 00:01:10,710
彼らが最初に出て行くとき
金曜日、あなたはだろうから

26
00:01:10,710 --> 00:01:14,380
彼らは必ずしもじゃないことを見つけます
長いまたはより挑戦的なあたりになっ

27
00:01:14,380 --> 00:01:14,950
SE。

28
00:01:14,950 --> 00:01:17,575
私はあなたがそれを見つけると思いますが、中に
一般的に、彼らはおよそ取る傾向にあります

29
00:01:17,575 --> 00:01:18,892
同じ時間のまわり。

30
00:01:18,892 --> 00:01:20,850
しかし、それは確かに依存します
学生、およびその上に

31
00:01:20,850 --> 00:01:22,880
考え方によって異なります
これであなたはそれに近づきます。

32
00:01:22,880 --> 00:01:24,910
しかし、常に、あなたが行っています
いくつかの壁にぶつかるために、

33
00:01:24,910 --> 00:01:26,350
あなたがヒットするつもりです
いくつかのバグ、そしてあなただけです

34
00:01:26,350 --> 00:01:27,950
できるようにするつもりはありません
いくつかの時点でそれを乗り越えます。

35
00:01:27,950 --> 00:01:31,380
そして、それはできるように非常貴重です
離れたステップ、次の日に戻ってきて、

36
00:01:31,380 --> 00:01:35,286
CS50に営業時間、ポストに行く話し合います
等が、実際にブロックされていない取得します。

37
00:01:35,286 --> 00:01:36,160
だから、心の中でそれを維持します。

38
00:01:36,160 --> 00:01:40,830
可能な限り最も早い開始
あなたができる最善のことです。

39
00:01:40,830 --> 00:01:44,160
我々はスタート地点だからここです
0週目でオーバークラス。

40
00:01:44,160 --> 00:01:47,441
そして、私たちはボランティアを得ることができます
ここで私はマイクを見つけるには？

41
00:01:47,441 --> 00:01:47,940
OK。

42
00:01:47,940 --> 00:01:48,900
すでに立ち。

43
00:01:48,900 --> 00:01:50,080
アップさあ。

44
00:01:50,080 --> 00:01:53,707
それはそれが動作するように起こっているかだと思います。

45
00:01:53,707 --> 00:01:54,415
あなたの名前は何ですか？

46
00:01:54,415 --> 00:01:55,570
ALAN ESTRADA：アラン・エストラーダ。

47
00:01:55,570 --> 00:01:56,778
DAVID J.マラン：アラン・エストラーダ。

48
00:01:56,778 --> 00:01:57,910
アップさあ。

49
00:01:57,910 --> 00:01:58,619
始めまして。

50
00:01:58,619 --> 00:01:59,910
ALAN ESTRADA：はじめまして。

51
00:01:59,910 --> 00:02:02,772
DAVID J.マラン：そして、あなたがここにいました
もちろん、0週目で私達、と。

52
00:02:02,772 --> 00:02:03,028
ALAN ESTRADA：私がいました。

53
00:02:03,028 --> 00:02:03,160
私がいました。

54
00:02:03,160 --> 00:02:05,868
>> DAVID J.マラン：だからあなたが行くことができます
先とマイク・スミスたちを見つけます、

55
00:02:05,868 --> 00:02:08,639
早くすることができますように！

56
00:02:08,639 --> 00:02:10,639
早くすることができますように。

57
00:02:10,639 --> 00:02:13,756
文字通り問題を引き裂きます
半分にあなたがする必要があるとして。

58
00:02:13,756 --> 00:02:15,130
>> ALAN ESTRADA：ええと。

59
00:02:15,130 --> 00:02:17,380
DAVID J.マラン：文字通り
半分に問題を引き裂きます。

60
00:02:17,380 --> 00:02:20,210

61
00:02:20,210 --> 00:02:22,083
>> ALAN ESTRADA：ああ。

62
00:02:22,083 --> 00:02:22,583
mmです。

63
00:02:22,583 --> 00:02:23,300
とても良い。

64
00:02:23,300 --> 00:02:23,700
>> DAVID J.マラン：OK。

65
00:02:23,700 --> 00:02:24,200
良い。

66
00:02:24,200 --> 00:02:24,701
ありがとう。

67
00:02:24,701 --> 00:02:25,700
ALAN ESTRADA：非常に良いです。

68
00:02:25,700 --> 00:02:26,210
OK。

69
00:02:26,210 --> 00:02:27,610
>> DAVID J.マラン：そして今、
あなたはそれを絞り込まました

70
00:02:27,610 --> 00:02:29,320
問題の半分のサイズに。

71
00:02:29,320 --> 00:02:31,267
今、私たちは四半期までです。

72
00:02:31,267 --> 00:02:33,475
あなたが注意を払っています
我々はどちら側に維持していますか？

73
00:02:33,475 --> 00:02:34,405
>> [笑い]

74
00:02:34,405 --> 00:02:35,970
>> ALAN ESTRADA：はい、私はthink--

75
00:02:35,970 --> 00:02:37,594
>> DAVID J.マラン：我々はどのようなセクションにありますか？

76
00:02:37,594 --> 00:02:39,150
ALAN ESTRADA：マフラー、そう。

77
00:02:39,150 --> 00:02:39,941
>> DAVID J.マラン：OK。

78
00:02:39,941 --> 00:02:42,810
しかし、マイク・スミスが起こっています
マフラーの後になるように。

79
00:02:42,810 --> 00:02:44,130
So--

80
00:02:44,130 --> 00:02:48,180
>> [笑い]

81
00:02:48,180 --> 00:02:48,742
>> 大丈夫。

82
00:02:48,742 --> 00:02:50,200
ALAN ESTRADA：どこを探していますか？

83
00:02:50,200 --> 00:02:52,049
DAVID J.マラン：マイク・スミス。

84
00:02:52,049 --> 00:02:53,090
ALAN ESTRADA：マイク・スミス。

85
00:02:53,090 --> 00:02:54,760
DAVID J.マラン：今、私たちは、手術にしています。

86
00:02:54,760 --> 00:02:57,840
今、医師。

87
00:02:57,840 --> 00:02:58,340
Now--

88
00:02:58,340 --> 00:02:59,856
>> ALAN ESTRADA：のは本当で手放しますLet's-。

89
00:02:59,856 --> 00:03:00,370
レアル。

90
00:03:00,370 --> 00:03:00,970
>> DAVID J.マラン：レアル。

91
00:03:00,970 --> 00:03:01,470
OK。

92
00:03:01,470 --> 00:03:03,700
あなたはレアルが必要な場合。

93
00:03:03,700 --> 00:03:05,250
さて、マイク・スミスは、方法は何ですか？

94
00:03:05,250 --> 00:03:06,250
>> ALAN ESTRADA：この方法です。

95
00:03:06,250 --> 00:03:07,333
>> DAVID J.マラン：方法は？

96
00:03:07,333 --> 00:03:08,240
ALAN ESTRADA：待ってください。

97
00:03:08,240 --> 00:03:08,790
M is--ね？

98
00:03:08,790 --> 00:03:09,110
我々はwith--開始しました

99
00:03:09,110 --> 00:03:10,090
>> DAVID J.マラン：うん。

100
00:03:10,090 --> 00:03:10,650
これらは、左ています。

101
00:03:10,650 --> 00:03:11,430
あなたの右。

102
00:03:11,430 --> 00:03:11,710
>> ALAN ESTRADA：うん。

103
00:03:11,710 --> 00:03:13,126
>> DAVID J.マラン：だからマイクのここインチ

104
00:03:13,126 --> 00:03:13,990
ALAN ESTRADA：何？

105
00:03:13,990 --> 00:03:14,665
>> [笑い]

106
00:03:14,665 --> 00:03:17,365

107
00:03:17,365 --> 00:03:18,330
>> 悪い例、みんな。

108
00:03:18,330 --> 00:03:18,830
ごめんなさい。

109
00:03:18,830 --> 00:03:21,610
DAVID J.マラン：これはお教えします
あなたの椅子から跳躍します。

110
00:03:21,610 --> 00:03:22,318
>> ALAN ESTRADA：ああ。

111
00:03:22,318 --> 00:03:22,890
ああ。

112
00:03:22,890 --> 00:03:23,390
見つけた。

113
00:03:23,390 --> 00:03:24,670
見つけた。

114
00:03:24,670 --> 00:03:25,170
ああ。

115
00:03:25,170 --> 00:03:25,669
ああ。

116
00:03:25,669 --> 00:03:26,812
これは私があなたを持って、[OK]をis--。

117
00:03:26,812 --> 00:03:27,520
右ここスミス？

118
00:03:27,520 --> 00:03:28,894
>> DAVID J.マラン：スミスは、ありがとうございました。

119
00:03:28,894 --> 00:03:30,535
だから私はスミスを見ておこうか！

120
00:03:30,535 --> 00:03:30,790
>> ALAN ESTRADA：ああ、うん。

121
00:03:30,790 --> 00:03:31,340
ダメダメダメ。

122
00:03:31,340 --> 00:03:31,600
いや、ああ。

123
00:03:31,600 --> 00:03:31,940
これは私のものです。

124
00:03:31,940 --> 00:03:32,580
>> DAVID J.マラン：ああ、あなたはスミスを得ました。

125
00:03:32,580 --> 00:03:33,415
OK。

126
00:03:33,415 --> 00:03:34,040
>> ALAN ESTRADA：ええ、私
右ここでスミスを得ました。

127
00:03:34,040 --> 00:03:34,700
申し訳ありませんが、みんな。

128
00:03:34,700 --> 00:03:35,860
私はMichael--を考え、私たち
マイケルを探していました。

129
00:03:35,860 --> 00:03:36,550
ごめんなさい。

130
00:03:36,550 --> 00:03:37,550
>> DAVID J.マラン：それはOKです。

131
00:03:37,550 --> 00:03:39,950
すべての権利、今、私たちはしています
Pacciniアンド・サンズへ。

132
00:03:39,950 --> 00:03:41,242
>> ALAN ESTRADA：Pacciniと息子。

133
00:03:41,242 --> 00:03:43,158
DAVID J.マラン：あなただけ
そして私は、この上です。

134
00:03:43,158 --> 00:03:44,050
OK。

135
00:03:44,050 --> 00:03:45,130
私たちにマイク・スミスを検索します。

136
00:03:45,130 --> 00:03:45,830
スミス。

137
00:03:45,830 --> 00:03:46,310
>> ALAN ESTRADA：スミス。

138
00:03:46,310 --> 00:03:46,750
>> DAVID J.マラン：スミス。

139
00:03:46,750 --> 00:03:47,728
私たちは、ごみRにしています。

140
00:03:47,728 --> 00:03:48,644
ALAN ESTRADA：酷いです。

141
00:03:48,644 --> 00:03:50,096
ああ。

142
00:03:50,096 --> 00:03:52,480
これは、しばらく時間がかかるとしています。

143
00:03:52,480 --> 00:03:54,340
>> [笑い]

144
00:03:54,340 --> 00:03:55,804

145
00:03:55,804 --> 00:03:56,720
DAVID J.マラン：靴。

146
00:03:56,720 --> 00:03:58,080
私たちは、靴にしています。

147
00:03:58,080 --> 00:04:00,210
>> ALAN ESTRADA：今、私たちはgonna--ています

148
00:04:00,210 --> 00:04:01,105
>> DAVID J.マラン：ニース。

149
00:04:01,105 --> 00:04:01,980
ALAN ESTRADA：Which--

150
00:04:01,980 --> 00:04:03,620
[笑い]

151
00:04:03,620 --> 00:04:05,440
ああ、これは素晴らしいです。

152
00:04:05,440 --> 00:04:06,910
[笑い]

153
00:04:06,910 --> 00:04:08,380

154
00:04:08,380 --> 00:04:09,390
>> DAVID J.マラン：それはOKです。

155
00:04:09,390 --> 00:04:11,365
>> ALAN ESTRADA：ああ、これは良いです。

156
00:04:11,365 --> 00:04:14,425
私はするつもりだとは思いません
この後PSAT仲間を持っています。

157
00:04:14,425 --> 00:04:15,300
DAVID J.マラン：良いです。

158
00:04:15,300 --> 00:04:16,078
スポーツ。

159
00:04:16,078 --> 00:04:17,036
ALAN ESTRADA：スポーツ。

160
00:04:17,036 --> 00:04:18,668
UM、L、M、N、O、P。

161
00:04:18,668 --> 00:04:19,459
DAVID J.マラン：OK。

162
00:04:19,459 --> 00:04:21,600
それでは、半分にこれを引き裂くてみましょう。

163
00:04:21,600 --> 00:04:22,270
大丈夫です。

164
00:04:22,270 --> 00:04:25,606
マイクので、これは、とにかく不十分終了します
スミスはイエローページになりません。

165
00:04:25,606 --> 00:04:26,430
>> ALAN ESTRADA：おやおや。

166
00:04:26,430 --> 00:04:27,140
>> DAVID J.マラン：いいえ、それはOKです。

167
00:04:27,140 --> 00:04:28,930
しかし、ここでは次のようにふりをしましょう
彼はこのページにあります。

168
00:04:28,930 --> 00:04:33,260
だから今、あなたがダウンして、問題を酔っぱらったしました
1ページに、我々はマイク・スミスを見つけました。

169
00:04:33,260 --> 00:04:35,180
>> [応援]

170
00:04:35,180 --> 00:04:35,757

171
00:04:35,757 --> 00:04:36,340
わかりました、ありがとうございます。

172
00:04:36,340 --> 00:04:40,700

173
00:04:40,700 --> 00:04:41,200
OK。

174
00:04:41,200 --> 00:04:43,646
それが臨時ました。

175
00:04:43,646 --> 00:04:45,954
しかし、それはまだ速かったです
線形検索よりも、

176
00:04:45,954 --> 00:04:47,870
ここで我々が​​開始
この本の始まり、

177
00:04:47,870 --> 00:04:51,210
左から右に、我々は我々の方法を移動し、
最終的にはマイク・スミスを探しています。

178
00:04:51,210 --> 00:04:53,540
だから、もし電話帳
多分千ページを持っていました、

179
00:04:53,540 --> 00:04:56,300
多分それはかかったでしょう
私たちの10かそこらのページの涙。

180
00:04:56,300 --> 00:04:59,380
>> しかし、あなたが活用している可能性があり
仮定に触れました

181
00:04:59,380 --> 00:05:03,602
すべてのことの間に、それは言うことです
事前に電話帳が何でしたの？

182
00:05:03,602 --> 00:05:04,310
聴衆：ソートさ。

183
00:05:04,310 --> 00:05:05,000
DAVID J.マラン：それはソートされています。

184
00:05:05,000 --> 00:05:05,160
右？

185
00:05:05,160 --> 00:05:07,909
それはとても、アルファベット順に並べ替えています
これらの名前と番号のすべてのこと

186
00:05:07,909 --> 00:05:11,230
にAのから順にソートされ
Zの、アルファベット順の間です。

187
00:05:11,230 --> 00:05:13,100
しかし、今日、私たちは今尋ねます
質問、よく、

188
00:05:13,100 --> 00:05:16,170
どのようにベライゾンまたは電話でした
同社は、その状態にそれを得ますか？

189
00:05:16,170 --> 00:05:19,560
>> それは一つのことだから活用します
その仮定、したがって、

190
00:05:19,560 --> 00:05:22,570
の問題を解決します
より効率的なアルゴリズム。

191
00:05:22,570 --> 00:05:24,900
しかし、我々は決して本当に
週ゼロに尋ねた、よく、

192
00:05:24,900 --> 00:05:27,790
値段はどれほどでした
ベライゾンまたは他の誰か

193
00:05:27,790 --> 00:05:29,620
ソートされた順序でその電話帳を取得するには？

194
00:05:29,620 --> 00:05:29,780
>> 右？

195
00:05:29,780 --> 00:05:31,529
それは問題ではない場合
マイク・スミスを検索

196
00:05:31,529 --> 00:05:35,190
それはあなたがかかる場合、超高速です
最初にページをソートする年。

197
00:05:35,190 --> 00:05:35,690
右？

198
00:05:35,690 --> 00:05:38,620
あなたにもちょ​​うどふるいにかけるかもしれません
ランダム化された電話帳を経て、

199
00:05:38,620 --> 00:05:40,690
それがスーパーになるだろう場合
それをソートするには高価。

200
00:05:40,690 --> 00:05:42,350
だから我々は、他のボランティアを持つことができます。

201
00:05:42,350 --> 00:05:46,350
のが取るでここに見てみましょう
どのように我々はどのようにup--に来ますmight--

202
00:05:46,350 --> 00:05:48,100
我々はこれらのソートについては行くかもしれません。

203
00:05:48,100 --> 00:05:51,990
>> そしてジョーダンが実際に可能性がある場合
ステージ上で、ここで私たちを参加。

204
00:05:51,990 --> 00:05:55,100
ちょっとアップさあ。

205
00:05:55,100 --> 00:05:56,359
あなたの名前は何ですか？

206
00:05:56,359 --> 00:05:57,150
キャロライン：キャロライン。

207
00:05:57,150 --> 00:05:58,691
DAVID J.マラン：キャロラインは、アップに来ます。

208
00:05:58,691 --> 00:06:02,070
そして、あなたが参加することがあります
ここで私とヨルダンこともできます。

209
00:06:02,070 --> 00:06:03,800
キャロラインは、ありがとうございました。

210
00:06:03,800 --> 00:06:04,300
大丈夫。

211
00:06:04,300 --> 00:06:08,330
だから、我々はここに持っているもの
キャロラインは26青冊です

212
00:06:08,330 --> 00:06:10,747
FASは、管理するために使用します
特定の期末試験。

213
00:06:10,747 --> 00:06:13,330
これらは、見つけるのは難しいなっています
私たちは事前に何をやりましたか

214
00:06:13,330 --> 00:06:15,800
私たちが誰かの名前を入れているということです
これらの各々の前面に、

215
00:06:15,800 --> 00:06:18,133
しかし、我々は、単純な、それを守ってきました
その後、完全な名前を出します。

216
00:06:18,133 --> 00:06:22,720
だから我々は名前で人を置きます
L、D、J、B、すべての方法のAからZ、

217
00:06:22,720 --> 00:06:24,090
しかし、彼らはランダムな順序にしています。

218
00:06:24,090 --> 00:06:26,890
そして、あなたは、あなたの話をするかどう
あなたのような問題を通じ方法

219
00:06:26,890 --> 00:06:31,620
それは、あなたが先に行くことができないと
Zに、私たちのためにこれらを並べ替えます

220
00:06:31,620 --> 00:06:34,070
>> 聴衆：[OK]を、ので、Lは真ん中、等です。

221
00:06:34,070 --> 00:06:35,050
Cが始まっています。

222
00:06:35,050 --> 00:06:42,410
B. L. Bの前にJ、Q。

223
00:06:42,410 --> 00:06:45,140
>> DAVID J.マラン：それを保持
1秒間考えました。

224
00:06:45,140 --> 00:06:48,910
そうでなければ、これは唯一であるため
私は、あなたに面白い、とジョーダン。

225
00:06:48,910 --> 00:06:49,724
そうしよう。

226
00:06:49,724 --> 00:06:50,640
聴衆：[聞こえません]。

227
00:06:50,640 --> 00:06:57,299
R.

228
00:06:57,299 --> 00:06:58,090
DAVID J.マラン：OK。

229
00:06:58,090 --> 00:06:59,310
あなたはなにをしているのですか？

230
00:06:59,310 --> 00:07:01,730
>> キャロライン：MはOの後に来ます

231
00:07:01,730 --> 00:07:02,564
>> DAVID J.マラン：OK。

232
00:07:02,564 --> 00:07:03,064
>> CAROLINE：O.

233
00:07:03,064 --> 00:07:04,120
DAVID J.マラン：O、グッド。

234
00:07:04,120 --> 00:07:04,970
>> CAROLINE：E.

235
00:07:04,970 --> 00:07:06,730
>> DAVID J.マラン：E、F。うん。

236
00:07:06,730 --> 00:07:07,620
>> キャロライン：T、U、V。

237
00:07:07,620 --> 00:07:10,689
>> DAVID J.マラン：それはそうV、T、U、V。
あなたが続けるmaking--ているように見えます。

238
00:07:10,689 --> 00:07:12,730
あなたが作っているように見えます
こちらに大きな山、

239
00:07:12,730 --> 00:07:13,910
そしてあそこに大きな山のようなもの。

240
00:07:13,910 --> 00:07:16,230
だから、アルファベットの前半、
アルファベットの後半。

241
00:07:16,230 --> 00:07:16,460
OK。

242
00:07:16,460 --> 00:07:16,960
良い。

243
00:07:16,960 --> 00:07:19,680
種類の二つに問題を分割します。

244
00:07:19,680 --> 00:07:21,771
M、N、X。うん。

245
00:07:21,771 --> 00:07:22,270
CAROLINE：K.

246
00:07:22,270 --> 00:07:22,980
DAVID J.マラン：OK。

247
00:07:22,980 --> 00:07:25,070
K.は、だから、種類の選択しています
それら次々、

248
00:07:25,070 --> 00:07:27,620
左または右のいずれかにそれを入れて、
またはZは、床の上に起こっています。

249
00:07:27,620 --> 00:07:28,012
OK。

250
00:07:28,012 --> 00:07:29,190
>> キャロライン：Z​​は、床の上に起こっています。

251
00:07:29,190 --> 00:07:29,360
>> DAVID J.マラン：OK。

252
00:07:29,360 --> 00:07:30,920
Yは、床の上に起こっています。

253
00:07:30,920 --> 00:07:31,735
今、私たちはXを置くことができます

254
00:07:31,735 --> 00:07:32,409
>> CAROLINE：G.

255
00:07:32,409 --> 00:07:33,700
DAVID J.マラン：Gさんは左に行きます。

256
00:07:33,700 --> 00:07:36,017
Sは右起こっています。

257
00:07:36,017 --> 00:07:37,642
すべての権利、Aは左のすべての方法を行っています。

258
00:07:37,642 --> 00:07:38,790
>> CAROLINE：A、B、C、D.

259
00:07:38,790 --> 00:07:39,873
>> DAVID J.マラン：今、良いです。

260
00:07:39,873 --> 00:07:43,260
我々が持っている、Bは、CのWのは、そこに行きます。

261
00:07:43,260 --> 00:07:45,566
すべての権利、T.

262
00:07:45,566 --> 00:07:46,611
>> キャロライン：H、I、J。

263
00:07:46,611 --> 00:07:47,860
DAVID J.マラン：H、I、Jグッド。

264
00:07:47,860 --> 00:07:49,160
CAROLINE：センターでは、私はgonna--よ

265
00:07:49,160 --> 00:07:50,000
DAVID J.マラン：OK。

266
00:07:50,000 --> 00:07:52,375
だから今、私たちは、種類になるだろう
これらの様々な山をマージします。

267
00:07:52,375 --> 00:08:00,730
そこで、Cを介して、私はDを参照し、
E、およびF、およびG、およびH、およびIニース。

268
00:08:00,730 --> 00:08:05,540
J、Kそして、この山があります
逆さまに、それは大丈夫です。

269
00:08:05,540 --> 00:08:06,040
確かに。

270
00:08:06,040 --> 00:08:07,240
我々はいくつかのコーナーをカットすることができます。

271
00:08:07,240 --> 00:08:07,950
OK。

272
00:08:07,950 --> 00:08:10,530
そして、我々は、W、X、Y、Zを必要とします

273
00:08:10,530 --> 00:08:11,250
>> キャロライン：うん。

274
00:08:11,250 --> 00:08:11,880
>> DAVID J.マラン：優秀。

275
00:08:11,880 --> 00:08:14,122
だからビッグにありがとう
これらをソートするためキャロライン。

276
00:08:14,122 --> 00:08:15,030
>> [応援]

277
00:08:15,030 --> 00:08:17,287
>> ありがとう。

278
00:08:17,287 --> 00:08:18,120
どうもありがとうございました。

279
00:08:18,120 --> 00:08:22,910
だから今のは一瞬考えてみましょう
どのキャロラインはそれをやって行きました、

280
00:08:22,910 --> 00:08:26,040
そしてまさに我々
どのように我々to--ことができました

281
00:08:26,040 --> 00:08:28,409
それを解決することができました
我々だけだった問題

282
00:08:28,409 --> 00:08:29,950
ランダム入力の全体の束を与えられました。

283
00:08:29,950 --> 00:08:31,610
>> まあ、それはそこにのように見えます
そこにシステムのビットでしたか？

284
00:08:31,610 --> 00:08:32,110
右。

285
00:08:32,110 --> 00:08:34,495
だから、以前の文字は、
アルファベットで、彼女

286
00:08:34,495 --> 00:08:37,120
左に置く、とされました
アルファベットの後の文字、

287
00:08:37,120 --> 00:08:38,270
彼女は右に入れていました。

288
00:08:38,270 --> 00:08:40,500
そして、すぐに彼女が見られるように
いくつかの近位文字、もの

289
00:08:40,500 --> 00:08:43,124
それは右隣同士に行きます、
彼女は順番にそれらを置きます。

290
00:08:43,124 --> 00:08:46,750
そして、私たちは種類のこれらの小さなを持っていました
発生したソートされた入力の山。

291
00:08:46,750 --> 00:08:50,540
>> そして、その結果は非常にどのようなものか
私たちのほとんどの人間は行うだろう。

292
00:08:50,540 --> 00:08:53,530
我々は一種のそれを取捨選択だろう、
私たちは種類のメカニズムを持っていると思います。

293
00:08:53,530 --> 00:08:56,930
しかし、それは書くことが難しいかもしれません
それダウン式自体インチ

294
00:08:56,930 --> 00:08:59,010
それはもう少し有機よりも感じました。

295
00:08:59,010 --> 00:09:02,560
だから我々は今、バインドできるかどうかを見てみましょう
少ない入力を持つ問題。

296
00:09:02,560 --> 00:09:05,170
>> 代わりに26の、してみましょう
はるかに少ない何かを

297
00:09:05,170 --> 00:09:09,890
直後の、7、と言うと
これらのドアは、いわば。

298
00:09:09,890 --> 00:09:11,300
わずか7の数字はありますか？

299
00:09:11,300 --> 00:09:15,240
そして今の目標であれば
手の値を見つけることであり、

300
00:09:15,240 --> 00:09:17,850
それでは、どのように効率的に見てみましょう
我々はこれをやって行くことができます。

301
00:09:17,850 --> 00:09:22,460
そして、私たちが今できることなら見てみましょう
いくつかの数値を適用するために開始し、

302
00:09:22,460 --> 00:09:26,310
記述すると、またはいくつかの式
当社の電話帳の効率

303
00:09:26,310 --> 00:09:31,060
アルゴリズム、私たちの試験の本アルゴリズム、および
より一般的には、情報を見つけます。

304
00:09:31,060 --> 00:09:34,770
>> このためだから、私は先に行かせて、
こちらにタッチスクリーン上に、

305
00:09:34,770 --> 00:09:41,100
持っているWebブラウザを設置
正確にこれらの7つのドア。

306
00:09:41,100 --> 00:09:46,670
そして、我々は他のものを得ることができれば
こっちに来てボランティア、

307
00:09:46,670 --> 00:09:48,480
私はここの上にこれらの同じドアを入れています。

308
00:09:48,480 --> 00:09:49,170
クイックボランティア。

309
00:09:49,170 --> 00:09:51,130
>> この選ぶ - デモが起こっています
今より速く、より迅速に。

310
00:09:51,130 --> 00:09:51,600
ダウンさあ。

311
00:09:51,600 --> 00:09:52,308
あなたの名前は何ですか？

312
00:09:52,308 --> 00:09:53,040
TREVOR：トレバー。

313
00:09:53,040 --> 00:09:53,998
>> DAVID J.マラン：トレバー？

314
00:09:53,998 --> 00:09:55,770
すべての権利、トレバーは、ダウンに来ます。

315
00:09:55,770 --> 00:09:59,212
だから、トレバーはこちらを志願しました
同様の問題が、だいずれかを実行します。

316
00:09:59,212 --> 00:10:02,170
範囲が狭く、それが起こっています
私たちは今、形式化しようとすることを可能にします

317
00:10:02,170 --> 00:10:03,970
これらの数字をソートするためのプロセス。

318
00:10:03,970 --> 00:10:05,500
>> だからトレバーは、はじめまして。

319
00:10:05,500 --> 00:10:08,720
だからここにとても配列であり、
、7ドアのリストを話します。

320
00:10:08,720 --> 00:10:10,327
前方に移動し、私たちに数50を見つけます。

321
00:10:10,327 --> 00:10:12,410
そして事実の後、
あなたはそれを見つけた方法を教えて。

322
00:10:12,410 --> 00:10:19,124

323
00:10:19,124 --> 00:10:20,040
すべての権利をbe--する必要があります。

324
00:10:20,040 --> 00:10:21,945
うん、これはここでは1ですか？

325
00:10:21,945 --> 00:10:24,680
おっと。

326
00:10:24,680 --> 00:10:25,560
OK。

327
00:10:25,560 --> 00:10:26,680
あなたはそのいずれかをクリックしました。

328
00:10:26,680 --> 00:10:28,690
良い。

329
00:10:28,690 --> 00:10:29,780
>> そして、良いです。

330
00:10:29,780 --> 00:10:30,970
今、あなたはそのいずれかをクリックしました。

331
00:10:30,970 --> 00:10:34,060
そして、私はあなたにマイクを与えてみましょう、
あなただけの瞬間にそれを持っているようにします。

332
00:10:34,060 --> 00:10:37,000
前方に移動し、クリックして
あなたは予定隣。

333
00:10:37,000 --> 00:10:39,812
いいね。

334
00:10:39,812 --> 00:10:41,020
TREVOR：私はドアをunclickすることはできますか？

335
00:10:41,020 --> 00:10:42,620
DAVID J.マラン：いいえ、あなたがunclickすることはできません。

336
00:10:42,620 --> 00:10:43,119
TREVOR：[OK]をクリックします。

337
00:10:43,119 --> 00:10:43,974
これです。

338
00:10:43,974 --> 00:10:45,640
DAVID J.マラン：どこに行きたいですか？

339
00:10:45,640 --> 00:10:46,410
どれ？

340
00:10:46,410 --> 00:10:47,230
>> TREVOR：その1。

341
00:10:47,230 --> 00:10:48,042
>> DAVID J.マラン：いいえ

342
00:10:48,042 --> 00:10:48,450
>> TREVOR：[OK]をクリックします。

343
00:10:48,450 --> 00:10:48,735
これです。

344
00:10:48,735 --> 00:10:49,020
>> DAVID J.マラン：はい。

345
00:10:49,020 --> 00:10:49,700
それは良かったです。

346
00:10:49,700 --> 00:10:50,380
大丈夫。

347
00:10:50,380 --> 00:10:53,900
だからあなたのアルゴリズムは何だったのか
これを行うための手順、トレバー？

348
00:10:53,900 --> 00:10:56,149
>> TREVOR：私はちょうど通過しました
ドア私は50を見つけるまで。

349
00:10:56,149 --> 00:10:56,940
DAVID J.マラン：OK。

350
00:10:56,940 --> 00:10:58,150
優れたアルゴリズム。

351
00:10:58,150 --> 00:10:59,540
だから、大丈夫です。

352
00:10:59,540 --> 00:11:03,120
実際に、私は明らかにしたらどうだから
これらの二つの他のドアの後ろに、どのような

353
00:11:03,120 --> 00:11:06,954
我々は、ということですここで見つけることができます
我々はランダムな入力を持っています。

354
00:11:06,954 --> 00:11:08,870
だから、実際の通りでした
あなたが得ることができるように良いです。

355
00:11:08,870 --> 00:11:12,509
そして、実際には、あなたがより良くなりました
徹底的に配列全体を検索します、

356
00:11:12,509 --> 00:11:15,300
それは実際にあったであろうので、
不運あなたは数を打つていた場合

357
00:11:15,300 --> 00:11:16,604
非常に最後のドアで50。

358
00:11:16,604 --> 00:11:18,520
しかしその代わりに、私たちの場合
あなたの仮定を与えました。

359
00:11:18,520 --> 00:11:20,630
私は一種のすべての仮定します
周りのこれらのドア、

360
00:11:20,630 --> 00:11:23,500
あなたが持っているように、
数字は、この時間をソートし、

361
00:11:23,500 --> 00:11:29,730
今回はそれが実際です
different--この時、

362
00:11:29,730 --> 00:11:32,640
それは実際にあなたのために並べ替えられています。

363
00:11:32,640 --> 00:11:35,380
そして今、手元にゴール
数50を打つことです。

364
00:11:35,380 --> 00:11:36,090
>> TREVOR：[OK]をクリックします。

365
00:11:36,090 --> 00:11:37,670
>> DAVID J.マラン：何が
あなたのアルゴリズムでは、になるだろうか？

366
00:11:37,670 --> 00:11:39,628
>> TREVOR：まあ、それはだ場合
ソート、それはどちらかだ行きます

367
00:11:39,628 --> 00:11:42,710
最大の場合は最大にbe--します、
降順、それは最初のものになるだろう、

368
00:11:42,710 --> 00:11:44,751
またはそれは反対だ場合、
それは最後の1になります。

369
00:11:44,751 --> 00:11:48,897
だから、僕はこのドアをタップし、よ
その後、ちょうど最後のドアをタップします。

370
00:11:48,897 --> 00:11:49,980
DAVID J.マラン：優秀。

371
00:11:49,980 --> 00:11:50,270
大丈夫。

372
00:11:50,270 --> 00:11:51,150
だから我々は数50を発見しました。

373
00:11:51,150 --> 00:11:52,970
だから、すぐにあなたが知っていたとして、
彼らは、私たちを選別し、

374
00:11:52,970 --> 00:11:55,040
この仮定を活用することができました。

375
00:11:55,040 --> 00:11:57,040
そこで、彼らは次のようにあまりにも多くのです
電話帳の例。

376
00:11:57,040 --> 00:11:59,540
すぐに持っているように、偶数と
このような小さな問題、

377
00:11:59,540 --> 00:12:02,380
あなたの入力は事前にソートされ、我々はできます
実際に間違いなく値を見つけます

378
00:12:02,380 --> 00:12:03,130
より効率的に。

379
00:12:03,130 --> 00:12:05,800
>> それがあった場合私はあなたを教えてくれませんでした
ビッグに小さなソート、または小規模から大規模、

380
00:12:05,800 --> 00:12:08,080
そしてそれは非常に合理的でした
一端または他に開始します

381
00:12:08,080 --> 00:12:09,750
実際にその目標値を検索します。

382
00:12:09,750 --> 00:12:11,400
だからだけでなくトレバーに感謝。

383
00:12:11,400 --> 00:12:13,260
そして、私はうまく行っpropose--ます。

384
00:12:13,260 --> 00:12:16,960
私たちは、その実際には、ほとんどのクリップを持っています
CS50で私たちのお気に入りの瞬間の中で、

385
00:12:16,960 --> 00:12:19,700
これにより、時々これらのデモ
かなり計画に従って行っていません。

386
00:12:19,700 --> 00:12:22,050
そして実際、今、私
誤ったインターフェイスをプルアップ

387
00:12:22,050 --> 00:12:23,508
タッチスクリーンを使用すると。

388
00:12:23,508 --> 00:12:24,660
だから、私のせいではありました。

389
00:12:24,660 --> 00:12:26,600
>> だから、これはためになります
来年のクリップと

390
00:12:26,600 --> 00:12:28,570
私は自分の画面上でクリックした理由。

391
00:12:28,570 --> 00:12:31,390
しかし、ここでは簡単に見てみましょう
昨年何が起こったかで

392
00:12:31,390 --> 00:12:34,770
ずっと、思いついたジェイと
ここでトレバーのように、志願し、

393
00:12:34,770 --> 00:12:39,380
この短いクリップでは、あなたが表示されます
この同じデモは全くしませんでしたか

394
00:12:39,380 --> 00:12:41,074
同じ教訓を明らかにしました。

395
00:12:41,074 --> 00:12:41,740
[ビデオ再生]

396
00:12:41,740 --> 00:12:45,360
私は、あなたが今何をしたい-allです
私のために、そして私たちのために見つけるために、

397
00:12:45,360 --> 00:12:51,674
本当に、数50
一歩ずつ。

398
00:12:51,674 --> 00:12:52,450
>> -The数50？

399
00:12:52,450 --> 00:12:53,190
>> -The数50。

400
00:12:53,190 --> 00:12:55,356
そして、あなたは何を明らかにすることができます
これらのドアのそれぞれの背後にあります

401
00:12:55,356 --> 00:12:58,540
単に指で触れることもできます。

402
00:12:58,540 --> 00:13:00,910
畜生。

403
00:13:00,910 --> 00:13:02,870
>> [笑い]

404
00:13:02,870 --> 00:13:03,806
>> [END再生]

405
00:13:03,806 --> 00:13:05,430
DAVID J.マラン：だから非常にうまくいきました。

406
00:13:05,430 --> 00:13:06,796
それらはソートされていないドアでした。

407
00:13:06,796 --> 00:13:08,670
そしてジェイ、もちろん、
あまりにも速く、すべてを発見しました。

408
00:13:08,670 --> 00:13:12,910
トレバーは、はるかに良い仕事をしました
教えやすい瞬間の観点から、

409
00:13:12,910 --> 00:13:15,850
そうでは今年、話すこと
それを見つけるために長いを取ります。

410
00:13:15,850 --> 00:13:17,950
もちろん、我々は与えました
ジェイ二度目のチャンス、

411
00:13:17,950 --> 00:13:20,320
それによって我々は、ドアをソート
私たちはトレバーのためにやったように、

412
00:13:20,320 --> 00:13:22,300
そして、トレバーは、スーパーだけでなく、この時間をしました。

413
00:13:22,300 --> 00:13:26,124
しかし、ジェイは半分にすぐにそれをやりました。

414
00:13:26,124 --> 00:13:26,790
[ビデオ再生]

415
00:13:26,790 --> 00:13:29,650
-The目標は今もあります
私たちに数50を見つけ、

416
00:13:29,650 --> 00:13:33,030
しかし、アルゴリズムそれを行うと、
あなたはそれについてつもり方法を教えて。

417
00:13:33,030 --> 00:13:33,660
>> -OK。

418
00:13:33,660 --> 00:13:35,604
>> あなたがそれを見つけた場合 - そして、あなたは映画を保ちます。

419
00:13:35,604 --> 00:13:37,228
あなたはそれが見つからない場合、あなたはそれを返します。

420
00:13:37,228 --> 00:13:38,044
>> -Man。

421
00:13:38,044 --> 00:13:38,860
>> -oh！

422
00:13:38,860 --> 00:13:40,800
>>  -  [聞こえない] [OK]をクリックします。

423
00:13:40,800 --> 00:13:46,236
だから私は端をチェックするつもりです
ああthere's--かどうかを判断する最初の。

424
00:13:46,236 --> 00:13:48,646
>> [拍手]

425
00:13:48,646 --> 00:13:53,948

426
00:13:53,948 --> 00:13:55,729
>> [END再生]

427
00:13:55,729 --> 00:13:56,520
DAVID J.マラン：OK。

428
00:13:56,520 --> 00:13:59,760
だから、明らかにドアをソート
効率化につながります。

429
00:13:59,760 --> 00:14:01,680
だから、二倍の速さ
私が何を意味するのかです。

430
00:14:01,680 --> 00:14:03,270
そしてそうジェイは幸運両方の時間を得ました。

431
00:14:03,270 --> 00:14:06,685
そして彼はまた、最後に幸運
今年、私はいくつかのBlu-rayディスクを注文

432
00:14:06,685 --> 00:14:07,560
実際に出て得ました。

433
00:14:07,560 --> 00:14:09,768
私は、今年ごめんなさい
同じ、トレバーを持っていませんでした。

434
00:14:09,768 --> 00:14:11,540
しかし、より好ましくは数年前でした。

435
00:14:11,540 --> 00:14:14,820
そして、あなたのいくつかはこのことを知っているかもしれません
彼はCS50にいた仲間、ショーン、

436
00:14:14,820 --> 00:14:17,780
正確に挑戦されました
同じ問題、SDではあるが、

437
00:14:17,780 --> 00:14:19,360
あなたはすぐに戻って一日で、表示されます。

438
00:14:19,360 --> 00:14:22,622
そして、あなたがただけではないことがわかります
彼は、ジェイより少し時間がかかります

439
00:14:22,622 --> 00:14:25,580
トレバーよりも少し長く、それがありました
実際にこの素晴らしい機会

440
00:14:25,580 --> 00:14:29,820
のほぼ全員を係合します
群衆ラ価格は奨励、右であります

441
00:14:29,820 --> 00:14:31,889
彼は、私たちが求めていた番号を検索します。

442
00:14:31,889 --> 00:14:32,930
のをしてみましょう。簡単に見てみ。

443
00:14:32,930 --> 00:14:33,320
>> [ビデオ再生]

444
00:14:33,320 --> 00:14:33,820
>> -OK。

445
00:14:33,820 --> 00:14:36,680
だからここにあなたの仕事、
ショーンは、以下の通りです。

446
00:14:36,680 --> 00:14:40,860
私はこれらの背後に隠されています
ドア数7。

447
00:14:40,860 --> 00:14:45,120
しかし、これらのドアの一部に隠れて
同様に他の負の数値です。

448
00:14:45,120 --> 00:14:47,500
そして、あなたの目標は、考えることです
この数値の一番上の行の

449
00:14:47,500 --> 00:14:50,390
ちょうど配列、または同じように
紙の作品の順序

450
00:14:50,390 --> 00:14:51,510
その背後にある番号を持ちます。

451
00:14:51,510 --> 00:14:55,540
そして、あなたの目標は、上部のみを使用して、あります
配列ここで、私は数7を見つけます。

452
00:14:55,540 --> 00:14:58,570
そして、私たちはその後、批評しようとしています
どのようにあなたがそれをやって行きます。

453
00:14:58,570 --> 00:14:59,070
-大丈夫。

454
00:14:59,070 --> 00:15:00,850
、私たちの数7をください-find。

455
00:15:00,850 --> 00:15:10,500

456
00:15:10,500 --> 00:15:11,000
いいえ。

457
00:15:11,000 --> 00:15:15,050

458
00:15:15,050 --> 00:15:18,550
五、19、13。

459
00:15:18,550 --> 00:15:22,240

460
00:15:22,240 --> 00:15:24,770
>> [笑い]

461
00:15:24,770 --> 00:15:25,910
>> これはトリックの質問ではありません。

462
00:15:25,910 --> 00:15:29,410

463
00:15:29,410 --> 00:15:29,910
1。

464
00:15:29,910 --> 00:15:33,218

465
00:15:33,218 --> 00:15:34,695
>> [笑い]

466
00:15:34,695 --> 00:15:37,861
この時点で、あなたのスコアが非常にではありません
良いので、あなたにも続ける可能性があります。

467
00:15:37,861 --> 00:15:40,610

468
00:15:40,610 --> 00:15:41,110
3。

469
00:15:41,110 --> 00:15:43,890

470
00:15:43,890 --> 00:15:45,378
>> [笑い]

471
00:15:45,378 --> 00:15:46,370

472
00:15:46,370 --> 00:15:47,774
>> 移動します。

473
00:15:47,774 --> 00:15:50,690
率直に言って、私は助けることが疑問に思うことができません
何をしてもso--、考えています

474
00:15:50,690 --> 00:15:51,959
>> [笑い]

475
00:15:51,959 --> 00:15:53,229

476
00:15:53,229 --> 00:15:55,020
唯一の一番上の行なので、
次の3つの左を持っています。

477
00:15:55,020 --> 00:15:56,200
だから、私は7を見つけます。

478
00:15:56,200 --> 00:15:59,700

479
00:15:59,700 --> 00:16:02,167
>> [笑い]

480
00:16:02,167 --> 00:16:14,870

481
00:16:14,870 --> 00:16:15,370
17。

482
00:16:15,370 --> 00:16:25,675

483
00:16:25,675 --> 00:16:26,946
セブン。

484
00:16:26,946 --> 00:16:28,780
>> [拍手]

485
00:16:28,780 --> 00:16:29,426
>> 大丈夫。

486
00:16:29,426 --> 00:16:30,360
>> [END再生]

487
00:16:30,360 --> 00:16:31,840
>> DAVID J.マラン：だから我々は可能性が
一日中、これらを見て。

488
00:16:31,840 --> 00:16:34,090
のそしてもちろん、いくつかの
おそらく今年のデモ

489
00:16:34,090 --> 00:16:36,330
今すぐ次に終わります
今年のビデオなども。

490
00:16:36,330 --> 00:16:39,040
だから今、実際にしてみましょう
アルゴリズムに焦点を合わせます

491
00:16:39,040 --> 00:16:42,140
ここで、我々はできないかどうかを確認
今正式始めます

492
00:16:42,140 --> 00:16:46,650
どのように我々は、我々のデータを得ることについて行くことができます
この状態に、それがソートだと、

493
00:16:46,650 --> 00:16:50,054
最終的に、私たちが実際にすることができますように
より効率的に検索します。

494
00:16:50,054 --> 00:16:52,470
そして、私たちが行っているにもかかわらず、
かなり小さいデータセットを使用します、

495
00:16:52,470 --> 00:16:54,511
8数字の私たちのように
ボード上にここにあります、

496
00:16:54,511 --> 00:16:58,230
最終的にこれらの同じ考えが適用できます
千入力に、百万の入力、

497
00:16:58,230 --> 00:17:02,100
アルゴリズムのため40億の入力、
基本的には同じことを行っています。

498
00:17:02,100 --> 00:17:05,359
>> そして、これは私たちの最後です
ボランティアの機会今日、

499
00:17:05,359 --> 00:17:09,790
しかし、おそらく最も関与する1つ、
これのために私たちは、8人のボランティアが必要

500
00:17:09,790 --> 00:17:12,960
出てくるとを通して私たちを歩きます
すぐにどうなるか仕分けのプロセス

501
00:17:12,960 --> 00:17:15,212
これらの音楽をすることは、ここに立っています。

502
00:17:15,212 --> 00:17:16,170
私はここに戻ってみましょう。

503
00:17:16,170 --> 00:17:19,692
>> だからturquoise--緑の中の1つは、それを何ですか？

504
00:17:19,692 --> 00:17:21,130
あなたがコミットされていますか？

505
00:17:21,130 --> 00:17:21,630
2。

506
00:17:21,630 --> 00:17:23,069
ダウンさあ。

507
00:17:23,069 --> 00:17:23,569
OK。

508
00:17:23,569 --> 00:17:24,420
3。

509
00:17:24,420 --> 00:17:25,400
四。

510
00:17:25,400 --> 00:17:27,247
5、me--がOKしてみましょう。

511
00:17:27,247 --> 00:17:28,830
あなたの友人が指名されています。

512
00:17:28,830 --> 00:17:31,340
6個、7個、8。

513
00:17:31,340 --> 00:17:32,130
アップさあ。

514
00:17:32,130 --> 00:17:32,630
大丈夫。

515
00:17:32,630 --> 00:17:33,190
どうもありがとうございます。

516
00:17:33,190 --> 00:17:33,689
アップさあ。

517
00:17:33,689 --> 00:17:34,790
アップさあ。

518
00:17:34,790 --> 00:17:35,330
>> 大丈夫。

519
00:17:35,330 --> 00:17:38,890
だから我々はhere--、これを持っているもの
より厄介なものの一つです、

520
00:17:38,890 --> 00:17:42,390
これは、あなたのユーモアを必要としますので、
時間のほんの少しのための私。

521
00:17:42,390 --> 00:17:43,442
あなたはナンバーワンでなければなりません。

522
00:17:43,442 --> 00:17:44,150
あなたの名前は何ですか？

523
00:17:44,150 --> 00:17:44,610
>> アナン：アナン。

524
00:17:44,610 --> 00:17:45,526
>> DAVID J.マラン：アナン。

525
00:17:45,526 --> 00:17:46,092
デビッド。

526
00:17:46,092 --> 00:17:46,800
あなたの名前は何ですか？

527
00:17:46,800 --> 00:17:47,140
>> JOSEPH：ジョセフ。

528
00:17:47,140 --> 00:17:49,190
>> DAVID J.マラン：ジョセフ、
あなたは数2​​つです。

529
00:17:49,190 --> 00:17:52,260
>> セレナ：セレナ、数3。

530
00:17:52,260 --> 00:17:53,722
ステファン、4番。

531
00:17:53,722 --> 00:17:54,430
CYNTHIA：シンシア。

532
00:17:54,430 --> 00:17:57,548
DAVID J.マラン：シンシア、数5。

533
00:17:57,548 --> 00:17:58,452
[聞こえません]

534
00:17:58,452 --> 00:17:59,618
DAVID J.マラン：[聞こえません]。

535
00:17:59,618 --> 00:18:00,391
デビッド、6番。

536
00:18:00,391 --> 00:18:00,890
MATT：マット。

537
00:18:00,890 --> 00:18:02,160
DAVID J.マラン：Mattの数7。

538
00:18:02,160 --> 00:18:02,850
そして？

539
00:18:02,850 --> 00:18:03,210
>> ウェイバリー：ウェイバリー。

540
00:18:03,210 --> 00:18:04,470
>> DAVID J.マラン：ウェイバリー、数8。

541
00:18:04,470 --> 00:18:04,970
大丈夫。

542
00:18:04,970 --> 00:18:06,510
場合は、おっとをcould--。

543
00:18:06,510 --> 00:18:08,820
あなたのように、あなたのすべての場合
そこに最初の課題、

544
00:18:08,820 --> 00:18:10,820
8曲のスタンドは、
ここで観客に面しています。

545
00:18:10,820 --> 00:18:14,200
あなたは上の数字を入れることができれば
これらの音楽は、そのような方法で立っています

546
00:18:14,200 --> 00:18:16,560
彼らが並ぶこと
ボード上の同じ番号。

547
00:18:16,560 --> 00:18:19,560
だから、自分がして、そのように見えるように
これらの音楽をあなたの番号を入れて

548
00:18:19,560 --> 00:18:21,960
ここに立っています。

549
00:18:21,960 --> 00:18:25,980
優れたこれまで。

550
00:18:25,980 --> 00:18:26,600
>> 優れています。

551
00:18:26,600 --> 00:18:26,890
OK。

552
00:18:26,890 --> 00:18:29,556
だから今、私たちは、依頼するつもりです
いくつかの異なる方法で質問です。

553
00:18:29,556 --> 00:18:31,610
どのように我々は、ソートについて行くことができます
ここでこれらの人々アップ？

554
00:18:31,610 --> 00:18:34,500
我々はいくつかのアプローチを持っていたので
以前、それによって私たちがしました

555
00:18:34,500 --> 00:18:36,360
二つの異なるバケットを作るようなもの。

556
00:18:36,360 --> 00:18:38,842
そして、我々は一般的でした
物事を一緒に縫い合わせ。

557
00:18:38,842 --> 00:18:41,050
すぐに我々は2つ​​の数値を見たように
それは、一緒に属し

558
00:18:41,050 --> 00:18:41,975
私たちは一緒にそれらを置きます。

559
00:18:41,975 --> 00:18:43,350
一緒に属する2つの文字。

560
00:18:43,350 --> 00:18:45,058
>> しかし、どうかを見てみましょう
これを形式化することはできません、

561
00:18:45,058 --> 00:18:48,044
我々は最終的に持っているように、
必要になりますいくつかの擬似コード、

562
00:18:48,044 --> 00:18:49,710
これであなたは、これらの問題を解決することができます。

563
00:18:49,710 --> 00:18:51,870
だから今、私は探しています
ここではこれらの数値で。

564
00:18:51,870 --> 00:18:55,030
そして、私はミスの全体の束を参照してください。

565
00:18:55,030 --> 00:18:57,750
最終的に、私は上の1つが欲しいです
左右に8。

566
00:18:57,750 --> 00:19:00,650
>> そして、私は見ています
これらの2つ、4つおよび2。

567
00:19:00,650 --> 00:19:02,930
そして、問題は明らかに、何ですか？

568
00:19:02,930 --> 00:19:04,261
うん。

569
00:19:04,261 --> 00:19:04,760
Soが

570
00:19:04,760 --> 00:19:07,160
二つは明らかに前に来ます
4、あなたは何を知っていますか？

571
00:19:07,160 --> 00:19:10,210
私が最初に貪欲なアプローチを見てみましょう、
あなたがする場合は、問題のような多くの

572
00:19:10,210 --> 00:19:13,790
あなたからリコール場合選ぶ - 設定
問題セットの一つのスタンダード版、

573
00:19:13,790 --> 00:19:16,820
ここで、私はローカルで問題を解決
それは私の目の前にここです

574
00:19:16,820 --> 00:19:17,690
それは私をリードし、どこを参照してください。

575
00:19:17,690 --> 00:19:17,870
>> OK。

576
00:19:17,870 --> 00:19:20,161
だから、2および4、私は手放します
先とちょうど2つのあなたを交換します。

577
00:19:20,161 --> 00:19:22,400
あなたは物理的に移動することができた場合
自分と自分の論文、

578
00:19:22,400 --> 00:19:25,040
私が得ているように見えます
より良い状態にあるリスト。

579
00:19:25,040 --> 00:19:26,330
>> 今、彼らは良いしています。

580
00:19:26,330 --> 00:19:28,480
私は、上に移動するつもりです
4と6は、よさそうです。

581
00:19:28,480 --> 00:19:29,110
問題ありません。

582
00:19:29,110 --> 00:19:30,440
シックス、8、[OK]をクリックします。

583
00:19:30,440 --> 00:19:31,860
八一、別の問題。

584
00:19:31,860 --> 00:19:34,750
8と約1本当だ何から？

585
00:19:34,750 --> 00:19:36,990
一つは、8つの前に来ます
そのため、私たちは何をすべきでしょうか？

586
00:19:36,990 --> 00:19:38,090
のは、これらの2つを交換してみましょう。

587
00:19:38,090 --> 00:19:39,316
Oneと8。

588
00:19:39,316 --> 00:19:40,690
そして今、私は続けるつもりです。

589
00:19:40,690 --> 00:19:42,030
私は先に探し続けるつもりです。

590
00:19:42,030 --> 00:19:42,840
そしてのは、何が起こるか見てみましょう。

591
00:19:42,840 --> 00:19:44,680
八三、の
もちろん、アウトオブオーダー。

592
00:19:44,680 --> 00:19:45,815
スワップをしてみましょう。

593
00:19:45,815 --> 00:19:46,940
もちろん八七、。

594
00:19:46,940 --> 00:19:47,481
アウトオブオーダー。

595
00:19:47,481 --> 00:19:48,280
スワップをしてみましょう。

596
00:19:48,280 --> 00:19:49,940
八五、もちろん、交換しよう。

597
00:19:49,940 --> 00:19:50,560
大丈夫。

598
00:19:50,560 --> 00:19:51,880
リストがソートされます。

599
00:19:51,880 --> 00:19:53,060
はい？

600
00:19:53,060 --> 00:19:54,280
>> [OK]を、明らかではありません。

601
00:19:54,280 --> 00:19:55,860
しかし、それは右、少し良いですか？

602
00:19:55,860 --> 00:19:57,270
通知は何が起こったかあるので。

603
00:19:57,270 --> 00:20:01,749
私たちは、小さいのスワップを行ったびに
番号は、種類のその方法を浸透さ、

604
00:20:01,749 --> 00:20:03,790
そして、大きな数
このように浸透させ、または私達はよ

605
00:20:03,790 --> 00:20:06,880
にバブリング言っ開始
左または右にバブリング。

606
00:20:06,880 --> 00:20:10,080
>> 今、それがあるため、十分ではありません
せいぜい数のかもしれません

607
00:20:10,080 --> 00:20:11,990
一つの場所を移動しました
前方、または最悪の場合、

608
00:20:11,990 --> 00:20:13,880
数が場合があります
さらに、1つの場所を移動しました。

609
00:20:13,880 --> 00:20:16,369
だから、何を、この種の知っています
これまでのところ、かなりうまくいきました。

610
00:20:16,369 --> 00:20:17,410
私はもう一度それを試してみましょう。

611
00:20:17,410 --> 00:20:18,880
2と4、彼らはOKです。

612
00:20:18,880 --> 00:20:20,180
四六、彼らはOKです。

613
00:20:20,180 --> 00:20:21,790
六一、アウトオブオーダー。

614
00:20:21,790 --> 00:20:23,007
それでは、次の2つを交換しましょう​​。

615
00:20:23,007 --> 00:20:25,840
そして今、問題のに気付きます
再び少し良くなり始め。

616
00:20:25,840 --> 00:20:27,006
六三、アウトオブオーダー。

617
00:20:27,006 --> 00:20:28,100
2つのあなたを交換しましょう​​。

618
00:20:28,100 --> 00:20:29,730
六七、あなたは良いしています。

619
00:20:29,730 --> 00:20:32,230
もちろん、注文のうち七五、。

620
00:20:32,230 --> 00:20:33,920
七、8、ためです。

621
00:20:33,920 --> 00:20:36,470
そして今、私がする必要があるかもしれません
もっとこの数回行います。

622
00:20:36,470 --> 00:20:39,830
そして、実際には、自分のためだと思います
おそらく何回最大限に

623
00:20:39,830 --> 00:20:41,330
私は前後に歩かなければならないのでしょうか？

624
00:20:41,330 --> 00:20:42,390
>> 我々は戻ってそれに来ます。

625
00:20:42,390 --> 00:20:43,700
だから、2と4はまだOKです。

626
00:20:43,700 --> 00:20:44,940
四一、いや。

627
00:20:44,940 --> 00:20:45,747
それでは、スワップをしましょう​​。

628
00:20:45,747 --> 00:20:47,830
そして再び、視覚的に気付きます
1は、泡立ちの一種であります

629
00:20:47,830 --> 00:20:49,163
それがあるべき左へ。

630
00:20:49,163 --> 00:20:50,010
四三スワップ。

631
00:20:50,010 --> 00:20:51,330
四六。

632
00:20:51,330 --> 00:20:53,100
六五スワップ。

633
00:20:53,100 --> 00:20:53,959
六七。

634
00:20:53,959 --> 00:20:55,000
セブンと8が良いです。

635
00:20:55,000 --> 00:20:55,500
>> 良い。

636
00:20:55,500 --> 00:20:58,460
私たちも良くなっています。

637
00:20:58,460 --> 00:20:59,130
それでは見てみましょう。

638
00:20:59,130 --> 00:21:00,940
今、私たちは2と1を持っています。

639
00:21:00,940 --> 00:21:02,520
もちろん、交換します。

640
00:21:02,520 --> 00:21:07,520
二三、3と4、4、および
5、6と7、7、8。

641
00:21:07,520 --> 00:21:08,020
良い。

642
00:21:08,020 --> 00:21:08,730
そして、あなたは何を知っていますか？

643
00:21:08,730 --> 00:21:11,190
私はそこに1変更を行ったため、
私は1健全性チェックを行うことができます。

644
00:21:11,190 --> 00:21:13,023
私はすべての道を行こう
バック先頭に。

645
00:21:13,023 --> 00:21:13,680
OK。

646
00:21:13,680 --> 00:21:14,750
一つは、うんtwo--、参照してください？

647
00:21:14,750 --> 00:21:15,870
何かが間違っていました。

648
00:21:15,870 --> 00:21:18,420
三つ、四つ、五つ、6個、7個、8個。

649
00:21:18,420 --> 00:21:21,920
そして、この最後のパスでは、あります
私の今と快適ます

650
00:21:21,920 --> 00:21:23,830
それがソートされていると主張しますか？

651
00:21:23,830 --> 00:21:24,330
OK。

652
00:21:24,330 --> 00:21:25,880
視覚的には、それは絶対に本当です。

653
00:21:25,880 --> 00:21:28,410
しかし、機能的に、どのような
また、ちょうど起こりました

654
00:21:28,410 --> 00:21:31,870
あなたを可能にする最後のパスで
このリストは実際にあることを確認するために、

655
00:21:31,870 --> 00:21:32,660
ソート？

656
00:21:32,660 --> 00:21:34,477
>> 私は何をしたか、この最後のパスをしませんか？

657
00:21:34,477 --> 00:21:35,810
聴衆：変更はありませんでした。

658
00:21:35,810 --> 00:21:36,120
DAVID J.マラン：申し訳ありませんか？

659
00:21:36,120 --> 00:21:37,070
聴衆：変更はありません。

660
00:21:37,070 --> 00:21:38,653
DAVID J.マラン：変化はなかったです。

661
00:21:38,653 --> 00:21:41,947
だから、私への愚かなことだろう
再びその同じアルゴリズムを行います

662
00:21:41,947 --> 00:21:43,780
私はをしなかった場合
初めて変更されます。

663
00:21:43,780 --> 00:21:45,160
そして、状態が変更されていません。

664
00:21:45,160 --> 00:21:47,576
確かに、私は作るつもりはありません
任意の二時間を変更します。

665
00:21:47,576 --> 00:21:49,820
だから、それは今安全です
言って、リストがソートされます。

666
00:21:49,820 --> 00:21:52,069
>> そして実際、これは今で
我々は一般的によ何か

667
00:21:52,069 --> 00:21:56,900
コー​​ルバブルソート、これにより、ペアごと、
あなたは、再び間違いを修正

668
00:21:56,900 --> 00:22:00,210
そして再び、そして再び、あなた
前後に行き続けます、

669
00:22:00,210 --> 00:22:03,370
そして前後に、あなたまで
その時点で、そのようなスワップをしません

670
00:22:03,370 --> 00:22:07,089
あなたは、私は、ええ、自信を持つことができます
ミスのすべてを固定し終えました。

671
00:22:07,089 --> 00:22:08,630
のはリセットし、別のアプローチを試してみましょう。

672
00:22:08,630 --> 00:22:11,590
あなたたちは、に戻って行くことができれば
あなたは瞬間前だったため、

673
00:22:11,590 --> 00:22:13,780
これはこのように見えました。

674
00:22:13,780 --> 00:22:17,640
それでは、アプローチaを見てみましょう
もう少し試験の本のように、

675
00:22:17,640 --> 00:22:21,122
それによって我々は常にありました
アルファベットの文字を選択

676
00:22:21,122 --> 00:22:22,830
私達は種類の望んでいたこと
次に対処します。

677
00:22:22,830 --> 00:22:26,420
多分それは高いの手紙でした、
A、または低い文字Zのような

678
00:22:26,420 --> 00:22:28,170
>> だから、誰もが戻って、この順序でです。

679
00:22:28,170 --> 00:22:29,800
そして今、私はこれをしましょう​​。

680
00:22:29,800 --> 00:22:34,880
それでは、私が知っている見てみましょう
ここで8の数字。

681
00:22:34,880 --> 00:22:37,410
私は先に行くつもりだと
ただ意図的に選択します

682
00:22:37,410 --> 00:22:38,520
最小要素。

683
00:22:38,520 --> 00:22:38,760
右？

684
00:22:38,760 --> 00:22:39,801
これも直感的なようです。

685
00:22:39,801 --> 00:22:42,560
なぜ私は、最小を見つけることはありません
要素、それが属する場所に置きます、

686
00:22:42,560 --> 00:22:45,280
その後、次の最小の要素を取得入れます
それどこそれが属する、とだけ繰り返します。

687
00:22:45,280 --> 00:22:46,820
>> 直感的にあるため、
それはあまりにも動作するはずです。

688
00:22:46,820 --> 00:22:48,441
だから4、それはかなり少数です。

689
00:22:48,441 --> 00:22:49,940
私はこれがどこにあるか覚えておくつもりです。

690
00:22:49,940 --> 00:22:50,523
ちょっと待って。

691
00:22:50,523 --> 00:22:51,577
二つは小さくなる。

692
00:22:51,577 --> 00:22:53,910
私は今、どこに2覚えましょう
で、約4を忘れます。

693
00:22:53,910 --> 00:22:55,050
我々は、後で対処します。

694
00:22:55,050 --> 00:22:56,460
六、私は興味がありません。

695
00:22:56,460 --> 00:22:57,810
エイトは、私が興味を持っていませんよ。

696
00:22:57,810 --> 00:22:59,780
一つは、私の新しい少数です。

697
00:22:59,780 --> 00:23:01,470
だから、私は1つがどこにあるか覚えておくつもりです。

698
00:23:01,470 --> 00:23:02,534
三、興味を持っていません。

699
00:23:02,534 --> 00:23:03,450
セブン、興味を持っていません。

700
00:23:03,450 --> 00:23:04,530
五、興味を持っていません。

701
00:23:04,530 --> 00:23:07,390
>> そこで脱落することなく、
ステージは今年、

702
00:23:07,390 --> 00:23:09,890
私は数をつかむつもり選びます - 
そしてあなたの名前は再び何でしたか？

703
00:23:09,890 --> 00:23:10,150
>> アナン：アナン。

704
00:23:10,150 --> 00:23:11,220
>> DAVID J.マラン：アナン。

705
00:23:11,220 --> 00:23:13,540
そして、あなたはで私に参加することができれば
リストの先頭

706
00:23:13,540 --> 00:23:14,870
あなたが属している場所の、あなたを入れてみましょう。

707
00:23:14,870 --> 00:23:16,080
Unfortunately--あなたの名前は何ですか？

708
00:23:16,080 --> 00:23:16,650
>> STEFAN：ステファン。

709
00:23:16,650 --> 00:23:18,191
>> DAVID J.マラン：ステファンは方法です。

710
00:23:18,191 --> 00:23:23,490
ステファンは、この問題を解決する前に
問題は、我々は何をすべきでしょうか？

711
00:23:23,490 --> 00:23:25,412
我々はステファンに何をしますか？

712
00:23:25,412 --> 00:23:27,269
>> 聴衆：[聞こえません]。

713
00:23:27,269 --> 00:23:28,060
DAVID J.マラン：OK。

714
00:23:28,060 --> 00:23:28,850
だから我々はそれを行うことができます。

715
00:23:28,850 --> 00:23:31,730
私たちは、ソートのステファンとを取ることができる彼の
4、ちょうど変数に入れて

716
00:23:31,730 --> 00:23:33,530
そして、のためにそれにしがみつきます
ある程度の時間、

717
00:23:33,530 --> 00:23:35,220
これにより、ナンバーワンのための部屋を作ります。

718
00:23:35,220 --> 00:23:36,280
そして、それは悪くはありません。

719
00:23:36,280 --> 00:23:39,270
私はなぜない、提案することができ
私たちはここでステファンを置きますか？

720
00:23:39,270 --> 00:23:41,610
なぜこれが1に違反する可能性があります
私たちが始めたアイデアの

721
00:23:41,610 --> 00:23:44,830
先週、前回の話？

722
00:23:44,830 --> 00:23:45,330
うん？

723
00:23:45,330 --> 00:23:45,740
>> 聴衆：[聞こえません]。

724
00:23:45,740 --> 00:23:46,860
>> DAVID J.マラン：それにはインデックスがありません。

725
00:23:46,860 --> 00:23:49,735
あなたのように、確かに、と考えるならば
配列、これは負のようなものです、

726
00:23:49,735 --> 00:23:52,900
そう実際にはメモリがありません
ここで、これは確かに配列の場合、

727
00:23:52,900 --> 00:23:55,090
以下のような私たちは講義で先週宣言しました。

728
00:23:55,090 --> 00:23:56,250
だから我々はこれを行うべきではありません。

729
00:23:56,250 --> 00:23:57,340
私たちは、変数に格納することがあります。

730
00:23:57,340 --> 00:23:57,820
>> それとも、何を知っていますか？

731
00:23:57,820 --> 00:23:59,153
私は他の誰かがそれを示唆して聞きました。

732
00:23:59,153 --> 00:24:01,020
我々はステファンと他に何ができますか？

733
00:24:01,020 --> 00:24:03,770
なぜ私たちは彼を立ち退かせず、
ナンバーワンがあった場所の上に彼を置きます。

734
00:24:03,770 --> 00:24:05,170
あなたがあそこに行きたいのであれば。

735
00:24:05,170 --> 00:24:07,300
そして実際、これは
かなり良い解決策。

736
00:24:07,300 --> 00:24:10,480
今一方では、私は種類ました
問題が悪化しました。

737
00:24:10,480 --> 00:24:13,650
フォー遠くになりました
それがあるべき場所から。

738
00:24:13,650 --> 00:24:14,900
それは、この半分に向かってする必要があります。

739
00:24:14,900 --> 00:24:16,100
>> しかし、あなたは何を知っていますか？

740
00:24:16,100 --> 00:24:17,630
それは不運だったかもしれません。

741
00:24:17,630 --> 00:24:18,822
たぶん数8はここにありました。

742
00:24:18,822 --> 00:24:20,530
だから、多分私達は希望
ラッキー頂いております、

743
00:24:20,530 --> 00:24:22,460
そして最後に近い8を押しました。

744
00:24:22,460 --> 00:24:24,710
だから、一日の終わりには、
その種類のすべての平均値アウト。

745
00:24:24,710 --> 00:24:26,085
私たちは4気にする必要はありません。

746
00:24:26,085 --> 00:24:29,400
私は今気にすべてがあります
最小の要素を選択します。

747
00:24:29,400 --> 00:24:32,030
>> そして今、私はするつもりだもの
ナンバーワンを忘れますさん

748
00:24:32,030 --> 00:24:35,160
永久に、私が知っているので
私の後ろにリストがソートされます。

749
00:24:35,160 --> 00:24:36,720
だから、私のリストは、以前のサイズ8でした。

750
00:24:36,720 --> 00:24:37,720
今は、サイズ7のです。

751
00:24:37,720 --> 00:24:40,340
だから、私の問題を得ています
直線的ではあるが、小さいです。

752
00:24:40,340 --> 00:24:43,022
だから今、私が選択するつもりです
現在の最小の要素、2。

753
00:24:43,022 --> 00:24:46,520
六個、8個、4個、3、7、5。

754
00:24:46,520 --> 00:24:47,770
それが最小の要素でした。

755
00:24:47,770 --> 00:24:49,416
だから私は何をするつもりですwith--
あなたの名前は再び何でしたか？

756
00:24:49,416 --> 00:24:49,760
>> JOSEPH：ジョセフ。

757
00:24:49,760 --> 00:24:50,085
>> DAVID J.マラン：ジョセフ？

758
00:24:50,085 --> 00:24:52,000
我々は場所でジョセフを残すつもりです。

759
00:24:52,000 --> 00:24:54,842
今、私はふりをするつもりです
これらの人はよくare--こと、

760
00:24:54,842 --> 00:24:56,550
私はこの二つのことを知っています
すでにソートされています。

761
00:24:56,550 --> 00:24:58,424
今度は、に焦点を当ててみましょう
リストの残りの部分。

762
00:24:58,424 --> 00:25:00,080
シックスは、現在最も小さいです。

763
00:25:00,080 --> 00:25:01,190
エイトは大きいです。

764
00:25:01,190 --> 00:25:02,970
フォー現在最も小さいです。

765
00:25:02,970 --> 00:25:04,762
スリーは現在最も小さいです。

766
00:25:04,762 --> 00:25:07,720
そして今、私は3を選択するつもりです、
誰があなたの名前は再び何is--？

767
00:25:07,720 --> 00:25:08,190
セレナ：セレナ。

768
00:25:08,190 --> 00:25:10,620
DAVID J.マラン：セレナ、あなたができれば
あなたの番号とスワップをつかみますwith--

769
00:25:10,620 --> 00:25:11,550
KALSANG：Kalsang。

770
00:25:11,550 --> 00:25:12,940
DAVID J.マラン：Kalsang。

771
00:25:12,940 --> 00:25:15,220
背面に来て、私たちはしています
これら二つを交換する予定。

772
00:25:15,220 --> 00:25:17,360
そして今、のは、自動操縦でこれを入れてみましょう。

773
00:25:17,360 --> 00:25:21,589
私が行くと君たちに任せるつもりです
次の最小の要素を選択します。

774
00:25:21,589 --> 00:25:22,380
ダン、焦げ茶色、焦げ茶色、焦げ茶色。

775
00:25:22,380 --> 00:25:24,560
ナンバー4、あなたは何をすべきでしょうか？

776
00:25:24,560 --> 00:25:26,261
優れています。

777
00:25:26,261 --> 00:25:27,760
今、私は別のパスを作るつもりです。

778
00:25:27,760 --> 00:25:28,590
ダン、焦げ茶色、焦げ茶色、焦げ茶色。

779
00:25:28,590 --> 00:25:31,465
私は5は次の最も小さい参照してください。

780
00:25:31,465 --> 00:25:32,840
今、私は別のパスを取るつもりです。

781
00:25:32,840 --> 00:25:33,631
ダン、焦げ茶色、焦げ茶色、焦げ茶色。

782
00:25:33,631 --> 00:25:34,880
六が最も小さいです。

783
00:25:34,880 --> 00:25:35,520
良い。

784
00:25:35,520 --> 00:25:36,585
セブンは最も小さいです。

785
00:25:36,585 --> 00:25:37,085
変更はありません。

786
00:25:37,085 --> 00:25:38,630
八が最も小さいです。

787
00:25:38,630 --> 00:25:39,170
完了。

788
00:25:39,170 --> 00:25:43,900
>> だから我々は単に反復することによって何をやりましたか
他の後に一つの要素を選択します

789
00:25:43,900 --> 00:25:47,230
私たちがしている何かを実装しています
選択ソートとして定式化する予定。

790
00:25:47,230 --> 00:25:49,120
そして、それはあっても、おそらくです
説明するのは簡単な、

791
00:25:49,120 --> 00:25:51,310
その中で、文字通りすべてのあなた
やりたいだけで維持されています

792
00:25:51,310 --> 00:25:54,700
リストを前後に行きます
選択し、次の最小の要素、

793
00:25:54,700 --> 00:25:55,720
あなたが行っているまで。

794
00:25:55,720 --> 00:25:58,650
>> だから、おそらく、さらに簡単です
直感的に、最後のよりも。

795
00:25:58,650 --> 00:26:00,020
それでは、最後の1を試してみましょう。

796
00:26:00,020 --> 00:26:03,060
あなたたちは、自分をリセットすることができれば
以下の位置に

797
00:26:03,060 --> 00:26:08,600
1最後の時間は、私たちができない場合を見てみましょう
今一つの他のアプローチを正式。

798
00:26:08,600 --> 00:26:12,857
実際には、誰か
そこに提案したいです

799
00:26:12,857 --> 00:26:14,440
他にどのように我々はこれをやって行くのでしょうか？

800
00:26:14,440 --> 00:26:17,439
流行語や並べ替えを投げなければ
既に知られている回答の、

801
00:26:17,439 --> 00:26:19,689
ただ直感的に、私たちは何ができますか？

802
00:26:19,689 --> 00:26:21,635
>> 聴衆：[聞こえません]。

803
00:26:21,635 --> 00:26:22,510
DAVID J.マラン：うん。

804
00:26:22,510 --> 00:26:24,620
だから、いくつかの素晴らしい直感があります。

805
00:26:24,620 --> 00:26:28,020
良いものは、これまで発生しているように見えます
我々は分割コンピュータサイエンスの

806
00:26:28,020 --> 00:26:30,832
および分割の問題を克服
それ半々と半分インチ

807
00:26:30,832 --> 00:26:32,540
だから確かに、我々
それを行うために開始することができます。

808
00:26:32,540 --> 00:26:35,754
そして実際に、それはになるだろう、私たちはよ
まだ、私たちの最高のソリューションのいずれかを参照してください。

809
00:26:35,754 --> 00:26:37,420
しかし、ここでは、ずっと前に戻ってそれに来るように。

810
00:26:37,420 --> 00:26:40,500
実際には、我々がやろうとしています
少し後今週こと。

811
00:26:40,500 --> 00:26:42,180
我々はこれを解決するために他に何を行う可能性がありますか？

812
00:26:42,180 --> 00:26:44,647
だからここに誰もがにあります
一見ランダムな順序。

813
00:26:44,647 --> 00:26:45,230
あのね？

814
00:26:45,230 --> 00:26:48,320
むしろ前後に行くよりも、
前後に、前後に

815
00:26:48,320 --> 00:26:50,624
たびに、これはのように感じています
私は歩行をたくさんやっています。

816
00:26:50,624 --> 00:26:52,790
なぜ私だけで起動しません
リストの先頭

817
00:26:52,790 --> 00:26:54,960
そしてちょうどそれが属する4を入れて？

818
00:26:54,960 --> 00:26:59,680
だから、私は瞬間のために仮定しましょう
私のリストは、この最初の要素です。

819
00:26:59,680 --> 00:27:04,937
4つの時間的にこの時点でソートされ、
場合、私は気にすべてがすべてがここにいるのですか？

820
00:27:04,937 --> 00:27:06,520
これは右、ソートの自明本当ですか？

821
00:27:06,520 --> 00:27:10,000
1番号を含むリスト、など
その数4は明らかにソートされます。

822
00:27:10,000 --> 00:27:13,070
>> だから、私はちょうど定めてみましょう
このリストがソートされています。

823
00:27:13,070 --> 00:27:15,090
しかし、今、私はこのリストの残りの部分を持っています。

824
00:27:15,090 --> 00:27:17,240
だから今、私は2つに遭遇します。

825
00:27:17,240 --> 00:27:21,690
2明らかにどこを行います
4に関して属していますか？

826
00:27:21,690 --> 00:27:22,580
4前。

827
00:27:22,580 --> 00:27:23,862
だから私はここで何ができるのでしょうか？

828
00:27:23,862 --> 00:27:24,820
もう一度あなたの名前は何ですか？

829
00:27:24,820 --> 00:27:25,090
>> JOSEPH：ジョセフ。

830
00:27:25,090 --> 00:27:26,030
>> DAVID J.マラン：ジョセフ、
あなたが一歩ことができれば

831
00:27:26,030 --> 00:27:27,790
あなたの番号とちょっと。

832
00:27:27,790 --> 00:27:31,130
そして今、ステファンはここで何をすべきでしょうか？

833
00:27:31,130 --> 00:27:33,720
のがここの上にステファンをシフトしてみましょう。

834
00:27:33,720 --> 00:27:35,520
そして今、ヨセフはここに入って来てみましょう。

835
00:27:35,520 --> 00:27:39,660
そして今、私はそれを主張してみましょう
ここですべてがソートされます。

836
00:27:39,660 --> 00:27:42,474
そこで、同様の結果が、A
根本的に異なるアプローチ。

837
00:27:42,474 --> 00:27:44,140
私もそこに何があるか見ていません。

838
00:27:44,140 --> 00:27:46,310
私はちょうどの要素を取っておきます
彼らは私に手渡しているように、

839
00:27:46,310 --> 00:27:47,240
そしてそれらに対処。

840
00:27:47,240 --> 00:27:48,330
>> だから今、私は数6を参照してください。

841
00:27:48,330 --> 00:27:51,110
6番はどこに属しているのでしょうか？

842
00:27:51,110 --> 00:27:53,250
我々は2つ​​、4つ、6つがあります。

843
00:27:53,250 --> 00:27:54,800
彼女は今、ある場所を正確に。

844
00:27:54,800 --> 00:27:57,750
だから今のはその一人で残してみましょう、と
リストのこの部分と主張

845
00:27:57,750 --> 00:27:58,772
今ソートされます。

846
00:27:58,772 --> 00:28:01,230
だから、これは根本的に感じています
その内の異なる私はちょうどよ

847
00:28:01,230 --> 00:28:05,230
ここでリストを移動します
直線的に、私は戻って倍増することはありませんよ。

848
00:28:05,230 --> 00:28:05,730
はい。

849
00:28:05,730 --> 00:28:06,230
大丈夫。

850
00:28:06,230 --> 00:28:08,190
だから8、どこに属しますか？

851
00:28:08,190 --> 00:28:08,730
ここ。

852
00:28:08,730 --> 00:28:09,310
パーフェクト。

853
00:28:09,310 --> 00:28:10,210
だから今、1。

854
00:28:10,210 --> 00:28:10,900
おっと。

855
00:28:10,900 --> 00:28:13,010
それはだようにこれは感じています
高価になるだろう。

856
00:28:13,010 --> 00:28:15,690
さて、以前のアルゴリズムで、
私は人を入れ替え。

857
00:28:15,690 --> 00:28:18,648
だから私は彼にすべての方法を置く可能性があります
初めは、その後ヨセフを移動しました。

858
00:28:18,648 --> 00:28:21,450
しかし、私は今、ジョセフを移動する場合
何が間違っていることになるだろうか？

859
00:28:21,450 --> 00:28:24,250
>> 今、私は一種の私がしましたundone--ました
一歩前進して、撮影しました

860
00:28:24,250 --> 00:28:26,300
一歩戻って、今理由
ヨセフは順不同であろう。

861
00:28:26,300 --> 00:28:26,830
それでは、これを実行してみましょう。

862
00:28:26,830 --> 00:28:29,150
あなたはナンバーワンを取ることができれば
そして、ちょっとバックステップ。

863
00:28:29,150 --> 00:28:30,490
どのように我々は何をすることができますput--
あなたの名前は再びでしたか？

864
00:28:30,490 --> 00:28:31,130
>> アナン：アナン。

865
00:28:31,130 --> 00:28:32,610
>> DAVID J.マラン：代わりにアナン？

866
00:28:32,610 --> 00:28:36,091
何が関連して発生する必要があります
2、4、6、8か？

867
00:28:36,091 --> 00:28:37,570
彼らはすべてシフトする必要があります。

868
00:28:37,570 --> 00:28:42,590
だから8がシフトしたい場合
まず、6つ、4つ、2つ。

869
00:28:42,590 --> 00:28:45,380
そしてアナン、あなたが希望の場合
良い、ここに来るのが好きです。

870
00:28:45,380 --> 00:28:47,760
しかし、ここで、私たちはしました
種類の価格を支払っ

871
00:28:47,760 --> 00:28:49,510
アルゴリズムにおける異なるポイントで。

872
00:28:49,510 --> 00:28:52,550
選択を前回のに対し
並べ替え、さらにはバブルソート、

873
00:28:52,550 --> 00:28:54,700
私は戻って歩いていると、
前後、前後に、

874
00:28:54,700 --> 00:28:58,360
確かに合算されています
時間的、そして文字通り段階的。

875
00:28:58,360 --> 00:29:00,660
>> 最初は挿入ソート、
一見、それはだように見えます

876
00:29:00,660 --> 00:29:05,150
スーパー賢く、その中で私はちょうどよ
ゆっくりと、インクリメンタルに進展し、

877
00:29:05,150 --> 00:29:07,120
私は、この前後には行きません。

878
00:29:07,120 --> 00:29:09,410
しかし、誰かが実際にある場合
注文のうち、通知

879
00:29:09,410 --> 00:29:10,840
私はしなければならなかったすべての作業。

880
00:29:10,840 --> 00:29:14,750
私は、リストの半分を移動しなければなりませんでした
ただナンバーワンのための部屋を作るために。

881
00:29:14,750 --> 00:29:16,790
だから、同じ量です
仕事のこれまでそれを

882
00:29:16,790 --> 00:29:18,690
仕事のちょうど別のタイプ、感じています。

883
00:29:18,690 --> 00:29:19,370
>> それでは、続けましょう。

884
00:29:19,370 --> 00:29:22,657
だから今、私たちは皆知っていること
1と8の間にソートされています。

885
00:29:22,657 --> 00:29:23,740
ここで、私は数3を持っています。

886
00:29:23,740 --> 00:29:25,864
あなたがピックアップしたい場合
数3は、1つ前のステップ。

887
00:29:25,864 --> 00:29:28,260
そして、何あなたたちは何をする必要がありますか？

888
00:29:28,260 --> 00:29:28,760
うん。

889
00:29:28,760 --> 00:29:33,070
だからもう一つ、二つ、三つのステップです。

890
00:29:33,070 --> 00:29:36,010
ただ、コスト、時間の3つのユニット
私は、3人は今収まることができるように。

891
00:29:36,010 --> 00:29:37,460
最後に、7。

892
00:29:37,460 --> 00:29:39,730
>> それでは、先に行くとしましょう
あなたは、ステップバックを取ります。

893
00:29:39,730 --> 00:29:42,780
これは私たちだけの費用としています
1時間の単位が、それは大丈夫です。

894
00:29:42,780 --> 00:29:44,170
そして今、5のは、に行きます
もう少し高価になります。

895
00:29:44,170 --> 00:29:45,340
あなたはバックステップしたい場合。

896
00:29:45,340 --> 00:29:48,380
我々は、8を移動する必要があります
七、6。

897
00:29:48,380 --> 00:29:50,749
そして、誰もが今、ソートされます。

898
00:29:50,749 --> 00:29:52,290
だからここに私たちのボランティアに大きな手。

899
00:29:52,290 --> 00:29:53,554
どうもありがとうございます。

900
00:29:53,554 --> 00:29:56,220
>> [拍手]

901
00:29:56,220 --> 00:29:56,860
>> みなさんありがとう。

902
00:29:56,860 --> 00:29:57,520
みなさんありがとう。

903
00:29:57,520 --> 00:30:02,940
それでは、今どれだけ見てみましょう
高価なすべてのことでした。

904
00:30:02,940 --> 00:30:06,210
のは、おそらく考えてみましょう
これらの最も簡単な、バブルソート。

905
00:30:06,210 --> 00:30:09,950
そして、私は唯一のため、最も簡単なと言います
あなただけのことで貪欲にそれを解決することができます

906
00:30:09,950 --> 00:30:11,660
ここでペアごとに問題を修正します。

907
00:30:11,660 --> 00:30:13,720
ペアごとの問題を修正
ここでは、何度も何度も

908
00:30:13,720 --> 00:30:17,680
そして再び、多くの繰り返し
あなたのような時間は、実際にする必要があります。

909
00:30:17,680 --> 00:30:21,050
>> だから、ことが判明
バブルソートと、よく、

910
00:30:21,050 --> 00:30:25,820
どのように多くの手順は、私が取る必要があるん
このアルゴリズムの最初のパス？

911
00:30:25,820 --> 00:30:30,850
私は、のいずれかをsee--せtake--可能性があります
2つ、3つ、4つ、5、6、7。

912
00:30:30,850 --> 00:30:32,190
そして、ここで8要素があります。

913
00:30:32,190 --> 00:30:35,280
だから、のようなものだnはマイナス1のステップへ
リストの先頭から取得

914
00:30:35,280 --> 00:30:36,380
リストの最後に。

915
00:30:36,380 --> 00:30:41,350
>> しかし、選択ソートで、私はことを思い出してください
何度も何度も要素を選択

916
00:30:41,350 --> 00:30:44,590
そして再び、それは最も小さいのです、
私は、場所に入れています

917
00:30:44,590 --> 00:30:46,616
しかし、私はないんだけど
再び私の後ろに見て。

918
00:30:46,616 --> 00:30:49,490
だから私はそれをもう少し明確だと思います
その後、初めてということに、私はかもしれません

919
00:30:49,490 --> 00:30:52,680
すべてのnマイナス1のステップを取る必要があります
最小の要素を検索します。

920
00:30:52,680 --> 00:30:55,920
それから私は、場所にそれらを置く、と私
以前ここにいた誰立ち退か。

921
00:30:55,920 --> 00:30:57,500
>> しかし、私はする必要はありません
この要素で探し続けます、

922
00:30:57,500 --> 00:30:59,040
私はそれが知っているので、
既に最小。

923
00:30:59,040 --> 00:31:01,581
だから今、私はちょうど7で見ることができます
要素は、6つの要素、

924
00:31:01,581 --> 00:31:03,290
その後五行、4つの要素。

925
00:31:03,290 --> 00:31:06,900
そのため、数学的、nがある場合
要素または番号の数

926
00:31:06,900 --> 00:31:11,990
使い始めたことを、あなたが想像することができます
これは、n -1と同じであること、

927
00:31:11,990 --> 00:31:14,250
プラスNマイナス2段階、
プラスNマイナス3段階、

928
00:31:14,250 --> 00:31:16,780
プラスNマイナス4段階、すべての
あと一歩までの方法。

929
00:31:16,780 --> 00:31:18,160
そして、私は私の最後の人にです。

930
00:31:18,160 --> 00:31:20,650
>> そして、あなたは多くのことを思い出した場合
統計書籍や数学の本の

931
00:31:20,650 --> 00:31:24,730
これらの式を持っています
ハードカバー背面または彼らの前、

932
00:31:24,730 --> 00:31:27,690
それがこのシリーズのことが判明
より簡単に表すことができます。

933
00:31:27,690 --> 00:31:28,857
n回nはマイナス2以上の1。

934
00:31:28,857 --> 00:31:31,273
それがないなら、それは大丈夫です
あなたの心の最前線に。

935
00:31:31,273 --> 00:31:32,420
しかし、これは確かに真実です。

936
00:31:32,420 --> 00:31:34,449
それはそれを書いているだけのシンプルな方法です。

937
00:31:34,449 --> 00:31:36,240
それから、あなたが考える場合
バック小学校に、

938
00:31:36,240 --> 00:31:38,698
あなただけの乗算を開始するとき
物事うち、このコースの、

939
00:31:38,698 --> 00:31:41,820
ちょうどN乗マイナスnは、2で割っています。

940
00:31:41,820 --> 00:31:44,772
私がやったすべてが拡大しています
そこに表現。

941
00:31:44,772 --> 00:31:46,730
そしてそうのはこれを書き換えてみましょう
少し違いました。

942
00:31:46,730 --> 00:31:49,780
それは、N 2を2で割っマイナスN /平方です。

943
00:31:49,780 --> 00:31:53,270
>> だからもう一度、私は一種の適用です
そこにいくつかの算術ルール。

944
00:31:53,270 --> 00:31:57,140
しかし、今気付くことの最大の用語
この式では、いわば、

945
00:31:57,140 --> 00:31:58,540
nが乗ということです。

946
00:31:58,540 --> 00:32:02,910
そうです、それは、n乗です
2、マイナスのn / 2で割りました。

947
00:32:02,910 --> 00:32:05,080
>> 一般的に、もしnが
大きな値になるだろう、

948
00:32:05,080 --> 00:32:08,740
私は、nが平方主張するつもりです
支配的要因になるだろう。

949
00:32:08,740 --> 00:32:10,490
それはちょうどになるだろう
大きな貢献者

950
00:32:10,490 --> 00:32:12,877
N / 2よりもステップ数です。

951
00:32:12,877 --> 00:32:13,960
だから私はこのとはどういう意味ですか？

952
00:32:13,960 --> 00:32:16,795
でも、簡単な例を試してみましょう
数学は少し大きいを取得しますが。

953
00:32:16,795 --> 00:32:20,210
>> だから我々は100万人を持っていたと仮定
ステージ上、または100万のもの

954
00:32:20,210 --> 00:32:21,320
私たちは、ソートしたいということ。

955
00:32:21,320 --> 00:32:23,730
のは万人をプラグしてみましょう
まさにその式に

956
00:32:23,730 --> 00:32:27,230
それが総取りどのように多くの手順を確認し
たとえば使用して百万の要素をソートするには、

957
00:32:27,230 --> 00:32:28,560
選択ソート。

958
00:32:28,560 --> 00:32:30,760
>> だから我々は、以前と同じ式を有するだろう。

959
00:32:30,760 --> 00:32:34,120
私が得られるように、私は、百万プラグたいです
、2で割っ乗万人

960
00:32:34,120 --> 00:32:35,990
マイナス2で割っ万人。

961
00:32:35,990 --> 00:32:40,180
私は、事前にその計算を行う場合
ここで、我々は5000億を持っています

962
00:32:40,180 --> 00:32:47,460
マイナス500,000します
私たち4999.995億を与え、

963
00:32:47,460 --> 00:32:49,270
これはかなりくそ大きいです。

964
00:32:49,270 --> 00:32:54,370
>> 実際には、あなたは今比較する場合
4990億999百万円

965
00:32:54,370 --> 00:33:01,210
私たちの元の値に対して500,000
5000億、それはとても気近いです。

966
00:33:01,210 --> 00:33:06,850
右？ nは2で与え割っ乗
us--いうか、nは2で割っ二乗

967
00:33:06,850 --> 00:33:08,370
私たち5000億を与えました。

968
00:33:08,370 --> 00:33:13,510
それはかなりくそ近いです
4999.995億に、

969
00:33:13,510 --> 00:33:17,970
500,000オフ差し引くと言うことです、
またはより一般的には、減算します

970
00:33:17,970 --> 00:33:20,010
nは、本当に大したことがない乗。

971
00:33:20,010 --> 00:33:22,490
これらを作るnが平方しました
数字は本当に速い成長します。

972
00:33:22,490 --> 00:33:25,790
>> さて、これは重要である限り
我々として、コンピュータ科学者として、

973
00:33:25,790 --> 00:33:29,350
一般的にはあまり気にするつもりはありません
これらの式のニュアンスについて

974
00:33:29,350 --> 00:33:31,400
そしてまさに
正確な答えがあります。

975
00:33:31,400 --> 00:33:33,390
私たちは、あなたが何を知っている、ということだけ気に？

976
00:33:33,390 --> 00:33:37,810
一日の終わりに、この式
二乗Nのオーダーです。

977
00:33:37,810 --> 00:33:39,350
>> はい、私たちはそこに2で割るいます。

978
00:33:39,350 --> 00:33:41,360
はい、私たちはオフのnマイナス2を引いています。

979
00:33:41,360 --> 00:33:46,860
しかし、一日の終わりに、用語
それは本当に私たちを傷つける、私たちがかかります

980
00:33:46,860 --> 00:33:48,995
手順の多くは、その正方形の用語です。

981
00:33:48,995 --> 00:33:51,370
だから何コンピュータ科学者
一般的に行うために起こっています

982
00:33:51,370 --> 00:33:54,160
それらのすべてを無視しています
小さい次項、

983
00:33:54,160 --> 00:33:56,900
そしてちょうどその1を見て
コストに最も貢献しています。

984
00:33:56,900 --> 00:34:00,530
>> 我々はできるので、これは、いいです
今はるかに大きい一般に話します

985
00:34:00,530 --> 00:34:02,470
アルゴリズムについては、それらを比較することができます。

986
00:34:02,470 --> 00:34:04,550
私はだと、実際
このOを使用すると、意図的です。

987
00:34:04,550 --> 00:34:06,680
私は順番に言うとき
私は特にです

988
00:34:06,680 --> 00:34:09,560
何かに言及
大きなO.とビッグOと呼ばれます

989
00:34:09,560 --> 00:34:14,090
そのコンピュータの表記があります
科学者は、記述するために使用しています

990
00:34:14,090 --> 00:34:16,710
上位何かに結合しました。

991
00:34:16,710 --> 00:34:21,150
>> ですから、アルゴリズムと言う場合
n個のビッグOで2乗さ、

992
00:34:21,150 --> 00:34:23,380
私が提案されているようなだけ
先ほど、その手段

993
00:34:23,380 --> 00:34:27,710
そのランニングの観点から
時間やその効率、

994
00:34:27,710 --> 00:34:30,090
それがために取ります
n個のステップを乗。

995
00:34:30,090 --> 00:34:31,420
多分少なく、多分より。

996
00:34:31,420 --> 00:34:33,435
しかし、それは、nの順に乗です。

997
00:34:33,435 --> 00:34:34,560
そして、それは上限です。

998
00:34:34,560 --> 00:34:36,530
それはあることを行っていません
それよりももっと痛いです。

999
00:34:36,530 --> 00:34:40,800
これは、n乗になるだろう、または2いません
N、またははるかに大きなものに。

1000
00:34:40,800 --> 00:34:43,800
これが上限であります
何でそのコストがあります。

1001
00:34:43,800 --> 00:34:46,150
だから、みましょうことを考えると
いくつかの例を考えてみましょう。

1002
00:34:46,150 --> 00:34:49,820
そして、これは単に有限リストです
非常に一般的な実行時間の

1003
00:34:49,820 --> 00:34:52,870
であることを意味していアルゴリズムの
私たちがきたいくつかのものを例示します

1004
00:34:52,870 --> 00:34:53,600
すでに見。

1005
00:34:53,600 --> 00:34:58,060
>> 例えば、例でそう
選択ソート、私はここで何を主張しています

1006
00:34:58,060 --> 00:35:02,250
その選択ソートの走行があります
時間は、N乗のオーダーです。

1007
00:35:02,250 --> 00:35:06,260
最悪の場合、私が持っているつもりです
ここでは、乱数の全体の束。

1008
00:35:06,260 --> 00:35:08,600
そして、私たちが数学的に見たように、
私は歩き続ける場合

1009
00:35:08,600 --> 00:35:11,310
リストをスルー
次の最小を選択リスト、

1010
00:35:11,310 --> 00:35:14,410
幾度もの要素は、私の場合
実際の手順のすべてを書き留め

1011
00:35:14,410 --> 00:35:18,750
私はformulaically提案されているように私は取っています
前に、それは、N乗のオーダーです

1012
00:35:18,750 --> 00:35:20,370
私が取っている段階。

1013
00:35:20,370 --> 00:35:24,520
>> そしてそれは、そのバブルが判明
ソートと挿入ソート

1014
00:35:24,520 --> 00:35:27,370
最悪の場合、同じように遅いです。

1015
00:35:27,370 --> 00:35:32,040
例えば、考えてみて、挿入ソート、
我々はに対処最後のアルゴリズム、

1016
00:35:32,040 --> 00:35:35,500
これは、私たちは、要素を見ていました、
それが属している場所と、それを挿入します。

1017
00:35:35,500 --> 00:35:38,720
そして、我々は次の要素を見て、
それが属している場所、それを挿入します。

1018
00:35:38,720 --> 00:35:40,990
>> だから、可能な限り最高のシナリオを検討してください。

1019
00:35:40,990 --> 00:35:45,590
私は私のボランティアがラインアップしていたと仮定
文字通りこのような、8一通り、

1020
00:35:45,590 --> 00:35:47,440
すでにソート。

1021
00:35:47,440 --> 00:35:51,300
挿入ソートはどのように多くのステップであります
8人をソートするために連れて行きます、

1022
00:35:51,300 --> 00:35:55,640
彼らがステージに到着した場合
このように見て？

1023
00:35:55,640 --> 00:35:57,410
>> 8人はすでにソート。

1024
00:35:57,410 --> 00:35:58,760
そして、私は挿入ソートを使用します。

1025
00:35:58,760 --> 00:36:02,180
アルゴリズムのその最後。

1026
00:36:02,180 --> 00:36:03,640
さて、本当の高速をreenactてみましょう。

1027
00:36:03,640 --> 00:36:05,504
私はここから始めあれば、私は1つを参照してください。

1028
00:36:05,504 --> 00:36:06,420
1はどこに属しているのでしょうか？

1029
00:36:06,420 --> 00:36:07,730
それはここに属します。

1030
00:36:07,730 --> 00:36:08,330
私は2つを参照してください。

1031
00:36:08,330 --> 00:36:09,660
二人はどこに属しているのでしょうか？

1032
00:36:09,660 --> 00:36:10,260
ここ。

1033
00:36:10,260 --> 00:36:10,900
私は3を参照してください。

1034
00:36:10,900 --> 00:36:11,920
3人はどこに属しているのでしょうか？

1035
00:36:11,920 --> 00:36:12,480
ここ。

1036
00:36:12,480 --> 00:36:13,100
>> 私は4を参照してください。

1037
00:36:13,100 --> 00:36:13,600
ここ。

1038
00:36:13,600 --> 00:36:15,660
5つ、6つ、7つ、8。

1039
00:36:15,660 --> 00:36:17,320
自分自身を繰り返す理由はありません。

1040
00:36:17,320 --> 00:36:21,260
だから、どのように多くの手順
すなわち、n個の点ですか？

1041
00:36:21,260 --> 00:36:23,870
これは、n個のオーダーです
手順は、右？ nはマイナス1。

1042
00:36:23,870 --> 00:36:27,567
しかし、私は線形数を取りました
ステップの、そして今私は終わりです。

1043
00:36:27,567 --> 00:36:28,900
だから、しかし、最良の場合です。

1044
00:36:28,900 --> 00:36:29,983
何最悪の場合はどうですか？

1045
00:36:29,983 --> 00:36:32,730
何8は、あそこにありました
そして、7がダウンしました、

1046
00:36:32,730 --> 00:36:35,840
そして、1と2はそう、ここを超えていました
リストは本当に逆転したこと？

1047
00:36:35,840 --> 00:36:38,300
>> さて、何が実際に起こります
これは数ありますか？

1048
00:36:38,300 --> 00:36:41,300
そして、我々は例だけのカップルをやります。

1049
00:36:41,300 --> 00:36:49,300
何確かに、もし、数8
ここで、number--おっと。

1050
00:36:49,300 --> 00:36:52,660

1051
00:36:52,660 --> 00:36:56,430
だから何であれば、確かに、数
8は、こちらにすべての方法です、

1052
00:36:56,430 --> 00:36:57,790
私は挿入ソートを使用していますか？

1053
00:36:57,790 --> 00:36:58,290
>> OK。

1054
00:36:58,290 --> 00:37:00,280
私はそれが場所でだ瞬間に主張しています。

1055
00:37:00,280 --> 00:37:03,152
しかし、今、どこseven-- 7は行くのですか？

1056
00:37:03,152 --> 00:37:04,360
もちろん、それはここを乗り越えます。

1057
00:37:04,360 --> 00:37:06,760
だから私は、8人以上の場所を移動する必要があります。

1058
00:37:06,760 --> 00:37:08,554
今6、どこに行くのですか？

1059
00:37:08,554 --> 00:37:09,220
まあ、すべての権利。

1060
00:37:09,220 --> 00:37:13,150
今、私は8オーバーを移動する必要があります
場所、および場所の上に7、

1061
00:37:13,150 --> 00:37:14,440
そして私は6をドスンと座ります。

1062
00:37:14,440 --> 00:37:16,870
>> そこで初めて、コスト
物事を解決する私の一歩、

1063
00:37:16,870 --> 00:37:18,570
それは私に物事を修正するには、2つのステップを要しました。

1064
00:37:18,570 --> 00:37:20,370
それはどのように多くのステップであります
修正するために連れて行きます

1065
00:37:20,370 --> 00:37:22,720
正しい場所に5を置くためのもの？

1066
00:37:22,720 --> 00:37:23,340
3。

1067
00:37:23,340 --> 00:37:29,520
今私がする必要があるため、
一、二、三を動かします。

1068
00:37:29,520 --> 00:37:32,430
どのように多くの手順は取るつもりされています
正しい場所に4を置きますか？

1069
00:37:32,430 --> 00:37:36,040
4プラス5、プラス6、+ 7。

1070
00:37:36,040 --> 00:37:40,260
>> そしてそれは、数学的に同一のです
我々は、選択ソートのために記載するもの。

1071
00:37:40,260 --> 00:37:42,130
我々は、このシリーズを持っています
それはただ増加しています。

1072
00:37:42,130 --> 00:37:45,650
1プラス2プラス3プラス4、
あるいは逆に、7プラス6

1073
00:37:45,650 --> 00:37:52,610
プラス5プラス4は、今日のためにアップ追加します
n個のオーダー乗にする目的。

1074
00:37:52,610 --> 00:37:57,640
>> だから私もそれを規定しましょう
バブルソートは、nの二乗でもあります。

1075
00:37:57,640 --> 00:38:01,340
バブルソートと、各ので、
私はリストを通過する時、

1076
00:38:01,340 --> 00:38:03,100
私は大体どのように多くのステップを取っていますか？

1077
00:38:03,100 --> 00:38:06,260
たびに私は、文字通り
そこに、そこから歩いて？

1078
00:38:06,260 --> 00:38:07,960
おおよそnステップ。

1079
00:38:07,960 --> 00:38:12,650
しかし、どのように何回も私はかもしれません
リストを通過する必要がありますか？

1080
00:38:12,650 --> 00:38:13,920
>> まあ、おおよそn個の時間。

1081
00:38:13,920 --> 00:38:15,680
たぶん、nはマイナス1であるが、おおよそn回。

1082
00:38:15,680 --> 00:38:16,430
まあ、それはなぜですか？

1083
00:38:16,430 --> 00:38:19,560
まあ、バブルソートと、もし
私たちは、バブルソートで始まります

1084
00:38:19,560 --> 00:38:23,570
最悪でリストを
再び完全な状況、

1085
00:38:23,570 --> 00:38:25,550
後方に、何が起こるだろうか？

1086
00:38:25,550 --> 00:38:28,830
私はリストを通過し、その数
一つはあそこのすべての方法に属します。

1087
00:38:28,830 --> 00:38:33,280
>> しかし、バブルソートで、どの程度まで1を行います
リストを私の最初のパスに移動しますか？

1088
00:38:33,280 --> 00:38:36,620
彼はどのように多くのスポットを取得しません
正しい場所に近いですか？

1089
00:38:36,620 --> 00:38:37,240
一つだけ。

1090
00:38:37,240 --> 00:38:40,281
だから、これを介して、あなたは親切の理由であれば、
このアルゴリズムを通じて毎回、

1091
00:38:40,281 --> 00:38:41,880
ダビデの服用およそnステップ。

1092
00:38:41,880 --> 00:38:44,940
しかし、どのように多くのパス
リストをそれがあります

1093
00:38:44,940 --> 00:38:49,060
バブルへのいずれかに連れて行きます
それが属する左に？

1094
00:38:49,060 --> 00:38:51,840
>> 彼は、のように移動するために持っています
n個のスペースがこの方法です。

1095
00:38:51,840 --> 00:38:57,960
だからリストのソートを行うには、
私は前後にn回を歩かなければなりません。

1096
00:38:57,960 --> 00:39:01,540
そして、それぞれの時間は、私はよ
n個の要素を見て。

1097
00:39:01,540 --> 00:39:05,410
ように、n個のものをn回行います
n個の順序は乗。

1098
00:39:05,410 --> 00:39:07,220
>> 今、我々はいくつかに表示されます
ショートパンツのこと

1099
00:39:07,220 --> 00:39:10,440
CS50の次の問題に埋め込まれています
これらに、別のアプローチを設定し、

1100
00:39:10,440 --> 00:39:13,490
しかし今のところ、ちょうど考えてみましょう
他のいくつかの実行時間、

1101
00:39:13,490 --> 00:39:16,840
仕分けものは取る場合は特に
でシンクする時間を少し。

1102
00:39:16,840 --> 00:39:21,790
我々はすでに見てきたアルゴリズムは何ですか
すなわち、n個のステップの順序をとりますか？

1103
00:39:21,790 --> 00:39:27,560
>> 線形数を取る必要がありますどのような
私たちがこれまで見てきたステップの？

1104
00:39:27,560 --> 00:39:29,350
あれは何でしょう？

1105
00:39:29,350 --> 00:39:30,480
電話帳を検索します。

1106
00:39:30,480 --> 00:39:31,390
最初のアルゴリズム。

1107
00:39:31,390 --> 00:39:31,560
右？

1108
00:39:31,560 --> 00:39:33,650
私たちは、直線的にしている場合には
マイク・スミスをお探しですか？

1109
00:39:33,650 --> 00:39:34,150
確かに。

1110
00:39:34,150 --> 00:39:37,180
0週目からは、私が始めたとき
一度に一つのページをめくります、

1111
00:39:37,180 --> 00:39:40,095
そして私もそれは親切だと言いました
リニア感アルゴリズム、

1112
00:39:40,095 --> 00:39:42,720
私たちは上の画像を持っていました
ストレート赤線とボード

1113
00:39:42,720 --> 00:39:44,678
ストレートイエロー
ライン、それらは確かにありま​​した

1114
00:39:44,678 --> 00:39:46,810
n個のビッグOであるアルゴリズム。

1115
00:39:46,810 --> 00:39:50,680
>> 電話でマイク・スミスを見つけるため、
最悪の場合、nページの本、

1116
00:39:50,680 --> 00:39:52,422
私のn措置をとることがあります。

1117
00:39:52,422 --> 00:39:53,630
出席を取ることについてはどう？

1118
00:39:53,630 --> 00:39:55,790
一二三四五六。

1119
00:39:55,790 --> 00:39:59,420
これの実行時間は何ですか
出席を取るためのアルゴリズム？

1120
00:39:59,420 --> 00:40:03,070
なぜなら理論的には、nのビッグO、私は
部屋に全員を指すように持っています。

1121
00:40:03,070 --> 00:40:05,861
>> さて余談として、どの程度
0週目から他の最適化？

1122
00:40:05,861 --> 00:40:08,117
2つ、4つ、6、8、10、12。

1123
00:40:08,117 --> 00:40:10,200
コンピューター科学者になります
実現、ちょっと待って、

1124
00:40:10,200 --> 00:40:12,320
それは、順番にい
nは2段階で割りました。

1125
00:40:12,320 --> 00:40:12,820
右？

1126
00:40:12,820 --> 00:40:14,444
私は一度に2人をやっているので。

1127
00:40:14,444 --> 00:40:17,015
しかし、我々は無視するつもりです
これらの低次の項、

1128
00:40:17,015 --> 00:40:19,140
そして、私たちはするつもりです
2による除算を捨てます、

1129
00:40:19,140 --> 00:40:21,830
そして、だけ、言って、nのビッグO
そのアルゴリズムのためにも。

1130
00:40:21,830 --> 00:40:22,760
>> これはどう？

1131
00:40:22,760 --> 00:40:26,170
当社は、これらのいくつかをスキップが、何だろう
n個のログだったアルゴリズムでしたか？

1132
00:40:26,170 --> 00:40:29,900
それはおよそログn個の手順を取りましたか？

1133
00:40:29,900 --> 00:40:30,870
分割統治。

1134
00:40:30,870 --> 00:40:31,369
その通りです。

1135
00:40:31,369 --> 00:40:33,900
電話帳の例のように
0週目およびそれ以前の今日、

1136
00:40:33,900 --> 00:40:36,191
ここで、我々は問題を分割
何度も何度も何度も。

1137
00:40:36,191 --> 00:40:39,070
私たちは週にボードに描きました
湾曲した緑の線としてゼロ、

1138
00:40:39,070 --> 00:40:41,460
そして我々はそれがその日だったと述べました
対数アルゴリズム。

1139
00:40:41,460 --> 00:40:44,970
>> そして実際、ステップ数は、
分割統治を実行するのにかかります、

1140
00:40:44,970 --> 00:40:48,610
私たちは始めましょうとして、またはバイナリ検索
電話帳のように、それを呼び出して、

1141
00:40:48,610 --> 00:40:50,680
ログおよびステップのオーダーです。

1142
00:40:50,680 --> 00:40:52,470
そして、これは奇妙な1のビットです。

1143
00:40:52,470 --> 00:40:54,910
>> 何が一歩を取り、
より具体的に

1144
00:40:54,910 --> 00:40:56,240
ステップの定数？

1145
00:40:56,240 --> 00:40:58,865
多分それは多分それは3ですが、2です、
しかし、コンピューター科学者だけ

1146
00:40:58,865 --> 00:41:01,423
1のビッグOとして、それを簡素化し、
手順のいくつかの定数。

1147
00:41:01,423 --> 00:41:04,256
あなたがそれを行うことが何か何
ステップの一定数を取りますか？

1148
00:41:04,256 --> 00:41:08,030

1149
00:41:08,030 --> 00:41:10,930
>> 拍手の実行時間は何ですか？

1150
00:41:10,930 --> 00:41:11,920
一定の時間。

1151
00:41:11,920 --> 00:41:12,420
右？

1152
00:41:12,420 --> 00:41:15,490
同様の実行時間は何ですか
一つだけを取る何かをやって

1153
00:41:15,490 --> 00:41:18,570
印刷F Hello Worldのような操作、。

1154
00:41:18,570 --> 00:41:24,110
すなわち、一定の時間であると言われるかもしれません
印刷Fと少ないコーナーケースでない限り、

1155
00:41:24,110 --> 00:41:28,260
何走行時間かもしれません
印刷のFは、実際にも？

1156
00:41:28,260 --> 00:41:28,790
なぜ？

1157
00:41:28,790 --> 00:41:30,550
その場合のn個の測定とは何ですか？

1158
00:41:30,550 --> 00:41:32,251
>> 聴衆：[聞こえません]。

1159
00:41:32,251 --> 00:41:33,250
DAVID J.マラン：その通り。

1160
00:41:33,250 --> 00:41:34,900
文字数
我々は、印刷したいです。

1161
00:41:34,900 --> 00:41:36,191
だから、非常に状況依存です。

1162
00:41:36,191 --> 00:41:39,910
今日、私たちは上の多くを集中してきました
ボード上のここに文字と数字。

1163
00:41:39,910 --> 00:41:43,540
しかし、それはまたあるかもしれません
実際の文字列内の文字。

1164
00:41:43,540 --> 00:41:46,420
だから、別のがあると判明します
気に開始され、測定、

1165
00:41:46,420 --> 00:41:48,530
それは反対です
ビッグOの、いわば。

1166
00:41:48,530 --> 00:41:50,120
>> それはオメガの表記です。

1167
00:41:50,120 --> 00:41:53,380
ビッグOは、何を意味するのに対し
上部のあなたの実行時間にバインドされましたか？

1168
00:41:53,380 --> 00:41:55,580
最大限に、どれだけの時間
何かがかかるかもしれませんか？

1169
00:41:55,580 --> 00:41:59,250
Omega--申し訳ありません、これは来続けます
up--はその反対で、

1170
00:41:59,250 --> 00:42:02,960
それによって、それが上下限です
何かがかかる場合があります時間の量。

1171
00:42:02,960 --> 00:42:10,480
>> Soが例えば、アルゴリズムは何ですか
それはいつものn乗の手順を実行しますか？

1172
00:42:10,480 --> 00:42:15,600
さて、私たちはアルゴリズムのいずれかを見てきました
今日、実際には、それにもあるかもしれません。

1173
00:42:15,600 --> 00:42:16,720
選択ソート。

1174
00:42:16,720 --> 00:42:18,270
選択ソートかなり愚かです。

1175
00:42:18,270 --> 00:42:21,760
でもでも、algorithm--残念場合
配列が既にソートされている場合、

1176
00:42:21,760 --> 00:42:24,150
選択ソートをしようとしています
リストを歩き続けます

1177
00:42:24,150 --> 00:42:28,907
それは最も小さい持っていることを確認します
要素、何度も何度もして、もう一度。

1178
00:42:28,907 --> 00:42:31,740
そして、あなたは人間であっても
観客は、数分待つことを知って、

1179
00:42:31,740 --> 00:42:33,948
あなたは既に経過
最小要素、コンピュータ

1180
00:42:33,948 --> 00:42:37,300
それが見えるまでことを知りません
リストをすべての方法。

1181
00:42:37,300 --> 00:42:40,240
同様に、下側のことをバインド
また考慮されるかもしれません

1182
00:42:40,240 --> 00:42:42,000
線形時間であるかもしれません。

1183
00:42:42,000 --> 00:42:48,260
>> それはどのくらいの時間をすることがかかります
最良でソートn個の要素

1184
00:42:48,260 --> 00:42:52,420
バブルソートのようなものを用いた場合？

1185
00:42:52,420 --> 00:42:54,280
あなたのリストがすでにソートされているとします。

1186
00:42:54,280 --> 00:42:56,696
私たちは、バブルソートをオンに取ると述べました
n個の順序は、ステップを乗。

1187
00:42:56,696 --> 00:42:59,640
しかし、それはすでに何をソートしていますか？

1188
00:42:59,640 --> 00:43:02,310
あなたは何をした後に実現した場合
配列内を1パス

1189
00:43:02,310 --> 00:43:03,540
あなたはスワップを行わなかったこと？

1190
00:43:03,540 --> 00:43:05,970
あなたがより多くのパスを作り続ける必要がありますか？

1191
00:43:05,970 --> 00:43:06,470
>> いいえ。

1192
00:43:06,470 --> 00:43:10,340
バブルソートのだから下界
線形であると言うことがあります。

1193
00:43:10,340 --> 00:43:11,830
n個のオメガ。

1194
00:43:11,830 --> 00:43:14,450
そして、私たちは見ることができ
これらの他にも。

1195
00:43:14,450 --> 00:43:17,990
それでは、簡単に見てみましょう
ここだけの可視化で

1196
00:43:17,990 --> 00:43:20,790
これらは自分自身を区別する方法を確認します。

1197
00:43:20,790 --> 00:43:24,592
私はこの中に、ここでダウンして行くつもりです
C50のウェブサイト上で利用可能なページ、

1198
00:43:24,592 --> 00:43:27,550
それが働いて得るために苦痛になり、
それはと呼ばれる技術を使用していますので、

1199
00:43:27,550 --> 00:43:30,560
あるJavaアプレット、
大部分がサポートされていない、これらの日、

1200
00:43:30,560 --> 00:43:32,730
少なくともChromeと特定の他者による。

1201
00:43:32,730 --> 00:43:37,070
>> そして、私が先に行くと、これを加速させます
アップと何が起こっているかを説明します。

1202
00:43:37,070 --> 00:43:40,840
これは、バブルのデモです
ソート、私たちが見た最初のアルゴリズム。

1203
00:43:40,840 --> 00:43:43,950
そして、各点での可視化です
これらのバーの数を表します。

1204
00:43:43,950 --> 00:43:45,710
大きなバー、
数より大きい。

1205
00:43:45,710 --> 00:43:47,520
小さいバー、
数より小さい。

1206
00:43:47,520 --> 00:43:50,353
そしてあなたも、視覚的に見ることができるもの
これは、超高速起こっているものの、

1207
00:43:50,353 --> 00:43:53,699
赤いバーは私のようであることで、
問題を修正する前後に歩きます。

1208
00:43:53,699 --> 00:43:56,740
あなたは大きな要素ということを見ることができます
確かに、右にバブルアップされています

1209
00:43:56,740 --> 00:43:59,650
小さい要素
左に湧き上がっています。

1210
00:43:59,650 --> 00:44:01,870
そして、ここでダウンして、私たちの場合
実際にはより密接に見て、

1211
00:44:01,870 --> 00:44:04,330
私たちは実際に数えることができます
比較とスワップの数

1212
00:44:04,330 --> 00:44:05,350
それが行われていました。

1213
00:44:05,350 --> 00:44:07,360
>> しかし、その代わりに、のは見てみましょう
第2のアルゴリズムで

1214
00:44:07,360 --> 00:44:11,240
私たちはして先を見て
ボランティア、選択ソート。

1215
00:44:11,240 --> 00:44:13,500
視覚的に、それは持っています
非常に異なる効果。

1216
00:44:13,500 --> 00:44:16,820
しかし、それはでは、再び、非常に直感的です
我々は次の最小を選択しておくこと

1217
00:44:16,820 --> 00:44:18,660
要素、私たちは少し幸運。

1218
00:44:18,660 --> 00:44:20,110
それは基本的に速く感じました。

1219
00:44:20,110 --> 00:44:22,840
しかし、我々は何度も何度もこれを実行した場合
そして再び入力の多くが付いて、

1220
00:44:22,840 --> 00:44:26,680
我々はそれが確かだと見ることが
まだn個の大きなOに乗。

1221
00:44:26,680 --> 00:44:29,920
>> それでは、最後のいずれかを実行してみましょう
ここでは、挿入ソート、

1222
00:44:29,920 --> 00:44:33,180
これは第3のアルゴリズムました
我々は見て、リコール

1223
00:44:33,180 --> 00:44:36,700
これは、扱っていること
要素それが彼らに遭遇すると、

1224
00:44:36,700 --> 00:44:39,290
しかし、それは多分にシフト
物事の上に部屋を作るために、

1225
00:44:39,290 --> 00:44:41,660
彼らが属している要素を挿入します。

1226
00:44:41,660 --> 00:44:45,330
>> そして、これはあまりにも与えてしまいます
最終的な結果。今、それらのすべての3つの

1227
00:44:45,330 --> 00:44:46,490
かなり速いと感じました。

1228
00:44:46,490 --> 00:44:48,740
そして実際、私はそれらを実行しました
かなり良いクリップで。

1229
00:44:48,740 --> 00:44:52,510
しかし、基本的に、彼らはすべてしています
正直に言うと、かなり恐ろしいです。

1230
00:44:52,510 --> 00:44:56,960
これらのアルゴリズムのすべてのこれまで
N乗のビッグOでその実行

1231
00:44:56,960 --> 00:44:59,270
かなりのを取ります
最終的に実行するための時間。

1232
00:44:59,270 --> 00:45:01,920
>> そして実際、我々が見ることができます
最後にこれを感じます

1233
00:45:01,920 --> 00:45:04,090
私はこの3番目と最後のデモを引き上げます。

1234
00:45:04,090 --> 00:45:05,840
これは、別のあります
起こっているの可視化

1235
00:45:05,840 --> 00:45:08,500
左側のバブルソートを表示するには、
途中で選択ソート、

1236
00:45:08,500 --> 00:45:13,410
私たちの一つとして何か、
手が先に提案した発生させ、

1237
00:45:13,410 --> 00:45:15,020
右側の並べ替えをマージします。

1238
00:45:15,020 --> 00:45:16,937
分断攻略
右の戦略。

1239
00:45:16,937 --> 00:45:19,520
そして、それは私たちがしているもの、実際には、です
水曜日に見に行きます。

1240
00:45:19,520 --> 00:45:21,990
しかし、の並列で実行するために、これらの時間をしましょう​​。

1241
00:45:21,990 --> 00:45:26,765
それは大体同じ数です
要素は、全てが同時に実行されています。

1242
00:45:26,765 --> 00:45:30,940

1243
00:45:30,940 --> 00:45:34,440
選択対バブルソート
マージソート対ソート。

1244
00:45:34,440 --> 00:45:36,760
>> 今、彼らはすべて実行しています
同時に理論インチ

1245
00:45:36,760 --> 00:45:39,830
CPUがで実行されています
同じ速度が、あなた

1246
00:45:39,830 --> 00:45:44,014
これがどのように退屈を感じることができます
非常に迅速になろうと、

1247
00:45:44,014 --> 00:45:45,930
そしてどれだけ速くするとき
私たちは週のビットを注入

1248
00:45:45,930 --> 00:45:49,330
ゼロのアルゴリズムすることができます
我々は物事をスピードアップします。

1249
00:45:49,330 --> 00:45:51,760
>> そして今のは、比較してみましょう
最後の形でこれらの。

1250
00:45:51,760 --> 00:45:55,710
私は先に行くつもりです
CS50のウェブサイトへ

1251
00:45:55,710 --> 00:45:59,020
我々は、今日のために、この最終的なリンクを持っています
ここで、インターネット上の誰か

1252
00:45:59,020 --> 00:46:03,960
親切にすることを一緒にビデオを置きます
何異なるソートをキャプチャ

1253
00:46:03,960 --> 00:46:07,510
アルゴリズムは次のように聞こえます。

1254
00:46:07,510 --> 00:46:09,577
これは、挿入ソートです。

1255
00:46:09,577 --> 00:46:12,072
>> [ビープ音]

1256
00:46:12,072 --> 00:46:13,070

1257
00:46:13,070 --> 00:46:16,850
>> これによりあなたは周波数を適用しています
バーバーの高さに基づいて。

1258
00:46:16,850 --> 00:46:19,826
これは、バブルソートです。

1259
00:46:19,826 --> 00:46:21,822
>> 【反っビープ音]

1260
00:46:21,822 --> 00:46:33,299

1261
00:46:33,299 --> 00:46:45,774
>> 今後is--次回来ます
次is--選択ソートアップ、

1262
00:46:45,774 --> 00:46:48,820
再び、我々はどこを選択しています
次の最小要素、

1263
00:46:48,820 --> 00:46:51,820
そして我々はそれが成長して見ることができます
左から右へ。

1264
00:46:51,820 --> 00:47:01,120

1265
00:47:01,120 --> 00:47:04,000
>> 今日これまでの並べ替え、私たちの勝者をマージします。

1266
00:47:04,000 --> 00:47:09,659

1267
00:47:09,659 --> 00:47:12,450
それは物事を分割していますに注意してください
[聞こえない]の半分と4分の1に。

1268
00:47:12,450 --> 00:47:17,510

1269
00:47:17,510 --> 00:47:21,660
私たちが持っていないノームソート、
話しました、そして視覚的に作成し、

1270
00:47:21,660 --> 00:47:24,450
とのビットをaudally
異なる形状と音。

1271
00:47:24,450 --> 00:47:27,060

1272
00:47:27,060 --> 00:47:30,160
前後に行きます、
物事をクリーンアップ。

1273
00:47:30,160 --> 00:47:32,230
また、ヒープソートをチェック
この男のウェブサイトで。

1274
00:47:32,230 --> 00:47:36,100

1275
00:47:36,100 --> 00:47:36,810
>> そして、それはそれです。

1276
00:47:36,810 --> 00:47:38,210
私たちはあなたの次の時間が表示されます。

1277
00:47:38,210 --> 00:47:42,647

1278
00:47:42,647 --> 00:47:48,334
>> 【WHOOSHINGと音楽]

1279
00:47:48,334 --> 00:50:24,839