(۲۰ دى ۱۳۹۳ ۱۲:۱۹ ق.ظ)fatemeh69 نوشته شده توسط:  

(19 دى ۱۳۹۳ ۰۹:۰۹ ب.ظ)Aurora نوشته شده توسط:  این جواب من نمی دونم درسته یا نه!
وقتی میخواد فرد نابغه رو پیدا کنه دو حالت داریم یکی بدترین روش: در این روش گروه ها یک نفری اند یعنی n تا گروه داریم. حالا یکی یکی از اینا می پرسیم که ایا نابغه تو گروه شماست اگر جواب بله بود همون فرد نابغه است. در بدترین حالت هم کل این n گروه باید جستجو بشن.
در بهترین روش دائما گروه نصف میشه تا مثل جستجوی دودویی اون فرد نابغه پیدا بشه. حالا شاید بپرسید تو جستجوی دودویی اعداد مرتب هستن و اینا
فرقش اینه که اینجا وقتی از گروه می پرسیم خودشون میگن بله یا خیر و نیازی به مقایسه نداریم.

درسته جواب همینه
ما دنبال بدترین مرتبه ی بهترین راه حل می گردیم
هر دفعه جمعیت رو نصف می کنیم از نصفیشون می پرسیم اگه گفت بله که همونو دوباره نصف می کنیم اگه گفت نه که می ریم اون یکی گروه و نصف می کنیم. n/2 نمی شه که
می شه logn
و می خواهیم خود فرد نابغه رو پیدا کنیم نه گروهشو

(۲۰ دى ۱۳۹۳ ۱۲:۲۱ ق.ظ)miladcr7 نوشته شده توسط:  چرا n/3 نه???یا یه تقسیم دیگه؟؟؟؟

(۲۰ دى ۱۳۹۳ ۱۲:۲۸ ق.ظ)fatemeh69 نوشته شده توسط:  

(20 دى ۱۳۹۳ ۱۲:۲۱ ق.ظ)miladcr7 نوشته شده توسط:  چرا n/3 نه???یا یه تقسیم دیگه؟؟؟؟

فرقی نداره شما هر دفعه اگه به m قسمت هم تقسیم کنید جواب می شه logn در مبنای m که مبناها تو پیچیدگی تاثیر ندارن