ارایه پویا

آرایه پویا. آرایه پویا، در علوم کامپیوتر، آرایه ای است که می تواند تغییر اندازه دهد و اجازه دهد عناصری به آن اضافه یا از آن حذف شود. امروزه امکان انجام این عمل در بسیاری از کتابخانه های استاندارد زبان های رایج برنامه نویسی تعبیه شده است. در یک آرایه پویا در ابتدای کار حافظه اختصاص داده نمی شود؛ به طوری که اندازه اش غیرقابل تغییر باشد.
ساده ترین آرایه پویا با اختصاص دادن آرایه ای به طول ثابت ساخته می شود که بعد آن را به دو قسمت تقسیم می کنند: قسمت اول عناصر آرایه پویا را ذخیره می کند و قسمت دوم ذخیره شده، یا بدون استفاده می ماند. سپس می توان با استفاده از فضای رزرو شده در زمانی ثابت عناصر را به انتهای آرایه پویا اضافه کرد یا آن ها را حذف کرد، تا زمانی که این فضا به طور کامل استفاده شود. تعداد عناصری که توسط محتویات آرایه پویا استفاده می شود اندازه منطقی یا اندازه آن است، در حالیکه اندازه آرایه زیرین ظرفیت آرایه پویا نام دارد، که حداکثر اندازه منطقی ممکن است. در برنامه هایی که اندازه منطقی کراندار است، این ساختار داده کفایت می کند. تغییر دادن اندازه آرایه زیرین عملی هزینه بر است، گاهی ناچار می شویم تمام محتویات آرایه را کپی کنیم.
برای جلوگیری از تحمیل هزینه های اضافی حاصل از تغییر اندازه دادن های مکرر، آرایه های پویا به مقدار زیادی تغییر اندازه می دهند، مثلاً به دو برابر اندازه اولیه تغییر اندازه می دهند، و فضای رزرو شده را برای بسط بعدی استفاده می کنند. عمل اضافه کردن یک عنصر باید مانند زیر انجام شود:
function insertEnd ( dynarray a, element e ) if ( a. size = a. capacity ) // ( اندازه را به دو برابر مقدار اولیه تغییر می دهیم ) : a. capacity ← a. capacity * 2 // ( کپی کردن محتویات در محل حافظه جدید ) a ← e a. size ← a. size + 1 در فرایند درج n عنصر، ظرفیت ها تشکیل تصاعد هندسی می دهند. بسط دادن آرایه با هر نسبت ثابتی تضمین می کند وارد کردن عصر در کل از ( O ( n زمان می برد، یعنی وارد کردن هر عنصر زمان سرشکن شده ثابتی می برد. مقدار این تناسب منجر به لزوم سبک سنگین کردن این فصله زمانی می شود: زمان متوسط هر بار وارد کردن تقریباً ( a/ ( a - ۱ است، در حالی که تعداد خانه های تلف شده از بالا به a−۱ ) n ) کراندار است. انتخاب a بستگی به برنامه دارد، ولی معمولاً a=۲ می گیرند. بعلاوه در بسیاری از آرایه های پویا اگر مقدار استفاده شده از حدی کمتر شود، مانند ۳۰٪ ظرفیت، آن را آزاد می کنند. آرایه های پویا مثال رایجی در تدریس تحلیل سرشکن شده[ ۱] هستند.