رتبها

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

1- البحث المتسلسل:
في هذا ، يتم اجتياز القائمة أو المصفوفة بالتسلسل ويتم فحص كل عنصر. على سبيل المثال: البحث الخطي
2- البحث الفاصل:
تم تصميم هذه الخوارزميات خصيصا للبحث في هياكل البيانات المصنفة، يعد هذا النوع من خوارزميات البحث أكثر فاعلية حيث يستهدف بشكل متكرر مركز بنية البحث

♦️ أمثلة لخوارزميات البحث:
1- Linear Search
2- Binary Search
3- Quickselect Algorithm
4- Hash table
5- Naïve string search or pattern matching algorithm (brute force)
6- Knuth, Morris and Pratt (KMP)
7- Binary trees

1- Linear Search:
البحث في جميع العناصر واحدا تلو الآخر، الوقت الخاص ب time complexity هو o(n)
نادرًا ما يتم استخدام البحث الخطي عمليًا لأن خوارزميات البحث الأخرى مثل خوارزمية البحث الثنائي وجداول التجزئة تسمح بمقارنة البحث بشكل أسرع مع البحث الخطي

2- Binary Search:
هو خوارزمية بحث مستخدمة في مصفوفة مرتبة عن طريق قسمة فترة البحث بشكل متكرر إلى النصف
تتمثل فكرة البحث الثنائي في استخدام المعلومات التي يتم فرز المصفوفة وتقليل التعقيد الزمني إلى O (log n)

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

- خلاف ذلك، قم بتضييقه إلى النصف العلوي
- تحقق بشكل متكرر من النقطة الثانية حتى يتم العثور على القيمة أو يصبح الفاصل الزمني فارغًا

3- Quickselect Algorithm (O(n)):
يستخدم Quickselect نفس الأسلوب العام مثل Quicksort، واختيار عنصر واحد كمحور وتقسيم البيانات إلى عنصرين بناءً على المحور، وفقًا لذلك على أنها أقل من أو أكبر من المحور

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

4- Hash table:
التجزئة hashing هي تقنية أو عملية لتعيين المفاتيح والقيم في جدول التجزئة باستخدام وظيفة التجزئة للوصول بشكل أسرع إلى العناصر، تعتمد كفاءة التعيين على كفاءة دالة التجزئة المستخدمة
مشاكل متعلقة بالتجزئة:
- التصادمات ممكنة
- سيكلف وقت البحث O(n) في أسوأ الحالات

5- Naïve string search or pattern matching algorithm (brute force):
يعد البحث عن الأنماط مشكلة مهمة في علوم الكمبيوتر، عندما نبحث عن سلسلة في ملف أو متصفح أو قاعدة بيانات، يتم استخدام خوارزميات البحث عن الأنماط لإظهار نتائج البحث

تطبيقاته:
- البحث عن الكلمات الأساسية في ملف
- محركات البحث
- البحث في قاعدة البيانات

6- Knuth, Morris and Pratt (KMP):
تستخدم خوارزمية المطابقة KMP خاصية متدهورة (النمط الذي له نفس الأنماط الفرعية يظهر أكثر من مرة في النمط) للنمط ويحسن حالة التعقيد الأسوأ إلى O (n)

الفكرة الأساسية وراء خوارزمية KMP هي:
عندما نكتشف عدم تطابق (بعد بعض التطابقات)، فإننا نعرف بالفعل بعض الأحرف في نص النافذة التالية
نحن نستفيد من هذه المعلومات لتجنب مطابقة الأحرف التي نعرف أنها ستتطابق على أي حال

مثال:
النص: abxabcabcaby
النمط: abcaby
نقارن i من النص و j في النمط حتى يحدث عدم تطابق، نتجاهل أي suffix متكرر والنقطة j في الحرف c في النهاية ونقارنها بـ i حتى يتم العثور على تطابق

7- Binary trees:
هي بنية بيانات شجرة ثنائية تعتمد على العقدة ولها الخصائص التالية:
- تحتوي الشجرة الفرعية اليسرى للعقدة على عقد فقط بمفاتيح أقل من مفتاح العقدة
- تحتوي الشجرة الفرعية اليمنى للعقدة على عقد فقط بمفاتيح أكبر من مفتاح العقدة

- يجب أن تكون كل من الشجرة الفرعية اليمنى واليسرى عبارة عن شجرة بحث ثنائية
يطلق عليها شجرة البحث لأنه يمكن استخدامها للبحث عن وجود رقم في وقت O (log (n))

هل تعلمت شيء جديد؟ لا تنس اعادة التغريد حتى يستفيد الجميع🙏

التصنيفات

المزيد من هذا الكاتب

مواضيع ذات صلة

الأكثر اعجابا

التصنيفات

المزيد من هذا الكاتب

مواضيع ذات صلة

الأكثر اعجابا

فك الثريد