طرق تحليل الخوارزميات
تغطي هذه الوحدة إطار عمل تحليل الخوارزميات، الرموز التقاربية، والتحليل الرياضي للخوارزميات التكرارية وغير التكرارية، بالإضافة إلى التحليل التجريبي.
Algorithms Analysis Methods
This module covers the algorithm analysis framework, asymptotic notations, mathematical analysis for recursive and non-recursive algorithms, and empirical analysis.
أهداف التعلم
- التعبير عن إطار عمل تحليل الخوارزميات وإطار التحليل.
- شرح دالة النمو، الرموز التقاربية، الدوال، وأوقات التشغيل.
- تطبيق إطار تحليل الخوارزميات على الدوال التكرارية وغير التكرارية.
- Express of analysis of algorithms framework and analysis framework.
- Explain the growth function Asymptotic notation, functions, and running times.
- Apply analysis of algorithm framework for recursive and non-recursive functions.
1 إطار عمل التحليل
1 The Analysis Framework
إطار عمل لتقييم كفاءة الخوارزمية بناءً على حجم المدخلات والعملية الأساسية، بدلاً من الاعتماد على سرعة الجهاز.
A framework to evaluate algorithm efficiency based on input size and basic operation, rather than hardware speed.
يعتمد إطار عمل تحليل الخوارزميات على نوعين من الكفاءة: الكفاءة الزمنية (Time efficiency) والكفاءة المكانية (Space efficiency).
بدلاً من قياس الوقت بالثواني (والذي يختلف باختلاف الأجهزة والمترجمات)، نقوم بحساب عدد مرات تنفيذ العملية الأساسية (Basic operation) كدالة في حجم المدخلات (Input size).
العملية الأساسية هي العملية التي تساهم بشكل أكبر في وقت التشغيل الكلي (عادة ما تكون داخل الحلقة الداخلية).
The algorithm analysis framework relies on two kinds of efficiency: Time efficiency and Space efficiency.
Instead of measuring time in seconds (which varies by hardware and compiler), we count the number of times the basic operation is executed as a function of the input size.
The basic operation is the operation that contributes most to the total running time (usually in the innermost loop).
لماذا نستخدم العملية الأساسية؟ لأن وقت التشغيل الكلي $T(n)$ يمكن تقريبه إلى $c_{op} \times C(n)$ حيث $c_{op}$ هو وقت تنفيذ العملية الأساسية و $C(n)$ هو عدد مرات تنفيذها.
هذا التجريد يسمح لنا بمقارنة الخوارزميات رياضياً بغض النظر عن بيئة التشغيل.
Why use the basic operation? Because the total running time $T(n)$ can be approximated as $c_{op} \times C(n)$ where $c_{op}$ is the execution time of the basic operation and $C(n)$ is the number of times it is executed.
This abstraction allows mathematical comparison of algorithms regardless of the execution environment.
لماذا يعتبر قياس وقت التشغيل بالثواني طريقة غير دقيقة لتحليل الخوارزميات؟ Why is measuring running time in seconds an inaccurate method for analyzing algorithms?
لأنه يعتمد على سرعة الجهاز، جودة المترجم (compiler)، ولغة البرمجة، مما يجعل المقارنة العادلة بين الخوارزميات مستحيلة.
Because it depends on hardware speed, compiler quality, and programming language, making fair comparison between algorithms impossible.
2 حالات الكفاءة (الأسوأ، الأفضل، والمتوسط)
2 Worst-case, Best-case, and Average-case Efficiencies
تختلف كفاءة الخوارزمية لنفس حجم المدخلات بناءً على طبيعة البيانات، مما يوجب دراسة الحالة الأسوأ، الأفضل، والمتوسطة.
Algorithm efficiency can vary for the same input size based on data nature, necessitating the study of worst, best, and average cases.
بالنسبة لبعض الخوارزميات (مثل البحث الخطي)، لا يعتمد وقت التشغيل على حجم المدخلات $n$ فقط، بل على تفاصيل المدخلات نفسها.
الحالة الأسوأ (Worst-case): أطول وقت تشغيل ممكن لمدخلات بحجم $n$.
الحالة الأفضل (Best-case): أسرع وقت تشغيل ممكن.
الحالة المتوسطة (Average-case): الكفاءة المتوقعة لمدخلات عشوائية، وتتطلب افتراضات احتمالية حول المدخلات.
For some algorithms (like Sequential Search), running time depends not just on input size $n$, but on the specifics of the input.
Worst-case: The longest running time for any input of size $n$.
Best-case: The fastest running time.
Average-case: The expected efficiency for random inputs, requiring probabilistic assumptions about the inputs.
الحالة المتوسطة ليست ببساطة المتوسط الحسابي بين الحالة الأفضل والأسوأ. لحسابها، يجب معرفة التوزيع الاحتمالي للمدخلات.
كما يوجد مفهوم الكفاءة المطفأة (Amortized Efficiency) والذي يطبق على سلسلة من العمليات على بنية بيانات، حيث يتم توزيع التكلفة العالية لعملية واحدة في الحالة الأسوأ على السلسلة بأكملها.
The average case is not simply the arithmetic mean of the best and worst cases. To calculate it, one must know the probability distribution of the inputs.
There is also Amortized Efficiency, which applies to a sequence of operations on a data structure, spreading the high cost of a single worst-case operation over the entire sequence.
| Worst-case | Best-case | Average-case | |
|---|---|---|---|
| التعريفDefinition | أطول وقت تشغيل لمدخل بحجم nLongest running time for input size n | أقصر وقت تشغيل لمدخل بحجم nShortest running time for input size n | الوقت المتوقع لمدخلات عشوائيةExpected time for random inputs |
في خوارزمية البحث الخطي، متى تحدث الحالة الأفضل والحالة الأسوأ؟ In Sequential Search, when do the best-case and worst-case occur?
الحالة الأفضل تحدث إذا كان العنصر المطلوب هو الأول في القائمة. الحالة الأسوأ تحدث إذا كان العنصر غير موجود أو موجود في نهاية القائمة.
Best-case occurs if the target element is the first in the list. Worst-case occurs if the element is not found or is at the very end of the list.
3 الرموز التقاربية
3 Asymptotic Notations
لغة رياضية لوصف رتبة نمو الخوارزميات عندما يؤول حجم المدخلات إلى المالانهاية (Big-O, Big-Omega, Big-Theta).
A mathematical language to describe the order of growth of algorithms as input size approaches infinity (Big-O, Big-Omega, Big-Theta).
تستخدم الرموز التقاربية لمقارنة رتب النمو:
- $O$ (Big-O): يمثل الحد الأعلى التقاربي (Asymptotic upper bound). الدالة $t(n) \in O(g(n))$ إذا كانت محصورة من الأعلى بمضاعف ثابت لـ $g(n)$. مفيد لتحليل الحالة الأسوأ.
- $\Omega$ (Big-Omega): يمثل الحد الأدنى التقاربي (Asymptotic lower bound). مفيد لتحليل الحالة الأفضل.
- $\Theta$ (Big-Theta): يمثل الحد المحكم التقاربي (Asymptotic tight bound). الدالة محصورة من الأعلى والأسفل. مفيد لتحليل الحالة المتوسطة أو عندما تتطابق الحالة الأسوأ والأفضل.
Asymptotic notations are used to compare orders of growth:
- $O$ (Big-O): Asymptotic upper bound. $t(n) \in O(g(n))$ if bounded above by a constant multiple of $g(n)$. Useful for worst-case analysis.
- $\Omega$ (Big-Omega): Asymptotic lower bound. Useful for best-case analysis.
- $\Theta$ (Big-Theta): Asymptotic tight bound. The function is bounded both above and below. Useful for average-case or when worst and best cases match.
التعريف الرياضي الدقيق لـ Big-O هو: يوجد ثابت موجب $c$ وعدد صحيح غير سالب $n_0$ بحيث أن $t(n) \le c \cdot g(n)$ لجميع $n \ge n_0$.
هذا يعني أننا نتجاهل الثوابت والحدود ذات الرتب الأقل لأن تأثيرها يتضاءل مع القيم الكبيرة جداً لـ $n$.
The formal definition of Big-O is: there exist positive constant $c$ and non-negative integer $n_0$ such that $t(n) \le c \cdot g(n)$ for all $n \ge n_0$.
This means we ignore constants and lower-order terms because their impact diminishes for very large values of $n$.
| Big-O (O) | Big-Omega (Ω) | Big-Theta (Θ) | |
|---|---|---|---|
| نوع الحدBound Type | حد أعلى (Upper Bound)Upper Bound | حد أدنى (Lower Bound)Lower Bound | حد محكم (Tight Bound)Tight Bound |
| الاستخدام الشائعCommon Usage | تحليل الحالة الأسوأWorst-case analysis | تحليل الحالة الأفضلBest-case analysis | تحليل الحالة المتوسطة / الدقيقةAverage-case / Exact analysis |
هل يمكن القول أن خوارزمية بوقت تشغيل $100n + 5$ تنتمي إلى $O(n^2)$؟ ولماذا؟ Can we say that an algorithm with running time $100n + 5$ belongs to $O(n^2)$? Why?
نعم، رياضياً $100n + 5 \in O(n^2)$ لأن $O$ يمثل حداً أعلى (Loose bound). ومع ذلك، الوصف الأدق والأكثر إحكاماً هو $O(n)$ أو $\Theta(n)$.
Yes, mathematically $100n + 5 \in O(n^2)$ because $O$ represents an upper bound (loose bound). However, the more precise and tight description is $O(n)$ or $\Theta(n)$.
4 التحليل الرياضي للخوارزميات غير التكرارية
4 Mathematical Analysis for Non-recursive Algorithms
تحليل يعتمد على إعداد مجاميع (Sums) لعدد مرات تنفيذ العملية الأساسية داخل الحلقات التكرارية (Loops).
Analysis based on setting up sums for the number of times the basic operation is executed inside loops.
خطة التحليل:
- تحديد حجم المدخلات.
- تحديد العملية الأساسية (غالباً في الحلقة الأعمق).
- التحقق مما إذا كان عدد مرات التنفيذ يعتمد فقط على حجم المدخلات أم يتطلب فصل الحالات (أسوأ، أفضل).
- إعداد مجموع (Sum) يعبر عن عدد مرات تنفيذ العملية الأساسية.
- استخدام قوانين المجاميع القياسية لإيجاد صيغة مغلقة (Closed form) أو رتبة النمو.
Analysis Plan:
- Decide on input size parameter.
- Identify the basic operation (innermost loop).
- Check if execution count depends only on input size or needs case separation (worst, best).
- Set up a sum expressing the basic operation execution count.
- Use standard sum formulas to find a closed form or order of growth.
في خوارزمية فحص تفرد العناصر (UniqueElements)، الحلقة الخارجية تعمل من $0$ إلى $n-2$، والحلقة الداخلية من $i+1$ إلى $n-1$.
المجموع الناتج هو $\sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1$.
بحل هذا المجموع نحصل على $\frac{(n-1)n}{2}$، مما يثبت أن الخوارزمية تنتمي إلى $\Theta(n^2)$.
In the UniqueElements algorithm, the outer loop runs from $0$ to $n-2$, and the inner loop from $i+1$ to $n-1$.
The resulting sum is $\sum_{i=0}^{n-2} \sum_{j=i+1}^{n-1} 1$.
Solving this yields $\frac{(n-1)n}{2}$, proving the algorithm is in $\Theta(n^2)$.
لماذا نركز على الحلقة الأعمق (Innermost loop) عند تحديد العملية الأساسية؟ Why do we focus on the innermost loop when identifying the basic operation?
لأن العملية الموجودة في الحلقة الأعمق هي التي يتم تنفيذها أكبر عدد من المرات، وبالتالي هي التي تهيمن على وقت التشغيل الكلي للخوارزمية.
Because the operation in the innermost loop is executed the most number of times, thus dominating the overall running time of the algorithm.
5 التحليل الرياضي للخوارزميات التكرارية
5 Mathematical Analysis for Recursive Algorithms
تحليل يعتمد على إعداد علاقات تكرار (Recurrence Relations) وحلها باستخدام طرق مثل التعويض العكسي (Backward Substitution).
Analysis based on setting up Recurrence Relations and solving them using methods like Backward Substitution.
خطة التحليل:
- تحديد حجم المدخلات.
- تحديد العملية الأساسية.
- التحقق من الحالات (أسوأ، أفضل).
- إعداد علاقة تكرار (Recurrence relation) مع شرط ابتدائي (Initial condition) لعدد مرات تنفيذ العملية الأساسية.
- حل علاقة التكرار لتحديد رتبة النمو. طريقة التعويض العكسي هي إحدى الطرق الشائعة لحل هذه العلاقات.
Analysis Plan:
- Decide on input size.
- Identify basic operation.
- Check cases (worst, best).
- Set up a recurrence relation with an initial condition for the basic operation count.
- Solve the recurrence to ascertain the order of growth. The method of backward substitutions is a common way to solve these.
مثال حساب المضروب (Factorial): دالة $F(n)$ تستدعي $F(n-1)$. العملية الأساسية هي الضرب.
علاقة التكرار هي $M(n) = M(n-1) + 1$ لـ $n > 0$، والشرط الابتدائي $M(0) = 0$.
باستخدام التعويض العكسي: $M(n) = M(n-2) + 2 = ... = M(n-i) + i$.
عندما $i = n$، نحصل على $M(0) + n = n$. إذن التعقيد هو $O(n)$.
Factorial example: $F(n)$ calls $F(n-1)$. Basic operation is multiplication.
Recurrence relation is $M(n) = M(n-1) + 1$ for $n > 0$, initial condition $M(0) = 0$.
Using backward substitution: $M(n) = M(n-2) + 2 = ... = M(n-i) + i$.
When $i = n$, we get $M(0) + n = n$. Thus, complexity is $O(n)$.
كيف نحدد الشرط الابتدائي (Initial condition) لعلاقة التكرار؟ How do we determine the initial condition for a recurrence relation?
من خلال فحص شرط التوقف (Base case) في الكود التكراري ومعرفة عدد مرات تنفيذ العملية الأساسية عنده (غالباً صفر أو واحد).
By inspecting the base case (stopping condition) in the recursive code and determining the number of times the basic operation is executed there (often zero or one).
6 التحليل التجريبي للخوارزميات
6 Empirical Analysis of Algorithm
بديل للتحليل الرياضي يتم من خلال تشغيل الخوارزمية فعلياً على عينات بيانات وقياس الأداء.
An alternative to mathematical analysis performed by actually running the algorithm on sample data and measuring performance.
يُستخدم التحليل التجريبي عندما يكون التحليل الرياضي صعباً أو معقداً. الخطة العامة:
- فهم هدف التجربة.
- تحديد مقياس الكفاءة (عدد العمليات أو وقت التشغيل الفعلي).
- تحديد خصائص عينة المدخلات (النطاق، الحجم).
- كتابة برنامج ينفذ الخوارزمية.
- توليد عينة من المدخلات (غالباً أرقام عشوائية).
- تشغيل الخوارزمية وتسجيل البيانات.
- تحليل البيانات الناتجة.
Empirical analysis is used when mathematical analysis is difficult. General Plan:
- Understand experiment purpose.
- Decide efficiency metric (operation count vs. physical time).
- Decide input sample characteristics (range, size).
- Prepare program implementing the algorithm.
- Generate input sample (often pseudorandom numbers).
- Run algorithm and record data.
- Analyze obtained data.
رغم فائدة التحليل التجريبي، إلا أنه يمتلك عيوباً مقارنة بالتحليل النظري، حيث أن النتائج قد تتأثر ببيئة التشغيل (Hardware/Compiler) ولا تعطي إثباتاً رياضياً قاطعاً لسلوك الخوارزمية عند أحجام مدخلات تقترب من المالانهاية.
Despite its usefulness, empirical analysis has drawbacks compared to theoretical analysis.
Results can be affected by the execution environment (Hardware/Compiler) and do not provide a definitive mathematical proof of the algorithm's behavior as input sizes approach infinity.
متى نفضل التحليل التجريبي على التحليل النظري (الرياضي)؟ When do we prefer empirical analysis over theoretical (mathematical) analysis?
عندما يكون التحليل الرياضي معقداً جداً، أو عندما نريد قياس الأداء الفعلي للخوارزمية على بيئة تشغيل محددة أو مع بيانات واقعية معينة.
When mathematical analysis is too complex, or when we want to measure the actual performance of the algorithm on a specific execution environment or with specific real-world data.