1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] TOMMY: Võtame pilk valik omamoodi, algoritm

2
00:00:09,980 --> 00:00:12,800
võtmise numbrite loendi ja sorteerimine neid.

3
00:00:12,800 --> 00:00:15,750
Algoritm, pea meeles, on lihtsalt samm-sammult

4
00:00:15,750 --> 00:00:18,370
korra saavutamise ülesanne.

5
00:00:18,370 --> 00:00:21,470
Põhiidee valik omamoodi on jagada

6
00:00:21,470 --> 00:00:23,390
meie nimekirjas kaheks osaks -

7
00:00:23,390 --> 00:00:26,810
järjestatud osa ja sorteerimata osa.

8
00:00:26,810 --> 00:00:30,200
Igal sammul algoritm, number on liikunud

9
00:00:30,200 --> 00:00:33,800
sortimata osal järjestatud osa kuni lõpuks

10
00:00:33,800 --> 00:00:35,880
Kogu nimekiri on järjestatud.

11
00:00:35,880 --> 00:00:38,510
Nii et siin on nimekiri kuus numbrit -

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

13
00:00:44,010 --> 00:00:47,680
Just nüüd kogu nimekirja peetakse sortimata.

14
00:00:47,680 --> 00:00:51,770
Kuigi arv nagu 16 võib olla juba oma õige

15
00:00:51,770 --> 00:00:56,040
asukoht, meie algoritm on kuidagi võimalik teada, et kuni

16
00:00:56,040 --> 00:00:57,980
Kogu nimekiri on järjestatud.

17
00:00:57,980 --> 00:01:01,355
Nii et me käsitleme igat numbrit võib sortimata kuni me järjestada

18
00:01:01,355 --> 00:01:03,800
seda ise.

19
00:01:03,800 --> 00:01:06,890
Me teame, et me tahame nimekiri olema tõusvas järjestuses.

20
00:01:06,890 --> 00:01:10,200
Nii et me tahame üles ehitada järjestatud osa meie nimekirja

21
00:01:10,200 --> 00:01:13,280
vasakult paremale, väiksemast ja lõpetades suuremaga.

22
00:01:13,280 --> 00:01:17,970
Selleks, et me peame leidma minimaalse sortimata element

23
00:01:17,970 --> 00:01:21,350
ja pane see lõpus järjestatud osa.

24
00:01:21,350 --> 00:01:25,370
Kuna see loetelu ei ole sorteeritud, ainus viis seda teha on

25
00:01:25,370 --> 00:01:29,330
pilk iga element sorteerimata osa, meenutades

26
00:01:29,330 --> 00:01:32,010
mis element on madalaim ja võrrelda

27
00:01:32,010 --> 00:01:33,770
iga osa sellest.

28
00:01:33,770 --> 00:01:36,150
Nii et me kõigepealt vaadata 23.

29
00:01:36,150 --> 00:01:38,650
See on esimene element oleme näinud, nii me meeles

30
00:01:38,650 --> 00:01:40,050
see minimaalseks.

31
00:01:40,050 --> 00:01:42,320
Järgmine me vaatame 42.

32
00:01:42,320 --> 00:01:46,720
42 on suurem kui 23, nii 23 on ikka vähe.

33
00:01:46,720 --> 00:01:51,210
Järgmine on 4, mis on väiksem kui 23, nii me mäletama 4

34
00:01:51,210 --> 00:01:52,880
kui uus minimaalselt.

35
00:01:52,880 --> 00:01:56,380
Järgmine on 16, mis on suurem kui 4, seega 4

36
00:01:56,380 --> 00:01:57,980
on veel minimaalne.

37
00:01:57,980 --> 00:02:03,670
8 on suurem kui 4 ja 15 on suurem kui 4, SO 4 peavad olema

38
00:02:03,670 --> 00:02:05,980
väikseim sortimata element.

39
00:02:05,980 --> 00:02:09,350
Nii et kuigi inimestena saame kohe näha, et 4 on

40
00:02:09,350 --> 00:02:12,300
minimaalne element, meie algoritm peab uurima

41
00:02:12,300 --> 00:02:15,710
iga sortimata element, isegi kui me oleme leidnud 4 -

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

43
00:02:16,860 --> 00:02:19,900
Nüüd, et oleme leidnud minimaalne element, 4, me tahame

44
00:02:19,900 --> 00:02:23,410
liikuda see sorteeritakse osa nimekirjast.

45
00:02:23,410 --> 00:02:27,320
Kuna see on esimene samm, see tähendab, et me taha panna 4 asendisse

46
00:02:27,320 --> 00:02:29,680
loetelu alguses.

47
00:02:29,680 --> 00:02:33,040
Praegu 23 on alguses nimekirja, nii

48
00:02:33,040 --> 00:02:36,080
olgem vahetada 4 ja 23.

49
00:02:36,080 --> 00:02:38,870
Nüüd meie nimekiri näeb välja selline.

50
00:02:38,870 --> 00:02:42,710
Me teame, et 4 peab olema oma lõplik asukoht, sest see on

51
00:02:42,710 --> 00:02:45,890
nii väikseim element ja element alguses

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

53
00:02:46,960 --> 00:02:50,650
Nii et see tähendab, et me ei ole kunagi vaja minna uuesti.

54
00:02:50,650 --> 00:02:53,910
Nii et olgem korrake seda protsessi lisada veel üks element, mis

55
00:02:53,910 --> 00:02:55,910
järjestatud osa nimekirjast.

56
00:02:55,910 --> 00:02:58,950
Me teame, et meil ei ole vaja vaadata 4, sest see on

57
00:02:58,950 --> 00:03:00,000
juba järjestatud.

58
00:03:00,000 --> 00:03:03,540
Nii saame alustada kell 42, mis me mäletama kui

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

60
00:03:05,290 --> 00:03:08,700
Nii et järgmine me vaatame 23, mis on vähem kui 42, nii et me

61
00:03:08,700 --> 00:03:11,620
Jäta 23 on uus miinimum.

62
00:03:11,620 --> 00:03:14,870
Järgmine näeme 16, mis on vähem kui 23, nii

63
00:03:14,870 --> 00:03:16,800
16 on uus miinimum.

64
00:03:16,800 --> 00:03:19,720
Nüüd vaatame 8, mis on väiksem kui 16, nii

65
00:03:19,720 --> 00:03:21,130
8 on uus miinimum.

66
00:03:21,130 --> 00:03:25,900
Ja lõpuks 8 on alla 15, nii et me teame, et 8 on minimaalne

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

68
00:03:27,780 --> 00:03:30,660
Nii et see tähendab, et peaksime lisama 8 järjestatud

69
00:03:30,660 --> 00:03:32,450
osa nimekirjast.

70
00:03:32,450 --> 00:03:35,990
Praegu 4 on ainult järjestatud element, nii et me tahame panna

71
00:03:35,990 --> 00:03:38,410
8 kõrval 4.

72
00:03:38,410 --> 00:03:41,920
Kuna 42 on esimene element sorteerimata osa

73
00:03:41,920 --> 00:03:47,260
loetelu, me tahame, et vahetada 42 ja 8.

74
00:03:47,260 --> 00:03:49,680
Nüüd meie nimekiri näeb välja selline.

75
00:03:49,680 --> 00:03:53,830
4 ja 8 moodustavad järjestatud osa nimekirja ja

76
00:03:53,830 --> 00:03:56,440
Ülejäänud numbrid näitavad sortimata

77
00:03:56,440 --> 00:03:58,260
osa nimekirjast.

78
00:03:58,260 --> 00:04:00,630
Nii et olgem jätkata teise iteratsiooni.

79
00:04:00,630 --> 00:04:03,850
Alustame 23 seekord, sest me ei pea vaatama

80
00:04:03,850 --> 00:04:05,770
4 ja 8 enam, sest need oleme

81
00:04:05,770 --> 00:04:07,660
juba järjestatud.

82
00:04:07,660 --> 00:04:10,270
16 on alla 23, nii me meeles

83
00:04:10,270 --> 00:04:12,070
16 Nagu uus miinimum.

84
00:04:12,070 --> 00:04:18,149
16 on väiksem kui 42, kuid 15 on alla 16, seega 15 peab olema

85
00:04:18,149 --> 00:04:20,480
miinimum sortimata element.

86
00:04:20,480 --> 00:04:24,580
Nii et nüüd me tahame vahetada 15 ja 23

87
00:04:24,580 --> 00:04:26,310
anna meile seda nimekirja.

88
00:04:26,310 --> 00:04:30,500
Järjestatud osa loetelu koosneb 4, 8 ja 15, ja

89
00:04:30,500 --> 00:04:33,210
need elemendid on ikka sortimata.

90
00:04:33,210 --> 00:04:36,900
Aga see lihtsalt nii juhtub, et järgmise sortimata element, 16,

91
00:04:36,900 --> 00:04:38,480
on juba järjestatud.

92
00:04:38,480 --> 00:04:42,060
Kuid seal on kuidagi meie algoritm teada, et 16

93
00:04:42,060 --> 00:04:45,230
on juba oma õigesse asukohta, seega peame siiski

94
00:04:45,230 --> 00:04:47,870
korrata täpselt sama protsessi.

95
00:04:47,870 --> 00:04:53,750
Nii näeme, et 16 on väiksem kui 42, ja 16 on väiksem kui 23, nii

96
00:04:53,750 --> 00:04:56,230
16 tuleb minimaalne element.

97
00:04:56,230 --> 00:04:59,010
See on võimatu, et vahetada see element iseendaga, et saaksime

98
00:04:59,010 --> 00:05:01,780
lihtsalt jätke see selles kohas.

99
00:05:01,780 --> 00:05:04,660
Seega on meil vaja veel üht liigu meie algoritm.

100
00:05:04,660 --> 00:05:09,370
42 on suurem kui 23, nii et 23 tuleb

101
00:05:09,370 --> 00:05:10,970
miinimum sortimata element.

102
00:05:10,970 --> 00:05:17,410
Kui me vahetada 23 ja 42, me lõpetame meie lõplik

103
00:05:17,410 --> 00:05:18,530
järjestatud loetelu -

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

105
00:05:23,390 --> 00:05:26,830
Me teame, 42 peab olema õiges kohas, sest see on

106
00:05:26,830 --> 00:05:30,210
ainult element left, ja see on valik omamoodi.

107
00:05:30,210 --> 00:05:32,100
Lähme nüüd ametlikuks meie algoritm mõned

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

109
00:05:34,540 --> 00:05:37,760
Liinil, näeme, et meil on vaja integreerida üle

110
00:05:37,760 --> 00:05:39,530
iga element nimekirja.

111
00:05:39,530 --> 00:05:42,150
Välja arvatud viimane osa, kuna 1 element

112
00:05:42,150 --> 00:05:44,230
nimekiri on juba järjestatud.

113
00:05:44,230 --> 00:05:48,100
Teisel liinil, arvame esimese osa sortimata

114
00:05:48,100 --> 00:05:51,080
osa nimekirjas olevat minimaalne, nagu tegime meie

115
00:05:51,080 --> 00:05:53,750
Näiteks, seega on meil midagi võrrelda.

116
00:05:53,750 --> 00:05:57,260
Kolmas liin algab teine ​​silmus, kus me itereerime

117
00:05:57,260 --> 00:05:59,170
iga sortimata element.

118
00:05:59,170 --> 00:06:02,150
Me teame, et pärast i iteratsiooni, järjestatud osa

119
00:06:02,150 --> 00:06:05,330
meie nimekirjas peab olema i elementidega sest iga samm

120
00:06:05,330 --> 00:06:06,890
sorteerib üks element.

121
00:06:06,890 --> 00:06:11,770
Nii et esimene sortimata element peab olema asendis i pluss 1.

122
00:06:11,770 --> 00:06:15,440
On line neli, me võrrelda praegust element minimaalset

123
00:06:15,440 --> 00:06:17,750
element, et oleme näinud siiani.

124
00:06:17,750 --> 00:06:20,560
Kui praegune element on väiksem kui minimaalne

125
00:06:20,560 --> 00:06:23,870
element, siis me mäletame praegune element nagu uus

126
00:06:23,870 --> 00:06:26,250
miinimum on line viis.

127
00:06:26,250 --> 00:06:29,900
Lõpuks liinidel kuue ja seitsme me swap minimaalne

128
00:06:29,900 --> 00:06:33,080
elemendi esimese sortimata element, mis

129
00:06:33,080 --> 00:06:36,990
lisades selle järjestatud osa nimekirjast.

130
00:06:36,990 --> 00:06:40,030
Kui meil on algoritm, olulisem küsimus küsida

131
00:06:40,030 --> 00:06:43,370
end programmeerijad on, kui kaua see veel kestab?

132
00:06:43,370 --> 00:06:46,970
Me kõigepealt küsida, kui kaua see aega võtab selle

133
00:06:46,970 --> 00:06:50,070
algoritm joosta halvimal juhul?

134
00:06:50,070 --> 00:06:51,640
Meenutagem siinkohal me esindame see töötab

135
00:06:51,640 --> 00:06:55,060
aega suur O notatsiooni.

136
00:06:55,060 --> 00:06:58,650
Selleks, et määrata kindlaks minimaalne sortimata element, me

137
00:06:58,650 --> 00:07:01,880
sisuliselt oli võrrelda iga element loendis

138
00:07:01,880 --> 00:07:04,040
iga teine ​​element nimekirjas.

139
00:07:04,040 --> 00:07:08,430
Intuitiivselt, see kõlab nagu O n ruudus operatsiooni.

140
00:07:08,430 --> 00:07:12,050
Vaadates meie pseudokoodi, meil on ka loop pesitses sees

141
00:07:12,050 --> 00:07:14,420
teine ​​silmus, mis tõesti kõlab nagu O

142
00:07:14,420 --> 00:07:16,480
n ruudus operatsiooni.

143
00:07:16,480 --> 00:07:19,250
Kuid pidage meeles, et me ei pea üle vaatama

144
00:07:19,250 --> 00:07:23,460
kogu nimekirja määramisel miinimum sortimata element?

145
00:07:23,460 --> 00:07:26,600
Kui me teadsime, et 4 oli järjestatud, näiteks me ei

146
00:07:26,600 --> 00:07:28,170
vaja vaadata uuesti.

147
00:07:28,170 --> 00:07:31,020
Kas see siis alumine sõiduaega?

148
00:07:31,020 --> 00:07:34,510
Meie nimekirja pikkus 6, meil oli vaja teha viis

149
00:07:34,510 --> 00:07:37,990
võrdlused esimese elemendi eest, neli võrdlust

150
00:07:37,990 --> 00:07:40,750
Teine element, ja nii edasi.

151
00:07:40,750 --> 00:07:44,690
See tähendab, et kogu sammude arv on summa

152
00:07:44,690 --> 00:07:49,160
täisarvud 1 kuni pikkus nimekirja miinus 1.

153
00:07:49,160 --> 00:07:51,005
Me ei esinda seda liitmise.

154
00:07:57,980 --> 00:07:59,910
Me ei hakka kohtuvaidlust siin.

155
00:07:59,910 --> 00:08:04,900
Aga selgub, et see liitmise on võrdne n korda

156
00:08:04,900 --> 00:08:07,540
n miinus 1 üle 2.

157
00:08:07,540 --> 00:08:14,220
Ehk samaväärselt, n ruudus üle 2 miinus n üle 2.

158
00:08:14,220 --> 00:08:18,860
Rääkides asümptootilisest runtime, see n ruudus perspektiivis

159
00:08:18,860 --> 00:08:22,070
läheb domineerima see n perspektiivis.

160
00:08:22,070 --> 00:08:27,850
Nii et valik omamoodi on O n ruudus.

161
00:08:27,850 --> 00:08:31,460
Tuletame meelde, et meie näites, valik omamoodi ikka vaja

162
00:08:31,460 --> 00:08:33,850
kontrollida, kas arv, mis oli juba sorteeritud

163
00:08:33,850 --> 00:08:35,450
vaja vedada.

164
00:08:35,450 --> 00:08:38,929
See tähendab, et kui me jooksime valik omamoodi üle juba

165
00:08:38,929 --> 00:08:43,070
järjestatud nimekirja, oleks vaja sama hulk meetmeid, mida ta

166
00:08:43,070 --> 00:08:46,340
oleks sõites üle täiesti sortimata nimekirja.

167
00:08:46,340 --> 00:08:51,470
Nii et valik omamoodi on parimal juhul täitmisel n ruudus,

168
00:08:51,470 --> 00:08:56,820
mis me esindame omega n ruudus.

169
00:08:56,820 --> 00:08:58,600
Ja see on see valik omamoodi.

170
00:08:58,600 --> 00:09:00,630
Lihtsalt üks paljudest algoritme saame

171
00:09:00,630 --> 00:09:02,390
kasutada sorteerida nimekirja.

172
00:09:02,390 --> 00:09:05,910
Minu nimi on Tommy, ja see on cs50.