Dynamic Arrays: Giải Thích, Phân Tích và Ứng Dụng¶

Dynamic arrays là một trong những cấu trúc dữ liệu phổ biến và hữu ích nhất hiện nay. Trong bài viết này, chúng ta sẽ cùng tìm hiểu kỹ về dynamic arrays, từ cách hoạt động, những ưu nhược điểm cho tới việc phân tích độ phức tạp thời gian khi thao tác với dynamic arrays. Hơn nữa, chúng ta sẽ so sánh dynamic arrays với static arrays và minh họa cách chúng hoạt động qua ví dụ trong Python.

1. Dynamic Arrays là gì?¶

Dynamic array (mảng động) là một cấu trúc dữ liệu cho phép kích thước mảng có thể thay đổi khi cần. Không giống như static arrays (mảng tĩnh) có kích thước cố định sau khi được khởi tạo, dynamic arrays có thể tự động mở rộng hoặc thu nhỏ để phù hợp với số lượng phần tử được thêm vào.

Các ngôn ngữ lập trình phổ biến đã tích hợp dynamic arrays mặc định, chẳng hạn như: - Python: Sử dụng list. - JavaScript: Array là dynamic theo mặc định. - Java: Sử dụng ArrayList. - C++: Sử dụng vector.

2. Giải Quyết Vấn Đề Kích Thước Cố Định¶

Vấn đề của mảng tĩnh là kích thước không thể thay đổi sau khi khởi tạo, dẫn đến hạn chế trong trường hợp số lượng phần tử không xác định hoặc có thể thay đổi theo thời gian. Dynamic arrays giải quyết vấn đề này bằng cách: - Khởi tạo với một kích thước mặc định (ví dụ: 3, 10, v.v.). - Khi các phần tử được thêm vào (push) vượt quá khả năng chứa, hệ thống sẽ tự động cấp phát một mảng mới có kích thước lớn hơn. - Quá trình này đi kèm với việc sao chép các giá trị từ mảng cũ sang mảng mới và giải phóng bộ nhớ của mảng cũ.

3. Cách Hoạt Động Nội Bộ của Dynamic Arrays¶

3.1. Quản Lý Kích Thước và Độ Dài¶

Capacity (Dung lượng): Số phần tử tối đa mà mảng có thể chứa trước khi cần mở rộng.
Length (Độ dài): Số lượng phần tử thực tế có trong mảng.
Một biến hoặc pointer được sử dụng để theo dõi vị trí của phần tử cuối cùng, từ đó xác định độ dài hiện tại của mảng.

3.2. Thao Tác Pushing và Popping¶

Pushing (Thêm phần tử vào cuối):
Nếu vẫn còn dung lượng, phần tử mới được thêm vào vị trí last_index + 1 và cập nhật pointer.
Nếu mảng đã đầy (length == capacity), quá trình cấp phát lại mảng sẽ xảy ra:
- Một mảng mới với kích thước gấp đôi mảng cũ được cấp phát.
- Các phần tử từ mảng cũ được sao chép sang mảng mới.
- Phần tử mới được chèn vào mảng mới.
Trong hầu hết trường hợp, thao tác push được thực hiện trong O(1). Khi phải mở rộng, thao tác mất O(n) do việc sao chép, nhưng về mặt amortized, mỗi thao tác push vẫn là O(1).
Popping (Xóa phần tử cuối):
Thao tác pop chỉ đơn giản là xóa phần tử cuối cùng và cập nhật pointer.
Thao tác này luôn thực hiện trong O(1).

4. Chiến Lược Mở Rộng: Tại sao lại Gấp Đôi Kích Thước?¶

Khi mảng đã đầy, thay vì tăng kích thước thêm một phần tử (ví dụ, capacity +1), dynamic arrays thường tăng kích thước theo tỷ lệ gấp đôi. Lý do: - Nếu tăng kích thước thêm từng đơn vị, tổng số sao chép khi thêm n phần tử liên tục sẽ là O(1 + 2 + 3 + … + n), gần như O(n²) trong trường hợp tệ. - Khi đôi kích thước, tổng số sao chép sẽ là:

S = 1 + 2 + 4 + ... + n

Đây là một chuỗi hình học có tổng được giới hạn bởi 2n, do đó, thời gian trung bình (amortized time complexity) của thao tác push vẫn là O(1).

5. Phân Tích Big O – Amortized Time Complexity¶

Đọc (Access): O(1) – Truy cập trực tiếp qua chỉ số.
Push/Pop (Không vượt quá capacity): O(1)
Push (Khi cần mở rộng): O(n) – Trong trường hợp phải cấp phát lại và sao chép, nhưng về trung bình (amortized) vẫn là O(1).
Chèn/Xoá ở giữa: O(n) – Do cần dịch chuyển các phần tử.

6. Ví Dụ Python Minh Họa Dynamic Array¶

Mặc dù Python list là một dynamic array được triển khai nội bộ, chúng ta có thể minh họa cơ chế hoạt động của dynamic array qua các thao tác cơ bản:

# Khởi tạo một danh sách trống (dynamic array)
dynamic_arr = []

# Push phần tử vào dynamic array
dynamic_arr.append(0)  # dynamic_arr: [0]
dynamic_arr.append(4)  # dynamic_arr: [0, 4]
dynamic_arr.append(7)  # dynamic_arr: [0, 4, 7]

print("Độ dài ban đầu:", len(dynamic_arr))  # Kết quả: 3

# Giả sử bây giờ chúng ta thêm phần tử thứ 4
# Nếu dung lượng hiện tại không đủ, Python sẽ tự động cấp phát bộ nhớ mới (dynamic reallocation)
dynamic_arr.append(9)
print("Sau khi thêm 9:", dynamic_arr)
print("Độ dài sau cập nhật:", len(dynamic_arr))

# Pop phần tử cuối (tương đương xóa 9)
last_item = dynamic_arr.pop()
print("Sau khi pop phần tử cuối:", dynamic_arr)

Trong ví dụ này: - Khi thêm phần tử 9 làm phần tử thứ 4, nếu mảng đã đầy thì quá trình cấp phát lại sẽ xảy ra (ví dụ: tăng dung lượng từ 3 lên 6) và sao chép các phần tử trước đó sang mảng mới. - Thao tác append thông thường được xem là O(1) về trung bình (amortized complexity) dù có thể có các lần thao tác chậm hơn (O(n)) khi phải mở rộng mảng. - Thao tác pop luôn thực hiện trong O(1).

7. Kết Luận¶

Dynamic arrays giúp giải quyết vấn đề kích thước cố định của mảng tĩnh bằng cách cho phép mảng tự động mở rộng khi cần thiết. Các thao tác cơ bản như truy xuất, thêm và xóa phần tử cuối đều hoạt động nhanh chóng với độ phức tạp O(1) về trung bình, mặc dù thao tác thêm phần tử có thể mất O(n) khi mảng cần mở rộng.

Hiểu rõ cách hoạt động của dynamic arrays giúp bạn thiết kế các thuật toán hiệu quả hơn và tối ưu hoá việc sử dụng bộ nhớ trong các ứng dụng thực tế. Hãy thường xuyên thực hành và kiểm chứng theo các ví dụ để làm chủ kỹ thuật này.

Chúc bạn thành công và tiếp tục khám phá các cấu trúc dữ liệu nâng cao hơn!