سلام
درخت این رو چطور باید بکشم و محاسبه کنم تا نخوام دستی بشینم الگوریتم رو روی کاغذ یا ذهن پیاده کنم؟ چون وقت زیاد میگیره
اگر الگوریتم جستجوی دودویی را برای جستجوی عناصر آرایه ۵,۱۰,۱۵,۲۰,۲۵,۳۰,۳۵,۴۰ به کار ببریم. میانگین تعداد مقایسه برای جستجوی موفق تقریبا کدام است؟
۲/۲
۲/۴
۲/۶
۲/۸
چون گفته میانگیم مقایسه باید این طور حساب کنیم؟ اگر گفته بود بدترین حالت باید حدپایین لگاریتم+۱ میکردیم. یا بهترین حالت ۱
اما چون گفته میانگین مقایسه یعنی در اصل t(n) درسته؟ ممنون
سلام
برای بدست اوردن میانگین مقایسه جستجوی موفق در الگوریتم جستجوی دودویی یه نکته داریم
درخت دودویی پر به تعداد عناصری که در صورت مسئله دادن رسم میکنیم بعد تعداد گره های اشغال شده رو در شماره سطح ضرب میکنیم
مثلا ریشه در ۱ سطح بعد در ۲ الا اخر.. در اخر تقسیم بر تعداد گره های اشغال شده
اینجا هم ۸ عنصر داریم
پس میشه
۱*۱ +
۲*۲ +
۴*۳ +
۱*۴
۲۱ تقسیم بر ۸ مییشه ۲/۶
(۲۱ مهر ۱۳۹۲ ۰۹:۴۲ ق.ظ)m@hboobe نوشته شده توسط: سلامجواب کاملا درسته
برای بدست اوردن میانگین مقایسه جستجوی موفق در الگوریتم جستجوی دودویی یه نکته داریم
درخت دودویی پر به تعداد عناصری که در صورت مسئله دادن رسم میکنیم بعد تعداد گره های اشغال شده رو در شماره سطح ضرب میکنیم
مثلا ریشه در ۱ سطح بعد در ۲ الا اخر.. در اخر تقسیم بر تعداد گره های اشغال شده
اینجا هم ۸ عنصر داریم
پس میشه
۱*۱ +
۲*۲ +
۴*۳ +
۱*۴
۲۱ تقسیم بر ۸ مییشه ۲/۶
اول میانه رو پیدا میکنیم که اینجا میشه ۲۰ برا اون ۱ بار مقایسه بعد برای عناصر سمت چپ و راستش دوباره میانه و بررسی تعداد جستجوها...