Algorithmic Efficiency
مُقدَّم| 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/ | الاستدعاءات التمهيدية |
التصحيح ليس دائماً كافياً
- يمكن لخوارزميتين أن تكونا صحيحتين، مع أن إحداهما قد تكون أفضل بكثير للاستخدام.
- الكفاءة الخوارزمية تقارن الخوارزميات حسب الموارد التي تستخدمها — أساساً الوقت والذاكرة.
- خوارزمية صحيحة ولكن بطيئة يمكن أن تكون عديمة الفائدة على المدخلات الكبيرة.
- لذلك نحتاج إلى طريقة لمقارنة كيف تتوسع.*
Algorithmic efficiency compares algorithms by:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Efficiency is about time and memory as input grows.
عدّ الخطوات بينما تنمو n
- قدر عدد الخطوات التي تستغرقها الخوارزمية بينما ينمو حجم مدخلاتها $n$.
- البحث الخطي يستهلك حوالي $n$ خطوات؛ البحث الثنائي حوالي $\log_2 n$؛ مقارنة كل زوج حوالي $n^2$.
- عندما يصبح $n$ كبيراً، تصبح هذه الفروقات هائلة.
- شكل النمو مهم جداً مقارنة بالميقاف الزمني.

كيف يزداد زمن تشغيل الخوارزمية مع حجم المدخلات n
How running time grows with n
Slide n and compare the curves: log n stays almost flat, n rises steadily, n² explodes. This is why we compare algorithms by how they scale, not with a stopwatch.
Match each algorithm to its rough number of steps for input size n.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
These growth rates decide which algorithm scales.
Which growth is considered unreasonable as n gets large?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Exponential growth quickly becomes far too slow.
When an exact answer is too slow, a ______ finds a good-enough solution fast.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
A heuristic trades a perfect answer for speed.
المعقول وغير المعقول
- نفصل بين وقت تشغيل معقول ووقت غير معقول.
- تقريباً، النمو مثل $n$ أو $n^2$ يعتبر معقولاً؛ مضاعفة الخطوات لكل عنصر إضافي (مثل $2^n$) ليس كذلك.
- عندما يكون الإجابة الدقيقة بطيئة جداً، استخدم الاستدراك — حلاً جيداً بما يكفي تم العثور عليه بسرعة.
- ليس مثالياً، لكنه مفيد عندما يكون المثالي مستحيلاً في الوقت المحدد.
A binary search of 1,000,000 sorted items needs at most about how many steps? (2^20 ≈ a million)
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Because 2^20 is just over a million, ~20 halvings suffice.
If an algorithm is correct, it will always run fast enough on large inputs.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
False. A correct algorithm can still be too slow on large inputs; it must also finish in a reasonable time.
بطيء جداً للاستخدام
- لهذا السبب بعض الخوارزميات الصحيحة تكون بطيئة جداً للتشغيل عملياً على المدخلات الكبيرة.
- كونها صحيحة ليس كافياً — يجب أن تنتهي الخوارزمية أيضاً في وقت معقول.
مليون عنصر. قد يستغرق البحث الخطي لـ 1,000,000 عنصر مرتب حتى 1,000,000 خطوة. يأخذ البحث الثنائي في الغالب حوالي 20 فقط، لأن $2^{20}$ أكبر قليلاً من مليون. على القوائم الصغيرة لا يهم الفرق كثيراً؛ على مليون عنصر، الثنائي هو الخيار الوحيد المعقول.
الكفاءة الخوارزمية تقارن بين الخوارزميات من حيث الموارد عندما ينمو حجم المدخلات $n$: خطي $n$، ثنائي $\log_2 n$، أزواج الكل $n^2$. النمو مثل $n$ أو $n^2$ يُعتبر معقولاً؛ أما $2^n$ فهو غير معقول (استخدم خوارزمية استقصائية). الخوارزمية الصحيحة التي تكون بطيئة جداً على المدخلات الكبيرة لا تكفي.