Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.
Đề bài
Hãy chỉ ra tính dừng của thuật toán tìm kiếm tuần tự.
Lời giải chi tiết
- Thuật toán tìm kiếm tuần tự:
Bước 1. Nhập N, các số hạng a,...a2,...aN và khoá k
Bước 2. i
Bước 3. Nếu ai= k thì thông báo chỉ số i, rồi kết thúc;
Bước 4. i
Bước 5. Nếu i > N thì thông báo dãy A không có số hạng nào có giá trị nào bằng k, rồi kết thúc;
Bước 6. Quay lại bước 3.
- Tính dừng của thuật toán tìm kiếm tuần tự (nghĩa là thuật toán phải kết thúc sau một số hữu hạn lần bước tính) xảy ra khi thỏa mãn một trong hai trường hợp:
+ Nếu tìm thấy giá trị cần tìm trong dãy A (ai= k) thì thông báo chỉ số i (vị trí tìm thấy khoá k trong dãy A), rồi kết thúc.
+ Nếu không tìm thấy giá trị cần tìm trong dãy A, vì bước 4 thực hiện việc tăng giá trị của i lớn hơn 1, nên sau N lần thì i > N, thông báo dãy A không có giá trị nào bằng k, rồi kết thúc.
Loigiaihay.com
Trong hầu hết các hệ quản lý dữ liệu, thao tác tìm kiếm thường được thực hiện nhất để khai thác thông tin khác nhau. Bởi vậy, khi xây dựng một hệ quản lý thông tin trên máy tính, bên cạnh các thuật toán tìm kiếm, các thuật toán sắp xếp dữ liệu cũng là một trong những chủ đề được quan tâm hàng đầu. Hãy cũng mình tìm hiểu về thuật toán tìm kiếm phổ biến nhé.
Thuật toán sắp xếp là gì?
Thuật toán sắp xếp Là bài toán giải quyết việc tổ chức dữ liệu theo một trật tự nhất định, thường là tăng dần hoặc giảm dần.
Ví dụ điển hình nhất trong thực tế như:
Các ứng dụng quản lý danh bạ ở điện thoại thì có sắp xếp theo số, theo tên. Quản lý học sinh thì có sắp xếp theo mã, điểm, theo lớp, theo trường, …
Như vậy, trong cuộc sống có rất nhiều mục đích cần phải sắp xếp các phần tử theo một trình tự nhất định. Như lúc bạn học lập trình bạn cần sắp xếp dãy số tăng dần, giảm dần bởi các kỹ thuật sắp xếp được nghiên cứu và phân tích kỹ lưỡng.
Trong ngành khoa học máy tính và toán học, thuật toán sắp xếp là một thuật toán sắp xếp các phần tử của một danh sách (hay một mảng) theo thứ tự tăng hoặc giảm tùy thuộc.
Có những thuật toán sắp sếp như:
- Sắp xếp chọn
- Sắp xếp chèn
- Sắp xếp nổi bọt
- Sắp xếp Quick sort
- Sắp xếp Help sort
- Sắp xếp Merge sort
Thuật toán tìm kiếm là gì?
Tìm kiếm là quá trình tìm một phần tử nằm trong một tập hợp rất nhiều phần tử dựa vào một yêu cầu nào đó. Ví dụ bạn cần tìm học sinh giỏi có tổng điểm cao nhất trong một danh sách học sinh của trường có 1000 học sinh thì quá trình đó ta gọi là tìm kiếm.
Nếu như một tập hợp đã được sắp xếp thì quá trình tìm kiếm trong tập hợp đó sẽ nhanh hơn.
Như ví dụ trên nếu điểm số học sinh đã được sắp xếp theo tăng dần hoặc giảm dần thì ta rất dễ tìm kiếm được học sinh đó. Còn nếu đó là một danh sách tùm lum không có thú tự thì bạn có thể sẽ mất nhiều thời gian để xử lý chúng.
Hiện nay, chúng ta thường sử dụng hai thuật toán tìm kiếm đó là
- Thuật toán tìm kiếm tuyến tính.
- Thuật toán tìm kiếm nhị phân.
Thuật toán tìm kiếm nhị phân là quá trình tìm kiếm trong một tập hợp đã được sắp xếp theo thứ tự.
Thuật toán tìm kiếm tuyến tính là quá trình tìm kiếm trong một tập hợp chưa sắp xếp.
Cả hai thuật toán đều có những ưu và nhược điểm khác nhau.
Xem thêm: Web dành cho lập trình viên
Thuật toán tìm kiếm tuyến tính
Ý tưởng
Thực hiện tìm kiếm từ đầu cho đến cuối mảng (hoặc ngược lại).
- Nếu tìm thấy trả vị trí của kết quả tìm kiếm.
- Nếu không tìm thấy thì trả về 1.
Các bước thực hiện
- Bước 1: Duyệt mảng (n phần tử) từ vị trí đầu tiên i = 0.
- Bước 2: Thực hiện so sánh giá trị arr[i] và key. Nếu arr[i] == key trả về vị trí i.
- Bước 3: Nếu như duyệt hết phần tử mảng vẫn không tìm thấy thì trả về -1.
Đánh giá
- Trong trường hợp tốt nhất, phần tử cần tìm nằm ngay ở vị trí đầu tiên, thuật toán sử dụng 1 lần so sánh.
- Trong trường hợp xấu nhất, phần tử cần tìm nằm ngay ở vị trí cuối hoặc không nằm trong mảng, thuật toán cần sử dụng n-1 lần so sánh.
- Linear Search đây là một giải thuật đơn giản khi hiện thực nó và giải thuật này khá hiệu quả với danh sách đủ nhỏ hoặc một danh sách chưa được sắp xếp.
Thuật toán tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm nhanh so với thuật toán tìm kiếm tuần tự, nhất là đối với một danh sách lớn, nhiều phần tử.
Ý tưởng
Để triển khai được thuật toán này hãy chắc chắn là mảng đã được sắp xếp. Dưới đây là ý tưởng triển khai thuật toán.
Xét đoạn mảng arr[left…right] cần phần tử tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
- Nếu phần tử arr[mid] = x. Đưa kết luận và thoát chương trình.
- Nếu arr[mid] < x. Ta chỉ thực hiện tìm kiếm trên đoạn arr[mid+1…right].
- Nếu arr[mid] > x. Ta chỉ thực hiện tìm kiếm trên đoạn arr[left…mid-1].
Khi áp dụng thuật toán tìm kiếm nhị phân. Độ phức tạp cho trường hợp xấu nhất gặp là O(log(n)).
Tại sao cần phải có thuật toán tìm kiếm?
Trong thực tế ở cuộc sống, có rất nhiều bài toán khác nhau. Nhưng hầu như tất cả những bài toán đó chúng ta đều quy về một bài toán duy nhất, đó chính là bài toán tìm kiếm.
Ví dụ đơn giản là khi bạn thực hiện giải một bài toán. Có thể bạn sẽ có nhiều cách thực hiện nó, nhưng mục đích cuối cùng của bạn chính là đi tìm lời giải của bài toán. Hay là khi bạn thực hiện một phép sắp xếp, lọc các phần tử của danh sách, mục đích chính của bạn đó là tìm kiếm những phần tử giúp thỏa mãn yêu cầu.
Dựa trên các nhu cầu thực tế, các bài toán tìm kiếm dẫn đến chúng ta cần tạo ra thuật toán tìm kiếm để giải quyết những vấn đề này.
Tùy vào cấu trúc dữ liệu mà chúng ta sẽ có những thuật toán tìm kiếm khác nhau sao cho phù hợp cho từng cấu trúc đó. Vì vậy, chúng ta không nên học thuộc lòng thuật toán tìm kiếm trên một tập dữ liệu duy nhất. Mà bạn hãy học ý tưởng của thuật toán và thực hiện áp dụng nó một cách linh hoạt cho các cấu trúc dữ liệu khác nhau ở các ngôn ngữ lập trình khác nhau. Từ đó lựa chọn được thuật toán nhanh nhất, tối ưu nhất cho mục đích của bạn.
Bài viết là những chia sẻ của mình về thuật toán tìm kiếm, cảm ơn các bạn đã quan tâm.
Tìm kiếm nhị phân so với Tìm kiếm tuyến tính
Tìm kiếm tuyến tính, còn được gọi là tìm kiếm tuần tự là thuật toán tìm kiếm đơn giản nhất. Nó tìm kiếm một giá trị được chỉ định trong danh sách bằng cách kiểm tra mọi phần tử trong danh sách. Tìm kiếm nhị phân cũng là một phương pháp được sử dụng để xác định một giá trị được chỉ định trong danh sách đã sắp xếp. Phương pháp tìm kiếm nhị phân giảm một nửa số phần tử được kiểm tra (trong mỗi lần lặp), giảm thời gian cần thiết để xác định vị trí mục đã cho trong danh sách.
Tìm kiếm tuyến tính là gì?
Tìm kiếm tuyến tính là phương pháp tìm kiếm đơn giản nhất, kiểm tra tuần tự từng phần tử trong danh sách cho đến khi tìm thấy một phần tử được chỉ định. Đầu vào cho phương pháp tìm kiếm tuyến tính là một chuỗi (chẳng hạn như mảng, tập hợp hoặc chuỗi) và mục cần tìm kiếm. Kết quả đầu ra là true nếu mục được chỉ định nằm trong chuỗi đã cho hoặc sai nếu nó không nằm trong chuỗi. Vì phương thức này sẽ kiểm tra mọi mục trong danh sách cho đến khi tìm thấy mục được chỉ định, nên trong trường hợp xấu nhất, nó sẽ đi qua tất cả các phần tử trong danh sách trước khi tìm thấy phần tử cần thiết. Độ phức tạp của tìm kiếm tuyến tính là o (n). Do đó, nó được coi là quá chậm để được sử dụng khi tìm kiếm các phần tử trong danh sách lớn. Nhưng điều này rất đơn giản và dễ thực hiện hơn.
Tìm kiếm nhị phân là gì?
Tìm kiếm nhị phân cũng là một phương pháp được sử dụng để định vị một mục cụ thể trong danh sách đã được sắp xếp. Phương pháp này bắt đầu bằng cách so sánh phần tử được tìm kiếm với các phần tử ở giữa danh sách. Nếu phép so sánh xác định rằng hai phần tử bằng nhau, phương thức sẽ dừng và trả về vị trí của phần tử. Nếu phần tử được tìm kiếm lớn hơn phần tử ở giữa, nó sẽ bắt đầu lại phương thức chỉ bằng cách sử dụng nửa dưới của danh sách đã sắp xếp. Nếu phần tử được tìm kiếm nhỏ hơn phần tử ở giữa, nó sẽ bắt đầu lại phương thức chỉ bằng cách sử dụng nửa trên của danh sách đã sắp xếp. Nếu phần tử được tìm kiếm không nằm trong danh sách, phương thức sẽ trả về một giá trị duy nhất cho biết điều đó. Do đó, phương pháp tìm kiếm nhị phân giảm một nửa số phần tử được so sánh (trong mỗi lần lặp), tùy thuộc vào kết quả của phép so sánh.Do đó, tìm kiếm nhị phân chạy theo thời gian logarit dẫn đến hiệu suất trường hợp trung bình o (log n).
Sự khác biệt giữa Tìm kiếm nhị phân và Tìm kiếm tuyến tính là gì?
Mặc dù cả tìm kiếm tuyến tính và tìm kiếm nhị phân đều là phương pháp tìm kiếm nhưng chúng có một số điểm khác biệt. Trong khi tìm kiếm nhị phân hoạt động trên danh sách được sắp xếp, tìm kiếm lót cũng có thể hoạt động trên danh sách không được sắp xếp. Sắp xếp danh sách thường có độ phức tạp trường hợp trung bình là n log n. tìm kiếm tuyến tính đơn giản và dễ thực hiện hơn so với tìm kiếm nhị phân. Tuy nhiên, tìm kiếm tuyến tính quá chậm để được sử dụng với danh sách lớn do hiệu suất trường hợp trung bình o (n) của nó. Mặt khác, tìm kiếm nhị phân được coi là một phương pháp hiệu quả hơn có thể được sử dụng với các danh sách lớn. Nhưng việc thực hiện tìm kiếm nhị phân có thể khá phức tạp và một nghiên cứu đã chỉ ra rằng mã chính xác cho tìm kiếm nhị phân chỉ có thể được tìm thấy trong 5 trong số 20 cuốn sách.