طلب طروقات الترميز في فيبوناتشي كومة

Question

يمكن طلب الترميز بمفرده يعني:

$ O (d (n)) + o (t (h)) - t (h)= o (d (n)) $

تخميني هو أنه لا يمكنك ذلك منذ الثابت في O (H) (H)) لا يزال موجودا بعد الطرح إذا كان الثابت> 0.

حسنا، هذا هو في الواقع الحالة، ولكن هناك عوامل أساسية.تظهر هذه المعادلة في تحليل كومة Fibonacci في CLRS (518).يأتي تبرير هذه الخطوة من الوظيفة المحتملة الأساسية.وفقا للمؤلفين، "يمكننا توسيع نطاق وحدات الإمكانات للسيطرة على المخفية المستمرة في $ O (T (H)) $ ".أريد أن أعرف كيف يحدث هذا، لكن لا أعرف حقا كيفية طرح هذا السؤال المعقد.

Answer 1

كما تشير إلى معادلةك الأولى غير صحيح بالضرورة.

اسمحوا لي بإعادة كتابة ذلك عن طريق إضافة الثوابت المضاعفة بشكل صريح: $ \ alpha d (n) + \ beta t (h) - \ gamma t (h)= o (d (n)) $ ، حيث $ \ gamma= 1 دولار . هنا المشكلة هي أن $ \ beta $ قد تكون أكبر من $ \ gamma= 1 $ .

ما يقوله المؤلفون هو أنه بدلا من التفكير في وحدة واحدة في قيمة وظيفتك المحتملة $ \ phi (h) $ يسهم وحدة واحدة من الإمكانات، يمكنك تخيل أنها تمثل فعلا $ \ جاما $ وحدات الإمكانات. هذه المبالغ لإعادة التحليل باستخدام وظيفة محتملة جديدة $ \ phi '(h) $ يعرف باسم $ \ phi' ( ح)=gamma \ cdot \ phi (h) $ . إذا قمت بذلك، فأنت قادر على التحكم في قيمة $ \ gamma $ في المعادلة أعلاه، في حين $ \ Beta $ يبقى كما هو.

اختيار قيمة $ \ gamma \ ge \ beta $ يضمن $ \ alpha d (n) + \ beta t (h) - \ gamma t (h)=alpha d (n) - \ underbrace {(\ gamma - beta)} _ {\ ge 0} t (h) \ le \ alpha d (n)= o (d (n)) $ ، حسب الرغبة.