الدرس 10 · الوحدة 5: تحليل الأداء الزمني للخوارزميات

تعقيد الحلقات والتعقيد اللوغاريتمي

كيف تقرأ التعقيد من شكل الكود، وتكشف الحلقة المخفية في سطر بريء. ⏱ نحو 35 دقيقة.

بعد هذا الدرس ستستطيع أن:

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

١الحلقة الداخلية تعتمد على الخارجية

كثيرًا ما تبدأ الحلقة الداخلية من موقع الخارجية، لتقارن كل زوج مرة واحدة فقط:

main.py

def count_pairs(n):    c = 0    for i in range(n):        for j in range(i + 1, n):    # تبدأ بعد i            c += 1    return c for n in [10, 100, 1000]:    print(n, count_pairs(n), n * (n - 1) // 2)

Shell×

>>> %Run main.py

10 45 45

100 4950 4950

1000 499500 499500

>>>

العدد n(n−1)/2 = n²/2 − n/2. احذف الثوابت والحد الأصغر: ما زال O(n²). نصف العمل، لكن النمو نفسه.

٢حلقة داخلية بعدد ثابت

إن كانت الحلقة الداخلية تدور عددًا ثابتًا لا يعتمد على n، فالمجموع خطي:

main.py

days = ["الأحد", "الإثنين", "الثلاثاء", "الأربعاء", "الخميس"]students = ["أحمد", "سارة", "خالد"] c = 0for s in students:          # n طالب    for d in days:          # 5 أيام دائمًا        c += 1print(c)   # 5n ← O(n)

Shell×

>>> %Run main.py

>>>

٣التعقيد اللوغاريتمي: التنصيف والمضاعفة

كل حلقة يتضاعف فيها المتغير أو ينقسم على عدد ثابت تدور O(log n) مرة:

main.py

def halving(n):    steps = 0    while n > 1:        n //= 2        steps += 1    return steps def doubling(n):    steps, i = 0, 1    while i < n:        i *= 2        steps += 1    return steps for n in [8, 1024, 1_000_000]:    print(n, halving(n), doubling(n))

Shell×

>>> %Run main.py

8 3 3

1024 10 10

1000000 19 20

>>>

مليون في 20 خطوة. اللوغاريتم بطيء النمو جدًّا، ولذلك O(log n) قريبة من الثابت عمليًّا.

٤n log n: من أين تأتي؟

الترتيب بالدمج يقسم القائمة نصفين مرارًا، فيتكون نحو log₂ n مستوى. وفي كل مستوى ندمج n عنصرًا كلها. المجموع: n في log n:

main.py

comparisons = 0def merge_sort(a):    global comparisons    if len(a) <= 1:        return a    mid = len(a) // 2    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])    out, i, j = [], 0, 0    while i < len(left) and j < len(right):        comparisons += 1        if left[i] <= right[j]: out.append(left[i]); i += 1        else: out.append(right[j]); j += 1    return out + left[i:] + right[j:] import math, randomrandom.seed(7)for n in [1000, 2000, 4000]:    comparisons = 0    merge_sort(random.sample(range(10**6), n))    print(n, comparisons, "| n log n ≈", round(n * math.log2(n)))

Shell×

>>> %Run main.py

1000 8697 | n log n ≈ 9966

2000 19374 | n log n ≈ 21932

4000 42841 | n log n ≈ 47863

>>>

٥التعقيد المخفي داخل سطر واحد

انتبه: بعض الأسطر القصيرة في بايثون تخفي حلقة كاملة:

السطر	التعقيد الحقيقي
`x in my_list`	`O(n)`: يبحث بحثًا خطيًّا
`x in my_set` و `x in my_dict`	`O(1)` في المتوسط
`my_list.insert(0, x)` و `my_list.pop(0)`	`O(n)`: يزيح كل العناصر
`my_list.append(x)` و `my_list.pop()`	`O(1)`
`sorted(a)` و `a.sort()`	`O(n log n)`
`a[2:8]` (تقطيع)	`O(k)`: ينسخ k عنصرًا

main.py

# يبدو O(n)، لكنه O(n²): البحث في قائمة داخل حلقةdef has_duplicates_slow(a):    seen = []    for x in a:        if x in seen:      # O(n) داخل حلقة O(n)            return True        seen.append(x)    return False # التصحيح: مجموعة بدل القائمة ← O(n)def has_duplicates_fast(a):    seen = set()    for x in a:        if x in seen:      # O(1)            return True        seen.add(x)    return False data = list(range(5000)) + [42]print(has_duplicates_slow(data), has_duplicates_fast(data))

Shell×

>>> %Run main.py

True True

>>>

٦تعقيد الدوال العودية

الدالة	كم استدعاءً؟	التعقيد
المضروب `factorial(n - 1)`	n استدعاء، كل واحد عمله ثابت	`O(n)`
البحث الثنائي العودي	كل استدعاء ينصّف المجال	`O(log n)`
الترتيب بالدمج	log n مستوى، وفي كل مستوى `O(n)`	`O(n log n)`
فيبوناتشي الساذج `fib(n-1) + fib(n-2)`	كل استدعاء يولّد استدعاءين	`O(2ⁿ)`؛ سنصلحه في الدرس 21

توقّع وتحقّق

for i in range(n): for j in range(i, n):

نحو n²/2.

i = 1; while i < n: i *= 3

مضاعفة بثابت.

حلقة على n وفي داخلها x in a_list:

in على قائمة خطي.

حلقة على n طالب وفي داخلها 7 أيام:

7n.

الخلاصة

j من i + 1 ما زالت O(n²)، والحلقة بعدد ثابت لا تضيف n.
التنصيف أو المضاعفة ← O(log n).
الدمج: log n مستوى × n عملية ← O(n log n).
in على القائمة O(n)، وعلى set و dict O(1).
العودية: عدد الاستدعاءات × عمل كل استدعاء.

تحدٍّ برمجي: اكشف O(n²) المخفية وأصلحها

متقدم

الدالة common تجد العناصر المشتركة بين قائمتين، لكنها O(n²). أعد كتابتها لتكون O(n)، وتأكد أن الناتج نفسه.

المطلوب:

استخدم مجموعة set لإحدى القائمتين.
حافظ على ترتيب العناصر كما في القائمة a.
اطبع الناتج: [3, 9, 15]

ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:

main.py

def common(a, b):    result = []    for x in a:        if x in b:            result.append(x)    return result a = [3, 4, 9, 11, 15]b = [15, 3, 8, 9, 20]print(common(a, b))

المطلوب×

[3, 9, 15]

💡 تلميح 1

bset = set(b) مرة واحدة قبل الحلقة.

💡 تلميح 2

x in bset تصبح O(1).

حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.

main.py

def common(a, b):    bset = set(b)    result = []    for x in a:        if x in bset:            result.append(x)    return result a = [3, 4, 9, 11, 15]b = [15, 3, 8, 9, 20]print(common(a, b))

انتقل إلى تقييم الدرساختيار من متعدد، وصح وخطأ، وأكمل الفراغ، وتتبّع الناتج.ابدأ التقييم ←

📝 معلم؟ أرسل ملاحظة للمؤلف عن هذا الدرس