Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

thumbnailday1_thuchanh

DSA Từ A-Z: Day 1 – Nền Tảng Cơ Bản và Phân Tích Độ Phức Tạp (Bài Tập )

Article by Loser1 – Learning AI with Losers

⚠️

Lưu ý: Kiến Thức Tiên Quyết

Các bạn nên đọc và nắm vững 2 phần lý thuyết trước khi bắt đầu làm bài tập nhé! Để đảm bảo không bỏ lỡ kiến thức quan trọng, hãy đọc theo thứ tự:

Lời Mở Đầu

Chào các bạn, lại là loser1 From Learning AI with losers đây ! Sau khi đã cùng nhau băng qua “khu rừng” lý thuyết với hai phần về nền tảng cơ bản và phân tích độ phức tạp, đã đến lúc chúng ta thực sự “getting our hands dirty” với những bài tập thực tế rồi! 💪

Về Nguồn Gốc Bài Tập

Để đảm bảo chất lượng và tính thực tiễn, mình đã tổng hợp các bài tập từ nguồn “xịn sò” nhất có thể – đó là đề thi của các trường đại học hàng đầu về công nghệ tại Việt Nam:

  • Trường Đại học Khoa học Tự nhiên, ĐHQG-HCM (HCMUS) (chủ yếu)
  • Trường Đại học Bách Khoa Hà Nội (HUST) (có thể)
  • Trường Đại học Công nghệ Thông tin, ĐHQG-HCM (UIT) (có thể )

Tại sao lại chọn các bài tập này? Bởi vì:

  1. Đây là những bài tập đã được kiểm chứng qua nhiều năm
  2. Chúng cover đầy đủ các kỹ năng phân tích thuật toán cần thiết
  3. Độ khó tăng dần, giúp bạn xây dựng tư duy một cách bài bản
  4. Đặc biệt, đây là style bài tập thường xuất hiện trong các buổi phỏng vấn tại các công ty lớn

Cấu Trúc Bài Tập

Mỗi bài tập sẽ được trình bày theo format sau:

  • 📝 Đề bài: Mô tả chi tiết yêu cầu
  • 💡 Gợi ý: Các hint giúp bạn tiếp cận vấn đề (có spoiler tag để bạn có thể tự suy nghĩ trước)
  • Lời giải: Giải thích chi tiết từng bước, kèm theo phân tích độ phức tạp
  • 🔍 Bình luận: Các observation và techniques quan trọng cần nhớ
  • 🎯 Follow-up: Các câu hỏi mở rộng để bạn tự luyện tập thêm

Lời Khuyên Trước Khi Bắt Đầu

  1. Đừng vội nhìn lời giải! Hãy dành ít nhất 20-30 phút để tự suy nghĩ về bài toán.
  2. Viết ra giấy các ý tưởng của bạn, vẽ sơ đồ nếu cần.
  3. Bắt đầu với test case đơn giản rồi mới đến các case phức tạp hơn.
  4. Nếu stuck, hãy đọc phần gợi ý trước khi xem lời giải.
  5. Sau khi có lời giải, hãy tự implement lại để đảm bảo bạn thực sự hiểu.

Chuẩn Bị Gì?

  • ⌨️ IDE/Editor yêu thích của bạn
  • 📒 Giấy bút để ghi chép
  • 🧠 Một cái đầu tỉnh táo
  • ⏰ Set aside khoảng 2-3 tiếng để focus
  • 🎧 Playlist nhạc coding để boost mood (optional nhưng recommended 😉)

Được rồi, giờ thì… Let’s crush some algorithms! 🚀

Phần 0 : Nền Tảng

Đề 1 :

Câu a:

Câu b:

Ưu và nhược điểm của kiến trúc dữ liệu động

Ưu điểm:

  • Tính linh hoạt: Cấu trúc dữ liệu động có thể thay đổi kích thước trong quá trình thực thi chương trình, cho phép thêm hoặc xóa phần tử dễ dàng mà không cần phải định nghĩa trước kích thước.
  • Sử dụng bộ nhớ hiệu quả: Không cần phải cấp phát bộ nhớ cho các phần tử không sử dụng, giúp tiết kiệm bộ nhớ.

Nhược điểm:

  • Chi phí truy cập: Truy cập vào các phần tử trong cấu trúc dữ liệu động thường chậm hơn so với cấu trúc dữ liệu tĩnh do cần phải theo dõi các con trỏ.
  • Quản lý bộ nhớ phức tạp: Cần phải quản lý bộ nhớ một cách cẩn thận để tránh rò rỉ bộ nhớ hoặc lỗi truy cập bộ nhớ.

Cấu trúc đề năm 18-19

Phần 1: Complexity

Đề 1:

a. Heapsort: O(nlogn) với n là số phần tử của mảng cần sắp thứ tự

b. Mergesort: O(nlogn) với n là số phần tử của mảng cần sắp thứ tự

c. Quicksort: O(n²) trong trường hợp xấu nhất, O(n log n) trong trường hợp trung bình và tốt nhất

d. Counting Sort: O(n + k) (với n là số phần tử và k là giá trị lớn nhất trong mảng)

e. Sequential Search: O(n) trong trường hợp trung bình với xấu nhất, O(1) trong trường hợp tốt nhất (với n là số phần tử)

f. Tìm kiếm nhị phân (Binary Search): O(log n) trong trường hợp trung bình với xấu nhất, O(1) trong trường hợp tốt nhất (với n là số phần tử)

g. Naive: O(n*m) trong trường hợp trung bình với xấu nhất, O(n) trong trường hợp tốt nhất

h. KMP: O(n + m): Với n là độ dài của chuỗi văn bản và m là độ dài của chuỗi mẫu

i. Xây dựng BST từ mảng sắp xếp tăng: O(n) với n là số phần tử

j. Tìm kiếm trong hash table trong trường hợp không có đụng độ xảy ra: O(1)

Đề 2:

Giải đáp độ phức tạp thời gian (Big-O) cho từng công việc:

  1. Kiểm tra dãy số nguyên có phải là max-heap: O(N)
  2. Kiểm tra dãy không giảm: O(N)
  3. Hiển thị phần tử cuối cùng của mảng: O(1)
  4. Lấy phần tử khỏi hàng đợi (trường hợp xấu nhất: hàng đợi dùng mảng): O(N)
  5. Tìm kiếm trên cây BST (cây suy biến): O(N)
  6. Xóa phần tử khỏi danh sách liên kết đơn (dựa trên giá trị): O(N)
  7. Hiển thị khóa chẵn giảm dần trên cây AVL: O(N log N)
  8. Xác định phần tử nhỏ nhất trên max-heap: O(N)

Đề 3:

ĐÁP ÁN

Gọi Số phần tử của A1, A2, A3 là n1, n2, n3

Câu a:

Cứ insert lần lượt phần tử vô cây nhị phân của A1, A2, A3

Độ phức tạp: O(NlogN) với N = n1 + n2 + n3 (cả 3 trường hợp tệ, trung bình, tốt nhất)

Câu 3:

Đầu tiên ta sẽ ghép 3 mảng lại với nhau lần lượt bằng thuật toán 2 con trỏ:

  • Đầu tiên mảng A1, A2 được ghép bằng thuật toán 2 con trỏ ta được một mảng A12 vẫn giữ được tăng dần
  • Ta lại tiếp tục dùng 2 con trỏ để ghép A12 với A3
  • Lúc này ta được mảng A123 với N = n1 + n2 + n3 là số phần tử
  • Cuối cùng ta dùng thuật toán chia trị để liên tục chia cắt mảng A123 để tìm phần tử pivot ở giữa để tạo nên cây nhị phân tìm kiếm từ mảng A123 tăng dần

Chi Phí:

Tổng chi phí O(N + LogN) = O(N) hay O(n) thỏa yêu cầu đề bài

Ghép mảng 2 con trỏ: O(N)

Từ mảng tăng dần chuyển sang BST: O(LogN)

Đề 4 :

ĐÁP ÁN

Không hiểu sao bắt đầu từ 1 kết thúc ở X.length mà không phải là từ 0 tới X.length-1

Giả sử 0 tới X.length:

  • Nó đang tìm kiếm khoảng cách nhỏ nhất của 2 phần tử trong mảng X
  • Độ phức tạp: O(n²) với n là số phần tử trong mảng X
C++

// Hàm heapify giúp xây dựng heap từ mảng
void heapify(vector<int>& X, int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;  // chỉ số con trái
    int right = 2 * i + 2; // chỉ số con phải

    if (left < n && X[left] < X[smallest])
        smallest = left;

    if (right < n && X[right] < X[smallest])
        smallest = right;

    if (smallest != i) {
        swap(X[i], X[smallest]);
        heapify(X, n, smallest);
    }
}

// Hàm Heapsort để sắp xếp mảng X
void Heapsort(vector<int>& X) {
    int n = X.size();

    // Xây dựng heap từ giữa mảng trở về đầu
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(X, n, i);
    }

    // Lấy phần tử lớn nhất (root) ra và heapify lại mảng
    for (int i = n - 1; i > 0; i--) {
        swap(X[0], X[i]); // Di chuyển phần tử lớn nhất về cuối
        heapify(X, i, 0); // Heapify lại mảng chưa sắp xếp
    }
}

// Hàm Better_A tính khoảng cách nhỏ nhất giữa các phần tử liên tiếp sau khi sắp xếp
int Better_A(vector<int>& X) {
    Heapsort(X); // Sắp xếp mảng X bằng Heapsort
    int d = INT_MAX; // Khởi tạo d với giá trị vô cùng (INT_MAX)

    // Duyệt qua các phần tử liên tiếp trong mảng đã sắp xếp
    for (int i = 0; i < X.size() - 1; i++) {
        int diff = abs(X[i] - X[i + 1]); // Tính hiệu giữa 2 phần tử liên tiếp
        if (diff < d) {
            d = diff; // Cập nhật khoảng cách nhỏ nhất
        }
    }

    return d; // Trả về khoảng cách nhỏ nhất
}

Time complexity: O(nlogn + n) = O(nlogn)
Space complexity: O(n)
với n là số phần tử trong mảng X

Đề 5 :

Đáp án

Lưu ý:

  • index bắt đầu từ 1
  • n >> m
  • T[1..n], P[1..m]
  • Đếm số lần xuất hiện của P trong T

1. Phân tích cấu trúc thuật toán:

Thuật toán sử dụng hai vòng lặp lồng nhau:

  • Vòng lặp ngoài (for i = 1 to n – m + 1): Duyệt qua từng vị trí bắt đầu có thể của chuỗi P trong văn bản T
  • Vòng lặp trong (while j < m && P[1+j] == T[i+j]): Kiểm tra xem chuỗi P có khớp với đoạn văn bản bắt đầu từ vị trí i của T hay không

2. Độ phức tạp từng phần:

  • Vòng lặp ngoài thực hiện O(n – m + 1) ≈ O(n) lần lặp (vì n ≫ m)
  • Vòng lặp trong thực hiện O(m) phép so sánh ký tự trong trường hợp xấu nhất

3. Tổng độ phức tạp:

Trường hợp xấu nhất:

  • Mỗi lần lặp của vòng ngoài, vòng trong chạy đủ m lần
  • Tổng số phép so sánh: O(n * m)
  • Ví dụ: T = “AAAAA…” và P = “AAA”

Trường hợp tốt nhất:

  • Chuỗi P không xuất hiện trong T, và mỗi lần kiểm tra chỉ mất O(1)
  • Tổng số phép so sánh: O(n)

Trường hợp trung bình:

  • Phụ thuộc vào dữ liệu, nhưng thường gần với O(n * m) do cần duyệt qua nhiều ký tự
Trường hợpĐộ phức tạp
Tốt nhấtO(n)
Xấu nhất/Trung bìnhO(n * m)

Đề 6 :

Lưu ý đề troll:

t, h, k, t, j, i thật sự không ảnh hưởng gì tới độ phức tạp thuật toán tại nó không ảnh hướng tới n.

Phân tích vòng lặp:

  • Vòng lặp while chạy cho đến khi n = 0
  • Mỗi lần lặp, n bị chia đôi (n = n / 2), tức là giá trị của n giảm theo cấp số nhân cơ số 2
  • Do đó, số lần lặp sẽ tương ứng với số lần cần chia n cho 2 để giá trị của nó đạt 0, hay bằng log₂(n) (làm tròn xuống)

1. Phép toán trong vòng lặp:

  • Trong mỗi lần lặp, các phép gán, kiểm tra điều kiện, và tính toán đều có độ phức tạp O(1)

2. Tổng độ phức tạp:

  • Số lần lặp là log₂(n), mỗi lần lặp có độ phức tạp O(1)
  • Do đó, tổng độ phức tạp của hàm là O(log n)

Đề 7 :

1. Số bước cần thực hiện:

  • Nếu chèn phần tử mới vào vị trí i, tất cả các phần tử từ vị trí i đến n−1 phải dịch chuyển sang phải một vị trí
  • Số phần tử cần dịch chuyển là n−i
  • Sau khi dịch chuyển, cần thêm 1 bước để gán phần tử mới vào vị trí i

2. Tổng số bước:

(n−i)+1

3. Trường hợp tốn ít bước nhất:

  • Khi i = n (thêm vào cuối mảng), không cần dịch chuyển phần tử nào
  • Chỉ cần 1 bước để gán phần tử mới

4. Tổng số bước trong trường hợp này:

n−n+1 = 1

Đề 7 :

Do a với b không ảnh hưởng tới loop dừng khi nào nên:

  • Time complexity: O(N+M)
  • Space Complexity: O(1)

Đề 8 :

a. Thực hiện phép nhân giữa hai số a,b

Chạy tay với a = 5, b = 7:

abTrả về
57return 7 + 2 * 14 = 35 (kết quả cuối cùng)
27return 2*7 = 14
17return 7 + 2*0 = 7
07return 0

b. Độ phức tạp:

  • Độ phức tạp theo thời gian: Base case là khi a = 0. Mỗi lần gọi đệ quy thì a sẽ thành a/2 nếu a chẵn hoặc (a-1)/2 nếu a lẻ. Nên thuật toán sẽ chạy 1 + log₂(a) (làm tròn xuống) lần.
  • Độ phức tạp theo không gian: Do gọi đệ quy log₂(a) lần nên không gian ngăn xếp cũng là log₂(a)

Kết luận:

  • Time complexity: O(log(a))
  • Space complexity: O(log(a))

Đề 8 :

Kiến thức

Đề 9 :

Hàm fast power dùng phương pháp chia để trị để tính lũy thừa x^n. Tuy nhiên cách triển khai hiện tại không tối ưu do gọi đệ quy hai lần cùng một giá trị n/2, dẫn đến phải tính toán lặp đi lặp lại.

Phân tích:

Với mỗi lần gọi, hàm tạo ra 2 lần đệ quy với n/2:

  • T(n) = 2*T(n/2) + O(1) (O(1) ở đây là base case)

Cải tiến:

Làm sao để tối ưu?

Tôi sẽ định dạng lại nội dung cho WordPress và sửa các lỗi nhỏ (nếu có):

Đề 10 :

Phân tích độ phức tạp theo thời gian:
  • Đầu tiên là vòng lặp ở ngoài luôn có độ phức tạp là O(m) do để sort được m số cuối thì luôn phải so sánh m số đó
Tiếp theo là vòng lặp ở trong:
  • Trường hợp xấu nhất: Các phần tử trong m phần tử cuối cần được chèn vào đầu của phần đã sắp xếp
  • Số phép so sánh cho mỗi phần tử thứ k:
  • Khi chèn phần tử thứ k thuộc m phần tử cuối, phần đã sắp xếp có kích thước n+k-1
  • Số phép so sánh tối đa n+k-1 hay n+m-1
Kết luận:

Cuối cùng dùng công thức nhân: O((m+n)*m)

Đề 10 :

Khi n = 10:

  • Vòng loop ngoài sẽ thực hiện 10 lần
  • Vòng loop trong thì:
  • khi i bắt đầu từ 0 thì j bắt đầu từ 0 -> thực hiện 10 lần
  • khi i bắt đầu từ 1 thì j bắt đầu từ 1 -> thực hiện 9 lần
  • khi i bắt đầu từ 9 thì j bắt đầu từ 9 -> thực hiện 1 lần

Vậy tổng số lần thực hiện hay S+=1 được gọi là 10*(1+2+…+10)

Đề 11 :

Bài này gặp rồi, tương tự thôi.

Đề 12 :

Lưu ý:

Có thể sai đề: tại ngay vòng while, j– không thấy ràng buộc j > 0 nên j có thể âm vô lý.
Ta sẽ giải theo đề đã sửa:

1. Hàm do_st():

  • Kiểm tra xem có tồn tại hai phần tử trong mảng arr[] sao cho tổng của chúng bằng giá trị S cho trước
  • Nếu tìm thấy, hàm trả về true và gán chỉ số của hai phần tử đó vào x1 và x2
  • Ngược lại, trả về false

2. Độ phức tạp thời gian của hàm do_st():

Ký hiệu Big-O: O(n)

Giải thích:

  • Vòng lặp for chạy từ i = 0 đến i < j, với j khởi tạo là n – 1
  • Trong mỗi lần lặp, j giảm tối đa n lần, nhưng mỗi phần tử chỉ được duyệt một lần
  • Tổng số phép so sánh và dịch chuyển con trỏ là O(n)

3. Độ phức tạp khi dùng hàm sort:

Nếu thuật toán sắp xếp O(n log n) (như merge, heap sort):

  • O(n) + O(nlogn) = O(nlogn)

Nếu thuật toán sắp xếp O(n²) (như interchange, insertion sort):

  • O(n) + O(n²) = O(n²)

Còn counting sort thì:

  • O(n) + O(n+k) = O(n+k)
  • Với n là số phần tử, k là số lớn nhất trong mảng

Đề 13 :

Câu 7 : Độ phức tạp là O(n^3)

Câu 8 :
Lời giải: Để so sánh các độ phức tạp, ta xếp theo thứ tự tăng dần: O(nlogn) < O(n⁴) < O(2ⁿ) < O(n!)

Vậy O(n!) là độ phức tạp lớn nhất.

Câu 9 : Định Nghĩa :

Bubble Sort là thuật toán sắp xếp đơn giản:

  • Liên tục so sánh và hoán đổi hai phần tử liền kề nếu chúng không đúng thứ tự
  • Quá trình lặp lại cho đến khi không còn cặp phần tử nào cần hoán đổi
  • Độ phức tạp: O(n²) trong mọi trường hợp
  • Không gian phụ trợ: O(1)
  • Là thuật toán sắp xếp ổn định (stable sort)

Đề 14 :

Câu 3: Độ phức tạp của thao tác thêm một phần tử vào mảng

Khi thêm một phần tử vào mảng, độ phức tạp phụ thuộc vào vị trí chèn:

Phân tích chi tiết:

  • Nếu chèn vào cuối mảng: O(1) – chỉ cần một phép gán
  • Nếu chèn vào đầu hoặc giữa mảng: O(n) – cần phải dịch chuyển các phần tử phía sau để tạo chỗ trống
  • Trường hợp xấu nhất là O(n) khi phải chèn vào vị trí đầu và dịch tất cả phần tử sang phải
Câu 4: Độ phức tạp của thao tác xoay cây AVL tại vị trí mất cân bằng

Phân tích:

  • Thao tác xoay AVL (cả trái và phải) có độ phức tạp là O(1)
  • Lý do: Chỉ cần thực hiện một số phép gán cố định để tái cấu trúc cây tại vị trí xoay
  • Tuy nhiên, việc xác định điểm mất cân bằng có thể tốn O(logn) khi duyệt từ điểm chèn lên gốc
Câu 5: Độ phức tạp của thao tác tìm kiếm tuần tự

Phân tích:

  • Trường hợp tốt nhất: O(1) – phần tử cần tìm nằm ở đầu mảng
  • Trường hợp xấu nhất: O(n) – phải duyệt hết mảng mới tìm thấy hoặc không tìm thấy
  • Trường hợp trung bình: O(n/2) = O(n) – trung bình phải duyệt nửa mảng

Trong đó n là số phần tử của mảng. Độ phức tạp không gian là O(1) vì chỉ cần một số biến phụ trợ cố định.

Đề 15 :

Phần 1: Phân tích cấu trúc vòng lặp

Đoạn code có 3 vòng lặp lồng nhau:

for (i = 1; i ≤ n; i++)
    for (j = 1; j ≤ i * i; j++)
        for (k = 1; k ≤ j; k++)
            sum++;

Để tính số lần thực hiện phép toán sum++, ta cần phân tích từ trong ra ngoài:

Phần 2: Phân tích vòng lặp trong cùng (k)

Vòng lặp k chạy từ 1 đến j:

for (k = 1; k ≤ j; k++)
    sum++;

Số lần thực hiện = j

Phần 3: Phân tích vòng lặp giữa (j)

Vòng lặp j chạy từ 1 đến i*i:

for (j = 1; j ≤ i * i; j++)

Với mỗi j, ta có j lần thực hiện từ vòng lặp k.
Tổng số lần thực hiện = 1 + 2 + 3 + … + (i * i) = (i*i)(i*i + 1)/2 = (i⁴ + i²)/2

Phần 4: Phân tích vòng lặp ngoài cùng (i)

Vòng lặp i chạy từ 1 đến n:

for (i = 1; i ≤ n; i++)

Với mỗi i, ta có (i⁴ + i²)/2 lần thực hiện từ hai vòng lặp trong.

Tổng số phép toán = ∑(i=1 đến n) (i⁴ + i²)/2
= (1/2)[∑(i=1 đến n) i⁴ + ∑(i=1 đến n) i²]

Phần 5: Sử dụng công thức trong chú ý

Theo chú ý: ∑(i=1 đến n) i^k ≈ (n^(k+1))/(k+1)

Áp dụng cho i⁴:

  • ∑(i=1 đến n) i⁴ ≈ n⁵/5

Áp dụng cho i²:

  • ∑(i=1 đến n) i² ≈ n³/3

Phần 6: Kết luận độ phức tạp

Tổng số phép toán = (1/2)[n⁵/5 + n³/3]
= (n⁵/10 + n³/6)

Do n⁵ là số hạng có bậc cao nhất, nên độ phức tạp của thuật toán là O(n⁵).

Giải thích thêm:

Vì vậy, ta có thể bỏ qua các số hạng có bậc thấp hơn và kết luận độ phức tạp là O(n⁵)

Khi n lớn, số hạng n⁵ sẽ chiếm ưu thế và lớn hơn rất nhiều so với n³

Các hệ số như 1/10 không ảnh hưởng đến ký hiệu Big-O

Đề 16 :

Đề 17 :

Đề 18 :

Tôi sẽ phân tích độ phức tạp trong trường hợp xấu nhất cho từng công việc:

1. Kiểm tra dãy số có phải là max-heap

Độ phức tạp: O(N)
Giải thích: Để kiểm tra max-heap, ta cần duyệt qua tất cả các nút và so sánh với các nút con. Mỗi phần tử cần được kiểm tra một lần, nên ta cần duyệt qua N phần tử.

2. Kiểm tra dãy không giảm

Độ phức tạp: O(N)
Giải thích: Ta cần duyệt qua toàn bộ dãy và so sánh từng cặp phần tử liền kề để đảm bảo a[i] ≤ a[i+1]. Việc này đòi hỏi duyệt qua N phần tử một lần.

3. Hiển thị phần tử cuối cùng của mảng

Độ phức tạp: O(1)
Giải thích: Truy cập trực tiếp vào phần tử cuối cùng của mảng chỉ cần một phép toán, không phụ thuộc vào kích thước mảng.

4. Lấy phần tử ra khỏi hàng đợi

Độ phức tạp: O(N)
Giải thích: Trong trường hợp xấu nhất của hàng đợi dùng mảng, khi lấy phần tử đầu ra, ta phải dịch chuyển tất cả các phần tử còn lại lên một vị trí.

5. Tìm kiếm trên cây nhị phân tìm kiếm

Độ phức tạp: O(N)
Giải thích: Trong trường hợp xấu nhất, cây bị suy biến thành một đường thẳng, ta phải duyệt qua tất cả N phần tử.

6. Xóa phần tử khỏi danh sách liên kết đơn

Độ phức tạp: O(N)
Giải thích: Trong trường hợp xấu nhất, phần tử cần xóa nằm ở cuối danh sách, ta phải duyệt từ đầu đến cuối danh sách để tìm và xóa nó.

7. Hiển thị các khóa chẵn theo chiều giảm dần trên cây AVL

Độ phức tạp: O(N)
Giải thích: Ta cần duyệt qua tất cả các nút của cây để tìm và hiển thị các khóa chẵn. Trong trường hợp xấu nhất, ta phải thăm tất cả N nút.

8. Xác định phần tử nhỏ nhất trên max-heap

Độ phức tạp: O(N)
Giải thích: Trong max-heap, phần tử nhỏ nhất luôn nằm ở các nút lá. Để tìm phần tử nhỏ nhất, ta cần duyệt qua tất cả các nút lá và so sánh chúng, điều này đòi hỏi việc kiểm tra tất cả N phần tử trong trường hợp xấu nhất.

Đề 19 :

Loser1 sẽ giúp bạn giải quyết bài toán sắp xếp chậu cây này một cách chi tiết. Hãy cùng phân tích từng bước:

Bước 1: Phân tích yêu cầu bài toán

  • Ta có n chậu cây cảnh với chiều cao khác nhau
  • Cần sắp xếp lại thành dãy tăng dần theo chiều cao
  • Mục tiêu: Tổng quãng đường di chuyển các chậu cây là ngắn nhất

Bước 2: Xác định phương pháp giải quyết
Để tối ưu quãng đường di chuyển, ta có thể áp dụng phương pháp “Sắp xếp tại chỗ”. Điều này có nghĩa là:

  • Ta sẽ giữ nguyên vị trí các chậu cây và chỉ hoán đổi vị trí giữa các cặp cây khi cần thiết
  • Mỗi lần hoán đổi, ta chọn cặp cây gần nhau nhất có thể để giảm thiểu quãng đường di chuyển

Bước 3: Thuật toán cụ thể

  1. Đánh số vị trí các chậu cây từ 1 đến n
  2. Xác định chiều cao của từng cây và gán nhãn tương ứng với vị trí cuối cùng nó cần đến
  3. Lặp lại các bước sau cho đến khi tất cả các cây đều ở đúng vị trí:
  • Tìm cây đang ở sai vị trí gần nhất
  • Hoán đổi với cây gần nhất mà việc hoán đổi sẽ đưa ít nhất một cây về đúng vị trí

Bước 4: Ví dụ minh họa
Giả sử có 5 chậu cây với chiều cao (đơn vị cm): 30, 15, 25, 10, 20
Vị trí ban đầu: [30] [15] [25] [10] [20]
Vị trí cần đến: [10] [15] [20] [25] [30]

Các bước hoán đổi:

  1. Hoán đổi 30 và 10: [10] [15] [25] [30] [20]
  2. Hoán đổi 30 và 20: [10] [15] [25] [20] [30]
  3. Hoán đổi 25 và 20: [10] [15] [20] [25] [30]

Bước 5: Kết luận
Phương pháp này đảm bảo:

  • Mỗi chậu cây chỉ di chuyển khi thực sự cần thiết
  • Các cây được hoán đổi với cây gần nhất có thể
  • Số lần di chuyển được giảm thiểu
  • Quãng đường di chuyển tổng cộng là ngắn nhất có thể

Đây là cách sắp xếp tối ưu nhất vì nó kết hợp được hai yếu tố:

  1. Đảm bảo thứ tự tăng dần theo yêu cầu
  2. Tối thiểu hóa quãng đường di chuyển thông qua việc ưu tiên hoán đổi các cây ở gần nhau

Quảng đường di chuyển các chậu là ngắn nhất -> số lần di chuyển ít nhất -> selection sort

Đề 20 :

Loser1 sẽ giải thích thuật toán Knuth-Morris-Pratt (KMP) thông qua code C++ và phân tích độ phức tạp của nó:

C++
// Thuật toán KMP dùng để tìm kiếm mẫu P trong chuỗi văn bản T
void computeLPSArray(string pattern, int M, int* lps) {
    int len = 0;  // Độ dài của tiền tố-hậu tố trùng nhau trước đó
    lps[0] = 0;   // lps[0] luôn bằng 0

    int i = 1;
    while (i < M) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPSearch(string pattern, string text) {
    int M = pattern.length();
    int N = text.length();

    // Tạo mảng lps[] để lưu độ dài tiền tố-hậu tố dài nhất
    int lps[M];
    computeLPSArray(pattern, M, lps);

    int i = 0;  // index cho text
    int j = 0;  // index cho pattern
    while (i < N) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }
        if (j == M) {
            cout << "Tìm thấy mẫu tại vị trí " << i - j << endl;
            j = lps[j - 1];
        }
        else if (i < N && pattern[j] != text[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

Phân tích độ phức tạp:

  1. Tiền xử lý (computeLPSArray):
  • Tạo mảng lps[] chứa thông tin về tiền tố-hậu tố dài nhất
  • Độ phức tạp: O(M), với M là độ dài của mẫu cần tìm
  • Không gian phụ trợ: O(M) cho mảng lps[]
  1. Tìm kiếm (KMPSearch):
  • Duyệt qua văn bản một lần duy nhất
  • Độ phức tạp: O(N), với N là độ dài văn bản
  • Mỗi ký tự trong văn bản chỉ được xét một lần
  • Không có quay lui như thuật toán naive
  1. Tổng độ phức tạp:
  • Thời gian: O(M + N)
    • O(M) cho tiền xử lý
    • O(N) cho tìm kiếm
  • Không gian: O(M) cho mảng lps[]
  1. So sánh với thuật toán naive (vét cạn):
  • Naive: O(M*N) trong trường hợp xấu nhất
  • KMP: O(M + N) trong mọi trường hợp
  • KMP hiệu quả hơn nhiều khi chuỗi văn bản dài và có nhiều trường hợp khớp một phần
  1. Ưu điểm của KMP:
  • Không cần quay lui trong văn bản
  • Sử dụng thông tin từ những lần so khớp trước
  • Hiệu quả với mọi loại dữ liệu đầu vào
  • Đặc biệt tốt khi tìm kiếm mẫu xuất hiện nhiều lần trong văn bản

KMP là một ví dụ điển hình về cách cải thiện độ phức tạp thời gian bằng cách sử dụng thêm một chút bộ nhớ và tiền xử lý thông minh.

quyminhhuy0@gmail.com
quyminhhuy0@gmail.com
Articles: 39

Newsletter Updates

Enter your email address below and subscribe to our newsletter

Subscribe
Notify of
guest

0 Comments
Inline Feedbacks
View all comments
AI Assistant
Hi! How can I help you today?
Adidas fleece hoodie. Heavy equipment transport pinellas fl.