پاسخ سنجش: گزینه ۱
چطوری میشه log n ؟ لطفا روش کار رو توضیح بدید
فقط تا اینجا رو می دونم که کمینه با احتمال [tex]\frac{1}{n}[/tex] می تونه در هر کدوم از n خونه باشه
برای ادامه ش گیج شدم
روش کار اینجوریه که قراره عنصر مین یا ماکس (چون صورت الگوریتم مشکل داره) پیدا کنه
اول کار عنصر اول آرایه را میبینه، با چه احتمالی عنصر مین هست ؟ [tex]1/n[/tex]
پس با این احتمال در مرتبه اول خط چهار اجرا میشه
مرحله بعد، دومین عنصر آرایه رو با مین مقایسه میکنه؟ احتمال اینکه این عنصر مین باشه چقدره ؟ [tex]1/(n-1)[/tex]
چون n-1 عنصر باقی مونده و با این احتمال میتونه مین باشه
و مراحل بعدی و احتمال های بعدی که جمع این احتمالها میشه logn
این فرمول نویسی Tex مشکل داشت ، نتونستم درست رابطه رو بنویسم
ما به دنبال مین اصلی هستیم وقتی مین پیدا شد دیگه شرط ما صدق نمی کنه وقتی دنبال یه عدد خاص در یک آرایه هستیم احتمال بودن اون عدد در هر ایندکس یک nام (یک تقسیم بر n) هست هدف ما پیدا کردن حالت متوسط یا امید ریاضیه
پس میشه مجموع ایندکس هر عدد ضرب در احتمالش
این جمع میشه n+1 تقسیم بر دو یعنی در حالت متوسط مین وسط آرایه میوفته پس در سمت راست آرایه شرط دیگر صادق نمی شه حالا آرایه نصف شده و باز همون مسئله پس
T(N)=T(N/2)+1
که میشه همون لاگ ان
این مسئله اسمش استخدام منشیه فصل ۵ clrs اثبات دقیقش هست