(۰۲ بهمن ۱۳۹۳ ۰۷:۳۷ ب.ظ)shayesteb نوشته شده توسط:  سلام

همگی خسته نباشید میشه حل این سوال رو بگید چطوری هست و اگه میشه رابطه بازگشتی هم بنویسید؟

یک الگوریتم تصادفی A قرار است تعیین کند که آیا یک عدد ورودی x اول هست یا خیر. میدانیم که A در یک بار اجرا :
الف) اگر x اول باشد جواب بله می دهد.
ب) اگر x اول نباشد با احتمال ۳/۴ جواب خیر میدهد
برای آنکه تضمین کنیم که درحالت ب با احتمال حداقل $1-\frac{1}{k}$ جواب خیر بدهد. الگوریتم را چند بار اجرا کنیم؟ )گزینه صحیح گزینه سوم هستش)

۱)$O(\sqrt{k})$
۲) $O(1)$
۳)$O(\log\: k)$
۴)$k$