>> [Music kucheza]
DOUG LLOYD: Uteuzi aina ni algorithm kwamba, kama unaweza kutarajia,
aina seti ya vipengele.
Na algorithm wanakumbuka ni hatua kwa hatua ya kuweka
maelekezo kwa ajili ya kukamilisha kazi.
>> Katika uteuzi aina wazo la msingi ni hii,
kupata ndogo zisizochambuliwa kipengele na kuongeza hivyo hadi mwisho wa orodha Iliyopangwa.
Ufanisi gani hii ni kujenga orodha yamepangwa, moja ya kipengele wakati huo.
Kuvunja ni chini ya pseudocode tunaweza kueleza algorithm hii
kama ifuatavyo, kurudia huu mpaka hakuna mambo zisizochambuliwa kubaki.
Kutafuta njia zisizochambuliwa na takwimu kupata thamani ndogo,
kisha wabadilishane thamani ndogo kwa sehemu ya kwanza ya sehemu zisizochambuliwa.
>> Ni inaweza kusaidia taswira hii, hivyo hebu tuangalie hii.
Hivyo hii, mimi kushindana, ni zisizochambuliwa safu na nimekuwa
zilionyesha kuwa na kuonyesha kwamba zote wa mambo ni rangi nyekundu,
wao ni bado yamepangwa.
Hii ni mzima sehemu zisizochambuliwa ya safu.
>> Basi hebu kwenda kupitia hatua ya uteuzi aina ya kutatua safu hii.
Hivyo tena, sisi ni gonna kurudia mpaka hakuna mambo zisizochambuliwa kubaki.
Tuko la gonna kupitia na takwimu kupata thamani ndogo,
na kisha wabadilishane kwamba thamani na sehemu ya kwanza ya sehemu zisizochambuliwa.
>> Hivi sasa, tena, nzima safu ni sehemu zisizochambuliwa.
Wote wa mambo nyekundu ni zisizochambuliwa.
Hivyo sisi kutafuta njia na tunaona thamani ndogo.
Sisi kuanza mwanzoni, sisi kwenda hadi mwisho,
tunaona thamani ndogo ni, moja.
Hivyo hiyo ni sehemu moja.
Na kisha sehemu mbili, wabadilishane kwamba thamani na sehemu ya kwanza ya sehemu zisizochambuliwa,
au kwanza kipengele nyekundu.
>> Katika kesi hiyo ambayo itakuwa ya tano, hivyo sisi wabadilishane moja na tano.
Wakati sisi kufanya hivyo, tunaweza kuibua kuona kwamba tumekuwa
wakiongozwa ndogo yenye thamani ya kipengele wa safu, kwa mwanzo.
Ufanisi kuchagua kwamba kipengele.
>> Na ili tuweze kweli kuthibitisha na hali ya kuwa moja, ni vyema.
Na hivyo tutaweza zinaonyesha sehemu yamepangwa wa safu yetu, kwa kuipaka rangi ya bluu.
>> Sasa sisi tu kurudia utaratibu tena.
Sisi kutafuta njia ya sehemu zisizochambuliwa ya safu kupata kipengele ndogo.
Katika kesi hiyo, ni mbili.
>> Sisi wabadilishane kwamba kwa mara ya kwanza kipengele cha sehemu zisizochambuliwa.
Katika kesi hiyo miwili pia hutokea kwa kuwa sehemu ya kwanza ya sehemu zisizochambuliwa.
Hivyo sisi wabadilishane mbili kwa yenyewe, ambayo kwa kweli tu majani mawili
ambako ni, na ni vyema.
Kuendelea juu, sisi kutafuta njia ya kupata kipengele ndogo.
Ni tatu.
Sisi wabadilishane kwa kwanza kipengele, ambayo ni watano.
Na sasa tatu ni Iliyopangwa.
>> Sisi kutafuta njia tena, na sisi kupata kipengele ndogo ni nne.
Sisi wabadilishane kwa kipengele kwanza ya zisizochambuliwa sehemu, na sasa nne ni Iliyopangwa.
>> Tunaona kwamba tano ni ndogo kipengele.
Sisi wabadilishane kwa kwanza kipengele cha sehemu zisizochambuliwa.
Na sasa tano ni Iliyopangwa.
>> Na kisha mwisho, yetu zisizochambuliwa sehemu lina
ya tu kipengele moja, hivyo sisi kutafuta njia ya
na tunaona kwamba ni sita ndogo, na kwa kweli, tu kipengele.
Na kisha tunaweza hali ya kuwa ni vyema.
Na sasa tumekuwa kimewashwa safu yetu kutoka kuwa kabisa zisizochambuliwa
katika nyekundu, ya namna kabisa katika bluu, kwa kutumia uteuzi aina.
>> Basi nini mazingira ya kesi mbaya hapa?
Vizuri katika hali mbaya zaidi kabisa kesi, inabidi kuangalia juu ya
wote wa mambo ya safu ya kupata ndogo zisizochambuliwa kipengele,
na tuna kurudia utaratibu huu mara n.
Mara kwa kila kipengele cha safu kwa sababu sisi tu, katika algorithm hii,
aina moja ya kipengele wakati huo.
>> Nini bora kesi mazingira?
Naam ni sawa, sawa?
Sisi kweli kuwa bado hatua kupitia kila kipengele moja ya safu
ili kuthibitisha kuwa ni, kwa kweli, kipengele ndogo.
>> Hivyo kesi mbaya Runtime, sisi kurudia mchakato n nyakati,
mara moja kwa kila moja ya mambo n.
Na katika bora kesi, tuna kufanya hivyo.
>> Hivyo kufikiri nyuma yetu Computational utata sanduku la vifaa,
unafikiri nini ni mbaya kesi Runtime kwa uteuzi aina?
Je, unafikiri ni bora kesi Runtime kwa uteuzi aina?
>> Je, nadhani Big O ya n squared, na Big Omega ya n squared?
Ningependa kuwa na haki.
Hayo ni, kwa kweli, kesi mbaya na kesi bora kukimbia
Mara kwa mara, kwa uteuzi aina.
>> Mimi nina Doug Lloyd.
Hii ni CS50.