سوال ۶۸ کنکور ارشد مهندسی کامپیوتر ۱۴۰۰
اهمیت
۰/۵
یک درخت ۱۵ رأسی داریم که یکی از رأس‌های آن به‌عنوان هدف درنظر گرفته شده است، اما ما از آن اطلاع نداریم. در هر پرسمان می‌توانیم یک رأس را انتخاب کنیم و متوجه شویم آیا این رأس هدف است یا نه و اگر نیست کدام یال آن را به هدف نزدیک‌تر است. در بدترین حالت چند پرسمان حداقل لازم است تا بتوانیم رأس هدف را پیدا کنیم؟
#tree#centroid-decomposition#search#worst-case#logarithmic