إثبات بناء BST متوازن من صفيف مرتبة هو $ \ Theta (n) $

Question

أقدم وقتا عصيبا، أثبتت بناء BST من مجموعة متوازنة من الصفيف هو $ \ Theta (n) $

حصلت على الصيغة التالية: $$ T (n)= 2t (\ frac {n} {2}) + \ theta (1) $

حاولت إثبات ذلك عن طريق الحث ولكن تعالى مع القضية التي $ N $ هي رقم فردي.

هل هناك طريقة أفضل لإثبات ذلك؟لا يعتبر الاستبدال دليلا صالحا (وصلت إلى الصيغة المغلقة باستخدام استبدال الدورة التدريبية).

Answer 1

إذا سمح لك باستخدام سيد نظرية ثم يمكنك أن تختتم على الفور أن $ t (n)=theta (n) $ (منذ $ n ^ {\ log_2 2}= n=أوميغا (1) $ ).

إذا لم يسمح لك باستخدام النظرية الرئيسية، فيمكنك كتابة هذا التكرار بدلا من ذلك: $$ T (n) \ Le 2t (\ lloor n / 2 \ rfloor) + c، $ حيث $ C> 0 $ هو ثابت مطلق و $ T (1) \ Le C $ . < / ص>

ثم يمكنك إثباتها عن طريق التعريفي على أن $ t (n) \ le 2cn - c $ . القضية الأساسية هي $ n= 1 $ وهي تافهة منذ $ t (1) \ le c= 2cn - c $ . فكر الآن $ n> 1 دولار ونفترض أن المطالبة تصل إلى $ n-1 $ ، نحن سوف تثبت أنه يحمل أيضا ل $ n $ : $$ T (n)= 2t (\ lloor n / 2 \ rfloor) + c \ le 2 (2c \ llloor n / 2 \ rfloor-c) + c \ le 2cn - 2c + c= 2cn-c.