1
00:00:00,000 --> 00:00:00,488

2
00:00:00,488 --> 00:00:10,800
>> [音楽再生]

3
00:00:10,800 --> 00:00:13,500
DAVIDマラン：すべての権利。

4
00:00:13,500 --> 00:00:14,670
すべての権利は​​、戻って歓迎します。

5
00:00:14,670 --> 00:00:18,120
だから、これは第4週、始まりです
その、すでに。

6
00:00:18,120 --> 00:00:21,320
そして、あなたはその先週思い出して、我々は置く
ほんの少しのために取ってコーディングする

7
00:00:21,320 --> 00:00:24,240
そして我々はもう少し話し始め
のようなことについて、ハイレベル

8
00:00:24,240 --> 00:00:28,130
いるものの、検索とソート
ややシンプルなアイデアは、されている

9
00:00:28,130 --> 00:00:31,840
問題のクラスの代表
あなたは、特に解決するために開始されます

10
00:00:31,840 --> 00:00:34,820
あなたは、最終的なことを考え始めると
プロジェクトや興味深いソリューションあなた

11
00:00:34,820 --> 00:00:36,760
現実世界の問題を持っているかもしれません。

12
00:00:36,760 --> 00:00:39,490
今、バブルソートは、最も単純なの一つであった
そのようなアルゴリズム、およびそれ

13
00:00:39,490 --> 00:00:42,900
これらの小数値を有することによって働い
リストまたは配列の種類の中で

14
00:00:42,900 --> 00:00:46,530
までトップにバブル自分の道を、と
大きな数字は、への道を下に移動

15
00:00:46,530 --> 00:00:47,930
そのリストの最後。

16
00:00:47,930 --> 00:00:50,650
>> そして、我々は視覚化できることを思い出す
バブルソート少し

17
00:00:50,650 --> 00:00:52,310
このような何か。

18
00:00:52,310 --> 00:00:53,640
だから私は先に行くと、[開始]をクリックしてみましょう。

19
00:00:53,640 --> 00:00:55,350
私はバブルソートを事前に選択しました。

20
00:00:55,350 --> 00:00:58,920
そして、あなたはその背青を思い出す場合
ラインは小さな、大きな数字を表す

21
00:00:58,920 --> 00:01:03,300
青い線は次のように、小さな数値を表す
我々は何度も何度もこれを通過し、

22
00:01:03,300 --> 00:01:07,680
再び、それぞれの次の二つのバーを比較する
赤の他の、我々は交換するつもりだ

23
00:01:07,680 --> 00:01:11,010
最大と最小の場合
彼らは、順不同である。

24
00:01:11,010 --> 00:01:14,150
>> だから、これは上に行くと上に行くと行く
で、あなたはそれが大きく表示されます

25
00:01:14,150 --> 00:01:16,700
要素は、への道を作っている
右に、そしてより小さい要素は

26
00:01:16,700 --> 00:01:17,900
左への道を作ること。

27
00:01:17,900 --> 00:01:21,380
しかし、我々は定量化し始めた
効率、

28
00:01:21,380 --> 00:01:22,970
このアルゴリズムの品質。

29
00:01:22,970 --> 00:01:25,200
そして、私たちによると、最悪で
場合、このアルゴリズムはかかった

30
00:01:25,200 --> 00:01:27,940
大体どのように多くの手順は？

31
00:01:27,940 --> 00:01:28,980
>> だからnの二乗。

32
00:01:28,980 --> 00:01:30,402
そしてnは何でしたか？

33
00:01:30,402 --> 00:01:31,650
>> 読者：要素の数。

34
00:01:31,650 --> 00:01:32,790
>> DAVIDマラン：だからnがあった
要素の数。

35
00:01:32,790 --> 00:01:33,730
そして私たちはしばしばこれをやる。

36
00:01:33,730 --> 00:01:36,650
我々は大きさについて話をしたい任意の時間
問題やサイズの

37
00:01:36,650 --> 00:01:39,140
入力、またはそれにかかる時間
出力を生成するために、私達はちょうどよ

38
00:01:39,140 --> 00:01:41,610
一般的などんな
入力は、nのようになります。

39
00:01:41,610 --> 00:01:45,970
だから戻って週0で、その数はページ
電話帳にnがあった。

40
00:01:45,970 --> 00:01:47,550
学生数
部屋にnがあった。

41
00:01:47,550 --> 00:01:49,630
だからここに、あまりにも、私たちは、フォローしている
そのパターン。

42
00:01:49,630 --> 00:01:52,800
>> さてN乗特にない
速いので、私たちはより良い実行しようとしました。

43
00:01:52,800 --> 00:01:55,970
そして、我々はいくつ見
他のアルゴリズムのうち、

44
00:01:55,970 --> 00:01:57,690
選択ソートであった。

45
00:01:57,690 --> 00:01:59,180
だから選択ソートだった
少し異なる。

46
00:01:59,180 --> 00:02:03,130
それはほとんど単純でしたが、私はあえて言う、
それによって、私は開始時に開始

47
00:02:03,130 --> 00:02:06,740
私たちのボランティアのリストと、私はちょうど再び
と何度も何度も経て

48
00:02:06,740 --> 00:02:10,060
リスト、最小を摘採
当時の要素と、彼を入れたり、

49
00:02:10,060 --> 00:02:13,040
彼女のリストの先頭に。

50
00:02:13,040 --> 00:02:16,410
>> しかし、これは、あまりにも、かつて我々は考え始め
数学を通して、より大きな

51
00:02:16,410 --> 00:02:19,860
絵は、何回考えた
私が行ったり来たりと戻っていた

52
00:02:19,860 --> 00:02:24,090
行ったり来たり、我々は最悪の場合で述べている、
選択ソートは、あまりにも、何でしたか？

53
00:02:24,090 --> 00:02:24,960
nの2乗。

54
00:02:24,960 --> 00:02:27,490
今、現実の世界では、それは可能性がある
実際にはわずかに速くなる。

55
00:02:27,490 --> 00:02:30,620
再びので、私は維持する必要がありませんでした
私が並べ替えられていた後にバックトラック

56
00:02:30,620 --> 00:02:31,880
最小要素。

57
00:02:31,880 --> 00:02:35,090
しかし、我々は非常に大きなnを考えてみれば、と
あなたは、ソートの数学などを行う場合

58
00:02:35,090 --> 00:02:39,170
私はnの二乗で、ボード上でやった
マイナス何か、他のすべて

59
00:02:39,170 --> 00:02:41,850
nの二乗、一度N以外
本当に大きくなる、しません

60
00:02:41,850 --> 00:02:42,850
本当に同じくらい重要では。

61
00:02:42,850 --> 00:02:45,470
だから、コンピュータ科学者として、私たちは、一種の
小さい方に目をつぶる

62
00:02:45,470 --> 00:02:49,220
要因や唯一の要因に焦点を当てに
作るために起こっている表現

63
00:02:49,220 --> 00:02:50,330
最大の違い。

64
00:02:50,330 --> 00:02:52,840
>> さて、最後に、私たちは見て
挿入ソートで。

65
00:02:52,840 --> 00:02:56,620
そして、これは、精神で同様であったが、
反復して通過するのではなくと

66
00:02:56,620 --> 00:03:01,250
で最小の要素のいずれかを選択する
時間は、私の代わりに手を取っている私

67
00:03:01,250 --> 00:03:04,070
すべては、配られ、私が決定しました
右側には、ここに属し。

68
00:03:04,070 --> 00:03:06,160
それから私は、次の要素に移っ
と決めた彼または

69
00:03:06,160 --> 00:03:07,470
彼女はここに属していた。

70
00:03:07,470 --> 00:03:08,810
そして、私は延々と移動しました。

71
00:03:08,810 --> 00:03:11,780
そして、私は、道に沿って、にかもしれない
するためにこれらの人をシフト

72
00:03:11,780 --> 00:03:13,030
彼らのために場所を空ける。

73
00:03:13,030 --> 00:03:16,880
だから精神的な逆転のようなものだった
選択ソートのものたち

74
00:03:16,880 --> 00:03:18,630
挿入ソートと呼ばれる。

75
00:03:18,630 --> 00:03:20,810
>> これらのトピックが発生するので、
現実の世界である。

76
00:03:20,810 --> 00:03:23,640
ほんの数年前、時一定の
上院議員は大統領のために実行されていた、

77
00:03:23,640 --> 00:03:27,160
エリック·シュミット、当時の最高経営責任者（CEO）
Googleは、実際に機会がありました

78
00:03:27,160 --> 00:03:28,040
彼にインタビューする。

79
00:03:28,040 --> 00:03:32,010
そして、我々は、このYouTubeのを共有しようと思いました
我々がターンアップができれば、ここであなたをクリップ

80
00:03:32,010 --> 00:03:32,950
ボリューム。

81
00:03:32,950 --> 00:03:39,360
>> [ビデオの再生]

82
00:03:39,360 --> 00:03:44,620
>>  - 現在、上院議員、あなたがGoogleでここにいる、
と私は大統領を考えるのが好き

83
00:03:44,620 --> 00:03:46,042
就職の面接のように。

84
00:03:46,042 --> 00:03:47,770
>> [笑い]

85
00:03:47,770 --> 00:03:50,800
>>  - 今、それを得るのは難しい
社長としての仕事。

86
00:03:50,800 --> 00:03:52,480
そして、あなたが通過している
今厳しさ。

87
00:03:52,480 --> 00:03:54,330
それはGoogleの仕事を得ることも難しい。

88
00:03:54,330 --> 00:03:59,610
我々が質問を持っていると我々は尋ねる
我々の候補者の質問。

89
00:03:59,610 --> 00:04:02,250
、この1つはラリーシュワイマーからのものである。

90
00:04:02,250 --> 00:04:05,325
>> [笑い]

91
00:04:05,325 --> 00:04:06,400
 - 君たちは、私は冗談だと思う？

92
00:04:06,400 --> 00:04:08,750
それはここです。

93
00:04:08,750 --> 00:04:12,110
への最も効率的な方法は何ですか
二百万ビットの整数を並べ替える？

94
00:04:12,110 --> 00:04:15,810
>> [笑い]

95
00:04:15,810 --> 00:04:18,260
>> まあ、ええと - 

96
00:04:18,260 --> 00:04:19,029
>> は - 私は申し訳ありません。

97
00:04:19,029 --> 00:04:19,745
多分、我々はすべき - 

98
00:04:19,745 --> 00:04:21,000
>>  - いや、いや、いや、いや、いや。

99
00:04:21,000 --> 00:04:21,470
>>  - それはない - 

100
00:04:21,470 --> 00:04:22,185
OK。

101
00:04:22,185 --> 00:04:25,328
>> -Iは、バブルソートと思う
移動するための間違った方法である。

102
00:04:25,328 --> 00:04:26,792
>> [笑い]

103
00:04:26,792 --> 00:04:28,510
>> [応援と拍手]

104
00:04:28,510 --> 00:04:31,211
>> 彼にこれを言った人、オン観賞したい？

105
00:04:31,211 --> 00:04:32,155
OK。

106
00:04:32,155 --> 00:04:33,350
>> [ENDビデオ再生]

107
00:04:33,350 --> 00:04:35,070
>> DAVIDマラン：だからそこにあなたがそれを持っている。

108
00:04:35,070 --> 00:04:39,600
だから私たちは、これらの実行を定量化するために始めました
何か回、いわば、

109
00:04:39,600 --> 00:04:43,480
ある漸近記法と呼ばれる
ただ回す当社ソートを参照

110
00:04:43,480 --> 00:04:47,420
それらの小さい要因に見て見ぬふりと
のみ実行時間を見て、

111
00:04:47,420 --> 00:04:51,250
これらのアルゴリズムの性能は、
nは時間をかけて本当に大きくなるとして。

112
00:04:51,250 --> 00:04:55,110
そして我々は大きなO.そしてビッグOを導入しました
我々は思っていた何かを表現

113
00:04:55,110 --> 00:04:57,000
上限としての。

114
00:04:57,000 --> 00:04:59,570
そして実際に、バリー、我々は下げることができます
マイク少しも？

115
00:04:59,570 --> 00:05:01,040
>> 私たちは、これが上限であると考える。

116
00:05:01,040 --> 00:05:04,710
nの二乗の手段だからビッグOでその
最悪の場合、のような何か

117
00:05:04,710 --> 00:05:07,780
選択ソートはかかるだろう
nの二乗のステップ。

118
00:05:07,780 --> 00:05:10,310
挿入ソートのような、または何か
nの二乗のステップでしょう。

119
00:05:10,310 --> 00:05:15,150
今すぐ挿入のような何かのため
ソート、最悪の場合何でしたか？

120
00:05:15,150 --> 00:05:18,200
配列を指定して、何が最悪だ
あなたが見つけるかもしれないという可能性シナリオ

121
00:05:18,200 --> 00:05:20,650
自分に直面？

122
00:05:20,650 --> 00:05:21,860
>> それは右、完全に後方のですか？

123
00:05:21,860 --> 00:05:24,530
それは完全に後ろ向きだ場合なので、
あなたは、仕事の全体の多くを行う必要があります。

124
00:05:24,530 --> 00:05:26,420
なぜなら、あなたは完全に後方なら、
あなたを見つけるつもりだ

125
00:05:26,420 --> 00:05:28,840
ここでの最大の要素は、たとえ
それはそこに属しています。

126
00:05:28,840 --> 00:05:31,140
だからでは、と言って、すべての権利をつもりだ
時間のこの瞬間、あなたがここに属している、

127
00:05:31,140 --> 00:05:32,310
ので、あなたは一人でそれを残す。

128
00:05:32,310 --> 00:05:35,425
>> その後は、ああ、実現いまいましい、私がしなければならない
このわずかに小さい要素に移動

129
00:05:35,425 --> 00:05:36,470
あなたの左。

130
00:05:36,470 --> 00:05:38,770
その後、私は再びそれをしなければならない
と何度も何度も。

131
00:05:38,770 --> 00:05:41,410
そして、私は前後に歩いている場合、あなた
パフォーマンスの感じのようなものであろう

132
00:05:41,410 --> 00:05:45,540
常に私がいるので、そのアルゴリズム、
でダウンして皆をシャッフル

133
00:05:45,540 --> 00:05:46,510
それのための部屋を作るために配列。

134
00:05:46,510 --> 00:05:47,750
だから最悪のケースだ。

135
00:05:47,750 --> 00:05:48,570
>> 対照的に - 

136
00:05:48,570 --> 00:05:50,320
これは前回接戦だった - 

137
00:05:50,320 --> 00:05:54,065
我々は言っている挿入ソート
何のオメガでしたか？

138
00:05:54,065 --> 00:05:57,530
最高のケースは何を実行している
挿入ソートの時間？

139
00:05:57,530 --> 00:05:58,520
だから、実際にnのだ。

140
00:05:58,520 --> 00:06:00,980
それは我々が残した空白になっていました
ボード上の最後の時間。

141
00:06:00,980 --> 00:06:03,160
>> そしてそれは、nのオメガ理由からだ？

142
00:06:03,160 --> 00:06:06,630
まあ、非常に最良の場合には、何
挿入ソートは手渡しするつもり？

143
00:06:06,630 --> 00:06:09,830
完全に並べ替えられているまあ、リスト
行うためにすでに、最低限の仕事。

144
00:06:09,830 --> 00:06:12,460
しかし、挿入ソートについてきちんとしたものだ
それはここから始まるとためです

145
00:06:12,460 --> 00:06:15,340
決定し、ああ、あなたは数である
1、あなたはここに属しています。

146
00:06:15,340 --> 00:06:16,970
ああ、何が幸運。

147
00:06:16,970 --> 00:06:17,740
>> あなたはナンバー2だ。

148
00:06:17,740 --> 00:06:19,030
また、ここに属しています。

149
00:06:19,030 --> 00:06:21,010
さらに良い3番、
あなたがここに属しています。

150
00:06:21,010 --> 00:06:25,210
できるだけ早くそれが年末になるにつれて
リスト当たりの挿入ソートの擬似コード

151
00:06:25,210 --> 00:06:28,010
私たちは、口頭を歩いている
最後の時間は、それが行われている。

152
00:06:28,010 --> 00:06:32,790
しかし、選択ソート、対照的に、
何をして保管？

153
00:06:32,790 --> 00:06:35,260
>> リストを通過保持
もう一度、もう一度、もう一度。

154
00:06:35,260 --> 00:06:39,160
キー洞察力だけがあったので
一度にすべての方法を見てきました

155
00:06:39,160 --> 00:06:42,500
リストの最後には、特定することができます
選択した要素があったことを

156
00:06:42,500 --> 00:06:45,560
確かに現在は最小要素。

157
00:06:45,560 --> 00:06:48,920
最後は、これらの異なったメンタルモデルはそう
いくつかの非常に現実世界をもたらすまで

158
00:06:48,920 --> 00:06:53,130
私たちにとっての違いだけでなく、これらの
理論上の漸近的な違い。

159
00:06:53,130 --> 00:06:56,910
>> だから、nのビッグO、その後、おさらいする
乗、我々はいくつかのように見てきました

160
00:06:56,910 --> 00:06:58,350
これまでのアルゴリズム。

161
00:06:58,350 --> 00:06:59,580
n個のビッグO？

162
00:06:59,580 --> 00:07:02,870
可能性アルゴリズムは何ですか
nは大きなOであると言うこと？

163
00:07:02,870 --> 00:07:06,930
最悪の場合には、かかる
ステップの線形数。

164
00:07:06,930 --> 00:07:07,810
>> OK、線形探索。

165
00:07:07,810 --> 00:07:10,470
最悪の場合には、どこにあるの
あなたは時を探している要素

166
00:07:10,470 --> 00:07:12,950
線形探索を適用する？

167
00:07:12,950 --> 00:07:14,680
>> OK、最悪の場合には、
それもありません。

168
00:07:14,680 --> 00:07:17,000
又は第最悪の場合には、周辺
です最後にすべての方法、

169
00:07:17,000 --> 00:07:18,880
プラスまたはマイナスワンステップ差。

170
00:07:18,880 --> 00:07:21,180
だから一日の終わりに、
我々はそれが線形だと言うことができます。

171
00:07:21,180 --> 00:07:23,910
n個のビッグOは、線形探索だろう
最悪のケースであるため、

172
00:07:23,910 --> 00:07:26,610
要素があってもそこにはありませんか、それはだ
最後にすべての方法。

173
00:07:26,610 --> 00:07:29,370
>> さて、n個のログの大O。

174
00:07:29,370 --> 00:07:32,760
我々は、約非常に詳細に話をしなかった
これが、我々は前にこれを見てきました。

175
00:07:32,760 --> 00:07:36,840
何がいわゆる対数で実行
時間、最悪の場合には？

176
00:07:36,840 --> 00:07:38,500
>> うん、そうバイナリ検索。

177
00:07:38,500 --> 00:07:42,930
最悪の場合には、バイナリ検索
どこかの要素があるかもしれない

178
00:07:42,930 --> 00:07:45,640
途中、どこか
配列の内部。

179
00:07:45,640 --> 00:07:48,040
しかし、あなただけに一度それを見つける
で、半分にリストを分割

180
00:07:48,040 --> 00:07:48,940
半分に半分、半分に、。

181
00:07:48,940 --> 00:07:50,200
そして出来上がり、それはそこだ。

182
00:07:50,200 --> 00:07:52,500
または再び、最悪の場合、
それもありません。

183
00:07:52,500 --> 00:07:56,770
しかし、あなたはそれがないということを知らない
あなたは、ソートのその最後に到達するまで

184
00:07:56,770 --> 00:08:00,470
半減によってボトムほとんどの要素
と半減と半減。

185
00:08:00,470 --> 00:08:01,400
>> 1のビッグO。

186
00:08:01,400 --> 00:08:03,540
だから私たちは3の2、ビッグOのビッグO可能性。

187
00:08:03,540 --> 00:08:06,260
あなただけの一定数をいつでも、
私達はちょうどだけ簡素化する一種の

188
00:08:06,260 --> 00:08:07,280
その1の大Oとして。

189
00:08:07,280 --> 00:08:10,440
でも、現実的に、それがかかる場合でも
それはしても2または100ステップ、

190
00:08:10,440 --> 00:08:13,680
ステップ一定数、
私達はちょうど1のビッグO言う。

191
00:08:13,680 --> 00:08:15,930
のアルゴリズムは何ですか
1のビッグOで？

192
00:08:15,930 --> 00:08:18,350
>> 読者：長さを見つける
変数の。

193
00:08:18,350 --> 00:08:21,090
>> DAVIDマラン：検索
変数の長さ？

194
00:08:21,090 --> 00:08:23,870
>> 聴衆：いいえ、長さ
それがすでにソートましょう。

195
00:08:23,870 --> 00:08:24,160
>> DAVIDマラン：良い。

196
00:08:24,160 --> 00:08:27,850
[OK]を、ので、何かの長さを見つける
その何かの長さがあれば、のような

197
00:08:27,850 --> 00:08:30,020
アレイは、いくつかの変数に格納されている。

198
00:08:30,020 --> 00:08:33,380
あなただけの変数を読むことができますので、
または変数を印刷したり、

199
00:08:33,380 --> 00:08:34,960
ただ、一般的にその変数にアクセスします。

200
00:08:34,960 --> 00:08:37,299
と出来上がり、それは一定の時間がかかります。

201
00:08:37,299 --> 00:08:38,909
>> これとは対照的に、スクラッチに戻って考える。

202
00:08:38,909 --> 00:08:42,460
Cの最初の週に戻って考える、
単にprintfの呼び出し、印刷

203
00:08:42,460 --> 00:08:46,240
画面上の何かが間違いなくある
時定数は、それだけかかるため

204
00:08:46,240 --> 00:08:50,880
表示するCPUサイクルのいくつかの数
画面上でそのテキスト。

205
00:08:50,880 --> 00:08:52,720
それとも待つ - それをしない？

206
00:08:52,720 --> 00:08:56,430
他にどのように我々は、モデルかもしれません
printf関数のパフォーマンス？

207
00:08:56,430 --> 00:09:00,420
誰かが、反対したい
多分それは本当に時定数ではないのですか？

208
00:09:00,420 --> 00:09:03,600
printfを実行しているかもしれませんどのような意味で
実際に上の文字列を印刷する時、

209
00:09:03,600 --> 00:09:05,580
画面には、何かで
定数以外。

210
00:09:05,580 --> 00:09:07,860
>> 読者：[聞こえない]。

211
00:09:07,860 --> 00:09:08,230
>> DAVIDマラン：うん。

212
00:09:08,230 --> 00:09:09,300
だから、それは私たちの視点に依存します。

213
00:09:09,300 --> 00:09:13,390
私たちは実際に入力を考える場合
文字列であるとしてprintf関数、および

214
00:09:13,390 --> 00:09:16,380
従って私達はそれの大きさを測定
その長さによって入力 - それでは、と呼ぶことにしましょう

215
00:09:16,380 --> 00:09:17,780
それだけでなく、長さn  - 

216
00:09:17,780 --> 00:09:21,990
間違いなく、printf関数自体は、nのビッグOです
それはあなたnステップを取るために起こっているので、

217
00:09:21,990 --> 00:09:24,750
これらn個のそれぞれをプリントアウトする
最も可能性の高い文字は、。

218
00:09:24,750 --> 00:09:27,730
少なくとも我々は想定している範囲で
多分それはforループを使っていることを

219
00:09:27,730 --> 00:09:28,560
ボンネットの下に。

220
00:09:28,560 --> 00:09:30,860
>> しかし、我々はそれを見なければならないでしょう
それをよりよく理解するためのコード。

221
00:09:30,860 --> 00:09:33,650
そして実際、一度皆さんが開始
あなたは、あなた自身のアルゴリズムを解析します

222
00:09:33,650 --> 00:09:34,900
文字通りまさにそれ。

223
00:09:34,900 --> 00:09:37,765
眼球のソートコードと考える
について - すべての権利、私はこのループを持っている

224
00:09:37,765 --> 00:09:41,870
ここか私はここでネストされたループを持っている、
n個のものをn回、行うために起こっていること

225
00:09:41,870 --> 00:09:46,050
そして、あなたは理由のあなたの方法を並べ替えることができます
コー​​ドを、たとえそれがだ

226
00:09:46,050 --> 00:09:47,980
擬似コードではなく、実際のコード。

227
00:09:47,980 --> 00:09:49,730
>> だから乗、nのオメガはどうですか？

228
00:09:49,730 --> 00:09:53,582
アルゴリズムとは何だった最高に
ケース、まだ取っN乗のステップ？

229
00:09:53,582 --> 00:09:54,014
うん？

230
00:09:54,014 --> 00:09:54,880
>> 読者：[聞こえない]。

231
00:09:54,880 --> 00:09:55,900
>> DAVIDマラン：だから選択ソート。

232
00:09:55,900 --> 00:09:59,150
その問題に実際に減少しているため
再び、私は知らないという事実に

233
00:09:59,150 --> 00:10:02,600
私まで、現在の最小を見つけた
私はすべてのくそ要素をチェックしました。

234
00:10:02,600 --> 00:10:08,050
nは、言う、のオメガだから、我々
一つ思い付いた。

235
00:10:08,050 --> 00:10:09,300
挿入ソート。

236
00:10:09,300 --> 00:10:12,370
リストがソートされるような場合
すでに、最良のケースで我々だけで持っている

237
00:10:12,370 --> 00:10:15,090
それを介して1パスを作るために、
その時点で我々は確信している。

238
00:10:15,090 --> 00:10:17,890
次いで言えること
確かに、線形である。

239
00:10:17,890 --> 00:10:20,570
>> 1のオメガはどうですか？

240
00:10:20,570 --> 00:10:23,790
最良の場合には、かかるかもしれないもの、
ステップ一定数？

241
00:10:23,790 --> 00:10:27,220
だからリニアサーチは、あなただけの幸運を得る場合
あなたが探している要素

242
00:10:27,220 --> 00:10:31,000
、リストの先頭にある右
あなたを始めているところです場合

243
00:10:31,000 --> 00:10:33,070
そのリストの線形トラバーサル。

244
00:10:33,070 --> 00:10:35,180
>> そして、これは真である
ものの数。

245
00:10:35,180 --> 00:10:37,660
例えば、偶数バイナリ
検索は1のオメガです。

246
00:10:37,660 --> 00:10:40,310
あなたは本当にくそ何を得ればので
の途中で幸運とピシャリ-DAB

247
00:10:40,310 --> 00:10:42,950
あなたの配列は数値です
あなたが探している？

248
00:10:42,950 --> 00:10:45,730
だから、あなたにも、そこに幸運を得ることができます。

249
00:10:45,730 --> 00:10:49,190
>> このいずれか、最後に、n個のログのnのオメガ。

250
00:10:49,190 --> 00:10:52,573
だからnのログN、私たちは本当にしませんでした
まだの話、しかし - 

251
00:10:52,573 --> 00:10:53,300
>> 読者：ソートマージ？

252
00:10:53,300 --> 00:10:53,960
>> DAVIDマラン：マージソート。

253
00:10:53,960 --> 00:10:56,920
つまり、前回の接戦だった
どこで我々が​​提案し、我々が示した

254
00:10:56,920 --> 00:10:58,600
視覚的に、アルゴリズムが存在することを。

255
00:10:58,600 --> 00:11:02,470
そして、ちょうどそのようなのようなものをマージ
根本的に高速であるアルゴリズム

256
00:11:02,470 --> 00:11:03,450
これらの他の人の一部より。

257
00:11:03,450 --> 00:11:07,800
実際には、だけでなく、短いマージ
最悪で最高のケースnのログN、

258
00:11:07,800 --> 00:11:09,460
ケースnのログN。

259
00:11:09,460 --> 00:11:14,540
そして、あなたは、この偶然の一致を持っているとき
オメガとビッグOは同じものであること？

260
00:11:14,540 --> 00:11:17,310
私たちは、実際に何としてそれを記述することができます
それはでも、シータと呼ばれる

261
00:11:17,310 --> 00:11:18,220
少し一般的。

262
00:11:18,220 --> 00:11:21,730
しかし、それは単に、2境界を意味します
この場合には、同じである。

263
00:11:21,730 --> 00:11:25,770
>> だからソートマージ、これは何を行います
本当に私たちのために煮詰める？

264
00:11:25,770 --> 00:11:27,000
まあ、動機を思い出す。

265
00:11:27,000 --> 00:11:30,340
私は別のアニメーションのことをプルアップしてみましょう
我々は、最後の時間を見ていませんでした。

266
00:11:30,340 --> 00:11:33,390
このいずれか、同じ考えですが、
それは少し大きいです。

267
00:11:33,390 --> 00:11:36,160
そして、私は先に行くと指摘するつもりだ
最初に - 私たちは上の挿入ソートを持って

268
00:11:36,160 --> 00:11:39,410
左上、その後、選択ソート、
バブルソート、他の種類のカップル - 

269
00:11:39,410 --> 00:11:42,670
シェルと迅速な - 私たちは話していないこと
約、およびヒープとソートマージ。

270
00:11:42,670 --> 00:11:47,090
>> だから、少なくとも上であなたの目を集中しようとする
その後、左と上のトップ3

271
00:11:47,090 --> 00:11:49,120
私がクリックしたときにソートをマージ
この緑の矢印。

272
00:11:49,120 --> 00:11:51,900
しかし、私はちょうどに、それらのすべては実行してみましょう
あなたの多様性の感覚を与える

273
00:11:51,900 --> 00:11:53,980
世界に存在するアルゴリズム。

274
00:11:53,980 --> 00:11:56,180
私はこの実行してみましょうするつもりです
ほんの数秒間。

275
00:11:56,180 --> 00:11:59,640
そして、あなたはあなたの目の焦点を合わせる場合 - ピック
ただのためのアルゴリズムは、それに焦点を当てる

276
00:11:59,640 --> 00:12:02,970
秒 - あなたが見ることから始めましょう
それが実装しているというパターン。

277
00:12:02,970 --> 00:12:04,530
>> マージソート、通知は、行われます。

278
00:12:04,530 --> 00:12:06,430
ヒープソート、クイックソート、シェル - 

279
00:12:06,430 --> 00:12:09,480
我々は3つを導入したので、それはそう
最悪のアルゴリズムが先週。

280
00:12:09,480 --> 00:12:12,960
しかし、それは私たちが今日ここにいることが良いことだ
の一つであるマージソート、見

281
00:12:12,960 --> 00:12:16,500
より簡単なものでも、見ることです
それはおそらくあなたの心を曲げるでしょうが

282
00:12:16,500 --> 00:12:17,490
少しだけ。

283
00:12:17,490 --> 00:12:21,130
ここでは見ることができますどれだけ
選択ソートは吸う。

284
00:12:21,130 --> 00:12:24,600
>> しかし、フリップ側では、それはだ
実装は本当に簡単。

285
00:12:24,600 --> 00:12:28,160
と多分の一つだPセット3、用
を実装することを選んだアルゴリズム

286
00:12:28,160 --> 00:12:28,960
標準版のために。

287
00:12:28,960 --> 00:12:30,970
完全に正しい、完全に罰金。

288
00:12:30,970 --> 00:12:35,210
>> しかし、再び、nが大きくなるように、もしあなた
より高速なアルゴリズムを実装する

289
00:12:35,210 --> 00:12:39,020
マージソートのように、オッズはで大きく、
大きな入力が、あなたのコードは、ある

290
00:12:39,020 --> 00:12:39,800
高速に実行するつもり。

291
00:12:39,800 --> 00:12:41,090
あなたのウェブサイトは、より良い仕事になるだろう。

292
00:12:41,090 --> 00:12:42,650
ユーザーは幸せになるだろうしている。

293
00:12:42,650 --> 00:12:45,280
そして、これらの効果があります
実際に与えることの

294
00:12:45,280 --> 00:12:47,350
私たちいくつかのより深い思考。

295
00:12:47,350 --> 00:12:49,990
>> それでは、マージ何を見てみましょう
ソートは、すべてについて実際にある。

296
00:12:49,990 --> 00:12:52,992
涼しい事はマージということです
ソートは、ちょうどこれです。

297
00:12:52,992 --> 00:12:56,300
これは、我々が呼ばれたものを、再び、です
擬似コード、擬似コードの存在

298
00:12:56,300 --> 00:12:57,720
英語のような構文。

299
00:12:57,720 --> 00:12:59,890
とシンプルです
魅惑的な一種の。

300
00:12:59,890 --> 00:13:02,840
>> だから、n個の要素の入力に - よう
ただ意味、ここでは、配列です。

301
00:13:02,840 --> 00:13:04,000
それは、その中にn個のものを持っている。

302
00:13:04,000 --> 00:13:05,370
それは我々がそこに言っているすべてです。

303
00:13:05,370 --> 00:13:07,560
>> nが2未満であると、戻り。

304
00:13:07,560 --> 00:13:08,640
だから、それはただ些細ケースだ。

305
00:13:08,640 --> 00:13:12,580
nが2未満の場合、明らかにそうではあり
ケースの事で1または0、

306
00:13:12,580 --> 00:13:14,780
すでにソートまたは存在している、
これだけを返す。

307
00:13:14,780 --> 00:13:15,900
行うには何もありません。

308
00:13:15,900 --> 00:13:18,360
だからオフに摘むための単純なケースだ。

309
00:13:18,360 --> 00:13:20,110
>> そうでなければ、我々は3つのステップがあります。

310
00:13:20,110 --> 00:13:23,650
要素の左半分、ソートをソート
要素の右半分、

311
00:13:23,650 --> 00:13:26,650
その後並べ半分をマージ。

312
00:13:26,650 --> 00:13:29,400
何がここで興味深いのは、つまり
私は右の、パントのようなものだ？

313
00:13:29,400 --> 00:13:32,300
円形の定義のようなものがあります
このアルゴリズムへ。

314
00:13:32,300 --> 00:13:35,986
どのような意味では、このアルゴリズムのです
定義円形？

315
00:13:35,986 --> 00:13:37,850
>> 読者：[聞こえない]。

316
00:13:37,850 --> 00:13:41,670
>> DAVIDマラン：ええ、私のソートアルゴリズム、
そのステップの二人は "ソートです

317
00:13:41,670 --> 00:13:44,640
頼むので何か。 "そして、
質問、まあ、何私が使用するつもりです

318
00:13:44,640 --> 00:13:46,460
左半分をソートする
右半分？

319
00:13:46,460 --> 00:13:49,600
そして、ここの美しさはであるにもかかわらず
再び、これはハラハラドキドキです

320
00:13:49,600 --> 00:13:54,030
部分は、潜在的には、同じ使用することができます
左半分をソートするアルゴリズム。

321
00:13:54,030 --> 00:13:54,700
>> しかし、ちょっと待って。

322
00:13:54,700 --> 00:13:57,070
あなたは、並べ替えるように言われているとき
左半分、二人は何ですか

323
00:13:57,070 --> 00:13:58,240
手順は次のことを行って？

324
00:13:58,240 --> 00:14:00,550
我々の左半分を並べます
左半分と右

325
00:14:00,550 --> 00:14:01,420
左半分の半分。

326
00:14:01,420 --> 00:14:04,430
くそー、どのように私はそれら二つを並べない
半分、または四半期、今？

327
00:14:04,430 --> 00:14:05,260
>> しかし、それはOKです。

328
00:14:05,260 --> 00:14:07,830
我々はここでソートアルゴリズムを持っている。

329
00:14:07,830 --> 00:14:10,660
そして、あなたはで心配かもしれませんが
最初、これは無限の一種である

330
00:14:10,660 --> 00:14:12,780
ループは、それはことはないサイクルだ
終わろうとして - それはに起こっている

331
00:14:12,780 --> 00:14:15,770
何が起こるかを一度終了？

332
00:14:15,770 --> 00:14:16,970
いったんnが2未満である。

333
00:14:16,970 --> 00:14:19,180
どの最終的に起こるために起こっている、
あなたが続ければ半減しているため

334
00:14:19,180 --> 00:14:23,020
確かに、これらの半分を半分に半減
最終的には終了するつもりだ

335
00:14:23,020 --> 00:14:25,350
アップするだけで、1または0の要素を持つ。

336
00:14:25,350 --> 00:14:28,500
その点、このアルゴリズムで
設定が完了したら言う。

337
00:14:28,500 --> 00:14:31,020
>> だから、これで本当の魔法
アルゴリズムは、内にあるように見え

338
00:14:31,020 --> 00:14:33,470
その最後のステップ、マージ。

339
00:14:33,470 --> 00:14:37,190
ちょうど2つをマージするというシンプルなアイデア
物事は、それが最終的に何が起こっているのだ

340
00:14:37,190 --> 00:14:40,920
私たちはの配列をソートできるようにするには、
8要素、言うてみましょう。

341
00:14:40,920 --> 00:14:44,410
だから私は、最大8つのより多くのストレスボールを持って
ここでは、8枚の紙、一

342
00:14:44,410 --> 00:14:45,500
グーグルガラス - 

343
00:14:45,500 --> 00:14:46,140
その私が手にする。

344
00:14:46,140 --> 00:14:46,960
>> [笑い]

345
00:14:46,960 --> 00:14:48,970
>> DAVIDマラン：私たちは、8を取ることができれば
ボランティア、と我々はできるかどうかを確認してみましょう

346
00:14:48,970 --> 00:14:51,430
そう、これを果たしている。

347
00:14:51,430 --> 00:14:52,500
うわー、OK。

348
00:14:52,500 --> 00:14:53,565
コンピュータサイエンスは、楽しみを得ています。

349
00:14:53,565 --> 00:14:54,320
わかりました。

350
00:14:54,320 --> 00:14:57,770
それでは、どのように約3、
そこに最大の手。

351
00:14:57,770 --> 00:14:58,580
後ろの4つ。

352
00:14:58,580 --> 00:15:02,220
そして、私たちはあなたをやる方法について
この行の3？

353
00:15:02,220 --> 00:15:03,390
前にと4。

354
00:15:03,390 --> 00:15:04,920
だから、8までに来る。

355
00:15:04,920 --> 00:15:12,060
>> [笑い]

356
00:15:12,060 --> 00:15:13,450
>> DAVIDマラン：私は実際によ
それが何であるかわからない。

357
00:15:13,450 --> 00:15:14,810
それはストレスボールはありますか？

358
00:15:14,810 --> 00:15:16,510
デスクランプ？

359
00:15:16,510 --> 00:15:18,650
材料？

360
00:15:18,650 --> 00:15:19,680
インターネット？

361
00:15:19,680 --> 00:15:20,160
>> OK。

362
00:15:20,160 --> 00:15:21,310
だから、最大で来る。

363
00:15:21,310 --> 00:15:22,310
誰がしたい - 

364
00:15:22,310 --> 00:15:23,570
来続ける。

365
00:15:23,570 --> 00:15:24,240
見てみましょう。

366
00:15:24,240 --> 00:15:26,460
そして、これは場所であなたを置く - 

367
00:15:26,460 --> 00:15:27,940
あなたは、場所1にいる。

368
00:15:27,940 --> 00:15:28,670
おっと、ちょっと待って。

369
00:15:28,670 --> 00:15:30,760
1、2、3、4、5、6、7  - 良い、ああ。

370
00:15:30,760 --> 00:15:31,310
すべての権利、私たちはいいです。

371
00:15:31,310 --> 00:15:35,130
すべての権利は​​、誰もが、席を持っている
しかし、Googleではなくガラスに。

372
00:15:35,130 --> 00:15:36,475
私キューこれら最大ましょう​​。

373
00:15:36,475 --> 00:15:37,115
あなたの名前は？

374
00:15:37,115 --> 00:15:37,440
>> MICHELLE：ミシェル。

375
00:15:37,440 --> 00:15:38,090
>> DAVIDマラン：ミシェル？

376
00:15:38,090 --> 00:15:42,000
すべての権利は​​、ように見えるようになる
オタク、OKだ場合。

377
00:15:42,000 --> 00:15:44,625
まあ、私もそう、私が思う、
ちょっと。

378
00:15:44,625 --> 00:15:45,875
スタンバイ、大丈夫。

379
00:15:45,875 --> 00:15:48,510

380
00:15:48,510 --> 00:15:50,950
私たちは、思い付くしようとしてきた
Googleのガラスのケースを使用しており、我々

381
00:15:50,950 --> 00:15:53,750
それだけでやるのは楽しいだろうと思った
この人々がステージにいるとき。

382
00:15:53,750 --> 00:15:57,120
我々は世界を記録します
彼らの視点から。

383
00:15:57,120 --> 00:15:58,410
わかりました。

384
00:15:58,410 --> 00:15:59,830
ではない、おそらくGoogleが意図したもの。

385
00:15:59,830 --> 00:16:02,260
あなたが気にしない場合は、すべての権利は​​、身に着けている
次厄介分間この、

386
00:16:02,260 --> 00:16:03,150
それは素晴らしいことでしょう。

387
00:16:03,150 --> 00:16:08,620
>> そうすべての権利、私たちはここでの配列を持っている
要素、およびその配列、当たりとして

388
00:16:08,620 --> 00:16:11,480
これらの人々に紙の破片 '
手が、現在並べ替えられています。

389
00:16:11,480 --> 00:16:12,050
>> MICHELLE：ああ、それはとても奇妙なことだ。

390
00:16:12,050 --> 00:16:12,810
>> DAVIDマラン：それはかなりランダムです。

391
00:16:12,810 --> 00:16:15,760
そして、ちょうどその瞬間に、私たちは試してみるつもりだ
実装するために一緒にマージソート

392
00:16:15,760 --> 00:16:17,950
そのキー洞察力がどこにあると参照してください。

393
00:16:17,950 --> 00:16:21,970
とマージソートとここにトリックがある
我々はまだ想定していないことを何か。

394
00:16:21,970 --> 00:16:24,030
私たちは、実際にいくつかを必要とする
追加スペース。

395
00:16:24,030 --> 00:16:26,650
だから何が特になるだろう
これについて興味深いのは、これらです。

396
00:16:26,650 --> 00:16:29,270
みんな少し動き回るつもりです
ちょっと、私はあることを仮定するつもりですので、

397
00:16:29,270 --> 00:16:31,880
スペースの余分な配列が、そこ
右それらの後ろ、言う。

398
00:16:31,880 --> 00:16:34,570
>> だから彼らは椅子の後ろなら、
それは二次的な配列です。

399
00:16:34,570 --> 00:16:36,960
彼らはここに座っているなら、それはだ
主要配列。

400
00:16:36,960 --> 00:16:40,170
しかし、これは我々が持っているリソースです
バブルでこれまで活用しない

401
00:16:40,170 --> 00:16:42,040
ソート、選択ソートと、
挿入ソートと。

402
00:16:42,040 --> 00:16:44,600
ちょうど先週思い出して、誰もが
の種類は場所にシャッフル。

403
00:16:44,600 --> 00:16:46,840
彼らは、任意の追加のメモリを使用しませんでした。

404
00:16:46,840 --> 00:16:49,310
我々はによって人々のための部屋を作った
周りの人を動かす。

405
00:16:49,310 --> 00:16:50,580
>> だから、これは、あまりにも重要な洞察である。

406
00:16:50,580 --> 00:16:53,410
このトレードオフは、一般に、そこ
資源のコンピュータサイエンス、。

407
00:16:53,410 --> 00:16:55,800
あなたが何かをスピードアップしたい場合は
時間のように、あなたはするつもりだ

408
00:16:55,800 --> 00:16:56,900
代金を支払わなければならない。

409
00:16:56,900 --> 00:17:00,750
そして、それらの価格の一つは、非常に頻繁にある
スペース、メモリの容量やハード

410
00:17:00,750 --> 00:17:01,700
あなたが使用しているディスクスペース。

411
00:17:01,700 --> 00:17:03,640
または、率直に言って、量
プログラマの時間。

412
00:17:03,640 --> 00:17:06,700
どのくらいそれが人間の、あなたにかかる時間、
実際にいくつかの詳細を実装する

413
00:17:06,700 --> 00:17:07,829
複雑なアルゴリズム。

414
00:17:07,829 --> 00:17:09,760
しかし、今日のために、トレードオフ
時間と空間です。

415
00:17:09,760 --> 00:17:11,930
>> だから、あなたたちは、ちょうどあなたを保持することができれば
ので、我々はあなたがしていることを数字を見ることができます

416
00:17:11,930 --> 00:17:15,839
確かに4,2、6、1、3、図7、図8に一致する。

417
00:17:15,839 --> 00:17:16,599
優秀。

418
00:17:16,599 --> 00:17:19,520
だから私は画策しようとするつもりだ
物事、君たちだけで可能であれば

419
00:17:19,520 --> 00:17:21,800
ここに私のリードに従ってください。

420
00:17:21,800 --> 00:17:26,650
>> だから私は、最初に、実装するつもりです
ある擬似コードの最初の一歩、

421
00:17:26,650 --> 00:17:29,440
nがある場合n個の要素の入力に
2未満、その後復帰。

422
00:17:29,440 --> 00:17:31,370
明らかに、それはしません
適用されるので、私たちは上を移動する。

423
00:17:31,370 --> 00:17:33,340
だから要素の左半分を並べ替える。

424
00:17:33,340 --> 00:17:36,220
だから私は私を集中するつもりだということを意味する
これらの上でちょっと注目

425
00:17:36,220 --> 00:17:37,310
ここに4人。

426
00:17:37,310 --> 00:17:39,774
すべての権利、私は次に何をしますか？

427
00:17:39,774 --> 00:17:40,570
>> 読者：左半分をソートします。

428
00:17:40,570 --> 00:17:42,780
>> DAVIDマラン：だから今、私はソートする必要が
これらの人の左半分。

429
00:17:42,780 --> 00:17:45,580
再びので、自分自身に仮定
目標は、左半分をソートすることです。

430
00:17:45,580 --> 00:17:46,440
どのようにそれを行うのですか？

431
00:17:46,440 --> 00:17:49,140
たださえ、指示に従ってください
我々は再びそれをやっているのに。

432
00:17:49,140 --> 00:17:50,160
だから左半分を並べ替える。

433
00:17:50,160 --> 00:17:52,030
今、私は、これらの2つの人を選別しています。

434
00:17:52,030 --> 00:17:53,563
次に何が来る？

435
00:17:53,563 --> 00:17:54,510
>> 読者：左半分をソートします。

436
00:17:54,510 --> 00:17:55,460
>> DAVIDマラン：並べ左半分。

437
00:17:55,460 --> 00:18:00,680
だから今は、これらの、ここでこの席、
大きさ1のリストです。

438
00:18:00,680 --> 00:18:01,365
そして、あなたの名前は何です再び？

439
00:18:01,365 --> 00:18:02,390
>> PRINCESS DAISY：プリンセスデイジー。

440
00:18:02,390 --> 00:18:03,690
>> DAVIDマラン：プリンセスデイジーはここにある。

441
00:18:03,690 --> 00:18:07,470
そして彼女はすでにいるので、ソートされている
リストはサイズ1である。

442
00:18:07,470 --> 00:18:09,490
私は次は何をしますか？

443
00:18:09,490 --> 00:18:13,680
そのリストがあるので、[OK]を、返す
2未満であるサイズ1。

444
00:18:13,680 --> 00:18:14,320
その後、次のステップは何ですか？

445
00:18:14,320 --> 00:18:17,490
そして今、あなたはどのようなする必要があります
あなたの心に後戻り。

446
00:18:17,490 --> 00:18:19,340
>> ある右半分を、ソート - 

447
00:18:19,340 --> 00:18:19,570
お名前は何ですか？

448
00:18:19,570 --> 00:18:20,220
>> LINDA：リンダ。

449
00:18:20,220 --> 00:18:20,980
>> DAVIDマラン：リンダ。

450
00:18:20,980 --> 00:18:23,210
そして我々は今、その何をしますか
我々は大きさ1のリストを持っている？

451
00:18:23,210 --> 00:18:24,440
>> AUDIENCE：リターン。

452
00:18:24,440 --> 00:18:24,760
>> DAVIDマラン：慎重。

453
00:18:24,760 --> 00:18:29,540
我々は最初に戻り、今では第三の
ステップ - と私は種類のことで、それを表現する場合

454
00:18:29,540 --> 00:18:33,490
私は今、現在、2つの座席を受け入れ
これら2つの要素をマージする必要があります。

455
00:18:33,490 --> 00:18:35,530
だから今は残念なことに、要素
順不同です。

456
00:18:35,530 --> 00:18:39,920
しかし、それはどこにマージ処理だ
説得力の取得を開始します。

457
00:18:39,920 --> 00:18:42,410
>> 君たちだけのために立ち上がることができるのであれば
瞬間、私はで、あなたを必要とするつもりだ

458
00:18:42,410 --> 00:18:44,170
瞬間、あなたの椅子の後ろに移行する。

459
00:18:44,170 --> 00:18:46,480
そして、もしリンダ、2であるため、
4よりも小さく、なぜしない

460
00:18:46,480 --> 00:18:48,130
あなたは、最初に集まってくる？

461
00:18:48,130 --> 00:18:48,690
そこに滞在。

462
00:18:48,690 --> 00:18:50,520
リンダだから、あなたは最初に集まってくる。

463
00:18:50,520 --> 00:18:53,820
>> 今、現実にはそれだけで、配列の場合
私達はちょうどリアルタイムで彼女を動かすことができ

464
00:18:53,820 --> 00:18:55,360
この椅子からこの場所へ。

465
00:18:55,360 --> 00:18:57,770
だから、いくつかの定数を取ったことを想像
ステップ1の数。

466
00:18:57,770 --> 00:18:58,480
そして今 - 

467
00:18:58,480 --> 00:19:01,490
しかし、我々にあなたを配置する必要があります
ここで最初の場所。

468
00:19:01,490 --> 00:19:03,930
>> そして今、あなたの周りに来ることがあれば、
同様に、我々はするつもりだ

469
00:19:03,930 --> 00:19:06,300
位置2にある。

470
00:19:06,300 --> 00:19:09,120
そして、それはこのような感じにもかかわらず
しばらく取って、今ある素敵なものだ

471
00:19:09,120 --> 00:19:14,710
のその左半分
左半分は現在、ソートされます。

472
00:19:14,710 --> 00:19:18,010
私たちは今、そうであれば次のステップは、何だった
物語の中で、さらに巻き戻し？

473
00:19:18,010 --> 00:19:18,980
>> 聴衆：右半分。

474
00:19:18,980 --> 00:19:19,900
>> DAVIDマラン：並べ右半分。

475
00:19:19,900 --> 00:19:21,320
だから、みんなにも、これを行う必要があります。

476
00:19:21,320 --> 00:19:23,510
だから、立ち上がることができれば、
ちょっと？

477
00:19:23,510 --> 00:19:25,192
そして、あなたの名前は何ですか？

478
00:19:25,192 --> 00:19:25,540
>> JESS：ジェス。

479
00:19:25,540 --> 00:19:25,870
>> DAVIDマラン：ジェス。

480
00:19:25,870 --> 00:19:29,720
[OK]を、ので、ジェスは今左です
右半分の半分。

481
00:19:29,720 --> 00:19:31,400
そして、彼女はサイズ1のリストだ。

482
00:19:31,400 --> 00:19:32,380
彼女は明らかに並べ替えられている。

483
00:19:32,380 --> 00:19:33,070
そして、あなたの名前を再び？

484
00:19:33,070 --> 00:19:33,630
>> MICHELLE：ミシェル。

485
00:19:33,630 --> 00:19:35,340
>> DAVIDマラン：ミシェルは明らかである
大きさ1のリスト。

486
00:19:35,340 --> 00:19:36,050
彼女はすでにソートだ。

487
00:19:36,050 --> 00:19:38,690
だから今魔法が、起こる
マージ処理。

488
00:19:38,690 --> 00:19:39,790
だから、誰が最初に来るようになるだろう？

489
00:19:39,790 --> 00:19:41,560
明らかミシェル。

490
00:19:41,560 --> 00:19:43,280
だから、あなたが戻って周りに来ることがあれば。

491
00:19:43,280 --> 00:19:47,090
我々は今、彼女のために用意してスペース
右ここにこの椅子の後ろにあります。

492
00:19:47,090 --> 00:19:51,580
そして今、あなたにも戻ってくることができれば、
我々は現在、2つ、明確にすること、持っている

493
00:19:51,580 --> 00:19:53,810
半分、サイズ2の各 - 

494
00:19:53,810 --> 00:19:57,090
とだけ描写の為に、もしあなた
スペースの少しを作ることができる - 

495
00:19:57,090 --> 00:19:59,780
1は、半分ここ残さ
ここでは右半分。

496
00:19:59,780 --> 00:20:01,160
>> 物語の中で、さらに巻き戻します。

497
00:20:01,160 --> 00:20:02,270
次は何ステップです？

498
00:20:02,270 --> 00:20:03,030
>> 読者：マージ。

499
00:20:03,030 --> 00:20:04,160
>> DAVIDマラン：だから今、私たちは、マージする必要があります。

500
00:20:04,160 --> 00:20:07,490
だからOK、今、ありがたいことに、私たちは
わずか4椅子を解放。

501
00:20:07,490 --> 00:20:11,480
だから我々は、多くのメモリを二回使っていますが、
我々は、間にフリップフロッピングを与えることができます

502
00:20:11,480 --> 00:20:12,330
二つの配列。

503
00:20:12,330 --> 00:20:14,190
どのように番号が最初に来ている？

504
00:20:14,190 --> 00:20:14,850
だから明らかに、ミシェル。

505
00:20:14,850 --> 00:20:16,680
だから周りに来て、取る
ここにあなたの席。

506
00:20:16,680 --> 00:20:19,120
そして2番は明らかである
次ので、あなたはここに来る。

507
00:20:19,120 --> 00:20:21,520
4番、6番。

508
00:20:21,520 --> 00:20:23,390
そして再び、そこにもかかわらず
関与歩行を少し、

509
00:20:23,390 --> 00:20:26,010
実際に、これらは、瞬時に発生する可能性
 - ひとつ移動させることにより

510
00:20:26,010 --> 00:20:26,880
[OK]を、よくやった。

511
00:20:26,880 --> 00:20:28,350
>> [笑い]

512
00:20:28,350 --> 00:20:29,680
>> DAVIDマラン：そして今、我々はしている
かなり良い形である。

513
00:20:29,680 --> 00:20:34,910
全体の左半分
入力は、現在ソートされている。

514
00:20:34,910 --> 00:20:37,370
すべての権利なので、これらの人が持っていた
私の利点 - 

515
00:20:37,370 --> 00:20:40,340
それはどのように上のすべての女の子を終わらなかった
左と右の上のすべての男の子？

516
00:20:40,340 --> 00:20:42,450
>> [OK]を、ので、みんな 'は今にしてください。

517
00:20:42,450 --> 00:20:44,680
だから私は、順を追ってません
これらの手順。

518
00:20:44,680 --> 00:20:46,550
我々は再適用することができれば我々は、表示されます
同じ擬似コード。

519
00:20:46,550 --> 00:20:50,050
あなたが先に行くと、立ち上がるしたい場合
そして君たちは、私はあなたにマイクを与えてみましょう。

520
00:20:50,050 --> 00:20:52,990
あなたは何を複製することはできませんかどうかを確認してください
我々だけでここにしました

521
00:20:52,990 --> 00:20:53,880
リストのもう一方の端。

522
00:20:53,880 --> 00:20:59,530
誰が、最初に話をする必要がある
アルゴリズムに基づいて？

523
00:20:59,530 --> 00:21:03,210
だから、前にやっているかを説明
あなたは、任意の足の動きを作る。

524
00:21:03,210 --> 00:21:05,930
>> SPEAKER 1：すべての権利、そう以来
私の左半分です

525
00:21:05,930 --> 00:21:07,790
左半分は、私が返すこと。

526
00:21:07,790 --> 00:21:08,730
右？

527
00:21:08,730 --> 00:21:09,250
>> DAVIDマラン：良い。

528
00:21:09,250 --> 00:21:10,350
>> SPEAKER 1：そして - 

529
00:21:10,350 --> 00:21:11,800
>> DAVIDマラン：ない
マイクは、次に行く？

530
00:21:11,800 --> 00:21:12,920
>> SPEAKER 1：次の番号。

531
00:21:12,920 --> 00:21:14,720
>> SPEAKER 2：だから私は右半分だ
の左半分の

532
00:21:14,720 --> 00:21:17,830
左半分、私は戻ります。

533
00:21:17,830 --> 00:21:18,050
>> DAVIDマラン：良い。

534
00:21:18,050 --> 00:21:18,550
あなたが返す。

535
00:21:18,550 --> 00:21:21,855
だから今あなたのために横に二人は何ですか？

536
00:21:21,855 --> 00:21:23,740
>> SPEAKER 2：私たちは小さいです誰が見て欲しい。

537
00:21:23,740 --> 00:21:24,200
>> DAVIDマラン：その通り。

538
00:21:24,200 --> 00:21:24,940
私たちは、マージしたい。

539
00:21:24,940 --> 00:21:27,590
我々はマージするために使用するつもりだスペース
あなたも、彼らはしているものの、中に

540
00:21:27,590 --> 00:21:30,250
明らかにすでにソート、我々は行っている
同じアルゴリズムに従うこと。

541
00:21:30,250 --> 00:21:31,560
だから、誰が戻って最初に行く？

542
00:21:31,560 --> 00:21:35,720
3だから、その後7。

543
00:21:35,720 --> 00:21:38,570
そして今、マイクが行く
これらの人に、OK？

544
00:21:38,570 --> 00:21:43,590
>> SPEAKER 3：だから私は右半分だ
左半分、私のnがより小さい

545
00:21:43,590 --> 00:21:45,048
1、ので、私はただ合格するつもりです - 

546
00:21:45,048 --> 00:21:46,380
>> DAVIDマラン：良い。

547
00:21:46,380 --> 00:21:49,450
>> SPEAKER 4：私の右半分だ
右の右半分の半分、私はよ

548
00:21:49,450 --> 00:21:51,740
また一人、私はそう
復帰するつもり。

549
00:21:51,740 --> 00:21:52,990
だから今我々はマージ。

550
00:21:52,990 --> 00:21:55,140

551
00:21:55,140 --> 00:21:56,150
>> SPEAKER 3：だから我々は戻って行く。

552
00:21:56,150 --> 00:21:57,160
>> DAVIDマラン：だからあなたが戻って入る。

553
00:21:57,160 --> 00:21:59,200
だから、5、8、その後、最初に行く。

554
00:21:59,200 --> 00:22:01,240
であり、現在観客、
我々は今、巻き戻ししなければならない段階

555
00:22:01,240 --> 00:22:02,200
戻って私達の心の中に？

556
00:22:02,200 --> 00:22:02,940
>> 読者：マージ。

557
00:22:02,940 --> 00:22:07,270
>> DAVIDマラン：左半分と右のマージ
オリジナルの左半分の半分。

558
00:22:07,270 --> 00:22:08,840
だから今 - 

559
00:22:08,840 --> 00:22:10,520
とだけ、これは明確にする
スペースを少し作る

560
00:22:10,520 --> 00:22:11,690
あなたとの間に二人の男。

561
00:22:11,690 --> 00:22:13,800
だから今、二つのリストだと、
左右。

562
00:22:13,800 --> 00:22:18,320
それでは、どのように我々は今、みんなにあなたをマージしない
再び席の最前列？

563
00:22:18,320 --> 00:22:19,600
>> 図3は、最初に行く。

564
00:22:19,600 --> 00:22:20,850
次に5、明らかに。

565
00:22:20,850 --> 00:22:23,110

566
00:22:23,110 --> 00:22:27,330
その後7、今8。

567
00:22:27,330 --> 00:22:28,710
[OK]を、今、私たちは何ですか？

568
00:22:28,710 --> 00:22:29,650
>> 読者：行って​​いない。

569
00:22:29,650 --> 00:22:32,440
>> DAVIDマラン：行っていない、なぜなら
明らかに、残りの1ステップがあります。

570
00:22:32,440 --> 00:22:35,720
しかし、再び、私はこれを使用している理由
"あなたの心の中で巻き戻し、"のような専門用語

571
00:22:35,720 --> 00:22:37,160
それが本当にだから、それはだ
何が起こっている。

572
00:22:37,160 --> 00:22:39,610
我々は、これらの手順のすべてを行っている
しかし、我々のために一時停止のようなものだ

573
00:22:39,610 --> 00:22:42,480
深く瞬間、ダイビング
アルゴリズム、一瞬一時停止、

574
00:22:42,480 --> 00:22:45,840
アルゴリズムに深く、そしてダイビング
今、我々は我々の巻き戻しのようなものする必要があります

575
00:22:45,840 --> 00:22:49,430
心とこれらの層のすべてを元に戻す
私たちは、ソートの保留にしたこと。

576
00:22:49,430 --> 00:22:51,790
>> だから今我々はサイズ4の2つのリストを持っている。

577
00:22:51,790 --> 00:22:54,790
君たちは、最後にもう一度立ち上がることができれば
とここまでの空間を少し作る

578
00:22:54,790 --> 00:22:57,230
これが左であることを明確にする
オリジナルの半分

579
00:22:57,230 --> 00:22:58,620
オリジナルの右半分。

580
00:22:58,620 --> 00:23:01,060
誰が最初​​の数字だと、私たち
背面にプルする必要がありますか？

581
00:23:01,060 --> 00:23:01,870
もちろんミシェル、。

582
00:23:01,870 --> 00:23:03,230
>> だから私たちはここでミシェルを置く。

583
00:23:03,230 --> 00:23:05,080
誰がナンバー2を持っている？

584
00:23:05,080 --> 00:23:06,440
番号2は、同様に背面に来る。

585
00:23:06,440 --> 00:23:07,800
数3？

586
00:23:07,800 --> 00:23:08,510
優秀。

587
00:23:08,510 --> 00:23:16,570
4番、5番、6番、
7番、および8番。

588
00:23:16,570 --> 00:23:18,850
>> [OK]を、ので、たくさんのように感じた
ステップの、確かに。

589
00:23:18,850 --> 00:23:22,390
しかし、今、我々は確認することができないかどうかを確認してみましょう
直感的に、この種の

590
00:23:22,390 --> 00:23:26,190
根本的に、特にとしてアルゴリズム
nは、私たちが見てきたように、本当に大きくなり

591
00:23:26,190 --> 00:23:29,170
アニメーションであり、
根本的に速くなります。

592
00:23:29,170 --> 00:23:33,400
だから私は最悪で、このアルゴリズムを主張
最良のケースでケースとさえ、

593
00:23:33,400 --> 00:23:36,160
n回ログのnのビッグOです。

594
00:23:36,160 --> 00:23:39,160
つまり、本のいくつかの側面があり
n個の手順がかかりますが、アルゴリズム

595
00:23:39,160 --> 00:23:43,110
別の態様は、どこかにあり
その繰り返し、そのループ、その

596
00:23:43,110 --> 00:23:44,410
ログnステップをとります。

597
00:23:44,410 --> 00:23:49,154
我々はどのようなものに我々の指を置くことができます
2つの数値はを参照している？

598
00:23:49,154 --> 00:23:51,320
さて、どこに - 

599
00:23:51,320 --> 00:23:54,160
マイクはどこでしょう？

600
00:23:54,160 --> 00:23:58,660
>> SPEAKER 1：ログnのだろう
二つに私たちを壊す - 

601
00:23:58,660 --> 00:23:59,630
本質的には、2で割る。

602
00:23:59,630 --> 00:24:00,120
>> DAVIDマラン：その通り。

603
00:24:00,120 --> 00:24:03,000
我々はこのように、任意のアルゴリズムを参照してくださいいつでも
までのところ、このパターンがあっただ

604
00:24:03,000 --> 00:24:04,200
分割、分割、分割。

605
00:24:04,200 --> 00:24:05,700
そしてそれは通常、削減だ
何かへ

606
00:24:05,700 --> 00:24:07,100
対数、ログベース2。

607
00:24:07,100 --> 00:24:10,180
しかし、それは本当に、何もすることができる
しかし、ベース2を記録。

608
00:24:10,180 --> 00:24:11,330
>> 今、nはどうですか？

609
00:24:11,330 --> 00:24:14,550
私は、我々は一種のことを分けていることがわかります
みんな - あなたを分け、あなたに分け、

610
00:24:14,550 --> 00:24:15,910
あなたを分け、分けた。

611
00:24:15,910 --> 00:24:18,760
終わりはどこから来るのでしょうか？

612
00:24:18,760 --> 00:24:19,810
>> だから、マージです。

613
00:24:19,810 --> 00:24:20,610
なぜならそれについて考える。

614
00:24:20,610 --> 00:24:25,420
あなたは一緒に8人をマージすると、
それによってそれらの半分4のセットです

615
00:24:25,420 --> 00:24:27,770
そして残りの半分は別です
4のセット、あなたはどのように行くのですか

616
00:24:27,770 --> 00:24:28,820
マージをしてはどうでしょうか？

617
00:24:28,820 --> 00:24:30,830
さて、皆さんはそれをやった
かなり直感的。

618
00:24:30,830 --> 00:24:34,140
>> しかし、私はその代わりに、もう少しそれをしなかった場合
念入りに、私が指さしたかもしれない

619
00:24:34,140 --> 00:24:38,090
私の左の最初の一番左の人
一番左の方を指差し手、

620
00:24:38,090 --> 00:24:42,080
私の右手でその半分の、と
ただその後を歩い

621
00:24:42,080 --> 00:24:46,990
最小の要素を指すリスト、
たびに、私の指を上を移動し、

622
00:24:46,990 --> 00:24:48,970
リストを通して、必要に応じてオーバー。

623
00:24:48,970 --> 00:24:51,890
しかし、これは合併に関する重要なものだ
プロセスは、私はこれらのペアを比較していますです

624
00:24:51,890 --> 00:24:53,460
要素。

625
00:24:53,460 --> 00:24:57,270
右半分から左から
半分、私は一度バックトラックはないよ。

626
00:24:57,270 --> 00:25:00,570
>> マージ自体は取っているので、
Nステップ以上のものはありません。

627
00:25:00,570 --> 00:25:03,250
そして、どのように何回は、私が持っていた
マージそれを行うには？

628
00:25:03,250 --> 00:25:07,150
さて、nより多くの、いや、私たちだけ
最後のマージとのことを見た。

629
00:25:07,150 --> 00:25:13,120
そして、あなたは取る何かをする場合
、nはn回のステップ、またはその逆を記録する

630
00:25:13,120 --> 00:25:15,210
それは私たちn回ログnを与えるために起こっている。

631
00:25:15,210 --> 00:25:16,310
>> そして、なぜこれが良いですか？

632
00:25:16,310 --> 00:25:19,600
さて、私たちはすでにそのログを知っていれば
右 -  nはnより良いですか？

633
00:25:19,600 --> 00:25:22,590
我々は、二分探索で電話帳を見た
たとえば、ログnは間違いだった

634
00:25:22,590 --> 00:25:23,760
リニアよりも良い。

635
00:25:23,760 --> 00:25:28,420
だから、nはn回ログを意味する
n回別のものより間違いなく良い

636
00:25:28,420 --> 00:25:30,390
nは、AKA nの二乗。

637
00:25:30,390 --> 00:25:32,400
そして、それは我々が最終的に感じるものだ。

638
00:25:32,400 --> 00:25:34,928
>> 拍手のそれほど大きく丸い、もし
我々はこれらの人については、可能性。

639
00:25:34,928 --> 00:25:38,920
>> [拍手]

640
00:25:38,920 --> 00:25:41,550
>> DAVIDマラン：そして、あなたの別れの贈り物 - 
あなたには、数値を保つかもしれない

641
00:25:41,550 --> 00:25:44,010
ご希望の場合。

642
00:25:44,010 --> 00:25:45,620
そして、あなたの別れの贈り物、いつものように。

643
00:25:45,620 --> 00:25:47,290
ああ、と私たちはあなたを送信します
映像、ミシェル。

644
00:25:47,290 --> 00:25:48,343
ありがとう。

645
00:25:48,343 --> 00:25:49,250
わかりました。

646
00:25:49,250 --> 00:25:50,400
ストレスボールをご自由にお召し上がりください。

647
00:25:50,400 --> 00:25:54,110
>> そして、私はその間に、プルアップしてみましょう
提供する私たちの友人ロブボーデン

648
00:25:54,110 --> 00:25:59,520
この上にやや異なる視点、
あなたは、これらを考えることができるので

649
00:25:59,520 --> 00:26:01,280
幾分で起こっ手順
別の方法。

650
00:26:01,280 --> 00:26:04,750
約ロブは何のために実際には、セットアップ
私たちがしたことを前提としています表示する

651
00:26:04,750 --> 00:26:09,030
既に分割までの完了
8小さなリストに大きなリスト、

652
00:26:09,030 --> 00:26:10,570
サイズ1の各。

653
00:26:10,570 --> 00:26:13,350
>> だから我々は、擬似コード変更している
少しだけで得るのソートする

654
00:26:13,350 --> 00:26:15,320
どのようにマージする作品の核となるアイデア。

655
00:26:15,320 --> 00:26:17,600
しかし、何の実行時間
彼はまだ行うについてです

656
00:26:17,600 --> 00:26:19,110
同じになるだろう。

657
00:26:19,110 --> 00:26:23,540
そして再び、ここでセットアップは、彼があるということです
サイズ1の8リストを始め。

658
00:26:23,540 --> 00:26:27,730
だから、彼はだ部分を見逃している
実際にログnを、n個のログは、ログNをやっ

659
00:26:27,730 --> 00:26:31,205
入力の分割。

660
00:26:31,205 --> 00:26:32,120
>> [ビデオの再生]

661
00:26:32,120 --> 00:26:33,615
>>  - すなわち、ステップ1のためのそれだ。

662
00:26:33,615 --> 00:26:38,270
繰り返しステップ2、のために
リストのペアをマージ。

663
00:26:38,270 --> 00:26:39,210
>> DAVIDマラン：フム。

664
00:26:39,210 --> 00:26:41,270
音声のみが来ている
私のコンピュータのうち、。

665
00:26:41,270 --> 00:26:42,520
のは、再びこれを試してみましょう。

666
00:26:42,520 --> 00:26:45,330

667
00:26:45,330 --> 00:26:48,310
>>  - ただ、任意になるを選ぶ - 
今、私たちは4つのリストを持っている。

668
00:26:48,310 --> 00:26:51,590

669
00:26:51,590 --> 00:26:52,120
前に学んでください。

670
00:26:52,120 --> 00:26:53,040
>> DAVIDマラン：あり私達は行く。

671
00:26:53,040 --> 00:27:00,510
>>  - マージ108と15を、私たちは終わる
ポップアップリスト15、108と。

672
00:27:00,510 --> 00:27:07,170
我々は、50と4のマージ
4、50で終わる。

673
00:27:07,170 --> 00:27:12,990
我々は、8と42のマージ
8、42で終わる。

674
00:27:12,990 --> 00:27:19,970
そして、私たちは、23と16をマージ
16、23で終わる。

675
00:27:19,970 --> 00:27:23,270
>> これで、すべて私たちのリストには、サイズが2である。

676
00:27:23,270 --> 00:27:26,690
それぞれのことに注意してください
4つのリストがソートされます。

677
00:27:26,690 --> 00:27:29,450
だから我々は、マージを開始することができます
再びリストのペア。

678
00:27:29,450 --> 00:27:38,420
我々は、15と108と4と50のマージ
まず、その15、4を取る

679
00:27:38,420 --> 00:27:41,500
50、次に108。

680
00:27:41,500 --> 00:27:50,610
、8、42と16のマージ23、我々は最初に取る
その後その後8、16、23、

681
00:27:50,610 --> 00:27:52,700
その後42。

682
00:27:52,700 --> 00:27:57,600
>> だから今我々は、サイズのちょうど2つのリストを持っている
ソートされてその各々4。

683
00:27:57,600 --> 00:28:01,170
だから今我々は、これらの2つのリストをマージします。

684
00:28:01,170 --> 00:28:11,835
まず、我々は4を取ること、そして私達は取る
8、次に我々は、その後、16その後、15を取る

685
00:28:11,835 --> 00:28:19,456
その後その後その後、23、42、50、108。

686
00:28:19,456 --> 00:28:19,872
>> [ENDビデオ再生]

687
00:28:19,872 --> 00:28:23,430
>> DAVIDマラン：繰り返しになりますが、予告、彼は決して
与えられたカップ2回以上触れ

688
00:28:23,430 --> 00:28:24,860
それを越えて前進した後。

689
00:28:24,860 --> 00:28:26,200
そこで彼は、繰り返すことのない。

690
00:28:26,200 --> 00:28:29,850
そこで彼は、いつも側に動いて、
私たちはn個を得たところ、それはです。

691
00:28:29,850 --> 00:28:33,290
>> なぜ私が1アニメーションをプルアップすることはできませ
我々は前に見たことが、今回

692
00:28:33,290 --> 00:28:35,110
マージソートにのみ焦点を当てています。

693
00:28:35,110 --> 00:28:38,030
私が先に行くと、拡大しましょう
このここにいます。

694
00:28:38,030 --> 00:28:42,530
まず、私はランダムな入力を選択してみましょう
これを拡大して、あなたが見るの並べ替えることができます

695
00:28:42,530 --> 00:28:46,600
我々は、付与された、以前にかかったのか
マージソートは、実​​際にやっている。

696
00:28:46,600 --> 00:28:50,330
>> ですから、これらの半分を取得したりすることに気づく
これらの四半期またはこれらの8分

697
00:28:50,330 --> 00:28:53,140
問題はその突然
良い形を取り始める。

698
00:28:53,140 --> 00:28:57,070
そして最後に、あなたはで見ること
最後の最後そのBAM、

699
00:28:57,070 --> 00:28:58,860
すべてが一緒にマージされます。

700
00:28:58,860 --> 00:29:01,690
>> したがって、これらは、ちょうど3異なります
同じ考え方になります。

701
00:29:01,690 --> 00:29:05,980
しかし、単に除算などの主要な洞察力、
と、非常に最初のクラスで征服

702
00:29:05,980 --> 00:29:10,640
我々は何とか分割することを決めたということでした
大きな何かに問題が、中に

703
00:29:10,640 --> 00:29:14,760
精神で同一の何かのソート、
しかし小さく、より小さい

704
00:29:14,760 --> 00:29:15,660
と小さい。

705
00:29:15,660 --> 00:29:18,420
>> 考える一種のようになりましたもうひとつの楽しい方法
これらについては、にもかかわらず、それはありません

706
00:29:18,420 --> 00:29:20,520
あなたと同じ直感を与えるつもり
理解があり、

707
00:29:20,520 --> 00:29:21,640
次のアニメーション。

708
00:29:21,640 --> 00:29:25,400
だから、これは誰かが一緒に入れてビデオです
その関連する異なる

709
00:29:25,400 --> 00:29:29,970
のための様々な操作で音
挿入ソート、マージソートのために、と

710
00:29:29,970 --> 00:29:31,150
他人のカップルのため。

711
00:29:31,150 --> 00:29:32,330
だから瞬間に、私はプレーを打つつもりです。

712
00:29:32,330 --> 00:29:33,600
それは長い分についてです。

713
00:29:33,600 --> 00:29:37,410
そして、あなたはまだ見ることができるにもかかわらず
パターンは、することができ、この時間が起こっ

714
00:29:37,410 --> 00:29:41,420
また、これらのアルゴリズムがどのように聞こえる
異なるとして実行する

715
00:29:41,420 --> 00:29:43,950
多少異なるパターン。

716
00:29:43,950 --> 00:29:45,830
>> これは、挿入ソートです。

717
00:29:45,830 --> 00:29:50,400
>> [TONESはPLAYING]

718
00:29:50,400 --> 00:29:52,400
>> DAVIDマラン：それは再試行されます
各要素を挿入する

719
00:29:52,400 --> 00:29:52,900
それが属する場所に。

720
00:29:52,900 --> 00:29:54,628
これは、バブルソートです。

721
00:29:54,628 --> 00:30:10,097
>> [TONESはPLAYING]

722
00:30:10,097 --> 00:30:13,630
>> DAVIDマラン：そして、あなたは手触りの並べ替えることができます
それがやっている方法は比較的少ない作業

723
00:30:13,630 --> 00:30:15,834
各ステップで。

724
00:30:15,834 --> 00:30:20,470
これは、退屈は鳴るもののようです。

725
00:30:20,470 --> 00:30:21,472
>> [TONESはPLAYING]

726
00:30:21,472 --> 00:30:25,222
>> DAVIDマラン：これは、選択ソートであり、
我々は我々がすることによってする要素を選択する場所

727
00:30:25,222 --> 00:30:28,845
何度も何度も何度も通って行く
そして冒頭でそれを置く。

728
00:30:28,845 --> 00:30:37,674
>> [TONESはPLAYING]

729
00:30:37,674 --> 00:30:43,970
>> DAVIDマラン：これはマージソートであり、その
あなたが本当に感じるように開始することができます。

730
00:30:43,970 --> 00:30:51,810
>> [TONESはPLAYING]

731
00:30:51,810 --> 00:30:54,770
>> [笑い]

732
00:30:54,770 --> 00:30:58,395
>> DAVIDマラン：ノームと呼ばれるもの
我々は見ていないソート、。

733
00:30:58,395 --> 00:31:13,630
>> [TONESはPLAYING]

734
00:31:13,630 --> 00:31:17,910
>> DAVIDマラン：だから、今、私は見てみましょう
あなたがうまくいけばであるように気を取られ

735
00:31:17,910 --> 00:31:21,110
音楽、私は少しをすり抜けることができる場合
ここで数学のビット。

736
00:31:21,110 --> 00:31:24,850
だから私たちにできること第四の方法はありませ
それはこれらの何を意味するのかを考える

737
00:31:24,850 --> 00:31:29,210
ものより速くなるための関数
我々は前に見てきた。

738
00:31:29,210 --> 00:31:32,470
そして、あなたはからコースで来ている場合
数学の背景に、

739
00:31:32,470 --> 00:31:36,030
実際に既におそらく知っているあなた
このテクニックに言葉を平手打ちすることができます - 

740
00:31:36,030 --> 00:31:40,400
すなわち再帰は、関数
それは何とか自分自身を呼び出します。

741
00:31:40,400 --> 00:31:44,780
>> そして再び、そのマージソートを思い出す
擬似コードは、ある意味で再帰的だった

742
00:31:44,780 --> 00:31:48,460
マージソートのステップのその1
ソートを呼び出すことだった - 

743
00:31:48,460 --> 00:31:49,740
それは、それ自体である。

744
00:31:49,740 --> 00:31:52,480
しかし、ありがたいことに、我々は維持しているため
呼び出しソート、またはマージソート、

745
00:31:52,480 --> 00:31:55,880
具体的には、小さく上
最終的には、より小さいリスト、我々

746
00:31:55,880 --> 00:32:00,005
我々は呼ぶことに何の底入れおかげ
ベースケース、ハードコードされた場合、その

747
00:32:00,005 --> 00:32:04,270
2未満、リストが小さい場合には前記
その場合は、単にすぐに戻ります。

748
00:32:04,270 --> 00:32:07,550
我々は特殊なケースを持っていなかった場合は、
アルゴリズムは底打ち、決して

749
00:32:07,550 --> 00:32:11,010
そして、あなたは確かになるだろう
本当に永遠に無限ループ。

750
00:32:11,010 --> 00:32:14,330
>> しかし、我々はすぐに入れたかったと仮定
この上でいくつかの数字は、再び、Nを使用して

751
00:32:14,330 --> 00:32:15,660
入力の大きさ。

752
00:32:15,660 --> 00:32:18,680
そして、私は何、お聞きしたかった
に関与して合計時間

753
00:32:18,680 --> 00:32:19,800
マージソートを実行している？

754
00:32:19,800 --> 00:32:22,960
またはより一般的には、何
時間のそれのコスト？

755
00:32:22,960 --> 00:32:24,730
>> まあそれはそれを測定することは非常に簡単です。

756
00:32:24,730 --> 00:32:29,010
nが2未満の場合、時間が関与
n個の要素をソートするには、

757
00:32:29,010 --> 00:32:30,480
nが2である場合、0である。

758
00:32:30,480 --> 00:32:31,410
私達はちょうど戻るので。

759
00:32:31,410 --> 00:32:32,510
完了すべき仕事がありません。

760
00:32:32,510 --> 00:32:35,660
今、間違いなく、多分それは一歩または2の
量を把握するための手順

761
00:32:35,660 --> 00:32:38,420
仕事、それが0に近い十分だ
私は全く仕事がありませんと言うつもりです

762
00:32:38,420 --> 00:32:40,940
リストが非常に小さい場合に必要
面白くする。

763
00:32:40,940 --> 00:32:42,580
>> しかし、このケースは、興味深いです。

764
00:32:42,580 --> 00:32:47,320
再帰的な場合は、支店であった
他に言った擬似コード、ソート

765
00:32:47,320 --> 00:32:52,000
左半分は、右を並べ替える
半分、半分ずつをマージ。

766
00:32:52,000 --> 00:32:55,530
今、この式はなぜ
その費用を表す？

767
00:32:55,530 --> 00:32:58,690
さて、nはTだけで意味
n個の要素を並べ替えるための時間。

768
00:32:58,690 --> 00:33:03,070
その後の右側に
そこ等号、nはTが分割

769
00:33:03,070 --> 00:33:06,600
2で何のコストを参照している？

770
00:33:06,600 --> 00:33:07,570
左半分のソート。

771
00:33:07,570 --> 00:33:10,990
2分周nは他のTである
おそらくのコストを参照する

772
00:33:10,990 --> 00:33:12,390
右半分を並べ替える。

773
00:33:12,390 --> 00:33:14,590
>> そしてプラスさn？

774
00:33:14,590 --> 00:33:15,420
マージされています。

775
00:33:15,420 --> 00:33:19,120
なぜなら、2つのリストのいずれかを持っている場合
サイズn 2以上と別のサイズのN

776
00:33:19,120 --> 00:33:22,580
2かけ、あなたは本質的に触れなければならない
ただロブのように、これらの要素のそれぞれ、

777
00:33:22,580 --> 00:33:24,990
コップのそれぞれに触れた、とだけ
我々はそれぞれに指摘したように

778
00:33:24,990 --> 00:33:26,310
ステージ上でボランティア。

779
00:33:26,310 --> 00:33:28,790
だからnはマージの費用です。

780
00:33:28,790 --> 00:33:31,780
>> さて、残念ながら、この式
再帰的にも、それ自体である。

781
00:33:31,780 --> 00:33:36,390
nがあれば、と言う、、質問をしそうだとすれば
16、ステージ上の16人がある場合

782
00:33:36,390 --> 00:33:40,670
ビデオ、どのように多くの合計16杯または
それらをソートする手順は時間がかかりますか

783
00:33:40,670 --> 00:33:41,550
マージソートと？

784
00:33:41,550 --> 00:33:45,790
それは、実際に明白な答えはありません
今、あなたは、ソートする必要があるため

785
00:33:45,790 --> 00:33:48,500
再帰的に次の式を答えます。

786
00:33:48,500 --> 00:33:51,190
>> 私が提案させているのでしかし、それは、OKだ
私たちは、次の作業を行うこと。

787
00:33:51,190 --> 00:33:56,670
16人をソートしたりするために必要な時間
16カップが表現されようとしている

788
00:33:56,670 --> 00:33:58,020
一般的には16のTのように。

789
00:33:58,020 --> 00:34:01,400
しかし、それは私たちによると、等しい
前の式、2倍の量

790
00:34:01,400 --> 00:34:04,780
時間がそれを並べ替えにかかる
8カッププラス16。

791
00:34:04,780 --> 00:34:08,590
そして再び、プラス16は、マージする時間です
と8のT 2回です

792
00:34:08,590 --> 00:34:10,790
左半分と右半分をソートする時間。

793
00:34:10,790 --> 00:34:11,989
>> しかし、再び、これは十分ではありません。

794
00:34:11,989 --> 00:34:13,210
我々はより深くに潜る必要があります。

795
00:34:13,210 --> 00:34:16,409
これは、我々が答えなければならないことを意味
質問8のTは何ですか？

796
00:34:16,409 --> 00:34:19,610
まあ8のTは、ちょうど2である
4プラス8倍T。

797
00:34:19,610 --> 00:34:20,520
まあ、4のTは何ですか？

798
00:34:20,520 --> 00:34:23,780
4のTは、2プラス4のちょうど2倍のTです。

799
00:34:23,780 --> 00:34:25,489
まあ、2のTは何ですか？

800
00:34:25,489 --> 00:34:29,030
2のTは、1プラス2のちょうど2倍のTです。

801
00:34:29,030 --> 00:34:31,940
>> そして再び、我々は得ることのようなものだ
このサイクルで立ち往生。

802
00:34:31,940 --> 00:34:34,790
しかし、それは、約ヒットするだ
いわゆるベースケース。

803
00:34:34,790 --> 00:34:37,310
1のT何なので、私たちは主張したのですか？

804
00:34:37,310 --> 00:34:37,810
0。

805
00:34:37,810 --> 00:34:39,730
だから今ようやく、我々は後方に動作することができます。

806
00:34:39,730 --> 00:34:44,290
>> 1のTが0である場合、私は今まで1戻ることができます
ここにこの男へのライン、私はすることができます

807
00:34:44,290 --> 00:34:46,330
1のTは0のプラグイン。

808
00:34:46,330 --> 00:34:51,770
だから、それが2回ゼロに等しいことを意味する
そうでなければ0、プラス2として知られています。

809
00:34:51,770 --> 00:34:53,739
となるように式全体は2です。

810
00:34:53,739 --> 00:34:58,740
>> 今、私は答え2のTを取る場合
2ですが、真ん中のライン、Tに差し込む

811
00:34:58,740 --> 00:35:02,740
4の、それは私を2回与える
2プラス4,8そう。

812
00:35:02,740 --> 00:35:07,080
私は、前に8に接続する場合
行、それは私を2回8、16を与えます。

813
00:35:07,080 --> 00:35:12,470
そして、私たちはその後、とそれを継続する場合
24は、16に追加して、我々は最終的に得る

814
00:35:12,470 --> 00:35:13,820
64の値。

815
00:35:13,820 --> 00:35:18,480
>> 今の、それ自体のソートが話すこと
n個の表記には何もない、

816
00:35:18,480 --> 00:35:20,700
ビッグO、私たちがしたことをオメガ
について話して。

817
00:35:20,700 --> 00:35:24,890
しかし、それは64が確かであることが判明
16、入力のサイズ、

818
00:35:24,890 --> 00:35:27,110
16のベース2を記録。

819
00:35:27,110 --> 00:35:30,200
そして、これは、ちょっと不慣れである場合だけ
背中と思うし、それが戻ってくる

820
00:35:30,200 --> 00:35:30,700
最終的にあなたに。

821
00:35:30,700 --> 00:35:33,775
これは、ログベース2の場合は、2のようなものだ
あなたに16を与えるものに上げて？

822
00:35:33,775 --> 00:35:36,380
ああ、それは4つなので、それは16倍4です。

823
00:35:36,380 --> 00:35:39,380
>> そして再び、それは大したことではありませんこの場合
かすんでメモリの一種は今です。

824
00:35:39,380 --> 00:35:43,720
しかし、今のところ、信仰を取る
16ログ16が64であること。

825
00:35:43,720 --> 00:35:46,590
そして確かに、この単純な正​​気​​と
チェックし、我々は確認しました - 

826
00:35:46,590 --> 00:35:48,250
しかし、正式に証明されていない - 

827
00:35:48,250 --> 00:35:52,800
そのマージの実行時間
ソートは確かにあるN Nを記録。

828
00:35:52,800 --> 00:35:53,790
>> そんなに悪くない。

829
00:35:53,790 --> 00:35:57,260
それよりも間違いなく良いです
我々はこれまで見てきたアルゴリズム、

830
00:35:57,260 --> 00:36:00,710
私たちが活用してきたので、それは、一つだ
再帰と呼ばれる技術。

831
00:36:00,710 --> 00:36:03,880
しかし、それよりも興味深い、その
分割と征服の概念。

832
00:36:03,880 --> 00:36:07,460
繰り返しになりますが、本当に0週のものという
今でもで再発されて

833
00:36:07,460 --> 00:36:08,740
もっと説得力のある方法。

834
00:36:08,740 --> 00:36:11,750
>> あなたがしている場合はすぐに楽しい小さな運動、
これをやったことがない - と、おそらくあなた

835
00:36:11,750 --> 00:36:14,660
通常の一種のため、持っていないでしょう
人々はこれを行うには思わない。

836
00:36:14,660 --> 00:36:20,650
しかし、私はgoogle.comに行く場合となら
私について何かを学びたい

837
00:36:20,650 --> 00:36:22,356
再帰は、入力します。

838
00:36:22,356 --> 00:36:25,106

839
00:36:25,106 --> 00:36:29,058
>> [笑い]

840
00:36:29,058 --> 00:36:32,030
[MORE笑い]

841
00:36:32,030 --> 00:36:33,385
DAVIDマラン：悪い冗談ゆっくり拡散。

842
00:36:33,385 --> 00:36:34,450
[笑い]

843
00:36:34,450 --> 00:36:36,970
DAVIDマラン：念のために、それがある。

844
00:36:36,970 --> 00:36:38,710
私はそれが間違ってスペルしませんでした、
と冗談はあり。

845
00:36:38,710 --> 00:36:40,810
わかりました。

846
00:36:40,810 --> 00:36:42,950
あなたの隣の人々にそれを説明する場合
それはかなりただまだクリックされていません。

847
00:36:42,950 --> 00:36:47,650
しかし、再帰は、より一般的には言及
呼び出し元の関数のプロセスに

848
00:36:47,650 --> 00:36:51,430
それ自体、又はより一般的には、分割する
することができます何かに問題

849
00:36:51,430 --> 00:36:56,220
同じ解くことにより、少しずつ解決
代表的な問題。

850
00:36:56,220 --> 00:36:58,400
>> まあ、みましょうチェンジギア
ちょっと。

851
00:36:58,400 --> 00:37:00,840
我々は、特定のcliffhangersに終了したいと、
ように設定することから始めましょう

852
00:37:00,840 --> 00:37:05,870
舞台、数分間、
非常にシンプルなアイデアで - 

853
00:37:05,870 --> 00:37:07,620
2つの要素をスワッピングのもの、右？

854
00:37:07,620 --> 00:37:10,040
我々がしてきたこれらのアルゴリズムのすべて
過去のカップルの話

855
00:37:10,040 --> 00:37:12,420
講義では、いくつかを含む
スワッピングの一種。

856
00:37:12,420 --> 00:37:14,630
今日、それは彼らが取得することによって可視化した
アップする彼らの椅子のうち、と

857
00:37:14,630 --> 00:37:18,570
歩き回ったが、コードの中で、我々はだろう
一つの配列から要素を取る

858
00:37:18,570 --> 00:37:20,370
と別のものにウンチそれ。

859
00:37:20,370 --> 00:37:21,880
>> だから我々はこれをやってどうやって行くのですか？

860
00:37:21,880 --> 00:37:24,850
まあ、私が先に行くと書いてみましょう
ここで簡単にプログラム。

861
00:37:24,850 --> 00:37:31,600
私が先に行くとするつもりです
この次のよう。

862
00:37:31,600 --> 00:37:33,910
これを呼び出してみましょう - 

863
00:37:33,910 --> 00:37:38,070
我々はこの1つを呼び出すために何をしたいですか？

864
00:37:38,070 --> 00:37:38,650
>> 実際には、ない。

865
00:37:38,650 --> 00:37:39,420
私は巻き戻してみましょう。

866
00:37:39,420 --> 00:37:41,220
私はそれを行うにはしたくない
まだ接戦。

867
00:37:41,220 --> 00:37:42,270
それは楽しみを台無しにします。

868
00:37:42,270 --> 00:37:43,600
代わりにこれを実行してみましょう。

869
00:37:43,600 --> 00:37:47,430
>> 私は少しを書きたいと仮定
プログラムは、それが今ではこれを包含

870
00:37:47,430 --> 00:37:48,700
再帰のアイデア。

871
00:37:48,700 --> 00:37:50,370
私は種類のそこに先んじて自分の得た。

872
00:37:50,370 --> 00:37:51,420
私は、次の操作を実行するつもりです。

873
00:37:51,420 --> 00:38:00,220
>> まず、クイックは、標準io.hののインクルード
cs50.h.のと同様に、インクルード

874
00:38:00,220 --> 00:38:03,200
そして私は先に行くつもりです
とint主無効を宣言

875
00:38:03,200 --> 00:38:04,360
通常の方法である。

876
00:38:04,360 --> 00:38:07,920
私は、私は、ファイルの名前が間違ってきた実現
私はちょうどここにそう。C拡張を追加してみましょう

877
00:38:07,920 --> 00:38:09,510
我々はそれを正しくコンパイルすることができます。

878
00:38:09,510 --> 00:38:10,970
この機能をオフに起動します。

879
00:38:10,970 --> 00:38:13,290
>> 私はかなり、書きたいと機能
単に、尋ね一つです

880
00:38:13,290 --> 00:38:16,210
その後数のユーザーとは、加算
その間のすべての数字

881
00:38:16,210 --> 00:38:19,920
番号と、言う、0。

882
00:38:19,920 --> 00:38:22,510
だから最初に私が先に行くつもりです
とint nを宣言します。

883
00:38:22,510 --> 00:38:24,760
それから私はいくつかのコードをコピーしてその
我々はしばらくの間使用してきました。

884
00:38:24,760 --> 00:38:26,660
何かが真である間。

885
00:38:26,660 --> 00:38:28,000
私は瞬間にそれに戻ってくる。

886
00:38:28,000 --> 00:38:29,010
>> 私が何をしたいのですか？

887
00:38:29,010 --> 00:38:33,460
私はprintfの肯定言いたい
整数でお願いします。

888
00:38:33,460 --> 00:38:36,130
そして私はするつもりです
言うnはint型を取得し取得します。

889
00:38:36,130 --> 00:38:38,800
だからもう一度、いくつかの定型コード
我々は前に使用したこと。

890
00:38:38,800 --> 00:38:40,810
そして、私はこれを行うつもりだ
nが1未満でいる。

891
00:38:40,810 --> 00:38:44,120
だから、これは、ユーザーことが保証されます
私に正の整数を与えます。

892
00:38:44,120 --> 00:38:45,490
>> そして今、私は次の操作を実行するつもりです。

893
00:38:45,490 --> 00:38:51,020
私は数字のすべてを追加したい
Nまたは0であり、nは1〜と、

894
00:38:51,020 --> 00:38:52,570
同等に、合計を取得します。

895
00:38:52,570 --> 00:38:55,100
だから大きなシグマ記号
あなたが思い出すかもしれない。

896
00:38:55,100 --> 00:38:59,050
だから私は、最初の呼び出しでこれを行うつもりだ
シグマと呼ばれる機能、

897
00:38:59,050 --> 00:39:06,030
Nでそれを渡して、それから私はするつもりです
printfの言う、答えはすぐそこです。

898
00:39:06,030 --> 00:39:08,180
>> だから要するに、私が取得し、
ユーザーからint型。

899
00:39:08,180 --> 00:39:09,280
私はそれがポジティブだことを確認してください。

900
00:39:09,280 --> 00:39:12,700
私は、変数と呼ばれる答えを宣言
その中にint型とストア復帰

901
00:39:12,700 --> 00:39:15,610
入力としてnを渡してシグマの値。

902
00:39:15,610 --> 00:39:17,060
そして私はその答えをプリントアウト。

903
00:39:17,060 --> 00:39:19,550
>> 残念なことに、シグマが聞こえるにもかかわらず
にあるかもしれない何かのように

904
00:39:19,550 --> 00:39:24,040
math.hはファイル、その宣言、
それは実際にはありません。

905
00:39:24,040 --> 00:39:24,690
だからOKです。

906
00:39:24,690 --> 00:39:26,170
私はこれを自分で実装することができます。

907
00:39:26,170 --> 00:39:29,160
私はと呼ばれる機能を実現するつもりだ
シグマ、それは取ることになるだろう

908
00:39:29,160 --> 00:39:29,900
パラメータ - 

909
00:39:29,900 --> 00:39:32,100
ただそれだけの男、呼んでみましょう
ので、それは違う。

910
00:39:32,100 --> 00:39:35,910
そして、ここまで、私が言おうとしてんだけど、
mが1未満であればよく、 - これは

911
00:39:35,910 --> 00:39:38,180
非常にプログラムを面白くない。

912
00:39:38,180 --> 00:39:41,700
だから私は先に行くつもりだと
すぐに0を返す。

913
00:39:41,700 --> 00:39:45,920
それだけですべてを合計しても意味がありません
1とmの番号mの場合

914
00:39:45,920 --> 00:39:48,470
0または負のそのものです。

915
00:39:48,470 --> 00:39:50,900
>> そして私は先に行くつもりです
と非常に反復的にこれを行う。

916
00:39:50,900 --> 00:39:53,090
私は、古い学校のこの種のをするつもりです
と私は先に行くつもりです

917
00:39:53,090 --> 00:39:57,150
と私はするつもりだと言う
0に合計を宣言します。

918
00:39:57,150 --> 00:39:59,630
それから私は持っているつもりです
int型のループのために - 

919
00:39:59,630 --> 00:40:02,820
と私はそれが私たちに合うようにやらせる
流通コードするので、コピーを持っている

920
00:40:02,820 --> 00:40:07,500
自宅で。 int型のiは、最大で1を取得
iがより小さいまたはmに等しい。

921
00:40:07,500 --> 00:40:09,430
私はプラスプラス。

922
00:40:09,430 --> 00:40:11,430
そして内側のループのためにこのの - 

923
00:40:11,430 --> 00:40:12,440
我々は、ほとんどそこにいる - 

924
00:40:12,440 --> 00:40:15,810
和は合計プラス1を取得します。

925
00:40:15,810 --> 00:40:17,670
そして私は和を返すつもりです。

926
00:40:17,670 --> 00:40:19,420
>> だから私は、すぐにこれをした
かなり確か。

927
00:40:19,420 --> 00:40:22,775
しかし、再び、主な機能は、きれいです
我々はしたコードに基づいて、簡単な

928
00:40:22,775 --> 00:40:23,190
これまで書かれた。

929
00:40:23,190 --> 00:40:25,610
肯定を得るために二重のループを使用して
ユーザーからint型。

930
00:40:25,610 --> 00:40:29,870
私はその後、新しい関数にそのint型を渡す
nは、再び、それを呼び出して、シグマと呼ばれる。

931
00:40:29,870 --> 00:40:33,100
と私は、戻り値は、答えを保存
現在はブラックボックスから

932
00:40:33,100 --> 00:40:35,460
変数に、シグマとして知ら
答えと呼ばれる。

933
00:40:35,460 --> 00:40:36,580
それから私は、それを印刷。

934
00:40:36,580 --> 00:40:39,090
>> 私たちは今の話を続けると、
シグマはどのように実装されている？

935
00:40:39,090 --> 00:40:40,840
私は、次のように実装することを提案する。

936
00:40:40,840 --> 00:40:43,560
エラーチェックの最初、少し
ユーザーがないことを確認し

937
00:40:43,560 --> 00:40:46,480
私と一緒にいじりとを渡す
いくつかの負の値または0の値。

938
00:40:46,480 --> 00:40:49,710
それから私はと呼ばれる変数を宣言
合計し、それを0に設定します。

939
00:40:49,710 --> 00:40:55,910
>> そして今、私は私が等しいから動き始める
1までであり、mを含むすべての方法、

940
00:40:55,910 --> 00:41:00,130
私はすべて含まれるようにしたいので
M、包括を通じて1からの数字。

941
00:41:00,130 --> 00:41:04,350
と内側のforループは、この、私はただやる
合計は、それが今は何でもなる、プラス

942
00:41:04,350 --> 00:41:08,900
iの値。

943
00:41:08,900 --> 00:41:10,370
プラスiの値。

944
00:41:10,370 --> 00:41:14,090
>> 余談として、あなたがこれを見ていないした場合
前に、いくつかのシンタックスシュガーはあり

945
00:41:14,090 --> 00:41:14,870
このラインのため。

946
00:41:14,870 --> 00:41:21,120
プラスは、私に等しいように私は、これを書き換えることができます
ただ自分自身にいくつかのキーストロークを保存する

947
00:41:21,120 --> 00:41:22,570
と少しクーラーを探すために。

948
00:41:22,570 --> 00:41:23,140
しかし、それはすべてです。

949
00:41:23,140 --> 00:41:24,660
それは機能的に同じものです。

950
00:41:24,660 --> 00:41:26,710
>> 残念なことに、このコードの
まだコンパイルするつもりはありません。

951
00:41:26,710 --> 00:41:31,600
私はどのようにシグマは0を、makeを実行する場合
私は怒鳴ら取得するつもり？

952
00:41:31,600 --> 00:41:33,473
何が好きではないために起こっている？

953
00:41:33,473 --> 00:41:35,740
>> 読者：[聞こえない]。

954
00:41:35,740 --> 00:41:37,800
>> DAVIDマラン：ええ、私は宣言していない
右上アップ機能、？

955
00:41:37,800 --> 00:41:40,590
Cはそれだけという点で、愚かなの一種である
あなたはそれが何を言うことありませんし、

956
00:41:40,590 --> 00:41:41,880
そのためにはそれをしなければならない。

957
00:41:41,880 --> 00:41:45,910
私はここに入力してヒットした場合などは、私はするつもりです
シグマについての警告が暗黙の取得

958
00:41:45,910 --> 00:41:46,860
宣言。

959
00:41:46,860 --> 00:41:48,120
>> ああ、問題ない。

960
00:41:48,120 --> 00:41:50,370
私は頂上まで行くことができ、私はすることができます
大丈夫、と言う、ちょっと待って。

961
00:41:50,370 --> 00:41:54,240
シグマは返す関数です。
int型とそれは期待し

962
00:41:54,240 --> 00:41:56,620
入力、セミコロンとしてint型。

963
00:41:56,620 --> 00:41:59,550
または私は全体の機能を置くことができ
メイン上、しかし、一般的に、私は思います

964
00:41:59,550 --> 00:42:02,260
それはだから、それに対してお勧め
いつも一番上にメインがあると便利

965
00:42:02,260 --> 00:42:06,310
あなたは右に飛び込むと知ることができるのか
プログラムは最初にメイン読んでやっている。

966
00:42:06,310 --> 00:42:07,930
>> だから今、私は画面をクリアしましょう​​。

967
00:42:07,930 --> 00:42:09,330
リメイクシグマ0。

968
00:42:09,330 --> 00:42:10,340
すべてがチェックアウトするように思われる。

969
00:42:10,340 --> 00:42:11,970
私はシグマ0を実行してみましょう。

970
00:42:11,970 --> 00:42:12,770
正のインター。

971
00:42:12,770 --> 00:42:15,580
私はそれを数をあげる
それをシンプルに保つための3。

972
00:42:15,580 --> 00:42:18,710
だから私に3を与える必要があります
プラス2に1を加えたので、6。

973
00:42:18,710 --> 00:42:20,750
入力して、確かに私は6を得る。

974
00:42:20,750 --> 00:42:21,820
>> 私は何か大きなものを行うことができます - 

975
00:42:21,820 --> 00:42:24,080
50、12、75。

976
00:42:24,080 --> 00:42:27,690
ただ接線として、私はするつもりです
本当に大きなようなとんでもないもの

977
00:42:27,690 --> 00:42:30,375
番号、ああ、実際に働いた - 

978
00:42:30,375 --> 00:42:31,600
ええ、私はそうだとは思わない。

979
00:42:31,600 --> 00:42:32,810
見てみましょう。

980
00:42:32,810 --> 00:42:34,060
実際にそれを台無しにしてみましょう。

981
00:42:34,060 --> 00:42:37,150

982
00:42:37,150 --> 00:42:38,400
>> それが問題です。

983
00:42:38,400 --> 00:42:43,180

984
00:42:43,180 --> 00:42:44,970
どうなってるの？

985
00:42:44,970 --> 00:42:46,050
コー​​ドは、悪くはない。

986
00:42:46,050 --> 00:42:48,470
それはまだ直線です。

987
00:42:48,470 --> 00:42:50,810
口笛はいえ、良い効果です。

988
00:42:50,810 --> 00:42:52,060
どうなってるの？

989
00:42:52,060 --> 00:42:54,700

990
00:42:54,700 --> 00:42:55,620
>> 私はそれを聞いたかどうかわからない。

991
00:42:55,620 --> 00:42:57,620
だから、判明 - と
これは脇の通りです。

992
00:42:57,620 --> 00:42:59,400
これは、コアではない
再帰のアイデア。

993
00:42:59,400 --> 00:43:02,480
私がしようとしているので、それは判明
、このような大きな数を表す最も

994
00:43:02,480 --> 00:43:06,980
おそらくそれが誤解されている
正でない数としてCによって、

995
00:43:06,980 --> 00:43:09,980
しかし、負の数。

996
00:43:09,980 --> 00:43:12,690
>> 我々はこれについて話が、それていない
負の数があるが判明

997
00:43:12,690 --> 00:43:14,210
加えて、世界で
正の数に。

998
00:43:14,210 --> 00:43:16,290
そして、あなたがすることができる手段
負の数を表す

999
00:43:16,290 --> 00:43:19,530
本質的には、いずれかを使用している
を示すために、特別なビット

1000
00:43:19,530 --> 00:43:20,400
負のオーバーポジティブ。

1001
00:43:20,400 --> 00:43:22,950
それは、それよりも少し複雑だ
それは基本的な考え方です。

1002
00:43:22,950 --> 00:43:26,740
>> だから残念ながら、Cが1を混乱されている場合は
実際の意味として、これらのビットの、

1003
00:43:26,740 --> 00:43:30,790
ああ、これが、私のループ負の数である
ここで、例えば、実際になることはありません

1004
00:43:30,790 --> 00:43:31,740
終了する予定。

1005
00:43:31,740 --> 00:43:33,850
私は実際に何かを印刷していたのであれば
何度も何度も、我々はだろう

1006
00:43:33,850 --> 00:43:34,650
全体の多くを参照してください。

1007
00:43:34,650 --> 00:43:36,220
しかし、再び、この点以外にある。

1008
00:43:36,220 --> 00:43:38,590
これは本当にただの一種である
私たちが来ることを知的好奇心

1009
00:43:38,590 --> 00:43:39,550
最終的にバックアップします。

1010
00:43:39,550 --> 00:43:43,400
しかし、今のところ、これは正しいです
我々は仮定した場合の実装

1011
00:43:43,400 --> 00:43:45,970
ユーザが整数を提供する
そのint型に収まる。

1012
00:43:45,970 --> 00:43:49,370
>> しかし、私は率直に言って、そのコードを主張する、
そんなにより簡単に行うことができます。

1013
00:43:49,370 --> 00:43:54,060
手元の目標は数字を取るのであれば
のような、mとのすべてを追加

1014
00:43:54,060 --> 00:43:59,510
それは1、あるいは逆の数字
1間と、私が主張

1015
00:43:59,510 --> 00:44:03,380
私はマージこのアイデアを借りることができます
ソートは、問題を取った、持っていた

1016
00:44:03,380 --> 00:44:05,660
このサイズの、それを割る
小さいものに。

1017
00:44:05,660 --> 00:44:09,875
多分半分が、小さくないが、
代表的に同じ。

1018
00:44:09,875 --> 00:44:12,130
同じ考えですが、小さい問題。

1019
00:44:12,130 --> 00:44:15,470
>> だから私は、実際にしている - 私は、このファイルを保存してみましょう
異なるバージョン番号を持つ。

1020
00:44:15,470 --> 00:44:17,670
私たちは、このバージョンを呼ぶことにします
1の代わりに0。

1021
00:44:17,670 --> 00:44:20,790
そして私は私が実際にできることを主張
この種でこれを再実装

1022
00:44:20,790 --> 00:44:22,160
心曲げ方法。

1023
00:44:22,160 --> 00:44:23,710
>> 私は一人でその一部を残すつもりです。

1024
00:44:23,710 --> 00:44:27,710
mが小さければ私は言うつもりです
0に等しい以上、あるいは - 

1025
00:44:27,710 --> 00:44:29,280
私はほんの少しになるつもりです
もっと肛門今回

1026
00:44:29,280 --> 00:44:30,520
 - 私のエラーチェックと

1027
00:44:30,520 --> 00:44:33,190
私が先に行くと0を返すつもりです。

1028
00:44:33,190 --> 00:44:34,490
これは任意である。

1029
00:44:34,490 --> 00:44:37,500
私は、単にユーザかどうかを決定しています
私に負の数を与え、私はよ

1030
00:44:37,500 --> 00:44:41,490
0を返します、そして、彼らは読んだことがあるはず
ドキュメントをより密接に。

1031
00:44:41,490 --> 00:44:42,170
>> 他の - 

1032
00:44:42,170 --> 00:44:44,070
私がやろうとしているものに気づく。

1033
00:44:44,070 --> 00:44:49,260
他の私は、Mプラスを返すつもりです - 

1034
00:44:49,260 --> 00:44:51,010
Mのシグマは何ですか？

1035
00:44:51,010 --> 00:44:56,710
まあ、MプラスMマイナス1シグマ、
プラスMマイナス2、プラスマイナス3メートル。

1036
00:44:56,710 --> 00:44:58,030
私は、そのうちのすべてを記述する必要はありません。

1037
00:44:58,030 --> 00:44:59,120
なぜ私はちょうどパントませんか？

1038
00:44:59,120 --> 00:45:05,080
再帰的に少し自分自身を呼び出す
小さい問題、セミコロン、

1039
00:45:05,080 --> 00:45:06,840
その日を呼び出す？

1040
00:45:06,840 --> 00:45:07,040
>> 右？

1041
00:45:07,040 --> 00:45:10,980
今ここでは、あまりにも、あなたが感じたり、心配かもしれません
これは私がだと無限ループであること

1042
00:45:10,980 --> 00:45:15,450
私が実装していますそれによって誘導、
呼び出しシグマによってシグマ。

1043
00:45:15,450 --> 00:45:20,342
しかし、それは私がいるので、完全にOKだ
どの行を追加先にと思った？

1044
00:45:20,342 --> 00:45:22,600
>> 読者：[聞こえない]。

1045
00:45:22,600 --> 00:45:25,430
>> DAVIDマラン：23から26、その
私の場合の条件です。

1046
00:45:25,430 --> 00:45:28,390
についての素晴らしい何ので
私は続けるので、ここで減算、

1047
00:45:28,390 --> 00:45:31,180
小さく、シグマより小さい問題を渡す
問題は、小さい - そうではありません

1048
00:45:31,180 --> 00:45:31,870
半分のサイズ。

1049
00:45:31,870 --> 00:45:34,380
それは、小さいだけで赤ちゃんの一歩だ
それはOKです。

1050
00:45:34,380 --> 00:45:38,050
結局、我々はうまくいくので
ダウンして1または0に我々の方法。

1051
00:45:38,050 --> 00:45:41,630
そして、かつて我々は0を打つ、シグマではありません
もはや自分自身を呼び出すつもり。

1052
00:45:41,630 --> 00:45:43,590
それはすぐに0を返すようになるだろう。

1053
00:45:43,590 --> 00:45:47,960
>> だから効果は、風のソートこの場合
まであなたの心に、Mプラスを追加することです

1054
00:45:47,960 --> 00:45:52,740
Mマイナス1、プラスMマイナス2、プラスMマイナス
3、プラスドット、ドット、ドット、mはマイナス

1055
00:45:52,740 --> 00:45:57,820
最終的に0と与え、M、
効果は、すべてのを追加するには最終的にある

1056
00:45:57,820 --> 00:45:59,070
一緒にこれらの事。

1057
00:45:59,070 --> 00:46:02,380
だから私たちは、再帰ではなく、持っている
我々はその問題解決

1058
00:46:02,380 --> 00:46:03,470
前に解決することができませんでした。

1059
00:46:03,470 --> 00:46:06,840
確かに、このバージョンの0、およびすべての
これまでの問題は、解決可能であった

1060
00:46:06,840 --> 00:46:09,980
単にループを使用してまたはwhile
ループまたは類似の構造物。

1061
00:46:09,980 --> 00:46:13,150
>> しかし、再帰が、私はあえて、私たちを与える
について考える別の方法

1062
00:46:13,150 --> 00:46:17,010
問題は、それによって我々が取ることができる場合
問題は、何かからそれを分ける

1063
00:46:17,010 --> 00:46:22,340
何かにやや大きいやや
小さく、私たちはそれを解決することができていると主張

1064
00:46:22,340 --> 00:46:26,040
おそらく、もう少しエレガントに言葉で
デザインの、少ないコードで、

1065
00:46:26,040 --> 00:46:30,980
そして多分だろうな問題を解決
我々は最終的に説明するように、難しくなる

1066
00:46:30,980 --> 00:46:33,280
純粋に反復して解く、を参照してください。

1067
00:46:33,280 --> 00:46:35,980
>> 私がしたことしかし接戦
上で私たちを残したいのはこれだった。

1068
00:46:35,980 --> 00:46:40,720
私が先に行くと、開いてみよう
からファイルをバックアップします - 

1069
00:46:40,720 --> 00:46:44,300
実際に、私が手放すと
この本当の高速を行う。

1070
00:46:44,300 --> 00:46:46,875
私が先に行くと提案してみましょう
次。

1071
00:46:46,875 --> 00:46:51,160

1072
00:46:51,160 --> 00:46:54,785
今日のコードの中では、このファイルはここにあります。

1073
00:46:54,785 --> 00:47:01,090

1074
00:47:01,090 --> 00:47:03,050
ここではこのいずれか、NOSWAP。

1075
00:47:03,050 --> 00:47:06,260
>> だから、これはその愚かな小さなプログラムです。
私は、クレームがすることを手早く

1076
00:47:06,260 --> 00:47:06,940
次。

1077
00:47:06,940 --> 00:47:10,140
メインでは、それは最初に宣言しています
int型は、Xと呼ばれ、それを割り当て

1078
00:47:10,140 --> 00:47:11,100
1の値。

1079
00:47:11,100 --> 00:47:13,520
それはint型、yを宣言し、
それに値2を割り当てます。

1080
00:47:13,520 --> 00:47:15,310
それは、xとyが何であるかを出力します。

1081
00:47:15,310 --> 00:47:17,781
それは、ドットドットドットを交換、と言います。

1082
00:47:17,781 --> 00:47:21,670
>> それは関数を呼び出すことが主張
Xを渡し、スワップと呼ばれ、

1083
00:47:21,670 --> 00:47:24,290
yは、そのうまくなっているという考え方
xとyは戻ってくるだろう

1084
00:47:24,290 --> 00:47:25,620
反対に、異なる。

1085
00:47:25,620 --> 00:47:27,110
それはスワップ主張！

1086
00:47:27,110 --> 00:47:28,420
感嘆符が付いた。

1087
00:47:28,420 --> 00:47:30,190
それは、xとyを出力します。

1088
00:47:30,190 --> 00:47:33,480
>> しかし、それはまさにこのことが判明
簡単なデモダウン

1089
00:47:33,480 --> 00:47:35,570
ここでは実際にバグがある。

1090
00:47:35,570 --> 00:47:38,870
私は一時的に宣言しているにもかかわらず
変数と一時的に入れて

1091
00:47:38,870 --> 00:47:42,010
それは、私は再割り当てしています
bの値 - 

1092
00:47:42,010 --> 00:47:45,080
その私がきたので、合理的な感じ
温度でのコピーを保存した。

1093
00:47:45,080 --> 00:47:48,410
それから私は平等に、Bを更新
一時にどんなだった。

1094
00:47:48,410 --> 00:47:51,610
移動のシェルゲームのこの種
BとBににこれを使用することにより

1095
00:47:51,610 --> 00:47:54,360
気温が感じると呼ばれる中年の男
完全に合理的。

1096
00:47:54,360 --> 00:47:57,270
>> 私はこれを実行したときにしかし、私はあることを主張
コー​​ドは、私は今やるとして - 

1097
00:47:57,270 --> 00:47:59,490
私が先に行くと、ここに貼り付けましょう。

1098
00:47:59,490 --> 00:48:01,995
私はこのnoswap.cと呼ぶことにします。

1099
00:48:01,995 --> 00:48:05,630
名前が示すようにと、これではありません
正しいプログラムになるだろう。

1100
00:48:05,630 --> 00:48:09,460
NOSWAP。/いいえスワップを行いません。

1101
00:48:09,460 --> 00:48:12,110
xは1であり、yが2であり、スワッピング、スワップ。

1102
00:48:12,110 --> 00:48:14,220
xは1であり、yは2である。

1103
00:48:14,220 --> 00:48:16,920
これがあっても、根本的に間違っている
これは完全にそうですけれども

1104
00:48:16,920 --> 00:48:17,730
私には合理的。

1105
00:48:17,730 --> 00:48:21,330
そして、そこに理由がありますが、私たちではない
ただまだその理由を明らかにする予定。

1106
00:48:21,330 --> 00:48:24,610
>> 私が欲しかった第二接戦今のところ
を残すためには、これです

1107
00:48:24,610 --> 00:48:27,120
クーポンコードの一種のアナウンス。

1108
00:48:27,120 --> 00:48:31,590
遅い日と私たちの技術革新は、今年
非自明な番号を引き起こしている

1109
00:48:31,590 --> 00:48:33,830
質問の、どのだった
なく、私たちの意思。

1110
00:48:33,830 --> 00:48:36,590
これらのクーポンコードの意図、
それによってあなたは、問題の一部を行う場合

1111
00:48:36,590 --> 00:48:39,850
、それによって余分な日を取得、早期に設定する
君たちが助けて支援する実際にあった

1112
00:48:39,850 --> 00:48:42,420
自分では、早期のソートを開始
あなたを奨励することである。

1113
00:48:42,420 --> 00:48:44,880
私たちは全体の負荷を分散させるのに役立ちます
営業時間は、より良いように

1114
00:48:44,880 --> 00:48:45,740
それは、win-winのようなものです。

1115
00:48:45,740 --> 00:48:48,860
>> 残念ながら、私は私の指示だと思います
そう、今日まで、非常に明確ではなかった

1116
00:48:48,860 --> 00:48:52,230
私はこの週末に戻って、更新され
に大きく、大胆なテキストでスペック

1117
00:48:52,230 --> 00:48:53,600
これらのような弾丸を説明します。

1118
00:48:53,600 --> 00:48:56,900
そして、ちょうどすることにより、より多くの公的にそれを言うために
デフォルトでは、問題セットは木曜日によるものである

1119
00:48:56,900 --> 00:48:58,400
正午に、シラバス当たり。

1120
00:48:58,400 --> 00:49:02,030
あなたの一部を終え、早期に開始した場合
12:00水曜日まで設定問題

1121
00:49:02,030 --> 00:49:05,170
PM、クーポンに関し、一部
コー​​ドは、アイデアは、あなたが拡張できるということです

1122
00:49:05,170 --> 00:49:07,710
については、締め切り
Pは金曜日までセット。

1123
00:49:07,710 --> 00:49:10,890
そのビットPの小さな部分から、ある
一般的に何であるかを基準に設定する

1124
00:49:10,890 --> 00:49:13,200
大きな問題は、あなたが買う
自分で余分な日。

1125
00:49:13,200 --> 00:49:15,190
繰り返しになりますが、それは考えるあなたを取得
問題セットにあなたを取得

1126
00:49:15,190 --> 00:49:16,380
営業時間は早くなります。

1127
00:49:16,380 --> 00:49:20,670
しかし、クーポンコードの問題がまだある
あなたがそれを提出しない場合でも、必要とした。

1128
00:49:20,670 --> 00:49:23,340
>> しかし、もっと説得力これです。

1129
00:49:23,340 --> 00:49:26,520
（STAGEウィスパー）そして、それらの人々が残し
早期にそれを後悔するつもりです。

1130
00:49:26,520 --> 00:49:28,620
としてバルコニーに人々がいます。

1131
00:49:28,620 --> 00:49:32,510
上の人々に、事前に私に謝罪
なりの理由でバルコニー

1132
00:49:32,510 --> 00:49:33,920
ほんの一瞬でクリア。

1133
00:49:33,920 --> 00:49:37,050
>> だから私たちは、次のいずれかを持っている幸運です
CS50の元頭ティーチングフェローで

1134
00:49:37,050 --> 00:49:39,302
dropbox.comという会社。

1135
00:49:39,302 --> 00:49:45,500
彼らは非常に寛大に寄付しています
このくらいのスペースはこちらのクーポンコード、

1136
00:49:45,500 --> 00:49:48,180
からなる次第です
いつもの2ギガバイト。

1137
00:49:48,180 --> 00:49:51,740
だから私たちは、この上で行うだろうと思ったのか
最後のノートでは、景品のビットを行うさ

1138
00:49:51,740 --> 00:49:55,380
ほんの一瞬では、我々は明らかにすることにより、
勝者と誰がクーポンを持っている

1139
00:49:55,380 --> 00:49:57,980
あなたがして、それらに行くことができることをコード
ウェブサイトでそれを入力し、出来上がりは、取得

1140
00:49:57,980 --> 00:50:01,370
あなたのための全体の多くのDropboxの容量
アプライアンスとあなたの個人的なファイルのために。

1141
00:50:01,370 --> 00:50:05,690
>> と参加したいと思います最初は、
この図では？

1142
00:50:05,690 --> 00:50:09,630
[OK]を、今ではそれはそれはさらに楽しくなります。

1143
00:50:09,630 --> 00:50:14,010
この25ギガバイトを受ける者
クーポンコード - 遠いです

1144
00:50:14,010 --> 00:50:16,150
後半よりも説得力のある
今、おそらく日 - 

1145
00:50:16,150 --> 00:50:20,620
の上部に装着されているものである
が存在する下シートクッション

1146
00:50:20,620 --> 00:50:21,620
そのクーポンコード。

1147
00:50:21,620 --> 00:50:23,480
あなたは今、下に見えるかもしれません
あなたのシートクッション。

1148
00:50:23,480 --> 00:50:28,710

1149
00:50:28,710 --> 00:50:29,680
>> [ビデオの再生]

1150
00:50:29,680 --> 00:50:31,620
>>  -  1つ、2つ、3つ。

1151
00:50:31,620 --> 00:50:35,015
>> [SCREAMING]

1152
00:50:35,015 --> 00:50:35,985
>>  - あなたは車を取得！

1153
00:50:35,985 --> 00:50:36,670
あなたは車を入手！

1154
00:50:36,670 --> 00:50:37,970
>> DAVIDマラン：我々は、表示されます
水曜日にあなた。

1155
00:50:37,970 --> 00:50:38,904
>>  - あなたは車を取得！

1156
00:50:38,904 --> 00:50:39,371
あなたは車を入手！

1157
00:50:39,371 --> 00:50:40,305
あなたは車を入手！

1158
00:50:40,305 --> 00:50:41,706
あなたは車を入手！

1159
00:50:41,706 --> 00:50:43,107
あなたは車を入手！

1160
00:50:43,107 --> 00:50:45,530
>> DAVIDマラン：バルコニー人々は、来る
ダウンここでフロントに、

1161
00:50:45,530 --> 00:50:46,866
どこに私たちは余分を持っている。

1162
00:50:46,866 --> 00:50:50,282
>>  - 誰もが車を取得！

1163
00:50:50,282 --> 00:50:52,234
誰もが車を取得！

1164
00:50:52,234 --> 00:50:52,722
>> [ENDビデオ再生]

1165
00:50:52,722 --> 00:50:54,590
>> ナレーター：次CS50で - 

1166
00:50:54,590 --> 00:51:00,374
>> SPEAKER 5：おやっおやっおやっおやっ私のああ
おやっおやっおやっおやっおやっおやっ - 

1167
00:51:00,374 --> 00:51:02,106
>> [ウクレレPLAYS]