بررسی درستی چند گزاره از داده ساختارها

Question

سلام

از 3 گزاره زیر 2 گزاره صحیح اعلام شده ، به نظرم هر 3 غلط هستند چه با hash و disjoin set و فیبوناچی و

امگا logn هستند :

1- داده ساختاری برای n عنصر وجود دارد که بتوان اعمال push وpop و یافتن عنصر کمینه موجود را در O(1) انجام داد.

2- داده ساختاری برای n عنصر وجود دارد که بتوان اعمال push وpop و یافتن عنصر کمینه موجود و یافتن مقدار بیشینه را در O(1) انجام داد.

3 -داده ساختاری برای n عنصر وجود دارد که بتوان اعمال push وpop و حذف عنصر کمینه موجود را در O(1) انجام داد.

با تشکر

Answer 1

سلام 

1و2 میشه چون می توانیم هر موقع که یک مقدار را داخل استک اضافه کنیم مقدار ماکزیمم و مینیمم را نیز با آن اضافه کنیم (می تونیم از دوتا استک هم اضافه کنیم) اینطور با هر بار اضافه کردن فقط کافیه یک مقایسه انجام بدیم(برای ماکزیمم و مینیمم دوتا مقایسه ) و به راحتی می توانیم با یک pop کردن از استک هم آخرین مقدار به همراه مینیمم یا ماکسیمم را بدست بیاوریم اما برای 3 اینطور نمی توان گفت (چون فکر کنم منظورش پشته و صف می باشد).

Comments

سلام طبق چیزی که شما میگید پس 3 هم درست هستش .  فرض کنید ساختار یک linked list باشه میشه زمان اضافه کردن عنصر اگر مینیمم بود  اشاره گری که ساخته میشه رو هم جدا ذخیره کرد و با (O(1 عنصر رو حذف کرد.

---

تو ساختار های قبلی به صورت پشته بودن و فقط می خواستیم عنصر را پیدا کنیم که با push و pop انجام میشد  برای لینک لیست هم به قول شما می تونیم آدرسی که اشاره گر به مینیمم یا ماکسیمم اشاره میکنه رو بدین به عنصر جاری اما برخلاف پشته و صف که ایندکس های اولو آخر رو داریم برای لینک لیست نداریم که بخواهیم آدرس عنصر مینیمم را داشته باشیم که باید برای این کار پیمایش انجام بدیم اما اگر داشتیم اونوقت آن هم در زمان o(1) شدنی بود

---

امکان ذخیره آدرس مینیمم هست(زمانی که push می کنیم کافیه که عنصری که اضافه میشه با عنصر مینیمم مقایسه بشه اگر کمتر بود آدرس ذخیره میشه )
 البته صحبت شما درسته این کار در کل قابل انجام نیست چون  بعد از یک بار حذف مینیمم حذف مینیمم بعدی با (1)O شدنی نیست