العثور على أعلى رقمين - علوم الكمبيوتر

Question

أحاول اكتشاف خوارزمية للعثور على أعلى رقمين في قائمة الأرقام.

يمكن العثور على أعلى رقم في مراحل n-1، ربما عن طريق القيام بالخطوة الأولى لفرز الفقاعات أو شيء من هذا القبيل.بالنسبة لي، يبدو أنه يمكن العثور على الرقم التالي الأعلى أيضًا في إجمالي 1.5n من المقارنات في المتوسط.

كلّفنا أستاذي بواجب منزلي لكتابة خوارزمية تجد أعلى رقمين في مقارنات n + log(n).هل هذا ممكن حتى؟أي أفكار أو اقتراحات؟

يحرر:عندما أقول n + log(n) فأنا لا أشير إلى O(n + log n)، بل أشير بالضبط إلى n + log n

Answer 1

نعم، من الممكن القيام بذلك في مدة لا تزيد عن (n + log n).لا أستطيع حقاً أن أخبرك كيف دون أن أكشف عن الإجابة، لكن دعني أحاول.:-)

خذ الأرقام n، وقارنها في أزواج في المرة الواحدة.خذ السقف (n/2) "الفائزين"، وكرر "مثل الشجرة الثنائية".أسئلة:كم عدد المقارنات اللازمة للعثور على أكبرها؟كم عدد الأشخاص الذين سيفوز عليهم هذا "الفائز"؟لمن قد يخسر ثاني أكبر؟إذن، كم عدد المقارنات التي نحتاجها الآن للعثور على ثاني أكبر عدد؟

الجواب هو مجموع ن-1 + سقف(سجل ن) - 1 المقارنات، حيث يكون السجل للقاعدة 2.يمكنك أيضًا أن تثبت باستخدام حجة عدائية أنه من غير الممكن القيام بعمل أفضل من هذا في أسوأ الحالات.

Answer 2

يحرر:عفوا، فاتتك حاجة بسيطة بسبب الغباء.هذا الحل غير صحيح، على الرغم من أنني أحتفظ به هنا لأنه لا يزال متوسطًا (n+log(n)).شكرًا لـ ShreevatsaR على الإشارة إلى غبائي.لقد فكرت في البحث الشجري، لكنني فاتني تمامًا فكرة التراجع للعثور على ثاني أعلى رقم في السجل (ن).

على أي حال، إليك دليلي على سبب عدم كون الخوارزمية السفلية أكثر من avg(n+log(n)).في الحياة الواقعية، يجب أن يظل الأداء جيدًا على الأقل.

• قارن أولا مع ثاني أعلى رقم مسجل.
• فقط إذا نجحت تلك المقارنة، قارن بأعلى رقم مسجل.

لإثبات أنه في المتوسط ​​n+log n، علينا ببساطة أن نثبت أن المقارنة الأولى تنجح فقط في log(n) مرات في المتوسط.وهذا أمر بسيط إلى حد ما لرؤيته أو إثباته.

1. افترض أن P هو الموضع الفعلي لثاني أكبر رقم حالي في نسخة مرتبة من القائمة، وقم بتشغيل الخوارزمية
2. إذا كان P > 2، فعند العثور على رقم أكبر، لن يكون P الجديد في المتوسط ​​أكثر من P/2.
3. إذا كانت P = 2، فلا يمكن أن تنجح المقارنة الأولى، حيث لا يوجد رقم أكبر من ثاني أكبر رقم حالي.
4. يمكن أن تساوي P على الأكثر N
5. من 2 و3 و4 يجب أن يكون من التافه أن نرى أن المقارنة الأولى لا يمكن أن تنجح أكثر من log(N) مرات في المتوسط.

Answer 3

وماذا عن هذا:

for each listOfNumbers as number
    if number > secondHighest
        if number > highest
            secondHighest = highest
            highest = number
        else
            secondHighest = number

Answer 4

والجواب المرسلة بواسطة ShreevatsaR يبدو أن O (ن سجل ن).

ومرور الأول (ن العمليات) وتنتج ن / 2 إجابات. بتكرار، أعتقد يعني أنك سوف تفعل ن / 2 العمليات لإنتاج ن / 4 إجابات. عليك أن تذهب من خلال سجل حلقة n مرة. هذا يشبه الى حد كبير نوعا دمج إلا أن دمج عمليات الفرز دائما ن الليمفاوية في كل مرة من خلال. كما تدير سجل حلقة n مرة. وأنا لا أرى كيف هذه الخوارزمية سوف تتبع عدد higest الثاني.

وnickf لديه الجواب الصحيح. أسوأ الحالات هي عندما يتم فرز القائمة، انها لن تفعل مقارنات 2N - التي هي O (ن)

وراجع للشغل، O (ن + تسجيل ن) هو O (ن) للتدوين ترتيب يشير إلى نمو مقارب أسوأ الحالات.

Answer 5

ويمكنك استخدام العد الفرز، نوع الجذر، نوع دلو أو غيرها من خوارزمية الزمن الخطي لفرز أول القائمة في ترتيب تنازلي. ثم مجرد الحصول على العناصر 2 الأولى من قائمة تم فرزها. لذلك هذا سيستغرق (ن) + 2 = (ن)

لاحظ أن هذه الخوارزميات يمكن فرز في الزمن الخطي لأن كل واحد لديه الافتراضات الخاصة بها.

Answer 6

وشبة الكود (ليس هذا الأساس ن؟)

int highestNum = 0
int secondHighest = highestNum

for(i = 0; i < list.length; i++)
{
if(list[i] >= highestNum)
{
secondHighest = highestNum
highestNum = list[i]
}
}