هل o (logn) دائما شجرة؟

Question

نرى دائمًا العمليات على شجرة (بحث ثنائي) تحتوي على أسوأ وقت تشغيل (Logn) بسبب ارتفاع الشجرة هو logn. أتساءل ما إذا كان قد قيل لنا أن الخوارزمية لديها وقت تشغيل كدالة لـ Logn ، على سبيل المثال M + nlogn ، هل يمكننا أن نستنتج أنها يجب أن تتضمن شجرة (معززة)؟

تحرير: بفضل تعليقاتك ، أدرك الآن أن قاعة الفجوة والشجرة الثنائية متشابهة بصريًا/مفاهيميًا. لم أقم مطلقًا بالاتصال بين الاثنين. لكنني أفكر في حالة يكون فيها O (logn) عبارة عن algo قطر الفجوة التي تنطوي على شجرة لا تحتوي على خاصية لشجرة BST/AVL/Red Black.

هذا هو بنية البيانات غير المنفصلة مع عمليات البحث/الاتحاد ، والتي يكون وقت تشغيلها O (N + Mlogn) ، مع كون N هو رقم العناصر وعدد عمليات البحث.

واسمحوا لي أن أعرف إذا كنت في عداد المفقودين ، لكن لا يمكنني رؤية كيف يتم تشغيل قهر الفجوة هنا. أنا فقط أرى في هذه الحالة (مجموعة مفككة) أنه يحتوي على شجرة بدون خاصية BST ووقت تشغيل هو وظيفة Logn. لذا فإن سؤالي هو لماذا/لماذا لا أستطيع إجراء تعميم من هذه الحالة.

Answer 1

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

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

مرة أخرى ، إذا كنت تريد أن تكون بشكل سيء بما فيه الكفاية ، فيمكنك تمديد النقطة التي يمكن تمثيل شجرة متعددة الممرات كنوع من النسخة المشوهة من شجرة ثنائية. إذا كنت ترغب في ذلك ، فيمكنك على الأرجح تمديد جميع الاستثناءات إلى درجة القول إن جميعها (على الأقل شيء مثل) الأشجار الثنائية. على الأقل بالنسبة لي ، ومع ذلك ، كل ما يفعله هو جعل "شجرة ثنائية" مرادف لـ "Divide and Casher". بمعنى آخر ، كل ما تنجزه هو تحريك المفردات وغمس مصطلحًا متميزًا ومفيدًا بشكل أساسي.

Answer 2

لا ، يمكنك أيضًا البحث عن صفيف ثنائي (على سبيل المثال). لكن لا تأخذ كلامي لذلك http://en.wikipedia.org/wiki/binary_search_algorithm

Answer 3

كمثال مضاد:

given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
    y = y + 1
return y

وقت التشغيل هو o (log (n)) ، ولكن لا شجرة هنا!

Answer 4

الجواب لا. البحث الثنائي لمجموعة فرز O(log(n)).

Answer 5

الخوارزميات تأخذ الوقت اللوغاريتمي عادة وجدت في العمليات على الأشجار الثنائية.

أمثلة على O (logn):

• العثور على عنصر في مجموعة مصنفة مع بحث ثنائي أو شجرة بحث متوازنة.

• ابحث عن قيمة في صفيف الإدخال المصنفة عن طريق Bisection.

Answer 6

كما O (log (n)) ليست سوى الحد الأعلى أيضا جميع خوارزميات O (1) مثل function (a, b) return a+b; إرضاء الحالة.

لكن يجب أن أوافق على جميع خوارزميات Theta (log (n)) تبدو كأنها خوارزميات الأشجار أو على الأقل يمكن استخلاصها على شجرة.

Answer 7

اجابة قصيرة:

لمجرد أن الخوارزمية لديها سجل (ن) كجزء من تحليلها لا يعني أن الشجرة متورطة. على سبيل المثال ، ما يلي هو خوارزمية بسيطة للغاية O(log(n)

for(int i = 1; i < n; i = i * 2)
  print "hello";

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

المزيد عن الأشجار:

فقط لأن الخوارزمية تتضمن "الأشجار" لا تعني O(logn) أيضاً. تحتاج إلى معرفة نوع الشجرة وكيف تؤثر العملية على الشجرة.

بعض الأمثلة:

• مثال 1)

سيكون إدخال أو البحث عن الشجرة غير المتوازنة التالية O(n).

• مثال 2)

إدراج أو البحث في الأشجار المتوازنة التالية من قبل O(log(n)).

شجرة ثنائية متوازنة:

شجرة متوازنة من الدرجة 3:

تعليقات اضافية

إذا كانت الأشجار التي تستخدمها لا تملك طريقة "للتوازن" أكثر من أن تكون هناك فرصة جيدة لأن تكون عملياتك O(n) الوقت لا O(logn). إذا كنت تستخدم الأشجار التي توازن ذاتيًا ، فستستغرق عادة المزيد من الوقت ، حيث تحدث موازنة الأشجار عادةً خلال مرحلة الإدراج.