AlgoVerse

پشته با MULTIPOP (تحلیل سرشکن)

یک MULTIPOP ممکن است چند عضو را با هم بردارد و گران باشد، ولی هر عضو حداکثر یک بار برداشته می‌شود؛ پس هزینه‌ی کل n عمل حداکثر 2n است.

پشته‌ای با سه عمل: PUSH(x)، POP و MULTIPOP(k) که حداکثر k عضو از بالا برمی‌دارد. یک MULTIPOP ممکن است O(n) هزینه داشته باشد، پس شاید فکر کنی n عمل O(n²) هزینه دارند.

ادامه‌ی توضیح ↓
ورودی:
n=10خروجی PDF

عددهای مثبت PUSH و منفی‌ها MULTIPOP اند: شش PUSH، MULTIPOP(4)، دو PUSH و MULTIPOP(10). هزینه‌ی کل ۱۶ برای ۱۰ عمل (۸ PUSH و ۸ pop)، کمتر از ۲ × ۱۰.

  1. def multipop_stack(ops):
  2. # A positive number pushes itself; −k pops up to k items at once (0 pops nothing).
  3. stack = []
  4. cost = 0
  5. for op in ops:
  6. if op > 0:
  7. stack.append(op)
  8. cost = cost + 1
  9. else:
  10. k = -op
  11. while stack and k > 0:
  12. stack.pop()
  13. k = k - 1
  14. cost = cost + 1
  15. return cost

ناوردا: تعداد کل pop ها هیچ‌وقت از تعداد کل push ها بیشتر نمی‌شود، پس هزینه‌ی کل حداکثر دو برابر تعداد عمل‌هاست.

شروع اجرا

503182139425-467768-109

متغیرهای محلی

نارنجی = در همین گام عوض شد

ops list

538192-476-10

Call stack

  1. multipop_stack()خط 1
گام ۱ از ۷۷
خط سیاه = push, multipop · خط نارنجی = گام کلیدیpush: 0/8 · multipop: 0/2 · pop: 0/8 · total: 0/1
    توضیح

    ایده

    پشته‌ای با سه عمل: PUSH(x)، POP و MULTIPOP(k) که حداکثر k عضو از بالا برمی‌دارد. یک MULTIPOP ممکن است O(n) هزینه داشته باشد، پس شاید فکر کنی n عمل O(n²) هزینه دارند.

    تحلیل سرشکن

    هر عضو فقط یک بار push و حداکثر یک بار pop می‌شود. پس تعداد کل pop ها (حتی درون MULTIPOP ها) از تعداد push ها بیشتر نیست و هزینه‌ی کل n عمل حداکثر 2n است: هر عمل به‌طور سرشکن O(1).

    روش پتانسیل: پتانسیل را تعداد عضوهای پشته بگیر. PUSH پتانسیل را یکی زیاد می‌کند (هزینه‌ی سرشکن ۲)، و هر pop یک واحد پتانسیل خرج می‌کند (هزینه‌ی سرشکن ۰).

    ورودی

    عددهای مثبت PUSH همان عدد و عدد منفی −k یعنی MULTIPOP(k).

    در trace به چه چیزی نگاه کنی

    • میله‌ها پشته‌اند (بالای پشته سمت راست). cost در پنل حافظه هزینه‌ی کل تا اینجاست.