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

سلام.

دوستان یه سواله راجع به درخت تصمیم گیری.

1) عمق این نوع درخت‌ها حداقل [tex]Log(n!)[/tex] است و در گروه [tex]O(nLogn)[/tex] قرار می‌گیرد.
2) عمق این نوع درخت‌ها حداکثر [tex]Log(n!)[/tex] است و در گروه [tex]O(nLogn)[/tex] قرار می‌گیرد.
3) عمق این نوع درخت‌ها حداکثر [tex]Log(n!)[/tex] است و حداقل تعداد مقایسه [tex]O(nLogn)[/tex] است.
4) عمق این نوع درخت‌ها حداقل [tex]Log(n!)[/tex] است و حداکثر تعداد مقایسه [tex]O(nLogn)[/tex] است.

گزینه 1 صحیح اعلام شده.

میشه بگید چرا؟

ممنون.

سلام.
تا جایی که اطلاع دارم عمق درخت تصمیم در بهترین حالت و شرایطی که حالت تکراری رو در نظر نگیره [tex]logn![/tex] میشه. که مرتبه این مشخص هست. این هم به خاطر تعداد برگ‌های درخت تصمیم (که !n ) هست.

ممنون.

ارتفاع در بدترین حالت چی؟

و تعداد مقایسه ها که در واقع قسمت دوم سواله.

این یه نکته از کتاب clrs هستش حالا دلیلشو که نمیدونم
فقط میدونم که درخت تصمیم این عمق رو داره تو یه کتاب خوندم : تعداد برگ های درخت تصمیم برای مرتب سازی n کلید برابر
!n هستش پس عمق اون ! log 2 n .
این و هم داریم که log2 n ! = O(n logn

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

توضیح داده چطوری می‌شه به این رابطه رسید.

ممنون از دوستان.

مشکل با ارتفاع حل شد. اما قسمت دوم سوال رو مشکل دارم.

اینو هم میدونم که [tex]Logn! = O(nLogn)[/tex] پس قسمت اوا سوال اوکیه.

اما گزینه های 3 و 4 چی؟ در مورد تعداد مقایسه ها هیچ نظری نمیشه داد؟

امیر جوون واسه حل مشکلت بهت توصیه می کنم آخر فصل مرتب سازی پارسه رو بخون!کاملتر از بقیه جاهاست!ا
التماس دعا

مرسی عملیات.

ساختمان پارسه رو دادم دست یکی. ندارمش فعلن.

سلام آقا امیر،
فرض کن سه تا عدد a1,2,3 داری، چند تا مقایسه لازمه؟ اول a1 , a2 رو مقایسه می‌کنیم، اگه a1 کوچیکتر a2 بود برو سمت چپ درخت اگه بزرگ‌تر بود برو سمت راست.
حالا تو گرهٔ سمت چپی a2 را با a3 مقایسه کن
تو گرهٔ سمت راستی هم به همین ترتیب.
کلاً باید تمامی جایگشت‌های ممکن رو بررسی کنی تا بلاخره این لیست رو مرتب کنی.
جایگشت‌های یک فهرست n عددی هم که مشخصه از مرتبهٔ n! هست.
اگه کتاب نیپولیتان رو داری، بگرد احتمالاً این مبحث رو پیدا می‌کنی.
یا حق.

(08 بهمن 1391 02:20 ب.ظ)Amir V نوشته شده توسط: [ -> ]مرسی عملیات.

ساختمان پارسه رو دادم دست یکی. ندارمش فعلن.

آقا امیر این سوال اگه اشتباه نکنم تصحیح شده بعدا و توی کتاب طورانی تصحیح شدش هست که واسه گزینه ی اول قسمت دوم گفته در گروه امگای nlogn قرار دارد که این درسته ،قسمت اولش هم که دوستان گفتن

(10 بهمن 1391 10:28 ب.ظ)avril22 نوشته شده توسط: [ -> ]گروه امگای nlogn قرار دارد که این درسته ،قسمت اولش هم که دوستان گفتن

موافقم درستش امگاست!!پارسه هم همینو گفته،قلی زاده هم همینو گفته!

تعداد برگ درخت تصمیم میشه !n که دربدترین حالت ارتفاع درخت حداقل میشه !logn و میشه مرتبهnlogn
خب پس این تست غلط هست چون شما حد پایینش رو تعیین کردی نه حد بالا پس در گروه O قرار نمیگیره! حواستون باشه!!!!