يعد البحث عن عنصر في مصفوفة إحدى العمليات الرئيسية عند العمل مع البيانات. يعتمد وقت تنفيذ البرنامج وأداء النظام بأكمله على فعالية هذه العملية. التعقيد الزمني للبحث في مصفوفة هو مقياس لعدد العمليات المطلوبة للعثور على عنصر في المصفوفة. يتم قياسه كدالة لحجم المصفوفة ويسمح لك بمقارنة فعالية خوارزميات البحث المختلفة.
يعتمد التعقيد الزمني للبحث في مصفوفة منتظمة على طريقة تنظيم البيانات. إذا لم يتم فرز المصفوفة ، فإن الطريقة الأبسط والأكثر سهولة للبحث هي التكرار المتسلسل من خلال عناصر المصفوفة. ومع ذلك ، فإن هذه الطريقة لها تعقيد زمني لـ ا(ن) ، أين ن هو عدد العناصر في المصفوفة. هذا يعني أن وقت البحث سيزداد بشكل متناسب مع زيادة حجم المصفوفة ويمكن أن يكون طويلا جدا للمصفوفات الكبيرة.
هناك أيضا خوارزميات بحث صفيف أكثر كفاءة بناء على مبادئ مختلفة. يتطلب بعضها الفرز المسبق للمصفوفة ، الأمر الذي قد يستغرق وقتا إضافيا. ومع ذلك ، نظرا لتعقيد الوقت المنخفض لهذه الخوارزميات ، يمكن أن تكون مرتبة من حيث الحجم أسرع من التكرار المتسلسل بأحجام صفيف كبيرة.
- تحديد التعقيد الزمني للبحث
- خوارزمية البحث الخطي
- خوارزمية البحث الثنائية
- التعقيد الزمني للبحث الخطي
- تعقيد الوقت للبحث الثنائي
- مقارنة الصعوبات الزمنية للبحث الخطي والثنائي
- البحث الخطي
- بحث ثنائي
- مقارنة صعوبات الوقت
- سؤال وجواب
- ما هو تعقيد الوقت من البحث عن عنصر في مجموعة العادية?
- كيف يعمل البحث عن عنصر في صفيف منتظم?
- ماذا يحدث إذا كان الصفيف يحتوي على عناصر مكررة?
- ما هي صعوبة العثور على عنصر في مصفوفة مرتبة?
تحديد التعقيد الزمني للبحث
التعقيد الزمني للبحث في مصفوفة عادية هو مقياس لعدد العمليات المطلوبة لإجراء بحث عن عنصر معين في المصفوفة. يسمح لك بتقييم فعالية خوارزمية البحث والتنبؤ بأدائها اعتمادا على حجم المصفوفة.
عادة ما يتم قياس تعقيد الوقت في عدد المقارنات بين العنصر المطلوب وعناصر المصفوفة ، وكذلك في عدد التكرارات للحلقة المطلوبة لاجتياز المصفوفة بأكملها.
كلما قل عدد العمليات المطلوبة للعثور على عنصر ، زادت سرعة عمل الخوارزمية وكلما كان تعقيد الوقت أفضل.
خوارزميات البحث الأكثر شيوعا هي البحث الخطي والبحث الثنائي. البحث الخطي له تعقيد زمني لـ ا (ن) ، أين ن هو عدد العناصر في المصفوفة. هذا يعني أن وقت البحث يزداد خطيا مع زيادة حجم الصفيف.
البحث الثنائي ، بدوره ، له تعقيد زمني لـ ا(سجل ن) ، مما يعني زيادة لوغاريتمية في وقت البحث مع زيادة حجم المصفوفة. هذه الخوارزمية أكثر كفاءة للبحث عن العناصر في المصفوفات المصنفة.
عند اختيار خوارزمية البحث ، من الضروري مراعاة حجم المصفوفة والدقة المطلوبة للبحث. بالنسبة للمصفوفات الصغيرة ، يمكن أن يكون البحث الخطي فعالا للغاية ، ولكن بالنسبة للمصفوفات الأكبر ، يمكن أن يعمل البحث الثنائي بشكل أسرع ويوفر الموارد.
خوارزمية البحث الخطي
البحث الخطي هو أبسط خوارزمية للبحث عن عنصر في مصفوفة عادية. يقوم بالبحث عن طريق مقارنة كل عنصر من عناصر المصفوفة بالتتابع مع القيمة المستهدفة.
يمكن تمثيل عملية البحث الخطي على النحو التالي:
- انتقل من خلال جميع عناصر المصفوفة ، بدءا من أول واحد.
- قارن كل عنصر بالقيمة المستهدفة.
- إذا كان العنصر يساوي القيمة المستهدفة ، فسيكون البحث ناجحا ويتم إرجاع فهرسه.
- إذا تم الوصول إلى نهاية المصفوفة ولم يتم العثور على القيمة المستهدفة ، يفشل البحث ويتم إرجاع -1.
تعقيد خوارزمية البحث الخطي هو ا (ن) ، أين ن هو عدد العناصر في المصفوفة. هذا يعني أنه في أسوأ الحالات ، سيتعين عليك المرور عبر المصفوفة بأكملها للبحث عن عنصر.
ميزة البحث الخطي هي بساطته وتعدد استخداماته. ومع ذلك ، عند العمل مع المصفوفات الكبيرة أو عند الحاجة إلى عمليات بحث متكررة ، يمكن لخوارزميات أكثر كفاءة مثل البحث الثنائي أو التجزئة تحقيق نتائج أسرع.
خوارزمية البحث الثنائية
تعد خوارزمية البحث الثنائي واحدة من أكثر الطرق فعالية للعثور على عنصر في مصفوفة مرتبة. يعتمد على مبدأ تقسيم مساحة البحث إلى نصفين ويمكن أن يكون أسرع بكثير من البحث الخطي البسيط.
باستخدام بحث خطي بسيط ، نكرر جميع عناصر المصفوفة ، ونقارن كل عنصر بالقيمة المطلوبة ونعيد فهرس العنصر إذا تم العثور عليه. هذا النهج له تعقيد زمني لـ ا (ن) ، أين ن هو عدد العناصر في المصفوفة.
تستخدم خوارزمية البحث الثنائي نهجا مختلفا. يتطلب مصفوفة مرتبة ويقسمها إلى قسمين. ثم يقارن القيمة المطلوبة مع العنصر الموجود في منتصف المصفوفة. إذا كانت القيمة أقل ، يستمر البحث على الجانب الأيسر ، وإلا على اليمين.
خطوات خوارزمية البحث الثنائي:
- تعيين الحدود اليسرى واليمنى للبحث
- احسب متوسط المؤشر بين الحدود اليسرى واليمنى
- قارن قيمة عنصر المؤشر المتوسط بالقيمة المطلوبة
- إذا كانت القيم متساوية ، فقم بإرجاع فهرس العنصر
- إذا كانت القيمة المطلوبة أقل ، فقم بتحديث الحد الأيمن إلى متوسط الفهرس ناقص واحد وانتقل إلى الخطوة 2
- إذا كانت القيمة المطلوبة أكبر ، فقم بتحديث الحد الأيسر إلى متوسط الفهرس زائد واحد وانتقل إلى الخطوة 2
- كرر الخطوات من 2 إلى 6 حتى يصبح الحد الأيسر أكبر من الحد الأيمن أو يتم العثور على العنصر
. خوارزمية البحث الثنائية لها تعقيد زمني لـ ا (سجل ن) ، أين ن هو عدد العناصر في المصفوفة. هذا يعني أن وقت تنفيذ الخوارزمية يزيد لوغاريتميا مع زيادة حجم الصفيف. لذلك ، يمكن أن يكون البحث الثنائي فعالا جدا حتى بالنسبة للمصفوفات الكبيرة.
ومع ذلك ، قبل استخدام خوارزمية البحث الثنائية ، من الضروري فرز المصفوفة. قد يستغرق فرز المصفوفة وقتا إضافيا وقد يكون عملية غير عملية إذا تغيرت المصفوفة بشكل متكرر.
بشكل عام ، خوارزمية البحث الثنائية فعالة وتستخدم على نطاق واسع للبحث عن العناصر في المصفوفات المصنفة. يقلل من عدد المقارنات ويقلل من وقت تنفيذ البحث.
التعقيد الزمني للبحث الخطي
البحث الخطي هو أحد أبسط طرق البحث عن عنصر في مصفوفة. يتم تنفيذ ذلك عن طريق التكرار بالتتابع من خلال جميع عناصر المصفوفة حتى يتم العثور على العنصر المطلوب أو يتم تمرير جميع العناصر من خلال.
يعتمد التعقيد الزمني للبحث الخطي على حجم المصفوفة وموقع العنصر المطلوب فيه. في أفضل الأحوال ، عندما يكون العنصر المطلوب في بداية المصفوفة ، سيكون وقت البحث ضئيلا-س (1) ، أي ثابت. في أسوأ الحالات ، عندما يكون العنصر المطلوب في نهاية المصفوفة أو مفقودا منه ، سيكون وقت البحث هو الحد الأقصى — س(ن) ، أين ن هو عدد العناصر في المصفوفة. في المتوسط ، سيكون وقت البحث متناسبا مع ن / 2-س (ن / 2) ، ولكن يمكن تبسيط هذا النوع من الكتابة إلى س(ن).
نظرا لبساطة التنفيذ وتعقيد الوقت المنخفض في أحسن الأحوال ، غالبا ما يتم استخدام البحث الخطي في المواقف التي يكون فيها حجم المصفوفة صغيرا أو عندما لا يتم فرز المصفوفة.
ومع ذلك ، تجدر الإشارة إلى أنه مع وجود كمية كبيرة من البيانات وعمليات البحث المستمرة ، قد يكون البحث الخطي غير فعال. في هذه الحالة ، يجدر الانتباه إلى خوارزميات البحث الأخرى ، مثل البحث الثنائي أو جداول التجزئة.
تعقيد الوقت للبحث الثنائي
البحث الثنائي هو خوارزمية فعالة للبحث عن عنصر في مصفوفة أو قائمة مرتبة. يعمل عن طريق تقسيم المصفوفة إلى جزأين ومقارنة قيمة العنصر المطلوب بالعنصر الموجود في المنتصف. إذا كان العنصر المطلوب يساوي العنصر الموجود في المنتصف ، فسيتم إكمال البحث. خلاف ذلك ، يستمر البحث في أحد نصفي المصفوفة ، ويتم تحديد النصف الذي يمكن تحديد العنصر المطلوب فيه فقط.
التعقيد الزمني للبحث الثنائي هو ا (سجل ن) ، أين ن هو عدد العناصر في المصفوفة. هذا يعني أن وقت تنفيذ الخوارزمية لا يزيد بشكل متناسب مع عدد العناصر ، ولكن لوغاريتميا. هذا التعقيد الوقت يجعل البحث الثنائي فعالة جدا للبحث صفائف كبيرة. على سبيل المثال ، عند البحث في مصفوفة من 1000 عنصر ، يتطلب البحث الثنائي حوالي 10 مقارنات فقط.
للحصول على أفضل أداء ، يتطلب البحث الثنائي طلب المصفوفة. إذا لم يتم فرز المصفوفة ، فمن الضروري فرزها أولا ، الأمر الذي قد يستغرق وقتا إضافيا. ومع ذلك ، عند استخدام البحث الثنائي في مصفوفة مرتبة ، يمكن تحقيق كفاءة عالية وتوفير الوقت.
مقارنة الصعوبات الزمنية للبحث الخطي والثنائي
عند العمل مع صفائف البيانات ، تتمثل إحدى العمليات المهمة في البحث عن عنصر في المصفوفة. هناك العديد من الخوارزميات التي تسمح لك بالبحث: الخطية والثنائية. دعونا ننظر إلى ميزاتها والاختلافات في مقارنة صعوبات الوقت.
البحث الخطي
البحث الخطي هو أبسط خوارزمية للبحث عن عنصر في صفيف. وهو يتألف من التكرار المتسلسل من خلال جميع عناصر المصفوفة ومقارنتها بالقيمة المطلوبة. إذا تم العثور على عنصر ، فإن الخوارزمية ترجع موضعها في المصفوفة ، وإلا فإنها ترجع قيمة تشير إلى عدم وجود العنصر.
التعقيد الزمني للبحث الخطي في أسوأ الحالات هو ا (ن) ، أين ن هو حجم المصفوفة. هذا يعني أن وقت تنفيذ الخوارزمية يعتمد خطيا على حجم المصفوفة. في الحالة المتوسطة وفي أفضل الأحوال ، سيكون التعقيد أيضا س (ن).
بحث ثنائي
يتم تطبيق البحث الثنائي فقط على صفائف البيانات التي تم فرزها. على عكس البحث الخطي ، فإنه لا يتطلب التكرار من خلال جميع عناصر المصفوفة. يعتمد البحث الثنائي على مبدأ تقسيم المصفوفة إلى نصفين حتى يتم العثور على العنصر المطلوب.
خوارزمية البحث الثنائية هي كما يلي:
- قم بتعيين القيم الأولية لحدود البحث: الحد الأدنى (منخفض) يساوي 0 والحد الأعلى (مرتفع) يساوي حجم المصفوفة ناقص 1.
- تأكد من أن الحد الأدنى أقل من أو يساوي الحد الأعلى. إذا تم استيفاء هذا الشرط ، فتابع البحث ، وإلا فلن يتم العثور على العنصر.
- احسب متوسط مؤشر العنصر: وسط = (منخفض + مرتفع) / 2.
- قارن العنصر المطلوب بالقيمة الموجودة في الموضع الموجود. إذا كانت متساوية ، فإن البحث ناجح ، وإلا قم بتغيير حدود البحث وفقا لنتيجة المقارنة.
- إذا كان العنصر المطلوب أكبر من القيمة في الموضع الذي تم العثور عليه ، فقم بتغيير الحد الأدنى إلى الوسط + 1 وانتقل إلى الخطوة 2.
- إذا كان العنصر المطلوب أقل من القيمة في الموضع الذي تم العثور عليه ، فقم بتغيير الحد الأعلى إلى الوسط 1 وانتقل إلى الخطوة 2.
التعقيد الزمني للبحث الثنائي في أسوأ الحالات هو ا (سجل ن) ، أين ن هو حجم المصفوفة. هذا يعني أن وقت تنفيذ الخوارزمية يعتمد لوغاريتميا على حجم المصفوفة. في الحالة المتوسطة وأفضل حالة ، سيكون التعقيد أيضا س (سجل ن).
مقارنة صعوبات الوقت
بمقارنة التعقيد الزمني للبحث الخطي والثنائي ، يمكننا استخلاص الاستنتاجات التالية:
- يحتوي البحث الخطي على تعقيد زمني خطي ، مما يعني أن وقت تنفيذ الخوارزمية يزداد بما يتناسب مع حجم المصفوفة. هذا يجعلها غير فعالة لكميات كبيرة من البيانات.
- يحتوي البحث الثنائي على تعقيد زمني لوغاريتمي ، مما يعني أن وقت تنفيذ الخوارزمية ينمو بشكل أبطأ من حجم المصفوفة. هذا يجعل البحث عن عنصر في صفائف بيانات كبيرة مرتبة أكثر كفاءة.
- ومع ذلك ، للبحث في المصفوفات الصغيرة ، يمكن أن يكون البحث الخطي أكثر كفاءة ، لأنه لا يتطلب الفرز المسبق للمصفوفة.
لذلك ، عند اختيار خوارزمية البحث ، من الضروري مراعاة حجم المصفوفة وترتيبها. البحث الخطي بسيط وفعال للمصفوفات الصغيرة ، بينما يفضل البحث الثنائي للمصفوفات الكبيرة المصنفة.
سؤال وجواب
ما هو تعقيد الوقت من البحث عن عنصر في مجموعة العادية?
التعقيد الزمني للبحث عن عنصر في مصفوفة عادية هو ا (ن) ، أين ن هو عدد العناصر في المصفوفة.
كيف يعمل البحث عن عنصر في صفيف منتظم?
عند البحث عن عنصر في مصفوفة عادية ، تتم مقارنة كل عنصر من عناصر المصفوفة بالتتابع مع العنصر المطلوب. إذا تم العثور على العنصر ، ينتهي البحث. إذا لم يتم العثور على العنصر ، يستمر البحث حتى نهاية المصفوفة.
ماذا يحدث إذا كان الصفيف يحتوي على عناصر مكررة?
إذا كانت المصفوفة تحتوي على عناصر مكررة ، فسيتم العثور على العنصر الأول المطابق لمعايير البحث أثناء البحث. ثم يتم الانتهاء من البحث ، ولا تؤخذ العناصر المكررة المتبقية في الاعتبار.
ما هي صعوبة العثور على عنصر في مصفوفة مرتبة?
التعقيد الزمني للبحث عن عنصر في مصفوفة مرتبة هو ا (سجل ن) ، أين ن هو عدد العناصر في المصفوفة. هذا يرجع إلى حقيقة أنه يمكن استخدام خوارزمية بحث ثنائية في البحث.