1
00:00:00,000 --> 00:00:02,570
[Powered by Google Translate] [Раздзел 3 - больш камфортнай]

2
00:00:02,570 --> 00:00:05,070
[Rob Боуден - Гарвардскі універсітэт]

3
00:00:05,070 --> 00:00:07,310
>> [Гэта CS50. - CS50.TV]

4
00:00:07,310 --> 00:00:12,700
>> Такім чынам, першы пытанне сфармулявана дзіўна.

5
00:00:12,700 --> 00:00:17,480
GDB дазваляе вам "адладка" праграмы, але, больш канкрэтна, што гэта дазволіць вам рабіць?

6
00:00:17,480 --> 00:00:22,590
Я адкажу, што адзін, і я не ведаю, што менавіта чакаў,

7
00:00:22,590 --> 00:00:27,910
такім чынам, я мяркую, што гэта нешта накшталт яна дазваляе крок за крокам

8
00:00:27,910 --> 00:00:31,540
ісці праз праграмы, ўзаемадзейнічаць з ім, змяняць зменныя, рабіць усе гэтыя рэчы -

9
00:00:31,540 --> 00:00:34,270
у асноўным цалкам кантраляваць выкананне праграмы

10
00:00:34,270 --> 00:00:38,410
і правяраць любой частцы выканання праграмы.

11
00:00:38,410 --> 00:00:43,030
Такім чынам, гэтыя функцыі дазваляюць адладжваць рэчы.

12
00:00:43,030 --> 00:00:44,830
Добра.

13
00:00:44,830 --> 00:00:50,520
Чаму бінарны пошук патрабуе, каб масіў будзе адсартаваны?

14
00:00:50,520 --> 00:00:53,360
Хто хоча адказаць?

15
00:00:56,120 --> 00:01:00,070
[Студэнт] Таму што ён не працуе, калі ён не сартуюцца. >> Так. [Смех]

16
00:01:00,070 --> 00:01:04,910
Калі гэта не адсартаваны, то немагчыма падзяліць яго напалову

17
00:01:04,910 --> 00:01:07,850
і ведаю, што ўсё, што лявей менш і ўсё, што правей

18
00:01:07,850 --> 00:01:10,490
больш сярэдняга значэння.

19
00:01:10,490 --> 00:01:12,790
Такім чынам, ён павінен быць адсартаваны.

20
00:01:12,790 --> 00:01:14,170
Добра.

21
00:01:14,170 --> 00:01:17,570
Чаму пузырьковый сартавання ў O п квадратаў?

22
00:01:17,570 --> 00:01:23,230
Хто-небудзь спачатку хачу даць вельмі хуткі высокім узроўні агляд таго, што бурбалка сартавання?

23
00:01:25,950 --> 00:01:33,020
[Студэнт] Вы ў асноўным ідуць праз кожны элемент, і вы праверыць некалькі першых элементаў.

24
00:01:33,020 --> 00:01:37,150
Калі яны з таго, дзе вы памяняць іх месцамі, то праверце наступныя некалькі элементаў і гэтак далей.

25
00:01:37,150 --> 00:01:40,770
Калі вы дойдзеце да канца, то вы ведаеце, што найбольшы элемент змяшчаецца ў канцы,

26
00:01:40,770 --> 00:01:42,750
так што вы ігнаруеце, што адзін, то вы працягвайце ісці да канца,

27
00:01:42,750 --> 00:01:48,490
і кожны раз вы павінны праверыць адзін элемент менш, пакуль вы не ўносіць ніякіх зменаў. >> Так.

28
00:01:48,490 --> 00:01:58,470
Гэта называецца пузырьковый сартавання, таму што калі перавярнуць масіў на бок, дык гэта ўверх і ўніз па вертыкалі,

29
00:01:58,470 --> 00:02:03,100
Затым вялікіх значэннях будзе апускацца на дно і малых значэнняў будзе тапырыцца да самага верху.

30
00:02:03,100 --> 00:02:05,210
Вось як ён атрымаў сваю назву.

31
00:02:05,210 --> 00:02:08,220
І так, вы проста праходзьце.

32
00:02:08,220 --> 00:02:11,190
Вы працягваеце праз масіў, памяняўшы большае значэнне

33
00:02:11,190 --> 00:02:14,040
Для атрымання найбольшых значэнняў на дно.

34
00:02:14,040 --> 00:02:17,500
>> Чаму гэта O п квадратаў?

35
00:02:18,690 --> 00:02:24,620
Па-першае, хто-небудзь хачу сказаць, чаму гэта O п квадратаў?

36
00:02:24,620 --> 00:02:28,760
[Студэнт] Таму што для кожнага прагону ён ідзе п раз.

37
00:02:28,760 --> 00:02:32,100
Вы можаце быць упэўнены, што Вы зрабілі важнейшы элемент ўвесь шлях уніз,

38
00:02:32,100 --> 00:02:35,230
Затым вам прыйдзецца паўтарыць, што для, як многія элементы. >> Так.

39
00:02:35,230 --> 00:02:41,800
Так што майце на ўвазе, што вялікая O азначае і тое, што вялікія сродкі Omega.

40
00:02:41,800 --> 00:02:50,560
The Big O, як верхняя мяжа аб тым, як павольна ён можа рэальна працаваць.

41
00:02:50,560 --> 00:02:58,990
Так, кажучы, што гэта O п квадрат, гэта не пра п інакш яна была б у стане кіраваць

42
00:02:58,990 --> 00:03:02,640
У лінейным часу, але гэта O п кубе

43
00:03:02,640 --> 00:03:06,390
таму што яна абмежаваная O п куб.

44
00:03:06,390 --> 00:03:12,300
Калі гэта абмежаваная O п квадрат, то гэта абмежаваная таксама на п куб.

45
00:03:12,300 --> 00:03:20,280
Так што п у квадраце, а ў абсалютнай горшым выпадку ён не можа рабіць лепш, чым N ў квадраце,

46
00:03:20,280 --> 00:03:22,830
Менавіта таму гэта O п квадрат.

47
00:03:22,830 --> 00:03:31,200
Такім чынам, каб убачыць невялікае матэматыцы, як яна выходзіць, каб быць паказаны ў квадраце,

48
00:03:31,200 --> 00:03:40,530
калі ў нас ёсць пяць рэчаў у нашым спісе, у першы раз, колькі свопов мы маглі б патэнцыйна трэба зрабіць

49
00:03:40,530 --> 00:03:47,170
для таго, каб атрымаць? Давайце на самай справе проста -

50
00:03:47,170 --> 00:03:52,040
Колькі свопы мы будзем мець, каб зрабіць у першым запуску пузырьковый сартавання ў масіве?

51
00:03:52,040 --> 00:03:53,540
[Студэнт] п - 1. >> Так.

52
00:03:53,540 --> 00:03:58,340
>> Калі ёсць 5 элементаў, мы збіраемся трэба зрабіць п - 1.

53
00:03:58,340 --> 00:04:01,100
Тады на другім колькі свопов мы будзем мець, каб зрабіць?

54
00:04:01,100 --> 00:04:03,440
[Студэнт] п - 2. >> Так.

55
00:04:03,440 --> 00:04:11,640
І трэці будзе п - 3, а затым для выгоды я буду пісаць у апошнія два

56
00:04:11,640 --> 00:04:15,270
як і тады, мы збіраемся трэба зрабіць 2 перастановак і 1 падпампоўкі.

57
00:04:15,270 --> 00:04:19,899
Я мяркую, што апошняя можа ці не можа фактычна павінны адбыцца.

58
00:04:19,899 --> 00:04:22,820
Гэта своп? Я не ведаю.

59
00:04:22,820 --> 00:04:26,490
Так што гэта агульная сума свопов або па крайняй меры параўнанняў вы павінны зрабіць.

60
00:04:26,490 --> 00:04:29,910
Нават калі вы не памяняць, вам усё яшчэ трэба параўнаць значэння.

61
00:04:29,910 --> 00:04:33,910
Такім чынам, існуе п - 1 параўнанняў у першыя праходзяць праз масіў.

62
00:04:33,910 --> 00:04:42,050
Калі пераставіць гэтыя рэчы, давайце самай справе зрабіць гэта шэсць рэчаў, так што ўсё складаецца добра,

63
00:04:42,050 --> 00:04:44,790
і тады я зраблю 3, 2, 1.

64
00:04:44,790 --> 00:04:49,910
Так што проста перастаўляючы гэтыя сумы, мы хочам, каб бачыць, як шмат параўнанняў мы робім

65
00:04:49,910 --> 00:04:52,700
ва ўсім алгарытме.

66
00:04:52,700 --> 00:04:56,550
Такім чынам, калі мы прынясем гэтыя хлопцы тут,

67
00:04:56,550 --> 00:05:07,470
Затым мы яшчэ раз падводзячы аднак шмат параўнанняў было.

68
00:05:07,470 --> 00:05:13,280
Але калі мы сумуецца гэтыя і прасумаваць гэтыя і прасумаваць гэтыя,

69
00:05:13,280 --> 00:05:18,130
яна па-ранейшаму такая ж праблема. Мы проста падвесці тых канкрэтных груп.

70
00:05:18,130 --> 00:05:22,400
>> Такім чынам, зараз мы падводзячы N 3 ст. Гэта не толькі 3 N.

71
00:05:22,400 --> 00:05:27,650
Гэта заўсёды будзе п / 2 N.

72
00:05:27,650 --> 00:05:29,430
І вось мы, здараецца, ёсць 6.

73
00:05:29,430 --> 00:05:34,830
Калі б мы мелі 10 рэчаў, то мы маглі б зрабіць гэтую групоўку на 5 розных пар рэчы

74
00:05:34,830 --> 00:05:37,180
і ў канчатковым выніку з N + N + N + N + N.

75
00:05:37,180 --> 00:05:45,840
Такім чынам, вы заўсёды будзеце атрымліваць п / 2 п, і так гэта мы будзем запісваць яго на п квадрат / 2.

76
00:05:45,840 --> 00:05:48,890
І хоць гэта фактар ​​паловы, якія, здараецца, прыходзяць у

77
00:05:48,890 --> 00:05:54,190
у сувязі з тым, што праз кожную ітэрацыю па масіве мы параўнаем 1 менш

78
00:05:54,190 --> 00:05:58,040
так што, як мы атрымаем больш за 2, але ён па-ранейшаму п квадрат.

79
00:05:58,040 --> 00:06:01,650
Мы не клапоцімся аб пастаянным фактары паловы.

80
00:06:01,650 --> 00:06:07,760
Так шмат вялікіх рэчаў O, як гэта належыць толькі на выгляд рабіць такога роду матэматыка,

81
00:06:07,760 --> 00:06:12,260
арыфметычных сум і геаметрычныя матэрыял серыі,

82
00:06:12,260 --> 00:06:17,750
але большасць з іх у гэтым курсе даволі простая.

83
00:06:17,750 --> 00:06:19,290
Добра.

84
00:06:19,290 --> 00:06:24,430
Чаму сартавання устаўкай ў Omega п? Што амега значыць?

85
00:06:24,430 --> 00:06:27,730
[Двух студэнтаў казаць адразу - неразборліва] >> Так.

86
00:06:27,730 --> 00:06:30,630
Omega вы можаце думаць аб якасці ніжняй мяжы.

87
00:06:30,630 --> 00:06:36,550
>> Таму незалежна ад таго, наколькі эфектыўна ваша ўстаўкі Алгарытм сартавання,

88
00:06:36,550 --> 00:06:41,810
незалежна ад таго, спіс, які перадаецца, ён заўсёды мае параўнаць па крайняй меры п рэчаў

89
00:06:41,810 --> 00:06:44,620
ці яно мае для перабору п рэчаў.

90
00:06:44,620 --> 00:06:47,280
Чаму гэта адбываецца?

91
00:06:47,280 --> 00:06:51,190
[Студэнт] Таму што, калі спіс ужо адсартаваны, то праз першую ітэрацыю

92
00:06:51,190 --> 00:06:54,080
Вы можаце гарантаваць, што самы першы элемент з'яўляецца крайняй меры,

93
00:06:54,080 --> 00:06:56,490
і другі ітэрацыі можна гарантаваць толькі першыя два

94
00:06:56,490 --> 00:07:00,010
таму што вы не ведаеце, што астатняй спіс адсартаваны. >> Так.

95
00:07:00,010 --> 00:07:08,910
Калі вы перадаеце ў цалкам адсартаваны спіс, па меншай меры, вы павінны ісці па ўсіх элементах

96
00:07:08,910 --> 00:07:12,180
бачыць, што нічога не трэба перамяшчаць.

97
00:07:12,180 --> 00:07:14,720
Такім чынам, якія праходзяць па спісе і кажуць о, гэта ўжо адсартаваныя,

98
00:07:14,720 --> 00:07:18,240
гэта немагчыма, каб вы ведалі, што гэта спарадкаваныя, пакуль вы праверыць кожны элемент

99
00:07:18,240 --> 00:07:20,660
, Каб убачыць, што яны ў вызначаным парадку.

100
00:07:20,660 --> 00:07:25,290
Такім чынам, ніжняя мяжа ўстаўкі сартавання Omega н.

101
00:07:25,290 --> 00:07:28,210
Тое, што ў горшым выпадку час працы сартавання зліццём,

102
00:07:28,210 --> 00:07:31,390
горшым выпадку быць вялікім O зноў?

103
00:07:31,390 --> 00:07:37,660
Такім чынам, у горшым выпадку, як жа сартаванне зліццём бегчы?

104
00:07:42,170 --> 00:07:43,690
[Студэнт] N часопіс п. >> Так.

105
00:07:43,690 --> 00:07:49,990
Самы хуткі агульныя алгарытмы сартавання з'яўляюцца п § п. Вы не можаце зрабіць лепш.

106
00:07:51,930 --> 00:07:55,130
>> Існуюць адмысловыя выпадкі, і калі ў нас ёсць час сёння, - але мы, верагодна won't -

107
00:07:55,130 --> 00:07:59,330
мы маглі бачыць той, які робіць лепш, чым п § п.

108
00:07:59,330 --> 00:08:04,050
Але ў агульным выпадку, вы не можаце зрабіць лепш, чым п § п.

109
00:08:04,050 --> 00:08:09,680
І сартаванне зліццём, здараецца, якую вы павінны ведаць, для гэтага, вядома, што п § п.

110
00:08:09,680 --> 00:08:13,260
І таму мы фактычна ажыццяўленні гэтага сёння.

111
00:08:13,260 --> 00:08:18,070
І, нарэшце, не больш чым у трох сказах, як працуе выбару роду?

112
00:08:18,070 --> 00:08:20,370
Хіба хто-небудзь хоча, каб адказаць, і я буду лічыць вашы прапановы

113
00:08:20,370 --> 00:08:22,390
таму што калі вы ідзяце на працягу 3 -

114
00:08:25,530 --> 00:08:28,330
Хто-небудзь памятае выбар роду?

115
00:08:31,280 --> 00:08:37,809
Выбар роду, як правіла, даволі лёгка запомніць, проста з назвы.

116
00:08:37,809 --> 00:08:45,350
Вы проста перабор масіва, знайсці тое, што найбольшае значэнне з'яўляецца або маленькі -

117
00:08:45,350 --> 00:08:47,290
незалежна ад таго, вы сартавання цалі

118
00:08:47,290 --> 00:08:50,750
Так скажам мы сартаванне ад меншага да большага.

119
00:08:50,750 --> 00:08:55,250
Вы ітэрацыі па масіве, гледзячы на ​​ўсё, што мінімальны элемент,

120
00:08:55,250 --> 00:08:59,750
, Вылучыце яе, а затым проста замяніць яго тое, што на першае месца.

121
00:08:59,750 --> 00:09:04,090
І тады на другім праходзе па масіве, звернеце ўвагу на мінімальны элемент зноў,

122
00:09:04,090 --> 00:09:07,490
, Вылучыце яе, а затым памяняць яго з тым, што на другой пазіцыі.

123
00:09:07,490 --> 00:09:10,650
Так што мы проста выбіраючы, мінімальныя значэння

124
00:09:10,650 --> 00:09:16,050
і ўстаўляючы іх у пярэдняй частцы масіва, пакуль не будзе адсартаваны.

125
00:09:19,210 --> 00:09:21,560
Пытанняў з гэтай нагоды?

126
00:09:21,560 --> 00:09:25,710
>> Гэта непазбежна з'яўляюцца ў формах вы павінны запоўніць, калі вы адпраўляеце PSET.

127
00:09:29,010 --> 00:09:32,360
Гэта ў асноўным адказы на іх.

128
00:09:32,360 --> 00:09:34,230
Такім чынам, цяпер праблемы з кадаваньне.

129
00:09:34,230 --> 00:09:40,140
Я ўжо разаслаў па электроннай пошце - Хто-небудзь не атрымаеце гэты ліст? Добра.

130
00:09:40,140 --> 00:09:46,630
Я ўжо разаслаў па электроннай пошце прастору, якое мы збіраемся выкарыстаць,

131
00:09:46,630 --> 00:09:52,120
і калі вы пстрыкніце на маё імя, - так што я думаю, што я збіраюся быць на дне

132
00:09:52,120 --> 00:09:57,170
з-за назад г - але калі вы націснеце на маё імя, вы ўбачыце 2 рэвізіі.

133
00:09:57,170 --> 00:10:02,650
1-я рэдакцыя збіраецца быць я ўжо скапіявалі і ўставілі код у прасторах

134
00:10:02,650 --> 00:10:06,900
для пошуку, што вам прыйдзецца выконваць.

135
00:10:06,900 --> 00:10:10,540
І Перагляд 2 будзе сартаваць рэчы, якія мы рэалізуем пасля гэтага.

136
00:10:10,540 --> 00:10:15,770
Такім чынам, вы можаце націснуць на мой Перагляд 1 і працаваць там.

137
00:10:17,350 --> 00:10:22,060
А зараз мы хочам рэалізаваць бінарны пошук.

138
00:10:22,060 --> 00:10:26,470
>> Хто-небудзь хоча, каб проста даць псевдокод высокага ўзроўню тлумачэння

139
00:10:26,470 --> 00:10:31,440
пра тое, што мы збіраемся трэба зрабіць для пошуку? Так.

140
00:10:31,440 --> 00:10:36,170
[Студэнт] Вы проста бераце сярэдзіне масіва і паглядзець, калі тое, што вы шукаеце

141
00:10:36,170 --> 00:10:38,650
менш, чым ці больш.

142
00:10:38,650 --> 00:10:41,080
І калі гэта менш, вы ідзяце ў палову, што гэта менш,

143
00:10:41,080 --> 00:10:44,750
а калі больш, вы ідзяце ў палову больш, і вы паўтарыць, што, пакуль вы не проста атрымаеце адну рэч.

144
00:10:44,750 --> 00:10:46,570
[Боуден] Так.

145
00:10:46,570 --> 00:10:51,320
Звярніце ўвагу, што нашы нумары масіў ўжо адсартаваны,

146
00:10:51,320 --> 00:10:57,190
і так гэта азначае, што мы можам скарыстацца тым, што і мы маглі б спачатку праверыць,

147
00:10:57,190 --> 00:11:00,390
Добра, я шукаю нумар 50.

148
00:11:00,390 --> 00:11:03,720
Такім чынам, я магу пайсці ў сярэдзіну.

149
00:11:03,720 --> 00:11:07,380
Блізкі цяжка вызначыць, калі гэта цотная колькасць рэчаў,

150
00:11:07,380 --> 00:11:10,820
але давайце проста сказаць, што мы заўсёды будзем абрэзаць да сярэдзіны.

151
00:11:10,820 --> 00:11:14,420
Так што тут у нас ёсць 8 рэчаў, так што сярэдняя будзе 16.

152
00:11:14,420 --> 00:11:17,330
Я шукаю 50, так 50 гэта больш, чым 16.

153
00:11:17,330 --> 00:11:21,310
Так што цяпер я ў прынцыпе можа ставіцца да маіх масіў гэтых элементаў.

154
00:11:21,310 --> 00:11:23,450
Я магу выкінуць усе з 16 больш.

155
00:11:23,450 --> 00:11:27,440
Цяпер мой масіў менавіта гэтыя 4 элемента, і я паўтару.

156
00:11:27,440 --> 00:11:31,910
Дык вось я хачу знайсці сярэдзіну зноў, што будзе 42.

157
00:11:31,910 --> 00:11:34,730
42 менш за 50, так што я магу выкінуць гэтыя два элемента.

158
00:11:34,730 --> 00:11:36,890
Гэта мая астатняя масіва.

159
00:11:36,890 --> 00:11:38,430
Я збіраюся знайсці сярэдзіну зноў.

160
00:11:38,430 --> 00:11:42,100
Я думаю, 50 быў дрэнны прыклад, таму што я заўсёды выкідваць рэчы налева,

161
00:11:42,100 --> 00:11:48,280
але па той жа мерай, калі я шукаў нешта

162
00:11:48,280 --> 00:11:52,100
і гэта менш, чым элемент У цяперашні час я гляджу,

163
00:11:52,100 --> 00:11:55,080
Затым я збіраюся выкінуць усё, што правей.

164
00:11:55,080 --> 00:11:58,150
Такім чынам, зараз мы павінны рэалізаваць гэта.

165
00:11:58,150 --> 00:12:02,310
Звярніце ўвагу, што мы павінны перадаць у памерах.

166
00:12:02,310 --> 00:12:06,730
Мы можам таксама не трэба жорстка памер кода.

167
00:12:06,730 --> 00:12:11,640
Таму, калі мы пазбавімся ад # вызначыць -

168
00:12:19,630 --> 00:12:21,430
Добра.

169
00:12:21,430 --> 00:12:27,180
Як я магу добра зразумець, што памер масіва нумароў у цяперашні час?

170
00:12:27,180 --> 00:12:30,950
>> Колькі элементаў у масіве лікаў?

171
00:12:30,950 --> 00:12:33,630
[Студэнт] Лічбы, кранштэйны,. Даўжыня?

172
00:12:33,630 --> 00:12:36,600
[Боуден], якога не існуе ў C.

173
00:12:36,600 --> 00:12:38,580
Вам трэба. Даўжыні.

174
00:12:38,580 --> 00:12:42,010
Масівы не маюць ўласцівасці, таму няма Даўжыня ўласцівасць масіваў

175
00:12:42,010 --> 00:12:45,650
што будзе проста даць вам як бы доўга яно адбудзецца, будзе.

176
00:12:48,180 --> 00:12:51,620
[Студэнт] Глядзіце, колькі памяці яна мае і падзяліць на колькі - >> Так.

177
00:12:51,620 --> 00:12:55,810
Так як мы можам паглядзець, колькі памяці яна мае? >> [Студэнт] Sizeof. >> Так, SizeOf.

178
00:12:55,810 --> 00:13:01,680
Sizeof з'яўляецца аператарам, які збіраецца вярнуць памер масіва лікаў.

179
00:13:01,680 --> 00:13:10,060
І гэта будзе, аднак многія цэлыя Ёсць моманты, памер цэлага

180
00:13:10,060 --> 00:13:14,050
так гэта тое, колькі памяці яна на самай справе займаюць.

181
00:13:14,050 --> 00:13:17,630
Так што, калі я хачу, каб колькасць рэчаў у масіве,

182
00:13:17,630 --> 00:13:20,560
Затым я збіраюся хочуць падзяліць на памер цэлага ліку.

183
00:13:22,820 --> 00:13:26,010
Добра. Так, што дазваляе мне прайсці ў памеры тут.

184
00:13:26,010 --> 00:13:29,430
Чаму я павінен прайсці ў памеры наогул?

185
00:13:29,430 --> 00:13:38,570
Чаму я не магу так проста зрабіць тут Int памер = SizeOf (стозе сена) / SizeOf (INT)?

186
00:13:38,570 --> 00:13:41,490
Чаму гэта не працуе?

187
00:13:41,490 --> 00:13:44,470
[Студэнт] Гэта не глабальная зменная.

188
00:13:44,470 --> 00:13:51,540
[Боуден] Haystack існуе, і мы перадаем у лічбах, як стог сена,

189
00:13:51,540 --> 00:13:54,700
і гэта накшталт прадвесце таго, што павінна прыйсці. Так.

190
00:13:54,700 --> 00:14:00,170
[Студэнт] Haystack гэта толькі спасылка на яго, так што ён вернецца, наколькі вялікі, што спасылка.

191
00:14:00,170 --> 00:14:02,150
Так.

192
00:14:02,150 --> 00:14:09,000
Я сумняваюся, што ў лекцыі, што вы бачылі ў стэк яшчэ на самай справе, ці не так?

193
00:14:09,000 --> 00:14:11,270
Мы толькі што гаварылі пра гэта.

194
00:14:11,270 --> 00:14:16,090
Такім чынам, стэк, дзе ўсе вашы зменныя будуць захаваны.

195
00:14:16,090 --> 00:14:19,960
>> Любая памяць якая вылучаецца для лакальных зменных ідзе ў стэк,

196
00:14:19,960 --> 00:14:24,790
і кожная функцыя атрымлівае сваё ўласнае прастору ў стэку, яго ўласны кадр стэка, як гэта называецца.

197
00:14:24,790 --> 00:14:31,590
Такім чынам, асноўная мае свой стэк, а ўнутры яго будзе існаваць гэты нумар масіва,

198
00:14:31,590 --> 00:14:34,270
і яна будзе памерам SizeOf (нумары).

199
00:14:34,270 --> 00:14:38,180
Гэта будзе мець памер лікаў, падзеленых па памеры элементаў,

200
00:14:38,180 --> 00:14:42,010
але, што ўсё жыве ў кадры стэка асноўнага аўтара.

201
00:14:42,010 --> 00:14:45,190
Калі мы выклікаем пошук, пошук атрымлівае уласны фрэйм ​​стэка,

202
00:14:45,190 --> 00:14:48,840
сваё ўласнае прастору для захоўвання ўсіх сваіх лакальных зменных.

203
00:14:48,840 --> 00:14:56,420
Але гэтыя аргументы - так стозе сена не з'яўляецца копіяй гэтага ўвесь масіў.

204
00:14:56,420 --> 00:15:00,990
Мы не перадаем ва ўсім масіве ў выглядзе копіі ў пошуку.

205
00:15:00,990 --> 00:15:04,030
Ён проста перадае спасылку на гэты масіў.

206
00:15:04,030 --> 00:15:11,470
Такім чынам, пошук можа атрымаць доступ да гэтыя лічбы праз гэтую спасылку.

207
00:15:11,470 --> 00:15:17,100
Ён па-ранейшаму доступ да рэчах, якія жывуць ўнутры стэка асноўнага аўтара,

208
00:15:17,100 --> 00:15:22,990
але ў асноўным, калі мы дабяромся да паказальнікаў, якія павінны быць у бліжэйшы час,

209
00:15:22,990 --> 00:15:24,980
гэта тое, што паказальнікі.

210
00:15:24,980 --> 00:15:29,400
Паказальнікі з'яўляюцца проста спасылкамі на рэчы, і вы можаце выкарыстоўваць паказальнікі для доступу да рэчы

211
00:15:29,400 --> 00:15:32,030
, Якія ў рамках іншых рэчаў »стэка.

212
00:15:32,030 --> 00:15:37,660
Таму, нават калі нумар з'яўляецца лакальным для асноўнага, мы ўсё яшчэ можам атрымаць да яго доступ праз гэты паказальнік.

213
00:15:37,660 --> 00:15:41,770
Але так як гэта проста паказальнік, і гэта проста спасылка,

214
00:15:41,770 --> 00:15:45,040
SizeOf (стозе сена) проста вяртае памер самой спасылкі.

215
00:15:45,040 --> 00:15:47,950
Ён не вяртае памер рэч, гэта паказвае.

216
00:15:47,950 --> 00:15:51,110
Ён не вяртае рэальны памер нумароў.

217
00:15:51,110 --> 00:15:55,660
І такім чынам, гэта не будзе працаваць, як мы хочам.

218
00:15:55,660 --> 00:15:57,320
>> Пытанняў з гэтай нагоды?

219
00:15:57,320 --> 00:16:03,250
Паказальнікі ўжо не будзе ў значна больш падрабязна ў горы тыдня.

220
00:16:06,750 --> 00:16:13,740
І менавіта таму многія рэчы, якія вы бачыце, большасць рэчаў, пошуку і сартаванні рэчаў,

221
00:16:13,740 --> 00:16:16,990
яны амаль усе будзеце мець патрэбу, каб прыняць рэальны памер масіва,

222
00:16:16,990 --> 00:16:20,440
таму што ў C, мы паняцця не маем, што памер масіва.

223
00:16:20,440 --> 00:16:22,720
Вам трэба ўручную перадаць яго цалі

224
00:16:22,720 --> 00:16:27,190
І вы не можаце ўручную перадаць ва ўсім масіве, таму што вы проста праходзілі ў спасылку

225
00:16:27,190 --> 00:16:30,390
і ён не можа атрымаць памер з спасылкі.

226
00:16:30,390 --> 00:16:32,300
Добра.

227
00:16:32,300 --> 00:16:38,160
Такім чынам, зараз мы хочам, каб ажыццявіць тое, што было растлумачана раней.

228
00:16:38,160 --> 00:16:41,530
Вы можаце працаваць на ім на працягу хвіліны,

229
00:16:41,530 --> 00:16:45,250
і вам не прыйдзецца турбавацца аб тым, каб усе выдатна 100% рабочы.

230
00:16:45,250 --> 00:16:51,410
Проста напішыце да паловы псевдокод, як вы думаеце, яна павінна працаваць.

231
00:16:52,000 --> 00:16:53,630
Добра.

232
00:16:53,630 --> 00:16:56,350
Не трэба быць цалкам зрабіць з гэтым пакуль няма.

233
00:16:56,350 --> 00:17:02,380
Але хто-небудзь адчуваць сябе камфортна з тым, што яны да гэтага часу,

234
00:17:02,380 --> 00:17:05,599
як тое, што мы можам працаваць з разам?

235
00:17:05,599 --> 00:17:09,690
Хто-небудзь хоча стаць валанцёрам? Ці я выпадкова абраць.

236
00:17:12,680 --> 00:17:18,599
Гэта не павінна быць права на любыя меры, але сёе-тое мы можам змяніць у працоўным стане.

237
00:17:18,599 --> 00:17:20,720
[Студэнт] Вядома. >> Добра.

238
00:17:20,720 --> 00:17:27,220
Такім чынам, вы можаце зэканоміць перагляду, націснуўшы на маленькую абразок Захаваць.

239
00:17:27,220 --> 00:17:29,950
Ты Ramya, дакладна? >> [Студэнт] Так. >> [Боуден] Добра.

240
00:17:29,950 --> 00:17:35,140
Так што цяпер я магу праглядаць перагляду і кожны можа пацягнуць перагляду.

241
00:17:35,140 --> 00:17:38,600
І тут мы маем - Добра.

242
00:17:38,600 --> 00:17:43,160
Так Ramya пайшоў з рэкурсіўнае рашэнне, якое, безумоўна, правільнае рашэнне.

243
00:17:43,160 --> 00:17:44,970
Ёсць два шляхі вы можаце зрабіць з гэтай праблемай.

244
00:17:44,970 --> 00:17:48,060
Вы можаце зрабіць гэта итеративно або рэкурсіўна.

245
00:17:48,060 --> 00:17:53,860
Большасць праблем, вы выявіце, што можна зрабіць рэкурсіўна таксама можа быць зроблена итеративно.

246
00:17:53,860 --> 00:17:58,510
Дык вось мы зрабілі гэта рэкурсіўна.

247
00:17:58,510 --> 00:18:03,730
>> У каго-небудзь хачу, каб вызначыць, што значыць зрабіць функцыю рэкурсіўнай?

248
00:18:07,210 --> 00:18:08,920
[Студэнт] Калі ў вас ёсць функцыя выклікае сама сябе

249
00:18:08,920 --> 00:18:13,470
, А затым называць сябе, пакуль ён выйдзе з сапраўдным і верным. >> Так.

250
00:18:13,470 --> 00:18:17,680
Рэкурсіўная функцыя гэта проста функцыя, якая называе сябе.

251
00:18:17,680 --> 00:18:24,140
Ёсць тры вялікіх рэчаў, якія рэкурсіўная функцыя павінна быць.

252
00:18:24,140 --> 00:18:27,310
Па-першае, відавочна, гэта выклікае сама сябе.

253
00:18:27,310 --> 00:18:29,650
Другі базавы варыянт.

254
00:18:29,650 --> 00:18:33,390
Так што ў нейкі момант функцыя павінна спыніць называць сябе,

255
00:18:33,390 --> 00:18:35,610
і гэта тое, што базавы варыянт прызначаны для.

256
00:18:35,610 --> 00:18:43,860
Такім чынам, мы ведаем, што мы павінны спыніцца, мы павінны адмовіцца ад нашай пошуку

257
00:18:43,860 --> 00:18:48,150
пры запуску роўная канца - і мы пойдзем па тым, што гэта значыць.

258
00:18:48,150 --> 00:18:52,130
Але, нарэшце, апошняя рэч, якая важная для рэкурсіўных функцый:

259
00:18:52,130 --> 00:18:59,250
Функцыі павінны неяк наблізіцца да базавых сцэнарам.

260
00:18:59,250 --> 00:19:04,140
Падобна гэтаму, калі вы на самой справе не ўсё абнаўлення, калі вы рабіць другі рэкурсіўны выклік,

261
00:19:04,140 --> 00:19:07,880
калі вы літаральна толькі выклікам функцыі зноў з тымі ж аргументамі

262
00:19:07,880 --> 00:19:10,130
і ніякіх глабальных зменных былі змененыя або нічога,

263
00:19:10,130 --> 00:19:14,430
вы ніколі не дасягнеце базавы варыянт, у гэтым выпадку, што гэта дрэнна.

264
00:19:14,430 --> 00:19:17,950
Гэта будзе бясконцая Рэкурсія і перапаўнення стэка.

265
00:19:17,950 --> 00:19:24,330
Але тут мы бачым, што абнаўленне адбываецца, паколькі мы абнаўляем пачатак канца + / 2,

266
00:19:24,330 --> 00:19:28,180
мы абнаўляем канцы аргументам тут, мы абнаўляем пачатку аргументам тут.

267
00:19:28,180 --> 00:19:32,860
Такім чынам, ва ўсіх рэкурсіўных выклікаў мы абнаўляем нешта. Добра.

268
00:19:32,860 --> 00:19:38,110
Вы хочаце ісці з намі праз ваша рашэнне? >> Вядома.

269
00:19:38,110 --> 00:19:44,270
Я выкарыстоўваю SearchHelp так, што кожны раз, калі я раблю выклік гэтай функцыі

270
00:19:44,270 --> 00:19:47,910
У мяне ёсць пачатак, дзе я шукаю ў масіве і ў канцы

271
00:19:47,910 --> 00:19:49,380
, Дзе я шукаю масіва.

272
00:19:49,380 --> 00:19:55,330
>> На кожным кроку, дзе ён кажа, што гэта сярэдні элемент, які з'яўляецца пачаткам канца + / 2,

273
00:19:55,330 --> 00:19:58,850
, Што роўна таго, што мы шукаем?

274
00:19:58,850 --> 00:20:04,650
І калі гэта так, то мы яго знайшлі, і я думаю, што перадаецца да ўзроўню рэкурсіі.

275
00:20:04,650 --> 00:20:12,540
І калі гэта не так, то мы правяраем, што сярэдняе значэнне масіва занадта вялікі,

276
00:20:12,540 --> 00:20:19,320
У гэтым выпадку мы глядзім на левай палове масіва, ідучы ад пачатку і да сярэдзіны азначніка.

277
00:20:19,320 --> 00:20:22,710
А ў адваротным выпадку мы робім у канцы тайма.

278
00:20:22,710 --> 00:20:24,740
[Боуден] Добра.

279
00:20:24,740 --> 00:20:27,730
Гучыць нядрэнна.

280
00:20:27,730 --> 00:20:36,640
Такім чынам, пару рэчаў, а на самай справе, гэта вельмі высокім узроўні рэч

281
00:20:36,640 --> 00:20:41,270
што вы ніколі не павінны ведаць, для гэтага, вядома, але гэта праўда.

282
00:20:41,270 --> 00:20:46,080
Рэкурсіўнага функцыі, вы заўсёды чуеце, што яны дрэнна справа

283
00:20:46,080 --> 00:20:51,160
таму што калі вы рэкурсіўна называць сябе занадта шмат разоў, вы атрымаеце перапаўненне стэка

284
00:20:51,160 --> 00:20:54,990
, Паколькі, як я ўжо казаў, кожная функцыя атрымлівае уласны фрэйм ​​стэка.

285
00:20:54,990 --> 00:20:59,500
Такім чынам, кожны выклік рэкурсіўнай функцыі атрымлівае уласны фрэйм ​​стэка.

286
00:20:59,500 --> 00:21:04,140
Так што калі вы зробіце 1000 рэкурсіўных выклікаў, вы атрымліваеце 1000 кадраў стэка,

287
00:21:04,140 --> 00:21:08,390
і хутка вы прывесці да таго, занадта шмат кадраў стэка і рэчы проста зламаць.

288
00:21:08,390 --> 00:21:13,480
Дык вось чаму рэкурсіўнага функцыі, як правіла, дрэнна.

289
00:21:13,480 --> 00:21:19,370
Але ёсць і добрыя падмноства рэкурсіўных функцый называецца хвастом рэкурсіўных функцый,

290
00:21:19,370 --> 00:21:26,120
і гэта здараецца, напрыклад, адной, дзе, калі кампілятар заўважае гэта

291
00:21:26,120 --> 00:21:29,920
і ён павінен, я думаю, - у Clang, калі вы перадаеце яго сцяг-O2

292
00:21:29,920 --> 00:21:33,250
то заўважыце, што гэта хвост рэкурсіўнага і зрабіць усё добра.

293
00:21:33,250 --> 00:21:40,050
>> Ён будзе выкарыстоўваць той жа кадр стэка зноў і зноў для кожнага рэкурсіўнага выкліку.

294
00:21:40,050 --> 00:21:47,010
І так як вы выкарыстоўваеце той жа кадр стэка, вам не трэба турбавацца аб

295
00:21:47,010 --> 00:21:51,690
ніколі стэк перапоўнены, і ў той жа час, як вы казалі,

296
00:21:51,690 --> 00:21:56,380
, Дзе калісьці вы вернецеся так, то ён павінен вярнуць усе гэтыя кадры стэка

297
00:21:56,380 --> 00:22:01,740
і 10-й выклік SearchHelp павінен вярнуцца ў 9-м, павінен вярнуцца ў 8-м.

298
00:22:01,740 --> 00:22:05,360
Так што не трэба адбыцца, калі функцыі хвост рэкурсіўнай.

299
00:22:05,360 --> 00:22:13,740
І таму тое, што робіць гэтая функцыя з'яўляецца рэкурсіўнай хвост звярніце ўвагу, што для любога выкліку searchHelp

300
00:22:13,740 --> 00:22:18,470
рэкурсіўны выклік, што ён робіць тое, што ён вяртаецца.

301
00:22:18,470 --> 00:22:25,290
Такім чынам, у першым звароце да SearchHelp, мы альбо неадкладна вярнуцца ілжывым,

302
00:22:25,290 --> 00:22:29,590
неадкладна вярнуць сапраўдны, або мы робім рэкурсіўны выклік SearchHelp

303
00:22:29,590 --> 00:22:33,810
дзе тое, што мы вяртаемся які то выклік вяртаецца.

304
00:22:33,810 --> 00:22:51,560
І мы не маглі гэта зрабіць, калі мы зрабілі нешта накшталт Int х = SearchHelp, вяртанне х * 2,

305
00:22:51,560 --> 00:22:55,440
толькі некаторыя выпадковыя змены.

306
00:22:55,440 --> 00:23:01,470
>> Так што зараз гэта рэкурсіўны выклік, гэта Int х = SearchHelp рэкурсіўнага выкліку,

307
00:23:01,470 --> 00:23:05,740
больш не з'яўляецца хваставой рэкурсіі, таму што на самой справе прыйдзецца вярнуцца

308
00:23:05,740 --> 00:23:10,400
вярнуцца да папярэдняга кадра стэка, так што, што папярэдні выклік функцыі

309
00:23:10,400 --> 00:23:13,040
можа нешта рабіць з вяртае значэнне.

310
00:23:13,040 --> 00:23:22,190
Так што гэта не хвост рэкурсіўнай, але тое, што было раней гэта прыгожа хвост рэкурсіўнай. Так.

311
00:23:22,190 --> 00:23:27,000
[Студэнт] не павінны другім выпадку база будзе ў першую чаргу правяраецца

312
00:23:27,000 --> 00:23:30,640
таму што не можа быць сітуацыі, калі, калі вы перадаеце яго аргумент

313
00:23:30,640 --> 00:23:35,770
Вы пачаць = канец, але яны іголка значэнне.

314
00:23:35,770 --> 00:23:47,310
Гэтае пытанне мы не можам працаваць у тым выпадку, калі канец іголкі значэння

315
00:23:47,310 --> 00:23:52,000
або пачаць = канец, адпаведна, пачатак = канец

316
00:23:52,000 --> 00:23:59,480
і вы на самой справе не праверыў, што асаблівае значэнне тым не менш,

317
00:23:59,480 --> 00:24:03,910
Затым пачынайце + канца / 2 проста будзе мець тое ж значэнне.

318
00:24:03,910 --> 00:24:07,890
Але мы ўжо вярнуліся ілжывым, і мы ніколі не правяралі значэнне.

319
00:24:07,890 --> 00:24:14,240
Так, па меншай меры, у першы выклік, калі памер роўны 0, то мы хочам вярнуцца ілжывым.

320
00:24:14,240 --> 00:24:17,710
Але калі памер роўны 1, то запуск не будзе роўных канца,

321
00:24:17,710 --> 00:24:19,820
і мы па крайняй меры праверыць адзін элемент.

322
00:24:19,820 --> 00:24:26,750
Але я думаю, вы маеце рацыю ў тым, што мы можам у канчатковым выніку ў выпадку, калі пачаць канца + / 2,

323
00:24:26,750 --> 00:24:31,190
Пачатак заканчвае тым, што гэтак жа, як пачатак канца + / 2,

324
00:24:31,190 --> 00:24:35,350
але мы ніколі на самай справе праверыць, што элемент.

325
00:24:35,350 --> 00:24:44,740
>> Такім чынам, калі мы спачатку правяраем, з'яўляецца сярэднім значэннем элемента мы шукаем,

326
00:24:44,740 --> 00:24:47,110
то мы можам неадкладна вярнуць праўдзівы.

327
00:24:47,110 --> 00:24:50,740
Інакш, калі яны роўныя, то няма ніякага сэнсу ў працягу

328
00:24:50,740 --> 00:24:58,440
так як мы толькі збіраемся абнавіць выпадку, калі мы знаходзімся на аднаго элемента масіва.

329
00:24:58,440 --> 00:25:01,110
Калі адзін элемент не той, якога мы шукаем,

330
00:25:01,110 --> 00:25:03,530
то ўсё не так. Так.

331
00:25:03,530 --> 00:25:08,900
[Студэнт] Справа ў тым, што, паколькі памер на самай справе больш, чым колькасць элементаў у масіве,

332
00:25:08,900 --> 00:25:13,070
ўжо ёсць зрушэнне - >> Так будзе памер -

333
00:25:13,070 --> 00:25:19,380
[Студэнт] Скажам, калі масіў быў памерам 0, то SearchHelp будзе на самой справе праверыць стагі сена з 0

334
00:25:19,380 --> 00:25:21,490
па першым клічы.

335
00:25:21,490 --> 00:25:25,300
Масіў мае памер 0, таму 0 з'яўляецца - >> Так.

336
00:25:25,300 --> 00:25:30,750
Там Іншая справа, што - гэта можа быць добрым. Давайце падумаем.

337
00:25:30,750 --> 00:25:40,120
Такім чынам, калі масіў быў 10 элементаў, а сярэдні мы збіраемся праверыць, з'яўляецца індэксам 5,

338
00:25:40,120 --> 00:25:45,700
так мы правяраем 5, і давайце скажам, што значэнне менш.

339
00:25:45,700 --> 00:25:50,720
Такім чынам, мы кідалі ўсё, ад 5 і далей.

340
00:25:50,720 --> 00:25:54,030
Так што пачніце з канца + / 2 будзе нашай новай мэты

341
00:25:54,030 --> 00:25:57,450
так што так, яна заўсёды застанецца за межамі масіва.

342
00:25:57,450 --> 00:26:03,570
Калі гаворка ідзе аб выпадку, калі яно было цотных або няцотных, то мы б праверыць, скажам, 4,

343
00:26:03,570 --> 00:26:05,770
але мы ўсё яшчэ выкідваюць -

344
00:26:05,770 --> 00:26:13,500
Так што так, канец заўсёды будзе за фактычны канец масіва.

345
00:26:13,500 --> 00:26:18,350
Такім чынам, элементы, якія мы засяродзіліся на, канец заўсёды будзе пасля гэтага.

346
00:26:18,350 --> 00:26:24,270
І таму, калі пачаць робіць усё роўныя рэшце рэшт, мы знаходзімся ў масіў памерам 0.

347
00:26:24,270 --> 00:26:35,600
>> Іншая рэч, я думаў, што мы абнаўляем пачынаюць пачаць + канца / 2,

348
00:26:35,600 --> 00:26:44,020
так што гэта той выпадак, калі ў мяне ўзнікаюць праблемы з, дзе пачынаюцца + канца / 2

349
00:26:44,020 --> 00:26:46,820
з'яўляецца элементам, мы правяраем.

350
00:26:46,820 --> 00:26:58,150
Скажам, у нас быў гэты 10-элементны масіў. Усё роўна.

351
00:26:58,150 --> 00:27:03,250
Так што пачніце з канца + / 2 будзе нешта накшталт гэтага,

352
00:27:03,250 --> 00:27:07,060
і калі гэта не ад значэння, што мы хочам абнавіць.

353
00:27:07,060 --> 00:27:10,060
Значэнне больш, таму мы хочам паглядзець на гэтую палову масіва.

354
00:27:10,060 --> 00:27:15,910
Такім чынам, як мы абнаўляем пачатку, мы абнаўляем пачатку зараз гэты элемент.

355
00:27:15,910 --> 00:27:23,790
Але гэта ўсё яшчэ можа працаваць, або, па крайняй меры, вы можаце зрабіць старт + канца / 2 + 1.

356
00:27:23,790 --> 00:27:27,850
[Студэнт] Вам не трэба будзе пачаць + канца [неразборліва] >> Так.

357
00:27:27,850 --> 00:27:33,240
Мы ўжо праверылі гэты элемент і ведаю, што гэта не той, які мы шукаем.

358
00:27:33,240 --> 00:27:36,800
Такім чынам, нам не трэба абнаўляць пачынаюць гэтым элементам.

359
00:27:36,800 --> 00:27:39,560
Мы можам проста прапусціць яго і абнаўляць пачынаюць быць гэты элемент.

360
00:27:39,560 --> 00:27:46,060
І ці ёсць калі-небудзь выпадак, скажам, што гэта быў канец,

361
00:27:46,060 --> 00:27:53,140
так, то пачатку было б гэтага, пачніце канцы + / 2 будзе такім,

362
00:27:53,140 --> 00:28:00,580
пачатак + канец - Так, я думаю, што гэта можа ў канчатковым выніку ў бясконцую рэкурсіі.

363
00:28:00,580 --> 00:28:12,690
Скажам, гэта проста масіў памерам 2 або масіў памерам 1. Я думаю, што гэта будзе працаваць.

364
00:28:12,690 --> 00:28:19,490
Такім чынам, у цяперашні час, з'яўляецца тое, што пачатак і канец элемента роўная 1 за яго межамі.

365
00:28:19,490 --> 00:28:24,110
Такім чынам, элемент, які мы збіраемся праверыць гэта адно,

366
00:28:24,110 --> 00:28:29,400
а потым, калі мы абнаўляем пачатку, мы абнаўляем пачынаюць 0 + 1/2,

367
00:28:29,400 --> 00:28:33,160
які скончыцца нас з пачатку быцця гэтага элемента.

368
00:28:33,160 --> 00:28:36,210
>> Такім чынам, мы правяраем і той жа элемент зноў і зноў.

369
00:28:36,210 --> 00:28:43,310
Так што гэта той выпадак, калі кожны рэкурсіўны выклік павінен на самой справе нешта абнаўляць.

370
00:28:43,310 --> 00:28:48,370
Так што нам трэба зрабіць, пачатак + канец / 2 + 1, альбо ёсць выпадак

371
00:28:48,370 --> 00:28:50,710
, Дзе мы на самай справе не абнаўленнем пачатку.

372
00:28:50,710 --> 00:28:53,820
Усё гэта бачылі?

373
00:28:53,820 --> 00:28:56,310
Добра.

374
00:28:56,310 --> 00:29:03,860
Хто-небудзь ёсць пытанні па гэтаму рашэнню ці больш каментароў?

375
00:29:05,220 --> 00:29:10,280
Добра. Хто-небудзь ёсць итерационного рашэнні, што мы ўсе можам глядзець?

376
00:29:17,400 --> 00:29:20,940
Хіба мы ўсё гэта робім рэкурсіўна?

377
00:29:20,940 --> 00:29:25,950
А таксама, я думаю, калі вы адкрылі яе, то вам, магчыма, давядзецца перавызначыць вашу папярэднюю.

378
00:29:25,950 --> 00:29:28,810
Ці значыць гэта аўтаматычна захоўваць? Я не ўпэўнены.

379
00:29:35,090 --> 00:29:39,130
Хто-небудзь ёсць итерационный?

380
00:29:39,130 --> 00:29:42,430
Мы можам прайсці праз гэта разам, калі няма.

381
00:29:46,080 --> 00:29:48,100
Ідэя будзе тое ж самае.

382
00:30:00,260 --> 00:30:02,830
Итерационные рашэння.

383
00:30:02,830 --> 00:30:07,140
Мы збіраемся хочуць у асноўным, робяць тую ж ідэю

384
00:30:07,140 --> 00:30:16,530
, Дзе мы хочам быць у курсе новых канцы масіва і новыя пачатку масіва

385
00:30:16,530 --> 00:30:18,510
і рабіць гэта зноў і зноў.

386
00:30:18,510 --> 00:30:22,430
І калі тое, што мы адсочваюць, як пачатак і канец ніколі не перасякаюцца,

387
00:30:22,430 --> 00:30:29,020
тады мы не знайшлі яго і мы можам вярнуцца ілжывым.

388
00:30:29,020 --> 00:30:37,540
Так як я магу гэта зрабіць? Любы ёсць прапановы або код для мяне, каб падцягнуць?

389
00:30:42,190 --> 00:30:47,450
[Студэнт] Ці падабаецца час цыклу. >> Так.

390
00:30:47,450 --> 00:30:49,450
Вы збіраецеся хочаце зрабіць пятлю.

391
00:30:49,450 --> 00:30:51,830
>> У вас ёсць код, я мог бы падцягнуць, або тое, што вы хацелі прапанаваць?

392
00:30:51,830 --> 00:30:56,340
[Студэнт] Я так думаю. >> Усё правільна. Гэта робіць рэчы прасцей. Якое было ваша імя?

393
00:30:56,340 --> 00:30:57,890
[Студэнт] Лукас.

394
00:31:00,140 --> 00:31:04,190
Перагляд 1. Добра.

395
00:31:04,190 --> 00:31:13,200
Нізкая тое, што мы называлі пачаць раней.

396
00:31:13,200 --> 00:31:17,080
Да гэта не зусім тое, што мы называлі да канца.

397
00:31:17,080 --> 00:31:22,750
На самай справе, у канцы Цяпер усярэдзіне масіва. Гэта элемент, які мы павінны разгледзець.

398
00:31:22,750 --> 00:31:26,890
Такім чынам, нізкае значэнне 0, да гэта памер масіва - 1,

399
00:31:26,890 --> 00:31:34,780
і зараз мы цыклаў, і мы правяраем -

400
00:31:34,780 --> 00:31:37,340
Я думаю, вы можаце прайсці праз гэта.

401
00:31:37,340 --> 00:31:41,420
Якое было ваша мысленне праз гэта? Ідзіце з намі праз код.

402
00:31:41,420 --> 00:31:49,940
[Студэнт] Вядома. Паглядзіце на стозе сена значэнне ў сярэдніх і параўнаць яго з іголкі.

403
00:31:49,940 --> 00:31:58,520
Так што, калі гэта больш, чым ваша іголка, то вы хочаце, каб - ой, на самай справе, што павінна быць наадварот.

404
00:31:58,520 --> 00:32:05,180
Вы збіраецеся хочаце, каб выкінуць правай паловы, і так так, гэта павінен быць шлях.

405
00:32:05,180 --> 00:32:08,830
[Боуден] Такім чынам, гэта павінна быць менш? Гэта тое, што вы сказалі? >> [Студэнт] Так.

406
00:32:08,830 --> 00:32:10,390
[Боуден] Добра. Паменш.

407
00:32:10,390 --> 00:32:15,700
Так што калі мы глядзім на гэта менш, чым тое, што мы хочам,

408
00:32:15,700 --> 00:32:19,410
то так, мы хочам, каб выкінуць левую палову,

409
00:32:19,410 --> 00:32:22,210
якая азначае, што мы абнаўляем ўсе мы разглядаем

410
00:32:22,210 --> 00:32:26,610
шляхам перамяшчэння нізкай справа ад масіва.

411
00:32:26,610 --> 00:32:30,130
Гэта выглядае добра.

412
00:32:30,130 --> 00:32:34,550
Я думаю, што гэта мае той жа пытанне, што мы казалі на папярэднім,

413
00:32:34,550 --> 00:32:49,760
дзе, калі нізкае значэнне 0 і вышэй роўны 1, то нізка + да / 2 будзе наладжаны на адно і тое ж зноў.

414
00:32:49,760 --> 00:32:53,860
>> І нават калі гэта не так, то гэта яшчэ больш эфектыўнай, па меншай меры

415
00:32:53,860 --> 00:32:57,630
проста выкінуць элемент, мы проста глядзелі на якіх мы ведаем не так.

416
00:32:57,630 --> 00:33:03,240
Так нізка + уверх / 2 + 1 - >> [студэнт] Гэта павінна быць па-іншаму.

417
00:33:03,240 --> 00:33:05,900
[Боуден] Альбо гэта павінна быць - 1, а іншая павінна быць + 1.

418
00:33:05,900 --> 00:33:09,580
[Студэнт] І не павінна быць двайны знак роўнасці. >> [Боуден] Так.

419
00:33:09,580 --> 00:33:11,340
[Студэнт] Так.

420
00:33:14,540 --> 00:33:15,910
Добра.

421
00:33:15,910 --> 00:33:21,280
І, нарэшце, зараз, калі ў нас ёсць гэта + 1 - 1 штука,

422
00:33:21,280 --> 00:33:31,520
гэта - яна не можа быць - гэта наогул магчыма для нізкай, каб у выніку значэнне большае, чым наверсе?

423
00:33:35,710 --> 00:33:40,320
Я думаю, што адзіны спосаб, які можа адбыцца - Хіба гэта магчыма? >> [Студэнт] я не ведаю.

424
00:33:40,320 --> 00:33:45,220
Але калі ён атрымлівае усечаны, а затым атрымлівае мінус, што 1, а затым - >> Так.

425
00:33:45,220 --> 00:33:47,480
[Студэнт] Было б, магчыма, атрымаць пераблыталіся.

426
00:33:49,700 --> 00:33:53,940
Я думаю, што гэта павінна быць добра толькі таму, што

427
00:33:53,940 --> 00:33:58,800
для таго, каб у канчатковым выніку больш яны павінны быць роўныя, я думаю.

428
00:33:58,800 --> 00:34:03,070
Але калі яны роўныя, то мы б не зрабілі той час як цыкл з самага пачатку

429
00:34:03,070 --> 00:34:06,670
і мы проста вярнуліся б значэнне. Так што я думаю, што мы добра цяпер.

430
00:34:06,670 --> 00:34:11,530
Звярніце ўвагу, што, хоць гэтая праблема больш не з'яўляецца рэкурсіўнай,

431
00:34:11,530 --> 00:34:17,400
такія ж ідэі дастасавальныя, дзе мы можам убачыць, як гэта так лёгка паддаецца

432
00:34:17,400 --> 00:34:23,659
на рэкурсіўнае рашэнне тым, што мы проста абнаўленне індэксаў зноў і зноў,

433
00:34:23,659 --> 00:34:29,960
мы робім праблемай менш і менш, мы факусуемся на падмноства масіва.

434
00:34:29,960 --> 00:34:40,860
[Студэнт] Калі нізкі роўны 0 і вышэй за 1, яны як бы 0 + 1/2, які пойдзе на 0,

435
00:34:40,860 --> 00:34:44,429
а то можна было б + 1, можна было б быць - 1.

436
00:34:47,000 --> 00:34:50,870
[Студэнт] Куды мы праверка роўнасці?

437
00:34:50,870 --> 00:34:55,100
Падобна гэтаму, калі сярэдні самай справе іголку?

438
00:34:55,100 --> 00:34:58,590
Мы ў цяперашні час не робіць гэтага? О!

439
00:35:00,610 --> 00:35:02,460
Калі it's -

440
00:35:05,340 --> 00:35:13,740
Так. Мы не можам проста зрабіць тэст тут, таму што скажам першай сярэдняй -

441
00:35:13,740 --> 00:35:16,430
[Студэнт] Гэта на самай справе хацеў не выкідвайце мяжы.

442
00:35:16,430 --> 00:35:20,220
Такім чынам, калі Вы хочаце пазбавіцца ад звязанага, вы павінны праверыць яго першым, ці любы іншы.

443
00:35:20,220 --> 00:35:23,350
Ah. Так. >> [Студэнт] Так.

444
00:35:23,350 --> 00:35:29,650
Такім чынам, мы выкінулі, якую мы ў цяперашні час глядзелі,

445
00:35:29,650 --> 00:35:33,260
якая азначае, што мы зараз павінны таксама мець

446
00:35:33,260 --> 00:35:44,810
калі (стозе сена [(нізкі + ўверх) / 2] == іголкай), то мы можам вярнуцца дакладна.

447
00:35:44,810 --> 00:35:52,070
І ці магу я пакласці яшчэ ці проста калі гэта азначае літаральна тое ж самае

448
00:35:52,070 --> 00:35:57,110
таму што гэта вярнуўся б праўдай.

449
00:35:57,110 --> 00:36:01,450
Так што я паклаў яшчэ, калі, але гэта не мае значэння.

450
00:36:01,450 --> 00:36:10,440
>> Так яшчэ, калі гэта, яшчэ гэта, і гэта з'яўляецца агульным, што я раблю

451
00:36:10,440 --> 00:36:14,340
дзе, нават калі гэта выпадак, калі ўсё тут добра,

452
00:36:14,340 --> 00:36:22,780
як нізкі ніколі не можа быць больш, чым ўверх, не варта разваг пра тое, што гэта праўда.

453
00:36:22,780 --> 00:36:28,010
Такім чынам, вы можаце таксама сказаць, у той час як нізкае, менш ці роўна

454
00:36:28,010 --> 00:36:30,720
або пры нізкім менш

455
00:36:30,720 --> 00:36:35,300
так што калі яны калі-небудзь роўнай ці нізкай адбываецца, каб прайсці міма,

456
00:36:35,300 --> 00:36:40,130
то мы можам вырвацца з гэтага цыклу.

457
00:36:41,410 --> 00:36:44,630
Пытанні, праблемы, каментары?

458
00:36:47,080 --> 00:36:49,270
Добра. Гэта выглядае добра.

459
00:36:49,270 --> 00:36:52,230
Цяпер мы хочам зрабіць сартаванне.

460
00:36:52,230 --> 00:37:04,030
Калі мы пойдзем да майго Другі перагляд, мы бачым тыя ж ліку,

461
00:37:04,030 --> 00:37:07,550
але цяпер ён больш не ў парадку сартавання.

462
00:37:07,550 --> 00:37:12,840
І мы хочам рэалізаваць з дапамогай любога роду алгарытм O п § п.

463
00:37:12,840 --> 00:37:17,240
Такім чынам, якой алгарытм вы думаеце, мы павінны рэалізаваць тут? >> [Студэнт] Зліццё роду.

464
00:37:17,240 --> 00:37:23,810
[Боуден] Так. Зліццё сартавання O (п § п), так гэта тое, што мы збіраемся рабіць.

465
00:37:23,810 --> 00:37:26,680
І праблема будзе даволі падобныя,

466
00:37:26,680 --> 00:37:31,920
, Дзе ён лёгка паддаецца рэкурсіўнае рашэнне.

467
00:37:31,920 --> 00:37:35,580
Мы таксама можам прыдумаць итерационного рашэнні, калі мы хочам,

468
00:37:35,580 --> 00:37:42,540
але Рэкурсія будзе лягчэй тут, і мы павінны зрабіць рэкурсіі.

469
00:37:45,120 --> 00:37:49,530
Я думаю, мы будзем хадзіць праз сартавання зліццём першае,

470
00:37:49,530 --> 00:37:54,280
хоць ёсць выдатныя відэа на сартавання зліццём ўжо. [Смех]

471
00:37:54,280 --> 00:37:59,780
Так сартавання зліццём ёсць - я марнаваць так шмат працы.

472
00:37:59,780 --> 00:38:02,080
О, ёсць толькі адзін злева.

473
00:38:02,080 --> 00:38:03,630
Такім чынам, зліццё.

474
00:38:08,190 --> 00:38:12,470
О, 1, 3, 5.

475
00:38:26,090 --> 00:38:27,440
Добра.

476
00:38:29,910 --> 00:38:33,460
Зліццё мае два асобных масіваў.

477
00:38:33,460 --> 00:38:36,780
Індывідуальна гэтых двух масіваў і сартуюцца.

478
00:38:36,780 --> 00:38:40,970
Такім чынам, гэты масіў, 1, 3, 5, адсартаваныя. Гэты масіў, 0, 2, 4, адсартаваныя.

479
00:38:40,970 --> 00:38:46,710
Цяпер тое, што зліццё павінны зрабіць, гэта аб'яднаць іх у адзін масіў, які сам адсартаваныя.

480
00:38:46,710 --> 00:38:57,130
Таму мы хочам масіў памерам 6, які будзе мець гэтыя элементы ўнутры яго

481
00:38:57,130 --> 00:38:59,390
у пэўным парадку.

482
00:38:59,390 --> 00:39:03,390
>> І таму мы можам скарыстацца тым, што гэтыя два масіва сартуюцца

483
00:39:03,390 --> 00:39:06,800
Для гэтага ў лінейным часу,

484
00:39:06,800 --> 00:39:13,510
лінейныя сэнс часу, калі гэты масіў памерам х, і гэта памер у,

485
00:39:13,510 --> 00:39:20,970
то агульны алгарытм павінен быць O (х + у). Добра.

486
00:39:20,970 --> 00:39:23,150
Такім чынам, прапановы.

487
00:39:23,150 --> 00:39:26,030
[Студэнт] Ці можам мы пачаць з левай?

488
00:39:26,030 --> 00:39:30,150
Такім чынам, вы будзеце ставіць 0 ўніз, а затым 1, а затым тут вы на 2.

489
00:39:30,150 --> 00:39:33,320
Так што гэта накшталт як у вас ёсць укладка, якая рухаецца направа. >> [Боуден] Так.

490
00:39:33,320 --> 00:39:41,070
Для абодвух гэтых масіваў, калі мы засяродзімся толькі на левы элемент.

491
00:39:41,070 --> 00:39:43,530
Паколькі абодва масівы сартуюцца, мы ведаем, што гэтыя 2 элемента

492
00:39:43,530 --> 00:39:46,920
самыя маленькія элементы ў любым масіве.

493
00:39:46,920 --> 00:39:53,500
Такім чынам, гэта азначае, што 1 з гэтых 2 элементы павінны быць найменшы элемент у нашым аб'яднаным масіве.

494
00:39:53,500 --> 00:39:58,190
Проста так атрымалася, што з'яўляецца найменшым адзін на гэты раз.

495
00:39:58,190 --> 00:40:02,580
Такім чынам, мы возьмем 0, устаўце яго на левай, таму што 0 менш за 1,

496
00:40:02,580 --> 00:40:08,210
так вазьміце 0, устаўце яе ў нашу першую пазіцыю, а затым абнаўляць гэты

497
00:40:08,210 --> 00:40:12,070
у цяперашні час засяроджаная на першы элемент.

498
00:40:12,070 --> 00:40:14,570
А цяпер паўтарыце.

499
00:40:14,570 --> 00:40:20,670
Такім чынам, зараз мы параўнаем 2 і 1. 1 менш, таму мы уставім 1.

500
00:40:20,670 --> 00:40:25,300
Мы абнаўляем гэты паказальнік, каб паказаць на гэтага хлопца.

501
00:40:25,300 --> 00:40:33,160
Цяпер мы робім гэта зноў, так што 2. Гэта дазволіць абнавіць, параўнаць гэтыя 2, 3.

502
00:40:33,160 --> 00:40:37,770
Гэты абнаўлення, то 4 і 5.

503
00:40:37,770 --> 00:40:42,110
Так што гэта зліццё.

504
00:40:42,110 --> 00:40:49,010
>> Гэта павінна быць даволі відавочна, што гэта лінейнае час, так як мы проста ідзем па кожнаму элементу раз.

505
00:40:49,010 --> 00:40:55,980
І гэта вялікі крок да рэалізацыі сартаванне зліццём гэта робіць.

506
00:40:55,980 --> 00:40:59,330
І гэта не так складана.

507
00:40:59,330 --> 00:41:15,020
Пара рэчаў, каб турбавацца аб тым, скажам, мы зліваліся 1, 2, 3, 4, 5, 6.

508
00:41:15,020 --> 00:41:30,930
У гэтым выпадку мы ў канчатковым выніку ў сцэнары, дзе гэтая будзе менш,

509
00:41:30,930 --> 00:41:36,160
Затым мы абнаўляем гэты паказальнік, на гэты раз будзе менш, абнаўляць,

510
00:41:36,160 --> 00:41:41,280
гэтым гэта менш, і цяпер вы павінны прызнаць,

511
00:41:41,280 --> 00:41:44,220
калі вы рэальна працаваць з элементаў з чым параўноўваць.

512
00:41:44,220 --> 00:41:49,400
Так як мы ўжо выкарысталі ўвесь гэты масіў,

513
00:41:49,400 --> 00:41:55,190
ўсё ў гэтым масіве зараз проста ўстаўляецца ў тут.

514
00:41:55,190 --> 00:42:02,040
Таму, калі мы калі-небудзь працаваць у кропку, дзе адзін з нашых масіваў цалкам аб'яднаны ўжо,

515
00:42:02,040 --> 00:42:06,510
Затым мы проста возьмем ўсе элементы іншых масіваў і ўставіць іх у канец масіва.

516
00:42:06,510 --> 00:42:13,630
Такім чынам, мы можам проста ўставіць 4, 5, 6. Добра.

517
00:42:13,630 --> 00:42:18,070
Гэта значыць, адна рэч, каб не выпусціць.

518
00:42:22,080 --> 00:42:26,120
Рэалізацыя, якая павінна быць крокам 1.

519
00:42:26,120 --> 00:42:32,600
Сартаванне зліццём затым на аснове гэтага, гэта 2 кроку, 2 дурных крокаў.

520
00:42:38,800 --> 00:42:42,090
Давайце проста даць гэтаму масіву.

521
00:42:57,920 --> 00:43:05,680
Такім чынам, сартаванне зліццём, крок 1, каб рэкурсіўна разбіць масіў на дзве паловы.

522
00:43:05,680 --> 00:43:09,350
Такім чынам падзяліць гэты масіў на дзве паловы.

523
00:43:09,350 --> 00:43:22,920
Цяпер у нас ёсць 4, 15, 16, 50 і 8, 23, 42, 108.

524
00:43:22,920 --> 00:43:25,800
І зараз мы робім гэта зноў, і мы падзяліць гэтыя дзве паловы.

525
00:43:25,800 --> 00:43:27,530
Я проста зраблю гэта на гэтым баку.

526
00:43:27,530 --> 00:43:34,790
Такім чынам, 4, 15 і 16, 50.

527
00:43:34,790 --> 00:43:37,440
Мы хацелі б зрабіць тое ж самае тут.

528
00:43:37,440 --> 00:43:40,340
І зараз мы падзялілі яго на дзве палоўкі зноў.

529
00:43:40,340 --> 00:43:51,080
І ў нас ёсць 4, 15, 16, 50.

530
00:43:51,080 --> 00:43:53,170
Так што гэта наш базавы сцэнар.

531
00:43:53,170 --> 00:44:00,540
Пасля масівы памерам 1, то мы спыняем з расшчапленнем на дзве паловы.

532
00:44:00,540 --> 00:44:03,190
>> Цяпер тое, што мы будзем рабіць з гэтым?

533
00:44:03,190 --> 00:44:15,730
Мы ў канчатковым выніку гэта таксама будзе распадацца на 8, 23, 42 і 108.

534
00:44:15,730 --> 00:44:24,000
Так што цяпер мы знаходзімся ў гэтай кропцы, цяпер крок два роды зліццё проста зліццё пары ў спісах.

535
00:44:24,000 --> 00:44:27,610
Таму мы хочам, каб аб'яднаць гэтыя. Мы проста патэлефанаваць зліцця.

536
00:44:27,610 --> 00:44:31,410
Мы ведаем, што зліццё будзе вярнуць іх у вызначаным парадку.

537
00:44:31,410 --> 00:44:33,920
4, 15.

538
00:44:33,920 --> 00:44:41,440
Цяпер мы хочам, каб аб'яднаць гэтыя, і выдасць спіс з тымі, у пэўным парадку,

539
00:44:41,440 --> 00:44:44,160
16, 50.

540
00:44:44,160 --> 00:44:57,380
Мы аб'яднаць гэтыя - я не магу напісаць - 8, 23 і 42, 108.

541
00:44:57,380 --> 00:45:02,890
Такім чынам, мы маем аб'яднаную пар адразу.

542
00:45:02,890 --> 00:45:05,140
Цяпер мы проста аб'яднаць зноў.

543
00:45:05,140 --> 00:45:10,130
Звярніце ўвагу, што кожны з гэтых спісаў, адсартаваных ў сабе,

544
00:45:10,130 --> 00:45:15,220
і тады мы можам проста аб'яднаць гэтыя спісы, каб атрымаць спіс памеры 4, які сартуецца

545
00:45:15,220 --> 00:45:19,990
і зліццё гэтых двух спісаў, каб атрымаць спіс памерам 4, адсартаваны.

546
00:45:19,990 --> 00:45:25,710
І, нарэшце, мы можам аб'яднаць гэтыя два спісу памер 4, каб атрымаць адзін спіс памеры 8, які сартуецца.

547
00:45:25,710 --> 00:45:34,030
Такім чынам, каб зразумець, што гэта агульная п § п, мы ўжо бачылі, што зліццё з'яўляецца лінейнай,

548
00:45:34,030 --> 00:45:40,390
таму, калі мы маем справу з зліццё гэтых, так як агульны кошт зліцця

549
00:45:40,390 --> 00:45:43,410
для гэтых двух спісаў знаходзіцца ўсяго ў 2, таму што -

550
00:45:43,410 --> 00:45:49,610
Ці добра, гэта O п, п, але вось толькі гэтыя 2 элемента, так што 2.

551
00:45:49,610 --> 00:45:52,850
І гэтыя 2 будзе 2 і гэтыя 2 будзе 2, і гэтыя 2 будзе 2,

552
00:45:52,850 --> 00:45:58,820
так праз усё зліваецца, што мы павінны зрабіць, мы ў канчатковым выніку робіць н.

553
00:45:58,820 --> 00:46:03,210
Як 2 + 2 + 2 + 2 складае 8, які з'яўляецца п,

554
00:46:03,210 --> 00:46:08,060
так што кошт зліцця ў гэтым мностве N.

555
00:46:08,060 --> 00:46:10,810
І тое ж самае і тут.

556
00:46:10,810 --> 00:46:16,980
Мы аб'яднаць гэтыя 2, то гэтыя 2 і індывідуальна гэтага зліцця зойме чатыры аперацыі,

557
00:46:16,980 --> 00:46:23,610
гэта зліццё зойме чатыры аперацыі, але зноў жа, паміж усім гэтым,

558
00:46:23,610 --> 00:46:29,030
мы ў канчатковым выніку зліцця п агульная рэчы, і таму гэты крок займае н.

559
00:46:29,030 --> 00:46:33,670
І так кожны ўзровень мае п элементаў у зліцці.

560
00:46:33,670 --> 00:46:36,110
>> А колькі узроўняў ёсць?

561
00:46:36,110 --> 00:46:40,160
На кожным узроўні нашага масіва павялічваецца на памер 2.

562
00:46:40,160 --> 00:46:44,590
Тут нашы масівы маюць памер 1, тут яны памерам 2, тут яны памерам 4,

563
00:46:44,590 --> 00:46:46,470
І, нарэшце, яны памерам 8.

564
00:46:46,470 --> 00:46:56,450
Такім чынам, паколькі яно падвойваецца, там будзе ў агульнай складанасці § п з гэтых узроўняў.

565
00:46:56,450 --> 00:47:02,090
Так што з § п узроўняў, кожны ўзровень з п агульная аперацый,

566
00:47:02,090 --> 00:47:05,720
мы атрымліваем § п п алгарытм.

567
00:47:05,720 --> 00:47:07,790
Пытанні?

568
00:47:08,940 --> 00:47:13,320
У людзей, якія ўжо дамагліся прагрэсу на тым, як ажыццявіць гэта?

569
00:47:13,320 --> 00:47:18,260
Хто-небудзь ужо ў стане, калі я магу проста падцягнуць свой код?

570
00:47:20,320 --> 00:47:22,260
Я магу даць хвіліну.

571
00:47:24,770 --> 00:47:27,470
Гэта адно будзе больш.

572
00:47:27,470 --> 00:47:28,730
Я настойліва рэкамендую паўтараюцца -

573
00:47:28,730 --> 00:47:30,510
Вы не павінны зрабіць рэкурсіі для зліцця

574
00:47:30,510 --> 00:47:33,750
таму што зрабіць рэкурсіі для зліцця, вы будзеце мець, каб прайсці кучу розных памераў.

575
00:47:33,750 --> 00:47:37,150
Можна, але гэта раздражняе.

576
00:47:37,150 --> 00:47:43,720
Але рэкурсіі для сартавання само па сабе даволі лёгка.

577
00:47:43,720 --> 00:47:49,190
Вы проста тэлефануйце роду літаральна на левай палове, сартаваць па правую палову. Добра.

578
00:47:51,770 --> 00:47:54,860
Любы, ёсць усё, што я магу пацягнуць яшчэ?

579
00:47:54,860 --> 00:47:57,540
Ці я дам адну хвіліну.

580
00:47:58,210 --> 00:47:59,900
Добра.

581
00:47:59,900 --> 00:48:02,970
Любы, ёсць нешта, што мы можам працаваць з?

582
00:48:05,450 --> 00:48:09,680
Ці мы будзем проста працаваць з гэтым, а затым разгарніце адтуль.

583
00:48:09,680 --> 00:48:14,050
>> Любы, ёсць больш, чым гэта, што я магу пацягнуць?

584
00:48:14,050 --> 00:48:17,770
[Студэнт] Так. Вы можаце падцягнуць мае. >> Усё правільна.

585
00:48:17,770 --> 00:48:19,730
Так!

586
00:48:22,170 --> 00:48:25,280
[Студэнт] Існавалі шмат умоў. >> О, чорт. Ці можаце вы -

587
00:48:25,280 --> 00:48:28,110
[Студэнт] У мяне ёсць для яго захавання. >> Так.

588
00:48:32,420 --> 00:48:35,730
Такім чынам, мы сапраўды рабілі зліцця асобна.

589
00:48:35,730 --> 00:48:38,570
Так, але гэта не так ужо дрэнна.

590
00:48:39,790 --> 00:48:41,650
Добра.

591
00:48:41,650 --> 00:48:47,080
Такім чынам, род сама проста тэлефаную mergeSortHelp.

592
00:48:47,080 --> 00:48:49,530
Растлумачце нам, што mergeSortHelp робіць.

593
00:48:49,530 --> 00:48:55,700
[Студэнт] MergeSortHelp ў значнай ступені робіць два асноўных этапу,

594
00:48:55,700 --> 00:49:01,270
якая з'яўляецца для сартавання кожную палову масіва, а затым аб'яднаць іх абодвух.

595
00:49:04,960 --> 00:49:08,050
[Боуден] Добра, дайце мне секунду.

596
00:49:10,850 --> 00:49:13,210
Я думаю, што гэта - >> [студэнт] мне трэба -

597
00:49:17,100 --> 00:49:19,400
Так. Я чагосьці не хапае.

598
00:49:19,400 --> 00:49:23,100
У зліцці, я разумею, што мне трэба, каб стварыць новы масіў

599
00:49:23,100 --> 00:49:26,530
таму што я не мог зрабіць гэта на месцы. >> Так. Вы не можаце. Выпраўце.

600
00:49:26,530 --> 00:49:28,170
[Студэнт] Так я ствараю новы масіў.

601
00:49:28,170 --> 00:49:31,510
Я забыўся ў канцы зліцця з паўторнай зменіцца.

602
00:49:31,510 --> 00:49:34,490
Добра. Мы маем патрэбу ў новым масіве.

603
00:49:34,490 --> 00:49:41,000
У сартавання зліццём, гэта амаль заўсёды так.

604
00:49:41,000 --> 00:49:44,340
Частка расходаў на лепшы алгарытм часам мудры

605
00:49:44,340 --> 00:49:47,310
Амаль заўсёды неабходнасці выкарыстоўваць трохі больш памяці.

606
00:49:47,310 --> 00:49:51,570
Дык вось, незалежна ад таго, як вы гэта робіце сартавання зліццём,

607
00:49:51,570 --> 00:49:54,780
Вам непазбежна давядзецца выкарыстоўваць дадатковую памяць.

608
00:49:54,780 --> 00:49:58,240
Ён або яна стварае новы масіў.

609
00:49:58,240 --> 00:50:03,400
І тады вы кажаце ў канцы мы проста трэба скапіяваць новы масіў у зыходным масіве.

610
00:50:03,400 --> 00:50:04,830
[Студэнт] Я так думаю, так.

611
00:50:04,830 --> 00:50:08,210
Я не ведаю, калі гэта працуе з пункту гледжання рахунку па спасылцы або што заўгодна, -

612
00:50:08,210 --> 00:50:11,650
Так, ён будзе працаваць. >> [Студэнт] Добра.

613
00:50:20,620 --> 00:50:24,480
Ці ведаеце вы паспрабаваць запусціць гэта? >> [Студэнт] Не, яшчэ няма. >> Добра.

614
00:50:24,480 --> 00:50:28,880
Паспрабуйце запусціць яго, і тады я буду казаць пра гэта на секунду.

615
00:50:28,880 --> 00:50:35,200
[Студэнт] Мне трэба, каб усе прататыпы функцый і ўсё, хоць, праўда?

616
00:50:37,640 --> 00:50:40,840
Прататыпы функцый. О, ты маеш на ўвазе - так.

617
00:50:40,840 --> 00:50:43,040
Сартаваць кліча mergeSortHelp.

618
00:50:43,040 --> 00:50:47,390
>> Такім чынам, для таго, каб сартаваць патэлефанаваць mergeSortHelp, mergeSortHelp павінны альбо былі вызначаны

619
00:50:47,390 --> 00:50:56,370
Перад сартавання або нам проста неабходна прататыпа. Проста скапіюйце і ўстаўце гэтага.

620
00:50:56,370 --> 00:50:59,490
І сапраўды гэтак жа, mergeSortHelp выклікае зліццё,

621
00:50:59,490 --> 00:51:03,830
але зліццё не быў вызначаны, таму мы можам проста дайце ведаць mergeSortHelp

622
00:51:03,830 --> 00:51:08,700
што гэта тое, што зліццё будзе выглядаць, вось і ўсё.

623
00:51:09,950 --> 00:51:15,730
Так mergeSortHelp.

624
00:51:22,770 --> 00:51:32,660
У нас ёсць праблема тут, дзе мы не маем базавы варыянт.

625
00:51:32,660 --> 00:51:38,110
MergeSortHelp рэкурсіўна, так што любы рэкурсіўнай функцыі

626
00:51:38,110 --> 00:51:42,610
будзе трэба нейкая падстава справа ведаць, калі спыніцца рэкурсіўна, якая называе сябе.

627
00:51:42,610 --> 00:51:45,590
Тое, што наша база выпадку будзе тут? Так.

628
00:51:45,590 --> 00:51:49,110
[Студэнт] Калі памер 1? >> [Боуден] Так.

629
00:51:49,110 --> 00:51:56,220
Так што, як мы бачылі, менавіта там, мы спыніліся расшчаплення масіваў

630
00:51:56,220 --> 00:52:01,850
як толькі мы атрымалі ў масівы памерам 1, якая непазбежна сартуюцца сябе.

631
00:52:01,850 --> 00:52:09,530
Такім чынам, калі памер роўны 1, мы ведаем, што масіў ўжо адсартаваны,

632
00:52:09,530 --> 00:52:12,970
таму мы можам проста вярнуцца.

633
00:52:12,970 --> 00:52:16,880
>> Звярніце ўвагу, што гэта пустэча, так што мы нічога не вяртаюць прыватнасці, мы проста вяртаем.

634
00:52:16,880 --> 00:52:19,580
Добра. Так што гэта наш базавы сцэнар.

635
00:52:19,580 --> 00:52:27,440
Я думаю, наш базавы сцэнар таксама можа быць, калі мы, здараецца, зліццё масіў памерам 0,

636
00:52:27,440 --> 00:52:30,030
мы, верагодна, хочаце, каб спыніць у нейкі момант,

637
00:52:30,030 --> 00:52:33,610
так што мы можам толькі сказаць, памерам менш за 2 ці менш або роўная 1

638
00:52:33,610 --> 00:52:37,150
так што гэта будзе працаваць для любога масіва цяпер.

639
00:52:37,150 --> 00:52:38,870
Добра.

640
00:52:38,870 --> 00:52:42,740
Так што гэта наш базавы сцэнар.

641
00:52:42,740 --> 00:52:45,950
Цяпер вы хочаце ісці з намі праз зліццё?

642
00:52:45,950 --> 00:52:49,140
Што азначаюць усе гэтыя выпадкі на ўвазе?

643
00:52:49,140 --> 00:52:54,480
Тут, наверсе, мы проста робім тую ж ідэю, -

644
00:52:56,970 --> 00:53:02,470
[Студэнт] Мне трэба праходзіў памеру з усімі выклікамі mergeSortHelp.

645
00:53:02,470 --> 00:53:10,080
Я дадаў памеры якасці дадатковага пачатковага і яго там няма, як і памер / 2.

646
00:53:10,080 --> 00:53:16,210
[Боуден] О, памер / 2, памер / 2. >> [Студэнт] Так, а таксама ў прыведзенай вышэй функцыі, а таксама.

647
00:53:16,210 --> 00:53:21,320
[Боуден] Тут? >> [Студэнт] Гэтак жа памеру. >> [Боуден] Ох. Памер, памер? >> [Студэнт] Так.

648
00:53:21,320 --> 00:53:23,010
[Боуден] Добра.

649
00:53:23,010 --> 00:53:26,580
Дазвольце мне думаць ні на секунду.

650
00:53:26,580 --> 00:53:28,780
Хіба мы сутыкнуліся з праблемай?

651
00:53:28,780 --> 00:53:33,690
Мы заўсёды лячэнні левым як 0. >> [Студэнт] Няма

652
00:53:33,690 --> 00:53:36,340
Гэта няправільна таксама. Выбачайце. Гэта павінна быць пачатак. Так.

653
00:53:36,340 --> 00:53:39,230
[Боуден] Добра. Мне падабаецца, што лепш.

654
00:53:39,230 --> 00:53:43,880
І канца. Добра.

655
00:53:43,880 --> 00:53:47,200
Так што цяпер вы хочаце ісці з намі праз зліццё? >> [Студэнт] Добра.

656
00:53:47,200 --> 00:53:52,150
Я проста ішоў па гэтай новай масіў, які я стварыў.

657
00:53:52,150 --> 00:53:57,420
Яе памер з'яўляецца памерам частцы масіва, які мы хочам быць адсартаваныя

658
00:53:57,420 --> 00:54:03,460
і спрабуе знайсці элемент, які я павінен пакласці ў новы этап масіва.

659
00:54:03,460 --> 00:54:10,140
Такім чынам, каб зрабіць гэта, спачатку я правяраю, калі ў левай палове масіва працягвае мець больш элементаў,

660
00:54:10,140 --> 00:54:14,260
і калі гэта не так, то вы спускаецеся да гэтага яшчэ ўмова, якое проста кажа

661
00:54:14,260 --> 00:54:20,180
Добра, яна павінна быць у правільным масіве, і мы пакладзем, што ў бягучым індэксе newArray.

662
00:54:20,180 --> 00:54:27,620
>> А потым у адваротным выпадку, я правяраю, калі правая частка масіва таксама скончыў,

663
00:54:27,620 --> 00:54:30,630
У гэтым выпадку я проста паклаў у левы.

664
00:54:30,630 --> 00:54:34,180
Гэта можа і не быць неабходным. Я не ўпэўнены.

665
00:54:34,180 --> 00:54:40,970
Але ў любым выпадку, дзве іншыя праверкі, які з двух меншых ў левую або правую.

666
00:54:40,970 --> 00:54:49,770
А таксама ў кожным канкрэтным выпадку, я павялічваючы залежнасці ад таго, запаўняльнік Я павялічвацца.

667
00:54:49,770 --> 00:54:52,040
[Боуден] Добра.

668
00:54:52,040 --> 00:54:53,840
Гэта выглядае добра.

669
00:54:53,840 --> 00:54:58,800
Хто-небудзь ёсць заўвагі ці пытанні ці праблемы?

670
00:55:00,660 --> 00:55:07,720
Такім чынам, чатыры выпадкі, што мы павінны прынесці рэчы ў проста быць - ці гэта выглядае як пяць -

671
00:55:07,720 --> 00:55:13,100
але мы павінны разгледзець пытанне аб левым масіве скончыліся, што нам трэба аб'яднацца,

672
00:55:13,100 --> 00:55:16,390
Ці мае права масіве скончыліся рэчы, якія мы павінны аб'яднаць -

673
00:55:16,390 --> 00:55:18,400
Я паказваючы на ​​нічога.

674
00:55:18,400 --> 00:55:21,730
Так ці левы масіў скончыліся рэчы або права масіве скончыліся рэчы.

675
00:55:21,730 --> 00:55:24,320
Гэтыя два выпадкі.

676
00:55:24,320 --> 00:55:30,920
Мы таксама маем патрэбу ў трывіяльным выпадку, ад таго, што засталося менш, чым правільныя рэчы.

677
00:55:30,920 --> 00:55:33,910
Тады мы хочам выбраць левую рэч.

678
00:55:33,910 --> 00:55:37,630
Тыя выпадкі.

679
00:55:37,630 --> 00:55:40,990
Так што гэта было правільна, так вось што.

680
00:55:40,990 --> 00:55:46,760
Масіў засталося. Гэта 1, 2, 3. Добра. Так што так, гэта тыя чатыры рэчы, якія мы маглі б зрабіць.

681
00:55:50,350 --> 00:55:54,510
І мы не будзем пераходзіць рашэння итерационным.

682
00:55:54,510 --> 00:55:55,980
Я б не рэкамендаваў -

683
00:55:55,980 --> 00:56:03,070
Зліццё роду з'яўляецца прыкладам функцыі, якая з'яўляецца адначасова не хвост рэкурсіўнай,

684
00:56:03,070 --> 00:56:07,040
гэта не так проста зрабіць яго хваставой рэкурсіі,

685
00:56:07,040 --> 00:56:13,450
але і гэта не вельмі лёгка зрабіць итеративным.

686
00:56:13,450 --> 00:56:16,910
Гэта вельмі лёгка.

687
00:56:16,910 --> 00:56:19,170
Гэтая рэалізацыя сартавання зліццём,

688
00:56:19,170 --> 00:56:22,140
злівацца, што б вы ні рабілі, вы збіраецеся пабудаваць зліцця.

689
00:56:22,140 --> 00:56:29,170
>> Такім чынам, сартаванне зліццём пабудаваны на зліцці рэкурсіўна менавіта гэтыя тры лініі.

690
00:56:29,170 --> 00:56:34,700
Итеративно, больш раздражняльнымі і больш цяжка думаць.

691
00:56:34,700 --> 00:56:41,860
Але звярніце ўвагу, што гэта не хвост рэкурсіўнай, так як mergeSortHelp - калі ён называе сябе -

692
00:56:41,860 --> 00:56:46,590
яго яшчэ трэба рабіць рэчы, пасля гэтага вяртаецца рэкурсіўных выклікаў.

693
00:56:46,590 --> 00:56:50,830
Так што гэты кадр стэка павінна працягваць існаваць нават пасля выкліку гэтага.

694
00:56:50,830 --> 00:56:54,170
А потым, калі вы называеце гэта, стэк павінен працягваць існаваць

695
00:56:54,170 --> 00:56:57,780
таму што нават пасля гэтага выкліку, мы ўсё яшчэ павінны злівацца.

696
00:56:57,780 --> 00:57:01,920
І гэта нетрывіяльная, каб зрабіць гэты хвост рэкурсіўнай.

697
00:57:04,070 --> 00:57:06,270
Пытанні?

698
00:57:08,300 --> 00:57:09,860
Добра.

699
00:57:09,860 --> 00:57:13,400
Такім чынам, вяртаючыся да сартаванне - ой, ёсць дзве рэчы, якія я хачу паказаць. Добра.

700
00:57:13,400 --> 00:57:17,840
Вяртаючыся да сартавання, мы зробім гэта хутка.

701
00:57:17,840 --> 00:57:21,030
Або шукаць. Сартаванне? Сартаванне. Так.

702
00:57:21,030 --> 00:57:22,730
Вяртаючыся да вытокаў роду.

703
00:57:22,730 --> 00:57:29,870
Мы хочам стварыць алгарытм, які сартуе масіў з выкарыстаннем любога алгарытму

704
00:57:29,870 --> 00:57:33,660
У O п.

705
00:57:33,660 --> 00:57:40,860
Так, як гэта магчыма? Хто-небудзь ёсць якія-небудзь роду -

706
00:57:40,860 --> 00:57:44,300
Я намякнуў, перш чым на -

707
00:57:44,300 --> 00:57:48,300
Калі мы збіраемся палепшыць з п § п к а п,

708
00:57:48,300 --> 00:57:51,450
Мы палепшылі наш алгарытм часам мудрай,

709
00:57:51,450 --> 00:57:55,250
гэта азначае, што мы збіраемся трэба зрабіць, каб нагнаць гэта?

710
00:57:55,250 --> 00:57:59,520
[Студэнт] прасторы. >> Так. Мы збіраемся выкарыстоўваць больш прасторы.

711
00:57:59,520 --> 00:58:04,490
І нават не проста больш месца, гэта экспанентна больш прасторы.

712
00:58:04,490 --> 00:58:14,320
Так што я думаю, што гэты тып алгарытму з'яўляецца тое, псеўда, псеўда полинома -

713
00:58:14,320 --> 00:58:18,980
псеўда - Я не магу ўспомніць. Псеўда нешта.

714
00:58:18,980 --> 00:58:22,210
Але гэта таму, што мы павінны выкарыстоўваць так шмат месца

715
00:58:22,210 --> 00:58:28,610
што гэта дасягальна, але не рэалістычна.

716
00:58:28,610 --> 00:58:31,220
>> І як мы можам гэтага дасягнуць?

717
00:58:31,220 --> 00:58:36,810
Мы можам дамагчыся гэтага, калі мы гарантуем, што любы канкрэтны элемент масіва

718
00:58:36,810 --> 00:58:39,600
ніжэй вызначанага памеру.

719
00:58:42,070 --> 00:58:44,500
Так што давайце проста скажам, што памеры 200,

720
00:58:44,500 --> 00:58:48,130
любы элемент у масіве ніжэй памеру 200.

721
00:58:48,130 --> 00:58:51,080
І гэта на самай справе вельмі рэалістычна.

722
00:58:51,080 --> 00:58:58,660
Вы можаце вельмі лёгка мець масіў, што вы ведаеце ўсё, што ў яго

723
00:58:58,660 --> 00:59:00,570
будзе менш, чым некаторы лік.

724
00:59:00,570 --> 00:59:07,400
Падобна гэтаму, калі ў вас ёсць абсалютна масіўнага вектарнага ці нешта

725
00:59:07,400 --> 00:59:11,810
але вы ведаеце, усё, што будзе паміж 0 і 5,

726
00:59:11,810 --> 00:59:14,790
то гэта будзе значна хутчэй гэта зрабіць.

727
00:59:14,790 --> 00:59:17,930
І звязаны ні па адным з элементаў 5,

728
00:59:17,930 --> 00:59:21,980
так што гэтая ацэнка, гэта значыць, колькі памяці вы збіраецеся выкарыстаць.

729
00:59:21,980 --> 00:59:26,300
Такім чынам, мяжа 200.

730
00:59:26,300 --> 00:59:32,960
У тэорыі заўсёды ёсць звязанае, так як цэлае можа быць толькі да 4 млрд.

731
00:59:32,960 --> 00:59:40,600
але гэта нерэальна, так як тады мы будзем з выкарыстаннем касмічных

732
00:59:40,600 --> 00:59:44,400
каля 4 млрд. даляраў. Так што гэта нерэальна.

733
00:59:44,400 --> 00:59:47,060
Але тут мы будзем казаць наша адзнака з'яўляецца 200.

734
00:59:47,060 --> 00:59:59,570
Увесь фокус у тым, каб рабіць гэта ў O п значыць, мы робім яшчэ адзін масіў завецца падлік памеру мяжу.

735
00:59:59,570 --> 01:00:10,470
Такім чынам, на самай справе, гэта цэтлік для - Я на самой справе не ведаю, калі Clang гэта робіць.

736
01:00:11,150 --> 01:00:15,330
Але ў GCC, па меншай меры - я мяркуючы, Clang робіць гэта занадта -

737
01:00:15,330 --> 01:00:18,180
гэта будзе проста ініцыялізаваць ўвесь масіў будзе 0s.

738
01:00:18,180 --> 01:00:25,320
Так што, калі я не хачу гэтага рабіць, то я мог бы зрабіць асобна для (INT = 0;

739
01:00:25,320 --> 01:00:31,500
я <BOUND, я + +) і разлічвае [я] = 0;

740
01:00:31,500 --> 01:00:35,260
Так што зараз усё усталёўваецца на 0.

741
01:00:35,260 --> 01:00:39,570
Я перабору мой масіў,

742
01:00:39,570 --> 01:00:51,920
і тое, што я раблю, я разлічваю чысла кожнага - давай сюды.

743
01:00:51,920 --> 01:00:55,480
У нас ёсць 4, 15, 16, 50, 8, 23, 42, 108.

744
01:00:55,480 --> 01:01:00,010
Што я разлічваю лік уваходжанняў кожнага з гэтых элементаў.

745
01:01:00,010 --> 01:01:03,470
Давайце на самай справе дадаць яшчэ пару сюды з некаторымі паўтараецца.

746
01:01:03,470 --> 01:01:11,070
Такім чынам, значэнне мы маем тут, значэнне, якое будзе масіў [I].

747
01:01:11,070 --> 01:01:14,850
Такім чынам, вал можа быць 4 або 8 або любы іншы.

748
01:01:14,850 --> 01:01:18,870
І зараз я разлічваю, колькі з гэтага значэння, я бачыў,

749
01:01:18,870 --> 01:01:21,230
так лічыць [значэнне] + +;

750
01:01:21,230 --> 01:01:29,430
Пасля гэтага не будзе зроблена, разлічвае будзе выглядаць як 0001.

751
01:01:29,430 --> 01:01:42,190
Давайце зробім падлік [значэнне] - выконваць + 1.

752
01:01:42,190 --> 01:01:48,230
>> Зараз гэта проста растлумачыць той факт, што мы, пачынаючы з 0.

753
01:01:48,230 --> 01:01:50,850
Такім чынам, калі 200 будзе наш самы вялікі нумар,

754
01:01:50,850 --> 01:01:54,720
Затым ад 0 да 200 складае 201 рэчаў.

755
01:01:54,720 --> 01:02:01,540
Такім чынам, лічыцца, гэта будзе выглядаць як 00001, таму што ў нас ёсць адзін 4.

756
01:02:01,540 --> 01:02:10,210
Тады мы будзем мець 0001, дзе мы будзем мець 1 у 8-м індэкс кольк.

757
01:02:10,210 --> 01:02:14,560
Мы будзем мець 2 ў 23-ы паказчык кольк.

758
01:02:14,560 --> 01:02:17,630
Мы будзем мець 2 у індэксе 42-й рахунак.

759
01:02:17,630 --> 01:02:21,670
Такім чынам, мы можам выкарыстоўваць рахунку.

760
01:02:34,270 --> 01:02:44,920
Так num_of_item = імпульсы [I].

761
01:02:44,920 --> 01:02:52,540
І таму, калі num_of_item роўна 2, гэта азначае, што мы хочам ўставіць 2 ліку я

762
01:02:52,540 --> 01:02:55,290
у нашым масіве.

763
01:02:55,290 --> 01:03:02,000
Так што мы павінны адсочваць, як далёка мы ў масіў.

764
01:03:02,000 --> 01:03:05,470
Такім чынам, індэкс = 0.

765
01:03:05,470 --> 01:03:09,910
Array - Я проста напісаць яе.

766
01:03:16,660 --> 01:03:18,020
Графы -

767
01:03:19,990 --> 01:03:28,580
масіў [індэкс + +] = я;

768
01:03:28,580 --> 01:03:32,490
Гэта тое, што я хачу? Я думаю, што тое, што я хачу.

769
01:03:35,100 --> 01:03:38,290
Так, гэта добра выглядае. Добра.

770
01:03:38,290 --> 01:03:43,050
Гэтак жа ўсе разумеюць, што мэта майго масіва лічыцца такое?

771
01:03:43,050 --> 01:03:48,140
Гэта падлік ліку уваходжанняў кожнага з гэтых лікаў.

772
01:03:48,140 --> 01:03:51,780
Тады я ітэрацыя, што мае значэнне масіва,

773
01:03:51,780 --> 01:03:57,190
і й пазіцыі ў масіве разлічвае

774
01:03:57,190 --> 01:04:01,930
гэты лік я вось што павінна з'явіцца ў маім масіве.

775
01:04:01,930 --> 01:04:06,840
Вось чаму пунктах 4, будзе на 1

776
01:04:06,840 --> 01:04:11,840
і налічвае ад 8 будзе 1, пунктах 23, будзе 2.

777
01:04:11,840 --> 01:04:16,900
Дык вось, колькі з іх я хачу ўставіць у мой масіве.

778
01:04:16,900 --> 01:04:19,200
Тады я проста гэта зрабіць.

779
01:04:19,200 --> 01:04:28,960
Я ўстаўка num_of_item я вось у маім масіве.

780
01:04:28,960 --> 01:04:31,670
>> Пытанні?

781
01:04:32,460 --> 01:04:43,100
І зноў жа, гэта лінейнае час, так як мы проста ітэрацыі ў гэты раз,

782
01:04:43,100 --> 01:04:47,470
але гэта таксама лінейныя у тым, што гэты лік апынецца,

783
01:04:47,470 --> 01:04:50,730
і так шмат у чым залежыць ад таго, што ваша мяжа.

784
01:04:50,730 --> 01:04:53,290
З звязанае 200, што не так ужо дрэнна.

785
01:04:53,290 --> 01:04:58,330
Калі мяжа будзе 10000, то гэта трохі горш,

786
01:04:58,330 --> 01:05:01,360
але калі ваша звязаных будзе 4 млрд., што гэта цалкам нерэальна

787
01:05:01,360 --> 01:05:07,720
і гэты масіў будзе мець, каб быць памерам 4 мільярды даляраў, што нерэальна.

788
01:05:07,720 --> 01:05:10,860
Дык вось што. Пытанні?

789
01:05:10,860 --> 01:05:13,270
[Неразборліва адказ студэнта] >> Добра.

790
01:05:13,270 --> 01:05:15,710
Я зразумеў адну рэч, калі мы перажываем.

791
01:05:17,980 --> 01:05:23,720
Я думаю, што праблема была ў Лукаса і, напэўна, кожны з нас бачыў.

792
01:05:23,720 --> 01:05:26,330
Я зусім забыўся.

793
01:05:26,330 --> 01:05:31,040
Адзінае, што я хацеў бы пракаментаваць, што, калі вы маеце справу з рэчамі, як індэксы,

794
01:05:31,040 --> 01:05:38,320
Вы ніколі не бачаць гэтага, калі вы пішаце цыкл,

795
01:05:38,320 --> 01:05:41,120
але тэхнічна, кожны раз, калі вы маеце справу з гэтымі паказчыкамі,

796
01:05:41,120 --> 01:05:45,950
Вы павінны амаль заўсёды справу з цэлымі лікамі без знака.

797
01:05:45,950 --> 01:05:53,850
Прычына гэтага ў тым, калі вы маеце справу з цэлымі лікамі,

798
01:05:53,850 --> 01:05:56,090
так што калі ў вас ёсць 2 цэлых лікаў, і вы складзеце іх разам

799
01:05:56,090 --> 01:06:00,640
і яны ў канчатковым выніку занадта вялікі, то вы ў канчатковым выніку з адмоўным лікам.

800
01:06:00,640 --> 01:06:03,410
Дык вось што цэлае перапаўнення.

801
01:06:03,410 --> 01:06:10,500
>> Калі дадаць 2 млрд і 1 млрд, я ў канчатковым выніку з адмоўнымі 1 мільярд даляраў.

802
01:06:10,500 --> 01:06:15,480
Вось як цэлыя працаваць на кампутарах.

803
01:06:15,480 --> 01:06:17,510
Такім чынам, праблема з выкарыстаннем -

804
01:06:17,510 --> 01:06:23,500
Гэта нармальна, за выключэннем, калі нізка, здараецца, 2 млрд і вышэй, здараецца, 1 млрд,

805
01:06:23,500 --> 01:06:27,120
то гэта будзе адмоўны 1 млрд. і затым мы збіраемся падзяліць гэта на 2

806
01:06:27,120 --> 01:06:29,730
і ў канчатковым выніку з адмоўнай 500 мільёнаў даляраў.

807
01:06:29,730 --> 01:06:33,760
Так што гэта толькі пытанне, калі вам здарыцца быць пошук у масіве

808
01:06:33,760 --> 01:06:38,070
мільярды рэчаў.

809
01:06:38,070 --> 01:06:44,050
Але калі нізка + да адбываецца перапаўненне, то гэта праблема.

810
01:06:44,050 --> 01:06:47,750
Як толькі мы іх без знака, затым 2 млрд. плюс 1 млрд. 3 млрд. даляраў.

811
01:06:47,750 --> 01:06:51,960
3000000000 падзяліць на 2 складае 1,5 мільярда даляраў.

812
01:06:51,960 --> 01:06:55,670
Таму, як толькі яны падпісаны, усё ідэальна.

813
01:06:55,670 --> 01:06:59,900
І гэта таксама праблема, калі вы пішаце вашыя цыклы,

814
01:06:59,900 --> 01:07:03,940
а на самай справе, гэта, верагодна, робіць гэта аўтаматычна.

815
01:07:09,130 --> 01:07:12,330
Гэта на самай справе проста крычаць на вас.

816
01:07:12,330 --> 01:07:21,610
Так што, калі гэта лік занадта вялікім, каб быць усяго толькі цэлы лік, але гэта будзе ўпісвацца ў цэлы лік без знака,

817
01:07:21,610 --> 01:07:24,970
яна будзе крычаць на вас, вось чаму вы ніколі не сутыкнецеся з праблемай.

818
01:07:29,150 --> 01:07:34,820
Вы можаце бачыць, што індэкс ніколі не будзе адмоўным,

819
01:07:34,820 --> 01:07:39,220
і таму, калі вы ітэрацыі па масіве,

820
01:07:39,220 --> 01:07:43,970
Вы можаце амаль заўсёды кажуць непадпісаныя Int я, але вы сапраўды не трэба.

821
01:07:43,970 --> 01:07:47,110
Справы ідуць працаваць у значнай ступені гэтак жа добра.

822
01:07:48,740 --> 01:07:50,090
Добра. [Шэптам] Колькі зараз часу?

823
01:07:50,090 --> 01:07:54,020
Апошняе, што я хацеў паказаць, - і я буду проста рабіць гэта вельмі хутка.

824
01:07:54,020 --> 01:08:03,190
Вы ведаеце, як мы # вызначыць такім чынам мы можам вызначыць # MAX, як 5 ці яшчэ што-небудзь?

825
01:08:03,190 --> 01:08:05,940
Давайце не будзем рабіць MAX. # Вызначыць звязаны як 200. Гэта тое, што мы рабілі раней.

826
01:08:05,940 --> 01:08:10,380
Гэта вызначае пастаяннае, якая толькі збіраецца быць скапіяваны і ўстаўлены

827
01:08:10,380 --> 01:08:13,010
дзе б мы ні здарылася, каб напісаць звязаныя.

828
01:08:13,010 --> 01:08:18,189
>> Так што мы сапраўды можам зрабіць больш з # вызначае.

829
01:08:18,189 --> 01:08:21,170
Мы можам вызначыць функцыі #.

830
01:08:21,170 --> 01:08:23,410
Яны на самай справе не функцыі, але мы будзем называць іх функцый.

831
01:08:23,410 --> 01:08:36,000
Прыкладам можа быць нешта накшталт MAX (х, у) вызначаецца як (х <у у: х). Добра.

832
01:08:36,000 --> 01:08:40,660
Такім чынам, вы павінны прывыкнуць да патройны сінтаксіс аператара,

833
01:08:40,660 --> 01:08:49,029
але х менш, чым у? Вярнуцца у, яшчэ вернуцца х.

834
01:08:49,029 --> 01:08:54,390
Такім чынам, вы можаце бачыць вы можаце зрабіць гэта асобнай функцыяй,

835
01:08:54,390 --> 01:09:01,399
і функцыя можа быць як BOOL MAX займае 2 аргументаў, вярнуць гэта.

836
01:09:01,399 --> 01:09:08,340
Гэта адзін з найбольш распаўсюджаных з іх я бачу, як гэта зрабіць. Мы называем іх макрасаў.

837
01:09:08,340 --> 01:09:11,790
Гэта макрас.

838
01:09:11,790 --> 01:09:15,859
Гэта толькі сінтаксіс для гэтага.

839
01:09:15,859 --> 01:09:18,740
Вы можаце напісаць макрас, каб зрабіць усё, што вы хочаце.

840
01:09:18,740 --> 01:09:22,649
Вы часта бачыце макрасы для адладкі printfs і іншае.

841
01:09:22,649 --> 01:09:29,410
Такім чынам, тып Printf, існуюць адмысловыя канстанты ў C, як падкрэсліваюць ЛІНІЯ падкрэслення,

842
01:09:29,410 --> 01:09:31,710
2 падкрэслівае ЛІНІЯ падкрэслення,

843
01:09:31,710 --> 01:09:37,550
і ёсць таксама я думаю, што 2 падкрэслення FUNC. Гэта магло б быць. Нешта накшталт гэтага.

844
01:09:37,550 --> 01:09:40,880
Гэтыя рэчы будуць заменены на імя функцыі

845
01:09:40,880 --> 01:09:42,930
або нумар радка, што вы знаходзіцеся.

846
01:09:42,930 --> 01:09:48,630
Часта, вы пішаце адладкі printfs, што тут я мог бы проста напісаць

847
01:09:48,630 --> 01:09:54,260
Адладка і ён будзе друкаваць нумар радка і функцыі, якія я апынуцца ў

848
01:09:54,260 --> 01:09:57,020
што яна сустракаецца, што DEBUG заяве.

849
01:09:57,020 --> 01:09:59,550
І вы таксама можаце раздрукаваць іншых рэчаў.

850
01:09:59,550 --> 01:10:05,990
Такім чынам, адзінае, што вы павінны сачыць за тое, калі я, здараецца, # вызначыць DOUBLE_MAX

851
01:10:05,990 --> 01:10:11,380
як нешта накшталт 2 * у і 2 * х.

852
01:10:11,380 --> 01:10:14,310
Так па якой прычыне, вы, аказваецца, зрабіць гэта шмат.

853
01:10:14,310 --> 01:10:16,650
Так што зрабіце гэта макрас.

854
01:10:16,650 --> 01:10:18,680
Гэта сапраўды зламаны.

855
01:10:18,680 --> 01:10:23,050
Я б назваў гэта, робячы нешта накшталт DOUBLE_MAX (3, 6).

856
01:10:23,050 --> 01:10:27,530
Такім чынам, што павінна быць вернута?

857
01:10:28,840 --> 01:10:30,580
[Студэнт] 12.

858
01:10:30,580 --> 01:10:34,800
Так, 12 павінны быць вернутыя, і 12 вяртаецца.

859
01:10:34,800 --> 01:10:43,350
3 замяняецца на х, 6 замяняецца на ў, і мы вяртаемся 2 * 6, што на 12.

860
01:10:43,350 --> 01:10:47,710
А што з гэтай нагоды? Што павінна быць вернута?

861
01:10:47,710 --> 01:10:50,330
[Студэнт] 14. >> У ідэале, 14.

862
01:10:50,330 --> 01:10:55,290
Справа ў тым, што, як хэш вызначае працу, памятаеце, што гэта літаральнае капіяванне і ўстаўка

863
01:10:55,290 --> 01:11:00,160
у значнай ступені за ўсё, так што гэта будзе інтэрпрэтавацца як

864
01:11:00,160 --> 01:11:11,270
у 3 менш, чым 1 плюс 6, 2 разы 1 плюс 6, 2 разы 3.

865
01:11:11,270 --> 01:11:19,780
>> Такім чынам, па гэтай прычыне вы амаль заўсёды абгарнуць ўсё ў круглых дужках.

866
01:11:22,180 --> 01:11:25,050
Любая зменная, вы амаль заўсёды абгарнуць ў дужкі.

867
01:11:25,050 --> 01:11:29,570
Ёсць выпадкі, калі вам не прыйдзецца, як я ведаю, што мне не трэба, каб зрабіць гэта тут

868
01:11:29,570 --> 01:11:32,110
таму, што менш, чым у значнай ступені заўсёды проста хадзіць на працу,

869
01:11:32,110 --> 01:11:34,330
Нягледзячы на ​​тое, што можа нават не быць праўдай.

870
01:11:34,330 --> 01:11:41,870
Калі ёсць нешта смешнае, як DOUBLE_MAX (1 == 2),

871
01:11:41,870 --> 01:11:49,760
тое, што адбываецца, каб замяніць 3 меньш, чым 1 роўны роўны 2,

872
01:11:49,760 --> 01:11:53,460
і так, то гэта будзе зрабіць 3 менш за 1, ці значыць гэта, роўны 2,

873
01:11:53,460 --> 01:11:55,620
якія ня тое, што мы хочам.

874
01:11:55,620 --> 01:12:00,730
Такім чынам, у мэтах прадухілення любога аператара прыярытэт праблемы,

875
01:12:00,730 --> 01:12:02,870
заўсёды абгарнуць ў дужкі.

876
01:12:03,290 --> 01:12:07,700
Добра. І вось яно, 5:30.

877
01:12:08,140 --> 01:12:12,470
Калі ў вас ёсць пытанні па PSET, дайце нам ведаць.

878
01:12:12,470 --> 01:12:18,010
Гэта павінна быць весела, і хакерам выданне таксама з'яўляецца значна больш рэалістычным

879
01:12:18,010 --> 01:12:22,980
чым хакерам выданне мінулага года, так што мы спадзяемся, што многія з вас паспрабаваць.

880
01:12:22,980 --> 01:12:26,460
У мінулым годзе было вельмі пераважнай.

881
01:12:28,370 --> 01:12:30,000
>> [CS50.TV]