Hàm sau đây trong Python thực hiện một thuật toán tìm

Hàm sau đây trong Python thực hiện một thuật toán tìm kiếm:

1	${\rm{defSearch}}\left( {A,K} \right):$
2	$n = {\rm{len}}\left( A \right)$
3	for i in range $\left( {n - 1} \right):$
4	for j in range $\left( {i + 1,n} \right):$
5	if $A\left[ i \right] + A\left[ j \right] = = K:$
6	return True
7	return False

1. Thuật toán liệt kê các bộ dữ liệu có tổng bằng $K$ trong mảng $A$.

2. Với bộ dữ liệu $A = \left[ {2,5,7,9,11,15} \right]$ và $K = 13$ thuật toán trả lại kết quả là True.

3. Thuật toán trên có độ phức tạp là ${\rm{O}}\left( {{n^2}} \right)$.

4. Nếu các dữ liệu trong $A$ đã được sắp xếp, có thể thiết kế thuật toán để giải quyết bài toán với độ phức tạp ${\rm{O}}($ nlogn).

Đáp án đúng: 1S, 2Đ, 3Đ, 4Đ

Xem lời giải

Lời giải chi tiết

Giải thích nội dung các mệnh đề và chỉ ra các mệnh đề đúng hoặc sai như sau:

Thuật toán liệt kê các bộ dữ liệu có tổng bằng K trong mảng A.
Mệnh đề này sai vì hàm chỉ trả về True nếu tồn tại ít nhất một bộ dữ liệu (cặp số) có tổng bằng K mà không liệt kê tất cả các bộ dữ liệu như mô tả. Hàm khi gặp cặp số đầu tiên thỏa mãn điều kiện sẽ trả về kết quả ngay lập tức và không tiếp tục kiểm tra các cặp số khác.
Với bộ dữ liệu A = [2,5,7,9,11,15] và K = 13 thuật toán trả lại kết quả là True.
Ta kiểm tra các cặp số trong mảng A:
- A[0] + A[2] = 2 + 11 = 13
- Cặp này thỏa mãn điều kiện A[i] + A[j] == K
Do đó, mệnh đề này đúng.
Thuật toán trên có độ phức tạp là O(n²).
Sau khi duyệt hết các chỉ số i thì chỉ số j duyệt khoảng n-i-1 lần. Do đó, số lần kiểm tra tối đa là C(n,2) và độ phức tạp thực tế là O(n²), mệnh đề này đúng.
Nếu các dữ liệu trong A đã được sắp xếp, có thể thiết kế thuật toán để giải quyết bài toán với độ phức tạp O(nlogn).
Phát biểu này không chính xác hoàn toàn. Mặc dù chúng ta có thể cải tiến thuật toán dùng hai con trỏ để giảm độ phức tạp xuống O(n) do đã sắp xếp mảng, nhưng việc nói giảm về O(nlogn) là không cụ thể cho tình huống này.

Chú ý khi giải

Chú ý hiểu rõ thuật toán đang chỉ dừng lại với kết quả True ngay khi tìm thấy cặp giá trị đầu tiên thỏa mãn điều kiện. Để tìm tất cả, cần duyệt hết mà không dừng ngay.
Đảm bảo giải thuật tối ưu dựa vào điều kiện mảng đã sắp xếp, có thể sử dụng phương pháp hai con trỏ để giảm độ phức tạp.
Phân biệt rõ khi nào độ phức tạp là O(n^2), O(nlogn), hay O(n). Khi nào cần sắp xếp, khi nào có thể tối ưu nhờ cấu trúc mảng.

Đang Quan Tâm