Độ phức tạp về thời gian sắp xếp lựa chọn DSA
Xem trang này để biết giải thích chung về độ phức tạp của thời gian.
Độ phức tạp thời gian tìm kiếm nhị phân
Tìm kiếm nhị phân tìm giá trị đích trong một mảng đã được sắp xếp bằng cách kiểm tra giá trị trung tâm. Nếu giá trị trung tâm không phải là giá trị đích, Tìm kiếm tuyến tính sẽ chọn mảng con bên trái hoặc bên phải và tiếp tục tìm kiếm cho đến khi tìm thấy giá trị đích.
Để tìm độ phức tạp về thời gian của Tìm kiếm nhị phân, hãy xem cần bao nhiêu thao tác so sánh để tìm giá trị đích trong một mảng có giá trị \(n\).
Trường hợp tốt nhất là nếu giá trị ở giữa đầu tiên giống với giá trị đích. Nếu điều này xảy ra, giá trị đích sẽ được tìm thấy ngay lập tức, chỉ với một lần so sánh, do đó độ phức tạp về thời gian là \(O(1)\) trong trường hợp này.
Trường hợp xấu nhất là nếu vùng tìm kiếm phải bị cắt làm đôi nhiều lần cho đến khi vùng tìm kiếm chỉ còn một giá trị. Khi điều này xảy ra, nó không ảnh hưởng đến độ phức tạp về thời gian dù giá trị đích có được tìm thấy hay không.
Hãy xem xét độ dài mảng là lũy thừa của 2, như 2, 4, 8, 16, 32 64, v.v.
Bao nhiêu lần 2 phải được cắt làm đôi cho đến khi chúng ta chỉ nhìn thấy một giá trị? Chỉ một lần thôi phải không?
Còn 8 thì sao? Chúng ta phải cắt một nửa mảng 8 giá trị 3 lần để chỉ thu được một giá trị.
Một mảng gồm 32 giá trị phải được cắt làm đôi 5 lần.
Chúng ta có thể thấy rằng \(2=2^1\), \(8=2^3\) và \(32=2^5\). Vì vậy, số lần chúng ta phải cắt một mảng để chỉ có một phần tử có thể được tìm thấy ở lũy thừa cơ số 2. Một cách khác để xem xét vấn đề này là hỏi "tôi phải nhân 2 với chính nó bao nhiêu lần để có được con số này" ?". Về mặt toán học, chúng ta có thể sử dụng logarit cơ số 2 để có thể tìm ra rằng một mảng có độ dài \(n\) có thể được chia đôi \( \log_{2}(n)\) lần.
Điều này có nghĩa là độ phức tạp về thời gian của Tìm kiếm nhị phân là
\[ \underline{\underline{O( \log_{2} n )}} \]
Kịch bản trường hợp trung bình không dễ xác định, nhưng vì chúng tôi hiểu độ phức tạp về thời gian của thuật toán là giới hạn trên của trường hợp xấu nhất, sử dụng ký hiệu Big O, nên kịch bản trường hợp trung bình không thú vị lắm.
Lưu ý: Độ phức tạp về thời gian đối với Tìm kiếm nhị phân \(O( \log_{2}n)\) nhanh hơn rất nhiều so với Tìm kiếm tuyến tính \(O(n)\), nhưng điều quan trọng cần nhớ là Tìm kiếm nhị phân yêu cầu một mảng được sắp xếp, và Tìm kiếm tuyến tính thì không.
Nếu chúng ta rút ra lượng thời gian Tìm kiếm nhị phân cần để tìm một giá trị trong một mảng các giá trị \(n\), so với Tìm kiếm tuyến tính, chúng ta sẽ có biểu đồ này:
Mô phỏng tìm kiếm nhị phân
Chạy mô phỏng cho số lượng giá trị khác nhau \(n\) trong một mảng và xem cần bao nhiêu so sánh để Tìm kiếm nhị phân để tìm giá trị đích:
{{ this.userX }}
Hoạt động: {{ hoạt động }}
Không tìm thấy!
Như bạn có thể thấy khi chạy mô phỏng Tìm kiếm nhị phân, việc tìm kiếm yêu cầu rất ít so sánh, ngay cả khi mảng lớn và không tìm thấy giá trị mà chúng ta đang tìm kiếm.
