يمكن لمصفوفة بطول N أن تحتوي على قيم 1،2،3 … N ^ 2.هل من الممكن الفرز في وقت O(n)؟

Question

نظرا لمجموعة من الطول N.يمكن أن تحتوي على قيم تتراوح من 1 إلى N^2 (N تربيع) كلاهما شامل، والقيم متكاملة.هل من الممكن فرز هذه المصفوفة في زمن O(N)؟اذا ممكن كيف؟

يحرر:هذه ليست واجبات منزلية.

Answer 1

اكتب كل عدد صحيح في الأساس N، أي أن كل x يمكن تمثيله بالشكل (x1, x2) حيث x = 1 + x1 + x2*N.يمكنك الآن فرزها مرتين من خلال الفرز العدي، مرة على x1 ومرة ​​على x2، مما يؤدي إلى الحصول على المصفوفة التي تم فرزها.

Answer 2

نعم ، يمكنك استخدام نوع راديكس مع ن دلاء واثنين من الممرات. في الأساس ، تعامل الأرقام على أنها تحتوي على رقمين في القاعدة ن.

Answer 3

من الممكن فرز أي مجموعة من الأعداد الصحيحة ذات القيمة القصوى المحددة جيدًا في O(n) الوقت باستخدام نوع راديكس. من المحتمل أن يكون هذا هو الحال بالنسبة لأي قائمة من الأعداد الصحيحة التي تواجهها. على سبيل المثال ، إذا كنت تقوم بفرز قائمة بالأعداد الصحيحة الدقيقة التعسفية ، فلن يكون ذلك صحيحًا. ولكن جميع أنواع C المتكاملة لها نطاقات ثابتة محددة جيدًا.