كيف تجد جميع الأعداد الصحيحة في مجموعة مفروشة من الحجم ن التي تظهر أوقات n / k؟

Question

أحاول العثور على الحل لهذه المشكلة: كيف تجد جميع الأعداد الصحيحة في مجموعة مفروشة من الحجم N التي تظهر أوقات n / k في أقل من وقت O (klogn)؟

يمكن أن أجد فقط تم توفير هذا السؤال ، حيث تم توفير محلول O (klogn).

Answer 1

دعنا نبدأ بالحالة $ 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.

تنظر الآن في $ n / 2 + 1 $ صفائف النموذج التالي: هناك تشغيل $ n / 2 $ العديد من $ 0 $ s بدأت في بعض الوظائف $ j \ in \ {1، \ ldots، N / 2 + 1 \} $ ، وبقية العناصر فريدة من نوعها. في كل صفيف من هذا القبيل، هناك خيار فريد من نوعه للفهرس $ i $ المذكورة أعلاه. وبالتالي فإن شجرة القرار تمثل الخوارزمية لديها $ n / 2 + 1 $ الأوراق، وبالتالي يجب أن يكون لديك عمق $ \ أوميغا (\ سجل ن) $ .

---

في الحالة العامة، يجب أن تعرف الخوارزمية فهرس $ 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 $ .

(قد تكون الخوارزميات محسنة بشكل صارخ لإعطاء ملزمة أعلى مطابقة.)