Mảng DSA
Mảng
Mảng là một cấu trúc dữ liệu dùng để lưu trữ nhiều phần tử.
Mảng được sử dụng bởi nhiều thuật toán.
Ví dụ: một thuật toán có thể được sử dụng để xem qua một mảng để tìm giá trị thấp nhất, như hình ảnh động bên dưới hiển thị:
Tốc độ:
{{ msgDone }}Giá trị thấp nhất: {{ minVal }}
Trong Python, một mảng có thể được tạo như thế này:
my_array = [7, 12, 9, 4, 11]Lưu ý: Mã Python ở trên thực sự tạo ra kiểu dữ liệu 'danh sách' Python, nhưng trong phạm vi của hướng dẫn này, kiểu dữ liệu 'danh sách' có thể được sử dụng giống như một mảng. Tìm hiểu thêm về danh sách Python tại đây .
Mảng được lập chỉ mục, nghĩa là mỗi phần tử trong mảng có một chỉ mục, một con số cho biết phần tử đó nằm ở đâu trong mảng. Các ngôn ngữ lập trình trong hướng dẫn này (Python, Java và C) sử dụng tính năng lập chỉ mục dựa trên số 0 cho mảng, nghĩa là phần tử đầu tiên trong mảng có thể được truy cập ở chỉ mục 0.
Trong Python, mã này sử dụng chỉ mục 0 để ghi phần tử mảng đầu tiên (giá trị 7) vào bảng điều khiển:
Thuật toán: Tìm giá trị nhỏ nhất trong mảng
Hãy tạo thuật toán đầu tiên bằng cấu trúc dữ liệu mảng.
Dưới đây là thuật toán tìm số nhỏ nhất trong mảng.
Làm thế nào nó hoạt động:
- Lần lượt duyệt qua các giá trị trong mảng.
- Kiểm tra xem giá trị hiện tại có phải là thấp nhất cho đến nay hay không và nếu có, hãy lưu trữ nó.
- Sau khi xem xét tất cả các giá trị, giá trị được lưu trữ sẽ là giá trị thấp nhất trong tất cả các giá trị trong mảng.
Hãy thử mô phỏng bên dưới để xem thuật toán tìm giá trị thấp nhất hoạt động như thế nào (hình động giống với hình động ở đầu trang này):
Tốc độ:
{{ msgDone }}Giá trị thấp nhất: {{ minVal }}
Mô phỏng tiếp theo này cũng tìm thấy giá trị thấp nhất trong một mảng, giống như mô phỏng ở trên, nhưng ở đây chúng ta có thể thấy cách kiểm tra các số bên trong mảng để tìm giá trị thấp nhất:
Thực hiện
Trước khi triển khai thuật toán bằng ngôn ngữ lập trình thực tế, trước tiên bạn nên viết thuật toán theo quy trình từng bước.
Nếu bạn có thể viết thuật toán bằng thứ gì đó giữa ngôn ngữ của con người và ngôn ngữ lập trình, thì thuật toán sẽ dễ thực hiện hơn sau này vì chúng ta tránh bị chìm đắm trong tất cả các chi tiết của cú pháp ngôn ngữ lập trình.
- Tạo một biến 'minVal' và đặt nó bằng giá trị đầu tiên của mảng.
- Đi qua mọi phần tử trong mảng.
- Nếu phần tử hiện tại có giá trị thấp hơn 'minVal', hãy cập nhật 'minVal' thành giá trị này.
- Sau khi xem xét tất cả các phần tử trong mảng, biến 'minVal' hiện chứa giá trị thấp nhất.
Bạn cũng có thể viết thuật toán theo cách giống ngôn ngữ lập trình hơn nếu muốn, như sau:
Variable 'minVal' = array[0]
For each element in the array
If current element < minVal
minVal = current element
Lưu ý: Hai mô tả từng bước của thuật toán mà chúng tôi đã viết ở trên có thể được gọi là 'mã giả'. Mã giả là mô tả về chức năng của một chương trình, sử dụng ngôn ngữ nằm giữa ngôn ngữ của con người và ngôn ngữ lập trình.
Sau khi chúng ta viết ra thuật toán, việc triển khai thuật toán bằng một ngôn ngữ lập trình cụ thể sẽ dễ dàng hơn nhiều:
Ví dụ
Trăn:
my_array = [7, 12, 9, 4, 11]
minVal = my_array[0] # Step 1
for i in my_array: # Step 2
if i < minVal: # Step 3
minVal = i
print('Lowest value: ',minVal) # Step 4 Chạy ví dụ »Độ phức tạp thời gian của thuật toán
Khi khám phá các thuật toán, chúng ta thường xem xét thời gian chạy của một thuật toán so với kích thước của tập dữ liệu.
Trong ví dụ trên, thời gian thuật toán cần chạy tỷ lệ thuận hoặc tuyến tính với kích thước của tập dữ liệu. Điều này là do thuật toán phải truy cập từng phần tử mảng một lần để tìm giá trị thấp nhất. Vòng lặp phải chạy 5 lần vì có 5 giá trị trong mảng. Và nếu mảng có 1000 giá trị thì vòng lặp sẽ phải chạy 1000 lần.
Hãy thử mô phỏng bên dưới để thấy mối quan hệ này giữa số lượng thao tác so sánh cần thiết để tìm giá trị thấp nhất và kích thước của mảng.
Xem trang này để được giải thích kỹ lưỡng hơn về độ phức tạp của thời gian.
Mỗi thuật toán trong hướng dẫn này sẽ được trình bày cùng với độ phức tạp về thời gian của nó.
{{ this.userX }}
Hoạt động: {{ hoạt động }}
