حالت متوسط: (تا اونجایی که یادمه)
اگر کلید در آرایه وجود داشته باشد:
احتمال وجود در هر خانه = [tex]\frac{1}{n}[/tex]
حالا
اگه جواب توی خانه اول باشه پس : به احتمال [tex]\frac{1}{n}[/tex] باید یک بار جستجو کنیم
اگه جواب توی خانه دوم باشه پس : به احتمال [tex]\frac{1}{n}[/tex] باید دوبار جستجو کنیم
.
.
.
اگه جواب توی خانه n ام باشه پس : به احتمال [tex]\frac{1}{n}[/tex] باید n بار جستجو کنیم :

[tex](\frac{1}{n}\ast1) (\frac{1}{n}\ast2) ... (\frac{1}{n}\ast n)=\: \frac{1}{n}(1 2 3 ... n)=\frac{1}{n}(n\ast\frac{n 1}{2})=\frac{n 1}{2}[/tex]

اگر کلید به احتمال p وجود داشته باشد : فقط به جای [tex]\frac{1}{n}[/tex]باید [tex]\frac{p}{n}[/tex] گذاشت :

[tex]p\ast\frac{n 1}{2}[/tex]

۱۰۰ درصد مطمئن نیستم ولی به نظرم همچین جوابی داشته باشه
بدترین و بهترین هم به نظرم میاد ۱و n باشه ولی اصلا مطمئن نیستم

چه تعداد از عناصر آرایه به طور متوسط باید چک شوند؟
متوسط = (بیشترین حالت + کمترین حالت) /۲ => 1/2 عناصر ارایه
بدترین حالت : همه باید چک شوند.
بهترین حالت : فقط یک عنصر چک شود.

سلام. به احتمال p عنصر در آرایه وجود داره. به احتمال [tex]1-p[/tex] عنصر در آرایه وجود نداره. اگه اندازه آرایه N باشه به احتمال [tex]1-p[/tex] باید N عنصر چک بشه و به احتمال p بطور متوسط [tex]\frac{N 1}{2}[/tex] عنصر چک میشه. پس جواب نهایی میشه [tex](1-p)N p(N 1)/2[/tex].

(۰۵ مرداد ۱۳۹۳ ۱۱:۱۸ ب.ظ)Jooybari نوشته شده توسط:  سلام. به احتمال p عنصر در آرایه وجود داره. به احتمال [tex]1-p[/tex] عنصر در آرایه وجود نداره. اگه اندازه آرایه N باشه به احتمال [tex]1-p[/tex] باید N عنصر چک بشه و به احتمال p بطور متوسط [tex]\frac{N 1}{2}[/tex] عنصر چک میشه. پس جواب نهایی میشه [tex]\frac{(1-p)N p(N 1)/2}{N}[/tex].

بابت جواب دوستان ممنون.
آقای جویباری میشه تشریحی تر پاسختون رو توضیح بدید لطفا. جواب آقای reza777gh برای حالتی هست که کلید در آرایه وجود داشته باشه و حالتی که کلید وجود نداشته باشه در نظر گرفته نشده. جواب شما چرا در نهایت تقسیم بر N میشه؟

ممنون

حالتی که کلید وجود نداره ذقیقاً N جستجو نیازه. تقسیم بر N رو مثل اینکه اشتباه نوشتم. عذرخواهی میکنم. تو ارسال قبلی هم درست کردم. [tex](1-p)N p(N 1)/2[/tex]

(۱۱ مرداد ۱۳۹۳ ۱۰:۱۰ ب.ظ)Jooybari نوشته شده توسط:  حالتی که کلید وجود نداره ذقیقاً N جستجو نیازه. تقسیم بر N رو مثل اینکه اشتباه نوشتم. عذرخواهی میکنم. تو ارسال قبلی هم درست کردم. [tex](1-p)N p(N 1)/2[/tex]

ممنون