| يجب أن يكون المرشحون قادرين على: | ملاحظات وإرشادات |
|---|---|
| إظهار فهم طريقتي البحث الخطي والبحث الثنائي | كتابة خوارزمية لتنفيذ البحث الخطي كتابة خوارزمية لتنفيذ البحث الثنائي الشروط اللازمة لاستخدام البحث الثنائي كيف يتغير أداء البحث الثنائي وفقاً لعدد عناصر البيانات |
| إظهار فهم طريقتي الفرز بالإدراج والفرز الفقاعي | كتابة خوارزمية لتنفيذ الفرز بالإدراج كتابة خوارزمية لتنفيذ الفرز الفقاعي قد يعتمد أداء روتين الفرز على الترتيب الأولي للبيانات وعدد عناصر البيانات |
| إظهار الفهم والاستخدام لـ الأنواع المجردة للبيانات (ADT) | كتابة خوارزميات لإيجاد عنصر في كل مما يلي: قائمة مرتبطة، شجرة ثنائية كتابة خوارزميات لإدراج عنصر في كل مما يلي: مكدس، طابور، قائمة مرتبطة، شجرة ثنائية كتابة خوارزميات لحذف عنصر من كل مما يلي: مكدس، طابور، قائمة مرتبطة إظهار الفهم بأن الرسم البياني هو مثال على نوع بيانات مجرد. وصف الخصائص الرئيسية للرسم البياني وتبرير استخدامه لموقف معين. لن يُطلب من المرشحين كتابة كود لهيكلة الرسم البياني |
| إظهار كيفية إمكانية تنفيذ الأنواع المجردة للبيانات باستخدام نوع abstract آخر | وصف الـADTs التالية وإظهار كيفية تنفيذها من أنواع مدمجة مناسبة أو ADTs أخرى: مكدس، طابور، قائمة مترابطة، قاموس، شجرة ثنائية |
| إظهار الفهم أن الخوارزميات المختلفة التي تؤدي نفس المهمة يمكن مقارنتها باستخدام معايير (مثل الوقت المستغرق لإنجاز المهمة والذاكرة المستخدمة) | بما في ذلك استخدام رمزية Big O لتحديد تعقيد الوقت والمساحة |
التفكير الحسابي وحل المشكلات
A-Level علوم الحاسوب · الموضوع 19
15:32
البحث والفرز
دفتر هاتف بمليون اسم. إذا فحصتها واحداً تلو الآخر، قد تقوم بمليون مقارنة. لكنك تعرف بالفعل الحيل: افتحها في المنتصف…
سرد باللغة الإنجليزية · ترجمة نصية بالإنجليزية و中文 يمكنك التبديل بينهما
19.1
خوارزميات البحث
المنهج
المصدر: منهج كامبريدج الدولي
يجد البحث قيمة مستهدفة في مجموعة، غالبًا ما تكون مصفوفة، ويعيد موضعها أو «لم يُعثر عليها».

البحث الخطي
البحث الخطي يمر من البداية إلى النهاية، مقارناً كل عنصر بالمستهدف:
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
لا يلزم أي إعداد، لذا يعمل على أي قائمة. في أسوأ الحالات O($n$) (عندما يكون الهدف في النهاية أو غير موجود)؛ وفي أفضل الحالات 1 مقارنة. استخدمه مع البيانات غير المرتبة أو القوائم الصغيرة. (القيمة -1 المعادة هي قيمة حارسة، أي موضع مستحيل يعني «لم يُعثر عليه»؛ وتختبر الجهة المستدعية IF result = -1.)
النسخة الامتحانية. يطلب الورق 3 إكمال بحث خطي مكتوب باستخدام علم وحلقة WHILE، والورق 4 كتابة دالة تُرجع الفهرس أو عدداً. كلاهما يبدو هكذا:
FUNCTION LinearSearch(Data : ARRAY OF INTEGER, Target : INTEGER) RETURNS INTEGER
DECLARE Index, Count : INTEGER
Count ← 0
FOR Index ← 1 TO 100
IF Data[Index] = Target THEN
Count ← Count + 1
ENDIF
NEXT Index
RETURN Count // how many times Target occurs; 0 means not found
ENDFUNCTION
للوقوف عند أول تطابق بدلاً من ذلك، استخدم حلقة WHILE Index <= 100 AND NOT Found تضع Found ← TRUE وتحتفظ بالفهرس. النقاط مخصصة للحلقة على كل عنصر، والمقارنة، وما يُرجع عندما يكون القيمة غائبة.

البحث الثنائي
يتطلب البحث الثنائي أن تكون البيانات مرتبة. انظر إلى العنصر الأوسط؛ فإن كان هو الهدف انتهى البحث، وإن كان الهدف أصغر فابحث في النصف الأيسر، وإلا ففي النصف الأيمن، مع تنصيف النطاق في كل مرة:
low ← 1
high ← n
WHILE low <= high DO
MiddleIndex ← (low + high) DIV 2
IF A[MiddleIndex] = target THEN
RETURN MiddleIndex
ENDIF
IF A[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDWHILE
RETURN -1
أسوأ حالة O($\log_{2} n$) — لمليون عنصر، حوالي 20 مقارنة. أسرع بكثير من البحث الخطي على مصفوفات كبيرة مرتبة، لكن يجب ترتيبها أولاً (تكلفة O($n \log n$) لمرة واحدة)، يستحق الأمر إذا كنت تبحث مرات عديدة.
«اذكر الشرط اللازم للبحث الثنائي.» يجب أن تكون البيانات مرتبة (تصاعديًا أو تنازليًا حسب المفتاح الذي يجري البحث عنه). «صف كيفية إجراء بحث ثنائي» (ثلاث درجات): (1) أوجد العنصر الأوسط في القائمة أو النطاق الحالي وقارنه بالهدف؛ (2) إذا تطابقا انتهى البحث؛ وإذا كان الهدف أصغر فأعد البحث في النصف الأدنى، وإذا كان أكبر ففي النصف الأعلى؛ (3) استمر في تنصيف النطاق حتى تجد العنصر أو يصبح النطاق فارغًا، مما يعني أنه غير موجود.
النسخة الامتحانية، مع الحدود والعلم، هي ما يجب إعادة إنتاجه عند طلب إكمال الخوارزمية:
DECLARE Lower, Upper, MiddleIndex : INTEGER
DECLARE Found : BOOLEAN
Lower ← 0
Upper ← 99
Found ← FALSE
WHILE Lower <= Upper AND NOT Found
MiddleIndex ← (Lower + Upper) DIV 2
IF Names[MiddleIndex] = Target THEN
Found ← TRUE
ELSE
IF Names[MiddleIndex] < Target THEN
Lower ← MiddleIndex + 1
ELSE
Upper ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
IF Found THEN
OUTPUT MiddleIndex
ELSE
OUTPUT "Not found"
ENDIF
مثال محلول (تتبّع بحث ثنائي). يحتوي Names[0:9] على Ali, Ben, Cai, Dev, Eva, Fay, Gus, Hal, Ivy, Jo. تتبّع نسخة الامتحان للبحث عن Target = "Ivy"، ثم عن Target = "Cat"، مع ذكر Lower وUpper وMiddleIndex في كل خطوة.
بالنسبة إلى «Ivy»:
| Lower | Upper | MiddleIndex | Names[MiddleIndex] | النتيجة |
|---|---|---|---|---|
| 0 | 9 | 4 | Eva | Eva < Ivy، لذا Lower ← 5 |
| 5 | 9 | 7 | Hal | Hal < Ivy، لذا Lower ← 8 |
| 8 | 9 | 8 | Ivy | Found ← TRUE |
المخرَج هو 8، بعد ثلاث مقارنات. بالنسبة إلى «Cat»: الوسط 4 (Eva > Cat، وUpper ← 3)؛ الوسط 1 (Ben < Cat, Lower ← 2); middle 2 (Cai < Cat, Lower ← 3); middle 3 (Dev > Cat، وUpper ← 2). الآن Lower (3) أكبر من Upper (2)، لذا تنتهي الحلقة ويُخرَج «Not found» بعد أربع مقارنات، وهي أسوأ حالة لعشرة عناصر ($\lceil\log_2 10\rceil = 4$). يقرّب DIV إلى الأسفل، لذا فإن وسط 0 و9 هو 4، وليس 4.5 أو 5. تُقارَن السلاسل وفق الترتيب الأبجدي (ترتيب رموز المحارف).
«اشرح كيف يتغير الأداء بتغير عدد العناصر.» تُنصّف كل مقارنة عدد العناصر المتبقية، لذا فإن الحد الأقصى لعدد المقارنات يقارب $\log_{2} n$: مضاعفة حجم القائمة تضيف مقارنة واحدة فقط. وهذا هو O($\log n$). «قارن بين البحث الخطي والثنائي»: يحتاج البحث الخطي إلى ما يصل إلى $n$ من المقارنات (O($n$))، وإلى نصف ذلك في المتوسط، لكنه يعمل على بيانات غير مرتبة؛ ويحتاج البحث الثنائي إلى $\log_{2} n$ على الأكثر (O($\log n$))، وهو أسرع بكثير للقوائم الكبيرة، لكن يجب أولًا ترتيب البيانات وأن تسمح بالوصول المباشر إلى العنصر الأوسط (مصفوفة، لا قائمة مترابطة). بالنسبة إلى $1000$ عنصرًا: $1000$ مقابل $10$ من المقارنات.

*فهرس بطاقات: السجلات المرتبة هي ما يجعل البحث الثنائي ممكناً — ضعّف، انظر، ضعّف مرة أخرى
البحث الخطي مقابل الثنائي
البحث عن قيمة. البحث الثنائي ينصف القائمة في كل خطوة (فقط على البيانات المرتبة)؛ بينما البحث الخطي يفحص العناصر واحداً تلو الآخر.
| English | العربية |
|---|---|
| insertion sort/ɪnˈsɜːʃn sɔːt/ | فرز الإدراج |
| bubble sort/ˈbʌbl sɔːt/ | ترتيب الفقاعة |
| binary search/ˈbaɪnəri sɜːtʃ/ | البحث الثنائي |
| array/əˈreɪ/ | مصفوفة |
| linear search/ˈlɪnɪə sɜːtʃ/ | بحث خطي |
19.1
خوارزميات الترتيب
ترتيب الفقاعات
يمر الترتيب الفقاعي على المصفوفة مرارًا، مبدّلًا أزواج العناصر المتجاورة غير المرتبة، بحيث «يطفو» العنصر الأكبر إلى النهاية في كل مرور:
FOR pass ← 1 TO n - 1
swapped ← FALSE
FOR i ← 1 TO n - pass
IF A[i] > A[i + 1] THEN
temp ← A[i]
A[i] ← A[i + 1]
A[i + 1] ← temp
swapped ← TRUE
ENDIF
NEXT i
IF swapped = FALSE THEN // already sorted
EXIT FOR
ENDIF
NEXT pass
أفضل حالة O($n$) (مرتب مسبقاً، مع الخروج المبكر); متوسط/أسوأ O($n^{2}$). بسيط لكن بطيء لـ $n$ كبير.
الترتيب بالإدراج
ترتيب الإدراج يبني بادئاً مرتباً من اليسار، بإدراج كل عنصر جديد في مكانه عن طريق تحريك الأكبر يميناً:
FOR i ← 2 TO n
key ← A[i]
j ← i - 1
WHILE j >= 1 AND A[j] > key DO
A[j + 1] ← A[j]
j ← j - 1
ENDWHILE
A[j + 1] ← key
NEXT i
أفضل حالة O($n$) (مرتب مسبقاً); أسوأ O($n^{2}$). جيد لـ صغيرة أو قريبة من الترتيب المصفوفات. يرتب محلياً و ثابت (يحافظ على ترتيب العناصر المتساوية).
تتبع الترتيب
مهارة شائعة هي عرض المصفوفة بعد كل مرور خارجي. لـ [D, T, H, R] مع ترتيب الإدراج: المرور 1 (المفتاح T) لا تغيير؛ المرور 2 (المفتاح H) → [D, H, T, R]؛ المرور 3 (المفتاح R) → [D, H, R, T].
الاشتقاق (عد العكسات). العكسة هي
تتحرك عناصر المصفوفة نفسها بطريقة مختلفة باستخدام الترتيب الفقاعي: يقارن المرور 1 بين D/T (دون تبديل)، وT/H (تبديل)، وT/R (تبديل)، فينتج [D, H, R, T] مع وجود العنصر الأكبر في النهاية؛ ولا يُجري المرور 2 أي تبديل، لذا توقف الراية الترتيب. اعرض المصفوفة كاملة بعد كل مرور، واحسب المقارنات إذا طُلب منك ذلك: $3$ في المرور 1 و$2$ في المرور 2 (تتوقف النسخة أعلاه قبل موضع إضافي في كل مرور)، أي $5$ إجمالًا.
كتابة خوارزمية ترتيب من البداية. يُجاب عن «اكتب شيفرة كاذبة لترتيب DataArray[1:1000] تصاعديًا» بترتيب فقاعي كامل مع راية للخروج المبكر، أو بترتيب بالإدراج، مع التصريح المناسب ووضع المسافات البادئة؛ ويستحق أي منهما الدرجة الكاملة إذا عمل مع كل مدخل:
DECLARE Pass, Index, Temp : INTEGER
DECLARE Swapped : BOOLEAN
Pass ← 1
REPEAT
Swapped ← FALSE
FOR Index ← 1 TO 1000 - Pass
IF DataArray[Index] > DataArray[Index + 1] THEN
Temp ← DataArray[Index]
DataArray[Index] ← DataArray[Index + 1]
DataArray[Index + 1] ← Temp
Swapped ← TRUE
ENDIF
NEXT Index
Pass ← Pass + 1
UNTIL Swapped = FALSE OR Pass = 1000
للترتيب التنازلي غيّر > إلى <؛ ولترتيب السجلات أو مصفوفة ذات 2 أبعاد حسب حقل واحد، قارن ذلك الحقل لكن بدّل السجل كاملًا (أو كل الأعمدة). إذا طُلبت كتابة ترتيب بالإدراج «ينفذ المهمة نفسها» التي ينفذها ترتيب فقاعي معطى، فاحتفظ باسم المصفوفة واتجاه الترتيب نفسيهما وأعد كتابة الترتيب بالإدراج أعلاه مع عكس المقارنة إذا كان الترتيب تنازليًا.
«صف طريقتين يتأثر بهما أداء الترتيب بالبيانات» (درجتان). (1) عدد العناصر: يستغرق ترتيب $O(n^{2})$ أربعة أضعاف الوقت عند مضاعفة عدد العناصر. (2) مدى ترتيب البيانات مسبقًا: ينتهي الترتيب الفقاعي باستخدام راية، أو الترتيب بالإدراج، بمرور واحد على البيانات المرتبة مسبقًا ($O(n)$)، ويبذل أكبر جهد مع البيانات المرتبة عكسيًا؛ ويعتمد عدد التبديلات على عدد الأزواج غير المرتبة. (يُقبل أيضًا: نطاق القيم المكررة أو عددها، وما إذا كانت العناصر سجلات كبيرة مكلفة النقل.) كل من الترتيب الفقاعي والترتيب بالإدراج هو O($n^{2}$) في أسوأ الحالات والحالة المتوسطة وO($n$) في أفضل الحالات؛ أما الترتيب السريع والترتيب بالدمج فهما O($n \log n$)، ولهذا يُستخدمان للبيانات الكبيرة.

[D, T, H, R]، حيث يتم إزاحة كل مفتاح إلى مكانه مرحلة تلو الأخرىمشاهدة عملية ترتيب
مرر خوارزمية الترتيب وراقب الأعمدة ترتب نفسها — كيف تعمل خوارزمية الترتيب خطوة بخطوة.
19.1
الأنواع المجردة للبيانات (ADTs) في الخوارزميات
تظهر الأنواع المجردة للبيانات (ADTs) من الموضوع 10 داخل العديد من الخوارزميات: المكدس يقود التمرير العميق وإلغاء الإجراءات؛ القائمة الانتظار تقود التمرير العرضي وترتيب الطباعة؛ القائمة المترابطة تسمح للنمو والتقلص.
يمكن بناء ADTs من أنواع مجردة أخرى وليس فقط من المصفوفات: قائمة انتظار من مكدسين؛ مكدس من قائمة مترابطة (دفع = إضافة رأس عقدة)؛ قائمة انتظار من قائمة مترابطة مع مؤشرات الرأس والذيل؛ شجرة ثنائية من عقد بمؤشرين للطفل؛ قاموس يخزن أزواج المفتاح→القيمة (غالباً على جدول هاش). فصل المهام بهذه الطريقة — لا يحتاج الخوارزم المستخدم للـ ADT إلى معرفة كيفية بنائه.
الـ ADTs التي يطلب منك الامتحان وصفها وتنفيذها
المكدس (آخر يدخل، أول يخرج): تُضاف العناصر (تُضغط) وتُزيل (تُفصح) في نفس النهاية، وهي الأعلى؛ مؤشر TopOfStack يحتفظ بمؤشر العنصر العلوي. يُنفذ باستخدام مصفوفة ذلك المؤشر واحد: يتحقق الدفع من أن المكدس ليس ممتلاً، يزيد المؤشر ويخزن العنصر؛ يتحقق الفصح من أنه ليس فارغاً، يعيد العنصر العلوي وينقص المؤشر.
FUNCTION Push(Item : INTEGER) RETURNS BOOLEAN
IF TopOfStack = 9 THEN // full (array 0 to 9)
RETURN FALSE
ENDIF
TopOfStack ← TopOfStack + 1
StackData[TopOfStack] ← Item
RETURN TRUE
ENDFUNCTION
FUNCTION Pop() RETURNS INTEGER
IF TopOfStack = -1 THEN // empty
RETURN -1
ENDIF
TopOfStack ← TopOfStack - 1
RETURN StackData[TopOfStack + 1]
ENDFUNCTION
قائمة الانتظار (أدخل أولاً، يخرج أولاً): تنضم العناصر إلى الخلف (دخول) وتخرج من الأمام (خروج)؛ مؤشران وعدد. في قائمة الانتظار الخطية ينزلق مؤشر الأمام عبر المصفوفة حتى تُهدر المساحة في البداية؛ قائمة الانتظار الدائرية تعيد تدوير كلا المؤشرين مع MOD، بحيث يتم إعادة استخدام كل خلية.

FUNCTION Enqueue(Item : STRING) RETURNS BOOLEAN
IF Count = 6 THEN // full
RETURN FALSE
ENDIF
Rear ← (Rear + 1) MOD 6
QueueArray[Rear] ← Item
Count ← Count + 1
RETURN TRUE
ENDFUNCTION
FUNCTION Dequeue() RETURNS STRING
IF Count = 0 THEN // empty
RETURN ""
ENDIF
DECLARE Item : STRING
Item ← QueueArray[Front]
Front ← (Front + 1) MOD 6
Count ← Count - 1
RETURN Item
ENDFUNCTION
القائمة المترابطة: تسلسل من العقد، كل منها يحمل عنصراً ومؤشراً للعقدة التالية؛ مؤشر البدء يعطي العقدة الأولى ومؤشر فارغ (0 أو $-1$) ينتهي القائمة. في تنفيذ المصفوفة تحتفظ مصفوفتان موازيان بالبيانات والمؤشرات، وتُربط الخلايا غير المستخدمة في قائمة حرة بحيث تعرف عملية الإدراج أين تضع العقدة الجديدة.

FUNCTION FindInList(Target : STRING) RETURNS INTEGER // index, or 0 if absent
DECLARE Current : INTEGER
Current ← Start
WHILE Current <> 0
IF Data[Current] = Target THEN
RETURN Current
ENDIF
Current ← Pointer[Current]
ENDWHILE
RETURN 0
ENDFUNCTION
لـ الإدراج في قائمة مرتبة: خذ أول خلية حرة (NewNode ← FreeList، FreeList ← Pointer[FreeList])، تخزن العنصر، ثم امشِ القائمة مع Previous وCurrent مؤشر حتى Data[Current] > Item أو النهاية؛ ضع Pointer[NewNode] ← Current وPointer[Previous] ← NewNode (أو Start ← NewNode إذا كان الأول). لـ الحذف، أعد ربط العقدة السابقة لتتجاوز المحذوفة وأعد الخلية للقائمة الحرة.
شجرة ثنائية: عقدة جذر، تحمل كل عقدة بيانات، إشارة يسرى لشجرة جزئية بقيم أصغر وإشارة يمنى لشجرة جزئية بقيم أكبر. تُنفذ كمصفوفة 2D (أو ثلاث مصفوعات 1D) Tree[Index, 0..2] للإشارة اليسرى، البيانات، الإشارة اليمنى، مع إشارة للجذر وإشارة للموقع الحر التالي.
FUNCTION FindInTree(Target : INTEGER) RETURNS INTEGER // index, or -1
DECLARE Current : INTEGER
Current ← Root
WHILE Current <> -1
IF Tree[Current, 1] = Target THEN
RETURN Current
ENDIF
IF Target < Tree[Current, 1] THEN
Current ← Tree[Current, 0] // go left
ELSE
Current ← Tree[Current, 2] // go right
ENDIF
ENDWHILE
RETURN -1
ENDFUNCTION
لـ الإدراج: ذخّر العنصر في العقدة الحرة التالية بكلا المؤشرين $-1$؛ إذا كانت الشجرة فارغة اجعلها الجذر؛ وإلا مشِ للأسفل من الجذر، اذهب يميناً أو يساراً بالمقارنة، حتى يصبح المؤشر الذي ستتبعه $-1$، وضع ذلك المؤشر على العقدة الجديدة. ADT من نوع ADT آخر: المكدس هو قائمة مترابطة يعمل فيها الدفع والفصح كلاهما في البداية؛ قائمة الانتظار هي قائمة مترابطة مع مؤشر بداية ومؤشر نهاية؛ يمكن إنشاء قائمة انتظار من مكدسين (دفع على أحدهما، فصح من الآخر، نقل كل شيء عندما يكون الثاني فارغاً)؛ عقد الشجرة الثنائية هي سجلات أو كائنات مربوطة بمؤشرات، لذلك تُبنى من بنية قائمة مترابطة من العقد. قائل أي عمليات النوع المجرد الجديد تتوافق مع أي عمليات النوع المجرد القديم.
يوضح الشكل الأول شجرة بحث ثنائية: لكل عقدة ما يصل إلى عقدتين فرعيتين، وتوضع القيم الأصغر من قيمة العقدة إلى يسارها، والأكبر إلى يمينها. ويوضح الشكل الثاني الطرق الثلاث لاجتياز الشجرة.


| English | العربية |
|---|---|
| linked list/lɪŋkt lɪst/ | قائمة مرتبطة |
| in place/ɪn pleɪs/ | في الموقع |
| stable/ˈsteɪbl/ | مستقر |
| stack/stæk/ | مكدس |
| queue/kjuː/ | طابور |
| node/nəʊd/ | عُقدَة |
| pointers/ˈpɔɪntəz/ | المؤشرات |
| binary tree/ˈbaɪnəri triː/ | شجرة ثنائية |
| dictionary/ˈdɪkʃənəri/ | قائمة المفردات |
| circular queue/ˈsɜːkjʊlə kjuː/ | طابور دائري |
| free list/friː lɪst/ | قائمة فارغة |
| time complexity/taɪm kəmˈpleksɪti/ | تعقيد الوقت |
| Big-O notation/bɪɡ əʊ nəʊˈteɪʃn/ | رمز بي-أو |
| space complexity/speɪs kəmˈpleksɪti/ | تعقيد المساحة |
19.1
مقارنة الخوارزميات
تعقيد الوقت
تعقيد الوقت هو كيفية نمو وقت التشغيل مع حجم الإدخال $n$، يُكتب بـ رمزية بي-أو O (الحد المهيمن): O(1) ثابت، O($\log n$) بحث ثنائي، O($n$) بحث خطي، O($n \log n$) عمليات فرز جيدة، O($n^{2}$) فقاعات/فرز إدراج. الرتبة الأصغر أفضل على النطاق الواسع، حتى لو كان خوارزمية أخرى أسرع لأحجام صغيرة $n$.
لتوضيح ذلك بشكل ملموس: لترتيب مليون عنصر، يكمل ترتيب $O(n \log n)$ في جزء من الثانية، بينما قد يستغرق ترتيب $O(n^{2})$ دقائق.
مثال محلول. قائمة مرتبة تحتوي على $1000$ عنصر. كم عدد المقارنات التي تحتاجها كل عملية بحث في أسوأ حالة؟
يبحث الخطي عن العناصر واحداً تلو الآخر، لذا قد يحتاج إلى ما يصل إلى $1000$ مقارنات — وهذا هو $O(n)$. أما البحث الثنائي فيقسم القائمة إلى نصفين في كل خطوة، لذا يحتاج إلى ما لا يزيد عن $\lceil \log_2 1000 \rceil = 10$ مقارنات — وهذا هو $O(\log n)$. مضاعفة القائمة لتصل إلى $2000$ عنصر تضيف فقط مقارنة واحدة للبحث الثنائي، ولكن ما يصل إلى $1000$ إضافية للبحث الخطي — ولهذا السبب، فإن ترتيب النمو وليس السرعة الخام هو ما يحدد الفائز على النطاق الواسع.
وصف رتبة التعقيد. O(1): الزمن ثابت، ولا يعتمد على عدد العناصر (إضافة عنصر إلى مكدس، أو قراءة عنصر من مصفوفة). O($\log n$): يزداد الزمن مع لوغاريتم عدد العناصر، لذا فإن مضاعفة البيانات تضيف خطوة إضافية ثابتة فقط (البحث الثنائي). O($n$): يزداد الزمن بالتناسب مع عدد العناصر (البحث الخطي، والمرور مرة واحدة على قائمة). O($n \log n$): أسوأ قليلًا من الخطي (خوارزميات الترتيب الفعالة). O($n^{2}$): يزداد الزمن مع مربع عدد العناصر، لذا فإن مضاعفة البيانات تضاعف الزمن أربع مرات (الترتيب الفقاعي والترتيب بالإدراج). يُجاب عن «اذكر تعقيد Big O للبحث الثنائي في Names[0:99]» بـ$O(\log n)$، ويُوصف معناه كما سبق؛ تقيس Big O كيفية تغير الزمن أو الذاكرة مع حجم البيانات، لا الزمن الفعلي.
مثال محلول (رتبة تعقيد مقطع برمجي). اذكر التعقيد الزمني لكل مقطع، حيث n هو عدد العناصر.
// Fragment A
FOR i ← 1 TO n
FOR j ← 1 TO n
Total ← Total + Grid[i, j]
NEXT j
NEXT i
// Fragment B
Count ← 0
WHILE n > 1
n ← n DIV 2
Count ← Count + 1
ENDWHILE
// Fragment C
FOR i ← 1 TO n
Total ← Total + A[i]
NEXT i
FOR i ← 1 TO n
OUTPUT A[i] / Total
NEXT i
تعقيد A هو $O(n^{2})$: تُنفذ التعليمة الداخلية $n$ مرة لكل مرور من مرات المرور الخارجية البالغ عددها $n$، أي $n \times n$ إجمالًا. وتعقيد B هو $O(\log n)$: يُنصَّف $n$ في كل مرور، لذا تُنفذ الحلقة نحو $\log_2 n$ مرة (عند $n = 64$، ست مرات مرور). وتعقيد C هو $O(n)$: تستغرق حلقتان إحداهما بعد الأخرى $n + n = 2n$ خطوة، وتُحذف الثوابت. القاعدة: الحلقات المتداخلة تُضرب، والحلقات المتتابعة تُجمع، ولا يُحتفظ إلا بالحد الأسرع نموًا، لذا فإن $3n^{2} + 5n + 2$ هو $O(n^{2})$.


تعقيد المساحة
تعقيد المساحة هو الذاكرة الإضافية المطلوبة. يستخدم ترتيب الفقاعة والإدراج O(1) إضافياً (في المكان)؛ يستخدم ترتيب merge sort O($n$)؛ تستخدم الاستدعاءات المتكررة ذاكرة مكدس تتناسب مع عمقها. غالباً ما يكون هناك توازن بين الوقت والذاكرة.
معايير أخرى
البساطة (أسهل في البرمجة والصيانة)، الاستقرار، والتكيّف (أسرع على البيانات شبه المرتبة). تعتمد الخوارزمية الصحيحة على البيانات والقيود.
كيف ينمو وقت التنفيذ مع n
ارفع n للأعلى وقارن المنحنيات: O(1) و O(log n) تظل مسطحة تقريبًا، O(n) ترتفع باستمرار، O(n²) تنفجر. ولهذا السبب تُستخدم Big-O — وليس ساعة إيقاف — للمقارنة بين الخوارزميات على المدخلات الكبيرة.
نمو Big-O
غيّر حجم الإدخال n وقارن مدى سرعة نمو عمل كل خوارزمية — وهو المبدأ وراء التعقيد الزمني.
19.2
الاستدعاء المتكرر
المنهج
| يجب أن يكون المرشحون قادرين على: | ملاحظات وإرشادات |
|---|---|
| إظهار فهم الاستدعاء الذاتي | الميزات الأساسية لـالاستدعاء الذاتي كيف يتم التعبير عن الاستدعاء الذاتي في لغة برمجة كتابة وتتبع الخوارزميات الاستدعاء الذاتي متى يكون استخدام الاستدعاء الذاتي مفيداً |
| إظهار الوعي بما يجب على المترجم فعله لترجمة كود البرمجة الاستدعاء الذاتي | استخدام المكدسات وإزالة الاستدعاءات |
المصدر: منهج كامبريدج الدولي
![أربع صناديق استدعاء، كل منها محاذى أسفل السابق: total([4, 7, 2]) = 4 + total([7, 2]); total([7, 2]) = 7 + total([2]); total([2]) = 2 + total([]); total([]) = 0 هي الحالة الأساسية. القيم تعود للأعلى: 2، ثم 9، ثم 13](/handout-media/a_level_computer_science/assets/19-recursion.png?v=1794647943)
الخوارزميات المتكررة تستخدم الاستدعاء المتكرر: تستدعي الدالة نفسها بإصدار أصغر من نفس المشكلة، حتى تنتهي سلسلة من خلال حالة أساسية. تتكون من جزأين: الحالة الأساسية (صغيرة بما يكفي لحلها مباشرة — بدونها لن يتوقف الاستدعاء المتكرر أبداً) والحالة المتكررة (تقليل المدخلات والاستدعاء لنفسها).
المضروب (Factorial):
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 OR n = 1 THEN
RETURN 1
ELSE
RETURN n * Factorial(n - 1)
ENDIF
ENDFUNCTION
الاستدعاء المتكرر طبيعي للمشاكل ذاتية التشابه: الأشجار، القسمة والفتح (البحث الثنائي، ترتيب merge)، والبيانات المتداخلة. عندما يكون غير مناسب، تكون الحلقة عادة أنظف.
«صف المقصود بالاستدعاء الذاتي» (درجتان). دالة أو إجراء يُعرَّف بدلالة نفسه: فهو يستدعي نفسه من داخل جسمه، بنسخة أصغر من المسألة في كل مرة، حتى يصل إلى حالة أساس. «اذكر ثلاث سمات أساسية للاستدعاء الذاتي»: (1) حالة أساس (شرط توقف) تعيد قيمة دون استدعاء آخر؛ (2) حالة عامة يستدعي فيها الروتين نفسه؛ (3) يقرّب كل استدعاء المسألة من حالة الأساس (تُخفَّض قيمة المعامل)، حتى ينتهي الاستدعاء الذاتي. تضيف بعض مخططات التصحيح: تُعاد القيم عند تتابع العودة من الاستدعاءات.
«صف متى يكون استخدام الاستدعاء الذاتي مفيدًا، وأعط مثالًا.» عندما تكون المسألة معرّفة طبيعيًا بدلالة نسخ أصغر من نفسها، بحيث يكون الحل بالاستدعاء الذاتي أقصر وأوضح وأقرب إلى التعريف الرياضي من الحلقة: مثل المضروب أو عدد فيبوناتشي، والبحث الثنائي، واجتياز شجرة ثنائية، والترتيب بالدمج أو الترتيب السريع، ومعالجة البنى المتداخلة مثل المجلدات داخل المجلدات. وهو اختيار ضعيف عندما يكون العمق كبيرًا (فقد يفيض المكدس) أو عندما تُحسب المسألة الفرعية نفسها مرات كثيرة (كما في حساب فيبوناتشي بالطريقة المباشرة).
تتبع استدعاء متكرر
بالنسبة لـ Factorial(4): تذهب الاستدعاءات نزولاً حتى Factorial(1)=1، ثم الانفكاك يضرب صعوداً: 2*1=2، 3*2=6، 4*6=24. النتيجة النهائية 24. تتبع كل استدعاء معلق على المكدس.
مثال محلول. الدالة أدناه معطاة بدون شرح. تتبع Unknown(3, 5) واذكر مخرجاتها وقيمتها المُرجعة.
FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
IF X < Y THEN
OUTPUT X + Y
RETURN Unknown(X + 1, Y - 1) + 1
ELSE
RETURN 0
ENDIF
ENDFUNCTION
الاستدعاء 1: $X = 3, Y = 5$: $3 < 5$، الإخراج 8، استدعاء Unknown(4, 4). الاستدعاء 2: $4 < 4$ غير صحيح، إرجاع 0. الانفكاك: يعود الاستدعاء 1 بـ $0 + 1 = 1$. إخراج 8، القيمة المُرجعة 1. اكتب التتبع كجدول بصف لكل استدعاء (المعاملات، الشرط، الإخراج، ما يُرجعه)، وقم بإرجاعات الاستدعاء الأعمق صعوداً: هذا هو الانفكاك الذي يبحث عنه مفتاح التصحيح.
مثال محلول (فيبوناتشي). Fib(n) يُرجع n عندما n < 2، وإلا Fib(n - 1) + Fib(n - 2). أوجد Fib(5).
Fib(5) = Fib(4) + Fib(3)؛ Fib(4) = Fib(3) + Fib(2)؛ Fib(3) = Fib(2) + Fib(1)؛ Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. لذا Fib(3) = 1 + 1 = 2، Fib(4) = 2 + 1 = 3، Fib(5) = 3 + 2 = 5. يتم الوصول إلى الحالة الأساسية مرات كثيرة (يتم حساب Fib(2) ثلاث مرات)، وهو سبب بطء هذه النسخة: فهي تقوم بـ 15 استدعاءً لـ $n = 5$ وتضاعف تقريباً عدد الاستدعاءات لكل زيادة في $n$.
تحويل الاستدعاء الذاتي إلى تكرار. يمكن إعادة كتابة كل إجراء استثنائي باستخدام حلقة، والتي تستهلك ذاكرة أقل وتكون أسرع: احتفظ بنتيجة متراكمة وكرر من الحالة الأساسية للأعلى. المضروب كحلقة:
FUNCTION Factorial(N : INTEGER) RETURNS INTEGER
DECLARE Result, Count : INTEGER
Result ← 1
FOR Count ← 2 TO N
Result ← Result * Count
NEXT Count
RETURN Result
ENDFUNCTION
عند الطلب لتحويل ترتيب إدراج استثنائي أو بحث إلى شكل تكراري، استبدل الاستدعاء الذاتي بحلقة على الفهرس الذي كان يتدرج خلاله الاستدعاء الذاتي، وحول الحالة الأساسية إلى شرط خروج الحلقة.

المخاطر
- الاستدعاء الذاتي اللانهائي إذا تم تفادي الحالة الأساسية — يتوقف البرنامج بسبب انفجار المكدس.
- استخدام ذاكرة مرتفع للاستدعاءات العميقة.
- بطيء إذا كان يعيد العمل (فيبوناتسي بدائي أسّي — استخدم حلقة أو التخزين المؤقت).
تتراجع العودية من الأوراق صعوداً
مرر عبر fib(4) بالترتيب الذي تنتهي فيه المكالمات فعليًا: تتحلل الأوراق (الحالات الأساسية) أولاً، ثم يجمع كل أب أبنائه. لاحظ أن fib(2) يتم حسابه مرتين — هذا العمل المكرر هو السبب في بطء العودية البدائية.
| English | العربية |
|---|---|
| recursion/rɪˈkɜːʃn/ | التكرار الذاتي |
| call stack/kɔːl stæk/ | مكدس الاستدعاء |
| base case/beɪs keɪs/ | الحالة الأساسية |
| recursive case/rɪˈkɜːsɪv keɪs/ | الحالة التكرارية |
| factorial/fækˈtɔːrɪəl/ | المضروب |
| divide-and-conquer/dɪˈvaɪd ænd ˈkɒŋkə/ | فرز وحل |
| general case/ˈdʒenərəl keɪs/ | الحالة العامة |
| parameters/pəˈræmɪtəz/ | المُعاملات |
| stack overflow/stæk ˌəʊvəˈfləʊ/ | تجاوز سعة المكدس |
| memoisation/ˌmeməʊaɪˈzeɪʃn/ | الترميز التذكاري |
| local variables/ˈləʊkl ˈveərɪəblz/ | المتغيرات المحلية |
| stack frame/stæk freɪm/ | إطار المكدس |
| return address/rɪˈtɜːn əˈdres/ | عنوان الإرجاع |
19.2
ما يفعله المترجم للكود الاستثنائي
يحتاج الاستدعاء الذاتي إلى أن يكون لكل استدعاء نسخة خاصة به من المعاملات والمتغيرات المحلية. يحافظ المترجم على هذه البيانات في مكدس الاستدعاءات. لكل استدعاء، يدفع إطار مكدس يحتوي على المعاملات، والمتغيرات المحلية، وعنوان الإرجاع (أين يستأنف في الدالة المستدعية). عندما تعود الدالة، يتم إعادة القيمة المُرجعة، يُزال الإطار، ويستأنف التحكم عند عنوان الإرجاع.

لأن لكل استدعاء إطاره الخاص، لا تطغى الاستدعاءات الذاتية على متغيرات بعضها. قد يكبر المكدس كثيرًا عند الاستدعاء الذاتي العميق، ولهذا قد يؤدي العمق الشديد إلى فيضه. وهذه هي آلية الاستدعاء والعودة نفسها المستخدمة في الاستدعاءات العادية غير الذاتية، ولا توجد «آلية استدعاء ذاتي» خاصة.
«اشرح لماذا يُعد المكدس مناسبًا لتنفيذ الاستدعاء الذاتي» (ثلاث درجات). يجب على كل استدعاء ذاتي حفظ عنوان العودة ومعاملاته ومتغيراته المحلية، وتكتمل الاستدعاءات بترتيب معاكس لترتيب إجرائها (فآخر استدعاء يُجرى هو أول استدعاء ينتهي)، وهذا يطابق تمامًا سلوك المكدس آخر داخل، أول خارج: كل استدعاء جديد يدفع إطارًا إلى المكدس، وكل عودة تسحب أحدث إطار، فتستعيد حالة المستدعي وتحدد له موضع استئناف التنفيذ. وهذه مهمة المترجم عند ترجمة الشيفرة ذات الاستدعاء الذاتي: فهو يولّد تعليمات دفع إطار إلى المكدس عند كل استدعاء وسحبه عند كل عودة، وتتتابع إزالة الإطارات مع عودة النتائج.
19.2
التعريفات التي يقبلها المصحح
تُصنّف أسئلة التعريف بناءً على صياغة ثابتة. احفظ هذه التعريفات بدقة، وقدم إجابة واحدة فقط.
| مصطلح | تعريف |
|---|---|
| البحث الخطي | فحص كل عنصر بالتتابع من البداية حتى العثور على الهدف أو الوصول إلى النهاية |
| البحث الثنائي | مقارنة الهدف بشكل متكرر مع العنصر الأوسط لقائمة مرتبة والتخلص من النصف الذي لا يمكن أن يحتوي عليه |
| ترتيب الفقاعات | المرور المتكرر عبر القائمة، وتبادل العناصر المتجاورة التي تقع في الترتيب الخاطئ، حتى لا تقوم أي مرور بتبادلات |
| ترتيب الإدراج | أخذ كل عنصر بالتتابع وإدخاله في مكانه الصحيح بين العناصر المرتبة مسبقًا |
| نوع البيانات المجرد | مجموعة من البيانات والعمليات التي يمكن تنفيذها عليها، يتم تعريفها بشكل مستقل عن طريقة تخزينها |
| مكدس | هيكل الأخير دخولاً، الأول خروجاً مع الدفع والرفع في الأعلى |
| طابور | هيكل الأول دخولاً، الأول خروجاً مع إضافة العناصر من الخلف وإزالتها من الأمام |
| قائمة مربوطة | تسلسل من العقد، كل منها يحمل بيانات ومؤشرًا للعقدة التالية، مع مؤشر بداية |
| شجرة ثنائية | عقد تحمل كل منها بيانات ومؤشرات إلى شجرة فرعية يسرى لقيم أصغر وشجرة فرعية يمنى لقيم أكبر |
| ترميز بي-أو | طريقة لتصنيف الوقت (أو الذاكرة) الذي يحتاجه خوارزمية بناءً على نموها مع حجم المدخلات |
| الاستدعاء الذاتي | إجراء يستدعي نفسه بنسخة أصغر من المشكلة حتى توقف حالتان أساسية الاستدعاءات |
| الحالة الأساسية | الشرط الذي يعود فيه الإجراء الاستثنائي دون استدعاء نفسه |
| الانفك | عودات سلسلة من الاستدعاءات الاستثنائية، من أعمق استدعاء إلى الأول، أثناء رفع إطارات المكدس |
19.2
نصائح للامتحان
- البحث: لا يحتاج البحث الخطي إلى ترتيب وتعقيده O($n$)؛ أما الثنائي فيحتاج إلى مصفوفة مرتبة وينصّف النطاق في كل مرة وتعقيده O($\log n$). احفظ الخوارزميتين جيدًا، بما في ذلك الحدود والراية.
- أنواع الترتيب: الفقاعة مع علم تبديل، والإدراج بمفتاح يُزيح العناصر الأكبر يمينًا؛ كلاهما O($n^{2}$) في أسوأ الحالات، وO($n$) على البيانات المرتبة. يعتمد الأداء على عدد العناصر ومدى ترتيبها.
- تطبيقات ADT هي إدارة مؤشرات: مؤشر علوي؛ أمامي وخلفي وعدد مع MOD؛ بداية ومؤشرات وقائمة حرة؛ جذر مع مؤشرات يسرى ويمنى. تحقق دائمًا من الامتلاء والفراغ.
- تتعلق Big O بكيفية تغير التعقيد: ثابت، أو لوغاريتمي، أو خطي، أو تربيعي. قل «تضيف مضاعفة البيانات مقارنة واحدة» بالنسبة إلى البحث الثنائي.
- الاستدعاء الذاتي: الحالة الأساسية، الحالة العامة، التقدم نحو الحالة الأساسية؛ مفيد عندما يتم تعريف المشكلة بدورها؛ تحتفظ المكدس بعناوين الإرجاع والمتغيرات لأن الاستدعاءات ترجع بالترتيب المعكوس. تتبع باستخدام جدول وفك الأعمدة من أعمق استدعاء.
أخطاء شائعة
- كتابة $O(2n)$ أو $O(n^{2} + n)$: احذف الثوابت والحدود الأصغر لتحصل على $O(n)$ و$O(n^{2})$.
- حساب فهرس الوسط على صورة $(Lower + Upper) / 2$ في تتبّع التنفيذ: تستخدم نسخة الامتحان
DIV، لذا قرّب إلى الأسفل. - استخدام البحث الثنائي على بيانات غير مرتبة، أو على قائمة مترابطة؛ وضبط
Lower ← MiddleIndexبدلاً منMiddleIndex + 1، مما يسبب حلقة لا نهائية. - حلقة داخلية لترتيب الفقاعة تعمل حتى نهاية المصفوفة في كل مرور، أو تبديل بدون متغير مؤقت.
- دفع أو إضافة لا يختبران الامتلاء، أو سحب أو إزالة لا يختبران الفراغ.
- تحريك مؤشر الأمامي للطابور بدون MOD في طابور دائري، أو اعتبار front = rear تعني دائمًا الفراغ.
- الإدراج في قائمة مترابطة عن طريق إزاحة محتويات المصفوفة؛ تتغير فقط المؤشرات.
- دالة ذاتية ببدون حالة أساسية، أو واحدة يكون فيها الاستدعاء الذاتي لا يصغر المشكلة.
- تتبع استدعاء متكرر ولكن نسيان إضافة العمل المعلق أثناء العودة للأعلى.
- الإجابة عن «لماذا يُستخدم المكدس» بعبارة «لأنه سريع»؛ السبب هو ترتيب العودة وفق مبدأ آخر داخل، أول خارج.
دروس تفاعلية حول هذا الموضوع
ا-working عليه خطوة بخطوة، مع تمارين تحقق فوري.