Đôi điều về tìm kiếm. Ưu+nhược điểm của hàm băm

Với một mớ hỗn độn thì việc tìm kiếm trở nên khó khăn và rối rắm. Thế nhưng, nếu ta sắp xếp lại mớ hỗn độn này theo một trình tự hợp lí thì việc tìm kiếm lại trở nên đơn giản hơn nhiều.

Mỗi cách tiếp cận (cái nhìn về dữ liệu) khác nhau sẽ cho ta các phương pháp thú vị khác nhau.

Bài toán: Cho một dãy số. Hỏi có hay không phần tử có giá trị bằng k cho trước.

Chúng ta xét 4 trường hợp sau:

Trường hợp 1. Với mớ hỗn độn, chưa được sắp xếp => Tìm kiếm tuần tự => Độ phức tạp: O(n). Chú ý: Việc thêm vào một phần tử mất O(1)

Trường hợp 2. Nếu mớ hỗn độn này không phải là hỗn độn mà được sắp xếp theo thứ tự tăng dần => Tìm kiếm nhị phân. Độ phức tạp: O(logn). Chú ý: Việc thêm vào một phần tử mất O(n)

Một câu hỏi khá thú vị là: Nếu như mớ hỗn độn này không được sắp xếp tăng dần mà ta vẫn muốn sử dụng tìm kiếm nhị phân để tận dụng O(logn) thì sao?

Trả lời:
– Việc sắp xếp lại (sử dụng QuickSort) mất: O(nlogn)
– Việc tìm kiếm mất O(logn)
=> Tổng độ phức tạp O(max(nlogn, logn)) = O(nlogn) > O(n)

Điều đó có nghĩa là trong trường hợp này còn tệ hơn cả tìm kiếm tuần tự :v

Trường hợp 3. Sử dụng cây nhị phân tìm kiếm => Độ phức tạp cho việc tìm kiếm: O(logn)
Nhược điểm: Việc thêm vào một phần tử mất độ phức tạp O(logn)

Trường hợp 4. Sử dụng bảng băm. Độ phức tạp cho việc tìm kiếm: O(1)

Kỹ thuật sử dụng bảng băm liên quan đến hàm băm. Nếu hàm băm được xây dựng tốt để hiện tượng đụng độ xảy ra là ít nhất. Ta giả sử ta tìm một hàm băm để không có hiện tượng đụng độ xảy ra (trường hợp lí tưởng).

Ưu điểm: Việc thêm vào một phần tử mất độ phức tạp: O(1), việc tìm kiếm một phần tử mất độ phức tạp: O(1)
Nhược điểm của hàm băm: Nếu số lượng phần tử của mảng là n = 2. Khi sử dụng bảng băm, đôi khi ta phải khai báo mảng với kích thước MAXN = 10000. Lãng phí !

Kết luận:
– Muốn nhanh thì phải chấp nhận tốn nhiều bộ nhớ hoặc sử dụng kỹ thuật Toán học tinh vi, phức tạp.
– Muốn tốn ít bộ nhớ thì phải chấp nhận chạy chậm.

“Hà Nội không vội được đâu”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: