كيف هو التعقيد المقارب لإيجاد الوقت الخطي للعنصر الأكبر التالي؟

Question

كنت أقرأ خوارزمية للحصول على العنصر الأكبر التالي لكل عنصر في المصفوفة.

يدعي الموقع أن التعليمات البرمجية الخاصة بهم تعمل O(n) الوقت، لكني غير قادر على الالتفاف حوله.

إن الاجتياز الكامل للمصفوفة من اليسار إلى اليمين سيكلف في حد ذاته O(n), ، علاوة على ذلك يمكن أن تكون هناك عمليات دفع/فرقعة متعددة في كل فهرس أثناء اجتياز القائمة.

على الرغم من أن عمليات الدفع/البوب ​​تستغرق وقتًا ثابتًا، إلا إذا تم استدعاؤها بمعدل متوسط m مرات لكل عنصر فهرس، سيكون لدينا O(m) كتكلفة عمليات الدفع/البوب ​​في كل مؤشر، مما يؤدي إلى O(mn) كتكلفة إجمالية، نظرًا لأن إجمالي عدد عمليات الدفع/البوب ​​يجب أن يكون تقريبًا (أو ربما بالضبط) مساويًا لـ n, ، يمكننا القول بأنه mn يساوي تقريبًا (أو ربما بالضبط) n مما يعني أن m هو ثابت.

هل تبريري صحيح؟

ما زلت لا أتمتع بالوضوح المناسب فيما يتعلق بأسبابي الخاصة، هل يمكن لأي شخص أن يقدم تفسيرًا أفضل بالإضافة إلى التحقق من صحة/إبطال مبرري؟

Answer 1

تم نسخ الرمز الزائف هنا للراحة:

1. ادفع العنصر الأول إلى المكدس.
   
2. اختر بقية العناصر واحدًا تلو الآخر واتبع الخطوات التالية في الحلقة.
   
   1. قم بتمييز العنصر الحالي كـ التالي.
      
   2. إذا لم يكن المكدس فارغًا، فقم بإخراج عنصر من المكدس ومقارنته به التالي.
      
   3. إذا كان التالي أكبر من العنصر المنبثق، إذن التالي هو العنصر الأكبر التالي للعنصر المنبثق.
      
   4. استمر في الظهور من المكدس بينما يكون العنصر المنبثق أصغر من التالي. التالي يصبح العنصر الأكبر التالي لجميع هذه العناصر المنبثقة
      
   5. لو التالي أصغر من العنصر المنبثق، ثم ادفع العنصر المنبثق للخلف.
      
   6. يدفع التالي على المكدس [هذه الخطوة مفقودة من الكود الزائف]
3. بعد انتهاء الحلقة في الخطوة 2، قم بإخراج كافة العناصر من المكدس واطبع -1 كعنصر تالي لها.

يتم تشغيل الحلقة الخارجية O(n) مرات.

من الواضح، باستثناء العمل المنجز للعناصر المنبثقة التي لم يتم دفعها للخلف (الخطوة رقم 4، مطروحًا منها العنصر الأخير الذي تعالجه)، فإن بقية تكرار الحلقة هو وقت ثابت.

لذا فإن أي عنصر يستمر في الظهور ودفعه مرة أخرى إلى المكدس سيتم تضمينه بالفعل في الوقت الثابت لكل تكرار حيث يتم ظهوره ودفعه مرة أخرى.

كل ما تبقى هو الأوقات التي تظهر فيها العناصر ولا يتم دفعها للخلف، ولكن من الواضح أن هذا لا يمكن أن يحدث إلا مرة واحدة لكل عنصر، وبالتالي فإن هذا يمثل، في المجمل، O(n) وقت الركض.

نظرًا لأننا لا نكرر العناصر الموجودة في المكدس أبدًا (ندفع كل عنصر من المصفوفة مرة واحدة، ثم ندفع مرة أخرى فقط بعد ظهوره) فلا يمكن أن يكون هناك أكثر من n العناصر الموجودة في المكدس، وبالتالي فإن الخطوة النهائية تستغرق على الأكثر O(n) وقت.

وبالتالي فإن إجمالي وقت التشغيل هو O(n + n + n) = O(n).

---

طريقة بديلة للتفكير في الأمر:

نقوم بتنفيذ عمليتي دفع كحد أقصى أثناء كل تكرار للحلقة (والتي توجد n ل).

وبالتالي هناك على الأكثر 2n عمليات الدفع، وبالتالي أيضًا على الأكثر 2n عمليات البوب ​​(لا يمكننا فرقع العناصر التي لم يتم دفعها).

نحن نقوم بقدر ثابت من العمل لكل عملية دفع/فرقعة، بالإضافة إلى أننا نقوم بقدر ثابت من العمل لكل تكرار حلقة (تجاهل العمل المنجز لكل عملية دفع/فرقعة)، وبالتالي فإن إجمالي وقت التشغيل هو O(n + 4n) = O(n).

Answer 2

انت ربما لديك m العمليات لكل تكرار n لكن m لا يزال ثابتا ومستقلا عن n.

عدد عمليات الدفع/البوب ​​ثابت لكل تكرار n لذلك لا تؤثر على التعقيد الزمني للخوارزمية.