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

Thao tác cơ bản trên mảng & độ phức tạp

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

Bảng độ phức tạp của các thao tác mảng — và quan trọng hơn, vì sao lại như vậy. Bạn sẽ "nhìn thấy" cảnh các phần tử phải dịch chỗ khi chèn vào đầu, để hiểu tận gốc con số O(n).

1. Bảng độ phức tạp các thao tác​

Thao tácĐộ phức tạpVì sao
Truy cập A[i]O(1)Tính địa chỉ trực tiếp
Cập nhật A[i] = xO(1)Ghi thẳng vào ô
Tìm kiếm (chưa sắp xếp)O(n)Phải duyệt từng phần tử
Thêm cuối (append)O(1) amortizedGhi vào ô trống cuối
Chèn ĐẦU / GIỮAO(n)Phải dịch các phần tử phía sau
Xóa ĐẦU / GIỮAO(n)Phải dịch các phần tử lấp chỗ trống
Xóa CUỐIO(1)Bỏ ô cuối, không dịch ai

Điểm cần nhớ: đầu/giữa = O(n), cuối = O(1). Lý do nằm ở tính liền kề của mảng.

2. Chạy debug: vì sao chèn ĐẦU tốn O(n)?​

Để giữ các ô liền kề, chèn vào đầu buộc mọi phần tử dịch sang phải một ô. Bước qua cảnh chèn 10 vào đầu [20, 30, 40] — đếm số lần dịch:

🐞 Chèn 10 vào đầu [20, 30, 40]Bước 1/5
1def chen_dau(A, x):
2  A.append(None)                  # them 1 cho trong o cuoi
3  for i in range(len(A) - 1, 0, -1):
4      A[i] = A[i - 1]             # dich phai
5  A[0] = x                        # dat x vao dau
6  return A
Biến tại bước này
A[20,30,40,None]
👉 Thêm chỗ trống ở cuối.

Mảng càng dài, càng nhiều phần tử phải dịch. Đó là lý do chèn đầu/giữa là O(n).

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

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

insert(0, ...) và pop(0) trông gọn một dòng, nhưng bên trong Python phải dịch cả mảng → O(n). Đừng để cú pháp ngắn đánh lừa về chi phí thật.

4. Mẹo: tránh thao tác đầu/giữa khi có thể​

  • Cần thêm/xóa liên tục ở đầu → cân nhắc deque (hàng đợi hai đầu) hoặc danh sách liên kết (học sau) — thêm/xóa đầu O(1).
  • Xây mảng kết quả → luôn append vào cuối thay vì chèn đầu rồi đảo.
  • Xóa nhiều phần tử giữa chừng → thường gom lại và tạo mảng mới một lần (O(n)) còn rẻ hơn xóa từng cái (O(n) mỗi lần → O(n²)).

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

  • Thao tác chủ yếu là đọc/ghi theo chỉ số và thêm cuối → mảng là lựa chọn tuyệt vời.
  • Thấy mình insert(0, ...) hoặc pop(0) trong vòng lặp → cảnh báo O(n²), tìm cách khác.

6. 🎮 Trò chơi: Đoán độ phức tạp thao tác mảng​

🎮 Thao tác mảng tốn bao nhiêu?Câu 1/5· Điểm 0· 🔥 0

Nhớ: theo chỉ số & cuối = O(1); tìm kiếm, đầu, giữa = O(n).

Chèn phần tử vào ĐẦU mảng.

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Vì sao chèn vào giữa mảng là O(n)?
2. Thao tác nào trên mảng là O(1)?
3. pop(0) lặp trong vòng for n lần có nguy cơ gì?

8. Hoàn thành​

…

☑️ Tiếp theo: 2.1.3 — Mảng nhiều chiều (ma trận, lưới 2D).