ترميز O الكبير
كلمة واحدة تصف كيف ستتصرف خوارزميتك حين تصبح البيانات مليونًا. ⏱ نحو 30 دقيقة.
- تشرح الغرض من ترميز
Oالكبير. - تميّز التعقيدات الشائعة من
O(1)إلىO(2ⁿ) وترتبها. - تبسّط التعبير بحذف الثوابت والحدود الصغرى.
- تقدّر تعقيد مقطع كود من بنية حلقاته.
١لماذا ترميز O؟
لا نريد أن نقول «تستغرق 3 ثوانٍ»، فهذا يعتمد على الجهاز. نريد أن نصف كيف ينمو عدد العمليات حين يكبر حجم المدخل n. ترميز O الكبير Big O يعطي هذا الوصف في كلمة واحدة، ويركز على الحالة الأسوأ.
٢التعقيدات الشائعة
| الترميز | الاسم | مثال | مضاعفة n تجعل العمل… |
|---|---|---|---|
O(1) | ثابت | الوصول إلى a[5]، والبحث في dict | كما هو |
O(log n) | لوغاريتمي | البحث الثنائي | يزيد خطوة واحدة |
O(n) | خطي | البحث الخطي، ومجموع القائمة | يتضاعف |
O(n log n) | شبه خطي | الترتيب بالدمج، و sorted | يتضاعف وأكثر قليلًا |
O(n²) | تربيعي | مقارنة كل عنصر بكل عنصر، والترتيب الفقاعي | ×4 |
O(2ⁿ) | أُسّي | تجربة كل المجموعات الجزئية | يتربع! (غير عملي) |
import mathprint(f"{'n':>8} {'log n':>6} {'n log n':>9} {'n²':>14}")for n in [10, 100, 1000, 10000, 100000]: print(f"{n:>8} {round(math.log2(n)):>6} {round(n * math.log2(n)):>9} {n * n:>14}")
٣قاعدتان للتبسيط
O يصف النمو مع البيانات الكبيرة جدًّا، لذلك نهمل ما لا يؤثر حين يكبر n:
| القاعدة | مثال |
|---|---|
| 1. احذف الثوابت: الضرب في رقم ثابت لا يغيّر شكل النمو. | 3n + 5 ← O(n)، و n / 2 ← O(n) |
| 2. أبقِ الحد الأكبر فقط: الحدود الأصغر تختفي مع n الكبير. | n² + 100n + 7 ← O(n²) |
# لماذا نهمل 100n أمام n²؟for n in [10, 1000, 100000]: big = n * n small = 100 * n print(n, "| n²:", big, "| 100n:", small, "| نسبة 100n من المجموع:", round(small / (big + small) * 100, 2), "%")
٤اقرأ التعقيد من الكود
| الكود | التعقيد | السبب |
|---|---|---|
x = a[0] + a[-1] | O(1) | عدد ثابت من العمليات مهما كان طول a |
for x in a: total += x | O(n) | مرور واحد على n عنصر |
for x in a: for y in a: … | O(n²) | n دورة داخل n دورة |
for x in a: … ثم for y in a: … | O(n) | حلقتان متتاليتان: 2n ← O(n) |
while n > 1: n = n // 2 | O(log n) | n ينقسم نصفين في كل دورة |
sorted(a) | O(n log n) | خوارزمية Timsort |
٥O و Ω و Θ
للاطلاع: يستخدم المختصون ثلاثة رموز. O حد أعلى (لن تكون أسوأ من هذا)، و Ω أوميغا حد أدنى (لن تكون أفضل من هذا)، و Θ ثيتا حين يتطابقان. في الحياة العملية حين يقول المبرمج «O(n)» يقصد غالبًا الحالة الأسوأ كما في هذا المقرر.
توقّع وتحقّق
بسّط: 5n² + 3n + 20
البحث الثنائي:
حلقتان متداخلتان على القائمة نفسها:
n × n.الوصول إلى a[1000]:
الخلاصة
Oيصف نمو العمليات معn، مستقلًّا عن الجهاز، وللحالة الأسوأ غالبًا.- الترتيب:
1 < log n < n < n log n < n² < 2ⁿ. - احذف الثوابت، وأبقِ الحد الأكبر.
- متتالية تُجمع، ومتداخلة تُضرب، والتنصيف
log n.
تحدٍّ برمجي: صنّف الدوال
متوسطلكل دالة من الثلاث: عدّ عملياتها بعدّاد لـ n = 8 و n = 16، واطبع النسبة بين العددين، ثم اطبع تعقيدها.
- f1: حلقة واحدة على n. و f2: حلقتان متداخلتان. و f3: نقسم n على 2 حتى يصبح 1.
- كل دالة تُرجع عدد مرات تنفيذ جسم الحلقة الداخلية.
- اطبع لكل دالة: الاسم، والعددين، والنسبة، والتعقيد، مثل:
f1 8 16 2.0 O(n)
ابدأ من هذا الكود، واضغط ▶ شغّل هنا لتكتب حلّك وتجرّبه مباشرة:
def f1(n): c = 0 for i in range(n): c += 1 return c # اكتب f2 و f3 ثم اطبع
💡 تلميح 1
f3: while n > 1: n = n // 2💡 تلميح 2
f(16) / f(8). لاحظ: 2 ثم 4 ثم 1.33حاول بنفسك أولًا؛ للمسألة أكثر من حلّ صحيح.
def f1(n): c = 0 for i in range(n): c += 1 return c def f2(n): c = 0 for i in range(n): for j in range(n): c += 1 return c def f3(n): c = 0 while n > 1: n = n // 2 c += 1 return c for name, f, big in [("f1", f1, "O(n)"), ("f2", f2, "O(n²)"), ("f3", f3, "O(log n)")]: print(name, f(8), f(16), f(16) / f(8), big)