كيفية كشف التعقيد من هيكل الكود

كيفية تحديد Big O من الكود

Big O مختبئ في شكل الكود. أربعة أنماط تغطي معظم الحالات:

حلقة واحدة على N عنصر: O(N)

# O(N): مرور واحد عبر القائمة
for item in list_of_n_items:
    process(item)

حلقات متداخلة، كل واحدة على N عنصر: O(N²)

# O(N²): كل عنصر مع كل عنصر آخر
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

البحث في الوقت الثابت: O(1)

وصول مصفوفة حسب الفهرس، البحث في جدول التجزئة — خطوة واحدة بغض النظر عن الحجم.

فرق و فتح (قطع المشكلة في النصف في كل خطوة): O(log N)

البحث الثنائي: كل فحص ينصف العناصر المتبقية.

---

O(N²) المختبئ: قائمة داخل حلقة

# هذا يبدو مثل O(N) لكنه في الواقع O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # يفحص جميع العناصر في visited: O(N)
        visited.append(item)  # الحلقة كاملة: O(N²)

سطر if item not in visited يفحص كل عنصر في visited في كل تكرار. فحص القائمة يكلف O(N). حلقة تعمل N مرة، في كل مرة تقوم بـ O(N) عمل: O(N) × O(N) = O(N²).

هذا النمط يظهر في 1,000+ مشروع مفتوح المصدر. الإصلاح يأخذ حرفًا واحدًا: استبدل visited = [] بـ visited = set(). اختبار عضوية المجموعة يكلف O(1)، وليس O(N). تغيير واحد. نتائج نفسها. 1,000× أسرع عند N=1,000.

صنف وأصلح هذا الكود

اقرأ هذا الكود:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

النظرية تلتقي الممارسة

Big O في البرية

Big O ليس مجرد نظرية. إنه يفصل البرامج التي تنتهي في ثوان عن البرامج التي تستغرق 17 دقيقة — على نفس المهمة بالضبط.

مثال حقيقي: كشف دورات التبعية في نظام البناء.

عندما تثبت برنامجًا، يحل الكمبيوتر رسم بياني للتبعيات: الحزمة A تحتاج B، B تحتاج C، وهكذا. يفحص نظام البناء هذا الرسم البياني للدورات.

خوارزمية كشف الدورات O(N²) تعمل بشكل جيد عند N=100 حزمة. عند N=50,000 حزمة (مشروع حقيقي): تستغرق 17 دقيقة. الإصلاح O(N): 10 ثوان.

هذا العيب الدقيق موجود في GHC (مصرف Haskell)، pip (مدير حزم Python)، Maven (نظام بناء Java)، Cargo (مدير حزم Rust)، & 1,000+ مشروع آخر.

ليس لأن مؤلفيهم كانوا غير مبالين. visited = [] كُتبت عندما كان N صغيرًا. تصلب الكود. نمت N. لم ينتبه أحد حتى بدأ البناء يستغرق نصف ساعة.

Big O هو المفردات التي تسمح لك بتسمية ما حدث — & إصلاحه.

---

هل تريد أن تذهب أعمق؟ دورتنا unhamming تتضمن فصلًا كاملاً عن Big O، MOAD-0001 (عيب O(N²) حقيقي وجد في 1,000+ مشروع مفتوح المصدر)، & لماذا تسمية نمط يسمح لك باكتشافه في كل مكان. انظر الفصل المفقود: تعقيد الخوارزمية.

تنبأ بأوقات البناء

نظام بناء يستخدم كشف دورات O(N²).

أوقات البناء المقاسة:

- N=100 حزمة: 0.01 ثانية

- N=1,000 حزمة: 1 ثانية

لـ O(N²): يتناسب الوقت مع (N_new / N_old)².

لـ O(N): يتناسب الوقت مع (N_new / N_old).