Big-O Notation Concept
تعريف Big-O
هي طريقة لوصف كيفية نمو وقت تنفيذ الخوارزمية مع زيادة حجم المدخلات ($N$).
نحن نهتم بـ "أسوأ سيناريو" (Worst Case) وعندما يكون $N$ كبيراً جداً.
- احذف الثوابت: $O(2N)$ تصبح $O(N)$.
- احذف الحدود الأقل: $O(N^2 + N)$ تصبح $O(N^2)$.
ترتيب السرعة (الأفضل للأبطأ)
Calculating Time from Code
1. Simple Loop
sum++;
}
Complexity: $O(N)$
لأن الحلقة تدور N مرة.
2. Nested Loops
for (j=0; j<N; j++)
k++;
Complexity: $O(N^2)$
حلقة داخل حلقة (ضرب).
3. Logarithmic Loop
mid = (low+high)/2;
...
}
Complexity: $O(\log N)$
المجال ينقسم للنصف في كل خطوة.
Recursion Analysis
كيف نحلل الدالة العودية؟
نحول الكود إلى علاقة تكرارية (Recurrence Relation) ثم نحلها.
if (N <= 1) return 1;
return Fib(N-1) + Fib(N-2);
التحليل الرياضي:
$T(N) = T(N-1) + T(N-2) + O(1)$
السبب: نفس القيم تحسب مراراً وتكراراً (Overlapping Subproblems).
Consecutive Loops (حلقات متتالية)
ما هو تعقيد هذا الكود؟
for(..N..) {..}
for(..N..) {..}
الطلاب يظنونها $O(N^2)$ خطأً!
الصحيح: $O(N) + O(N) = O(2N) = O(N)$. (جمع وليس ضرب).
Dependent Inner Loop
for (j=0; j<i; j++) ...
الحلقة الداخلية تعتمد على i.
عدد المرات: $0 + 1 + 2 + ... + (N-1) = N(N-1)/2$.
التعقيد النهائي: $O(N^2)$.