البحث في هيكل البيانات: شرح طرق بحث مختلفة

شبكة الاتصالات آخذة في التوسع ، وبالتالي فإن الناس يستخدمون الإنترنت! تتجه الشركات إلى التقنيات الرقمية من أجل الإدارة الفعالة. البيانات التي تم إنشاؤها على الإنترنت آخذة في الازدياد ، وبالتالي أصبحت مجموعات البيانات معقدة. من الضروري تنظيم البيانات وإدارتها والوصول إليها وتحليلها بعناية وكفاءة ، وهيكل البيانات هي التقنية الأكثر فائدة ، وتركز المقالة على ذلك!

هيكل البيانات

في علوم الكمبيوتر ، تعد هياكل البيانات هي الأساس لأنواع البيانات المجردة (ADT) ، حيث تمثل ADT الشكل المنطقي لنوع البيانات. يتم تنفيذ التخطيط المادي لنوع البيانات باستخدام بنية البيانات. تُستخدم أنواع هياكل البيانات المختلفة لأنواع مختلفة من التطبيقات ؛ البعض متخصص في مهام معينة.

هيكل البيانات عبارة عن مجموعة من قيم البيانات والعلاقات فيما بينها ، والعمليات والوظائف التي تنطبق على البيانات. يساعد في تنظيم وإدارة وتخزين البيانات بتنسيق معين. وبالتالي ، يمكن للمستخدمين الوصول بسهولة إلى البيانات وتعديلها بكفاءة.

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

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

ما هو البحث في هيكل البيانات؟

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

طرق البحث

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

• البحث المتسلسل

يتم اجتياز المصفوفة أو قائمة العناصر بالتسلسل أثناء التحقق من كل مكون من مكونات المجموعة.

على سبيل المثال ، البحث الخطي.

• البحث الفاصل

يتم تضمين الخوارزميات المصممة صراحة للبحث في هياكل البيانات المصنفة في البحث الفاصل. كفاءة هذه الخوارزميات أفضل بكثير من خوارزميات البحث الخطي.

على سبيل المثال ، بحث ثنائي ، بحث لوغاريتمي.

يتم فحص هذه الطرق بناءً على الوقت الذي تستغرقه الخوارزمية للبحث عن عنصر يطابق عنصر البحث في مجموعات البيانات ويتم تقديمها بواسطة ،

• أفضل وقت ممكن
• متوسط ​​الوقت
• أسوأ الأوقات

المخاوف الأساسية تتعلق بأسوأ الأوقات التي تؤدي إلى تنبؤات مضمونة لأداء الخوارزمية كما يسهل حسابها مقارنة بمتوسط ​​الأوقات.

لتوضيح الأمثلة والمفاهيم في هذه المقالة ، يتم النظر في العناصر "n" في جمع البيانات بأي تنسيق بيانات. تستخدم العمليات السائدة لتبسيط التحليل ومقارنة الخوارزمية. للبحث في بنية بيانات ، تعتبر المقارنة عملية سائدة ، والتي يتم الإشارة إليها بواسطة O () ويتم نطقها كـ "big-Oh" أو "Oh".

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

دعنا نحصل على رؤية تفصيلية للبحث الخطي والبحث الثنائي في بنية البيانات.

البحث الخطي

تبحث خوارزمية البحث الخطي في جميع العناصر في المصفوفة بالتسلسل. أفضل وقت للتنفيذ هو واحد ، في حين أن أسوأ وقت تنفيذ هو n ، حيث n هو العدد الإجمالي للعناصر في صفيف البحث.

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

البحث الخطي له بعض التعقيدات كما هو موضح أدناه:

• تعقيد الفضاء

التعقيد المكاني للبحث الخطي هو O (n) لأنه لا يستخدم أي مساحة إضافية حيث n هو عدد العناصر في المصفوفة.

• تعقيد الوقت

* أفضل حالة تعقيد = O (1) يحدث عندما يكون عنصر البحث موجودًا في العنصر الأول في صفيف البحث.

* التعقيد الأسوأ للحالة = O (n) يحدث عندما لا يكون عنصر البحث موجودًا في مجموعة العناصر أو المصفوفة.

* متوسط ​​التعقيد = O (n) يشار إليه عندما يكون العنصر موجودًا في مكان ما في صفيف البحث.

مثال،

لنأخذ مجموعة من العناصر كما هو موضح أدناه:

45 ، 78 ، 12 ، 67 ، 08 ، 51 ، 39 ، 26

للعثور على '51' في مجموعة مكونة من 8 عناصر مذكورة أعلاه ، ستقوم خوارزمية البحث الخطي بفحص كل عنصر بالتسلسل حتى يشير مؤشره إلى 51 في مساحة الذاكرة. يستغرق إيجاد 51 في المصفوفة O (6) وقتًا. للعثور على 12 ، في المصفوفة أعلاه ، يستغرق الأمر O (3) ، بينما ، بالنسبة لـ 26 ، يتطلب وقت O (8).

بحث ثنائي

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

يحتاج البحث الثنائي إلى ترتيب فرز للعناصر. إنه أسرع من خوارزمية البحث الخطي. تعمل على مبدأ فرق تسد.

تعقيد وقت التشغيل = O (تسجيل ن)

تحتوي خوارزمية البحث الثنائي على تعقيدات كما هو موضح أدناه:

• أسوأ حالة تعقيد = O (n log n)
• متوسط ​​التعقيد = O (ن سجل ن)
• أفضل درجة تعقيد للحالة = O (1)

مثال،

لنأخذ خوارزمية مرتبة من 08 عنصرًا:

08 ، 12 ، 26 ، 39 ، 45 ، 51 ، 67 ، 78

للعثور على 51 في مصفوفة من العناصر أعلاه ،

ستقسم الخوارزمية المصفوفة إلى صفيفتين ، 08 ، 12 ، 26 ، 39 و 45 ، 51 ، 67 ، 78

نظرًا لأن 51 أكبر من 39 ، فسيبدأ البحث عن العناصر الموجودة على الجانب الأيمن للمصفوفة.

وسوف يقسم كذلك إلى قسمين مثل 45 و 51 و 67 و 78

نظرًا لأن 51 أصغر من 67 ، فسيبدأ البحث على يسار تلك المصفوفة الفرعية.

يتم تقسيم هذه المصفوفة الفرعية مرة أخرى إلى قسمين هما 45 و 51.

نظرًا لأن 51 هو الرقم المطابق لعنصر البحث ، فإنه سيعيد رقم الفهرس الخاص به لهذا العنصر في المصفوفة.

وسيستنتج أن عنصر البحث 51 يقع في الموضع السادس في المصفوفة.

يقلل البحث الثنائي الوقت إلى النصف حيث يتم تقليل عدد المقارنة بشكل كبير من خوارزمية البحث الخطي.

اقرأ: أنواع هياكل البيانات في بايثون

بحث الاستيفاء

إنه متغير محسّن لخوارزمية البحث الثنائي ويعمل على موضع فحص عنصر البحث. على غرار خوارزميات البحث الثنائي ، يعمل بكفاءة فقط على جمع البيانات المصنفة.

أسوأ وقت تنفيذ = O (n)

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

خاتمة

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

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

تعد بنية البيانات جزءًا أساسيًا من برمجة الكمبيوتر أثناء التعامل مع مجموعات البيانات. يحتاج المبرمجون والمطورون إلى الاستمرار في تحديث وتطوير مهاراتهم بالأساسيات والتحديثات في تقنيات برمجة الكمبيوتر. يجب على المبرمجين الذين يتعاملون مع بنية البيانات اختيار الدورات في كثير من الأحيان.

إذا كنت مهتمًا بمعرفة المزيد عن علم البيانات ، فراجع برنامج IIIT-B & upGrad التنفيذي PG في علوم البيانات الذي تم إنشاؤه للمهنيين العاملين ويقدم أكثر من 10 دراسات حالة ومشاريع ، وورش عمل عملية عملية ، وإرشاد مع خبراء الصناعة ، وجهاً لوجه مع مرشدين في هذا المجال ، وأكثر من 400 ساعة من التعلم والمساعدة في العمل مع الشركات الكبرى.

استعد لمهنة المستقبل

برنامج الشهادة المتقدمة في علوم البيانات