![]() |
سوال ۳۹ ساختمان داده it88 - نسخهی قابل چاپ |
سوال ۳۹ ساختمان داده it88 - Aurora - 21 بهمن ۱۳۹۰ ۰۷:۳۷ ب.ظ
Hتابع درهم سازی است که دارای M خانه است و در آن N عنصر ذخیره می شود برای رفع برخورد این جدول از روش زنجیر استفاده شده متوسط و بدترین زمان برای یک جستجوی یک عنصر؟ جواب: تتا N , تتا N/M چرا؟؟؟ |
سوال ۳۹ ساختمان داده it88 - mamat - 21 بهمن ۱۳۹۰ ۰۸:۲۷ ب.ظ
خیلی ساده هستش. اگه مثلا فرض کنی در بدترین حالت همه عناصر به صورت زنجیر به فقط یک مدخل نگاشت بشن میشه یک جستجوی خطی که باید N عنصر را جستجو کند. ولی اگه با یک تابع توزیع به صورت a=N/M به هر گره کسری از دادهها نگاشت بشن میشه حالت متوسطش که میشه همون N/M برای مثال اگه ۱۰ عنصر داشته باشیم و ۵ مدخل میشه ۱۰/۵ یعنی همون ۲ که یک حالت متوسطه حالت خوبش هم اینه که N=M باشه که برای هر مدخل یک عنصر نگاشت میشه. امیدوارم درست بوده باشه |