كفاءة الخوارزمية
| English | العربية |
|---|---|
| Algorithmic efficiency/ˌælɡəˈrɪθmɪk ɪˈfɪʃənsi/ | كفاءة الخوارزميات |
| slow/sləʊ/ | بطيء |
| steps/steps/ | خطوات |
| reasonable/ˈriːzənəbl/ | معقول |
| unreasonable/ʌnˈriːzənəbl/ | غير معقول |
| heuristic/hjuːˈrɪstɪk/ | خوارزمية استدلالية (heuristic) |
التصحيح ليس دائماً كافياً
- يمكن لخوارزميتين أن تكونا صحيحتين، مع أن إحداهما قد تكون أفضل بكثير للاستخدام.
- الكفاءة الخوارزمية تقارن الخوارزميات حسب الموارد التي تستخدمها — أساساً الوقت والذاكرة.
- خوارزمية صحيحة ولكن بطيئة يمكن أن تكون عديمة الفائدة على المدخلات الكبيرة.
- لذلك نحتاج إلى طريقة لمقارنة كيف تتوسع.*
تكافؤ الخوارزميات يقارن بين الخوارزميات عبر:
الكفاءة تتعلق بالوقت والذاكرة كلما كبر المدخل.
عدّ الخطوات بينما تنمو n
- قدر عدد الخطوات التي تستغرقها الخوارزمية بينما ينمو حجم مدخلاتها $n$.
- البحث الخطي يستهلك حوالي $n$ خطوات؛ البحث الثنائي حوالي $\log_2 n$؛ مقارنة كل زوج حوالي $n^2$.
- عندما يصبح $n$ كبيراً، تصبح هذه الفروقات هائلة.
- شكل النمو مهم جداً مقارنة بالميقاف الزمني.
كيف ينمو وقت التنفيذ مع n
اسحب الشريحة n وقارن المنحنيات: يظل log n مسطحاً تقريباً، يرتفع n بانتظام، وينفجر n². ولهذا نقارن الخوارزميات حسب كيفية تكيفها مع الحجم، وليس باستخدام ساعة توقيت.
طابق كل خوارزمية بعددها التقريبي للخطوات لحجم مدخل n.
تحدد هذه معدلات النمو أي خوارزمية قابلة للتوسع.
أي نمو يُعتبر غير معقول كلما كبرت n؟
النمو الأسي يصبح ببطء كبير جداً بسرعة فائقة.
عندما يكون الإجابة الدقيقة بطيئة جداً، فإن ______ يجد حلاً جيداً بما يكفي بسرعة.
الخوارزمية الاستدلالية تتنازل عن إجابة مثالية مقابل السرعة.
المعقول وغير المعقول
- نفصل بين وقت تشغيل معقول ووقت غير معقول.
- تقريباً، النمو مثل $n$ أو $n^2$ يعتبر معقولاً؛ مضاعفة الخطوات لكل عنصر إضافي (مثل $2^n$) ليس كذلك.
- عندما يكون الإجابة الدقيقة بطيئة جداً، استخدم الاستدراك — حلاً جيداً بما يكفي تم العثور عليه بسرعة.
- ليس مثالياً، لكنه مفيد عندما يكون المثالي مستحيلاً في الوقت المحدد.
بحث ثنائي لـ 1,000,000 عنصر مرتب يحتاج إلى أقصى قدر من كم عدد الخطوات؟ (2^20 ≈ مليون)
بما أن 2^20 تزيد قليلاً عن مليون، فإن ~20 من نصفات الكمية تكفي.
يمكن للخوارزمية الصحيحة أن تكون بطيئة جداً للاستخدام على المدخلات الكبيرة.
يجب أن تنتهي أيضاً في وقت معقول.
بطيء جداً للاستخدام
- لهذا السبب بعض الخوارزميات الصحيحة تكون بطيئة جداً للتشغيل عملياً على المدخلات الكبيرة.
- كونها صحيحة ليس كافياً — يجب أن تنتهي الخوارزمية أيضاً في وقت معقول.
مليون عنصر. قد يستغرق البحث الخطي لـ 1,000,000 عنصر مرتب حتى 1,000,000 خطوة. يأخذ البحث الثنائي في الغالب حوالي 20 فقط، لأن $2^{20}$ أكبر قليلاً من مليون. على القوائم الصغيرة لا يهم الفرق كثيراً؛ على مليون عنصر، الثنائي هو الخيار الوحيد المعقول.
الكفاءة الخوارزمية تقارن بين الخوارزميات من حيث الموارد عندما ينمو حجم المدخلات $n$: خطي $n$، ثنائي $\log_2 n$، أزواج الكل $n^2$. النمو مثل $n$ أو $n^2$ يُعتبر معقولاً؛ أما $2^n$ فهو غير معقول (استخدم خوارزمية استقصائية). الخوارزمية الصحيحة التي تكون بطيئة جداً على المدخلات الكبيرة لا تكفي.