Algorithmic efficiency
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · تحتاج هذه الصفحة إلى متصفح حديث (يدعم SharedArrayBuffer). يرجى تحديث Chrome أو Edge أو Firefox أو Safari إلى أحدث إصدار.
English
What we'll do
- Two programs can both be correct but take very different time.
- This lesson is about efficiency: how the work grows as the input grows.
- Read and think about the ideas; then a few short tasks let you count the steps yourself.
العربية
ما سنفعله
- يمكن لكلا البرنامجين أن يكونا صحيحين ولكن يستغرقا وقتًا مختلفًا تمامًا.
- هذه الدرس是关于 الكفاءة: كيف ينمو العمل مع نمو المدخلات.
- اقرأ وأفكر في الأفكار؛ ثم عدة مهام قصيرة تسمح لك بـ عدّ الخطوات بنفسك.
English
Counting the work
- We measure an algorithm by how many steps it does, not seconds.
- Steps in seconds depend on the computer; counting steps does not.
- More input usually means more steps. The question is how much more.
العربية
عدّ العمل
- نقيس الخوارزمية بـ عدد الخطوات التي تنفذها، وليس بالثواني.
- خطوات الثواني تعتمد على جهاز الكمبيوتر؛ عدّ الخطوات لا يعتمد عليه.
- مدخلات أكبر تعني عادةً خطوات أكثر. السؤال هو كم أكثر.
English
Reasonable vs unreasonable run time
- Some algorithms grow slowly: double the input, do about double the work.
- Some algorithms grow fast: a little more input means a huge jump in work.
- "Reasonable" run time grows slowly enough to finish; "unreasonable" blows up.
العربية
وقت التشغيل المعقول مقابل غير المعقول
- بعض الخوارزميات تنمو ببطء: مضاعفة المدخلات تعني ضعف العمل تقريبًا.
- بعض الخوارزميات تنمو بسرعة: زيادة طفيفة في المدخلات تعني قفزًا هائلًا في العمل.
- وقت التشغيل "المعقول" ينمو ببطء كافٍ للانتهاء؛ "غير المعقول" ينهار.
Input size: 10 20 40
Search a list: 10 20 40 (slow growth - reasonable)
Try all orders: 3,628,800 ... a number with 48 digits (explodes!)
English
A tiny demo: counting steps
- Below we count the comparisons a linear search makes.
- The count grows in step with the list size — slow, steady growth.
- Try changing the size to see the count follow it.
العربية
عرض توضيحي صغير: عدّ الخطوات
- أدناه نعد المقارنات التي يقوم بها البحث الخطي.
- العدد ينمو خطوة بخطوة مع حجم القائمة — نمو بطيء ومستقر.
- حاول تغيير الحجم لترى العدد يتبعه.
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))
English
When fast is not enough
- Some problems have no known fast algorithm.
- The only methods try a huge number of possibilities — too slow for big input.
- For these, we often accept a good-enough answer instead of the perfect one.
العربية
عندما لا يكون السرعة كافية
- بعض المشاكل ليس لها خوارزمية سريعة معروفة.
- الطرق الوحيدة تحاول عددًا هائلًا من الاحتمالات — بطيئة جدًا للمدخلات الكبيرة.
- لهذه الحالات، نقبل غالبًا إجابة جيدة بما يكفي بدلاً من المثالية.
English
Undecidable problems
- Worse than slow: some problems cannot be solved by any algorithm at all.
- These are called undecidable problems.
- No matter how fast computers get, no program can always give the right answer.
العربية
مشاكل غير قابلة للحل
- أسوأ من البطء: بعض المشاكل لا يمكن حلها بأي خوارزمية على الإطلاق.
- تسمى هذه المشاكل مشاكل غير قابلة للحل.
- مهما زادت سرعة أجهزة الكمبيوتر، لن يتمكن أي برنامج من إعطاء الإجابة الصحيحة دائمًا.
Fast : finishes quickly, even for big input
Slow but doable : finishes, but may take a very long time
Undecidable : no algorithm can solve it for every input
English
Key ideas to remember
- Efficiency is about how work grows with input size.
- Slow-growing algorithms scale to big inputs; fast-growing ones do not.
- Some problems are unreasonable to solve exactly, and some are undecidable.
العربية
أفكار رئيسية للتذكر
- الكفاءة تتعلق بكيفية نمو العمل مع حجم المدخلات.
- الخوارزميات ذات النمو البطيء تقبل المدخلات الكبيرة؛ ذات النمو السريع لا تقبل.
- بعض المشاكل مستحيلة الحل بدقة، وبعضها غير قابل للحل.
English
Common mistakes
- Big-O describes how the running time GROWS with the input size.
- A reasonable-time algorithm scales; an unreasonable one does not.
العربية
أخطاء شائعة
- Big-O تصف كيفية نمو وقت التشغيل مع حجم المدخلات.
- خوارزمية ذات وقت معقول تقبل المدخلات الكبيرة؛ غير المعقولة لا تقبل.
English
Now you try
- Write small functions that count steps to feel how the work grows.
- Compare a single loop, a nested loop, and "try all orders". Press Check answer.
العربية
الآن جرب بنفسك
- اكتب دوال صغيرة تعدّ الخطوات لتشعر بكيفية نمو العمل.
- قارن حلقة تكرارية واحدة، وحلقة مفرغة، و"تجربة جميع الترتيبات". اضغط تحقق من الإجابة.
Explore · استكشف
How algorithms scale
As input grows, O(n²) explodes while O(log n) barely moves.
Write scan_compares(data, target) that returns how many comparisons a linear search makes. Compare each item to target, counting one each time, and stop as soon as you find it. If it is not in the list, you compared every item. Example: scan_compares([5, 8, 2], 8) → 2.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.
Write pair_count(n) that uses a loop inside a loop (both over range(n)) and returns how many times the inner step runs. This is n × n. Example: pair_count(3) → 9. This grows much faster than a single loop.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.
Write count_orderings(n) that returns how many different orders n items can be placed in — that is 1 × 2 × ... × n (n factorial). count_orderings(0) is 1. Example: count_orderings(3) → 6. Notice how fast it explodes: count_orderings(10) is over 3 million.
Click Run to see the output here. · اضغط تشغيل لرؤية المخرجات هنا.