وقتی تمام اعداد آرایه در یک محدوده خاص باشن مثلا بین ۱ تا ۱۰۰۰ با استفاده از مرتب سازی شمارشی میشه آرایه رو با مرتبه‌ی خطی مرتب کرد.

(۰۶ آذر ۱۳۹۲ ۱۲:۱۴ ق.ظ)mfXpert نوشته شده توسط:  وقتی تمام اعداد آرایه در یک محدوده خاص باشن مثلا بین ۱ تا ۱۰۰۰ با استفاده از مرتب سازی شمارشی میشه آرایه رو با مرتبه‌ی خطی مرتب کرد.

تو یه سوال پرسیده شده که آیا n عدد صحیح و مثبت کوچکتر از n^100 را می توان در زمان خطی مرتب کرد؟ و توی جواب هم گفته که با الگوریتم شمارشی میشه با مرتبه خطی مرتبش کرد . ولی در حالی که n یک محدوده خاص نیست و متغیره.

(۰۵ آذر ۱۳۹۲ ۱۱:۵۶ ب.ظ)amirid نوشته شده توسط:  برای مرتب کردن یک آرایه چه زمانی می توان از الگوریتم شمارشی که دارای O(n) d است ،استفاده کرد؟ و با چه شرایطی از الگوریتم های با پیچیدگی nlogn استفاده کرد؟ [/code]

این که گفته محدوده اعداد از $\mathcal{O}(n^{100})$ هستش، یعنی محدوده اعدادمون مشخصه! و ما میتونیم یه ارایه به اندازه این محدوده بگیریم و به صورت شمارشی اونو توی مرتبه خطی مرتب کنیم.
هر چند من معتقدم که این جواب که توی کتاب قدسی هستش غلطه چون مرتب سازی شمارشی مرتبش از $\mathcal{O}(n k)$ هستش و وقتی این الگوریتم خطی میشه که $k \in \mathcal{O}(n)$ باشه ولی توی این سوال میشه از مرتبه $\mathcal{O}(n n^{100})$ که میشه $\mathcal{O}(n^{100})$!