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

تحلیل زمانی پیاده سازی صف و پشته

ارسال:
  

javad94 پرسیده:

Question تحلیل زمانی پیاده سازی صف و پشته

سلام دوستان

به دو تا سوال زیر پاسخ دهید :

۱ – وقتی که می خواهیم یک صف رو توسط دو پشته پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟

۲ – وقتی که می خواهیم یک پشته رو توسط دو صف پیاده سازی کنیم تحلیل زمانی چه جوری می شود؟

تحلیل خودم واسه سوال اول این است که چون دو پشته داریم برای ساخت یک صف : پشته اول هم Push و هم Pop در زمان O(1) انجام می شود و هم در پشته دوم هر دوی عملیات Push و Pop در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.

واسه سوال دوم چون دو صف داریم برای ساخت یک پشته : صف اول هم درج و هم حذف در زمان O(1) انجام می شود و هم در صف دوم هر دوی عملیات درج و حذف در زمان O(1) انجام می شود پس در کل زمان O(1) خواهد بود.

اگر اشتباه می کنم لطفا منو راهنمایی کنید و تحلیل درست رو انجام بدین .

بسیار سپاسگزارم
نقل قول این ارسال در یک پاسخ

۴
ارسال:
  

Farid_Feyzi پاسخ داده:

RE: تحلیل زمانی پیاده سازی صف و پشته

سلام
به نظرم سعی کنید یکم دقیق تر بررسی رو انجام بدین. یعنی صرفا به جای اینکه ببینین هزینه عملیات 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
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

rad.bahar پاسخ داده:

RE: تحلیل زمانی پیاده سازی صف و پشته

(۰۵ مرداد ۱۳۹۲ ۰۴:۵۲ ب.ظ)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 برابر طول صف قبل از درج عنصر جدید می باشد
تحلیل مشابه ای را هم می توان برای پیاده سازی پشته با دو صف نیز بیان کرد
اگر اشتباه می کنم یا منظورتون بد فهمیدم لطفا جواب بدید
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

javad94 پاسخ داده:

تحلیل زمانی پیاده سازی صف و پشته

ممنونم از هر دو دوست عزیز

درسته به قول آقا فرید من به جزئیات توجه نکردم ....

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  استخدام کارشناس تحلیل داده zeinab_IT ۰ ۱,۲۸۲ ۱۷ بهمن ۱۴۰۰ ۱۲:۳۱ ب.ظ
آخرین ارسال: zeinab_IT
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۹۳۶ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  استفاده از پشته armiii ۰ ۱,۱۱۲ ۰۳ دى ۱۴۰۰ ۱۲:۴۳ ق.ظ
آخرین ارسال: armiii
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۹۱۸ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۶۱۹ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  بهترین گرایش برای موقعیت شغلی تحلیل سیستم shahabkarimi00 ۳ ۶,۰۷۱ ۰۹ آذر ۱۳۹۹ ۰۳:۳۵ ب.ظ
آخرین ارسال: mohammadasadi1
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۷,۵۱۱ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  خواص محیط برای عامل سیستم تحلیل تصاویر پزشکی Ali1991khe ۶ ۶,۰۳۳ ۰۴ مهر ۱۳۹۹ ۰۸:۳۲ ق.ظ
آخرین ارسال: Ali1991khe
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۳,۰۵۵ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۶۴۹ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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