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

2
00:00:11,904 --> 00:00:12,910
>> 教授：すべての権利。

3
00:00:12,910 --> 00:00:16,730
これはCS50であり、これは
週3の終わり。

4
00:00:16,730 --> 00:00:20,230
だから我々はないサンダースに、今日ここにいます
代わりにWeidnerライブラリの劇場、。

5
00:00:20,230 --> 00:00:23,170
これの内部スタジオ
ハウザーメーカーとして知られています、

6
00:00:23,170 --> 00:00:28,310
または私達はメーカーHを言う、または条ばなりません
あなたがそのジョークを楽しんでいる場合、私たちは、say--

7
00:00:28,310 --> 00:00:30,540
それから、実際のです
同級生、マーク、オンライン、

8
00:00:30,540 --> 00:00:32,420
誰がTwitterでできるだけ多くを示唆しました。

9
00:00:32,420 --> 00:00:34,270
今は約クールなものです
スタジオでここにいます

10
00:00:34,270 --> 00:00:38,410
私はこれらの緑に囲まれているということです
壁、グリーンスクリーンやクロマキー、

11
00:00:38,410 --> 00:00:43,290
そうCS50のことを意味し、話すこと
私には知られていない制作チーム、

12
00:00:43,290 --> 00:00:47,380
今、パッティングすることができ
私ほとんどの世界のどこかで、

13
00:00:47,380 --> 00:00:48,660
良くも悪くもため。

14
00:00:48,660 --> 00:00:51,800
>> 今どのような問題が設定され、待ち受け
二人は、この一週間のためにあなたの手の中にあります

15
00:00:51,800 --> 00:00:53,830
しかし、問題に設定
3この来週、

16
00:00:53,830 --> 00:00:56,600
あなたが挑戦されます
15のいわゆるゲーム、

17
00:00:56,600 --> 00:00:58,960
その古いパーティーの好意
あなたが受信思い出すかもしれません

18
00:00:58,960 --> 00:01:02,030
全体の束を持っている子として
上下にスライドできる数の、

19
00:01:02,030 --> 00:01:05,790
左右、および1つのギャップがあります
パズルの中、あなたのその中に

20
00:01:05,790 --> 00:01:07,840
実際に、これらのパズルのピースをスライドさせることができます。

21
00:01:07,840 --> 00:01:11,150
最終的にあなたがこれを受け取ります
いくつかのセミランダムな順序でパズル、

22
00:01:11,150 --> 00:01:12,940
そして目標はです
ソートそれ、上から下へ、

23
00:01:12,940 --> 00:01:16,310
1から、左から右へ
最大15までのすべての方法。

24
00:01:16,310 --> 00:01:19,360
>> 残念ながら、実装
あなたは手元にあります

25
00:01:19,360 --> 00:01:21,590
ソフトウェアになるだろう
ベースではなく、物理的に。

26
00:01:21,590 --> 00:01:25,280
あなたが実際に書き込みする必要があるとしています
コー​​ドを使用して、学生やユーザ缶

27
00:01:25,280 --> 00:01:26,760
15のゲームをプレイ。

28
00:01:26,760 --> 00:01:29,030
そして、実際には、ハッカーで
15のゲームの版、

29
00:01:29,030 --> 00:01:32,155
あなたが実装することが課題になるだろう、
この古い学校だけではなく演奏

30
00:01:32,155 --> 00:01:35,010
ゲームではなく、解決
それを、神モードを実装し、

31
00:01:35,010 --> 00:01:38,280
その結果、実際に、話すこと
人間のためのパズルを解き、

32
00:01:38,280 --> 00:01:41,080
ヒントを提供することにより、
ヒント後に、ヒントの後。

33
00:01:41,080 --> 00:01:42,280
だから、より多くのその次の週に。

34
00:01:42,280 --> 00:01:43,720
しかし、それは先にあるものです。

35
00:01:43,720 --> 00:01:47,610
>> 今のことを思い出して、今週初めに
あなたがする場合は、我々は、この接戦を持っていました、

36
00:01:47,610 --> 00:01:52,560
それによって私たちはソートしていた最高の
賢明は、nのO大の上限でした

37
00:01:52,560 --> 00:01:53,210
乗。

38
00:01:53,210 --> 00:01:56,520
換言すれば、バブルソート、
選択ソート、挿入ソート、

39
00:01:56,520 --> 00:01:59,120
それらのすべて、異なるしばらく
それらの実装において、

40
00:01:59,120 --> 00:02:03,480
実行中の乗n個に権限を委譲
非常に最悪の場合の時間。

41
00:02:03,480 --> 00:02:06,010
そして、我々は一般的にあると仮定
ソートするための非常に最悪のケース

42
00:02:06,010 --> 00:02:08,814
そのあなたの入力の一つです
完全に後ろ向きになります。

43
00:02:08,814 --> 00:02:11,980
そして実際、それは非常にいくつかの手順を取りました
これらのアルゴリズムのそれぞれを実装します。

44
00:02:11,980 --> 00:02:15,110
>> 今クラスの最後に
リコール、我々はバブルソートを比較しました

45
00:02:15,110 --> 00:02:19,390
他の1に対して選択ソートに対する
我々は一度にマージソートと呼ばれています、

46
00:02:19,390 --> 00:02:22,120
私はそれが取っていることを提案します
週のレッスンの利点

47
00:02:22,120 --> 00:02:24,060
ゼロ、分割統治。

48
00:02:24,060 --> 00:02:28,810
そしてどういうわけかのいくつかの種類を達成
対数最終的に時間を実行して、

49
00:02:28,810 --> 00:02:31,024
代わりに何かの
それは純粋に二次です。

50
00:02:31,024 --> 00:02:33,440
そしてそれは、かなり対数ではありません
それはそれよりもう少しです。

51
00:02:33,440 --> 00:02:36,520
しかし、あなたはクラスから思い出すと、
それははるかに速く、はるかにました。

52
00:02:36,520 --> 00:02:38,210
我々は中断した場所を見てみましょう。

53
00:02:38,210 --> 00:02:41,880

54
00:02:41,880 --> 00:02:45,370
>> 選択対バブルソート
ソートマージソート対。

55
00:02:45,370 --> 00:02:47,700
今、彼らはすべての中で、実行しています
理論、同時に。

56
00:02:47,700 --> 00:02:50,510
CPUが同じ速度で実行されています。

57
00:02:50,510 --> 00:02:54,990
しかし、あなたはこれをどのように退屈を感じることができます
非常に迅速になろうと、

58
00:02:54,990 --> 00:02:58,790
そしてどれだけ速く、我々は注入時
0週目のアルゴリズムのビット、

59
00:02:58,790 --> 00:03:00,080
我々は物事をスピードアップすることができます。

60
00:03:00,080 --> 00:03:01,630
>> だからマークソートは素晴らしい見えます。

61
00:03:01,630 --> 00:03:05,220
どのように我々は、順番に、それを活用することができます
より迅速に数字を並べ替えることができます。

62
00:03:05,220 --> 00:03:07,140
まあさんが戻って考えてみましょう
我々成分に

63
00:03:07,140 --> 00:03:10,380
のことを、週にゼロに戻っていました
電話帳の誰かを探して、

64
00:03:10,380 --> 00:03:12,380
そして、思い出し
私たちが提案した擬似コード、

65
00:03:12,380 --> 00:03:14,560
これを介して、我々は見つけることができます
マイク・スミスのような人、

66
00:03:14,560 --> 00:03:16,310
このような小さなものを見ました。

67
00:03:16,310 --> 00:03:20,820
>> 今、特に見てみましょう
ラインで7,8、および10と11、

68
00:03:20,820 --> 00:03:25,240
我々が保持することによりれ、そのループを誘導
再び3行目に行くと、再び、

69
00:03:25,240 --> 00:03:26,520
そして再び。

70
00:03:26,520 --> 00:03:31,790
しかし、それは私たちが見ることができることが判明しました
このアルゴリズムは、ここで擬似コードで、

71
00:03:31,790 --> 00:03:33,620
もう少し全体的に。

72
00:03:33,620 --> 00:03:35,960
実際に、私は何を探しています
ここで、画面上で、

73
00:03:35,960 --> 00:03:41,180
検索するためのアルゴリズムであります
ページのいくつかのセットの中マイク・スミス。

74
00:03:41,180 --> 00:03:45,520
そして実際、我々はこれを簡素化することができ
これらの行7と8で、アルゴリズム、

75
00:03:45,520 --> 00:03:49,860
10と11は、ちょうど、これを言って
これは私が黄色でここに提示しました。

76
00:03:49,860 --> 00:03:52,210
換言すれば、マイク
スミスは、以前の本の中で、

77
00:03:52,210 --> 00:03:55,004
私たちはステップを指定する必要はありません
ステップによって、今どのように彼を見つける行きます。

78
00:03:55,004 --> 00:03:56,920
私たちは、指定する必要はありません
3行目に戻って、

79
00:03:56,920 --> 00:03:58,960
なぜ我々はだけではなく、しません、
たとえば、より一般的には、

80
00:03:58,960 --> 00:04:01,500
にマイクを検索
本の左半分。

81
00:04:01,500 --> 00:04:03,960
>> 逆に、マイクがある場合
実際、後に本の中で、

82
00:04:03,960 --> 00:04:07,540
私達はちょうど引用終わり検索を引用していない理由
本の右半分にマイク用。

83
00:04:07,540 --> 00:04:11,030
つまり、なぜ私たちはしません
自分が言うのとパントの並べ替え、

84
00:04:11,030 --> 00:04:13,130
この中にはマイクを検索
本のサブセット、

85
00:04:13,130 --> 00:04:16,279
私たちの既存のに任せます
私たちに伝えるためのアルゴリズム

86
00:04:16,279 --> 00:04:18,750
マイクでの検索方法
この本の左半分。

87
00:04:18,750 --> 00:04:20,750
言い換えれば、私たちの
このアルゴリズムは、それが動作するかどうかです

88
00:04:20,750 --> 00:04:24,670
こののこの厚さの電話帳、
厚さ、またはいかなる厚さ。

89
00:04:24,670 --> 00:04:27,826
だから我々は再帰的にすることができます
このアルゴリズムを定義します。

90
00:04:27,826 --> 00:04:29,950
言い換えれば、上
ここで画面は、アルゴリズムであります

91
00:04:29,950 --> 00:04:33,130
マイク・スミスを検索します
電話帳のページ間。

92
00:04:33,130 --> 00:04:37,410
だから、7行目および10に、してみましょう
まさにそればかり言います。

93
00:04:37,410 --> 00:04:40,250
そして、私はこの言葉の瞬間を使用
前、実際、再帰

94
00:04:40,250 --> 00:04:42,450
今の流行語であり、
それは、このプロセスです

95
00:04:42,450 --> 00:04:47,210
何とかによって周期的な何かをすることの
あなたが既に持っているコードを使用して、

96
00:04:47,210 --> 00:04:49,722
そして、それを再び呼び出します
そして再び、そして再び。

97
00:04:49,722 --> 00:04:51,930
今では重要になるだろう
我々は何とか底こと

98
00:04:51,930 --> 00:04:53,821
アウト、無限に長いことはしてはいけません。

99
00:04:53,821 --> 00:04:56,070
そうでなければ我々はするつもりです
確かに無限ループを持っています。

100
00:04:56,070 --> 00:04:59,810
しかし、我々はこのアイデアを借りることができるかどうかを見てみましょう
再帰の、再び何かをすること

101
00:04:59,810 --> 00:05:03,600
そして、何度も何度も、解決するために
マージソート経由問題

102
00:05:03,600 --> 00:05:05,900
並べ替え、すべてのより効率的に。

103
00:05:05,900 --> 00:05:06,970
>> だから私は、あなたがマージソート与えます。

104
00:05:06,970 --> 00:05:07,920
のは、見てみましょう。

105
00:05:07,920 --> 00:05:10,850
そこでここでは擬似コードとは
私たちは、ソートを実装する可能性があります、

106
00:05:10,850 --> 00:05:12,640
マージソートと呼ばれるこのアルゴリズムを使用して。

107
00:05:12,640 --> 00:05:13,880
そしてそれは非常に単純にこれです。

108
00:05:13,880 --> 00:05:15,940
n個の要素の入力時に、
言い換えれば、あなたがしている場合

109
00:05:15,940 --> 00:05:18,830
与えられたn個の要素と数字と
入力されたか、どのような文字、

110
00:05:18,830 --> 00:05:22,430
あなたはn個の要素、もし与えられている場合
nが2未満である、単に返します。

111
00:05:22,430 --> 00:05:22,930
右？

112
00:05:22,930 --> 00:05:26,430
なお、nが2未満であれば理由
つまり、要素の私のリスト

113
00:05:26,430 --> 00:05:30,446
サイズ0または1のいずれかであり、かつ
これらのささいな例の両方で、

114
00:05:30,446 --> 00:05:31,570
リストはすでにソートされています。

115
00:05:31,570 --> 00:05:32,810
リストがない場合は、ソートされています。

116
00:05:32,810 --> 00:05:35,185
そして、長さのリストがあるかどうか
図1に示すように、それは明らかにソートします。

117
00:05:35,185 --> 00:05:38,280
だから、このアルゴリズムは、次の目的にのみ必要
本当に面白い何かをします、

118
00:05:38,280 --> 00:05:40,870
我々は2つ​​以上を有する場合
私たちに与えられた要素。

119
00:05:40,870 --> 00:05:42,440
それでは、次に、魔法を見てみましょう。

120
00:05:42,440 --> 00:05:47,500
それ以外の要素の左半分を並べ替えます、
その後、要素の右半分を並べ替えます、

121
00:05:47,500 --> 00:05:49,640
その後、ソートされた半分をマージします。

122
00:05:49,640 --> 00:05:52,440
曲げ心のようなものは何ですか
ここで、私は本当にないことです

123
00:05:52,440 --> 00:05:56,190
あなたに言っているように見えます
まだ何も、右か？

124
00:05:56,190 --> 00:05:59,560
すべての私は、のリストを与えられて言いました
n個の要素は、左半分を並べ替えます、

125
00:05:59,560 --> 00:06:01,800
右半分は、
ソート半分をマージし、

126
00:06:01,800 --> 00:06:03,840
しかし、ここで実際の秘密のソースは何ですか？

127
00:06:03,840 --> 00:06:05,260
アルゴリズムはどこですか？

128
00:06:05,260 --> 00:06:09,150
まあそれは、これらの二行ことが判明
まず、素子の一種左半分

129
00:06:09,150 --> 00:06:13,970
要素のソート右半分、
再帰呼び出しがあり、いわば。

130
00:06:13,970 --> 00:06:16,120
>> 結局、この時
時点、私が持っています

131
00:06:16,120 --> 00:06:18,950
へとアルゴリズム
要素の全体の束を並べ替えますか？

132
00:06:18,950 --> 00:06:19,450
はい。

133
00:06:19,450 --> 00:06:20,620
それはここです。

134
00:06:20,620 --> 00:06:25,180
これは、画面上で右ここだし、
私はステップの同じセットを使用することができます

135
00:06:25,180 --> 00:06:28,500
左半分をソートするには、
私は右半分できますように。

136
00:06:28,500 --> 00:06:30,420
そして実際、再び、そして再び。

137
00:06:30,420 --> 00:06:34,210
だから、どうやら、私たちはすぐによ
この、マージソートの魔法を見ます

138
00:06:34,210 --> 00:06:37,967
その非常に最終的に埋設されています
ライン、ソートされた半分をマージします。

139
00:06:37,967 --> 00:06:39,300
そして、それはかなり直感的なようです。

140
00:06:39,300 --> 00:06:41,050
あなたは、あなたを半分ずつを取り、
何とか、それらを一緒にマージし、

141
00:06:41,050 --> 00:06:43,260
私たちはこれを参照してくださいよ
具体的瞬間インチ

142
00:06:43,260 --> 00:06:45,080
>> しかし、これは完全なアルゴリズムです。

143
00:06:45,080 --> 00:06:46,640
そしてのは、正確な理由を見てみましょう。

144
00:06:46,640 --> 00:06:50,912
さて、我々はこれらの同じを与えられていると仮定
画面上でここに8要素、1

145
00:06:50,912 --> 00:06:53,120
8を介して、しかし、彼らはしています
一見ランダムなためです。

146
00:06:53,120 --> 00:06:55,320
そして、手元の目標です
これらの要素をソートします。

147
00:06:55,320 --> 00:06:58,280
さてどのように私は約行くことができます
再び、使用してそれをやって、

148
00:06:58,280 --> 00:07:00,407
この擬似コードごとに、マージソート？

149
00:07:00,407 --> 00:07:02,740
そして再び、この中に深く根付きました
あなたの心、ちょっと。

150
00:07:02,740 --> 00:07:05,270
最初のケースはかなりあります
些細な、それが2未満だと、

151
00:07:05,270 --> 00:07:07,060
ただなすべき仕事は決してありません、戻ります。

152
00:07:07,060 --> 00:07:09,290
だから、実際には3あります
本当に心に留めておくべき手順。

153
00:07:09,290 --> 00:07:11,081
ここでも、再度、私は
持つようにするつもり

154
00:07:11,081 --> 00:07:13,980
左半分をソートするには、
右半分を並べ替えます、

155
00:07:13,980 --> 00:07:15,890
して、その一回
二つの半分は、ソートされています

156
00:07:15,890 --> 00:07:18,710
私はそれらを一緒にマージしたいです
1ソートされたリストに。

157
00:07:18,710 --> 00:07:19,940
だから、心の中でそれを維持します。

158
00:07:19,940 --> 00:07:21,310
>> そこでここでは、元のリストです。

159
00:07:21,310 --> 00:07:23,510
それでは、としてこれを扱いましょう
配列、我々が始めました

160
00:07:23,510 --> 00:07:25,800
2週では、これは
メモリの連続ブロック。

161
00:07:25,800 --> 00:07:28,480
この場合には、8つを含みます
数字は、背中合わせにバックアップします。

162
00:07:28,480 --> 00:07:30,700
そして今度は、マージソートを適用してみましょう。

163
00:07:30,700 --> 00:07:33,300
だから私は最初にソートしたいです
このリストの左半分、

164
00:07:33,300 --> 00:07:37,370
、したがって、してみましょう
4、8,6、および2に焦点を当てます。

165
00:07:37,370 --> 00:07:41,000
>> 今どのように私は約行きます
サイズ4のリストをソートしますか？

166
00:07:41,000 --> 00:07:45,990
さて、私は今考えなければなりません
左半分の左を並べ替え。

167
00:07:45,990 --> 00:07:47,720
ここでも、のはちょっと巻き戻してみましょう。

168
00:07:47,720 --> 00:07:51,010
擬似コードは、これである場合、
私は、8つの要素が与えられています、

169
00:07:51,010 --> 00:07:53,230
8は明らかに大きく、
よりまたは2に等しいです。

170
00:07:53,230 --> 00:07:54,980
だから、最初のケースでは適用されません。

171
00:07:54,980 --> 00:07:58,120
だから、最初の8つの要素は、私をソートします
要素の左半分を並べ替えます

172
00:07:58,120 --> 00:08:01,930
私は、私は、マージ、右半分を並べ替えます
2つのソートの半分、サイズ4の各。

173
00:08:01,930 --> 00:08:02,470
OK。

174
00:08:02,470 --> 00:08:07,480
>> しかし、あなたはちょうど私に言ってきた場合には、並べ替えます
今サイズ4である左半分、

175
00:08:07,480 --> 00:08:09,350
どのように私は左半分を並べ替えるのですか？

176
00:08:09,350 --> 00:08:11,430
さて、私が持っている場合
四つの要素の入力、

177
00:08:11,430 --> 00:08:14,590
私は最初の左を並べ替えます
2、右2、

178
00:08:14,590 --> 00:08:16,210
そして私はそれらを一緒にマージされます。

179
00:08:16,210 --> 00:08:18,700
だから、再び、それは少しになります
ここでゲームを曲げ心の、

180
00:08:18,700 --> 00:08:21,450
あなたは、一種の、する必要があるため、
あなたが物語のどこにいるかを覚えて、

181
00:08:21,450 --> 00:08:23,620
しかし、一日の終わりに、
任意の数の要素が与えられ、

182
00:08:23,620 --> 00:08:25,620
あなたが最初にソートしたいです
左半分、右半分、

183
00:08:25,620 --> 00:08:26,661
その後、それらを一緒にマージされます。

184
00:08:26,661 --> 00:08:28,630
のは、まさにそれを行うために始めましょう。

185
00:08:28,630 --> 00:08:30,170
ここでは8要素の入力です。

186
00:08:30,170 --> 00:08:31,910
今、私たちはここで左半分を見ています。

187
00:08:31,910 --> 00:08:33,720
どのように私は、4つの要素をソートしていますか？

188
00:08:33,720 --> 00:08:35,610
さて、私は、最初の左半分を並べ替えます。

189
00:08:35,610 --> 00:08:37,720
今どのように私は左半分を並べ替えるのですか？

190
00:08:37,720 --> 00:08:39,419
さて、私は2つの要素を与えられてきました。

191
00:08:39,419 --> 00:08:41,240
それでは、この2つの要素をソートしてみましょう。

192
00:08:41,240 --> 00:08:44,540
2は以上
もちろん、2に等しいです。

193
00:08:44,540 --> 00:08:46,170
だから、最初のケースでは適用されません。

194
00:08:46,170 --> 00:08:49,010
>> だから私は今、左をソートする必要があり
この2つの要素の半分。

195
00:08:49,010 --> 00:08:50,870
左半分には、もちろん、わずか4です。

196
00:08:50,870 --> 00:08:54,020
それでは、どのよう私は1つの要素のリストをソートしますか？

197
00:08:54,020 --> 00:08:57,960
さて、その特別な基本ケース
トップアップ、いわば、適用されます。

198
00:08:57,960 --> 00:09:01,470
1は2未満であり、私の
リストには、実際のサイズ1のです。

199
00:09:01,470 --> 00:09:02,747
だから、僕は返します。

200
00:09:02,747 --> 00:09:03,580
私は何もしません。

201
00:09:03,580 --> 00:09:06,770
そして実際、私がしてきたことを見て
行われ、4がすでにソートされています。

202
00:09:06,770 --> 00:09:09,220
私はすでにてるよう
ここでは部分的に成功。

203
00:09:09,220 --> 00:09:11,750
>> 今では種類の愚かなようです
主張するが、それは本当ですします。

204
00:09:11,750 --> 00:09:13,700
図4は、大きさ1のリストです。

205
00:09:13,700 --> 00:09:15,090
これは、すでにソートです。

206
00:09:15,090 --> 00:09:16,270
それは左半分です。

207
00:09:16,270 --> 00:09:18,010
今、私は右半分を並べ替えます。

208
00:09:18,010 --> 00:09:22,310
私の入力は8、一つの要素であります
同様に、すでにソート。

209
00:09:22,310 --> 00:09:25,170
あまりにも、愚かな、しかし、再び、
この基本原理

210
00:09:25,170 --> 00:09:28,310
私たちは今、構築できるように起こっています
この成功したの上に。

211
00:09:28,310 --> 00:09:32,260
4は現在、8がソートされ、ソート
その最後のステップは何でしたか？

212
00:09:32,260 --> 00:09:35,330
だから、3番目と最後のステップ、任意の
リスト、リコールをソートしている時、

213
00:09:35,330 --> 00:09:38,310
二つの部分をマージすることでした、
左右。

214
00:09:38,310 --> 00:09:39,900
それでは、まさにそれをやらせます。

215
00:09:39,900 --> 00:09:41,940
私の左半分には、もちろん、4です。

216
00:09:41,940 --> 00:09:43,310
私の右半分は8です。

217
00:09:43,310 --> 00:09:44,100
>> それでは、これを実行してみましょう。

218
00:09:44,100 --> 00:09:46,410
最初に私は割り当てするつもりです
いくつかの追加のメモリ、

219
00:09:46,410 --> 00:09:48,680
私はここに表すだろうと、
ただ、二次配列として、

220
00:09:48,680 --> 00:09:49,660
それは、これをフィットするのに十分な大きさです。

221
00:09:49,660 --> 00:09:52,243
しかし、あなたは延長想像することができます
その長方形の全長、

222
00:09:52,243 --> 00:09:53,290
我々はより多くの後に必要がある場合。

223
00:09:53,290 --> 00:09:58,440
私は4取り、8、およびマージするにはどうすればよいです
サイズ1のものと二つのリスト一緒に？

224
00:09:58,440 --> 00:10:00,270
ここでは、あまりにも、非常にシンプル。

225
00:10:00,270 --> 00:10:03,300
4は、その後、最初に来る8を付属しています。

226
00:10:03,300 --> 00:10:07,130
私はソートする場合ので、
左半分、右半分、

227
00:10:07,130 --> 00:10:09,900
次にそれらの二つの部分をマージ
一緒に、ソート順で、

228
00:10:09,900 --> 00:10:11,940
4は、その後、最初に来る8を付属しています。

229
00:10:11,940 --> 00:10:15,810
>> だから、私たちも、進歩しているように見えます
私は実際の作業を行っていないのに。

230
00:10:15,810 --> 00:10:17,800
私達は物語の中でどこでも覚えています。

231
00:10:17,800 --> 00:10:19,360
私たちは、もともと8要素を取りました。

232
00:10:19,360 --> 00:10:21,480
私たちは4で左半分を、ソート。

233
00:10:21,480 --> 00:10:24,450
その後、我々は左半分をソート
2であった左半分の。

234
00:10:24,450 --> 00:10:25,270
そしてここで私達は行きます。

235
00:10:25,270 --> 00:10:26,920
私たちはそのステップで完了です。

236
00:10:26,920 --> 00:10:29,930
>> だから我々は、ソートした場合
我々は今、2の左半分

237
00:10:29,930 --> 00:10:32,130
2の右半分をソートする必要があります。

238
00:10:32,130 --> 00:10:35,710
だから2の右半分であります
ここでこれらの2つの値、6 2。

239
00:10:35,710 --> 00:10:40,620
それでは、今のサイズの入力をみましょう
図2は、その後、左半分を並べ替えると、

240
00:10:40,620 --> 00:10:42,610
右半分、その後、
それらを一緒にマージされます。

241
00:10:42,610 --> 00:10:45,722
さてどのように私は、サイズのリストを並べ替えます
1、ちょうど数6を含みますか？

242
00:10:45,722 --> 00:10:46,430
私はすでに行われています。

243
00:10:46,430 --> 00:10:48,680
サイズ1のそのリストがソートされます。

244
00:10:48,680 --> 00:10:52,140
>> 私は別のリストをソートするにはどうすればよいです
サイズ1、いわゆる右半分。

245
00:10:52,140 --> 00:10:54,690
まあそれは、あまりにも、すでにソートされています。

246
00:10:54,690 --> 00:10:56,190
数2は一人です。

247
00:10:56,190 --> 00:11:00,160
だから今、私は二つの部分を持って、左と
右、私はそれらを一緒にマージする必要があります。

248
00:11:00,160 --> 00:11:01,800
私は自分自身にいくつかの余分なスペースを与えてみましょう。

249
00:11:01,800 --> 00:11:05,580
そして、そこに2を入れ
その後、6そこに、それによって、

250
00:11:05,580 --> 00:11:10,740
そのリストを並べ替え、左右
そして最終的に、それを一緒にマージします。

251
00:11:10,740 --> 00:11:12,160
だから私は少し良い形でね。

252
00:11:12,160 --> 00:11:16,250
私は、行っているためではないよ、明らかに4、8、2、
図6は、私が欲しい最後の順序ではありません。

253
00:11:16,250 --> 00:11:20,640
しかし、私は今、その大きさ2の2つのリストを持っています
両方、それぞれ、ソートされています。

254
00:11:20,640 --> 00:11:24,580
だから今、あなたはあなたの心の中に巻き戻した場合
目、それは私たちを残しましたか？

255
00:11:24,580 --> 00:11:28,520
私はその後、8要素で開始私
、4の左半分に絞り込ま

256
00:11:28,520 --> 00:11:31,386
その後、2の左半分と、
2の右半分、

257
00:11:31,386 --> 00:11:34,510
私は左を並べ替え、したがって、終了しました
2の半分、及び2の右半分、

258
00:11:34,510 --> 00:11:37,800
ので、ここで3番目と最後のステップは何ですか？

259
00:11:37,800 --> 00:11:41,290
私は一緒にマージする必要があります
サイズ2の二つのリスト。

260
00:11:41,290 --> 00:11:42,040
それでは、先に行きましょう。

261
00:11:42,040 --> 00:11:43,940
そして、ここで画面上に、与えます
私いくつかの追加のメモリ、

262
00:11:43,940 --> 00:11:47,170
技術的にも、私がしたことに気づきます
トップアップ空白の全体の束を持って

263
00:11:47,170 --> 00:11:47,670
そこ。

264
00:11:47,670 --> 00:11:50,044
私は特にになりたい場合
効率的なスペース賢いです、

265
00:11:50,044 --> 00:11:52,960
私は要素の移動を開始できました
前後に上下。

266
00:11:52,960 --> 00:11:55,460
しかし、単に視覚的に分かりやすくするために、
私は、以下のそれを置くつもりです

267
00:11:55,460 --> 00:11:56,800
きれいなものを維持します。

268
00:11:56,800 --> 00:11:58,150
>> だから私は、サイズ2の2つのリストを持っています。

269
00:11:58,150 --> 00:11:59,770
最初のリストには、4​​と8を持っています。

270
00:11:59,770 --> 00:12:01,500
第2のリストは、2と6を有します。

271
00:12:01,500 --> 00:12:03,950
それでは、それらをマージしてみましょう
一緒にソートされたためです。

272
00:12:03,950 --> 00:12:09,910
図2は、もちろん、最初に来ます
その後4、その後6、その後8。

273
00:12:09,910 --> 00:12:12,560
そして今、我々はなっているように見えます
どこか興味深いです。

274
00:12:12,560 --> 00:12:15,720
今、私はの半分をソートしました
リスト、そして偶然、それはです

275
00:12:15,720 --> 00:12:18,650
すべての偶数が、その
、確かに、単なる偶然です。

276
00:12:18,650 --> 00:12:22,220
そして、私は今、左をソートします
半分、それは2、4、6、8だように。

277
00:12:22,220 --> 00:12:23,430
何も順不同でません。

278
00:12:23,430 --> 00:12:24,620
それは進行中のように感じています。

279
00:12:24,620 --> 00:12:26,650
>> 私はたような今では感じています
今永遠に話をされて、

280
00:12:26,650 --> 00:12:29,850
したがって、この場合に見られることを残るもの
アルゴリズムは、実際に、より効率的です。

281
00:12:29,850 --> 00:12:31,766
しかし、我々はを通じてつもりです
スーパー念入りこと。

282
00:12:31,766 --> 00:12:34,060
コンピュータは、もちろん、
そのようにそれを行うだろう。

283
00:12:34,060 --> 00:12:34,840
だから我々はどこにいますか？

284
00:12:34,840 --> 00:12:36,180
我々は、8つの要素から始まりました。

285
00:12:36,180 --> 00:12:37,840
私は4の左半分をソート。

286
00:12:37,840 --> 00:12:39,290
私はそれで行われているように見えます。

287
00:12:39,290 --> 00:12:42,535
だから今、次のステップはにあります
4の右半分を並べ替えます。

288
00:12:42,535 --> 00:12:44,410
そして、この部分は、私たちが行くことができます
もう少しを通して

289
00:12:44,410 --> 00:12:47,140
すぐに、あなたがしているものの、
ただ、巻き戻しや一時停止することを歓迎

290
00:12:47,140 --> 00:12:49,910
でそれを通して考えます
自分のペースが、何

291
00:12:49,910 --> 00:12:53,290
我々は今持っているの機会です
4上の正確な同じアルゴリズムを実行します

292
00:12:53,290 --> 00:12:54,380
異なる番号。

293
00:12:54,380 --> 00:12:57,740
>> それでは、先に行きましょう、とに焦点を当てます
私たちはここにいる右半分、。

294
00:12:57,740 --> 00:13:01,260
その左半分
右半分、そして今

295
00:13:01,260 --> 00:13:04,560
左の左半分
その右半分の半分、

296
00:13:04,560 --> 00:13:08,030
どのように私は、サイズのリストを並べ替えます
1だけ番号1を含みますか？

297
00:13:08,030 --> 00:13:09,030
これはすでに行われています。

298
00:13:09,030 --> 00:13:11,830
私は、リストのために同じことを行うにはどうすればよいです
わずか7を含むサイズ1の？

299
00:13:11,830 --> 00:13:12,840
これはすでに行われています。

300
00:13:12,840 --> 00:13:16,790
この半分のためのステップ3
これら2つの要素をマージすることです

301
00:13:16,790 --> 00:13:20,889
サイズ2、1,7の新しいリストに。

302
00:13:20,889 --> 00:13:23,180
すべてを行っているようには見えません。
それほど面白い作品。

303
00:13:23,180 --> 00:13:24,346
それでは、次に何が起こるか見てみましょう。

304
00:13:24,346 --> 00:13:29,210
私はただの左半分をソート
私の元の入力の右半分。

305
00:13:29,210 --> 00:13:32,360
今度は右の並べ替えましょう
5および3が含まれています半分、。

306
00:13:32,360 --> 00:13:35,740
それでは、再び左を見てみましょう
半分、ソート、右半分、ソート、

307
00:13:35,740 --> 00:13:39,120
そして、これらの2つを一緒にマージし、
いくつかの追加の空間に、

308
00:13:39,120 --> 00:13:41,670
3は、最初に来る5を付属しています。

309
00:13:41,670 --> 00:13:46,190
そして今、私たちはソートしています
右半分の左半分

310
00:13:46,190 --> 00:13:49,420
元の問題の、および
右半分の右半分

311
00:13:49,420 --> 00:13:50,800
元の問題の。

312
00:13:50,800 --> 00:13:52,480
3番目と最後のステップは何ですか？

313
00:13:52,480 --> 00:13:54,854
よく一緒に、これらの二つの部分をマージします。

314
00:13:54,854 --> 00:13:57,020
だから、私は自分自身いくつかを取得してみましょう
再び余分なスペースが、私は、

315
00:13:57,020 --> 00:13:58,699
トップをその予備のスペースを使用している可能性があります。

316
00:13:58,699 --> 00:14:00,490
しかし、我々は維持するつもりです
視覚的にそれは簡単。

317
00:14:00,490 --> 00:14:07,070
私は今1にマージしてみましょう、と
次に3、次に5、次に7。

318
00:14:07,070 --> 00:14:10,740
これにより、今では私を残します
元の問題の右半分

319
00:14:10,740 --> 00:14:12,840
それは完全にソートされます。

320
00:14:12,840 --> 00:14:13,662
>> だから何が残りますか？

321
00:14:13,662 --> 00:14:16,120
私が言い続けるような気が
同じものを再度、再度、

322
00:14:16,120 --> 00:14:18,700
それはの反射です
我々は再帰を使用しているという事実。

323
00:14:18,700 --> 00:14:21,050
使用方法
アルゴリズムを再度、再度、

324
00:14:21,050 --> 00:14:23,940
の小さいサブセットに
元の問題。

325
00:14:23,940 --> 00:14:27,580
だから私は今、左にソートします
元の問題の半分。

326
00:14:27,580 --> 00:14:30,847
私は右のソートされた半分を持っています
元の問題の。

327
00:14:30,847 --> 00:14:32,180
3番目と最後のステップは何ですか？

328
00:14:32,180 --> 00:14:33,590
ああ、それはマージです。

329
00:14:33,590 --> 00:14:34,480
それでは、それを行うことができます。

330
00:14:34,480 --> 00:14:36,420
それでは、いくつかの追加を割り当ててみましょう
メモリが、私の神、私たちは

331
00:14:36,420 --> 00:14:37,503
今どこにでも置くことができます。

332
00:14:37,503 --> 00:14:40,356
我々は、利用可能なので、多くのスペースを持っています
私たちに、私たちはそれをシンプルにしておこう。

333
00:14:40,356 --> 00:14:42,730
代わりに帰るのと
など当社独自のメモリを搭載しました、

334
00:14:42,730 --> 00:14:44,480
のはそれをやらせます
視覚的にダウンしてここで以下、

335
00:14:44,480 --> 00:14:47,240
マージ仕上げるします
左半分と右半分。

336
00:14:47,240 --> 00:14:49,279
>> だからマージすることで、何をする必要がありますか？

337
00:14:49,279 --> 00:14:50,820
私は順序で要素を取りたいです。

338
00:14:50,820 --> 00:14:53,230
だから、左半分を見て、
私は、最初の数は2である参照してください。

339
00:14:53,230 --> 00:14:55,230
私は右半分を見て、
私は最初の番号を参照してください

340
00:14:55,230 --> 00:14:58,290
そう明らかに、1であります
数は、私は摘み取るしたいです

341
00:14:58,290 --> 00:15:00,430
私の最終的なリストの最初に置きますか？

342
00:15:00,430 --> 00:15:01,449
もちろん、1。

343
00:15:01,449 --> 00:15:02,990
今私は、同じ質問をしたいと思います。

344
00:15:02,990 --> 00:15:05,040
左半分には、私はしました
まだ数2を得ました。

345
00:15:05,040 --> 00:15:07,490
右半分に、
私は数3を持っています。

346
00:15:07,490 --> 00:15:08,930
どれ私が選択したいですか？

347
00:15:08,930 --> 00:15:11,760
もちろん、数2、
今の候補者に気付きます

348
00:15:11,760 --> 00:15:13,620
右に左に4,3です。

349
00:15:13,620 --> 00:15:15,020
のは、もちろん、3を選択してみましょう。

350
00:15:15,020 --> 00:15:18,020
今の候補は4は上にあります
右に左、5。

351
00:15:18,020 --> 00:15:19,460
私たちは、もちろん、4を選択します。

352
00:15:19,460 --> 00:15:21,240
右に左、5の6。

353
00:15:21,240 --> 00:15:22,730
私たちは、もちろん、5]を選択します。

354
00:15:22,730 --> 00:15:25,020
左側の6、右側に7。

355
00:15:25,020 --> 00:15:29,320
私たちは、6を選択し、次に我々
7を選択し、我々は8を選択します。

356
00:15:29,320 --> 00:15:30,100
出来上がり。

357
00:15:30,100 --> 00:15:34,370
>> 言葉のだから膨大な数の後に、我々
8要素のリストをソートしています

358
00:15:34,370 --> 00:15:38,450
8一通りのリストに、
それは、各ステップで増加してい

359
00:15:38,450 --> 00:15:40,850
しかし、どのくらいの時間がなかったです
それはそれを行うために私たちを取ります。

360
00:15:40,850 --> 00:15:43,190
さて、私は意図的にしました
絵のことを打ち出しました

361
00:15:43,190 --> 00:15:46,330
ここで、我々は一種のことができますように
除算を参照するか、感謝

362
00:15:46,330 --> 00:15:49,060
征服にそれが起こっています。

363
00:15:49,060 --> 00:15:52,830
>> 確かにあなたはウェイクを振り返るならば、
私は、これらの点線のすべてを残してきました

364
00:15:52,830 --> 00:15:55,660
プレースホルダでは、次のことができ、
種類の、逆の順序で、参照してください。

365
00:15:55,660 --> 00:15:58,800
あなたは親切なのに戻って見れば
歴史今、私の元のリスト

366
00:15:58,800 --> 00:16:00,250
サイズ8の、もちろんです。

367
00:16:00,250 --> 00:16:03,480
そして、以前、私がいました
サイズ4の二つのリストを扱います、

368
00:16:03,480 --> 00:16:08,400
して、サイ​​ズ2の4つのリスト、
して、サイ​​ズ1の8のリスト。

369
00:16:08,400 --> 00:16:10,151
>> だから、これはどのような行い、
種類の、のことを思い出させますか？

370
00:16:10,151 --> 00:16:11,858
のまあ、確かに、任意の
私たちがきたアルゴリズム

371
00:16:11,858 --> 00:16:14,430
これまで見どこ
分割、および分割、および分割、

372
00:16:14,430 --> 00:16:19,500
再び物事を持っておくと、
再び、この一般的な考え方になります。

373
00:16:19,500 --> 00:16:23,100
それで何かがあります
対数は、ここで起こって。

374
00:16:23,100 --> 00:16:26,790
そしてそれは、nのかなりのログはありませんが、
対数コンポーネントがあります

375
00:16:26,790 --> 00:16:28,280
我々だけで何をやったかと。

376
00:16:28,280 --> 00:16:31,570
>> 今度は、それが実際にどのように考えてみましょう。

377
00:16:31,570 --> 00:16:34,481
そこで再び、n個のログでした
偉大な実行時間、

378
00:16:34,481 --> 00:16:36,980
我々は次のように何かをしたとき
バイナリ検索、我々は今それを呼び出すように、

379
00:16:36,980 --> 00:16:40,090
分割統治戦略
これを介して、我々はマイク・スミスを見つけました。

380
00:16:40,090 --> 00:16:41,020
今技術的に。

381
00:16:41,020 --> 00:16:43,640
それがあっても、n個のログベース2です
ほとんどの数学のクラスで、しかし、

382
00:16:43,640 --> 00:16:45,770
10は通常、あなたがとる基本です。

383
00:16:45,770 --> 00:16:48,940
しかし、コンピュータ科学者、ほとんどの場合、
考え、ベース2の観点で話します、

384
00:16:48,940 --> 00:16:52,569
私たちは、一般的にただのログを言います
N、Nの代わりにログベース2の、

385
00:16:52,569 --> 00:16:55,110
しかし、彼らは正確に一つとしています
コンピュータの世界でも同じ

386
00:16:55,110 --> 00:16:57,234
科学、脇など、
一定の係数があります

387
00:16:57,234 --> 00:17:01,070
両者の違い、それはですので、
より正式な理由のために、とにかく議論の余地。

388
00:17:01,070 --> 00:17:04,520
>> しかし、今のところ、我々は何を気に
この例です。

389
00:17:04,520 --> 00:17:08,520
それでは、例により証明わけにはいきませんが、で
少なくとも数字の例を使用

390
00:17:08,520 --> 00:17:10,730
あなたがする場合は、健全性チェックとして手元に。

391
00:17:10,730 --> 00:17:14,510
だから、以前の式には、ログベースでした
Nの2が、この場合のnは何ですか。

392
00:17:14,510 --> 00:17:18,526
I nは、元の番号を持っていた、または8
元の数の具体的。

393
00:17:18,526 --> 00:17:20,359
今ではほとんどされています
しばらく、私はかなりよ

394
00:17:20,359 --> 00:17:25,300
必ずそのログベース2
8は3値の、

395
00:17:25,300 --> 00:17:29,630
実際、何がそれは約うれしいです
その3回の正確数であり、

396
00:17:29,630 --> 00:17:33,320
リストを分けることができます
長さ8の再び、そして再び、

397
00:17:33,320 --> 00:17:36,160
そして再び、あなたは左だまで
ジャストサイズ1のリストがあります。

398
00:17:36,160 --> 00:17:36,660
右？

399
00:17:36,660 --> 00:17:40,790
8,2に進み、4に進み
1に行く、それはです

400
00:17:40,790 --> 00:17:43,470
まさにそれの反射
私たちはちょっと前に持っていた絵。

401
00:17:43,470 --> 00:17:47,160
どこにするように少しの健全性チェック
対数が実際に関与しています。

402
00:17:47,160 --> 00:17:50,180
>> だから今、他に何ここに関与していますか？ N。

403
00:17:50,180 --> 00:17:53,440
だから、すべてのことに注意してください
時間は、私はリストを分割し、

404
00:17:53,440 --> 00:17:58,260
歴史の中で逆の順序ではあるが
ここで、私はまだ、n個のことをやりました。

405
00:17:58,260 --> 00:18:02,320
ことを必要としたことをマージするステップ
私は、数字の一人一人に触れます

406
00:18:02,320 --> 00:18:05,060
それをスライドさせるために
その適切な場所。

407
00:18:05,060 --> 00:18:10,760
だから、たとえこのの高さ
図は、サイズログnのnまたは3であります

408
00:18:10,760 --> 00:18:13,860
具体的には、換言すれば、
私はここで3つの部門をしました。

409
00:18:13,860 --> 00:18:18,800
私は水平方向にどのくらいの仕事をしました
このチャートたびに沿って？

410
00:18:18,800 --> 00:18:21,110
>> まあ、私がやったn個のステップ
私がしている場合ので、仕事

411
00:18:21,110 --> 00:18:24,080
四つの要素と四つの要素を持って、
私はそれらを一緒にマージする必要があります。

412
00:18:24,080 --> 00:18:26,040
私が通過する必要があります
これら4およびこれらの4、

413
00:18:26,040 --> 00:18:28,123
最終的にそれらをマージします
バック8要素に。

414
00:18:28,123 --> 00:18:32,182
逆にした場合、私は8本の指を持っています
私はそうでない、こっち、および8

415
00:18:32,182 --> 00:18:34,390
fingers-- sorry--私がしている場合
こっち4本の指を持って、

416
00:18:34,390 --> 00:18:37,380
これは私が、4本の指を行います
こちらに、私はこれは、

417
00:18:37,380 --> 00:18:40,590
その後、それは同じです
例として前、私が行った場合

418
00:18:40,590 --> 00:18:44,010
中ものの8本の指を持っています
私は、一種の、行うことができます合計。

419
00:18:44,010 --> 00:18:47,950
私は正確に、ここで行うことができます
その後、私は確かにすることができます

420
00:18:47,950 --> 00:18:50,370
これらのリストのすべてをマージ
サイズ1の一緒に。

421
00:18:50,370 --> 00:18:54,050
しかし、私は確かに見ています
各要素で一度だけ。

422
00:18:54,050 --> 00:18:59,640
したがって、このプロセスの高さは、ログnは
このプロセスの幅は、そのように、話します

423
00:18:59,640 --> 00:19:02,490
nがあるので、私たちは見えるもの
有するように、最終的に、あります

424
00:19:02,490 --> 00:19:06,470
サイズn回の実行時間は、nをログに記録します。

425
00:19:06,470 --> 00:19:08,977
>> 言い換えれば、我々は、分割
リスト、ログn回、

426
00:19:08,977 --> 00:19:11,810
しかし、我々はそれをしたたびに、私たちは持っていました
要素の一つ一つに触れ

427
00:19:11,810 --> 00:19:13,560
それらをマージするために、
すべて一緒に、これ

428
00:19:13,560 --> 00:19:18,120
、ステップをN、私たちは持っているn回のnを記録しました
またはコンピュータ科学者が言うように、

429
00:19:18,120 --> 00:19:20,380
漸近的に、これは
ビッグワードになります

430
00:19:20,380 --> 00:19:22,810
アッパーを説明します
実行時にバインドされ、

431
00:19:22,810 --> 00:19:28,010
私たちは大きなOで実行されています
ログnは時間の、いわば。

432
00:19:28,010 --> 00:19:31,510
>> さて、これはので、重要です
実行時間は何であったかを思い出します

433
00:19:31,510 --> 00:19:34,120
バブルソート、選択と
ソート、挿入ソート、

434
00:19:34,120 --> 00:19:38,200
そして、存在していてもいくつかの他、
nが私達がでたところだったの二乗しました。

435
00:19:38,200 --> 00:19:39,990
そして、あなたは、この種の、ここではこれを見ることができます。

436
00:19:39,990 --> 00:19:45,720
nが平方した場合、明らかであるn回
Nが、ここで我々が​​持っているn回ログn、

437
00:19:45,720 --> 00:19:48,770
私たちはすでに一週間から知っています
ゼロ、そのログnは、対数、

438
00:19:48,770 --> 00:19:50,550
リニアなものよりも優れています。

439
00:19:50,550 --> 00:19:52,930
結局、絵を思い出します
赤と黄色と

440
00:19:52,930 --> 00:19:56,500
私たちが描いたと緑の線、
緑の対数線ははるかに低かったです。

441
00:19:56,500 --> 00:20:00,920
したがって、より良い、より速く
ストレート黄色と赤の線よりも、

442
00:20:00,920 --> 00:20:05,900
n回ログnは、確かに、良いです
nよりn倍、あるいはn乗。

443
00:20:05,900 --> 00:20:09,110
>> だから我々は持っているように見えます
アルゴリズムのマージを同定し

444
00:20:09,110 --> 00:20:11,870
はるかに実行されますソート
確かに時間の短縮、および、

445
00:20:11,870 --> 00:20:16,560
それがなぜ、今週初めに、ときです
我々はバブル間のコンテストを見ました

446
00:20:16,560 --> 00:20:20,750
ソート、選択ソート、およびマージ
ソート、ソート本当に、本当に勝ったマージ。

447
00:20:20,750 --> 00:20:23,660
そして実際、私たちも待ちませんでした
バブルソートや選択ソートのための

448
00:20:23,660 --> 00:20:24,790
終了します。

449
00:20:24,790 --> 00:20:27,410
>> 今度は、一つの他のパスを見てみましょう
この時、もう少しから

450
00:20:27,410 --> 00:20:31,030
正式な視点だけで
場合は、これは、より良好な共振します

451
00:20:31,030 --> 00:20:33,380
より高いレベルの議論より。

452
00:20:33,380 --> 00:20:34,880
だからここにアルゴリズムが再びです。

453
00:20:34,880 --> 00:20:36,770
のは、自分自身を聞いてみよう、
何走行時間

454
00:20:36,770 --> 00:20:39,287
これは様々なステップをアルゴリズムのでしょうか？

455
00:20:39,287 --> 00:20:41,620
それでは、最初にそれを分割してみましょう
ケースと第2ケース。

456
00:20:41,620 --> 00:20:46,280
IFの場合は、IFとELSE、
nが2未満であれば、単に返します。

457
00:20:46,280 --> 00:20:47,580
一定の時間のように感じています。

458
00:20:47,580 --> 00:20:50,970
これは、2つのステップのように、種類の、です、
nが2未満である場合、返さ。

459
00:20:50,970 --> 00:20:54,580
しかし、我々は月曜日に言ったように、
一定時間、または1のビッグO、

460
00:20:54,580 --> 00:20:57,130
二段階三することができ
ステップ、でも千手順。

461
00:20:57,130 --> 00:20:59,870
重要なのは、それがあるということです
ステップ一定数。

462
00:20:59,870 --> 00:21:03,240
だから黄色は擬似コードを強調
ここで実行され、我々はそれを呼ぶことにします、

463
00:21:03,240 --> 00:21:04,490
一定の時間。

464
00:21:04,490 --> 00:21:06,780
だからより正式に、と
私たちはこのto--つもりです

465
00:21:06,780 --> 00:21:09,910
我々程度になります
n個のT now--この権利を正式な、

466
00:21:09,910 --> 00:21:15,030
問題の実行時間
それは、入力として、n個の代をとり、

467
00:21:15,030 --> 00:21:19,150
、1の大きなOに等しいです
nが2未満である場合。

468
00:21:19,150 --> 00:21:20,640
だから、その上の条件です。

469
00:21:20,640 --> 00:21:24,150
nがより小さいのであれば、明確にします
2、私たちはその後、非常に短いリストを持っています

470
00:21:24,150 --> 00:21:29,151
nは走行時間、n個のT、
1または0、この非常に特殊な場合には、

471
00:21:29,151 --> 00:21:30,650
それだけで一定の時間になるだろう。

472
00:21:30,650 --> 00:21:32,691
これは、1を取るために起こっています
ステップ、2ステップ、何でも。

473
00:21:32,691 --> 00:21:33,950
これは、工程の固定数です。

474
00:21:33,950 --> 00:21:38,840
>> だから、ジューシーな部分が確実でなければなりません
擬似コード内の他のケース。

475
00:21:38,840 --> 00:21:40,220
ELSEケース。

476
00:21:40,220 --> 00:21:44,870
ソート右の要素のソート左半分、
要素の半分は、ソートされた半分をマージします。

477
00:21:44,870 --> 00:21:46,800
これらのステップのそれぞれはどのくらいかかりますか？

478
00:21:46,800 --> 00:21:49,780
さて、実行している場合
n個の要素をソートする時間

479
00:21:49,780 --> 00:21:53,010
である、のはそれを非常に呼びましょう
一般的に、T nは、

480
00:21:53,010 --> 00:21:55,500
その後、左のソート
要素の半分

481
00:21:55,500 --> 00:21:59,720
言うような、一種の、あります、
2で割ったn個のT、

482
00:21:59,720 --> 00:22:03,000
同様に右半分をソート
要素の言うような、一種の、あります、

483
00:22:03,000 --> 00:22:06,974
n個のTは2分割した後、
ソート半分をマージします。

484
00:22:06,974 --> 00:22:08,890
さて、私が持っている場合、一部の
ここで要素の数、

485
00:22:08,890 --> 00:22:11,230
4、およびいくつかの数のような
ここで要素の、4のように、

486
00:22:11,230 --> 00:22:14,650
私は、これらの4つのそれぞれをマージする必要があります
で、これら4 1、内の各

487
00:22:14,650 --> 00:22:17,160
他の後に、そのよう
最終的に私は8要素を持っています。

488
00:22:17,160 --> 00:22:20,230
それはそれはnステップのO大だように感じていますか？

489
00:22:20,230 --> 00:22:23,500
私は指とのそれぞれのnを持っていれば
それらの場所にマージする必要があり、

490
00:22:23,500 --> 00:22:25,270
それはまた別のnステップのようなものです。

491
00:22:25,270 --> 00:22:27,360
>> だから確かにformulaically、
我々は、これを表現することができます

492
00:22:27,360 --> 00:22:29,960
最初は少しゾッとするほどではあるが
一見、それは何かであります

493
00:22:29,960 --> 00:22:31,600
それは、まさにそのロジックをキャプチャします。

494
00:22:31,600 --> 00:22:35,710
走行時間、T Nの、IF N
2以上です。

495
00:22:35,710 --> 00:22:42,500
この場合、ELSEの場合には、n個のTで
、2で割った、プラスNのTは2で割りました

496
00:22:42,500 --> 00:22:45,320
n個のプラスビッグオー、いくつかの
ステップの線数、

497
00:22:45,320 --> 00:22:51,630
多分ちょうどn、多分2回
nは、それは、おおよそn個の順序です。

498
00:22:51,630 --> 00:22:54,060
どのように我々はできる、あまりにも、なるように、
formulaicallyこれを表現。

499
00:22:54,060 --> 00:22:56,809
今、あなたがなければ、これを知っているだろう
あなたは、あなたの心にそれを記録してきました

500
00:22:56,809 --> 00:22:58,710
またはでそれを見て
その教科書の裏、

501
00:22:58,710 --> 00:23:00,501
少しがあるかもしれません
最後に、シートをカンニング、

502
00:23:00,501 --> 00:23:03,940
これは、実際に起こっています
NログnのOビッグ私たちに与えて、

503
00:23:03,940 --> 00:23:06,620
その再発理由
あなたは、画面上でここに見ています

504
00:23:06,620 --> 00:23:09,550
あなたが実際に、それを行った場合
例の無限の数、

505
00:23:09,550 --> 00:23:13,000
または、あなたはformulaicallyそれをやった、あなたが希望
この式から、このことを見ます

506
00:23:13,000 --> 00:23:17,100
自身のトンで、再帰的です
nは右の何かの上に、

507
00:23:17,100 --> 00:23:21,680
左側に渡ってn個のトンと、これはすることができます
実際に発現され、最終的に、

508
00:23:21,680 --> 00:23:24,339
Nログnの大きな行くように。

509
00:23:24,339 --> 00:23:26,130
確信していない場合、それがです
ただ、今の罰金

510
00:23:26,130 --> 00:23:28,960
確かに、それはだと、信仰を取ります、
その再発につながるもの、

511
00:23:28,960 --> 00:23:31,780
これは、もう少しです
探しに数学的なアプローチ

512
00:23:31,780 --> 00:23:36,520
マージソートの実行時
一人で、その擬似コードに基づきます。

513
00:23:36,520 --> 00:23:39,030
>> 今度は、少してみましょう
すべてのことから息抜き、

514
00:23:39,030 --> 00:23:41,710
とを見てみましょう
特定の元上院議員、人

515
00:23:41,710 --> 00:23:44,260
少し見覚えかもしれませんが、
Googleのエリックに座っ人

516
00:23:44,260 --> 00:23:48,410
インタビューのためのいくつかの時間前シュミット、
ステージ上で、全体の束の前で

517
00:23:48,410 --> 00:23:53,710
人々の、最終的に話して
かなり今おなじみだトピック。

518
00:23:53,710 --> 00:23:54,575
のは、見てみましょう。

519
00:23:54,575 --> 00:24:01,020

520
00:24:01,020 --> 00:24:03,890
>> エリック・シュミット：今上院議員、
あなたは、Googleのここにいます

521
00:24:03,890 --> 00:24:09,490
私は考えるのが好き
就職の面接など大統領。

522
00:24:09,490 --> 00:24:11,712
今では社長として仕事を得るのは難しいです。

523
00:24:11,712 --> 00:24:12,670
オバマ大統領：右。

524
00:24:12,670 --> 00:24:13,940
エリック・シュミット：そして、あなたがしています
今[聞こえない]何をするつもり。

525
00:24:13,940 --> 00:24:15,523
それはGoogleの仕事を得ることも困難です。

526
00:24:15,523 --> 00:24:17,700
オバマ大統領：右。

527
00:24:17,700 --> 00:24:21,330
>> エリック・シュミット：私たちは、質問があります、
そして私たちは候補者の質問を、

528
00:24:21,330 --> 00:24:24,310
この1は、ラリー・シュワイマーからです。

529
00:24:24,310 --> 00:24:25,890
>> オバマ大統領：[OK]をクリックします。

530
00:24:25,890 --> 00:24:27,005
>> エリック・シュミット：何？

531
00:24:27,005 --> 00:24:28,130
君たちは私が冗談だと​​思いますか？

532
00:24:28,130 --> 00:24:30,590
それはここです。

533
00:24:30,590 --> 00:24:33,490
最も効率的な方法には​​どのようなものです
百万32ビット整数を並べ替えますか？

534
00:24:33,490 --> 00:24:37,560

535
00:24:37,560 --> 00:24:38,979
>> オバマ大統領：Well--

536
00:24:38,979 --> 00:24:41,020
エリック・シュミット：時々、
多分私は申し訳ありませんが、maybe--

537
00:24:41,020 --> 00:24:42,750
オバマ大統領：いや、いや、
いや、いや、いや、私はthink--

538
00:24:42,750 --> 00:24:43,240
エリック・シュミット：それはないですit--

539
00:24:43,240 --> 00:24:45,430
オバマ大統領：私
思う、私はバブルを考えます

540
00:24:45,430 --> 00:24:46,875
ソートはどこへ行くか、間違った方法であろう。

541
00:24:46,875 --> 00:24:49,619

542
00:24:49,619 --> 00:24:50,535
エリック・シュミット：さあ。

543
00:24:50,535 --> 00:24:52,200
誰がこの彼に言いましたか？

544
00:24:52,200 --> 00:24:54,020
OK。

545
00:24:54,020 --> 00:24:55,590
私はコンピュータサイエンスなかったですon--

546
00:24:55,590 --> 00:24:58,986
>> オバマ大統領：我々はしました
そこに私たちのスパイを得ました。

547
00:24:58,986 --> 00:24:59,860
教授：すべての権利。

548
00:24:59,860 --> 00:25:03,370
それでは、私たちを残してみよう
アルゴリズムの理論的な世界

549
00:25:03,370 --> 00:25:06,520
漸近解析で
、およびそれらのいくつかのトピックに戻ります

550
00:25:06,520 --> 00:25:09,940
週0と1、スタートから
いくつかの補助輪を削除するには、

551
00:25:09,940 --> 00:25:10,450
あなたがする場合。

552
00:25:10,450 --> 00:25:13,241
あなたが本当に理解するように
最終的に地面、何から

553
00:25:13,241 --> 00:25:16,805
ときに、ボンネットの下に起こって
記述、コンパイル、およびプログラムを実行します。

554
00:25:16,805 --> 00:25:19,680
これがあったことを、具体的に思い出して
私たちが見た最初のCプログラム、

555
00:25:19,680 --> 00:25:22,840
標準的な、簡単なプログラム
一種の、相対的に言って、

556
00:25:22,840 --> 00:25:24,620
ここで、それは、Hello Worldのを印刷します。

557
00:25:24,620 --> 00:25:27,610
そして、私は、プロセスを言ったことを思い出してください
そのソースコードを通過

558
00:25:27,610 --> 00:25:28,430
まさにこれは。

559
00:25:28,430 --> 00:25:31,180
あなたは、ソースコード、パスを取ります
それコンパイラを通して、クランのように、

560
00:25:31,180 --> 00:25:34,650
そして、出て、そのオブジェクト・コードは、来ます
この、0と1のようになります。

561
00:25:34,650 --> 00:25:37,880
コンピュータのCPU、中央その
処理装置や脳、

562
00:25:37,880 --> 00:25:39,760
最終的には理解しています。

563
00:25:39,760 --> 00:25:42,460
>> それはそれはだということが判明
単純化し過ぎのビット、

564
00:25:42,460 --> 00:25:44,480
私たちが今していること
位置が離れていじめます

565
00:25:44,480 --> 00:25:46,720
本当にをされているかを理解します
ボンネットの下に起こっています

566
00:25:46,720 --> 00:25:48,600
あなたが実行するたびに
打ち鳴らす、またはより一般的には、

567
00:25:48,600 --> 00:25:53,040
毎回あなたは、プログラムを作ります
作成し、CF 50 IDE使用して。

568
00:25:53,040 --> 00:25:56,760
具体的には、もののように
これが最初に生成され、

569
00:25:56,760 --> 00:25:58,684
あなたが最初のプログラムをコンパイルするとき。

570
00:25:58,684 --> 00:26:00,600
言い換えれば、ときに
あなたのソースコードを取ります

571
00:26:00,600 --> 00:26:04,390
そして最初の何、それをコンパイル
クランによって出力されます

572
00:26:04,390 --> 00:26:06,370
アセンブリ・コードとして知られているものです。

573
00:26:06,370 --> 00:26:08,990
そして実際に、それはまさにこのようになります。

574
00:26:08,990 --> 00:26:11,170
>> 私はでコマンドを実行しました
以前のコマンドライン。

575
00:26:11,170 --> 00:26:16,260
クランダッシュ資本のhello.cに、
これはファイルを作成しました

576
00:26:16,260 --> 00:26:19,490
私と呼ばれるhello.sため、
その内側に正確でした

577
00:26:19,490 --> 00:26:22,290
これらのコンテンツ、およびもう少し
上記ともう少し以下、

578
00:26:22,290 --> 00:26:25,080
私はジューシーに置かれています
ここで画面上の情報。

579
00:26:25,080 --> 00:26:29,190
あなたが密接に見れば、あなたが表示されます
少なくともいくつかの馴染みのキーワード。

580
00:26:29,190 --> 00:26:31,330
私たちは、一番上のメインを持っています。

581
00:26:31,330 --> 00:26:35,140
私たちは途中でダウンしているのprintf。

582
00:26:35,140 --> 00:26:38,670
そして、我々はまた、世界ハロー持っています
下方に引用符でバックスラッシュnを。

583
00:26:38,670 --> 00:26:42,450
>> そして、ここで他のすべて
非常に低レベルの指示であります

584
00:26:42,450 --> 00:26:45,500
コンピュータのCPUが理解できます。

585
00:26:45,500 --> 00:26:50,090
メモリを移動するCPU命令
周りに、メモリからのロード文字列、

586
00:26:50,090 --> 00:26:52,750
そして最終的に、印刷
画面上のもの。

587
00:26:52,750 --> 00:26:56,780
今何が後にかかわらず起こります
このアセンブリコードが生成されますか？

588
00:26:56,780 --> 00:26:59,964
最終的に、あなたは確かに、行います、
まだオブジェクトコードを生成します。

589
00:26:59,964 --> 00:27:02,630
しかし、実際に持っているのステップは
ボンネットの下で起こっされて

590
00:27:02,630 --> 00:27:04,180
もう少しこのように見えます。

591
00:27:04,180 --> 00:27:08,390
ソースコードはアセンブリコードとなり、
これは、オブジェクトコードとなり、

592
00:27:08,390 --> 00:27:11,930
ここで手術の言葉であり、その
あなたがソースコードをコンパイルすると、

593
00:27:11,930 --> 00:27:16,300
アウト後、アセンブリコードは付属しており、
あなたは、アセンブリコードをアセンブルするとき、

594
00:27:16,300 --> 00:27:17,800
アウトオブジェクトコードが付属しています。

595
00:27:17,800 --> 00:27:20,360
>> 今クランは、超洗練されています
コンパイラの多くのように、

596
00:27:20,360 --> 00:27:23,151
そしてそれは、これらのステップをすべて行います
一緒に、それは必ずしもありません

597
00:27:23,151 --> 00:27:25,360
出力任意の中間
あなたも見ることができるファイル。

598
00:27:25,360 --> 00:27:28,400
それは物事をコンパイルし、
これは一般的な用語であること

599
00:27:28,400 --> 00:27:30,000
このプロセス全体を説明しています。

600
00:27:30,000 --> 00:27:32,000
しかし、あなたが本当にしたい場合は
特にであることが、あります

601
00:27:32,000 --> 00:27:34,330
多くは、よりそこにも起こっています。

602
00:27:34,330 --> 00:27:38,860
>> しかし、それでは、また、今でも考えてみましょう
その超簡単なプログラム、hello.cに、

603
00:27:38,860 --> 00:27:40,540
関数と呼ばれます。

604
00:27:40,540 --> 00:27:41,870
これは、printfのと呼ばれます。

605
00:27:41,870 --> 00:27:46,900
しかし、私は、確かに、printfのを書いていません
それはいわば、Cが付属しています。

606
00:27:46,900 --> 00:27:51,139
それはだ機能のリコールです
標準io.hで宣言され、これは

607
00:27:51,139 --> 00:27:53,180
ヘッダーファイルは、あります
ここでは、私たちが実際にありますよ

608
00:27:53,180 --> 00:27:55,780
長い前に、より多くの深さに飛び込みます。

609
00:27:55,780 --> 00:27:58,000
しかし、ヘッダファイルです
一般的に伴います

610
00:27:58,000 --> 00:28:02,920
コー​​ド・ファイル、ソースコードファイル、そうすることによって
標準io.h.が存在するのと同じよう

611
00:28:02,920 --> 00:28:05,930
>> いつか前に、誰かが、
または誰かの、また書きました

612
00:28:05,930 --> 00:28:11,040
で、標準io.cと呼ばれるファイル
これは実際の定義は、

613
00:28:11,040 --> 00:28:15,220
またはprintf関数の実装では、
およびその他の機能の房、

614
00:28:15,220 --> 00:28:16,870
実際に書き込まれます。

615
00:28:16,870 --> 00:28:22,140
だから我々はことを検討した場合、その与えられました
ここで左に、hello.cを、ときに

616
00:28:22,140 --> 00:28:26,250
コンパイル、場合でも、私たちにhello.sを与えます
クランは、所定の位置に保存する気にしません

617
00:28:26,250 --> 00:28:31,360
我々はそれを見て、そのアセンブリコードすることができます
、hello.oに組み立てれます

618
00:28:31,360 --> 00:28:34,630
デフォルトの名前は、確かに、あります
あなたがソースをコンパイルするたびに与えられました

619
00:28:34,630 --> 00:28:39,350
オブジェクトコードにコードが、そうではありません
まだそれを実行するのは非常に準備ができて、

620
00:28:39,350 --> 00:28:41,460
別のステップのため
起こることがあり、持っています

621
00:28:41,460 --> 00:28:44,440
過去数のために起こって
週間、あなたにおそらく知られず。

622
00:28:44,440 --> 00:28:47,290
>> 具体的にどこか
CS50 IDEで、この、

623
00:28:47,290 --> 00:28:49,870
あまりにも、少しになります
一瞬のために単純化し過ぎ、

624
00:28:49,870 --> 00:28:54,670
ある、または時間にありました、
標準io.cと呼ばれるファイル、

625
00:28:54,670 --> 00:28:58,440
誰かがにコンパイルすることを
標準io.sまたは同等の、

626
00:28:58,440 --> 00:29:02,010
その誰かが、その後組み立て
標準io.oに、

627
00:29:02,010 --> 00:29:04,600
またはそれはに判明します
わずかに異なるファイル

628
00:29:04,600 --> 00:29:07,220
異なるフォーマットを持つことができます
完全ファイル拡張子、

629
00:29:07,220 --> 00:29:11,720
しかし、理論的には概念的に、正確に
これらの工程は、何らかの形で発生していました。

630
00:29:11,720 --> 00:29:14,060
その今、言ってどれ
私はプログラムを書いているとき、

631
00:29:14,060 --> 00:29:17,870
ただ世界がこんにちは、と言うのhello.c、
そして、私は誰かの他の人のコードを使用しています

632
00:29:17,870 --> 00:29:22,480
上にかつてのprintfのような
時間、標準io.cと呼ばれるファイルで、

633
00:29:22,480 --> 00:29:26,390
その後、何とか私を取る必要があります
オブジェクトコード、私の0と1、

634
00:29:26,390 --> 00:29:29,260
そして、その人のオブジェクト
コー​​ド、または0と1、

635
00:29:29,260 --> 00:29:34,970
何とかにそれらを一緒にリンクします
1最終的なファイル、ハローと呼ばれる、その

636
00:29:34,970 --> 00:29:38,070
持っているゼロのすべてと
私の主な機能からのもの、

637
00:29:38,070 --> 00:29:40,830
0のすべて
そして、printfのためのもの。

638
00:29:40,830 --> 00:29:44,900
>> そして実際、その最後のプロセスがあります
あなたのオブジェクトコードをリンクする、と呼ばれます。

639
00:29:44,900 --> 00:29:47,490
出力はの
実行可​​能ファイルです。

640
00:29:47,490 --> 00:29:49,780
で、公正でそう
一日の終わりに、何もありません

641
00:29:49,780 --> 00:29:52,660
1週間以降に変更された、ときに我々
最初のプログラムをコンパイルを開始しました。

642
00:29:52,660 --> 00:29:55,200
確かに、このすべてがされています
ボンネットの下に起こって、

643
00:29:55,200 --> 00:29:57,241
しかし、今、我々は位置にいます
ここで、我々は実際にすることができます

644
00:29:57,241 --> 00:29:58,794
これらの様々なステップを離れていじめます。

645
00:29:58,794 --> 00:30:00,710
そして実際、最後に
日の、我々はまだです

646
00:30:00,710 --> 00:30:04,480
0と1を残し、どの
今実際に素晴らしいセグエです

647
00:30:04,480 --> 00:30:08,620
Cの別の能力に、その
我々は、ほとんど活用していたていませんでした

648
00:30:08,620 --> 00:30:11,250
現在までに、ビット演算子として知られています。

649
00:30:11,250 --> 00:30:15,220
つまり、これまで、いつでも我々はしました
C言語でCまたは変数内のデータを扱って、

650
00:30:15,220 --> 00:30:17,660
私たちはのようなものを持っていました
文字や山車とイン

651
00:30:17,660 --> 00:30:21,990
そして、longとdouble型等が挙げられるが、
それらのすべては、少なくとも8ビットです。

652
00:30:21,990 --> 00:30:25,550
我々はまだできていたことがありません
個々のビットを操作し、

653
00:30:25,550 --> 00:30:28,970
さらには個々のビット、しかし、我々
知っている、0と1を表すことができます。

654
00:30:28,970 --> 00:30:32,640
今では、C言語で、あなたことが判明
個々のビットへのアクセスを得ることができ、

655
00:30:32,640 --> 00:30:35,530
次の構文を知っていれば、
これでそれらを取得します。

656
00:30:35,530 --> 00:30:38,010
>> それでは、見てみましょう
ビット演算子で。

657
00:30:38,010 --> 00:30:41,700
だから、いくつかのシンボルがここに描かれています
我々は、一種の、一種の、前に見てきました。

658
00:30:41,700 --> 00:30:45,580
私は、垂直​​にアンパサンドを見ます
バー、同様にいくつかの他、

659
00:30:45,580 --> 00:30:49,430
そのアンパサンドアンパサンドをリコール
我々の前に見てきたものです。

660
00:30:49,430 --> 00:30:54,060
あなたが持っている論理AND演算子、
二人一緒に、または論理OR

661
00:30:54,060 --> 00:30:56,300
オペレータ、あなた
2つの垂直バーを持っています。

662
00:30:56,300 --> 00:31:00,550
ビット演算子は、我々はよ
、個々のビットを操作するを参照してください。

663
00:31:00,550 --> 00:31:03,810
単に1つのアンパサンドを使用して、
単一の垂直バー、キャレット記号

664
00:31:03,810 --> 00:31:06,620
少し、次に来ます
チルダし、左

665
00:31:06,620 --> 00:31:08,990
ブラケットは、ブラケットを左、
右ブラケット右ブラケット。

666
00:31:08,990 --> 00:31:10,770
これらのそれぞれは、異なる意味を持ちます。

667
00:31:10,770 --> 00:31:11,950
>> 実際には、のは見てみましょう。

668
00:31:11,950 --> 00:31:16,560
今日は古い学校に行きましょう、と使用
往年のタッチスクリーン、

669
00:31:16,560 --> 00:31:18,002
ホワイトボードとして知られています。

670
00:31:18,002 --> 00:31:19,710
そして、このホワイトボード
私たちを可能にするために起こっています

671
00:31:19,710 --> 00:31:27,360
いくつかの非常に単純なシンボルを表現するために、
あるいはむしろ、いくつかの非常に単純な式、

672
00:31:27,360 --> 00:31:29,560
我々は最終的にそれからできること
レバレッジ、順番に

673
00:31:29,560 --> 00:31:33,230
個別にアクセスします
Cプログラム内のビット。

674
00:31:33,230 --> 00:31:34,480
言い換えれば、はこのやろう。

675
00:31:34,480 --> 00:31:37,080
用してみましょう最初の話
アンパサンド回りのモーメント、

676
00:31:37,080 --> 00:31:39,560
これはビット単位のAND演算子です。

677
00:31:39,560 --> 00:31:42,130
言い換えれば、これは
ことができ、オペレータ

678
00:31:42,130 --> 00:31:45,930
私は左側の変数を持っています
典型的には、右側の変数

679
00:31:45,930 --> 00:31:50,640
または個々の値、その場合、私たちと
一緒には、私の最終的な結果を提供します。

680
00:31:50,640 --> 00:31:51,560
だから私は何を意味していますか？

681
00:31:51,560 --> 00:31:54,840
プログラムでは、変数を使用している場合
これらの値の1店舗という、

682
00:31:54,840 --> 00:31:58,000
あるいは単に、簡単なそれを維持させて、
個別に0と1を書き出します、

683
00:31:58,000 --> 00:32:00,940
ここでは、アンパサンド演算子はどのように動作するかです。

684
00:32:00,940 --> 00:32:06,400
0アンパサンド0は0に等しいとしています。

685
00:32:06,400 --> 00:32:07,210
さて、なぜそのようになるのですか？

686
00:32:07,210 --> 00:32:09,291
>> それは非常に似ていると
ブール式、

687
00:32:09,291 --> 00:32:10,540
ことを、私たちはこれまで説明してきました。

688
00:32:10,540 --> 00:32:15,800
あなたはすべての後と思われる場合は、0です
偽、0は、偽偽および偽であります

689
00:32:15,800 --> 00:32:18,720
我々が議論してきたように、あります
論理的に、また偽。

690
00:32:18,720 --> 00:32:20,270
だから我々はここにも0を得ます。

691
00:32:20,270 --> 00:32:24,390
あなたは0アンパサンドを取る場合
1、よく、あまりにも、その

692
00:32:24,390 --> 00:32:29,890
このためので、0になるだろう
左側の発現は、真または1であることが

693
00:32:29,890 --> 00:32:32,360
それが本当の、真であることが必要です。

694
00:32:32,360 --> 00:32:36,320
しかし、ここで我々が​​持っている偽
真、または0と1。

695
00:32:36,320 --> 00:32:42,000
ここでもう一度、私たちは1アンパサンドを持っている場合
0、、あまりにも、0になるだろうことを、

696
00:32:42,000 --> 00:32:47,240
私たちは1アンパサンド1を持っている場合、
最後に、私たちは1ビットを持っています。

697
00:32:47,240 --> 00:32:50,340
だから、他の言葉で、私たちはやっていません
この演算子と何も面白いこと

698
00:32:50,340 --> 00:32:51,850
まだ、このアンパサンド演算子。

699
00:32:51,850 --> 00:32:53,780
これは、ビット単位のAND演算子です。

700
00:32:53,780 --> 00:32:57,290
しかし、これらは成分であります
これを介して我々が行うことができます

701
00:32:57,290 --> 00:32:59,240
我々はすぐにわかるよう面白いこと、。

702
00:32:59,240 --> 00:33:02,790
>> 今度は1つだけを見てみましょう
ここに右のオーバー垂直バー。

703
00:33:02,790 --> 00:33:06,710
私は0ビットと私を持っている場合
それともと、ビット単位

704
00:33:06,710 --> 00:33:11,030
OR演算子、他の0ビット、
それは私に0を与えるために起こっています。

705
00:33:11,030 --> 00:33:17,540
私は0ビットを取るとか、場合
1ビット、私は1を取得するつもりです。

706
00:33:17,540 --> 00:33:19,830
そして実際に、ちょうどのための
透明度は、私は戻って行きましょう、

707
00:33:19,830 --> 00:33:23,380
そのように私の垂直バー
1のと間違えていません。

708
00:33:23,380 --> 00:33:26,560
私はすべてを書き換えてみましょう
私の1の小さなより

709
00:33:26,560 --> 00:33:32,700
明らかに、私の場合、私たちは次のように参照してください。
1または0、すなわち1になるだろうしています、

710
00:33:32,700 --> 00:33:39,060
私は1 OR 1があれば、
あまりにも、1になるだろう。

711
00:33:39,060 --> 00:33:42,900
だからか、その論理的に見ることができます
オペレータは非常に動作が異なります。

712
00:33:42,900 --> 00:33:48,070
これは私0または0を私に0を与える与えるが、
それ以外のすべての組み合わせは私に1を与えます。

713
00:33:48,070 --> 00:33:52,480
限り、私は内の1つの1を持っているとして、
式は、結果が1になるだろう。

714
00:33:52,480 --> 00:33:55,580
>> ANDと対照的に
オペレータ、アンパサンド、

715
00:33:55,580 --> 00:34:00,940
私は中2 1のを持っている場合にのみ、
式は、私が実際に1アウトを得るのですか。

716
00:34:00,940 --> 00:34:02,850
今いくつかの他のがあります
事業者にも。

717
00:34:02,850 --> 00:34:04,810
そのうちの一つは、もう少し複雑です。

718
00:34:04,810 --> 00:34:07,980
だから私は先に行くと、消去せ
これは、いくつかの領域を解放します。

719
00:34:07,980 --> 00:34:13,020

720
00:34:13,020 --> 00:34:16,460
そしてのは、見てみましょう
ちょっとキャレット記号、。

721
00:34:16,460 --> 00:34:18,210
これは、典型的には
あなたが入力できる文字

722
00:34:18,210 --> 00:34:21,420
キーボード保持シフトにと
あなたの米国の上の数字の後、1

723
00:34:21,420 --> 00:34:22,250
キーボード。

724
00:34:22,250 --> 00:34:26,190
>> だから、これは排他的です
OR演算子、排他的論理和。

725
00:34:26,190 --> 00:34:27,790
だから私たちはただ、OR演算子を見ました。

726
00:34:27,790 --> 00:34:29,348
これは、排他的論理和演算子です。

727
00:34:29,348 --> 00:34:30,639
実際の違いは何ですか？

728
00:34:30,639 --> 00:34:34,570
まあちょうど式を見てみましょう、
そして最終的に原料として使用します。

729
00:34:34,570 --> 00:34:37,690
0 XOR 0。

730
00:34:37,690 --> 00:34:39,650
私は常に0であると言うつもりです。

731
00:34:39,650 --> 00:34:41,400
それは排他的論理和の定義です。

732
00:34:41,400 --> 00:34:47,104
0 XOR 1が1になるだろう。

733
00:34:47,104 --> 00:34:58,810
1 XOR 0は1になるだろう、
1 XOR 1になるだろうか？

734
00:34:58,810 --> 00:34:59,890
間違いましたか？

735
00:34:59,890 --> 00:35:00,520
または右？

736
00:35:00,520 --> 00:35:01,860
知りません。

737
00:35:01,860 --> 00:35:02,810
0。

738
00:35:02,810 --> 00:35:04,700
今ここで何が起こっているの？

739
00:35:04,700 --> 00:35:06,630
まあについて考えます
この演算子の名前。

740
00:35:06,630 --> 00:35:09,980
排他的論理和、ように
名前は、一種の、示唆しています、

741
00:35:09,980 --> 00:35:13,940
答えは唯一であることを行っています
1入力は排他的である場合には、

742
00:35:13,940 --> 00:35:15,560
排他的に異なります。

743
00:35:15,560 --> 00:35:18,170
だからここに入力があります
同様に、出力が0であるので。

744
00:35:18,170 --> 00:35:20,700
ここで入力があります
同様に、出力が0であるので。

745
00:35:20,700 --> 00:35:25,640
ここで彼らは、出力が異なるものです
排他的であるので、出力は1です。

746
00:35:25,640 --> 00:35:28,190
だから、と非常によく似てい
そして、、それは非常に似ています、

747
00:35:28,190 --> 00:35:32,760
か、それは非常に似ていると
ORが、唯一の排他的な方法です。

748
00:35:32,760 --> 00:35:36,210
これは、もはや1ではありません
我々は、2つの1のを持っているので、

749
00:35:36,210 --> 00:35:38,621
そして、排他的ではない、それらのひとつ。

750
00:35:38,621 --> 00:35:39,120
大丈夫。

751
00:35:39,120 --> 00:35:40,080
何他の人はどうですか？

752
00:35:40,080 --> 00:35:44,220
まあチルダは、一方、あります
ありがたいことに、実際にはいいとシンプル。

753
00:35:44,220 --> 00:35:46,410
そして、これが単項であります
意味オペレータ、

754
00:35:46,410 --> 00:35:50,400
それは、ただ1つの入力に印加されています、
一方のオペランド、いわば。

755
00:35:50,400 --> 00:35:51,800
ていない左右に。

756
00:35:51,800 --> 00:35:56,050
言い換えれば、あなたは、チルダを取る場合
0、答えは反対になります。

757
00:35:56,050 --> 00:35:59,710
そして、あなたは1のチルダ取る場合、
答えは反対があるでしょう。

758
00:35:59,710 --> 00:36:02,570
だから、チルダ演算子です
ビットを否定する方法、

759
00:36:02,570 --> 00:36:06,000
またはからのビットを反転
0から1、または1から0。

760
00:36:06,000 --> 00:36:09,820
>> そして、それは最終的に私たちを残します
ちょうど2つの最終事業者と、

761
00:36:09,820 --> 00:36:13,840
いわゆる左シフトし、
右シフト演算いわゆる。

762
00:36:13,840 --> 00:36:16,620
それでは、どのようにそれらの作業を見てみましょう。

763
00:36:16,620 --> 00:36:20,780
書かれた左シフト演算子、
そのような2アングルブラケットと、

764
00:36:20,780 --> 00:36:22,110
以下のように動作します。

765
00:36:22,110 --> 00:36:27,390
左に、私の入力、または私のオペランドの場合
シフト演算子は、非常に単純に1です。

766
00:36:27,390 --> 00:36:33,750
そして、私は、その後にコンピュータを伝えます
1は、7ヶ所を言うことを、左シフト

767
00:36:33,750 --> 00:36:37,150
結果は私かのようです
その1を取り、それを移動させます

768
00:36:37,150 --> 00:36:40,160
に渡って7ヶ所
左、およびデフォルトでは、

769
00:36:40,160 --> 00:36:42,270
我々はそれを仮定するつもりです
右側のスペース

770
00:36:42,270 --> 00:36:44,080
ゼロでパディングされようとしています。

771
00:36:44,080 --> 00:36:50,316
言い換えれば、1が起こっているシフト7を残し
私に1が続く、1、2、3を与えるために、

772
00:36:50,316 --> 00:36:54,060
4、5、6、7ゼロ。

773
00:36:54,060 --> 00:36:57,380
だからのように、それはあなたがすることができます
1のような少数を取り​​ます、

774
00:36:57,380 --> 00:37:00,740
そして、明らかにはるかにそれを作ります
このようにはるかに大きな、ずっと、

775
00:37:00,740 --> 00:37:06,460
しかし、我々は実際に見に行くしています
それのためのより多くの巧妙なアプローチ

776
00:37:06,460 --> 00:37:08,080
代わりに、同様に、

777
00:37:08,080 --> 00:37:08,720
>> 大丈夫。

778
00:37:08,720 --> 00:37:10,060
それを週に3回は終わりです。

779
00:37:10,060 --> 00:37:11,400
私たちはあなたの次の時間が表示されます。

780
00:37:11,400 --> 00:37:12,770
これはCS50ました。

781
00:37:12,770 --> 00:37:17,270

782
00:37:17,270 --> 00:37:22,243
>> [音楽再生]

783
00:37:22,243 --> 00:37:25,766
>> SPEAKER 1：彼はスナックにありました
バーでは、ホットファッジサンデーを食べます。

784
00:37:25,766 --> 00:37:28,090
彼はすべての彼の顔の上にそれを持っていました。

785
00:37:28,090 --> 00:37:30,506
彼は、ひげのようにそのチョコレートを着ています

786
00:37:30,506 --> 00:37:31,756
SPEAKER 2：あなたは何をしているのか？

787
00:37:31,756 --> 00:37:32,422
SPEAKER 3：うーん？

788
00:37:32,422 --> 00:37:33,500
何？

789
00:37:33,500 --> 00:37:36,800
>> SPEAKER 2：あなただけのダブルディップましたか？

790
00:37:36,800 --> 00:37:38,585
あなたは二重のチップを浸しました。

791
00:37:38,585 --> 00:37:39,460
SPEAKER 3：すみません。

792
00:37:39,460 --> 00:37:44,440
SPEAKER 2：あなたは、チップを浸し
一口を取って、あなたは再び浸しました。

793
00:37:44,440 --> 00:37:44,940
SPEAKER 3：

794
00:37:44,940 --> 00:37:48,440
SPEAKER 2：だから、パッティングのようなものです
ディップであなたの全体の口の右側。

795
00:37:48,440 --> 00:37:52,400
次回は、チップを取ります
一度だけ、それを浸し、それを終了します。

796
00:37:52,400 --> 00:37:53,890
>> SPEAKER 3：あなたは、何ダンを知っていますか？

797
00:37:53,890 --> 00:37:58,006
あなたがディップしたい方法を浸します。

798
00:37:58,006 --> 00:38:01,900
私はディップしたい方法を浸します。

799
00:38:01,900 --> 00:38:03,194