1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[音楽再生]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVIDマラン：これはCS50です。

5
00:00:14,010 --> 00:00:18,090
そして、これは開始との両方である
literally--ほぼ終わりのようend--

6
00:00:18,090 --> 00:00:18,825
週6の。

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> 私は共有したいと思った
楽しい事実を少し。

9
00:00:22,640 --> 00:00:25,370
私はからリブログ引き上げられてきた
過去の学期のデータセット。

10
00:00:25,370 --> 00:00:29,710
あなたは、私たちはすべての上をお願いすることを思い出すかもしれ
あなたがオンラインで見てきた場合には、P·セット·フォーム

11
00:00:29,710 --> 00:00:31,580
またはあなたが個人的に出席してしまった場合。

12
00:00:31,580 --> 00:00:33,020
そして、ここでのデータです。

13
00:00:33,020 --> 00:00:34,710
だから、今日は非常に予測可能だった。

14
00:00:34,710 --> 00:00:37,126
しかし、我々は少しを過ごすしたかった
時間のあなたと、それにもかかわらず。

15
00:00:37,126 --> 00:00:40,599
誰もがなぜこれを推測したいと思います
グラフは、アップダウン、アップダウン、そうジャギーです

16
00:00:40,599 --> 00:00:41,265
そう一貫して？

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
どのようなピークの各々を行う
と谷が表す？

19
00:00:45,130 --> 00:00:46,005
>> 読者：[聞こえない]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVIDマラン：確かに。

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
そして、もっと面白いこと、神が禁じて、
我々は金曜日に1講座を開催

24
00:00:55,480 --> 00:00:58,960
学期の初めに、
それは我々が起こる見るものだ。

25
00:00:58,960 --> 00:01:03,430
だから、今日、私たちは少しは参加
データ構造の詳細。

26
00:01:03,430 --> 00:01:06,660
そしてあなたに固体の多くを与えるために
5での問題のためのメンタルモデル、

27
00:01:06,660 --> 00:01:07,450
これ、今出ている。

28
00:01:07,450 --> 00:01:10,817
スペルミス、特徴、我々はよ
手あなたのテキストフ​​ァイル10万

29
00:01:10,817 --> 00:01:12,650
プラス英単語、および
あなたが持っているつもり

30
00:01:12,650 --> 00:01:17,770
巧みにそれらをロードする方法を見つけ出すために
メモリに、いくつかのデータを使用して、RAMに

31
00:01:17,770 --> 00:01:19,330
お好みの構造。

32
00:01:19,330 --> 00:01:22,470
>> 今、そのようなデータ構造は、可能性
ことが、おそらくすべきではない、

33
00:01:22,470 --> 00:01:25,630
かなり単純化したリンクリスト、
その私たちが最後の時間を導入しました。

34
00:01:25,630 --> 00:01:29,220
とリンクされたリストには、少なくとも持っていた
配列上の1つの利点。

35
00:01:29,220 --> 00:01:32,096
の一つの利点は何ですか
間違いなくリンクリスト？

36
00:01:32,096 --> 00:01:32,950
>> 聴衆：挿入。

37
00:01:32,950 --> 00:01:33,908
>> DAVIDマラン：挿入。

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
あなたはそのことで何を意味するのですか？

40
00:01:35,196 --> 00:01:37,872
>> 読者：どこに沿って
リスト[聞こえない]。

41
00:01:37,872 --> 00:01:38,770
>> DAVIDマラン：良い。

42
00:01:38,770 --> 00:01:42,090
だから、どこに要素を挿入することができます
あなたは、リストの途中で欲しい

43
00:01:42,090 --> 00:01:45,490
何をシャッフルすることなく、
その私たちのソートで、結論

44
00:01:45,490 --> 00:01:47,630
議論ではない
必ずしも良いこと、

45
00:01:47,630 --> 00:01:51,200
実際に移動する時間がかかるため
これらの人間の全てを左右。

46
00:01:51,200 --> 00:01:55,540
そしてそう、リンクされたリストで、次のことができます
ただ、malloc関数で新しいノードを割り当てる、

47
00:01:55,540 --> 00:01:58,385
その後のカップルを更新
max-- 2、3の操作をpointers--

48
00:01:58,385 --> 00:02:01,480
私たちは誰かをスロットにできるしている
リストに任意の場所で。

49
00:02:01,480 --> 00:02:03,550
>> 他に何が有利であった
リンクリストはどうですか？

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
うん？

52
00:02:05,659 --> 00:02:06,534
>> 読者：[聞こえない]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVIDマラン：パーフェクト。

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
パーフェクト。

57
00:02:11,090 --> 00:02:12,070
それは本当にダイナミックだ。

58
00:02:12,070 --> 00:02:15,100
そして、あなたがコミットしていないことを、
事前に、いくつかの固定サイズへ

59
00:02:15,100 --> 00:02:18,750
メモリのチャンク、あなたがしているのと同じよう
アレイの逆さまとする

60
00:02:18,750 --> 00:02:22,455
あなたが唯一の上のノードを割り当てることができるということです
それによってのみできるだけ多くのスペースを使用してオンデマンド

61
00:02:22,455 --> 00:02:23,330
あなたが実際に必要として。

62
00:02:23,330 --> 00:02:26,830
配列とは対照的に、あなたがかもしれない
誤って少なすぎるを割り当てる。

63
00:02:26,830 --> 00:02:28,871
そしてそれはちょうど起こっている
首の痛みであると

64
00:02:28,871 --> 00:02:32,440
新しい大きな配列を再割り当てするには、copy
古い配列を解放し、すべてのものの上、

65
00:02:32,440 --> 00:02:33,990
その後、あなたのビジネスを動き回る。

66
00:02:33,990 --> 00:02:37,479
良くも悪くも、あなたは道を割り当てるかもしれません
あなたが実際に必要とするよりも多くのメモリ、

67
00:02:37,479 --> 00:02:40,520
ので、あなたは非常に持っているつもり
いわば、配列を過疎。

68
00:02:40,520 --> 00:02:44,350
>> だから、リンクリストはあなたにこれらを提供します
ダイナミズムと柔軟性の利点

69
00:02:44,350 --> 00:02:46,080
挿入および欠失を持つ。

70
00:02:46,080 --> 00:02:48,000
しかし確実に支払われる価格が存在しなければならない。

71
00:02:48,000 --> 00:02:50,000
テーマ実際に、ある
クイズゼロで探索

72
00:02:50,000 --> 00:02:52,430
トレードオフのカップルがいた
我々はこれまで見てきました。

73
00:02:52,430 --> 00:02:56,161
だから、支払った価格または何
リンクリストの欠点？

74
00:02:56,161 --> 00:02:56,660
うん。

75
00:02:56,660 --> 00:02:57,560
>> 聴衆：いいえランダムアクセス。

76
00:02:57,560 --> 00:02:58,809
>> DAVIDマラン：いいえランダムアクセス。

77
00:02:58,809 --> 00:02:59,540
しかし、誰が気に？

78
00:02:59,540 --> 00:03:01,546
ランダムアクセスが説得力のある音は鳴りません。

79
00:03:01,546 --> 00:03:02,421
>> 読者：[聞こえない]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVIDマラン：その通り。

82
00:03:05,740 --> 00:03:07,580
あなたが持っているしたい場合は
特定のalgorithm--

83
00:03:07,580 --> 00:03:10,170
と私は実際に提案してみましょう
特にバイナリサーチ、どの

84
00:03:10,170 --> 00:03:12,600
私たちはかなりbit--を使用しました1です
もしランダムアクセスを持っていない場合、

85
00:03:12,600 --> 00:03:15,516
あなたはその単純な算術演算を行うことはできません
真ん中の要素と同様見つける

86
00:03:15,516 --> 00:03:16,530
そして右のそれにジャンプする。

87
00:03:16,530 --> 00:03:20,239
代わりに、最初に起動する必要があります
要素と直線的に左から検索

88
00:03:20,239 --> 00:03:22,780
右にあなたが検索したい場合は、
中間または任意の他の要素。

89
00:03:22,780 --> 00:03:24,410
>> 聴衆：それはおそらくより多くのメモリを取る。

90
00:03:24,410 --> 00:03:25,040
>> DAVIDマランは：より多くのメモリをとります。

91
00:03:25,040 --> 00:03:27,464
どこにその追加的である
メモリ内から来るコスト？

92
00:03:27,464 --> 00:03:28,339
>> 読者：[聞こえない]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVIDマラン：その通り。

95
00:03:33,440 --> 00:03:35,679
ここで、このケースでは、持っていた
整数のリンクリスト、

96
00:03:35,679 --> 00:03:37,470
そしてまだ我々は倍増している
メモリー容量

97
00:03:37,470 --> 00:03:39,680
我々はまた、これらのポインタを格納することによって必要とする。

98
00:03:39,680 --> 00:03:42,090
今ではあまり大したことのよう
あなたの構造体は大きくなる

99
00:03:42,090 --> 00:03:45,320
そしてあなたがいない番号を記憶しているが、
多分学生や他のいくつかのオブジェクト。

100
00:03:45,320 --> 00:03:46,880
しかし、ポイントは確かに残っている。

101
00:03:46,880 --> 00:03:49,421
だから操作の数
リンクされたリストに呼ばれていました

102
00:03:49,421 --> 00:03:50,570
N--リニアのビッグOのだった。

103
00:03:50,570 --> 00:03:54,730
挿入や検索のようなもの
または削除場合の要素

104
00:03:54,730 --> 00:03:57,720
の一番最後にあることを起こった
それがソートされていないかどうかをリスト。

105
00:03:57,720 --> 00:04:01,167
>> 時には、あなたが幸運を得ると中かもしれません
これらの操作のため、下界

106
00:04:01,167 --> 00:04:04,250
あなたがならも、一定の時間かもしれない
常に最初の要素を見て、

107
00:04:04,250 --> 00:04:05,070
例えば。

108
00:04:05,070 --> 00:04:09,360
しかし最終的に、私たちは約束した
聖杯を達成するために

109
00:04:09,360 --> 00:04:12,630
データ構造、または
それらのいくつかの近似、

110
00:04:12,630 --> 00:04:14,290
一定の時間を経て。

111
00:04:14,290 --> 00:04:17,579
我々は、要素を見つけるか、要素を追加することができます
またはリストから要素を削除する？

112
00:04:17,579 --> 00:04:19,059
我々は非常にすぐに参照しなければならない。

113
00:04:19,059 --> 00:04:21,100
そしてそれは、そのいずれかを判明
私たちがしているメカニズムの

114
00:04:21,100 --> 00:04:23,464
今日の使用を開始する予定、
Pの年間使用は、5を設定

115
00:04:23,464 --> 00:04:24,630
実際にはかなり精通している。

116
00:04:24,630 --> 00:04:27,430
例えば、これは束である場合
各試験の書籍、の

117
00:04:27,430 --> 00:04:29,660
学生の最初のを持ってい
その上で姓と名、

118
00:04:29,660 --> 00:04:31,820
と私はからそれらを拾う
試験の終わりに、

119
00:04:31,820 --> 00:04:33,746
それらはすべてき​​れいです
ランダムな順序で多く、

120
00:04:33,746 --> 00:04:36,370
そして我々は、ソートについて行くたい
これらの試験はその結果、一度等級

121
00:04:36,370 --> 00:04:38,661
それだけで非常に簡単だし、
より速く、それらをバック手へ

122
00:04:38,661 --> 00:04:40,030
学生にアルファベット順に。

123
00:04:40,030 --> 00:04:42,770
あなたの本能は何だろう
このような試験の杭のため？

124
00:04:42,770 --> 00:04:45,019
>> さて、あなたは私に似ている場合は、
これはMであることを表示されることがあり、

125
00:04:45,019 --> 00:04:48,505
私は、ソートのにこれを置くつもりだ
これが私のテーブルや私の床である場合

126
00:04:48,505 --> 00:04:50,650
私は物事を広めています
ゆうパックや私の配列really--

127
00:04:50,650 --> 00:04:52,210
私はそこにおけるMSのすべてを置くことがあります。

128
00:04:52,210 --> 00:04:52,710
ああ。

129
00:04:52,710 --> 00:04:55,020
ここで、Aは、だから私はかもしれないです
こっちAsを置く。

130
00:04:55,020 --> 00:04:55,520
ああ。

131
00:04:55,520 --> 00:04:57,980
ここで私は行くよもうA.です
こっちのことを置くために。

132
00:04:57,980 --> 00:05:02,490
ここZ.は、別のMであるので、ここだ
私はこのような山を作り始めるかもしれません。

133
00:05:02,490 --> 00:05:06,620
その後多分私は以降でいいと思う
ソートの非常にせこい-LYソート

134
00:05:06,620 --> 00:05:07,710
個々の杭。

135
00:05:07,710 --> 00:05:11,300
しかし、ポイントは、私はなりです
私は左利きだ入力で

136
00:05:11,300 --> 00:05:14,016
と私はいくつかの計算されてしまいます
その入力に基づいて決定。

137
00:05:14,016 --> 00:05:15,640
それがで始まる場合、あそこにそれを置く。

138
00:05:15,640 --> 00:05:18,980
それは、Zで始まる場合、それを上に置く
そこに、との間のすべて。

139
00:05:18,980 --> 00:05:22,730
>> だから、これはだ技法である
一般hashing-- H-A-S-H--として知られている

140
00:05:22,730 --> 00:05:26,550
これは一般のように取って意味
計算するためにその入力を入力して使用して

141
00:05:26,550 --> 00:05:30,940
値は、一般的に数、およびその
番号は、ストレージへのインデックスです

142
00:05:30,940 --> 00:05:32,260
配列のような容器。

143
00:05:32,260 --> 00:05:35,490
換言すれば、私が持っているかもしれません
ハッシュ関数は、私は私の頭の中でそうであるように、

144
00:05:35,490 --> 00:05:37,940
その私が誰かの見たら
Aで始まる名前、

145
00:05:37,940 --> 00:05:40,190
私はそれをマップするつもりだ
私の頭の中でゼロに。

146
00:05:40,190 --> 00:05:44,160
私はZで誰かを参照している場合と、私は今
私の頭の中で25にそれをマップするために行く

147
00:05:44,160 --> 00:05:46,220
その後にそれを置く
最後のほとんどの杭。

148
00:05:46,220 --> 00:05:50,990
>> さて、あなたがいない私の脳を考える場合には
しかし、Cプログラム、どのような番号ができた

149
00:05:50,990 --> 00:05:53,170
あなたは、同じ結果を達成するために頼る？

150
00:05:53,170 --> 00:05:55,594
言い換えれば、あなたの場合
ASCII文字Aを持っていた

151
00:05:55,594 --> 00:05:57,510
どのように決定するのですか
何バケツにそれを置くか？

152
00:05:57,510 --> 00:05:59,801
あなたは、おそらくしたくない
これ、バケット65に入れて

153
00:05:59,801 --> 00:06:01,840
あそこようなものだ
正当な理由なく。

154
00:06:01,840 --> 00:06:04,320
あなたはAを置く場所を選択してください
そのASCII値の面で？

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
どこのASCIIにしたいん
賢くバケツを思い付くする値

157
00:06:08,920 --> 00:06:09,480
でそれを置くか？

158
00:06:09,480 --> 00:06:10,206
>> 読者：マイナスA.

159
00:06:10,206 --> 00:06:10,956
>> DAVIDマラン：うん。

160
00:06:10,956 --> 00:06:13,190
だから、マイナスAまたはマイナス
特に65それはだ場合は、

161
00:06:13,190 --> 00:06:18,240
資本A.または98の場合
それは小文字のaをだ。

162
00:06:18,240 --> 00:06:21,300
そしてその結果は、非常に、私たちができるようになる
簡単かつ非常に算術的に、

163
00:06:21,300 --> 00:06:23,260
そのようなバケツに何かを置く。

164
00:06:23,260 --> 00:06:26,010
だから、私たちが実際に行う判明
このだけでなくても、クイズ付き。

165
00:06:26,010 --> 00:06:29,051
>> だから、あなたはあなたの丸思い出すかもしれません
表紙に仲間の名前を教える。

166
00:06:29,051 --> 00:06:32,270
とTFの名が組織された
アルファベット順にこれらの列に、

167
00:06:32,270 --> 00:06:34,400
よく、それを信じるかどうか、
とき私たちのすべての80プラス

168
00:06:34,400 --> 00:06:37,800
、グレードに他の夜集まりました
私たちのグレーディングプロセスの最後のステップ

169
00:06:37,800 --> 00:06:41,830
ビッグにクイズをハッシュすることです
[聞こえない]のフロアのスペース

170
00:06:41,830 --> 00:06:45,110
そしてみんなのクイズをレイアウトする
彼らのTFの正確順

171
00:06:45,110 --> 00:06:47,700
カバー上の名前、理由
それは私たちのためにはるかに簡単です

172
00:06:47,700 --> 00:06:51,290
その用いた線形を検索する
検索や賢さのいくつかの種類

173
00:06:51,290 --> 00:06:54,050
彼または検索するためのTF
彼女の生徒のクイズ。

174
00:06:54,050 --> 00:06:56,060
>> ハッシングのため、このアイデア
であるあなたが見るだろうと

175
00:06:56,060 --> 00:07:00,520
実際にはかなり非常に強力である
ありふれた、非常に直感的な、

176
00:07:00,520 --> 00:07:03,000
ずっとおそらく分裂などが挙げられる
統治は、週にゼロだった。

177
00:07:03,000 --> 00:07:05,250
私早送りハッカソンへ
数年前。

178
00:07:05,250 --> 00:07:08,040
これはZamylaとのカップルだった
他のスタッフの挨拶の学生

179
00:07:08,040 --> 00:07:09,030
彼らが入って来たように。

180
00:07:09,030 --> 00:07:12,680
そして、我々は折りたたみの全体の束を持っていた
名前タグとそこにテーブル。

181
00:07:12,680 --> 00:07:15,380
そして、我々は組織化さ名札を持っていた
同様のようなあそこで

182
00:07:15,380 --> 00:07:16,690
そしてあそこZsは。

183
00:07:16,690 --> 00:07:20,350
そしてそうTFの1は非常に巧妙に
命令としてこれを書いた

184
00:07:20,350 --> 00:07:21,030
一日のために。

185
00:07:21,030 --> 00:07:24,480
学期の週で12本
すべて完璧な感覚と皆を作った

186
00:07:24,480 --> 00:07:25,310
何をすべきかを知っていた。

187
00:07:25,310 --> 00:07:27,900
しかし、いつでもあなたがした
同じようにキューイングされ、

188
00:07:27,900 --> 00:07:30,272
あなたが実装しようとしている
ハッシュの同じ概念。

189
00:07:30,272 --> 00:07:31,730
それでは、それは少し形式化してみましょう。

190
00:07:31,730 --> 00:07:32,890
ここでは配列です。

191
00:07:32,890 --> 00:07:36,820
それは、少しであることが描かれています
広いだけで視覚的に、描写するために、

192
00:07:36,820 --> 00:07:38,920
私たちは、文字列を置く可能性があること
このようなもので。

193
00:07:38,920 --> 00:07:41,970
そして、この配列は、
明らかにサイズが26の合計の。

194
00:07:41,970 --> 00:07:43,935
そして事が呼び出されます
テーブルを任意。

195
00:07:43,935 --> 00:07:48,930
しかし、これは単に芸術家の演出です
ハッシュテーブルが何であるかの。

196
00:07:48,930 --> 00:07:52,799
>> だから、ハッシュテーブルは今まで起こっている
より高いレベルのデータ構造である。

197
00:07:52,799 --> 00:07:54,840
一日の終わりに
私たちはあなたことを確認しようとしている

198
00:07:54,840 --> 00:07:58,700
ハッシュテーブルを実装することができる
多くのチェックイン·ラインのようなものです

199
00:07:58,700 --> 00:08:02,059
このような多くのハッカソンで
表には、試験の本をソートするために使用。

200
00:08:02,059 --> 00:08:03,850
しかし、ハッシュテーブルである
この高レベルのソート

201
00:08:03,850 --> 00:08:08,250
配列を使用することができますコンセプト
それを実装するためにボンネットの下に、

202
00:08:08,250 --> 00:08:11,890
またはそれは長のリストを使用するか、またはさえなかった
おそらくいくつかの他のデータ構造。

203
00:08:11,890 --> 00:08:15,590
そして今、それはtheme--取っている
これらの基本的な成分の一部

204
00:08:15,590 --> 00:08:18,310
アレイおよびこの建物のように
長リストのようになりましブロック

205
00:08:18,310 --> 00:08:21,740
そして私たちが構築することができます他に何見て
食材のようなものの上に

206
00:08:21,740 --> 00:08:26,550
レシピに、より多くを作る
興味深く、有用な最終結果。

207
00:08:26,550 --> 00:08:28,680
>> ハッシュテーブルを持つので、
我々はそれを実装する場合があります

208
00:08:28,680 --> 00:08:32,540
メモリ内に絵画的にこのような、しかし
それはどのように実際にアップするコード化されたことがあります？

209
00:08:32,540 --> 00:08:33,789
まあ、単にこれです。

210
00:08:33,789 --> 00:08:38,270
すべて大文字で容量が、ちょうどある場合
いくつかは、例えば26 constant--

211
00:08:38,270 --> 00:08:42,030
alphabet--の26文字のために
私は私の変数テーブルを呼ぶかもしれない、

212
00:08:42,030 --> 00:08:45,630
と私はするつもりだと主張しているかもしれません
char型星そこに、または文字列を置く。

213
00:08:45,630 --> 00:08:49,880
あなたのであれば、それはこのように単純だ
ハッシュテーブルを実装したい。

214
00:08:49,880 --> 00:08:51,490
そして、まだ、これは実際には単なる配列です。

215
00:08:51,490 --> 00:08:53,198
しかし、再び、ハッシュ
テーブルには、今私たちはよです

216
00:08:53,198 --> 00:08:57,470
ただの抽象データ型を呼び出す
上に概念的なレイヤリングのようなもの

217
00:08:57,470 --> 00:09:00,780
もっと世俗的な何かの
今のアレイが好きです。

218
00:09:00,780 --> 00:09:02,960
>> さて、どのように我々は行くのですか
問題を解決するでしょうか？

219
00:09:02,960 --> 00:09:06,980
さて、以前の私は贅沢を持っていた
ここでは十分な表スペースを持っていることの

220
00:09:06,980 --> 00:09:09,460
私は置くことができるように、
クイズはどこでも私が望んでいた。

221
00:09:09,460 --> 00:09:10,620
ようにすると、ここに行くかもしれない。

222
00:09:10,620 --> 00:09:12,100
ZSはここに行くかもしれない。

223
00:09:12,100 --> 00:09:13,230
Msはここに行くかもしれない。

224
00:09:13,230 --> 00:09:14,740
そして私は、いくつかの余分なスペースを持っていた。

225
00:09:14,740 --> 00:09:18,740
しかし、これはチート右のビットです
今、このテーブルのため、実際に私の場合

226
00:09:18,740 --> 00:09:22,720
配列のようなものと考え、ちょうどある
いくつかの固定サイズになるだろう。

227
00:09:22,720 --> 00:09:25,380
>> だから、技術的には、私が引っ張っている場合
別の生徒のクイズアップ

228
00:09:25,380 --> 00:09:28,490
そしてこの人の、ああ、参照してください。
名前は、あまりにもAで始まる

229
00:09:28,490 --> 00:09:30,980
私は種類のそれをそこに置きたい。

230
00:09:30,980 --> 00:09:34,740
しかし、すぐに、私はそこにそれを置くように、もし
この表には、実際に配列を表し、

231
00:09:34,740 --> 00:09:37,840
私はオーバーライドまたはつかうことするつもりだ
誰でもこの生徒のクイズです。

232
00:09:37,840 --> 00:09:38,340
右？

233
00:09:38,340 --> 00:09:41,972
これが配列の場合、一つだけ缶
これらの細胞または要素のそれぞれに行く。

234
00:09:41,972 --> 00:09:43,680
そして、私は一種の持っている
ピックアップして選択します。

235
00:09:43,680 --> 00:09:45,735
>> さて、以前の私のようなもの
このまたは私を騙していた

236
00:09:45,735 --> 00:09:47,526
だけの種類の積層
互いに上記の彼ら。

237
00:09:47,526 --> 00:09:49,170
しかし、それはコードの中で飛ぶことはないだろう。

238
00:09:49,170 --> 00:09:52,260
だから私はどこに置くことができる
名前は第二学生

239
00:09:52,260 --> 00:09:54,964
Aは私が持っていたすべてはこれである場合である
利用可能な表スペース？

240
00:09:54,964 --> 00:09:57,880
そして、私は3つのスロットと、それを使用しました
わずか数他がありますように見えます。

241
00:09:57,880 --> 00:09:58,959
あなたは何ができますか？

242
00:09:58,959 --> 00:09:59,834
読者：[聞こえない]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVIDマラン：うん。

245
00:10:01,315 --> 00:10:02,370
多分ちょうどそれをシンプルに保つみましょう。

246
00:10:02,370 --> 00:10:02,660
右？

247
00:10:02,660 --> 00:10:04,243
私はそれを置きたい場所、それは適合しません。

248
00:10:04,243 --> 00:10:07,450
だから私はそれを置くつもりだ
技術的にはここで、Bは行くだろう。

249
00:10:07,450 --> 00:10:09,932
さて、もちろん、私が始めている
コー​​ナーに自分自身をペイントする。

250
00:10:09,932 --> 00:10:11,890
私は学生に取得する場合
名前が実際にBであり、

251
00:10:11,890 --> 00:10:14,840
現在、Bは少し移動されようとしている
フォワードとしてはうん、起こるかもしれない、

252
00:10:14,840 --> 00:10:17,530
これがBであれば、今ではここに行かなければならない。

253
00:10:17,530 --> 00:10:20,180
>> ので、この非常に迅速に
問題となる可能性があり、

254
00:10:20,180 --> 00:10:23,850
それは実際にテクニックだ
プロービング線形と呼ばれ、

255
00:10:23,850 --> 00:10:26,650
あなたは自分を検討することにより
アレイは、行に沿うようである。

256
00:10:26,650 --> 00:10:29,680
そして、あなたは単にプローブの種類や
利用可能な各要素を検査

257
00:10:29,680 --> 00:10:31,360
利用可能なスポットを探している。

258
00:10:31,360 --> 00:10:34,010
とすぐあなたが見つけるように
1、あなたはそこにドロップします。

259
00:10:34,010 --> 00:10:38,390
>> さて、価格は今支払われている
このソリューションのために何ですか？

260
00:10:38,390 --> 00:10:41,300
我々は、固定サイズの配列を持っている、
と私は名前を挿入したとき

261
00:10:41,300 --> 00:10:44,059
その中に、少なくとも最初は、何ですか
挿入の実行時間

262
00:10:44,059 --> 00:10:46,350
学生を「置くため
右のバケットでクイズ？

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
何のビッグOの？

265
00:10:50,002 --> 00:10:51,147
>> 聴衆：N。

266
00:10:51,147 --> 00:10:52,480
DAVIDマラン：私は、nのビッグOのを聞いた。

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
真実ではない。

269
00:10:54,300 --> 00:10:56,490
しかし、我々は離れていじめるよ
なぜ一瞬で。

270
00:10:56,490 --> 00:10:57,702
それは他に何でしょうか？

271
00:10:57,702 --> 00:10:58,755
>> 読者：[聞こえない]

272
00:10:58,755 --> 00:11:00,380
DAVIDマラン：そして私は視覚的にそれをやってみましょう。

273
00:11:00,380 --> 00:11:04,720
だからこの手紙Sであると仮定し

274
00:11:04,720 --> 00:11:05,604
>> 聴衆：それは一つだ。

275
00:11:05,604 --> 00:11:06,520
DAVIDマラン：それは一つだ。

276
00:11:06,520 --> 00:11:06,710
右？

277
00:11:06,710 --> 00:11:08,950
これは、どの配列です
我々は、ランダムアクセスを持っていることを意味します。

278
00:11:08,950 --> 00:11:11,790
そして、私たちはこの考えている場合
25ゼロこのような、

279
00:11:11,790 --> 00:11:13,800
そして我々はそれを実現するため、
ああ、ここに私の入力Sです、

280
00:11:13,800 --> 00:11:16,350
私は確かに変換することができます
S、ASCII文字、

281
00:11:16,350 --> 00:11:18,540
対応する数
ゼロと25の間

282
00:11:18,540 --> 00:11:20,910
その後すぐに
それが属する場所に置きます。

283
00:11:20,910 --> 00:11:26,120
>> しかし、もちろん、とすぐに私がに着くように
名前の二人目は、AまたはBまたはC

284
00:11:26,120 --> 00:11:29,300
最終的に、私が使用した場合には
私の解決策としてプロービングリニア、

285
00:11:29,300 --> 00:11:31,360
の実行時間
最悪の場合には挿入

286
00:11:31,360 --> 00:11:33,120
実際にどのように委譲しようとしている？

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
そして、私はここでそれを聞いてなかった
正しく早い段階で。

289
00:11:36,045 --> 00:11:36,920
読者：[聞こえない]

290
00:11:36,920 --> 00:11:41,620
DAVIDマラン：だからそれはかつて確かにnとする
あなたが十分に大きなデータセットを持っている。

291
00:11:41,620 --> 00:11:44,410
したがって、一方では、もし
あなたの配列が十分な大きさ

292
00:11:44,410 --> 00:11:48,287
そして、あなたのデータはあなたが、十分に希薄である
この美しい時定数を得る。

293
00:11:48,287 --> 00:11:50,620
しかし、すぐに作業を開始するように
より多くの要素を取得し、

294
00:11:50,620 --> 00:11:53,200
ちょうど統計的にあなたが得る
手紙を持つ多くの人々

295
00:11:53,200 --> 00:11:56,030
として自分の名前や手紙
Bは、潜在的可能性

296
00:11:56,030 --> 00:11:57,900
何かもっと直線的に委譲。

297
00:11:57,900 --> 00:11:59,640
だから、非常に完璧ではない。

298
00:11:59,640 --> 00:12:00,690
だから我々はやれること？

299
00:12:00,690 --> 00:12:03,210
>> さて、私たちのものだった
ときに我々の前に解決策

300
00:12:03,210 --> 00:12:06,820
より多くのダイナミズムを持ちたい
許可された配列のようなもの？

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
読者：[聞こえない]

303
00:12:08,960 --> 00:12:10,030
DAVIDマラン：我々は何を紹介したのですか？

304
00:12:10,030 --> 00:12:10,530
うん。

305
00:12:10,530 --> 00:12:11,430
だから、リンクリスト。

306
00:12:11,430 --> 00:12:14,430
さて、リンクされたものを見てみましょう
リストには、代わりに私たちのために行う可能性があります。

307
00:12:14,430 --> 00:12:17,630
さて、私は、その私たちを提案してみましょう
次のように絵を描く。

308
00:12:17,630 --> 00:12:19,620
さて、これは異なっている
例からの画像

309
00:12:19,620 --> 00:12:24,750
別のテキストから、実際には、その
実際にはサイズ31の配列を使用している。

310
00:12:24,750 --> 00:12:28,220
この著者は、単に
文字列をハッシュすることを決めた

311
00:12:28,220 --> 00:12:32,430
人名に基づいていない、
しかし彼らの生年月日に基づいて。

312
00:12:32,430 --> 00:12:35,680
かかわらず、月の、彼らが考え出し
あなたは月の最初の日に生まれている場合

313
00:12:35,680 --> 00:12:39,580
または月の31日、作者
その値に基づいてハッシュ化する、

314
00:12:39,580 --> 00:12:44,154
少し外に名前を広がるように
ちょうど26のスポットが許すかもしれないよりもっと。

315
00:12:44,154 --> 00:12:47,320
そして、おそらくそれは少しより均一だ
アルファベット文字と一緒に行くよりも、

316
00:12:47,320 --> 00:12:50,236
理由はもちろん、おそらくあります
名前を持つ、世界で多くの人々

317
00:12:50,236 --> 00:12:54,020
それは、より確かで始まる
アルファベットのいくつかの他の文字。

318
00:12:54,020 --> 00:12:56,380
だから、多分これは少しある
より均一と仮定すると

319
00:12:56,380 --> 00:12:58,640
一様分布
今月渡って赤ちゃんの。

320
00:12:58,640 --> 00:12:59,990
>> しかし、もちろん、これはまだ不完全である。

321
00:12:59,990 --> 00:13:00,370
右？

322
00:13:00,370 --> 00:13:01,370
私たちは、衝突を抱えている。

323
00:13:01,370 --> 00:13:04,680
この中で、複数の人
データ構造は、依然として

324
00:13:04,680 --> 00:13:08,432
少なくとも同じ誕生日を持つ
あなたは関係なく、月のだ。

325
00:13:08,432 --> 00:13:09,640
しかし、著者は何をしたのか？

326
00:13:09,640 --> 00:13:13,427
我々は配列を持っているようにまあ、それは見えます
垂直に描かれた左側に、

327
00:13:13,427 --> 00:13:15,010
それはちょうどアーティストの演奏だ。

328
00:13:15,010 --> 00:13:18,009
それは問題ではありませんどのような方向ます
配列を描く、それはまだアレイだ。

329
00:13:18,009 --> 00:13:20,225
これは明らかの配列は何ですか？

330
00:13:20,225 --> 00:13:21,500
>> 読者：リンクリスト。

331
00:13:21,500 --> 00:13:21,650
>> DAVIDマラン：うん。

332
00:13:21,650 --> 00:13:23,490
それはだように見えます
リンクリストの配列。

333
00:13:23,490 --> 00:13:26,490
だからもう一度、ソートのこの時点まで
現在、これらのデータ構造を使用する

334
00:13:26,490 --> 00:13:28,550
それ以上の成分として
興味深いソリューション、

335
00:13:28,550 --> 00:13:30,862
あなたは絶対に取ることができます
配列のような、基本的な、

336
00:13:30,862 --> 00:13:33,320
そして、より多くの何かを取る
リンクリストのような興味深い

337
00:13:33,320 --> 00:13:36,660
とさえさえにそれらを組み合わせる
より興味深いデータ構造。

338
00:13:36,660 --> 00:13:39,630
そして実際に、これはあまりにだろう
ハッシュテーブルと呼ばれる、

339
00:13:39,630 --> 00:13:42,610
それによって配列である
実際には、ハッシュテーブル、

340
00:13:42,610 --> 00:13:45,600
しかし、そのハッシュテーブルはあります
チェーン、いわば、

341
00:13:45,600 --> 00:13:50,220
それはに基づいて拡大または縮小することができます
挿入したい要素の数。

342
00:13:50,220 --> 00:13:52,990
>> さて、それに応じて、何が
今の時間を実行している？

343
00:13:52,990 --> 00:13:58,030
私は誰かを挿入したい場合は
その誕生日10月31日である、

344
00:13:58,030 --> 00:13:59,040
彼または彼女はどこに行くのでしょうか？

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
わかりました。

347
00:14:01,030 --> 00:14:02,819
それは31と言う非常に下部にある。

348
00:14:02,819 --> 00:14:03,610
そして、それは完璧だ。

349
00:14:03,610 --> 00:14:05,060
つまり、一定の時間でした。

350
00:14:05,060 --> 00:14:08,760
しかし、我々は他の誰かを見つける場合には
その誕生日です、見てみましょう、

351
00:14:08,760 --> 00:14:10,950
10月、11月、12月31日？

352
00:14:10,950 --> 00:14:12,790
どこ彼または彼女は行くつもりですか？

353
00:14:12,790 --> 00:14:13,290
同じこと。

354
00:14:13,290 --> 00:14:13,970
しかし二つのステップ。

355
00:14:13,970 --> 00:14:15,303
つまり、それはしかし、一定ではないですね。

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
わかりました。

358
00:14:16,860 --> 00:14:17,840
現時点ではそれがある。

359
00:14:17,840 --> 00:14:20,570
しかし、一般的な場合において、
我々は追加より多くの人々、

360
00:14:20,570 --> 00:14:23,790
確率的に、我々はつもりだ
より多くの衝突を取得します。

361
00:14:23,790 --> 00:14:26,820
>> さて、これは少しある
より良い技術的理由

362
00:14:26,820 --> 00:14:34,580
今、私のチェーンは中かもしれない
最悪の場合どのくらい？

363
00:14:34,580 --> 00:14:38,890
私は、このよりにn個の人を挿入した場合
高度なデータ構造であり、n人

364
00:14:38,890 --> 00:14:41,080
最悪の場合、それがn個になるだろう。

365
00:14:41,080 --> 00:14:41,815
なぜ？

366
00:14:41,815 --> 00:14:43,332
>> 読者：ので、もし誰も
同じ誕生日を持つ、

367
00:14:43,332 --> 00:14:44,545
彼らは一行ことになるだろう。

368
00:14:44,545 --> 00:14:45,420
DAVIDマラン：パーフェクト。

369
00:14:45,420 --> 00:14:47,480
それは少し不自然かもしれませんが、
しかし、本当に最悪の場合には、

370
00:14:47,480 --> 00:14:50,117
全員が同じ誕生日を持つ場合、
あなたが持っている入力が与えられ、

371
00:14:50,117 --> 00:14:51,950
あなたが持っているつもり
大規模な長鎖。

372
00:14:51,950 --> 00:14:54,241
だから、あなたはそれを呼び出すことができ
テーブルをハッシュが、本当にそれはだ

373
00:14:54,241 --> 00:14:56,810
とだけ大規模なリンクリスト
無駄なスペースの全体の多く。

374
00:14:56,810 --> 00:15:00,460
しかし、一般的に、私たちはと仮定した場合
少なくとも、誕生日はuniform--です

375
00:15:00,460 --> 00:15:01,750
そしてそれはおそらくありません。

376
00:15:01,750 --> 00:15:02,587
私はそれをアップする作ってるんだ。

377
00:15:02,587 --> 00:15:04,420
しかし、我々は仮定した場合、用
議論のために

378
00:15:04,420 --> 00:15:07,717
彼らは、その後理論的には、場合であること
これは垂直表現です

379
00:15:07,717 --> 00:15:11,050
アレイで、よくして、うまくいけばあなたがいる
あるチェーンを取得するつもり、あなたが知っている、

380
00:15:11,050 --> 00:15:15,880
ほぼ同じ長さの場所のそれぞれ
これらは、その月の日を表す。

381
00:15:15,880 --> 00:15:19,930
>> 月に31日間があるかどうか、今、
それは本当に私の走行時間を意味し、

382
00:15:19,930 --> 00:15:25,230
31以上のn個のビッグOが、ある
リニアよりも良い感じ。

383
00:15:25,230 --> 00:15:27,950
しかし、私たちの一つ何だった
公約数週間

384
00:15:27,950 --> 00:15:31,145
前にそれを表現するに来たときはいつでも
アルゴリズムの実行時間？

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
ただ唯一の高次項を見てください。

387
00:15:35,190 --> 00:15:35,690
右？

388
00:15:35,690 --> 00:15:37,400
31は間違いなく便利です。

389
00:15:37,400 --> 00:15:39,610
しかし、これはまだ、nのビッグOで。

390
00:15:39,610 --> 00:15:41,730
しかし、テーマの一つ
問題は、5つの設定

391
00:15:41,730 --> 00:15:43,950
になるだろう
絶対にそれを認める、

392
00:15:43,950 --> 00:15:47,320
漸近的に、理論的には
このデータ構造

393
00:15:47,320 --> 00:15:50,470
ただ同然ではない
1大規模なリンクリスト。

394
00:15:50,470 --> 00:15:53,550
実際、最悪の場合には、この
ハッシュテーブルには、その中に委譲可能性があります。

395
00:15:53,550 --> 00:15:57,620
>> しかし、現実の世界では、私達と人間
その自身のMacやPCまたは何

396
00:15:57,620 --> 00:16:01,240
そして現実の世界を実行している
実世界のデータ上のソフトウェア、

397
00:16:01,240 --> 00:16:03,260
どのアルゴリズムあなたが好むするつもりですか？

398
00:16:03,260 --> 00:16:09,180
終了ステップまたは取るもの
かかるnは31の手順で割った1

399
00:16:09,180 --> 00:16:12,900
データの一部作品を見つけるために、または
いくつかの情報を検索するには？

400
00:16:12,900 --> 00:16:16,580
私は絶対に31になり、意味
現実の世界の違い。

401
00:16:16,580 --> 00:16:18,540
それが31倍高速である。

402
00:16:18,540 --> 00:16:20,880
そして私たち人間は確かにある
ことを理解しようとして。

403
00:16:20,880 --> 00:16:23,004
>> だから、二分法を実現
そこに実際に間

404
00:16:23,004 --> 00:16:25,920
理論的に物事について話
間違いと漸近的にどの

405
00:16:25,920 --> 00:16:28,760
私たちが見てきたように値を持ち、
しかし現実の世界では、

406
00:16:28,760 --> 00:16:32,930
あなただけのことを心配している場合
一般的な入力のための人間の幸せ、

407
00:16:32,930 --> 00:16:36,010
あなたは非常によく受け入れたいかもしれません
はい、これが線形である、という事実は、

408
00:16:36,010 --> 00:16:38,360
それが31倍高速だ
より直線的である可能性があります。

409
00:16:38,360 --> 00:16:41,610
そしていっそのこと、私たちはする必要はありません
誕生日のような任意の何かを、

410
00:16:41,610 --> 00:16:44,030
我々は少しを過ごすことができ
より多くの時間と賢さ

411
00:16:44,030 --> 00:16:47,140
そして私たちがやるかもしれないものを考え、
多分人の名前を与えられ、

412
00:16:47,140 --> 00:16:50,130
それらを組み合わせることが彼らの誕生日
何かを把握するための成分

413
00:16:50,130 --> 00:16:52,720
それは本当に多い
均一かつ少ないジャギー、

414
00:16:52,720 --> 00:16:56,250
ので、この絵よりも、話すこと
現在、それは可能性があります示唆している。

415
00:16:56,250 --> 00:16:57,750
どのように我々はコード内でこれを実装するだろうか？

416
00:16:57,750 --> 00:17:00,280
さて、私は、その私たちを提案してみましょう
ちょうど私達がしたいくつかの構文を借りる

417
00:17:00,280 --> 00:17:01,799
これまで数回を使用していました。

418
00:17:01,799 --> 00:17:03,590
と私は定義するつもりです
再びノード、

419
00:17:03,590 --> 00:17:06,812
ほんの一部の総称である
いくつかのデータ構造のコンテナ。

420
00:17:06,812 --> 00:17:09,020
私はそれを提案するつもりだ
文字列がそこに起こっている。

421
00:17:09,020 --> 00:17:11,369
しかし、我々は服用開始するつもりだ
今、これらの補助輪オフ。

422
00:17:11,369 --> 00:17:13,230
>> これ以上のCS50ライブラリない
本当に、あなたが望む場合を除き

423
00:17:13,230 --> 00:17:15,230
あなたの最後のためにそれを使用する
結構ですプロジェクトは、

424
00:17:15,230 --> 00:17:18,569
しかし、今、私たちは引き戻すするつもりだ
カーテンとそれだけでchar型のスターだと言う。

425
00:17:18,569 --> 00:17:22,069
だから、そこに言葉があることを行っている
問題になっている人の名前。

426
00:17:22,069 --> 00:17:25,079
そして今、私はリンクを持っている
ここで次のノードに

427
00:17:25,079 --> 00:17:28,170
これらが表すように
ノードの各々

428
00:17:28,170 --> 00:17:30,950
チェーン内の、潜在的に、
リンクリストの。

429
00:17:30,950 --> 00:17:34,090
>> そして今、どのように私は宣言しない
ハッシュテーブル自体？

430
00:17:34,090 --> 00:17:36,660
どのように私はこの全体の構造体を宣言しますか？

431
00:17:36,660 --> 00:17:40,960
まあ、本当に、私はポインタを使用し多くのように
リストの最初の要素だけに

432
00:17:40,960 --> 00:17:44,510
前、同じように私は言うことができます
私はちょうどポインタの束を必要とする

433
00:17:44,510 --> 00:17:46,270
この全体のハッシュテーブルを実装します。

434
00:17:46,270 --> 00:17:49,484
私は配列を持っているつもりだ
ハッシュテーブル用のテーブルと呼ばれる。

435
00:17:49,484 --> 00:17:50,900
それは、サイズ容量であることになるだろう。

436
00:17:50,900 --> 00:17:52,525
それはそれで収まることができますどのように多くの要素です。

437
00:17:52,525 --> 00:17:56,180
これで、これらの要素のそれぞれ
アレイは、ノードのスターになるだろう。

438
00:17:56,180 --> 00:17:56,810
なぜ？

439
00:17:56,810 --> 00:18:00,160
さて、この絵あたり、私は何だ
ハッシュテーブルなどを実装

440
00:18:00,160 --> 00:18:04,330
効果的に初めにちょうどある
我々は垂直に描かれてきたこの配列、

441
00:18:04,330 --> 00:18:06,820
その正方形の各
ポインタを表す。

442
00:18:06,820 --> 00:18:09,170
スラッシュを持っているものという
それらを介してだけではnullです。

443
00:18:09,170 --> 00:18:11,410
そして持っているものは、
右に行く矢印

444
00:18:11,410 --> 00:18:16,140
実際のノードへの実際のポインタである、
リンクリストの開始をエルゴ。

445
00:18:16,140 --> 00:18:19,050
>> だからここに、その後、どのように我々はかもしれないです
ハッシュテーブルを実装する

446
00:18:19,050 --> 00:18:21,580
別々のチェーンを実装しています。

447
00:18:21,580 --> 00:18:22,840
今、私たちはより良い行うことができますか？

448
00:18:22,840 --> 00:18:25,632
すべての権利は​​、私は最後の時間を約束したこと
我々は、一定の時間を達成することができます。

449
00:18:25,632 --> 00:18:27,381
そして、私は一種のあなたを与えた
ここで、一定時間、

450
00:18:27,381 --> 00:18:29,850
が、その後、本当にいないと述べ
一定の時間、それはまだだから

451
00:18:29,850 --> 00:18:31,890
合計に依存
素子数

452
00:18:31,890 --> 00:18:34,500
あなたが入力することにしている
データ構造。

453
00:18:34,500 --> 00:18:35,980
しかし、我々はこれをしなかったとします。

454
00:18:35,980 --> 00:18:39,550
私はこっちの画面に戻りましょう。

455
00:18:39,550 --> 00:18:44,520
明確な、私はまたここにこれを投影してみましょう
画面には、と私はこれをしなかったとします。

456
00:18:44,520 --> 00:18:49,300
私は名前を挿入するとし
Davenの私のデータ構造に変換する。

457
00:18:49,300 --> 00:18:52,100
>> だから私は、文字列を挿入したい
データ構造にDaven。

458
00:18:52,100 --> 00:18:54,370
私は何を使用していない場合は、
テーブルをハッシュが、私は使用し

459
00:18:54,370 --> 00:18:56,980
さらに重要なものツリー状
家系図のような

460
00:18:56,980 --> 00:18:59,670
あなたは、いくつかのルートを持っている
トップその後ノードとリーフ

461
00:18:59,670 --> 00:19:01,440
それが下向きと外側に行く。

462
00:19:01,440 --> 00:19:04,450
、そのIと仮定する
Davenのを挿入したい

463
00:19:04,450 --> 00:19:06,430
現在、空のリストに何に。

464
00:19:06,430 --> 00:19:09,780
私は、次の操作を実行するつもりです：私は
このファミリ内のノードを作成するつもり

465
00:19:09,780 --> 00:19:15,170
ツリー状のデータ構造に見える
それぞれのこのような小さな

466
00:19:15,170 --> 00:19:19,640
長方形があり、それでは言わせて、
その中に今26要素について。

467
00:19:19,640 --> 00:19:21,650
そして、各セル
この配列に起こっている

468
00:19:21,650 --> 00:19:23,470
アルファベットの文字を表します。

469
00:19:23,470 --> 00:19:28,190
>> 具体的には、私が治療するつもりです
これは、次にB、次にC、次いでDである

470
00:19:28,190 --> 00:19:29,310
ここで、この1。

471
00:19:29,310 --> 00:19:32,940
だから、これは効果的にしようとしている
手紙D.を表す

472
00:19:32,940 --> 00:19:36,040
しかしDavenのすべてを挿入する
私はもう少しを行う必要が名前を付けます。

473
00:19:36,040 --> 00:19:37,840
だから私は最初いわば、ハッシュするつもりです。

474
00:19:37,840 --> 00:19:41,049
私は最初の文字を見てするつもりです
Davenのは明らかにDであるもので、

475
00:19:41,049 --> 00:19:42,840
と私は割り当てるつもりです
見えノード

476
00:19:42,840 --> 00:19:45,570
のような大きな大きな四角形をthis--
全体アルファベットを収まるほど。

477
00:19:45,570 --> 00:19:47,140
>> 今、Dが行われます。

478
00:19:47,140 --> 00:19:49,720
今A. D-A-V-E-Nは目標である。

479
00:19:49,720 --> 00:19:51,220
だから今、私はするつもりです何これです。

480
00:19:51,220 --> 00:19:54,027
できるだけ早く私は、D通知を始めとして
そこにはポインタがありません。

481
00:19:54,027 --> 00:19:56,860
これは、現時点では、ガベージ値の
または私はヌルに初期化可能性があります。

482
00:19:56,860 --> 00:19:59,630
しかし、私は一緒に行く続けるみましょう
ツリーを構築するこのアイデア。

483
00:19:59,630 --> 00:20:04,260
私はこれらの別のものを割り当てさせ
その中に26の要素を持つノード。

484
00:20:04,260 --> 00:20:05,150
>> そして、あなたは何を知っていますか？

485
00:20:05,150 --> 00:20:09,130
これは、メモリ内だけのノードである場合、その
私は、構造体を使用して、malloc関数を使用して作成

486
00:20:09,130 --> 00:20:11,240
我々はすぐにわかりますように、
私はthis--するつもりです

487
00:20:11,240 --> 00:20:14,450
私はから矢印を引くつもりだ
ダウンDを表すもの

488
00:20:14,450 --> 00:20:15,860
この新しいノードに。

489
00:20:15,860 --> 00:20:19,240
そして今、第一次の
Davenの名前の文字、

490
00:20:19,240 --> 00:20:24,150
私が先に行くつもりV--のD-A-V--
そして、このように別のノードを描き、

491
00:20:24,150 --> 00:20:30,150
それによって、ここにV族元素、どの
我々はinstance--おっとために描きます。

492
00:20:30,150 --> 00:20:31,020
私たちはそこに描画されません。

493
00:20:31,020 --> 00:20:31,936
それはここに行くために起こっている。

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> その後、我々はするつもりだ
これはV.であると考える

496
00:20:35,712 --> 00:20:44,920
その後、ここまで私たちはインデックスになるだろう
ダウンVから我々はEを検討します何に

497
00:20:44,920 --> 00:20:50,100
その後、ここから私たちはするつもりだ
ここでこれらのノードのいずれかを持って行く。

498
00:20:50,100 --> 00:20:52,930
そして今、我々は答えるために質問があります。

499
00:20:52,930 --> 00:20:57,840
私は何とかあることを示すために必要
私たちは、文字列の末尾にDavenだ。

500
00:20:57,840 --> 00:20:59,490
だから、僕はそれがnull残すことができる。

501
00:20:59,490 --> 00:21:02,670
>> しかし、我々はDavenのが何を持っている場合は、
フルネームも、その

502
00:21:02,670 --> 00:21:04,280
我々は、ダベンポートと述べてきたように、ありますか？

503
00:21:04,280 --> 00:21:06,970
だからDavenは何である場合
実際に部分文字列、

504
00:21:06,970 --> 00:21:08,960
はるかに長い文字列の接頭辞？

505
00:21:08,960 --> 00:21:11,450
私達はちょうど永久にできない
何も起こっていないと言う

506
00:21:11,450 --> 00:21:14,410
我々は可能性があるので、そこに行くために
ダベンポートのような単語を挿入することはありません

507
00:21:14,410 --> 00:21:15,840
このデータ構造に

508
00:21:15,840 --> 00:21:19,560
>> だから我々は何ができるか、代わりです
これらの各要素を処理する

509
00:21:19,560 --> 00:21:22,170
多分2を有するものとして
それらの内の要素。

510
00:21:22,170 --> 00:21:24,810
一つは、確かに、ポインタである
私が行ってきたように。

511
00:21:24,810 --> 00:21:27,100
これらのボックスのため、各
ただ一つのセルではありません。

512
00:21:27,100 --> 00:21:29,855
しかし、どのような場合トップ
底の1のひとつ選ぶ

513
00:21:29,855 --> 00:21:32,230
ので、ヌルになるだろう
ただまだダベンポートありません。

514
00:21:32,230 --> 00:21:34,197
何なら、トップ1
いくつかの特別な値はありますか？

515
00:21:34,197 --> 00:21:36,530
そして、それは少しになるだろう
それをこのサイズを描画するのは難しい。

516
00:21:36,530 --> 00:21:38,130
しかし、それだけでチェックマークだと仮定します。

517
00:21:38,130 --> 00:21:38,920
チェックしてください。

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-Nが文字列である
このデータ構造である。

519
00:21:44,230 --> 00:21:48,350
>> 一方、私はより多くのスペースを持っていた場合
ここで、私は、P-O-R-Tを行うことができます

520
00:21:48,350 --> 00:21:52,650
と私は、ノードにチェックを入れることができます
それは非常に最後に手紙Tを有する。

521
00:21:52,650 --> 00:21:55,460
だから、これは大規模である
複雑に見えるデータ構造。

522
00:21:55,460 --> 00:21:57,210
そして、私の手書き
確かに助けにはならない。

523
00:21:57,210 --> 00:22:00,043
しかし、私は、何かを挿入したい場合
他に、私たちはどうなるのかを検討してください。

524
00:22:00,043 --> 00:22:03,370
我々はデビッドを入れたい場合は、
私たちは、同じロジック、D-A-Vに従うだろう

525
00:22:03,370 --> 00:22:08,802
しかし、今私は次に指すことになり
要素ではないEから、私からDへ

526
00:22:08,802 --> 00:22:10,760
そうであるように起こっている
このツリー内の複数のノード。

527
00:22:10,760 --> 00:22:12,325
私たちは、以上のコールのmallocを持っているつもりです。

528
00:22:12,325 --> 00:22:14,700
しかし、私はしたくない
この絵の完全な混乱。

529
00:22:14,700 --> 00:22:17,710
それでは、1つではなく、見てみましょう
その、プリ策定されています

530
00:22:17,710 --> 00:22:21,810
このようにして、ドットをドットではない、
ドットが、ちょうど略さ配列。

531
00:22:21,810 --> 00:22:23,950
しかし、各ノードの
ここでは、この木のアップで

532
00:22:23,950 --> 00:22:26,700
同じthing--を表し
サイズ26の配列レイ。

533
00:22:26,700 --> 00:22:28,860
>> または私達はなりたい場合は、
本当に適切な今、何を

534
00:22:28,860 --> 00:22:30,790
誰かの名前などの場合
アポストロフィ、レッツ

535
00:22:30,790 --> 00:22:35,560
各ノードが実際に持っていることを前提とし
その中に27のインデックスだけでなく、26のような。

536
00:22:35,560 --> 00:22:42,020
だから、これは今のデータであることを行っている
構造はtrie--、T-R-I-Eと呼ばれる。

537
00:22:42,020 --> 00:22:46,120
たぶんあるトライ、
ツリーの歴史的に巧妙な名前

538
00:22:46,120 --> 00:22:49,040
そのはのために最適化さだ
もちろん、検索、

539
00:22:49,040 --> 00:22:50,870
それはトライですので、I-Eで綴られている。

540
00:22:50,870 --> 00:22:52,710
しかし、それはトライの歴史です。

541
00:22:52,710 --> 00:22:55,860
>> だから、トライがこのツリー状のデータであり、
家系図のような構造

542
00:22:55,860 --> 00:22:57,510
それは、最終的にはそのように動作します。

543
00:22:57,510 --> 00:23:00,890
そして、ここでのほんの一例です
他の人の名前の全体の束。

544
00:23:00,890 --> 00:23:03,540
しかし、今の質問
手元に持っているものです。

545
00:23:03,540 --> 00:23:08,070
我々は間違いなく、よりを導入することによって得られる
複雑なデータ構造、および一

546
00:23:08,070 --> 00:23:09,870
率直に言って、それは大量のメモリを使用しています。

547
00:23:09,870 --> 00:23:11,703
>> 、たとえ理由
現時点では、私が唯一だ

548
00:23:11,703 --> 00:23:15,050
D'sのポインタを使用して
AとVとESとNS、

549
00:23:15,050 --> 00:23:16,700
私は多くのメモリの一体を無駄にしています。

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
しかし、私は一つのリソースを費やす場所、
私は戻って別のものを獲得する傾向があります。

552
00:23:22,660 --> 00:23:26,020
だから私はより多くのスペースを費やしている場合には、
おそらく望み何ですか？

553
00:23:26,020 --> 00:23:27,407
私は何より少ない支出てること？

554
00:23:27,407 --> 00:23:28,240
読者：少ない時間。

555
00:23:28,240 --> 00:23:28,990
DAVIDマラン：時間。

556
00:23:28,990 --> 00:23:30,320
さて、なぜそれがでしょうか？

557
00:23:30,320 --> 00:23:33,880
さて、挿入は何ですか
時間、今やビッグOの観点から、

558
00:23:33,880 --> 00:23:37,660
Davenのような名前の
またはダベンポートまたはデビッド？

559
00:23:37,660 --> 00:23:39,340
さて、Davenは5つのステップだった。

560
00:23:39,340 --> 00:23:42,350
ダベンポートは、9つのステップになり、
ので、それはさらにいくつかの手順になります。

561
00:23:42,350 --> 00:23:44,250
デビッドは、同様に5つのステップになります。

562
00:23:44,250 --> 00:23:47,230
だから、それらは、コンクリートである
数字、しかし確実にあります

563
00:23:47,230 --> 00:23:49,550
の上限
誰かの名前の長さ。

564
00:23:49,550 --> 00:23:52,240
そして実際、問題で
5仕様のセット、

565
00:23:52,240 --> 00:23:54,050
我々は提案するつもりだ
それは何か、その

566
00:23:54,050 --> 00:23:55,470
それが40-いくつか奇数の文字です。

567
00:23:55,470 --> 00:23:58,180
>> 現実的には、誰も持っていません
無限に長い名前、

568
00:23:58,180 --> 00:24:01,542
αの長さということである
名前または当社がかもしれない文字列の長さ

569
00:24:01,542 --> 00:24:03,750
の特定の状態を有する
構造は間違いなく何ですか？

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
それは一定です。

572
00:24:06,250 --> 00:24:06,430
右？

573
00:24:06,430 --> 00:24:09,310
それはのような大きな一定かもしれない
40代が、それは一定である。

574
00:24:09,310 --> 00:24:13,752
そしてそれはどのように多くのへの依存を持たない
その他の名称は、このデータ構造である。

575
00:24:13,752 --> 00:24:15,460
換言すれば、I場合
今挿入したかった

576
00:24:15,460 --> 00:24:20,540
コルトンまたはガブリエルまたはロブまたはZamylaまたは
アリソンまたはベリンダまたはその他の名前

577
00:24:20,540 --> 00:24:23,940
スタッフからこのデータに変換
構造は、実行時間である

578
00:24:23,940 --> 00:24:26,750
他の名前を挿入する
全く影響されようとして

579
00:24:26,750 --> 00:24:30,220
どのように多くの他の要素によるものである
既にデータ構造内？

580
00:24:30,220 --> 00:24:31,040
そうではありません。

581
00:24:31,040 --> 00:24:31,540
右？

582
00:24:31,540 --> 00:24:36,150
我々は効果的に使用しているため
この多層ハッシュテーブル。

583
00:24:36,150 --> 00:24:38,280
との実行時間
これらの操作のいずれか

584
00:24:38,280 --> 00:24:41,510
の数に依存しているではない
データ構造内の要素

585
00:24:41,510 --> 00:24:43,090
最終的にしようとしているか
データ構造内とすることで、

586
00:24:43,090 --> 00:24:44,714
しかし、どのような特別の長さ？

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> 対象の文字列
作るんおり、挿入された

589
00:24:49,200 --> 00:24:52,580
この漸近的に一定
1のtime--大きなO。

590
00:24:52,580 --> 00:24:54,720
と率直に言って、ただで
現実の世界では、この

591
00:24:54,720 --> 00:24:58,380
Davenの名前をとり挿入手段
5つのステップ、またはダベンポート9様

592
00:24:58,380 --> 00:25:00,100
ステップ、またはデビッドの5つのステップ。

593
00:25:00,100 --> 00:25:03,071
それはかなりくそ小さな実行時間です。

594
00:25:03,071 --> 00:25:05,320
そして、確かに、それは非常にだ
良いこと、特に

595
00:25:05,320 --> 00:25:08,126
それは総に依存しません
そこにある要素の数。

596
00:25:08,126 --> 00:25:10,500
だから我々はこれを実装する方法
コー​​ド内の構造の種類は？

597
00:25:10,500 --> 00:25:12,900
それはもう少しだ
複雑な、まだそれはだ

598
00:25:12,900 --> 00:25:15,050
のアプリケーションだけ
基本的なビルディングブロック。

599
00:25:15,050 --> 00:25:17,830
私は再定義するつもりです
私たちノードを次のように

600
00:25:17,830 --> 00:25:21,100
BOOL word--と呼ばれ、この
何でも呼び出すことができた。

601
00:25:21,100 --> 00:25:23,970
しかし、ブール値を表す
私は、チェックマークとして描いたもの。

602
00:25:23,970 --> 00:25:24,490
はい。

603
00:25:24,490 --> 00:25:26,720
これは文字列の終わりです
このデータ構造である。

604
00:25:26,720 --> 00:25:30,702
>> もちろん、ノードスター
子供に言及がある。

605
00:25:30,702 --> 00:25:32,410
そして、確かに、ただ好き
家系、あなた

606
00:25:32,410 --> 00:25:34,370
ノードを検討する
それをオフにぶら下がっている

607
00:25:34,370 --> 00:25:36,920
一部の親の底部の
子どもされる要素。

608
00:25:36,920 --> 00:25:40,510
だから子供たちがしようとしている
27の配列を、27日いずれかになり

609
00:25:40,510 --> 00:25:41,680
ちょうどアポストロフィためのものである。

610
00:25:41,680 --> 00:25:43,390
私たちは、ソートするつもりだ
特別な場合のこと。

611
00:25:43,390 --> 00:25:45,400
ですから、特定のを持つことができます
アポストロフィを含む名前。

612
00:25:45,400 --> 00:25:47,399
多分ハイフンべき
そこに行くが、あなたはよ

613
00:25:47,399 --> 00:25:50,330
p個セット5我々は唯一のケアに表示
文字やアポストロフィ約。

614
00:25:50,330 --> 00:25:52,990
>> そして、あなたはどのように表すか
データ構造自体？

615
00:25:52,990 --> 00:25:56,454
どのようにルートを表します
このトライの、いわば？

616
00:25:56,454 --> 00:25:59,620
さて、あなたは、リンクされたリストと同じように
最初の要素へのポインタを必要としています。

617
00:25:59,620 --> 00:26:04,270
トライであなただけのいずれかが必要
このトライのルートへのポインタ。

618
00:26:04,270 --> 00:26:07,290
そこからあなたがハッシュすることができます
あなたのようにダウンして深く深く

619
00:26:07,290 --> 00:26:10,460
構造内の他のすべてのノードに。

620
00:26:10,460 --> 00:26:13,440
だから、単純にこの缶の持つ
私たちは、その構造体を表しています。

621
00:26:13,440 --> 00:26:15,877
>> 今ああ、質問をMeanwhile--。

622
00:26:15,877 --> 00:26:17,220
>> 読者：BOOL言葉は何ですか？

623
00:26:17,220 --> 00:26:20,490
>> DAVIDマラン：ブール·ワードがある
ちょうどこのC化身

624
00:26:20,490 --> 00:26:22,920
私が説明したものの
ここでは、ときに、このボックスに

625
00:26:22,920 --> 00:26:26,000
私は、それぞれの分割開始
2ピースに配列の要素。

626
00:26:26,000 --> 00:26:27,600
一つは、次のノードへのポインタである。

627
00:26:27,600 --> 00:26:30,280
もう一つは、である必要があります
チェックボックスのようなもの

628
00:26:30,280 --> 00:26:33,770
はい、ありますと言って
ここで終了Daven語、

629
00:26:33,770 --> 00:26:35,610
私たちはしたくないので、
現時点では、デイブ。

630
00:26:35,610 --> 00:26:39,320
>> Daveはあることを行っているにもかかわらず
合法的な言葉は、彼がトライではありません

631
00:26:39,320 --> 00:26:39,830
まだ。

632
00:26:39,830 --> 00:26:40,950
そしてDは言葉ではない。

633
00:26:40,950 --> 00:26:42,770
とD-Aは、単語や名前ではありません。

634
00:26:42,770 --> 00:26:45,020
だから、チェックマーク
あなただけ一度示している

635
00:26:45,020 --> 00:26:48,190
このノードがヒット
文字の前の道

636
00:26:48,190 --> 00:26:50,700
実際にあなたが挿入した文字列。

637
00:26:50,700 --> 00:26:53,660
だから、すべてのブール値です
そこには私たちのためにやっている。

638
00:26:53,660 --> 00:26:55,500
>> トライ上の任意の他の質問？

639
00:26:55,500 --> 00:26:56,215
うん。

640
00:26:56,215 --> 00:26:58,035
>> 聴衆：オーバーラップとは何ですか？

641
00:26:58,035 --> 00:26:59,945
あなたがDaveとDavenを持っている場合はどうなりますか？

642
00:26:59,945 --> 00:27:00,820
DAVIDマラン：パーフェクト。

643
00:27:00,820 --> 00:27:02,580
あなたがDaveとDavenを持っている場合はどうなりますか？

644
00:27:02,580 --> 00:27:06,240
我々は挿入した場合ので、ニックネームを言う
David-- Dave--のD-A-V-Eの？

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
これは実際に超簡単です。

647
00:27:08,700 --> 00:27:10,325
だから我々は唯一の4つのステップを取るつもりだ。

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E。そして、私はに何がありますか
私はその第4のノードを打つ一度やる？

650
00:27:15,847 --> 00:27:16,680
ちょうどチェックしよう。

651
00:27:16,680 --> 00:27:18,000
我々はすでに行ってもいいです。

652
00:27:18,000 --> 00:27:18,840
Doneを。

653
00:27:18,840 --> 00:27:19,750
4つのステップ。

654
00:27:19,750 --> 00:27:21,590
漸近的に一定の時間。

655
00:27:21,590 --> 00:27:26,300
そして今、我々はそれが両方のデイブ示さきた
そしてDavenは、構造内の文字列です。

656
00:27:26,300 --> 00:27:27,710
そうではない問題。

657
00:27:27,710 --> 00:27:30,200
そして、どのように存在に気づく
Davenのそれをしなかった

658
00:27:30,200 --> 00:27:34,750
いつでも多かれ少なかれを取る
デイブおよびその逆のための時間。

659
00:27:34,750 --> 00:27:36,000
>> だから我々は今、他に何ができますか？

660
00:27:36,000 --> 00:27:40,680
私たちは前にこの比喩を使ってきた
トレーのようなものを表す。

661
00:27:40,680 --> 00:27:43,380
しかし、それはことが判明
トレイスタックは、実際に

662
00:27:43,380 --> 00:27:47,187
別の抽象データの実証
より高いレベルのデータ構造type--

663
00:27:47,187 --> 00:27:49,770
終わりの日はちょうどであること
配列やリンクリストのような

664
00:27:49,770 --> 00:27:50,970
以上の世俗的な何か。

665
00:27:50,970 --> 00:27:53,270
しかし、それはもっと面白い
概念的なコンセプト。

666
00:27:53,270 --> 00:27:56,440
これらのようなスタック、
ここメイザーでトレイ、

667
00:27:56,440 --> 00:27:58,750
一般的に呼ばれている
ちょうどスタックをthat--。

668
00:27:58,750 --> 00:28:02,540
>> データ構造のこの種の
あなたは2 operations--を持っている

669
00:28:02,540 --> 00:28:05,880
あなたがのために1いわゆるプッシュを持っている
スタックに何かを追加

670
00:28:05,880 --> 00:28:08,320
別のトレイを置くように
スタックの一番上にバックアップします。

671
00:28:08,320 --> 00:28:11,350
そして、あなたを意味する、ポップ
一番上のトレイを脱ぐ。

672
00:28:11,350 --> 00:28:16,210
しかし、どのようなスタックに関する重要なのは、ということです
それがこの奇妙な特性を持っている。

673
00:28:16,210 --> 00:28:19,560
食堂のスタッフの通りです
次の食事のためのトレイを並べ替える、

674
00:28:19,560 --> 00:28:21,380
何がになるだろう
どのように学生約真

675
00:28:21,380 --> 00:28:22,856
このデータ構造と相互作用？

676
00:28:22,856 --> 00:28:24,480
読者：彼らは1オフをポップするつもりだ。

677
00:28:24,480 --> 00:28:26,550
DAVIDマラン：彼らはするつもりだ
1オフ、うまくいけばトップをポップ。

678
00:28:26,550 --> 00:28:28,910
それ以外の場合は、だけの種類の愚かだ
底にすべての道を行く。

679
00:28:28,910 --> 00:28:29,070
右？

680
00:28:29,070 --> 00:28:31,620
データ構造は、実際には許可しない
あなたは、少なくとも底のトレイをつかむために

681
00:28:31,620 --> 00:28:32,520
簡単に。

682
00:28:32,520 --> 00:28:35,040
したがって、この好奇心があります
スタックへのプロパティ

683
00:28:35,040 --> 00:28:39,730
最後の項目であること
最初の1外になるだろう。

684
00:28:39,730 --> 00:28:43,400
およびコンピュータ科学者が呼び出す
これは後入れ先出しLIFO--。

685
00:28:43,400 --> 00:28:45,540
そして、それは実際に持っているん
興味深い応用。

686
00:28:45,540 --> 00:28:50,090
それは必然的にいくつかのように明確ではありません
他のものは、それが、実際には、有用であり得る

687
00:28:50,090 --> 00:28:54,040
それは、実際に実現することができる
いくつかの異なる方法で。

688
00:28:54,040 --> 00:28:58,550
>> だから一つであり、実際に、みましょう
私にその飛び込むまでもありません。

689
00:28:58,550 --> 00:28:59,860
のではなく、これをやってみましょう。

690
00:28:59,860 --> 00:29:03,700
ほとんどの1を見てみましょう
同じ考えが、それはちょっと公平だ。

691
00:29:03,700 --> 00:29:04,200
右？

692
00:29:04,200 --> 00:29:07,560
あなたはこれらのファンの男の子の一つ以上なら
本当にアップル製品が好きな女の子

693
00:29:07,560 --> 00:29:10,130
あなたが午前3:00に目が覚めた
いくつかの店で並ぶ

694
00:29:10,130 --> 00:29:14,150
非常に最新のiPhoneを取得するには、
このようにキューに入れられた可能性があります。

695
00:29:14,150 --> 00:29:15,800
>> 今、キューは非常に意図的に名前が付けられています。

696
00:29:15,800 --> 00:29:18,190
ありますので、それはラインだ
それにはいくつかの公平性。

697
00:29:18,190 --> 00:29:18,690
右？

698
00:29:18,690 --> 00:29:21,690
あなたがしている場合、それは一種の吸い込まだろう
アップルストアで最初にそこに着いた

699
00:29:21,690 --> 00:29:25,700
しかし、あなたは効果的に一番下です
トレイその後のAppleの従業員のため

700
00:29:25,700 --> 00:29:28,189
誰が最後の人をポップ
実際にラインに入った。

701
00:29:28,189 --> 00:29:31,230
スタックやキュー、たとえそう
機能的に彼らはsame--の一種だ

702
00:29:31,230 --> 00:29:33,105
それはちょうどこのコレクションだ
資源のの

703
00:29:33,105 --> 00:29:36,210
成長しshrink--するつもりはあります
それは、この公平性の側面、

704
00:29:36,210 --> 00:29:39,634
現実の世界では、少なくとも、
どこで行使操作

705
00:29:39,634 --> 00:29:40,800
根本的に異なっている。

706
00:29:40,800 --> 00:29:43,360
キューstack--
rather--持っていると言われて

707
00:29:43,360 --> 00:29:45,320
二つの操作：n個のキューおよびdキュー。

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
またはあなたはそれらを呼び出すことができます
物事の任意の数。

710
00:29:48,090 --> 00:29:50,770
しかし、あなたは単にキャプチャしたい
1が追加されているという考え

711
00:29:50,770 --> 00:29:53,230
一つは、最終的に減算される。

712
00:29:53,230 --> 00:29:58,840
>> さてボンネットの下に、両方のスタック
キューがどのように実装することができますか？

713
00:29:58,840 --> 00:30:01,390
私たちは、のコードに行くことはありません
それより高いレベルのため、

714
00:30:01,390 --> 00:30:03,387
アイデアは、ソートのより明白である。

715
00:30:03,387 --> 00:30:04,470
私は意味、人間は何をしますか？

716
00:30:04,470 --> 00:30:07,030
私はAppleの最初の人間だ場合
ストアこれはフロントドアで、

717
00:30:07,030 --> 00:30:08,130
あなたが知っている、私はここに立ってするつもりです。

718
00:30:08,130 --> 00:30:09,750
そして次の人の
ここに立つつもり。

719
00:30:09,750 --> 00:30:11,500
そして次の人の
ここに立つつもり。

720
00:30:11,500 --> 00:30:13,792
だから何のデータ構造
キューに向いている？

721
00:30:13,792 --> 00:30:14,542
>> 聴衆：キュー。

722
00:30:14,542 --> 00:30:15,667
DAVIDマラン：まあ、待ち行列。

723
00:30:15,667 --> 00:30:16,390
かしこまりました。

724
00:30:16,390 --> 00:30:16,920
他には？

725
00:30:16,920 --> 00:30:17,600
>> 読者：リンクリスト。

726
00:30:17,600 --> 00:30:18,990
>> DAVIDマラン：リンク
あなたが実装できるリスト。

727
00:30:18,990 --> 00:30:22,500
とリンクされたリストが原因その後いいです
対照的に、それは長い任意に成長することができます

728
00:30:22,500 --> 00:30:24,880
いくつかの固定された数を有することに
ストア内の人々の。

729
00:30:24,880 --> 00:30:27,030
しかし、おそらく固定数
場所の合法的である。

730
00:30:27,030 --> 00:30:30,350
彼らは唯一の20のように持っている場合ので、
初日のiPhone、多分

731
00:30:30,350 --> 00:30:33,930
彼らは唯一のサイズの配列を必要とする
そのキューを表すために20、その

732
00:30:33,930 --> 00:30:37,070
私たちが話し始めると、今だけと言うことです
これらのより高いレベルの問題について、

733
00:30:37,070 --> 00:30:38,890
あなたはそれを実装することができます
任意の数の方法。

734
00:30:38,890 --> 00:30:42,030
そしておそらくちょうどに行くあります
空間と時間にトレードオフである

735
00:30:42,030 --> 00:30:43,950
あるいは単に自分のコードの複雑さ。

736
00:30:43,950 --> 00:30:45,380
>> スタックはどう？

737
00:30:45,380 --> 00:30:48,190
さて、スタックは、我々はあまりにも見てきました
ちょうどこれらのトレイである可能性があります。

738
00:30:48,190 --> 00:30:50,007
そして、あなたは、この配列を実装することができます。

739
00:30:50,007 --> 00:30:53,090
しかし、いくつかの点では、アレイを使用する場合は、
何トレーに起こるだろう

740
00:30:53,090 --> 00:30:54,173
あなたが鎮圧しようとしている？

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
わかりました。

743
00:30:55,670 --> 00:30:57,490
あなただけになるだろう
それほど高く行くことができる。

744
00:30:57,490 --> 00:31:00,156
そして、私は彼らがマザーにしていると思う
実際にその開口部に凹ん。

745
00:31:00,156 --> 00:31:01,950
だから、確かに、それはほとんどだ
メイザーが使用しているような

746
00:31:01,950 --> 00:31:03,783
固定サイズの配列、
あなただけのことができるので、

747
00:31:03,783 --> 00:31:08,302
その開口部で非常に多くのトレイに収まる
人々の膝の下にある下壁。

748
00:31:08,302 --> 00:31:10,010
そしてその結果は次のようになります
配列であると言われ、

749
00:31:10,010 --> 00:31:14,300
しかし、我々は確かにそれを実装することができ
より一般的にはリンクされたリストを持つ。

750
00:31:14,300 --> 00:31:16,390
>> さて、どのような別のデータ構造はどうですか？

751
00:31:16,390 --> 00:31:18,760
私はここに視覚的な他の1を引き上げてみましょう。

752
00:31:18,760 --> 00:31:24,710
ここで、この約1どのようなもの？

753
00:31:24,710 --> 00:31:28,920
なぜそれが持っていないために役に立つかもしれない
トライのように空想何か、どの

754
00:31:28,920 --> 00:31:32,370
我々はこれらの非常に広いのノードを持っていた見て、
それらの各々は、アレイ内にある？

755
00:31:32,370 --> 00:31:35,740
しかし、我々はより多くの何かを何をすれば
単純に、古い学校の家系図のように、

756
00:31:35,740 --> 00:31:38,110
ここに、そのノードのそれぞれ
ほんの数を記憶している。

757
00:31:38,110 --> 00:31:42,180
代わりに、名前または子孫の
ちょうどこのような番号を記憶している。

758
00:31:42,180 --> 00:31:45,250
>> 我々が使用するだけでなく、専門用語
データ構造は、両方の試行で

759
00:31:45,250 --> 00:31:49,510
トライは、再び、である木、
ちょうど1そのノード配列です、

760
00:31:49,510 --> 00:31:51,680
あなたがまだあるかもしれない
小学校から、使用

761
00:31:51,680 --> 00:31:53,860
あなたは家族を作ったとき
tree--葉や根

762
00:31:53,860 --> 00:31:57,250
木との子の
親とその兄弟。

763
00:31:57,250 --> 00:32:03,670
そして、私たちは木を実装する場合があり、
例えば、単にこのよう。

764
00:32:03,670 --> 00:32:07,420
ツリーは、ノードとして場合、一
数はこれらの円、

765
00:32:07,420 --> 00:32:09,947
それは持っているつもりはない
つのポインタが、二つ。

766
00:32:09,947 --> 00:32:11,780
そしてできるだけ早くあなたが追加する
第2のポインタ、あなた

767
00:32:11,780 --> 00:32:13,905
実際に今ソートすることができます
二次元データの

768
00:32:13,905 --> 00:32:14,780
メモリ内の構造。

769
00:32:14,780 --> 00:32:16,660
ずっと二次元様
配列は、次の操作を実行でき

770
00:32:16,660 --> 00:32:18,904
二次元のようなものを持っている
リンクされたリストが、もの

771
00:32:18,904 --> 00:32:20,820
それがパターンに従う
どこに何サイクルがありません。

772
00:32:20,820 --> 00:32:24,487
それは本当に1を持つツリーです
祖父母方法ここまで、その後

773
00:32:24,487 --> 00:32:27,320
いくつかの両親と子供たちと
孫とひ孫。

774
00:32:27,320 --> 00:32:28,370
等。

775
00:32:28,370 --> 00:32:32,390
>> しかし、あまりにもこのことについては本当にきちんとしたものだ
ちょうどコードのビットであなたをいじめるために、

776
00:32:32,390 --> 00:32:35,370
からリコール再帰
しばらく前に、それによって

777
00:32:35,370 --> 00:32:38,220
あなたが自分自身を呼び出す関数を書く。

778
00:32:38,220 --> 00:32:41,140
これは美しい機会です
何かを実装する

779
00:32:41,140 --> 00:32:42,920
再帰のように、このためを考えてみましょう。

780
00:32:42,920 --> 00:32:43,860
>> これが木です。

781
00:32:43,860 --> 00:32:48,040
と私はどのようで少し肛門してきた
私は通りに整数を入れる。

782
00:32:48,040 --> 00:32:51,020
それは特別になるようにそんなに
二分探索木をname--。

783
00:32:51,020 --> 00:32:53,460
今、私たちは、バイナリを聞いた
あなたを検索することができますが、

784
00:32:53,460 --> 00:32:55,180
この事の名前から逆動作しますか？

785
00:32:55,180 --> 00:32:59,280
どのように私のパターンとは何ですか
このツリーに整数を挿入？

786
00:32:59,280 --> 00:33:00,696
それは任意ではありません。

787
00:33:00,696 --> 00:33:01,570
いくつかのパターンがあります。

788
00:33:01,570 --> 00:33:02,090
うん。

789
00:33:02,090 --> 00:33:03,370
>> 読者：左側の小さいもの。

790
00:33:03,370 --> 00:33:03,690
>> DAVIDマラン：うん。

791
00:33:03,690 --> 00:33:05,062
小さいものは左側にある。

792
00:33:05,062 --> 00:33:06,270
大きなものは右側にあります。

793
00:33:06,270 --> 00:33:12,940
そのような真のステートメントがあること
親は、その左側の子よりも大きい

794
00:33:12,940 --> 00:33:14,850
その右の子よりも小さい。

795
00:33:14,850 --> 00:33:17,750
そして一人でいることさえある
再帰的な言葉の定義

796
00:33:17,750 --> 00:33:20,500
あなたはそれを適用することができますので、
すべてのノードに同じロジック

797
00:33:20,500 --> 00:33:23,080
それだけボトムス
アウト、ベースケースあなたなら

798
00:33:23,080 --> 00:33:25,740
あなたのいずれかを打ったとき、意志
葉、いわば、

799
00:33:25,740 --> 00:33:28,580
休暇は、さらに子を持たないところ。

800
00:33:28,580 --> 00:33:30,614
>> 今、どのように数44を見つけるかもしれない？

801
00:33:30,614 --> 00:33:32,280
あなたはHM、ルートから始まると言うでしょう。

802
00:33:32,280 --> 00:33:35,690
55は44ではないだから私は行きたくない
右または、私は左に行きたいですか？

803
00:33:35,690 --> 00:33:37,190
さて、明らかにあなたが左に行きたい。

804
00:33:37,190 --> 00:33:40,060
そしてそれはちょうど携帯電話のようなものだ
バイナリ検索で書籍の例

805
00:33:40,060 --> 00:33:41,099
より一般的。

806
00:33:41,099 --> 00:33:43,390
しかし、我々はそれを実装している
今もう少し動的に

807
00:33:43,390 --> 00:33:45,339
配列ができる場合がありますより。

808
00:33:45,339 --> 00:33:48,130
そして実際に、あなたが見てみたい場合は、
コー​​ドで、一見してください。

809
00:33:48,130 --> 00:33:49,671
これは、ラインの全体の束のように見えます。

810
00:33:49,671 --> 00:33:51,220
しかし、それは美しく簡単です。

811
00:33:51,220 --> 00:33:54,490
あなたは、関数を実装する場合
その目的は生活の中で呼ば検索

812
00:33:54,490 --> 00:33:57,290
値を検索することです
のようなnは、整数、

813
00:33:57,290 --> 00:34:01,756
あなたが1 pointer--で渡されている
根のノードへのポインタ、

814
00:34:01,756 --> 00:34:04,380
むしろ、そこからそのツリーの
あなたが他のすべてにアクセスすることができ、

815
00:34:04,380 --> 00:34:08,850
どのように素直に気付く
あなたはロジックを実装することができます。

816
00:34:08,850 --> 00:34:10,880
木がnullの場合、
明らかにそれはありません。

817
00:34:10,880 --> 00:34:11,880
ちょうどfalseを返してみましょう。

818
00:34:11,880 --> 00:34:12,000
右？

819
00:34:12,000 --> 00:34:14,040
あなたはそれに何も渡していない場合、
そこには何もありません。

820
00:34:14,040 --> 00:34:17,900
>> そうでなければ、nがより小さい場合
今n個の矢印N--ツリー矢印、

821
00:34:17,900 --> 00:34:20,670
我々は、スーパーを導入しましたリコール
簡潔に先日、

822
00:34:20,670 --> 00:34:25,100
それはちょうど、デリファレンスを意味し、
ポインタとnと呼ばれるフィールドを見てください。

823
00:34:25,100 --> 00:34:27,690
だから、そこに行くと意味
Nと呼ばれるフィールドを見てください。

824
00:34:27,690 --> 00:34:33,810
nのであれば、あなたが与えられている値は、小さい
木々の整数の値よりも、

825
00:34:33,810 --> 00:34:35,449
どこに行きたいですか？

826
00:34:35,449 --> 00:34:36,389
左へ。

827
00:34:36,389 --> 00:34:37,780
>> だから、再帰を気づく。

828
00:34:37,780 --> 00:34:39,860
私は真実ではないreturning--よ。

829
00:34:39,860 --> 00:34:40,989
偽ません。

830
00:34:40,989 --> 00:34:45,670
私はどんな答えを返すよ
渡し、呼び出しから自分自身にある

831
00:34:45,670 --> 00:34:50,100
冗長で再びnは、
今は少し異なる何ですか？

832
00:34:50,100 --> 00:34:51,989
どうすれば問題を小さくするのですか？

833
00:34:51,989 --> 00:34:54,920
私は2番目として渡している
引数ではなく、ツリーのルート、

834
00:34:54,920 --> 00:34:59,616
しかし、この場合は左の子。

835
00:34:59,616 --> 00:35:00,990
だから私は左の子に渡している。

836
00:35:00,990 --> 00:35:04,720
>> 一方、nがより大きい場合
私は現在見ているノード、

837
00:35:04,720 --> 00:35:06,690
私は右側を検索します。

838
00:35:06,690 --> 00:35:10,880
そうでなければ、木は、nullでない場合と
要素は左にはない場合

839
00:35:10,880 --> 00:35:13,240
それは、右にはない
ケース素晴らしく何ですか？

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
私たちは実際にノードを見つけた
質問、および私たちはtrueを返します。

842
00:35:18,440 --> 00:35:21,490
>> だから我々は単に表面に傷だ
現在、これらのデータ構造の一部。

843
00:35:21,490 --> 00:35:24,370
問題は5を設定では、よ
なおさらこれらを探る、

844
00:35:24,370 --> 00:35:27,250
そして、あなたのデザインが与えられます
このことについて移動する方法の選択。

845
00:35:27,250 --> 00:35:30,250
私が上で結論付けたいのですがどのような
わずか30秒ティーザーです

846
00:35:30,250 --> 00:35:32,080
来週以降を待って何の。

847
00:35:32,080 --> 00:35:35,390
>> 我々はありがたいbegin--として、あなたはかもしれない
ゆっくりと私たちの移行をthink--

848
00:35:35,390 --> 00:35:38,680
Cと下の世界から
レベルの実装の詳細、

849
00:35:38,680 --> 00:35:42,090
我々は取ることができている世界へ
他の誰かが最終的に持っていることを付与された

850
00:35:42,090 --> 00:35:44,010
これらのデータを実装
私たちのための構造、

851
00:35:44,010 --> 00:35:47,570
そして我々は理解することから始めましょう
実装の現実世界の手段

852
00:35:47,570 --> 00:35:50,560
ウェブベースのプログラムと
より一般的にウェブサイト

853
00:35:50,560 --> 00:35:52,910
そしてまた、非常にセキュリティ
我々は唯一だ含意

854
00:35:52,910 --> 00:35:54,850
の表面を傷つけるし始めて。

855
00:35:54,850 --> 00:35:57,320
ここで私たちを待って何です
来る日。

856
00:35:57,320 --> 00:36:00,480
>> [ビデオ再生]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Heは、メッセージに付属している、
すべての彼の独自のプロトコルを持つ。

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
彼は残酷の世界に来た
ファイアウォール、思いやりルータ、

861
00:36:30,894 --> 00:36:33,368
そして危険、死よりもはるかに悪い。

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
彼は速いです。

864
00:36:36,236 --> 00:36:37,980
彼は強いです。

865
00:36:37,980 --> 00:36:42,830
彼は、TCP / IPのだ、と彼はあなたのアドレスを持っている。

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
「ネットの戦士たち。」

868
00:36:48,074 --> 00:36:49,660
[ENDビデオ再生]

869
00:36:49,660 --> 00:36:50,910
DAVIDマラン：来週来る。

870
00:36:50,910 --> 00:36:51,880
私たちは、あなたが表示されます。

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[ビデオ再生]

873
00:36:56,060 --> 00:36:59,240
-and今、「ディープ思考」
Davenファーナムによる。

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-Davidはいつも始まる
、と講演「よし。」

876
00:37:05,820 --> 00:37:08,750
なぜ、 "ここソリューションです
「今週の問題セットに

877
00:37:08,750 --> 00:37:12,180
または「私たちは、Aのすべてを与えている？」

878
00:37:12,180 --> 00:37:13,380
[笑い]

879
00:37:13,380 --> 00:37:15,530
[ENDビデオ再生]