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
Гэта канец тры тыдні, і калі
Вы не скарысталіся ўжо,

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. І
сапраўды, імёны, што проста,

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
калі б мы маглі атрымаць адзін добраахвотнік,
можа быць, ад далей таму, чым звычайна.

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
СПІКЕР: Добра, у мяне ёсць
тут сіні кнігі праз Z,

33
00:01:36,790 --> 00:01:41,680
і я збіраюся рабіць выгляд, што
У мяне ёсць адзін са студэнтаў,

34
00:01:41,680 --> 00:01:45,770
і яны ідуць у некалькі выпадковым
У канцы трохгадзіннага іспыту блока,

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
ад А да 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
У нас ёсць некалькі паль падобна,
большы, тры паменш.

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

67
00:03:33,790 --> 00:03:36,415
>> АЎДЫТОРЫЯ: я іх замове
калі я знаходжу два лісты

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
Гэта проста, ну, па-першае,
У мяне гэты стэк тут.

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
СПІКЕР: ОК, выдатна.

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. All
Добра, віншую, вы зрабілі гэта.

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
Запіс біць было б
адна хвіліна і 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
Такім чынам, трохі падобны
па духу пузырьковый сартавання,

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
Вы зрабілі тое чатырох адсартаваных паль, і
затым эфектыўна аб'ядналі іх разам.

101
00:05:00,567 --> 00:05:02,650
І вось, мяркую, яшчэ адзін
Тэхніка ў цэлым.

102
00:05:02,650 --> 00:05:06,950
Вы не разглядаць яго як адзін вялікі кучы,
Вы падзялілі праблему на чатыры карэ,

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
з васьмі сваіх аднакласнікаў тут,
здавалася б, выпадкова сартуюцца спачатку.

108
00:05:22,640 --> 00:05:26,110
І мы тады вырашылі парамі, калі
два элемента з таго,

109
00:05:26,110 --> 00:05:26,950
проста памяняць іх месцамі.

110
00:05:26,950 --> 00:05:28,930
Так чатыры і два
відавочна, з таго,

111
00:05:28,930 --> 00:05:31,080
так гэтыя два аднакласнікаў
памяняліся месцамі.

112
00:05:31,080 --> 00:05:35,390
А потым мы паўтарылі з чатырох да шасці гадоў,
затым шэсць і восем, на кожнай ітэрацыі,

113
00:05:35,390 --> 00:05:36,980
рухацца направа.

114
00:05:36,980 --> 00:05:42,590
>> Таму, улічваючы, восем чалавек, колькі парамі
параўнання я зрабіў падчас прагулкі з

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
Таму што, калі ёсць восем
людзі, але ў вас ёсць пару

119
00:05:51,405 --> 00:05:53,880
ім і вы працягваць рухацца
адзін хоп направа,

120
00:05:53,880 --> 00:05:56,060
вы не будзеце мець восем
параўнання, таму што вы не можаце параўнаць

121
00:05:56,060 --> 00:05:59,226
элемент сам у сабе, ці гэта будзе
проста бессэнсоўна, так што вы павінны сем.

122
00:05:59,226 --> 00:06:01,290
Ці ў больш агульным, калі
у нас ёсць рускіх людзей, мы

123
00:06:01,290 --> 00:06:04,300
зрабіць п мінус 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
Я ішоў злева направа па
этап, узяў мяне н мінус 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
параўнання двух людзей, што адчувае сябе
як добры адзінкі вымярэння.

134
00:06:35,900 --> 00:06:40,980
>> Так н мінус 1 крокі ў першы раз,
але тое што адбылося пасля гэтага?

135
00:06:40,980 --> 00:06:46,610
Што адзін Верх адзін праход
праз адваротным выпадку малокомплектных спіс?

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
Нумар восем, хоць яна
пачалося тут, кожны раз, калі я

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
>> Зараз па гэтай логіцы, колькі параўнання
ці трэба рабіць на другі раз

144
00:07:07,630 --> 00:07:09,800
Я раблю, што праход злева направа?

145
00:07:09,800 --> 00:07:10,730
н мінус 2, ці не так?

146
00:07:10,730 --> 00:07:14,297
Было б проста марнаваць свой час, калі I
трымаць параўноўваючы восем супраць каго

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
будзе плюс н мінус два крокі,
дзе п лік людзей.

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
У канцы гэтага алгарытму, па-відаць
ў вас ёсць толькі адно параўнанне пакінулі.

153
00:07:31,259 --> 00:07:33,800
Вы павінны роду выправіць
пачатку спісу ў выпадку двух

154
00:07:33,800 --> 00:07:36,540
і адзін выйшлі з ладу
і павінен быць адзін і два,

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
У агульным выпадку, калі ў вас ёсць
зменная, як у я, і на самай справе гэта адно,

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
п раз п мінус 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
Так што давайце памножым гэта, так вось
н квадрат, мінус п, усё падзяліць на 2.

171
00:08:19,920 --> 00:08:23,200
Гэта сапраўды п квадрат,
падзеленае на 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
Выкажам здагадку, у мяне не было восем
людзі, але сказаць, мільён.

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, мінус
млн, падзеленае на 2.

179
00:08:42,868 --> 00:08:44,159
Цяпер тое, што, што збіраецца раўняцца?

180
00:08:44,159 --> 00:08:47,354
Так 500000000000, мінус 500 000.

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
можа заняць мне 499.999.500.000
крокі ці параўнання ў рэшце рэшт,

184
00:09:01,800 --> 00:09:02,900
мы проста экстрапаляцыі.

185
00:09:02,900 --> 00:09:06,860
>> Гэта адчувае сябе даволі павольна, але, шчыра кажучы
вымярэння адзін пэўны ўваход

186
00:09:06,860 --> 00:09:09,160
як гэта, не ўсё, што кажа пра многае.

187
00:09:09,160 --> 00:09:14,050
Але на самой справе гэта азначае, што да як п
атрымлівае больш і больш, гэты алгарытм

188
00:09:14,050 --> 00:09:16,280
выгляд адчувае сябе горш і
горш, ці вы сапраўды

189
00:09:16,280 --> 00:09:20,450
пачынаюць адчуваць боль, што
ўзвядзенне ў ступень, што п квадрат,

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
Шміт, генеральны дырэктар у той час,

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, Што ты тут
у Google, і мне падабаецца

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
і гэты ад Лары Швімэр.

204
00:10:09,770 --> 00:10:14,760
Што-вы, хлопцы, думаеце, што я
жартую, гэта прама тут.

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
>> -Прабачце, 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
>> -Давай, Які сказаў яму, гэты?

213
00:10:38,180 --> 00:10:40,590
Я не бачыў кампутар
навука ў фоне.

214
00:10:40,590 --> 00:10:42,130
>> -Мы Атрымалі нашы шпіёны там.

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 ВИДЕОВОСПРОИЗВЕДЕНИЕ]

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
можа заняць цэлых 500 мільярдаў крокаў.

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
>> Так што я выдзелены жоўтым колерам тут
Вынікам п падзеленае на квадрат 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
як толькі мы адымаецца ад п падзеленае на лік 2.

229
00:11:20,180 --> 00:11:24,850
І прэтэнзіі я збіраюся зрабіць цяпер,
хто, чорт вазьмі клапоціцца калі адняць ад

230
00:11:24,850 --> 00:11:30,060
трохі стары п над 2, калі першы
частка гэтай формулы з'яўляецца нашмат больш?

231
00:11:30,060 --> 00:11:33,910
Гэта дамінуе над іншым
Тэрмін, н квадрат падзелены на 2

232
00:11:33,910 --> 00:11:37,510
так нашмат больш, ясна, як
н становіцца вялікім, як мільён,

233
00:11:37,510 --> 00:11:41,450
што ёсць на самой справе вялікая розніца ў
канец дня паміж 500000000000

234
00:11:41,450 --> 00:11:45,730
і 499.999.500.000?

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
>> Як н становіцца больш, мы сапраўды
будзе клапаціцца аб велічыні

242
00:12:07,340 --> 00:12:11,560
Тэрмiн у любым такім аналізе
наш выступ алгарытмы.

243
00:12:11,560 --> 00:12:16,230
І я збіраюся сказаць, вы ведаеце, што,
пузырьковый сартавання парадку вялікага O,

244
00:12:16,230 --> 00:12:18,060
парадку п квадрат.

245
00:12:18,060 --> 00:12:20,090
Гэта не зусім н
квадрат, як мы бачылі,

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
І гэта 500 мільярдаў супраць 250
млрд сапраўды, што вялікую справу?

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
Так што нешта накшталт вялікай O п
квадрат, я сцвярджаю, што 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
гэта будзе ў вялікі 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
будзе называецца абмежаваным,
па п, лінейнай функцыяй,

281
00:14:04,300 --> 00:14:07,260
ня квадратычнай, вось выгнутыя?

282
00:14:07,260 --> 00:14:10,780
Што сабой алгарытм, які
заўсёды займае не больш за

283
00:14:10,780 --> 00:14:12,860
чым як п крокаў, або
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
п, ці не так?

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
ой, вось нумар восем,
ці што гэта значэнне.

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
Так, вядома ,, п з'яўляецца верхняй мяжой.

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
ёсць час, бегаючы Гэта
абмежаваная вялікім O з часопіса п, увайдзіце н?

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
Тое, што было паказчыкам таго, наколькі
колькі часу ці колькі слёз IT

308
00:15:07,754 --> 00:15:10,170
узяў мяне, каб знайсці такога чалавека, як
Майк Сміт у тэлефоннай кнізе?

309
00:15:10,170 --> 00:15:13,212
Мы сцвярджалі, што гэта быў часопіс п, і
нават калі не знаёмыя ці гэта

310
00:15:13,212 --> 00:15:15,170
трохі туманна, што
лагарыфм ці паказчык быў,

311
00:15:15,170 --> 00:15:17,650
толькі памятайце, што § п
як правіла, адносіцца да працэсу,

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
>> Так увайсці н тычыцца, вядома,
да прыкладу тэлефоннай кнігі,

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
Калі ён выкарыстоўваецца бінарны пошук, увайдзіце н
будзе верхняя мяжа, колькі

318
00:15:37,374 --> 00:15:38,040
час, якое патрабуецца.

319
00:15:38,040 --> 00:15:44,027
Але гэтыя алгарытмы, якія беглі ў
§ п мяркуецца, якія ключавыя дэталі?

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
>> Цяпер, што гэта можа азначаць, Big 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, можа быць, гэта 1000,

329
00:16:04,060 --> 00:16:07,750
але гэта залежыць ад
памер праблемы.

330
00:16:07,750 --> 00:16:10,850
Незалежна ад таго, наколькі вялікі п,
пастаянная алгарытм час

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
незалежна ад таго, як доўга
масіў на З?

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
Што сабой алгарытм, які мае
ніжняя мяжа п крокаў,

362
00:17:31,920 --> 00:17:33,350
або 2n крокаў, або крокі 3n?

363
00:17:33,350 --> 00:17:36,241
Некаторыя фактар ​​п крокаў,
вось яго ніжняй мяжы.

364
00:17:36,241 --> 00:17:36,740
Так?

365
00:17:36,740 --> 00:17:37,910
>> АЎДЫТОРЫЯ: Bubble роду?

366
00:17:37,910 --> 00:17:41,610
>> СПІКЕР: Bubble роду бярэ
Вы мінімальна п крокаў, то чаму?

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
калі я ўручаю вам восем чалавек
якія ўжо адсартаваныя,

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
Але што адбываецца, каб у вас н крокі.

381
00:18:09,700 --> 00:18:12,033
>> І наадварот, тое, што яшчэ адзін
спосаб думаць пра гэта?

382
00:18:12,033 --> 00:18:15,240
Bubble роду з'яўляецца амега,
так бы мовіць, з п,

383
00:18:15,240 --> 00:18:19,050
таму што калі вы паглядзіце на
менш, чым п элементаў, тое, што

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
Мы людзі маглі погляд на васьмі
людзі і быць як, о, гэта сартуецца,

387
00:18:26,800 --> 00:18:28,430
што мяне не ўзялі н крокі, але гэта зрабіў.

388
00:18:28,430 --> 00:18:30,810
Твае вочы, хоць вас выгляд
ад таго, маюць вялікае поле зроку,

389
00:18:30,810 --> 00:18:33,184
Вы глядзелі на васьмі элементаў,
Вы глядзелі на восем чалавек,

390
00:18:33,184 --> 00:18:34,610
вось восем крокаў эфектыўна.

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
Што сабой алгарытм, які мае больш нізкі
абмежаванне на час яго працы аднаго?

399
00:18:54,565 --> 00:18:58,350
1 крок, 2 кроку, 10 крокаў, але
сталым, залежыць ад п,

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
ОК, упэўнены.

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
Паколькі Е сапраўды бярэ
ўваход, гэта радок,

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
>> Узяў адзін крок, можа быць, два крокі,
але пастаяннае лік крокаў

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
атрымаць вельмі пашанцавала два разы запар.

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
і амега, ніжняя мяжа,
адзін у тым жа, што

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
н або тэта некаторага іншага значэння.

435
00:20:18,270 --> 00:20:20,661
Гэта проста азначае, калі большая
Высновы і амега аднолькавыя.

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
н мінус 1, ці не так?

445
00:20:44,437 --> 00:20:47,770
Таму што, калі я проста пачаць з таго, што я знаходжуся
улічваючы і я пачынаю параўноўваць яго ці яе,

446
00:20:47,770 --> 00:20:49,519
то яму ці ёй, як ён
ці ёй, яму ці ёй, я

447
00:20:49,519 --> 00:20:52,010
можа толькі пару элементаў
разам н мінус 1 раз.

448
00:20:52,010 --> 00:20:55,630
Так выбар роду ж бярэ
н мінус 1 крокі ў першы раз.

449
00:20:55,630 --> 00:20:59,540
>> Колькі крокаў трэба, каб я
знайсці другі найменшы элемент?

450
00:20:59,540 --> 00:21:02,920
н мінус 2, таму што я нямы
калі я працягваю глядзець на тыя ж людзі,

451
00:21:02,920 --> 00:21:06,280
зноў, калі я ўжо выбралі яго
або яе і пакласці іх на месца.

452
00:21:06,280 --> 00:21:09,270
І трэці крок, н
мінус 3, то п мінус 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
н квадрат, калі мы робім да, што сумаванне.

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
Можа быць, гэта п, як і раней.

461
00:21:32,360 --> 00:21:35,040
Можа быць, гэта н квадрат, як гэта
Цяпер як верхняя грань.

462
00:21:35,040 --> 00:21:35,874
>> АЎДЫТОРЫЯ: н квадрат.

463
00:21:35,874 --> 00:21:36,664
СПІКЕР: н квадрат.

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
можа дазвольце мне перапыніць пасля
усяго п або каля крокі.

473
00:21:54,350 --> 00:21:57,080
Так сапраўды, выбар
сартаваць, амега п квадрат.

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
Так што, калі было тры чалавекі, тут і
новы чалавек належаў спосаб там,

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
І так, што п мінус 1 shufflings,
н мінус 2 shufflings, п

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 з'яўляецца адным
што пацешна глядзець ўверх.

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
>> І на самай справе, калі вы чытаеце
як артыкулы Вікіпедыі,

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
маючы яшчэ некалькі элементаў,
але больш за двух працэсараў.

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
Добра.

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
ОК, прыемна пазнаёміцца.

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
Дык хто з гледачоў, што з'яўляецца
па меншай меры, адзін элемент алгарытму

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
Пасля таго, як у нас ёсць чатыры адсартаваныя касцюмы, што
нам трэба зрабіць, каб чатырох паль

576
00:26:16,950 --> 00:26:20,059
для дасягнення адной
сартуюцца палубу, дастаткова проста?

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
але па меншай меры на чатыры часткі.

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
Такім чынам, давайце паглядзім, дзве хвіліны
і восем секунд,

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
Прычым у псевдокода I
пералічыў больш метадычную шлях

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
Гэтыя лініі як бы, ідуць у
Лінія тры, і вы можаце роду

606
00:27:52,910 --> 00:27:55,140
думаць пра тое, што ў вашым
разумовым поглядам як пятля.

607
00:27:55,140 --> 00:27:59,080
Гэта кажу вам, каб вярнуцца да кроку
тры і паўтараю, зноў, і зноў,

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
з'яўляецца пошук Mike
у тым жа чынам,

616
00:28:29,140 --> 00:28:31,580
але толькі ў левай
палова ці правая палова.

617
00:28:31,580 --> 00:28:33,420
>> Такім чынам, іншымі словамі, калі
Я пачынаю з крокам адзін,

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
калі Сміт раней у кнізе, крок сем
шукаць Майка ў левай палове кнігі.

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
І гэта ў корані адрозніваецца
ад тых трох апошніх, і, вядома,

641
00:29:50,040 --> 00:29:52,140
Апошнія чатыры, калі мы ўключым bogosort.

642
00:29:52,140 --> 00:29:54,810
Вось псевдокод для сартавання зліццём.

643
00:29:54,810 --> 00:30:00,170
Калі на ўваходзе п элементаў, таму, улічваючы,
масіў памеру 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
Што маецца на ўвазе калі аддам цябе
масіў, даўжыня якога н менш 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
І вось, калі ён адчувае сябе
як мы Copping з.

663
00:30:43,230 --> 00:30:46,900
Я папрасіў вас разабрацца
п элементаў, і я

664
00:30:46,900 --> 00:30:50,712
кажучы, добра, зрабіце гэта з дапамогай сартавання
налева і сартавання права.

665
00:30:50,712 --> 00:30:52,420
Але я кажу адно
Іншая справа, і гэта

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
Ці магу я абмяняць восем стрэс
мячы для васьмі чалавек?

675
00:31:19,470 --> 00:31:29,320
Добра, а як наконт вас тры, вы чатыры
у гэтым раздзеле, пяць, шэсць, і давайце

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
ОК, ды ОК.

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
Нумар два, нумар тры, нумар чатыры,
нумар пяць, шэсць, сем, восем.

683
00:31:50,800 --> 00:31:52,140
Я правільна зрабіў восем на гэты раз.

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
>> Так сартаванне зліццём у першую чаргу
на ўваходзе п элементаў,

691
00:32:15,149 --> 00:32:18,440
і, відавочна, не менш за два, гэта
восем, так што я яшчэ крыху папрацаваць.

692
00:32:18,440 --> 00:32:21,140
Так што цяпер у думках мы як клас
цяпер у яшчэ галіны,

693
00:32:21,140 --> 00:32:22,540
што азначае тры крокі.

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
Так як я магу ісці аб сартаванні
Спіс зараз памеру чатыры?

700
00:32:36,770 --> 00:32:38,730
Што мой алгарытм?

701
00:32:38,730 --> 00:32:42,580
Спачатку я праверыць гэта н менш двух, няма,
так што я прыступіць да яшчэ блок зноў.

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
Добра, так што цяпер я называю жа зліццё
алгарытм сартавання, з'яўляецца н менш за два?

707
00:32:57,000 --> 00:33:00,590
Не, гэта два, так што я павінен разабрацца
левая палова, а правая палова.

708
00:33:00,590 --> 00:33:02,042
Таму тут мы ідзем, сартаваць левую палову.

709
00:33:02,042 --> 00:33:03,750
Чаму б вам проста не
зрабіце адзін крок наперад.

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
ОК, Дарэн актывізаваў
наперад, і ён цяпер сартуецца.

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
Добра, шэсць, я збіраюся сцвярджаць,
Вы зараз сартуюцца, давай наперад.

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
Даволі трывіяльна, так што я
збіраецца аб'яднаць у шэсць,

765
00:34:44,310 --> 00:34:46,930
зрабіць крок назад,
восем, зрабіць крок назад.

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
Так ніхто не збіраецца злівацца ў месцы
тут, калі б вы маглі зрабіць крок назад,

789
00:35:30,509 --> 00:35:32,930
і тры збіраецца
зрабіць крок назад, зліваюцца.

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
Пяць прыйдзе першым,
і сем прыйдзе наступны.

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
>> ОК, гэта дзіўна.

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
Я збіраюся рухаць правай рукой адзін
пераступіць пазначыць нумар тры,

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
У нас ёсць Лукі з нумар два
або Крыс з нумарам тры.

829
00:37:05,000 --> 00:37:07,460
Відавочна Лукі, лік
два, так што вы прыйшлі сюды.

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
Так тры будзе далей,
затым чатыры будзе далей,

838
00:37:31,650 --> 00:37:38,750
і цяпер пяць будзе далей, то шэсць,
і сем, і, нарэшце, восем.

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
Выбар роду, што з'яўляецца яшчэ адным
даволі проста адзін,

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
можа быць пры ўжыванні да набору дадзеных, гэта
нават не памер восем, але нават шмат,

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
Калі мы робім гэта ў апошні раз,
давайце Перазагрузіць, давайце вернемся

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
>> АЎДЫТОРЫЯ: Увайсці н.

878
00:39:41,890 --> 00:39:42,760
>> СПІКЕР: Увайсці н.

879
00:39:42,760 --> 00:39:46,300
Але тады ёсць яшчэ адзін ключавы крок,
гэты алгарытм не ўвайсці п крокаў.

880
00:39:46,300 --> 00:39:48,992
Калі б гэта было толькі ўвайсці п крокаў,
мы былі б у той жа праблемы

881
00:39:48,992 --> 00:39:51,200
як і раней, дзе мы не можам быць
што ўсё ў сартуюцца.

882
00:39:51,200 --> 00:39:54,480
Вы павінны мінімальна паглядзець на п элементаў
каб пераканацца, што п элементаў сартуюцца,

883
00:39:54,480 --> 00:39:55,950
у адваротным выпадку гэта скачок веры.

884
00:39:55,950 --> 00:39:59,810
>> Так што гэта мінімальна часопіс п крокаў, але
што з гэтай нагоды ключавой стадыі зліцця

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
Гэта п, але я не зрабіў усяго
аб'яднаць у апошні раз.

888
00:40:10,150 --> 00:40:15,089
На кожнай з гэтых ўкладзеных выклікаў, на кожным
з тых, ўкладзеных зліццё, я да гэтага часу сартуюцца.

889
00:40:15,089 --> 00:40:18,380
Я аб'яднаны гэтыя два хлопцы, то гэтыя два
хлопцы, то гэтыя два хлопцы і так далей.

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
Так што, калі што падзяляе спіс
можна зрабіць часопіс п раз,

895
00:40:28,570 --> 00:40:33,880
і зліццё ў канчатковым рахунку, прымае п
крокі, што можа быць цяпер верхняя

896
00:40:33,880 --> 00:40:37,000
абмежаванне на які працуе
Час нашага алгарытму?

897
00:40:37,000 --> 00:40:37,980
н увайсці н.

898
00:40:37,980 --> 00:40:40,560
>> І на самай справе, вось што
мы дасягнулі тут.

899
00:40:40,560 --> 00:40:44,650
Так пачуццё, што вы бачыце візуальна, калі
гэтыя тры рэчы працаваць бок аб бок

900
00:40:44,650 --> 00:40:47,930
з'яўляецца н квадрат супраць п
квадрат супраць н часопіса п.

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