1
00:00:00,000 --> 00:00:03,332
>> [Играет музыка]

2
00:00:03,332 --> 00:00:06,490
>> ANDI Пэн: Добро пожаловать в неделю 3 раздела.

3
00:00:06,490 --> 00:00:09,550
Спасибо, что вы, ребята, все приходящие на
в этом более раннее время начала сегодня.

4
00:00:09,550 --> 00:00:11,466
Мы получили хороший, немного
интимная группа сегодня.

5
00:00:11,466 --> 00:00:14,570
Так что надеюсь, мы доберемся до
отделка, пожалуй, рано,

6
00:00:14,570 --> 00:00:15,780
немного пораньше.

7
00:00:15,780 --> 00:00:22,057
Так быстро, просто некоторые
Анонсы повестке дня сегодня.

8
00:00:22,057 --> 00:00:23,890
Прежде чем мы начнем, мы
собираюсь просто перейти

9
00:00:23,890 --> 00:00:28,910
некоторые краткие материально-технических вопросов, PSET
вопросы, Инструктаж, такие вещи, как, что.

10
00:00:28,910 --> 00:00:30,250
И тогда мы будем нырять прямо в.

11
00:00:30,250 --> 00:00:34,710
Мы будем использовать отладчик GDB под названием, чтобы
начать развенчание наш код, который Дэвид

12
00:00:34,710 --> 00:00:36,550
объяснил в лекции в другой день.

13
00:00:36,550 --> 00:00:39,420
Мы пойдем в течение четырех видов рода.

14
00:00:39,420 --> 00:00:42,310
Мы пойдем на них довольно быстро
так как они довольно интенсивно.

15
00:00:42,310 --> 00:00:45,710
Но знайте, что все слайды и
Исходный код всегда онлайн.

16
00:00:45,710 --> 00:00:50,810
Так что не стесняйтесь, в вашем прочтении, чтобы
вернуться назад и взглянуть на это.

17
00:00:50,810 --> 00:00:53,930
>> Мы пойдем через
асимптотическая обозначения, которые

18
00:00:53,930 --> 00:00:55,944
это просто причудливый способ
сказать "время автономной работы",

19
00:00:55,944 --> 00:00:58,360
где у нас есть большой O, которая
Дэвид объяснил в лекции.

20
00:00:58,360 --> 00:01:01,550
И у нас также есть Omega, который
это нижняя граница времени выполнения.

21
00:01:01,550 --> 00:01:06,450
И мы будем говорить немного больше
в глубине о том, как эти работы.

22
00:01:06,450 --> 00:01:10,160
И, наконец, мы пойдем по бинарного поиска,
потому что многие из вас, кто уже

23
00:01:10,160 --> 00:01:15,190
взглянул на ваших psets, наверное, знаете, что
что это вопрос, который находится в вашем PSET.

24
00:01:15,190 --> 00:01:17,470
Таким образом, вы будете все будут счастливы
что мы рассмотрим это сегодня.

25
00:01:17,470 --> 00:01:20,610
>> И, наконец, за ваш
раздел обратной связи, я на самом деле

26
00:01:20,610 --> 00:01:23,000
осталось около 15 минут при
конец просто перейти

27
00:01:23,000 --> 00:01:27,730
логистика pset3, какие-либо вопросы,
может быть, немного руководством, если хотите,

28
00:01:27,730 --> 00:01:28,990
прежде чем мы начнем программирование.

29
00:01:28,990 --> 00:01:30,890
Так давайте попробуем получить через
материал довольно быстро.

30
00:01:30,890 --> 00:01:33,880
И тогда мы можем провести некоторое время
принимая больше вопросов для PSET.

31
00:01:33,880 --> 00:01:35,230
ХОРОШО.

32
00:01:35,230 --> 00:01:39,570
>> Быстро, поэтому лишь немногие
Анонсы прежде чем мы начнем сегодня.

33
00:01:39,570 --> 00:01:45,410
Во-первых, добро пожаловать, чтобы сделать
это через два ваших psets.

34
00:01:45,410 --> 00:01:49,432
Я взглянул на your-- Да, давайте
получить аплодисменты для этого одного.

35
00:01:49,432 --> 00:01:51,140
На самом деле, я был очень,
действительно впечатлен.

36
00:01:51,140 --> 00:01:55,800
Я оцениваются первый PSET для вас, ребята
на прошлой неделе и вы, ребята, сделали невероятное.

37
00:01:55,800 --> 00:01:58,290
>> Стиль был на момент
кроме нескольких замечаний.

38
00:01:58,290 --> 00:02:00,660
Убедитесь, что вы всегда
Комментируя свой код.

39
00:02:00,660 --> 00:02:03,040
Но ваши psets были на точке.

40
00:02:03,040 --> 00:02:05,549
И держать его.

41
00:02:05,549 --> 00:02:08,090
И это хорошо для грейдера в
видеть, что вы, ребята, положить

42
00:02:08,090 --> 00:02:10,704
как много усилий в вашем стиле
и ваш дизайн в коде

43
00:02:10,704 --> 00:02:12,120
что мы хотели бы, чтобы вы видите.

44
00:02:12,120 --> 00:02:16,450
Так я передаю по моей благодарности
для остальных ТП.

45
00:02:16,450 --> 00:02:19,210
>> Однако есть
Несколько вопросов тант

46
00:02:19,210 --> 00:02:22,010
Я просто хочу, чтобы перейти на что
как бы жизнь

47
00:02:22,010 --> 00:02:24,900
и много другого
ТП «живет немного легче.

48
00:02:24,900 --> 00:02:28,220
Во-первых, я заметил это
мимо week-- как многие из вас

49
00:02:28,220 --> 00:02:32,301
были работает на check50
код, прежде чем представить?

50
00:02:32,301 --> 00:02:32,800
ХОРОШО.

51
00:02:32,800 --> 00:02:36,690
Таким образом, каждый должен делать check50,
because-- secret-- мы на самом деле

52
00:02:36,690 --> 00:02:41,540
запустить check50 как часть нашей правоте
скрипты для тестирования кода.

53
00:02:41,540 --> 00:02:45,480
Так что, если ваш код не удается
check50, по всей вероятности,

54
00:02:45,480 --> 00:02:47,570
это, вероятно, будет
потерпеть неудачу также наш чек.

55
00:02:47,570 --> 00:02:49,320
Иногда вы, ребята,
есть правильные ответы.

56
00:02:49,320 --> 00:02:52,200
Мол, в жадные, некоторые из
у вас есть правильные цифры,

57
00:02:52,200 --> 00:02:53,960
Вы просто распечатать некоторые дополнительные вещи.

58
00:02:53,960 --> 00:02:55,940
И, что дополнительный материал
на самом деле не проходит проверку,

59
00:02:55,940 --> 00:02:58,440
потому что компьютер не
знаю, что он ищет.

60
00:02:58,440 --> 00:03:00,981
И так будет просто запустить через,
видеть, что ваш вывод не

61
00:03:00,981 --> 00:03:03,810
соответствует тому, что мы ожидаем ответ
быть, и отметьте, что это неправильно.

62
00:03:03,810 --> 00:03:06,560
>> И я знаю, что произошло в
некоторые из ваших случаях на этой неделе.

63
00:03:06,560 --> 00:03:09,870
Так что я вернулся и вручную
regraded код каждого.

64
00:03:09,870 --> 00:03:12,780
В будущем, хотя,
Пожалуйста, убедитесь, что

65
00:03:12,780 --> 00:03:14,570
что вы работаете
проверить 50 на коде.

66
00:03:14,570 --> 00:03:17,970
Потому что это своего рода боли в ТП
чтобы вернуться и вручную реклассификацию

67
00:03:17,970 --> 00:03:21,197
каждый PSET для каждого
один, немного пропустил экземпляр.

68
00:03:21,197 --> 00:03:22,530
Так что я не снимал ни одного очка.

69
00:03:22,530 --> 00:03:25,210
Я думаю, что, может быть, снял
один или два для проектирования.

70
00:03:25,210 --> 00:03:27,710
В будущем, хотя, если
Вы не справляются check50,

71
00:03:27,710 --> 00:03:31,330
точки будут приняты
от правильности.

72
00:03:31,330 --> 00:03:35,020
>> Кроме того, в psets
за пятницам в полдень.

73
00:03:35,020 --> 00:03:38,990
Я думаю, что есть семь минут
в конце льготного периода, что мы даем вам.

74
00:03:38,990 --> 00:03:42,434
За время Гарвардского, они позволили
семь минут поздно, чтобы всем.

75
00:03:42,434 --> 00:03:44,350
Так вот в Йельском университете, мы будем
придерживаться, что хорошо.

76
00:03:44,350 --> 00:03:47,910
Но довольно много, в 12:07,
если ваш PSET это не в том,

77
00:03:47,910 --> 00:03:49,720
это будет отмечен как поздно.

78
00:03:49,720 --> 00:03:53,160
И поэтому, хотя она отмечается
а поздно, я TA--

79
00:03:53,160 --> 00:03:54,870
прежнему будет классификации ваши psets.

80
00:03:54,870 --> 00:03:56,760
Таким образом, вы все еще будете видеть сорт появляются.

81
00:03:56,760 --> 00:03:58,820
Тем не менее, известно, что в
конец семестра,

82
00:03:58,820 --> 00:04:02,270
все поздние psets будет просто
автоматически обнуляется с помощью компьютера.

83
00:04:02,270 --> 00:04:04,490
>> Мы делаем это по двум причинам.

84
00:04:04,490 --> 00:04:09,220
Один из них, иногда мы получаем
извинился, как отговорки деканатов,

85
00:04:09,220 --> 00:04:10,762
позже, что я не знаю, о еще.

86
00:04:10,762 --> 00:04:13,761
Таким образом, мы хотели, чтобы убедиться, что мы классификации
все только в том случае, как, я

87
00:04:13,761 --> 00:04:15,080
отсутствует простить декана.

88
00:04:15,080 --> 00:04:17,000
А во-вторых, имейте в
ум, вы все еще можете

89
00:04:17,000 --> 00:04:19,370
падение один PSET, что
обладает полными точки размах.

90
00:04:19,370 --> 00:04:21,430
И таким образом, мы хотели, чтобы оценка
все ваши psets только

91
00:04:21,430 --> 00:04:24,730
чтобы убедиться, что ваш осциллографа
есть и вы пытаетесь их.

92
00:04:24,730 --> 00:04:29,150
Таким образом, даже если это поздно, вы все еще будете
получить кредит для области видимости точек, я думаю.

93
00:04:29,150 --> 00:04:33,730
>> Так Мораль история, сделать
Убедитесь, что ваш psets в по времени.

94
00:04:33,730 --> 00:04:38,350
И если они не находятся в на время,
знаю, что это не здорово.

95
00:04:38,350 --> 00:04:41,678
Да, прежде чем я двигаться дальше, кто-нибудь есть
любые вопросы, касающиеся обратной связи Pset?

96
00:04:41,678 --> 00:04:42,178
Да.

97
00:04:42,178 --> 00:04:43,630
>> АУДИТОРИЯ: Вы сказали, мы
может упасть один из psets?

98
00:04:43,630 --> 00:04:44,296
>> ANDI Пэн: Да.

99
00:04:44,296 --> 00:04:47,050
Так что в целом девять psets
в течение семестра.

100
00:04:47,050 --> 00:04:50,610
И если у вас есть область
points-- так просто сфера,

101
00:04:50,610 --> 00:04:53,567
довольно много, вы попыткой выполнения
Проблема, вы положить в время,

102
00:04:53,567 --> 00:04:56,150
вы показываете, что вы имеете
продемонстрировали вы читали спецификации.

103
00:04:56,150 --> 00:04:57,191
Это довольно много возможностей.

104
00:04:57,191 --> 00:04:59,370
И если вы выполняете
Сфера точки, мы

105
00:04:59,370 --> 00:05:03,360
может упасть самая низкая
одним из полном объеме.

106
00:05:03,360 --> 00:05:06,790
Так вот в ваших интересах, чтобы
заполнить и попробовать все PSET.

107
00:05:06,790 --> 00:05:10,320
>> Даже если upload-- ни один из
им работать, загружать их все.

108
00:05:10,320 --> 00:05:13,711
И тогда мы будем, мы надеемся, смогут
дать вам некоторые из этих точек обратно.

109
00:05:13,711 --> 00:05:14,210
Круто.

110
00:05:14,210 --> 00:05:16,780
Другие вопросы?

111
00:05:16,780 --> 00:05:17,840
Отлично.

112
00:05:17,840 --> 00:05:21,960
>> Во-вторых, офис hours-- несколько
быстрые заметки о рабочих часов.

113
00:05:21,960 --> 00:05:24,300
Итак, сначала приходят в начале недели.

114
00:05:24,300 --> 00:05:26,909
Никто не когда-нибудь в
Приёмные часы по понедельникам.

115
00:05:26,909 --> 00:05:28,700
Christabel пришли к
Приёмные часы прошлой ночью.

116
00:05:28,700 --> 00:05:29,691
Да, Christabel.

117
00:05:29,691 --> 00:05:32,190
И что мы имеем в офисе
часов прошлой ночью, Christabel?

118
00:05:32,190 --> 00:05:33,020
>> АУДИТОРИЯ: У нас было мороженое.

119
00:05:33,020 --> 00:05:36,160
>> ANDI Пэн: Так что это правильно, мы должны были
мороженое на офисных часов вчера вечером.

120
00:05:36,160 --> 00:05:39,390
Хотя я не могу обещать вам, что
мы будем иметь мороженое в рабочее время

121
00:05:39,390 --> 00:05:43,230
каждую неделю, что я могу обещать вам,
является то, что будет значительно

122
00:05:43,230 --> 00:05:45,380
лучше студент соотношение TA.

123
00:05:45,380 --> 00:05:47,650
Как законно, это как три к одному.

124
00:05:47,650 --> 00:05:50,350
Принимая во внимание, что с контрастируют
Четверг, у вас есть около 150

125
00:05:50,350 --> 00:05:52,830
действительно подчеркнул детей и не мороженое.

126
00:05:52,830 --> 00:05:55,360
И это просто не продуктивно для всех.

127
00:05:55,360 --> 00:05:58,730
Так Мораль этой истории в том, прийти пораньше
в рабочее время и хорошие вещи

128
00:05:58,730 --> 00:06:00,310
случится.

129
00:06:00,310 --> 00:06:02,110
>> Кроме того, быть готовыми, чтобы задать вопросы.

130
00:06:02,110 --> 00:06:03,200
Вы знаете?

131
00:06:03,200 --> 00:06:05,420
Независимо от того, ТА, я
думаю, говорили,

132
00:06:05,420 --> 00:06:10,710
мы получали пару студентов
которые приходят в четверг на, вроде бы, 10:50

133
00:06:10,710 --> 00:06:15,100
не прочитав спецификацию
будучи, как мне помочь, помоги мне.

134
00:06:15,100 --> 00:06:18,200
К сожалению, в тот момент, есть
не так много мы можем сделать, чтобы помочь вам.

135
00:06:18,200 --> 00:06:19,590
Так что приезжайте в начале недели.

136
00:06:19,590 --> 00:06:22,040
Приходите пораньше, чтобы рабочее время.

137
00:06:22,040 --> 00:06:23,350
Будьте готовы задавать вопросы.

138
00:06:23,350 --> 00:06:25,310
Убедитесь, что вы, как
студент, находятся там, где

139
00:06:25,310 --> 00:06:27,620
Вы должны быть так, что
ТП может направлять вас вместе

140
00:06:27,620 --> 00:06:32,850
что и часы офиса
должны быть выделены для.

141
00:06:32,850 --> 00:06:37,380
>> Во-вторых, так что я знаю профессоров
хотел удивить нас с тестами.

142
00:06:37,380 --> 00:06:39,439
Я был профессором те
как, йо, кстати,

143
00:06:39,439 --> 00:06:41,230
помните, что среднесрочный
у вас есть следующий понедельник.

144
00:06:41,230 --> 00:06:42,855
Да, я не знаю, о том, что среднесрочный.

145
00:06:42,855 --> 00:06:45,630
Так что я собираюсь быть, что ТА
что напоминает вам все, что викторину

146
00:06:45,630 --> 00:06:47,270
0-- потому что, вы знаете, мы CS.

147
00:06:47,270 --> 00:06:50,730
Теперь, когда мы сделали массивы, вы получите
почему это викторина 0, не викторины 1, а?

148
00:06:50,730 --> 00:06:51,320
ХОРОШО.

149
00:06:51,320 --> 00:06:52,490
О, я получил некоторые смешки на том, что один.

150
00:06:52,490 --> 00:06:53,120
ХОРОШО.

151
00:06:53,120 --> 00:06:59,710
>> Так викторины 0 будет 14 октября, если
Вы находитесь в разделе понедельник-среду

152
00:06:59,710 --> 00:07:02,920
и 15 октября, если вы находитесь в
раздел вторник-четверг.

153
00:07:02,920 --> 00:07:05,630
Это не распространяется на
тех из вас, в Гарварде

154
00:07:05,630 --> 00:07:10,350
who-- Я думаю, вы все будете
принимать ваши опросы на 14-м.

155
00:07:10,350 --> 00:07:13,560
>> Так что, да, на следующей неделе, если
Дэвид, в лекции, идет,

156
00:07:13,560 --> 00:07:15,747
да, так об этом
Тест на следующей неделе, вы все

157
00:07:15,747 --> 00:07:17,580
не будут шокированы, потому что
вы пришли в разделе

158
00:07:17,580 --> 00:07:19,664
и вы знаете, что ваш
Тест 0 в течение двух недель.

159
00:07:19,664 --> 00:07:21,580
И мы будем иметь отзыв
сессий и все.

160
00:07:21,580 --> 00:07:26,360
Так что не беспокойтесь о
бояться за это.

161
00:07:26,360 --> 00:07:29,890
Любые вопросы before-- какие-либо вопросы
на всех касающимся технических вопросов,

162
00:07:29,890 --> 00:07:32,591
классификации, офисная часов, секции?

163
00:07:32,591 --> 00:07:33,090
Да.

164
00:07:33,090 --> 00:07:35,100
>> АУДИТОРИЯ: Так викторины
будет на лекции?

165
00:07:35,100 --> 00:07:35,766
>> ANDI Пэн: Да.

166
00:07:35,766 --> 00:07:39,460
Так викторины, я думаю, 60
минут, выделенные в этом временном интервале

167
00:07:39,460 --> 00:07:42,240
что вы будете просто взять
в лекционном зале.

168
00:07:42,240 --> 00:07:44,810
Таким образом, вы не должны прийти в
на, вроде бы, случайного 7:00 PM.

169
00:07:44,810 --> 00:07:46,140
Все хорошо.

170
00:07:46,140 --> 00:07:47,100
Да.

171
00:07:47,100 --> 00:07:50,060
Круто.

172
00:07:50,060 --> 00:07:50,840
>> Все в порядке.

173
00:07:50,840 --> 00:07:54,330
Итак, мы собираемся, чтобы
ввести понятие для вас

174
00:07:54,330 --> 00:08:00,760
На этой неделе, что Дэвид уже вроде
из затронули в лекции на прошлой неделе.

175
00:08:00,760 --> 00:08:02,010
Это называется GDB.

176
00:08:02,010 --> 00:08:05,570
И, как многие из вас, в то время как в
курс написания psets,

177
00:08:05,570 --> 00:08:09,981
заметил большую кнопку, которая говорит
"Отладка" на верхней части IDE?

178
00:08:09,981 --> 00:08:10,480
ХОРОШО.

179
00:08:10,480 --> 00:08:13,770
Так что теперь мы на самом деле получить, чтобы раскопать
тайна какой то кнопки на самом деле

180
00:08:13,770 --> 00:08:14,270
делает.

181
00:08:14,270 --> 00:08:16,790
И я гарантирую вам, что это
красивая, красивая вещь.

182
00:08:16,790 --> 00:08:20,740
>> Так до сих пор, я думаю,
там было две вещи

183
00:08:20,740 --> 00:08:23,320
студенты были, как правило,
делать при отладке psets.

184
00:08:23,320 --> 00:08:27,635
Один из них, они либо добавить в
Е () - так каждые несколько линий,

185
00:08:27,635 --> 00:08:29,760
они добавляют в Е () -
ой, что это переменная?

186
00:08:29,760 --> 00:08:32,551
О, что это переменная now--
и вы вроде увидеть прогрессирование

187
00:08:32,551 --> 00:08:33,940
ваш код, как это работает.

188
00:08:33,940 --> 00:08:37,030
Или второй способ сделать детей
что они просто написать целую вещь

189
00:08:37,030 --> 00:08:38,610
а затем перейти, как это в конце концов.

190
00:08:38,610 --> 00:08:39,970
Надеюсь, это работает.

191
00:08:39,970 --> 00:08:44,851
Я гарантирую вам, GDB лучше
чем оба из этих методов.

192
00:08:44,851 --> 00:08:45,350
Да.

193
00:08:45,350 --> 00:08:46,980
Так что это будет ваш новый лучший друг.

194
00:08:46,980 --> 00:08:51,780
Потому что это красивая вещь
которые визуально отображает как

195
00:08:51,780 --> 00:08:54,850
что ваш код делает
в определенный момент

196
00:08:54,850 --> 00:08:57,486
а также то, что все ваши
переменные проведения,

197
00:08:57,486 --> 00:08:59,610
как то, что их значения,
в этой конкретной точке.

198
00:08:59,610 --> 00:09:02,670
И таким образом, вы можете действительно
установить точки останова в коде.

199
00:09:02,670 --> 00:09:04,350
Вы можете запустить через линию за линией.

200
00:09:04,350 --> 00:09:07,324
И GDB будет просто для
Вы, отображается для вас,

201
00:09:07,324 --> 00:09:09,490
то, что все ваши переменные
которые, что они делают,

202
00:09:09,490 --> 00:09:10,656
что происходит в коде.

203
00:09:10,656 --> 00:09:13,240
И таким образом, это
так легче увидеть

204
00:09:13,240 --> 00:09:17,120
что вместо происходит из-тов PRINTF
или записывая свои заявления.

205
00:09:17,120 --> 00:09:19,160
>> Таким образом, мы будем делать пример этом позже.

206
00:09:19,160 --> 00:09:20,660
Таким образом, это кажется немного абстрактным.

207
00:09:20,660 --> 00:09:23,490
Не беспокойтесь, мы не будем делать примеры.

208
00:09:23,490 --> 00:09:29,170
И так, по существу, три крупнейших,
Наиболее используемые функции вам нужно в GDB

209
00:09:29,170 --> 00:09:32,500
являются Далее, перешагнуть
и шаг в кнопки.

210
00:09:32,500 --> 00:09:34,860
Я собираюсь возглавить
есть, на самом деле, прямо сейчас.

211
00:09:34,860 --> 00:09:40,930
>> Так может вы, ребята, все видеть, что
или я должен увеличить немного?

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
В спину, вы можете видеть, что?

214
00:09:44,470 --> 00:09:45,730
Должен ли я увеличить?

215
00:09:45,730 --> 00:09:46,480
Только немного?

216
00:09:46,480 --> 00:09:49,390
Ладно, круто.

217
00:09:49,390 --> 00:09:50,280
Там мы идем.

218
00:09:50,280 --> 00:09:50,960
ХОРОШО.

219
00:09:50,960 --> 00:09:57,000
>> Так что я, вот, моя
Реализация для жадный.

220
00:09:57,000 --> 00:10:01,430
И в то время как многие из вас, ребята писали
жадные в то время как петли form--, что

221
00:10:01,430 --> 00:10:04,890
это вполне приемлемо способ сделать
it-- другой способ сделать это, чтобы просто

222
00:10:04,890 --> 00:10:06,280
разделить на модулю.

223
00:10:06,280 --> 00:10:09,290
Потому что тогда вы можете иметь свой
значение, а затем иметь свой остаток.

224
00:10:09,290 --> 00:10:11,150
И тогда вы можете просто
добавить все это вместе.

225
00:10:11,150 --> 00:10:13,390
Ли логика, что я делаю
здесь смысл для всех,

226
00:10:13,390 --> 00:10:14,117
прежде чем мы начнем?

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
Вид?

229
00:10:17,980 --> 00:10:18,710
Круто.

230
00:10:18,710 --> 00:10:19,210
Отлично.

231
00:10:19,210 --> 00:10:21,290
Это довольно сексуальная часть
кода, я бы сказал.

232
00:10:21,290 --> 00:10:23,502
Как я уже сказал, Давид, в
лекции, через некоторое время,

233
00:10:23,502 --> 00:10:25,960
вы все начинаете видеть код
как что-то, что красиво.

234
00:10:25,960 --> 00:10:29,950
И иногда, когда вы видите красивый
Код, это такой замечательный ощущение.

235
00:10:29,950 --> 00:10:35,410
>> Так, однако, в то время как этот код очень
красиво, это не работает должным образом.

236
00:10:35,410 --> 00:10:37,750
Так что давайте работать check50 на этом.

237
00:10:37,750 --> 00:10:39,440
Проверьте 50 20-- уп.

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2?

240
00:10:43,720 --> 00:10:44,990
Это pset2?

241
00:10:44,990 --> 00:10:46,870
Да.

242
00:10:46,870 --> 00:10:47,520
О, pset1.

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
ХОРОШО.

245
00:10:52,890 --> 00:10:53,900
Таким образом, мы работать check50.

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> И, как вы, ребята, можете посмотреть здесь,
это неспособность пару случаев.

248
00:11:07,170 --> 00:11:10,165
И для некоторых из вас, в
Конечно делать свои проблемные наборы,

249
00:11:10,165 --> 00:11:11,110
вы, как, ах, почему оно не работает.

250
00:11:11,110 --> 00:11:13,318
Почему это работает для некоторых
значения, но не для других?

251
00:11:13,318 --> 00:11:17,760
Ну, GDB будет помочь вам понять
почему эти входы не работали.

252
00:11:17,760 --> 00:11:18,320
>> ХОРОШО.

253
00:11:18,320 --> 00:11:21,640
Итак, давайте посмотрим, одно из
проверяет меня неудачу в check50

254
00:11:21,640 --> 00:11:24,920
был входное значение 0,41.

255
00:11:24,920 --> 00:11:27,830
Таким образом, правильный ответ, что
вы должны получать это 4.

256
00:11:27,830 --> 00:11:33,090
Но вместо того, что я распечатки
это 3-н, что неверно.

257
00:11:33,090 --> 00:11:36,190
Так что давайте просто запустить вручную, просто
убедитесь, что check50 работает.

258
00:11:36,190 --> 00:11:36,940
Давайте сделаем ./greedy.

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
Ой, я должен сделать жадный.

261
00:11:43,340 --> 00:11:43,840
Там мы идем.

262
00:11:43,840 --> 00:11:44,381
Теперь ./greedy.

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> Сколько причитается?

265
00:11:47,670 --> 00:11:49,550
Давайте сделаем 0.41.

266
00:11:49,550 --> 00:11:52,590
И да, мы видим здесь
что это вывод 3

267
00:11:52,590 --> 00:11:55,160
когда правильный ответ,
В самом деле, должно быть 4.

268
00:11:55,160 --> 00:12:01,460
Так что давайте ввести GDB и посмотреть, как мы
может идти о фиксации этой проблемы.

269
00:12:01,460 --> 00:12:03,992
>> Итак, первый шаг в
всегда отладки кода

270
00:12:03,992 --> 00:12:05,950
это установить точку останова,
или точка, в которой вы

271
00:12:05,950 --> 00:12:09,079
хочу компьютера или
отладчик, чтобы начать смотреть.

272
00:12:09,079 --> 00:12:11,120
Так что, если вы действительно не
знаю, что ваша проблема,

273
00:12:11,120 --> 00:12:14,670
Обычно, типичный, что мы хотим, чтобы
сделать, это установить точку останова на наш основной.

274
00:12:14,670 --> 00:12:18,520
Так что, если вы, ребята, можете видеть это
красная кнопка рядом,

275
00:12:18,520 --> 00:12:22,860
Да, это было мне установив
останова для главной функции.

276
00:12:22,860 --> 00:12:24,130
Я нажмите что.

277
00:12:24,130 --> 00:12:26,130
>> И тогда я могу пойти к моей кнопки Debug.

278
00:12:26,130 --> 00:12:27,036
Я ударил эту кнопку.

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
Позвольте мне отдалиться, если я могу.

281
00:12:36,555 --> 00:12:38,020
Там мы идем.

282
00:12:38,020 --> 00:12:40,730
Таким образом, мы имеем здесь, панель справа.

283
00:12:40,730 --> 00:12:43,680
Я извиняюсь, ребята в спину, вы
не могу видеть очень хорошо.

284
00:12:43,680 --> 00:12:49,090
Но по сути, все
это право панель делает

285
00:12:49,090 --> 00:12:53,130
является отслеживание и выделенный
линия, которая является строка кода

286
00:12:53,130 --> 00:12:56,640
что компьютер в данный момент,
а также все ваши переменные

287
00:12:56,640 --> 00:12:57,600
здесь.

288
00:12:57,600 --> 00:13:00,487
>> Итак, вы получили центов, монеты, п,
объявлены на разные вещи

289
00:13:00,487 --> 00:13:01,070
в этот момент.

290
00:13:01,070 --> 00:13:04,850
Не беспокойтесь, потому что у нас нет на самом деле не
инициализации их к любым переменным еще.

291
00:13:04,850 --> 00:13:07,200
Таким образом, в вашем компьютере, ваш
Компьютер просто видя,

292
00:13:07,200 --> 00:13:14,376
ой, 32767 был последний используемая функция
этого пространства памяти в моем компьютере.

293
00:13:14,376 --> 00:13:16,000
И так вот где центов в настоящее время.

294
00:13:16,000 --> 00:13:19,360
Но ни что когда-то вы не запустите код,
она должна стать инициализации.

295
00:13:19,360 --> 00:13:24,110
>> Так давайте пройдем, линию
линия, то, что здесь происходит.

296
00:13:24,110 --> 00:13:25,350
ХОРОШО.

297
00:13:25,350 --> 00:13:29,400
Так здесь являются три
кнопки, которые я только что объяснил.

298
00:13:29,400 --> 00:13:34,090
Вы должны играть, или функцию Run,
Кнопка, у вас есть Шаг за кнопку,

299
00:13:34,090 --> 00:13:36,600
и у вас также есть Шаг в кнопки.

300
00:13:36,600 --> 00:13:41,260
И, по существу, все три
им просто пройти через код

301
00:13:41,260 --> 00:13:42,690
и делать разные вещи.

302
00:13:42,690 --> 00:13:45,680
>> Так обычно, когда вы отладки,
мы не хотим, чтобы просто нажать Play,

303
00:13:45,680 --> 00:13:47,930
потому Игра будет просто запустить
код к концу этого.

304
00:13:47,930 --> 00:13:49,070
И тогда у вас не будет на самом деле
знаю, что ваша проблема

305
00:13:49,070 --> 00:13:51,432
есть, если вы не установите несколько точек останова.

306
00:13:51,432 --> 00:13:53,890
Если вы установите несколько точек останова,
это будет просто автоматически

307
00:13:53,890 --> 00:13:56,030
бежать от одной точки останова,
к другому, чтобы в следующий.

308
00:13:56,030 --> 00:13:58,030
Но в этом случае мы в
только, что один, потому что мы

309
00:13:58,030 --> 00:13:59,970
хочу работать наш путь
сверху вниз вниз.

310
00:13:59,970 --> 00:14:04,830
Итак, мы собираемся, чтобы игнорировать эту кнопку
сейчас для целей этой программы.

311
00:14:04,830 --> 00:14:08,230
>> Так Шаг над функцией только
переступает каждой строки

312
00:14:08,230 --> 00:14:11,510
и говорит вам, что
компьютер делает.

313
00:14:11,510 --> 00:14:14,630
Шаг в функции идет
в реальной функции

314
00:14:14,630 --> 00:14:16,000
это на строке кода.

315
00:14:16,000 --> 00:14:19,070
Так, например, как Е (),
, которая является функцией, верно?

316
00:14:19,070 --> 00:14:21,980
Если бы я хотел, чтобы физически шаг
в функции Е (),

317
00:14:21,980 --> 00:14:25,610
Я бы на самом деле идти в части
Код, где Е () была написана и посмотреть,

318
00:14:25,610 --> 00:14:26,730
что там происходит.

319
00:14:26,730 --> 00:14:29,924
>> Но, как правило, мы предполагаем, что
код, который мы даем вам работы.

320
00:14:29,924 --> 00:14:31,340
Мы предполагаем, что Е () работает.

321
00:14:31,340 --> 00:14:33,170
Мы предполагаем, что GetInt () работает.

322
00:14:33,170 --> 00:14:35,170
Таким образом, нет никакой необходимости
шаг в этих функций.

323
00:14:35,170 --> 00:14:37,170
Но если есть функции
что вы пишете сами

324
00:14:37,170 --> 00:14:39,060
что вы хотите, чтобы проверить
, что происходит,

325
00:14:39,060 --> 00:14:41,200
Вы хотели бы шаг
в этой функции.

326
00:14:41,200 --> 00:14:43,940
>> Так что сейчас мы только собираемся
перешагнуть этот кусок кода.

327
00:14:43,940 --> 00:14:44,485
Итак, давайте посмотрим.

328
00:14:44,485 --> 00:14:46,547
О, печать, "О Хай, как
много изменений причитается? "

329
00:14:46,547 --> 00:14:47,130
Мы не волнует.

330
00:14:47,130 --> 00:14:49,830
Мы знаем, что работает,
таким образом, мы шаг за нее.

331
00:14:49,830 --> 00:14:53,290
>> Так п, которая является нашим поплавок, что
мы в initialized-- или declared--

332
00:14:53,290 --> 00:14:56,810
наверху, мы теперь
равная, что GetFloat ().

333
00:14:56,810 --> 00:14:57,810
Итак, давайте перешагнуть что.

334
00:14:57,810 --> 00:14:59,580
И мы видим, на
Нижняя здесь, программа

335
00:14:59,580 --> 00:15:03,360
побуждает меня к входу значение.

336
00:15:03,360 --> 00:15:08,580
Итак, давайте Введите значение мы хотим
проверить здесь, что 0,41.

337
00:15:08,580 --> 00:15:09,160
Отлично.

338
00:15:09,160 --> 00:15:12,780
>> Так что теперь N-- вы, ребята, видите
здесь, на bottom-- это

339
00:15:12,780 --> 00:15:15,140
stored--, потому что мы
еще не округляется, это

340
00:15:15,140 --> 00:15:19,540
хранятся в этом, как гигант
поплавок, который 0,4099999996,

341
00:15:19,540 --> 00:15:22,550
который находится достаточно близко к нашему
Цели, прямо сейчас, до 0,41.

342
00:15:22,550 --> 00:15:26,090
И тогда мы увидим в дальнейшем, как мы
продолжать продвижение по программе,

343
00:15:26,090 --> 00:15:29,850
После здесь, н стало
округлые и центов стала 41.

344
00:15:29,850 --> 00:15:30,350
Отлично.

345
00:15:30,350 --> 00:15:32,230
Итак, мы знаем, что работа нашей округления в.

346
00:15:32,230 --> 00:15:34,700
Мы знаем, что у нас есть
правильное число центов,

347
00:15:34,700 --> 00:15:36,990
так что мы знаем, что это
на самом деле не проблема.

348
00:15:36,990 --> 00:15:40,050
>> Таким образом, мы по-прежнему шагать
в этой программе.

349
00:15:40,050 --> 00:15:40,900
Мы идем сюда.

350
00:15:40,900 --> 00:15:46,139
И так после этой строки кода, мы
должны знать, сколько четверти у нас есть.

351
00:15:46,139 --> 00:15:46,680
Мы перешагнуть.

352
00:15:46,680 --> 00:15:52,040
И вы видите, мы, на самом деле, есть один
четверть, потому что мы вычитали 25

353
00:15:52,040 --> 00:15:53,790
из нашего начального значения 41.

354
00:15:53,790 --> 00:15:55,890
И у нас есть 16 остается нашим центов.

355
00:15:55,890 --> 00:15:58,830
>> Понимает ли все, как
программа пошагового

356
00:15:58,830 --> 00:16:02,980
и почему центов стала 16
и почему, в настоящее время, монеты стал 1?

357
00:16:02,980 --> 00:16:04,610
Все следующее, что логика?

358
00:16:04,610 --> 00:16:05,110
Круто.

359
00:16:05,110 --> 00:16:07,860
Так, как в данный момент,
Рабочая программа, верно?

360
00:16:07,860 --> 00:16:09,797
Мы знаем, что это именно делать
то, что мы хотим.

361
00:16:09,797 --> 00:16:11,880
И мы на самом деле не
должны распечатать, ах, какой

362
00:16:11,880 --> 00:16:14,430
является центов на данный момент,
что монеты в этой точке.

363
00:16:14,430 --> 00:16:17,170
>> Мы продолжаем идти по программе.

364
00:16:17,170 --> 00:16:18,100
Переступить.

365
00:16:18,100 --> 00:16:18,620
Круто.

366
00:16:18,620 --> 00:16:19,700
Мы идем по десять центов.

367
00:16:19,700 --> 00:16:20,200
Отлично.

368
00:16:20,200 --> 00:16:22,367
Мы видим, что это заняло
от $ 0.10 за копейки.

369
00:16:22,367 --> 00:16:23,450
И теперь у нас есть две монеты.

370
00:16:23,450 --> 00:16:25,260
Правильно.

371
00:16:25,260 --> 00:16:31,555
>> Перейдем гроши, и мы видим
что мы получили, оставшиеся центов.

372
00:16:31,555 --> 00:16:32,680
Хм, это странно.

373
00:16:32,680 --> 00:16:37,540
До здесь программы, я должен был
чтобы вычли мои гроши.

374
00:16:37,540 --> 00:16:39,400
Может быть, я просто не был
делает эту строку право.

375
00:16:39,400 --> 00:16:42,190
И, увы, вы можете увидеть
здесь, потому что мы знаем,

376
00:16:42,190 --> 00:16:44,360
что мы вступаем
через линии 32 и 33,

377
00:16:44,360 --> 00:16:50,560
вот где наша программа
неправильно было переменные работать.

378
00:16:50,560 --> 00:16:55,136
Таким образом, мы можем посмотреть и увидеть, о,
Я вычитания центов здесь,

379
00:16:55,136 --> 00:16:57,010
но я на самом деле не
добавляя к моей стоимости монеты.

380
00:16:57,010 --> 00:16:57,860
Я добавляю к центов.

381
00:16:57,860 --> 00:17:00,234
И я не хочу, чтобы добавить к
центов, я хочу, чтобы добавить к монетам.

382
00:17:00,234 --> 00:17:05,420
Так что, если мы меняем что монеты,
мы получили рабочую программу.

383
00:17:05,420 --> 00:17:06,730
Я могу запустить check50.

384
00:17:06,730 --> 00:17:11,063
Вы можете просто выйти из GDB права
здесь и затем запустить check50 снова.

385
00:17:11,063 --> 00:17:11,938
Я мог бы просто сделать это.

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
Я должен сделать жадный.

388
00:17:18,480 --> 00:17:19,940
0,41.

389
00:17:19,940 --> 00:17:22,819
И вот, это печать
из правильного ответа.

390
00:17:22,819 --> 00:17:26,569
>> Итак, как вы, ребята, можете видеть, GDB
это действительно мощный инструмент

391
00:17:26,569 --> 00:17:29,940
когда у нас так много кода
происходит, и так много переменных

392
00:17:29,940 --> 00:17:32,510
что это трудно для нас, как
человеку, чтобы отслеживать.

393
00:17:32,510 --> 00:17:35,360
Компьютер, в GDB
отладчик, имеет возможность

394
00:17:35,360 --> 00:17:37,020
чтобы отслеживать все.

395
00:17:37,020 --> 00:17:40,480
Я знаю, в Visionaire, вы, ребята, вероятно,
возможно, попали некоторые ошибки сегментации

396
00:17:40,480 --> 00:17:43,150
потому что вы бежали
вне границ вашего массива.

397
00:17:43,150 --> 00:17:46,510
В примере Цезаря, это
именно то, что я здесь реализована.

398
00:17:46,510 --> 00:17:50,060
>> Так что я забыл, чтобы проверить
что бы произошло, если бы я

399
00:17:50,060 --> 00:17:52,510
не имеют два аргумента командной строки.

400
00:17:52,510 --> 00:17:53,880
Я просто не ставили в этом чеке.

401
00:17:53,880 --> 00:17:57,380
И поэтому, если я бегу Debug-- я поставил
мой останова направо там.

402
00:17:57,380 --> 00:17:58,055
Я бегу Debug.

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> ХОРОШО.

405
00:18:16,550 --> 00:18:17,050
Да.

406
00:18:17,050 --> 00:18:20,350
Так на самом деле, GDB должен был
, что сказал мне, что

407
00:18:20,350 --> 00:18:22,300
был сбой сегментации там.

408
00:18:22,300 --> 00:18:24,883
Я не знаю, что происходит
тут, но, когда я побежал,

409
00:18:24,883 --> 00:18:25,590
она работает.

410
00:18:25,590 --> 00:18:29,410
При запуске строк кода через и
GDB может просто внезапно бросить на вас,

411
00:18:29,410 --> 00:18:31,540
идти и смотреть то, что красный ошибка.

412
00:18:31,540 --> 00:18:33,930
Это вам скажу, эй, ты
была ошибку сегментации,

413
00:18:33,930 --> 00:18:38,550
Это означает, что вы пытались получить доступ
пространство в массиве, что не существует.

414
00:18:38,550 --> 00:18:39,050
Да.

415
00:18:39,050 --> 00:18:43,280
>> Таким образом, в следующей проблеме
установленные на этой неделе, вы, ребята,

416
00:18:43,280 --> 00:18:45,600
вероятно, будет много
переменные с плавающей вокруг.

417
00:18:45,600 --> 00:18:48,560
Вы не собираетесь быть уверены, что
Все они имеют в виду в определенный момент.

418
00:18:48,560 --> 00:18:53,560
Так GDB действительно поможет вам в выясняя
то, что они все сравнявшись

419
00:18:53,560 --> 00:18:55,940
и быть в состоянии видеть, что визуально.

420
00:18:55,940 --> 00:19:01,995
Кто путать от того, как
либо из этого работал?

421
00:19:01,995 --> 00:19:02,495
Круто.

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
Все в порядке.

424
00:19:10,620 --> 00:19:14,260
Таким образом, после того, что мы
собирается погрузиться

425
00:19:14,260 --> 00:19:17,562
в четыре различных
типы сортов на этой неделе.

426
00:19:17,562 --> 00:19:19,520
Как многие из вас, прежде
всего, прежде чем мы начнем,

427
00:19:19,520 --> 00:19:23,020
прочитал всю спецификацию для pset3?

428
00:19:23,020 --> 00:19:23,824
ХОРОШО.

429
00:19:23,824 --> 00:19:24,740
Я горжусь вами, ребята.

430
00:19:24,740 --> 00:19:29,110
Вот как половина класса, который
значительно больше, чем в прошлый раз.

431
00:19:29,110 --> 00:19:33,950
>> Так что здорово, потому что, когда
мы говорим о содержании

432
00:19:33,950 --> 00:19:36,170
в lecture-- или извините,
в section-- Мне нравится

433
00:19:36,170 --> 00:19:38,210
связать много, что
назад к тому, что это PSET

434
00:19:38,210 --> 00:19:40,210
и как вы хотите, чтобы
осуществить, что в вашем PSET.

435
00:19:40,210 --> 00:19:42,400
Так что, если вы приходите, имеющих
читать спецификации, он будет

436
00:19:42,400 --> 00:19:45,510
будет намного проще для вас, чтобы понять,
то, что я говорю о том, когда я говорю,

437
00:19:45,510 --> 00:19:48,720
эй, это может быть действительно
хорошее место для реализации такого рода.

438
00:19:48,720 --> 00:19:52,870
Так что те, из вас, кто читал
особое_разрешение знаю, что, как часть вашего PSET,

439
00:19:52,870 --> 00:19:54,900
Вы будете иметь, чтобы
написать тип рода.

440
00:19:54,900 --> 00:19:58,670
Так что это может быть очень полезно
для многих из вас сегодня.

441
00:19:58,670 --> 00:20:01,760
>> Таким образом, мы начнем с того,
по сути, самый простой тип

442
00:20:01,760 --> 00:20:04,580
из рода, выбор рода.

443
00:20:04,580 --> 00:20:06,800
Типичный алгоритм
как мы идти об этом

444
00:20:06,800 --> 00:20:10,460
is-- Давид через них все в
лекция, так что я буду быстро двигаться вдоль

445
00:20:10,460 --> 00:20:13,900
here-- существу, вы
есть массив значений.

446
00:20:13,900 --> 00:20:17,170
И тогда вы найдете
маленький несортированный значение

447
00:20:17,170 --> 00:20:20,200
и вы поменять это значение с
первый несортированный значение.

448
00:20:20,200 --> 00:20:22,700
А потом вы просто повторять
с остальной части списка.

449
00:20:22,700 --> 00:20:25,740
>> И вот наглядное объяснение
о том, как это будет работать.

450
00:20:25,740 --> 00:20:30,460
Так, например, если мы должны были начать
с массивом из пяти элементов, индекс

451
00:20:30,460 --> 00:20:35,910
От 0 до 4, с 3, 5, 2, 6, и 4 значения
помещен в array-- это прямо сейчас,

452
00:20:35,910 --> 00:20:38,530
мы просто будем считать,
что они все без сортировки

453
00:20:38,530 --> 00:20:41,130
потому что мы не испытали в противном случае.

454
00:20:41,130 --> 00:20:44,130
>> Так как выбор рода будет
работа, что бы прежде

455
00:20:44,130 --> 00:20:46,800
проходят через полностью
в несортированных массива.

456
00:20:46,800 --> 00:20:49,120
Было бы выбрать наименьшее значение.

457
00:20:49,120 --> 00:20:51,750
В этом случае, 3, правый
Теперь, является наименьшим.

458
00:20:51,750 --> 00:20:52,680
Он получает до 5.

459
00:20:52,680 --> 00:20:55,620
Нет, 5 не больше than--
или извините, не менее 3 than--.

460
00:20:55,620 --> 00:20:57,779
Таким образом, минимальное значение по-прежнему 3.

461
00:20:57,779 --> 00:20:58,695
И тогда вы получите 2.

462
00:20:58,695 --> 00:21:00,990
Компьютер видит, ой, 2 меньше, чем 3.

463
00:21:00,990 --> 00:21:02,750
Теперь 2 должно быть минимальное значение.

464
00:21:02,750 --> 00:21:06,630
И так 2 свопы с этой первой величины.

465
00:21:06,630 --> 00:21:10,702
>> Таким образом, после одного прохода, мы действительно видим
что 2 и 3 меняются местами.

466
00:21:10,702 --> 00:21:13,910
И мы только собираемся продолжать делать
Это снова с остальной частью массива.

467
00:21:13,910 --> 00:21:17,660
Итак, мы собираемся, чтобы просто запустить через
Последние четыре индексы массива.

468
00:21:17,660 --> 00:21:20,670
Мы увидим, что 3
следующий минимальное значение.

469
00:21:20,670 --> 00:21:23,240
Итак, мы собираемся, чтобы поменять что с 4.

470
00:21:23,240 --> 00:21:26,900
И тогда мы просто будем продолжать
не проходит через до, в конце концов, вы

471
00:21:26,900 --> 00:21:33,730
попасть в отсортированном массиве, в котором
2, 3, 4, 5, 6 и все сортируются.

472
00:21:33,730 --> 00:21:37,530
Все понимают ли логику
о том, как работает выбор рода?

473
00:21:37,530 --> 00:21:39,669
>> Вы просто есть какой-то
минимального значения.

474
00:21:39,669 --> 00:21:41,210
Вы отслеживать, что это такое.

475
00:21:41,210 --> 00:21:45,170
И всякий раз, когда вы найдете его, вы поменять его
с первым значением в array--

476
00:21:45,170 --> 00:21:48,740
или, не первый value--
следующее значение в массиве.

477
00:21:48,740 --> 00:21:50,150
Круто.

478
00:21:50,150 --> 00:21:55,460
>> Итак, как вы, ребята, вроде
видел из мельком,

479
00:21:55,460 --> 00:21:58,450
мы собираемся псевдокод это.

480
00:21:58,450 --> 00:22:02,510
Так что, если вы, ребята, в задней хотите
образуют группу, каждый в таблице

481
00:22:02,510 --> 00:22:06,170
могут образовывать мало партнера, я собираюсь
чтобы дать вам, ребята, как три минуты

482
00:22:06,170 --> 00:22:08,190
просто говорить через
логика, на английском языке,

483
00:22:08,190 --> 00:22:14,161
о том, как мы могли бы реализовать
псевдокод написать выбора рода.

484
00:22:14,161 --> 00:22:14,910
И есть конфеты.

485
00:22:14,910 --> 00:22:16,118
Пожалуйста, приходите и получите конфету.

486
00:22:16,118 --> 00:22:19,520
Если вы находитесь в спине и вы хотите
конфеты, я могу бросить конфеты на вас.

487
00:22:19,520 --> 00:22:22,850
На самом деле, сделать you-- прохладно.

488
00:22:22,850 --> 00:22:23,552
Ой, извини.

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
ХОРОШО.

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> Так что, если мы хотели бы, а
класс, записи псевдокод

493
00:25:27,140 --> 00:25:30,466
о том, как можно было бы подойти
эта проблема, просто не стесняйтесь.

494
00:25:30,466 --> 00:25:32,340
Я просто ходить, а
в порядке, спросите группы

495
00:25:32,340 --> 00:25:35,065
на следующей строке
что мы должны делать.

496
00:25:35,065 --> 00:25:37,840
Так что, если вы, ребята, хотите, чтобы начать
выключен, то, что первое, что

497
00:25:37,840 --> 00:25:40,600
делать, когда вы пытаетесь
осуществить способ решить эту программу

498
00:25:40,600 --> 00:25:43,480
выборочно отсортировать список?

499
00:25:43,480 --> 00:25:46,349
Давайте предположим, что мы только что
есть массив, ладно?

500
00:25:46,349 --> 00:25:49,088
>> АУДИТОРИЯ: Вы хотите, чтобы создать некоторые
рода [неразборчиво], что вы

501
00:25:49,088 --> 00:25:50,420
проходит через весь массиве.

502
00:25:50,420 --> 00:25:51,128
>> ANDI Пэн: Право.

503
00:25:51,128 --> 00:25:54,100
Таким образом, вы будете хотеть, чтобы итерации
через каждый пространства, правильно?

504
00:25:54,100 --> 00:26:05,490
Так здорово.

505
00:26:05,490 --> 00:26:08,600
Если вы, ребята, хотите, чтобы дать мне
Следующий line-- да, в спину.

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> АУДИТОРИЯ: Проверьте их
все для самых маленьких.

508
00:26:13,290 --> 00:26:14,248
>> ANDI Пэн: Там мы идем.

509
00:26:14,248 --> 00:26:17,438
Поэтому мы хотим, чтобы пройти и проверить
видеть, что минимальное значение, верно?

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
Я собираюсь сокращать, что "мин."

512
00:26:24,840 --> 00:26:27,658
Что вы, ребята, хотите делать после
Вы нашли минимальное значение?

513
00:26:27,658 --> 00:26:28,533
>> АУДИТОРИЯ: [неразборчиво]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI Пэн: Так что вы собираетесь хотят
переключить его с первого этом массиве,

516
00:26:33,150 --> 00:26:33,650
правильно?

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
Это начало, я собираюсь сказать.

519
00:26:46,850 --> 00:26:47,220
Все в порядке.

520
00:26:47,220 --> 00:26:50,386
Так что теперь вы поменялись первым
Один из них, что вы хотите сделать после этого?

521
00:26:50,386 --> 00:26:54,840
Так что теперь мы знаем, что это одно здесь
должны быть наименьшее значение, не так ли?

522
00:26:54,840 --> 00:26:58,310
Тогда у вас есть дополнительный отдых
массива, что это несортированный.

523
00:26:58,310 --> 00:27:01,569
Так что вы хотите сделать здесь, если вы
ребята, хотите, чтобы дать мне следующую строку?

524
00:27:01,569 --> 00:27:04,610
АУДИТОРИЯ: Итак вы хотите перебрать
через оставшуюся часть массива.

525
00:27:04,610 --> 00:27:05,276
ANDI Пэн: Да.

526
00:27:05,276 --> 00:27:09,857
И так, что же переборе
вид подразумевает мы, наверное, нужно?

527
00:27:09,857 --> 00:27:10,440
Какой тип--

528
00:27:10,440 --> 00:27:12,057
>> АУДИТОРИЯ: О, дополнительная переменная?

529
00:27:12,057 --> 00:27:13,890
ANDI Пэн: Возможно
другой цикл, не так ли?

530
00:27:13,890 --> 00:27:28,914
Таким образом, мы, вероятно, захотят
для перебора through-- здорово.

531
00:27:28,914 --> 00:27:31,830
И тогда вы будете идти назад и
вероятно, проверить минимум раз

532
00:27:31,830 --> 00:27:32,100
правильно?

533
00:27:32,100 --> 00:27:34,975
И вы собираетесь повторять
это, потому что петли только собирается

534
00:27:34,975 --> 00:27:36,010
держать работает, верно?

535
00:27:36,010 --> 00:27:39,190
>> Итак, как вы, ребята, можете видеть, мы
просто общий псевдокод

536
00:27:39,190 --> 00:27:41,480
о том, как мы хотим, чтобы эта программа смотреть.

537
00:27:41,480 --> 00:27:46,646
Это итерация здесь, то, что мы
как правило, нужно написать в коде

538
00:27:46,646 --> 00:27:49,270
если мы хотим, чтобы итерации через
Массив, какой тип структуры?

539
00:27:49,270 --> 00:27:51,030
Я думаю, Кристабель
уже говорил это раньше.

540
00:27:51,030 --> 00:27:51,500
>> Зала: для петли.

541
00:27:51,500 --> 00:27:52,160
>> ANDI Пэн: для цикла?

542
00:27:52,160 --> 00:27:52,770
В точку.

543
00:27:52,770 --> 00:27:56,060
Так это, наверное,
будет цикл.

544
00:27:56,060 --> 00:27:59,240
Что такое проверка здесь собирается значит?

545
00:27:59,240 --> 00:28:02,536
Как правило, если вы хотите, чтобы проверить
если что-то что-то else--

546
00:28:02,536 --> 00:28:03,270
>> АУДИТОРИЯ: Если.

547
00:28:03,270 --> 00:28:06,790
>> ANDI PENG: если, верно?

548
00:28:06,790 --> 00:28:10,790
А потом своп здесь, мы будем
перейти позже, потому что Давида

549
00:28:10,790 --> 00:28:12,770
прошел через это в лекции, а также.

550
00:28:12,770 --> 00:28:14,580
А потом второй итерации implies--

551
00:28:14,580 --> 00:28:15,120
>> АУДИТОРИЯ: Еще цикл.

552
00:28:15,120 --> 00:28:16,745
>> ANDI Пэн: --another цикл, точно.

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
Так что, если мы ищем
на это правильно, мы

555
00:28:22,000 --> 00:28:24,680
можно увидеть, что мы, вероятно,
понадобится вложенный цикл

556
00:28:24,680 --> 00:28:28,330
с условным заявлением в там
а затем фактическое кусок кода, который это

557
00:28:28,330 --> 00:28:31,360
собирается поменять значения.

558
00:28:31,360 --> 00:28:35,980
Так что я просто вообще написано
псевдокод код здесь.

559
00:28:35,980 --> 00:28:38,910
И тогда мы на самом деле происходит
физически, как класс,

560
00:28:38,910 --> 00:28:40,700
попытаться осуществить это сегодня.

561
00:28:40,700 --> 00:28:42,486
Давайте вернемся в этот IDE.

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> Ой-ой.

564
00:28:50,230 --> 00:28:51,754
Почему это не-- там.

565
00:28:51,754 --> 00:28:52,253
ХОРОШО.

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
Извините, позвольте мне попытаться увеличить немного больше.

568
00:28:57,500 --> 00:28:59,310
Там мы идем.

569
00:28:59,310 --> 00:29:05,060
Все, что я делаю здесь, я создал
Программа называется "выбор / sort.c."

570
00:29:05,060 --> 00:29:10,860
Я создал массив из девяти
Значения, 4, 8, 2, 1, 6, 9, 7, 5, 3.

571
00:29:10,860 --> 00:29:14,370
В настоящее время, как вы можете
Понимаете, они не упорядочены.

572
00:29:14,370 --> 00:29:17,880
н будет число,
говорит вам сумму значений

573
00:29:17,880 --> 00:29:18,920
у вас есть в вашем массиве.

574
00:29:18,920 --> 00:29:20,670
В этом случае, у нас есть девять значений.

575
00:29:20,670 --> 00:29:23,760
И я только что получил цикл здесь
что выводит несортированный массив.

576
00:29:23,760 --> 00:29:28,370
>> И в конце концов, я также получил для
цикл, который печатает его снова.

577
00:29:28,370 --> 00:29:32,070
Так, теоретически, если эта программа
работает правильно, в конце концов,

578
00:29:32,070 --> 00:29:35,670
Вы должны увидеть печатный цикл
в котором 1, 2, 3, 4, 5, 6, 7, 8,

579
00:29:35,670 --> 00:29:39,310
9 все правильно в порядке.

580
00:29:39,310 --> 00:29:43,410
>> Таким образом, мы получили наш псевдокод здесь.

581
00:29:43,410 --> 00:29:46,090
Кто-нибудь хочет, целью которых я просто
пойду просить volunteers--

582
00:29:46,090 --> 00:29:49,540
скажите мне точно, что если ввести
мы хотим, чтобы, во-первых, просто итерации

583
00:29:49,540 --> 00:29:52,840
по начало этого массива?

584
00:29:52,840 --> 00:29:55,204
Что строка кода я
вероятно, здесь нужно?

585
00:29:55,204 --> 00:29:56,990
>> АУДИТОРИЯ: [неразборчиво]

586
00:29:56,990 --> 00:29:59,010
>> ANDI Пэн: Да, чувствую,
бесплатно, целью которых извините, вам

587
00:29:59,010 --> 00:30:02,318
не должны стоять up-- чувство
свободно поднять свой голос немного.

588
00:30:02,318 --> 00:30:08,190
>> АУДИТОРИЯ: Для INT я равна 0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI Пэн: Да, хорошо.

590
00:30:10,690 --> 00:30:15,220
>> АУДИТОРИЯ: я меньше длины массива.

591
00:30:15,220 --> 00:30:19,630
>> ANDI Пэн: Так что имейте в
против здесь, потому что мы

592
00:30:19,630 --> 00:30:23,060
не есть функция, которая
говорит нам длина массива,

593
00:30:23,060 --> 00:30:25,790
у нас уже есть
Значение, которое хранит, что.

594
00:30:25,790 --> 00:30:27,920
Правильно?

595
00:30:27,920 --> 00:30:31,010
Еще одна вещь, чтобы держать
в mind-- в массиве

596
00:30:31,010 --> 00:30:33,940
из девяти значений, какие индексы?

597
00:30:33,940 --> 00:30:38,720
Давайте просто скажем, этот массив 0 до 3.

598
00:30:38,720 --> 00:30:41,500
Вы видите, что последний
Индекс самом деле 3.

599
00:30:41,500 --> 00:30:45,530
Это не 4, хотя есть
четыре значения в массиве.

600
00:30:45,530 --> 00:30:49,866
>> Так здесь, мы должны быть очень осторожны,
того, что наше условие для длины

601
00:30:49,866 --> 00:30:50,490
будет.

602
00:30:50,490 --> 00:30:51,948
>> АУДИТОРИЯ: не было бы н минус 1?

603
00:30:51,948 --> 00:30:54,440
ANDI Пэн: Это происходит
п минус 1, точно.

604
00:30:54,440 --> 00:30:57,379
Имеет ли это смысл, почему
это п минус 1, все?

605
00:30:57,379 --> 00:30:58,920
Это потому, что массивы равны нулю, индексированные.

606
00:30:58,920 --> 00:31:02,010
Они начинаются с 0 и запустить до н минус 1.

607
00:31:02,010 --> 00:31:03,210
Да, это немного сложнее.

608
00:31:03,210 --> 00:31:03,730
ХОРОШО.

609
00:31:03,730 --> 00:31:05,929
А потом--

610
00:31:05,929 --> 00:31:08,054
АУДИТОРИЯ: Isnt'1, что
уже позаботились, хотя,

611
00:31:08,054 --> 00:31:11,400
, просто не говорю "меньше или
равно "и просто говорю" менее "?

612
00:31:11,400 --> 00:31:13,108
>> ANDI Пэн: Это
очень хороший вопрос.

613
00:31:13,108 --> 00:31:13,630
Так да.

614
00:31:13,630 --> 00:31:17,410
Но также, таким образом, что мы
реализации проверки право,

615
00:31:17,410 --> 00:31:19,120
вам нужно сравнить два значения.

616
00:31:19,120 --> 00:31:21,009
Таким образом, вы на самом деле хотите, чтобы
оставить "на" пустой.

617
00:31:21,009 --> 00:31:23,050
Потому что, если вы сравните
это одно, вы не собираетесь

618
00:31:23,050 --> 00:31:25,530
есть что-нибудь после него
сравнить, правда?

619
00:31:25,530 --> 00:31:27,460
Да.

620
00:31:27,460 --> 00:31:29,297
Так я ++.

621
00:31:29,297 --> 00:31:30,380
Давайте добавим наши скобки в.

622
00:31:30,380 --> 00:31:30,880
Упс.

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
Отлично.

625
00:31:34,710 --> 00:31:39,117
Таким образом, мы имеем начало
нашей внешней петли.

626
00:31:39,117 --> 00:31:41,450
Так что теперь мы, вероятно, хотите, чтобы
создать переменную для хранения

627
00:31:41,450 --> 00:31:43,085
трек наименьшим значением, верно?

628
00:31:43,085 --> 00:31:45,751
Кто-нибудь хочет, чтобы дать мне
строка кода, которая будет это делать?

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
Что нам нужно, если мы собираемся
хотят, чтобы сохранить что-нибудь?

631
00:31:53,570 --> 00:31:55,047
>> Правильно.

632
00:31:55,047 --> 00:31:57,630
Может быть, лучше, что название
будет be-- "Темп" полностью works--

633
00:31:57,630 --> 00:32:00,655
может быть, более метко назвал бы,
если мы хотим, чтобы маленький value--

634
00:32:00,655 --> 00:32:01,624
>> АУДИТОРИЯ: Мин.

635
00:32:01,624 --> 00:32:02,790
ANDI Пэн: мин, там мы идем.

636
00:32:02,790 --> 00:32:05,230
мин будет хорошо.

637
00:32:05,230 --> 00:32:08,340
И вот что нам делать
хочу, чтобы инициализировать его?

638
00:32:08,340 --> 00:32:09,620
Это немного сложнее.

639
00:32:09,620 --> 00:32:13,580
Потому что сейчас на
начало этого массива,

640
00:32:13,580 --> 00:32:15,730
Вы еще не смотрели ни на что, не так ли?

641
00:32:15,730 --> 00:32:19,200
Так что, автоматически, если
мы только на я равна 0,

642
00:32:19,200 --> 00:32:22,302
то, что мы хотим, чтобы инициализировать
наш первый минимальное значение для?

643
00:32:22,302 --> 00:32:22,802
АУДИТОРИЯ: я.

644
00:32:22,802 --> 00:32:24,790
ANDI Пэн: я, точно.

645
00:32:24,790 --> 00:32:27,040
Christabel, почему мы хотим
инициализировать его я?

646
00:32:27,040 --> 00:32:28,510
>> АУДИТОРИЯ: Потому что, ну,
мы, начиная с 0.

647
00:32:28,510 --> 00:32:31,660
Так, потому что мы не имеем ничего, чтобы сравнить
это, минимум будет в конечном итоге 0.

648
00:32:31,660 --> 00:32:32,451
>> ANDI Пэн: Точно.

649
00:32:32,451 --> 00:32:34,400
Таким образом, она совершенно точно.

650
00:32:34,400 --> 00:32:36,780
Потому что у нас на самом деле не
посмотрел на что-нибудь еще,

651
00:32:36,780 --> 00:32:38,680
мы не знаем, что наша минимальное значение.

652
00:32:38,680 --> 00:32:41,960
Мы хотим, чтобы просто инициализировать его
я, что, в настоящее время, прямо здесь.

653
00:32:41,960 --> 00:32:44,750
И, как мы по-прежнему
двигаться вниз этот массив,

654
00:32:44,750 --> 00:32:48,122
мы увидим, что, друг с
Дополнительный проход, я увеличивает.

655
00:32:48,122 --> 00:32:49,830
И так в этой точке,
я, вероятно, будет

656
00:32:49,830 --> 00:32:52,329
хотят быть минимальным,
потому что это будет что угодно

657
00:32:52,329 --> 00:32:54,520
начало неотсортированной массива.

658
00:32:54,520 --> 00:32:55,270
Круто.

659
00:32:55,270 --> 00:32:58,720
>> Так что теперь мы хотим, чтобы добавить
для цикла здесь это

660
00:32:58,720 --> 00:33:03,225
собирается повторять через
несортированный или остальная часть этого массива.

661
00:33:03,225 --> 00:33:05,808
Кто-нибудь хочет, чтобы дать мне
строка кода, которая будет это делать?

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint-- что нам нужно здесь?

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
Что собирается идти в этом для цикла?

666
00:33:18,820 --> 00:33:19,465
Да.

667
00:33:19,465 --> 00:33:21,590
АУДИТОРИЯ: Таким образом, мы хотели бы
иметь различный число,

668
00:33:21,590 --> 00:33:25,080
потому что мы бежим до конца
массива вместо I, так что, возможно

669
00:33:25,080 --> 00:33:25,760
J.

670
00:33:25,760 --> 00:33:27,301
>> ANDI Пэн: Да, J звучит хорошо для меня.

671
00:33:27,301 --> 00:33:27,850
Равно?

672
00:33:27,850 --> 00:33:33,930
>> АУДИТОРИЯ: Так бы я плюс 1, потому что
Вы начинаете на следующей значения.

673
00:33:33,930 --> 00:33:40,395
А потом к end-- так снова, J является
меньше, чем п минус 1, а затем J ++.

674
00:33:40,395 --> 00:33:41,103
ANDI Пэн: Отлично.

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> А потом здесь, мы собираемся хотите
чтобы проверить, если наше условие выполняется,

677
00:33:52,750 --> 00:33:53,250
правильно?

678
00:33:53,250 --> 00:33:55,740
Потому что вы хотите, чтобы
изменить минимальное значение

679
00:33:55,740 --> 00:33:58,700
если это на самом деле меньше, чем
вы сравниваете его, верно?

680
00:33:58,700 --> 00:34:01,146
Так что мы собираемся хотите здесь?

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
Проверьте, чтобы видеть.

683
00:34:04,897 --> 00:34:06,730
Какой вид заявления
мы, вероятно, будет

684
00:34:06,730 --> 00:34:08,389
ти хотите использовать, если мы
хочу кое-что проверить?

685
00:34:08,389 --> 00:34:09,360
>> АУДИТОРИЯ: если заявление.

686
00:34:09,360 --> 00:34:10,485
>> ANDI PENG: если заявление.

687
00:34:10,485 --> 00:34:13,155
Так if-- и то, что будет
условие, что мы хотим в

688
00:34:13,155 --> 00:34:13,988
нашей, если заявление?

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> АУДИТОРИЯ: Если значение J
меньше, чем значение i--

691
00:34:22,960 --> 00:34:24,600
>> ANDI Пэн: Точно.

692
00:34:24,600 --> 00:34:27,480
Так if-- так что это массив называется "массив".

693
00:34:27,480 --> 00:34:27,980
Отлично.

694
00:34:27,980 --> 00:34:30,465
Так что, если array-- что это было?

695
00:34:30,465 --> 00:34:31,090
Повтори.

696
00:34:31,090 --> 00:34:39,590
>> АУДИТОРИЯ: Если массив-J меньше
Массив-я, то мы бы изменить мин.

697
00:34:39,590 --> 00:34:41,590
Таким образом, мин будет к.

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI Пэн: Имеет ли это смысл?

700
00:34:47,249 --> 00:34:48,670
ХОРОШО.

701
00:34:48,670 --> 00:34:52,929
А теперь сюда, мы на самом деле
хотим реализовать обмен, верно?

702
00:34:52,929 --> 00:34:58,285
Так Напомним, что в лекции, что Давид, когда
он пытался обменять the--, что было

703
00:34:58,285 --> 00:34:59,996
it-- апельсиновый сок и milk--

704
00:34:59,996 --> 00:35:01,150
>> АУДИТОРИЯ: Это было отвратительно.

705
00:35:01,150 --> 00:35:02,816
>> ANDI Пэн: Да, это было своего рода брутто.

706
00:35:02,816 --> 00:35:05,310
Но это было довольно хорошо
Концепция демонстрации время.

707
00:35:05,310 --> 00:35:08,430
Так что думайте о ваших ценностей здесь.

708
00:35:08,430 --> 00:35:10,794
Вы получили массив
из мин, массив I,

709
00:35:10,794 --> 00:35:12,460
или то, что мы пытались поменять здесь.

710
00:35:12,460 --> 00:35:15,310
И вы, вероятно, не может залить их в
друг с другом, в то же время, так?

711
00:35:15,310 --> 00:35:17,180
Так что мы собираемся
чтобы нужно создать здесь

712
00:35:17,180 --> 00:35:19,126
для того, чтобы правильно поменять значения?

713
00:35:19,126 --> 00:35:19,820
>> АУДИТОРИЯ: временная переменная.

714
00:35:19,820 --> 00:35:21,370
>> ANDI Пэн: временная переменная.

715
00:35:21,370 --> 00:35:22,570
Так давайте сделаем Int темп.

716
00:35:22,570 --> 00:35:25,681
Смотри, это было бы лучше
Время, целью которых эй, что это было?

717
00:35:25,681 --> 00:35:26,180
ХОРОШО.

718
00:35:26,180 --> 00:35:29,800
Так что это было бы лучше
время назвать переменную "Темп".

719
00:35:29,800 --> 00:35:30,730
Так давайте сделаем Int темп.

720
00:35:30,730 --> 00:35:32,563
Что мы собираемся
SET TEMP равную здесь?

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
АУДИТОРИЯ: Мин?

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI Пэн: Это немного сложнее.

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
Это на самом деле не имеет значения, в конце концов.

727
00:35:44,880 --> 00:35:47,690
Это не имеет значения, что
заказ вы решите поменять в

728
00:35:47,690 --> 00:35:50,862
так долго, как вы делаете, что вы
отслеживать то, что вы подкачки.

729
00:35:50,862 --> 00:35:52,250
>> АУДИТОРИЯ: Это может быть массив я.

730
00:35:52,250 --> 00:35:53,666
>> ANDI Пэн: Да, давайте сделаем массив-I.

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
И тогда то, что следующая строка
кода мы хотим иметь здесь?

733
00:35:59,305 --> 00:36:00,680
АУДИТОРИЯ: массив я равна массива-J.

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI Пэн: И, наконец?

736
00:36:08,070 --> 00:36:12,070
АУДИТОРИЯ: массив J равна массива я.

737
00:36:12,070 --> 00:36:14,525
АУДИТОРИЯ: Или массива J равно
Массив-temp-- или температуры.

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI Пэн: ОК.

740
00:36:19,430 --> 00:36:21,510
Так что давайте работать и посмотрим,
если он будет работать.

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
Где, что происходит?

743
00:36:39,335 --> 00:36:40,210
О, что это проблема.

744
00:36:40,210 --> 00:36:44,320
Смотри, на линии 40, мы
пытается использовать массив-J?

745
00:36:44,320 --> 00:36:47,022
Но где J существует только в?

746
00:36:47,022 --> 00:36:48,402
>> АУДИТОРИЯ: В течение цикла.

747
00:36:48,402 --> 00:36:49,110
ANDI Пэн: Право.

748
00:36:49,110 --> 00:36:51,730
Так что мы собираемся нужно сделать?

749
00:36:51,730 --> 00:36:53,170
>> АУДИТОРИЯ: Определить его пределами the--

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
АУДИТОРИЯ: Да, я думаю, вы должны
использовать другой, если заявление, не так ли?

752
00:37:00,610 --> 00:37:05,230
Так как, если minimum--
Все в порядке, дайте мне подумать.

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI Пэн: Ребята, попробуйте
взглянуть Давайте

755
00:37:09,990 --> 00:37:11,270
см, что это то, что мы можем сделать здесь?

756
00:37:11,270 --> 00:37:11,811
>> АУДИТОРИЯ: ОК.

757
00:37:11,811 --> 00:37:15,900
Таким образом, если минимальная не равна
j-- так что если минимальная еще i--

758
00:37:15,900 --> 00:37:17,570
то мы бы не поменять.

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI Пэн: Значит ли это, равно я?

761
00:37:24,712 --> 00:37:25,920
Что вы хотите сказать здесь?

762
00:37:25,920 --> 00:37:30,494
>> АУДИТОРИЯ: Или да, если
минимум не равное I, да.

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI Пэн: ОК.

765
00:37:40,210 --> 00:37:42,040
Ну, что решает, вроде, наши проблемы.

766
00:37:42,040 --> 00:37:47,265
Но это еще не решить
Проблема что произойдет, если j-- так J

767
00:37:47,265 --> 00:37:49,890
не существует вне его, то, что
Вы хотите, чтобы мы с ним делать?

768
00:37:49,890 --> 00:37:50,698
Объявить его пределами?

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
Давайте попробуем это работает.

771
00:38:02,730 --> 00:38:04,435
Ой-ой.

772
00:38:04,435 --> 00:38:06,200
Наша рода не работает.

773
00:38:06,200 --> 00:38:10,060
>> Как вы можете видеть, нашу начальную
Массив были те значения.

774
00:38:10,060 --> 00:38:14,800
И после этого он должен иметь
был в 1, 2, 3, 4, 5, 6, 7, 8, 9.

775
00:38:14,800 --> 00:38:15,530
Это не работает.

776
00:38:15,530 --> 00:38:16,030
Ах.

777
00:38:16,030 --> 00:38:17,184
Что мы делаем?

778
00:38:17,184 --> 00:38:17,850
АУДИТОРИЯ: Отладка.

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI Пэн: Ладно, мы можем попробовать.

781
00:38:23,370 --> 00:38:25,030
Мы можем отладить.

782
00:38:25,030 --> 00:38:26,042
Осмотрите немного.

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
Давайте установим нашу точку останова.

785
00:38:33,656 --> 00:38:37,280
Давайте like-- OK.

786
00:38:37,280 --> 00:38:40,444
>> Так, потому что мы уже знаем, что
эти линии, 15 через 22,

787
00:38:40,444 --> 00:38:43,610
которые working--, потому что все, что я делаю
просто перебирая и printing--

788
00:38:43,610 --> 00:38:45,406
Я могу идти вперед и пропустить это.

789
00:38:45,406 --> 00:38:47,280
Давайте начнем с линии 25.

790
00:38:47,280 --> 00:38:48,712
ООП позвольте мне избавиться от этого.

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> АУДИТОРИЯ: Так точки останова
где начинается отладка?

793
00:38:54,057 --> 00:38:54,890
ANDI Пэн: Или остановок.

794
00:38:54,890 --> 00:38:55,670
АУДИТОРИЯ: Или остановок.

795
00:38:55,670 --> 00:38:55,930
ANDI Пэн: Да.

796
00:38:55,930 --> 00:38:58,640
Вы можете установить точки останова и несколько
он может просто прыгать от одного к другому.

797
00:38:58,640 --> 00:39:01,590
Но в этом случае мы не знаем,
где ошибка происходит.

798
00:39:01,590 --> 00:39:03,780
Таким образом, мы просто хотим
начать сверху вниз.

799
00:39:03,780 --> 00:39:05,020
Ага.

800
00:39:05,020 --> 00:39:05,550
ХОРОШО.

801
00:39:05,550 --> 00:39:08,460
>> Так эта линия здесь, мы можем вмешаться.

802
00:39:08,460 --> 00:39:11,499
Вы можете увидеть здесь,
мы получили массив.

803
00:39:11,499 --> 00:39:13,290
Те значения
что в массиве.

804
00:39:13,290 --> 00:39:16,360
Вы видите, что, как индекс 0,
соответствует value-- о,

805
00:39:16,360 --> 00:39:17,526
Я собираюсь попробовать, чтобы увеличить.

806
00:39:17,526 --> 00:39:20,650
К сожалению, это действительно трудно
чтобы see-- по индексу массива 0,

807
00:39:20,650 --> 00:39:24,090
мы имеем значение 4 и
Затем так далее, и так далее.

808
00:39:24,090 --> 00:39:25,670
У нас есть локальные переменные.

809
00:39:25,670 --> 00:39:28,570
Сейчас я равна
0, что мы хотим, чтобы это было.

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> И так давайте держать пошаговое.

812
00:39:33,690 --> 00:39:36,850
Наш минимальный равен 0,
которые мы также хотим, чтобы это было.

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
И тогда мы входим наш второй для
цикл, если массив J меньше, чем массив-I,

815
00:39:45,560 --> 00:39:46,380
который его не было.

816
00:39:46,380 --> 00:39:48,130
Так же вы видите, как
что пропустил что?

817
00:39:48,130 --> 00:39:52,430
>> АУДИТОРИЯ: так должно, если
Минимальный все that-- не следует, что

818
00:39:52,430 --> 00:39:55,424
быть внутри первым цикл?

819
00:39:55,424 --> 00:39:57,340
ANDI Пэн: Нет, потому что
Вы все еще хотите, чтобы проверить.

820
00:39:57,340 --> 00:40:00,329
Вы хотите, чтобы сделать сравнение каждый
Время, даже после запуска через него.

821
00:40:00,329 --> 00:40:02,620
Вы не просто хотите, чтобы сделать это
на первом проход.

822
00:40:02,620 --> 00:40:05,240
Вы хотите, чтобы сделать это с
каждый проход снова.

823
00:40:05,240 --> 00:40:07,198
Итак, вы хотите, чтобы проверить
Ваше состояние внутри.

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
Таким образом, мы только собираемся
держать работает через здесь.

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
Я дам вам подсказку парням.

828
00:40:18,420 --> 00:40:23,910
Это связано с тем, что при
Вы проверяете ваш условный,

829
00:40:23,910 --> 00:40:26,600
Вы не проверяя
для правильного индекса.

830
00:40:26,600 --> 00:40:32,510
Так что сейчас вы проверка
Индекс массива J меньше, чем массив

831
00:40:32,510 --> 00:40:33,970
Индекс I.

832
00:40:33,970 --> 00:40:36,580
Но то, что ты делаешь на
начало для цикла?

833
00:40:36,580 --> 00:40:38,260
Вы не установив J, равный I?

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> Да, так что мы на самом деле можем
выйти из отладчика здесь.

836
00:40:45,415 --> 00:40:47,040
Итак, давайте взглянем на нашем псевдокоде.

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For-- мы собираемся
начать в я равна 0.

839
00:40:52,580 --> 00:40:54,760
Мы собираемся идти до н минус 1.

840
00:40:54,760 --> 00:40:58,040
Давайте проверим, мы имели это право?

841
00:40:58,040 --> 00:40:59,580
Да, это было в порядке.

842
00:40:59,580 --> 00:41:02,080
>> Итак внутри здесь, мы
создадим минимальное значение

843
00:41:02,080 --> 00:41:03,630
и установить, что в I равны.

844
00:41:03,630 --> 00:41:04,950
Разве мы это делаем?

845
00:41:04,950 --> 00:41:06,270
Да, это сделал.

846
00:41:06,270 --> 00:41:10,430
В настоящее время в нашей внутренней петли для, мы
собирается делать J равна я в п минус 1.

847
00:41:10,430 --> 00:41:11,950
Разве мы это делаем?

848
00:41:11,950 --> 00:41:15,540
В самом деле, мы сделали это.

849
00:41:15,540 --> 00:41:19,922
>> Так, однако, что мы здесь сравнения?

850
00:41:19,922 --> 00:41:20,925
>> АУДИТОРИЯ: J + 1.

851
00:41:20,925 --> 00:41:21,716
ANDI Пэн: Точно.

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
И тогда вы будете хотеть, чтобы установить
минимальная равна J плюс 1, а.

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
Так что я прошел через это очень быстро.

856
00:41:32,640 --> 00:41:36,190
Как вы, ребята понимают
почему это J + 1?

857
00:41:36,190 --> 00:41:36,890
ХОРОШО.

858
00:41:36,890 --> 00:41:40,700
>> Таким образом, в вашем массиве, в
Ваш первый проход через,

859
00:41:40,700 --> 00:41:44,850
Ваш цикл, для Int
я равна 0, давайте просто

860
00:41:44,850 --> 00:41:46,740
предположить, что это не была изменена еще.

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
У нас есть массив, полностью,
всего четыре несортированные элементы, верно?

863
00:41:56,760 --> 00:42:00,760
Поэтому мы хотим, чтобы инициализировать я равняться 0.

864
00:42:00,760 --> 00:42:03,650
И я намерен просто
проходят через эту петлю.

865
00:42:03,650 --> 00:42:08,560
И поэтому в первом проходе, мы собираемся
инициализировать переменную "мин"

866
00:42:08,560 --> 00:42:11,245
что также равно I, потому что
мы не иметь минимальное значение.

867
00:42:11,245 --> 00:42:12,870
Так вот в настоящее время равен 0, а также.

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
И тогда мы будем идти до конца.

870
00:42:17,640 --> 00:42:19,270
И мы хотим, чтобы итерации снова.

871
00:42:19,270 --> 00:42:22,900
Теперь, когда мы нашли, что наш минимальный
есть, мы хотим, чтобы перебора

872
00:42:22,900 --> 00:42:25,190
снова, чтобы увидеть, если это сравнение, не так ли?

873
00:42:25,190 --> 00:42:40,440
Так J, вот, идет
на равное I, который является 0.

874
00:42:40,440 --> 00:42:46,320
И потом, если массив J плюс я, что
это тот, который дальше снова, как менее

875
00:42:46,320 --> 00:42:49,270
чем то, что ваш текущий минимум
значение, вы хотите поменять местами.

876
00:42:49,270 --> 00:42:56,850
>> Так что давайте просто сказать, что мы
получил, как, 2, 5, 1, 8.

877
00:42:56,850 --> 00:43:01,610
Прямо сейчас, я равна
0 и J равен 0.

878
00:43:01,610 --> 00:43:05,210
И это наша минимальное значение.

879
00:43:05,210 --> 00:43:09,950
Если массив-J плюс i-- так что если один
это после того, что мы, глядя на

880
00:43:09,950 --> 00:43:13,450
больше, чем один перед этим,
это станет минимум.

881
00:43:13,450 --> 00:43:18,120
>> Так вот, мы видим, что 5
не меньше, чем.

882
00:43:18,120 --> 00:43:19,730
Так это будет, чтобы не быть 5.

883
00:43:19,730 --> 00:43:23,580
Мы видим, что 1 меньше, чем 2, не так ли?

884
00:43:23,580 --> 00:43:32,970
Итак, теперь мы знаем, что наша минимум
будет значение индекса на 0, 1, 2.

885
00:43:32,970 --> 00:43:34,030
Да?

886
00:43:34,030 --> 00:43:39,170
А потом, когда вы получаете здесь,
Вы можете поменять правильные значения.

887
00:43:39,170 --> 00:43:42,610
>> Так что, когда вы, ребята, просто имея J
раньше, вы не глядя на то

888
00:43:42,610 --> 00:43:43,260
после этого.

889
00:43:43,260 --> 00:43:44,520
Вы искали на
то же самое значение, что

890
00:43:44,520 --> 00:43:46,290
Поэтому он просто ничего не делал.

891
00:43:46,290 --> 00:43:49,721
Имеет ли это смысл для всех,
Поэтому нам нужно что плюс 1 там?

892
00:43:49,721 --> 00:43:50,220
ХОРОШО.

893
00:43:50,220 --> 00:43:53,345
Теперь давайте просто запустить через него, чтобы сделать
что остальная часть кода является правильным.

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
Почему, что случилось?

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
Ах, это мин прямо здесь.

898
00:44:16,364 --> 00:44:17,780
Мы сравнивали неверное значение.

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
О нет.

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> Ах да, здесь мы были
обмен неправильные значения, а также.

903
00:44:33,482 --> 00:44:34,940
Потому что мы искали в I и J.

904
00:44:34,940 --> 00:44:36,440
Те, кого мы проверяли.

905
00:44:36,440 --> 00:44:39,160
Мы на самом деле хотим, чтобы поменять местами
Минимальный ток минимум,

906
00:44:39,160 --> 00:44:40,550
с тем, что один снаружи.

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
И, как вы, ребята, можете увидеть вниз
здесь, у нас есть отсортированный массив.

909
00:45:05,402 --> 00:45:07,110
Это просто было сделать с
тот факт, что, когда

910
00:45:07,110 --> 00:45:09,350
мы проверяли
Значения, которые мы сравнивали,

911
00:45:09,350 --> 00:45:11,226
мы не смотрели на правильные значения.

912
00:45:11,226 --> 00:45:13,850
Мы искали в том же самом
здесь, на самом деле не его замены.

913
00:45:13,850 --> 00:45:17,135
Вы должны смотреть на один следующий
к нему, а затем вы можете поменять.

914
00:45:17,135 --> 00:45:19,260
Так вот то, что было своего рода
прослушивание наш код, прежде чем.

915
00:45:19,260 --> 00:45:22,460
И то, что я сделал здесь есть все,
отладчик мог бы сделать для вас

916
00:45:22,460 --> 00:45:23,810
Я просто сделал это на
доска, потому что это легче

917
00:45:23,810 --> 00:45:26,320
чтобы увидеть, а не пытаться
для увеличения масштаба отладчика.

918
00:45:26,320 --> 00:45:29,391
Имеет ли это смысл для всех?

919
00:45:29,391 --> 00:45:29,890
Круто.

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> Все в порядке.

922
00:45:35,410 --> 00:45:41,070
Мы можем двигаться дальше к разговору о
асимптотическая обозначения, которые

923
00:45:41,070 --> 00:45:44,580
это просто фантазии способ сказать
выполнения всех этих видов.

924
00:45:44,580 --> 00:45:47,650
Так что я знаю Дэвида, в лекции,
коснулся автономной работы.

925
00:45:47,650 --> 00:45:52,124
И он пошел через весь формуле
о том, как рассчитать время автономной работы.

926
00:45:52,124 --> 00:45:53,040
Не беспокойтесь об этом.

927
00:45:53,040 --> 00:45:54,660
Если вы действительно любопытно
о том, как это работает,

928
00:45:54,660 --> 00:45:55,810
не стесняйтесь говорить со мной после раздела.

929
00:45:55,810 --> 00:45:57,560
Мы можем пройти через
формулы вместе.

930
00:45:57,560 --> 00:46:00,689
Но все вы, ребята, должны действительно
знаю, что п в квадрате более 2

931
00:46:00,689 --> 00:46:01,980
это то же самое, как н в квадрате.

932
00:46:01,980 --> 00:46:04,710
Потому что наибольший номер,
показатель растет больше всего.

933
00:46:04,710 --> 00:46:06,590
И так для наших целей,
Все мы заботимся о

934
00:46:06,590 --> 00:46:09,470
является то, что гигантский номер, который растет.

935
00:46:09,470 --> 00:46:13,340
>> Так что в лучшем случае
выполнения отборочного рода?

936
00:46:13,340 --> 00:46:15,830
Если вы собираетесь иметь
для перебора списка

937
00:46:15,830 --> 00:46:18,712
а затем перебора
остальные этого списка,

938
00:46:18,712 --> 00:46:20,420
сколько раз
Вы собираетесь вероятно,

939
00:46:20,420 --> 00:46:24,612
в худшем case-- в
лучшем случае, sorry-- запустить через?

940
00:46:24,612 --> 00:46:27,070
Может быть, лучше спросить
чтобы спросить, что это худший случай

941
00:46:27,070 --> 00:46:28,153
выполнения отборочного рода.

942
00:46:28,153 --> 00:46:29,366
АУДИТОРИЯ: п в квадрате.

943
00:46:29,366 --> 00:46:30,740
ANDI Пэн: Это н квадрат, правильно.

944
00:46:30,740 --> 00:46:36,986
Так простой способ думать об этом, как,
в любое время у вас есть два вложенных циклов для,

945
00:46:36,986 --> 00:46:38,110
это будет н в квадрате.

946
00:46:38,110 --> 00:46:40,386
Потому что не только ты
проходящей через раз,

947
00:46:40,386 --> 00:46:42,260
у вас есть, чтобы вернуться
и бежать через него

948
00:46:42,260 --> 00:46:44,980
снова внутри для каждого значения.

949
00:46:44,980 --> 00:46:48,640
Таким образом, в этом случае, вы работаете п
раз н квадрат, который is-- извините,

950
00:46:48,640 --> 00:46:50,505
п раз п, равен п в квадрате.

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> И вроде тоже немного
уникальным в том смысле

953
00:46:56,360 --> 00:46:59,774
что это не имеет значения, если эти
Значения уже в порядке.

954
00:46:59,774 --> 00:47:01,440
Он по-прежнему собирается запустить через любом случае.

955
00:47:01,440 --> 00:47:03,872
Давайте просто сказать, что это был 1, 2, 3, 4.

956
00:47:03,872 --> 00:47:07,080
Независимо от того, является ли он в
порядок, это все равно бы пробежал

957
00:47:07,080 --> 00:47:08,620
и до сих пор проверяется минимальное значение.

958
00:47:08,620 --> 00:47:10,100
Это сделало бы
такое же количество проверок

959
00:47:10,100 --> 00:47:12,780
каждый раз, даже если он
на самом деле не трогать.

960
00:47:12,780 --> 00:47:16,940
>> Таким образом, в таком случае, лучшим и худшим
Время автономной работы фактически эквивалентны.

961
00:47:16,940 --> 00:47:19,160
Таким образом, ожидаемый выполнения
селекционного сорта,

962
00:47:19,160 --> 00:47:23,790
которые мы обозначаем символом
тета, тета, в данном случае,

963
00:47:23,790 --> 00:47:24,790
Также будет н квадрат.

964
00:47:24,790 --> 00:47:26,480
Все эти три будет н квадрат.

965
00:47:26,480 --> 00:47:29,653
Это все понятно, почему
среда выполнения п квадрате?

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> Все в порядке.

968
00:47:33,980 --> 00:47:39,120
Так что я просто хочу, чтобы быстро бежать
через остальную часть сортов.

969
00:47:39,120 --> 00:47:41,137
Алгоритм
пузырь sort-- помните,

970
00:47:41,137 --> 00:47:43,220
это было первым
Дэвид подошел в лекции.

971
00:47:43,220 --> 00:47:46,000
По сути, вы шаг
через весь список

972
00:47:46,000 --> 00:47:48,950
и вы swap-- вас всего
Сравнение двух одновременно.

973
00:47:48,950 --> 00:47:51,350
И если это больше,
чем вы просто поменять их местами.

974
00:47:51,350 --> 00:47:53,590
Так что, если это больше, вы бы поменять.

975
00:47:53,590 --> 00:47:56,180
Я получил официальное право здесь.

976
00:47:56,180 --> 00:47:59,100
>> Так что давайте просто сказать, что вы были 8, 6, 4, 2.

977
00:47:59,100 --> 00:48:00,571
Вы бы сравнить 8 и 6.

978
00:48:00,571 --> 00:48:01,570
Вы должны были бы поменять их местами.

979
00:48:01,570 --> 00:48:02,610
Вы бы сравнить 8 и 4.

980
00:48:02,610 --> 00:48:03,609
Вы должны были бы поменять их местами.

981
00:48:03,609 --> 00:48:07,000
Если у вас есть, чтобы поменять 8 и
2, изменить их.

982
00:48:07,000 --> 00:48:10,760
Таким образом, в таком смысле, вы можете видеть,
сыграна в течение длительного периода времени,

983
00:48:10,760 --> 00:48:13,730
как значения рода пузырь
концы, который является, почему мы называем его

984
00:48:13,730 --> 00:48:15,320
пузырьковая сортировка.

985
00:48:15,320 --> 00:48:19,950
>> Мы просто запустить через раз на
наш второй проход, и наш третий проход,

986
00:48:19,950 --> 00:48:21,150
и наш четвертый проход.

987
00:48:21,150 --> 00:48:25,820
По сути, пузырьковая сортировка работает только
до тех пор, пока не делают никаких больше свопы.

988
00:48:25,820 --> 00:48:31,109
Так что в этом смысле, это просто
общая псевдокод для него.

989
00:48:31,109 --> 00:48:32,650
Не беспокойтесь, это не все будет на сайте.

990
00:48:32,650 --> 00:48:34,990
Мы не должны на самом деле пойти по этому поводу.

991
00:48:34,990 --> 00:48:38,134
>> Мы просто инициализировать счетчик
переменная, которая начинается с 0.

992
00:48:38,134 --> 00:48:39,800
И мы перебора всего массива.

993
00:48:39,800 --> 00:48:43,420
И если одно значение, если это is--
значение больше, чем данное значение,

994
00:48:43,420 --> 00:48:44,610
Вы собираетесь поменять их местами.

995
00:48:44,610 --> 00:48:46,860
И тогда ты просто
продолжать идти.

996
00:48:46,860 --> 00:48:47,970
И вы собираетесь рассчитывать.

997
00:48:47,970 --> 00:48:50,845
И вы только собираетесь продолжать делать
это в то время счетчик больше

998
00:48:50,845 --> 00:48:53,345
чем 0, что означает, что
каждый раз, когда у вас есть, чтобы поменять,

999
00:48:53,345 --> 00:48:55,220
Вы знаете, вы хотите пойти
назад и еще раз проверить.

1000
00:48:55,220 --> 00:48:59,510
Вы хотите, чтобы держать проверку, пока вы не знаете,
что вы не должны поменять больше.

1001
00:48:59,510 --> 00:49:05,570
>> Так что самый лучший и худший
Дело среда выполнения для пузырьковой сортировки?

1002
00:49:05,570 --> 00:49:09,300
И hint-- это на самом деле отличается
от выбора вида в смысле

1003
00:49:09,300 --> 00:49:11,810
что эти два ответы не совпадают.

1004
00:49:11,810 --> 00:49:14,709
Подумайте о том, что будет происходить в
случай, если он был уже отсортирован.

1005
00:49:14,709 --> 00:49:16,500
И думать о том,
что произойдет, если он был

1006
00:49:16,500 --> 00:49:18,372
в случае, в котором он не был отсортирован.

1007
00:49:18,372 --> 00:49:20,580
И вы можете запустить вид
через что, почему происходит.

1008
00:49:20,580 --> 00:49:22,954
Я дам вам, ребята, как, 30
секунд, чтобы думать об этом.

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> ХОРОШО.

1011
00:49:53,540 --> 00:49:57,462
Кто-нибудь есть предположение, что в
в худшем случае время выполнения пузырьковой сортировки является?

1012
00:49:57,462 --> 00:49:57,962
Да.

1013
00:49:57,962 --> 00:50:07,810
>> АУДИТОРИЯ: было бы, как, п раз
п минус 1 или что-то подобное?

1014
00:50:07,810 --> 00:50:10,650
Мол, каждый раз, когда он работает,
это просто, как один своп менее

1015
00:50:10,650 --> 00:50:10,960
что бы это ни было.

1016
00:50:10,960 --> 00:50:12,668
>> ANDI Пэн: Да, так
Вы совершенно правы.

1017
00:50:12,668 --> 00:50:15,940
И это тот случай, когда ваш
Ответ на самом деле более сложная

1018
00:50:15,940 --> 00:50:17,240
чем мы должны дать.

1019
00:50:17,240 --> 00:50:19,772
Так это будет run-- Я
собираюсь стереть все это здесь.

1020
00:50:19,772 --> 00:50:20,480
Все ли хорошо?

1021
00:50:20,480 --> 00:50:21,869
Могу ли я стереть это?

1022
00:50:21,869 --> 00:50:22,368
ХОРОШО.

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
Вы собираетесь работать через п
раз в первый раз, не так ли?

1025
00:50:30,320 --> 00:50:33,200
И они собираются запустить через
п минус 1 во второй раз, верно?

1026
00:50:33,200 --> 00:50:37,130
И тогда вы будете держать
происходит, п мой 2, и так далее.

1027
00:50:37,130 --> 00:50:40,210
Дэвид сделал это в лекции, где,
если вы добавили все эти ценности,

1028
00:50:40,210 --> 00:50:48,080
Вы получаете то, что это like-- yeah--
более 2, что существенно снижает просто

1029
00:50:48,080 --> 00:50:49,784
до п квадрате.

1030
00:50:49,784 --> 00:50:51,700
Вы собираетесь получить
странно доля там.

1031
00:50:51,700 --> 00:50:53,892
И так просто знаю, что
п квадрате всегда

1032
00:50:53,892 --> 00:50:55,350
имеет приоритет над фракцией.

1033
00:50:55,350 --> 00:50:58,450
И поэтому в этом случае худшего
выполнения будет н в квадрате.

1034
00:50:58,450 --> 00:51:00,210
Если бы это было в порядке убывания
порядок, думаю, вам,

1035
00:51:00,210 --> 00:51:02,530
должны сделать своп каждый раз.

1036
00:51:02,530 --> 00:51:05,170
>> Что бы, потенциально,
в лучшем случае выполнения?

1037
00:51:05,170 --> 00:51:08,580
Давайте просто сказать, что если список уже был
в порядке, что бы во время выполнения будет?

1038
00:51:08,580 --> 00:51:09,565
>> АУДИТОРИЯ: п.

1039
00:51:09,565 --> 00:51:10,690
ANDI Пэн: Это н, точно.

1040
00:51:10,690 --> 00:51:11,600
И почему это п?

1041
00:51:11,600 --> 00:51:13,850
АУДИТОРИЯ: потому что вы просто
должны проверить на каждом раз.

1042
00:51:13,850 --> 00:51:14,770
ANDI Пэн: Точно.

1043
00:51:14,770 --> 00:51:17,150
Таким образом, в лучшем выполнения,
если этот список был уже

1044
00:51:17,150 --> 00:51:20,270
sorted-- скажем 1, 2, 3, 4-- вы
просто пройти, вы бы проверить,

1045
00:51:20,270 --> 00:51:21,720
вы увидите, ох, все они оправдались.

1046
00:51:21,720 --> 00:51:22,636
У меня не было, чтобы поменять.

1047
00:51:22,636 --> 00:51:23,370
Я задолбался.

1048
00:51:23,370 --> 00:51:26,500
Таким образом, в этом случае, это просто п
или количество шагов, которые вы просто

1049
00:51:26,500 --> 00:51:29,870
должен был проверить в первом списке.

1050
00:51:29,870 --> 00:51:33,990
>> И после этого, мы теперь попал
сортировка вставками, где

1051
00:51:33,990 --> 00:51:39,260
алгоритм, по существу, разделить
это в отсортированном и несортированных части.

1052
00:51:39,260 --> 00:51:42,810
А потом один за другим,
неотсортированной значения

1053
00:51:42,810 --> 00:51:46,880
вставляется в соответствующих
позиции в начале списка.

1054
00:51:46,880 --> 00:51:52,120
>> Так, например, у нас есть
Список 3, 5, 2, 6, 4 снова.

1055
00:51:52,120 --> 00:51:54,750
Мы знаем, что это в настоящее время
несортированный, потому что мы только что

1056
00:51:54,750 --> 00:51:57,030
начал смотреть на него.

1057
00:51:57,030 --> 00:52:00,610
Мы смотрим и мы знаем, что
первое значение сортируется, верно?

1058
00:52:00,610 --> 00:52:04,190
Если вы только глядя на массив
Размер одного, вы знаете, что это сортируется.

1059
00:52:04,190 --> 00:52:08,230
>> Итак, мы знаем, что
Остальные четыре несортированный.

1060
00:52:08,230 --> 00:52:10,980
Мы идем через, и мы видим, что значение.

1061
00:52:10,980 --> 00:52:11,730
Давай вернемся.

1062
00:52:11,730 --> 00:52:13,130
Смотрите, что значение 5?

1063
00:52:13,130 --> 00:52:14,110
Мы смотрим на него.

1064
00:52:14,110 --> 00:52:15,204
Мы сравниваем его до 3.

1065
00:52:15,204 --> 00:52:17,870
Мы знаем, что это больше, чем
3, так что мы знаем, что это сортируется.

1066
00:52:17,870 --> 00:52:22,940
Таким образом, мы теперь знаем, что первые два
сортируются, а последние три не являются.

1067
00:52:22,940 --> 00:52:24,270
>> Мы взглянем на 2.

1068
00:52:24,270 --> 00:52:25,720
Сначала мы проверяем его 5.

1069
00:52:25,720 --> 00:52:26,700
Это меньше, чем 5?

1070
00:52:26,700 --> 00:52:27,240
Это не.

1071
00:52:27,240 --> 00:52:29,510
Таким образом, мы должны держать глядя вниз.

1072
00:52:29,510 --> 00:52:30,940
Тогда вы проверить 2 от 3.

1073
00:52:30,940 --> 00:52:31,850
Это меньше, чем?

1074
00:52:31,850 --> 00:52:32,350
Нет.

1075
00:52:32,350 --> 00:52:35,430
Таким образом, вы знаете, что 2 должен быть вставлен
в передней и 3 и 5

1076
00:52:35,430 --> 00:52:38,200
оба должны быть вытеснены.

1077
00:52:38,200 --> 00:52:42,190
Сделайте это снова 6 и 4.

1078
00:52:42,190 --> 00:52:48,962
И мы просто следите существу,
где мы просто проверить, проверить, проверить.

1079
00:52:48,962 --> 00:52:51,170
И пока это не в праве
должность, мы бы просто

1080
00:52:51,170 --> 00:52:54,890
вставьте его в правильном положении,
который является, где имя пришел.

1081
00:52:54,890 --> 00:52:59,830
>> Так что это просто алгоритм,
псевдокод таковой, вроде,

1082
00:52:59,830 --> 00:53:04,990
о том, как мы будет осуществлять
сортировка вставками.

1083
00:53:04,990 --> 00:53:05,954
Псевдокод здесь.

1084
00:53:05,954 --> 00:53:06,620
Это все в Интернете.

1085
00:53:06,620 --> 00:53:10,720
Не беспокойтесь, если вы, ребята,
пытаясь скопировать это вниз.

1086
00:53:10,720 --> 00:53:14,500
Итак, еще раз, то же самое, что question--
будет лучшим и худшим автономной работы

1087
00:53:14,500 --> 00:53:16,120
для вставки рода?

1088
00:53:16,120 --> 00:53:17,750
Это очень похоже на последний вопрос.

1089
00:53:17,750 --> 00:53:20,479
Я дам вам, ребята, как, 30
секунд, чтобы думать об этом, а также.

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> ОК ли кто-то хочет
дать мне худший выполнения?

1092
00:53:50,071 --> 00:53:50,570
Да.

1093
00:53:50,570 --> 00:53:51,490
>> АУДИТОРИЯ: п в квадрате.

1094
00:53:51,490 --> 00:53:52,573
>> ANDI Пэн: Это н квадрате.

1095
00:53:52,573 --> 00:53:53,730
И почему это п квадрате?

1096
00:53:53,730 --> 00:53:57,562
>> АУДИТОРИЯ: Потому что в
обратный порядок, у вас есть

1097
00:53:57,562 --> 00:54:02,619
пройти через п раз п, is--

1098
00:54:02,619 --> 00:54:03,660
ANDI Пэн: Да, именно так.

1099
00:54:03,660 --> 00:54:06,610
Так же, как и в пузырьковой сортировки.

1100
00:54:06,610 --> 00:54:08,720
Если этот список в
порядке убывания, вы

1101
00:54:08,720 --> 00:54:11,240
придется проверить первый раз.

1102
00:54:11,240 --> 00:54:13,470
А потом с каждым
дополнительная стоимость, вы

1103
00:54:13,470 --> 00:54:16,390
придется проверить его против
каждый значение, верно?

1104
00:54:16,390 --> 00:54:20,290
И так в целом, вы собираетесь сделать
А.Н. раз н-пасс другой п пройти, что

1105
00:54:20,290 --> 00:54:21,750
в п квадрате.

1106
00:54:21,750 --> 00:54:22,860
Что можно сказать о лучшем случае?

1107
00:54:22,860 --> 00:54:24,360
Да.

1108
00:54:24,360 --> 00:54:28,840
>> АУДИТОРИЯ: N минус 1, поскольку
Первый уже в квадрат.

1109
00:54:28,840 --> 00:54:30,270
>> ANDI Пэн: Так, близко.

1110
00:54:30,270 --> 00:54:31,850
Ответ на самом деле п.

1111
00:54:31,850 --> 00:54:37,189
Поскольку в то время как Первый
сортировать, она не может его actually--

1112
00:54:37,189 --> 00:54:38,980
мы просто повезло, в
что пример, что 2

1113
00:54:38,980 --> 00:54:40,930
произошло наименьшее число.

1114
00:54:40,930 --> 00:54:43,680
Но не всегда будет так.

1115
00:54:43,680 --> 00:54:48,040
Если 2 уже отсортированы в начале
но вы посмотрите, и есть 1 здесь,

1116
00:54:48,040 --> 00:54:49,144
1 будет поднять его.

1117
00:54:49,144 --> 00:54:51,060
И это будет в конечном
до того столкнулся в любом случае.

1118
00:54:51,060 --> 00:54:56,250
>> Таким образом, в лучшем случае,
это на самом деле просто будет н.

1119
00:54:56,250 --> 00:54:59,090
Если у вас есть 1, 2, 3,
4, 5, 6, 7, 8, вы

1120
00:54:59,090 --> 00:55:00,940
собирается запустить через
что весь список сразу

1121
00:55:00,940 --> 00:55:03,430
чтобы проверить, если все в порядке.

1122
00:55:03,430 --> 00:55:07,390
Это все ясно, на работающем
раз отбора, а?

1123
00:55:07,390 --> 00:55:09,960
Я знаю, что иду через
это очень быстро.

1124
00:55:09,960 --> 00:55:13,330
Но точно знаю, что, если вы знаете,
общие понятия, вы должны быть хорошо.

1125
00:55:13,330 --> 00:55:16,070
ХОРОШО.

1126
00:55:16,070 --> 00:55:19,790
Так что я просто дам вам, ребята, может быть, как,
минуту, чтобы поговорить с вашими соседями

1127
00:55:19,790 --> 00:55:21,890
на то, что лишь некоторые
из основных отличий

1128
00:55:21,890 --> 00:55:23,540
между этими типами сортов.

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
Мы пойдем над тем в ближайшее время.

1131
00:56:25,570 --> 00:56:26,444
АУДИТОРИЯ: О, хорошо.

1132
00:56:26,444 --> 00:56:27,320
ANDI Пэн: Да.

1133
00:56:27,320 --> 00:56:28,380
ХОРОШО.

1134
00:56:28,380 --> 00:56:33,420
Прохладный, давайте вновь созвать как класс.

1135
00:56:33,420 --> 00:56:34,330
ХОРОШО.

1136
00:56:34,330 --> 00:56:37,579
Так что это было своего рода
открытый вопрос в том смысле,

1137
00:56:37,579 --> 00:56:39,120
что есть много ответов на них.

1138
00:56:39,120 --> 00:56:40,746
И мы будем идти над некоторыми из них кратко.

1139
00:56:40,746 --> 00:56:43,411
Я просто хотел, чтобы вы, ребята
думая о том, что дифференцированный

1140
00:56:43,411 --> 00:56:44,530
все три типа сортов.

1141
00:56:44,530 --> 00:56:47,440
И услышал я, также, большой
question-- что же сортировки слиянием сделать?

1142
00:56:47,440 --> 00:56:50,110
Большой вопрос, потому что это
то, что мы в следующем покрытия.

1143
00:56:50,110 --> 00:56:52,850
>> Так объединить рода является
один вид, что функции

1144
00:56:52,850 --> 00:56:56,100
очень по-разному от других видов.

1145
00:56:56,100 --> 00:56:58,180
Как вы, ребята, можете see--
сделал Давид, что демо

1146
00:56:58,180 --> 00:57:01,130
где он все круто
шумы, видя, как объединить

1147
00:57:01,130 --> 00:57:04,010
Сортировать побежал, как бесконечно
быстрее, чем двух других типов?

1148
00:57:04,010 --> 00:57:04,510
ХОРОШО.

1149
00:57:04,510 --> 00:57:07,580
Так это потому, что слияние
Сортировать реализует этот разрыв

1150
00:57:07,580 --> 00:57:11,020
и завоевать концепцию, что мы
говорили о многом в лекции.

1151
00:57:11,020 --> 00:57:14,550
В том смысле, что мы хотели бы работать
умнее, а не труднее, когда вы разделите

1152
00:57:14,550 --> 00:57:18,120
и завоевать проблемы, и сломать их
вниз, а затем положить их вместе,

1153
00:57:18,120 --> 00:57:19,930
хорошие вещи всегда происходят.

1154
00:57:19,930 --> 00:57:21,960
>> Так так, что сливаются
Сортировать по существу работает

1155
00:57:21,960 --> 00:57:24,660
является то, что делит
несортированный массив пополам.

1156
00:57:24,660 --> 00:57:26,500
А потом он получил две половинки массивов.

1157
00:57:26,500 --> 00:57:28,220
И это как раз те сортирует две половинки.

1158
00:57:28,220 --> 00:57:31,750
Он просто держит деления пополам, в
половина, пополам, пока все не будет отсортирован

1159
00:57:31,750 --> 00:57:33,680
а затем рекурсивно
ставит все это вместе.

1160
00:57:33,680 --> 00:57:36,550
>> Так что это действительно абстрактной.

1161
00:57:36,550 --> 00:57:38,750
Так что это просто немного псевдокода.

1162
00:57:38,750 --> 00:57:41,040
Имеет ли это смысл в
так, как это работает?

1163
00:57:41,040 --> 00:57:43,870
Так что давайте просто сказать, у вас есть
массив п элементов, правильно?

1164
00:57:43,870 --> 00:57:45,450
Если п меньше, чем 2, вы можете вернуться.

1165
00:57:45,450 --> 00:57:49,040
Потому что вы знаете, что, если есть
только одна вещь, она должна быть отсортированы.

1166
00:57:49,040 --> 00:57:52,600
В противном случае, вы сортировать левую половину,
а затем отсортировать правую половину,

1167
00:57:52,600 --> 00:57:54,140
и тогда вы сливаются.

1168
00:57:54,140 --> 00:57:56,979
>> Так в то время как выглядит на самом деле легко,
в действительности, думать об этом это

1169
00:57:56,979 --> 00:58:00,270
вид трудно. Потому что вы, как
ну вот вроде работает на себя.

1170
00:58:00,270 --> 00:58:00,769
Правильно?

1171
00:58:00,769 --> 00:58:02,430
Это работает на себя.

1172
00:58:02,430 --> 00:58:05,479
Так что в этом смысле, Дэвид коснулся
на рекурсии в классе.

1173
00:58:05,479 --> 00:58:07,270
И это понятие
мы поговорим о более.

1174
00:58:07,270 --> 00:58:11,430
Это что это, эти две линии
Здесь, на самом деле это просто программа

1175
00:58:11,430 --> 00:58:13,860
говорю это, чтобы запустить себя
с другой вход.

1176
00:58:13,860 --> 00:58:17,230
Таким образом, вместо запуска себя с
полнота п элементов,

1177
00:58:17,230 --> 00:58:20,530
Вы можете разбить его вниз в
левая половина и правая половина

1178
00:58:20,530 --> 00:58:22,680
а затем запустить его снова.

1179
00:58:22,680 --> 00:58:26,050
>> И тогда мы будем смотреть на него визуально,
потому что я визуальный ученик.

1180
00:58:26,050 --> 00:58:27,270
Это работает лучше для меня.

1181
00:58:27,270 --> 00:58:29,890
Таким образом, мы будем смотреть на наглядном примере здесь.

1182
00:58:29,890 --> 00:58:36,237
>> Скажем, мы имеем массив, шесть
Элементы, 3, 5, 2, 6, 4, 1, не отсортированы.

1183
00:58:36,237 --> 00:58:37,820
Ладно, есть много на этой странице.

1184
00:58:37,820 --> 00:58:43,179
Так что, если вы, ребята, можете посмотреть на
Первый шаг здесь, 3, 5, 2, 6, 4, 1,

1185
00:58:43,179 --> 00:58:44,220
Вы можете разделить его пополам.

1186
00:58:44,220 --> 00:58:45,976
У вас есть 3, 5, 2, 6, 4, 1.

1187
00:58:45,976 --> 00:58:48,850
Вы знаете, что это вам aren't--
не знаю, если они сортируются или нет,

1188
00:58:48,850 --> 00:58:52,517
так вы держите разбивая их в половине,
пополам, пополам, пока в конце концов,

1189
00:58:52,517 --> 00:58:53,600
у вас есть только один элемент.

1190
00:58:53,600 --> 00:58:56,790
И один элемент всегда сортируются, верно?

1191
00:58:56,790 --> 00:59:01,560
>> Итак, мы знаем, что 3, 5, 2, 4, 6,
1, сами по себе, сортируются.

1192
00:59:01,560 --> 00:59:05,870
И теперь мы можем положить их обратно вместе.

1193
00:59:05,870 --> 00:59:07,510
Таким образом, мы знаем 3, 5.

1194
00:59:07,510 --> 00:59:08,510
Ставим их вместе.

1195
00:59:08,510 --> 00:59:09,617
Мы знаем, что это отсортированный.

1196
00:59:09,617 --> 00:59:10,450
В 2-х до сих пор там.

1197
00:59:10,450 --> 00:59:11,830
Мы можем поставить 4 и 6 вместе.

1198
00:59:11,830 --> 00:59:13,996
Мы знаем, что это сортируется,
таким образом, мы положить, что вместе.

1199
00:59:13,996 --> 00:59:14,940
А 1 есть.

1200
00:59:14,940 --> 00:59:18,720
>> А потом вы просто посмотрите на
эти две половинки прямо здесь.

1201
00:59:18,720 --> 00:59:21,300
Вы имеете 3, 5, 2, 2, 3, 5.

1202
00:59:21,300 --> 00:59:23,465
Вы можете просто сравнить
начало всего.

1203
00:59:23,465 --> 00:59:26,340
Потому что вы знаете, что это сортируется
и вы знаете, что это сортируется.

1204
00:59:26,340 --> 00:59:29,360
Тогда вы не должны даже
сравнить 5, вы просто сравнить 3.

1205
00:59:29,360 --> 00:59:32,070
А 2 меньше, чем 3, так
Вы знаете, 2 необходимо перейти в конец.

1206
00:59:32,070 --> 00:59:33,120
>> То же самое там.

1207
00:59:33,120 --> 00:59:34,740
1-необходимо перейти сюда.

1208
00:59:34,740 --> 00:59:37,330
А потом, когда вы идете, чтобы положить
эти два значения вместе,

1209
00:59:37,330 --> 00:59:39,950
Вы знаете, что это сортируется и
Вы знаете, что сортируется.

1210
00:59:39,950 --> 00:59:43,240
Так то 1 и
2, 1 составляет менее 2.

1211
00:59:43,240 --> 00:59:45,570
Это говорит о том, что 1
должны пойти на конце этого

1212
00:59:45,570 --> 00:59:47,480
даже не глядя на 3 или 5.

1213
00:59:47,480 --> 00:59:50,100
А потом в 4, вы можете просто
проверить, что идет прямо здесь.

1214
00:59:50,100 --> 00:59:51,480
Вы не должны смотреть на 5.

1215
00:59:51,480 --> 00:59:52,570
То же самое с 6.

1216
00:59:52,570 --> 00:59:55,860
Вы знаете, что это просто 6--
не должны быть рассмотрены.

1217
00:59:55,860 --> 00:59:57,870
>> И поэтому в этом пути, вы
только спасти себя

1218
00:59:57,870 --> 00:59:59,526
много шагов, когда вы сравниваете.

1219
00:59:59,526 --> 01:00:02,150
Вы не должны сравнивать каждый
Элемент с другими элементами.

1220
01:00:02,150 --> 01:00:05,230
Вы просто сравните против тех
что вам нужно, чтобы сравнить ее с.

1221
01:00:05,230 --> 01:00:06,870
Так что вроде абстрактной концепции.

1222
01:00:06,870 --> 01:00:10,540
Не беспокойтесь, если это не
достаточно удара вас прямо еще.

1223
01:00:10,540 --> 01:00:14,740
Но, как правило, это
как сортировка слиянием работает.

1224
01:00:14,740 --> 01:00:17,750
Вопросы, простых вопросов,
прежде, чем я двигаться дальше?

1225
01:00:17,750 --> 01:00:18,550
Да.

1226
01:00:18,550 --> 01:00:22,230
>> АУДИТОРИЯ: Так вы сказали, что вы берете
1, а затем 4 и 6

1227
01:00:22,230 --> 01:00:23,860
и положил их в.

1228
01:00:23,860 --> 01:00:26,800
Так не those-- не
Вы ищете на них

1229
01:00:26,800 --> 01:00:28,544
как отдельные элементы, а не как в целом?

1230
01:00:28,544 --> 01:00:29,210
ANDI Пэн: Да.

1231
01:00:29,210 --> 01:00:32,020
Так, что происходит
является то, что вы в основном

1232
01:00:32,020 --> 01:00:33,650
создают совершенно новый массив.

1233
01:00:33,650 --> 01:00:36,690
Таким образом, вы знаете, что, вот, у меня есть
два массива размером 3, верно?

1234
01:00:36,690 --> 01:00:39,600
Таким образом, вы знаете, что мой отсортированный массив
должен иметь шесть элементов.

1235
01:00:39,600 --> 01:00:42,270
Таким образом, вы просто создать
Новый объем памяти.

1236
01:00:42,270 --> 01:00:44,270
Так вы вроде как
будучи расточительным памяти,

1237
01:00:44,270 --> 01:00:46,186
но это не имеет значения
потому что это так мало.

1238
01:00:46,186 --> 01:00:48,590
Таким образом, вы смотрите на 1
и вы посмотрите на 2.

1239
01:00:48,590 --> 01:00:50,770
И вы знаете, что 1 меньше, чем 2.

1240
01:00:50,770 --> 01:00:53,840
Таким образом, вы знаете, что 1 должны идти в
начало всех тех.

1241
01:00:53,840 --> 01:00:55,850
>> Вы даже не нужно
смотреть на 3 и 5.

1242
01:00:55,850 --> 01:00:57,400
Таким образом, вы знаете, 1 идет туда.

1243
01:00:57,400 --> 01:00:59,300
Тогда вы в основном отрубить 1.

1244
01:00:59,300 --> 01:01:00,370
Это, вроде бы, умер для нас.

1245
01:01:00,370 --> 01:01:03,690
Тогда мы просто должны 2,
3, 5, а затем 4 и 6.

1246
01:01:03,690 --> 01:01:06,270
И тогда вы знаете, что вы
сравнить 4 и 2,

1247
01:01:06,270 --> 01:01:07,560
ой, 2 должны пойти туда.

1248
01:01:07,560 --> 01:01:09,685
Таким образом, вы хлопнуть 2 вниз, рубите его.

1249
01:01:09,685 --> 01:01:12,060
Тогда вы просто есть 3
и 5 в 4 и 6.

1250
01:01:12,060 --> 01:01:14,650
И вы просто держать его измельчение
пока вы не положить их в массиве.

1251
01:01:14,650 --> 01:01:17,110
>> АУДИТОРИЯ: Так ты просто всегда
Сравнивая [неразборчиво]?

1252
01:01:17,110 --> 01:01:17,710
>> ANDI Пэн: Точно.

1253
01:01:17,710 --> 01:01:19,590
Так что в этом смысле, вы
просто сравнение, по сути,

1254
01:01:19,590 --> 01:01:21,240
один номер против другой номер.

1255
01:01:21,240 --> 01:01:22,990
И потому что вы знаете
что это сортируется, вам

1256
01:01:22,990 --> 01:01:24,350
не придется искать через
все номера.

1257
01:01:24,350 --> 01:01:25,870
Вы просто должны посмотреть на первый.

1258
01:01:25,870 --> 01:01:27,582
И тогда вы можете просто хлопнуть
их вниз, потому что вы знаете,

1259
01:01:27,582 --> 01:01:29,640
они принадлежат, где они должны принадлежать.

1260
01:01:29,640 --> 01:01:31,030
Да.

1261
01:01:31,030 --> 01:01:32,920
Хороший вопрос.

1262
01:01:32,920 --> 01:01:35,290
>> И потом, если любой из вас
немного амбициозный,

1263
01:01:35,290 --> 01:01:38,660
не стесняйтесь, чтобы посмотреть на этот код.

1264
01:01:38,660 --> 01:01:40,680
Это на самом деле
физическая реализация

1265
01:01:40,680 --> 01:01:42,150
о том, как мы должны написать сортировки слиянием.

1266
01:01:42,150 --> 01:01:44,070
И вы можете видеть, это очень мало.

1267
01:01:44,070 --> 01:01:46,310
Но идеи, лежащие в
это довольно сложная.

1268
01:01:46,310 --> 01:01:50,865
Так что, если вы чувствуете, как рисунок на это
в выполнении домашних заданий сегодня, не стесняйтесь.

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> ХОРОШО.

1271
01:01:54,740 --> 01:01:58,070
Так и Давид подошел это в лекции.

1272
01:01:58,070 --> 01:02:00,660
Что в лучшем случае
Время автономной работы, в худшем случае время автономной работы,

1273
01:02:00,660 --> 01:02:05,680
и ожидаемые автономной работы от сортировки слиянием?

1274
01:02:05,680 --> 01:02:07,260
Через пару секунд, чтобы подумать.

1275
01:02:07,260 --> 01:02:11,198
Это довольно трудно, но вид
интуитивным, если вы думаете об этом.

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
Все в порядке.

1278
01:02:23,054 --> 01:02:25,269
>> Зала: в худшем случае п п журнала?

1279
01:02:25,269 --> 01:02:26,060
ANDI Пэн: Точно.

1280
01:02:26,060 --> 01:02:29,380
И почему это п п войти.

1281
01:02:29,380 --> 01:02:32,230
>> АУДИТОРИЯ: Разве это не потому, что он
становится экспоненциально быстрее,

1282
01:02:32,230 --> 01:02:35,390
так что это, как функции, которые
а просто быть п

1283
01:02:35,390 --> 01:02:37,529
квадрат или что-то?

1284
01:02:37,529 --> 01:02:38,320
ANDI Пэн: Точно.

1285
01:02:38,320 --> 01:02:40,750
Таким образом, причина, по которой
выполнения на это н журнала

1286
01:02:40,750 --> 01:02:44,310
п because--, что ты
делать во всех этих шагов?

1287
01:02:44,310 --> 01:02:46,190
Вы просто рубить его пополам, верно?

1288
01:02:46,190 --> 01:02:48,750
И поэтому, когда мы делаем
войти, все, что он делает

1289
01:02:48,750 --> 01:02:53,150
делит проблему пополам,
в два раза, в два раза, в более половины.

1290
01:02:53,150 --> 01:02:56,430
И в этом смысле, вы можете вид
из устранить линейную модель

1291
01:02:56,430 --> 01:02:57,510
что мы использовали.

1292
01:02:57,510 --> 01:03:00,254
Потому что, когда вы нарезать
вещи в половине, это журнал.

1293
01:03:00,254 --> 01:03:02,420
Вот только математический
способ представления его.

1294
01:03:02,420 --> 01:03:06,310
>> И, наконец, в конце, вы
просто сделать один последний пас через

1295
01:03:06,310 --> 01:03:07,930
поставить все из них в порядке, верно?

1296
01:03:07,930 --> 01:03:10,330
И так, если вы просто должны
проверить одну вещь, это п.

1297
01:03:10,330 --> 01:03:13,420
И так ты вроде
умножения вместе.

1298
01:03:13,420 --> 01:03:17,660
Так что это, как вы получили, что окончательный
проверить п сюда с бревна п

1299
01:03:17,660 --> 01:03:18,390
здесь.

1300
01:03:18,390 --> 01:03:21,060
И если умножить
им, что это н н войти.

1301
01:03:21,060 --> 01:03:26,100
>> И так в лучшем случае и худшие
Корпус и ожидается, все п п войти.

1302
01:03:26,100 --> 01:03:27,943
Это также, как другого рода.

1303
01:03:27,943 --> 01:03:30,090
Это как выбор рода
в том смысле, что

1304
01:03:30,090 --> 01:03:32,131
Не имеет значения, что ваш
Список, это просто будет

1305
01:03:32,131 --> 01:03:34,801
чтобы сделать то же самое каждый раз.

1306
01:03:34,801 --> 01:03:35,300
ХОРОШО.

1307
01:03:35,300 --> 01:03:39,950
Итак, как вы, ребята, можете видеть, даже если
растения, которые мы пошли through-- п

1308
01:03:39,950 --> 01:03:41,660
квадрат, это не очень эффективно.

1309
01:03:41,660 --> 01:03:47,060
И даже в этом п п журнала
не самым эффективным.

1310
01:03:47,060 --> 01:03:49,720
Если вы, ребята, интересно,
есть механизмы сортировки

1311
01:03:49,720 --> 01:03:54,310
которые являются настолько эффективно, что они
почти практически плоским в режиме исполнения.

1312
01:03:54,310 --> 01:03:55,420
>> У вас есть некоторые журнал N.

1313
01:03:55,420 --> 01:03:58,190
У вас есть некоторые журнал журнала N.

1314
01:03:58,190 --> 01:04:00,330
Мы не касаемся их
в этом классе сейчас.

1315
01:04:00,330 --> 01:04:02,663
Но если вы, ребята, интересно,
не стесняйтесь Google, что

1316
01:04:02,663 --> 01:04:04,392
наиболее эффективные механизмы сортировки.

1317
01:04:04,392 --> 01:04:06,350
Я не знаю, есть
некоторые действительно смешные,

1318
01:04:06,350 --> 01:04:09,860
like-- есть некоторые действительно
смешные, которые люди делают.

1319
01:04:09,860 --> 01:04:12,210
И вы удивляетесь, как они
когда-нибудь думали об этом.

1320
01:04:12,210 --> 01:04:15,730
Так Google, если у вас есть запасной
Время, на то, что некоторые забавные способы

1321
01:04:15,730 --> 01:04:17,730
что people-- а также
эффективные ways-- люди

1322
01:04:17,730 --> 01:04:20,371
смогли реализовать всевозможные.

1323
01:04:20,371 --> 01:04:20,870
ХОРОШО.

1324
01:04:20,870 --> 01:04:22,880
И вот только маленький удобный график.

1325
01:04:22,880 --> 01:04:26,850
Я знаю все о тебе, до этого викторине 0,
будет в вашей комнате, вероятно, пытается

1326
01:04:26,850 --> 01:04:27,960
запомнить это.

1327
01:04:27,960 --> 01:04:30,940
Так что приятно там для вас, ребята.

1328
01:04:30,940 --> 01:04:37,120
Только не забывайте, логику, made--
Поэтому эти цифры были происходит.

1329
01:04:37,120 --> 01:04:39,870
Если вы всегда теряется, просто убедитесь,
уверен, что вы знаете, что сорта.

1330
01:04:39,870 --> 01:04:40,820
И вы можете запустить через
их в своем уме

1331
01:04:40,820 --> 01:04:42,903
чтобы выяснить, почему те,
ответы ответы на эти вопросы.

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> Все в порядке.

1334
01:04:47,600 --> 01:04:49,680
Итак, мы собираемся, чтобы переместить
на, наконец, поиска.

1335
01:04:49,680 --> 01:04:51,638
Потому что, как тех из вас,
кто читал PSET,

1336
01:04:51,638 --> 01:04:55,175
поиск также является частью
Проблема этой неделе задает.

1337
01:04:55,175 --> 01:04:57,300
Вам будет предложено осуществить
два типа поисков.

1338
01:04:57,300 --> 01:05:00,070
Одним из них является линейный поиск и
один двоичный поиск.

1339
01:05:00,070 --> 01:05:01,760
>> Таким образом, линейный поиск довольно легко.

1340
01:05:01,760 --> 01:05:04,070
Вы просто хотите, чтобы поиск элемента
из списка, чтобы увидеть, если вы его получите.

1341
01:05:04,070 --> 01:05:05,444
Вы просто должны перебора.

1342
01:05:05,444 --> 01:05:08,170
И если он равен то,
вы можете просто вернуть его, верно?

1343
01:05:08,170 --> 01:05:10,890
Но тот, что мы наиболее
заинтересованы в разговоре о

1344
01:05:10,890 --> 01:05:14,550
это бинарный поиск, право, которое является
разделяй и властвуй механизм, который

1345
01:05:14,550 --> 01:05:18,190
Дэвид демонстрировал в лекции.

1346
01:05:18,190 --> 01:05:20,810
>> Помните пример телефонной книги
что он продолжает воспитывать,

1347
01:05:20,810 --> 01:05:23,960
тот, который он вроде боролись
немного на прошедший год,

1348
01:05:23,960 --> 01:05:27,530
где вы разделите задачу на половине,
в два раза, в два раза, снова и снова,

1349
01:05:27,530 --> 01:05:30,730
пока вы не найдете то, что вы ищете?

1350
01:05:30,730 --> 01:05:33,727
И вы получили
время выполнения, что хорошо.

1351
01:05:33,727 --> 01:05:35,810
И вы можете видеть, это
значительно более эффективным

1352
01:05:35,810 --> 01:05:39,080
чем любой другой тип поиска.

1353
01:05:39,080 --> 01:05:41,880
>> Таким образом, путь, который мы бы идти о
реализации двоичного поиска

1354
01:05:41,880 --> 01:05:46,510
есть, если у нас было множество,
Индекс 0 до 6, семь элементов,

1355
01:05:46,510 --> 01:05:49,790
мы можем смотреть в середине, right--
извините, если наш вопрос first--

1356
01:05:49,790 --> 01:05:53,840
если мы хотим, чтобы задать вопрос о, не
массив содержит элемент 7,

1357
01:05:53,840 --> 01:05:56,840
Очевидно, будучи людей, и имеющий
такой маленький массив, это просто для нас

1358
01:05:56,840 --> 01:05:58,210
чтобы сказать да.

1359
01:05:58,210 --> 01:06:05,750
Но путь к реализации двоичный
Поиск будет выглядеть в середине.

1360
01:06:05,750 --> 01:06:08,020
>> Мы знаем, что индекс 3
средний, потому что мы

1361
01:06:08,020 --> 01:06:09,270
знаю, что есть семь элементов.

1362
01:06:09,270 --> 01:06:10,670
Что 7 делится на 2?

1363
01:06:10,670 --> 01:06:12,850
Вы можете отрубить что дополнительный 1.

1364
01:06:12,850 --> 01:06:14,850
Вы получили 3 в середине.

1365
01:06:14,850 --> 01:06:17,590
Так массив из 3 равно 7?

1366
01:06:17,590 --> 01:06:18,900
Это не правильно?

1367
01:06:18,900 --> 01:06:21,050
Но мы можем сделать пару чеков.

1368
01:06:21,050 --> 01:06:25,380
Это массив из 3 меньше, чем 7 или
это массив из 3 больше, чем 7?

1369
01:06:25,380 --> 01:06:27,240
>> И мы знаем, что это меньше, чем 7.

1370
01:06:27,240 --> 01:06:30,259
Итак, мы знаем, что, ну, она должна
не может быть в левой половине.

1371
01:06:30,259 --> 01:06:32,300
Мы знаем, что это должно быть
в правой половине, верно?

1372
01:06:32,300 --> 01:06:34,662
Таким образом, мы можем просто отрубить половину массива.

1373
01:06:34,662 --> 01:06:36,370
Мы даже не должны
смотреть на него больше.

1374
01:06:36,370 --> 01:06:38,711
Потому что мы знаем, что
половина нашего problem--

1375
01:06:38,711 --> 01:06:41,210
мы знаем, что ответ находится в
правая половина нашей задачи.

1376
01:06:41,210 --> 01:06:42,580
Таким образом, мы просто посмотрите на это сейчас.

1377
01:06:42,580 --> 01:06:44,860
>> Так что теперь мы смотрим на
Середина то, что осталось.

1378
01:06:44,860 --> 01:06:46,880
Этот показатель 5.

1379
01:06:46,880 --> 01:06:50,200
Мы делаем то же самое еще раз проверку
и мы видим, что это меньше.

1380
01:06:50,200 --> 01:06:52,050
Таким образом, мы смотрим в левой части, что.

1381
01:06:52,050 --> 01:06:53,430
И тогда мы видим, что чек.

1382
01:06:53,430 --> 01:06:57,600
Является ли значение массива в
Индекс 4 равна 7?

1383
01:06:57,600 --> 01:06:58,260
Это.

1384
01:06:58,260 --> 01:07:03,580
Таким образом, мы можем вернуться так, потому что
мы нашли значение в нашем списке.

1385
01:07:03,580 --> 01:07:06,738
Ли путь я прошел
что смысл всем?

1386
01:07:06,738 --> 01:07:08,760
ХОРОШО.

1387
01:07:08,760 --> 01:07:11,670
Я дам вам, ребята, может быть, как,
три, четыре минуты, чтобы выяснить,

1388
01:07:11,670 --> 01:07:13,270
как псевдокод это.

1389
01:07:13,270 --> 01:07:18,070
>> Итак, представьте, я попросил вас написать
Функция называется поиск (), что вернулся

1390
01:07:18,070 --> 01:07:20,640
значение, логическое значение,
что это правда или false-- как,

1391
01:07:20,640 --> 01:07:22,970
верно, если вы нашли
значение, ложь, если вы не сделали.

1392
01:07:22,970 --> 01:07:25,230
И тогда вы были
прошел в стоимости вы

1393
01:07:25,230 --> 01:07:28,410
искали в ценности, которые
это array-- о, я определенно поставить

1394
01:07:28,410 --> 01:07:29,410
что в неправильном месте.

1395
01:07:29,410 --> 01:07:29,580
ХОРОШО.

1396
01:07:29,580 --> 01:07:31,829
В любом случае, что должно быть
был справа значений.

1397
01:07:31,829 --> 01:07:36,280
А потом Int N это число
элементов в этом массиве.

1398
01:07:36,280 --> 01:07:39,430
Как бы вы идти о попытке
в псевдокоде эту проблему в?

1399
01:07:39,430 --> 01:07:41,630
Я дам вам, ребята, как
три минуты, чтобы сделать это.

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
Нет, я думаю, что есть only--
да, есть одна прямо здесь.

1402
01:08:02,595 --> 01:08:03,261
АУДИТОРИЯ: Могу ли я?

1403
01:08:03,261 --> 01:08:04,388
ANDI Пэн: Да, у меня есть ты.

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
Это работает?

1406
01:08:11,050 --> 01:08:12,290
Ладно, круто.

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> ХОРОШО.

1409
01:10:44,720 --> 01:10:47,630
Все правильные парни, мы
собирается обуздать его.

1410
01:10:47,630 --> 01:10:49,730
ХОРОШО.

1411
01:10:49,730 --> 01:10:54,020
Так предположим, что у нас есть эта прекрасная
немного массив с п значений в нем.

1412
01:10:54,020 --> 01:10:55,170
Я не рисовать линии.

1413
01:10:55,170 --> 01:10:58,649
Но как бы мы идти о
пытаюсь написать это?

1414
01:10:58,649 --> 01:11:00,440
Кто-нибудь хочет
дать мне первую линию?

1415
01:11:00,440 --> 01:11:02,814
Если вы хотите, чтобы дать мне
Первая строка этого псевдокода.

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> АУДИТОРИЯ: [неразборчиво]

1418
01:11:08,430 --> 01:11:10,138
АУДИТОРИЯ: Вы хотели
для перебора through--

1419
01:11:10,138 --> 01:11:11,094
АУДИТОРИЯ: Просто еще один цикл?

1420
01:11:11,094 --> 01:11:11,760
АУДИТОРИЯ: --Для.

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI Пэн: Так что это одно немного сложнее.

1423
01:11:17,780 --> 01:11:23,130
Подумайте about-- вы хотите
держать работает этот цикл

1424
01:11:23,130 --> 01:11:27,950
снова и снова, пока, когда?

1425
01:11:27,950 --> 01:11:30,819
>> АУДИТОРИЯ: До [неразборчиво]
значение равно этому значению.

1426
01:11:30,819 --> 01:11:31,610
ANDI Пэн: Точно.

1427
01:11:31,610 --> 01:11:33,900
Таким образом, вы можете на самом деле просто write--
мы можем даже упростить его больше.

1428
01:11:33,900 --> 01:11:35,630
Мы можем просто сделать то время как цикл, верно?

1429
01:11:35,630 --> 01:11:39,380
Таким образом, вы можете просто loop--
мы знаем, что это какое-то время.

1430
01:11:39,380 --> 01:11:42,850
Но сейчас, я собираюсь
сказать "петлю" - через что?

1431
01:11:42,850 --> 01:11:46,640
Цикл until-- что
наш заканчивая состояние?

1432
01:11:46,640 --> 01:11:47,510
Я думаю, что я слышал.

1433
01:11:47,510 --> 01:11:48,530
Я слышал, кто-то сказать.

1434
01:11:48,530 --> 01:11:51,255
>> Аудитория: Значения равна середину.

1435
01:11:51,255 --> 01:11:52,255
ANDI Пэн: Скажи это еще раз.

1436
01:11:52,255 --> 01:11:54,470
АУДИТОРИЯ: Или, до
Значение вы ищете

1437
01:11:54,470 --> 01:11:58,470
Для равна среднего значения.

1438
01:11:58,470 --> 01:12:00,280
>> ANDI Пэн: Что делать, если это не там?

1439
01:12:00,280 --> 01:12:03,113
Что делать, если значение вы ищете
для на самом деле не в этом массиве?

1440
01:12:03,113 --> 01:12:05,890
АУДИТОРИЯ: Вы возвращаетесь 1.

1441
01:12:05,890 --> 01:12:08,850
>> ANDI Пэн: Но то, что мы хотим, чтобы
цикл до если у нас есть состояние?

1442
01:12:08,850 --> 01:12:09,350
Да.

1443
01:12:09,350 --> 01:12:11,239
>> АУДИТОРИЯ: пока есть только одно значение?

1444
01:12:11,239 --> 01:12:13,530
ANDI Пэн: Вы можете цикл
until-- так что вы знаете, что вы

1445
01:12:13,530 --> 01:12:15,714
будет иметь максимальное значение, не так ли?

1446
01:12:15,714 --> 01:12:18,130
И вы знаете, что вы собираетесь
иметь значение мин, верно?

1447
01:12:18,130 --> 01:12:20,379
Потому что также, это то, что
Я забыл сказать, прежде чем,

1448
01:12:20,379 --> 01:12:22,640
что что-то, что это
критически бинарного поиска

1449
01:12:22,640 --> 01:12:24,182
является то, что ваш массив уже отсортированы.

1450
01:12:24,182 --> 01:12:26,973
Потому что нет никакого способа делать
это, если они просто случайные значения.

1451
01:12:26,973 --> 01:12:29,190
Вы не знаете, если один это
больше, чем другие, верно?

1452
01:12:29,190 --> 01:12:32,720
>> Таким образом, вы знаете, что ваш Макс и
Ваши минут здесь, верно?

1453
01:12:32,720 --> 01:12:35,590
Если вы собираетесь быть регулировки
Ваш макс в ваших минут и mid--

1454
01:12:35,590 --> 01:12:38,470
давайте предположим, ваш
Значение среднего правильно here--

1455
01:12:38,470 --> 01:12:43,910
Вы собираетесь в основном
цикл до тех пор, минимальная не

1456
01:12:43,910 --> 01:12:47,510
примерно то же самое, как ваш макс, прямо или
если ваш максимум не то же самое, как ваш мин.

1457
01:12:47,510 --> 01:12:48,040
Правильно?

1458
01:12:48,040 --> 01:12:51,340
Потому что, когда это произойдет, вы знаете, что
Вы в конечном итоге попал в такое же значение.

1459
01:12:51,340 --> 01:12:59,135
Так вы не хотите, чтобы петли, пока ваш мин
меньше или равно, целью которых упс,

1460
01:12:59,135 --> 01:13:01,510
не менее или равно,
иначе around-- Макс.

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> Разве что смысл?

1463
01:13:16,160 --> 01:13:18,810
Я взял несколько попыток, чтобы получить это право.

1464
01:13:18,810 --> 01:13:21,869
Но цикл, пока ваш максимального значения
по сути почти нет

1465
01:13:21,869 --> 01:13:23,410
чем или равно вашей минимум, верно?

1466
01:13:23,410 --> 01:13:25,201
Вот когда вы знаете,
что вы сошлись.

1467
01:13:25,201 --> 01:13:29,290
АУДИТОРИЯ: Когда ваша максимальная
значение меньше, чем минимум?

1468
01:13:29,290 --> 01:13:31,040
ANDI Пэн: Если вы держите
регулируя его, что

1469
01:13:31,040 --> 01:13:32,380
это то, что мы собираемся
чтобы делать в этом.

1470
01:13:32,380 --> 01:13:33,460
Имеет ли это смысл?

1471
01:13:33,460 --> 01:13:35,750
Минимальная и максимальная просто
целые числа, мы, вероятно,

1472
01:13:35,750 --> 01:13:39,260
собирается хотите создать, чтобы держать
трек, где мы ищем.

1473
01:13:39,260 --> 01:13:41,790
Поскольку массив существует
независимо от того, что мы делаем.

1474
01:13:41,790 --> 01:13:45,030
Мол, мы на самом деле не физически
отрубание массива, верно?

1475
01:13:45,030 --> 01:13:47,261
Мы просто регулируя
где мы ищем.

1476
01:13:47,261 --> 01:13:48,136
Имеет ли это смысл?

1477
01:13:48,136 --> 01:13:48,472
>> АУДИТОРИЯ: Да.

1478
01:13:48,472 --> 01:13:49,110
>> ANDI Пэн: ОК.

1479
01:13:49,110 --> 01:13:57,090
Так что, если это условие нашей петли,
то, что мы хотим внутри этой петли?

1480
01:13:57,090 --> 01:13:58,700
Что мы собираемся быть желание сделать?

1481
01:13:58,700 --> 01:14:02,390
Так что сейчас, у нас есть
макс и мин, право,

1482
01:14:02,390 --> 01:14:04,962
вероятно, создана где-то здесь.

1483
01:14:04,962 --> 01:14:07,170
Мы собираемся, вероятно, хотите
найти середину, верно?

1484
01:14:07,170 --> 01:14:08,450
Как мы собираемся, чтобы быть
возможность найти середину?

1485
01:14:08,450 --> 01:14:09,491
Что mathematical--

1486
01:14:09,491 --> 01:14:11,079
АУДИТОРИЯ: Макс плюс мин разделены на 2.

1487
01:14:11,079 --> 01:14:11,870
ANDI Пэн: Точно.

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
Имеет ли это смысл?

1490
01:14:21,620 --> 01:14:25,780
И вы, ребята, понять, почему мы
не просто use--, почему мы сделали это

1491
01:14:25,780 --> 01:14:27,850
а не делать просто п делится на 2?

1492
01:14:27,850 --> 01:14:30,310
Это потому, что п является значение
что собирается остаться то же самое.

1493
01:14:30,310 --> 01:14:30,979
Правильно?

1494
01:14:30,979 --> 01:14:34,020
Но, как мы скорректируем нашу минимум и
Максимальные значения, они собираются изменить.

1495
01:14:34,020 --> 01:14:36,040
И в результате, наш средний
собирается менять слишком.

1496
01:14:36,040 --> 01:14:37,873
Так вот почему мы хотим
сделать это прямо здесь.

1497
01:14:37,873 --> 01:14:38,510
ХОРОШО.

1498
01:14:38,510 --> 01:14:41,600
>> А потом, в настоящее время, что
мы нашли our-- да.

1499
01:14:41,600 --> 01:14:44,270
>> АУДИТОРИЯ: Просто быстро question--
когда вы говорите, мин и макс,

1500
01:14:44,270 --> 01:14:46,410
мы предполагая, что
это уже отсортированы?

1501
01:14:46,410 --> 01:14:48,400
>> ANDI Пэн: Да, это на самом деле
предпосылкой для бинарного поиска,

1502
01:14:48,400 --> 01:14:49,816
что вы должны знать, что это сортируется.

1503
01:14:49,816 --> 01:14:53,660
Именно поэтому-то, вы пишете в вашем
Проблема установить до вашего бинарного поиска.

1504
01:14:53,660 --> 01:14:55,910
ХОРОШО.

1505
01:14:55,910 --> 01:14:58,876
Так что теперь мы знаем, где наша середина
является то, что вы хотите сделать здесь?

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> АУДИТОРИЯ: Мы хотим, чтобы сравнить
что к другому.

1508
01:15:04,319 --> 01:15:05,110
ANDI Пэн: Точно.

1509
01:15:05,110 --> 01:15:12,280
Таким образом, вы будете сравнивать
с середины до значения, не так ли?

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
И что это говорит
нам, когда мы сравниваем?

1512
01:15:18,670 --> 01:15:22,226
Что мы хотим делать дальше?

1513
01:15:22,226 --> 01:15:25,389
>> АУДИТОРИЯ: Если значение больше
чем середине, мы хотим, чтобы отрезать его.

1514
01:15:25,389 --> 01:15:26,180
ANDI Пэн: Точно.

1515
01:15:26,180 --> 01:15:33,940
Таким образом, если значение больше
чем середине, мы

1516
01:15:33,940 --> 01:15:36,550
захочет изменить эти
Минимальное и исчерпан, верно?

1517
01:15:36,550 --> 01:15:38,980
Что мы хотим изменить?

1518
01:15:38,980 --> 01:15:42,145
Так что, если мы знаем, что где-то значение
здесь, что вы у нас изменить?

1519
01:15:42,145 --> 01:15:44,758
Мы хотим изменить нашу
Минимальный быть в середине, не так ли?

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
А потом еще, если он находится в этом
половина, что мы хотим изменить?

1522
01:15:54,292 --> 01:15:55,306
>> АУДИТОРИЯ: Ваша максимальная.

1523
01:15:55,306 --> 01:15:55,972
ANDI Пэн: Да.

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
А потом вы просто
держать цикл, верно?

1526
01:16:04,680 --> 01:16:08,920
Потому что сейчас, после одной итерации
через, у вас есть макс здесь.

1527
01:16:08,920 --> 01:16:10,760
И тогда вы можете пересчитать середине.

1528
01:16:10,760 --> 01:16:11,990
И тогда вы можете сравнить.

1529
01:16:11,990 --> 01:16:14,766
И вы собираетесь продолжать
не до минут и Maxes

1530
01:16:14,766 --> 01:16:15,890
существенно сошлись.

1531
01:16:15,890 --> 01:16:17,890
И вот, когда вы знаете, что
Вы попали в конец.

1532
01:16:17,890 --> 01:16:20,280
И либо вы нашли его
или вы не в этой точке.

1533
01:16:20,280 --> 01:16:23,170
>> Имеет ли это смысл для всех?

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
ХОРОШО.

1536
01:16:26,770 --> 01:16:27,900
Это очень важно,
потому что вы будете иметь

1537
01:16:27,900 --> 01:16:29,760
чтобы написать это в коде сегодня.

1538
01:16:29,760 --> 01:16:32,660
Но вы, ребята, есть очень хороший
чувство, что вы должны делать,

1539
01:16:32,660 --> 01:16:34,051
и это хорошо.

1540
01:16:34,051 --> 01:16:34,550
ХОРОШО.

1541
01:16:34,550 --> 01:16:38,840
Итак, мы получили около семи
минуты осталось раздел.

1542
01:16:38,840 --> 01:16:43,170
Таким образом, мы будем говорить о
это PSET, что мы будем делать.

1543
01:16:43,170 --> 01:16:46,410
Таким образом, PSET разделен на две половины.

1544
01:16:46,410 --> 01:16:50,230
Первая половина включает
реализации находку

1545
01:16:50,230 --> 01:16:54,210
в котором Вы пишете, линейный поиск, А
бинарный поиск, и алгоритм сортировки.

1546
01:16:54,210 --> 01:16:56,690
>> Таким образом, это является первым
раз в PSET где

1547
01:16:56,690 --> 01:17:00,050
мы будем давать вам, ребята, что называется
Код распределения, который является код

1548
01:17:00,050 --> 01:17:02,740
что мы предварительно написано,
но просто оставили несколько кусков от

1549
01:17:02,740 --> 01:17:04,635
для Вас, чтобы закончить запись.

1550
01:17:04,635 --> 01:17:07,510
Таким образом, вы, ребята, когда вы смотрите на это
Код, вы могли бы получить действительно страшно.

1551
01:17:07,510 --> 01:17:08,630
Если вы просто хотите, Ах, я
не знаю, что делает,

1552
01:17:08,630 --> 01:17:11,670
Я не знаете, как, кажется, что
так сложно, ах, расслабиться.

1553
01:17:11,670 --> 01:17:12,170
Это нормально.

1554
01:17:12,170 --> 01:17:12,930
Читайте спецификацию.

1555
01:17:12,930 --> 01:17:16,920
Спецификация будет объяснить вам точно
что все эти программы делают.

1556
01:17:16,920 --> 01:17:20,560
>> Например, generate.c программа
что придет с вашего PSET.

1557
01:17:20,560 --> 01:17:24,060
Вы на самом деле не имеют к ней прикоснуться, но
Вы должны понимать, что он делает.

1558
01:17:24,060 --> 01:17:28,550
И generate.c, все это делает,
либо генерации случайных чисел

1559
01:17:28,550 --> 01:17:32,400
или вы можете дать ему семя, как у
условный номер, который он принимает,

1560
01:17:32,400 --> 01:17:34,140
и генерирует больше число.

1561
01:17:34,140 --> 01:17:37,170
Таким образом, есть определенный способ, чтобы
осуществить generate.c, в котором

1562
01:17:37,170 --> 01:17:42,760
вы можете просто сделать кучу цифр
для вас, чтобы проверить свои другие методы на.

1563
01:17:42,760 --> 01:17:45,900
>> Так что, если вы хотите, чтобы для
Например, проверить свои находки,

1564
01:17:45,900 --> 01:17:48,970
Вы хотели бы, чтобы запустить generate.c,
генерировать кучу цифр,

1565
01:17:48,970 --> 01:17:50,880
а затем запустить функцию помощников.

1566
01:17:50,880 --> 01:17:53,930
Ваша функция помощники где вы
на самом деле физически написания кода.

1567
01:17:53,930 --> 01:17:59,330
И думаю, помощников в виде файла библиотеки
Вы пишете, что находка звонит.

1568
01:17:59,330 --> 01:18:02,950
И так в течение helpers.c, вы будете
сделать поиска и сортировки.

1569
01:18:02,950 --> 01:18:06,500
>> И тогда вы будете по существу
просто положить их все вместе.

1570
01:18:06,500 --> 01:18:10,350
Спецификация скажет вам, как
положить, что в командной строке.

1571
01:18:10,350 --> 01:18:14,880
И вы сможете проверить, является ли
не ваша сортировки и поиска работают.

1572
01:18:14,880 --> 01:18:15,870
Круто.

1573
01:18:15,870 --> 01:18:18,720
Кто-нибудь уже началась, и
встречающиеся проблемы или вопросы

1574
01:18:18,720 --> 01:18:20,520
они имеют сейчас с этим?

1575
01:18:20,520 --> 01:18:21,020
ХОРОШО.

1576
01:18:21,020 --> 01:18:21,476
>> АУДИТОРИЯ: Подождите.

1577
01:18:21,476 --> 01:18:21,932
У меня есть вопрос.

1578
01:18:21,932 --> 01:18:22,844
>> ANDI Пэн: Да.

1579
01:18:22,844 --> 01:18:28,390
>> АУДИТОРИЯ: Так что я начал делать
линейный поиск в helpers.c

1580
01:18:28,390 --> 01:18:29,670
и это не было действительно работает.

1581
01:18:29,670 --> 01:18:34,590
Но потом я узнал, мы просто
должны удалить его и сделать бинарный поиск.

1582
01:18:34,590 --> 01:18:36,991
Так не все ли равно, если он не работает?

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI Пэн: Короткий ответ: нет.

1585
01:18:41,510 --> 01:18:42,642
Но так как мы не--

1586
01:18:42,642 --> 01:18:44,350
АУДИТОРИЯ: Но никто не
на самом деле проверки.

1587
01:18:44,350 --> 01:18:46,058
ANDI Пэн: Мы никогда не
увидите, что.

1588
01:18:46,058 --> 01:18:49,590
Но вы, вероятно, хотите, чтобы
что ваш поиск работы.

1589
01:18:49,590 --> 01:18:51,700
Потому что, если ваш линейный
поиск не работает,

1590
01:18:51,700 --> 01:18:54,410
то скорее всего, ваш бинарный
Поиск не будет работать, как хорошо.

1591
01:18:54,410 --> 01:18:56,646
Потому что у вас есть подобное
Логика в них обоих.

1592
01:18:56,646 --> 01:18:58,020
И нет, это не имеет значения.

1593
01:18:58,020 --> 01:19:01,300
Таким образом, единственными вы включите
в являются своего рода и бинарный поиск.

1594
01:19:01,300 --> 01:19:02,490
Да.

1595
01:19:02,490 --> 01:19:06,610
>> А также, много детей были
пытаясь собрать helpers.c.

1596
01:19:06,610 --> 01:19:09,550
Вы на самом деле не допускаются
чтобы сделать это, потому что helpers.c

1597
01:19:09,550 --> 01:19:11,200
не имеет основную функцию.

1598
01:19:11,200 --> 01:19:13,550
И поэтому вы должны только
быть на самом деле компиляции

1599
01:19:13,550 --> 01:19:18,670
генерировать и найти, потому что найти звонки
helpers.c и функции в ней.

1600
01:19:18,670 --> 01:19:20,790
Так что делает отладку
боль в заднице.

1601
01:19:20,790 --> 01:19:22,422
Но это то, что мы должны делать.

1602
01:19:22,422 --> 01:19:23,880
АУДИТОРИЯ: Вы просто сделать все, верно?

1603
01:19:23,880 --> 01:19:27,290
ANDI Пэн: вы можете просто
сделать все как хорошо, да.

1604
01:19:27,290 --> 01:19:28,060
ХОРОШО.

1605
01:19:28,060 --> 01:19:32,570
Так вот оно что в плане того, что
PSET просит, чтобы вы все делаете.

1606
01:19:32,570 --> 01:19:35,160
Если у вас есть какие-либо вопросы, пожалуйста,
свободным спросить мне после раздела.

1607
01:19:35,160 --> 01:19:37,580
Я буду здесь, как, 20 минут.

1608
01:19:37,580 --> 01:19:40,500
>> И да, Pset-х
действительно не так уж плохо.

1609
01:19:40,500 --> 01:19:41,680
Вы, ребята, должно быть в порядке.

1610
01:19:41,680 --> 01:19:43,250
Они, просто следуйте рекомендациям.

1611
01:19:43,250 --> 01:19:47,840
Вид есть чувство, по логике, то, что
должно происходить, и вы будете в порядке.

1612
01:19:47,840 --> 01:19:48,690
Не слишком страшно.

1613
01:19:48,690 --> 01:19:50,220
Там очень много кода
уже написано.

1614
01:19:50,220 --> 01:19:53,011
Не слишком страшно, если вы не
понять, что все это значит.

1615
01:19:53,011 --> 01:19:54,749
Если это много, это совершенно нормально.

1616
01:19:54,749 --> 01:19:55,790
И пришли к офисной часов.

1617
01:19:55,790 --> 01:19:57,520
Мы поможем вам взглянуть.

1618
01:19:57,520 --> 01:20:00,810
>> АУДИТОРИЯ: с дополнительными
Функции, мы смотрим те до?

1619
01:20:00,810 --> 01:20:03,417
>> ANDI Пэн: Да, те в коде.

1620
01:20:03,417 --> 01:20:05,750
В игре 15, половина из
это уже написана для вас.

1621
01:20:05,750 --> 01:20:09,310
Так что те функции
уже в коде.

1622
01:20:09,310 --> 01:20:12,020
Ага.

1623
01:20:12,020 --> 01:20:12,520
Все в порядке.

1624
01:20:12,520 --> 01:20:14,000
Ну, удачи.

1625
01:20:14,000 --> 01:20:15,180
Это отвратительно день.

1626
01:20:15,180 --> 01:20:19,370
Так надеюсь, вы, ребята, не чувствовать себя слишком
плохо о пребывании внутри и кодирования.

1627
01:20:19,370 --> 01:20:22,133