/codegym.vn/ - 144
toán khi đó sẽ là k.n + c, trong đó k là thời gian tính toán trong mỗi vòng lặp và c là
thời gian thực thi các bước chuẩn bị trước khi chạy vòng lặp (khởi tạo biến đếm, đặt
giá trị ban đầu). Chúng ta không thể biết trước được k do nó phụ thuộc vào độ phức
tạp của thuật toán nhận diện phần tử, còn c thì là một hằng số. Do đó mô hình tính
toán độ phức tạp ở đây chỉ có một biến số là n và hàm f(n) luôn cho kết quả là n. Ta
nói rằng độ phức tạp của thuật toán tìm kiếm tuyến tính là O(n) (đọc là: O lớn của n).
Đối với thuật toán tìm kiếm nhị phân, số vòng lặp tối đa phải thực hiện là log(n). Theo
cùng một cách phân tích như trên, độ phức tạp của thuật toán là O(log(n)) (đọc là: O-
lớn của lô-ga-rit của n).
Bậc O-lớn của thuật toán tìm kiếm tuyến tính và tìm kiếm nhị phân có thể biểu diễn
trên cùng một hệ trục tọa độ như sau:
Nhìn trên sơ đồ, chúng ta có thể thấy rằng ở một n đủ lớn, độ phức tạp của thuật toán
tìm kiếm nhị phân tăng rất chậm, trái ngược với độ phức tạp của thuật toán tìm kiếm
nhị phân thì tăng nhanh một cách ổn định.
Lưu ý: Như vậy có thể kết luận rằng thuật toán tìm kiếm nhị phân thì có hiệu suất tốt
hơn thuật toán tìm kiếm tuyến tính. Tuy nhiên lưu ý rằng, thuật toán nhị phân chỉ có
thể thực hiện được trên dữ liệu đã được sắp xếp.
6. Các lỗi thường gặp
Lỗi thường gặp #1: Chỉ số đầu tiên là 1
Ví dụ:
1.
for
(
let
i
=
1
;
i
<
array
.
length
;
i
++)
{
2.
if
(
value
===
array
[
i
])
{
3.
return
i
;
4.
}
5.
}
Đoạn mã trên bắt đầu vòng lặp từ chỉ số 1, nghĩa là từ vị trí thứ 2 trong mảng. Như
vậy, có khả năng xảy ra sai sót bởi vì chúng ta đã bỏ qua phần tử đầu tiên của mảng.
Cách khắc phục: Luôn luôn bắt đầu với chỉ số đầu tiên của mảng là 0. Đoạn mã đúng
là như sau:
