Phân tích giải thuật

Đặt vấn đề

Độ phức tạp thuật toán là một khái niệm quen thuộc với hầu hết các lập trình viên. Tuy nhiên, bạn đã bao giờ tự hỏi:

• Tại sao vòng lặp for có độ phức tạp $O(n)$?
• Hai vòng lặp for lồng nhau thì có độ phức tạp $O(n^2)$?
• Đoạn code này thì chạy mất bao lâu?

Thực ra thì ý niệm về thời gian chạy của công việc tính toán đã có từ rất lâu rồi, ít nhất là từ thời của Babbage. Ông từng nói:

Khi một máy phân tích xuất hiện, nó nhất định sẽ định hướng sự phát triển của khoa học trong tương lai. Mỗi khi một kết quả được tìm kiếm với sự hỗ trợ của nó, câu hỏi sẽ được đặt ra: Bằng cách tính toán nào mà máy tính có thể đạt được những kết quả này trong thời gian ngắn nhất?

Máy phân tích của Babbage có một cái tay quay. Khi ông quan tâm đến thời gian chạy của máy, thực ra ông muốn biết cần quay tay bao nhiêu lần để hoàn thành tính toán. Ngày nay, mặc dù cái tay quay đã được thay thế bằng các phép tính xảy ra hàng tỷ lần mỗi giây, nhưng mấu chốt vẫn là: chúng ta quan tâm đến việc cần thực hiện bao nhiêu thao tác rời rạc để hoàn thành một công việc tính toán.

Bằng những cách tiếp cận tương tự như vậy thì các nhà khoa học phát triển một phương pháp có tên là Scientific method để giải quyết vấn đề này. Scientific method bao gồm các bước cơ bản sau:

• Observe quan sát thời gian chạy chương trình.
• Hypothesize đưa ra một mô hình phù hợp với quan sát.
• Predict đưa ra các tiên đoán dựa trên giả thuyết.
• Verify kiểm chứng các tiên đoán đó bằng thực nghiệm.
• Validate lặp lại quá trình cho đến khi quan sát và giả thuyết có kết quả tương đồng.

Three-Sum

Hãy xem xét một ví dụ cụ thể: bài toán Three-Sum. Bài toán yêu cầu tìm số bộ ba số trong một danh sách sao cho tổng của chúng bằng 0.

Ví dụ với 8 số nguyên:

8
30 -40 -20 -10 40 0 10 5

Bằng mắt thường ta có thể thấy được có 4 bộ ba số có tổng bằng 0.

Mục tiêu là viết một chương trình tính số bộ ba đó cho một danh sách bất kỳ. Phương pháp đơn giản nhất là brute-force.

    public int count(int[] a) {
        int n = a.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = j+1; k < n; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

Tiếp theo, chúng ta quan tâm đến thời gian chạy của hàm trên. Bạn có thể dùng đồng hồ bấm giờ, điện thoại hoặc một công cụ đo thời gian để thử nghiệm.

Dễ thấy rằng, mỗi khi tăng gấp đôi kích thước input, thời gian thực thi tăng lên đáng kể. Điều này có thể biểu diễn bằng một đồ thị với trục Y là thời gian chạy và trục X là kích thước input.

Để dễ dàng hơn trong việc phân tích, chúng ta vẽ đồ thị log-log. Trong biểu đồ này, đường thẳng có độ dốc bằng 3 cho thấy hàm thời gian chạy tỷ lệ với $n^3$.

$\lg{T(n)} = b\lg{n} + c$

$T(n) = an^{b} 　　với\;a = 2^{c}$

Thực ra, nếu áp dụng quy tắc hàm mũ (power law), bạn cũng sẽ có kết quả tương tự. Khi bạn có một đường thẳng với độ dốc $b$, hàm của bạn sẽ tỷ lệ thuận với $a*n^{b}$. Điều bạn cần làm là mỗi lần nhân đôi kích thước input và tính tỷ lệ thời gian chạy cho $n$ và $2n$. Tỷ lệ này sẽ hội tụ về một hằng số. Thực tế, log của tỷ lệ đó cũng hội tụ về một hằng số, và đó chính là số mũ của $n$ trong hàm thời gian chạy.

Vấn đề tiếp theo là ta cần ước lượng $a$. Vậy làm thế nào để ước lượng $a$? Để xác định hằng số $a$, chúng ta chỉ cần chạy thực nghiệm và giải phương trình.

Sau khi đã xác định số mũ $b = 3$, chúng ta có thể chạy thử nghiệm với giá trị $N$ lớn và so sánh kết quả với dự đoán từ mô hình đã vẽ đồ thị.

Từ giả thuyết này, chúng ta có thể dễ dàng dự đoán thời gian chạy cho các input 16000 và 32000.(Hãy thử ước lượng thời gian và kiểm chứng nhé)

Tuy nhiên, trong thực tế, có rất nhiều yếu tố ảnh hưởng đến thời gian chạy của chương trình. Các yếu tố độc lập với máy tính như thuật toán và dữ liệu bạn chạy là những yếu tố quyết định số mũ $b$ trong hàm mũ. Các yếu tố phụ thuộc vào hệ thống như phần cứng, phần mềm, và các chương trình đang chạy trên máy tính của bạn là những yếu tố quyết định hằng số $a$ trong hàm mũ.

Các mô hình toán học

Quan sát hiện tượng chỉ cho phép chúng ta tiên đoán hiệu năng, nhưng không giúp hiểu rõ thuật toán. Vì vậy, ta cần đến các mô hình toán học.

Khái niệm này được phát triển bởi Don Knuth vào cuối thập niên 60. Knuth đề xuất rằng chúng ta có thể tính tổng thời gian chạy của một chương trình bằng cách xác định các thao tác cơ bản, tính chi phí của chúng, và nhân với tần suất thực thi.

Ví dụ, với bài toán one-sum (tìm số lượng số bằng 0 trong một danh sách):

Như vậy là chỉ cần một vòng for, ta duyệt tuần tự và kiểm tra xem, nếu số đó bằng 0 thì sẽ tăng biến count.

    int count = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 0)
            count++;
    }

Phân tích đoạn code trên một chút. Chúng ta có:

• Có $n+1$ phép so sánh giữa $i$ với $n$.
• Có $n$ phép so sánh giữa $a[i]$ với 0.
• Có $n$ lần truy nhập mảng $a[]$

Phân tích tương tự cho bài toán two-sum (tìm số lượng cặp số có tổng bằng 0):

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i +1; j < n; j++) {
            if (a[i] + a[j] == 0)
                count++;
        }
    }

Trong đoạn code này, biến $i$ và $j$ được khởi tạo và gán giá trị $n$ lần. Số phép so sánh và truy cập mảng có thể tính toán dựa trên tần suất thực thi.

Phép so sánh bằng 0 có vẻ phức tạp hơn một chút. Ta có thể thấy rằng mỗi lần lệnh if chạy thì có hai lần truy cập mảng và một lần so sánh bằng 0. Vậy lệnh if được chạy bao nhiêu lần?

$n - 1$ lần ở lần lặp thứ nhất,

$n - 2$ lần ở lần lặp thứ 2,

$\vdots$

và 0 lần ở lần lặp cuối cùng.

⇒ có $\frac{n(n-1)}{2}$ phép if. Nghĩa là có $n(n-1)$ lần truy nhập mảng, và $\frac{n(n-1)}{2}$ phép so sánh bằng 0.

Tương tự như vậy, ta có thể tính được số phép so sánh nhỏ hơn là: $\frac{(n + 1)(n + 2)}{2}$

Số lần chạy phép ++ thì cũng không cố định, nhưng nó giao động trong khoảng từ $\frac{n(n - 1)}{2}$ đến $n(n - 1)$.

Với những bài toán đơn giản như one-sum, two-sum thì chúng ta có thể dễ dàng thống kê được tần suất của các thao tác cơ bản. Tuy nhiên, với những bài toán phức tạp hơn, việc đếm các thao tác cơ bản sẽ trở nên khó khăn. Vậy câu hỏi đặt ra là: Có cần thiết phải đếm tất cả các thao tác cơ bản? Điều này tương tự như thống kê. Khi tập mẫu đủ lớn, không cần phải tính toán toàn bộ dữ liệu. Ở đây cũng vậy, khi ước lượng thô là đủ tốt thì không cần phải tính toán đầy đủ tất cả các phép toán cơ bản. Dĩ nhiên, bạn vẫn có thể đếm từng thao tác, đặt trọng số và cộng chúng lại. Nhưng thực tế, người ta chỉ cần đếm những thao tác chạy chậm nhất (có chi phí cao nhất hoặc được thực hiện nhiều lần nhất). Trong bài toán two-sum, thao tác được thực hiện nhiều nhất là truy cập mảng, với tần suất $n(n-1)$ lần.

Ok, đến đây ta có $n(n-1)$, vậy $O(n^{2})$ nó nằm ở đâu?

Trong thực tế thì người ta sẽ làm thêm một bước đơn giản hóa mô hình toán học. Bước đó gọi là tilde notation. Tạm dịch là lấy xấp xỉ. Trong bước này ta sẽ bỏ qua các hệ số bậc thấp hơn trong công thức.

Tại sao lại vậy?

Vì hàm $n(n-1)$ và $n^{2}$ có sự sai khác không quá lớn, nên chúng ta sẽ xét đến cặp hàm số: $f(n) = n^{3} + 100n + 10$ và $g(n) = n^{3}$

Với $n$ nhỏ thì ta có thế thấy sự khác biệt về giá trị của 2 hàm này tương đối lớn. Nhưng chúng ta không quan tâm đến $n$ nhỏ, vì chúng ta đang cần ước lượng thời gian chạy cho $n$ lớn. Khi $n$ nhỏ thì thời gian chạy cũng không đáng kể.

Khi $n$ lớn, giá trị của chúng dần tiến lại gần nhau. Khi đó, $f(n) \sim g(n)$ hay $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)} = 1$.

Quay lại với bài toán two-sum, khi này ta sẽ có $n(n-1) \sim n^{2}$. Như vậy, với mô hình chi phí và phép xấp xỉ, ta có thể ước lượng thời gian chạy của chương trình two-sum là $an^{2}$ với $a$ là hằng số.

Trong thực tế có rất nhiều cách tính xấp xỉ(cái này liên quan nhiều đến giải tích và toán rời rạc), nhưng người ta hay sử dụng Euler–Maclaurin formula. Khi đó thì ta có thể thừa nhận một số kết quả:

Hay ba vòng for lồng nhau như trong bài toán three-sum sấp xỉ với $\frac{n^{3}}{6}$

Kết luận

Như Knuth đã nói, tồn tại các mô hình toán học chính xác cho thuật toán. Tuy nhiên, trong thực tế, các mô hình xấp xỉ đủ dùng để mô tả thời gian chạy. Đôi khi, chúng ta sử dụng toán học để chứng minh, nhưng đôi khi chỉ cần trích dẫn công trình của các chuyên gia.

Dự liệu test cho bài toán three-sum: 1K-ints 2K-ints 4K-ints 8K-ints 16K-ints 32K-ints 1M-ints Nguồn tham khảo: Analysis of Algorithms