«Հաշվողական տեսակավորում»–ի խմբագրումների տարբերություն

Առաջին երկու ալգորիթմերում առաջին երկու ցիկլերը աշխատում են համապատասխանաբար [[Теория сложности вычислений|<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>: Արդյունքում` բոլոր երեք ալգորիթմերն էլ ունեն գծային ժամանակավոր <math>\Theta(n + k)</math> աշխատունակություն: Առաջին երկու ալգորիթմերում օգտագործվող հիշողությունը հավասար է <math>\Theta(k)</math>, իսկ երրորդում` <math>\Theta(n + k)</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>: Ալգորիթմը կայուն է:

Ակնհայտ է, որ ալգորիթմի ժամաննակավոր գնահատականը հավասար ըէ <math>\Theta(n^2)</math>, հիշողությունը` <math>\Theta(n)</math>: