آرایه‌ها (Arrays)

آرایه چیست؟

آرایه (Array) مجموعه‌ای از عناصر هم‌نوع است که در خانه‌های پشت‌سرهم حافظه ذخیره می‌شوند. هر عنصر با اندیس (index) — معمولاً از صفر — شناسایی می‌شود.

اندیس:   0    1    2    3    4
مقدار: [10] [25] [30] [45] [50]

چرا دسترسی آرایه O(1) است؟

چون خانه‌ها پشت‌سرهم‌اند، کامپیوتر می‌تواند با یک محاسبه آدرس هر خانه را پیدا کند:

آدرس خانه i = آدرس شروع + (i × اندازه هر عنصر)

مثل ردیف صندلی سینما: برای صندلی شماره ۵۰ لازم نیست از صندلی ۱ تا ۴۹ بروید؛ مستقیم محاسبه می‌شود!

عملیات و پیچیدگی‌ها

درج در وسط آرایه — چرا کند است؟

برای درج در اندیس ۲، همه عناصر بعد از آن باید یک خانه به عقب بروند تا جا باز شود. در بدترین حالت (درج در ابتدا) همه n عنصر جابه‌جا می‌شوند ← O(n).

آرایه دوبعدی (ماتریس)

آرایه‌ای از آرایه‌ها — مثل جدول سطر و ستون:

matrix = [[1, 2, 3],
          [4, 5, 6],
          [7, 8, 9]]
matrix[1][2]  # سطر ۱، ستون ۲ -> 6

کاربرد: تصویر (پیکسل‌ها)، صفحه بازی شطرنج، جدول ضرب.

آرایه پویا (Dynamic Array)

آرایه خام اندازه ثابت دارد. زبان‌ها «آرایه پویا» می‌دهند (list پایتون، vector در C++):

• وقتی پر شود، آرایه بزرگ‌تر (معمولاً ۲ برابر) می‌سازد و همه را کپی می‌کند
• به همین دلیل append در پایتون به‌طور میانگین O(1) است

آرایه در پایتون

list پایتون در واقع آرایه پویای انعطاف‌پذیر است (می‌تواند انواع مختلف را هم نگه دارد). برای آرایه عددی خالص و بهینه، ماژول array یا NumPy موجود است.

الگوهای پرکاربرد آرایه

• دو اشاره‌گر: دو اندیس از دو طرف برای جستجوی جفت (مثل مسئله Two Sum در داده مرتب)
• پنجره لغزان: زیرآرایه متوالی با پیچیدگی O(n)
• پیشوند جمعی: محاسبه تجمعی برای پاسخ فوری کوئری‌ها

جمع‌بندی

• آرایه: حافظه پشت‌سرهم + دسترسی اندیسی O(1)
• درج/حذف وسط: O(n) به‌خاطر جابه‌جایی
• list پایتون = آرایه پویا با append میانگین O(1)
• برای دسترسی تصادفی بهترین؛ برای درج مکرر وسط، نه