NỘI DUNG
Thuật toán tìm kiếm là một quy trình hệ thống được thiết kế để tìm kiếm thông tin trong một tập hợp dữ liệu. Có nhiều loại thuật toán tìm kiếm khác nhau, nhưng chúng đều có mục đích chung là tìm kiếm thông tin trong một tập hợp dữ liệu và trả về kết quả tìm kiếm.
Thuật toán tìm kiếm tuyến tính
Mô tả thuật toán
Thuật toán tìm kiếm tuyến tính là một phương pháp đơn giản để tìm kiếm một phần tử cụ thể trong một danh sách. Thuật toán này hoạt động bằng cách duyệt qua từng phần tử của danh sách cho đến khi phần tử cần tìm được tìm thấy hoặc danh sách đã được duyệt qua mà không tìm thấy phần tử cần tìm.
Các bước thực hiện thuật toán tìm kiếm tuyến tính như sau:
- Đưa ra danh sách cần tìm kiếm.
- Nhập giá trị phần tử cần tìm kiếm.
- Duyệt qua từng phần tử của danh sách.
- So sánh giá trị của phần tử đang xét với giá trị cần tìm kiếm.
- Nếu giá trị phần tử bằng giá trị cần tìm kiếm, trả về vị trí của phần tử trong danh sách.
- Nếu đã duyệt qua toàn bộ danh sách mà không tìm thấy phần tử cần tìm kiếm, trả về giá trị không tìm thấy.
Ví dụ thuật toán
Ví dụ, giả sử ta có danh sách các số nguyên: 2, 5, 8, 9, 11 và muốn tìm kiếm số 9. Các bước để thực hiện thuật toán tìm kiếm tuyến tính như sau:
- Đưa ra danh sách: 2, 5, 8, 9, 11.
- Giá trị cần tìm kiếm là 9.
- Duyệt qua từng phần tử của danh sách: 2, 5, 8, 9.
- So sánh giá trị của phần tử đang xét với giá trị cần tìm kiếm: 2, 5, 8, 9.
- Tìm thấy giá trị cần tìm kiếm tại vị trí thứ 4 trong danh sách.
- Trả về vị trí của phần tử tìm thấy.
Độ phức tạp của thuật toán
Thuật toán tìm kiếm tuyến tính có độ phức tạp thời gian là O(n), nghĩa là thời gian tìm kiếm tăng theo số lượng phần tử trong danh sách. Thuật toán này là một phương pháp đơn giản và dễ hiểu, tuy nhiên độ phức tạp của nó có thể rất lớn đối với các danh sách lớn.
Cài đặt thuật toán với Python
def linear_search(arr, x):
# Duyệt qua từng phần tử của danh sách arr
for i in range(len(arr)):
# So sánh phần tử đang xét với giá trị cần tìm kiếm x
if arr[i] == x:
# Trả về vị trí của phần tử tìm thấy
return i
# Nếu đã duyệt qua toàn bộ danh sách mà không tìm thấy giá trị cần tìm kiếm, trả về giá trị không tìm thấy (-1)
return -1
Trong ví dụ trên, hàm linear_search được định nghĩa để tìm kiếm phần tử x trong danh sách arr. Hàm này sử dụng vòng lặp for để duyệt qua từng phần tử của danh sách và so sánh giá trị của phần tử đang xét với giá trị x. Nếu giá trị phần tử bằng giá trị x, hàm sẽ trả về vị trí của phần tử trong danh sách. Nếu đã duyệt qua toàn bộ danh sách mà không tìm thấy giá trị cần tìm kiếm, hàm sẽ trả về giá trị -1 để chỉ ra rằng không tìm thấy.
Sau đây là một ví dụ về cách gọi hàm linear_search để tìm kiếm giá trị 9 trong danh sách arr:
arr = [2, 5, 8, 9, 11]
x = 9
result = linear_search(arr, x)
if result == -1:
print("Không tìm thấy giá trị", x)
else:
print("Giá trị", x, "được tìm thấy tại vị trí", result)
Thuật toán tìm kiếm nhị phân
Mô tả thuật toán
Thuật toán tìm kiếm nhị phân là một phương pháp tìm kiếm hiệu quả trong các danh sách được sắp xếp. Thay vì duyệt qua từng phần tử của danh sách, thuật toán tìm kiếm nhị phân chia danh sách thành các nửa và chỉ tìm kiếm trong nửa phù hợp với giá trị cần tìm kiếm. Các bước thực hiện thuật toán tìm kiếm nhị phân như sau:
-
Đưa ra danh sách cần tìm kiếm và giá trị cần tìm kiếm.
-
Xác định phần tử giữa của danh sách.
-
So sánh giá trị cần tìm kiếm với phần tử giữa của danh sách.
-
Nếu giá trị cần tìm kiếm bằng phần tử giữa của danh sách, trả về vị trí của phần tử trong danh sách.
-
Nếu giá trị cần tìm kiếm nhỏ hơn phần tử giữa của danh sách, thực hiện thuật toán tìm kiếm nhị phân trên nửa đầu tiên của danh sách.
-
Nếu giá trị cần tìm kiếm lớn hơn phần tử giữa của danh sách, thực hiện thuật toán tìm kiếm nhị phân trên nửa thứ hai của danh sách.
-
Lặp lại các bước 2 đến 6 cho đến khi tìm thấy phần tử cần tìm kiếm hoặc không còn phần tử nào để tìm kiếm.
Ví dụ thuật toán
Ví dụ, giả sử ta có danh sách các số nguyên đã được sắp xếp tăng dần: 2, 5, 8, 9, 11 và muốn tìm kiếm số 9. Các bước để thực hiện thuật toán tìm kiếm nhị phân như sau:
- Đưa ra danh sách đã sắp xếp tăng dần: 2, 5, 8, 9, 11.
- Giá trị cần tìm kiếm là 9.
- Thiết lập chỉ số đầu tiên là 0 và chỉ số cuối cùng là 4.
- Tính toán chỉ số của phần tử giữa bằng cách lấy trung bình của chỉ số đầu tiên và chỉ số cuối cùng: (0 + 4) / 2 = 2.
- So sánh giá trị của phần tử giữa (8) với giá trị cần tìm kiếm (9).
- Vì giá trị của phần tử giữa nhỏ hơn giá trị cần tìm kiếm, ta cập nhật chỉ số đầu tiên bằng giá trị phần tử giữa cộng thêm 1, và quay trở lại bước 4.
- Tính toán lại chỉ số của phần tử giữa bằng cách lấy trung bình của chỉ số đầu tiên và chỉ số cuối cùng: (3 + 4) / 2 = 3.
- So sánh giá trị của phần tử giữa (9) với giá trị cần tìm kiếm (9).
- Vì giá trị của phần tử giữa bằng giá trị cần tìm kiếm, ta đã tìm thấy phần tử cần tìm kiếm tại vị trí thứ 3 trong danh sách.
- Trả về vị trí của phần tử tìm thấy.
Độ phức tạp của thuật toán
Do danh sách đã được sắp xếp trước khi thực hiện thuật toán tìm kiếm nhị phân, nên độ phức tạp của thuật toán là O(log n), nghĩa là thời gian tìm kiếm sẽ giảm theo số lượng phần tử trong danh sách. Tuy nhiên, nếu danh sách chưa được sắp xếp thì trước tiên cần phải sắp xếp danh sách và độ phức tạp của thuật toán sẽ tăng lên thành O(n log n) do phải sắp xếp trước khi thực hiện tìm kiếm nhị phân. Mặc dù vậy, thuật toán tìm kiếm nhị phân vẫn tối ưu hơn thuật toán tìm kiếm tuyến tính. Đây là một thuật toán hay được áp dụng để giải quyết các bài toán đòi hỏi về tốc độ tính toán.
Cài đặt Thuật toán với Python
Dưới đây là một ví dụ về cách triển khai thuật toán tìm kiếm nhị phân bằng ngôn ngữ Python:
def binary_search(arr, x):
# Thiết lập các chỉ mục ban đầu
low = 0
high = len(arr) - 1
mid = 0
# Duyệt qua mảng để tìm kiếm phần tử x
while low <= high:
mid = (high + low) // 2
# Kiểm tra xem phần tử có ở giữa không
if arr[mid] < x:
low = mid + 1
# Kiểm tra xem phần tử có ở giữa không
elif arr[mid] > x:
high = mid - 1
# Nếu phần tử được tìm thấy ở giữa thì trả về vị trí đó
else:
return mid
# Nếu không tìm thấy phần tử trong mảng, trả về -1
return -1
# Sử dụng để kiểm tra thuật toán
arr = [2, 3, 4, 10, 40]
x = 10
# Hàm gọi tìm kiếm nhị phân
result = binary_search(arr, x)
if result != -1:
print("Phần tử được tìm thấy tại vị trí", str(result))
else:
print("Phần tử không được tìm thấy trong mảng")
Hàm tìm kiếm bisect và insort trong Python
Trong Python, hàm tìm kiếm nhị phân có sẵn được gọi là bisect. Hàm này cho phép tìm kiếm một giá trị trong một danh sách đã được sắp xếp theo thứ tự tăng dần và trả về vị trí của giá trị đó trong danh sách.
Cú pháp của hàm bisect là:
bisect(list, value, lo=0, hi=len(list))
Trong đó:
list: là danh sách cần tìm kiếm giá trị, đã được sắp xếp theo thứ tự tăng dần.value: là giá trị cần tìm kiếm trong danh sách.lo(tùy chọn): là chỉ số bắt đầu tìm kiếm trong danh sách. Mặc định là 0.hi(tùy chọn): là chỉ số kết thúc tìm kiếm trong danh sách. Mặc định là độ dài của danh sách.
Hàm bisect sẽ trả về vị trí đầu tiên trong danh sách mà giá trị cần tìm kiếm có thể được chèn vào mà vẫn giữ được thứ tự tăng dần của danh sách.
Ngoài ra, Python còn có hàm insort để chèn một giá trị vào danh sách đã được sắp xếp theo thứ tự tăng dần và vẫn giữ được thứ tự tăng dần của danh sách. Hàm insort sử dụng bisect để xác định vị trí để chèn giá trị vào danh sách.
Cú pháp của hàm insort là:
insort(list, value, lo=0, hi=len(list))
Trong đó, các tham số có ý nghĩa tương tự như trong hàm bisect.
Dưới đây là một số ví dụ về cách sử dụng hàm bisect và insort trong Python:
ví dụ về cách sử dụng hàm bisect
from bisect import bisect
my_list = [1, 3, 4, 5, 7, 8, 10]
position = bisect(my_list, 6)
print(position) # Kết quả là 4, giá trị 6 có thể chèn vào danh sách ở vị trí thứ 4 để vẫn giữ thứ tự tăng dần của danh sách
position = bisect(my_list, 0)
print(position) # Kết quả là 0, giá trị 0 có thể chèn vào danh sách ở vị trí đầu tiên để vẫn giữ thứ tự tăng dần của danh sách
ví dụ về cách sử dụng hàm insort
from bisect import insort
my_list = [1, 3, 4, 5, 7, 8, 10]
insort(my_list, 6)
print(my_list) # Kết quả là [1, 3, 4, 5, 6, 7, 8, 10], giá trị 6 đã được chèn vào danh sách và vẫn giữ thứ tự tăng dần của danh sách
insort(my_list, 0)
print(my_list) # Kết quả là [0, 1, 3, 4, 5, 6, 7, 8, 10], giá trị 0 đã được chèn vào danh sách và vẫn giữ thứ tự tăng dần của danh sách
Chú ý rằng hàm insort sẽ thay đổi danh sách ban đầu, không trả về một danh sách mới.
Đánh giá độ phức tạp của các thuật toán
Thuật toán tìm kiếm nhị phân và hàm tìm kiếm bisect có chung một đặc điểm là đều áp dụng cho danh sách đã được sắp xếp theo thứ tự tăng dần. Tuy nhiên, độ phức tạp của chúng khác nhau.
- Thuật toán tìm kiếm nhị phân: Độ phức tạp trung bình của thuật toán tìm kiếm nhị phân là O(log n), trong đó n là số phần tử trong danh sách. Đây là một độ phức tạp rất hiệu quả, vì nếu danh sách có kích thước lớn, thì số lần so sánh cần thiết để tìm kiếm một phần tử sẽ rất ít so với việc duyệt tuyến tính qua tất cả các phần tử trong danh sách.
- Hàm
bisect: Độ phức tạp của hàmbisectlà O(log n), tương tự như thuật toán tìm kiếm nhị phân, vì nó sử dụng cùng một thuật toán để tìm kiếm vị trí cần chèn giá trị vào danh sách đã sắp xếp. - Hàm
insort: Độ phức tạp của hàminsortlà O(n), trong đó n là số phần tử trong danh sách. Điều này là do khi chèn một giá trị mới vào danh sách, các phần tử phía sau giá trị đó phải được di chuyển sang phía sau một vị trí để tạo khoảng trống cho giá trị mới. Do đó, độ phức tạp của hàminsortsẽ tăng lên tương ứng với số phần tử cần phải di chuyển trong danh sách.
Tóm lại, thuật toán tìm kiếm nhị phân và hàm bisect đều có độ phức tạp hiệu quả O(log n), trong khi độ phức tạp của hàm insort là O(n). Do đó, khi cần tìm kiếm một phần tử trong một danh sách đã được sắp xếp, nên sử dụng thuật toán tìm kiếm nhị phân hoặc hàm bisect để đạt được hiệu quả tốt nhất. Nếu cần chèn một giá trị mới vào danh sách, hàm insort có thể được sử dụng, tuy nhiên nên cân nhắc đến độ phức tạp của nó.