«Հաշվողական տեսակավորում»–ի խմբագրումների տարբերություն
Content deleted Content added
չ clean up, replaced: → (5) oգտվելով ԱՎԲ |
չ կետադրություն, փոխարինվեց: : → ։ (5) |
||
Տող 1.
'''Հաշվողական տեսակավորումը''' [[տեսակավորման ալգորիթմ]] է, որում օգտագործվում է տեսակավորվող [[զանգվածի]] թվերի շարքը` համընկնող էլեմենտների տեսակավորման համար։ Հաշվողական տեսակավորման կիրառությունը ամբողջական է միայն այն ժամանակ, երբ տեսակավորվող թվերն ունեն հնարավոր նշանակության շարքեր, որը բավականին փոքր է տեսակավորվող բազմության հետ համեմատած, օրինակ` 1000-ից փոքր միլիոն բնական թվեր։ Ալգորիթմի արդյունավետությունը նվազում է, եթե մի քնի տարբեր էլեմենտների մեկ բջջի մեջ ընկնելու դեպքում անհրաժեշտ է լինում դրանք կրկին տեսակավորել։ Բջջի ներսում տեսակավորման անհրաժեշտությունը կորցնում է ալգորիթմի իմաստը, քանի որ յուրաքանչյուր էլեմենտ ստիպված կլինենք դիտարկել մեկ անգամից ավելի։
Ենթադրենք, որ մուտքային զանգվածը բաղկացած է <math>n</math> հատ ամբողջ թվերից`0-ից <math>k - 1</math> միջակայքում, որտեղ <math>k \in \mathbb N</math>
== Պարզ ալգորիթմ ==
Տող 55.
== Վերլուծություն ==
Առաջին երկու ալգորիթմերում առաջին երկու ցիկլերը աշխատում են համապատասխանաբար [[Теория сложности вычислений|<math>\Theta(k)</math>]] և <math>\Theta(n)</math> համար, կրկնակի ցիկլը` <math>\Theta(n + k)</math> համար։ Երրորդ ալգորիթմում ցիկլը զբաղեցնում են համապատասխանաբար <math>\Theta(k)</math>, <math>\Theta(n)</math>, <math>\Theta(k)</math> և <math>\Theta(n)</math>
== Հաշվողական տեսակավորման քառակուսային ալգորիթմ ==
Այստեղ օգտագործվում են մուտքային <code>A</code> զանգվածը և <code>B</code> օժանդակ զանգվածը` տեսակավորված բազմության համար։ Ալգորիթմում անհրաժեշտ է <code>A[i]</code> մուտքային զանգվածի յուրաքանչյուր էլեմենտի համար հաշվարկել <math>c_1</math>-ից փոքր էլեմենտների թիվը, և դրան հավասար, բայց <math>c_2</math> (<math>c = c_1 + c_2</math>)-ից առաջ գտնվող էլեմենտների թիվը։ Այնուհետև <code>B[c]</code> փոխանցել <code>A[i]</code>
<code>
SquareCountingSort
Տող 74.
=== Վերլուծություն ===
Ակնհայտ է, որ ալգորիթմի ժամաննակավոր գնահատականը հավասար է <math>\Theta(n^2)</math>, հիշողությունը` <math>\Theta(n)</math>
== Իրագործման օրինակներ ==
| |||