سلام دوستان
به دو تا سوال زیر پاسخ دهید :
۱ – وقتی که می خواهیم یک صف رو توسط دو پشته پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟
۲ – وقتی که می خواهیم یک پشته رو توسط دو صف پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟
تحلیل خودم واسه سوال اول این است که چون دو پشته داریم برای ساخت یک صف : پشته اول هم Push و هم Pop در زمان O(1) انجام می شود و هم در پشته دوم هر دوی عملیات Push و Pop در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.
واسه سوال دوم چون دو صف داریم برای ساخت یک پشته : صف اول هم درج و هم حذف در زمان O(1) انجام می شود و هم در صف دوم هر دوی عملیات درج و حذف در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.
اگر اشتباه می کنم لطفا منو راهنمایی کنید و تحلیل درست رو انجام بدین .
بسیار سپاسگزارم
(۰۵ مرداد ۱۳۹۲ ۰۴:۵۲ ب.ظ)afshin.dam نوشته شده توسط: ۱ – وقتی که می خواهیم یک صف رو توسط دو پشته پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟راستش مطمئن نیستم که حرفی که می زنم درسته ولی با تحلیل شما هم موافق نیستم
۲ – وقتی که می خواهیم یک پشته رو توسط دو صف پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟
تحلیل خودم واسه سوال اول این است که چون دو پشته داریم برای ساخت یک صف : پشته اول هم Push و هم Pop در زمان O(1) انجام می شود و هم در پشته دوم هر دوی عملیات Push و Pop در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.
واسه سوال دوم چون دو صف داریم برای ساخت یک پشته : صف اول هم درج و هم حذف در زمان O(1) انجام می شود و هم در صف دوم هر دوی عملیات درج و حذف در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.
به نظرم برای پیاده سازی یک صف توسط دو پشته باید این گونه عمل کرد که یکی از پشته ها(پشته اول) حاوی تمامی عناصر صف (به این ترتیب که عنصری که در سر صف قرار دارد در بالای پشته و عناصر میانی صف بعد از ان تا اخرین عنصر صف که ته پشته قرار دارد) و پشته دوم خالی باشد
حالا در اینجا دو موضوع مطرح میشه
اولی حذف از صف که چون همواره عنصر سر صف بالای پشته قرار دارد این کار در مرنبه O(1) انجام میشه
دومی درج در صف. برای اولین باری که صف خالیه فقط کافیه با یک عملیات push عنصر جدید را یه پشته اضافه کرد ولی اگر صف خالی نیست برای این کار باید عنصری که اضافه می شود در ته پشته اول قرار گیرد. برای این کار تمام عناصر موجود در پشته اول را با pop و push کردن های متوالی به پشته دوم منتقل می کنیم تا پشته اول خالی شود سپس عنصر جدید را با یک push به پشته اول اضافه می کنیم و بعد دوباره با pop و push کردن های متوالی تمام بقیه عناصر صف را از پشته دوم به اول منتقل می کنیم پس از این کار دوباره عناصر صف به ترتیبی که عنصری که در سر صف قرار دارد در بالای پشته و عناصر میانی صف بعد از ان تا اخرین عنصر صف در ته پشته مرتب می شوند که تعداد pop و push این کار مجموعا ۲n+1 تا است یعنی مرتبه زمانی ان O(n) است توجه کنید که n برابر طول صف قبل از درج عنصر جدید می باشد
تحلیل مشابه ای را هم می توان برای پیاده سازی پشته با دو صف نیز بیان کرد
اگر اشتباه می کنم یا منظورتون بد فهمیدم لطفا جواب بدید
سلام
به نظرم سعی کنید یکم دقیق تر بررسی رو انجام بدین. یعنی صرفا به جای اینکه ببینین هزینه عملیات Push و Pop و یا عملیات روی صف [tex]O(1)[/tex] میشه یا [tex]O(n)[/tex]، بیایین ببینین دقیقاً چند میشه مثلا ۱ یا ۲ یا ۳ یا ۲n و ...
سوالات کنکور اخیراً به این سمت میرن و باید ریزتر بشین و با جزئیات تمام مطالب رو بررسی کنید.
یک پشته با دو صف:
روش اول:
Push:
درج در صف ۱
هزینه = ۱
POP:
تا زمانی که اندازه صف ۱ بزرگتر از ۱ هست، از صف ۱ عناصر حذف شده و در صف ۲ درج می شوند.
حذف اخرین عنصر موجود در صف ۱ و برگرداندن آن و تغییر نام صف ۱ به صف ۲ و بالعکس
هزینه: n-1 حذف + n-1 درج + ۱ حذف---- پس: ۲n-1 (با فرض اینکه قبل حذف، n عنصر تو صف۱ هست)
روش دوم:
Push:
درج در صف ۲
انتقال همه عناصر موجود در صف ۱ به صف ۲، سپس تغییر نام های صف ۱ به صف ۲ و بالعکس
هزینه: ۱ درج + n درج = n+1 (با فرص اینکه موقع درج، n عنصر در صف ۱ هست)
POP:
حذف عنصر از صف ۱
هزینه= ۱
پس روش دوم بهتر هست.
پیاده سازی یک صف با دو پشته:
Queue
درج عنصر جدید در پشته۱
هزینه: ۱
Dequeue:
اگر پشته ۲ خالی باشد، همه عناصر پشته ۱ را پاپ کرده در پشته ۲ پوش کنید
عنصر بالای پشته ۲ را پاپ کرده و برگردانید.
هزینه: n تا پاپ+n تا پوش + ۱ پاپ = ۲n+1
البته میشه همه عناصر بجز یه عنصر آخر رو از پشته ۱ پاپ کنیم و در پشته ۲ پوش کنیم و اون تک عنصر که تو پشته ۱ مونده رو به عنوان خروجی برگردونیم که اینجوری هزینه میشه n-1+n-1+1=2n-1
ممنونم از هر دو دوست عزیز
درسته به قول آقا فرید من به جزئیات توجه نکردم ....
ممنونم