موضوع مقاله: آرایه پویا | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # آرایه پویا | مقدمه: اکثر عملیات ها سریع هستند (زمان ثابت) اما آن هایی که با لاکپشت نمایش داده شده اند به اندازه ضریبی از اندازه آرایه زمان می برند. | ## بخش 1: آرایه پویا | آرایه پویا، در علوم کامپیوتر، آرایه‌ای است که می‌تواند تغییر اندازه دهد و اجازه دهد عناصری به آن اضافه یا از آن حذف شود. امروزه امکان انجام این عمل در بسیاری از کتابخانه‌های استاندارد زبان‌های رایج برنامه‌نویسی تعبیه شده‌است. در یک آرایه پویا در ابتدای کار حافظه اختصاص داده نمی‌شود؛ به‌طوری‌که اندازه‌اش غیرقابل تغییر باشد. آرایه‌های پویای کراندار و ظرفیت آن‌ها ساده‌ترین آرایه پویا با اختصاص دادن آرایه‌ای به طول ثابت ساخته می‌شود که بعد آن را به دو قسمت تقسیم می‌کنند: قسمت اول عناصر آرایه پویا را ذخیره می‌کند و قسمت دوم ذخیره شده، یا بدون استفاده می‌ماند. سپس می‌توان با استفاده از فضای رزرو شده در زمانی ثابت عناصر را به انتهای آرایه پویا اضافه کرد یا آن‌ها را حذف کرد، تا زمانی که این فضا به‌طور کامل استفاده شود. تعداد عناصری که توسط محتویات آرایه پویا استفاده می‌شود اندازه منطقی یا اندازه آن است، در حالیکه اندازه آرایه زیرین ظرفیت آرایه پویا نام دارد، که حداکثر اندازه منطقی ممکن است. تغییر دادن اندازه آرایه زیرین عملی هزینه بر است، گاهی ناچار می‌شویم تمام محتویات آرایه را کپی کنیم. | ## بخش 2: آرایه پویا | تصاعد هندسی و هزینه واگذار شده برای جلوگیری از تحمیل هزینه‌های اضافی حاصل از تغییر اندازه دادن‌های مکرر، آرایه‌های پویا به مقدار زیادی تغییر اندازه می‌دهند، مثلاً به دو برابر اندازه اولیه تغییر اندازه می‌دهند، و فضای رزرو شده را برای بسط بعدی استفاده می‌کنند. بسط دادن آرایه با هر نسبت ثابتی تضمین می‌کند وارد کردن عصر در کل از (O(n زمان می‌برد، یعنی وارد کردن هر عنصر زمان سرشکن شده ثابتی می‌برد. مقدار این تناسب منجر به لزوم سبک‌سنگین کردن این فصله زمانی می‌شود: زمان متوسط هر بار وارد کردن تقریباً (a/(a-۱ است، در حالی که تعداد خانه‌های تلف شده از بالا به a−۱)n) کراندار است. بعلاوه در بسیاری از آرایه‌های پویا اگر مقدار استفاده شده از حدی کمتر شود، مانند ۳۰٪ ظرفیت، آن را آزاد می‌کنند. معمولاً آرایه‌های پویا در کل فقط یک حافظه اضافی کوچکی برای اطلاعات اندازه و ظرفیت دارند. این ویژگی موجب می‌شود آرایه‌های پویا ابزار مناسبی برای ساختن داده ساختار متناسب با حافظه نهان شوند. آرایه‌های پویا در مقایسه با لینک لیست، قابلیت شاخص گذاریindexing سریع تری دارند (زمان ثابت در برابر زمان خطی) و معمولاً به دلیل اصلاح محل مرجع عناصر سریعتر می‌توان بر روی عناصر واقع در خانه‌های آرایه حرکت کرد؛ اگرچه، آرایه‌های پویا برای وارد کردن در محلی دلخواه یا پاک کردن از جایگاهی اختیاری زمانی خطی نیاز دارند، چون همه عناصر بعدی باید یک عنصر جابه‌جا شوند، در حالیکه لینک لیست می‌تواند این عمل را در زمانی ثابت انجام دهد. | ## بخش 3: آرایه پویا | به وسیلهٔ میانگیر وقفهgap buffer و متغیرهای بردار صف شده این اشکال را برطرف کرده‌اند که در مورد آن در قسمت متغیرها بحث شده‌است. همچنین، ممکن است یافتن فضایی پیوسته در ناحیه یک حافظه بسیار قطعه بندی شده هزینه بر یا غیرممکن باشد، در حالیکه لینک لیست‌ها نیازی ندارند همه داده ساختار به‌طورپیوسته در حافظه ذخیره شود. متغیرها میانگیرهای وقفه شبیه آرایه‌های پویا هستند ولی اجازه می‌دهند عملگرهای کارای درج و حذف نزدیک محل اختیاری مشابه جمع شوند. برخی از پیاده‌سازی‌های صف دو سر از آرایه‌های صف دو سر استفاده می‌کنند، که اجازه درج/جابجایی در هر دو سر، به جای یک طرف می‌دهد. درخت آرایه‌ای درهم حافظه‌ای از مرتبه n۱/۲ هدر می‌دهد، که n تعداد عناصر آرایه‌است. وقتی دنباله‌ای از اشیا به انتهای درخت آرایه‌ای درهم می‌افزاییم، کارکرد سرشکن الگوریتم O(۱) است. در مقاله‌ای یک داده ساختار آرایه پویای صفیtiered dynamic array توصیف کرد، که در هر نقطه‌ای از زمان تنها n۱/۲ فضا برای n عنصر هدر می‌داد، و آن‌ها کران پایینی را ثابت کردند که نشان می‌داد در هر آرایه پویایی اگر عملگرها می‌خواهند زمان ثابت سرشکنی بگیرند حداقل به این مقدار فضا نیاز هست. | ## جمع‌بندی | بعلاوه، برای مواردی که رشد کردن و جمع شدن میانگیرنه تنها درحالت سرشکن بلکه در بدترین حالت ثابت باشد، متغیری ارائه کردند.