1
00:00:00,000 --> 00:00:05,726
>> [Music kucheza]

2
00:00:05,726 --> 00:00:08,600
DOUG LLOYD: Uteuzi aina ni
algorithm kwamba, kama unaweza kutarajia,

3
00:00:08,600 --> 00:00:10,470
aina seti ya vipengele.

4
00:00:10,470 --> 00:00:12,470
Na algorithm wanakumbuka
ni hatua kwa hatua ya kuweka

5
00:00:12,470 --> 00:00:15,260
maelekezo kwa ajili ya kukamilisha kazi.

6
00:00:15,260 --> 00:00:17,580
>> Katika uteuzi aina
wazo la msingi ni hii,

7
00:00:17,580 --> 00:00:22,080
kupata ndogo zisizochambuliwa kipengele na
kuongeza hivyo hadi mwisho wa orodha Iliyopangwa.

8
00:00:22,080 --> 00:00:26,970
Ufanisi gani hii ni kujenga
orodha yamepangwa, moja ya kipengele wakati huo.

9
00:00:26,970 --> 00:00:29,800
Kuvunja ni chini ya pseudocode
tunaweza kueleza algorithm hii

10
00:00:29,800 --> 00:00:34,490
kama ifuatavyo, kurudia huu mpaka
hakuna mambo zisizochambuliwa kubaki.

11
00:00:34,490 --> 00:00:38,660
Kutafuta njia zisizochambuliwa
na takwimu kupata thamani ndogo,

12
00:00:38,660 --> 00:00:44,130
kisha wabadilishane thamani ndogo kwa
sehemu ya kwanza ya sehemu zisizochambuliwa.

13
00:00:44,130 --> 00:00:47,130
>> Ni inaweza kusaidia taswira hii,
hivyo hebu tuangalie hii.

14
00:00:47,130 --> 00:00:49,710
Hivyo hii, mimi kushindana, ni
zisizochambuliwa safu na nimekuwa

15
00:00:49,710 --> 00:00:53,040
zilionyesha kuwa na kuonyesha kwamba zote
wa mambo ni rangi nyekundu,

16
00:00:53,040 --> 00:00:54,420
wao ni bado yamepangwa.

17
00:00:54,420 --> 00:00:57,670
Hii ni mzima
sehemu zisizochambuliwa ya safu.

18
00:00:57,670 --> 00:01:02,020
>> Basi hebu kwenda kupitia hatua ya
uteuzi aina ya kutatua safu hii.

19
00:01:02,020 --> 00:01:05,296
Hivyo tena, sisi ni gonna kurudia
mpaka hakuna mambo zisizochambuliwa kubaki.

20
00:01:05,296 --> 00:01:07,920
Tuko la gonna kupitia
na takwimu kupata thamani ndogo,

21
00:01:07,920 --> 00:01:11,990
na kisha wabadilishane kwamba thamani na
sehemu ya kwanza ya sehemu zisizochambuliwa.

22
00:01:11,990 --> 00:01:14,380
>> Hivi sasa, tena, nzima
safu ni sehemu zisizochambuliwa.

23
00:01:14,380 --> 00:01:16,534
Wote wa mambo nyekundu ni zisizochambuliwa.

24
00:01:16,534 --> 00:01:18,700
Hivyo sisi kutafuta njia na
tunaona thamani ndogo.

25
00:01:18,700 --> 00:01:20,533
Sisi kuanza mwanzoni,
sisi kwenda hadi mwisho,

26
00:01:20,533 --> 00:01:23,630
tunaona thamani ndogo ni, moja.

27
00:01:23,630 --> 00:01:24,860
Hivyo hiyo ni sehemu moja.

28
00:01:24,860 --> 00:01:29,440
Na kisha sehemu mbili, wabadilishane kwamba thamani na
sehemu ya kwanza ya sehemu zisizochambuliwa,

29
00:01:29,440 --> 00:01:31,340
au kwanza kipengele nyekundu.

30
00:01:31,340 --> 00:01:34,980
>> Katika kesi hiyo ambayo itakuwa ya
tano, hivyo sisi wabadilishane moja na tano.

31
00:01:34,980 --> 00:01:37,320
Wakati sisi kufanya hivyo, tunaweza
kuibua kuona kwamba tumekuwa

32
00:01:37,320 --> 00:01:41,260
wakiongozwa ndogo yenye thamani ya kipengele
wa safu, kwa mwanzo.

33
00:01:41,260 --> 00:01:43,920
Ufanisi kuchagua kwamba kipengele.

34
00:01:43,920 --> 00:01:47,520
>> Na ili tuweze kweli kuthibitisha
na hali ya kuwa moja, ni vyema.

35
00:01:47,520 --> 00:01:52,080
Na hivyo tutaweza zinaonyesha sehemu yamepangwa
wa safu yetu, kwa kuipaka rangi ya bluu.

36
00:01:52,080 --> 00:01:53,860
>> Sasa sisi tu kurudia utaratibu tena.

37
00:01:53,860 --> 00:01:57,430
Sisi kutafuta njia ya sehemu zisizochambuliwa ya
safu kupata kipengele ndogo.

38
00:01:57,430 --> 00:01:59,000
Katika kesi hiyo, ni mbili.

39
00:01:59,000 --> 00:02:02,100
>> Sisi wabadilishane kwamba kwa mara ya kwanza
kipengele cha sehemu zisizochambuliwa.

40
00:02:02,100 --> 00:02:05,540
Katika kesi hiyo miwili pia hutokea kwa kuwa
sehemu ya kwanza ya sehemu zisizochambuliwa.

41
00:02:05,540 --> 00:02:08,650
Hivyo sisi wabadilishane mbili kwa yenyewe,
ambayo kwa kweli tu majani mawili

42
00:02:08,650 --> 00:02:11,257
ambako ni, na ni vyema.

43
00:02:11,257 --> 00:02:13,840
Kuendelea juu, sisi kutafuta njia ya
kupata kipengele ndogo.

44
00:02:13,840 --> 00:02:15,030
Ni tatu.

45
00:02:15,030 --> 00:02:17,650
Sisi wabadilishane kwa kwanza
kipengele, ambayo ni watano.

46
00:02:17,650 --> 00:02:19,450
Na sasa tatu ni Iliyopangwa.

47
00:02:19,450 --> 00:02:22,440
>> Sisi kutafuta njia tena, na sisi
kupata kipengele ndogo ni nne.

48
00:02:22,440 --> 00:02:28,070
Sisi wabadilishane kwa kipengele kwanza ya
zisizochambuliwa sehemu, na sasa nne ni Iliyopangwa.

49
00:02:28,070 --> 00:02:29,910
>> Tunaona kwamba tano ni
ndogo kipengele.

50
00:02:29,910 --> 00:02:32,900
Sisi wabadilishane kwa kwanza
kipengele cha sehemu zisizochambuliwa.

51
00:02:32,900 --> 00:02:34,740
Na sasa tano ni Iliyopangwa.

52
00:02:34,740 --> 00:02:36,660
>> Na kisha mwisho, yetu
zisizochambuliwa sehemu lina

53
00:02:36,660 --> 00:02:38,576
ya tu kipengele moja,
hivyo sisi kutafuta njia ya

54
00:02:38,576 --> 00:02:41,740
na tunaona kwamba ni sita
ndogo, na kwa kweli, tu kipengele.

55
00:02:41,740 --> 00:02:44,906
Na kisha tunaweza hali ya kuwa ni vyema.

56
00:02:44,906 --> 00:02:47,530
Na sasa tumekuwa kimewashwa safu yetu
kutoka kuwa kabisa zisizochambuliwa

57
00:02:47,530 --> 00:02:52,660
katika nyekundu, ya namna kabisa
katika bluu, kwa kutumia uteuzi aina.

58
00:02:52,660 --> 00:02:54,920
>> Basi nini mazingira ya kesi mbaya hapa?

59
00:02:54,920 --> 00:02:57,830
Vizuri katika hali mbaya zaidi kabisa
kesi, inabidi kuangalia juu ya

60
00:02:57,830 --> 00:03:02,170
wote wa mambo ya safu ya
kupata ndogo zisizochambuliwa kipengele,

61
00:03:02,170 --> 00:03:04,750
na tuna kurudia
utaratibu huu mara n.

62
00:03:04,750 --> 00:03:09,090
Mara kwa kila kipengele cha safu
kwa sababu sisi tu, katika algorithm hii,

63
00:03:09,090 --> 00:03:12,180
aina moja ya kipengele wakati huo.

64
00:03:12,180 --> 00:03:13,595
>> Nini bora kesi mazingira?

65
00:03:13,595 --> 00:03:15,040
Naam ni sawa, sawa?

66
00:03:15,040 --> 00:03:18,440
Sisi kweli kuwa bado hatua kupitia
kila kipengele moja ya safu

67
00:03:18,440 --> 00:03:22,040
ili kuthibitisha kuwa ni,
kwa kweli, kipengele ndogo.

68
00:03:22,040 --> 00:03:26,760
>> Hivyo kesi mbaya Runtime, sisi
kurudia mchakato n nyakati,

69
00:03:26,760 --> 00:03:28,960
mara moja kwa kila moja ya mambo n.

70
00:03:28,960 --> 00:03:31,940
Na katika bora kesi,
tuna kufanya hivyo.

71
00:03:31,940 --> 00:03:35,340
>> Hivyo kufikiri nyuma yetu
Computational utata sanduku la vifaa,

72
00:03:35,340 --> 00:03:39,250
unafikiri nini ni mbaya
kesi Runtime kwa uteuzi aina?

73
00:03:39,250 --> 00:03:41,840
Je, unafikiri ni bora
kesi Runtime kwa uteuzi aina?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> Je, nadhani Big O ya n squared,
na Big Omega ya n squared?

76
00:03:49,325 --> 00:03:49,950
Ningependa kuwa na haki.

77
00:03:49,950 --> 00:03:52,490
Hayo ni, kwa kweli,
kesi mbaya na kesi bora kukimbia

78
00:03:52,490 --> 00:03:55,100
Mara kwa mara, kwa uteuzi aina.

79
00:03:55,100 --> 00:03:56,260
>> Mimi nina Doug Lloyd.

80
00:03:56,260 --> 00:03:58,600
Hii ni CS50.

81
00:03:58,600 --> 00:04:00,279