Կարող եք անվանել ալգորիթմներ, որոնց ասիմպտոտիկ բարդությունը ավելի լավ է, քան արագ դասավորության?

Արագ դասավորումը միջինում աշխատում է O(n log n) ժամանակում, ինչը համեմատության ալգորիթմների համար օպտիմալ ասիմպտոտիկ է։ Այնուամենայնիվ, որոշ դեպքերում ավելի լավ ասիմպտոտիկ բարդությամբ ալգորիթմներ կան.

• Հաշվարկային դասավորում (Counting Sort) — O(n + k), որտեղ k արժեքների տիրույթն է։ Փորձառու է ավելի արագ, եթե k շատ մեծ չէ:
• Ռադիքսային դասավորում (Radix Sort) — O(d * (n + k)), որտեղ d թվանշանների քանակն է, k՝ համակարգի հիմքը։ արդյունավետ է թվեր կամ տողեր դասավորելու համար:
• Միասնական դասավորում (Merge Sort) — երաշխավորված է O(n log n), կայուն և կանխատեսելի:

Маһим է: Ավելի լավ, քան O(n log n) բարդությամբ ալգորիթմները չեն հիմնվում տարրերի համեմատության վրա, այլ օգտագործում են լրացուցիչ ենթադրություններ տվյալների մասին (օրինակ, սահմանափակ արժեքների տիրույթ):