1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: Le të bëjmë një vështrim në lloj të përzgjedhjes, një algoritmi

2
00:00:09,980 --> 00:00:12,800
për të marrë një listë të numrave dhe zgjidhja e tyre.

3
00:00:12,800 --> 00:00:15,750
Një algoritëm, mbani mend, është thjesht një hap-pas-hapi

4
00:00:15,750 --> 00:00:18,370
Procedura për kryerjen e një detyre.

5
00:00:18,370 --> 00:00:21,470
Ideja themelore prapa përzgjedhjes lloj është për të ndarë

6
00:00:21,470 --> 00:00:23,390
Lista e jonë në dy pjesë -

7
00:00:23,390 --> 00:00:26,810
një pjesë të renditura dhe një pjesë unsorted.

8
00:00:26,810 --> 00:00:30,200
Në çdo hap të algorithm, një numër i është lëvizur nga

9
00:00:30,200 --> 00:00:33,800
Pjesa unsorted në pjesën renditura derisa përfundimisht

10
00:00:33,800 --> 00:00:35,880
Lista e tërë është renditura.

11
00:00:35,880 --> 00:00:38,510
Kështu që këtu është një listë e gjashtë numrave -

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

13
00:00:44,010 --> 00:00:47,680
Tani për tani lista është konsideruar gjithë Unsorted.

14
00:00:47,680 --> 00:00:51,770
Edhe pse një numër si 16 Maj tashmë të jetë në korrekt i saj

15
00:00:51,770 --> 00:00:56,040
vendndodhjen, algorithm tonë nuk ka asnjë mënyrë për të ditur se deri në

16
00:00:56,040 --> 00:00:57,980
Lista e tërë është renditura.

17
00:00:57,980 --> 00:01:01,355
Pra, ne do të konsiderojmë çdo numër të Unsorted deri ne lloj

18
00:01:01,355 --> 00:01:03,800
ajo veten.

19
00:01:03,800 --> 00:01:06,890
Ne e dimë se ne duam lista të jetë në ngjitje qëllim.

20
00:01:06,890 --> 00:01:10,200
Pra, ne do të duan për të ndërtuar pjesën e renditura të listës sonë

21
00:01:10,200 --> 00:01:13,280
nga e majta në të djathtë, më të vogël tek më i madhi.

22
00:01:13,280 --> 00:01:17,970
Për ta bërë këtë, ne do të duhet për të gjetur elementin minimal Unsorted

23
00:01:17,970 --> 00:01:21,350
dhe e vuri atë në fund të pjesës renditura.

24
00:01:21,350 --> 00:01:25,370
Që nga kjo listë nuk është e renditur, e vetmja mënyrë për të bërë këtë është që të

25
00:01:25,370 --> 00:01:29,330
shikojmë në çdo element në pjesën Unsorted, duke kujtuar

26
00:01:29,330 --> 00:01:32,010
cili element është i ulët dhe krahasimin e

27
00:01:32,010 --> 00:01:33,770
çdo element për këtë.

28
00:01:33,770 --> 00:01:36,150
Pra, ne do të shikojmë të parë në 23.

29
00:01:36,150 --> 00:01:38,650
Ky është elementi i parë që ne kemi parë, kështu që ne do të kujtojmë

30
00:01:38,650 --> 00:01:40,050
atë si minimum.

31
00:01:40,050 --> 00:01:42,320
Ardhshëm ne do të shikojmë në 42.

32
00:01:42,320 --> 00:01:46,720
42 është më e madhe se 23, kështu që 23 është ende minimale.

33
00:01:46,720 --> 00:01:51,210
Tjetra është 4 e cila është më pak se 23, kështu që ne do të kujtojmë 4

34
00:01:51,210 --> 00:01:52,880
si minimum të ri.

35
00:01:52,880 --> 00:01:56,380
Tjetra është 16 e cila është më e madhe se 4, kështu që 4

36
00:01:56,380 --> 00:01:57,980
është ende minimale.

37
00:01:57,980 --> 00:02:03,670
8 është më e madhe se 4 dhe 15 është më e madhe se 4, kështu që duhet të jetë 4

38
00:02:03,670 --> 00:02:05,980
elementi më i vogël unsorted.

39
00:02:05,980 --> 00:02:09,350
Pra, edhe pse si njerëzit mund të shohë menjëherë se është 4

40
00:02:09,350 --> 00:02:12,300
elementi minimal, algorithm ynë ka nevojë të shohim në

41
00:02:12,300 --> 00:02:15,710
çdo element unsorted, edhe pasi kemi gjetur 4 -

42
00:02:15,710 --> 00:02:16,860
element minimale.

43
00:02:16,860 --> 00:02:19,900
Pra, tani që ne kemi gjetur elementin minimal, 4, ne do të duam

44
00:02:19,900 --> 00:02:23,410
për të lëvizur atë në pjesën e renditura të listës.

45
00:02:23,410 --> 00:02:27,320
Që ky është hapi i parë, kjo do të thotë që ne duam të vënë në 4

46
00:02:27,320 --> 00:02:29,680
fillimi i listës.

47
00:02:29,680 --> 00:02:33,040
Tani për tani 23 është në fillim të listës, në mënyrë

48
00:02:33,040 --> 00:02:36,080
le të bie në ujdi 4 dhe 23.

49
00:02:36,080 --> 00:02:38,870
Deri tani lista jonë duket si ky.

50
00:02:38,870 --> 00:02:42,710
Ne e dimë se 4 duhet të jenë në vendin e saj përfundimtare, sepse ajo është

51
00:02:42,710 --> 00:02:45,890
si elementi më i vogël dhe elementi në fillim

52
00:02:45,890 --> 00:02:46,960
nga lista.

53
00:02:46,960 --> 00:02:50,650
Pra, kjo do të thotë që ne kurrë nuk duhet të lëvizin atë përsëri.

54
00:02:50,650 --> 00:02:53,910
Pra, le të përsëris këtë proces për të shtuar një element të

55
00:02:53,910 --> 00:02:55,910
pjesë të renditura nga lista.

56
00:02:55,910 --> 00:02:58,950
Ne e dimë se ne nuk kemi nevojë të shikojmë në 4, për shkak se është

57
00:02:58,950 --> 00:03:00,000
renditura tashmë.

58
00:03:00,000 --> 00:03:03,540
Kështu që ne mund të fillojnë në 42, të cilat ne do të kujtohet si

59
00:03:03,540 --> 00:03:05,290
element minimale.

60
00:03:05,290 --> 00:03:08,700
Kështu që herën tjetër ne do të shikojmë në të 23 i cili është më pak se 42, kështu që ne

61
00:03:08,700 --> 00:03:11,620
kujtohet 23 është minimumi i ri.

62
00:03:11,620 --> 00:03:14,870
Tjetra ne shohim 16 e cila është më pak se 23, në mënyrë që

63
00:03:14,870 --> 00:03:16,800
16 është minimumi i ri.

64
00:03:16,800 --> 00:03:19,720
Tani ne shikojmë në 8 që është më pak se 16, në mënyrë që

65
00:03:19,720 --> 00:03:21,130
8 është minimumi i ri.

66
00:03:21,130 --> 00:03:25,900
8 Dhe në fund është më pak se 15, kështu që ne e dimë se është një minimum 8

67
00:03:25,900 --> 00:03:27,780
element unsorted.

68
00:03:27,780 --> 00:03:30,660
Kështu që do të thotë ne duhet të append 8 të renditura

69
00:03:30,660 --> 00:03:32,450
pjesë e listës.

70
00:03:32,450 --> 00:03:35,990
Tani për tani 4 është elementi zgjidhet vetëm, kështu që ne duam të zhvillohet

71
00:03:35,990 --> 00:03:38,410
8 tej në 4.

72
00:03:38,410 --> 00:03:41,920
Që nga 42 është elementi i parë në pjesën Unsorted e

73
00:03:41,920 --> 00:03:47,260
lista, ne do të duan të bie në ujdi 42 dhe 8.

74
00:03:47,260 --> 00:03:49,680
Deri tani lista jonë duket si ky.

75
00:03:49,680 --> 00:03:53,830
4 dhe 8 përfaqësojnë pjesën renditura e lista, dhe

76
00:03:53,830 --> 00:03:56,440
Numrat e mbetura përfaqësojnë unsorted

77
00:03:56,440 --> 00:03:58,260
pjesë e listës.

78
00:03:58,260 --> 00:04:00,630
Pra, le të vazhdojmë me një tjetër përsëritje.

79
00:04:00,630 --> 00:04:03,850
Ne fillim me 23 këtë kohë, pasi ne nuk kemi nevojë të shohim në

80
00:04:03,850 --> 00:04:05,770
e 4 dhe 8 më, sepse ata kanë

81
00:04:05,770 --> 00:04:07,660
tashmë janë të renditura.

82
00:04:07,660 --> 00:04:10,270
16 është më pak se 23, kështu që ne do të kujtojmë

83
00:04:10,270 --> 00:04:12,070
16 si minimum të ri.

84
00:04:12,070 --> 00:04:18,149
16 është më pak se 42, por 15 është më pak se 16, kështu që duhet të jetë 15

85
00:04:18,149 --> 00:04:20,480
elementi minimal unsorted.

86
00:04:20,480 --> 00:04:24,580
Pra, tani ne duam të bie në ujdi 15 dhe 23 të

87
00:04:24,580 --> 00:04:26,310
na jep këtë listë.

88
00:04:26,310 --> 00:04:30,500
Pjesa renditura e listës përbëhet nga 4, 8 dhe 15, dhe

89
00:04:30,500 --> 00:04:33,210
këto elemente janë Unsorted ende.

90
00:04:33,210 --> 00:04:36,900
Por kjo ndodh pikërisht kështu që elementi tjetër unsorted, 16,

91
00:04:36,900 --> 00:04:38,480
është renditur tashmë.

92
00:04:38,480 --> 00:04:42,060
Megjithatë, nuk ka asnjë mënyrë për të algorithm tonë për të dini se 16

93
00:04:42,060 --> 00:04:45,230
tashmë është në vendin e tij të saktë, kështu që ne ende nevojë për të

94
00:04:45,230 --> 00:04:47,870
përsëritur pikërisht procesin e njëjtë.

95
00:04:47,870 --> 00:04:53,750
Pra, ne shohim se është më pak se 16 42, dhe 16 është më pak se 23, në mënyrë që

96
00:04:53,750 --> 00:04:56,230
16 duhet të jetë element minimale.

97
00:04:56,230 --> 00:04:59,010
Është e pamundur të bie në ujdi me këtë element në vetvete, kështu që ne mund të

98
00:04:59,010 --> 00:05:01,780
thjesht lënë atë në këtë vend.

99
00:05:01,780 --> 00:05:04,660
Pra, ne kemi nevojë të kalojë një shumë të algorithm tonë.

100
00:05:04,660 --> 00:05:09,370
42 është më e madhe se 23, 23 kështu duhet të jetë

101
00:05:09,370 --> 00:05:10,970
element minimale unsorted.

102
00:05:10,970 --> 00:05:17,410
Pasi ne bie në ujdi 23 dhe 42, ne fund me finale tonë

103
00:05:17,410 --> 00:05:18,530
Lista e renditura -

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

105
00:05:23,390 --> 00:05:26,830
42 Ne e dimë se duhet të jetë në vendin e duhur pasi kjo është e

106
00:05:26,830 --> 00:05:30,210
Elementi i vetëm u largua, dhe kjo është lloj përzgjedhje.

107
00:05:30,210 --> 00:05:32,100
Le tani formalizojë algorithm tonë me disa

108
00:05:32,100 --> 00:05:34,540
pseudokod.

109
00:05:34,540 --> 00:05:37,760
On line një, ne mund të shohim se ne kemi nevojë për të integruar mbi

110
00:05:37,760 --> 00:05:39,530
çdo element i listës.

111
00:05:39,530 --> 00:05:42,150
Përveç element i fundit, pasi elementi 1

112
00:05:42,150 --> 00:05:44,230
Lista është renditur tashmë.

113
00:05:44,230 --> 00:05:48,100
On line dy, ne e konsiderojmë elementin e parë të unsorted

114
00:05:48,100 --> 00:05:51,080
pjesë e listës të jetë minimale, siç bëmë me tonë

115
00:05:51,080 --> 00:05:53,750
Për shembull, kështu që ne kemi diçka për të krahasuar të.

116
00:05:53,750 --> 00:05:57,260
Line tre fillon një lak të dytë në të cilën ne iterate mbi

117
00:05:57,260 --> 00:05:59,170
çdo element unsorted.

118
00:05:59,170 --> 00:06:02,150
Ne e dimë se pas kam iterations, pjesa renditura

119
00:06:02,150 --> 00:06:05,330
e listës sonë duhet të ketë elemente i në atë që çdo hap

120
00:06:05,330 --> 00:06:06,890
llojet një element.

121
00:06:06,890 --> 00:06:11,770
Pra, elementi i parë unsorted duhet të jetë në pozitë që unë plus 1.

122
00:06:11,770 --> 00:06:15,440
On line katër, ne krahasojmë elementin aktuale në minimum

123
00:06:15,440 --> 00:06:17,750
element që kemi parë deri tani.

124
00:06:17,750 --> 00:06:20,560
Nëse elementi i tanishëm është më i vogël se minimumi

125
00:06:20,560 --> 00:06:23,870
element, atëherë ne kujtojmë elementin e tanishme si e re

126
00:06:23,870 --> 00:06:26,250
minimale on line pesë.

127
00:06:26,250 --> 00:06:29,900
Së fundi, në linjat e gjashtë dhe shtatë, ne bie në ujdi minimum

128
00:06:29,900 --> 00:06:33,080
Elementi me elementin e parë Unsorted, duke

129
00:06:33,080 --> 00:06:36,990
duke shtuar se në pjesën e renditura të listës.

130
00:06:36,990 --> 00:06:40,030
Pasi ne kemi një algoritmi, një pyetje e rëndësishme që të kërkoni

131
00:06:40,030 --> 00:06:43,370
veten si programuesit është se sa kohë ka që marrin?

132
00:06:43,370 --> 00:06:46,970
Ne do të pari shtrohet pyetja se sa kohë do të marrë për këtë

133
00:06:46,970 --> 00:06:50,070
algorithm për të kandiduar në rastin më të keq?

134
00:06:50,070 --> 00:06:51,640
Kujtoj ne përfaqësojmë këtë drejtimin

135
00:06:51,640 --> 00:06:55,060
Ora me simbol Big O.

136
00:06:55,060 --> 00:06:58,650
Në mënyrë që të përcaktojë elementin minimal Unsorted, ne

137
00:06:58,650 --> 00:07:01,880
në thelb duhej të krahasojnë çdo element në listë për

138
00:07:01,880 --> 00:07:04,040
çdo element tjetër në listë.

139
00:07:04,040 --> 00:07:08,430
Intuitive, kjo tingëllon si një O e operimit n katror.

140
00:07:08,430 --> 00:07:12,050
Kërkim në pseudokod tonë, ne gjithashtu kemi një lak mbivendosur brenda

141
00:07:12,050 --> 00:07:14,420
tjetër loop, e cila me të vërtetë tingëllon si një O

142
00:07:14,420 --> 00:07:16,480
e veprimit n katror.

143
00:07:16,480 --> 00:07:19,250
Megjithatë, mos harroni se ne nuk duhet të shohim mbi

144
00:07:19,250 --> 00:07:23,460
Lista e të gjithë kur përcaktohet elementin minimal Unsorted?

145
00:07:23,460 --> 00:07:26,600
Pasi ne e dinim se ishte 4 renditura, për shembull, ne nuk

146
00:07:26,600 --> 00:07:28,170
duhet të shohim në atë përsëri.

147
00:07:28,170 --> 00:07:31,020
Pra, e bën këtë më të ulët kohë running?

148
00:07:31,020 --> 00:07:34,510
Për listën tonë të gjatësisë 6, kemi nevojë për të bërë pesë

149
00:07:34,510 --> 00:07:37,990
krahasimet për elementin e parë, katër krahasimet për

150
00:07:37,990 --> 00:07:40,750
elementi i dytë, dhe kështu në.

151
00:07:40,750 --> 00:07:44,690
Kjo do të thotë se numri i përgjithshëm i hapave është shuma e

152
00:07:44,690 --> 00:07:49,160
integers nga 1 deri në gjatësinë e listës minus 1.

153
00:07:49,160 --> 00:07:51,005
Ne mund të përfaqësojë këtë me një mbledhje.

154
00:07:57,980 --> 00:07:59,910
Ne nuk do të shkojë në summations këtu.

155
00:07:59,910 --> 00:08:04,900
Por rezulton se kjo përmbledhje është e barabartë me n herë

156
00:08:04,900 --> 00:08:07,540
n minus 1 mbi 2.

157
00:08:07,540 --> 00:08:14,220
Ose ekuivalente, n katror mbi 2 minus n mbi 2.

158
00:08:14,220 --> 00:08:18,860
Kur flasim për kohën e duhur asymptotic, ky term n katror

159
00:08:18,860 --> 00:08:22,070
do të dominojnë këtë term n.

160
00:08:22,070 --> 00:08:27,850
Pra, zgjedhja është lloj O n katror.

161
00:08:27,850 --> 00:08:31,460
Kujtojnë se në shembullin tonë, lloj përzgjedhje ende e nevojshme për të

162
00:08:31,460 --> 00:08:33,850
kontrolloni nëse një numër që është renditur tashmë

163
00:08:33,850 --> 00:08:35,450
nevojshme për të lëvizur.

164
00:08:35,450 --> 00:08:38,929
Kështu që do të thotë se në qoftë se ne u lloj përzgjedhje mbi një tashmë

165
00:08:38,929 --> 00:08:43,070
renditura listë, ajo do të kërkojë të njëjtin numër hapash si ajo

166
00:08:43,070 --> 00:08:46,340
do kur drejtimin mbi një listë krejtësisht Unsorted.

167
00:08:46,340 --> 00:08:51,470
Pra, ka një lloj përzgjedhje performancën më të mirë rastin e n katror,

168
00:08:51,470 --> 00:08:56,820
që ne përfaqësojmë me omega n katror.

169
00:08:56,820 --> 00:08:58,600
Dhe kjo është ajo për lloj përzgjedhjes.

170
00:08:58,600 --> 00:09:00,630
Vetëm një nga algoritme shumë ne mund të

171
00:09:00,630 --> 00:09:02,390
përdorin për të zgjidhur një listë.

172
00:09:02,390 --> 00:09:05,910
Emri im është Tommy, dhe kjo është CS50.