1
00:00:00,000 --> 00:00:11,270

2
00:00:11,270 --> 00:00:14,910
>> スピーカー：すべての権利、これはCS50である。

3
00:00:14,910 --> 00:00:19,020
これを週に3回の終わりであり、もし
すでに活用していないが、

4
00:00:19,020 --> 00:00:21,790
ランチがあることを知っている
ここで、いつものように今週の金曜日

5
00:00:21,790 --> 00:00:25,430
あなたは良い会話を楽しむことができます
火と氷でと食品

6
00:00:25,430 --> 00:00:27,980
CS50ののいくつかに
スタッフとクラスメート。

7
00:00:27,980 --> 00:00:30,170
ここにこのURLへのヘッド。

8
00:00:30,170 --> 00:00:33,420
>> これでリコールすることや
すぐに精通することができ、

9
00:00:33,420 --> 00:00:35,970
ここではこれらの事、その
終了時に与えられている

10
00:00:35,970 --> 00:00:37,850
多くのクラスのための学期。

11
00:00:37,850 --> 00:00:40,870
におけるいわゆる受験青本、
あなたが試験にあなたの答えを書いてください。

12
00:00:40,870 --> 00:00:44,240
今私はここにある26など
それらのそれぞれの青色の書籍、

13
00:00:44,240 --> 00:00:47,580
Zまで名前はAを書き込まれ、
確かに名前が単純な、Aということである

14
00:00:47,580 --> 00:00:50,490
Zまでそして、もう一つの
手近な目標、今日

15
00:00:50,490 --> 00:00:53,910
何を続けることになるだろう
私たちではありません月曜日、上で開始

16
00:00:53,910 --> 00:00:57,830
とても多くのコードを見て、本当に
アイデアや問題解決を見て。

17
00:00:57,830 --> 00:01:00,170
目標の一つと
このコースの約束

18
00:01:00,170 --> 00:01:02,985
もっと考えすることを教えることです
慎重に、より念入りに、

19
00:01:02,985 --> 00:01:05,400
より効率的な問題を解決する。

20
00:01:05,400 --> 00:01:09,526
そして実際、私たちは本当にそれを行うことができます
でも、コードの行を触れることなく。

21
00:01:09,526 --> 00:01:12,150
だから私は、ゾウのカップルを持っている
ここに今日、オレンジ、青、

22
00:01:12,150 --> 00:01:15,780
私たちは1ボランティアを得ることができれば、
多分少し奥にいつもよりから。

23
00:01:15,780 --> 00:01:18,070
どのようにすぐそこについては、下に来る。

24
00:01:18,070 --> 00:01:24,180
の目標は、になるだろう
ここで、この試験に役立つプラス管理する。

25
00:01:24,180 --> 00:01:24,935
あなたの名前は？

26
00:01:24,935 --> 00:01:25,768
>> 聴衆：メアリーベス。

27
00:01:25,768 --> 00:01:27,560
スピーカー：メアリー·ベス、アップ時に来る。

28
00:01:27,560 --> 00:01:29,560
私はあなたのためにここにマイクを取得しましょう​​。

29
00:01:29,560 --> 00:01:32,172

30
00:01:32,172 --> 00:01:32,880
よろしくね。

31
00:01:32,880 --> 00:01:34,005
>> 聴衆：はじめまして。

32
00:01:34,005 --> 00:01:36,790
スピーカー：すべての権利、私は持っている
ここにブルーブックのAからZ、

33
00:01:36,790 --> 00:01:41,680
そして私はそれをふりをするつもりだ
私は学生のいずれかを持って、

34
00:01:41,680 --> 00:01:45,770
それらは幾分ランダムに入って来ている
3時間の試験ブロックの終わりに、

35
00:01:45,770 --> 00:01:49,400
ので、いくつかで終わるいる
このようなセミランダムな順序。

36
00:01:49,400 --> 00:01:54,510
今だけの瞬間のあなたの仕事は、起こっている
これは彼らが取得する方法実際にbe--する

37
00:01:54,510 --> 00:01:56,820
の最後に中になって
クラス、最も可能性が高い。

38
00:01:56,820 --> 00:02:01,120
あなたの仕事は今非常に、あることを行っている
単純に、私たちのためにこれらの青い本をソートする

39
00:02:01,120 --> 00:02:05,220
AからZまで

40
00:02:05,220 --> 00:02:08,400
>> 聴衆：ああ、これは
永遠に連れて行く。

41
00:02:08,400 --> 00:02:13,747
>> スピーカー：そして、私たちは見てます
これを行うように、全くプレッシャーはありません。

42
00:02:13,747 --> 00:02:15,330
聴衆：いや、いや、圧力か何か。

43
00:02:15,330 --> 00:02:19,230

44
00:02:19,230 --> 00:02:23,570
>> スピーカー：そして楽しみのために、
のタイマーを設置しましょう​​。

45
00:02:23,570 --> 00:02:26,680

46
00:02:26,680 --> 00:02:28,700
>> 聴衆：とても楽しい、とても楽しい。

47
00:02:28,700 --> 00:02:36,741

48
00:02:36,741 --> 00:02:38,574
>> スピーカー：私はあなたのためにマイクを保持することができます。

49
00:02:38,574 --> 00:02:40,240
すべての権利、私たちは私たちの速度を倍増しました。

50
00:02:40,240 --> 00:02:44,190

51
00:02:44,190 --> 00:02:49,060
だからその間に、私は何のポーズましょう
メアリーベスのための質問になるだろう

52
00:02:49,060 --> 00:02:51,540
彼女がどのように、何をやっているされている
彼女はこれを解決するについて行く？

53
00:02:51,540 --> 00:02:54,040
そして、実際に、あなたが持っていない可能性があり
今まで何かについて考えた

54
00:02:54,040 --> 00:02:57,440
あなたが選ぶときと非常にシンプル
このように26冊まで、

55
00:02:57,440 --> 00:02:59,350
自然がありますかどの
彼らに注文する。

56
00:02:59,350 --> 00:03:01,335
プロセスとは何ですか
あなたが実際に使用するのか？

57
00:03:01,335 --> 00:03:03,770
それだけでかなりランダムである
あなたが見る最初のものを選ぶ

58
00:03:03,770 --> 00:03:05,250
その場所にそれを置く？

59
00:03:05,250 --> 00:03:09,680
あなたが最初に周りのあなたの手を動かしてください
その後、Bを探して先をお探しですか？

60
00:03:09,680 --> 00:03:11,722
あなたが見てみてください
並んでそれら一対のサイド

61
00:03:11,722 --> 00:03:14,680
ちょうど、ちょっと待って、これを言う
右ではなく、その後の順序を入れ替える？

62
00:03:14,680 --> 00:03:16,960
私たちは月曜日にすでに見ました
いくつかの方法がありますことを

63
00:03:16,960 --> 00:03:22,140
私たちはこれを行うことができる、と
確かに私たちはここで終わり近くなど、

64
00:03:22,140 --> 00:03:26,360
私はおそらくノートを取る
メアリーベスが何をしているかの。

65
00:03:26,360 --> 00:03:30,040
私たちは、それはそう少数の山、持っている
3小さいもの、1より大きい。

66
00:03:30,040 --> 00:03:33,790

67
00:03:33,790 --> 00:03:36,415
>> 聴衆：私はそれらを注文してい
私は2つの文字を見つけたとき

68
00:03:36,415 --> 00:03:39,540
私が知っている順序で一緒にしていること、
私はそうでないので、私はそれらを一緒に入れて

69
00:03:39,540 --> 00:03:42,915
維持を心配する必要はあり
本の全体の行を追跡。

70
00:03:42,915 --> 00:03:45,706
それは、Aが最初で、ああ、ちょうどだ
私はここで、このスタックを持っている。

71
00:03:45,706 --> 00:03:47,580
スピーカー：だから、ほとんどのような
パズルのピースこと

72
00:03:47,580 --> 00:03:49,860
右の形状にしてい
お互いに一致。

73
00:03:49,860 --> 00:03:51,026
聴衆：かなり多く、うん。

74
00:03:51,026 --> 00:03:55,320
スピーカー：OK、優れた。

75
00:03:55,320 --> 00:03:59,850
そして今、これらの各
杭は、おそらくソートされて？

76
00:03:59,850 --> 00:04:00,990
>> 聴衆：うん。

77
00:04:00,990 --> 00:04:09,900
>> スピーカー：すべての権利、Z.すべてのAから
右、おめでとう、あなたはそれをやった。

78
00:04:09,900 --> 00:04:11,461
あなたの選択肢があります。

79
00:04:11,461 --> 00:04:11,960
ブルー？

80
00:04:11,960 --> 00:04:13,530
すべての権利、それをありがとうございました。

81
00:04:13,530 --> 00:04:16,679
だから、メアリーベスは提案しなかった
彼女のアプローチは何だった、

82
00:04:16,679 --> 00:04:19,720
しかし、別のアプローチは、どのように何
これらのことを並べ替えて行くのでしょうか？

83
00:04:19,720 --> 00:04:21,130
あなただったらどうしましたか？

84
00:04:21,130 --> 00:04:24,060
ビートにレコードがあったであろう
1分50秒かそこら、

85
00:04:24,060 --> 00:04:26,039
プラスのものは私が数えるのを忘れていました。

86
00:04:26,039 --> 00:04:27,080
あなただったらどうしましたか？

87
00:04:27,080 --> 00:04:27,579
うん？

88
00:04:27,579 --> 00:04:28,735
聴衆：スタックを取る。

89
00:04:28,735 --> 00:04:29,776
初めから開始します。

90
00:04:29,776 --> 00:04:32,284
あなたの論文をチェックしてください。

91
00:04:32,284 --> 00:04:36,586
そして一番上が高い場合
以上は、多分、それらは、ある

92
00:04:36,586 --> 00:04:38,980
底ものである
高く、それらを切り替えてください。

93
00:04:38,980 --> 00:04:41,300
>> スピーカー：そう、始まる
上部と下部に、

94
00:04:41,300 --> 00:04:43,716
そして、あなたの方法を作業
内側に、それらを交換すること、そのような？

95
00:04:43,716 --> 00:04:46,580
類似の[OK]を、これほど少ない
バブルソートとその精神においては、

96
00:04:46,580 --> 00:04:49,160
しかし両極端を選ぶ
しない隣接する対。

97
00:04:49,160 --> 00:04:52,080
しかし、それの短いがありますということです
確かに、さまざまな方法の束

98
00:04:52,080 --> 00:04:54,210
私たちはこれを行うことができ、そして
率直に言って、私はちょっとあなたを思う

99
00:04:54,210 --> 00:04:55,700
右、カップルのアプローチを採用した？

100
00:04:55,700 --> 00:05:00,567
次の4つのソートされた杭のようなものを作り、
その後効果的にそれらを一緒にマージされた。

101
00:05:00,567 --> 00:05:02,650
そして、それは、あえて言う、別の
完全な技術。

102
00:05:02,650 --> 00:05:06,950
あなたは、一つの大きな山として扱っていなかった
あなたは、4クワッドに問題を分割

103
00:05:06,950 --> 00:05:09,820
あなたが説明し、その後何とか場合
最終的にはそれらを統合しました。

104
00:05:09,820 --> 00:05:13,410
>> それでは、最終的には、考えてみましょう、
どのように他の私たちは、これを行うことがあります。

105
00:05:13,410 --> 00:05:15,860
私たちは、概念を形式化
バブルソート前回、

106
00:05:15,860 --> 00:05:18,780
とバブルソートのリコールだった
私たちは可視化されたアルゴリズム

107
00:05:18,780 --> 00:05:22,640
ここまでクラスメートの8と、
一見ランダムに最初に選別した。

108
00:05:22,640 --> 00:05:26,110
そして、私たちは、その後も、ペアごとに決定した
2つの要素は、順不同である

109
00:05:26,110 --> 00:05:26,950
単にそれらを交換。

110
00:05:26,950 --> 00:05:28,930
だから、4と2アール
明らかに故障して、

111
00:05:28,930 --> 00:05:31,080
ので、これらの2クラスメート
ポジションを入れ替え。

112
00:05:31,080 --> 00:05:35,390
そして、私たちは4と6を用いて繰り返し、
その後6および8、それぞれの繰り返しで、

113
00:05:35,390 --> 00:05:36,980
右に移動する。

114
00:05:36,980 --> 00:05:42,590
>> だから、どのように多くのペアごとの8人に与えられた
から歩きながら、私は比較をしましたか

115
00:05:42,590 --> 00:05:45,220
そのような反復で左から右へ？

116
00:05:45,220 --> 00:05:48,410
どのように多くの比較は？

117
00:05:48,410 --> 00:05:49,197
セブン、右か？

118
00:05:49,197 --> 00:05:51,405
そのため8があるかどう
人が、あなたはペアを持っている

119
00:05:51,405 --> 00:05:53,880
彼らとあなたが動かし続ける
一方、右にホップ

120
00:05:53,880 --> 00:05:56,060
あなたが8を持っているつもりはない
比較あなたは比較することはできませんので、

121
00:05:56,060 --> 00:05:59,226
自身に対する要素、またはそれはだろ
あなたは7を持っているので、単に、無意味であること。

122
00:05:59,226 --> 00:06:01,290
またはより一般的には、もし
私たちは、n人を持って、私たち

123
00:06:01,290 --> 00:06:04,300
nはマイナス1比較を行う
バブルソートで。

124
00:06:04,300 --> 00:06:08,150
>> それでは、今どのように良いか考えてみましょう
悪いバブルソート、実際にあった、とみてください

125
00:06:08,150 --> 00:06:13,570
と自分自身の語彙を精製して、
これは、このようなアルゴリズムを批判するために、

126
00:06:13,570 --> 00:06:14,430
そしてすぐに私たち自身。

127
00:06:14,430 --> 00:06:16,970
を最初に通過だから
バブルソート、初めて

128
00:06:16,970 --> 00:06:20,909
私が渡って、左から右に歩い
舞台は、私のn  -  1の比​​較を行った。

129
00:06:20,909 --> 00:06:22,950
そして、それは私のことになるだろう
測定単位、右か？

130
00:06:22,950 --> 00:06:26,170
私はこの種の話を散歩し、
やややや遅い、速い、

131
00:06:26,170 --> 00:06:29,300
そう秒の私の数を数える
特に語っていないが、

132
00:06:29,300 --> 00:06:32,260
しかしの数を数える
私は月曜日に行った操作を、

133
00:06:32,260 --> 00:06:35,900
2人を比較し、それは感じている
メジャーの素敵な単位を挙げることができる。

134
00:06:35,900 --> 00:06:40,980
>> だから、nはマイナス1は、第1の時間ステップ、
が、その後何がその後起こったのですか？

135
00:06:40,980 --> 00:06:46,610
ワンパスの1利点は何ですか
それ以外の場合はソートされていないリストを？

136
00:06:46,610 --> 00:06:49,840
あなたは何の要素について教えてくださいすることができます
あそこのすべての方法は誰でしたか？

137
00:06:49,840 --> 00:06:51,300
うん？

138
00:06:51,300 --> 00:06:52,870
そう、最大の要素でしたか？

139
00:06:52,870 --> 00:06:55,710
ナンバー8、でも彼女も
私は、ここに毎回開始

140
00:06:55,710 --> 00:06:57,860
彼女に対して比較
隣人、彼女が保た

141
00:06:57,860 --> 00:07:00,480
右まで泡立てる
リストの右側。

142
00:07:00,480 --> 00:07:02,710
そして実際、それはどこだ
このアルゴリズムは、その名前を取得します。

143
00:07:02,710 --> 00:07:07,630
>> 今、そのロジックによる、どのように多くの比較
私は2番目の時間に行う必要があります

144
00:07:07,630 --> 00:07:09,800
私は、左から右に通過させる？

145
00:07:09,800 --> 00:07:10,730
nはマイナス2、右か？

146
00:07:10,730 --> 00:07:14,297
私はあればそれはちょうど私の時間を無駄にすることになる
誰かに対して8を比較しておく

147
00:07:14,297 --> 00:07:16,630
他に、私たちはすでに知っているので、
彼女は正しい場所にいた。

148
00:07:16,630 --> 00:07:19,760
だから少しです
最適化のため、次のパス

149
00:07:19,760 --> 00:07:23,899
プラスnはマイナス2段階になるだろう、
ここで、nは、人の数である。

150
00:07:23,899 --> 00:07:26,940
今、あなたはちょっとさえ、外挿することができます
あなたはコンピュータ科学者いないのであれば、

151
00:07:26,940 --> 00:07:27,680
これはどのように終了します。

152
00:07:27,680 --> 00:07:31,259
このアルゴリズムの終了時に、おそらくは
あなただけの1の比較左持っている。

153
00:07:31,259 --> 00:07:33,800
あなたはちょっと修正する必要があり
ケース2に、リストの先頭

154
00:07:33,800 --> 00:07:36,540
一つは、順不同である
と、1と2でなければなりません

155
00:07:36,540 --> 00:07:40,330
これはで底に
プラス1の最終比較。

156
00:07:40,330 --> 00:07:44,500
>> さて、ドット、ドット、それはだ波のドット種類
ジューシーな詳細のいくつかを手に、

157
00:07:44,500 --> 00:07:46,452
しかしちょうど先に行くと単純化しましょう​​。

158
00:07:46,452 --> 00:07:48,660
あなたが高いから思い出して
学校、率直に言って、あなた方の多く

159
00:07:48,660 --> 00:07:50,340
持っていた数学の本を持っていた
少しチートシート

160
00:07:50,340 --> 00:07:52,550
前面カバーまたはオン
お見せした背面カバー

161
00:07:52,550 --> 00:07:56,400
どのシリーズのような和
これは、最終的に合算。

162
00:07:56,400 --> 00:07:59,600
一般的なケースでは、あなたが持っている場合
nのような変数、そして実際にこれ、

163
00:07:59,600 --> 00:08:01,634
あなたはあなたを見ている場合
古い学校の数学の本、

164
00:08:01,634 --> 00:08:04,050
これが実際にあることを見るでしょう
、ここではこの合計につながります

165
00:08:04,050 --> 00:08:07,970
n回nはマイナス1すべて2で割った。

166
00:08:07,970 --> 00:08:11,172
だから、今の私にはちょうど明記しましょう
これは、そのように信仰の飛躍に、真である

167
00:08:11,172 --> 00:08:12,880
それが、これは合計何
まで、私たちは可能性

168
00:08:12,880 --> 00:08:14,341
より一般的な場合にそれを証明する。

169
00:08:14,341 --> 00:08:15,590
しかし、今のはこれを拡張してみましょう。

170
00:08:15,590 --> 00:08:19,920
それはですのでそれでは、これを掛けてみましょう
nの二乗、マイナスnは、すべてが2で割った。

171
00:08:19,920 --> 00:08:23,200
それは、本当にだのn乗
マイナスnは2の上に、2で割った、

172
00:08:23,200 --> 00:08:25,010
その結果は、すべて素晴らしく、興味深いです。

173
00:08:25,010 --> 00:08:27,060
しかし、私たちとどうなる
今プラグイン値はありますか？

174
00:08:27,060 --> 00:08:29,724
私は8を持​​っていなかったとします
人が、万人に言う。

175
00:08:29,724 --> 00:08:31,890
そして、万人という理由だけで
それはかなり大きな数だが、

176
00:08:31,890 --> 00:08:34,039
のは、その中にプラグインして、何が起こるか見てみましょう。

177
00:08:34,039 --> 00:08:39,039
だから私は、その数式に万人を接続した場合
私は、万人が乗取得するつもりだ

178
00:08:39,039 --> 00:08:42,868
2で割った、マイナスA
百万ドルは、2で割った。

179
00:08:42,868 --> 00:08:44,159
今等しくしようとしていることは何ですか？

180
00:08:44,159 --> 00:08:47,354
だから5000億、マイナス50万。

181
00:08:47,354 --> 00:08:49,270
そして、私は実際に行うかどう
その数学アウト、その手段

182
00:08:49,270 --> 00:08:53,920
その仕分け人
バブルソートを持つ人

183
00:08:53,920 --> 00:09:01,800
私に4999.995億がかかる場合があります
最後のステップや比較、

184
00:09:01,800 --> 00:09:02,900
私たちは外挿している。

185
00:09:02,900 --> 00:09:06,860
>> これはかなり遅いと感じますが、率直に言って
1特定の入力を測定する

186
00:09:06,860 --> 00:09:09,160
このように、すべてのことを語っていない。

187
00:09:09,160 --> 00:09:14,050
しかし、確かに、それはnはそれを示唆していない
ますます大きく、このアルゴリズムを取得します

188
00:09:14,050 --> 00:09:16,280
ちょっと悪く感じ、
悪いことに、またはあなたが本当に

189
00:09:16,280 --> 00:09:20,450
それの痛みを感じ始める
べき乗、すなわちnは、乗

190
00:09:20,450 --> 00:09:21,770
これはかなり急速に追加されます。

191
00:09:21,770 --> 00:09:25,340
そして、このディテールではありません
実際には、人を失った

192
00:09:25,340 --> 00:09:29,640
数年前、ある上院議員だった人
選挙運動、面接のために座っ

193
00:09:29,640 --> 00:09:32,180
Googleのエリックと
シュミット、当時の最高経営責任者（CEO）、

194
00:09:32,180 --> 00:09:36,380
質問でチャレンジした
多くのように今日は模索しています。

195
00:09:36,380 --> 00:09:38,468
それでは見てみましょう。

196
00:09:38,468 --> 00:09:45,280
>> [ビデオ再生]

197
00:09:45,280 --> 00:09:48,560
>> -Senator、あなたはここにいる
グーグルで、私は好き

198
00:09:48,560 --> 00:09:53,382
大統領を考えるために
就職の面接など。

199
00:09:53,382 --> 00:09:56,434
今、それを得るのは難しい
社長としての仕事、

200
00:09:56,434 --> 00:09:58,100
そしてあなたは今厳しさを通じてつもりだ。

201
00:09:58,100 --> 00:10:01,860
それは、Googleの仕事を得ることも難しい。

202
00:10:01,860 --> 00:10:05,490
私たちは、質問がある、と私たち
私たちの候補者の質問を、

203
00:10:05,490 --> 00:10:09,770
この1つは、ラリー·シュワイマーからのものである。

204
00:10:09,770 --> 00:10:14,760
あなたたちは、私は思うWhat--
冗談、それはここです。

205
00:10:14,760 --> 00:10:17,930
への最も効率的な方法は何ですか
万人の32ビット整数を並べ替える？

206
00:10:17,930 --> 00:10:21,800

207
00:10:21,800 --> 00:10:24,350
>> -Well--

208
00:10:24,350 --> 00:10:25,200
>> 申し訳ありません-I'm、maybe--

209
00:10:25,200 --> 00:10:27,400
>> いや、いや、 - いいえ。

210
00:10:27,400 --> 00:10:30,700
私は、バブルソートを考える
どこへ行くか、間違った方法だろう。

211
00:10:30,700 --> 00:10:34,165

212
00:10:34,165 --> 00:10:38,180
>> -COMe上、誰が彼にこれを言った？

213
00:10:38,180 --> 00:10:40,590
私はコンピュータを見ていない
あなたの背景の科学。

214
00:10:40,590 --> 00:10:42,130
>> -We'veはそこに私たちのスパイを得た。

215
00:10:42,130 --> 00:10:44,930

216
00:10:44,930 --> 00:10:48,444
>> -OK、の異なる尋ねるみましょう
面接の質問。

217
00:10:48,444 --> 00:10:49,300
>> [END VIDEO再生]

218
00:10:49,300 --> 00:10:52,290
>> スピーカー：だからの話
しかし具体的な数値、

219
00:10:52,290 --> 00:10:53,890
すべてのことに有用であることを行っていません。

220
00:10:53,890 --> 00:10:56,810
それは、人生の教訓そのバブルではない
ソート、万人の入力を与え、

221
00:10:56,810 --> 00:10:58,590
できるだけ多く5000億などのステップがかかる場合があります。

222
00:10:58,590 --> 00:11:01,120
あなたは本当に一般化することはできません
あまりにも効果的とは

223
00:11:01,120 --> 00:11:03,560
そして良いデザインの意思決定を行う
プログラムを書くとき。

224
00:11:03,560 --> 00:11:07,070
それでは、どのようにも注目しましょう
私たちは、この結果を単純化することがあります。

225
00:11:07,070 --> 00:11:11,780
>> だから私はここに黄色で強調表示した
n個の結果は、2で割った値の二乗

226
00:11:11,780 --> 00:11:14,330
乗ので万人
2で除算し、次いで

227
00:11:14,330 --> 00:11:16,710
私は何を強調してきた
究極の答えはあった

228
00:11:16,710 --> 00:11:20,180
私たちはオフを差し引いた後、nは2で割った。

229
00:11:20,180 --> 00:11:24,850
そして、私が今するつもりだ主張は、ある
あなたがオフに引くかどうheckが気に誰が

230
00:11:24,850 --> 00:11:30,060
2時第1オーバー少し古いのn
この数式の一部はそんなに大きい？

231
00:11:30,060 --> 00:11:33,910
これは、他を支配
この用語は、nは2で割った二乗

232
00:11:33,910 --> 00:11:37,510
ように、明確に、そんなに大きい
nは、万人のように大きくなる

233
00:11:37,510 --> 00:11:41,450
それは本当にでは大きな差がある
5000億間の一日の終わりに

234
00:11:41,450 --> 00:11:45,730
と4999.995億？

235
00:11:45,730 --> 00:11:46,349
いまいち。

236
00:11:46,349 --> 00:11:48,640
だから私たちがしようとしているもの
コンピュータ科学者であるように行います

237
00:11:48,640 --> 00:11:53,270
これらの低次の項を無視して、
このような何かを取り、実際に

238
00:11:53,270 --> 00:11:56,050
単にそれを簡素化する
問題にはなるだろう言葉。

239
00:11:56,050 --> 00:12:00,315
当社のデータセットが取得大きく、大きく
私達のデータベースは、複数のウェブページを取得する

240
00:12:00,315 --> 00:12:02,690
私たちは、検索するより多くを持っている
あなたがFacebook上で持っている友人。

241
00:12:02,690 --> 00:12:07,340
>> nが大きくなると、私たちは本当にしている
最大の気にするつもりは

242
00:12:07,340 --> 00:12:11,560
任意のそのような分析での用語
私たちのアルゴリズムの性能。

243
00:12:11,560 --> 00:12:16,230
そして、私はあなたが何を知っている、と言うつもりです、
バブルソートは大きなOのオーダーである、

244
00:12:16,230 --> 00:12:18,060
n個のオーダーで二乗。

245
00:12:18,060 --> 00:12:20,090
それは、ちょうどnではありません
私たちが見てきたように乗、

246
00:12:20,090 --> 00:12:22,060
誰が本当に気に
これらのより小さな用語について、

247
00:12:22,060 --> 00:12:24,390
と率直に言って、誰が本当に
私たちは2で割る場合に気に？

248
00:12:24,390 --> 00:12:25,870
それはちょうど一定の係数です。

249
00:12:25,870 --> 00:12:29,480
そして、250対5000億です
億契約の本当に大きい？

250
00:12:29,480 --> 00:12:32,190
私はちょうど一年待つことができる、
文字通り私のラップトップを聞かせて

251
00:12:32,190 --> 00:12:34,810
ハードウェアでの倍の速取得、
その差のその種

252
00:12:34,810 --> 00:12:36,650
ちょうど時間をかけて自然に消えます。

253
00:12:36,650 --> 00:12:39,300
>> 私たちが気にすることはあり
表現、一部

254
00:12:39,300 --> 00:12:42,489
変化させるために起こっている表現の
私たちの入力がどんどん大きくなるにつれて。

255
00:12:42,489 --> 00:12:45,280
そして実際、現実の世界では、
それはますます何が起こっているのかだ

256
00:12:45,280 --> 00:12:48,330
私たちの問題への入力で、
アルゴリズムが大きくなっている。

257
00:12:48,330 --> 00:12:53,470
だから、大きなO記法であることを行っている、
漸近記法、私たちだけでは

258
00:12:53,470 --> 00:12:57,160
記述するためにコンピュータ科学者として使用
性能、走行時間、

259
00:12:57,160 --> 00:12:58,130
アルゴリズムの。

260
00:12:58,130 --> 00:13:00,800
私たちはアルゴリズムを比較できるように、
書かれた別のコンピュータ上で

261
00:13:00,800 --> 00:13:04,170
さまざまな人による、使用することにより
いくつかの基本的に同じようなメトリック

262
00:13:04,170 --> 00:13:07,557
比較の数のようにあなたがしている
多分スワップの数を作ったり、

263
00:13:07,557 --> 00:13:08,140
あなたが作っている。

264
00:13:08,140 --> 00:13:11,910
>> 私たちはするつもりはない
カウントは時間である

265
00:13:11,910 --> 00:13:13,981
それは時計を渡し
通常、壁に。

266
00:13:13,981 --> 00:13:16,230
私たちが心配するつもりはない
約どのくらいのメモリである。

267
00:13:16,230 --> 00:13:17,820
あなたが本日使用している
少なくとも、それはだけれども

268
00:13:17,820 --> 00:13:19,370
私たちが計測した場合、別のリソース。

269
00:13:19,370 --> 00:13:23,610
私達は私達の分析をベースにしようとするつもりだ
ただ、基本的な操作について、もの、

270
00:13:23,610 --> 00:13:25,930
率直に言って、あなたが最も視覚的に見ることができる。

271
00:13:25,930 --> 00:13:30,700
n個のビッグOのようなものとそう
乗、私は、nのOは二乗と主張している

272
00:13:30,700 --> 00:13:35,820
いわゆる上限です
バブルソートの実行時間。

273
00:13:35,820 --> 00:13:38,820
言い換えれば、あなたの場合
があることを主張したかった

274
00:13:38,820 --> 00:13:41,370
何でこの上限
アルゴリズムがかかることがあり、手順、

275
00:13:41,370 --> 00:13:46,240
それは、nの大きなOになるだろう
上限は、この場合、二乗。

276
00:13:46,240 --> 00:13:49,710
>> 私が代わりに変更された場合
バブルソートではないようにする話、

277
00:13:49,710 --> 00:13:50,910
しかし、この上限に関する。

278
00:13:50,910 --> 00:13:54,030
あなたは、アルゴリズムを考えることができます
私たちはすでに見てきたこと

279
00:13:54,030 --> 00:13:59,530
その上限は、最大
時間や動作を測定し、

280
00:13:59,530 --> 00:14:04,300
有界されると言われる
nは、線形関数によって

281
00:14:04,300 --> 00:14:07,260
湾曲したのではない二次1？

282
00:14:07,260 --> 00:14:10,780
そのアルゴリズムは何ですか
常にこれ以上取らない

283
00:14:10,780 --> 00:14:12,860
nステップ等より
2nのステップ、または3nのステップ？

284
00:14:12,860 --> 00:14:13,360
うん？

285
00:14:13,360 --> 00:14:15,030
>> 聴衆：検索
リストの中の最大の数は？

286
00:14:15,030 --> 00:14:16,930
>> スピーカー：パーフェクト、発見
リストの中の最大の数。

287
00:14:16,930 --> 00:14:18,940
私はのリストを与えられている場合は
例えば人、

288
00:14:18,940 --> 00:14:21,440
人のそれぞれは、番号を保持している
最大数は何ですか

289
00:14:21,440 --> 00:14:23,770
ステップでそれは私を取る必要があり、
合理的にスマートな人、

290
00:14:23,770 --> 00:14:27,530
そのリストで最大の人を見つけるには？

291
00:14:27,530 --> 00:14:28,100
nは、右か？

292
00:14:28,100 --> 00:14:31,320
最悪の場合には、どこにあるため
最大値はでしょうか？

293
00:14:31,320 --> 00:14:32,700
右、最後にすべての方法。

294
00:14:32,700 --> 00:14:34,575
最悪の場合にはそう
私は、上限かもしれません

295
00:14:34,575 --> 00:14:36,450
すべての道を行かなければならない
こっち等であっても、

296
00:14:36,450 --> 00:14:39,170
ああ、ここ数8ですが、
またはその値が何であれ。

297
00:14:39,170 --> 00:14:41,330
今ではただ愚かなことだろう
私が続けられた場合には、右か？

298
00:14:41,330 --> 00:14:43,840
より多くの要素を探して
そのうちの最後のは、あそこであれば？

299
00:14:43,840 --> 00:14:45,340
だからきっと、nが上限である。

300
00:14:45,340 --> 00:14:47,420
私は実行する必要はありません
それ以上のステップ。

301
00:14:47,420 --> 00:14:51,580
>> だから何かの代わりに私がすることを提案
この世界ではアルゴリズムが存在すること

302
00:14:51,580 --> 00:14:57,750
の稼働時間がある
ログnのビッグOで囲まれた、ログn？

303
00:14:57,750 --> 00:15:00,390
どこに前にこれを見たことがありますか？

304
00:15:00,390 --> 00:15:00,890
うん？

305
00:15:00,890 --> 00:15:03,309
>> 聴衆：電話帳の問題では？

306
00:15:03,309 --> 00:15:04,850
スピーカー：電話帳の問題のように。

307
00:15:04,850 --> 00:15:07,754
どのようにの尺度は何だった
多くの時間、またはどのように多くの涙、それ

308
00:15:07,754 --> 00:15:10,170
のような人を見つけるために連れて行ってくれました
電話帳内のマイク·スミス？

309
00:15:10,170 --> 00:15:13,212
私たちは、ログnを主張した、と
でも、不慣れな場合、またはそれです

310
00:15:13,212 --> 00:15:15,170
何A少しかすん
対数または指数だった、

311
00:15:15,170 --> 00:15:17,650
ちょうどそのログnを覚えている
一般的プロセスを指し、

312
00:15:17,650 --> 00:15:20,790
この場合は、分割する
再び、そして再び半分に何か、

313
00:15:20,790 --> 00:15:25,790
そして再び、そして再び、そのようなこと、その
あなたはそれを行うように、ますます小さな取得します。

314
00:15:25,790 --> 00:15:28,470
>> nは必ず、参照するのだからログインし、
電話帳を例に、

315
00:15:28,470 --> 00:15:32,662
理論的には二分探索に、とき、私たち
ボード上の仮想のドアを持っていた、

316
00:15:32,662 --> 00:15:34,370
またはショーンだったとき
何かを探し。

317
00:15:34,370 --> 00:15:37,374
彼はバイナリ検索を使用していた場合は、ログn
どのくらいの上限になります

318
00:15:37,374 --> 00:15:38,040
かかる時間。

319
00:15:38,040 --> 00:15:44,027
しかし、中に走ったそれらのアルゴリズム
nは何キー詳細を引き受けログ？

320
00:15:44,027 --> 00:15:45,360
リストは、右のソートされていること？

321
00:15:45,360 --> 00:15:47,789
あなたのアルゴリズムでは、もし間違っている
あなたの入力がソートされていない、

322
00:15:47,789 --> 00:15:49,830
まだあなたが使用している
バイナリサーチのようなもの

323
00:15:49,830 --> 00:15:51,704
あなたがジャンプする可能性がありますので、
右の要素の上に

324
00:15:51,704 --> 00:15:53,600
実現することなく、それは確かにありま​​す。

325
00:15:53,600 --> 00:15:55,600
>> さて、これは一つ、大きなOで何を意味するのでしょうか？

326
00:15:55,600 --> 00:15:59,117
これは、アルゴリズムという意味ではありません
唯一の一歩を踏み出し、

327
00:15:59,117 --> 00:16:01,200
それはちょうどそれがかかることを意味
ステップの定数。

328
00:16:01,200 --> 00:16:04,060
多分それは多分それはだ、1だ
10、多分それは千ですが、

329
00:16:04,060 --> 00:16:07,750
それはとは無関係だ
問題の大きさ。

330
00:16:07,750 --> 00:16:10,850
どんなに大きなnは、
定数時間アルゴリズム

331
00:16:10,850 --> 00:16:12,747
常に同じステップ数をとります。

332
00:16:12,747 --> 00:16:15,080
それでは、アルゴリズムかもしれない
私たちは話をしたか、単に

333
00:16:15,080 --> 00:16:20,418
直感的にそれがあることをあなたに来る
いつも、いわゆる一定の時間で実行されます？

334
00:16:20,418 --> 00:16:20,918
うん？

335
00:16:20,918 --> 00:16:22,001
>> 聴衆：二つの数字を追加します。

336
00:16:22,001 --> 00:16:25,320
スピーカー：二つの数字を追加し、
2プラス2は行われ、4に等しい。

337
00:16:25,320 --> 00:16:27,227
だから、うまくいくかもしれない、他に何？

338
00:16:27,227 --> 00:16:28,560
どのように、より現実の世界についての、ええ？

339
00:16:28,560 --> 00:16:30,686
>> 聴衆：検索
リストの最初のもの。

340
00:16:30,686 --> 00:16:32,810
スピーカー：最初の検索
リストの要素、確認してください。

341
00:16:32,810 --> 00:16:34,540
私たちは、実際に話をしてきた
すでにアレイに関する、

342
00:16:34,540 --> 00:16:36,540
どのように入手できますか
配列の最初の要素、

343
00:16:36,540 --> 00:16:40,465
どんなに長い
配列はCコードである？

344
00:16:40,465 --> 00:16:43,090
あなただけのブラケットのように使用します
ゼロ表記は、バム、あなたはそこにいる。

345
00:16:43,090 --> 00:16:46,120
余談としてそして実際の配列、
一般的に知られている何かをサポート

346
00:16:46,120 --> 00:16:49,240
ランダムアクセス、ランダムアクセスなど
メモリ、あなたは文字通りことができるので、

347
00:16:49,240 --> 00:16:50,284
いずれかの場所にジャンプします。

348
00:16:50,284 --> 00:16:52,700
私たちも、より簡単にこれを行うことができます
私たちは週にゼロに巻き戻すことができます

349
00:16:52,700 --> 00:16:53,900
私たちはスクラッチをしたとき。

350
00:16:53,900 --> 00:16:59,707
それがためにどのくらいの時間がかかりました
スクラッチでのブロックは実行に言う？

351
00:16:59,707 --> 00:17:00,790
ただ、一定の時間、右か？

352
00:17:00,790 --> 00:17:03,960
、何かを言うと言う
何か、それは問題ではない

353
00:17:03,960 --> 00:17:07,359
大きな傷の世界がどのように、それは常にです
同じ時間を取るつもり

354
00:17:07,359 --> 00:17:08,490
単に何かを言って。

355
00:17:08,490 --> 00:17:11,089
>> だから、一定の時間だ、
しかしフリップサイドは何ですか？

356
00:17:11,089 --> 00:17:13,030
それは、上側であった場合
境界、私たちが何をしたい場合

357
00:17:13,030 --> 00:17:17,089
下限を記述するために
私たちのアルゴリズムの時間を実行している？

358
00:17:17,089 --> 00:17:19,852
ほぼベストケース
潜在的に、可能ならば、

359
00:17:19,852 --> 00:17:23,060
これらの用語は最高に適用される可能性がありますが
ケース、最悪の場合、平均的なケースより

360
00:17:23,060 --> 00:17:26,359
一般的に、しかしちょうど注目しましょう
より一般的には下限について。

361
00:17:26,359 --> 00:17:31,920
持つアルゴリズムは何ですか
低い、nステップの下限

362
00:17:31,920 --> 00:17:33,350
または2nのステップ、または3nのステップ？

363
00:17:33,350 --> 00:17:36,241
nステップのいくつかの要因、
それは、その下限です。

364
00:17:36,241 --> 00:17:36,740
うん？

365
00:17:36,740 --> 00:17:37,910
>> 聴衆：バブルソート？

366
00:17:37,910 --> 00:17:41,610
>> スピーカー：バブルソート取る
あなた最小限nステップ、なぜですか？

367
00:17:41,610 --> 00:17:42,279
これはなぜですか？

368
00:17:42,279 --> 00:17:45,320
なぜそれはあなたに来て開始する必要があります
直感的に、それがない場合でも、だけではなく、

369
00:17:45,320 --> 00:17:46,530
まだ？

370
00:17:46,530 --> 00:17:47,030
うん？

371
00:17:47,030 --> 00:17:47,990
>> 聴衆：[聞こえない]。

372
00:17:47,990 --> 00:17:51,652

373
00:17:51,652 --> 00:17:52,360
スピーカー：その通り。

374
00:17:52,360 --> 00:17:55,810
の可能な限り最高のシナリオでは
バブルソート、およびアルゴリズムの多くは、

375
00:17:55,810 --> 00:17:58,769
私はあなたに8人が手にした場合
誰がすでにソートされている、

376
00:17:58,769 --> 00:18:00,560
それは愚かなことだ
あなたのために、アルゴリズム、

377
00:18:00,560 --> 00:18:02,202
前後に行くために
何度も、右か？

378
00:18:02,202 --> 00:18:04,285
とすぐにあなたとあるので
一度リストの中を歩く、

379
00:18:04,285 --> 00:18:08,090
あなたは、実現すべきああ、私が作ったノー
スワップは、このリストは、出口にソートされます。

380
00:18:08,090 --> 00:18:09,700
しかし、それは、あなたのnのステップを取ることになるだろう。

381
00:18:09,700 --> 00:18:12,033
>> 逆に、別のものだ
それについての考え方？

382
00:18:12,033 --> 00:18:15,240
バブルソートは、オメガである、
これのN、話す、

383
00:18:15,240 --> 00:18:19,050
あなたが見れば理由
どのようなn個の要素、より少ない

384
00:18:19,050 --> 00:18:23,009
根本的な問題はありますか？

385
00:18:23,009 --> 00:18:24,550
それは、右のソートだ場合は、知りません。

386
00:18:24,550 --> 00:18:26,800
私たちは8時マイトの視線を人間
人とは、、のようなああ、それはソートだこと

387
00:18:26,800 --> 00:18:28,430
それは私のnステップを取らなかったが、それはなかった。

388
00:18:28,430 --> 00:18:30,810
あなたの目、にもかかわらず、あなたの種類の
のビジョンの大きな視野を持って、

389
00:18:30,810 --> 00:18:33,184
あなたは8つの要素を見て、
あなたは八人を見て、

390
00:18:33,184 --> 00:18:34,610
それが効果的に8つのステップです。

391
00:18:34,610 --> 00:18:38,612
そして、私は、全体の中を歩く場合にのみ、
リストには、私は、はい、ソートされ、実現しません。

392
00:18:38,612 --> 00:18:41,320
私は途中ですべて、思考停止した場合
右、それはかなり、これまでのソートだ

393
00:18:41,320 --> 00:18:42,520
それはソートされていないだオッズは何ですか？

394
00:18:42,520 --> 00:18:44,186
それは正しいことを行っていないアルゴリズム。

395
00:18:44,186 --> 00:18:46,250
速いが、正しくない可能性があります。

396
00:18:46,250 --> 00:18:48,500
>> だから今、私たちはの方法を持っている
下限を記述し、

397
00:18:48,500 --> 00:18:49,710
そして、時定数約何？

398
00:18:49,710 --> 00:18:54,565
下を持つアルゴリズムは何ですか
1、その実行時間の下限？

399
00:18:54,565 --> 00:18:58,350
1ステップ、2ステップ、10ステップが、
、定数nは独立して、

400
00:18:58,350 --> 00:18:59,310
入力のサイズは？

401
00:18:59,310 --> 00:19:03,930

402
00:19:03,930 --> 00:19:04,600
ええ、後ろに。

403
00:19:04,600 --> 00:19:05,309
>> 聴衆：のprintf？

404
00:19:05,309 --> 00:19:06,183
スピーカー：それは何ですか？

405
00:19:06,183 --> 00:19:07,184
聴衆：のprintf？

406
00:19:07,184 --> 00:19:07,850
スピーカー：のprintf。

407
00:19:07,850 --> 00:19:08,400
[OK]を、確認してください。

408
00:19:08,400 --> 00:19:10,720
だから、ステップの固定数を取ります。

409
00:19:10,720 --> 00:19:13,170
そして、私は今ではnow--必要があります
私たちはCコードの話をしている

410
00:19:13,170 --> 00:19:16,040
そして、何かをスクラッチしない
、と言うようなのprintfと、

411
00:19:16,040 --> 00:19:17,710
私たちは慎重に取得するために開始する必要があります。

412
00:19:17,710 --> 00:19:21,090
printfのは時間がかかりますかので
入力は、文字列ですが、

413
00:19:21,090 --> 00:19:23,220
や文字列は、技術的に長さを持っています。

414
00:19:23,220 --> 00:19:25,530
だから私たちは現在、ピックアップする場合は、
あなたに、あなたは気にしない場合には、

415
00:19:25,530 --> 00:19:29,430
技術的に、私たちはそのprintfのを主張する可能性が
可変長の入力を取得し、

416
00:19:29,430 --> 00:19:32,270
そして確かにそれはより多くかかることがあります
この長い文字列を表示するための時間、

417
00:19:32,270 --> 00:19:33,560
この長いより。

418
00:19:33,560 --> 00:19:36,570
>> だから私たちは何を検討している場合
仕分けと例をお探しですか？

419
00:19:36,570 --> 00:19:40,450
電話でのマイク·スミスについての何
ブック、またはより一般的には二分探索？

420
00:19:40,450 --> 00:19:42,220
最良のケースでは、何が起こるのでしょうか？

421
00:19:42,220 --> 00:19:45,577
私は、バム、電話帳を開いて、
マイク·スミスの数があります。

422
00:19:45,577 --> 00:19:46,660
私はすぐに彼を呼び出すことができます。

423
00:19:46,660 --> 00:19:49,390
>> 一歩、多分2つのステップを取った、
しかしステップの一定数の

424
00:19:49,390 --> 00:19:50,230
私は幸運であれば。

425
00:19:50,230 --> 00:19:52,570
そして、率直に言って、私たちは上を見た
月曜日あなたの同級生

426
00:19:52,570 --> 00:19:54,710
2回続けて非常に幸運。

427
00:19:54,710 --> 00:19:57,050
そして、それは確かに一定であった
下限の時間

428
00:19:57,050 --> 00:20:01,280
問題のアルゴリズムに見つけるための
閉じそれらの背後にある数50

429
00:20:01,280 --> 00:20:01,830
ドア。

430
00:20:01,830 --> 00:20:06,400
>> さて、余談ですが、あなたは発見するかのように
ビッグO、上限、両方その

431
00:20:06,400 --> 00:20:09,310
オメガ、下限、
その同じの1である

432
00:20:09,310 --> 00:20:11,830
同式は、
括弧、あなたもできます

433
00:20:11,830 --> 00:20:15,170
ちょうど空想であると言う
その何かがシータにあり

434
00:20:15,170 --> 00:20:18,270
nまたは他の値のシータの。

435
00:20:18,270 --> 00:20:20,661
それはちょうどその時、大きな意味
Oとオメガは同じです。

436
00:20:20,661 --> 00:20:21,910
今どのような選択ソートはどうですか？

437
00:20:21,910 --> 00:20:23,400
それではこの新しい語彙を使用してみましょう。

438
00:20:23,400 --> 00:20:27,407
選択ソートでは、何だった
もう一度やって、そして再び、そして再び？

439
00:20:27,407 --> 00:20:29,990
私が通って行き来した
リストには、誰をお探しですか？

440
00:20:29,990 --> 00:20:33,260

441
00:20:33,260 --> 00:20:34,730
最小数。

442
00:20:34,730 --> 00:20:37,560
>> それでは、どのよう多くの手順、方法
多くの比較は私でした

443
00:20:37,560 --> 00:20:43,250
誰を把握するために行う必要があります
リスト中の最小要素でしたか？

444
00:20:43,250 --> 00:20:44,437
nはマイナス1、右か？

445
00:20:44,437 --> 00:20:47,770
私はちょうど私は1で始まる場合は、そのため
与えられたと私は彼または彼女を比較開始、

446
00:20:47,770 --> 00:20:49,519
その後、彼または彼女は彼
または彼女は彼または彼女は、私

447
00:20:49,519 --> 00:20:52,010
要素のみをペアリングすることができます
一緒のn  -  1回。

448
00:20:52,010 --> 00:20:55,630
だから選択はソートも同様に取り
nはマイナス1は、第1回繰り返します。

449
00:20:55,630 --> 00:20:59,540
>> それはに私を取るんどのように多くの手順
二番目に小さい要素を見つける？

450
00:20:59,540 --> 00:21:02,920
nはマイナス2、私はだから、ダムであること
私は、同じ人を見続ければ

451
00:21:02,920 --> 00:21:06,280
再び私はすでに彼を選択した場合は、
または彼女とその場所にそれらを置く。

452
00:21:06,280 --> 00:21:09,270
そして第三段階はn
マイナス3、そしてnはマイナス4。

453
00:21:09,270 --> 00:21:11,020
私たちは、このパターンを見てきました
の前に、実際

454
00:21:11,020 --> 00:21:13,460
選択ソート同様
上限があります

455
00:21:13,460 --> 00:21:16,210
私たちは、その総和を行う場合は、nの二乗。

456
00:21:16,210 --> 00:21:19,790
その下限、選択ソートとは何ですか？

457
00:21:19,790 --> 00:21:25,350
最低限、どのくらいの時間の必須の選択
私たちは月曜日にそれを定義されている並べ替え、取る？

458
00:21:25,350 --> 00:21:29,370

459
00:21:29,370 --> 00:21:30,490
つのオプションを提案する。

460
00:21:30,490 --> 00:21:32,360
多分それは以前と同様に、Nさん。

461
00:21:32,360 --> 00:21:35,040
多分それはそれとして、二乗Nさん
上限として、今です。

462
00:21:35,040 --> 00:21:35,874
>> 聴衆：nの二乗。

463
00:21:35,874 --> 00:21:36,664
スピーカー：nの二乗。

464
00:21:36,664 --> 00:21:37,368
なぜ？

465
00:21:37,368 --> 00:21:40,060
>> 聴衆：あなたが持っているので
[聞き取れない]を定義します。

466
00:21:40,060 --> 00:21:41,510
>> スピーカー：その通り。

467
00:21:41,510 --> 00:21:45,077
私は、選択ソートを定義した少なくとも同
それはかなりナイーブだった、続ける、

468
00:21:45,077 --> 00:21:46,160
最小の要素を探します。

469
00:21:46,160 --> 00:21:47,770
最小の要素を見つけ、再度行く。

470
00:21:47,770 --> 00:21:49,490
最小の要素を見つけ、再度行く。

471
00:21:49,490 --> 00:21:51,700
のないソートはありません
そこに、その中で最適化

472
00:21:51,700 --> 00:21:54,350
私は後に中止させていただく場合がございます
ちょうどn個かそこらのステップ。

473
00:21:54,350 --> 00:21:57,080
だから実際には、選択
ソート、n個のオメガ二乗。

474
00:21:57,080 --> 00:22:00,667
>> 私が撮った挿入ソート、約どのような
私は与えられたし、私は彼をそのまま流し方

475
00:22:00,667 --> 00:22:01,750
または彼女の右の場所で？

476
00:22:01,750 --> 00:22:04,958
それから私は、二人目に進ん
正しい場所に彼または彼女をそのまま流し。

477
00:22:04,958 --> 00:22:07,910
そして、次の人は、そのまま流し
彼または彼女の右の場所で。

478
00:22:07,910 --> 00:22:10,537
これは非常にあることに注意してください
いわばリニア、。

479
00:22:10,537 --> 00:22:12,620
私は私は、直線よ
行ったり来たりしない、

480
00:22:12,620 --> 00:22:16,080
私は本当に戻って見ていないが、初めてだ
私は彼を挿入したときに何が起こっている

481
00:22:16,080 --> 00:22:20,302
または彼女の先頭へ
私たちは月曜日に行ったように、リスト？

482
00:22:20,302 --> 00:22:21,010
何が起きているのでしょうか？

483
00:22:21,010 --> 00:22:21,510
うん？

484
00:22:21,510 --> 00:22:23,122
聴衆：[聞こえない]。

485
00:22:23,122 --> 00:22:24,830
スピーカー：ええ、その
右、キャッチでしたか？

486
00:22:24,830 --> 00:22:26,746
あなたが思い出すかもしれませんから
クラスメート、彼らの場合

487
00:22:26,746 --> 00:22:29,670
との任意の動きを作っていた
自分の足、それが動作した。

488
00:22:29,670 --> 00:22:33,610
だからここに3人があった場合には
新しい人は、そこに道の上に属し

489
00:22:33,610 --> 00:22:37,360
このような長いステージ上で、確かに、彼
または彼女はちょうど最後の最後まで行くことができます。

490
00:22:37,360 --> 00:22:40,074
しかし、私たちは考えている場合は、
コンピュータとメモリの配列、

491
00:22:40,074 --> 00:22:41,990
これらの人々が行っている
オーバーシャ​​ッフルに持っている

492
00:22:41,990 --> 00:22:43,260
その人のための部屋を作る。

493
00:22:43,260 --> 00:22:46,930
そして、その結果、nはマイナス1 shufflings、
nはマイナス2 shufflings、n個

494
00:22:46,930 --> 00:22:50,660
マイナス3 shufflingsはただ一種のです
私の後ろではなく、私の目の前で起こって

495
00:22:50,660 --> 00:22:52,710
以前のように、ある意味で。

499
00:22:52,557 --> 00:22:54,640
今はさておき、などなど
あなたがオンラインで見ているかもしれません

500
00:22:54,640 --> 00:22:57,699
何についてチャンスをうかがっ起動した場合
ソート、非常に多くの異なるものがあります

501
00:22:57,699 --> 00:22:59,490
そのうちそこに、いくつかの
他よりも優れています。

502
00:22:59,490 --> 00:23:02,200
実際、bogosortは1である
それがルックアップする楽しみのようなものだ。

503
00:23:02,200 --> 00:23:06,650
Bogosortはセットを取る
番号やカードのデッキを言う、

504
00:23:06,650 --> 00:23:09,870
ランダムにシャッフルし、
彼らはソートしている場合はチェックします。

505
00:23:09,870 --> 00:23:12,130
ない場合には、再びない。

506
00:23:12,130 --> 00:23:14,140
ない場合には、再びない。

507
00:23:14,140 --> 00:23:15,440
そうでない場合は、再びない。

508
00:23:15,440 --> 00:23:17,060
信じられないほど愚かな。

509
00:23:17,060 --> 00:23:19,520
>> そして実際、あなたが読んでいる場合
Wikipediaの記事のように、

510
00:23:19,520 --> 00:23:21,200
そのニックネームは愚かなものです。

511
00:23:21,200 --> 00:23:25,180
それは最終的に動作しますが、
うまくいけば、十分な時間を与え、

512
00:23:25,180 --> 00:23:28,240
しかしその時間
かなりの時間がかかることがあります。

513
00:23:28,240 --> 00:23:31,650
私ができるのであれば、のは物事をスピードアップしましょう
以前のメアリーベスの例からアップ、

514
00:23:31,650 --> 00:23:35,150
さらにいくつかの要素を有することによって、
2つ以上のプロセッサ。

515
00:23:35,150 --> 00:23:37,100
二人、よろしければ
私を参加気にしないだろう。

516
00:23:37,100 --> 00:23:40,972
どのように約1こっち、と
それではあそこ誰もgo--ないしましょう​​？

517
00:23:40,972 --> 00:23:41,722
あそこ誰か？

518
00:23:41,722 --> 00:23:42,221
[OK]をクリックします。

519
00:23:42,221 --> 00:23:44,190
黒であなた
シャツは、はい、ダウン来る。

520
00:23:44,190 --> 00:23:45,000
すべての権利、あなたの名前は何ですか？

521
00:23:45,000 --> 00:23:45,720
>> 聴衆：ピーター。

522
00:23:45,720 --> 00:23:46,100
>> スピーカー：それは何ですか？

523
00:23:46,100 --> 00:23:46,766
>> 聴衆：ピーター。

524
00:23:46,766 --> 00:23:49,450
スピーカー：ピーター、デビッド、はじめまして。

525
00:23:49,450 --> 00:23:53,670
すべての権利、私たちは、ここでピーターを持っているあなたの場合
こっちのテーブルの上に来てほしい。

526
00:23:53,670 --> 00:23:54,550
そして、あなたの名前は何ですか？

527
00:23:54,550 --> 00:23:55,216
>> 聴衆：エレナ。

528
00:23:55,216 --> 00:23:55,970
スピーカー：エレナ。

529
00:23:55,970 --> 00:23:57,030
OK、はじめまして。

530
00:23:57,030 --> 00:23:58,060
エレナはピーターを満たしています。

531
00:23:58,060 --> 00:23:59,170
ピーター、エレナ。

532
00:23:59,170 --> 00:24:02,290
そして、私たちはアンドリューが必要です
ここでもアップでお願いします。

533
00:24:02,290 --> 00:24:06,107
そして、あなたの課題は、起こっている
カードのデッキをソートすることができます。

534
00:24:06,107 --> 00:24:08,190
そして不慣れな場合は、デッキ
カードべき究極的に

535
00:24:08,190 --> 00:24:11,064
のような少し何かをソートする
私たちはその後、クラブをやるときは、この

536
00:24:11,064 --> 00:24:13,660
その後スペード、ハートと
一つとしてエースからダイヤモンド、、

537
00:24:13,660 --> 00:24:15,570
王までのすべての方法。

538
00:24:15,570 --> 00:24:20,890
>> 私はあなたを与えるつもりだカード
量が52であることを行っている。

539
00:24:20,890 --> 00:24:23,160
私たちは、同じようにするつもりだ
ちょっと時間ができ、。

540
00:24:23,160 --> 00:24:26,410
私たちはアンドリューをスローするつもりだ
ここで画面上に、

541
00:24:26,410 --> 00:24:28,170
これを行うように見るようにする。

542
00:24:28,170 --> 00:24:31,070
だからこれのすべてのこと
、すべてがより見えている

543
00:24:31,070 --> 00:24:33,490
これらは、私がアマゾンに乗ったカードです。

544
00:24:33,490 --> 00:24:42,861
そこで、彼らはランダムにすでに
ソートされ、私たちはあなたのタイミングをするつもりだ。

545
00:24:42,861 --> 00:24:44,610
そして、私たちはするつもりだ
本当のこの時間は、それを維持し、

546
00:24:44,610 --> 00:24:47,820
私たちはあなたに圧力をしようとしている
そうでなければ、これは退屈でしょう理由

547
00:24:47,820 --> 00:24:48,460
すぐに。

548
00:24:48,460 --> 00:24:53,860
あなたが52を並べ替えるに進みことができれば
今一緒にいくつかの手段を介して要素。

549
00:24:53,860 --> 00:25:04,710

550
00:25:04,710 --> 00:25:07,180
>> そして再び、私たちはこれらを見ながら
人は最終的に、何をすべきか

551
00:25:07,180 --> 00:25:10,200
明白なことを生成するために起こっている
結果は、本当に考える

552
00:25:10,200 --> 00:25:12,962
どのように彼らはお互いにそれをやっている、
どのようにそれを記述することがあります。

553
00:25:12,962 --> 00:25:15,045
再び、これらは理由
すべてのプロセス、アルゴリズム、

554
00:25:15,045 --> 00:25:17,090
人間として当たり前の私たちは取ること。

555
00:25:17,090 --> 00:25:22,349
しかし、あなたは、おそらく長い間持っていた
直感、限り、あなたの前にあっても

556
00:25:22,349 --> 00:25:24,390
服用を考えた
コンピュータサイエンスのクラスます

557
00:25:24,390 --> 00:25:27,223
との直感を持っていたかもしれない
これは、このような問題点を解決する。

558
00:25:27,223 --> 00:25:29,560
しかし、あなたが認識したら、
パターンと開始

559
00:25:29,560 --> 00:25:32,407
での手順を形式化するために
あなたはこれらの問題を解決している、

560
00:25:32,407 --> 00:25:35,490
あなたは多くを解決できることを見つけることができます
より興味深く、はるかに複雑

561
00:25:35,490 --> 00:25:39,190
迅速に問題。

562
00:25:39,190 --> 00:25:42,351
だから、聴衆から誰かが、何か
アルゴリズムの少なくとも1つの要素

563
00:25:42,351 --> 00:25:43,350
彼らはここ使用していること？

564
00:25:43,350 --> 00:25:44,275
>> 聴衆：[聞き取れない]

565
00:25:44,275 --> 00:25:45,150
スピーカー：それは何ですか？

566
00:25:45,150 --> 00:25:47,062
聴衆：スーツバイ。

567
00:25:47,062 --> 00:25:47,770
スピーカー：スーツバイ。

568
00:25:47,770 --> 00:25:50,630
したがって、最初の彼らはクラスタリングされている
ダイヤモンドのすべて一緒に

569
00:25:50,630 --> 00:25:52,560
それは、全て思わ
一緒にそれはそう心、

570
00:25:52,560 --> 00:25:56,520
など、尊敬せずに
カードの番号などです。

571
00:25:56,520 --> 00:26:00,900
そして今、彼らは、例えば、表示され、
数によってそれらをソートする。

572
00:26:00,900 --> 00:26:06,870

573
00:26:06,870 --> 00:26:08,910
非常に良い。

574
00:26:08,910 --> 00:26:12,370
>> すべての権利、これに何が起こっているか
ここで、最終的な段階である？

575
00:26:12,370 --> 00:26:16,950
私たちは、4つのソートされたスーツを持っていたら、どのような
私たちは4山に何をする必要があります

576
00:26:16,950 --> 00:26:20,059
1を達成するために、
非常に単純に、デッキをソート？

577
00:26:20,059 --> 00:26:21,350
だから私たちは再びそれらをマージする必要があります。

578
00:26:21,350 --> 00:26:25,160
>> だから面白いアイデアがあります
再び、あえて言う、でも非常に直感的です

579
00:26:25,160 --> 00:26:28,140
あなたが平手打ちことはなかった可能性がある場合
その上の標識のようなもの。

580
00:26:28,140 --> 00:26:31,900
分割するこの基本的な概念
この半分の時間で問題ではない、

581
00:26:31,900 --> 00:26:33,410
しかし、少なくとも4個に。

582
00:26:33,410 --> 00:26:36,810
ほとんどの解決
基本的には同一の問題

583
00:26:36,810 --> 00:26:40,480
互いの単離において、
し、結果をマージする。

584
00:26:40,480 --> 00:26:46,940

585
00:26:46,940 --> 00:26:50,140
そして、優れた、やった。

586
00:26:50,140 --> 00:26:52,140
すべての権利は​​、大きな丸い
拍手の、私たちができれば。

587
00:26:52,140 --> 00:26:56,480
>> [拍手]

588
00:26:56,480 --> 00:26:59,740
>> スピーカー：私は何をよ見当がつかない
これらとは、しかしここに行く。

589
00:26:59,740 --> 00:27:01,690
どうもありがとうございました。

590
00:27:01,690 --> 00:27:04,660
それでは、2分見てみましょう
そして8秒、

591
00:27:04,660 --> 00:27:07,490
あなたの友人に挑戦したいと思います。

592
00:27:07,490 --> 00:27:12,160
その後何になるだろう
このことから奪うこと

593
00:27:12,160 --> 00:27:13,830
私たちは、より一般的に活用できる​​のか？

594
00:27:13,830 --> 00:27:16,080
さて、戻って考える
この数値の配列、

595
00:27:16,080 --> 00:27:19,060
とのいくつかにすぐに戻って考える
私たちは、過去に書いた擬似コード、

596
00:27:19,060 --> 00:27:22,080
これはのための擬似コードだった
電話帳の問題を解決する。

597
00:27:22,080 --> 00:27:25,150
これにより擬似コードでは、私は
より系統的な方法を列挙し

598
00:27:25,150 --> 00:27:28,400
私は非常に直感的にやった方法を説明するの
電話を分割する人間アルゴリズム

599
00:27:28,400 --> 00:27:31,650
半分に本、繰り返し、繰り返し、繰り返し、
私はマイク·スミスのような人を見つけるまで、

600
00:27:31,650 --> 00:27:33,790
彼は電話帳に実際にある場合。

601
00:27:33,790 --> 00:27:37,610
>> しかし、私は一種の私が電話するよ何に使用
ここで非常に反復アプローチ、

602
00:27:37,610 --> 00:27:42,160
特に通知の中8行目と11行目。

603
00:27:42,160 --> 00:27:46,750
これらは、反復の証拠である
アプローチ、ルーピングの手法、

604
00:27:46,750 --> 00:27:49,040
それはまさにだから
彼らが誘発する行動。

605
00:27:49,040 --> 00:27:52,910
これらの行の両方がに行くと言う
ライン3、そしてあなたができるような

606
00:27:52,910 --> 00:27:55,140
あなたにそのことを考える
ループものとして心の目。

607
00:27:55,140 --> 00:27:59,080
これは、バックステップに上がるためにあなたを伝えるだ
3を繰り返し、再び、そして再び、

608
00:27:59,080 --> 00:28:00,010
そして再び。

609
00:28:00,010 --> 00:28:04,410
>> しかし、私たちは主要なアイデアをどのように活用した場合
ここで私たちは前回しなかったことを、

610
00:28:04,410 --> 00:28:10,280
そして、ライン8を簡素化し、
11行目とその隣人

611
00:28:10,280 --> 00:28:12,840
ちょうどこの、黄色のように。

612
00:28:12,840 --> 00:28:16,480
それは基本的に短くしないです
擬似コード非常に多く、

613
00:28:16,480 --> 00:28:20,530
それは根本的に変えることだ
私のアルゴリズムの性質に依存する。

614
00:28:20,530 --> 00:28:24,220
私が今言っている
手順7で、ステップ10において、

615
00:28:24,220 --> 00:28:29,140
マイクを検索することです
まったく同じ方法で、

616
00:28:29,140 --> 00:28:31,580
ちょうど左側にある
半分または右半分。

617
00:28:31,580 --> 00:28:33,420
>> そのように、換言すれば、もし
私は、ステップ1からスタート

618
00:28:33,420 --> 00:28:36,150
中央に開いた、電話帳をピックアップ
電話帳の名前を見て、

619
00:28:36,150 --> 00:28:39,010
スミスは間にある場合には
名前の、マイク、他の呼び出し

620
00:28:39,010 --> 00:28:44,340
スミスは、以前の本の中であれば、7ステップ
本の左半分にマイクを検索してください。

621
00:28:44,340 --> 00:28:47,130
しかし、そのようなもののように感じている
それは正しい、ぶら下がっ私を残している？

622
00:28:47,130 --> 00:28:49,240
黄色で表示されます
命令が、私をどのように行う

623
00:28:49,240 --> 00:28:51,870
左にマイクを検索
電話帳の半分？

624
00:28:51,870 --> 00:28:54,210
私はどこにありますか
私とアルゴリズム

625
00:28:54,210 --> 00:28:57,100
マイク·スミスのような人を検索することができますか？

626
00:28:57,100 --> 00:28:58,980
まあ、それは顔で私たちを見つめています。

627
00:28:58,980 --> 00:29:03,090
私は、文字通り、まったく同じを使用することができます
プログラムは、効果的にトップに上がっていく

628
00:29:03,090 --> 00:29:06,490
何度も再実行
同じコード行。

629
00:29:06,490 --> 00:29:10,610
>> だから、これは感じるはずにもかかわらず、
循環的な定義のビットのような

630
00:29:10,610 --> 00:29:13,480
あなたが誰かのに答えるどこ
ちょうど一種の尋ねることで問題

631
00:29:13,480 --> 00:29:15,990
再び同じ質問、
のような、なぜ、なぜ、なぜ？

632
00:29:15,990 --> 00:29:21,580
私たちは、ハードコーディングされたので現実はある
特別な数行、手順4、

633
00:29:21,580 --> 00:29:25,320
、あれば、ステップ12であるその
効果的に別のブランチであり、

634
00:29:25,320 --> 00:29:30,120
私たちはそれらのその場しのぎの対策を持っているので、
私たちは、このアルゴリズムは終了します

635
00:29:30,120 --> 00:29:32,050
マイクを見つけるか、私たちはしないと。

636
00:29:32,050 --> 00:29:36,810
しかし、今のステップ7と10年には持っている
私たちは再帰アルゴリズムと呼ぶことにします。

637
00:29:36,810 --> 00:29:40,420
そして、再帰は確かに強力なアイデアです
それは、最初は少し曲げ心だ

638
00:29:40,420 --> 00:29:42,500
次のように私たちが今、適用する。

639
00:29:42,500 --> 00:29:46,600
>> 最後のソートになるソートマージすること
私たちは正式には少なくともクラスで、見てください。

640
00:29:46,600 --> 00:29:50,040
そして、それは根本的に違う
これらの最後の3つから、確か

641
00:29:50,040 --> 00:29:52,140
最後の4つは、私たちはbogosortが含ま​​れている場合。

642
00:29:52,140 --> 00:29:54,810
ここではマージソートのための擬似コードです。

643
00:29:54,810 --> 00:30:00,170
n個の要素の入力にするため、ある場合には
大きさnの配列、nが2未満である場合には、

644
00:30:00,170 --> 00:30:01,040
リターン。

645
00:30:01,040 --> 00:30:03,610
では、なぜ私はそれを持っています
正気最初のチェック？

646
00:30:03,610 --> 00:30:09,477
私はあなたを渡した場合に意味の周辺情報
その長さnの配列が2未満である？

647
00:30:09,477 --> 00:30:11,060
それはすでに、右、明らかに、ソートされたのですか？

648
00:30:11,060 --> 00:30:13,640
リストには、どちらか持っているので
自明である一つの要素、

649
00:30:13,640 --> 00:30:15,180
それはだからソート
そこに唯一のもの。

650
00:30:15,180 --> 00:30:18,138
それとも、それは意味の大きさゼロのためです
本質的になるようにソートするものは何も、ありません

651
00:30:18,138 --> 00:30:18,720
それがソートされます。

652
00:30:18,720 --> 00:30:20,410
そこに間違っただけでは何もありません。

653
00:30:20,410 --> 00:30:22,310
だから、私たちの、いわゆるベースケースです。

654
00:30:22,310 --> 00:30:24,440
>> つまり、基本的に変わるところである
私たちはマイクで何をしたかと。

655
00:30:24,440 --> 00:30:26,023
マイクの電話帳にある場合は、彼に電話。

656
00:30:26,023 --> 00:30:27,740
彼がそこにいないなら、あきらめる。

657
00:30:27,740 --> 00:30:31,240
それは確認する、いわゆるベースケースだ
一日の終わりに、このアルゴリズム

658
00:30:31,240 --> 00:30:33,540
特定の状況で停止します。

659
00:30:33,540 --> 00:30:37,890
>> しかし、ここで信仰の飛躍は、他に、今だ
要素の左半分を並べ替える

660
00:30:37,890 --> 00:30:39,740
右を並べ替える
要素の半分、

661
00:30:39,740 --> 00:30:41,189
してからソートされた半分をマージ。

662
00:30:41,189 --> 00:30:43,230
それは感じているところそして、ここだ
私たちは盗むしているような。

663
00:30:43,230 --> 00:30:46,900
私は、並べ替えることができます求めてきました
n個の要素、と私は今

664
00:30:46,900 --> 00:30:50,712
[OK]を、ソートしてそれを行う、と言って
左と右のソート。

665
00:30:50,712 --> 00:30:52,420
しかし、私は1つを言っている
他の事、そしてこの

666
00:30:52,420 --> 00:30:55,530
それはそう重要なテーマであり、
これまで勘と、

667
00:30:55,530 --> 00:30:57,380
マージのこの第三段階があります。

668
00:30:57,380 --> 00:31:00,430
どちらも、それも
精神でそのようにダムだが、

669
00:31:00,430 --> 00:31:02,320
のような物事をマージ
一緒に、それが思われる

670
00:31:02,320 --> 00:31:05,380
に向けた重要なステップであると
その二つの問題の再組み立て

671
00:31:05,380 --> 00:31:07,330
半分に最終的に分割した。

672
00:31:07,330 --> 00:31:12,090
>> あなただろう場合それでは、これをやらせる、ソートマージ
もう一つのデモンストレーションとユーモア私、、

673
00:31:12,090 --> 00:31:14,730
ちょうどそのように私たちはいくつかを持っている
で動作する数字。

674
00:31:14,730 --> 00:31:19,470
私は8ストレスを交換することができます
8人のためのボール？

675
00:31:19,470 --> 00:31:29,320
どのように約3すべての権利、あなた4
このセクション、5つ、6つ、そしてみましょう中

676
00:31:29,320 --> 00:31:30,720
7、図8に示すように、投入時に来るのか。

677
00:31:30,720 --> 00:31:35,120

678
00:31:35,120 --> 00:31:36,520
[OK]うん、OK。

679
00:31:36,520 --> 00:31:38,640
マイナス8は、そこに私達は行く、プラス1。

680
00:31:38,640 --> 00:31:39,150
優秀。

681
00:31:39,150 --> 00:31:42,000
すべての右、上に来てみましょう
すぐにあなたの番号を与える。

682
00:31:42,000 --> 00:31:50,800
ナンバー2、ナンバー3、4番、
数5つ、6つ、7つ、8。

683
00:31:50,800 --> 00:31:52,140
私は正しくこの時間を8でした。

684
00:31:52,140 --> 00:31:56,390
>> そう、あなたができれば先に行くと、
それでは元の順序で並べ替えてみましょう

685
00:31:56,390 --> 00:31:59,810
昨日持っていたことを見ている
このように、あなたは気にしないならば。

686
00:31:59,810 --> 00:32:03,620
そしてのは、テーブルの前でそれを行うことができます。

687
00:32:03,620 --> 00:32:06,510
すべての権利なので、ソートマージ。

688
00:32:06,510 --> 00:32:08,820
それが起こっている場所です
興味深いの種類を取得するには、

689
00:32:08,820 --> 00:32:12,800
私は自分自身を与えているように見えるので、
そんなに少ない情報今日。

690
00:32:12,800 --> 00:32:15,149
>> したがって、最初のすべてのマージソート
n個の要素の入力で、

691
00:32:15,149 --> 00:32:18,440
それがだ、明らかではない2未満である
8ので、私は行うにいくつかのより多くの仕事を持っている。

692
00:32:18,440 --> 00:32:21,140
だから今精神的に私たちのクラスとして
他の枝に今ある、

693
00:32:21,140 --> 00:32:22,540
その3つのステップを意味します。

694
00:32:22,540 --> 00:32:25,017
第一に、私はソートする必要が
要素の左半分。

695
00:32:25,017 --> 00:32:26,350
それでは、どのよう私はこれをやって行くのですか？

696
00:32:26,350 --> 00:32:28,950
まあ、私は一種のつもりだ
精神的にここにリストを分割し、

697
00:32:28,950 --> 00:32:30,700
あなたがする必要はありません
物理的に移動し、私は今

698
00:32:30,700 --> 00:32:33,180
のみに焦点を当てるつもり
ここで要素の左半分。

699
00:32:33,180 --> 00:32:36,770
だから私は、ソートについてどのように行くのですか
今のサイズ4のリストは？

700
00:32:36,770 --> 00:32:38,730
私のアルゴリズムは何ですか？

701
00:32:38,730 --> 00:32:42,580
最初に私は確認していない、nは2未満である、
私は再び他のブロックに進みます。

702
00:32:42,580 --> 00:32:43,900
並べ替え要素の半分を残しました。

703
00:32:43,900 --> 00:32:45,608
>> だから今、もう一度、精神的に、
これはどこにある

704
00:32:45,608 --> 00:32:49,550
あなたはたくさんの計上しなければならない
精神的な歴史、可能ならば。

705
00:32:49,550 --> 00:32:51,940
今、私は左の並べ替えています
左半分の半分。

706
00:32:51,940 --> 00:32:57,000
すべての権利、今私は私の同じマージを呼び出す
ソートアルゴリズムを、2 nよりも小さい？

707
00:32:57,000 --> 00:33:00,590
いいえ、それは2であるので、私はソートする必要が
左半分、右半分。

708
00:33:00,590 --> 00:33:02,042
だからここに私達は行く、左半分を並べ替える。

709
00:33:02,042 --> 00:33:03,750
なぜあなたは単にない
前進1歩を踏み出す。

710
00:33:03,750 --> 00:33:04,415
あなたの名前は？

711
00:33:04,415 --> 00:33:04,860
>> 聴衆：ダレン。

712
00:33:04,860 --> 00:33:05,260
>> スピーカー：ダン。

713
00:33:05,260 --> 00:33:06,040
ダンは踏み出しています。

714
00:33:06,040 --> 00:33:06,748
>> 聴衆：ダレン。

715
00:33:06,748 --> 00:33:09,000
スピーカー：ダレン行わ。

716
00:33:09,000 --> 00:33:10,090
あなたはダレンやダンを言ったの？

717
00:33:10,090 --> 00:33:10,550
>> 聴衆：ダレン。

718
00:33:10,550 --> 00:33:11,216
>> スピーカー：ダレン。

719
00:33:11,216 --> 00:33:14,422
[OK]を、ダレンは強化しています
フォワードと彼は今ソートされます。

720
00:33:14,422 --> 00:33:16,130
そして、これはほとんどあり
無意味なクレーム、右か？

721
00:33:16,130 --> 00:33:18,862
私は実際に達成されていないようだ
何が、のを続行しましょう​​。

722
00:33:18,862 --> 00:33:20,820
今私は、右を並べてみましょう
要素の半分。

723
00:33:20,820 --> 00:33:21,200
あなたの名前は？

724
00:33:21,200 --> 00:33:21,690
>> 聴衆：ルーク。

725
00:33:21,690 --> 00:33:22,273
>> スピーカー：ルーク。

726
00:33:22,273 --> 00:33:23,400
さあ、一歩前進。

727
00:33:23,400 --> 00:33:25,640
完了、私はルークをソートしています。

728
00:33:25,640 --> 00:33:28,570
左半分が現在ソートされており、
右半分は現在、ソートされ

729
00:33:28,570 --> 00:33:30,770
これもまた、ここで重要なステップがあります。

730
00:33:30,770 --> 00:33:32,940
私は次に何をする何が必要ですか？

731
00:33:32,940 --> 00:33:33,941
ソートされた半分をマージします。

732
00:33:33,941 --> 00:33:36,648
今、私たちはただ必要があるとしている
前後にこのように誰もが、

733
00:33:36,648 --> 00:33:38,620
私は一種の必要があるため
いくつかのスクラッチ領域。

734
00:33:38,620 --> 00:33:40,411
それはほとんどこれらのようなものだ
人はテーブルの上にある、

735
00:33:40,411 --> 00:33:42,460
と私はいくつかの部屋を必要とする
上でそれらを周りに移動します。

736
00:33:42,460 --> 00:33:44,170
だから私は、マージするつもりです
見ることによってあなたたち

737
00:33:44,170 --> 00:33:45,960
左半分と右半分で。

738
00:33:45,960 --> 00:33:48,740
そして、明らかに最初に来る人は、
左半分または右半分？

739
00:33:48,740 --> 00:33:52,710
だから、右半分は、それでは、以上のルークを移動してみましょう
ここダレンの元の位置に。

740
00:33:52,710 --> 00:33:57,640
そして今では自分の左半分をマージするには
ダレンは、すぐそこに移動するようになるだろう。

741
00:33:57,640 --> 00:33:59,750
>> だから、ほとんどのように感じている
バブルソート効果、

742
00:33:59,750 --> 00:34:02,482
しかし、私の基本的なアルゴリズム、
今回は非常に異なる。

743
00:34:02,482 --> 00:34:04,815
物事が取得する場所しかし、今だ
少し迷惑なあなたのため

744
00:34:04,815 --> 00:34:06,810
精神的に巻き戻ししなければならない
私はどこにオフにしておいた。

745
00:34:06,810 --> 00:34:09,893
私はソートされた半分を合併しましたが、
これは私が私のアルゴリズムでどこてる意味？

746
00:34:09,893 --> 00:34:12,229

747
00:34:12,229 --> 00:34:13,770
私は右の、右半分を並べ替える必要がありますか？

748
00:34:13,770 --> 00:34:15,910
>> あなたは文字通り、巻き戻した場合
ビデオでは、よ

749
00:34:15,910 --> 00:34:18,339
私たちはこれになっていることがわかり
ルークとダレンのポイント

750
00:34:18,339 --> 00:34:21,370
左をソートすることにより
左半分の半分。

751
00:34:21,370 --> 00:34:23,430
それから、それらをマージ
、半分をソートしている

752
00:34:23,430 --> 00:34:27,941
次のステップは、ソートであることを意味し
左半分の右半分。

753
00:34:27,941 --> 00:34:29,649
すべての権利、そうしてみましょう
より迅速にこれを行う。

754
00:34:29,649 --> 00:34:33,282
すべての権利、6、私は主張するつもりだ
あなたは今、前方に来て、並べ替えられています。

755
00:34:33,282 --> 00:34:33,990
あなたの名前は？

756
00:34:33,990 --> 00:34:34,589
>> 聴衆：アドリアーノ。

757
00:34:34,589 --> 00:34:35,200
>> スピーカー：アドリアーノ。

758
00:34:35,200 --> 00:34:36,010
アドリアーノは現在ソートされます。

759
00:34:36,010 --> 00:34:36,450
そして、あなたの名前は何ですか？

760
00:34:36,450 --> 00:34:37,080
>> 聴衆：アレックス。

761
00:34:37,080 --> 00:34:38,379
>> スピーカー：アレックスは今ソートされます。

762
00:34:38,379 --> 00:34:40,750
左半分、右半分、
最後のステップは何ですか？

763
00:34:40,750 --> 00:34:41,250
マージ。

764
00:34:41,250 --> 00:34:44,310
プリティ些細なので、私は今
6マージしようとして、

765
00:34:44,310 --> 00:34:46,930
バックステップを取る、
8は、ステップを取り戻す。

766
00:34:46,930 --> 00:34:49,530
そして今、これは注意してください
便利持ち帰り、何

767
00:34:49,530 --> 00:34:53,930
今の左半分程度真実である
リストに関係なく、私たちはどのように始まったのかの？

768
00:34:53,930 --> 00:34:55,090
それは、ソートされます。

769
00:34:55,090 --> 00:34:57,750
>> 今ではで並べ替えないです
物事の大きなスキーム、

770
00:34:57,750 --> 00:35:00,250
それは独立してソートされ
残りの半分の。

771
00:35:00,250 --> 00:35:04,100
私が続ければ今何段階私が上だ
物語がどのように始まったのか、巻き戻し？

772
00:35:04,100 --> 00:35:05,680
今、私は右半分をソートする必要があります。

773
00:35:05,680 --> 00:35:07,630
だから今、私たちは道奥にしている
物語の冒頭、

774
00:35:07,630 --> 00:35:08,921
とのより迅速、これをやらせる。

775
00:35:08,921 --> 00:35:11,320
だから私は、ソートするつもりです
リスト全体の右半分。

776
00:35:11,320 --> 00:35:13,060
次のステップは何ですか？

777
00:35:13,060 --> 00:35:15,840
右半分の左半分をソートします。

778
00:35:15,840 --> 00:35:18,715
の左半分をソート
右半分の左半分。

779
00:35:18,715 --> 00:35:19,590
そして、あなたの名前は何ですか？

780
00:35:19,590 --> 00:35:20,230
>> 聴衆：オマール。

781
00:35:20,230 --> 00:35:21,970
>> スピーカー：オマールは、行われ、前進。

782
00:35:21,970 --> 00:35:22,860
左半分がソートされます。

783
00:35:22,860 --> 00:35:23,330
そして、あなたの名前は何ですか？

784
00:35:23,330 --> 00:35:23,820
>> 聴衆：クリス。

785
00:35:23,820 --> 00:35:25,620
>> スピーカー：クリスは、一歩を踏み出す
前進、あなたは今ソートされる。

786
00:35:25,620 --> 00:35:27,010
今重要なステップは何ですか？

787
00:35:27,010 --> 00:35:27,510
マージ。

788
00:35:27,510 --> 00:35:30,509
したがって、1つの場所に合流しようとしている
ここに、あなたが戻って一歩を踏み出すことができれば、

789
00:35:30,509 --> 00:35:32,930
そして3人はしようとしている
マージ、ステップを取り戻す。

790
00:35:32,930 --> 00:35:38,080
だからの左半分
右半分は、ソートされるようになりました。

791
00:35:38,080 --> 00:35:41,747
率直に言って、このアルゴリズムは、私たちのように感じている
以前より道より多くの時間を無駄にしている、

792
00:35:41,747 --> 00:35:44,830
私たちはリアルタイムでこれをしなかったなら、私たちはよ
持ち帰りがあることを行ってものを見る。

793
00:35:44,830 --> 00:35:47,970
今ここに私は右の、午前
右半分の半分、

794
00:35:47,970 --> 00:35:50,170
私が先に行くと左半分を並べてみましょう。

795
00:35:50,170 --> 00:35:51,482
一歩前進、あなたの名前は何ですか？

796
00:35:51,482 --> 00:35:52,190
聴衆：ラムジー。

797
00:35:52,190 --> 00:35:53,210
スピーカー：ラムジーは今ソートされます。

798
00:35:53,210 --> 00:35:53,570
あなたの名前は？

799
00:35:53,570 --> 00:35:54,200
>> 聴衆：マリーナ。

800
00:35:54,200 --> 00:35:57,033
>> スピーカー：マリーナは今のようにソートされる
さて、あなたは一歩を取る場合。

801
00:35:57,033 --> 00:36:00,690
ここで重要なステップは、今私は、マージされている
私の二つのリストから摘み取るつもり、

802
00:36:00,690 --> 00:36:01,720
左と右。

803
00:36:01,720 --> 00:36:05,150
ファイブは、最初に来ることを行っている
そして7は、次の来ることを行っている。

804
00:36:05,150 --> 00:36:06,410
そして再び、これは意図的なもの。

805
00:36:06,410 --> 00:36:08,535
彼らが取っているという事実
前後のステップ

806
00:36:08,535 --> 00:36:12,997
私たちができないことを示すためのものです
同様に容易な場所にこのアルゴリズムを行う

807
00:36:12,997 --> 00:36:15,830
バブルソート、選択ソートなど、
どこでちょうど私達と挿入ソート

808
00:36:15,830 --> 00:36:16,960
人を入れ替える続けた。

809
00:36:16,960 --> 00:36:19,940
私は文字通りの並べ替えを必要とする
メモ用紙のもので

810
00:36:19,940 --> 00:36:21,827
これらの人々を置くために
私はマージを行いながら、

811
00:36:21,827 --> 00:36:23,410
そして私は場所に戻ってそれらを置くことができます。

812
00:36:23,410 --> 00:36:27,260
私が使用しているので、それがキーだ
新しいリソース、スペースだけではなく、時間。

813
00:36:27,260 --> 00:36:28,270
>> [OK]を、これは素晴らしいです。

814
00:36:28,270 --> 00:36:32,050
左半分、右半分は、ソートされ
ソートされた、今ではキーのマージステップ。

815
00:36:32,050 --> 00:36:33,450
どのように私はこれをマージするつもり？

816
00:36:33,450 --> 00:36:35,470
だから、あなたが私に従うだろうかどう
左手と右手、

817
00:36:35,470 --> 00:36:38,930
私は私の左手を指すつもりだ
左半分では、私の右手

818
00:36:38,930 --> 00:36:42,680
右半分では、今私が持っている
にマージする段階的に決定する。

819
00:36:42,680 --> 00:36:44,650
誰が、明らかに最初に来る？

820
00:36:44,650 --> 00:36:45,150
ナンバーワン。

821
00:36:45,150 --> 00:36:47,327
だから、こっちに来て、
ここに私たちのスクラッチパッドです。

822
00:36:47,327 --> 00:36:49,910
だから今ナンバーワン、と予告
私は自分の右手で何をやる、

823
00:36:49,910 --> 00:36:54,152
私は私の右手1を移動するつもりです
ポイント番号3にステップオーバー、

824
00:36:54,152 --> 00:36:55,860
そして今、私は確認する必要があり
同じ決定。

825
00:36:55,860 --> 00:36:58,387
そして、実際に右に立つ
ここでルークの前もしできれば、

826
00:36:58,387 --> 00:36:59,720
これは私たちのスクラッチパッドであるためです。

827
00:36:59,720 --> 00:37:00,610
だから、誰が次に来る？

828
00:37:00,610 --> 00:37:05,000
私たちは、数2でルークを持っている
または番号3とクリス。

829
00:37:05,000 --> 00:37:07,460
もちろんルーク、数
2、あなたがここに来るようにします。

830
00:37:07,460 --> 00:37:11,270
>> しかし、私の左手は今まで起こっている
ダレンを指すようにインクリメントされ、

831
00:37:11,270 --> 00:37:15,160
とここで奪うキーです
マージ、私はこれをやり続けるつもりだ、

832
00:37:15,160 --> 00:37:17,340
明らかに、あなたの種類の場合
の論理に従ってください。

833
00:37:17,340 --> 00:37:19,670
しかし、私の手は決してありません
後方に行くつもり、

834
00:37:19,670 --> 00:37:23,861
その私は今までに移動してることを意味
私のマージ処理が残され、

835
00:37:23,861 --> 00:37:26,360
それがカギになるだろう
一瞬で私たちの分析。

836
00:37:26,360 --> 00:37:27,859
>> だから今のが急速にこれを終了させ。

837
00:37:27,859 --> 00:37:31,650
だから3人は、次に来る
その後4人が次に来る、

838
00:37:31,650 --> 00:37:38,750
そして今5は、6その後、次に来る
そして最後に、その後7、および8。

839
00:37:38,750 --> 00:37:42,960
最も遅いアルゴリズムのように感じている
まだではなく、実際に私たちの場合

840
00:37:42,960 --> 00:37:45,510
同じ種類でそれを実行する
クロック速度の、に非常に

841
00:37:45,510 --> 00:37:48,106
同じで、話す
以前のように時計を刻む。

842
00:37:48,106 --> 00:37:48,605
なぜ？

843
00:37:48,605 --> 00:37:51,100
さて、見てみましょう
最終結果を見てください。

844
00:37:51,100 --> 00:37:56,990
>> とさせて頂いて、のはこちらに戻りましょう
視覚的にデモを引き上げ

845
00:37:56,990 --> 00:37:59,030
私達はちょうど何をしたかの。

846
00:37:59,030 --> 00:38:06,110
この上で、ここにズーム
こちらのページは、Firefoxを伝える

847
00:38:06,110 --> 00:38:08,200
私たちはキューしたいこと
このボックスに、最大みましょう

848
00:38:08,200 --> 00:38:11,260
これで、バブルソートを言う
私たちは、現在十分に精通している

849
00:38:11,260 --> 00:38:14,130
別のある選択ソート、
かなり簡単な1、

850
00:38:14,130 --> 00:38:18,250
これ、今、今日のマージソート、
私たちのクライマックス結末になります。

851
00:38:18,250 --> 00:38:21,530
それはそんなに時間がかかった理由
ここに人間と私と一緒に口頭で、

852
00:38:21,530 --> 00:38:23,480
明らかに、私はすべての工程を説明するよ。

853
00:38:23,480 --> 00:38:26,920
しかし、あなたは、単に多く、これを実行した場合
私たちは、バブルソートや選択を行ったように

854
00:38:26,920 --> 00:38:30,890
並べ替えだけでなく、視覚的に、時計
どれだけ、より効率的に

855
00:38:30,890 --> 00:38:33,330
このレバレッジ
分裂と征服

856
00:38:33,330 --> 00:38:39,150
のデータセットに適用することができる場合
なくてもサイズが8、それでもずっと、

857
00:38:39,150 --> 00:38:39,970
はるかに大きい。

858
00:38:39,970 --> 00:38:44,585
私は、あなたがすることによって、ソート側マージ与える
これらの他のアルゴリズムを有する側。

859
00:38:44,585 --> 00:38:56,364

860
00:38:56,364 --> 00:38:58,530
これは痛みを伴う取得する予定です
迅速、エンディング

861
00:38:58,530 --> 00:39:00,890
特にクライマックスではありません
彼らはただソートすることになります。

862
00:39:00,890 --> 00:39:05,280
しかし、キーが奪うということです
より高速なマージソートどのくらい見て

863
00:39:05,280 --> 00:39:08,110
あなたは私は考えていない限り、だった
だけの種類のあなたといじり。

864
00:39:08,110 --> 00:39:13,100
私たちは、この最後に1回行うと、
それではこれをリロードしてみましょう、の戻りましょう

865
00:39:13,100 --> 00:39:14,960
そして、バブルソートを選択
ちょうど蹴りのために、

866
00:39:14,960 --> 00:39:17,330
の挿入]を選択してみましょう
ソート、ちょうど良い測定のために。

867
00:39:17,330 --> 00:39:20,020
そして再び、この時間は、みましょう
マージソートを選択してみましょう

868
00:39:20,020 --> 00:39:21,595
実際に並んでこれらの副作用を実行します。

869
00:39:21,595 --> 00:39:24,140

870
00:39:24,140 --> 00:39:26,930
>> そしてそれは、実際には、まぐれではありません。

871
00:39:26,930 --> 00:39:31,140
私は効果的にやったのは、私だである
もう一度、半分に私の入力を分け、

872
00:39:31,140 --> 00:39:32,240
そして再び、そして再び。

873
00:39:32,240 --> 00:39:35,590
そして、あなたができるだけなので何度もあります
半分に入力を分割し、左

874
00:39:35,590 --> 00:39:36,240
と右。

875
00:39:36,240 --> 00:39:39,425
私たちが見ておくの式は何ですか
つまり、半分に分割を記述する

876
00:39:39,425 --> 00:39:41,050
再び、そして再び、そして再び、そして再び？

877
00:39:41,050 --> 00:39:41,890
>> 聴衆：nはログインしてください。

878
00:39:41,890 --> 00:39:42,760
>> スピーカー：ログのn。

879
00:39:42,760 --> 00:39:46,300
しかし、その後、一つの他の重要なステップがあります、
このアルゴリズムは、n個のステップをログに記録されていません。

880
00:39:46,300 --> 00:39:48,992
それがあった場合はログのみのnステップ、
私たちは同じ問題になるだろう

881
00:39:48,992 --> 00:39:51,200
私たちがすることはできませんここで前と
必ずすべてのソートされた。

882
00:39:51,200 --> 00:39:54,480
あなたは最小限にn個の要素を見ている
n個の要素がソートされていることを確認することが、

883
00:39:54,480 --> 00:39:55,950
それ以外の場合は、信仰の飛躍だ。

884
00:39:55,950 --> 00:39:59,810
>> だから、最小限にログインするn個のステップですが、
このキー併合ステップについてどのような

885
00:39:59,810 --> 00:40:04,370
私がマージされ、私の左半分と右
ステージ全体に歩い半分？

886
00:40:04,370 --> 00:40:06,980
マージすることは、どのように多くの手順とは？

887
00:40:06,980 --> 00:40:10,150
それはnのだが、私はちょうどしませんでした
最終的な時間をマージ。

888
00:40:10,150 --> 00:40:15,089
これらのネストされた呼び出しのそれぞれには、それぞれに
これらのネストされたマージ、私はまだソート。

889
00:40:15,089 --> 00:40:18,380
私は、これら2つのこれらの2人を、マージ
みんな、これら2つの人など。

890
00:40:18,380 --> 00:40:19,955
>> だから私は再び、そして再びマージしなかった。

891
00:40:19,955 --> 00:40:20,580
何回？

892
00:40:20,580 --> 00:40:23,510
だから、毎回、私は分割
リストは半分に、私はマージを行いました。

893
00:40:23,510 --> 00:40:25,460
マージを行うには、半分にリストを分割します。

894
00:40:25,460 --> 00:40:28,570
だから、リストを分割する場合は、
ログをn回行うことができ、

895
00:40:28,570 --> 00:40:33,880
とマージは、最終的にn個をとり
今アッパーかもしれないどのような手順、

896
00:40:33,880 --> 00:40:37,000
ランニングの下限
このアルゴリズムの時間？

897
00:40:37,000 --> 00:40:37,980
nはn個を記録します。

898
00:40:37,980 --> 00:40:40,560
>> そして実際、それは何ですか
私たちはここで達成した。

899
00:40:40,560 --> 00:40:44,650
ですから、視覚的にしたときに表示感触
これらの3つのものが並んで実行

900
00:40:44,650 --> 00:40:47,930
N Nに対して二乗さ
n個のログのn乗に対して。

901
00:40:47,930 --> 00:40:51,010
どの基本的に私たちが表示されます、
今日が、将来的にだけでなく、

902
00:40:51,010 --> 00:40:52,760
はるかに、はるかに高速です。

903
00:40:52,760 --> 00:40:56,010
これらの人のための拍手、
私はストレスボールとそれらを報いるであろう。

904
00:40:56,010 --> 00:41:00,260
今日はここに休会しましょう​​、と
私たちは月曜日にお会いします。

905
00:41:00,260 --> 00:41:02,255