1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: skulum taka a líta á konar val, algrím

2
00:00:09,980 --> 00:00:12,800
fyrir að taka lista yfir númer og flokkun þeirra.

3
00:00:12,800 --> 00:00:15,750
Reiknirit, muna, er einfaldlega skref-fyrir-skref

4
00:00:15,750 --> 00:00:18,370
aðferð til að ljúka verkefni.

5
00:00:18,370 --> 00:00:21,470
Grunnhugmyndin á bak konar val er að skipta

6
00:00:21,470 --> 00:00:23,390
lista okkar í tvo hluta -

7
00:00:23,390 --> 00:00:26,810
a raðað hluti og unsorted hluta.

8
00:00:26,810 --> 00:00:30,200
Í hvert skref reiknirit, er fjöldi flutt úr

9
00:00:30,200 --> 00:00:33,800
Unsorted hluta til raðað hluta til að lokum

10
00:00:33,800 --> 00:00:35,880
Allt lista er raðað.

11
00:00:35,880 --> 00:00:38,510
Svo hér er listi yfir sex númer -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, og 15.

13
00:00:44,010 --> 00:00:47,680
Núna er allt listi er talin Unsorted.

14
00:00:47,680 --> 00:00:51,770
Jafnvel þótt fjöldi eins og 16. maí þegar vera rétt þess

15
00:00:51,770 --> 00:00:56,040
staðsetningu, reiknirit okkar hefur enga leið að vita það fyrr en

16
00:00:56,040 --> 00:00:57,980
Allt lista er raðað.

17
00:00:57,980 --> 00:01:01,355
Þannig að við munum íhuga hvert númerið Unsorted fyrr við að raða

18
00:01:01,355 --> 00:01:03,800
það sjálf.

19
00:01:03,800 --> 00:01:06,890
Við vitum að við viljum lista til að vera í hækkandi röð.

20
00:01:06,890 --> 00:01:10,200
Þannig að við munum vilja til að byggja upp raðað hluta lista okkar

21
00:01:10,200 --> 00:01:13,280
frá vinstri til hægri, minnsta til stærsta.

22
00:01:13,280 --> 00:01:17,970
Til að gera það, munum við þurfa að finna lágmarks óflokkuðu þáttur

23
00:01:17,970 --> 00:01:21,350
og setja það í lok raðaða hluta.

24
00:01:21,350 --> 00:01:25,370
Þar sem þetta er ekki raðað, er eina leiðin til að gera það er að

25
00:01:25,370 --> 00:01:29,330
líta á hvern þáttur í óflokkuðu hluta, muna

26
00:01:29,330 --> 00:01:32,010
hvaða þáttur er lægsta og samanburður

27
00:01:32,010 --> 00:01:33,770
hver þáttur í því.

28
00:01:33,770 --> 00:01:36,150
Svo munum við fyrst líta á 23.

29
00:01:36,150 --> 00:01:38,650
Þetta er fyrsti þáttur sem við höfum séð, svo við munum muna

30
00:01:38,650 --> 00:01:40,050
það sem minnst.

31
00:01:40,050 --> 00:01:42,320
Næst munum við líta á 42.

32
00:01:42,320 --> 00:01:46,720
42 er stærri en 23, svo er 23 enn lágmarki.

33
00:01:46,720 --> 00:01:51,210
Næst er 4 sem er minna en 23, svo við munum muna 4

34
00:01:51,210 --> 00:01:52,880
sem nýju lágmarki.

35
00:01:52,880 --> 00:01:56,380
Næsta er 16 sem er stærri en 4, svo 4

36
00:01:56,380 --> 00:01:57,980
er enn lágmarki.

37
00:01:57,980 --> 00:02:03,670
8 er stærri en 4, og 15 er stærri en 4, SO 4 þarf að vera

38
00:02:03,670 --> 00:02:05,980
minnsti Unsorted þáttur.

39
00:02:05,980 --> 00:02:09,350
Svo jafnvel þó eins og menn sem við getum strax séð að 4 er

40
00:02:09,350 --> 00:02:12,300
lágmarks þáttur, reiknirit okkar þarf að líta á

41
00:02:12,300 --> 00:02:15,710
hvert Unsorted þáttur, jafnvel eftir að við höfum fundið 4 -

42
00:02:15,710 --> 00:02:16,860
lágmarki þáttur.

43
00:02:16,860 --> 00:02:19,900
Svo nú er að við höfum fundið lágmarks frumefni, 4, munum við viljum

44
00:02:19,900 --> 00:02:23,410
að færa það inn í raðaða hluta á listanum.

45
00:02:23,410 --> 00:02:27,320
Þar sem þetta er fyrsta skrefið, það þýðir að við viljum að setja 4 í

46
00:02:27,320 --> 00:02:29,680
upphaf listanum.

47
00:02:29,680 --> 00:02:33,040
Núna 23 er í upphafi á listanum, svo

48
00:02:33,040 --> 00:02:36,080
við skulum skipta um 4 og 23.

49
00:02:36,080 --> 00:02:38,870
Svo nú lista okkar lítur svona út.

50
00:02:38,870 --> 00:02:42,710
Við vitum að 4 verða að vera í síðasta stað, því það er

51
00:02:42,710 --> 00:02:45,890
bæði lítill þáttur og þáttur í upphafi

52
00:02:45,890 --> 00:02:46,960
á listanum.

53
00:02:46,960 --> 00:02:50,650
Þannig að þetta þýðir að við gerum ekki alltaf að færa það aftur.

54
00:02:50,650 --> 00:02:53,910
Svo skulum endurtaka þetta ferli til að bæta annar þáttur til

55
00:02:53,910 --> 00:02:55,910
raðað hluti á listanum.

56
00:02:55,910 --> 00:02:58,950
Við vitum að við þurfum ekki að horfa á 4, því það er

57
00:02:58,950 --> 00:03:00,000
þegar raðað.

58
00:03:00,000 --> 00:03:03,540
Þannig að við getum byrjað á 42, sem við munum muna sem

59
00:03:03,540 --> 00:03:05,290
lágmarki þáttur.

60
00:03:05,290 --> 00:03:08,700
Svo næst munum við líta á 23 sem er minna en 42, svo við

61
00:03:08,700 --> 00:03:11,620
man 23 er nýja lágmarki.

62
00:03:11,620 --> 00:03:14,870
Næst ætlum við að sjá 16 sem er minna en 23, svo

63
00:03:14,870 --> 00:03:16,800
16 er nýja lágmarki.

64
00:03:16,800 --> 00:03:19,720
Nú erum við að líta á 8 sem er minna en 16, svo

65
00:03:19,720 --> 00:03:21,130
8 er nýtt lágmark.

66
00:03:21,130 --> 00:03:25,900
Og að lokum 8 er minna en 15, þannig að við vitum að 8 er lágmark

67
00:03:25,900 --> 00:03:27,780
Unsorted þáttur.

68
00:03:27,780 --> 00:03:30,660
Svo þýðir að við ættum að bæta 8 að raða

69
00:03:30,660 --> 00:03:32,450
hluti á listanum.

70
00:03:32,450 --> 00:03:35,990
Núna 4 er bara raðað atriði, þannig að við viljum að setja

71
00:03:35,990 --> 00:03:38,410
8 við hliðina á 4.

72
00:03:38,410 --> 00:03:41,920
Þar 42 er fyrsti þáttur í óflokkuðu hluta

73
00:03:41,920 --> 00:03:47,260
lista, munum við vilja til að skipta um 42 og 8.

74
00:03:47,260 --> 00:03:49,680
Svo nú lista okkar lítur svona út.

75
00:03:49,680 --> 00:03:53,830
4 og 8 tákna raðað hluta listanum og

76
00:03:53,830 --> 00:03:56,440
eftir tölur tákna unsorted

77
00:03:56,440 --> 00:03:58,260
hluti á listanum.

78
00:03:58,260 --> 00:04:00,630
Svo skulum halda áfram með öðru endurtekning.

79
00:04:00,630 --> 00:04:03,850
Við byrjum með 23 í þetta sinn, þar sem við þurfum ekki að horfa á

80
00:04:03,850 --> 00:04:05,770
The 4 og 8 aftur því þeir hafa

81
00:04:05,770 --> 00:04:07,660
þegar verið raðað.

82
00:04:07,660 --> 00:04:10,270
16 er minna en 23, svo við munum muna

83
00:04:10,270 --> 00:04:12,070
16 eins og nýju lágmarki.

84
00:04:12,070 --> 00:04:18,149
16 er minna en 42, en 15 er minna en 16, svo 15 verður

85
00:04:18,149 --> 00:04:20,480
lágmarks Unsorted þáttur.

86
00:04:20,480 --> 00:04:24,580
Svo nú að við viljum skipta á 15 og 23 til

87
00:04:24,580 --> 00:04:26,310
gefa okkur þennan lista.

88
00:04:26,310 --> 00:04:30,500
Raðaða hluti listanum samanstendur af 4, 8 og 15, og

89
00:04:30,500 --> 00:04:33,210
þessir þættir eru enn Unsorted.

90
00:04:33,210 --> 00:04:36,900
En það gerist bara svo að næsta unsorted frumefni, 16,

91
00:04:36,900 --> 00:04:38,480
er þegar raðað.

92
00:04:38,480 --> 00:04:42,060
Hins vegar, það er engin leið fyrir reiknirit okkar að vita að 16

93
00:04:42,060 --> 00:04:45,230
er nú þegar í rétta stað, svo að við þurfum enn að

94
00:04:45,230 --> 00:04:47,870
endurtaka nákvæmlega sömu aðferð.

95
00:04:47,870 --> 00:04:53,750
Þannig sjáum við að 16 er minna en 42, og 16 er minna en 23, svo

96
00:04:53,750 --> 00:04:56,230
16 verða að vera að lágmarki þáttur.

97
00:04:56,230 --> 00:04:59,010
Það er ómögulegt að skipta þessi þáttur með sig, þannig að við getum

98
00:04:59,010 --> 00:05:01,780
einfaldlega láta það í þessum stað.

99
00:05:01,780 --> 00:05:04,660
Þannig að við þurfum eitt fleiri fara á reiknirit okkar.

100
00:05:04,660 --> 00:05:09,370
42 er meira en 23, svo 23 hlýtur að vera

101
00:05:09,370 --> 00:05:10,970
lágmarki Unsorted þáttur.

102
00:05:10,970 --> 00:05:17,410
Þegar við skipti á 23 og 42, við enda upp með endanlegri okkar

103
00:05:17,410 --> 00:05:18,530
raðað lista -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
Við vitum 42 verða að vera á réttum stað þar sem það er

106
00:05:26,830 --> 00:05:30,210
eini þátturinn eftir, og það er val tegund.

107
00:05:30,210 --> 00:05:32,100
Skulum formlega nú reiknirit okkar með nokkrum

108
00:05:32,100 --> 00:05:34,540
sauðakóðanum.

109
00:05:34,540 --> 00:05:37,760
Á línu eitt, getum við séð að við þurfum að samþætta yfir

110
00:05:37,760 --> 00:05:39,530
hver þáttur af listanum.

111
00:05:39,530 --> 00:05:42,150
Nema síðasta þáttur þar sem 1 þáttur

112
00:05:42,150 --> 00:05:44,230
Listinn er þegar raðað.

113
00:05:44,230 --> 00:05:48,100
Á línu tvö, telja við fyrsta þáttur í unsorted

114
00:05:48,100 --> 00:05:51,080
hluti á listanum til að vera lágmark, eins og við gerðum með okkar

115
00:05:51,080 --> 00:05:53,750
dæmi, þannig að við höfum eitthvað til að bera saman.

116
00:05:53,750 --> 00:05:57,260
Line þrjú hefst annað lykkju sem við iterate yfir

117
00:05:57,260 --> 00:05:59,170
hver Unsorted þáttur.

118
00:05:59,170 --> 00:06:02,150
Við vitum að eftir að ég endurtekningar, raðaða hluta

119
00:06:02,150 --> 00:06:05,330
lista okkar verður að hafa i þætti í henni frá hverju skrefi

120
00:06:05,330 --> 00:06:06,890
konar einn þáttur.

121
00:06:06,890 --> 00:06:11,770
Svo fyrsta unsorted þátturinn verður að vera í stöðu ég auk 1.

122
00:06:11,770 --> 00:06:15,440
Á línu fjögur, bera saman við núverandi þáttur í lágmarki

123
00:06:15,440 --> 00:06:17,750
þáttur sem við höfum séð hingað til.

124
00:06:17,750 --> 00:06:20,560
Ef núverandi þáttur er minni en lágmarks

125
00:06:20,560 --> 00:06:23,870
þáttur, svo við minnumst nú þáttur sem nýr

126
00:06:23,870 --> 00:06:26,250
Lágmark á línu fimm.

127
00:06:26,250 --> 00:06:29,900
Að lokum, á línum sex og sjö, skipta við lágmarks

128
00:06:29,900 --> 00:06:33,080
þáttur með fyrstu óflokkuðu frumefni, þannig

129
00:06:33,080 --> 00:06:36,990
bæta því við raðaða hluta á listanum.

130
00:06:36,990 --> 00:06:40,030
Þegar við höfum reiknirit, mikilvæg spurning að spyrja

131
00:06:40,030 --> 00:06:43,370
okkur sem forritari er hversu lengi var það tekið?

132
00:06:43,370 --> 00:06:46,970
Við munum fyrst spyrja hversu langan tíma tekur það fyrir þetta

133
00:06:46,970 --> 00:06:50,070
algrím til að keyra í versta falli?

134
00:06:50,070 --> 00:06:51,640
Muna að tákna þetta gangi

135
00:06:51,640 --> 00:06:55,060
tíma með stóru O merki.

136
00:06:55,060 --> 00:06:58,650
Í því skyni að ákvarða lágmarks óflokkuðu frumefni, við

137
00:06:58,650 --> 00:07:01,880
raun þurfti að bera hvert stak í listanum til

138
00:07:01,880 --> 00:07:04,040
hver annar þáttur í listanum.

139
00:07:04,040 --> 00:07:08,430
Innsæi, þetta hljómar eins og O í n veldi rekstri.

140
00:07:08,430 --> 00:07:12,050
Þegar litið er á sauðakóðanum, höfum við einnig lykkju hreiður inni

141
00:07:12,050 --> 00:07:14,420
önnur lykkja, sem vissulega hljómar eins og O

142
00:07:14,420 --> 00:07:16,480
í n veldi rekstri.

143
00:07:16,480 --> 00:07:19,250
En mundu að við höfum ekki þurft að líta yfir

144
00:07:19,250 --> 00:07:23,460
allt lista við ákvörðun lágmarks óflokkuðu frumefni?

145
00:07:23,460 --> 00:07:26,600
Þegar við vissum að 4 var raðað, til dæmis, við fengum ekki

146
00:07:26,600 --> 00:07:28,170
þurfa að líta á það aftur.

147
00:07:28,170 --> 00:07:31,020
Svo þýðir þetta lægri í gangi tíma?

148
00:07:31,020 --> 00:07:34,510
Fyrir lista okkar lengd 6 þurftum við að fimm

149
00:07:34,510 --> 00:07:37,990
samanburð á fyrstu frumefni, fjögur samanburð

150
00:07:37,990 --> 00:07:40,750
annar þátturinn, og svo framvegis.

151
00:07:40,750 --> 00:07:44,690
Það þýðir að heildarfjöldi skref er summan af

152
00:07:44,690 --> 00:07:49,160
Heiltölurnar frá 1 til lengd lista mínus 1.

153
00:07:49,160 --> 00:07:51,005
Við getum táknað þetta með samantekt.

154
00:07:57,980 --> 00:07:59,910
Við munum ekki fara inn summations hér.

155
00:07:59,910 --> 00:08:04,900
En það kemur í ljós að þessi samantekt er jafn n sinnum

156
00:08:04,900 --> 00:08:07,540
N mínus 1 yfir 2.

157
00:08:07,540 --> 00:08:14,220
Eða equivalently, n veldi yfir 2 mínus N á 2.

158
00:08:14,220 --> 00:08:18,860
Þegar rætt er um asymptotic afturkreistingur, þetta N kvaðrat tíma

159
00:08:18,860 --> 00:08:22,070
er að fara að ráða þessa n tíma.

160
00:08:22,070 --> 00:08:27,850
Svo er val konar O N veldi.

161
00:08:27,850 --> 00:08:31,460
Muna að í dæmi okkar, val tegund enn þörf til

162
00:08:31,460 --> 00:08:33,850
athuga hvort tala sem var þegar raðað

163
00:08:33,850 --> 00:08:35,450
þarf að flytja.

164
00:08:35,450 --> 00:08:38,929
Svo það þýðir að ef við hljóp val konar yfir þegar

165
00:08:38,929 --> 00:08:43,070
raðað lista, myndi það krefjast þess sama fjölda ráðstafanir sem þau

166
00:08:43,070 --> 00:08:46,340
myndi þegar í gangi yfir alveg óflokkuðu lista.

167
00:08:46,340 --> 00:08:51,470
Svo er val að raða besta ræða árangur n veldi,

168
00:08:51,470 --> 00:08:56,820
sem við tákna með omega n veldi.

169
00:08:56,820 --> 00:08:58,600
Og það er það að raða val.

170
00:08:58,600 --> 00:09:00,630
Bara eitt af mörgum reiknirit sem við getum

171
00:09:00,630 --> 00:09:02,390
nota til að raða listanum.

172
00:09:02,390 --> 00:09:05,910
Mitt nafn er Tommy, og þetta er cs50.