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

$(\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}$

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

$p\ast\frac{n 1}{2}$

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

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

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

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

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

ممنون

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

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

ممنون