تحليل وقت التشغيل غير الرسمي
مُقدَّم| English | المعنى |
|---|---|
| run time/rʌn taɪm/ | وقت التشغيل |
| linear/ˈlɪnɪə/ | خطي |
| quadratic/kwɒˈdrætɪk/ | تربيعي |
عدّ العمل
- نقيس زمن تشغيل البرنامج بـ كم مرة تتكرر جملته الأساسية.
- ليس ثواني (تتغير حسب الآلة) — بل عدد العمليات مع نمو المدخلات.
- عمليات أكثر لنفس حجم المدخلات → خوارزمية أبطأ.
- هذا يسمح لنا بمقارنة الخوارزميات بإنصاف، مستقلة عن الأجهزة.
حلقة واحدة: حوالي n
- حلقة تمر على
nعناصر تشغّل جسمها حواليnمرة. - مضاعفة المدخلات → ضعف العمل تقريباً. هذا نمو خطي.
- جمع مصفوفة، البحث في قائمة واحداً تلو الآخر: كلهم حوالي
nخطوات. - تُكتب بشكل غير رسمي "ترتيب
n."
حلقة متداخلة: حوالي n²
- حلقة متداخلة تمر على
nعناصر تشغّل جسمها الداخلي حواليn × n = n²مرة. - مضاعفة المدخلات → أربعة أضعاف العمل تقريباً. هذا نمو تربيعي.
- مقارنة جميع الأزواج، ملء شبكة
n × n: حواليn²خطوة. n²تنمو أسرع بكثير منnكلما كبرتn.
مقارنة النمو
- لمقارنة الخوارزميات، اسأل كيف ينمو العمل مع نمو المدخلات.
- لـ
nكبيرة، خوارزميةnتتفوق على خوارزميةn²— غالباً بفارق كبير. - ركز على الجزء من الكود الذي يعمل أكثر (عادة الحلقة الداخلية).
- الحد الأسرع نمواً يهيمن على وقت التشغيل الكلي.
احكم على وقت التشغيل بالنمو، وليس بعدداً ثابتاً. خوارزمية تقوم بـ n خطوات وأخرى تقوم بـ 2n + 5 خطوة كلاهما ينمو خطياً — للمقارنة، الثابت و+5 لا يهمان؛ الشكل (n مقابل n²) هو المهم. حلقة واحدة حوالي n؛ حلقة متداخلة حوالي n²، وهو ينمو أسرع بكثير للمدخلات الكبيرة.
طريقتان لإيجاد التكرار في n عناصر:
- الحلقات المتداخلة تقارن كل زوج: حوالي
n²خطوات. - الفرز أولاً، ثم مرور واحد: خطوات أقل بكثير لـ
nكبيرة. - بالنسبة لـ
n = 1000،n²تعني مليون خطوة — نهجn²أبطأ بكثير.
تحليل زمن التشغيل غير الرسمي يعد عدد مرات تشغيل العبارات مع نمو المدخلات. حلقة واحدة على n عناصر هي حوالي n (خطي)؛ حلقة متداخلة هي حوالي n² (تربيعي)، وتنمو أسرع بكثير. قارن الخوارزميات بنموها، مع التركيز على الكود الأكثر تنفيذاً (الأعمق).
كيف ينمو العمل مع n
حلقة متداخلة (n²) تنمو بشكل أسرع بكثير من حلقة فردية (n).
حلقة فردية فوق n عنصر تعمل جسمها تقريباً كم مرة؟
Difficulty 1/5 · 100 coins + a small bonus on first completion today
حلقة واحدة فوق n عنصر → حوالي n خطوات (خطي).
حلقة متداخلة فوق n عنصر تعمل جسمها الداخلي تقريباً كم مرة؟
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n × n = n² (تربيعي).
من أجل n = 1000، كم عدد الخطوات تقريباً لخوارزمية n² (بالملايين)؟
Difficulty 2/5 · 140 coins + a small bonus on first completion today
1000² = 1,000,000 = 1 مليون.
من أجل n كبيرة، خوارزمية n-خطوات تكون عموماً أسرع من خوارزمية n²-خطوات.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
n² تنمو بشكل أسرع بكثير، لذا تقوم بعمل أكبر بكثير عند n الكبيرة.
نقيس وقت التشغيل بالثواني، وهو نفس الشيء على كل حاسوب.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
نحن نعد العمليات مقابل حجم الإدخال — الثواني تختلف حسب الآلة.