ادغام n عنصر = بدترین حالت مرتبه n
حالا اولیش میشه ۲n/k
دومی ۲n/k + n/k = 3n/k
سومی ۳n/k + n/k = 4n/k
....
...
...
آخری nk/k

و در مجموع k(k+1)/2*n/k خلاصه kهابا هم بپرن میشه مرتبه nk
البته من پایه ریاضیم ضعیفه ولی خداییش فکر نکنم غلطم باشه .
قبول دارید؟

(۲۹ بهمن ۱۳۹۰ ۰۷:۴۹ ب.ظ)afshinmu نوشته شده توسط:  n عمل داره انجام میشه اونوقت شما بر logn تقسیم می کنید؟ با حساب شما میشه logn/n . در ضمن من خودم یه مثال زدم که با n=8 15 تا مقایسه لازم داشت که n نمیشه در نظر گرفت و اگه nlogn در نظر بگیریم میشه nlogn/n که همون logn هستش . البته من نمی دونم nlogn می تونیم در نظر بگیریم یا باید بیشتر باشه ولی مطمئنا از مرتبه logn کمتر نیست

درسته ، منم طی محاسباتی که سر جلسه کردم همون lgn میشه.

یکی nk بود یکی nlogk یکی klogn گزینه دیگه چی بود؟اصلا nlogn داشت?

بچه ها این سوال ۹۶ رو کسی زده لطفا بگید که تحلیلتون برای حل سوال چطور بوده؟

(۳۰ بهمن ۱۳۹۰ ۰۱:۲۸ ق.ظ)mp1368 نوشته شده توسط:  بچه ها این سوال ۹۶ رو کسی زده لطفا بگید که تحلیلتون برای حل سوال چطور بوده؟

من ۱ زدم ولی هیچ دفاعی ندارم ازش

(۳۰ بهمن ۱۳۹۰ ۰۱:۲۹ ق.ظ)afshinmu نوشته شده توسط:  

(30 بهمن ۱۳۹۰ ۰۱:۲۸ ق.ظ)mp1368 نوشته شده توسط:  بچه ها این سوال ۹۶ رو کسی زده لطفا بگید که تحلیلتون برای حل سوال چطور بوده؟

من ۱ زدم ولی هیچ دفاعی ندارم ازش

من خودم هم ۱ رو زذم (مبنا دفترچه A).
ولی به قول شما فقط به تحلیل اون لحظه خودم اعتماد کردم و تست رو زدم ولی خوب استدلالم حداقل واسه خودم که خوب بود.

بچه ها میتونن سوال ۹۹ رو با این گراف امتحان کنن؟
به نظر من دقت نمی کنیم که گفته کوچکتر باشد.نه کوچکتر مساوی
وزن بیشترین یال ۱۱ هست که برابر وزن یک درخت پوشاست.
خروجی کدوم الگوریتم [b]همواره [/b]کمتر است ؟
با این مثال می بینیم که هیچ کدوم

(۳۰ بهمن ۱۳۹۰ ۰۱:۳۰ ب.ظ)deledivouneh نوشته شده توسط:  بچه ها میتونن سوال ۹۹ رو با این گراف امتحان کنن؟
به نظر من دقت نمی کنیم که گفته کوچکتر باشد.نه کوچکتر مساوی
وزن بیشترین یال ۱۱ هست که برابر وزن یک درخت پوشاست.
خروجی کدوم الگوریتم [b]همواره [/b]کمتر است ؟
با این مثال می بینیم که هیچ کدوم

گفته کوچکترین دوست گلم . بین ۲و۴و۳و۲و۴ کدوم کوچکترینه؟؟؟؟مشخصه ۲ دیگه . ارتباطی به بحث کوچکتر یا کوچکتر مساوی نداره . به هیچ وجه . وگرنه هیچ الگوریتمی قابل ابداع نیست !!!! نه الان بلکه در آینده . چون همیشه گرافی میشه مثال زد که کوچکترین ( با تفسیر شما) رو نشه پیدا کرد .

(۳۰ بهمن ۱۳۹۰ ۰۱:۳۰ ب.ظ)deledivouneh نوشته شده توسط:  بچه ها میتونن سوال ۹۹ رو با این گراف امتحان کنن؟
به نظر من دقت نمی کنیم که گفته کوچکتر باشد.نه کوچکتر مساوی
وزن بیشترین یال ۱۱ هست که برابر وزن یک درخت پوشاست.
خروجی کدوم الگوریتم [b]همواره [/b]کمتر است ؟
با این مثال می بینیم که هیچ کدوم

میگم نکنه جواب الکی من به این تست درست دربیاد (ارسال ۳۵) چون این گرافی که شما کشیدی داره گزینه (هردو) را نقض می کنه.

درخت پوشای این گراف هم با کراسکال و هم با پریم میشه این: (اگه من اشتباه نکنم)
که این هم که خوب پرقدرت ترین ش یال ۵ هست دیگه.

(۳۰ بهمن ۱۳۹۰ ۰۸:۴۵ ب.ظ)AmirGooran نوشته شده توسط:  درخت پوشای این گراف هم با کراسکال و هم با پریم میشه این: (اگه من اشتباه نکنم)
که این هم که خوب پرقدرت ترین ش یال ۵ هست دیگه.

جواب شما مربوط به یال هست ولی سوال گفته کم قدرت ترین درخت(یعنی جمع وزن یال های درخت ).
این درسته که هر دو تا می تونن باشن ولی همواره نه

سوال گفته : قدرت یعنی : وزن کمترین یال در یک درخت پوشا
بنابراین قدرت درخت پوشای من میشه : ۵
یعنی درختی وجود داره که قدرتش از این کمتر باشه؟!

به نظر من طراح همون درخت گلوگاه رو گفته که کاملا مشخصه ،درخت پوشای گلوگاه بزرگترین یالش نسبت به سایر درختان پوشا کمترین باشه ، یعنی همین سوال اما طراح خواسته با کلمات بازی کنه تا طرف فقط حفظ نکرده باشه یا میخواسته بپیچونه !!
هر درخت فراگیر کمینه هم یک گلوگاه هست حتما ، پس هر دو گلوگاه رو می دن(مسائل آخر فصل MST)

بحث سقفه
تابلوست که میشه nk

سوال ۹۶ میشه o(n)
سوال ۹۷ نمی دونم میگفتن ۴ میشه
سوال ۹۸ میشه nk این سوال شکلش عوض شده تکراری بود تو سوالات گذشته دیدم گفته بود مقدار بهینه K چقدره؟
سوال ۹۹ میشه هرذو مورد (من اشتباه زدم)
سوال ۱۰۰ میشه log n ترتیبش اینجوریه که حلقه اول یه بار بعد ۲ بار بعد..
۱+۲+۱+۳+۱+۲+۱+۴+۱+۲+۳+۱+۵+...=n/2 1+ n/4 2 + n/6 3+...=1/2=
۱/۲n logn که سرشکنش میشه ۱/۲ log n
بازم اشتباه زدم
سوال ۱۰۱ من زدم درست نادرست نمی دونم درست یا نه اما هرجور حساب که کنی برا ۶ عنصر حداقل ۱۲ مقایسه نیاز داره اگه کسی جواب قطعی داره من منتظرم

(۰۴ اسفند ۱۳۹۰ ۱۱:۳۰ ب.ظ)hussein.sh نوشته شده توسط:  سوال ۹۶ میشه o(n)
سوال ۹۷ نمی دونم میگفتن ۴ میشه
سوال ۹۸ میشه nk این سوال شکلش عوض شده تکراری بود تو سوالات گذشته دیدم گفته بود مقدار بهینه K چقدره؟
سوال ۹۹ میشه هرذو مورد (من اشتباه زدم)
سوال ۱۰۰ میشه log n ترتیبش اینجوریه که حلقه اول یه بار بعد ۲ بار بعد..
۱+۲+۱+۳+۱+۲+۱+۴+۱+۲+۳+۱+۵+...=n/2 1+ n/4 2 + n/6 3+...=1/2=
۱/۲n logn که سرشکنش میشه ۱/۲ log n
بازم اشتباه زدم
سوال ۱۰۱ من زدم درست نادرست نمی دونم درست یا نه اما هرجور حساب که کنی برا ۶ عنصر حداقل ۱۲ مقایسه نیاز داره اگه کسی جواب قطعی داره من منتظرم

دوست خوبم شما سوال ۱۰۱ رو اشتباه زدین
قسمت الف درسته و اما قسمت ب که دقیقا ۸ سوال در این مورد بدر آزمون های دانشگاه MIT مطرح شده. این مسئله مربوط به درخت تصمیمه جوابش اینه که درخت تصمیم دقیقا ۶ فاکتوریل برگ داره یعنی ۷۲۰ برگ و ما با ۱۰ مقایسه می تونیم مرتب سازی رو انجام بدیم به خاطر اینکه ۲ به توان ۱۰ مقایسه داریم که ۱۰۲۴ می شه و ۷۲۰ از ۱۰۲۴ کوچکتره و از ۲ به توان ۹ که ۵۱۲ می شه بزرگتر که عدد ۱۰ حداقل مقدار جستجو هستش.