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

[راضیه اکبری]

برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا

[parinaz_st70]

(۲۴ بهمن ۱۳۹۲ ۰۲:۲۹ ب.ظ)راضیه اکبری نوشته شده توسط:  سلام
یکی از سوالات ساختمان داده حداقل و حداکثر تعداد مقایسه ها برای ادغام دو لیست مرتب را میخواست و گزینه ها هم ترکیبی از n , 2n, 2n-1,n-1 بود
مسلما طرز فکر من اشتباه بوده چون سوال ساده به نظر میومد و من اینطوری به فکرم می رسید که در بهترین حالت بزرگترین عنصر یکی از لیست ها از کوچکترین عنصر لیست دیگر کوچکتر هستش و در نتیجه یک مقایسه کافیه صورت سوال صرفا تعداد مقایسه را خواسته بود پس هزینه رفتن به انتهای لیست شاملش نمیشه در واقع مثل عمل merg در الگوریتم mergsort الگوریتم
نهایتا این طور فکر کردم که تمام عناصر لیست اول که کوچکتر از لیست دوم هستن با عنصر اول لیست دوم در بهترین حالت مقایسه می شوند پس n مقایسه داریم که به نظرم خیلی غلط میاد
چون فردا کنکور مهندسی دارم اگه لطف کنین بگین کجا دارم اشتباه میکنم ممنون میشم حتی اگه خیلی دارم اشتباه بی سوادانه ای می کنم اشکال نداره بگین ممنون میشم

تو بدترین کیس من زیک زاک رفتم یعنی ۱۳۵۷ و اون یکی هم ۲۴۶۸ به نظرم بیشتر از این دیگه نمیشه چون تو هر گام مقایسه داریم که شذ ۷ تا ۲n-1!

[amirgh142]

گزینه ها رو برعکس نداده بودن؟؟؟ حداقل و حداکثر و میخواست به ترتیب اما جاشون اشتباه بود فکر کنم.. منظورم اینه که حداکثر اول نوشتن بعدش حداقل... منم ۲n-1 و n رو آوردم

[parinaz_st70]

---

k هی داشت نصف میشد تو هر محله هم nk باهاش جمع میشد زدم nklgk

[sahar_rostami2]

(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)itsgu88 نوشته شده توسط:  مرتبه زمانی T(k,n) رو من زدم O(nk)

من knlogn زدم...سوال ماکس هیپ هم nlogm +mlogn

[blue70]

سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

[Fot30]

(۲۴ بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط:  برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا

اگر هر دو آرایه باشن میشه به صورت درجا با O(N) هیپ ساخت.

[iammiti]

(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)راضیه اکبری نوشته شده توسط:  ببینید در الگوریتم merg sort در ساختمان داده انتهای دو تا لیست یک بی نهایت میذارن در نتیجه مقایسه دو لیست اینجوری میشه که میگین منتهی این جا دو لیست مرتب داریم اگه بزرگترین عنصر یکی از لیست ها از عنصر اول لیست دیگه کوچکتر باشه خب بقیه عناصر لیست اول هم کوچکتر میشن دیگه مقایسه نمیخواد

شرایط خاص در نظر نگیرید در حل مساله..همیشه باعث خطا میشه..شما تو این مورد شرایط خاص گرفتین
n=1 , n=2 مثال میزدید راحت به جواب میرسیدید..البته n=1 کافی بود تا ۳تا گزینه حذف بشه

[mehdi1902]

(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)itsgu88 نوشته شده توسط:  مرتبه زمانی T(k,n) رو من زدم O(nk)

به نظر منم O(nk) میشه !

[izadan11]

(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)itsgu88 نوشته شده توسط:  مرتبه زمانی T(k,n) رو من زدم O(nk)

من هم nk زدم با اینکه اثباتش کردم ولی باز ازش مطمئن نبودم
اینجور عمل کرد که
$\frac{n1k}{2} \frac{n2k}{2}=\frac{k}{2}(n1 n2)$
پس هر بار نصف میشه در نتیجه با سری هندسی شد kn

(۲۴ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)Orchid نوشته شده توسط:  من این سوال رو نزدم اما اینطور فکر کردم که با هزینه nlogn از مین هیپ بر میداریم و با هزینه nlogm به مکس هیپ اضافه می کنیم که میشه nlogn + nlogm که توی گزینه ها نبود احتمالا من اشتباه می کنم جواب درست چی بوده؟

من این سوال مشکل داره
چون ما نمی دونیم مرتبه n و m چه جوری هست
فرض کنیم m>n
الان با یک راه(اضافه کردن یکی یکی) حل میشه nlogm
و با یه راه حل دیگه میشه n+m الان کدوم کوچکتره؟
اگر اولی کوچکتر باشه میشه اون گزینه که مین داشت
اگر دومی کوچیکتر هم میشه n+m

[Aseman7]

(۲۴ بهمن ۱۳۹۲ ۰۲:۳۳ ب.ظ)unicornux نوشته شده توسط:  اون ترکیب ماکس هیپ و مین هیپ چطور میشه به نظرت؟

باید ترکیب شون ماکس هیپ می شد(صورت سوال)
پس اگه یه نود خالی برای ریشه ماکس هیپ جدید بذاریم و ماکس دو ریشه ی دو تا هیپ را بذارم داخل ان نود (که البته بیشتر ریشه همان ماکس قرار می گیره ) بعدش این جا مهمترین کار یعنی تبدیل مین هیپ به ماکس باید صورت بگیره که به نظرم همان گزینه ۱ o(m+N) میشه.

[izadan11]

(۲۴ بهمن ۱۳۹۲ ۰۲:۵۰ ب.ظ)blue70 نوشته شده توسط:  سلام به همه
اون سوال ساختمان داده که درخت جستجوی دودویی متوازن بود یکی از مقادیر گره ها به خاطر نویز تغییر می کرد مرتبه اش چی میشد ؟

nlogn یا log n؟

من زدم n
مشکل کار اینجاست که سوال مشخص نکرده ما گره رو داریم یا نه
چون گفته بود گرهی من فرض کردم که نداریم و با یک dfs میشه از پیچیدگی n
اگر هم منظور دونستن گره بوده میشه log n

[itsgu88]

مرتبه زمانی عبارت زیر:

T(n,k)=T(n1,[k/2])+T(n2,[k/2])+nkT(n=n1+n2) , T(n,1)=T(1,k)=1

O(n^2k):A
O(nk):B
O(klogn):C
O(nlogk)


من خودم گزینه دوم رو انتخاب کردم

[mehdi1902]

(۲۴ بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)راضیه اکبری نوشته شده توسط:  برای ترکیب دو هیپ من اینطوری گفتم که در زمان nlogn و mlogm ماکس و مین هیپ تبدیل به دو ارایه مرتب میشن حالا در بدترین حالت برای ادغام دو ارایه m+n-1 میشود و ساخت یک ماکس هیپ با m+n عنصر در زمان o(m+n هستش پس نهایتا داریم nlogn+mlogm+o(m+n که میشه nlogn+mlogm اگه اشتباه میکنم بگین لطفا که فردا این اشتبا ه رو تو کنکور مهندسی نکنم احیانا

این سوالش اشتباه نبود :-؟
یه دونه O(n) برای تبدیل مین به ماکس. یه دونه min {logn , log m} هم برای اینکه به هم وصل بشن. مثلن ماکس یکی رو بیاریم ریشه و مرتبش کنیم درخت رو و فرزند دیگه شو بذاریم اون یه درخت. یعنی میشه
n + min {logn , logm}

[virtual girl]

(۲۴ بهمن ۱۳۹۲ ۰۲:۳۳ ب.ظ)damavand_kellap نوشته شده توسط:  مرتبه زمانی ادغام دو لیست مرتب به طول M و n در بهترین حالت میشه min(m,n) و در بدترین حالت میشه m+n_1 که اینجا چون طول هر دو لیست n بود پس مرتبه میشه n و ۲n_1

به نظرم همین گزینه پاسخ درست باشه تو یکی از آزمونهای آزمایشی یه موسسه این سوال اومده بود و جواب همین بود