Chuyển tới nội dung chính

Mảng tĩnh vs mảng động

Bạn sẽ học được gì

Mảng (array) là cấu trúc dữ liệu cơ bản và quan trọng nhất — gần như mọi thứ khác xây trên nó. Bạn sẽ hiểu vì sao lấy phần tử thứ i của mảng là tức thì (O(1)), và khác biệt giữa mảng tĩnh với mảng động.

1. Trực quan: dãy ô tủ đánh số liền nhau​

Tưởng tượng một dãy ô tủ đặt sát nhau, đánh số 0, 1, 2, 3... Mảng chính là vậy: các phần tử nằm liền kề nhau trong bộ nhớ, mỗi ô có một chỉ số (index).

chỉ số:   0     1     2     3     4
        ┌─────┬─────┬─────┬─────┬─────┐
   A =  │ 10  │ 20  │ 30  │ 40  │ 50  │
        └─────┴─────┴─────┴─────┴─────┘
địa chỉ: 100   104   108   112   116      (mỗi ô cách nhau đều nhau)

2. Vì sao A[i] là O(1)? (chìa khoá của mảng)​

Vì các ô liền kề và đều nhau, máy tính địa chỉ ô thứ i bằng một phép tính:

địa_chỉ(A[i]) = địa_chỉ_đầu + i × (kích thước mỗi ô)

Không cần dò từ đầu — nhảy thẳng tới đúng ô. Lấy A[0] hay A[1000000] đều một bước như nhau. Đây là siêu năng lực của mảng: truy cập ngẫu nhiên tức thì.

Bước qua để thấy mọi truy cập đều là 1 bước, dù ở vị trí nào:

🐞 Truy cập theo chỉ số luôn là O(1)Bước 1/4
1A = [10, 20, 30, 40, 50]
2print(A[0])
3print(A[4])
4print(A[2])
Biến tại bước này
A[10,20,30,40,50]
👉 Mảng nằm liền kề trong bộ nhớ.

3. Mảng TĨNH vs mảng ĐỘNG​

Mảng tĩnh: kích thước cố định khi tạo. Nhanh, gọn, nhưng không thêm được quá sức chứa. Hay gặp ở C, Java (int[]).

Mảng động: tự lớn lên khi đầy. Hầu hết ngôn ngữ hiện đại dùng nó: Python list, Java ArrayList, JS Array. Thêm phần tử (append) là amortized O(1) — nhớ lại bài 1.2.6: khi đầy thì nhân đôi sức chứa, trung bình vẫn rẻ.

A = [1, 2, 3]     # mang dong trong Python
A.append(4)        # tu lon len -> [1, 2, 3, 4]

4. Code mẫu (chạy thật)​

Đang tải trình chạy code…

5. Mặt trái: thêm/xóa GIỮA mảng tốn O(n)​

Vì các ô phải liền kề, chèn/xóa ở giữa buộc phải dịch mọi phần tử phía sau → O(n). Đây là điểm yếu của mảng (ta sẽ học kỹ ở bài tiếp theo và thấy danh sách liên kết khắc phục ra sao).

6. Mẫu nhận diện​

  • Cần truy cập nhanh theo vị trí, dữ liệu ít thay đổi giữa chừng → dùng mảng.
  • Cần thêm/xóa liên tục ở giữa/đầu → mảng tốn O(n) mỗi lần, cân nhắc cấu trúc khác.
  • Đa số bài DSA bắt đầu từ mảng — nắm chắc nó trước.

7. 🎮 Trò chơi: Hiểu mảng​

🎮 Hiểu mảngCâu 1/4· Điểm 0· 🔥 0

Nhớ: liền kề trong bộ nhớ → truy cập theo chỉ số O(1); thêm/xóa giữa phải dịch → O(n).

Lấy A[1000] trong mảng 1 triệu phần tử tốn?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Đặc điểm cốt lõi giúp mảng truy cập O(1) là?
2. Khác biệt chính giữa mảng tĩnh và mảng động?
3. Thao tác nào trên mảng là O(n)?

9. Hoàn thành​

…

☑️ Tiếp theo: 2.1.2 — Thao tác cơ bản & độ phức tạp (nhìn rõ vì sao chèn đầu tốn O(n)).