1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] Tommy: Hebu tuangalie aina ya uteuzi, algorithm

2
00:00:09,980 --> 00:00:12,800
kwa ajili ya kuchukua orodha ya namba na kuchagua yao.

3
00:00:12,800 --> 00:00:15,750
algorithm, kumbuka, ni tu hatua kwa hatua

4
00:00:15,750 --> 00:00:18,370
utaratibu kwa ajili ya kukamilisha kazi.

5
00:00:18,370 --> 00:00:21,470
wazo la msingi nyuma ya aina uteuzi ni ya kugawanya

6
00:00:21,470 --> 00:00:23,390
orodha yetu ya ndani ya sehemu mbili -

7
00:00:23,390 --> 00:00:26,810
sehemu sorted na sehemu zisizochambuliwa.

8
00:00:26,810 --> 00:00:30,200
Katika kila hatua ya algorithm, idadi ni wakiongozwa kutoka

9
00:00:30,200 --> 00:00:33,800
zisizochambuliwa fungu kwa fungu sorted mpaka hatimaye

10
00:00:33,800 --> 00:00:35,880
orodha nzima ni Iliyopangwa.

11
00:00:35,880 --> 00:00:38,510
Hivyo hapa ni orodha ya namba sita -

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

13
00:00:44,010 --> 00:00:47,680
Hivi sasa orodha nzima ni kuchukuliwa zisizochambuliwa.

14
00:00:47,680 --> 00:00:51,770
Hata ingawa idadi kama Mei 16 tayari katika sahihi yake

15
00:00:51,770 --> 00:00:56,040
mahali, algorithm wetu hana njia ya kujua kwamba mpaka

16
00:00:56,040 --> 00:00:57,980
orodha nzima ni Iliyopangwa.

17
00:00:57,980 --> 00:01:01,355
Hivyo tutaweza kufikiria kila idadi kuwa zisizochambuliwa mpaka sisi wachambue

18
00:01:01,355 --> 00:01:03,800
ni sisi wenyewe.

19
00:01:03,800 --> 00:01:06,890
Tunajua kwamba tunataka kuwa katika orodha wakipanda utaratibu.

20
00:01:06,890 --> 00:01:10,200
Hivyo tutaweza wanataka kujenga sehemu sorted ya orodha yetu ya

21
00:01:10,200 --> 00:01:13,280
kutoka kushoto kwenda kulia, ndogo kwa ukubwa.

22
00:01:13,280 --> 00:01:17,970
Ili kufanya hivyo, tutaweza haja ya kutafuta chini ya kipengele zisizochambuliwa

23
00:01:17,970 --> 00:01:21,350
na kuiweka katika mwisho wa sehemu Iliyopangwa.

24
00:01:21,350 --> 00:01:25,370
Tangu orodha hii si sorted, njia pekee ya kufanya hivyo ni

25
00:01:25,370 --> 00:01:29,330
kuangalia kila kipengele katika sehemu zisizochambuliwa, wakikumbuka

26
00:01:29,330 --> 00:01:32,010
ambayo ni kipengele cha chini na kulinganisha

27
00:01:32,010 --> 00:01:33,770
kila kipengele kwamba.

28
00:01:33,770 --> 00:01:36,150
Hivyo tutaweza kwanza tuangalie 23.

29
00:01:36,150 --> 00:01:38,650
Hii ni kipengele kwanza tumeona, hivyo tutaweza kukumbuka

30
00:01:38,650 --> 00:01:40,050
ni kama kima cha chini.

31
00:01:40,050 --> 00:01:42,320
Next tutaangalia 42.

32
00:01:42,320 --> 00:01:46,720
42 ni kubwa kuliko 23, hivyo ni 23 bado kiwango cha chini.

33
00:01:46,720 --> 00:01:51,210
Next ni 4 ambayo ni chini ya 23, hivyo tutaweza kumbuka 4

34
00:01:51,210 --> 00:01:52,880
kama kima cha chini mpya.

35
00:01:52,880 --> 00:01:56,380
Next ni 16 ambayo ni kubwa kuliko 4, hivyo 4

36
00:01:56,380 --> 00:01:57,980
bado ni kiwango cha chini.

37
00:01:57,980 --> 00:02:03,670
8 ni kubwa kuliko 4, na 15 ni kubwa kuliko 4, hivyo lazima 4

38
00:02:03,670 --> 00:02:05,980
ndogo zisizochambuliwa kipengele.

39
00:02:05,980 --> 00:02:09,350
Hivyo ingawa kama binadamu tunaweza mara moja kuona kwamba ni 4

40
00:02:09,350 --> 00:02:12,300
kipengele cha chini, algorithm mahitaji yetu ya kuangalia

41
00:02:12,300 --> 00:02:15,710
kila kipengele zisizochambuliwa, hata baada ya sisi Nimepata 4 -

42
00:02:15,710 --> 00:02:16,860
kima cha chini ya kipengele.

43
00:02:16,860 --> 00:02:19,900
Hivyo sasa kwamba tumekuwa kupatikana kipengele cha chini, 4, tutaweza wanataka

44
00:02:19,900 --> 00:02:23,410
kwa hoja ndani ya fungu sorted ya orodha.

45
00:02:23,410 --> 00:02:27,320
Tangu hii ni hatua ya kwanza, hii ina maana tunataka kuweka 4 katika

46
00:02:27,320 --> 00:02:29,680
mwanzo wa orodha.

47
00:02:29,680 --> 00:02:33,040
Hivi sasa ni 23 wakati wa mwanzo wa orodha, hivyo

48
00:02:33,040 --> 00:02:36,080
hebu wabadilishane 4 na 23.

49
00:02:36,080 --> 00:02:38,870
Hivyo sasa orodha yetu inaonekana kama hii.

50
00:02:38,870 --> 00:02:42,710
Tunajua kwamba 4 lazima kuwa katika eneo lake la mwisho, kwa sababu ni

51
00:02:42,710 --> 00:02:45,890
wote kipengele ndogo na kipengele mwanzoni

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

53
00:02:46,960 --> 00:02:50,650
Hivyo hii ina maana kwamba sisi si milele haja ya hoja hiyo tena.

54
00:02:50,650 --> 00:02:53,910
Basi hebu kurudia utaratibu huu kwa kuongeza mwingine kipengele kwa

55
00:02:53,910 --> 00:02:55,910
Iliyopangwa sehemu ya orodha.

56
00:02:55,910 --> 00:02:58,950
Tunajua kwamba hatuna haja ya kuangalia 4, kwa sababu ni

57
00:02:58,950 --> 00:03:00,000
tayari Iliyopangwa.

58
00:03:00,000 --> 00:03:03,540
Hivyo tunaweza kuanza saa 42, ambayo tutaweza kumbuka kama

59
00:03:03,540 --> 00:03:05,290
kima cha chini ya kipengele.

60
00:03:05,290 --> 00:03:08,700
Hivyo ijayo tutaangalia 23 ambayo ni chini ya 42, hivyo sisi

61
00:03:08,700 --> 00:03:11,620
kumbuka ni kiwango cha chini 23 mpya.

62
00:03:11,620 --> 00:03:14,870
Next sisi kuona 16 ambayo ni chini ya 23, hivyo

63
00:03:14,870 --> 00:03:16,800
16 ni kiwango cha chini mpya.

64
00:03:16,800 --> 00:03:19,720
Sasa tunaangalia 8 ambayo ni chini ya 16, hivyo

65
00:03:19,720 --> 00:03:21,130
8 ni kima cha chini mpya.

66
00:03:21,130 --> 00:03:25,900
Na hatimaye 8 ni chini ya 15, hivyo tunajua kwamba ni kima cha chini cha 8

67
00:03:25,900 --> 00:03:27,780
zisizochambuliwa kipengele.

68
00:03:27,780 --> 00:03:30,660
Hivyo kwamba maana tunapaswa append 8 kwa sorted

69
00:03:30,660 --> 00:03:32,450
sehemu ya orodha.

70
00:03:32,450 --> 00:03:35,990
Hivi sasa ni kipengele 4 tu sorted, hivyo tunataka kuweka

71
00:03:35,990 --> 00:03:38,410
Ijayo 8-4.

72
00:03:38,410 --> 00:03:41,920
Tangu 42 ni kipengele kwanza katika sehemu ya zisizochambuliwa

73
00:03:41,920 --> 00:03:47,260
orodha, tutaweza wanataka wabadilishane 42 na 8.

74
00:03:47,260 --> 00:03:49,680
Hivyo sasa orodha yetu inaonekana kama hii.

75
00:03:49,680 --> 00:03:53,830
4 na 8 kuwakilisha sehemu sorted ya orodha, na

76
00:03:53,830 --> 00:03:56,440
iliyobaki idadi kuwakilisha zisizochambuliwa

77
00:03:56,440 --> 00:03:58,260
sehemu ya orodha.

78
00:03:58,260 --> 00:04:00,630
Basi hebu kuendelea na iteration mwingine.

79
00:04:00,630 --> 00:04:03,850
Tunaweza kuanza na 23 wakati huu, kwa vile hatuna haja ya kuangalia

80
00:04:03,850 --> 00:04:05,770
4 na 8 tena kwa sababu wameweza

81
00:04:05,770 --> 00:04:07,660
tayari Iliyopangwa.

82
00:04:07,660 --> 00:04:10,270
16 ni chini ya 23, hivyo tutaweza kukumbuka

83
00:04:10,270 --> 00:04:12,070
16 kama kiwango cha chini mpya.

84
00:04:12,070 --> 00:04:18,149
16 ni chini ya 42, lakini 15 ni chini ya 16, hivyo 15 lazima

85
00:04:18,149 --> 00:04:20,480
kima cha chini cha zisizochambuliwa kipengele.

86
00:04:20,480 --> 00:04:24,580
Hivyo sasa tunataka wabadilishane 15 na 23 kwa

87
00:04:24,580 --> 00:04:26,310
kutupatia orodha hii.

88
00:04:26,310 --> 00:04:30,500
sehemu ya orodha Iliyopangwa lina 4, 8 na 15, na

89
00:04:30,500 --> 00:04:33,210
mambo haya bado zisizochambuliwa.

90
00:04:33,210 --> 00:04:36,900
Lakini tu hivyo hutokea kwamba ijayo zisizochambuliwa kipengele, 16,

91
00:04:36,900 --> 00:04:38,480
tayari Iliyopangwa.

92
00:04:38,480 --> 00:04:42,060
Hata hivyo, hakuna njia kwa algorithm yetu ya kujua kwamba 16

93
00:04:42,060 --> 00:04:45,230
ni tayari katika eneo lake sahihi, hivyo bado tunahitaji

94
00:04:45,230 --> 00:04:47,870
kurudia hasa mchakato huo.

95
00:04:47,870 --> 00:04:53,750
Hivyo tunaona kuwa 16 ni chini ya 42, na 16 ni chini ya 23, hivyo

96
00:04:53,750 --> 00:04:56,230
16 lazima kipengele cha chini.

97
00:04:56,230 --> 00:04:59,010
Ni vigumu wabadilishane hii kipengele kwa yenyewe, ili tuweze

98
00:04:59,010 --> 00:05:01,780
tu kuondoka katika eneo hili.

99
00:05:01,780 --> 00:05:04,660
Hivyo tunahitaji moja zaidi kupita ya kompyuta yetu.

100
00:05:04,660 --> 00:05:09,370
42, ni mkubwa kuliko 23, hivyo 23 lazima

101
00:05:09,370 --> 00:05:10,970
kima cha chini cha zisizochambuliwa kipengele.

102
00:05:10,970 --> 00:05:17,410
Mara sisi byta 23 na 42, sisi kuishia na mwisho wetu

103
00:05:17,410 --> 00:05:18,530
Iliyopangwa orodha -

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

105
00:05:23,390 --> 00:05:26,830
Tunajua 42 lazima kuwa katika mahali sahihi tangu ni

106
00:05:26,830 --> 00:05:30,210
kipengele tu kushoto, na kwamba ni uteuzi aina.

107
00:05:30,210 --> 00:05:32,100
Hebu sasa kurasimisha algorithm wetu na baadhi ya

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

109
00:05:34,540 --> 00:05:37,760
On line moja, tunaweza kuona kuwa tunahitaji kuunganisha juu ya

110
00:05:37,760 --> 00:05:39,530
kila kipengele cha orodha.

111
00:05:39,530 --> 00:05:42,150
Isipokuwa kipengele mwisho, tangu kipengele 1

112
00:05:42,150 --> 00:05:44,230
orodha tayari Iliyopangwa.

113
00:05:44,230 --> 00:05:48,100
On line mbili, tunaona kipengele kwanza ya zisizochambuliwa

114
00:05:48,100 --> 00:05:51,080
sehemu ya orodha ya kuwa kima cha chini, kama tulivyofanya kwa wetu

115
00:05:51,080 --> 00:05:53,750
mfano, hivyo tuna kitu kulinganisha na.

116
00:05:53,750 --> 00:05:57,260
Line tatu huanza kitanzi pili ambayo sisi iterate juu ya

117
00:05:57,260 --> 00:05:59,170
kila kipengele zisizochambuliwa.

118
00:05:59,170 --> 00:06:02,150
Tunajua kwamba baada i iterations, fungu sorted

119
00:06:02,150 --> 00:06:05,330
ya orodha yetu lazima i vipengele ndani yake tangu kila hatua

120
00:06:05,330 --> 00:06:06,890
aina moja ya kipengele.

121
00:06:06,890 --> 00:06:11,770
Hivyo kwanza kipengele zisizochambuliwa lazima kuwa katika nafasi i plus 1.

122
00:06:11,770 --> 00:06:15,440
On line nne, sisi kulinganisha kipengele sasa kwa kiwango cha chini

123
00:06:15,440 --> 00:06:17,750
kipengele kwamba tumekuwa kuona hadi sasa.

124
00:06:17,750 --> 00:06:20,560
Kama kipengele sasa ni ndogo kuliko kima cha chini cha

125
00:06:20,560 --> 00:06:23,870
kipengele, basi sisi kukumbuka kipengele sasa kama mpya

126
00:06:23,870 --> 00:06:26,250
kima cha chini kwenye mstari tano.

127
00:06:26,250 --> 00:06:29,900
Hatimaye, kwa mistari sita na saba, sisi byta kima cha chini cha

128
00:06:29,900 --> 00:06:33,080
kipengele kwa kipengele kwanza zisizochambuliwa, na hivyo

129
00:06:33,080 --> 00:06:36,990
akiongeza kuwa sehemu ya orodha Iliyopangwa.

130
00:06:36,990 --> 00:06:40,030
Mara tuna algorithm, swali muhimu kuuliza

131
00:06:40,030 --> 00:06:43,370
wenyewe kama programmers ni muda gani ili kuchukua?

132
00:06:43,370 --> 00:06:46,970
Tutaweza kwanza kuuliza swali jinsi gani kuchukua muda mrefu kwa ajili ya hii

133
00:06:46,970 --> 00:06:50,070
algorithm kukimbia katika hali mbaya?

134
00:06:50,070 --> 00:06:51,640
Wanakumbuka sisi kuwakilisha hii mbio

135
00:06:51,640 --> 00:06:55,060
muda na nukuu kubwa O.

136
00:06:55,060 --> 00:06:58,650
Ili kuamua kiwango cha chini zisizochambuliwa kipengele, sisi

137
00:06:58,650 --> 00:07:01,880
kimsingi alikuwa kulinganisha kila kipengele katika orodha ya

138
00:07:01,880 --> 00:07:04,040
kila kipengele nyingine katika orodha.

139
00:07:04,040 --> 00:07:08,430
Intuitively, hii inaonekana kama O ya operesheni n squared.

140
00:07:08,430 --> 00:07:12,050
Kuangalia pseudocode yetu, sisi pia kuwa kitanzi nested ndani ya

141
00:07:12,050 --> 00:07:14,420
mwingine kitanzi, ambayo kwa hakika inaonekana kama O

142
00:07:14,420 --> 00:07:16,480
ya n operesheni squared.

143
00:07:16,480 --> 00:07:19,250
Hata hivyo, kumbuka kwamba sisi hakuwa na haja ya kuangalia juu ya

144
00:07:19,250 --> 00:07:23,460
nzima orodha wakati kuamua kiwango cha chini zisizochambuliwa kipengele?

145
00:07:23,460 --> 00:07:26,600
Mara sisi alijua kwamba alikuwa 4 sorted, kwa mfano, hatukuwa

146
00:07:26,600 --> 00:07:28,170
haja ya kuangalia tena.

147
00:07:28,170 --> 00:07:31,020
Hivyo gani hii chini wakati mbio?

148
00:07:31,020 --> 00:07:34,510
Kwa orodha ya urefu 6, sisi zinahitajika ili kufanya tano

149
00:07:34,510 --> 00:07:37,990
kulinganisha kwa kipengele kwanza, nne kulinganisha kwa

150
00:07:37,990 --> 00:07:40,750
kipengele cha pili, na kadhalika.

151
00:07:40,750 --> 00:07:44,690
Hiyo ina maana kwamba idadi ya jumla ya hatua ni jumla ya

152
00:07:44,690 --> 00:07:49,160
integers kutoka 1 kwa urefu wa orodha minus 1.

153
00:07:49,160 --> 00:07:51,005
Tunaweza kuwakilisha jambo hili kwa summation.

154
00:07:57,980 --> 00:07:59,910
Sisi si kwenda katika summations hapa.

155
00:07:59,910 --> 00:08:04,900
Lakini zinageuka kuwa summation hii ni sawa na mara n

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

157
00:08:07,540 --> 00:08:14,220
Au equivalently, n squared zaidi ya 2 bala n zaidi ya 2.

158
00:08:14,220 --> 00:08:18,860
Tunapozungumzia Runtime asymptotic, hii n squared mrefu

159
00:08:18,860 --> 00:08:22,070
ni kwenda kutawala muda huu n.

160
00:08:22,070 --> 00:08:27,850
Hivyo uteuzi aina ni O ya n squared.

161
00:08:27,850 --> 00:08:31,460
Kumbuka kwamba katika mfano wetu, uteuzi aina bado zinahitajika

162
00:08:31,460 --> 00:08:33,850
kuangalia kama namba kwamba alikuwa tayari sorted

163
00:08:33,850 --> 00:08:35,450
zinahitajika kuwa wakiongozwa.

164
00:08:35,450 --> 00:08:38,929
Hivyo kwamba ina maana kwamba kama sisi mbio uteuzi aina zaidi ya tayari

165
00:08:38,929 --> 00:08:43,070
Iliyopangwa orodha, ni itahitaji idadi sawa ya hatua kama

166
00:08:43,070 --> 00:08:46,340
ingekuwa wakati wa mbio juu ya orodha kabisa zisizochambuliwa.

167
00:08:46,340 --> 00:08:51,470
Hivyo uteuzi aina ana bora kesi ya utendaji ya n squared,

168
00:08:51,470 --> 00:08:56,820
ambayo sisi kuwakilisha na omega n squared.

169
00:08:56,820 --> 00:08:58,600
Na hiyo ni kwa ajili ya aina ya uteuzi.

170
00:08:58,600 --> 00:09:00,630
Moja tu ya algorithms wengi tunaweza

171
00:09:00,630 --> 00:09:02,390
kutumia aina orodha.

172
00:09:02,390 --> 00:09:05,910
Jina langu ni Tommy, na hii ni cs50.