تالار گفتمان مانشت

سلام، لطفا اینجا فقط سوالات ساختمان داده را بزاریم و جواب بدیم.
یک سوال این بود
یک درخت متوازن با n راس. در هر گره تعداد عناصر موجود در زیر درخت را ذخیره کرده ایم، چند تا از اعمال زیر را میتوان در O(logn) انجام داد؟
- یافتن مرتبه عنصر داده شده.
- یافتن تعداد عناصر بین a و b که a<b
- یافتن جمع عناصر بین a و b که a<b

چند تا از اینا درست بودند؟

من زدم 2تا چون اخریش ضایع n میشد

(17 بهمن 1393 02:37 ب.ظ)me_pro نوشته شده توسط: [ -> ]من زدم ۲تا چون اخریش ضایع n میشد

من هم 2 تا زدم !

(17 بهمن 1393 03:00 ب.ظ)Hamed_H8 نوشته شده توسط: [ -> ]

(17 بهمن 1393 02:37 ب.ظ)me_pro نوشته شده توسط: [ -> ]من زدم ۲تا چون اخریش ضایع n میشد

من هم ۲ تا زدم !

منم زدم دو تا.

می توو

از حل رابطه بازگشتی سوال ندادن ؟ :دی

منم زدم 2 تا

اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

(17 بهمن 1393 04:07 ب.ظ)sourena نوشته شده توسط: [ -> ]اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

Log* اوردم من.

من اصلا نمیدونم log* یعنی چی؟؟؟ :-D

(17 بهمن 1393 04:07 ب.ظ)sourena نوشته شده توسط: [ -> ]اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

من زدم :
Lg*n
درسته؟
چون این گزینه برای اعداد خیلی بزرگ میشه 6 ؟؟

(17 بهمن 1393 04:07 ب.ظ)sourena نوشته شده توسط: [ -> ]اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

جوابش بنظرم به سمت یه عدد میل میکنه. گزینه ها رو نمیدونم چیه اما *Log هم یه عدد ثابت فرض میشه.

(17 بهمن 1393 04:12 ب.ظ)sourena نوشته شده توسط: [ -> ]من اصلا نمیدونم log* یعنی چی؟؟؟ :-D

یعنی n تا لگاریتم تو در تو :-) ( زیاد درست نیست این تعریف )

تعریف درستش
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(17 بهمن 1393 02:27 ب.ظ)saber1366 نوشته شده توسط: [ -> ]سلام، لطفا اینجا فقط سوالات ساختمان داده را بزاریم و جواب بدیم.
یک سوال این بود
یک درخت متوازن با n راس. در هر گره تعداد عناصر موجود در زیر درخت را ذخیره کرده ایم، چند تا از اعمال زیر را میتوان در O(logn) انجام داد؟
- یافتن مرتبه عنصر داده شده.
- یافتن تعداد عناصر بین a و b که a<b
- یافتن جمع عناصر بین a و b که a<b

چند تا از اینا درست بودند؟

اگر درخت صرفا متوازن باشه هیچ کدوم در زمان log n حل نمیشه مگه اینکه صورت سوال رو بد گذاشته باشید!! مثلا برای مورد 2 در یک درخت متوازن وقتی ندونیم ترتیب کلیدها چطوره عملا یک جستجو خطی نیاز داریم که مرتبه اون در بدترین حالت خطی است . مورد 3 هم که مشخصه که مرتبه خطی داره.

(17 بهمن 1393 04:07 ب.ظ)sourena نوشته شده توسط: [ -> ]اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

log*(n)=t درس بود