Trong thuật toán, điều gì được chỉ ra khi một thao tác có độ phức tạp là O(log n)?

Khi một thao tác có độ phức tạp là O(log n), điều này ám chỉ rằng thời gian thực hiện hoặc số lần lặp lại của thao tác tăng theo một cách logarit với kích thước dữ liệu đầu vào n.

Ví dụ, trong thuật toán tìm kiếm nhị phân, thời gian thực hiện của thuật toán là O(log n). Khi tìm kiếm một phần tử trong một mảng đã được sắp xếp, thao tác này so sánh phần tử tìm kiếm với phần tử ở giữa của mảng. Nếu phần tử tìm kiếm nhỏ hơn phần tử ở giữa, thuật toán sẽ tiếp tục tìm kiếm trong nửa mảng bên trái; ngược l...