Basic enlightenment on Data Structures & Algorithms. How important is this subject?
Xin chào mọi người, mình là Cường - thực tập sinh công nghệ thông tin - khóa java 21st
Nếu phải bầu chọn 1 môn học hay, thú vị, và hữu ích với các bạn sinh viên công nghệ thông tin đặc biệt là chuyên ngành phần mềm thì Cường sẽ đề cử môn Cấu Trúc Dữ Liệu & Giải Thuật “Data Structures & Algorithms”. Đây là một môn học rèn luyện tư duy lập trình rất tốt cho các bạn. Và đó cũng là cái mà để các công ty test các bạn mỗi khi đi xin việc. Mới ra trường hoặc đã có kinh nghiệm vài năm đều được test các thuật toán hết. Vì vậy trong bài viết ngày hôm nay Cường sẽ nói về Cấu Trúc Dữ Liệu & Giải Thuật.
Phụ lục
- Khái Niệm
- Big o Notation (kí hiệu chứ o lớn)
Khái Niệm
Cấu Trúc Dữ Liệu
- Cấu trúc (Structure): là sự sắp xếp và tổ chức các yếu tố bên trong của một vật hay hệ thống nào đó.
- Dữ liệu (data): Dữ liệu có thể hiểu là tất cả những gì tồn tại dưới dạng thông tin, và khi lưu trữ vào máy tính, nó thường được chuyển đổi thành các định dạng khác nhau để dễ dàng quản lý và sử dụng.
Ví dụ: “1 idol kpop chúng ta cần quan tấm đến tên, tuối, địa chỉ, chiều cao, cân nặng, danh sách âm nhạc,…”
Và các thông tin sẽ được lưu vào các biến (variable)
Dưới đây là ví dụ về dữ liệu idol kpop được lưu dưới dạng json:
{
"idol": {
"name": "Lisa",
"age": 26,
"address": "Bangkok, Thailand",
"height_cm": 166,
"weight_kg": 48,
"music_list": [
{
"song_title": "LALISA",
"release_date": "2021-09-10",
"album": "LALISA"
},
{
"song_title": "MONEY",
"release_date": "2021-09-10",
"album": "LALISA"
}
]
}
}
Cấu trúc dữ liệu(Data Structures): là nhóm các dữ liệu có liên kết với nhau.
Có rất nhiều các thức liên kết dữ liệu khác nhau đồng nghĩa với việc chúng ta sẽ có nhiều loại cấu trúc dữ liệu khác nhau.
Cấu trúc dữ liệu phổ biến mà mọi người đã được học là “array”
Array: là tập hợp các dữ liệu có cùng kiểu (datatype)
String[] musicList1 = {"Song A", "Song B", "Song C"};
Giải Thuật
Giải Thuật (Algorithms): tên gọi khác là thuật toán là cách thức để giải quyết 1 vấn đề, 1 bài toán
Chúng ta cần giải 1 bài toán nhanh và hiệu quả nhất
Ví dụ “khi ta sự dụng gg thì nó sẽ trả về cho ta kết quả rất nhanh 0,0001 s”
Vậy làm sao để chúng ta đánh giá được thuật toán: Trong lập trình để đo lường được cái hiệu năng của thuật toán người ta có 1 khái niệm gọi là Độ Phức Tạp Của Thuật Toán
Kí hiệu: " Big O notation " O(…)
Khái niệm Big O Notation đã được đưa ra để định nghĩa, đo lường tính hiệu quả của một thuật toán. Nó dựa vào số bước cần thực hiện cho một tác vụ nào đó để đo lường tính hiệu quả của thuật toán đó.
Big O Notation
Trong toán học, ký hiệu O lớn dùng để chỉ hành vi giới hạn của một hàm số khi đối số tiến đến một giá trị nhất định hoặc vô cùng. Đối với lĩnh vực khoa học máy tính, nó còn dùng để mô tả hành vi thuật toán (ví dụ, về mặt thời gian tính toán hoặc lượng bộ nhớ cần dùng) khi kích thước dữ liệu thay đổi.
– Wikipedia –
Ký hiệu Big-O mô tả các hàm theo tốc độ tăng của chúng: các hàm khác nhau có cùng tốc độ tăng có thể được mô tả bởi cùng một ký hiệu. Một số hàm phổ biến thường gặp như:
O(1): Độ phức tạp hằng số
O(log n): Độ phức tạp logarit
O(n): Độ phức tạp tuyến tính
O(n2): Độ phức tạp đa thức
O(an): Độ phức tạp hàm mũ mũ
Áp dụng Big o Notation (kí hiệu chứ o lớn) O(…)
Thuật toán tìm kiếm
Yêu cầu: tìm ra idol có số tuổi cao nhất
cho mảng ages = {25, 30, 28, 22, 35, 29, 31, 27};
public class FindMaxAge {
public static void main(String[] args) {
// Tạo một mảng chứa 8 giá trị tuổi
int[] ages = {25, 30, 28, 22, 35, 29, 31, 27};
// Gọi phương thức để tìm tuổi lớn nhất
int maxAge = findMaxAge(ages);
// In ra tuổi lớn nhất
System.out.println("Tuổi lớn nhất là: " + maxAge);
}
// Phương thức tìm tuổi lớn nhất
public static int findMaxAge(int[] ages) {
int maxAge = ages[0]; // Khởi tạo maxAge với giá trị đầu tiên trong mảng
for (int i = 1; i < ages.length; i++) { // Vòng lặp từ chỉ số 1 đến hết mảng
if (ages[i] > maxAge) {
maxAge = ages[i]; // Cập nhật maxAge nếu tìm thấy giá trị lớn hơn
}
}
return maxAge;
}
}
kết quả:
Độ phức tạp thời gian (Time Complexity): O(n)
Với n là số lượng phần tử trong mảng.
Vòng lặp duyệt qua toàn bộ mảng một lần, và mỗi phép toán trong vòng lặp có độ phức tạp là hằng số.
Yêu cầu 2:“sắp xếp các idol theo tuổi tăng dần”
cho mảng ages = {25, 30, 28, 22, 35, 29, 31, 27};
import java.util.Arrays;
public class SortAges {
public static void main(String[] args) {
// Tạo một mảng chứa 8 giá trị tuổi
int[] ages = {25, 30, 28, 22, 35, 29, 31, 27};
// Sắp xếp mảng theo thứ tự tăng dần
bubbleSort(ages);
// Chuyển mảng đã sắp xếp thành chuỗi và in ra
String sortedAges = Arrays.toString(ages);
System.out.println("Mảng tuổi sau khi sắp xếp: " + sortedAges);
}
// Phương thức sắp xếp nổi bọt (Bubble Sort) sử dụng vòng lặp for
public static void bubbleSort(int[] array) {
int n = array.length;
// Vòng lặp để đảm bảo rằng mảng được sắp xếp hoàn toàn
for (int i = 0; i < n - 1; i++) {
// Vòng lặp để so sánh các phần tử kế tiếp và hoán đổi nếu cần
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Hoán đổi array[j] và array[j + 1]
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}
Kết quả :
Độ Phức Tạp:
Thuật toán sắp xếp (Bubble Sort):
Độ phức tạp thời gian: O(n²), vì có hai vòng lặp lồng nhau.
Độ phức tạp không gian: O(1), vì sử dụng không gian thêm hằng số cho việc hoán đổi các phần tử.
Còn rất nhiều thuật toán rất hay nữa, thì Cường sẽ giới thiệu ở bài viết tới
Thanks for reading the blog post. love you soo much!!. Goodbye and see you again ❤😍😘
Bình luận