حل تشریحی سوال شماره 9 ساختمان داده ها و طراحی الگوریتم ها
کنکور دکتری مهندسی کامپیوتر 1404
فرض کنید یک پشته S داده شده است که عملیات های استاندارد PUSH، POP و TOP را پشتیبانی می کند. حال می خواهید یک عملیات جدید به نام FIND-MAX(S) طراحی کنید که بزرگ ترین مقدار موجود در پشته را در زمان بهینه پیدا کند. کدام مورد زیر، رویکرد صحیح و کارآمدی برای پیاده سازی این عملیات ارائه می دهد؟
همراه با هر PUSH، مقدار جدید را در متغیر MAX ذخیره کنید اگر مقدار جدید بزرگ تر از مقدار موجود در MAX باشد. عملیات FIND-MAX(S) در این روش دارای پیچیدگی است، اما بازگرداندن مقدار قبلی MAX پس از یک عملیات POP ، به زمان O(n) نیاز دارد.
در هر بار فراخوانی FIND-MAX(S)، تمامی عناصر پشته را با استفاده از عملیات POP خارج کنید، بزرگ ترین مقدار را پیدا کنید و سپس عناصر را به ترتیب اصلی به پشته بازگردانید. این روش دارای پیچیدی زمانی O(n) برای هر فراخوانی است.
از یک پشته کمکی M استفاده کنید که در هر PUSH مقدار بزرگ ترین عنصر پشته S را تا آن لحظه ذخیره می کند. در هنگام POP، مقدار بالای پشته M نیز حذف می شود. عملیات FIND-MAX(S) در این روش، دارای پیچیدگی زمان O(1) است.
در هر PUSH، مقدار بزرگ ترین عنصر پشته تا آن لحظه را با استفاده از مقایسه بازگشتی تعیین کنید و آن را به پشته اصلی S اضافه کنید. این روش دارای پیچیدگی زمان O(logn) برای FIND-MAX(S) است.