Sayansi ya kompyuta inahusu kuelewa ugumu wa algoriti na miundo ya data.
Una orodha ya vipengee vinavyohitaji kupangwa, lakini huna wakati au nyenzo za kutumia algoriti changamano zaidi ya kupanga.
Upangaji wa uwekaji ni mojawapo ya algoriti rahisi zaidi za kupanga, lakini inaweza kuwa polepole kwa orodha kubwa.
Utekelezaji rahisi na uelewa umefanya njia hii kupendwa kati ya waandaaji wa programu. Ni kamili kwa orodha ndogo au unapohitaji suluhisho la haraka.
Katika chapisho hili la blogi, tutaangalia ugumu wa wakati wa kupanga uwekaji. Algorithm hii inatumika kupanga safu, na ina wakati wa kukimbia wa O(n2) Hii ina maana kwamba utata wa wakati huongezeka kwa ukubwa wa safu.
Walakini, algoriti hii inaweza kuwa haraka mara nyingi kuliko algoriti zingine za kupanga, kama vile upangaji haraka.
Wacha tuangalie kwa undani jinsi upangaji wa uwekaji unavyofanya kazi!
Algorithm ya Upangaji wa Uingizaji ni Nini?
Kipengee kimoja kwa wakati mmoja, aina ya uwekaji hutoa safu inayoweza kupangwa, ambayo mara nyingi huitwa orodha.
Kwa mfano, kupanga kunatumika katika programu ngumu za kompyuta kama vile watunzi, ambapo mpangilio wa ishara ni muhimu kwa tafsiri ya programu.
Je, Uingizaji Hufanya Kazi Gani?
Tunapotumia upangaji wa uwekaji kupanga safu, kanuni huanza kwa kutafuta kipengee kidogo zaidi kwenye orodha na kukiingiza katika nafasi sahihi.
Kisha hupata kipengee kidogo zaidi na kuiingiza kwenye nafasi sahihi, na kadhalika.
Algorithm inafanya kazi kwa kupitia orodha, kulinganisha kila kitu na ile inayokuja mbele yake.
Ikiwa vitu viko katika mpangilio mbaya, algorithm hubadilisha. Kisha inakagua ili kuona ikiwa orodha imepangwa, na ikiwa iko, algorithm inaisha.
Kwa mazoezi, aina ya uwekaji mara nyingi hutekelezwa kwa kutumia mistari michache ya msimbo, na kuifanya kuwa chaguo maarufu la kupanga safu ndogo. Walakini, ugumu wa wakati unapaswa kuzingatiwa wakati wa kutumia algorithm hii.
Mfano:
Hapa kuna mfano wa jinsi upangaji wa uwekaji unavyofanya kazi. Tutatumia safu zifuatazo:
1, 2, 3, 4, 5, 6
Algorithm huanza kwa kutafuta kipengee kidogo zaidi katika orodha, ambayo ni 1. Kisha inaiingiza kwenye nafasi sahihi, nafasi ya kwanza. Kisha hupata bidhaa ndogo zaidi inayofuata, ambayo ni 2. Inaiingiza kwenye nafasi sahihi, ambayo ni nafasi ya pili.
Kisha hupata bidhaa ndogo zaidi inayofuata, ambayo ni 3. Inaiingiza kwenye nafasi sahihi, ambayo ni nafasi ya tatu.
Kisha hupata kipengee kidogo zaidi, ambacho ni 4. Inaingiza kwenye nafasi sahihi, ambayo ni nafasi ya nne, na kadhalika. Orodha sasa imepangwa!
Tunaweza kuona kutoka kwa mfano kwamba algorithm inachukua ulinganisho sita na kubadilishana kupanga orodha. Hii ni kwa sababu inachukua n2 kulinganisha na kubadilishana kupanga orodha ya vitu n. Katika kesi hii, n = 6.
Jinsi ya Kuboresha Utata wa Kupanga Muda?
Wakati aina ya uwekaji ina wakati wa kukimbia wa O(n2), inaweza kuboreshwa kwa kutumia algorithm bora ya kupanga, kama vile quicksort.
Quicksort ina wakati wa kukimbia wa O(n log n), ambayo ni haraka sana kuliko O(n2).
Walakini, katika hali zingine, upangaji wa uwekaji unaweza kuwa haraka kuliko upangaji wa haraka.
Kwa mfano, ikiwa orodha tayari iko katika mpangilio, upangaji wa uwekaji utachukua muda mfupi kuliko upangaji haraka.
Kwa mazoezi, aina ya uwekaji mara nyingi hutekelezwa kwa kutumia mistari michache ya msimbo, na kuifanya kuwa chaguo maarufu la kupanga safu ndogo.
Walakini, ugumu wa wakati unapaswa kuzingatiwa wakati wa kutumia algorithm hii.
Matatizo ya Wakati
Hali Mbaya Zaidi Utata O(n2):
Ugumu wa wakati huongezeka kwa saizi ya safu. Inachukua n2 kulinganisha na kubadilishana kupanga orodha ya vitu n.
Kwa mfano, ikiwa tuna safu ya ukubwa wa 1000, algoriti itachukua ulinganisho 1,000,000 na kubadilishana kupanga safu.
Utata wa Kesi Bora O(n):
Ugumu wa wakati ni sawa na saizi ya safu ya ingizo. I
t inachukua n kulinganisha na kubadilishana kupanga orodha ya vitu n. Kwa mfano, fikiria safu ya ukubwa wa 5. Algorithm itachukua ulinganisho tano na kubadilishana kupanga safu.
Utata Wastani wa Kesi O(n2):
Ugumu wa wakati ni kati ya hali ngumu zaidi na bora zaidi katika kesi hii.
Inachukua n2 kulinganisha na kubadilishana kupanga orodha ya vitu n.
Kwa hivyo, upangaji wa uwekaji ni algorithm thabiti ya kupanga.
Kwa Nini Upangaji wa Uingizaji Ni Imara?
Upangaji wa uwekaji ni thabiti kwa sababu huhifadhi mpangilio wa vipengee sawa katika safu ya ingizo.
Hii ni muhimu kwa programu nyingi, kama vile kurejesha data au uchambuzi wa kifedha. Kwa mfano, ikiwa tuna orodha mbili za nambari na tunataka kuzilinganisha, tunahitaji kuhakikisha kwamba utaratibu wa vipengele umehifadhiwa.
Ikiwa orodha hazijapangwa, hatutazilinganisha kwa usahihi.
Acha Reply