زمان کنونی: ۰۳ آذر ۱۴۰۳, ۰۱:۵۴ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی

ارسال:
  

Morris پرسیده:

سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی

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



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

مطالب زیر را تنها من باب مزاح عرض می کنم Big Grin :
در کنکور ۹۰ نیز طراح، سوالی شبیه این مطرح کرده بود و آن قدر در صورت سوال فرو رفت که سوال را نادرست مطرح کرد و آن سوال حذف شد. گویا همان طراح دو سال بعد متوجه اشتباه خود شد و آن سوال را کمی پیچیده تر مجددا مطرح نموده و خیلی دوست دارم بدانم که آیا این بار هم برای خود پشت پا انداخته و سکندری خورده است یا اینکه من موضوعی را به یاد نمی آورم.


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۵
ارسال:
  

mahsalove پاسخ داده:

RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی

سلام
این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی:
n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر!
بدترین حالت وقتی است که ۳/۴ جدول پر باشد در این صورت با اولین عمل درج جدولی به طول ۲ برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم ۳/۸ جدول پر است :
۳/۴ m=
۳/۸(۲ m)
که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n)
پس همون تتا n ج درست است!

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

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

نقل قول این ارسال در یک پاسخ

ارسال:
  

Morris پاسخ داده:

RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی

سپاس فراوان از شما دوست عزیز با توضیحات شما موضوع را کاملا متوجه شدم.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Riemann پاسخ داده:

RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی

(۱۵ بهمن ۱۳۹۲ ۱۲:۴۲ ب.ظ)mahsalove نوشته شده توسط:  سلام
این ج که واستون می نویسم ج دکتر یوسفی هست در باب این سوال که سر کلاس برای ما حل کردن!اول تعریف هزینه سرشکنی یعنی:
n عمل را در بدترین حالت بگیر سپس میانگینشان را بگیر!
بدترین حالت وقتی است که ۳/۴ جدول پر باشد در این صورت با اولین عمل درج جدولی به طول ۲ برابر ایجاد می شود و با مرتبه تتا n عناصر جدول قبلی به جدول جدید کپی می شوند.حال اگر یک عمل حذف انجام دهیم ۳/۸ جدول پر است :
۳/۴ m=
۳/۸(۲ m)
که دوباره مجبوریم جدولی به اندازه نصف ایجاد و دوباره عمل کپی را انجام دهیم.(تتا n)
پس همون تتا n ج درست است!

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

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


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

۳
ارسال:
  

mahsalove پاسخ داده:

RE: سوال ۵۱ ساختمان داده ۹۲ مهندسی - جداول درهم سازی

ببینید تا اونجایی که من یادمه دکتر یوسفی گفتن اگر بدترین حالت این موقعه اتفاق بیفته پس به صورت مکرر با هر حذف و درج این روند داره ادامه پیدا می کنه چون طبق تعریف سرشکن شده ما برای n عمل در بدترین حالت در نظر گرفتیم پس با هر حذف و درجی این تتا n داره برای هر عمل اتفاق می افته پس برای n عمل هر کدوم جداگانه n پس میشه n^2/n=n

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

موفق باشید....
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Question بهترین منبع ساختمان داده برای کنکور ارشد marvelous ۱۰ ۱۲,۵۷۹ ۱۵ آذر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: msnmkh
  فیلم آموزش ساختمان داده negin_bt ۰ ۱,۲۶۴ ۲۰ مهر ۱۴۰۱ ۰۷:۵۶ ب.ظ
آخرین ارسال: negin_bt
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۹۰۸ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۶۱۵ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۷,۴۶۴ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  معرفی کتاب برای ساختمان داده siamakaf ۲ ۴,۶۶۳ ۱۲ آبان ۱۳۹۹ ۰۹:۲۱ ق.ظ
آخرین ارسال: siamakaf
  ساختمان داده و پایگاه داده پارسه امیدوار ۴ ۴,۵۲۹ ۱۲ خرداد ۱۳۹۹ ۰۸:۰۳ ب.ظ
آخرین ارسال: marvelous
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۴,۲۰۱ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  فصل HEAP از کتاب ساختمان داده طورانی (پارسه) tourani ۳۷ ۳۹,۹۸۸ ۱۲ اسفند ۱۳۹۸ ۰۵:۱۹ ب.ظ
آخرین ارسال: hossein4070
  منبع ساختمان داده RASPINA ۷ ۷,۹۴۷ ۱۶ آذر ۱۳۹۸ ۰۱:۳۰ ق.ظ
آخرین ارسال: Behnam‌

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close