۰
subtitle
(۲۰ دى ۱۳۹۰ ۰۲:۳۷ ب.ظ)vijay نوشته شده توسط:اگه در مورد این سوال از الگوریتم مرتب سازی BST(درخت جست و جوی دودویی) استفاده کنیم همین مرتبه بدست میاد.
کسی میدونه چرا گزینه ۳ جواب میشه؟؟؟؟؟
ممنون میشم جواب بدید.
به این صورت عمل میکنیم که اعدادی که با هم برابر ند رو در یک گره قرار میدیم پس ارتفاع درخت بر اساس اعداد که مقدار متفاوت دارند تعیین میشه. یعنی در اینجا logn عدد مختلف داریم پس ارتفاع میشه: loglogn
و چون n تا عدد داریم که که در درخت درج کنیم زمان درج کردن میشه:
تعداد اعداد آرایه *ارتفاع درخت----->n(loglogn)
و با پیمایش میانوندی که مرتبش میشه O(n) یک لیست مرتب رو به ما میده.
یک مثال با ۸ عدد پیوست کردم. log8=3 عدد مختلف داریم.
پس گزینهی درست همون ۳ هست.