Brute Force & Exhaustive Search القوة الغاشمة و البحث الشامل (Exhaustive Search)
The "Just Do It" strategy. Simple, direct, and capable of solving small-scale instances through sheer computational power. استراتيجية "فقط افعلها". بسيطة ومباشرة وقادرة على حل المشكلات صغيرة الحجم من خلال القوة الحسابية البحتة.
What is Brute Force? ما هي القوة الغاشمة (Brute Force)؟
Brute Force is a straightforward approach based directly on the problem statement and definitions. It is the easiest strategy to apply ("Just do it"). While generally inefficient ($O(n^2)$ or worse), it is extremely useful for verifying solutions or solving small-size problems . Brute Force هي نهج مباشر يعتمد كلياً على بيان المشكلة والتعريفات. إنها الاستراتيجية الأسهل للتطبيق ("فقط افعلها"). على الرغم من أنها غير فعالة بشكل عام ($O(n^2)$ أو أسوأ)، إلا أنها مفيدة للغاية للتحقق من الحلول أو حل المشاكل صغيرة الحجم.
Sorting Titans: The $O(n^2)$ Club عمالقة الفرز: نادي الـ $O(n^2)$
Selection Sort Selection Sort
Scans the entire list to find the smallest element and swaps it with the first position. Then repeats for the rest of the list . يقوم بمسح القائمة بأكملها للعثور على أصغر عنصر وتبديله مع المركز الأول. ثم يكرر العملية لبقية القائمة.
min $\leftarrow$ i
for j $\leftarrow$ i+1 to n-1 do
if A[j] < A[min] min $\leftarrow$ j
swap A[i], A[min]
Bubble Sort Bubble Sort
Compares adjacent elements and swaps them if they are out of order. This "bubbles up" the largest element to the end . يقارن العناصر المتجاورة ويبدلها إذا كانت خارج الترتيب. هذا يجعل العنصر الأكبر "يطفو" (Bubbles up) إلى النهاية.
for j $\leftarrow$ 0 to n-2-i do
if A[j+1] < A[j]
swap A[j], A[j+1]
Searching & Strings البحث والنصوص (Searching & Strings)
Sequential Search & The Sentinel Trick Sequential Search و خدعة الـ Sentinel
Linear scan. Standard enhancement: Append the search key $K$ to the end of the list ($A[n] \leftarrow K$). This acts as a Sentinel, eliminating the need to check `if i < n` inside the loop loop . مسح خطي (Linear scan). التحسين القياسي: إلحاق مفتاح البحث $K$ بنهاية القائمة ($A[n] \leftarrow K$). يعمل هذا كـ Sentinel، مما يلغي الحاجة للتحقق من `if i < n` داخل الحلقة.
Brute-Force String Matching مطابقة النصوص بالقوة الغاشمة
Worst: O(nm) الأسوأ: O(nm)Align pattern $P$ at every possible position in Text $T$ and check for a match. محاذاة النمط $P$ عند كل موضع ممكن في النص $T$ والتحقق من التطابق.
Most shifts fail after 1 comparison. Average efficiency is actually Linear $O(n)$ . معظم التحولات تفشل بعد مقارنة واحدة. الكفاءة المتوسطة هي في الواقع خطية $O(n)$.
Exhaustive Search البحث الشامل (Exhaustive Search)
Used for Combinatorial Problems. It generates every possible element in the domain (permutations or subsets) to find the optimum . تستخدم لـ Combinatorial Problems. تولد كل عنصر ممكن في المجال (التباديل أو المجموعات الفرعية) للعثور على الأمثل.
Traveling Salesman (TSP) Traveling Salesman (TSP)
Find shortest tour visiting all $n$ cities. إيجاد أقصر جولة تزور جميع المدن الـ $n$.
- Modeled as Hamiltonian Circuit.تنمذج كدائرة هاملتونيان (Hamiltonian Circuit).
- Requires generating $(n-1)!$ permutations.تتطلب توليد $(n-1)!$ تباديل.
- Impractical for large $n$ .غير عملية للـ $n$ الكبيرة.
Knapsack Problem مشكلة حقيبة الظهر (Knapsack)
Find most valuable subset fitting in capacity $W$. إيجاد المجموعة الفرعية الأكثر قيمة التي تناسب السعة $W$.
- Requires generating all $2^n$ subsets.تتطلب توليد جميع المجموعات الفرعية $2^n$.
- Check feasibility (Weight $\le W$).التحقق من الجدوى (الوزن $\le W$).
- Pick Max Value .اختر القيمة القصوى.
Assignment Problem مشكلة التعيين (Assignment)
Assign $n$ people to $n$ jobs for min cost. تعيين $n$ أشخاص لـ $n$ وظائف بأقل تكلفة.
- One-to-one correspondence.تطابق واحد لواحد.
- Requires $n!$ permutations.تتطلب $n!$ تباديل.
- Sum costs, find min .جمع التكاليف، إيجاد الأقل.
Graph Traversals اجتياز الرسم البياني (Graph Traversals)
| Feature الميزة | DFS (Depth-First) DFS (العمق أولاً) | BFS (Breadth-First) BFS (العرض أولاً) |
|---|---|---|
| Data Structure هيكل البيانات | Stack (LIFO) / Recursion Stack (LIFO) / Recursion | Queue (FIFO) Queue (FIFO) |
| Movement الحركة | Dives deep, backtracks at dead ends. يغوص عميقاً، يتراجع (backtracks) عند النهايات المسدودة. | Concentric waves (visit neighbors first). موجات متحدة المركز (يزور الجيران أولاً). |
| Complexity (Matrix) التعقيد (Matrix) | $O(|V|^2)$ | $O(|V|^2)$ |
| Complexity (List) التعقيد (List) | $O(|V|+|E|)$ | $O(|V|+|E|)$ |
The Exam Vault خزنة الاختبار
Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ
TRAP: Knapsack Efficiency فخ: كفاءة Knapsack
Never say Knapsack exhaustive search is $O(n)$. It requires generating all subsets, which is $2^n$ (Exponential). Even for small $n$, this grows incredibly fast. It is $O(2^n)$. لا تقل أبداً أن البحث الشامل لـ Knapsack هو $O(n)$. يتطلب توليد جميع المجموعات الفرعية، وهو $2^n$ (أسي). حتى بالنسبة لـ $n$ الصغيرة، ينمو هذا بسرعة مذهلة. إنه $O(2^n)$.
TRAP: DFS/BFS Complexity فخ: تعقيد DFS/BFS
If asked "What is the complexity of DFS?", do not give a single answer. You MUST specify the representation: $O(|V|^2)$ for Adjacency Matrix, but $O(|V|+|E|)$ for Adjacency List. Missing this distinction loses points . إذا سُئلت "ما هو تعقيد DFS؟"، لا تعطِ إجابة واحدة. يجب عليك تحديد التمثيل: $O(|V|^2)$ لـ Adjacency Matrix، ولكن $O(|V|+|E|)$ لـ Adjacency List. عدم ذكر هذا التمييز يضيع الدرجات.
SECRET: The Sentinel سر: الحارس (The Sentinel)
In Sequential Search, appending the key to the end of the array is not just a coding trick; it's a formal algorithmic enhancement that removes the `i < n` check from the loop, technically halving the overhead per iteration . في البحث المتسلسل (Sequential Search)، إلحاق المفتاح بنهاية المصفوفة ليس مجرد خدعة برمجية؛ إنه تحسين خوارزمي رسمي يزيل التحقق من `i < n` من الحلقة، مما يقلل تقنياً من الحمل الزائد لكل تكرار بمقدار النصف.
KEY CONCEPT: Selection vs Bubble مفهوم مفتاحي: Selection مقابل Bubble
Both are $O(n^2)$, but Selection Sort is usually preferred because it performs fewer swaps ($O(n)$ swaps vs $O(n^2)$ swaps in Bubble Sort). Memorize this nuance. كلاهما $O(n^2)$، لكن Selection Sort يفضل عادةً لأنه ينفذ عدد أقل من التبديلات (swaps) ($O(n)$ تبديلات مقابل $O(n^2)$ في Bubble Sort). احفظ هذا الفارق الدقيق.