تحديات برمجيةإختيار الخوارزمية الأفضل
- مقدمة
- المثال الأول
- المثال الثاني
- المثال الثالث
مقدمة
في الدرس السابق تعلمنا كيف يتم تقييم أداء الكود و متى يتم إعتباره ممتازاً, جيداً, مقبولاً و سيئاً.
الآن سنتفق على أننا دائماً يجب أن نكتب الكود بأفضل شكل ممكن حتى نحصل على أفضل أداء ممكن من ناحية الوقت الذي يحتاجه الكود حتى يتنفذ بالكامل.
في هذا الدرس سنضع عدة تمارين يمكن حلها بأكثر من طريقة و سنحدد أي الطرق هي الطرق الأفضل بناءً على قواعد تقييم الكود التي تعلمناها في الدرس السابق.
المثال الأول
لنفترض أننا نريد حساب ناتج جمع جميع الأعداد الموجودة بين 1
و n
.
الحل الأول
لحل هذا التمرين يمكن تجهيز متغير إسمه s
لحفظ المجموع النهائي, ثم ننشئ حلقة من 1
إلى n
و في كل دورة فيها نقوم بإضافة قيمة العداد i
على قيمة المتغير s
.
الحل التالي هو الحل التقليدي و الذي اعتدنا أن نفعله, و بالمناسبة فإن تقييم هذا الحل هو O(n) لأن الحلقة تعيد تنفيذ الموضوع فيها بمقدار قيمة n
.
s = 0 n = int(input("Enter n: ")) for i in range(1, n + 1): s += i print("s =", s)
هل هذا الحل هو الحل الأفضل أم يمكن إيجاد حل أفضل يستغرق وقت أقل في التنفيذ؟
الجواب هو كلا, لأنه يمكن حساب ناتج جمع كل الأرقام الموجودة من 1
إلى n
بدون استخدام حلقة و بأمر واحد فقط!
هذا ما سنراه في الحل الثاني.
الحل الثاني
لحساب ناتج جمع جميع الأرقام الموجودة من 1
إلى n
سنستخدم القاعدة n * (n + 1) / 2
و التي ندرسها في مادة الرياضيات.
إذاً سنكتب أمر يتنفذ مرة واحدة فقط بدل استخدام حلقة و بالتالي فإن الخوارزمية تعتبر أسرع و أفضل خوارزمية ممكنة لأن وقت تنفيذها ثابت.
بمعنى أخر, تقييم الكود التالي هو O(1).
n = int(input("Enter n: ")) s = n * (n + 1) / 2 print("s =", s)
المثال الثاني
لنفترض أننا نريد حساب قيمة n!
.
الحل الأول
لحل هذا التمرين يمكن إستخدام أسلوب الـ Recursion, أي تعريف دالة تستدعي نفسها.
الحل التالي هو الحل التقليدي و لكنه يعتبر الأسوأ على الإطلاق لأن تقييم هذا الحل هو O(n!) و هذا يعتبر أسوء تقييم ممكن.
def factorial(n): if n > 0: return n * factorial(n - 1) return 1 n = int(input("Enter n: ")) print(str(n) + '! =', factorial(n))
الحل الثاني
يمكن حل التمرين السابق باستخدام حلقة عادية بدل تعريف دالة تستدعي نفسها.
الحل التالي أفضل من الحل السابق و يعتبر حل مقبول أيضاً لأن تقييم هذا الحل هو O(n).
def factorial(n): f = 1 for i in range(1, n + 1): f *= i return f n = int(input("Enter n: ")) print(str(n) + '! =', factorial(n))
المثال الثالث
لنفترض أننا نريد طباعة جميع الأرقام المزدوجة الموجودة من 0
إلى n
.
الحل الأول
لحل هذا التمرين يمكن إنشاء حلقة من 0
إلى n
و في كل دورة نشيّك على قيمة العداد i
لمعرفة ما إن كان باقي القسمة يساوي 0
أم لا.
إذا كان باقي القسمة هو 0
فمعنى ذلك أن قيمة العداد i
عبارة عن عدد مزدوج و بالتالي سنقوم بطباعتها.
تقييم هذا الحل هو O(n) و لكنه لا يعتبر الحل الأفضل لأنه كان بالإمكان تقليص وقت التنفيذ إلى النصف, أي إلى O(n/2) كما سترى في الحل الثاني.
n = int(input("Enter n: ")) for i in range(n + 1): if i % 2 == 0: print(i, end=" ")
الحل الثاني
يمكنك حل التمرين السابق بطريقة أسهل و أكثر كفاءة.
ببساطة يمكنك إنشاء حلقة من 0
إلى n
و جعل قيمة العداد i
تزيد 2
في كل دورة.
بما أن قيمة العداد ستزيد 2
في كل دورة بدل 1
فهذا يعني أن عدد الخطوات التي سيتم تنفيذها هو النصف و بالتالي تقييم الكود سيكون O(n/2).
n = int(input("Enter n: ")) for i in range(0, n + 1, 2): print(i, end=" ")