كيف تجد جميع الأعداد الصحيحة في مجموعة مفروشة من الحجم ن التي تظهر أوقات n / k؟
-
29-09-2020 - |
سؤال
أحاول العثور على الحل لهذه المشكلة: كيف تجد جميع الأعداد الصحيحة في مجموعة مفروشة من الحجم N التي تظهر أوقات n / k في أقل من وقت O (klogn)؟
يمكن أن أجد فقط تم توفير هذا السؤال ، حيث تم توفير محلول O (klogn).
المحلول
دعنا نبدأ بالحالة $ k= 2 $ ، ويفترض أن الخوارزمية مقرها مقارنة.
أدعي أن أي خوارزمية تجد حتى عنصر واحد يظهر $ n / 2 $ مرات يجب أن تعرف الفهرس $ i $ مثل $ A [i + 1]= a [i + n / 2] $ . في الواقع، لنفترض أن هذا ليس هو الحال، ودعنا نفترض البساطة أن إدخالات $ A $ هي أرقام حقيقية. دعنا نقول أن الخوارزمية تعرف القيم التالية: $$ A [i_1]=CDOTS= A [j_1] إنه ثابت مع معرفة الخوارزمية بأن $ A [i_1-1] وهلم جرا، ومع القليل جهد يمكننا ترتيب أنه لا يوجد عنصر يظهر $ n / 2 $ times.
في الحالة العامة، يجب أن تعرف الخوارزمية فهرس $ i $ $ مثل $ a [i + 1]= A [i + n / k] $ لكل عنصر هو الإخراج. يمكننا تقسيم الصفيف في $ k / 2 $ أجزاء من الحجم $ 2n / k $ ، والنظر فيها $ (n / k + 1) ^ k $ الأمثلة كما كان من قبل، حيث $ r $ العنصر الظهور $ n / k $ مرات في $ r $ الجزء. هذا يعطي الحد الأدنى من $ \ Omega (k \ log (n / k)) $ ، مطابقة الحد العلوي الخاص بك تقريبا لجميع قيم $ K $ .
(قد تكون الخوارزميات محسنة بشكل صارخ لإعطاء ملزمة أعلى مطابقة.)