🎲Algorithms

Thuật toán là một quy trình bao gồm các bước để giải quyết vấn đề hoặc hoàn thành nhiệm vụ, thường được ứng dụng trong lập trình máy tính và xử lý dữ liệu.

Algorithm complexity

What is time complexity so important?

Thuật toán hợp lệ là thuật toán cần 1 thời gian cần thiết để khởi chạy. Thời gian mà thuật toán giải quyết được vấn đề của bài toán đặt ra chính là time complexity của 1 thuật toán. Time complexity là thước đo hữu ích trong việc phân tích thiết kế thuật toán. Đó là lí do mà time complexity rất quan trọng.

What is algorithm complexity?

Về bản chất, độ phức tạp giải thuật là một hàm ước lượng (có thể không chính xác) số phép tính mà giải thuật cần thực hiện (từ đó dễ dàng suy ra thời gian thực hiện của giải thuật) đối với bộ dữ liệu đầu vào (Input) có kích thước n. Trong đó, n có thể là số phần tử của mảng trong trường hợp bài toán sắp xếp hoặc tìm kiếm, hoặc có thể là độ lớn của số trong bài toán kiểm tra số nguyên tố, …

Giả sử X là một giải thuật và n là kích cỡ của dữ liệu đầu vào. Thời gian và lượng bộ nhớ được sử dụng bởi giải thuật X là hai nhân tố chính quyết định hiệu quả của giải thuật X:

• Nhân tố thời gian: Thời gian được đánh giá bằng việc tính số phép tính chính (chẳng hạn như các phép so sánh trong thuật toán sắp xếp).

• Nhân tố bộ nhớ: Lượng bộ nhớ được đánh giá bằng việc tính lượng bộ nhớ tối đa mà giải thuật cần sử dụng.

Độ phức tạp của một giải thuật (một hàm f(n)) cung cấp mối quan hệ giữa thời gian chạy và/hoặc lượng bộ nhớ cần được sử dụng bởi giải thuật.

Sort

QuickSort

Quicksort là thuật toán dựa trên bài toán Chia để trị, phân chia mảng thành các phần nhỏ để sắp xếp. Quicksort chọn 1 phần tử làm điểm so sánh và đưa các phần tử có giá trị nhỏ hơn về bên trái, đưa các phần tử có giá trị nhỏ hơn về bên phải. Quá trình phân mảng sẽ diễn ra cho đến khi mảng được sắp xếp hoàn toàn.

Phân loại: Giải thuật sắp xếp
Phức tạp thời gian: Trung bình O(n log n)
Xấu nhất: O(n2)
Phức tạp dữ liệu: Khác nhau tùy vào cách hiện thực
Tối ưu: Thỉnh thoảng

How does QuickSort work?

Keywork của quá trình xử lí của Quicksort là partition

Partition

Sau khi hiểu về thuật toán, có lẽ bạn sẽ có một nghi vấn nhỏ nảy lên trong đầu: Tại sao chọn phần tử chốt là phần tử đầu tiên bên trái? Và cách chọn phần tử chốt có ảnh hưởng đến độ nhanh chậm của sắp xếp hay không? Thực tế thì kỹ thuật chọn phần tử chốt ảnh hưởng khá lớn đến thuật toán, bởi chúng ta có khả năng bị rơi vào các vòng lặp vô hạn. Một số cách chọn phần tử chốt để bạn tham khảo:

• Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.

• Chọn phần tử đứng giữa danh sách làm phần tử chốt.

• Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.

• Chọn phần tử ngẫu nhiên làm phần tử chốt. (Cách này có thể dẫn đến khả năng rơi vào các trường hợp đặc biệt)

Cài đặt thuật toán

// Java implementation of QuickSort
import java.io.*;

class GFG {

	// A utility function to swap two elements
	static void swap(int[] arr, int i, int j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// This function takes last element as pivot,
	// places the pivot element at its correct position
	// in sorted array, and places all smaller to left
	// of pivot and all greater elements to right of pivot
	static int partition(int[] arr, int low, int high)
	{
		// Choosing the pivot
		int pivot = arr[high];

		// Index of smaller element and indicates
		// the right position of pivot found so far
		int i = (low - 1);

		for (int j = low; j <= high - 1; j++) {

			// If current element is smaller than the pivot
			if (arr[j] < pivot) {

				// Increment index of smaller element
				i++;
				swap(arr, i, j);
			}
		}
		swap(arr, i + 1, high);
		return (i + 1);
	}

	// The main function that implements QuickSort
	// arr[] --> Array to be sorted,
	// low --> Starting index,
	// high --> Ending index
	static void quickSort(int[] arr, int low, int high)
	{
		if (low < high) {

			// pi is partitioning index, arr[p]
			// is now at right place
			int pi = partition(arr, low, high);

			// Separately sort elements before
			// partition and after partition
			quickSort(arr, low, pi - 1);
			quickSort(arr, pi + 1, high);
		}
	}
	// To print sorted array
	public static void printArr(int[] arr)
	{
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
	}

	// Driver Code
	public static void main(String[] args)
	{
		int[] arr = { 10, 7, 8, 9, 1, 5 };
		int N = arr.length;

		// Function call
		quickSort(arr, 0, N - 1);
		System.out.println("Sorted array:");
		printArr(arr);
	}
}

// This code is contributed by Ayush Choudhary
// Improved by Ajay Virmoti

Out put:

Sorted array: 
1 5 7 8 9 10 

Ưu nhược điểm

Ưu điểm	Nhược điểm
Tốc độ sắp xếp nhanh.	Phụ thuộc vào cách chọn phần tử chốt.
Được sử dụng trong nhiều thư viện của các ngôn ngữ như C++, Java, ...	Không ổn định.

Search

Sequential Search

Tìm kiếm tuần tự (Sequential Search hay Linear Search) là một giải thuật đơn giản, rất dễ cài đặt. Bắt đầu từ đối tượng a1, duyệt qua tất cả các đối tượng, cho tới khi tìm thấy đối tượng có khóa mong muốn, hoặc duyệt hết toàn bộ dãy mà không tìm thấy khóa đó.

Example of Linear Search

Ví dụ thuật toán:

sequential_search(a[], n, k)
{
    for (i = 1; i <= n; ++i)
        if (a[i].key == k)
            return i;
            
    // Không tìm thấy đối tượng nào có khóa bằng k, trả về -1.
    return -1;
}

Đánh giá

Mặc dù giải thuật Tìm kiếm tuần tự rất đơn giản và dễ cài đặt, tuy nhiên nhược điểm của nó nằm ở độ phức tạp. Trong trường hợp tốt nhất, giải thuật có độ phức tạp là O(1), nhưng trong trường hợp xấu nhất lên tới O(n). Vì vậy độ phức tạp tổng quát của giải thuật là O(n), chỉ phù hợp với những bài toán có kích thước không gian tìm kiếm nhỏ.

Binary Search

Thuật toán Binary Serach (Tìm kiếm nhị phân) là một thuật toán tìm kiếm tuyến tính cao cấp hơn với thời gian chạy là O(logN).

Mô tả thuật toán

Về cơ bản, các bước thực hiện tìm kiếm x trong mảng như sau:

• So sánh x với phần tử ở giữa

• Nếu x khớp với phần tử ở giữa, chúng ta trả về chỉ số giữa

• Nếu x lớn hơn phần tử giữa, thì x chỉ có thể nằm trong nửa phân đoạn bên phải sau phần tử mid. Vì vậy, chúng ta chỉ tìm kiếm ở nữa phải của mảng

• Nếu x nhỏ hơn phần tử giữa tiếp tục tìm ở nửa bên trái

• Lặp lại đến khi tìm ra x hoặc trả về null khi x không nằm trong mảng

Đánh giá

Đối với các danh sách lớn, thuật toán này tốt hơn hẳn tìm kiếm tuyến tính, nhưng nó đòi hỏi danh sách phải được sắp xếp từ trước và đòi hỏi khả năng truy nhập ngẫu nhiên (random access).

Thuật toán tìm kiếm nhị phân chạy nhanh hơn tìm kiếm tuần tự nhưng cũng có một số nhược điểm. Nó chậm hơn bảng băm.

Thuật toán tìm kiếm nhị phân thường dùng để tìm kiếm phần tử trong một danh sách đã được sắp xếp, ví dụ như trong một danh bạ điện thoại sắp xếp theo tên, có thể tìm kiếm số điện thoại của một người theo tên người đó.

Nếu nội dung danh sách bị thay đổi thì danh sách phải được sắp xếp lại trước khi sử dụng tìm kiếm nhị phân.

Mà thao tác này thường tốn nhiều thời gian.