تعقيد الخوارزمية

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

• يرتدي
• ينظف
• تغذية جيدة

ما هي الخوارزمية التي ستسمح لك بتحقيق هذه النتيجة؟

1. استيقظ على المنبه.
2. استحم، اغسل وجهك.
3. تحضير وجبة الإفطار، وتحضير القهوة/الشاي.
4. يأكل.
5. إذا لم تقم بكوي ملابسك منذ المساء، قم بكويها.
6. يرتدى ملابسة.
7. اترك المنزل.

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

1. قم بالشراء أو التنزيل على الإنترنت "قاموس الأسماء الشخصية الروسية" طبعة 1966.
2. ابحث عن كل اسم في قائمتنا في هذا القاموس.
3. اكتب على قطعة من الورق أي صفحة من القاموس يوجد الاسم.
4. رتّب الأسماء باستخدام الملاحظات الموجودة على قطعة من الورق.

هل سيسمح لنا هذا التسلسل من الإجراءات بحل مشكلتنا؟ نعم سيسمح بذلك تماما فهل سيكون هذا الحل فعالا ؟ بالكاد. نأتي هنا إلى خاصية أخرى مهمة جدًا للخوارزميات - كفاءتها . يمكن حل المشكلة بطرق مختلفة. ولكن سواء في البرمجة أو في الحياة اليومية، نختار الطريقة التي ستكون أكثر فعالية. إذا كانت مهمتك هي صنع شطيرة بالزبدة، فيمكنك بالطبع البدء بزراعة القمح وحلب البقرة. ولكن هذا سيكون حلاً غير فعال - فهو سيستغرق الكثير من الوقت وسيكلف الكثير من المال. لحل مشكلتك البسيطة، يمكنك ببساطة شراء الخبز والزبدة. والخوارزمية الخاصة بالقمح والبقرة، على الرغم من أنها تسمح لك بحل المشكلة، إلا أنها معقدة للغاية بحيث لا يمكن تطبيقها عمليًا. لتقييم مدى تعقيد الخوارزميات في البرمجة، تم إنشاء تدوين خاص يسمى Big-O ("big O") . يتيح لك Big-O تقدير مدى اعتماد وقت تنفيذ الخوارزمية على البيانات التي تم تمريرها إليها . دعونا نلقي نظرة على أبسط مثال - نقل البيانات. تخيل أنك بحاجة إلى نقل بعض المعلومات في شكل ملف عبر مسافة طويلة (على سبيل المثال، 5000 كيلومتر). ما هي الخوارزمية التي ستكون الأكثر كفاءة؟ يعتمد ذلك على البيانات التي يتعين عليه العمل معها. على سبيل المثال، لدينا ملف صوتي بحجم 10 ميغابايت. في هذه الحالة، ستكون الخوارزمية الأكثر فعالية هي نقل الملف عبر الإنترنت. سوف يستغرق الأمر بضع دقائق فقط! لذلك، دعونا نعبر عن خوارزميتنا مرة أخرى: "إذا كنت بحاجة إلى نقل المعلومات في شكل ملفات على مسافة 5000 كيلومتر، فأنت بحاجة إلى استخدام نقل البيانات عبر الإنترنت." عظيم. الآن دعونا نحللها. فهل يحل مشكلتنا؟ بشكل عام، نعم، يحلها تماما. ولكن ماذا يمكنك أن تقول عن تعقيدها؟ حسنًا، الآن هذا هو المكان الذي تصبح فيه الأمور مثيرة للاهتمام. الحقيقة هي أن الخوارزمية الخاصة بنا تعتمد إلى حد كبير على البيانات الواردة، أي حجم الملفات. الآن لدينا 10 ميغابايت وكل شيء على ما يرام. ماذا لو أردنا نقل 500 ميجا بايت؟ 20 جيجا؟ 500 تيرابايت؟ 30 بيتابايت؟ هل ستتوقف خوارزميتنا عن العمل؟ لا، لا يزال من الممكن نقل كل هذه الكميات من البيانات. هل سيستغرق الأمر وقتًا أطول لإكماله؟ نعم! نحن نعرف الآن ميزة مهمة في الخوارزمية الخاصة بنا: كلما زاد حجم البيانات التي سيتم نقلها، كلما استغرقت الخوارزمية وقتًا أطول لإكمالها . لكننا نود أن نفهم بشكل أكثر دقة كيف تبدو هذه العلاقة (بين حجم البيانات والوقت الذي يستغرقه نقلها). في حالتنا، سيكون تعقيد الخوارزمية خطيًا. "الخطي" يعني أنه مع زيادة حجم البيانات، سيزداد وقت إرسالها بشكل متناسب تقريبًا. إذا كان هناك ضعف البيانات، فسيستغرق نقلها ضعف الوقت. إذا كان هناك بيانات أكثر 10 مرات، فسيزيد وقت النقل 10 مرات. باستخدام تدوين Big-O، يتم تعريف تعقيد الخوارزمية لدينا على أنه O(N) . من الأفضل تذكر هذا الترميز للرجوع إليه مستقبلاً؛ فهو يُستخدم دائمًا للخوارزميات ذات التعقيد الخطي. يرجى ملاحظة: أننا لا نتحدث هنا على الإطلاق عن أشياء "متغيرة" مختلفة: سرعة الإنترنت، وقوة جهاز الكمبيوتر الخاص بنا، وما إلى ذلك. عند تقييم مدى تعقيد الخوارزمية، فإن هذا ببساطة لا معنى له - فليس لدينا أي سيطرة عليه على أي حال. تقوم Big-O بتقييم الخوارزمية نفسها، بغض النظر عن "البيئة" التي يجب أن تعمل فيها. دعونا نواصل مع مثالنا. لنفترض أنه اتضح في النهاية أن حجم الملفات المراد نقلها هو 800 تيرابايت. إذا قمنا بنقلها عبر الإنترنت، فسيتم حل المشكلة بالطبع. هناك مشكلة واحدة فقط: الإرسال عبر رابط حديث قياسي (بسرعة 100 ميغابت في الثانية) الذي يستخدمه معظمنا في منازلنا سيستغرق حوالي 708 أيام. ما يقرب من 2 سنوات! :O لذا، من الواضح أن خوارزميتنا ليست مناسبة هنا. نحن بحاجة إلى حل آخر! وفجأة، جاءت شركة أمازون العملاقة لتكنولوجيا المعلومات لمساعدتنا! تسمح لك خدمة Amazon Snowmobile بتحميل كميات كبيرة من البيانات إلى وحدات تخزين متنقلة وتسليمها إلى العنوان المطلوب بالشاحنة! لذلك لدينا خوارزمية جديدة! "إذا كنت بحاجة إلى نقل المعلومات على شكل ملفات على مسافة 5000 كيلومتر، وستستغرق العملية أكثر من 14 يومًا عند نقلها عبر الإنترنت، فأنت بحاجة إلى استخدام شاحنات النقل من أمازون". لقد تم اختيار رقم 14 يومًا هنا بشكل عشوائي: لنفترض أن هذه هي المدة القصوى التي يمكننا تحملها. دعونا نحلل الخوارزمية لدينا. ماذا عن السرعة؟ وحتى لو سارت الشاحنة بسرعة 50 كم/ساعة فقط، فإنها ستقطع مسافة 5000 كيلومتر خلال 100 ساعة فقط. هذا ما يزيد قليلاً عن أربعة أيام! وهذا أفضل بكثير من خيار النقل عبر الإنترنت. ماذا عن مدى تعقيد هذه الخوارزمية؟ هل ستكون خطية أيضًا، O(N)؟ لا، لن يحدث ذلك. ففي نهاية المطاف، لا تهتم الشاحنة بكمية التحميل التي تقوم بها - فهي ستظل تسير بنفس السرعة تقريبًا وتصل في الوقت المحدد. سواء كان لدينا 800 تيرابايت، أو 10 أضعاف البيانات، ستصل الشاحنة إلى هناك خلال 5 أيام. بمعنى آخر، تتميز خوارزمية توصيل البيانات عبر الشاحنات بتعقيد مستمر . "الثابت" يعني أنه لا يعتمد على البيانات التي تم تمريرها إلى الخوارزمية. ضع محرك أقراص فلاش سعة 1 جيجابايت في الشاحنة وسيصل خلال 5 أيام. ضع الأقراص التي تحتوي على 800 تيرابايت من البيانات هناك، وسوف تصل خلال 5 أيام. عند استخدام Big-O، يُشار إلى التعقيد الثابت بالرمز O(1) . منذ أن تعرفنا على O(N) وO(1) ، دعونا نلقي نظرة الآن على المزيد من الأمثلة "المبرمجة" :) لنفترض أنه تم إعطاؤك مصفوفة مكونة من 100 رقم، والمهمة هي طباعة كل منها على وحدة التحكم. تكتب حلقة عادية forتؤدي هذه المهمة

int[] numbers = new int[100];
// ..заполняем массив числами

for (int i: numbers) {
   System.out.println(i);
}

ما هو مدى تعقيد الخوارزمية المكتوبة؟ خطي، O(N). يعتمد عدد الإجراءات التي يجب على البرنامج تنفيذها على عدد الأرقام التي تم تمريرها إليه بالضبط. إذا كان هناك 100 رقم في المصفوفة، فسيكون هناك 100 إجراء (مخرجات على الشاشة)، وإذا كان هناك 10000 رقم في المصفوفة، فسيلزم تنفيذ 10000 إجراء. هل يمكن تحسين الخوارزمية لدينا؟ لا. على أية حال، سيتعين علينا جعل N يمر عبر المصفوفة وتنفيذ N مخرجات إلى وحدة التحكم. دعونا ننظر إلى مثال آخر.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

لدينا رقم فارغ LinkedListندخل فيه عدة أرقام. نحتاج إلى تقدير مدى تعقيد الخوارزمية الخاصة بإدراج رقم واحد في LinkedListمثالنا، وكيف يعتمد ذلك على عدد العناصر في القائمة. الجواب هو O(1) - التعقيد المستمر . لماذا؟ يرجى ملاحظة: في كل مرة نقوم بإدخال رقم في بداية القائمة. بالإضافة إلى ذلك، كما تتذكر، عند إدراج الأرقام في LinkedListالعناصر، لا يتم نقلها إلى أي مكان - تتم إعادة تعريف الروابط (إذا نسيت فجأة كيفية عمل LinkedList، فقم بإلقاء نظرة على إحدى محاضراتنا القديمة ). إذا كان الرقم الأول في قائمتنا الآن هو الرقم х، وقمنا بإدراج الرقم y في بداية القائمة، فكل ما نحتاجه هو:

x.previous  = y;
y.previous = null;
y.next = x;

بالنسبة لإعادة تعريف المرجع هذا، لا يهمنا عدد الأرقام الموجودة الآنLinkedList - واحد على الأقل، مليار على الأقل. سيكون تعقيد الخوارزمية ثابتًا - O(1).

التعقيد اللوغاريتمي

لا تُصب بالذعر! :) إذا كانت كلمة "لوغاريتمي" تجعلك ترغب في إغلاق المحاضرة وعدم مواصلة القراءة، فانتظر بضع دقائق. لن تكون هناك صعوبات رياضية هنا (هناك الكثير من هذه التفسيرات في أماكن أخرى)، وسوف نقوم بتحليل جميع الأمثلة "على الأصابع". تخيل أن مهمتك هي العثور على رقم محدد واحد في مجموعة مكونة من 100 رقم. بتعبير أدق، تحقق مما إذا كان هناك على الإطلاق. بمجرد العثور على الرقم المطلوب، يجب إيقاف البحث، ويجب أن يتم عرض الإدخال "تم العثور على الرقم المطلوب!" في وحدة التحكم. فهرسها في المصفوفة = ...." كيف يمكنك حل مثل هذه المشكلة؟ الحل واضح هنا: تحتاج إلى تكرار عناصر المصفوفة واحدًا تلو الآخر، بدءًا من العنصر الأول (أو الأخير) والتحقق مما إذا كان الرقم الحالي يتطابق مع الرقم المطلوب. وبناء على ذلك، فإن عدد الإجراءات يعتمد بشكل مباشر على عدد العناصر الموجودة في المصفوفة. إذا كان لدينا 100 رقم، فسنحتاج إلى الانتقال إلى العنصر التالي 100 مرة والتحقق من الرقم بحثًا عن تطابق 100 مرة. إذا كان هناك 1000 رقم، فسيكون هناك 1000 خطوة فحص، ومن الواضح أن هذا تعقيد خطي، O(N) . سنضيف الآن توضيحًا واحدًا إلى مثالنا: يتم فرز المصفوفة التي تحتاج إلى العثور على رقم فيها بترتيب تصاعدي . هل هذا يغير شيئا لمهمتنا؟ لا يزال بإمكاننا البحث عن الرقم المطلوب بالقوة الغاشمة. ولكن يمكننا استخدام خوارزمية البحث الثنائي المعروفة بدلاً من ذلك . في الصف العلوي من الصورة نرى مصفوفة مرتبة. نحتاج فيه إلى العثور على الرقم 23. بدلاً من التكرار على الأرقام، نقوم ببساطة بتقسيم المصفوفة إلى جزأين والتحقق من متوسط ​​الرقم في المصفوفة. نجد الرقم الموجود في الخلية 4 ونتحقق منه (الصف الثاني في الصورة). هذا الرقم هو 16، ونحن نبحث عن 23. والرقم الحالي أقل. ماذا يعني هذا؟ أن جميع الأرقام السابقة (الموجودة حتى الرقم 16) لا تحتاج إلى التحقق : فهي بالتأكيد ستكون أقل من الرقم الذي نبحث عنه، لأن مصفوفتنا مرتبة! لنواصل البحث بين العناصر الخمسة المتبقية. انتبه:لقد قمنا بفحص واحد فقط، ولكننا قمنا بالفعل بحذف نصف الخيارات الممكنة. لم يتبق لدينا سوى 5 عناصر. سنكرر خطوتنا - نقسم المصفوفة المتبقية مرة أخرى على 2 ونأخذ العنصر الأوسط مرة أخرى (السطر 3 في الشكل). هذا الرقم هو 56، وهو أكبر من الرقم الذي نبحث عنه. ماذا يعني هذا؟ أن نتجاهل 3 خيارات أخرى - الرقم 56 نفسه، ورقمين بعده (بالتأكيد أكبر من 23، لأن المصفوفة مرتبة). لم يتبق لدينا سوى رقمين للتحقق منهما (الصف الأخير في الشكل) - الأرقام التي تحتوي على فهارس المصفوفة 5 و6. نتحقق من الرقم الأول، وهذا ما كنا نبحث عنه - الرقم 23! فهرسه = 5! دعونا نلقي نظرة على نتائج الخوارزمية، وبعد ذلك سوف نفهم مدى تعقيدها. (بالمناسبة، أنت الآن تفهم سبب تسميته بالثنائي: جوهره هو تقسيم البيانات باستمرار على 2). والنتيجة مثيرة للإعجاب! إذا كنا نبحث عن الرقم المطلوب باستخدام البحث الخطي، فسنحتاج إلى 10 عمليات تحقق، ولكن مع البحث الثنائي قمنا بذلك في 3! في أسوأ الأحوال، سيكون هناك 4 منهم، إذا كان الرقم الذي نحتاجه في الخطوة الأخيرة هو الثاني، وليس الأول. وماذا عن تعقيدها؟ هذه نقطة مثيرة للاهتمام للغاية :) تعتمد خوارزمية البحث الثنائي على عدد العناصر الموجودة في المصفوفة بشكل أقل بكثير من خوارزمية البحث الخطي (أي التعداد البسيط). مع وجود 10 عناصر في المصفوفة، سيحتاج البحث الخطي إلى 10 عمليات فحص كحد أقصى، وسيحتاج البحث الثنائي إلى 4 عمليات فحص كحد أقصى. الفرق 2.5 مرة. لكن بالنسبة لمصفوفة مكونة من 1000 عنصر، سيحتاج البحث الخطي إلى 1000 عملية تحقق، وسيحتاج البحث الثنائي إلى 10 عمليات تحقق فقط ! الفرق بالفعل 100 مرة! انتبه:زاد عدد العناصر في المصفوفة 100 مرة (من 10 إلى 1000)، وزاد عدد عمليات التحقق اللازمة للبحث الثنائي 2.5 مرة فقط - من 4 إلى 10. وإذا وصلنا إلى 10000 عنصر ، فسيكون الفرق أكثر إثارة للإعجاب: 10000 عمليات فحص للبحث الخطي، وإجمالي 14 عملية فحص للبحث الثنائي. ومرة أخرى: زاد عدد العناصر 1000 مرة (من 10 إلى 10000)، لكن عدد الشيكات زاد 3.5 مرة فقط (من 4 إلى 14). تعقيد خوارزمية البحث الثنائي هو لوغاريتمي ، أو في تدوين Big-O، O(log n) . لماذا هو يسمى ذلك؟ اللوغاريتم هو معكوس الأسي. يتم استخدام اللوغاريتم الثنائي لحساب أس 2. على سبيل المثال، لدينا 10000 عنصر نحتاج إلى دراستها باستخدام البحث الثنائي. الآن لديك صورة أمام عينيك، وأنت تعلم أن هذا يتطلب 14 فحصًا كحد أقصى. ولكن ماذا لو لم تكن هناك صورة أمام عينيك، وتحتاج إلى حساب العدد الدقيق للفحوصات اللازمة؟ يكفي الإجابة على سؤال بسيط: إلى أي قوة يجب رفع الرقم 2 بحيث تكون النتيجة >= عدد العناصر التي يتم فحصها؟ مقابل 10000 ستكون القوة الرابعة عشرة. 2 أس 13 صغير جدًا (8192) لكن 2 أس 14 = 16384 ، هذا الرقم يحقق شرطنا (هو >= عدد العناصر في المصفوفة). لقد وجدنا اللوغاريتم - 14. هذا هو عدد الشيكات التي نحتاجها! :) الخوارزميات وتعقيدها موضوع واسع جدًا بحيث لا يمكن إدراجه في محاضرة واحدة. لكن معرفة ذلك أمر مهم للغاية: في العديد من المقابلات، ستواجه مشكلات خوارزمية. من الناحية النظرية، يمكنني أن أوصيك بعدة كتب. مكان جيد للبدء هو " Grocking Algorithms ": على الرغم من أن الأمثلة الموجودة في الكتاب مكتوبة بلغة بايثون، إلا أن لغة الكتاب وأمثلته بسيطة للغاية. الخيار الأفضل للمبتدئين، كما أنه صغير الحجم. قراءة أكثر جدية: كتب روبرت لافوريت وروبرت سيدجويك . كلاهما مكتوب بلغة Java، مما سيجعل التعلم أسهل قليلاً بالنسبة لك. بعد كل شيء، أنت على دراية تامة بهذه اللغة! :) بالنسبة للطلاب ذوي الخلفية الرياضية الجيدة، فإن الخيار الأفضل هو كتاب توماس كورمان . لكنك لن تكتفي بالنظرية فقط! "اعرف" != "كن قادرًا" يمكنك التدرب على حل مشكلات الخوارزمية على HackerRank و Leetcode . غالبًا ما يتم استخدام المشكلات من هناك حتى أثناء المقابلات في Google وFacebook، لذلك لن تشعر بالملل بالتأكيد :) لتعزيز مادة المحاضرة، أنصحك بمشاهدة مقطع فيديو ممتاز حول Big-O على YouTube. نراكم في المحاضرات القادمة! :)