Algorithms & Complexity

الفصل الثاني: الخوارزميات وتعقيدها الحسابي

الهدف: كتابة Pseudocode، البحث والترتيب، وفهم الـ Big-O رياضياً.
1

What is an Algorithm؟

ليست أي خطوات تسمى "خوارزمية". يجب أن تتوفر فيها 7 شروط :

Input لها مدخلات.
Output تنتج مخرجات.
Definiteness الخطوات واضحة بدقة.
Correctness تعطي الناتج الصحيح.
Finiteness تنتهي بعد عدد محدود من الخطوات.
Effectiveness كل خطوة يمكن تنفيذها.
Generality تعمل على أي مدخلات من نفس النوع.
2

Searching Algorithms

Linear Search (البحث الخطي)

ابحث عن العنصر $x$ بالمرور على القائمة واحداً تلو الآخر.

For i = 1 to n:
  If a[i] == x then return i
Return "Not Found"
Complexity: $O(n)$

Binary Search (البحث الثنائي)

اقسم القائمة لنصفين في كل مرة. (يشرط أن تكون القائمة مرتبة!).

While i <= j:
  m = (i+j)/2
  If x > a[m] then i = m+1
  Else j = m-1
Complexity: $O(\log n)$
3

Sorting Algorithms

Bubble Sort (ترتيب الفقاعة)

قارن كل عنصرين متجاورين وبدل بينهما إذا كانا في ترتيب خاطئ. كرر العملية $n$ مرة.
التعقيد: $O(n^2)$. (بطيء جداً).

Insertion Sort (الترتيب بالإدراج)

ابدأ بالعنصر الثاني، وقارنه بما قبله وضعه في مكانه الصحيح.
التعقيد: $O(n^2)$ (أسوأ حالة)، ولكنه سريع إذا كانت القائمة شبه مرتبة.

4

Growth of Functions

Big-O ($O$)

Upper Bound (أسوأ حالة)

$f(x) \le C \cdot g(x)$
for $x > k$

Big-Omega ($\Omega$)

Lower Bound (أفضل حالة)

$f(x) \ge C \cdot g(x)$
for $x > k$

Big-Theta ($\Theta$)

Tight Bound (بالضبط)

$C_1 g(x) \le f(x) \le C_2 g(x)$

Hierarchy of Complexity

$1$ < $\log n$ < $n$ < $n \log n$ < $n^2$ < $2^n$ < $n!$
🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / شرط هام

Binary Search Input

هل يعمل البحث الثنائي على أي قائمة؟
لا! يجب أن تكون القائمة مرتبة (Sorted) أولاً.
إذا لم تكن مرتبة، يجب ترتيبها أولاً (وهذا يكلف وقتاً) أو استخدام Linear Search.

PROOF / إثبات

Showing $x^2 + 2x + 1$ is $O(x^2)$

We need $C, k$ such that $x^2 + 2x + 1 \le C x^2$.
Let $k=1$. Since $x \ge 1$:
$x^2 + 2x + 1 \le x^2 + 2x^2 + x^2 = 4x^2$.
So, $C=4, k=1$. Done!

→ السابق (Ch 1) الفصل التالي (Ch 3) ←