📏 المصفوفات وتعقيد الوقت دائماً في الأسئلة الاختيارية
كل امتحان نهائي يحتوي على أسئلة قليلة على الأقل تسأل عن تعقيد وقت العمليات (إدراج، حذف، بحث) على المصفوفات، القوائم، المكدسات، الطوابير، الأشجار، الترتيب، إلخ.
جدول مرجعي سريع لـ Big-O
| العملية / الخوارزمية | أفضل | متوسط | أسوأ | ملاحظات / مفتاح الأسئلة |
|---|---|---|---|---|
| الوصول في المصفوفة (A[i]) | O(1) | O(1) | O(1) | وصول مباشر بالفهرس → وقت ثابت |
| البحث في مصفوفة غير مرتبة | O(1) | O(n) | O(n) | "بحث خطي"، "بدون ترتيب"، "مسح كل العناصر" |
| البحث الثنائي (مصفوفة مرتبة) | O(1) | O(log n) | O(log n) | "مرتبة"، "الوسط"، "نصف كل خطوة" |
| إدراج في النهاية (سعة كافية) | O(1) | O(1) | O(1) | فقط ضع في A[الحجم] |
| إدراج في البداية / الوسط | O(n) | O(n) | O(n) | يحتاج نقل العناصر |
| حذف من البداية / الوسط | O(n) | O(n) | O(n) | نقل لملء الفراغ |
في عدة امتحانات سابقة، يعطونك جزء كود يتكرر على مصفوفة بـ:
✅ التعقيد = O(n)
إذا كان هناك حلقات
✅ التعقيد = O(n²) (شائع جداً في الأسئلة الاختيارية).
for (int i = 0; i < n; i++) ...✅ التعقيد = O(n)
إذا كان هناك حلقات
for متداخلة:for i in 0..n
for j in 0..n✅ التعقيد = O(n²) (شائع جداً في الأسئلة الاختيارية).
كيف تجيب على أسئلة التعقيد
- تجاهل الثوابت: 2n + 5 → O(n)
- اختر الحد الأسرع نمواً: n² + 100n → O(n²)
- الحلقات التي تعمل
nمرة → O(n) - الحلقات المتداخلة → اضرب: خارجية n، داخلية n → O(n²)
- فرق تسد (بحث ثنائي، أفضل/متوسط الفرز السريع) → O(n log n) أو O(log n)
إذا رأيت "اقسم المشكلة للنصف كل خطوة" → فكر في log n.
إذا رأيت "حلقات متداخلة مزدوجة على نفس النطاق" → فكر في n².
🔗 القوائم المرتبطة
قائمة مرتبطة أحادية مقابل ثنائية
قائمة مرتبطة أحادية
- كل عقدة:
data,next - يمكن التحرك للأمام فقط
- ذاكرة أقل
- إدراج/حذف في الرأس → O(1)
قائمة مرتبطة ثنائية
- كل عقدة:
data,next,prev - تحرك للأمام والخلف
- ذاكرة أكثر
- إدراج/حذف في الذيل مع مؤشر الذيل → O(1)
عمليات شائعة في الامتحان
| العملية | قائمة مرتبطة أحادية | قائمة مرتبطة ثنائية | التعقيد |
|---|---|---|---|
| إدراج في الرأس | تغيير مؤشر الرأس | تغيير الرأس والسابق | O(1) |
| إدراج في الذيل (بدون مؤشر ذيل) | اجتياز القائمة كاملة | اجتياز القائمة كاملة | O(n) |
| إدراج في الذيل (مع مؤشر ذيل) | ليس بسيطاً | سهل باستخدام الذيل | O(1) |
| بحث بالقيمة | اجتياز باتجاه واحد | اجتياز في أي اتجاه | O(n) |
| حذف بمفتاح معطى | يحتاج مؤشر سابق أو التعامل مع الرأس | استخدم prev و next |
O(n) |
سؤال شائع جداً من امتحانات سابقة:
سؤال: أي هيكل بيانات أفضل للإدراج/الحذف في وسط قائمة كبيرة عندما لديك مؤشر للعقدة مسبقاً؟
✅ الإجابة: قائمة مرتبطة (O(1) لضبط المؤشرات) مقابل المصفوفة (O(n) لنقل العناصر).
سؤال: أي هيكل بيانات أفضل للإدراج/الحذف في وسط قائمة كبيرة عندما لديك مؤشر للعقدة مسبقاً؟
✅ الإجابة: قائمة مرتبطة (O(1) لضبط المؤشرات) مقابل المصفوفة (O(n) لنقل العناصر).
سؤال مؤشر نموذجي
Node *p = head;
while (p != nullptr) {
p = p->next;
}
🧠 هذه الحلقة ببساطة تجتاز القائمة وتتوقف عند nullptr. التعقيد: O(n).
ارسم دائماً 3 صناديق:
prev, curr, next عندما تكون غير متأكد من تحديثات المؤشر في أسئلة الحذف/الإدراج.
📚 المكدسات والطوابير
المفاهيم وحالات الاستخدام
المكدس (LIFO)
- آخر داخل أول خارج
- العمليات:
push,pop,top - يستخدم لـ:
- استدعاءات الدوال (مكدس الاستدعاء)
- تقييم العبارات (لاحق)
- عمليات التراجع
الطابور (FIFO)
- أول داخل أول خارج
- العمليات:
enqueue,dequeue,front - يستخدم لـ:
- بحث بالعرض أولاً
- جدولة المهام
- التخزين المؤقت (الطابعات، الشبكات)
تنفيذ المصفوفة مقابل القائمة المرتبطة
| هيكل البيانات | تنفيذ المصفوفة | تنفيذ القائمة المرتبطة |
|---|---|---|
| المكدس |
استخدم مؤشر أعلىpush: A[++top] = x;pop: return A[top--];فيضان إذا كان top = حجم-1 |
ادفع/اسحب من رأس القائمة لا يوجد حد ثابت للحجم ذاكرة أكثر قليلاً (مؤشرات) |
| الطابور |
استخدم front, rearطابور دائري لإعادة استخدام المساحة خدعة امتحان شائعة: "ممتلئ" حتى لو بعض الخلايا فارغة |
أضف للطابور في الذيل، احذف من المقدمة فعال إذا حافظت على كلا المؤشرين |
سؤال تتبع بأسلوب الامتحان النهائي:
معطى: ابدأ بمكدس فارغ. نفذ:
حالة المكدس من الأعلى → الأسفل:
بعد push(1) → [1]
بعد push(2) → [2, 1]
بعد push(3) → [3, 2, 1]
بعد pop() → [2, 1]
بعد push(4) → [4, 2, 1]
معطى: ابدأ بمكدس فارغ. نفذ:
push(1), push(2), push(3), pop(), push(4)حالة المكدس من الأعلى → الأسفل:
بعد push(1) → [1]
بعد push(2) → [2, 1]
بعد push(3) → [3, 2, 1]
بعد pop() → [2, 1]
بعد push(4) → [4, 2, 1]
لتقييم العبارات اللاحقة، اقرأ دائماً من اليسار لليمين واستخدم مكدساً. عندما ترى معاملاً، اسحب آخر معاملين، احسب، ثم ادفع النتيجة.
🌳 الأشجار وأشجار البحث الثنائية (BST)
كل امتحان نهائي حديث يتضمن: بناء شجرة بحث ثنائية من تسلسل، إيجاد الارتفاع، عد العقد، أو إعطاء أوامر الاجتياز (مسبق/بالترتيب/لاحق، بالمستوى).
تعريفات أساسية
- ارتفاع الشجرة: عدد الحواف في أطول مسار من الجذر لورقة (أحياناً يعرف بعدد العقد – تحقق من شرائحك؛ جامعة ولاية بنسلفانيا عادة تستخدم الحواف).
- عمق العقدة: عدد الحواف من الجذر لتلك العقدة.
- الورقة: عقدة بدون أبناء.
- شجرة ثنائية كاملة: كل عقدة لها 0 أو 2 أبناء.
- شجرة ثنائية تامة: كل المستويات ممتلئة ما عدا الأخير ربما؛ الأخير يملأ من اليسار لليمين.
خاصية شجرة البحث الثنائية
لكل عقدة X: جميع المفاتيح في الشجرة الفرعية اليسرى < X.key وجميع المفاتيح في الشجرة الفرعية اليمنى > X.key
أوامر الاجتياز
| الاجتياز | الترتيب | الاستخدام |
|---|---|---|
| ما قبل الترتيب | جذر – يسار – يمين | نسخ الشجرة، التعبير البادئ |
| بالترتيب | يسار – جذر – يمين | يعطي ترتيباً مصفى في شجرة البحث الثنائية |
| ما بعد الترتيب | يسار – يمين – جذر | حذف الشجرة، التعبير اللاحق |
| بالمستوى | BFS بالمستوى باستخدام طابور | أقصر مسار في شجرة غير موزونة |
ابن شجرة بحث ثنائية من: 50, 30, 70, 20, 40, 60, 80
الإدراج بهذا الترتيب يعطي:
ما قبل الترتيب: 50, 30, 20, 40, 70, 60, 80
ما بعد الترتيب: 20, 40, 30, 60, 80, 70, 50
الإدراج بهذا الترتيب يعطي:
50
/ \
30 70
/ \ / \
20 40 60 80
بالترتيب: 20, 30, 40, 50, 60, 70, 80 (مصفى)ما قبل الترتيب: 50, 30, 20, 40, 70, 60, 80
ما بعد الترتيب: 20, 40, 30, 60, 80, 70, 50
تعقيد عمليات شجرة البحث الثنائية
| العملية | الحالة المتوسطة | أسوأ حالة (منحرفة) | ملاحظة |
|---|---|---|---|
| بحث | O(log n) | O(n) | اذهب يسار / يمين اعتماداً على المفتاح |
| إدراج | O(log n) | O(n) | نفس البحث + أرفق عقدة جديدة |
| حذف | O(log n) | O(n) | ثلاث حالات: 0, 1, 2 أبناء |
في أسئلة الامتحان التي تسأل عن التعقيد ويقولون "شجرة بحث ثنائية متوازنة" → استخدم O(log n). إذا أظهروا سلسلة منحرفة (مثل قائمة مرتبطة)، التعقيد يصبح O(n).
⛰️ الأكوام وطوابير الأولوية
أساسيات الكوم
- شجرة ثنائية تامة مخزنة كمصفوفة.
- كوم عظمى: كل عقدة ≥ أبنائها.
- كوم صغرى: كل عقدة ≤ أبنائها.
- طابور الأولوية: ADT مجرد غالباً ما ينفذ بالكوم.
تمثيل المصفوفة
إذا كان الجذر عند الفهرس 1:
الابن الأيسر لـ i → 2i
الابن الأيمن لـ i → 2i + 1
الأب لـ i → ⌊i / 2⌋
الابن الأيسر لـ i → 2i
الابن الأيمن لـ i → 2i + 1
الأب لـ i → ⌊i / 2⌋
التعقيدات
| العملية | الكوم | التعقيد | لماذا؟ |
|---|---|---|---|
| إدراج (دفع) | الكوم | O(log n) | اصعد للأعلى على طول الارتفاع |
| احصل على الأعلى/الأدنى | الكوم | O(1) | في الجذر |
| احذف الأعلى/الأدنى (سحب) | الكوم | O(log n) | بدل مع الأخير، انزل للأسفل |
| ابن كوم من n عنصر | heapify | O(n) | سؤال خادع – ليس O(n log n) |
سؤال اختياري شائع: "ما هو تعقيد بناء كوم من مصفوفة غير مرتبة من n عنصر؟"
العديد من الطلاب يختارون O(n log n) لكن الإجابة الصحيحة هي O(n) باستخدام heapify من الأسفل للأعلى.
العديد من الطلاب يختارون O(n log n) لكن الإجابة الصحيحة هي O(n) باستخدام heapify من الأسفل للأعلى.
#️⃣ الجداول التجزئة
أفكار رئيسية
- استخدم دالة تجزئة
h(key)لتعيين المفاتيح → فهرس. - الهدف: متوسط O(1) للبحث/الإدراج/الحذف.
- يجب معالجة التصادمات:
- التسلسل (قوائم مرتبطة)
- العنونة المفتوحة (فحص خطي / تربيعي، تجزئة مزدوجة)
عامل الحمل (α)
α = عدد العناصر / حجم الجدول
أكبر α ⇒ تصادمات أكثر ⇒ عمليات أبطأ.
حل التصادم
| الطريقة | كيف تعمل | مفاتيح الامتحان |
|---|---|---|
| التسلسل | كل فهرس في الجدول يخزن قائمة مرتبطة من المفاتيح | O(1 + α) بحث متوسط |
| الفحص الخطي | جرب الفهرس، ثم الفهرس+1، الفهرس+2,... | مشكلة التكتل الأولي |
| الفحص التربيعي | جرب الفهرس + 1²، الفهرس + 2²... | يقلل التكتل لكن أصعب تنفيذاً |
| التجزئة المزدوجة | استخدم تجزئة ثانوية للقفز | أفضل توزيع في العنونة المفتوحة |
سؤال نموذجي: "لأي هيكل بيانات يكون تعقيد البحث تقريباً O(1) في المتوسط لكن O(n) في أسوأ حالة؟"
✅ الإجابة الصحيحة: جدول التجزئة.
✅ الإجابة الصحيحة: جدول التجزئة.
🕸️ الرسوم البيانية، BFS و DFS
امتحانات CS210 الأخيرة ركزت بشدة على BFS، DFS، عقد الأشجار/الرمادية/السوداء، المكونات المتصلة، وأقصر مسار في الرسوم البيانية غير الموزونة.
تمثيلات الرسم البياني
| التمثيل | المساحة | متى يكون الأفضل | ملاحظات |
|---|---|---|---|
| مصفوفة التجاور | O(V²) | رسم بياني كثيف، V صغير | فحص سريع للحافة(u,v): O(1) |
| قائمة التجاور | O(V + E) | الرسوم البيانية المتفرقة | أفضل لـ BFS/DFS عندما E ≪ V² |
BFS مقابل DFS
BFS (بحث بالعرض أولاً)
- يستخدم طابور
- يزور الجيران مستوى تلو مستوى
- يجد أقصر مسار في الرسوم البيانية غير الموزونة
- جيد لـ:
- أقصر مسار
- اجتياز بالمستوى
DFS (بحث بالعمق أولاً)
- يستخدم مكدس أو عودية
- يذهب عميقاً قبل الرجوع
- جيد لـ:
- كشف الدورات
- الفرز الطولوجي (DAG)
- المكونات المتصلة
شفرة زائفة لـ BFS (قائمة التجاور)
BFS(G, s):
for each vertex v in G:
color[v] = WHITE
dist[v] = ∞
parent[v] = NIL
color[s] = GRAY
dist[s] = 0
Q = empty queue
ENQUEUE(Q, s)
while Q not empty:
u = DEQUEUE(Q)
for each v in Adj[u]:
if color[v] == WHITE:
color[v] = GRAY
dist[v] = dist[u] + 1
parent[v] = u
ENQUEUE(Q, v)
color[u] = BLACK
في تتبع الامتحان، اكتب جدولاً صغيراً من
color, dist, parent لكل رأس وقم بالتحديث خطوة بخطوة. يحبون السؤال "ما هي شجرة BFS؟" أو "ما هي المسافة من s إلى v؟".
🔃 الترتيب والبحث
جدول خدعة خوارزميات الترتيب
| الخوارزمية | أفضل | متوسط | أسوأ | ثابت؟ | ملاحظات |
|---|---|---|---|---|---|
| فرز الاختيار | O(n²) | O(n²) | O(n²) | لا | ابحث عن الأدنى، بدل؛ تبديلات قليلة |
| فرز الفقاعة | O(n) | O(n²) | O(n²) | نعم | بدل المجاور؛ يمكن التوقف مبكراً |
| فرز الإدراج | O(n) | O(n²) | O(n²) | نعم | جيد للمصفوفات شبه المرتبة |
| الفرز الدمجي | O(n log n) | O(n log n) | O(n log n) | نعم | فرق تسد، مساحة إضافية O(n) |
| الفرز السريع | O(n log n) | O(n log n) | O(n²) | لا (أساسي) | في المكان، اختيار المحور مهم |
| فرز الكوم | O(n log n) | O(n log n) | O(n log n) | لا | يستخدم الكوم، في المكان، غير ثابت |
سؤال CS210 نهائي شائع:
"أي خوارزمية ترتيب لها نفس تعقيد O(n²) في أفضل، متوسط وأسوأ الحالات؟"
✅ الإجابة: فرز الاختيار.
"أي خوارزمية ترتيب لها نفس تعقيد O(n²) في أفضل، متوسط وأسوأ الحالات؟"
✅ الإجابة: فرز الاختيار.
البحث الثنائي
- يتطلب مصفوفة مرتبة.
- يقارن بشكل متكرر مع عنصر الوسط.
- التعقيد: O(log n).
BinarySearch(A, key):
low = 0
high = n - 1
while low <= high:
mid = (low + high) / 2
if A[mid] == key:
return mid
else if A[mid] < key:
low = mid + 1
else:
high = mid - 1
return -1
إذا ذكر السؤال "قارن مع عنصر الوسط" أو "تخلص من نصف مساحة البحث كل مرة" → الإجابة دائماً تقريباً البحث الثنائي بـ O(log n) وقت.
🪜 العودية والتتبع
كيف تتتبع الكود العودي (نمط الامتحان)
- اكتب جدولاً صغيراً من الاستدعاءات:
f(4),f(3), إلخ. - قيم الحالة الأساسية بوضوح.
- افرد من الحالة الأساسية للأعلى باستخدام القيم المرجعة.
مثال:
تتبع لـ
int mystery(int n) {
if (n == 0) return 1;
return 2 * mystery(n - 1);
}
تتبع لـ
mystery(3):- mystery(0) = 1 (أساسي)
- mystery(1) = 2 * mystery(0) = 2
- mystery(2) = 2 * mystery(1) = 4
- mystery(3) = 2 * mystery(2) = 8
mystery(3) ترجع 8 = 2³+¹؟ هنا النمط 2ⁿ → 2³ = 8.
علاقة تكرار → تعقيد (بديهي)
| علاقة التكرار | مثال | التعقيد |
|---|---|---|
| T(n) = T(n-1) + O(1) | عودية خطية (عد تنازلي) | O(n) |
| T(n) = T(n/2) + O(1) | بحث ثنائي | O(log n) |
| T(n) = 2T(n/2) + O(n) | الفرز الدمجي | O(n log n) |
| T(n) = 2T(n-1) + O(1) | عودية سيئة جداً | O(2ⁿ) |
🎯 أنماط امتحان CS210 النهائي وقائمة مراجعة أخيرة
ما يتكرر في كل امتحان نهائي تقريباً
- ✔️ أسئلة اختيارية لتعقيد الوقت (المصفوفات، القوائم، BST، الترتيب، الجداول التجزئة).
- ✔️ تتبع قطعة كود وإعطاء المخرج / التعقيد.
- ✔️ بناء أو اجتياز شجرة بحث ثنائية (مسبق/بالترتيب/لاحق/بالمستوى).
- ✔️ تتبع BFS أو DFS مع طابور/مكدس + جداول اللون/المسافة.
- ✔️ تحديد خوارزمية ترتيب من الوصف (اختيار مقابل إدراج مقابل دمج مقابل سريع).
- ✔️ سؤال مؤشر خادع لإدراج/حذف القائمة المرتبطة.
- ✔️ أسئلة مفاهيمية عن الكوم أو طابور الأولوية.
مطبات شائعة
- ❌ قول أن البحث الثنائي يعمل على مصفوفة غير مرتبة.
- ❌ نسيان أن أسوأ حالة للفرز السريع هي O(n²).
- ❌ الخلط بين BFS (طابور) و DFS (مكدس).
- ❌ التفكير أن بناء كوم هو O(n log n) بدلاً من O(n).
- ❌ نسيان أن الاجتياز بالترتيب لـ BST يعطي ترتيباً مصفى.
- ❌ استخدام O(log n) لـ BST غير متوازنة بدلاً من O(n).
خريطة ذهنية أخيرة
المصفوفات
- وصول O(1)
- إدراج/حذف في الوسط O(n)
القائمة المرتبطة
- إدراج/حذف في الرأس O(1)
- بحث O(n)
المكدس والطابور
- LIFO و FIFO
- جميع العمليات O(1)
شجرة البحث الثنائية
- متوازنة: O(log n)
- منحرفة: O(n)
جدول التجزئة
- متوسط O(1)
- أسوأ O(n)
الترتيب
- n²: اختيار، إدراج، فقاعة
- n log n: دمج، سريع (متوسط)، كوم
إذا علقت في سؤال اختياري، أولاً استبعد الخيارات التي تنتهك التعريفات بوضوح: مثلاً، "BFS يستخدم مكدس" خطأ فوراً؛ "الاجتياز بالترتيب يعطي ترتيباً عشوائياً في BST" خطأ؛ "جدول التجزئة أسوأ حالة O(1)" خطأ.