ج#:خوارزمية فعالة للعثور على أكبر عناصر m في مصفوفة N x N

Question

أود أن أعرف ما إذا كانت هناك خوارزمية فعالة للعثور على أكبر عناصر m في مصفوفة N x N، برأس طريقة مثل هذا:

double[] greatestValues(double[][] matrix, int numberOfElements);

أيه أفكار؟

Answer 1

إذا تعاملت مع مصفوفة N x N كمصفوفة من عناصر N x N، فيمكنك تطبيق إحدى التقنيات التالية:

التطبيق المباشر لخوارزمية الاختيار القائمة على الفرز السريع يمكن استخدام خوارزمية التحديد السريع للفرز للعثور على أكبر أو أكبر عناصر K.للعثور على أصغر العناصر K العثور على أصغر عنصر KTH باستخدام متوسط ​​خوارزمية سريعة القائمة على النوع المتوسط.بعد التقسيم الذي يجد العنصر الأصغر KTH ، سيتم عرض جميع العناصر الأصغر من العنصر الأصغر KTH إلى اليسار إلى العنصر KTH وسيكون كل العناصر أكبر موجودًا إلى عنصر KTH الأصغر.وهكذا تشكل جميع العناصر من العناصر الأولى إلى KTH شاملة أصغر العناصر K.تعقيد الوقت خطي في n ، إجمالي عدد العناصر.

الحلول القائمة على بنية البيانات هناك طريقة بسيطة أخرى تتمثل في إضافة كل عنصر من عناصر القائمة إلى بنية بيانات تعيين مرتبة ، مثل كومة أو شجرة بحث ثنائية التوازن الذاتي ، مع معظم عناصر K.كلما تحتوي بنية البيانات على أكثر من عناصر K ، نقوم بإزالة أكبر عنصر ، والذي يمكن القيام به في وقت O (log k).تستغرق كل عملية إدخال أيضًا وقت O (log k) ، مما يؤدي إلى وقت O (nlog k) بشكل عام.

من الممكن تحويل القائمة إلى كومة في وقت θ (n) ، ثم اجتياز الكومة باستخدام خوارزمية البحث المعدلة الأولى التي تضع العناصر في قائمة انتظار ذات أولوية (بدلاً من قائمة الانتظار العادية التي يتم استخدامها عادة في أ BFS) ، وإنهاء الفحص بعد اجتياز عناصر K بالضبط.نظرًا لأن حجم قائمة الانتظار يبقى O (k) في جميع أنحاء اجتياز ، فإنه يتطلب وقت O (Klog K) لإكماله ، مما يؤدي إلى حد زمني لـ O (N + Klog K) على هذه الخوارزمية.

من هنا.