الحد الأدنى النظري من العثور على عدد من تكرارات عدد صحيح مستهدف في صفيف مرتبة

Question

نظرا مجموعة فرز من الأعداد الصحيحة وعدد صحيح الهدف، ابحث عن عدد مرات الأعداد الصحيحة المستهدفة.

من المعروف أن البحث الثنائي لديه تعقيد الوقت $ o (\ lg n) $ حيث $ n$ هو حجم الصفيف. على سبيل المثال، بالنظر إلى صفيف $ [1،2،3،3،4،5] $ ومستهدف 3 دولار،$ يجب أن تعود الخوارزمية $ 2 $ نظرا لأن هناك نسختان من $ 3 $ في الصفيف.

سؤال: هل هناك خوارزميات أسرع والتي لها تعقيد الوقت أقل من $ o (\ lg n)؟ $ خلاف ذلك، هل هناك دليل لإثبات أن $ \ أوميغا (\ LG N) $ هو الحد الأدنى النظري؟

Answer 1

تتطلب المشكلة $ \ omega (\ log n) $ الوصول إلى الذاكرة حتى إذا كنت وعدت بأن عدد صحيح الهدف يظهر في معظم مرة واحدة مرة واحدة. يمكنك إثبات ذلك باستخدام حجة خصم.

قل أن الهدف هو الصفر. إذا تبقى الوصول الأول إلى الصفيف إلى المركز، فإن الإجابة $ - 1 $ ، وتعيين العناصر عقليا على اليسار لتكون $ - 2، -3، \ LDots $ . إذا كان الوصول الأول هو حق المركز، والإجابة $ + 1 دولار ، وقم بإعداد العناصر عقليا إلى اليمين لتكون 2 دولار ، 3، \ LDots $ .

لنفترض أن الوصول الأول كان على يمين الوسط، ويقول موقف $ i $ ، والنظر في الوصول الثاني. إذا كان ذلك يمينا الحق في الوصول الأول، فأنت تعرف بالفعل ما للإجابة. خلاف ذلك، هناك حالتان. إذا كان موضع الوظيفة التي تم الوصول إليها $ J $ هي أقل من $ I / 2 $ ، الإجابة $ - 1 دولار (وملء العناصر إلى اليسار). إذا كان أكثر من $ I / 2 $ ، الإجابة $ + 1/2 $ (وملء عناصر إلى اليمين حتى وضع $ i $ ).

متابعة بهذه الطريقة، في كل خطوة عدد المراكز التي يمكن أن تحتوي على العنصر المستهدف في النصف في كل خطوة. أخيرا، عندما لا يزال عنصر واحد فقط على المحك، دون الاستعلام عن ذلك، لا يمكن أن تعرف الخوارزمية بالتأكيد ما إذا كان الصفيف يحتوي على العنصر المستهدف أم لا. يستغرق الأمر $ \ log_2 n $ خطوات للوصول إلى هذه الخطوة.

ما سبق يوضح بالفعل أن البحث الثنائي هو الأمثل للبحث عن صفيف فرز.

Answer 2

هناك $ n $ الإجابات المحتملة.تمنحك كل مقارنة على الأكثر قليلا من المعلومات.تحتاج إلى الأقل $ \ LG N $ bits من المعلومات لوصف الإجابة، لذلك ستحتاج إلى $ \LG N $ المقارنات.