الحالة الأفضل والأسوأ والمتوسطة

١الخوارزمية نفسها، وأعمال مختلفة

البحث الخطي: نفحص العناصر من الأول حتى نجد المطلوب. كم مقارنة يحتاج؟ يعتمد على مكان العنصر. جرّب المحاكاة مرتين: مرة لعنصر في البداية، ومرة لعنصر غير موجود:

٢ثلاث حالات نحللها

نتحقق من ذلك بالحساب. نبحث عن كل عنصر في قائمة من 10 عناصر، ونعدّ المقارنات:

def linear_search(a, x):    comparisons = 0    for v in a:        comparisons += 1        if v == x:            break    return comparisons a = list(range(1, 11))          # 10 عناصرcounts = [linear_search(a, x) for x in a]print("كل الحالات:", counts)print("الأفضل:", min(counts))print("الأسوأ:", max(counts))print("المتوسط:", sum(counts) / len(counts))

٣لماذا نهتم بالحالة الأسوأ أكثر؟

لأنها ضمان: مهما كان المدخل، لن تتجاوز الخوارزمية هذا العدد. نظام حجز الطيران لا يكفيه أن يكون سريعًا «في المتوسط»؛ يجب ألا يتعطل أبدًا في أسوأ يوم.

٤الحالات في خوارزمية ترتيب

الترتيب بالإدراج يُدخل كل عنصر في مكانه الصحيح في الجزء المرتب. شاهد كيف يختلف عمله على قائمة شبه مرتبة وعلى قائمة معكوسة:

def insertion_comparisons(a):    a = list(a)    count = 0    for i in range(1, len(a)):        j = i        while j > 0:            count += 1            if a[j - 1] > a[j]:                a[j - 1], a[j] = a[j], a[j - 1]                j -= 1            else:                break    return count n = 100print("مرتبة:", insertion_comparisons(range(n)))print("معكوسة:", insertion_comparisons(range(n, 0, -1)))

على قائمة مرتبة أصلًا: 99 مقارنة فقط (الحالة الأفضل). وعلى قائمة معكوسة: 4950 مقارنة (الحالة الأسوأ). الخوارزمية نفسها، والفرق 50 ضعفًا بسبب المدخل وحده.