Werrej[Aħbi][Uri]
Ix-xjenza tal-kompjuter hija kollha dwar il-fehim tal-kumplessitajiet tal-algoritmi u l-istrutturi tad-dejta.
Għandek lista ta' oġġetti li jridu jiġu magħżula, iżda m'għandekx il-ħin jew ir-riżorsi biex tuża algoritmu ta' għażla aktar kumpless.
L-issortjar tal-inserzjoni huwa wieħed mill-algoritmi tal-issortjar l-aktar sempliċi, iżda jista 'jkun bil-mod għal listi kbar.
Implimentazzjoni u fehim faċli għamlu dan il-metodu favorit fost il-programmaturi. Hija perfetta għal listi żgħar jew meta jkollok bżonn soluzzjoni ta 'malajr.
F'dan il-blog post, se nħarsu lejn il-kumplessità tal-ħin tal-għażla tal-inserzjoni. Dan l-algoritmu jintuża biex jissortja arrays, u għandu runtime ta 'O (n2). Dan ifisser li l-kumplessità tal-ħin tiżdied mad-daqs tal-firxa.
Madankollu, dan l-algoritmu jista 'jkun aktar mgħaġġel ħafna drabi minn algoritmi oħra ta' għażla, bħal quicksort.
Ejja nagħtu ħarsa aktar mill-qrib lejn kif taħdem l-għażla tal-inserzjoni!
X'inhu Insertion Sort Algoritmu?
Element wieħed kull darba, it-tip ta' inserzjoni jiġġenera firxa li tista' tiġi magħżula, li ta' spiss tissejjaħ bħala lista.
Pereżempju, l-għażla hija applikata fi programmi tal-kompjuter ikkumplikati bħal kompilaturi, fejn l-ordni tat-tokens hija importanti għall-interpretazzjoni tal-programm.
Kif Taħdem l-Inserzjoni Sort?
Meta nużaw issortjar ta 'inserzjoni biex issolvi firxa, l-algoritmu jibda billi jsib l-iżgħar oġġett fil-lista u jdaħħalha fil-pożizzjoni korretta.
Imbagħad isib l-iżgħar oġġett li jmiss u jdaħħalha fil-pożizzjoni korretta, eċċ.
L-algoritmu jaħdem billi jdawwal il-lista, iqabbel kull oġġett ma 'dak li jiġi qabel.
Jekk l-oġġetti jkunu fl-ordni ħażina, l-algoritmu jibdelhom. Imbagħad jiċċekkja biex tara jekk il-lista hijiex magħżula, u jekk hux, l-algoritmu jintemm.
Fil-prattika, is-sortjar tal-inserzjoni huwa spiss implimentat bl-użu ta 'ftit linji ta' kodiċi, li jagħmilha għażla popolari għall-għażla ta 'arrays żgħar. Madankollu, il-kumplessità tal-ħin għandha tiġi kkunsidrata meta jintuża dan l-algoritmu.
Eżempju:
Hawnhekk huwa eżempju ta 'kif taħdem issortjar inserzjoni. Aħna se nużaw il-firxa li ġejja:
1, 2, 3, 4, 5, 6
L-algoritmu jibda billi jsib l-iżgħar oġġett fil-lista, li huwa 1. Imbagħad idaħħalha fil-pożizzjoni korretta, l-ewwel pożizzjoni. Imbagħad isib l-iżgħar oġġett li jmiss, li huwa 2. Daħħal fil-pożizzjoni korretta, li hija t-tieni pożizzjoni.
Imbagħad isib l-iżgħar oġġett li jmiss, li huwa 3. Idaħħalha fil-pożizzjoni korretta, li hija t-tielet pożizzjoni.
Imbagħad isib l-iżgħar oġġett li jmiss, li huwa 4. Daħħalha fil-pożizzjoni korretta, li hija r-raba 'pożizzjoni, eċċ. Il-lista issa hija magħżula!
Nistgħu naraw mill-eżempju li l-algoritmu jieħu sitt paraguni u tpartit biex issolvi l-lista. Dan għaliex tieħu n2 paraguni u tpartit biex issolvi lista ta 'n oġġetti. F'dan il-każ, n=6.
Kif Ittejjeb il-Kumplessità tal-Ħin tal-Issortjar tal-Inserzjoni?
Filwaqt li inserzjoni sort għandha runtime ta 'O (n2), jista 'jitjieb bl-użu ta' algoritmu ta 'għażla aħjar, bħal quicksort.
Quicksort għandu runtime O(n log n), li huwa ħafna aktar mgħaġġel minn O(n2).
Madankollu, f'xi każijiet, issortjar inserzjoni jista 'jkun aktar mgħaġġel minn quicksort.
Pereżempju, jekk il-lista tkun diġà fl-ordni, l-għażla tal-inserzjoni tieħu inqas ħin minn quicksort.
Fil-prattika, is-sortjar tal-inserzjoni huwa spiss implimentat bl-użu ta 'ftit linji ta' kodiċi, li jagħmilha għażla popolari għall-għażla ta 'arrays żgħar.
Madankollu, il-kumplessità tal-ħin għandha tiġi kkunsidrata meta jintuża dan l-algoritmu.
Kumplessitajiet tal-Ħin
Kumplessità tal-Agħar Każ O(n2):
Il-kumplessità tal-ħin tiżdied mad-daqs tal-firxa. Huwa jieħu n2 paraguni u tpartit biex issolvi lista ta 'n oġġetti.
Pereżempju, jekk ikollna firxa ta 'daqs 1000, l-algoritmu se jieħu 1,000,000 paragun u tpartit biex issolvi l-firxa.
Kumplessità tal-Aħjar Każ O(n):
Il-kumplessità tal-ħin hija l-istess bħad-daqs tal-firxa tal-input. I
t tieħu n paraguni u tpartit biex issolvi lista ta 'n oġġetti. Pereżempju, ikkunsidra firxa ta 'daqs 5. L-algoritmu se jieħu ħames paraguni u tpartit biex issolvi l-firxa.
Kumplessità Medja tal-Każ O(n2):
Il-kumplessità tal-ħin hija bejn l-agħar u l-aqwa kumplessitajiet f'dan il-każ.
Huwa jieħu n2 paraguni u tpartit biex issolvi lista ta 'n oġġetti.
Għalhekk, issortjar ta 'inserzjoni huwa algoritmu ta' għażla stabbli.
Għaliex l-Inserzjoni Sort Stabbli?
It-tip ta 'inserzjoni huwa stabbli minħabba li jippreserva l-ordni ta' elementi ugwali fil-firxa ta 'input.
Dan huwa importanti għal ħafna applikazzjonijiet, bħall-irkupru tad-dejta jew l-analiżi finanzjarja. Pereżempju, jekk ikollna żewġ listi ta 'numri u rridu nqabbluhom, irridu niżguraw li l-ordni tal-elementi tiġi ppreservata.
Jekk il-listi ma jiġux magħżula, aħna mhux se nqabbluhom b'mod preċiż.
Ħalli Irrispondi