Big-O بدون تعقيد
تعرف على ترميز Big-O بطريقة عملية تساعدك على مقارنة الحلول واتخاذ قرار أفضل عند نمو حجم البيانات.
السؤال الحقيقي: ماذا يحدث عندما تكبر البيانات؟
قد تنفذ دالتان بسرعة متقاربة عند عشر عناصر، ثم تصبح إحداهما أبطأ بوضوح عند مليون عنصر. ترميز Big-O يصف كيف ينمو عدد العمليات أو حجم الذاكرة مع حجم الإدخال n. هو نموذج للمقارنة قبل القياس، وليس بديلًا عن قياس الأداء الحقيقي.
نتجاهل الثوابت والحدود الأصغر عندما نناقش النمو التقريبي. الدالة التي تنفذ 3n + 20 عملية تصنف O(n)، لأن أثر n هو المسيطر عند زيادة الحجم. هذا لا يعني أن الثوابت لا تهم في الإنتاج؛ يعني فقط أن Big-O تجيب عن سؤال مختلف.
الأنماط التي ستقابلها كثيرًا
الوصول إلى عنصر مصفوفة بفهرسه O(1) تقريبيًا. المرور على كل العناصر O(n). البحث الثنائي في قائمة مرتبة O(log n) لأنه يستبعد نصف المساحة كل خطوة. حلقة داخل حلقة تمران على كل زوج غالبًا O(n²). الفرز المقارن الجيد عادةً O(n log n).
لا تحفظ القائمة دون ربطها بسبب. اكتب عدد مرات تكرار العمل بالنسبة إلى n. إذا انقسمت المشكلة إلى النصف كل مرة ففكر في log n. إذا أنشأت كل التركيبات الممكنة فقد يظهر نمو أُسّي، وهو تحذير مبكر قبل كتابة تفاصيل الحل.
function indexUsers(users) {
const byId = new Map();
for (const user of users) {
byId.set(user.id, user);
}
return byId;
}
const usersById = indexUsers(users);
usersById.get(targetId);الزمن والذاكرة مقايضة
استخدام Map في المثال يستهلك ذاكرة إضافية O(n)، لكنه يجعل عمليات البحث المتكررة أسرع. إذا كنت ستبحث مرة واحدة فقط، قد لا يستحق بناء الفهرس. وإذا كانت الذاكرة محدودة جدًا، قد تختار حلاً أبطأ يستخدم مساحة أقل.
احسب أيضًا حجم المخرجات. لا يمكن لخوارزمية تعيد نسخة من n عناصر أن تستخدم مساحة أقل من حجم الناتج نفسه. وعند تحليل recursion، انتبه إلى عمق مكدس الاستدعاءات حتى لو لم تنشئ مصفوفة جديدة صراحة.
طريقة عملية في المقابلة والمشروع
حدد n بوضوح، ثم اكتب العملية المسيطرة، ثم اذكر الزمن والذاكرة، ثم ناقش المقايضة. بعد ذلك قِس على بيانات تشبه الإنتاج لأن cache وسرعة الشبكة وقاعدة البيانات قد تكون أهم من تعقيد دالة صغيرة.
لا تستخدم Big-O لتبرير تعقيد معماري غير مطلوب. حل O(n) بسيط على قائمة لا تتجاوز مئة عنصر قد يكون أفضل من فهرس يحتاج مزامنة وصيانة. الهدف هو قرار واعٍ مبني على حجم متوقع، لا مطاردة أفضل رمز في كل سطر.
- •عرّف حجم الإدخال n.
- •حدد أكثر جزء يتكرر مع نمو n.
- •افصل متوسط الحالة عن أسوأ حالة عندما يغيّر ذلك القرار.
- •اختبر ببيانات واقعية بعد التحليل.
المراجع ومزيد من القراءة
عن المؤلف
يراجع أسامة زيدان محتوى كود هاب بهدف تقديم شرح عربي واضح يربط المفاهيم البرمجية بالقرارات التي يواجهها المتعلم أثناء التطبيق.
صفحة المؤلف