DSA Big O

تدريبات تدوين كبيرة

المفاهيم الرئيسية

• يشير تعقيد الفضاء إلى مقدار الذاكرة الفعلية التي تتطلبها الخوارزمية لإكمالها.
• يشير تعقيد الوقت إلى عدد العمليات التي تتطلبها الخوارزمية.
• الترميز الكبير O هو وسيلة لوصف التعقيد الزمني للخوارزمية.
• العلاقة الخطية هي عندما تنمو شيئان مختلفان (مثال على أن عملية التشغيل وحلقة) تنمو بشكل مباشر وخطي مع بعضهما البعض.
• يستغرق الوقت الثابت (O (1)) نفس الوقت من الوقت لإكمال بغض النظر عن حجم المدخلات. "الكأس المقدسة".
• يستغرق وقت لوغاريتمي (O (السجل (N))) وقتًا أطول مع مدخلات أكبر ، لكن وقت التشغيل يزداد ببطء. يقطع حجم المشكلة في نصف كل جولة. أفضل شيء بعد وقت ثابت (O (1)).
• يحتوي الوقت الخطي (O (N)) على أوقات تشغيل تتناسب مباشرة مع حجم (N) من الإدخال.
• الوقت متعدد الحدود (O (n^k)) لديه وقت تشغيل سيكون بعض حجم الإدخال N الذي رفع إلى بعض الطاقة الثابتة k .
• الوقت الأسي (O (2^n)) لديه أوقات تشغيل تنمو بسرعة مع أي زيادة في حجم الإدخال.

أمثلة

• O (1) - أمثلة على الخوارزميات O (1) تصل إلى عنصر صفيف أو إجراء عمليات حسابية أساسية (على سبيل المثال ، إضافة رقمين).

• o (log (n)) - مثال جيد على خوارزمية (O (log (n))) تبحث عن أشخاص في دفتر الهاتف. لا تحتاج إلى التحقق من كل شخص في دفتر الهاتف للعثور على الشخص الصحيح ؛ بدلاً من ذلك ، يمكنك ببساطة التقسيم والخروج من خلال البحث بناءً على المكان الذي يكون فيه اسمه أبجديًا ، وفي كل قسم ، تحتاج فقط إلى استكشاف مجموعة فرعية من كل قسم قبل أن تجد في النهاية رقم هاتف شخص ما. بالطبع ، سيظل دفتر هاتف أكبر يستغرق وقتًا أطول ، لكنه لن ينمو بالسرعة التي تزيد بها الزيادة النسبية في الحجم الإضافي. تذكر ذلك:
  • يعد اختيار العنصر التالي لأداء بعض الإجراءات أحد الاحتمالات العديدة
  • سيحتاج واحد فقط إلى اختياره. أو
  • العناصر التي يتم تنفيذ الإجراء هي أرقام N

• o (n) - بعض الأمثلة لخوارزميات O (n) تلخص العناصر في صفيف وإيجاد الحد الأدنى أو الحد الأقصى للقيمة في صفيف.

• o (n^k) - أسهل طريقة لفهم تعقيد الوقت متعدد الحدود مع حلقات متداخلة. الخوارزمية التي تتطلب مستويين من الحلقات على المدخلات ستكون O (n^2) في حين أن واحدة تتطلب 3 مستويات من الحلقات ستكون O (n^3). في كلتا الحالتين ، لدينا تعقيد وقت متعدد الحدود.

• o (2^n) - للحصول على مدخلات من الحجم 2 ، ستستغرق خوارزمية الوقت الأسي 2^2 = 4 وقت. مع مدخلات الحجم 10 ، ستستغرق الخوارزمية نفسها 2^10 = 1024 مرة ، ومع إدخال حجم 100 ، سوف يستغرق 2^100 = 1.26765060022823 * 1030 الوقت. غالبًا ما تكون الخوارزميات مع وقت التشغيل O (2^n) خوارزميات متكررة تحل مشكلة من الحجم N عن طريق حل مشكلتين أصغر من الحجم N-1.

وقت تعقيد الوقت

العمليات المطلوبة من خلال تعقيدات زمنية مختلفة

موارد

• ورقة
• Web Dev مبسط
• CS50 فيديو التعقيد الحسابي
• Hackerrank Big O Todation Video

نظرة عامة على التدريبات

في هذه التدريبات ، سوف تمارس تحديد التعقيد الكبير للخوارزميات. لكل تدريبات ، سنقدم مقتطف رمز لوظيفة ، وستعمل على التعقيد الكبير من خلال تحليل الكود دون تشغيله.

1. ما هو كبير O لهذا؟

1. حدد O Big O للخوارزمية التالية: أنت تجلس في غرفة بها 15 شخصًا. تريد أن تجد زميلًا في اللعب لكلبك ، ويفضل أن يكون من نفس السلالة. لذلك تريد أن تعرف ما إذا كان أي شخص من بين 15 شخصًا لديه نفس السلالة مثل كلبك. أنت تقف وتصرخ ، الذي لديه هنا مسترد ذهبي وترغب في أن تكون لعبة لعب للذهبي. شخص ما يصرخ - "أنا أفعل ، كن سعيدا لإحضاره"

2. حدد O Big O للخوارزمية التالية: أنت تجلس في غرفة بها 15 شخصًا. تريد أن تجد زميلًا في اللعب لكلبك من نفس السلالة. لذلك تريد أن تعرف ما إذا كان أي شخص من بين 15 شخصًا لديه نفس السلالة مثل كلبك. تبدأ مع الشخص الأول وتسأله عما إذا كان لديه مسترد ذهبي. يقول لا ، ثم تسأل الشخص التالي ، والآخر ، والآخر حتى تجد شخصًا لديه ذهبية أو لا يوجد أي شخص آخر يسأله.

2. حتى أو غريب

ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    if (value % 2 === 0) {
        return true;
    }
    else {
        return false;
    }
}

3. هل أنت هنا؟

ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    for (let i = 0; i < arr1.length; i++) {
        const el1 = arr1[i];
        for (let j = 0; j < arr2.length; j++) {
            const el2 = arr2[j];
            if (el1 === el2) return true;
        }
    }
    return false;
}

4. المضاعفة

ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    for (let i = 0; i < array.length; i++) {
        array[i] *= 2;
    }
    return array;
}

5. البحث الساذج

ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    for (let i = 0; i < array.length; i++) {
        if (array[i] === item) {
            return i;
        }
    }
}

6. إنشاء أزواج

ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    for (let i = 0; i < arr.length; i++) {
        for(let j = i + 1; j < arr.length; j++) {
            console.log(arr[i] + ", " +  arr[j] );
        }
    }
}

7. حساب التسلسل

ماذا تفعل الخوارزمية التالية؟ ما هو تعقيد وقت التشغيل؟ اشرح إجابتك

    let result = [];
    for (let i = 1; i <= num; i++) {

        if (i === 1) {
            result.push(0);
        }
        else if (i === 2) {
            result.push(1);
        }
        else {
            result.push(result[i - 2] + result[i - 3]);
        }
    }
    return result;
}

8. بحث فعال

في هذا المثال ، نعود إلى مشكلة البحث باستخدام نهج أكثر تطوراً من البحث الساذج أعلاه. افترض أن صفيف الإدخال يتم فرزه دائمًا. ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    let minIndex = 0;
    let maxIndex = array.length - 1;
    let currentIndex;
    let currentElement;

    while (minIndex <= maxIndex) {
        currentIndex = Math.floor((minIndex + maxIndex) / 2);
        currentElement = array[currentIndex];

        if (currentElement < item) {
            minIndex = currentIndex + 1;
        }
        else if (currentElement > item) {
            maxIndex = currentIndex - 1;
        }
        else {
            return currentIndex;
        }
    }
    return -1;
}

9. عنصر عشوائي

ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    return arr[Math.floor(Math.random() * arr.length)];
}

10. ما أنا؟

ماذا تفعل الخوارزمية التالية؟ ما هي الخوارزمية الكبيرة التالية؟ اشرح إجابتك

    if (n < 2 || n % 1 !== 0) {
        return false;
    }
    for (let i = 2; i < n; ++i) {
        if (n % i === 0) return false;
    }
    return true;
}

11. برج هانوي

برج Hanoi هو لغز رياضي مشهور جدًا (بعضها يدعو إلى لعبة!). هكذا تسير الأمور:

• هناك ثلاثة قضبان وعدد من الأقراص بأحجام مختلفة يمكن أن تنزلق على أي قضيب. يبدأ اللغز بالأقراص المكدسة بدقة بترتيب تصاعدي من الحجم على قضيب واحد ، وأصغر قرص في الأعلى (مما يجعل شكل مخروطي). القضبان الأخرى فارغة لتبدأ.

• الهدف من اللغز هو نقل كومة القضبان بأكملها إلى قضيب آخر (لا يمكن أن يكون القضيب الأصلي حيث تم تكديسه من قبل) حيث سيتم تكديسه بالترتيب الصاعد أيضًا. يجب أن يتم ذلك طاعة القواعد التالية:

  • قد يتم نقل قرص واحد فقط في وقت واحد
  • تتكون كل خطوة من أخذ القرص العلوي من أحد القضبان وانزلاقه على قضيب آخر ، أعلى الأقراص الأخرى التي قد تكون موجودة بالفعل على هذا القضيب.
  • قد لا يوضع قرص أكبر على قرص أصغر.

مهمتك:

• اشتق خوارزمية لحل برج اللغز هانوي.
• تنفيذ الخوارزمية الخاصة بك باستخدام العودية. يجب أن يعرض برنامجك كل حركة من القرص من قضيب إلى آخر.
• إذا أعطيت 5 أقراص ، كيف تبدو القضبان بعد 7 مكالمات متكررة؟
• كم عدد الحركات اللازمة لإكمال اللغز مع 3 أقراص؟ مع 4 أقراص؟ مع 5 أقراص؟
• ما هو وقت تشغيل الخوارزمية الخاصة بك؟

12. النسخة التكرارية

حل التدريبات ملف JS 12 بشكل متكرر.

13 عودية كبيرة س

خذ الحلول من هذا الريبو وحدد التعقيدات الزمنية (كبيرة O) لكل منها.

14. تكرار كبير يا

خذ حلولك من التدريبات التكرارية في ملف JS 12 وحدد التعقيدات الزمنية (الكبيرة O) لكل منها.