التعقيد الزمني

يعكس زمن التشغيل كفاءة الخوارزمية بطريقة بديهية ودقيقة. وإذا أردنا تقدير زمن تشغيل قطعة شيفرة تقديراً دقيقاً، فكيف نفعل ذلك؟

1. حدّد منصة التشغيل، بما فيها تكوين العتاد ولغة البرمجة وبيئة النظام وغيرها، لأن هذه العوامل كلها تؤثر في كفاءة تنفيذ الشيفرة.
2. قدّر الزمن اللازم لمختلف العمليات الحسابية، فمثلاً تحتاج عملية جمع + إلى 1 ns، وتحتاج عملية ضرب * إلى 10 ns، وتحتاج عملية طباعة print() إلى 5 ns، وهكذا.
3. أحصِ جميع العمليات الحسابية في الشيفرة، واجمع أزمنة تنفيذ جميع العمليات للحصول على زمن التشغيل.

فمثلاً، في الشيفرة التالية، حجم بيانات الإدخال هو $n$:

// على منصة تشغيل معينة
func algorithm(n int) {
    a := 2     // 1 ns
    a = a + 1  // 1 ns
    a = a * 2  // 10 ns
    // حلقة n مرة
    for i := 0; i < n; i++ {  // 1 ns
        fmt.Println(a)        // 5 ns
    }
}

// على منصة تشغيل معينة
function algorithm(n: number): void {
    var a: number = 2; // 1 ns
    a = a + 1; // 1 ns
    a = a * 2; // 10 ns
    // حلقة n مرة
    for(let i = 0; i < n; i++) { // 1 ns
        console.log(0); // 5 ns
    }
}

وبحسب الطريقة أعلاه، يمكن الحصول على زمن تشغيل الخوارزمية وهو $(6n + 12)$ ns:

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

إحصاء اتجاه نمو الزمن

لا يحصي تحليل التعقيد الزمني زمن تشغيل الخوارزمية، بل يحصي اتجاه نمو زمن تشغيل الخوارزمية مع زيادة حجم البيانات.

مفهوم «اتجاه نمو الزمن» مجرّد بعض الشيء؛ ولنفهمه عبر مثال. لنفترض أن حجم بيانات الإدخال هو $n$، وبمعطى ثلاث خوارزميات A وB وC:

// التعقيد الزمني للخوارزمية A: رتبة ثابتة
func algorithm_A(n int) {
    fmt.Println(0)
}
// التعقيد الزمني للخوارزمية B: رتبة خطية
func algorithm_B(n int) {
    for i := 0; i < n; i++ {
        fmt.Println(0)
    }
}
// التعقيد الزمني للخوارزمية C: رتبة ثابتة
func algorithm_C(n int) {
    for i := 0; i < 1000000; i++ {
        fmt.Println(0)
    }
}

// التعقيد الزمني للخوارزمية A: رتبة ثابتة
function algorithm_A(n: number): void {
    console.log(0);
}
// التعقيد الزمني للخوارزمية B: رتبة خطية
function algorithm_B(n: number): void {
    for (let i = 0; i < n; i++) {
        console.log(0);
    }
}
// التعقيد الزمني للخوارزمية C: رتبة ثابتة
function algorithm_C(n: number): void {
    for (let i = 0; i < 1000000; i++) {
        console.log(0);
    }
}

يوضح الشكل أدناه التعقيد الزمني لدوال الخوارزميات الثلاث أعلاه.

• تحتوي الخوارزمية A على عملية طباعة واحدة فقط، ولا ينمو زمن تشغيل الخوارزمية مع زيادة $n$. ونسمّي التعقيد الزمني لهذه الخوارزمية «الرتبة الثابتة».
• في الخوارزمية B، تحتاج عملية الطباعة إلى تكرار $n$ مرة، وينمو زمن تشغيل الخوارزمية خطياً مع زيادة $n$. ويُسمى التعقيد الزمني لهذه الخوارزمية «الرتبة الخطية».
• في الخوارزمية C، تحتاج عملية الطباعة إلى تكرار $1000000$ مرة. ورغم أن زمن التشغيل طويل جداً، فهو مستقل عن حجم بيانات الإدخال $n$. لذلك يكون التعقيد الزمني لـC هو نفسه التعقيد الزمني لـA، أي «الرتبة الثابتة» أيضاً.

مقارنةً بحساب زمن تشغيل الخوارزمية مباشرةً، فما خصائص تحليل التعقيد الزمني؟

• يستطيع التعقيد الزمني تقييم كفاءة الخوارزمية تقييماً فعالاً. فمثلاً، ينمو زمن تشغيل الخوارزمية B خطياً؛ فعندما $n > 1$ تكون أبطأ من الخوارزمية A، وعندما $n > 1000000$ تكون أبطأ من الخوارزمية C. وفي الواقع، ما دام حجم بيانات الإدخال $n$ كبيراً بما يكفي، فإن خوارزمية بتعقيد «الرتبة الثابتة» تكون دائماً أفضل من خوارزمية بتعقيد «الرتبة الخطية»، وهذا هو بالضبط معنى اتجاه نمو الزمن.
• طريقة اشتقاق التعقيد الزمني أبسط. فمن الواضح أن منصة التشغيل وأنواع العمليات الحسابية لا علاقة لهما باتجاه نمو زمن تشغيل الخوارزمية. لذلك يمكننا في تحليل التعقيد الزمني أن نعامل ببساطة زمن تنفيذ جميع العمليات الحسابية على أنه «زمن وحدة» واحد، فنختصر «تتبع زمن تشغيل كل عملية» إلى «إحصاء عدد العمليات»، مما يقلل صعوبة التقدير تقليلاً كبيراً.
• للتعقيد الزمني أيضاً قيود معينة. فمثلاً، رغم أن الخوارزميتين A وC لهما التعقيد الزمني نفسه، فإن زمن تشغيلهما الفعلي يختلف اختلافاً كبيراً. وبالمثل، رغم أن التعقيد الزمني للخوارزمية B أعلى من تعقيد C، فعندما يكون حجم بيانات الإدخال $n$ صغيراً تكون الخوارزمية B أفضل بوضوح من الخوارزمية C. وفي مثل هذه الحالات، يصعب غالباً الحكم على كفاءة الخوارزميات بالاعتماد على التعقيد الزمني وحده. وبالطبع، رغم المشكلات أعلاه، يظل تحليل التعقيد أنجع الطرق وأكثرها شيوعاً لتقييم كفاءة الخوارزميات.

الحد الأعلى التقاربي للدوال

بمعطى دالة حجم إدخالها $n$:

func algorithm(n int) {
    a := 1      // +1
    a = a + 1   // +1
    a = a * 2   // +1
    // حلقة n مرة
    for i := 0; i < n; i++ {   // +1
        fmt.Println(a)         // +1
    }
}

function algorithm(n: number): void{
    var a: number = 1; // +1
    a += 1; // +1
    a *= 2; // +1
    // حلقة n مرة
    for(let i = 0; i < n; i++){ // +1 (يُنفَّذ i++ في كل جولة)
        console.log(0); // +1
    }
}

ولتكن عدد عمليات الخوارزمية دالةً في حجم بيانات الإدخال $n$، ويرمز إليها بـ$T(n)$. عندئذٍ يكون عدد عمليات الدالة أعلاه:

$T(n)$ دالة خطية، مما يدل على أن اتجاه نمو زمن تشغيلها خطي، ومن ثمّ فإن تعقيدها الزمني من الرتبة الخطية.

ونرمز للتعقيد الزمني من الرتبة الخطية بـ$O(n)$. ويُسمى هذا الرمز الرياضي ترميز $O$ الكبير، وهو يمثّل الحد الأعلى التقاربي للدالة $T(n)$.

يحسب تحليل التعقيد الزمني في جوهره الحد الأعلى التقاربي لـ«عدد العمليات $T(n)$»، ولهذا تعريف رياضي واضح.

وكما هو موضح في الشكل أدناه، فإن حساب الحد الأعلى التقاربي هو إيجاد دالة $f(n)$ بحيث عندما يؤول $n$ إلى اللانهاية يكون $T(n)$ و$f(n)$ في المستوى نفسه من النمو، ولا يختلفان إلا بمعامل ثابت $c$.

طريقة الاشتقاق

فكرة الحد الأعلى التقاربي رياضية بعض الشيء. وإذا شعرت أنك لم تفهمها فهماً كاملاً، فلا تقلق. يمكننا أولاً إتقان طريقة الاشتقاق، ثم استيعاب معناها الرياضي تدريجياً بالممارسة المستمرة.

وفقاً للتعريف، بعد تحديد $f(n)$ يمكننا الحصول على التعقيد الزمني $O(f(n))$. فكيف نحدد الحد الأعلى التقاربي $f(n)$؟ إجمالاً، ينقسم ذلك إلى خطوتين: أولاً إحصاء عدد العمليات، ثم تحديد الحد الأعلى التقاربي.

الخطوة 1: إحصاء عدد العمليات

بالنسبة إلى الشيفرة، أُحصِ من الأعلى إلى الأسفل سطراً سطراً. غير أنه بما أن المعامل الثابت $c$ في $c \cdot f(n)$ أعلاه يمكن أن يكون بأي مقدار، فإن المعاملات والحدود الثابتة في عدد العمليات $T(n)$ يمكن تجاهلها جميعاً. ووفقاً لهذا المبدأ، يمكن تلخيص تقنيات التبسيط التالية في الإحصاء.

1. تجاهل الثوابت في $T(n)$. لأنها كلها مستقلة عن $n$، فلا تؤثر في التعقيد الزمني.
2. احذف جميع المعاملات. فمثلاً، تكرار الحلقة $2n$ مرة أو $5n + 1$ مرة وغير ذلك يمكن تبسيطه كله إلى $n$ مرة، لأن المعامل قبل $n$ لا يؤثر في التعقيد الزمني.
3. استخدم الضرب في الحلقات المتداخلة. فعدد العمليات الإجمالي يساوي حاصل ضرب عدد العمليات في الحلقتين الخارجية والداخلية، مع إمكان تطبيق التقنيتين 1. و2. على كل طبقة من الحلقة على حدة.

بمعطى دالة، يمكننا استخدام التقنيات أعلاه لإحصاء عدد العمليات:

func algorithm(n int) {
    a := 1     // +0 (التقنية 1)
    a = a + n  // +0 (التقنية 1)
    // +n (التقنية 2)
    for i := 0; i < 5 * n + 1; i++ {
        fmt.Println(0)
    }
    // +n*n (التقنية 3)
    for i := 0; i < 2 * n; i++ {
        for j := 0; j < n + 1; j++ {
            fmt.Println(0)
        }
    }
}

function algorithm(n: number): void {
    let a = 1;  // +0 (التقنية 1)
    a = a + n;  // +0 (التقنية 1)
    // +n (التقنية 2)
    for (let i = 0; i < 5 * n + 1; i++) {
        console.log(0);
    }
    // +n*n (التقنية 3)
    for (let i = 0; i < 2 * n; i++) {
        for (let j = 0; j < n + 1; j++) {
            console.log(0);
        }
    }
}

تعرض الصيغة التالية نتائج الإحصاء قبل استخدام التقنيات أعلاه وبعدها؛ وكلاهما يؤدي إلى تعقيد زمني $O(n^2)$.

الخطوة 2: تحديد الحد الأعلى التقاربي

يتحدد التعقيد الزمني بالحد الأعلى رتبةً في $T(n)$. ويعود السبب إلى أنه عندما يؤول $n$ إلى اللانهاية، سيؤدي الحد الأعلى رتبةً دوراً مهيمناً، ويمكن تجاهل تأثير الحدود الأخرى.

يعرض الجدول أدناه بعض الأمثلة، وقد استُخدمت فيه بعض القيم المبالغ فيها لتأكيد الاستنتاج القائل إن «المعاملات لا تزحزح الرتبة». فعندما يؤول $n$ إلى اللانهاية، تصبح هذه الثوابت ضئيلة.

الجدول   التعقيدات الزمنية المقابلة لأعداد مختلفة من العمليات

الأنواع الشائعة

وليكن حجم بيانات الإدخال $n$. ويوضح الشكل أدناه أنواع التعقيد الزمني الشائعة (مرتبة من الأدنى إلى الأعلى).

الرتبة الثابتة $O(1)$

لا يعتمد عدد العمليات في الرتبة الثابتة على حجم بيانات الإدخال $n$، أي إنه لا يتغير بتغير $n$.

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

/* الرتبة الثابتة */
func constant(n int) int {
	count := 0
	size := 100000
	for i := 0; i < size; i++ {
		count++
	}
	return count
}

/* الرتبة الثابتة */
function constant(n: number): number {
    let count = 0;
    const size = 100000;
    for (let i = 0; i < size; i++) count++;
    return count;
}

الرتبة الخطية $O(n)$

ينمو عدد العمليات في الرتبة الخطية خطياً مع حجم بيانات الإدخال $n$. وتظهر الرتبة الخطية عادةً في الحلقات أحادية الطبقة:

/* الرتبة الخطية */
func linear(n int) int {
	count := 0
	for i := 0; i < n; i++ {
		count++
	}
	return count
}

/* الرتبة الخطية */
function linear(n: number): number {
    let count = 0;
    for (let i = 0; i < n; i++) count++;
    return count;
}

عمليات مثل اجتياز المصفوفات واجتياز القوائم المترابطة لها تعقيد زمني $O(n)$، حيث $n$ طول المصفوفة أو القائمة المترابطة:

/* الرتبة الخطية (اجتياز مصفوفة) */
func arrayTraversal(nums []int) int {
	count := 0
	// عدد التكرارات يتناسب مع طول المصفوفة
	for range nums {
		count++
	}
	return count
}

/* الرتبة الخطية (اجتياز مصفوفة) */
function arrayTraversal(nums: number[]): number {
    let count = 0;
    // عدد التكرارات يتناسب مع طول المصفوفة
    for (let i = 0; i < nums.length; i++) {
        count++;
    }
    return count;
}

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

الرتبة التربيعية $O(n^2)$

ينمو عدد العمليات في الرتبة التربيعية تربيعياً مع حجم بيانات الإدخال $n$. وتظهر الرتبة التربيعية عادةً في الحلقات المتداخلة، حيث يكون التعقيد الزمني للحلقتين الخارجية والداخلية $O(n)$، فيكون التعقيد الزمني الإجمالي $O(n^2)$:

/* الرتبة الأسية */
func quadratic(n int) int {
	count := 0
	// عدد التكرارات يرتبط تربيعياً بحجم البيانات n
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			count++
		}
	}
	return count
}

/* الرتبة الأسية */
function quadratic(n: number): number {
    let count = 0;
    // عدد التكرارات يرتبط تربيعياً بحجم البيانات n
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            count++;
        }
    }
    return count;
}

يقارن الشكل أدناه التعقيدات الزمنية للرتب الثابتة والخطية والتربيعية.

وبأخذ الترتيب الفقاعي مثالاً، تنفّذ الحلقة الخارجية $n - 1$ مرة، وتنفّذ الحلقة الداخلية $n-1$ ثم $n-2$ ثم $\dots$ ثم $2$ ثم $1$ مرة، بمتوسط $n / 2$ مرة، فيكون التعقيد الزمني $O((n - 1) n / 2) = O(n^2)$:

/* الرتبة التربيعية (الترتيب الفقاعي) */
func bubbleSort(nums []int) int {
	count := 0 // عدّاد
	// الحلقة الخارجية: الجزء غير المرتب هو [0, i]
	for i := len(nums) - 1; i > 0; i-- {
		// الحلقة الداخلية: بدّل أكبر عنصر في الجزء غير المرتب [0, i] إلى الطرف الأيمن من ذلك الجزء
		for j := 0; j < i; j++ {
			if nums[j] > nums[j+1] {
				// بدّل nums[j] وnums[j + 1]
				tmp := nums[j]
				nums[j] = nums[j+1]
				nums[j+1] = tmp
				count += 3 // تبديل العنصر يتضمن 3 عمليات وحدة
			}
		}
	}
	return count
}

/* الرتبة التربيعية (الترتيب الفقاعي) */
function bubbleSort(nums: number[]): number {
    let count = 0; // عدّاد
    // الحلقة الخارجية: الجزء غير المرتب هو [0, i]
    for (let i = nums.length - 1; i > 0; i--) {
        // الحلقة الداخلية: بدّل أكبر عنصر في الجزء غير المرتب [0, i] إلى الطرف الأيمن من ذلك الجزء
        for (let j = 0; j < i; j++) {
            if (nums[j] > nums[j + 1]) {
                // بدّل nums[j] وnums[j + 1]
                let tmp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = tmp;
                count += 3; // تبديل العنصر يتضمن 3 عمليات وحدة
            }
        }
    }
    return count;
}

الرتبة الأسية $O(2^n)$

يُعدّ «انقسام الخلايا» البيولوجي مثالاً نموذجياً على النمو بالرتبة الأسية: فالحالة الابتدائية خلية واحدة، وبعد جولة انقسام واحدة تصبح $2$، وبعد جولتين تصبح $4$، وهكذا؛ وبعد $n$ جولة من الانقسام توجد $2^n$ خلية.

يحاكي الشكل أدناه والشيفرة التالية عملية انقسام الخلايا، بتعقيد زمني $O(2^n)$. لاحظ أن المدخل $n$ يمثّل عدد جولات الانقسام، وأن القيمة المعادة count تمثّل العدد الإجمالي للانقسامات.

/* الرتبة الأسية (تنفيذ بحلقة) */
func exponential(n int) int {
	count, base := 0, 1
	// تنقسم الخلايا إلى خليتين في كل جولة، فتكوّن المتتالية 1, 2, 4, 8, ..., 2^(n-1)
	for i := 0; i < n; i++ {
		for j := 0; j < base; j++ {
			count++
		}
		base *= 2
	}
	// count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
	return count
}

/* الرتبة الأسية (تنفيذ بحلقة) */
function exponential(n: number): number {
    let count = 0,
        base = 1;
    // تنقسم الخلايا إلى خليتين في كل جولة، فتكوّن المتتالية 1, 2, 4, 8, ..., 2^(n-1)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < base; j++) {
            count++;
        }
        base *= 2;
    }
    // count = 1 + 2 + 4 + 8 + .. + 2^(n-1) = 2^n - 1
    return count;
}

وفي الخوارزميات الفعلية، تظهر الرتبة الأسية غالباً في الدوال التعاودية. فمثلاً، في الشيفرة التالية، تنقسم الدالة تعاودياً إلى قسمين، وتتوقف بعد $n$ انقسام:

/* الرتبة الأسية (تنفيذ تعاودي) */
func expRecur(n int) int {
	if n == 1 {
		return 1
	}
	return expRecur(n-1) + expRecur(n-1) + 1
}

/* الرتبة الأسية (تنفيذ تعاودي) */
function expRecur(n: number): number {
    if (n === 1) return 1;
    return expRecur(n - 1) + expRecur(n - 1) + 1;
}

نمو الرتبة الأسية سريع جداً، وهو شائع في الطرق الاستنفادية (البحث الشامل، والتتبّع الرجعي، وغيرها). وبالنسبة إلى المسائل ذات أحجام البيانات الكبيرة، لا تُقبل الرتبة الأسية، وتتطلب عادةً حلولاً بالبرمجة الديناميكية أو الخوارزميات الجشعة.

الرتبة اللوغاريتمية $O(\log n)$

وبالمقابل للرتبة الأسية، تعكس الرتبة اللوغاريتمية حالة «التنصيف في كل جولة». وليكن حجم بيانات الإدخال $n$. وبما أنه يُنصَّف في كل جولة، فعدد دورات الحلقة هو $\log_2 n$، وهو الدالة العكسية لـ$2^n$.

يحاكي الشكل أدناه والشيفرة التالية عملية «التنصيف في كل جولة»، بتعقيد زمني $O(\log_2 n)$، ويُختصر إلى $O(\log n)$:

/* الرتبة اللوغاريتمية (تنفيذ بحلقة) */
func logarithmic(n int) int {
	count := 0
	for n > 1 {
		n = n / 2
		count++
	}
	return count
}

/* الرتبة اللوغاريتمية (تنفيذ بحلقة) */
function logarithmic(n: number): number {
    let count = 0;
    while (n > 1) {
        n = n / 2;
        count++;
    }
    return count;
}

وعلى غرار الرتبة الأسية، تظهر الرتبة اللوغاريتمية أيضاً في الدوال التعاودية. وتشكّل الشيفرة التالية شجرة تعاود ارتفاعها $\log_2 n$:

/* الرتبة اللوغاريتمية (تنفيذ تعاودي) */
func logRecur(n int) int {
	if n <= 1 {
		return 0
	}
	return logRecur(n/2) + 1
}

/* الرتبة اللوغاريتمية (تنفيذ تعاودي) */
function logRecur(n: number): number {
    if (n <= 1) return 0;
    return logRecur(n / 2) + 1;
}

تظهر الرتبة اللوغاريتمية عادةً في الخوارزميات القائمة على استراتيجية التقسيم والتغلب، وتعكس فكرة تقسيم المسألة وتبسيطها مراراً. وهي تنمو ببطء، وهي التعقيد الزمني المثالي بعد الرتبة الثابتة.

الرتبة الخطية اللوغاريتمية $O(n \log n)$

تظهر الرتبة الخطية اللوغاريتمية عادةً في الحلقات المتداخلة، حيث يكون التعقيد الزمني لطبقتي الحلقة $O(\log n)$ و$O(n)$ على التوالي. والشيفرة ذات الصلة كما يلي:

/* الرتبة الخطية اللوغاريتمية */
func linearLogRecur(n int) int {
	if n <= 1 {
		return 1
	}
	count := linearLogRecur(n/2) + linearLogRecur(n/2)
	for i := 0; i < n; i++ {
		count++
	}
	return count
}

/* الرتبة الخطية اللوغاريتمية */
function linearLogRecur(n: number): number {
    if (n <= 1) return 1;
    let count = linearLogRecur(n / 2) + linearLogRecur(n / 2);
    for (let i = 0; i < n; i++) {
        count++;
    }
    return count;
}

يوضح الشكل أدناه كيف تنشأ الرتبة الخطية اللوغاريتمية. فكل مستوى من الشجرة الثنائية يحتوي في المجموع على $n$ عملية، وللشجرة $\log_2 n + 1$ مستوى، فيكون التعقيد الزمني $O(n \log n)$.

التعقيد الزمني لخوارزميات الترتيب السائدة هو عادةً $O(n \log n)$، مثل الترتيب السريع وترتيب الدمج والترتيب بالكومة.

الرتبة العاملية $O(n!)$

تقابل الرتبة العاملية مسألة «التباديل» الرياضية. فبمعطى $n$ عنصراً مختلفاً، أوجد جميع مخططات التباديل الممكنة؛ وعدد المخططات هو:

يُنفَّذ المضروب عادةً بالتعاود. وكما هو موضح في الشكل أدناه والشيفرة التالية، يتفرع المستوى الأول إلى $n$ فرعاً، ويتفرع المستوى الثاني إلى $n - 1$ فرعاً، وهكذا، حتى المستوى $n$ حيث يتوقف التفرع:

/* الرتبة العاملية (تنفيذ تعاودي) */
func factorialRecur(n int) int {
	if n == 0 {
		return 1
	}
	count := 0
	// التفرع من 1 إلى n
	for i := 0; i < n; i++ {
		count += factorialRecur(n - 1)
	}
	return count
}

/* الرتبة العاملية (تنفيذ تعاودي) */
function factorialRecur(n: number): number {
    if (n === 0) return 1;
    let count = 0;
    // التفرع من 1 إلى n
    for (let i = 0; i < n; i++) {
        count += factorialRecur(n - 1);
    }
    return count;
}

لاحظ أنه بما أن $n! > 2^n$ دائماً عندما $n \geq 4$، فإن الرتبة العاملية تنمو أسرع من الرتبة الأسية، وهي أيضاً غير مقبولة لأجل $n$ الكبيرة.

أسوأ التعقيدات الزمنية وأفضلها والمتوسطة

كفاءة الزمن في الخوارزمية ليست ثابتة غالباً، بل ترتبط بتوزيع بيانات الإدخال. لنفترض أننا ندخل مصفوفة nums طولها $n$، حيث تتكوّن nums من الأعداد من $1$ إلى $n$، ويظهر كل عدد مرة واحدة فقط، لكن ترتيب العناصر مبعثر عشوائياً. والمطلوب إعادة فهرس العنصر $1$. ويمكننا استخلاص الاستنتاجات التالية.

• عندما تكون nums = [?, ?, ..., 1]، أي عندما يكون العنصر الأخير هو $1$، يلزم اجتياز المصفوفة كاملة، فيبلغ التعقيد الزمني في أسوأ حالة $O(n)$.
• وعندما تكون nums = [1, ?, ?, ...]، أي عندما يكون العنصر الأول هو $1$، فلا حاجة إلى مواصلة الاجتياز مهما كان طول المصفوفة، فيبلغ التعقيد الزمني في أفضل حالة $\Omega(1)$.

يقابل «التعقيد الزمني في أسوأ حالة» الحد الأعلى التقاربي للدالة، ويُرمز إليه بترميز $O$ الكبير. وبالمقابل، يقابل «التعقيد الزمني في أفضل حالة» الحد الأدنى التقاربي للدالة، ويُرمز إليه بترميز $\Omega$:

/* ابحث عن فهرس العدد 1 في المصفوفة nums */
func findOne(nums []int) int {
	for i := 0; i < len(nums); i++ {
		// عندما يكون العنصر 1 في رأس المصفوفة، نحصل على أفضل تعقيد زمني O(1)
		// عندما يكون العنصر 1 في ذيل المصفوفة، نحصل على أسوأ تعقيد زمني O(n)
		if nums[i] == 1 {
			return i
		}
	}
	return -1
}

/* ابحث عن فهرس العدد 1 في المصفوفة nums */
function findOne(nums: number[]): number {
    for (let i = 0; i < nums.length; i++) {
        // عندما يكون العنصر 1 في رأس المصفوفة، نحصل على أفضل تعقيد زمني O(1)
        // عندما يكون العنصر 1 في ذيل المصفوفة، نحصل على أسوأ تعقيد زمني O(n)
        if (nums[i] === 1) {
            return i;
        }
    }
    return -1;
}

ومن الجدير بالذكر أننا نادراً ما نستخدم التعقيد الزمني في أفضل حالة عملياً، لأنه لا يتحقق عادةً إلا باحتمال ضئيل جداً وقد يكون مضللاً بعض الشيء. أما التعقيد الزمني في أسوأ حالة فهو أكثر عملية لأنه يعطي قيمة أمان للكفاءة، مما يتيح لنا استخدام الخوارزمية بثقة.

ومن المثال أعلاه نرى أن التعقيد الزمني في أسوأ حالة وفي أفضل حالة ينشأ كلاهما فقط في ظل توزيعات إدخال معينة، قد تحدث باحتمال منخفض جداً وقد لا تعكس كفاءة تشغيل الخوارزمية انعكاساً حقيقياً. وفي المقابل، يستطيع التعقيد الزمني المتوسط أن يعكس كفاءة تشغيل الخوارزمية في ظل بيانات إدخال عشوائية، ويُرمز إليه بترميز $\Theta$.

وبالنسبة إلى بعض الخوارزميات، يمكننا اشتقاق الحالة المتوسطة في ظل توزيع بيانات عشوائي ببساطة. فمثلاً، في المثال أعلاه، بما أن مصفوفة الإدخال مبعثرة عشوائياً، فإن احتمال ظهور العنصر $1$ عند أي فهرس متساوٍ، لذا يكون متوسط عدد دورات الحلقة في الخوارزمية نصف طول المصفوفة $n / 2$، فيكون التعقيد الزمني المتوسط $\Theta(n / 2) = \Theta(n)$.

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