تشرح هذه الخريطة كيف احسب كلفة الخوارزمية: كم عملية تُجري بحسب حجم البيانات، n، وكيف يتزايد عندما يتزايد n.
الكلفة هي دالة من n. الثواني تعتمد على الحاسوب؛ أما العمليات فلا.
اضغط كل مربع لترى شرحه. والأسهم ← → (أو الأزرار في الأسفل) تنتقل إلى التالي و Esc يغلقها. وبعد أن تراها يظهر ✓؛ اضغطه لإزالته. والمربعات التي فيها «?» تخص مستويات أخرى.
تشرح هذه الخريطة كيف احسب كلفة الخوارزمية: كم عملية يُجري البرنامج. لكل مربع شرح قصير، وفي بعض الحالات تمرين.
الخوارزمية أكثر سريع عندما يُجري عمليات أقل.
اضغط كل مربع لترى شرحه. والأسهم ← → تنتقل إلى التالي و Esc يغلقها. وبعد أن تراها يظهر ✓.
الصف الرابع ESO (للمتقدمين). نسخة مبسطة: قواعد الحساب، والترتيب بالنسبة إلى n، والبحث الثنائي. دون تدوين O(·) رسمي، ودون رسوم بيانية للخوارزميات، ودون مربع العمليات.
يتوافق مع: الرقمنة للصف الرابع (التفكير الحوسبي: المعياران 3.1 و3.2، خوارزميات منطقية وفعّالة).
نشاط مقترح: عدّ عمليات حلقة، ثم تحقق بالبحث الثنائي من عدد خطواته.
PTD-I · الصف الأول من البكالوريا. تُضاف قواعد الحساب (التسلسل والشرط والحلقة)، وتدوين O(·)، ورسوم النمو والزمن، والبحث الخطي، والفرز بالاختيار. لم تعد تجارب الزمن (ms) في المركز: ما يُقاس هو عدد العمليات.
يتوافق مع: البرمجة ومعالجة البيانات I: CEsp1 (تحليل الخوارزميات وتصميمها، المعيار 1.3 بشأن الكلفة الحوسبية) وCEsp3 (كفاءة العمليات وتعقيدها في بنى البيانات).
نشاط مقترح: بسرعة 10⁹ عملية في الثانية و n = 10⁶، احسب كم يستغرق البحث الخطي (n) والفقاعي (n(n−1)/2)، وقارن ذلك بالرسم البياني للزمن.
PTD-II · الصف الثاني من البكالوريا. المحتوى نفسه في PTD-I: قواعد الحساب، وتدوين O(·)، ورسوم النمو، وخوارزميات البحث والترتيب.
يتوافق مع: البرمجة ومعالجة البيانات II: CEsp1 (الخوارزميات والتفكير الحوسبي).
نشاط مقترح: قارن يدوياً البحث الخطي والثنائي مع n = 1 000 000 وبرّر الفرق.
المربعات التي فيها «?» مخفية في هذا المستوى: نقرة تكشفها وتُظهر علاقتها، ونقرة أخرى تفتح نافذتها، وبعد رؤيتها تُخفيها نقرة أخرى. والزر 🔗 ينسخ رابطاً فيه المستوى والمربعات المكشوفة.
المحدِّد المستوى يغيّر الخريطة وكل النوافذ. وفي العنوان يُحفظ المستوى (?edad=4eso, ptd1 أو ptd2) والمربعات المكشوفة (&ver=casos,fonts).
عندما نقول إن خوارزمية سريعة، يجب أن نحدد سريعة في ماذا. الثواني تعتمد على الحاسوب والنظام وما يعمل حالياً. لذلك نعدّ عمليات.
عندما تقارن خوارزميتين، اسأل نفسك: ما الذي ينمو وبأي مقدار?
تقيس الكلفة الحوسبية العمل الذي يؤديه البرنامج بحسب حجم البيانات (n. انظر إلى أمرين: الزمن (عدد العمليات) و الذاكرة (كم من المساحة تشغل).
الكلفة الحوسبية لخوارزمية هي عددعمليات أساسية الذي يُجريه بحسب حجم البيانات، n. الثواني تعتمد على الحاسوب؛ أما العمليات فلا.
العملية الأساسية (الإسناد أو الجمع أو المقارنة أو الوصول إلى موضع) تكلّف 1. وتُعدّ أسوأ حالة، وهذا ما يضمن النتيجة لأي بيانات.
| الدالة T(n) | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| n | 10 | 1 000 | 1 000 000 |
| n² | 100 | 1 000 000 | 1 000 000 000 000 |
الثواني لا تصلح لمقارنة الخوارزميات. عُدّ عمليات وانظر كيف تنمو عندما ينمو n.
الحجم n. تعتمد كل الصيغ على حجم واحد، n: عدد البيانات التي يستقبلها الخوارزمية. حدِّد n قبل العد (عدد العناصر أو الأرقام أو الصفوف، حسب المسألة).
ينفّذ البرنامج التعليمات واحدة تلو الأخرى. لحساب الكلفة اجمع التعليمات. وإذا وُجدت حلقة فاضرب في عدد مرات تكرارها.
التعليمة البسيطة تكلّف 1. الحلقة تضرب كلفة جسمها في عدد التكرارات.
يجمع البرنامج أربع بنى. وتُحسب الكلفة الإجمالية بتطبيق قاعدة على كل بنية.
| البنية | قاعدة الكلفة | مثال |
|---|---|---|
| تعليمة بسيطة | 1 | x ← x + 1 ← 1 |
| التسلسل | مجموع الكلفات | A؛ ثم B ← T(A) + T(B) |
| الشرط | الاختبار + المسار الأغلى | إذا … فإن … وإلا … ← 1 + أكبر(T₁, T₂) |
| حلقة | التكرارات × كلفة الجسم | من i = 1 إلى n: x ← x + 1 ← n |
عندما لا تعرف أي مسار من الشرط سيُنفَّذ، استخدم الأغلى: وهو أسوأ حالة.
كلفة الحلقة هي كلفة جسمها مضروبة في عدد التكرارات. عملية واحدة لا تُلاحَظ، أما مليون عملية فنعم.
| البنية | العمليات مع n = 1 000 | العمليات مع n = 1 000 000 |
|---|---|---|
| حلقة | 1 000 | 1 000 000 |
| حلقتان متداخلتان | 1 000 000 | 1 000 000 000 000 |
عُدّ عدد مرات تنفيذ الجسم الأعمق. حلقة من n خطوة تُجري n عملية؛ وحلقتان متداخلتان من n خطوة تُجريان n · n.
حلقتان متداخلتان هما O(n²)؛ حلقة، O(n).
بنية تبدو بسيطة («إنها مجرد حلقة») قد تُخفي بحثاً بداخلها. انظر دائماً إلى ما في داخل الحلقة.
الحلقة تكرر جسمها. والكلفة الإجمالية هي كلفة الجسم مضروبة في عدد التكرارات.
| البنية | العمليات مع n = 1 000 | العمليات مع n = 1 000 000 |
|---|---|---|
| حلقة | 1 000 | 1 000 000 |
| حلقتان متداخلتان (n · n) | 1 000 000 | 1 000 000 000 000 |
| حلقتان، والثانية حتى i | 500 500 | 500 000 500 000 |
الحلقة هي O(n). حلقتان متداخلتان هما O(n²). الحلقات المتداخلة التي تصل إلى i تُجري n(n+1)/2 خطوة: أيضاً O(n²)، لأننا نتجاهل الثابت ½.
بنية تبدو بسيطة («إنها مجرد حلقة») قد تُخفي بحثاً بداخلها. انظر دائماً إلى ما في داخل الحلقة.
يقارن الفرز الفقاعي الجيران ويبدّلهما إذا كانا بترتيب خاطئ. ويكرر المرور حتى لا يُجري أي تبديل. وهو الخوارزمية النموذجية لفهم الكلفة، لأن كل شيء فيه يمكن عدّه.
| n (البيانات) | المقارنات (أسوأ حالة) | التبديلات (المتوسط) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
كل مرور يضع أكبر قيمة في النهاية. مع n بيانة، يُجري المرور الأول n−1 مقارنة، والتالي n−2، وهكذا حتى 1. والمجموع في أسوأ حالة: n(n−1)/2.
لاحظ: إذا تضرب البيانات في 10, يتضاعف العمل بمقدار 100.
هذا هو O(n²). تتزايد المقارنات كمربع n.
يقارن الفرز الفقاعي كل زوج من الجيران ويبدّل المتجاورين الخاطئين. وبعد كل مرور يبقى أكبر قيمة في النهاية.
| n (البيانات) | المقارنات (أسوأ حالة) | التبديلات (المتوسط) |
|---|---|---|
| 10 | 45 | 22,5 |
| 100 | 4 950 | 2 475 |
| 1 000 | 499 500 | 249 750 |
| 10 000 | 49 995 000 | 24 997 500 |
يُجري المرور الأول n−1 مقارنة، والثاني n−2، وهكذا حتى 1. المجموع في أسوأ حالة: (n−1) + (n−2) + … + 1 = n(n−1)/2، أي O(n²).
رسم بياني للزمن: الزمن متناسب مع عدد العمليات. بسرعة 10⁹ عملية في الثانية، تستغرق 10⁶ عملية 1 ملّي ثانية.
إذا كانت القائمة مرتبة فلا حاجة إلى النظر فيها كلها. تنظر إلى الوسط وتستبعد النصف الذي لا يمكن أن يحوي ما تبحث عنه. كل خطوة تُنقص الحجم إلى النصف.
القائمة هي 1، 2، 3… n: لا حاجة إلى تخزينها كاملةً في الذاكرة، ولهذا يمكن التجربة مع مليار.
| n (البيانات) | خطوات الثنائي (أسوأ حالة) | مقارنات الخطي (أسوأ حالة) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
كل خطوة تُجري مقارنة واحدة وتستبعد النصف. والخطوات نحو log₂ n. لهذا فإن مليار بيانة تحتاج إلى 30 خطوة فقط.
هذا هو O(log n).
الثنائي يعمل فقط إذا كانت القائمة مرتبة. ترتيبها له كلفة أيضاً.
ينظر البحث الثنائي إلى وسط القائمة المرتبة ويستبعد النصف الذي لا يمكن أن يحتوي ما تبحث عنه. كل خطوة تقسم على 2.
القائمة هي 1، 2، 3… n. تُعدّ الخطوات فقط: لا حاجة إلى تخزينها في الذاكرة.
| n (البيانات) | خطوات (أسوأ حالة) | البحث الخطي (أسوأ حالة) |
|---|---|---|
| 1 000 | 10 | 1 000 |
| 1 000 000 | 20 | 1 000 000 |
| 1 000 000 000 | 30 | 1 000 000 000 |
كل خطوة تُنقص الحجم إلى النصف: بعد k خطوة يبقى n / 2ᵏ عنصراً. ولأن n / 2ᵏ = 1 عندما k = log₂ n، فإن الكلفة هي O(log n).
البحث الثنائي يعمل فقط إذا كانت القائمة مرتبة. ترتيبها له كلفة أيضاً.
رسم بياني للزمن: الزمن متناسب مع عدد العمليات. بسرعة 10⁹ عملية في الثانية، تستغرق 10⁶ عملية 1 ملّي ثانية.
عندما تنمو البيانات تنمو الكلفة بوتيرة معينة. والتدوين O(·) يحتفظ بهذا الإيقاع فقط ويتجاهل الثوابت.
يتزايد O(log n) ببطء شديد: عندما ينتقل n من 1 إلى 20 يصل إلى ≈ 4,3 فقط، بينما يصل O(n) إلى 20.
مع n صغير تبدو كل المنحنيات متقاربة؛ ابتداءً من n ≈ 10 ينفصل المنحنى التربيعي عن الباقي.
| الدالة | n = 10 | n = 1 000 | n = 1 000 000 |
|---|---|---|---|
| O(log n) | ≈ 3 | ≈ 10 | ≈ 20 |
| O(n) | 10 | 1 000 | 1 000 000 |
| O(n log n) | ≈ 33 | ≈ 10 000 | ≈ 20 000 000 |
| O(n²) | 100 | 1 000 000 | 1 000 000 000 000 |
O(1): الكلفة لا تعتمد على n. O(log n): كل خطوة تقسم على 2 (الثنائي). O(n): متناسبة مع n (البحث الخطي). O(n log n): نموذجية لخوارزميات الترتيب الجيدة. O(n²): حلقتان متداخلتان (الفقاعي، الاختيار).
عندما يُضرب n في 10: مع O(n) تُضرب الكلفة في 10؛ ومع O(n²) في 100؛ ومع O(log n) لا تتغير تقريباً.
تجاهل الثوابت والحدود الصغيرة: 3n² + 5n هي O(n²).
يشرح الترتيب بالنسبة إلى n كيف تنمو الكلفة عندما تنمو البيانات. وهي الفكرة الأهم في هذه الخريطة.
عندما يُضرب n في 10، تُضرب الكلفة O(n) في 10 أيضاً، لكن الكلفة O(n²) تُضرب في 100.
إذا كانت الكلفة O(n)، ينمو العمل بالقدر نفسه الذي تنمو به البيانات. وإذا كانت O(n²)، فإن مضاعفة البيانات تُضاعف العمل أربع مرات.
المهم هو كيف ينمو، لا العدد الدقيق للعمليات.
يمكن للخوارزمية نفسها أن تستغرق وقتاً أطول أو أقصر حسب البيانات. لذلك يميز التحليل ثلاث حالات: أفضل, متوسط و أسوأ.
| حالة | الفرز الفقاعي | الثنائي |
|---|---|---|
| أفضل | n−1 مقارنة (قائمة مرتبة بالفعل) | خطوة واحدة (الوسط هو المطلوب) |
| متوسط | ≈ n²/2 مقارنة | ≈ log₂ n خطوة |
| أسوأ | n(n−1)/2 مقارنة | ⌊log₂ n⌋ + 1 خطوة |
إذا كانت النسبة قريبة من 2 فالنمو خطي تقريباً؛ وإذا كانت قريبة من 4 فهو تربيعي. وضوضاء المتصفح تمنع الدقة التامة، لذلك يُؤخذ وسيط 3 تكرارات.
لتقييم خوارزمية يجب النظر إلى بيانات أسوأ حالة (تلك التي تجعله يعمل أكثر)، ولكن أيضاً الحالة المتوسطة، وهي عادةً الأكثر شيوعاً.
قياس واحد لحالة معينة لا يخبرك أيها الأسوأ. حلّل الحالة ثم قِس.
ينظر البحث الخطي إلى العناصر واحداً تلو الآخر حتى يجد ما تبحث عنه. وهو أبسط طريقة، ويُستخدم مرجعاً للمقارنة بالبحث الثنائي.
يُقارَن كل عنصر بالقيمة المطلوبة حتى يُعثر عليها أو يُصل إلى النهاية.
| حالة | المقارنات | مع n = 1 000 000 |
|---|---|---|
| أفضل (هو الأول) | 1 | 1 |
| متوسط (في المنتصف) | n / 2 | 500 000 |
| أسوأ (هو الأخير أو غير موجود) | n | 1 000 000 |
الكلفة هي O(n): يُفحص كل عنصر مرة واحدة على الأكثر.
عندما تذكر كلفة، قل أي حالة هي: الأفضل أو المتوسط أو الأسوأ.
رسم بياني للزمن: الزمن متناسب مع عدد العمليات. بسرعة 10⁹ عملية في الثانية، تستغرق 10⁶ عملية 1 ملّي ثانية.
الفرز بالاختيار يبحث عن الأصغر في الجزء غير المرتب ويضعه في المقدمة. كرّر ذلك حتى تُرتَّب القائمة كلها.
يبحث المرور الأول عن الأصغر بين n عنصراً (n−1 مقارنة) ويضعه في الموضع الأول. والمرور التالي يبحث بين n−1 عنصراً، وهكذا حتى الأخير.
| n (البيانات) | المقارنات (دائماً) |
|---|---|
| 10 | 45 |
| 100 | 4 950 |
| 1 000 | 499 500 |
المجموع: (n−1) + (n−2) + … + 1 = n(n−1)/2، أي O(n²) في جميع الحالات. ويُجري n−1 تبديلاً على الأكثر.
الفرز بالاختيار يُجري دائماً المقارنات نفسها؛ أما الفقاعي فيمكن أن يتوقف مبكراً إذا كانت القائمة مرتبة.
رسم بياني للزمن: الزمن متناسب مع عدد العمليات. بسرعة 10⁹ عملية في الثانية، تستغرق 10⁶ عملية 1 ملّي ثانية.
الفرز بالإدراج يأخذ كل عنصر ويضعه في مكانه الصحيح داخل الجزء المرتب.
في أسوأ حالة (قائمة معكوسة) تُجري n(n−1)/2 مقارنة: O(n²). في أفضل حالة (قائمة مرتبة بالفعل) تُجري n−1 فقط: O(n).
الإدراج سريع عندما تكون القائمة مرتبة تقريباً.
الفرز بالدمج يقسم القائمة إلى نصفين، ويرتب كل نصف ثم يدمجهما.
كل مستوى من التقسيمات يُجري n خطوة، وهناك log₂ n مستوى. والكلفة هي O(n log n) في جميع الحالات.
للقوائم الكبيرة تكون أسرع بكثير من الفقاعي.
القياس سهل أن يُجرى بشكل خاطئ. هذه أكثر الأخطاء شيوعاً وكيفية تجنّبها.
قبل أن تقول إن خوارزمية أسرع، اسأل نفسك: بأي بيانات، وعلى أي جهاز، وكم مرة قستُه.
اقرأ كل موقف واختر أي مفهوم يشرح الحالة. وإذا اخترت حالة موجودة أيضاً لكنها ليست الرئيسية، فسنخبرك بذلك.
يجمع برنامج مليون عدد داخل حلقة. أي مفهوم يفسر لماذا الكلفة مرتفعة؟
يجمع برنامج مليون عدد داخل حلقة. أي مفهوم يفسر لماذا الكلفة مرتفعة؟
تبحث عن العدد 42 في قائمة مرتبة من مليون عدد. تنظر إلى الوسط، وتستبعد النصف، وبعد نحو 20 خطوة تجده. ما هذه الخوارزمية؟
خوارزمية تمرّ على القائمة وتقارن الجيران وتبدّلهم. ومع القائمة المعكوسة تُجري n(n−1)/2 مقارنة. ما هذه الخوارزمية؟
تستغرق خوارزمية 4 أضعاف الزمن عندما تضاعف البيانات. أي مفهوم يصف نمو كلفتها؟
تبحث عن عدد في قائمة غير مرتبة من n عنصراً، وتقارنه بكل عنصر حتى تجده. ما هذه الخوارزمية؟
تبحث خوارزمية عن الأصغر في الجزء غير المرتب وتضعه في المقدمة. وتُجري n(n−1)/2 مقارنة حتى لو كانت القائمة مرتبة بالفعل. ما هذه الخوارزمية؟
تجمع هذه الخريطة مفاهيم كلاسيكية في تحليل الخوارزميات وأهداف المنهج في جزر البليار. وهنا يمكنك التحقق منها والتعمق فيها.