1. Bản chất Toán học & Tổ chức Bộ nhớ RAM

Mảng (Array / Static Array):

Về mặt vật lý, mảng là một khối các ô nhớ liên tiếp nhau (Contiguous Memory Block) trên RAM. Mỗi ô nhớ có kích thước cố định và lưu trữ một phần tử cùng kiểu dữ liệu.

Chỉ số (Index):       0       1       2       3       4
Địa chỉ RAM:       [1000]  [1004]  [1008]  [1012]  [1016]
Giá trị:           |  12  |  45  |  78  |  23  |  90  |

• Công thức tính địa chỉ ô nhớ: Để truy cập phần tử thứ i, máy tính không cần duyệt qua các phần tử trước đó mà tính trực tiếp địa chỉ RAM:

  $$\text{Address}(i) = \text{Base Address} + i \times \text{Element Size}$$

  (Nhờ công thức đại số này, phép truy cập arr[i] đạt độ phức tạp tức thì $O(1)$).

Mảng động (Dynamic Array / Python List):

Mảng tĩnh có nhược điểm lớn: kích thước cố định lúc khai báo. Mảng động giải quyết vấn đề này bằng cơ chế Cấp phát lại bộ nhớ (Reallocation):

1. Tạo một mảng cố định ban đầu với dung lượng (Capacity) cho trước.

2. Khi mảng bị đầy (Size = Capacity), mảng động sẽ tự động tạo một mảng mới có kích thước gấp đôi ($\text{Capacity} \times 2$).

3. Sao chép toàn bộ dữ liệu từ mảng cũ sang mảng mới và giải phóng mảng cũ.

Độ phức tạp Amortized (Độ phức tạp trung bình phân bổ):

Mặc dù thao tác nhân đôi mảng tốn $O(N)$ để sao chép, nhưng thao tác này diễn ra rất thưa thớt. Khi phân bổ chi phí này cho $N$ lần chèn append(), chi phí trung bình cho mỗi lần thêm phần tử vào cuối vẫn là $O(1)$ Amortized.

2. Sơ đồ So sánh Thao tác trên Mảng

1. Truy cập arr[i]:             O(1)  --> Tính trực tiếp địa chỉ
2. Chèn/Xóa ở cuối (append):     O(1)  --> Không phải dời phần tử nào
3. Chèn/Xóa ở đầu/giữa (insert): O(N)  --> Phải dời N phần tử còn lại sang phải/trái