Big O من جدول التجزئة مقابل شجرة البحث الثنائية

Question

التي ستستغرق وقتا أطول؟

اطبع جميع العناصر المخزنة في شجرة بحث ثنائية بترتيب مصنّعة أو طباعة جميع العناصر المخزنة في جدول التجزئة بترتيب فرز.

سوف يستغرق الأمر وقتًا أطول لطباعة عناصر جدول التجزئة بالترتيب المصنف لأن جدول التجزئة لم يتم فرزه أبدًا؟ و BST هو؟

Answer 1

انت على حق. يتم فرز علامات التجزئة بواسطة بعض وظائف التجزئة ، وليس حسب ترتيب الفرز الطبيعي ، لذلك يجب عليك استخراج جميع الإدخالات O (n) وفرزها O (nlogn) بينما يمكنك اجتياز شجرة البحث الثنائية بالترتيب الطبيعي في O ( ن).

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

من ناحية أخرى ، يمكنك العثور على عنصر في شجرة بحث ثنائية في "الوقت اللوغاريتمي" (o (log n)) لأنه تم بالفعل فرز البيانات لك.

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

يتمتع،

روبرت سيارتينو

Answer 5

هذا يثير بعض الأسئلة المثيرة للاهتمام. هل لا تزال شجرة البحث أسرع بالنظر إلى ما يلي؟

1. دمج وقت الإعداد لكل من جدول التجزئة و BST؟
2. إذا كانت خوارزمية التجزئة تنتج قائمة الكلمات المصنفة. من الناحية الفنية ، يمكنك إنشاء جدول التجزئة الذي يستخدم خوارزمية تفعل. في هذه الحالة ، يجب أن تنزل سرعة BST مقابل جدول التجزئة إلى مقدار الوقت الذي يستغرقه ملء جدول التجزئة بالترتيب المصنف.

Answer 6

تحقق أيضًا من الاعتبارات ذات الصلة لقائمة التخطي مقابل الشجرة الثنائية: تخطي القائمة مقابل الشجرة الثنائية