Algorithms Analysis Methods طرق تحليل الخوارزميات (Algorithms)

Mastering the framework to measure efficiency, asymptotic notations, and the mathematical analysis of recursive and non-recursive algorithms. إتقان إطار العمل لقياس الكفاءة، والترميزات المقاربة (Asymptotic notations)، والتحليل الرياضي للخوارزميات العودية وغير العودية.

Time vs Space الوقت مقابل المساحة O, Ω, Θ Notations O, Ω, Θ Notations Recurrence Relations Recurrence Relations Empirical Analysis التحليل التجريبي

The Analysis Framework إطار عمل التحليل (Analysis Framework)

Two Types of Efficiency نوعان من الكفاءة

  • Time Efficiency: How fast the algorithm runs (Time Complexity). كفاءة الوقت (Time Efficiency): مدى سرعة تشغيل الخوارزمية (تعقيد الوقت).
  • Space Efficiency: Memory units required for algorithm + input/output (Space Complexity). كفاءة المساحة (Space Efficiency): وحدات الذاكرة المطلوبة للخوارزمية + المدخلات/المخرجات.

Measuring Input Size ($n$) قياس حجم المدخلات ($n$)

Input size depends on the problem type : يعتمد حجم الإدخال على نوع المشكلة:

  • Polynomials: Degree of polynomial or number of coefficients. كثيرات الحدود (Polynomials): درجة كثير الحدود أو عدد المعاملات.
  • Matrices: Dimensions ($n \times n$). المصفوفات (Matrices): الأبعاد ($n \times n$).
  • Primality Check: Number of bits $b = \lfloor \log_2 n \rfloor + 1$ (NOT the number value itself). اختبار الأولية (Primality Check): عدد البتات $b = \lfloor \log_2 n \rfloor + 1$ (وليس قيمة الرقم نفسه).

The "Basic Operation" العملية الأساسية (Basic Operation)

We DO NOT measure time in seconds or milliseconds because that depends on the computer speed, compiler, and quality of code . نحن لا نقيس الوقت بالثواني أو المللي ثانية لأن ذلك يعتمد على سرعة الكمبيوتر، المترجم (compiler)، وجودة الكود.

Instead, we count the Basic Operation: the operation contributing most to running time (usually the most frequent one inside the innermost loop). بدلاً من ذلك، نحسب العملية الأساسية (Basic Operation): العملية التي تساهم بشكل أكبر في وقت التشغيل (عادةً الأكثر تكراراً داخل الحلقة الأعمق).

Problem المشكلة Basic Operation العملية الأساسية
Searching List البحث في القائمة Key Comparison مقارنة المفاتيح
Matrix Multi. ضرب المصفوفات Multiplication الضرب
Graph Problem مشكلة الرسم البياني Visiting Vertex زيارة الرأس (Vertex)

Worst, Best, & Average Cases الحالات: الأسوأ، الأفضل، والمتوسطة

Worst-Case الحالة الأسوأ (Worst-Case)

The input that makes the algorithm run the longest. It provides an Upper Bound guarantee. The algorithm will never take longer than this . الإدخال الذي يجعل الخوارزمية تعمل لأطول فترة. يوفر ضمان الحد الأعلى (Upper Bound). الخوارزمية لن تستغرق وقتاً أطول من هذا أبداً.

$C_{worst}(n)$

Best-Case الحالة الأفضل (Best-Case)

The input that makes the algorithm run the fastest. Usually trivial (e.g., finding the item at index 0) . الإدخال الذي يجعل الخوارزمية تعمل بأسرع ما يمكن. عادة ما تكون بديهية (مثلاً، العثور على العنصر في الفهرس 0).

$C_{best}(n)$

Average-Case الحالة المتوسطة (Average-Case)

Based on probabilistic assumptions. Usually lies between Best and Worst. Requires knowing probability distribution of inputs . تعتمد على افتراضات احتمالية. عادة ما تقع بين الأفضل والأسوأ. تتطلب معرفة التوزيع الاحتمالي للمدخلات.

$C_{avg}(n)$

Amortized Efficiency: Not a single run, but the average cost over a sequence of operations. Useful when one expensive operation pays for many cheap ones (discovered by Robert Tarjan) . الكفاءة المطفأة (Amortized Efficiency): ليست تشغيلاً واحداً، بل متوسط التكلفة عبر سلسلة من العمليات. مفيدة عندما تدفع عملية واحدة مكلفة ثمن العديد من العمليات الرخيصة.

Asymptotic Notations ($O, \Omega, \Theta$) الترميزات المقاربة ($O, \Omega, \Theta$)

1. Big-O Notation $O(g(n))$ 1. Big-O Notation $O(g(n))$

Upper Bound. $t(n)$ grows no faster than $g(n)$. الحد الأعلى (Upper Bound). $t(n)$ تنمو ليس أسرع من $g(n)$.

$t(n) \le c \cdot g(n)$ for all $n \ge n_0$

Use for Worst-Case Analysis. تستخدم لتحليل الحالة الأسوأ.

c·g(n) t(n) n

2. Big-Omega Notation $\Omega(g(n))$ 2. Big-Omega Notation $\Omega(g(n))$

Lower Bound. $t(n)$ grows at least as fast as $g(n)$. الحد الأدنى (Lower Bound). $t(n)$ تنمو على الأقل بنفس سرعة $g(n)$.

$t(n) \ge c \cdot g(n)$ for all $n \ge n_0$

Use for Best-Case Analysis. تستخدم لتحليل الحالة الأفضل.

t(n) c·g(n)

3. Big-Theta Notation $\Theta(g(n))$ 3. Big-Theta Notation $\Theta(g(n))$

Tight Bound. $t(n)$ grows at the same rate as $g(n)$. الحد المحكم (Tight Bound). $t(n)$ تنمو بنفس معدل $g(n)$.

$c_2 \cdot g(n) \le t(n) \le c_1 \cdot g(n)$

Use for Exact/Average Analysis. تستخدم للتحليل الدقيق/المتوسط.

c1·g(n) t(n) c2·g(n)

Non-Recursive Analysis تحليل الخوارزميات غير العودية

Process : العملية:

  1. Decide on input parameter ($n$). تحديد معلمة الإدخال ($n$).
  2. Identify basic operation (innermost loop). تحديد العملية الأساسية (الحلقة الأعمق).
  3. Set up a Summation $\sum$. إعداد Summation $\sum$.
  4. Solve the sum to find closed form. حل المجموع لإيجاد الصيغة المغلقة (Closed Form).

// Example: UniqueElements

$C_{worst}(n) = \sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1$

$= \frac{(n-1)n}{2} \approx \frac{1}{2}n^2 \in \Theta(n^2)$

Recursive Analysis تحليل الخوارزميات العودية

Process : العملية:

  1. Decide on input parameter ($n$). تحديد معلمة الإدخال ($n$).
  2. Identify basic operation. تحديد العملية الأساسية.
  3. Set up a Recurrence Relation. إعداد Recurrence Relation.
  4. Solve using Backward Substitution. الحل باستخدام التعويض العكسي (Backward Substitution).

// Example: Factorial F(n)

$M(n) = M(n-1) + 1$ for $n > 0$

$M(0) = 0$

Result: $M(n) = n$

Empirical Analysis التحليل التجريبي (Empirical Analysis)

Used when mathematical analysis is too difficult. Involves generating random inputs, running the actual code, measuring time/count, and plotting results . يستخدم عندما يكون التحليل الرياضي صعباً للغاية. يتضمن توليد مدخلات عشوائية، وتشغيل الكود الفعلي، وقياس الوقت/العدد، ورسم النتائج.

The Exam Vault خزنة الاختبار

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: Value vs. Size فخ: القيمة (Value) مقابل الحجم (Size)

For Primality Testing, if the input is $n = 1,000,000$, the input size is NOT $10^6$. It is the number of bits: $b = \log_2(10^6) \approx 20$. This is a classic trick question . في اختبار الأولية (Primality Testing)، إذا كان الإدخال $n = 1,000,000$، فإن حجم الإدخال ليس $10^6$. إنه عدد البتات: $b = \log_2(10^6) \approx 20$. هذا سؤال خادع كلاسيكي.

TRAP: Inner Loops فخ: الحلقات الداخلية (Inner Loops)

Don't just count the loops. Look at the limits.
Loop $1..n$ inside Loop $1..n$ $\rightarrow O(n^2)$.
Loop $1..n$ inside Loop $1..10$ $\rightarrow O(n)$ (because 10 is constant). لا تقم فقط بعدّ الحلقات. انظر إلى الحدود (limits).
حلقة $1..n$ داخل حلقة $1..n$ $\rightarrow O(n^2)$.
حلقة $1..n$ داخل حلقة $1..10$ $\rightarrow O(n)$ (لأن 10 ثابت).

SECRET: The Constant Factor سر: العامل الثابت (Constant Factor)

In Asymptotic notation, constants ($c$) and lower order terms are ignored. $100n + 5 \in O(n^2)$ is technically true (loose bound), but $\Theta(n)$ is the tight (better) answer . في الترميز المقارب (Asymptotic notation)، يتم تجاهل الثوابت ($c$) والحدود ذات الرتبة المنخفضة. $100n + 5 \in O(n^2)$ صحيح تقنياً (حد فضفاض)، لكن $\Theta(n)$ هي الإجابة المحكمة (الأفضل).

KEY CONCEPT: Backward Substitution مفهوم مفتاحي: التعويض العكسي

Master the "Method of Backward Substitution" for recursive relations. It is the primary method required for Module 2 exams to prove $M(n)=n$ or similar . أتقن "طريقة التعويض العكسي" (Backward Substitution) للعلاقات العودية. إنها الطريقة الأساسية المطلوبة في اختبارات الوحدة 2 لإثبات $M(n)=n$ أو ما شابه.