4.1 So sánh độ phức tạp thời gian của tìm kiếm tuyến tính và tìm kiếm nhị phân
Hãy cùng so sánh độ phức tạp thời gian của tìm kiếm tuyến tính và tìm kiếm nhị phân nhé.
Tìm kiếm tuyến tính:
- Độ phức tạp thời gian:
O(n), trong đónlà số lượng phần tử trong mảng hoặc danh sách. - Trường hợp tốt nhất:
O(1)— phần tử được tìm thấy ngay từ đầu. - Trường hợp trung bình:
O(n/2) = O(n)— phần tử được tìm thấy trung bình ở giữa đâu đó. - Trường hợp xấu nhất:
O(n)— phần tử được tìm thấy ở cuối hoặc không có trong danh sách.
Tìm kiếm nhị phân:
- Độ phức tạp thời gian:
O(log n), trong đónlà số lượng phần tử trong mảng hoặc danh sách. - Trường hợp tốt nhất:
O(1)— phần tử được tìm thấy ở bước đầu tiên (phần tử trung bình). - Trường hợp trung bình:
O(log n)— tìm kiếm trong mảng đã sắp xếp. - Trường hợp xấu nhất:
O(log n)— phần tử được tìm thấy ở bước cuối cùng hoặc không có trong danh sách.
Ví dụ phân tích độ phức tạp thời gian
Tìm kiếm tuyến tính:
- Mảng
[1, 3, 5, 7, 9, 11, 13], phần tử cần tìm là 7. - Kiểm tra từng phần tử cho đến khi tìm thấy 7 tại chỉ số 3.
- Cần 4 lần kiểm tra, tương ứng với
O(n).
Tìm kiếm nhị phân:
- Mảng
[1, 3, 5, 7, 9, 11, 13], phần tử cần tìm là7. - Phần tử trung bình (7) được tìm thấy ở bước đầu tiên.
- Cần 1 lần kiểm tra, tương ứng với
O(log n).
4.2 Ưu điểm và nhược điểm của từng phương pháp
Hãy xem xét ưu điểm và nhược điểm của từng loại tìm kiếm.
Tìm kiếm tuyến tính:
Ưu điểm:
- Dễ dàng triển khai: Tìm kiếm tuyến tính rất dễ thực hiện và hiểu.
- Không yêu cầu đối với dữ liệu: Tìm kiếm tuyến tính có thể áp dụng cho dữ liệu chưa được sắp xếp.
- Phù hợp với các mảng nhỏ: Tìm kiếm tuyến tính hiệu quả cho các mảng có kích thước nhỏ.
Nhược điểm:
- Hiệu quả thấp cho các mảng lớn: Độ phức tạp thời gian
O(n)làm cho nó không hiệu quả cho các mảng lớn. - Thời gian thực hiện lâu: Đối với các mảng lớn, tìm kiếm tuyến tính có thể mất nhiều thời gian, đặc biệt khi phần tử cần tìm gần cuối hoặc không có trong mảng.
Tìm kiếm nhị phân:
Ưu điểm:
- Hiệu quả cao cho các mảng lớn: Độ phức tạp thời gian
O(log n)làm cho nó rất hiệu quả cho các mảng lớn. - Thực thi nhanh: Tìm kiếm nhị phân nhanh hơn nhiều so với tìm kiếm tuyến tính khi làm việc với các mảng đã sắp xếp lớn.
Nhược điểm:
- Yêu cầu dữ liệu đã sắp xếp: Tìm kiếm nhị phân chỉ hoạt động với các mảng đã sắp xếp, điều này có thể yêu cầu thêm thời gian để sắp xếp trước.
- Phức tạp trong việc triển khai: Triển khai tìm kiếm nhị phân phức tạp hơn so với tìm kiếm tuyến tính.
4.3 Khi nào sử dụng loại tìm kiếm nào
Hãy xem xét khi nào nên sử dụng tìm kiếm tuyến tính và khi nào nên sử dụng tìm kiếm nhị phân.
Tìm kiếm tuyến tính.
Sử dụng tìm kiếm tuyến tính khi:
- Mảng hoặc danh sách chưa được sắp xếp.
- Kích thước của mảng hoặc danh sách nhỏ.
- Cần sự đơn giản và giải pháp nhanh chóng mà không cần chi phí thêm cho việc sắp xếp.
- Cần tìm sự xuất hiện đầu tiên hoặc tất cả các lần xuất hiện của phần tử.
- Dữ liệu đến theo thời gian thực, và việc sắp xếp trước không khả thi hoặc không hợp lý.
Tìm kiếm nhị phân.
Sử dụng tìm kiếm nhị phân nếu:
- Mảng hoặc danh sách đã được sắp xếp.
- Kích thước của mảng hoặc danh sách lớn.
- Tìm kiếm phần tử thường xuyên trong cùng một tập dữ liệu (có thể sắp xếp dữ liệu một lần trước).
- Tốc độ tìm kiếm quan trọng.
- Có thể chấp nhận được việc mất thời gian để sắp xếp dữ liệu trước.
4.4 Ví dụ về bài toán cho tìm kiếm tuyến tính
1. Tìm kiếm trong một danh sách chưa được sắp xếp
Cần tìm chỉ số của một số nhất định trong danh sách số chưa được sắp xếp.
Ví dụ:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target)) # Kết quả: 2
2. Tìm kiếm sự xuất hiện đầu tiên trong mảng
Cần tìm sự xuất hiện đầu tiên của phần tử nhất định trong danh sách chuỗi.
Ví dụ:
def linear_search(arr, target):
for index, element in enumerate(arr):
if element == target:
return index
return -1
words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target)) # Kết quả: 1
3. Tìm kiếm trong dữ liệu thời gian thực
Tìm một phần tử trong dòng dữ liệu đến theo thời gian thực.
Ví dụ:
import random
def find_in_stream(stream, target):
for index, element in enumerate(stream):
if element == target:
return index
return -1
stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))
4.5 Ví dụ về bài toán cho tìm kiếm nhị phân
1. Tìm kiếm trong một mảng đã sắp xếp
Cần tìm chỉ số của một số nhất định trong mảng số đã được sắp xếp.
Ví dụ:
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target)) # Kết quả: 3
2. Tìm kiếm thường xuyên trong tập dữ liệu lớn
Thường xuyên tìm kiếm phần tử trong một mảng số đã sắp xếp lớn.
Ví dụ:
import random
sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))
3. Tìm kiếm phần tử trong cơ sở dữ liệu đã sắp xếp
Tìm bản ghi trong một cơ sở dữ liệu đã sắp xếp theo trường khóa.
Ví dụ:
database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
left, right = 0, len(db) - 1
while left <= right:
mid = (left + right) // 2
if db[mid]["id"] == target_id:
return db[mid]
elif db[mid]["id"] < target_id:
left = mid + 1
else:
right = mid - 1
return None
target_id = 54321
print(binary_search_db(database, target_id))
GO TO FULL VERSION