Linear search | Tìm kiếm tuyến tính

Khi lập trình, tôi chắc bạn cũng thường xuyên dùng vòng lặp để tìm giá trị trong array (mảng), nên có thể thấy đây là một thuật toán đơn giản và được sử dụng thường xuyên. Ở phần này, chúng ta sẽ tìm hiểu linear search ở góc độ của khoa học máy tính.

Hình minh họa dưới thể hiện việc tìm kiếm tuần tự của thuật tìm kiếm Tuyến tính

Bây giò, tôi thể hiện minh họa bằng đoạn code sau:

const linearSearch = (value, inputArray) => {
 for (let i = 0; i < inputArray.length; ++i) {
   if (value === inputArray[i]) {
	 return i
	}
   }
   return null
}
	

const Arr = [10, 14, 26, 27, 31, 33, 35, 42, 44]
	

	console.log(linearSearch(33, Arr))

Xem đoạn code mẫu trên, chúng ta có thể thấy công việc tìm kiếm sẽ bắt đầu từ index 0 cho đến cuối cùng, trong quá trình tìm, nếu tìm thấy giá trị, nó sẽ trả về, hoặc null nếu giá trị đó không tồn tại.

Tìm kiếm tuyến tính rất hữu ích trong hầu hết các ứng dụng, nếu bạn có một tập hợp dữ liệu không lớn lắm, không cần phải quan tâm đến tối ưu hiệu suất, thì rõ ràng lợi ích của nó là đơn giản hóa, tối ưu và dễ triển khai. Lợi ích khác là bạn có thể lưu trữ trong mảng mà không cần quan tâm đến trình tự sắp xếp của nó.

Đo lường hiệu suất

Tuy nhiên nếu xét về mặt hiệu suất, với kích cỡ input nhỏ, thì linear search không phải là vấn đề cần phải bận tâm. Nhưng điều gì sẽ xảy ra khi kích cơ nó lên tới 20,000 phần tử để tìm kiếm?

Trường hợp tốt nhất đối với linear search là 𝛺(1), trường hợp này là khi kết quả được tìm thấy ngay trong lần đầu.

Với case xấu nhất, nó phải lặp tuần tự hết tất cả các phần tử, do đó nó là O(n).

Đối với case trung bình, nó hơi phức tạp hơn, các bạn có thể tham khảo câu trả lời tại đây, tôi sẽ nói đơn giản hơn chút, một giá trị thường có xu hướng được tìm thấy ở gần nửa đầu hoặc nửa cuối của array. Thông thường, đối với một array có N phần tử, linear search sẽ thử định vị một phần tử trong khoảng N/2. Nếu một array có 20,000 phần tử, linear search sẽ so sánh với 10,000 phần tử theo từng trường hợp. Điều này giả định rằng việc phần tử tìm kiếm luôn tồn tại trong mảng. N/2 là số so sánh trung bình, và số so sánh tối đa luôn là N.

Sau đây là minh họa trên đồ thị

Do đó, theo các trường hợp, bạn cũng thấy là sự tăng trưởng của thuật toán theo chiều tuyến tính (linear) đúng như tên gọi của nó.

Các bạn cũng có thể tham khảo video