تالار گفتمان مانشت
مرتبه اجرایی تست - نسخه‌ی قابل چاپ
مرتبه اجرایی تست - vijay - 20 دى ۱۳۹۰ ۰۲:۳۷ ب.ظ

[تصویر: 62238_1_1379096101.png][تصویر: 62238_1_1379096101.png]
کسی میدونه چرا گزینه ۳ جواب میشه؟؟؟؟؟
ممنون میشم جواب بدید.

RE: مرتبه اجرایی تست - homa - 23 دى ۱۳۹۰ ۰۸:۱۴ ب.ظ

(۲۰ دى ۱۳۹۰ ۰۲:۳۷ ب.ظ)vijay نوشته شده توسط:  [تصویر: 62804_1_1379095981.png][تصویر: 62804_1_1379095981.png]
کسی میدونه چرا گزینه ۳ جواب میشه؟؟؟؟؟
ممنون میشم جواب بدید.
اگه در مورد این سوال از الگوریتم مرتب سازی BST(درخت جست و جوی دودویی) استفاده کنیم همین مرتبه بدست میاد.
به این صورت عمل میکنیم که اعدادی که با هم برابر ند رو در یک گره قرار میدیم پس ارتفاع درخت بر اساس اعداد که مقدار متفاوت دارند تعیین میشه. یعنی در اینجا logn عدد مختلف داریم پس ارتفاع میشه: [tex]loglogn[/tex]
و چون n تا عدد داریم که که در درخت درج کنیم زمان درج کردن میشه‌:

تعداد اعداد آرایه *ارتفاع درخت----->[tex]n(loglogn)[/tex]

و با پیمایش میانوندی که مرتبش میشه [tex]O(n)[/tex] یک لیست مرتب رو به ما میده.
یک مثال با ۸ عدد پیوست کردم. log8=3 عدد مختلف داریم.

پس گزینه‌ی درست همون ۳ هست.