Độ phức tạp thời gian của tìm kiếm nhị phân

Câu hỏi

Trong trường hợp xấu nhất, tìm kiếm nhị phân trên mảng đã sắp xếp gồm n phần tử có độ phức tạp thời gian là bao nhiêu?

1. A. O(1)
2. B. O(n)
3. C. O(log n)
4. D. O(n log n)

Đáp án

C. O(log n)

Giải thích

Mỗi bước, tìm kiếm nhị phân so sánh giá trị cần tìm với phần tử ở giữa rồi bỏ đi nửa mảng chắc chắn không chứa nó. Số phần tử còn phải xét giảm một nửa sau mỗi bước, nên cần khoảng log₂ n bước; với một triệu phần tử chỉ cần khoảng 20 lần so sánh. O(n) là độ phức tạp của tìm kiếm tuần tự. O(1) là truy cập trực tiếp một phần tử theo chỉ số. O(n log n) là độ phức tạp của các thuật toán sắp xếp tốt như sắp xếp trộn.

Chủ đề: Công nghệ phần mềm và lập trình · Mức độ: Vận dụng