يعد البحث الثنائي أحد أكثر الخوارزميات كفاءة للبحث في مصفوفة مرتبة. ومع ذلك ، عندما يتعلق الأمر بالبحث في قائمة مرتبطة بشكل مضاعف ، قد يختلف تعقيد الخوارزمية.
في مجموعة فرزها ، يتم تنفيذ البحث الثنائي في س (سجل ن) الوقت ، مما يجعلها سريعة جدا وفعالة. ومع ذلك ، في حالة وجود قائمة مرتبطة بشكل مضاعف ، قد يكون البحث عن طريق التقسيم أمرا صعبا ، حيث لا يمكننا الوصول بسرعة إلى عنصر تعسفي في القائمة.
على الرغم من ذلك ، هناك طرق لتحسين خوارزمية البحث الثنائية في قائمة مرتبطة بشكل مضاعف. على سبيل المثال ، يمكنك استخدام مؤشر إلى الموضع الحالي في القائمة ومقارنة قيم عناصر القائمة بالقيمة المطلوبة ، والانتقال إلى اليمين أو اليسار حتى يتم العثور على العنصر المطلوب أو حتى يتم الوصول إلى نهاية القائمة. سيؤدي ذلك إلى تحسين التعقيد المقارب للخوارزمية وإجراء البحث في س (سجل ن) الوقت.
ومع ذلك ، تجدر الإشارة إلى أن التعقيد المقارب للبحث الثنائي في قائمة مرتبطة بشكل مضاعف سيكون أقل من المصفوفة المصنفة. لذلك ، عند اختيار بنية بيانات لتنفيذ البحث ، يجب أن تأخذ في الاعتبار تفاصيل المهمة وعدد العناصر التي يجب العمل بها.
- تعقيد مقارب
- بحث ثنائي
- قائمة مرتبطة بشكل مضاعف
- الحجم ن
- الوصف
- أمثلة
- مقارنة مع الخوارزميات الأخرى
- سؤال وجواب
- ما هو التعقيد المقارب للبحث الثنائي في قائمة مرتبطة بشكل مضاعف?
تعقيد مقارب
التعقيد المقارب هو أداة لتحليل فعالية الخوارزميات. يصف كيف يتغير وقت تنفيذ الخوارزمية أو الذاكرة المستخدمة مع زيادة حجم بيانات الإدخال.
للبحث الثنائي في قائمة مرتبطة بشكل مضاعف ، يعتمد التعقيد المقارب على عدد العناصر في القائمة. دع حجم القائمة يكون ن.
في كل تكرار للبحث الثنائي ، يتم تقسيم القائمة إلى قسمين ثم يتم البحث في أحد هذه الأجزاء. وبالتالي ، بعد كل تكرار ، ينخفض عدد العناصر التي يجب البحث عنها إلى النصف.
مثل هذه الخوارزمية لها تعقيد لوغاريتمي ، يشار إليه بـ س (سجل (ن)). هذا يعني أن وقت تنفيذ الخوارزمية ينمو ببطء مقارنة بالزيادة في حجم القائمة.
لذلك ، يعد البحث الثنائي في قائمة مرتبطة بشكل مضاعف واحدة من أكثر الخوارزميات فعالية للبحث عن العناصر في تسلسل تم فرزه.
بحث ثنائي
البحث الثنائي هو خوارزمية تستخدم للبحث عن عنصر في قائمة مرتبة. وهو يعمل عن طريق تقسيم القائمة إلى قسمين ومقارنة القيمة المطلوبة مع العنصر في منتصف القائمة.
التعقيد المقارب للبحث الثنائي في قائمة حجم مرتبطة بشكل مضاعف ن هو ا (سجل ن). هذا يعني أن وقت تنفيذ الخوارزمية يزيد لوغاريتميا مع زيادة حجم القائمة.
يمكن وصف عملية البحث الثنائي على النحو التالي:
- تحديد منتصف القائمة.
- قارن القيمة المطلوبة بالعنصر الموجود في منتصف القائمة.
- إذا كانت القيمة التي تبحث عنها تساوي العنصر الموجود في منتصف القائمة ، فسيكتمل البحث.
- إذا كانت القيمة المطلوبة أقل من العنصر الموجود في منتصف القائمة ، فكرر العملية للنصف الأيسر من القائمة.
- إذا كانت القيمة المطلوبة أكبر من العنصر الموجود في منتصف القائمة ، فكرر العملية للنصف الأيمن من القائمة.
- كرر الخطوات من 1 إلى 5 حتى يتم العثور على العنصر المطلوب أو حتى يتم تحديد أن العنصر مفقود من القائمة.
البحث الثنائي هو وسيلة فعالة للعثور على عنصر في قائمة مرتبطة بشكل مضاعف. يسمح لك بتقليل عدد الشيكات بمقدار النصف في كل تكرار للبحث وتقليل وقت تنفيذ الخوارزمية. لذلك ، يتم استخدامه على نطاق واسع في مختلف المجالات حيث يكون من الضروري العثور على العناصر بكفاءة بكميات كبيرة من البيانات.
قائمة مرتبطة بشكل مضاعف
القائمة المرتبطة بشكل مضاعف هي بنية بيانات يتم فيها ربط كل عنصر بعنصر القائمة السابق والتالي. يحتوي كل عنصر على قيمة ومؤشرات للعناصر السابقة والتالية. على عكس القائمة المرتبطة منفردة ، تسمح القائمة المرتبطة بشكل مضاعف بالعمليات في كلا الاتجاهين.
الميزة الرئيسية لقائمة مرتبطة بشكل مضاعف مرتبة هي أن عناصر القائمة مرتبة بترتيب تم فرزه. هذا يعني أن كل عنصر له قيمة أكبر من أو تساوي قيمة العنصر السابق ، وأقل من أو تساوي قيمة العنصر التالي. تتيح لك بنية البيانات هذه البحث بكفاءة عن العناصر وإدراج عناصر جديدة.
لتنفيذ قائمة مرتبطة بشكل مضاعف ، تحتاج إلى استخدام فئة أو بنية تحتوي على حقول لقيم العناصر ، بالإضافة إلى مؤشرات للعناصر السابقة والتالية. بالإضافة إلى ذلك ، للبحث عن العناصر وإدراجها بكفاءة ، تحتاج إلى الاحتفاظ بمؤشر إلى بداية القائمة ونهايتها.
واحدة من العمليات المستخدمة بشكل متكرر على قائمة مرتبطة بشكل مضاعف مرتبة هي البحث الثنائي. يسمح لك البحث الثنائي بالعثور بكفاءة على العناصر الموجودة في القوائم المرتبة في س (سجل ن) الوقت ، أين ن هو عدد العناصر في القائمة. تعتمد هذه الخوارزمية على مبدأ تقسيم القائمة إلى نصفين ثم البحث عن العنصر المطلوب في النصف المقابل من القائمة.
الحجم ن
في سياق التعقيد المقارب للبحث الثنائي في قائمة مرتبة مرتبطة بشكل مضاعف ، الحجم ن يلعب دورا مهما. الحجم ن يحدد عدد العناصر في القائمة ويؤثر على أداء الخوارزمية.
كلما زاد حجم ن ، كلما استغرق الأمر وقتا أطول لإجراء بحث ثنائي. وذلك لأن البحث الثنائي يتطلب تقسيم القائمة إلى قسمين والتحقق من العنصر في منتصف القائمة. كلما زاد عدد العناصر في القائمة ، سيتم تنفيذ المزيد من عمليات التقسيم.
ومع ذلك ، نظرا لخصائص البحث الثنائي ، يظل تعقيده المقارب لوغاريتميا ، أي س(سجل ن). هذا يعني أن عدد العمليات المطلوبة لإجراء بحث ثنائي ينمو ببطء مقارنة بنمو الحجم ن.
عندما يتضاعف حجم ن ، يزداد عدد عمليات البحث الثنائية بمقدار واحد فقط. هذا يجعل البحث الثنائي خوارزمية فعالة للعمل مع القوائم الكبيرة المصنفة.
ومع ذلك ، تجدر الإشارة إلى أن التعقيد المقارب للبحث الثنائي يصف فقط تعقيده الزمني. لتقييم أداء الخوارزمية حقا ، من الضروري أيضا مراعاة العوامل المتعلقة باستخدام الذاكرة والوصول إلى البيانات.
الوصف
البحث الثنائي هو خوارزمية للبحث في قائمة مرتبة ، يعتمد عملها على مبدأ "فرق تسد". يسمح لك بالعثور على عنصر معين في وقت يتناسب مع اللوغاريتمي لعدد العناصر في القائمة.
القائمة المرتبطة بشكل مضاعف هي بنية بيانات تتكون من عقد ، يحتوي كل منها على رابط للعقدة السابقة والتالية. القائمة المرتبطة بشكل مضاعف هي قائمة يتم فيها ترتيب العناصر بترتيب تصاعدي أو تنازلي.
التعقيد المقارب للبحث الثنائي في قائمة حجم مرتبطة بشكل مضاعف ن هو ا (سجل ن). هذا يعني أن وقت تنفيذ الخوارزمية سينمو لوغاريتميا مع نمو حجم القائمة. يتم تحقيق هذا التعقيد من خلال استخدام تقسيم القائمة إلى نصفين عند كل تكرار للبحث.
عند إجراء بحث ثنائي في قائمة مرتبطة بشكل مضاعف ، يتم تحديد منتصف القائمة أولا. ثم تتم مقارنة القيمة المطلوبة بالقيمة الموجودة في المنتصف. إذا كانت القيم متساوية ، فسيتم إكمال البحث والعثور على العنصر. إذا كانت القيمة التي تبحث عنها أقل من القيمة الموجودة في المنتصف ، يستمر البحث في النصف الأيسر من القائمة. إذا كانت القيمة التي تبحث عنها أكبر من القيمة الموجودة في المنتصف ، يستمر البحث في النصف الأيمن من القائمة. تتكرر العملية حتى يتم العثور على عنصر أو استنفاد القائمة.
يعد البحث الثنائي في قائمة مرتبطة بشكل مضاعف طريقة فعالة للبحث عن العناصر في مجموعات البيانات المرتبة. يوفر وصولا سريعا إلى العنصر المطلوب حتى مع وجود كميات كبيرة من البيانات ، نظرا لأن وقت تنفيذ الخوارزمية ينمو ببطء أكثر من خطيا.
أمثلة
مثال 1:
إدخال البيانات: فرز قائمة مرتبطة بشكل مضاعف من حجم 5: [1, 3, 5, 7, 9].
العنصر المطلوب: 3.
التكرار قائمة منتصف القائمة العنصر المطلوب النتيجة 1 [1, 3, 5, 7, 9] 5 3 وجدت تعقيد مقارب: س (سجل ن)
المثال 2:
إدخال البيانات: فرز قائمة مرتبطة بشكل مضاعف من حجم 8: [2, 4, 6, 8, 10, 12, 14, 16].
العنصر المطلوب: 9.
التكرار قائمة منتصف القائمة العنصر المطلوب النتيجة 1 [2, 4, 6, 8, 10, 12, 14, 16] 8 9 غير موجود تعقيد مقارب: س (سجل ن)
المثال 3:
إدخال البيانات: فرز قائمة مرتبطة بشكل مضاعف من حجم 4: [3, 6, 9, 12].
العنصر المطلوب: 6.
التكرار قائمة منتصف القائمة العنصر المطلوب النتيجة 1 [3, 6, 9, 12] 6 6 وجدت تعقيد مقارب: س (سجل ن)
مقارنة مع الخوارزميات الأخرى
يعد البحث الثنائي في قائمة مرتبطة بشكل مضاعف واحدة من أكثر الخوارزميات فعالية للبحث عن عنصر.ومع ذلك ، هناك خوارزميات أخرى يمكن استخدامها أيضا للبحث في مثل هذه القائمة. دعونا ننظر إلى بعض منهم:
- البحث الخطي: البحث الخطي هو خوارزمية بحث بسيطة عن العناصر تتحقق بالتتابع من كل عنصر من عناصر القائمة حتى يتم العثور على العنصر المطلوب. تعقيدها هو ا (ن) ، أين ن هو حجم القائمة. بالمقارنة مع البحث الثنائي ، يتطلب البحث الخطي عمليات أكثر بكثير في حالة القوائم الكبيرة.
- بحث الاستيفاء: يستخدم بحث الاستيفاء الاستيفاء الخطي للعثور على الموضع التقريبي لعنصر في القائمة. تعمل هذه الطريقة فقط مع القوائم المرتبة. في المتوسط ، تعقيدها هو س (سجل (سجل (ن))) ، مما يجعلها أكثر كفاءة من البحث الثنائي. ومع ذلك ، في أسوأ الحالات ، يمكن أن يصل تعقيدها إلى س(ن).
- جداول التجزئة: جداول التجزئة هي بنية بيانات تستخدم دالة تجزئة لتحويل مفتاح إلى فهرس صفيف. أنها تسمح لك بالبحث بسرعة ، إدراج وحذف العناصر. ومع ذلك ، يتطلب بناء جداول التجزئة وصيانتها تكاليف إضافية للذاكرة والحوسبة. البحث الثنائي في القائمة هو حل أكثر كفاءة إذا كانت هناك قائمة مرتبة في البداية.
وبالتالي ، يظل البحث الثنائي في قائمة مرتبطة بشكل مضاعف واحدة من أكثر الخوارزميات فعالية للبحث عن العناصر في مثل هذه القائمة. لديها تعقيد لوغاريتمي س (سجل (ن)) ويتطلب الحد الأدنى من الجهد الحسابي. ومع ذلك ، يعتمد اختيار خوارزمية معينة على تفاصيل المهمة ومتطلبات الأداء.
سؤال وجواب
ما هو التعقيد المقارب للبحث الثنائي في قائمة مرتبطة بشكل مضاعف?
التعقيد المقارب للبحث الثنائي في قائمة متصلة بشكل مضاعف هو ا (سجل ن) ، أين ن هو حجم القائمة. هذا يعني أن وقت تنفيذ الخوارزمية يزيد لوغاريتميا مع زيادة حجم القائمة.