Thuật toán và độ phức tạp: câu hỏi luyện tập có giải thích

1Độ phức tạp đo cái gì

Thuật toán là một danh sách hữu hạn các bước chính xác để giải một bài toán, chẳng hạn sắp xếp một danh sách hoặc tìm một cái tên trong danh bạ.

Hai thuật toán có thể giải cùng một bài toán nhưng mất lượng thời gian rất khác nhau. Độ phức tạp mô tả khối lượng công việc tăng thế nào khi dữ liệu đầu vào lớn lên.

Kích thước của đầu vào được gọi là n: số phần tử cần sắp xếp, độ dài của một danh sách, số nút trong một đồ thị.

Hãy hình dung việc tìm một cái tên trong danh bạ 1000 trang. Đọc từng trang mất tới 1000 bước. Mở giữa cuốn sách rồi chia đôi mỗi lần chỉ mất khoảng 10 bước.

Độ phức tạp thời gian đếm số bước. Độ phức tạp không gian đếm lượng bộ nhớ phụ. Cả hai đều được viết như một hàm của n.

Thông thường người ta xét trường hợp xấu nhất: khối lượng công việc lớn nhất trên mọi đầu vào cỡ n. Đôi khi đề hỏi trường hợp trung bình hoặc trường hợp tốt nhất.

2Big O và các lớp tăng trưởng

Ký hiệu Big O chỉ giữ lại điều quan trọng với n lớn. Bạn bỏ các hệ số hằng và chỉ giữ số hạng tăng nhanh nhất.

Với n = 1000, số hạng n² là 3 000 000, trong khi 5n chỉ là 5000. Các số hạng nhỏ hơn hầu như không làm thay đổi tổng.

Các lớp này xuất hiện lặp đi lặp lại, xếp từ tăng trưởng chậm nhất đến nhanh nhất:

• O(1), hằng số: đọc một phần tử mảng theo chỉ số của nó.
• O(log n), logarit: tìm kiếm nhị phân, chia đôi bài toán ở mỗi bước.
• O(n), tuyến tính: một lượt duyệt qua mọi phần tử, chẳng hạn tìm giá trị lớn nhất.
• O(n log n): các thuật toán sắp xếp tốt như sắp xếp trộn (merge sort).
• O(n²), bậc hai: hai vòng lặp lồng nhau trên các phần tử, như sắp xếp nổi bọt (bubble sort).
• O(2ⁿ), hàm mũ: thử mọi tập con. Nó nhanh chóng trở nên không dùng được.

Big O là một cận trên: khối lượng công việc tăng nhiều nhất là nhanh như vậy. Ω (Big Omega) là cận dưới, còn Θ (Theta) là cận chặt, vừa là cận trên vừa là cận dưới.

Cơ số của logarit không quan trọng trong Big O, vì các logarit với cơ số khác nhau chỉ khác nhau một hệ số hằng.

3Tìm kiếm, sắp xếp và đệ quy

Một vài thuật toán xuất hiện trong hầu hết mọi khóa học. Hãy học độ phức tạp của chúng như những sự kiện.

• Tìm kiếm tuyến tính kiểm tra từng phần tử một: O(n). Tìm kiếm nhị phân cần một mảng đã sắp xếp và chia đôi phạm vi ở mỗi bước: O(log n).
• Sắp xếp nổi bọt, chèn và chọn so sánh và hoán đổi các phần tử trong các vòng lặp lồng nhau: O(n²). Sắp xếp chèn là O(n) trên mảng đã được sắp xếp.
• Sắp xếp trộn chia mảng làm đôi, sắp xếp từng nửa rồi trộn lại: O(n log n) trong mọi trường hợp, với O(n) bộ nhớ phụ.
• Sắp xếp nhanh (quicksort) chia quanh một phần tử chốt: O(n log n) trung bình, nhưng O(n²) trong trường hợp xấu nhất, chẳng hạn mảng đã sắp xếp với phần tử đầu làm chốt.
• Không có thuật toán sắp xếp nào chỉ dựa vào so sánh có thể vượt qua Ω(n log n) trong trường hợp xấu nhất. Sắp xếp đếm nhanh hơn vì nó không so sánh.

Một hàm đệ quy tự gọi chính nó trên đầu vào nhỏ hơn cho đến khi gặp trường hợp cơ sở mà nó trả lời trực tiếp. Thời gian chạy của nó được viết bằng một hệ thức truy hồi:

• T(n) = T(n/2) + O(1) cho O(log n), như tìm kiếm nhị phân.
• T(n) = 2T(n/2) + O(n) cho O(n log n), như sắp xếp trộn.
• T(n) = T(n − 1) + O(n) cho O(n²).
• T(n) = 2T(n − 1) + O(1) cho O(2ⁿ).

Ba ý tưởng thiết kế đáng biết. Chia để trị chia nhỏ, giải và kết hợp. Tham lam chọn lựa tốt nhất cục bộ ở mỗi bước. Quy hoạch động lưu đáp án của các bài toán con chồng lấn để chúng chỉ được tính một lần.

4Phương pháp từng bước

Để tìm độ phức tạp thời gian của một đoạn mã:

1. Xác định n là gì: kích thước của đầu vào.
2. Đếm mỗi vòng lặp chạy bao nhiêu lần. Vòng lặp cộng thêm 1 mỗi lần chạy khoảng n lần. Vòng lặp nhân đôi hoặc chia đôi chạy khoảng log₂ n lần.
3. Các vòng lặp lồng nhau thì nhân. Các vòng lặp nối tiếp nhau thì cộng.
4. Với hàm đệ quy, hãy viết hệ thức truy hồi: có bao nhiêu lời gọi, trên kích thước nào, cộng với công việc của mỗi lời gọi.
5. Giữ số hạng tăng nhanh nhất và bỏ các hằng số.
6. Kiểm tra với một số nhỏ, chẳng hạn n = 8 hoặc n = 1024.

Với câu hỏi lý thuyết, trước hết hãy gọi tên thuật toán hoặc ý tưởng mà nó mô tả, rồi nhớ lại độ phức tạp và các điều kiện của nó (đầu vào đã sắp xếp, trọng số không âm, bài toán con chồng lấn).

5Một ví dụ có lời giải

Theo dõi từng bước. Hãy thử đoán bước tiếp theo trước khi mở nó.

6Lỗi thường gặp

• Nhân các vòng lặp chạy nối tiếp nhau. n + n = 2n vẫn là O(n).
• Giữ lại hằng số, như O(2n) hay O(n/2). Cả hai đều là O(n).
• Coi vòng lặp nhân đôi là n vòng. Nó chạy khoảng log₂ n lần.
• Dùng tìm kiếm nhị phân trên dữ liệu chưa sắp xếp, hoặc trên danh sách liên kết mà phần tử giữa không thể truy cập trong một bước.
• Nêu trường hợp trung bình của quicksort khi đề hỏi trường hợp xấu nhất.
• Nghĩ rằng Big O nghĩa là “chính xác”. O(n²) là một cận trên; Θ(n²) mới là tốc độ tăng chính xác.

7Các câu hỏi thi trông như thế nào

• Dễ: thuật ngữ và sự kiện chính. Độ phức tạp của tìm kiếm nhị phân, sắp xếp trộn hay truy cập mảng, ý nghĩa của O, Ω và Θ, đệ quy là gì.
• Trung bình: vận dụng khái niệm. Độ phức tạp của một đoạn mã, một hệ thức truy hồi cần giải, thời gian thay đổi thế nào khi n tăng gấp đôi, thuật toán nào phù hợp với một tác vụ.
• Khó: ca bài tập và phân tích. Định lý thợ (master theorem), các trường hợp xấu nhất của quicksort, tham lam so với quy hoạch động, và các lớp P, NP và NP-đầy đủ.

P gồm các bài toán có thể giải trong thời gian đa thức. NP gồm các bài toán mà lời giải có thể được kiểm tra trong thời gian đa thức. Mọi bài toán thuộc P đều thuộc NP; việc P = NP hay không vẫn chưa được biết.