القاعدة التقريبية 10^8

ينفّذ المحكّم الإلكتروني المعتاد نحو 10^8 عملية بسيطة في الثانية. وهذا الرقم هو ميزانية العمليات المتاحة للبرنامج بأكمله. 💡

اضرب عدد العمليات في العمل المنجز في كل خطوة، ثم قارنه بـ الحد الزمني. إذا وقع عدد الخطوات ضمن الميزانية، فمن المرجح أن ينجح الحل.

مسح O(n) على n = 10^6 لا يتطلب سوى مليون خطوة، وهو أقل بكثير من الميزانية. وتنجح الحلول الخطية تقريبًا دائمًا بفارق مريح.

عند n = 10^6، يحتاج الفرز بتعقيد O(n log n) إلى نحو 2 × 10^7 خطوة. وهذا لا يزال ضمن ميزانية الثانية الواحدة بكثير، لذا نادرًا ما يكون الفرز عنق الزجاجة.

يبلغ الأسلوب ذو التعقيد O(n^2) حد الميزانية قرب n = 10^4، حيث يتطلب 10^8 خطوة. وبعد ذلك يبدأ التعقيد التربيعي في تجاوز الحد الزمني.

لا يصمد الحل ذو التعقيد O(n^3) إلا حتى نحو n = 500. وتكعيب هذا العدد يعطي تقريبًا 10^8 خطوة، أي عند حافة الميزانية.

يتضاعف O(2^n) مع كل خطوة، لذا لا يعمل إلا مع قيم صغيرة جدًا لـ n، نحو 20 إلى 25. وبعد ذلك يتجاوز عدد العمليات 10^8 بسرعة هائلة.

تنفّذ Python كل خطوة بسرعة أقل، لذا تعامل مع الميزانية باعتبارها أقرب إلى 10^7 في الحلقات الضيقة. كن حذرًا عندما تبدو القيود قريبة من الحد.

تحسب قاعدة 10^8 الخطوات البسيطة. أما العمل المكلف داخل الحلقة، مثل بناء السلاسل النصية، فيضيف عاملًا ثابتًا يقلّص ميزانيتك الفعلية.

غالبًا ما يكون الحد الزمني ثانية أو ثانيتين. ويضاعف الحد البالغ ثانيتين تقريبًا ميزانيتك، مما يمنحك هامشًا إضافيًا قليلًا.

عوّض دائمًا قيمة n في تعقيدك وقارنها أولًا بـ 10^8. فهذا الفحص السريع للمعقولية يجنبك كتابة حل محكوم عليه بالفشل.

طبّق قاعدة 10^8 عمليًا.

أصبحت الآن تربط العمليات بالزمن: نحو 10^8 في الثانية. التعقيدان الخطي وn log n آمنان، والتربيعي يبلغ حدّه قرب 10^4، وتفحص ذلك قبل كتابة التعليمات البرمجية. ✅