Space and Time Trade-Offs مقايضات المساحة والوقت (Trade-Offs)

Spending memory to save time. We preprocess inputs or use extra structures to accelerate algorithms from brute force to blazing fast. إنفاق الذاكرة لتوفير الوقت. نقوم بمعالجة المدخلات مسبقاً أو استخدام هياكل إضافية لتسريع الخوارزميات من القوة الغاشمة إلى سرعة فائقة.

Input Enhancement Input Enhancement Prestructuring Prestructuring Distribution Counting Distribution Counting Horspool's Algorithm Horspool's Algorithm

Strategies for Trading Space استراتيجيات مقايضة المساحة

1. Input Enhancement 1. Input Enhancement (تحسين المدخلات)

Preprocess the problem's input (in whole or part) and store additional info to use later. معالجة مدخلات المشكلة مسبقاً (كلياً أو جزئياً) وتخزين معلومات إضافية لاستخدامها لاحقاً.

  • Counting Sorts Counting Sorts
  • String Searching (Horspool, Boyer-Moore) String Searching (Horspool, Boyer-Moore)

2. Prestructuring 2. Prestructuring (إعادة الهيكلة المسبقة)

Process the input to build a data structure that makes accessing elements easier or faster. معالجة المدخلات لبناء هيكل بيانات يجعل الوصول للعناصر أسهل أو أسرع.

  • Hashing Hashing
  • Indexing Schemes (B-Trees) أنظمة الفهرسة (B-Trees)

Sorting by Counting الفرز بالعد (Sorting by Counting)

Method A: Comparison-Counting Sort الطريقة أ: Comparison-Counting Sort

For each element $A[i]$, count how many elements are smaller than it. This count is its exact position in the sorted array . لكل عنصر $A[i]$، احسب كم عنصراً أصغر منه. هذا العدد هو موضعه الدقيق في المصفوفة المرتبة.

for i $\leftarrow$ 0 to n-2 do
  for j $\leftarrow$ i+1 to n-1 do
    if A[i] < A[j]
      Count[j] $\leftarrow$ Count[j] + 1
    else Count[i] $\leftarrow$ Count[i] + 1
// Copy to Result Array S
for i $\leftarrow$ 0 to n-1 do S[Count[i]] $\leftarrow$ A[i]

Complexity التعقيد

$O(n^2)$

No improvement over simple sorts. لا تحسن عن الفرز البسيط.

Method B: Distribution Counting Sort الطريقة ب: Distribution Counting Sort

Assume elements come from a small set of integers between $l$ and $u$. We compute frequencies, then cumulative frequencies (distribution), to calculate positions directly . افترض أن العناصر تأتي من مجموعة صغيرة من الأعداد الصحيحة بين $l$ و $u$. نحسب الترددات، ثم الترددات التراكمية (التوزيع)، لحساب المواقع مباشرة.

1 Compute Frequencies ($F$). حساب الترددات ($F$).
2 Compute Distribution ($D$): $D[j] = D[j-1] + F[j]$. حساب التوزيع ($D$): $D[j] = D[j-1] + F[j]$.
3 Place elements: $S[D[A[i]-l]-1] = A[i]$. وضع العناصر: $S[D[A[i]-l]-1] = A[i]$.

Complexity التعقيد

$O(n)$

Linear time! (If range is small) وقت خطي! (إذا كان المدى صغيراً)

String Matching مطابقة النصوص (String Matching)

Brute force string matching takes $O(nm)$. We can do better by Preprocessing the pattern to know how much to shift when a mismatch occurs. مطابقة النصوص بالقوة الغاشمة تستغرق $O(nm)$. يمكننا التحسين عن طريق Preprocessing للنمط لمعرفة مقدار الإزاحة عند حدوث عدم تطابق.

Horspool's Algorithm Horspool's Algorithm

A simplified version of Boyer-Moore. It compares the pattern from Right-to-Left. If a mismatch occurs, it determines the shift size based on the character in the text aligned with the last character of the pattern. نسخة مبسطة من Boyer-Moore. تقارن النمط من اليمين لليسار. إذا حدث عدم تطابق، تحدد حجم الإزاحة بناءً على الحرف الموجود في النص المحاذي لآخر حرف في النمط.

Text: Text: ... B A R B E R ...
Pattern: Pattern: L E A D E R

Logic: Look at 'B' in Text (aligned with Pattern's end). 'B' is not in Pattern? Shift full length! المنطق: انظر إلى 'B' في النص (بمحاذاة نهاية النمط). 'B' ليست في النمط؟ قم بإزاحة كامل الطول!

The Shift Table Construction بناء جدول الإزاحة (Shift Table)

For each character $c$ in the alphabet: لكل حرف $c$ في الأبجدية:

  • If $c$ is NOT in the pattern: Shift by pattern length $m$. إذا كان $c$ ليس في النمط: إزاحة بطول النمط $m$.
  • If $c$ IS in the pattern: Shift by distance from right end ($m - 1 - k$). إذا كان $c$ في النمط: إزاحة بالمسافة من الطرف الأيمن ($m - 1 - k$).
  • Note: Only consider the last occurrence of $c$ (excluding the very last character itself for calculation purposes) . ملاحظة: خذ بعين الاعتبار فقط آخر ظهور لـ $c$ (باستثناء الحرف الأخير نفسه لأغراض الحساب).

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

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

TRAP: Distribution Sort Range فخ: نطاق Distribution Sort

"Is Distribution Counting Sort always linear $O(n)$?"
NO! It depends on the range of values ($k$). The complexity is actually $O(n + k)$. If $k \approx n^2$, the algorithm becomes $O(n^2)$, which is worse than Mergesort. "هل Distribution Counting Sort دائماً خطي $O(n)$؟"
لا! يعتمد ذلك على نطاق القيم ($k$). التعقيد الفعلي هو $O(n + k)$. إذا كان $k \approx n^2$، تصبح الخوارزمية $O(n^2)$، وهو أسوأ من Mergesort.

TRAP: Horspool's Lookup فخ: بحث Horspool

When a mismatch occurs in Horspool, which character do you look up in the Shift Table?
NOT the mismatched character. You look at the character in the TEXT that is aligned with the LAST character of the pattern. عند حدوث عدم تطابق في Horspool، أي حرف تبحث عنه في جدول الإزاحة؟
ليس الحرف غير المتطابق. تنظر إلى الحرف في النص (TEXT) المحاذي للحرف الأخير في النمط.

SECRET: Comparison Counting سر: Comparison Counting

Professors teach Comparison-Counting Sort ($O(n^2)$) not because it's useful (it's not), but to prove that simply throwing "extra space" at a problem doesn't automatically solve "time" efficiency. You need the right strategy (like Distribution Counting). يدرس الأساتذة Comparison-Counting Sort ($O(n^2)$) ليس لأنه مفيد (هو ليس كذلك)، ولكن لإثبات أن مجرد إضافة "مساحة إضافية" لمشكلة لا يحل تلقائياً كفاءة "الوقت". تحتاج إلى الاستراتيجية الصحيحة (مثل Distribution Counting).

KEY CONCEPT: Worst Case Horspool مفهوم مفتاحي: أسوأ حالة Horspool

Despite being very fast on average ($O(n)$), Horspool's (and Boyer-Moore's) worst case is still $O(nm)$, just like Brute Force. This happens with patterns like "AAAAA" in text "AAAAAAAA". على الرغم من كونها سريعة جداً في المتوسط ($O(n)$)، فإن أسوأ حالة لـ Horspool (و Boyer-Moore) لا تزال $O(nm)$، تماماً مثل القوة الغاشمة. يحدث هذا مع أنماط مثل "AAAAA" في نص "AAAAAAAA".