تحليل تعقيد الخوارزميات: افهم Big O بمقارنة نمو العمل

Big O بتوصف إيه؟

حدد أيضًا الحالة التي تحللها: أسوأ حالة، أو متوسطًا بافتراضات معينة، أو حالة أخرى. الرمز وحده لا يعني تلقائيًا أسوأ حالة.

قارن النمو

هذه قيم رياضية توضيحية، لا أزمنة تشغيل فعلية. الثوابت والتنفيذ والجهاز تؤثر في القياس العملي.

تقليل مجال بحث مناسب إلى النصف كل مرة يؤدي إلى نمو لوغاريتمي في عدد الخطوات. المرور على كل العناصر ينمو خطيًا، ومقارنة كل زوج مرتب قد تنمو تربيعيًا.

حلقات متتالية أم متداخلة؟

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

لكن ليس كل تداخل تربيعيًا. لو الحلقة الداخلية تنفذ ثلاث مرات دائمًا، يظل النمو خطيًا. احسب التكرارات الفعلية قبل تبسيطها.

احسب تجهيز البيانات

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

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

المساحة الإضافية جزء من التحليل

الاحتفاظ بأكبر قيمة أثناء المرور يحتاج مساحة إضافية ثابتة. إنشاء نسخة كاملة من n عنصر يحتاج مساحة إضافية خطية.

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

تمرين سريع

في نموذج مبسط، طريقة تنفذ 5n عملية وأخرى مربع n. عند n = 3 تكون القيم 15 و9. وعند n = 100 تصبح 500 و10,000.

هذا يوضح اختلاف النمو التقاربي عن أداء الأحجام الصغيرة. لا تحول الرمز إلى حكم بأن برنامجًا أسرع مع كل المدخلات.

عند دراسة الخوارزميات في جمال تك، استفد من هياكل البيانات لتحديد العمليات التي تعدها. الشرح الجيد يذكر الحجم والحالة والافتراضات.