تمارين

مراجعة المفاهيم

التعقيد الزمني والتعقيد المكاني للتكرار والتعاود

تحسب الدالتان التاليتان كلتاهما $1 + 2 + \dots + n$ (افترض أن $n \ge 1$ ). اجعل قيمة n تساوي 4، وأجب عن الأسئلة باتباع ترتيب تنفيذ البرنامج الفعلي، ثم قارن كفاءة الطريقتين.

/* الجمع بالتكرار */
func sumIter(n int) int {
	res := 0
	for i := 1; i <= n; i++ {
		res += i
	}
	return res
}

TypeScript

/* الجمع بالتكرار */
function sumIter(n: number): number {
    let res = 0;
    for (let i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}

عند تشغيل الدالة التكرارية بقيمة n = 4، ما قيمة المجمّع res بعد كل دورة من دورات الحلقة؟
عند تشغيل الدالة التعاودية بقيمة n = 4، ما القيم التي تأخذها الوسيطة n بالترتيب؟ وعندما تعود الاستدعاءات من أعمق مستوى، كيف نحصل على النتيجة؟
ما التعقيد الزمني والتعقيد المكاني للطريقتين؟ اشرح استدلالك باستخدام عمليتي التنفيذ الواردتين في السؤالين 1 و2.

الإجابة

يأخذ متغير الحلقة i القيم 1, 2, 3, 4. وبعد كل دورة يصبح res على الترتيب 1, 3, 6, 10، لذا تعيد الدالة التكرارية القيمة 10.
تأخذ الوسيطة n القيم 4 → 3 → 2 → 1. ويعيد أعمق استدعاء القيمة 1. ثم تحصل الاستدعاءات المتبقية على 2 + 1 = 3 و3 + 3 = 6 و4 + 6 = 10 بهذا الترتيب. وعند أعمق نقطة، تكون استدعاءات الدالة الأربعة كلها ما تزال غير مكتملة.
تؤدي الدالتان عدداً من دورات الحلقة أو الاستدعاءات يتناسب مع $n$ ، لذا يكون التعقيد الزمني لكلتيهما $O(n)$ . أما التعقيد المكاني فيختلف بينهما. فالنسخة التكرارية تستخدم عدداً ثابتاً من المتغيرات فقط، لذا يكون تعقيدها المكاني $O(1)$ . وفي النسخة التعاودية، يجب أن تنتظر الاستدعاءات الأسبق نتيجةً قبل أن تعود، لذا يحمل مكدس الاستدعاءات حتى $n$ استدعاء في الوقت نفسه. وتعقيدها المكاني $O(n)$ .

وعند تحليل التعقيد المكاني، تذكّر أن تشمل المساحة التي تستخدمها الاستدعاءات التعاودية إلى جانب المتغيرات المكتوبة في الشيفرة.

التعقيد الزمني لثلاث مقاطع شيفرة

يأخذ كل مقطع من مقاطع الشيفرة التالية عدداً صحيحاً موجباً $n$ كمدخل. رتّبها من الأدنى إلى الأعلى من حيث التعقيد الزمني، واذكر تعقيد كل واحد منها.

/* حلقة خطية */
func linearLoop(n int) int {
	res := 0
	for i := 0; i < n; i++ {
		res += i
	}
	return res
}

TypeScript

/* حلقة خطية */
function linearLoop(n: number): number {
    let res = 0;
    for (let i = 0; i < n; i++) {
        res += i;
    }
    return res;
}

الإجابة

الترتيب من الأدنى إلى الأعلى هو: المقطع 3 بتعقيد $O(\log n)$ ، ثم المقطع 1 بتعقيد $O(n)$ ، ثم المقطع 2 بتعقيد $O(n^2)$ . فالمقطع 3 ينصّف $n$ في كل دورة، لذا يعمل نحو $\log_2 n$ مرة. أما حلقة المقطع 1 فتعمل $n$ مرة بالضبط. وتعمل الحلقة الداخلية في المقطع 2 $n,n-1,\dots,1$ مرة، أي $n(n+1)/2$ في المجموع، لذا يكون تعقيده الزمني تربيعياً.

أي طريقة للعكس تستهلك مساحة أقل؟

توجد طريقتان لعكس جميع عناصر المصفوفة nums:

أنشئ مصفوفة جديدة res بالطول نفسه، وانسخ العناصر إليها بترتيب معكوس، ثم أعِدها.
حرّك فهرسين i وj إلى الداخل من البداية والنهاية، مع تبديل nums[i] وnums[j] في كل خطوة.

ما التعقيد المكاني لكل طريقة؟ وأيّهما عملية «في المكان»؟

الإجابة

تحتاج هذه الطريقة إلى مصفوفة مساعدة بالطول نفسه للمدخل، لذا يكون تعقيدها المكاني $O(n)$ .
لا تستخدم هذه الطريقة سوى متغيري فهرس، لذا يكون تعقيدها المكاني $O(1)$ . وهي عملية في المكان.

ولاحظ أن العكس في المكان يغيّر مصفوفة الإدخال، لذا لا يُفضَّل إلا عندما يكون تعديل الإدخال مسموحاً. أما إذا وجب الحفاظ على المصفوفة الأصلية، فلا مفرّ من تكلفة النسخ في الطريقة الأولى.

تمارين برمجية

عدد فيبوناتشي

تُعرَّف متتالية فيبوناتشي بـ $F(0)=0$ و $F(1)=1$ ، ولأجل $n\ge2$ يكون $F(n)=F(n-1)+F(n-2)$ .

بمعطى عدد صحيح غير سالب n، استخدم حلقة لحساب $F(n)$ وإعادته. ولا تستخدم التعاود.

تلميحات

تعامل مع حالتي كون n تساوي 0 أو 1 على حدة
لا نحتاج إلى حساب الحد التالي سوى إلى الحدين السابقين؛ فلا حاجة إلى تخزين المتتالية كاملة
عند تحديث المتغيرين، احرص ألا تكتب فوق قيمة قديمة قبل استخدامها

LeetCode{ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }

السابق ملخص التالي بنى البيانات