انجمنصفحه اولجستجوی انجمن

[saber1366]

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

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

[me_pro]

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

[Hamed_H8]

(۱۷ بهمن ۱۳۹۳ ۰۲:۳۷ ب.ظ)me_pro نوشته شده توسط:  من زدم ۲تا چون اخریش ضایع n میشد

من هم ۲ تا زدم !

[saber1366]

(۱۷ بهمن ۱۳۹۳ ۰۳:۰۰ ب.ظ)Hamed_H8 نوشته شده توسط:  

(17 بهمن ۱۳۹۳ ۰۲:۳۷ ب.ظ)me_pro نوشته شده توسط:  من زدم ۲تا چون اخریش ضایع n میشد

من هم ۲ تا زدم !

منم زدم دو تا.

[ziba.O]

می توو

[arash691]

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

[m.teymourpour]

منم زدم ۲ تا

[sourena]

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

[hadinahavandi]

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

Log* اوردم من.

[sourena]

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

[newwink]

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

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

[Masoud05]

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

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

[arash691]

(۱۷ بهمن ۱۳۹۳ ۰۴:۱۲ ب.ظ)sourena نوشته شده توسط:  من اصلا نمیدونم log* یعنی چی؟؟؟ :-D

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

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

[Masoud05]

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

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

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

[me_pro]

(۱۷ بهمن ۱۳۹۳ ۰۴:۰۷ ب.ظ)sourena نوشته شده توسط:  اینو چی زدین بچه ها ؟
[tex]T(n)=T(\lg n)\: \: o(1)\: ,\: T(0)=1[/tex]
مرتبه این رابطه چی میشه ؟

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