یکی از دوستان یه راه حل دیگه ای ارئه داد ، تغییر متغیر n = 2^k ولی اخرش رو نفهمیدم ! بنظرتون درسته ؟
[tex]T(n)=T(logn) o(1)اگردرنظربگیریمn=2^kT(2^k)=T(log2^k) o(1)W(k)=W(k) o(1)W=θ(k)T(n)=θ(logn)[/tex]
با این مشکل دارم
[tex]W(k)=W(k) o(1)\: \: \: W=θ(k)[/tex]
(۱۷ بهمن ۱۳۹۳ ۰۷:۱۴ ب.ظ)sntbrz نوشته شده توسط:(17 بهمن ۱۳۹۳ ۰۵:۰۳ ب.ظ)me_pro نوشته شده توسط:منم با این استدلال زدم ۱۱(17 بهمن ۱۳۹۳ ۰۵:۰۰ ب.ظ)ziba.O نوشته شده توسط: سوال درهم سازی رو چی زدین؟
k mod m ، تو بدترین حالت m چند باشه؟(i بتوان ۲)
من گفتم چون باید m اول باشه و اینگه هر چی بیشتر باشه احتمال برخورد کمتر میشه ۱۱ رو زدم نمیدونم درسته یا نه
من هم با همین استدلال زدم ۱۱/اولش استدلالم عدد بزرگتر بود ولی بعد تا ۱۰۰ تست کردم دیدم ۱۲ خیلی ضایع درمیاد گفتم ۱۱ چون اوله احتمالا اینطور نشه.
(۱۷ بهمن ۱۳۹۳ ۱۰:۲۳ ب.ظ)noronet نوشته شده توسط: pivot فقط ۴و۵ میشدند...۹ هم میشد.همه از اون کوچیکتر بودن اونم تو آخر بود.
جستجوی متوازن هم فقط یک عبارت درست بود ... عبارت دوم
(۱۸ بهمن ۱۳۹۳ ۱۲:۳۴ ق.ظ)arash691 نوشته شده توسط: یکی از دوستان یه راه حل دیگه ای ارئه داد ، تغییر متغیر n = 2^k ولی اخرش رو نفهمیدم ! بنظرتون درسته ؟
[tex]T(n)=T(logn) o(1)اگردرنظربگیریمn=2^kT(2^k)=T(log2^k) o(1)W(k)=W(k) o(1)W=θ(k)T(n)=θ(logn)[/tex]
با این مشکل دارم
[tex]W(k)=W(k) o(1)\: \: \: W=θ(k)[/tex]
این روش اشتباس
معادله آخری که بدست اومده اصلا بازگشتی نیست!
جواب همون Log* n میشه
اره معادله ی اخر اصلا" بازگشتی نیست فکر میکنم همون log*n درست باشه
(۱۷ بهمن ۱۳۹۳ ۰۴:۲۹ ب.ظ)Masoud05 نوشته شده توسط:(17 بهمن ۱۳۹۳ ۰۲:۲۷ ب.ظ)saber1366 نوشته شده توسط: سلام، لطفا اینجا فقط سوالات ساختمان داده را بزاریم و جواب بدیم.
یک سوال این بود
یک درخت متوازن با n راس. در هر گره تعداد عناصر موجود در زیر درخت را ذخیره کرده ایم، چند تا از اعمال زیر را میتوان در O(logn) انجام داد؟
- یافتن مرتبه عنصر داده شده.
- یافتن تعداد عناصر بین a و b که a<b
- یافتن جمع عناصر بین a و b که a<b
چند تا از اینا درست بودند؟
اگر درخت صرفا متوازن باشه هیچ کدوم در زمان log n حل نمیشه مگه اینکه صورت سوال رو بد گذاشته باشید!! مثلا برای مورد ۲ در یک درخت متوازن وقتی ندونیم ترتیب کلیدها چطوره عملا یک جستجو خطی نیاز داریم که مرتبه اون در بدترین حالت خطی است . مورد ۳ هم که مشخصه که مرتبه خطی داره.
درخت مرتبه اماری یه درخت قرمز سیاهه و درخت قرمز سیاه ه م یه درخت متوازنه دو گزینه اول رو با درخت مرتبه
اماری میشد توی (Order(lognانجام داد اما گزینه سوم زمانی که aوb بزرگترین و کوچکترین عنصر باشن خب بدترین حالت رخ داده و مسلما از (order(n حل خواهد شد
(۱۷ بهمن ۱۳۹۳ ۱۰:۳۶ ب.ظ)behruz_p نوشته شده توسط:(17 بهمن ۱۳۹۳ ۱۰:۲۳ ب.ظ)noronet نوشته شده توسط: pivot فقط ۴و۵ میشدند...۹ نمیتونست باشه؟!
جستجوی متوازن هم فقط یک عبارت درست بود ... عبارت دوم
هر کار کردم ۹ نمیشد .. یعنی هر جا ۹ رو قرار دادم اول اخر وسط .. نشد که نشد/
(۱۸ بهمن ۱۳۹۳ ۰۱:۰۷ ق.ظ)hadinahavandi نوشته شده توسط:(17 بهمن ۱۳۹۳ ۰۷:۱۴ ب.ظ)sntbrz نوشته شده توسط:(17 بهمن ۱۳۹۳ ۰۵:۰۳ ب.ظ)me_pro نوشته شده توسط:منم با این استدلال زدم ۱۱(17 بهمن ۱۳۹۳ ۰۵:۰۰ ب.ظ)ziba.O نوشته شده توسط: سوال درهم سازی رو چی زدین؟
k mod m ، تو بدترین حالت m چند باشه؟(i بتوان ۲)
من گفتم چون باید m اول باشه و اینگه هر چی بیشتر باشه احتمال برخورد کمتر میشه ۱۱ رو زدم نمیدونم درسته یا نه
من هم با همین استدلال زدم ۱۱/اولش استدلالم عدد بزرگتر بود ولی بعد تا ۱۰۰ تست کردم دیدم ۱۲ خیلی ضایع درمیاد گفتم ۱۱ چون اوله احتمالا اینطور نشه.
(۱۷ بهمن ۱۳۹۳ ۱۰:۲۳ ب.ظ)noronet نوشته شده توسط: pivot فقط ۴و۵ میشدند...۹ هم میشد.همه از اون کوچیکتر بودن اونم تو آخر بود.
جستجوی متوازن هم فقط یک عبارت درست بود ... عبارت دوم
منم دقت کردم ولی هرجا ۹ رو میگزاشتی اول اخر وسط باز به هیچ عنوان ۹ نمیتونست در اخر pivot باشه.. چه صعودی میگرفتی یا نزولی .. یعنی یک جا پیدا نمیکردی ۹
اونجا باشه و سرانجام در اخر محور بشه ... مگر اینکه بخشی از یک ارایه می بود .. در ان صورت ۹ هم میشد.
بچه ها ساختمانا به نظرم این بود.اگه کسی سوال داشت بگه.
log* که قبوله
اون سواله هم سه تاشون میتونستن pivot باشن.
دوستان در مورد سوالی که درخت جستجوی دودویی متوازن بود وقتی هر نود تعداد نودای زیر درختاشو داره.جای a و b با لاگ ان پیدا میشه.بعد از رو عددی که تو اون نود نوشته شده اعداد بین a و b با استفاده از پدراشون و ...(باید تو شکل گفته شه ولی مطمئنم) پیدا میشه .مرتبشونم که با لاگ ان پیدا شد.در ضمن چون اگه a رو کمترین عنصر و b رو بیشترین بگیریم.کل عناصرو باید جمع بزنیم تو یکی از سه قسمت O(n) میخواد.که قابل قبول نیس.پس دو تا میشه ایشالا.
سرشکنی هم من زدم ادد یه دونه.جمع دو تا.واس برعکسش راه حلشو میدونم با تابع پتانسیل.ولی واس خود همین دقیقا نمیدونم تو جلسه چی فکر کردم که اینو زدم.این سوال احتمال داره جزو سوالایی باشه که واسش دو تا گزینه درست اعلام بشه.
اون لیسته هم طبق گفته ی دوستان اونی میشد که اول مقادیر اشاره گرای x رو تغییر میدادی و دفترچه e به نظرم گزینه ۴ بود اگه درست یادم باشه.
یه سوالم بود که واس هش بود.از بین دو گزینه ای که عدد اول بودن ۱۱ درسته به نظرم.چون تعداد کمتری عدد هستن که مضرب ۱۱ هستن تا مضرب ۷/
داخل پرانتز باید بگم:
خسته نباشین دوستان.امیدوارم سربلند باشین.سوالای سیستم و نظریش خیلی مزخرف بود.خیلی..... . ای کاش همش مسئله بود که اگه بود خیلی خوب میشد.
من هم log* زدم به نظرم درسته
اون یکی رو هم ۳ تا pivot میشد.
و سوال hash تو کتاب پارسه گفته بود باید اول باشه بین ۷ و ۱۱ هم احتمال ۱۱ خیلی بشتره منم ۱۱ زدم
اون سوال logn درخت متوازن چی میشد؟
ولی به نظر من چون هیچ شرطی جز متوازن بودن نداشت دو تای آخری مرتبه o(n) میشد .تازه نگفته بود درخت سیاه و قرمزه که :|
(۱۹ بهمن ۱۳۹۳ ۰۲:۵۶ ب.ظ)pe.esf نوشته شده توسط: من هم log* زدم به نظرم درستهداداش تقریبا ۱۰۰ درصد مطئنم که سه تارو درست زدی و یکیو متاسفانه غلط.حالا شاید بازم من اشتباه گفته باشم و اون یکیتم درست باشه.ولی مطئنم رو جوابم اگه اشتباه نکرده باشم.
اون یکی رو هم ۳ تا pivot میشد.
و سوال hash تو کتاب پارسه گفته بود باید اول باشه بین ۷ و ۱۱ هم احتمال ۱۱ خیلی بشتره منم ۱۱ زدم
اون سوال logn درخت متوازن چی میشد؟
ولی به نظر من چون هیچ شرطی جز متوازن بودن نداشت دو تای آخری مرتبه o(n) میشد .تازه نگفته بود درخت سیاه و قرمزه که :|
بچه ها لطفا با توجه به دفترچه بفرمایید سوال ۵۱ جوابش گزینه ۱ میشه یا ۴؟!!
(۱۹ بهمن ۱۳۹۳ ۰۷:۰۶ ب.ظ)ehsansjs نوشته شده توسط: بچه ها لطفا با توجه به دفترچه بفرمایید سوال ۵۱ جوابش گزینه ۱ میشه یا ۴؟!!
۴ میشه داداش من
تو یک قسمت اخرش مشکل ایجاد میکنه اگه دقت کنی
(۱۹ بهمن ۱۳۹۳ ۰۷:۰۶ ب.ظ)ehsansjs نوشته شده توسط: بچه ها لطفا با توجه به دفترچه بفرمایید سوال ۵۱ جوابش گزینه ۱ میشه یا ۴؟!!آره ۴ میشه
والا من از خدامه ۴ باشه ولی گزینه ۱ کجاش غلطه؟؟!!
(به اینم توجه کنید که سوال گفته آدرسnext n رو داریم!)
(۱۹ بهمن ۱۳۹۳ ۰۷:۴۳ ب.ظ)ehsansjs نوشته شده توسط: والا من از خدامه ۴ باشه ولی گزینه ۱ کجاش غلطه؟؟!!عزیز من یک به جای اینکه پریویوس عنصری که بعد از ایکس باشه به ایکس اشاره کنه.پریویوس ایکس به خود ایکس اشاره میکنه
(به اینم توجه کنید که سوال گفته آدرسnext n رو داریم!)
خیالت راحت که جواب ۴ هست عزیز
اگه ناراحت نمیشیدا باید عرض کنم که احتمالا شما ترتیب رو دقت نمیکنید یه بار شکل بکشید و گزینه ۱ رو به ترتیب برید میفهمید من چی میگم