تالار گفتمان مانشت

نسخه‌ی کامل: سوال 51 ساختمان داده 92 مهندسی - جداول درهم سازی
شما در حال مشاهده‌ی نسخه‌ی متنی این صفحه می‌باشید. مشاهده‌ی نسخه‌ی کامل با قالب بندی مناسب.
سلام دوستان. امیدوارم در این روز ها که خیلی به امتحان نزدیک شدیم شاد و سلامت باشید.
در ادامه سوالی را قرار دادم که پاسخ آن مرا راضی نمی کند.
اولا صورت سوال گفته فرض کنید n عنصر در جدول وجود دارد ولی در حل فرض کرده n خانه خالی داریم.
دوما هزینه سرشکن را حساب نکرده است بلکه هزینه کل را حساب کرده است (باید نتیجه را بر n تقسیم کند).



به نظر من پاسخ این سوال گزینه ۱ است.
در صورت امکان بفرمایید راه حل آن به چه صورت است.

مطالب زیر را تنها من باب مزاح عرض می کنم Big Grin :
در کنکور ۹۰ نیز طراح، سوالی شبیه این مطرح کرده بود و آن قدر در صورت سوال فرو رفت که سوال را نادرست مطرح کرد و آن سوال حذف شد. گویا همان طراح دو سال بعد متوجه اشتباه خود شد و آن سوال را کمی پیچیده تر مجددا مطرح نموده و خیلی دوست دارم بدانم که آیا این بار هم برای خود پشت پا انداخته و سکندری خورده است یا اینکه من موضوعی را به یاد نمی آورم.
سلام
این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی:
n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر!
بدترین حالت وقتی است که 3/4 جدول پر باشد در این صورت با اولین عمل درج جدولی به طول 2 برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم 3/8 جدول پر است :
3/4 m=
3/8(2 m)
که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n)
پس همون تتا n ج درست است!

یعنی میانگین n عمل در بدترین حالت که بدترین حالتم این زمان اتفاق می افتد.

موفق باشید....

سپاس فراوان از شما دوست عزیز با توضیحات شما موضوع را کاملا متوجه شدم.
(15 بهمن 1392 12:42 ب.ظ)mahsalove نوشته شده توسط: [ -> ]سلام
این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی:
n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر!
بدترین حالت وقتی است که ۳/۴ جدول پر باشد در این صورت با اولین عمل درج جدولی به طول ۲ برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم ۳/۸ جدول پر است :
۳/۴ m=
۳/۸(۲ m)
که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n)
پس همون تتا n ج درست است!

یعنی میانگین n عمل در بدترین حالت که بدترین حالتم این زمان اتفاق می افتد.

موفق باشید....


سلام
ممنونم از جوابتون ولی من متوجه نشدم، اونچه که دیدم این بود که شما فقط دوتا عمل رو انجام دادید نه n عمل! یه دونه درج که وقتی جدول به مرز رسیده که باعث میشه ما گسترش بدیم جدولو و دیگری یه دونه حذف مانند بالا در شرایط مرزی؟ ولی چیزی از n-1 عمل باقی مونده نگفتید و میانگین نگرفتید! البته شاید من متوجه نشدم.Undecided
ببینید تا اونجایی که من یادمه دکتر یوسفی گفتن اگر بدترین حالت این موقعه اتفاق بیفته پس به صورت مکرر با هر حذف و درج این روند داره ادامه پیدا می کنه چون طبق تعریف سرشکن شده ما برای n عمل در بدترین حالت در نظر گرفتیم پس با هر حذف و درجی این تتا n داره برای هر عمل اتفاق می افته پس برای n عمل هر کدوم جداگانه n پس میشه n^2/n=n

که دیگه طبق تعریف سرشکن شده یعنی میانگین n عمل در بدترین حالت ج همین میشه!

موفق باشید....
لینک مرجع