۰
subtitle
ارسال: #۱
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
سلام.
دوستان یه سواله راجع به درخت تصمیم گیری.
۱) عمق این نوع درخت‌ها حداقل [tex]Log(n!)[/tex] است و در گروه [tex]O(nLogn)[/tex] قرار می‌گیرد.
۲) عمق این نوع درخت‌ها حداکثر [tex]Log(n!)[/tex] است و در گروه [tex]O(nLogn)[/tex] قرار می‌گیرد.
۳) عمق این نوع درخت‌ها حداکثر [tex]Log(n!)[/tex] است و حداقل تعداد مقایسه [tex]O(nLogn)[/tex] است.
۴) عمق این نوع درخت‌ها حداقل [tex]Log(n!)[/tex] است و حداکثر تعداد مقایسه [tex]O(nLogn)[/tex] است.
گزینه ۱ صحیح اعلام شده.
میشه بگید چرا؟
ممنون.
دوستان یه سواله راجع به درخت تصمیم گیری.
۱) عمق این نوع درخت‌ها حداقل [tex]Log(n!)[/tex] است و در گروه [tex]O(nLogn)[/tex] قرار می‌گیرد.
۲) عمق این نوع درخت‌ها حداکثر [tex]Log(n!)[/tex] است و در گروه [tex]O(nLogn)[/tex] قرار می‌گیرد.
۳) عمق این نوع درخت‌ها حداکثر [tex]Log(n!)[/tex] است و حداقل تعداد مقایسه [tex]O(nLogn)[/tex] است.
۴) عمق این نوع درخت‌ها حداقل [tex]Log(n!)[/tex] است و حداکثر تعداد مقایسه [tex]O(nLogn)[/tex] است.
گزینه ۱ صحیح اعلام شده.
میشه بگید چرا؟
ممنون.
۰
ارسال: #۲
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
سلام.
تا جایی که اطلاع دارم عمق درخت تصمیم در بهترین حالت و شرایطی که حالت تکراری رو در نظر نگیره [tex]logn![/tex] میشه. که مرتبه این مشخص هست. این هم به خاطر تعداد برگ‌های درخت تصمیم (که !n ) هست.
تا جایی که اطلاع دارم عمق درخت تصمیم در بهترین حالت و شرایطی که حالت تکراری رو در نظر نگیره [tex]logn![/tex] میشه. که مرتبه این مشخص هست. این هم به خاطر تعداد برگ‌های درخت تصمیم (که !n ) هست.
۰
ارسال: #۳
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
ممنون.
ارتفاع در بدترین حالت چی؟
و تعداد مقایسه ها که در واقع قسمت دوم سواله.
ارتفاع در بدترین حالت چی؟
و تعداد مقایسه ها که در واقع قسمت دوم سواله.
۰
ارسال: #۴
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
این یه نکته از کتاب clrs هستش حالا دلیلشو که نمیدونم
فقط میدونم که درخت تصمیم این عمق رو داره تو یه کتاب خوندم : تعداد برگ های درخت تصمیم برای مرتب سازی n کلید برابر
!n هستش پس عمق اون ! log 2 n .
این و هم داریم که log2 n ! = O(n logn
فقط میدونم که درخت تصمیم این عمق رو داره تو یه کتاب خوندم : تعداد برگ های درخت تصمیم برای مرتب سازی n کلید برابر
!n هستش پس عمق اون ! log 2 n .
این و هم داریم که log2 n ! = O(n logn
۰
۰
ارسال: #۶
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
ممنون از دوستان.
مشکل با ارتفاع حل شد. اما قسمت دوم سوال رو مشکل دارم.
اینو هم میدونم که [tex]Logn! = O(nLogn)[/tex] پس قسمت اوا سوال اوکیه.
اما گزینه های ۳ و ۴ چی؟ در مورد تعداد مقایسه ها هیچ نظری نمیشه داد؟
مشکل با ارتفاع حل شد. اما قسمت دوم سوال رو مشکل دارم.
اینو هم میدونم که [tex]Logn! = O(nLogn)[/tex] پس قسمت اوا سوال اوکیه.
اما گزینه های ۳ و ۴ چی؟ در مورد تعداد مقایسه ها هیچ نظری نمیشه داد؟
۰
ارسال: #۷
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
امیر جوون واسه حل مشکلت بهت توصیه می کنم آخر فصل مرتب سازی پارسه رو بخون!کاملتر از بقیه جاهاست!ا
التماس دعا
التماس دعا
۰
ارسال: #۸
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
مرسی عملیات.
ساختمان پارسه رو دادم دست یکی. ندارمش فعلن.
ساختمان پارسه رو دادم دست یکی. ندارمش فعلن.
۰
ارسال: #۹
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
سلام آقا امیر،
فرض کن سه تا عدد a1,2,3 داری، چند تا مقایسه لازمه؟ اول a1 , a2 رو مقایسه می‌کنیم، اگه a1 کوچیکتر a2 بود برو سمت چپ درخت اگه بزرگ‌تر بود برو سمت راست.
حالا تو گرهٔ سمت چپی a2 را با a3 مقایسه کن
تو گرهٔ سمت راستی هم به همین ترتیب.
کلاً باید تمامی جایگشت‌های ممکن رو بررسی کنی تا بلاخره این لیست رو مرتب کنی.
جایگشت‌های یک فهرست n عددی هم که مشخصه از مرتبهٔ n! هست.
اگه کتاب نیپولیتان رو داری، بگرد احتمالاً این مبحث رو پیدا می‌کنی.
یا حق.
فرض کن سه تا عدد a1,2,3 داری، چند تا مقایسه لازمه؟ اول a1 , a2 رو مقایسه می‌کنیم، اگه a1 کوچیکتر a2 بود برو سمت چپ درخت اگه بزرگ‌تر بود برو سمت راست.
حالا تو گرهٔ سمت چپی a2 را با a3 مقایسه کن
تو گرهٔ سمت راستی هم به همین ترتیب.
کلاً باید تمامی جایگشت‌های ممکن رو بررسی کنی تا بلاخره این لیست رو مرتب کنی.
جایگشت‌های یک فهرست n عددی هم که مشخصه از مرتبهٔ n! هست.
اگه کتاب نیپولیتان رو داری، بگرد احتمالاً این مبحث رو پیدا می‌کنی.
یا حق.
(۰۸ بهمن ۱۳۹۱ ۰۲:۲۰ ب.ظ)Amir V نوشته شده توسط: مرسی عملیات.
ساختمان پارسه رو دادم دست یکی. ندارمش فعلن.
۰
ارسال: #۱۰
RE: ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
آقا امیر این سوال اگه اشتباه نکنم تصحیح شده بعدا و توی کتاب طورانی تصحیح شدش هست که واسه گزینه ی اول قسمت دوم گفته در گروه امگای nlogn قرار دارد که این درسته ،قسمت اولش هم که دوستان گفتن
۰
ارسال: #۱۱
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
۰
ارسال: #۱۲
ارتفاع و تعداد مقایسه در درخت انتخابی - IT 84
تعداد برگ درخت تصمیم میشه !n که دربدترین حالت ارتفاع درخت حداقل میشه !logn و میشه مرتبهnlogn
خب پس این تست غلط هست چون شما حد پایینش رو تعیین کردی نه حد بالا پس در گروه O قرار نمیگیره! حواستون باشه!!!!
خب پس این تست غلط هست چون شما حد پایینش رو تعیین کردی نه حد بالا پس در گروه O قرار نمیگیره! حواستون باشه!!!!
موضوع‌های مرتبط با این موضوع... |
|||||
| موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
| تعداد برگ درخت؟؟؟؟؟؟؟ | rad.bahar | ۴ | ۳,۹۸۸ |
۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ آخرین ارسال: mohamadrra |
|
| دو سوال در مورد درخت BST(درخت جستجوی دودویی) | امیدوار | ۳ | ۵,۲۰۲ |
۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ آخرین ارسال: marzi.pnh |
|
| زمان جستجوی درخت | fateme.sm | ۰ | ۱,۶۲۳ |
۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ آخرین ارسال: fateme.sm |
|
| مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۱۰۱ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
| عمق درخت ???? | rad.bahar | ۱ | ۲,۱۴۸ |
۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ آخرین ارسال: عزیز دادخواه |
|
| تعداد جواب | mostafaheydar1370 | ۲۱ | ۱۷,۴۴۱ |
۰۱ مهر ۱۳۹۹ ۱۱:۴۱ ب.ظ آخرین ارسال: miinaa |
|
| محاسبه ارتفاع درخت.... | baharkhanoom | ۳ | ۷,۵۷۷ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ آخرین ارسال: mohsentafresh |
|
| تعداد روش های نوشتن عدد n | ss311 | ۲ | ۳,۰۴۷ |
۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ آخرین ارسال: ss311 |
|
| تعداد مسیرها در گراف | ss311 | ۰ | ۱,۸۴۳ |
۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311 |
|
| تعداد درخت فراگیر | ss311 | ۰ | ۲,۱۱۷ |
۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ آخرین ارسال: ss311 |
|
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close