Big O Notation: ما يتوقعه امتحان A-Level في علوم الحاسوب فعلاً

Big O notation تظهر في كل مقرر A-level رئيسي في علوم الحاسوب (AQA, OCR, Edexcel) وتربك الكثير من الطلاب ليس لأن الرياضيات صعبة، بل لأنهم لا يرونها مرتبطة بالكود الفعلي. هذا شرح عملي لما تحتاج إلى معرفته وكيفية الإجابة على أسئلة الامتحانات عنها بدون إطالة.

ما يقيسه Big O فعلاً

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

عندما تكتب O(n)، أنت تقول: إذا ضاعفت الإدخال، العمل يتضاعف تقريباً. O(n²) تعني أن مضاعفة الإدخال تضاعف العمل أربع مرات تقريباً. هذه العلاقة هي ما يريده الممتحنون منك أن تحددها، وليس عدد العمليات الدقيق.

التعقيدات التي تحتاج إلى معرفتها

في A-level، هذه هي الحالات التي تظهر مراراً وتكراراً:

• O(1) – وقت ثابت. الوصول إلى عنصر المصفوفة بالفهرس: arr[5]. لا يهم حجم المصفوفة.
• O(log n) – لوغاريتمي. البحث الثنائي في قائمة مرتبة. كل خطوة تنصف فضاء البحث المتبقي.
• O(n) – خطي. حلقة واحدة عبر قائمة، مثل البحث الخطي الذي يفحص كل عنصر مرة واحدة.
• O(n log n) – خطي لوغاريتمي. Merge sort و quicksort (الحالة المتوسطة) يقعان هنا.
• O(n²) – تربيعي. حلقات متداخلة على نفس البيانات، وهذا بالضبط ما يفعله bubble sort و insertion sort و selection sort.
• O(2ⁿ) – أسي. Fibonacci العودي الساذج بدون memoisation. يصبح سيئاً بسرعة.

يجب أن تكون قادراً على النظر إلى الكود الوهمي والقول أي من هذه هو على الفور، لأن هذا هو في الأساس ما يتم اختباره.

قراءة الكود للتعقيد

الطريقة التي تعمل في كل مرة: عد الحلقات وانظر كيف ترتبط بـ n.

# O(n) - حلقة واحدة، مسار واحد
for i in range(n):
    print(i)

# O(n^2) - حلقة متداخلة، كلاهما مرتبط بـ n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - فضاء البحث ينصف في كل تكرار
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

الحلقة المتداخلة حيث يعتمد نطاق الحلقة الداخلية على n لا تزال O(n²)، حتى لو بدت مختلفة قليلاً (مثل for j in range(i) بدلاً من for j in range(n) — هذا لا يزال تربيعياً بشكل عام، فقط مع فرق في عامل ثابت).

انتبه للحلقات التي لا تعتمد على n على الإطلاق. الحلقة التي تعمل دائماً 10 مرات بغض النظر عن حجم الإدخال هي O(1)، حتى لو كانت هناك حلقة موجودة. الممتحنون يحبون إدراج هذا.

خوارزميات الفرز الشائعة و Big O الخاصة بها

هذا موضوع امتحان مفضل لأنه يجمع بين مقررين في وقت واحد: خوارزميات الفرز والتعقيد.

الخوارزمية	أفضل حالة	أسوأ حالة
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

اتساق Merge sort (نفس التعقيد في أفضل وأسوأ حالة) يستحق الإشارة إليه صراحة إذا سأل سؤال لماذا تختار هذا على bubble sort للمجموعات البيانات الكبيرة. أفضل حالة في bubble sort من O(n) تنطبق فقط مع تحسين الخروج المبكر عندما لا تحدث عمليات تبديل في مسار — اذكر هذه التفاصيل إذا أثرت عليها، لأن بعض مجالس الامتحانات تتوقعها.

حيث يفقد الطلاب النقاط

الأكبر: الكتابة