آرایه های پویا ساختارهای داده هستند که به طور خودکار هنگامی که به ظرفیت می رسند، اندازه گیری می کنند. درک هزینه های حفظ شده آنها به ارزیابی کارایی آنها در چندین عملیات کمک می کند.

هزینه های حفظ شده چیست؟

هزینه حفظ شده هزینه متوسط برای هر عملیات بر اساس یک توالی از عملیات است.این هزینه های بالا برای به روز رسانی گاه به گاه با توزیع آنها در بسیاری از عملیات ارزان را هموار می کند.

Dynamic Array

عملیات مشترک در آرایه های پویا شامل قرار دادن، حذف و بازیابی اثرات.در پایان معمولاً مکرر ترین عملیات است که ممکن است باعث بازسازی زمانی شود که ظرفیت افزایش یابد.

محاسبه هزینه های Amortized Cost

هنگام قرار دادن عناصر، آرایه زمانی که پر شود، دو برابر می شود.هزینه بازسازی شامل کپی کردن تمام عناصر موجود به آرایه جدید است.اگر چه بازسازی گران است، اما به طور مداوم رخ می دهد.

به عنوان مثال، اگر یک آرایه با ظرفیت 1 شروع شود، توالی جبران هزینه ها بر روی چندین واردکننده می تواند خلاصه شود:

  • عنصر 1 را وارد کنید: هزینه 1
  • عنصر دوم را وارد کنید: اندازه (هزینه 1)، کل هزینه 2
  • عنصر سوم را وارد کنید: اندازه (هزینه 2)، کل هزینه 3
  • عنصر چهارم را وارد کنید: اندازه (هزینه 4)، کل هزینه 4

کل هزینه بیش از n Insertions متناسب با 2n است و هزینه حفظ شده برای هر وارد کردن تقریبا O (1) است.