Giới thiệu về CTDL & Giải thuật

DSA là gì?

Cấu trúc dữ liệu (Data Structures) là cách tổ chức và lưu trữ dữ liệu trong máy tính sao cho có thể truy cập và sử dụng hiệu quả.

Giải thuật (Algorithms) là một tập hợp các bước có thứ tự để giải quyết một vấn đề cụ thể.

💡

DSA giống như công cụ trong hộp đồ nghề của lập trình viên. Biết chọn đúng công cụ cho đúng việc sẽ giúp bạn làm việc hiệu quả hơn!

Tại sao cần học DSA?

1. Viết code hiệu quả hơn

Ví dụ tìm phần tử trùng lặp - so sánh O(n²) vs O(n):

Python


# Cách không tối ưu - O(n²)
def find_duplicate_slow(arr):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return arr[i]
    return None
 
# Cách tối ưu với Set - O(n)
def find_duplicate_fast(arr):
    seen = set()
    for num in arr:
        if num in seen:
            return num
        seen.add(num)
    return None

Kotlin


// Cách không tối ưu - O(n²)
fun findDuplicateSlow(arr: List<Int>): Int? {
    for (i in arr.indices) {
        for (j in i + 1 until arr.size) {
            if (arr[i] == arr[j]) return arr[i]
        }
    }
    return null
}
 
// Cách tối ưu với Set - O(n)
fun findDuplicateFast(arr: List<Int>): Int? {
    val seen = mutableSetOf<Int>()
    for (num in arr) {
        if (num in seen) return num
        seen.add(num)
    }
    return null
}

Dart


// Cách không tối ưu - O(n²)
int? findDuplicateSlow(List<int> arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int j = i + 1; j < arr.length; j++) {
      if (arr[i] == arr[j]) return arr[i];
    }
  }
  return null;
}
 
// Cách tối ưu với Set - O(n)
int? findDuplicateFast(List<int> arr) {
  Set<int> seen = {};
  for (int num in arr) {
    if (seen.contains(num)) return num;
    seen.add(num);
  }
  return null;
}

Swift


// Cách không tối ưu - O(n²)
func findDuplicateSlow(_ arr: [Int]) -> Int? {
    for i in 0..<arr.count {
        for j in (i + 1)..<arr.count {
            if arr[i] == arr[j] { return arr[i] }
        }
    }
    return nil
}
 
// Cách tối ưu với Set - O(n)
func findDuplicateFast(_ arr: [Int]) -> Int? {
    var seen = Set<Int>()
    for num in arr {
        if seen.contains(num) { return num }
        seen.insert(num)
    }
    return nil
}

Java


// Cách không tối ưu - O(n²)
public static Integer findDuplicateSlow(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) return arr[i];
        }
    }
    return null;
}
 
// Cách tối ưu với Set - O(n)
public static Integer findDuplicateFast(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    for (int num : arr) {
        if (seen.contains(num)) return num;
        seen.add(num);
    }
    return null;
}

2. Giải quyết vấn đề phức tạp

DSA cung cấp các mẫu (patterns) đã được chứng minh để giải quyết nhiều loại bài toán:

Tìm đường đi ngắn nhất
Sắp xếp dữ liệu
Tìm kiếm nhanh
Tối ưu hóa

3. Phỏng vấn kỹ thuật

Hầu hết các công ty công nghệ lớn (Google, Facebook, Amazon…) đều yêu cầu DSA trong phỏng vấn.

Các cấu trúc dữ liệu cơ bản

Cấu trúc	Mô tả	Ví dụ thực tế
Array	Danh sách có thứ tự, truy cập theo index	Danh sách học sinh
Linked List	Các node liên kết với nhau	Playlist nhạc
Stack	LIFO - Vào sau, ra trước	Nút Undo/Redo
Queue	FIFO - Vào trước, ra trước	Hàng đợi mua vé
Hash Table	Lưu trữ key-value	Từ điển
Tree	Cấu trúc phân cấp	Thư mục file
Graph	Các đỉnh kết nối bởi cạnh	Mạng xã hội

Các thuật toán quan trọng

Thuật toán	Mục đích
Binary Search	Tìm kiếm nhanh trong mảng đã sắp xếp
Merge Sort	Sắp xếp hiệu quả O(n log n)
BFS/DFS	Duyệt đồ thị
Dynamic Programming	Tối ưu hóa bài toán con lặp lại

Lộ trình học

Bắt đầu từ đâu?

Độ phức tạp thuật toán - Hiểu Big O trước tiên
Mảng (Array) - Cấu trúc dữ liệu cơ bản nhất
Tiếp tục theo lộ trình trong sidebar

⚠️

Mẹo học DSA hiệu quả:

Hiểu khái niệm trước, code sau
Vẽ hình minh họa khi cần
Thực hành nhiều bài tập trên LeetCode
Đừng nản nếu không giải được ngay - DSA cần thời gian!