الفرز في الوقت الخطي؟ [مغلق

Question

بالنظر إلى مجموعة مدخلات من الأعداد الصحيحة N في النطاق [0..N ^ 3-1]، توفر خوارزمية فرز وقت خطي.

هذا مراجعة للاختبار الخاص بي يوم الخميس، وليس لدي أي فكرة عن كيفية الاقتراب من هذه المشكلة.

Answer 1

إلقاء نظرة أيضا على أنواع ذات صلة أيضا: Pigeonhole فرز أو عد الفرز, ، إلى جانب راديكس فرز كما ذكرنا بوكو.

Answer 2

القي نظرة على راديكس فرز.

Answer 3

عندما يقول الناس "خوارزمية الفرز"، فإنهم يشيرون غالبا إلى "خوارزمية فرز المقارنة"، وهي أي خوارزمية تعتمد فقط على القدرة على السؤال "هل هذا الشيء أكبر أو أصغر من ذلك". لذلك إذا كنت تقتصر على مطالبة بسؤال واحد حول البيانات، فلن تحصل أبدا على أكثر من سجل n * (n) (ناتجية القيام بسجل (ن) وبعد

إذا كان بإمكانك الهروب من قيود "نوع المقارنة" واسأل سؤالا أكثر تطورا حول قطعة من البيانات، على سبيل المثال "ما هو Base 10 Radix من هذه البيانات"، ثم يمكنك التوصل إلى أي عدد من خوارزميات فرز الوقت الخطي، انهم فقط يأخذون المزيد من الذاكرة.

هذا هو إجازة مساحة الوقت. يستغرق فرز المقارنة قليلا أو بدون ذاكرة الوصول العشوائي ويعمل في وقت n * سجل (ن). يتم تشغيل راديكس فرز (على سبيل المثال) في ذاكرة O (N) و o (log (radix)).

Answer 4

ويكيبيديا يظهر العديد من خوارزميات الفرز المختلفة وتعقيداتها. قد ترغب في التحقق منها

Answer 5

انها حقا بسيطة، إذا كانت n = 2 والأرقام فريدة من نوعها:

• بناء مجموعة من البتات (2 ^ 31-1 بت => ~ 256 ميجابايت). تهيئة لهم إلى الصفر.
• اقرأ المدخلات، لكل قيمة ترى تعيين بت المعني في الصفيف إلى 1.
• مسح الصفيف، لكل مجموعة بت، إخراج القيمة المعنية.

تعقيد => O (2N)

خلاف ذلك، استخدم راديكس فرز:

تعقيد => O (KN) (نأمل)

Answer 6

أعتقد أن الأرقام كثلاثة أرقام حيث يتراوح كل رقم من 0 إلى N-1. فرز هذه الأرقام مع راديكس فرز. لكل رقم من الأرقام، هناك مكالمة لعسل الترتيب الذي يأخذ وقت Theta (n + n)، بحيث يتوافق إجمالي وقت التشغيل Theta (n).

Answer 7

يمكن تمثيل مجموعة من مجموعة محدودة من الأرقام بواسطة صورة نقطية من BITS. في هذه الحالة، صورة نقطية 500 ميجابايت، لذلك من أجل أي شيء سوى قوائم ضخمة، ستكون أفضل حالا مع راديكس فرز. كما تواجه الرقم K، قم بتعيين صورة نقطية [k] = 1. اجتياز واحد من خلال القائمة، O (N).

Answer 8

على حد سواء آل المجوهرات:

M;// unsorted array
lngth; //number items of M
for(int i=0; i < lngth; i++)sorted[M[i]];

إنه بمفرده Algo ALGo للتعقيد الخطي، لكنه لديه تعقيد O (K * N) بواسطة RAM (N - Number Array Elements، K - Element's Len)