۰
subtitle
ارسال: #۱
  
مشکل در hash
با سلام.
ببخشید من توی این دو تا سوال مشکل دارم برای سوال اول تعداد مقایسه های برای جستجوی موفق رو متوجه شدم وای نمیدونم تعدا جستجوی نا موفق روچه جوری باید به دست بیارم.
بعد واسه سوال دوم هم کلا روش به دست آوردن پیچیدگی رو متوجه نشدم ممنون میشم کمکم کنین
ببخشید من توی این دو تا سوال مشکل دارم برای سوال اول تعداد مقایسه های برای جستجوی موفق رو متوجه شدم وای نمیدونم تعدا جستجوی نا موفق روچه جوری باید به دست بیارم.
بعد واسه سوال دوم هم کلا روش به دست آوردن پیچیدگی رو متوجه نشدم ممنون میشم کمکم کنین
۰
ارسال: #۲
  
RE: مشکل در hash
ببخشید من یادم رفته بود بگم برای سوال اول جواب گزینه ی ۴ و برای سوال دوم گزینه ی ۱ هست. برای سوال اول روش به دست آوردن تعداد مقایسه ها برای جستجوی موفق رو نوشته ولی برای ناموفق متاسفانه چیزی نگفته
خواهش میکنم اگه کسی میدونه بهم بگه خیلی ممنون
خواهش میکنم اگه کسی میدونه بهم بگه خیلی ممنون
۰
ارسال: #۳
  
Re: مشکل در hash
هیچکس نیس جواب این سوالا رو بده
Sent from my C5303 using Tapatalk
Sent from my C5303 using Tapatalk
۰
ارسال: #۴
  
RE: مشکل در hash
(۲۱ آذر ۱۳۹۲ ۰۵:۰۴ ب.ظ)nafas_70 نوشته شده توسط: با سلام.
ببخشید من توی این دو تا سوال مشکل دارم برای سوال اول تعداد مقایسه های برای جستجوی موفق رو متوجه شدم وای نمیدونم تعدا جستجوی نا موفق روچه جوری باید به دست بیارم.
بعد واسه سوال دوم هم کلا روش به دست آوردن پیچیدگی رو متوجه نشدم ممنون میشم کمکم کنین
سوال اول:
که تصویرش رو ضمیمه کردم ۸ خانه از ۰ تا ۷ داریم و با توجه به جدول هش داده شده اینطوری میشه ساختش
خب جستجوی نا موفق یعنی تابع هش یک عنصری یه خانه ای رو بمون داده حالا باید حساب کنیم چند تا خانه که الگوریتم بررسی میکنه میبینه که توی هش قرار نگرفته (نمیدونم خوب گفتم یا نه)
برای مثال اگه هش برای عنصری عدد صفر برگردوند الگوریتم باید خانه صفر رو بررسی کنه و چون اونجا خالیه میبینه اونجا چیزی نیست در نتیجه عنصر وجود نداره (پس با یه مقایسه فهمید)
برای خانه اول: وقتی هش عدد ۱ رو برگردونه الگوریتم میره میبینه E اونجا هست (۱ مقایسه) بعد خانه بعدیش هم بررسی میکنه میبینه خالیه در نتیجه ۲ مقایسه در کل
برای خانه دوم: وقتی هش عدد ۲ برگدونه مانند خانه صفر عمل میکنه (۱ مقایسه)
برای خانه سوم: وقتی هش عدد ۳ رو برگدونه الگوریتم خانه ۳ رو بررسی میکنه A توشه بعد میره خانه بعدی میبینه C توشه همینطوری میره تا آخر وقتی D رو هم توی خانه ۶ دید یه بار دیگه باید بره جلو تا دیگه مطمئن بشه وجود نداره (۵ مقایسه)
بقیه هم همینطور الی آخر
محاسبات نهایی:
۱+۲+۱+۵+۴+۳+۲+۱=۱۹
۸ خانه داریم در نتیجه ۱۹/۸
ولی سوال دوم:
به طور متوسط توی هر لیست پیوندی هش شده n/m عنصر قرار گرفته. (چون n عنصر داریم که میخواهیم توی m خانه قرار بدیم در نتیجه در هر خانه به طور متوسط n/m عنصر قرار میگیره)
در نتیجه با تتا n/m میشه بهش رسید. این شد حالت متوسط
بدترین حالت هم وقتی هست که تمامی عناصر به یک خانه نگاشت بشن در نتیجه باید تمام عنصر های درون اون خانه رو به صورت خطی پیمایش کرد چون N عنصر توی یه خانه داریم و میخواهیم به صورت خطی پیمایش کنیم مرتبه هم تتا n میشه (بدترین حالت)
۰
ارسال: #۵
  
Re: مشکل در hash
مرسی واقعا لطف کردین کامل متوجه شدم ممنون
Sent from my C5303 using Tapatalk
Sent from my C5303 using Tapatalk
۰
۰
ارسال: #۷
  
Re: RE: مشکل در hash
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close