با سلام.
ببخشید من توی این دو تا سوال مشکل دارم برای سوال اول تعداد مقایسه های برای جستجوی موفق رو متوجه شدم وای نمیدونم تعدا جستجوی نا موفق روچه جوری باید به دست بیارم.
بعد واسه سوال دوم هم کلا روش به دست آوردن پیچیدگی رو متوجه نشدم ممنون میشم کمکم کنین
ببخشید من یادم رفته بود بگم برای سوال اول جواب گزینه ی ۴ و برای سوال دوم گزینه ی ۱ هست. برای سوال اول روش به دست آوردن تعداد مقایسه ها برای جستجوی موفق رو نوشته ولی برای ناموفق متاسفانه چیزی نگفته
خواهش میکنم اگه کسی میدونه بهم بگه خیلی ممنون
هیچکس نیس جواب این سوالا رو بده
Sent from my C5303 using Tapatalk
(۲۱ آذر ۱۳۹۲ ۰۵:۰۴ ب.ظ)nafas_70 نوشته شده توسط: با سلام.
ببخشید من توی این دو تا سوال مشکل دارم برای سوال اول تعداد مقایسه های برای جستجوی موفق رو متوجه شدم وای نمیدونم تعدا جستجوی نا موفق روچه جوری باید به دست بیارم.
بعد واسه سوال دوم هم کلا روش به دست آوردن پیچیدگی رو متوجه نشدم ممنون میشم کمکم کنین
سوال اول:
که تصویرش رو ضمیمه کردم ۸ خانه از ۰ تا ۷ داریم و با توجه به جدول هش داده شده اینطوری میشه ساختش
خب جستجوی نا موفق یعنی تابع هش یک عنصری یه خانه ای رو بمون داده حالا باید حساب کنیم چند تا خانه که الگوریتم بررسی میکنه میبینه که توی هش قرار نگرفته (نمیدونم خوب گفتم یا نه)
برای مثال اگه هش برای عنصری عدد صفر برگردوند الگوریتم باید خانه صفر رو بررسی کنه و چون اونجا خالیه میبینه اونجا چیزی نیست در نتیجه عنصر وجود نداره (پس با یه مقایسه فهمید)
برای خانه اول: وقتی هش عدد ۱ رو برگردونه الگوریتم میره میبینه E اونجا هست (۱ مقایسه) بعد خانه بعدیش هم بررسی میکنه میبینه خالیه در نتیجه ۲ مقایسه در کل
برای خانه دوم: وقتی هش عدد ۲ برگدونه مانند خانه صفر عمل میکنه (۱ مقایسه)
برای خانه سوم: وقتی هش عدد ۳ رو برگدونه الگوریتم خانه ۳ رو بررسی میکنه A توشه بعد میره خانه بعدی میبینه C توشه همینطوری میره تا آخر وقتی D رو هم توی خانه ۶ دید یه بار دیگه باید بره جلو تا دیگه مطمئن بشه وجود نداره (۵ مقایسه)
بقیه هم همینطور الی آخر
محاسبات نهایی:
۱+۲+۱+۵+۴+۳+۲+۱=۱۹
۸ خانه داریم در نتیجه ۱۹/۸
ولی سوال دوم:
به طور متوسط توی هر لیست پیوندی هش شده n/m عنصر قرار گرفته. (چون n عنصر داریم که میخواهیم توی m خانه قرار بدیم در نتیجه در هر خانه به طور متوسط n/m عنصر قرار میگیره)
در نتیجه با تتا n/m میشه بهش رسید. این شد حالت متوسط
بدترین حالت هم وقتی هست که تمامی عناصر به یک خانه نگاشت بشن در نتیجه باید تمام عنصر های درون اون خانه رو به صورت خطی پیمایش کرد چون N عنصر توی یه خانه داریم و میخواهیم به صورت خطی پیمایش کنیم مرتبه هم تتا n میشه (بدترین حالت)
مرسی واقعا لطف کردین کامل متوجه شدم ممنون
Sent from my C5303 using Tapatalk
این سوال آزمون پارسه
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
چیزی که پارسه حلش کرده یعنی پیشنهاد داده این مورد هست
![[تصویر: 234089_13586150250490971008.jpg]](https://img.manesht.ir/234089_13586150250490971008.jpg)
متوجه نشدم! البته کلا با این موضوع مشکل دارم.
(۱۲ دى ۱۳۹۲ ۰۲:۲۵ ق.ظ)farham_heidari نوشته شده توسط: سلام میتونید بفرمایید جست و جوی موفق چقدر میشه ؟؟
میشه ۸/۵ گزینه ی ۴ درسته
Sent from my C5303 using Tapatalk