1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: Ejja tagħti ħarsa lejn it-tip ta 'għażla, algoriżmu

2
00:00:09,980 --> 00:00:12,800
għat-teħid ta 'lista ta' numri u l-għażla tagħhom.

3
00:00:12,800 --> 00:00:15,750
Algoritmu, ftakar, huwa sempliċement pass-pass

4
00:00:15,750 --> 00:00:18,370
proċedura għall-kisba ta 'kompitu.

5
00:00:18,370 --> 00:00:21,470
L-idea bażika wara sort għażla huwa li jaqsam

6
00:00:21,470 --> 00:00:23,390
lista tagħna f'żewġ porzjonijiet -

7
00:00:23,390 --> 00:00:26,810
porzjon magħżula u porzjon mhux magħżul.

8
00:00:26,810 --> 00:00:30,200
F'kull pass ta 'l-algoritmu, numru jiġi mċaqlaq mill-

9
00:00:30,200 --> 00:00:33,800
porzjon mhux magħżul għall-porzjon magħżul sakemm eventwalment l-

10
00:00:33,800 --> 00:00:35,880
lista sħiħa qed magħżula.

11
00:00:35,880 --> 00:00:38,510
Allura hawnhekk lista ta 'sitt numri -

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

13
00:00:44,010 --> 00:00:47,680
Dritt issa l-lista sħiħa hija kkunsidrata mhux magħżul.

14
00:00:47,680 --> 00:00:51,770
Anke jekk numru simili 16 tista 'tkun diġà fil korretta tagħha

15
00:00:51,770 --> 00:00:56,040
lokalità, algoritmu tagħna m'għandha l-ebda mod sabiex tkun taf li sakemm l-

16
00:00:56,040 --> 00:00:57,980
lista sħiħa qed magħżula.

17
00:00:57,980 --> 00:01:01,355
Allura aħna ser jikkunsidraw kull numru li għandu mhux magħżul sakemm aħna issolvi

18
00:01:01,355 --> 00:01:03,800
dan lilna nfusna.

19
00:01:03,800 --> 00:01:06,890
Aħna nafu li aħna rridu l-lista li tkun f'ordni axxendenti.

20
00:01:06,890 --> 00:01:10,200
Allura aħna ser jridu jibnu l-porzjon magħżula ta 'lista tagħna

21
00:01:10,200 --> 00:01:13,280
mix-xellug għal-lemin, iżgħar għall-akbar.

22
00:01:13,280 --> 00:01:17,970
Biex tagħmel dan, aħna ser bżonn issib l-element mhux magħżul minimu

23
00:01:17,970 --> 00:01:21,350
u poġġih fl-aħħar tal-porzjon magħżul.

24
00:01:21,350 --> 00:01:25,370
Peress li din il-lista ma jintgħażlux, l-uniku mod biex tagħmel dan huwa li

25
00:01:25,370 --> 00:01:29,330
tħares lejn kull element fil-porzjon mhux magħżul, ftakar

26
00:01:29,330 --> 00:01:32,010
li l-element huwa l-aktar baxx u t-tqabbil

27
00:01:32,010 --> 00:01:33,770
kull element għal dan.

28
00:01:33,770 --> 00:01:36,150
Allura aħna ser ewwel tħares lejn il-23.

29
00:01:36,150 --> 00:01:38,650
Dan huwa l-ewwel element Rajna, hekk aħna ser tiftakar

30
00:01:38,650 --> 00:01:40,050
bħala l-minimu.

31
00:01:40,050 --> 00:01:42,320
Li jmiss aħna ser tħares lejn 42.

32
00:01:42,320 --> 00:01:46,720
42 hija akbar minn 23, hekk 23 għadha l-minimu.

33
00:01:46,720 --> 00:01:51,210
Li jmiss huwa l-4 li huwa inqas minn 23, hekk aħna ser tiftakar 4

34
00:01:51,210 --> 00:01:52,880
bħala l-minimu l-ġdid.

35
00:01:52,880 --> 00:01:56,380
Li jmiss huwa 16 li hija akbar minn 4, hekk 4

36
00:01:56,380 --> 00:01:57,980
għadu l-minimu.

37
00:01:57,980 --> 00:02:03,670
8 hija akbar minn 4, u 15 hija akbar minn 4, hekk 4 għandhom ikunu

38
00:02:03,670 --> 00:02:05,980
l-element mhux magħżul iżgħar.

39
00:02:05,980 --> 00:02:09,350
Allura anke jekk bħala bnedmin nistgħu immedjatament tara li 4 huwa

40
00:02:09,350 --> 00:02:12,300
l-element minimu, algoritmu tagħna teħtieġ li tħares lejn

41
00:02:12,300 --> 00:02:15,710
kull element mhux magħżul, anki wara konna sabet 4 - l-

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

43
00:02:16,860 --> 00:02:19,900
Allura issa li aħna ħadthom misjuba-element minimu, 4, aħna ser rridu

44
00:02:19,900 --> 00:02:23,410
li jġorrhom fil-porzjon magħżula tal-lista.

45
00:02:23,410 --> 00:02:27,320
Peress li dan huwa l-ewwel pass, dan ifisser li rridu li tqiegħed 4 fi

46
00:02:27,320 --> 00:02:29,680
il-bidu tal-lista.

47
00:02:29,680 --> 00:02:33,040
Dritt issa 23 huwa fil-bidu tal-lista, sabiex

48
00:02:33,040 --> 00:02:36,080
ejja tpartit l-4 u l-23.

49
00:02:36,080 --> 00:02:38,870
Allura issa lista tagħna tidher bħal dan.

50
00:02:38,870 --> 00:02:42,710
Aħna nafu li 4 għandu jkun fil-post finali tagħha, minħabba li hija

51
00:02:42,710 --> 00:02:45,890
kemm l-element iżgħar u l-element fil-bidu

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

53
00:02:46,960 --> 00:02:50,650
Allura dan ifisser li aħna ma qatt ħtieġa li jġorrhom mill-ġdid.

54
00:02:50,650 --> 00:02:53,910
Mela ejja irrepeti dan il-proċess biex iżżid element ieħor għall-

55
00:02:53,910 --> 00:02:55,910
porzjon magħżula tal-lista.

56
00:02:55,910 --> 00:02:58,950
Aħna nafu li aħna ma bżonn li nħarsu lejn il-4, għaliex dan huwa

57
00:02:58,950 --> 00:03:00,000
diġà magħżula.

58
00:03:00,000 --> 00:03:03,540
Allura nistgħu tibda fil-42, li aħna ser tiftakar bħala l-

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

60
00:03:05,290 --> 00:03:08,700
Allura li jmiss aħna ser tħares lejn il-23 li hija inqas minn 42, hekk aħna

61
00:03:08,700 --> 00:03:11,620
tiftakar 23 huwa l-minimu ġdid.

62
00:03:11,620 --> 00:03:14,870
Li jmiss naraw il-16 li huwa anqas minn 23, hekk

63
00:03:14,870 --> 00:03:16,800
16 huwa l-minimu ġdid.

64
00:03:16,800 --> 00:03:19,720
Issa aħna nħarsu lejn l-8 li hija inqas minn 16, hekk

65
00:03:19,720 --> 00:03:21,130
8 hija l-minimu ġdid.

66
00:03:21,130 --> 00:03:25,900
U finalment 8 huwa anqas minn 15, hekk nafu li 8 huwa minimu

67
00:03:25,900 --> 00:03:27,780
mhux magħżul element.

68
00:03:27,780 --> 00:03:30,660
Allura dan ifisser li għandna jehmeż 8 għall-magħżula

69
00:03:30,660 --> 00:03:32,450
porzjon tal-lista.

70
00:03:32,450 --> 00:03:35,990
Dritt issa 4 huwa l-uniku element magħżula, hekk aħna tixtieq li ssir

71
00:03:35,990 --> 00:03:38,410
-li jmiss 8 għall-4.

72
00:03:38,410 --> 00:03:41,920
Peress 42 huwa l-ewwel element fil-porzjon mhux magħżul tal-

73
00:03:41,920 --> 00:03:47,260
lista, aħna ser tixtieq li tpartit l-42 u l-8.

74
00:03:47,260 --> 00:03:49,680
Allura issa lista tagħna tidher bħal dan.

75
00:03:49,680 --> 00:03:53,830
4 u 8 jirrappreżentaw il-porzjon magħżula tal-lista, u l-

76
00:03:53,830 --> 00:03:56,440
numri li jifdal jirrappreżentaw l-mhux magħżul

77
00:03:56,440 --> 00:03:58,260
porzjon tal-lista.

78
00:03:58,260 --> 00:04:00,630
Mela ejja tkompli ma 'iterazzjoni.

79
00:04:00,630 --> 00:04:03,850
Nibdew bl 23 dan iż-żmien, peress li aħna ma bżonn li nħarsu lejn

80
00:04:03,850 --> 00:04:05,770
l-4 u l-8 jibqgħalu għaliex stajt

81
00:04:05,770 --> 00:04:07,660
diġà ġew magħżula.

82
00:04:07,660 --> 00:04:10,270
16 huwa anqas minn 23, hekk aħna ser tiftakar

83
00:04:10,270 --> 00:04:12,070
16, kif l-minimu ġdid.

84
00:04:12,070 --> 00:04:18,149
16 huwa anqas minn 42, iżda 15 hija anqas minn 16, u għalhekk 15 għandu jkun

85
00:04:18,149 --> 00:04:20,480
l-element mhux magħżul minimu.

86
00:04:20,480 --> 00:04:24,580
Allura issa irridu li tpartit l-15 u l-23 sa

87
00:04:24,580 --> 00:04:26,310
agħtina din il-lista.

88
00:04:26,310 --> 00:04:30,500
Il-porzjon magħżula tal-lista tikkonsisti minn 4, 8 u 15, u

89
00:04:30,500 --> 00:04:33,210
dawn l-elementi għadhom mhux magħżula.

90
00:04:33,210 --> 00:04:36,900
Iżda huwa biss hekk jiġri li l-element mhux magħżul li jmiss, 16,

91
00:04:36,900 --> 00:04:38,480
huwa diġà magħżula.

92
00:04:38,480 --> 00:04:42,060
Madankollu, hemm ebda mod biex algoritmu tagħna jkunu jafu li 16

93
00:04:42,060 --> 00:04:45,230
hija diġà fil-post korretta tagħha, hekk aħna għad iridu

94
00:04:45,230 --> 00:04:47,870
irrepeti eżattament l-istess proċess.

95
00:04:47,870 --> 00:04:53,750
Allura naraw li 16 hija inqas minn 42, u 16 huwa anqas minn 23, hekk

96
00:04:53,750 --> 00:04:56,230
16 għandha tkun l-element minimu.

97
00:04:56,230 --> 00:04:59,010
Huwa impossibbli li tpartit dan l-element ma innifsu, sabiex inkunu nistgħu

98
00:04:59,010 --> 00:05:01,780
sempliċiment jitilqu minnu f'dan il-post.

99
00:05:01,780 --> 00:05:04,660
Għalhekk għandna bżonn pass wieħed aktar ta 'algoritmu tagħna.

100
00:05:04,660 --> 00:05:09,370
42 huwa akbar minn 23, u għalhekk 23 għandu jkun il-

101
00:05:09,370 --> 00:05:10,970
element mhux magħżul minimu.

102
00:05:10,970 --> 00:05:17,410
Ladarba aħna tpartit l-23 u l-42, aħna jispiċċaw ma 'finali tagħna

103
00:05:17,410 --> 00:05:18,530
magħżula 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
Nafu 42 għandu jkun fil-post korretta peress li huwa l-

106
00:05:26,830 --> 00:05:30,210
uniku element xellug, u li sort għażla.

107
00:05:30,210 --> 00:05:32,100
Ejja issa jifformalizza algoritmu tagħna ma 'xi

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

109
00:05:34,540 --> 00:05:37,760
Fuq linja waħda, nistgħu naraw li għandna bżonn li jiġu integrati aktar

110
00:05:37,760 --> 00:05:39,530
kull element tal-lista.

111
00:05:39,530 --> 00:05:42,150
Ħlief l-aħħar element, peress li l-element 1

112
00:05:42,150 --> 00:05:44,230
lista hija diġà magħżula.

113
00:05:44,230 --> 00:05:48,100
Fuq linja 2, inqisu li l-ewwel element tal-mhux magħżul

114
00:05:48,100 --> 00:05:51,080
porzjon tal-lista biex ikunu l-minimu, kif għamilna ma 'tagħna

115
00:05:51,080 --> 00:05:53,750
eżempju, hekk aħna ikollhom xi ħaġa li jqabblu.

116
00:05:53,750 --> 00:05:57,260
Linja 3 jibda loop 2 li aħna jtenni aktar

117
00:05:57,260 --> 00:05:59,170
kull element mhux magħżul.

118
00:05:59,170 --> 00:06:02,150
Aħna nafu li wara i iterazzjonijiet, l-magħżula porzjon

119
00:06:02,150 --> 00:06:05,330
tal-lista tagħna għandu jkollhom i elementi fiha mill f'kull pass

120
00:06:05,330 --> 00:06:06,890
xorta 1 elementi.

121
00:06:06,890 --> 00:06:11,770
Allura l-element mhux magħżul 1 għandhom ikunu f'pożizzjoni i plus 1.

122
00:06:11,770 --> 00:06:15,440
Fuq linja 4, inqabblu l-element attwali għall-minimu

123
00:06:15,440 --> 00:06:17,750
element li Rajna s'issa.

124
00:06:17,750 --> 00:06:20,560
Jekk l-element attwali hija iżgħar mill-minimu

125
00:06:20,560 --> 00:06:23,870
element, allura aħna niftakru l-element kurrenti bħala l-ġdid

126
00:06:23,870 --> 00:06:26,250
minimu fuq linja 5.

127
00:06:26,250 --> 00:06:29,900
Fl-aħħarnett, fuq il-linji 6 u 7, aħna tpartit l-minimu

128
00:06:29,900 --> 00:06:33,080
element bl-element mhux magħżul l-ewwel, biex b'hekk

129
00:06:33,080 --> 00:06:36,990
żżidu mal-porzjon magħżula tal-lista.

130
00:06:36,990 --> 00:06:40,030
Ladarba għandna algoritmu, kwistjoni importanti li titlob

131
00:06:40,030 --> 00:06:43,370
ruħna bħala programmaturi huwa kemm ma dan jieħu?

132
00:06:43,370 --> 00:06:46,970
Aħna ser ewwel titlob il-kwistjoni kemm żmien ma jieħdu għal dan

133
00:06:46,970 --> 00:06:50,070
algoritmu jiddekorri fl-agħar każ?

134
00:06:50,070 --> 00:06:51,640
Recall nirrappreżentaw dan tmexxija

135
00:06:51,640 --> 00:06:55,060
ħin ma 'O notazzjoni kbar.

136
00:06:55,060 --> 00:06:58,650
Sabiex jiġi ddeterminat l-element mhux magħżul minimu, aħna

137
00:06:58,650 --> 00:07:01,880
essenzjalment kellhom iqabblu kull element fil-lista biex

138
00:07:01,880 --> 00:07:04,040
kull element ieħor fil-lista.

139
00:07:04,040 --> 00:07:08,430
Intuwittivament, dan ħsejjes bħal O ta 'n-operazzjoni kwadru.

140
00:07:08,430 --> 00:07:12,050
Ħarsa lejn pseudocode tagħna, aħna għandna wkoll loop nested ġewwa

141
00:07:12,050 --> 00:07:14,420
ieħor loop, li tabilħaqq tinstema 'O

142
00:07:14,420 --> 00:07:16,480
ta 'operazzjoni n kwadru.

143
00:07:16,480 --> 00:07:19,250
Madankollu, ftakar li aħna ma bżonn li tħares fuq il-

144
00:07:19,250 --> 00:07:23,460
lista sħiħa meta jiġi ddeterminat l-element mhux magħżul minimu?

145
00:07:23,460 --> 00:07:26,600
Ladarba aħna kien jaf li l-4 kien magħżul, per eżempju, aħna ma

146
00:07:26,600 --> 00:07:28,170
bżonn li nħarsu lejn din darb'oħra.

147
00:07:28,170 --> 00:07:31,020
Allura ma dan jbaxxu l-running time?

148
00:07:31,020 --> 00:07:34,510
Għal-lista tagħna ta 'tul 6, aħna meħtieġa biex jagħmlu 5

149
00:07:34,510 --> 00:07:37,990
paraguni għall-ewwel element, erba paraguni għall

150
00:07:37,990 --> 00:07:40,750
it-tieni element, u l-bqija.

151
00:07:40,750 --> 00:07:44,690
Dan ifisser li n-numru totali ta 'passi huwa s-somma ta'

152
00:07:44,690 --> 00:07:49,160
l-interi minn 1 sa t-tul tal-lista minus 1.

153
00:07:49,160 --> 00:07:51,005
Nistgħu jirrappreżentaw dan bil-kalkolu totali.

154
00:07:57,980 --> 00:07:59,910
Aħna mhux se tidħol fis ammonti totali hawnhekk.

155
00:07:59,910 --> 00:08:04,900
Iżda jirriżulta li din l-addizzjoni hija ugwali għal n darbiet

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

157
00:08:07,540 --> 00:08:14,220
Jew ekwivalenti, n kwadrat aktar minn 2 minus n aktar minn 2.

158
00:08:14,220 --> 00:08:18,860
Meta wieħed jitkellem dwar runtime asintotiku, dan it-terminu kwadrat n

159
00:08:18,860 --> 00:08:22,070
se jiddominaw dan it-terminu n.

160
00:08:22,070 --> 00:08:27,850
Allura xorta għażla hija O ta 'n kwadru.

161
00:08:27,850 --> 00:08:31,460
Ifakkar li fl-eżempju tagħna, sort għażla għad hemm bżonn li

162
00:08:31,460 --> 00:08:33,850
jiċċekkjaw jekk numru li kien diġà mifthiema

163
00:08:33,850 --> 00:08:35,450
meħtieġa biex jiġu mċaqalqa.

164
00:08:35,450 --> 00:08:38,929
Allura dan ifisser li jekk aħna dam tip ta 'għażla matul diġà

165
00:08:38,929 --> 00:08:43,070
magħżula lista, ikun jeħtieġ l-istess numru ta 'passi kif

166
00:08:43,070 --> 00:08:46,340
kieku waqt il-ġiri fuq lista kompletament mhux magħżul.

167
00:08:46,340 --> 00:08:51,470
Allura xorta għażla għandu prestazzjoni aħjar każ ta 'n kwadrat,

168
00:08:51,470 --> 00:08:56,820
li nirrappreżentaw mal omega n kwadru.

169
00:08:56,820 --> 00:08:58,600
U li hija għal tip ta 'għażla.

170
00:08:58,600 --> 00:09:00,630
Just wieħed mill-algoritmi ħafna nistgħu

171
00:09:00,630 --> 00:09:02,390
tuża biex issolvi lista.

172
00:09:02,390 --> 00:09:05,910
Jisimni Tommy, u dan huwa cs50.