📊 Mảng (Array)

Tưởng tượng bộ nhớ máy tính là một dãy ô đánh số liên tiếp. Mảng (array) là cách đơn giản nhất để tổ chức dữ liệu trên đó: đặt các phần tử nằm sát nhau, mỗi phần tử chiếm đúng một số ô cố định. Nhờ vậy, muốn biết phần tử thứ i nằm ở đâu, máy tính không cần dò tìm - chỉ cần một phép tính: địa_chỉ_phần_tử_0 + i × kích_thước_1_phần_tử. Đây là lý do arr[i] luôn là O(1), bất kể mảng có 10 hay 10 triệu phần tử.

Cái giá của việc “nằm sát nhau”

Tính liên tục trong bộ nhớ vừa là điểm mạnh, vừa là ràng buộc của mảng.

Thêm/xóa ở giữa hoặc đầu mảng tốn O(n). Vì các phần tử phải nằm liền kề tuyệt đối, chèn một phần tử vào giữa buộc phải dịch chuyển tất cả phần tử phía sau sang phải một ô để “nhường chỗ” - và xóa thì ngược lại, dịch chuyển các phần tử phía sau sang trái để lấp khoảng trống.

arr = [1, 2, 5, 4]
arr.insert(2, 3)   # chèn 3 vào vị trí 2 -> phải dịch 5, 4 sang phải
# arr = [1, 2, 3, 5, 4]

Kích thước mảng “thô” (raw array) là cố định. Khi khai báo một mảng 5 phần tử, hệ thống cấp đúng một khối bộ nhớ liên tục đủ cho 5 phần tử - không hơn. Muốn mở rộng, không có cách nào khác ngoài cấp phát một khối mới lớn hơn rồi copy toàn bộ dữ liệu cũ sang, vì phần bộ nhớ ngay sau khối hiện tại có thể đã bị chương trình khác chiếm dụng.

Mảng động (dynamic array): “ảo thuật” đằng sau `list.append()`

Trong thực tế, bạn hiếm khi dùng mảng kích thước cố định - hầu hết ngôn ngữ cung cấp sẵn mảng động (Python list, Java/Kotlin ArrayList, Dart List, Swift Array), cho phép append thoải mái mà “quên” luôn giới hạn kích thước.

Bí quyết: bên dưới, mảng động vẫn là một mảng thô bình thường, nhưng luôn cấp phát dư ra một vùng nhớ dự phòng (gọi là capacity, lớn hơn số phần tử đang dùng thực sự - length). Khi append mà vùng dự phòng đã đầy, nó sẽ tự động:

Cấp phát một mảng mới, thường gấp đôi capacity cũ.
Copy toàn bộ phần tử cũ sang mảng mới - thao tác này tốn O(n).
Giải phóng mảng cũ, tiếp tục append vào mảng mới.

arr = []
for i in range(10):
    arr.append(i)   # gần như luôn O(1), thỉnh thoảng có 1 lần "nhảy vọt" tốn O(n)

Vì capacity tăng gấp đôi mỗi lần cần mở rộng, số lần phải copy toàn bộ mảng giảm dần theo cấp số nhân - tính trung bình trên rất nhiều lần append, chi phí mỗi lần chỉ còn O(1). Đây gọi là độ phức tạp khấu hao (amortized) O(1): một vài lần gọi tốn kém được “rải đều” ra cho tất cả các lần gọi trước đó.

Vì sao mảng nhanh hơn linked list trên phần cứng thật?

Về mặt lý thuyết, duyệt một mảng và duyệt một linked list đều là O(n). Nhưng trên thực tế, duyệt mảng luôn nhanh hơn đáng kể - vì Big O chỉ đếm số bước tính toán, không đo tốc độ phần cứng thực thi từng bước.

CPU không đọc RAM từng byte một lần - mỗi lần cần dữ liệu, nó nạp cả một khối nhớ liền kề vào cache (bộ nhớ đệm siêu nhanh ngay trên chip CPU), dựa trên giả định rằng chương trình có xu hướng dùng dữ liệu “gần” dữ liệu vừa dùng - gọi là tính cục bộ không gian (spatial locality).

Với mảng: các phần tử nằm liền kề, nên đọc arr[i] xong, CPU đã tiện thể nạp sẵn arr[i+1], arr[i+2]… vào cache. Lần truy cập kế tiếp gần như miễn phí.
Với linked list: các node nằm rải rác khắp bộ nhớ. Đọc xong node hiện tại không giúp ích gì cho việc đọc node tiếp theo - CPU phải “đi ra RAM” lại từ đầu mỗi lần, chậm hơn cache hàng chục đến hàng trăm lần.

Hai kỹ thuật quen thuộc trên mảng

Two pointers - dùng hai chỉ số duyệt mảng từ hai phía, thu hẹp dần khoảng cách, thường giúp giảm độ phức tạp từ O(n²) xuống O(n):

def reverse_array(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

Sliding window - duy trì một “cửa sổ” kích thước cố định (hoặc thay đổi) trượt qua mảng, cập nhật kết quả tăng dần thay vì tính lại từ đầu mỗi lần:

def max_sum_subarray(arr, k):
    """Tổng lớn nhất của k phần tử liên tiếp"""
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]   # thêm phần tử mới, bỏ phần tử cũ
        max_sum = max(max_sum, window_sum)
    return max_sum

Không có kỹ thuật này, tính tổng mọi cửa sổ kích thước k một cách brute-force sẽ tốn O(n × k); sliding window đưa nó về O(n) bằng cách tái sử dụng kết quả của cửa sổ trước.

Tóm tắt

Thao tác	Độ phức tạp	Vì sao
Truy cập `arr[i]`	O(1)	Tính trực tiếp từ địa chỉ + offset
`append` cuối mảng động	O(1) khấu hao	Đa số lần không cần resize
Chèn/xóa đầu hoặc giữa	O(n)	Phải dịch chuyển các phần tử phía sau
Tìm kiếm giá trị	O(n)	Không có thứ tự nào để khai thác (nếu chưa sắp xếp)