سلام دوستان
این سوال فصل دوم کتاب CLRS هستش.
الگوریتم جستجوی خطی را در نظر بگیرید. چه تعداد از عناصر آرایه به طور متوسط باید چک شوند؟ برای همه ی عناصر احتمال برابر در نظر بگیرید. در مورد بدترین حالت چطور؟
میدونم که باید احتمال در نظر بگیریم برای وجود داشتنش در آرایه و بعد برای هر عنصر بگیم با احتمال p/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].
حالت متوسط: (تا اونجایی که یادمه)
اگر کلید در آرایه وجود داشته باشد:
احتمال وجود در هر خانه = [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 باشه ولی اصلا مطمئن نیستم
(۰۵ مرداد ۱۳۹۳ ۱۱:۱۸ ب.ظ)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]
ممنون