سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی - نسخهی قابل چاپ |
سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی - Morris - 15 بهمن ۱۳۹۲ ۱۰:۳۴ ق.ظ
سلام دوستان. امیدوارم در این روز ها که خیلی به امتحان نزدیک شدیم شاد و سلامت باشید. در ادامه سوالی را قرار دادم که پاسخ آن مرا راضی نمی کند. اولا صورت سوال گفته فرض کنید n عنصر در جدول وجود دارد ولی در حل فرض کرده n خانه خالی داریم. دوما هزینه سرشکن را حساب نکرده است بلکه هزینه کل را حساب کرده است (باید نتیجه را بر n تقسیم کند). به نظر من پاسخ این سوال گزینه ۱ است. در صورت امکان بفرمایید راه حل آن به چه صورت است. مطالب زیر را تنها من باب مزاح عرض می کنم : در کنکور ۹۰ نیز طراح، سوالی شبیه این مطرح کرده بود و آن قدر در صورت سوال فرو رفت که سوال را نادرست مطرح کرد و آن سوال حذف شد. گویا همان طراح دو سال بعد متوجه اشتباه خود شد و آن سوال را کمی پیچیده تر مجددا مطرح نموده و خیلی دوست دارم بدانم که آیا این بار هم برای خود پشت پا انداخته و سکندری خورده است یا اینکه من موضوعی را به یاد نمی آورم. |
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی - mahsalove - 15 بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ
سلام این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی: n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر! بدترین حالت وقتی است که ۳/۴ جدول پر باشد در این صورت با اولین عمل درج جدولی به طول ۲ برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم ۳/۸ جدول پر است : ۳/۴ m= ۳/۸(۲ m) که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n) پس همون تتا n ج درست است! یعنی میانگین n عمل در بدترین حالت که بدترین حالتم این زمان اتفاق می افتد. موفق باشید.... |
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی - Morris - 15 بهمن ۱۳۹۲ ۰۳:۳۳ ب.ظ
سپاس فراوان از شما دوست عزیز با توضیحات شما موضوع را کاملا متوجه شدم. |
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی - Riemann - 16 بهمن ۱۳۹۲ ۱۲:۱۶ ب.ظ
(۱۵ بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ)mahsalove نوشته شده توسط: سلام سلام ممنونم از جوابتون ولی من متوجه نشدم، اونچه که دیدم این بود که شما فقط دوتا عمل رو انجام دادید نه n عمل! یه دونه درج که وقتی جدول به مرز رسیده که باعث میشه ما گسترش بدیم جدولو و دیگری یه دونه حذف مانند بالا در شرایط مرزی؟ ولی چیزی از n-1 عمل باقی مونده نگفتید و میانگین نگرفتید! البته شاید من متوجه نشدم. |
RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی - mahsalove - 16 بهمن ۱۳۹۲ ۰۲:۲۲ ب.ظ
ببینید تا اونجایی که من یادمه دکتر یوسفی گفتن اگر بدترین حالت این موقعه اتفاق بیفته پس به صورت مکرر با هر حذف و درج این روند داره ادامه پیدا می کنه چون طبق تعریف سرشکن شده ما برای n عمل در بدترین حالت در نظر گرفتیم پس با هر حذف و درجی این تتا n داره برای هر عمل اتفاق می افته پس برای n عمل هر کدوم جداگانه n پس میشه n^2/n=n که دیگه طبق تعریف سرشکن شده یعنی میانگین n عمل در بدترین حالت ج همین میشه! موفق باشید.... |