كفاءة الخوارزميات
ما سنفعله
- يمكن لكلا البرنامجين أن يكونا صحيحين ولكن يستغرقا وقتًا مختلفًا تمامًا.
- تركز هذه الدرس على الكفاءة: كيف يتزايد حجم العمل مع زيادة حجم المدخلات.
- اقرأ وأفكر في الأفكار؛ ثم عدة مهام قصيرة تسمح لك بـ عدّ الخطوات بنفسك.
عدّ العمل
- نقيس الخوارزمية بـ عدد الخطوات التي تنفذها، وليس بالثواني.
- خطوات الثواني تعتمد على جهاز الكمبيوتر؛ عدّ الخطوات لا يعتمد عليه.
- مدخلات أكبر تعني عادةً خطوات أكثر. السؤال هو كم أكثر.
وقت التشغيل المعقول مقابل غير المعقول
- الوقت المعقول يعني أن عدد الخطوات يتزايد بشكل كثير حدودي، أو ببطء أكثر: ثابت، خطي، تربيعي أو مكعب.
- حلقة واحدة هي خطية. وحلقة داخل حلقة أخرى هي تربيعية (n × n). التربيع يتزايد أسرع من الخطي، ولا يزال يُعتبر وقتاً معقولاً.
- الوقت غير المعقول يعني نمواً أسيًا أو مضروبياً. زيادة طفيفة في المدخلات تجعل العمل يرتفع بشكل هائل.
Input size: 10 20 40
Search a list: 10 20 40 (linear - reasonable)
Nested loops: 100 400 1,600 (square - still reasonable)
Try all orders: 3,628,800 ... 48 digits (factorial - unreasonable)
عرض توضيحي صغير: عدّ الخطوات
- أدناه نعد المقارنات التي يقوم بها البحث الخطي.
- العدد ينمو خطوة بخطوة مع حجم القائمة — نمو بطيء ومستقر.
- حاول تغيير الحجم لترى العدد يتبعه.
def count_steps(n):
steps = 0
data = list(range(n))
target = -1 # not in the list, so we scan everything
for item in data:
steps = steps + 1
if item == target:
break
return steps
print(count_steps(10))
print(count_steps(20))
print(count_steps(40))
عندما لا يكون السرعة كافية
- بعض المشاكل ليس لها خوارزميات معروفة تعمل في وقت معقول.
- طريقة دقيقة قد تحاول جميع الترتيبات. هذا نمو مضروبي، لذا فهو غير معقول للمدخلات الكبيرة.
- الخوارزمية التقريبية هي اختصار يمكنه إعطاء إجابة كافية. لا يوجد ضمان بأنها الأفضل. لا تحتاج إلى حفظ خوارزمية تقريبية محددة.
مشاكل غير قابلة للحل
- أسوأ من البطء: بعض المشاكل لا يمكن حلها بأي خوارزمية على الإطلاق.
- تسمى هذه المشاكل مشاكل غير قابلة للحل.
- مهما زادت سرعة أجهزة الكمبيوتر، لن يتمكن أي برنامج من إعطاء الإجابة الصحيحة دائمًا.
Reasonable : constant, linear, square or cube growth
Unreasonable : exponential or factorial growth
Undecidable : no algorithm can solve it for every input
أفكار رئيسية للتذكر
- الكفاءة تتعلق بكيفية نمو عدد الخطوات مع حجم المدخلات، وليس بعدد الثواني التي تستغرقها حاسوب ما.
- النمو كثير الحدود أو أقل يعتبر وقتاً معقولاً. الحلقة المتداخلة (n × n) لا تزال معتبرة وقتاً معقولاً.
- النمو الأسي أو المضاعفي يعتبر غير معقول. بعض المسائل أيضاً غير قابلة للحل.
أخطاء شائعة
- وصف الحلقة المتداخلة بأنها غير معقول هو خطأ. نمو التربيع والمكعب لا يزالان يمثلان وقتاً معقولاً.
- استخدام تدوين Big-O الرسمي كقاعدة للامتحان. لا يتم اختبار Big-O. الشرط هو أن يكون الخط متعدد الحدود أو أقل، مقابل الأسي أو المضاعف.
الآن جرب بنفسك
- اكتب دوال صغيرة تعدّ الخطوات لتشعر بكيفية نمو العمل.
- قارن حلقة واحدة، وحلقة متداخلة، و"تجربة جميع الترتيبات". الحلقة المتداخلة لا تزال تمثل وقتاً معقولاً. اضغط على تحقق من الإجابة.
كيف تتوسع الخوارزميات
نمو التربيع أسرع من الخط المستقيم، ولا يزال معقولاً من حيث الوقت. نمو المضروب غير معقول.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب scan_compares(data, target) تُرجع كم عدد المقارنات التي يقوم بها البحث الخطي. قارن كل عنصر بـ target، احسب واحد في كل مرة، وتوقف فوراً عند العثور عليه. إن لم يكن في القائمة، قارنت كل عنصر. مثال: scan_compares([5, 8, 2], 8) → 2.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب pair_count(n) تستخدم حلقة داخل حلقة (كلاهما على range(n)) وتُرجع كم مرة تُنفَّذ الخطوة الداخلية. هذا هو n × n. مثال: pair_count(3) → 9. هذا ينمو أسرع بكثير من حلقة واحدة.
اضغط تشغيل لرؤية المخرجات هنا.
الصعوبة 3/5 · 200 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
اكتب count_orderings(n) الذي يُرجع عدد الترتيبات المختلفة التي يمكن وضع n عناصر فيها — أي 1 × 2 × ... × n (المضروب n!). count_orderings(0) قيمته 1. مثال: count_orderings(3) → 6. لاحظ كيف تنمو بسرعة: count_orderings(10) يتجاوز 3 مليون.
اضغط تشغيل لرؤية المخرجات هنا.