Tài liệu ôn tập cấu trúc dữ liệu

Cấu trúc dữ liệu và giải thuật

Ngày thi: 7h00 - 27/12/2025 - 1.C103

A. Độ phức tạp

O(1) > O(log n) > O(n) > O(n log n) > O(n²)

Độ phức tạp thuật toán (Time Complexity) là cách đo mức độ tăng thời gian chạy của thuật toán khi kích thước dữ liệu đầu vào tăng lên.

• Không đo bằng giây, ms, hay tốc độ máy
• Đo bằng số phép toán cơ bản (so sánh, gán, cộng, trừ…)
• Mục tiêu: so sánh thuật toán nào hiệu quả hơn khi dữ liệu lớn

O-lớn – O (Big-O) (TH xấu nhất)

• O(f(n)) mô tả giới hạn trên của độ phức tạp thuật toán, tức là trường hợp xấu nhất (worst case).

Omega – Ω (Big-Omega) (TH tốt nhất)

• Ω(f(n)) mô tả giới hạn dưới của độ phức tạp, tức là trường hợp tốt nhất (best case).

Theta – Θ (Big-Theta) (TH chính xác nhất)

• Θ(f(n)) mô tả độ phức tạp chặt, tức là cả giới hạn trên và dưới đều là f(n).

Công thức tính độ phức tạp:
T(n) = O(n)

* Chú thích:

Độ phức tạp = số lần thực hiện thao tác cơ bản khi n tăng lớn

• So sánh (<, >, ==)
• Gán
• Truy cập phần tử
• Cộng / trừ / nhân / chia đơn giản

Công thức nhớ nhanh:

• Truy xuất mảng: O(1)
• Duyệt mảng 1D: O(n)
• Duyệt mảng 2D: O(mn)

Khi đề hỏi:

“Phân tích độ phức tạp theo Big-O”

→ Luôn trả lời:

1. Thời gian
2. Không gian
3. Nêu lý do ngắn gọn

• 1 vòng lặp / 2 vòng lặp không lồng nhau => O(n)
• 2 vòng lặp lồng nhau => O(n2)
• Mỗi lần lặp bị chia đôi n => O(log n)
• O(n log n): vòng lặp trong là (log n), vì chia đôi. Vòng lặp ngoài là n.

=> O(n log n)

B. Đệ quy

Định nghĩa

Đệ quy là kỹ thuật trong đó hàm gọi lại chính nó để giải bài toán nhỏ hơn cùng dạng.

Một hàm đệ quy phải có:

• Điều kiện dừng
• Lời gọi đệ quy

Độ phức tạp thường gặp

• T(n) = T(n-1) + 1 → O(n)
• T(n) = T(n/2) + 1 → O(log n)

C. Mảng & Danh sách liên kết

1. Mảng

Định nghĩa

Mảng là cấu trúc dữ liệu lưu các phần tử liên tiếp trong bộ nhớ, truy cập bằng chỉ số.

Đặc điểm:

• Truy xuất phần tử: O(1)
• Kích thước cố định

2. Danh sách liên kết đơn

Định nghĩa

Mỗi node gồm:

• Dữ liệu
• Con trỏ trỏ đến node kế tiếp

Minh họa

data | next → data | next → NULL

3. Danh sách liên kết đôi

Định nghĩa

Mỗi node có:

• Con trỏ tới node trước
• Con trỏ tới node sau

Minh họa

prev | data | next

D. Sort

1. Bubble Sort O(n²)

a. Định nghĩa

So sánh các cặp phần tử kề nhau, đổi chỗ nếu sai thứ tự.

b. Minh họa

Mỗi vòng lặp, phần tử lớn nhất “nổi” về cuối mảng.

Vòng lặp 1:

(5,1) → đổi → [1,5,4,2]

(5,4) → đổi → [1,4,5,2]

(5,2) → đổi → [1,4,2,5]

Vòng lặp 2

(1,4) → không đổi

(4,2) → đổi → [1,2,4,5]

Vòng lặp 3

(1,2) → không đổi

Kết quả

[1,2,4,5]

c. Code

2. Selection Sort O(n²)

a. Định nghĩa

Mỗi lần chọn phần tử nhỏ nhất trong phần chưa sắp xếp.

b. Minh họa

Chọn min → đưa về đầu mảng.

Lượt 1

• Min = 11
• Đổi chỗ với 64

[11, 25, 12, 22, 64]

Lượt 2

• Min trong [25,12,22,64] = 12

[11, 12, 25, 22, 64]

Lượt 3

• Min = 22

[11, 12, 22, 25, 64]

Kết quả

[11,12,22,25,64]

c. Code

3. Insertion Sort O(n²)

a. Định nghĩa

Chèn phần tử vào đúng vị trí trong đoạn đã sắp xếp.

b. Minh họa

Giống cách sắp bài trên tay.

c. Code

4. Quick Sort O(n log n)

a. Định nghĩa

Chọn pivot, chia mảng thành 2 phần, sắp xếp đệ quy.

b. Minh họa

Phần nhỏ hơn pivot bên trái, lớn hơn bên phải.

[9, 3, 7, 1, 6]

Chọn pivot

Giả sử pivot = 6

Partition

< 6 | 6 | > 6

[3,1] 6 [9,7]

Đệ quy

Sắp xếp tiếp:

[1,3] | 6 | [7,9]

Kết quả

[1,3,6,7,9]

c. Code

5. Merge Sort O(n log n)

a. Định nghĩa

Thuật toán chia để trị, chia mảng làm đôi rồi trộn.

b. Minh họa

Chia → sắp xếp → trộn.

c. Code

E. Stack

a. Định nghĩa

Stack là cấu trúc LIFO (vào sau ra trước).

b. Minh họa

Push → Pop ở đỉnh stack.

c. Code

F. Queue

a. Định nghĩa

Queue là cấu trúc FIFO (vào trước ra trước).

b. Minh họa

Enqueue cuối, Dequeue đầu.

c. Code

G. Tree

a. Định nghĩa

Cây là cấu trúc phân cấp gồm các node, có node gốc.

b. Minh họa

Root → node con trái / phải.

• A là cha của B và C
• B là cha của D và E
• D, E, F là nút lá

Bậc của nút

• A có bậc 2
• C có bậc 1
• D có bậc 0

Chiều cao của cây

• Mức 0: A
• Mức 1: B, C
• Mức 2: D, E, F

c. Code

*Chú thích:

• Tuyến tính → duyệt từ đầu → O(n)
• Nhị phân → chia đôi → O(log n)

Cây:

• Root: 1
• Leaf: không có con
• Bậc = số con
• Chiều cao = số mức sâu nhất

H. Tìm kiếm

1. Tìm kiếm tuyết tính

a. Định nghĩa

Duyệt từng phần tử để tìm giá trị cần tìm.

b. Minh họa

So sánh từ đầu đến cuối.

A = [4, 7, 1, 9, 3] Cần tìm: x = 9

• Bước 1: so sánh 4 ≠ 9
• Bước 2: so sánh 7 ≠ 9
• Bước 3: so sánh 1 ≠ 9
• Bước 4: so sánh 9 = 9 → TÌM THẤY

c. Code

2. Tìm kiếm nhị phân O(log n)

a. Định nghĩa

Chia đôi mảng đã sắp xếp để tìm kiếm.

b. Minh họa

So sánh với phần tử giữa.

A = [1, 3, 5, 7, 9, 11, 13] Cần tìm: x = 9

• left = 0, right = 6
• mid = (0 + 6)/2 = 3
• A[mid] = 7

=> 9 > 7 → bỏ nửa trái

• left = 4, right = 6
• mid = (4 + 6)/2 = 5
• A[mid] = 11

=> 9 < 11 → bỏ nửa phải

• left = 4, right = 4
• mid = 4
• A[mid] = 9 → TÌM THẤY

=> Tìm thấy 9

c. Code

Code minh họa:

#include <iostream>
using namespace std;

/* =========================
A. ĐỆ QUY
========================= */
int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}

/* =========================
B. MẢNG
========================= */
void printArray(int a[], int n) {
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << endl;
}

/* =========================
C. DANH SÁCH LIÊN KẾT ĐƠN
========================= */
struct Node {
int data;
Node* next;
};

Node* createNode(int x) {
Node* p = new Node;
p->data = x;
p->next = NULL;
return p;
}

/* =========================
D. SORT
========================= */

/* Bubble Sort */
void bubbleSort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (a[j] > a[j + 1])
swap(a[j], a[j + 1]);
}

/* Selection Sort */
void selectionSort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIdx = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[minIdx])
minIdx = j;
swap(a[i], a[minIdx]);
}
}

/* Insertion Sort */
void insertionSort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}

/* Quick Sort */
int partition(int a[], int low, int high) {
int pivot = a[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (a[j] < pivot) {
i++;
swap(a[i], a[j]);
}
}
swap(a[i + 1], a[high]);
return i + 1;
}

void quickSort(int a[], int low, int high) {
if (low < high) {
int pi = partition(a, low, high);
quickSort(a, low, pi - 1);
quickSort(a, pi + 1, high);
}
}

/* Merge Sort */
void merge(int a[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];

for (int i = 0; i < n1; i++) L[i] = a[l + i];
for (int j = 0; j < n2; j++) R[j] = a[m + 1 + j];

int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) a[k++] = L[i++];
else a[k++] = R[j++];
}
while (i < n1) a[k++] = L[i++];
while (j < n2) a[k++] = R[j++];
}

void mergeSort(int a[], int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(a, l, m);
mergeSort(a, m + 1, r);
merge(a, l, m, r);
}
}

/* =========================
E. STACK (mảng)
========================= */
#define MAX 100
int stackArr[MAX];
int top = -1;

void push(int x) {
stackArr[++top] = x;
}

int pop() {
return stackArr[top--];
}

/* =========================
F. QUEUE (mảng)
========================= */
int queueArr[MAX];
int front = 0, rear = -1;

void enqueue(int x) {
queueArr[++rear] = x;
}

int dequeue() {
return queueArr[front++];
}

/* =========================
G. TREE (Cây nhị phân)
========================= */
struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
};

TreeNode* newTreeNode(int x) {
TreeNode* p = new TreeNode;
p->data = x;
p->left = p->right = NULL;
return p;
}

/* =========================
H. TÌM KIẾM
========================= */

/* Tìm kiếm tuyến tính */
int linearSearch(int a[], int n, int x) {
for (int i = 0; i < n; i++)
if (a[i] == x) return i;
return -1;
}

/* Tìm kiếm nhị phân (mảng đã sắp xếp) */
int binarySearch(int a[], int n, int x) {
int l = 0, r = n - 1;
while (l <= r) {
int m = (l + r) / 2;
if (a[m] == x) return m;
if (a[m] < x) l = m + 1;
else r = m - 1;
}
return -1;
}

/* =========================
MAIN
========================= */
int main() {
int a[] = {5, 2, 9, 1, 3};
int n = 5;

cout << "Factorial(5): " << factorial(5) << endl;

bubbleSort(a, n);
printArray(a, n);

cout << "Linear search 3: " << linearSearch(a, n, 3) << endl;
cout << "Binary search 3: " << binarySearch(a, n, 3) << endl;

push(10); push(20);
cout << "Pop stack: " << pop() << endl;

enqueue(100); enqueue(200);
cout << "Dequeue queue: " << dequeue() << endl;

TreeNode* root = newTreeNode(1);
root->left = newTreeNode(2);
root->right = newTreeNode(3);

return 0;
}