5 thuật toán mọi lập trình viên cần biết

12/03/2021by Hợp Long0
1-1-e1615533537135.jpg

Hôm nay, HopLongTech sẽ giới thiệu về năm thuật toán tìm kiếm cùng với việc triển khai chúng trong C ++ và Java.

– Thuật toán Linear Search
– Thuật toán Binary Search
– Thuật toán Ternary Search
– Thuật toán Jump Search
– Thuật toán Exponential Search

1. Thuật toán Linear Search


Đây là thuật toán đơn giản nhất trong tất cả các thuật toán tìm kiếm. Trong kiểu tìm kiếm này, một hoạt động tìm kiếm liên tiếp được diễn ra qua tất cả từng phần tử. Mỗi phần tử đều được kiểm tra và nếu tìm thấy bất kỳ kết nối nào thì phần tử cụ thể đó được trả về; nếu không tìm thấy thì quá trình tìm kiếm tiếp tục diễn ra cho tới khi tìm kiếm hết dữ liệu.
– Độ phức tạp về thời gian: O 
– Độ phức tạp không gian: O (1)
Dưới đây là một ví dụ việc triển khai tìm kiếm tuyến tính trong C ++

Không có mô tả ảnh.

2. Thuật toán Binary Search


Binary Search – tìm kiếm nhị phân, còn gọi là tìm kiếm nửa khoảng, tìm kiếm logarit, hay binary chop, là một thuật toán tìm kiếm xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp. Thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng.
– Độ phức tạp thời gian: O (log [n]) trong đó cơ số của log = 2
– Độ phức tạp của không gian: O (1) để thực hiện lặp trong khi O (log [n]) để thực hiện đệ quy vì với mỗi lần gọi đệ quy, một ngăn xếp mới được tạo ra.
Dưới đây là cách triển khai đệ quy của tìm kiếm nhị phân trong Java. Để thực hành, hãy cố gắng tự viết bản triển khai lặp đi lặp lại. Ví dụ:

Có thể là hình ảnh về văn bản cho biết 'public int binarySearchRecursive( int { int int int target) // RECURSIVE IMPLEMENTATION OF BINARY SEARCH int mid (1+r)/2; // base case checks if array is empty or not if (.1= a[mid]) t return binarySearchRecursive(a, mid+1, , target): } // recursive case 2 else { return binarySearchRecursive(a, 1, mid-1, target); removes right array }'

3. Thuật toán Ternary Search


Tương tự với thuật toán tìm kiếm nhị phân, Ternary Search – Tìm kiếm tam phân là một kỹ thuật trong khoa học máy tính dùng để tìm kiếm giá trị lớn nhất (maximum) hay nhỏ nhất (minimum) của một unimodal function, và đây cũng là một ví dụ ứng dụng lớp thuật toán Chia để trị (divide and conquer).
– Độ phức tạp thời gian: O (log [n]) trong đó cơ số của log = 3
– Độ phức tạp của không gian: O (1) để thực hiện lặp lại trong khi O (log [n]) để thực hiện đệ quy

Có thể là hình ảnh về văn bản cho biết '#include using namespace std; int ternaryI(int a[], int int ) int = =n-1; while( r-1>=0 partiton (-1)3) 1+partiton; int mid2 partiton; if target [mid1]) return mid1; else target return else target mid1-1; target mid2+1; [mid2]) else a[mid1] a[mid2] else mid1+1; =mid2-1; while ends return -1; function ends int main() int arr[] int 10; target int tsi ternaryI(arr, target, n); cout "Result TSI

4. Thuật toán Jump Search

Cơ chế của Jump Search đó là tìm ra một hệ số nhảy được tính bằng : Căn bậc hai của số phần tử. Từ hệ số tìm được, Jump Search sẽ thực hiện nhảy phần tử theo hệ số để tìm ra phần từ lớn hơn giá trị tìm kiếm. => Phần tử tìm kiếm sẽ nằm trong khoảng của nhảy mà chứa phần từ lớn hơn giá trị tìm kiếm ở trên.
– Độ phức tạp về thời gian: O (log [sqrt (n)])
– Độ phức tạp của không gian: O (1) để triển khai lặp lại trong khi O (log [sqrt (n)]) để triển khai đệ quy

Ví dụ:

Không có mô tả ảnh.

5. Thuật toán Exponential Search

Exponential Search là một cải tiến so với tìm kiếm nhị phân. Nó hoạt động trên một mảng được sắp xếp nhất định. Thay vì thực hiện tìm kiếm nhị phân trên toàn bộ tập dữ liệu, chúng ta tìm một khối có giá trị đích và sau đó thực hiện tìm kiếm nhị phân trong khối nhỏ đó. Để tìm khối, chúng ta lấy chỉ số (1) và kiểm tra giá trị của nó với giá trị đích. Nếu mục tiêu nhiều hơn giá trị chỉ mục này, thì chúng ta nhân đôi độ dài của khối hiện tại và kiểm tra chỉ mục (2) và tiếp tục làm điều này cho chỉ mục (4), (8), (16), v.v. cho đến khi tìm ra khối thích hợp. Vì toàn bộ hoạt động của khối này xảy ra trong 1–2–4–8–16-…, đó là lý do tìm kiếm này được gọi là tìm kiếm theo cấp số nhân.
– Độ phức tạp về thời gian: O (log [i]) trong đó i là chỉ số của phần tử cần tìm kiếm
– Độ phức tạp không gian: O (1) khi chúng ta sử dụng lặp đi lặp lại tìm kiếm nhị phân trong khi O (log [i]) để thực hiện đệ quy tìm kiếm nhị phân.

Ví dụ:

Có thể là hình ảnh về ‎văn bản cho biết '‎package search; public class Exponential extends Binary public int expoSearch( int[] ,ه int target) { int bound 1; while bound a.length && target bound 2; a[bound]) This below while loop does the same job while bound a.length) if target

5 thuật toán này không phải là những thuật toán tìm kiếm duy nhất hiện có. Còn một số thuật toán tìm kiếm phố biển khác như Tìm kiếm Nội suy hay Tìm kiếm Fibbonaci. Nhưng nếu bạn chú ý quan sát, bạn sẽ nhận ra tìm kiếm bậc ba, bước nhảy và hàm mũ chẳng qua là một bản sửa đổi của tìm kiếm tuyến tính hoặc nhị phân. Và trường hợp của phép nội suy và tìm kiếm fibonacci cũng vậy.

Do đó, nếu bạn thành thạo với tìm kiếm tuyến tính và nhị phân, bạn sẽ dễ dàng nắm bắt được bất kỳ thuật toán tìm kiếm nào trong số này.

Hợp Long


Leave a Reply

Your email address will not be published. Required fields are marked *


Hà Nội

Trụ sở chính


1800.6345

1900.6536

hoplong.com

[email protected]

Chi nhánh

We Are Everywhere



Hệ thống chi nhánh

Văn phòng: 87 Lĩnh Nam, Hà NộiKho: 946 Bạch Đằng, Hà NộiNhà máy: 22/64 Sài Đồng , Hà NộiCN1: 27 Vũ Giới – Bắc NinhCN2: 465 Chợ Hàng Mới – Hải PhòngCN3: 69 Nguyễn Lai – Đà NẵngCN4: 181/1 TTN17, Q12, TPHCM


Hợp Long Social

Theo dõi chúng tôi

Theo dõi Hoplong trên mạng xã hội để cập nhật các thông tin và hoạt động mới nhất.