Comparing algorithms and ADTs in algorithms
مُقدَّم| English | المعنى |
|---|---|
| Big-O/bɪɡ əʊ/ | تعبير بي-أو |
| time complexity/taɪm kəmˈpleksɪti/ | تعقيد الوقت |
| space complexity/speɪs kəmˈpleksɪti/ | تعقيد المساحة |
| depth-first/depθ fɜːst/ | أولوية العمق |
| breadth-first/bredθ fɜːst/ | أولوية العرض |
| binary tree/ˈbaɪnəri triː/ | شجرة ثنائية |
الخوارزمية التي ستبقى أطول من الكون
- يجب على بائع زيارة 25 مدينة والعودة إلى المنزل بأقصر طريق. جرب كل ترتيب وسيكون هناك حوالي $10^{23}$ منها. آلة تتحقق من مليار ترتيب في الثانية ستحتاج ثلاثة ملايين عام.
- أضف مدينة واحدة أخرى وسيتضاعف العمل بمقدار 25 مرة. هذا ليس حاسوبًا يحتاج إلى أن يكون أسرع؛ بل هو نهج لا يمكن أن يعمل أبدًا، بأي سرعة، على أي عتاد.
- معرفة ذلك قبل كتابة البرنامج هو ما تخدمه له تحليل التعقيد. إنه الفرق بين اختيار خوارزمية واكتشاف، بعد أشهر، أن خوارزميتك لا قابلة للتوسع.
- هذه الدرس هو Big-O للوقت والمساحة، وكيف تشكل الأنواع المجردة للبيانات (ADTs) الخوارزميات المبنية عليها.
تعقيد الوقت
- تعقيد الوقت يصف كيف ينمو وقت التشغيل مع حجم المدخلات $n$. يُكتب باستخدام رمز Big-O، الذي يحتفظ فقط بالحد السائد ويتجاهل الثوابت.
- $O(1)$ ثابت، لا يعتمد الوقت على $n$ على الإطلاق. $O(\log n)$ لوغاريتمي، كما في البحث الثنائي. $O(n)$ خطي، كما في البحث الخطي. $O(n \log n)$، الترتيبات الجيدة. $O(n^2)$ تربيعي، كما في ترتيب الفقاعات وترتيب الإدراج.
- سبب تجاهل الثوابت: أنها تُطغى عليها. قد تتفوق خوارزمية $O(n^2)$ على خوارزمية $O(n \log n)$ من أجل $n = 10$، ولكن عند $n = 10{,}000$ لا شيء من الثوابت يمكن أن ينقذها.

تتقاطع المنحنيات مرة واحدة، وبعد ذلك يحدد الترتيب كل شيء
How running time grows with n
Slide n upward and compare the curves: O(1) and O(log n) stay almost flat, O(n) rises steadily, O(n²) explodes. This is why Big-O — not a stopwatch — is how we compare algorithms on large inputs.
Which Big-O describes binary search?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Halving the range each step is logarithmic — O(log n).
Which Big-O describes bubble sort in the worst case?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Two nested loops over n elements give O(n²).
Match each algorithm to its time complexity.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Linear search is O(n), binary search O(log n), bubble sort O(n²).
مثال محلول: ما الذي يفعله مضاعفة المدخلات
- يأخذ الخوارزمية 4 ثوانٍ على 1,000 عناصر. قدر وقتها على 2,000 عناصر إذا كانت $O(n)$، ثم إذا كانت $O(n^2)$.
- $O(n)$: مضاعفة $n$ تضاعف الوقت، لذا حوالي 8 ثوانٍ.
- $O(n^2)$: مضاعفة $n$ تربّع الوقت، لذا حوالي 16 ثانية. عند 10,000 عنصر ستكون 100 ضعف الأصلي، حوالي 400 ثانية.
- $O(\log n)$ سيضيف خطوة واحدة فقط، و**$O(1)$** لن يتغير على الإطلاق. استنتج من الترتيب، وليس من معادلة.
An O(n squared) algorithm takes 4 seconds on 1,000 items. Roughly how many seconds will it take on 2,000?
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Doubling n quadruples an O(n squared) time. The same doubling would take an O(n) algorithm from 4 seconds to 8.
تعقيد المساحة
- تعقيد الفراغ هو الذاكرة الإضافية التي يحتاجها الخوارزمية، عدا عن مدخلاته.
- ترتيب الفقاعات وترتيب الإدراج يستخدمان $O(1)$ ذاكرة إضافية: يعملان محليًا، مما يتطلب المتغيرات القليلة فقط. استخدام دمج الترتيب $O(n)$، لأنه يبني مصفوفة ثانية.
- الاستخدام العودي يستخدم ذاكرة المكدس متناسبة مع عمقه، لأن كل استدعاء لم يكتمل يحتفظ بإطاره الخاص.
- غالبًا ما يكون هناك مفاضلة بين الوقت والذاكرة: تخزين النتائج لتجنب إعادة حسابها، كما تفعل الذاكرة المؤقتة، يشتري السرعة بالمساحة.
ما الذي يحدد الاختيار آخر
- Big-O يتعلق بـ النمو، وليس السرعة المطلقة. بالنسبة لـ $n$ صغير، يمكن لخوارزمية $O(n^2)$ بسيطة أن تتفوق على خوارزمية $O(n \log n)$ معقدة، ومن الأسهل كتابتها بشكل صحيح.
- الاستقرار مهم عندما تكون القائمة مرتبة بالفعل حسب مجال آخر. البساطة مهمة لأن الخوارزمية البسيطة تحتوي على أماكن أقل لإخفاء الأخطاء.
- الإجابة الصادقة عن "أي خوارزمية" غالبًا ما تذكر الترتيب و الظروف: هذه، لأن $n$ كبير والبيء arrives unsorted.
An "in place" sort:
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
Why is bubble sort's space complexity O(1) even though it sorts an array of n items?
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
It sorts in place. Merge sort is O(n) because it builds a second array, and recursion costs memory proportional to its depth.
ADTs داخل الخوارزميات
- الأنواع المجردة للبيانات من الموضوع 10 هي الآلية التي تُبنى عليها الخوارزميات، واختيار واحد منها يشكل الخوارزمية.
- المكدس يعطي البحث الأولوية العمقية: ادفع الجيران، وأخذ أحدثها، وينغمس البحث في مسار واحد قبل التراجع. recursion uses the call stack for exactly this.
- الطابور يعطي البحث الأولوية العرضية: أدخل الجيران في الطابور، وأقدمها، وينتشر البحث للخارج في حلقات، وهو ما يجد أقصر طريق في الرسم البياني غير الموزون.
- الشجرة الثنائية تحافظ على القيم مرتبة بحيث يستبعد البحث نصف العقد المتبقية في كل خطوة، مما يمنح البحث الثنائي $O(\log n)$ على بنية يمكن أيضًا أن تنمو.
Which statements about Big-O are correct? Select جميعها that apply.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Big-O says nothing about seconds; it is about growth. That is why the crossover with a simpler algorithm exists at small sizes.
مثال محلول: نفس الرسم البياني، بحثان
- متاهة يتم استكشافها من مدخل واحد. قارن استخدام مكدس مع استخدام طابور.
- مع المكدس، يتم استكشاف المسار الذي تم العثور عليه مؤخرًا التالي، لذلك يذهب البحث عميقًا في مسار واحد حتى ينتهي، ثم يعود. يستخدم ذاكرة متناسبة مع عمق المسار.
- مع الطابور، يتم استكشاف المسار الذي تم العثور عليه قديمًا التالي، لذلك يفحص البحث كل شيء على بُعد خطوة واحدة، ثم كل شيء على بُعد خطوتين. يجد أقصر طريق أولاً، لكنه يحتفظ بكل موقع على المسافة الحالية في الذاكرة.
- سمِّ نوع البيانات المجرد، وسمِّ الترتيب الناتج للاستكشاف، وسمِّ النتيجة.
A stack (LIFO) naturally drives a depth-first traversal, while a queue (FIFO) drives a breadth-first traversal.
الصعوبة 1/5 · 100 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
The ADT you choose decides the search order — stack goes deep first, queue explores level by level.
Match each ADT to the search it produces and its consequence.
الصعوبة 2/5 · 140 عملة + مكافأة صغيرة عند الإنجاز الأول اليوم
Most recent first, or oldest first. That single choice decides whether the search goes deep or wide.
علامات ضائعة
- Big-O يصف النمو مع حجم المدخلات، وليس الثواني. "إنه سريع" ليس إجابة عن التعقيد.
- مضاعفة المدخلات تضاعف وقت $O(n)$ وتربّع $O(n^2)$. استنتج من الترتيب.
- تعقيد المساحة هو الذاكرة الإضافية، ولهذا السبب يُعد ترتيب الموضع في $O(1)$ حتى لو كان حجم المصفوفة $n$.
- المكدس يعطي البحث العميق، والجدول يعطي البحث العريض. الحصول على هذه الأزواج بشكل صحيح هو جوهر عدد من الأسئلة.
لقد فهمت الأمر
- تعقيد الوقت في Big-O يصف النمو مع $n$: $O(1)$، $O(\log n)$، $O(n)$، $O(n \log n)$، $O(n^2)$؛ يتم تجاهل الثوابت لأنه على النطاق الكبير، الترتيب هو ما يحدد
- مضاعفة $n$ تضاعف $O(n)$ وتربع $O(n^2)$؛ نقطة التقاطع مع خوارزمية "أسوأ" لا توجد إلا لـ $n$ الصغيرة
- تعقيد المساحة هو الذاكرة الإضافية: الترتيبات الموضعية هي $O(1)$، ودمج الترتيب (merge sort) هو $O(n)$، والتراجع يتطلب عمق المكدس
- المكدس يعطي البحث العميق، والجدول يعطي البحث العريض، والشجرة الثنائية تقلل العقد المتبقية للنصف في كل خطوة