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

- 17 mins

Đặt vấn đề

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

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 như sau:

As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise: By what course of calculation can these results be arrived at by the machine in the shortest time? Charles Baddage

Có thể tạm dịch như sau:

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

Analytic Engine

Máy phân tích của Baddage có một cái tay quay. Khi Babbage quan tâm đến thời gian chạy của cái máy, thực ra cái ông muốn biết là ta phải quay tay bao nhiêu lần(là quay cái tay quay của máy phân tích nhé). Và ngay nay thì cũng không khác là mấy. Cái tay quay được thay thế bằng cái gì gì xảy ra cả tỷ lần 1 giây. Nhưng mấu chốt là chúng ta vẫn quan tâm xem phải thực hiện một thao tác rời rạc nào đó bao nhiêu lần để 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 đã đưa ra một phương pháp có tên là Scientific method để giải quyết vấn đề này. Việc này có thể không làm hé lộ các bí mật mới của vũ trụ, nhưng ta có thể dùng Scientific method và coi máy tính như đối tượng nghiên cứu để dẫn đến hiểu biết về việc chương trình của ta sẽ cho hiệu năng ra sao.

Scientific method có một số nguyên lý cơ bản sau:

Three-Sum

Trước tiên ta lấy ví dụ một bài toán có tên là three-sum(sum chứ không phải some nhé :troll:). Bài toán được phát biểu như sau: Nếu ta có N số nguyên khác nhau, có bao nhiêu bộ ba số có tổ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.

a[i] a[j] a[k] sum
30 -40 10 0
30 -20 -10 0
-40 40 0 0
-10 0 10 0

Mục tiêu của ta là viết một chương trình tính số bộ ba đó cho file input bất kì, cho bộ N số bất kì. Đây là bài toán vô cùng quan trọng trong thực tế (liên quan đến các vấn đề trong computational geometry), nhưng lại là bài toán dễ viết code. Cách đơn giản nhất có lẽ 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, cái mà ta quan tâm là thời gian chạy của hàm trên là bao nhiêu? Bước này mình xin phép được bỏ qua mà chỉ đưa ra kết quả. Bạn có thể dùng đồng hồ bấm giờ, điện thoại hoặc một thứ gì đó có thể đo thời gian để thử nhé.

n time (seconds)
250 0.0
500 0.0
1000 0.1
2000 0.8
4000 6.4
8000 51.1
16000 ???

Ta có thể dễ dàng nhận ra mối liên hệ giữa kích thước input và thời gian thực thi. Mỗi lần ta tăng gấp đôi kích thước input thì chắc chắn chương trình chạy lâu hơn. Và từ tập kết quả đó ta dễ dàng vẽ một đồ thị với thời gian chạy là trục Y và kích thước input là trục X. Và kết quả là ta được một đường cong như đồ thì bên trái của hình dưới đây.

three sum

Và thực ra, vì nhiều bài toán nằm trong thể loại này, nên việc mà khoa học thường làm là vẽ đồ thị dạng log-log(như đồ thị bên phải). Nếu ta vẽ đồ thị theo tỉ lệ kiểu này, ta rất hay có được một đường thẳng. Và độ dốc của đường thẳng chính là chìa khóa của thông tin. Trong trường hợp này, đường thẳng có độ dốc bằng 3, bạn có thể dùng phương pháp hồi quy để khớp một đường thẳng qua các điểm dữ liệu.

Dựa vào đồ thị log-log ta sẽ có:

2 lũy thừa cả 2 phía của phương trình ta sẽ được biểu thức tương đương:

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

n time(seconds) ratio lg ratio
250 0.0   -
500 0.0 4.8 2.3
1000 0.1 6.9 2.8
2000 0.8 7.7 2.9
4000 6.4 8.0 3.0
8000 51.1 8.0 3.0

Vấn đề tiếp theo là ta cần ước lượng $a$. Vậy làm thế nào để ước lượng $a$? Ta chỉ việc chạy lấy kết quả rồi giải phương trình ra $a$.

Sau khi đã xác định số mũ $b = 3$, ta hãy chạy cho N lớn nào đó, và ta được kết quả khá gần với dự tính của mô hình mà ta đã vẽ đồ thị.

Từ giả thuyết ta dễ dàng để tiên đoán thời gian chạy cho 16000, 32000 input.(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: thuật toán, dữ liệu mà bạn chạy. Đó là những yếu tố quyết định $b$ trong hàm mũ. Và các yếu tố phụ thuộc hệ thống như: phần cứng, phần mềm, cái gì đang chạy trong 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ũ.

mathematical models

Quan sát hiện tượng như ta đã làm cho phép ta tiên đoán hiệu năng, nhưng nó thực sự không giúp ta hiểu thuật toán đang làm gì. Do đó, tiếp theo ta sẽ xem xét mô hình toán học(mathematical models). Đó là cách để hiểu rõ hơn về chuyện gì đang xảy ra.

Khái niệm này được xây dựng và phát triển từ cuối thập niên 60 của thế kỷ trước bởi Don Knuth. Khi đó, các hệ thống máy tính thực sự bắt đầu trở nên phức tạp. Và các nhà khoa học máy tính quan tâm đến việc liệu chúng ta sẽ có thể hiểu chuyện gì đang xảy ra hay không. Và Knuth đã nói rằng đó là cái mà chúng ta chắc chắn sẽ làm được. 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 tất cả các thao tác cơ bản, tính chi phí của chúng, tính tần suất thực thi và lấy tổng của chi phí nhân với tần số thực hiện cho từng thao tác cơ bản. Bạn phải phân tích chương trình để xác định tập thao tác cơ bản, còn chi phí phụ thuộc vào máy tính. Tần suất dẫn ta tới toán học vì nó phụ thuộc vào thuật toán và dữ liệu input. Knuth đã viết một bộ sách với những phân tích chi tiết và chính xác về mô hình tính toán cho nhiều thuật toán.

Vậy làm thế nào để tính chi phí của các thao tác cơ bản?

Cái này thì mình cũng không rõ lắm, nhưng mình đoán là người ta sẽ chạy thực nghiệm với cùng 1 phép tính. Ví dụ như: người ta sẽ chạy phép công một tỷ lần và sẽ suy ra được phép cộng trên máy tính đó mất chi phí 2.1 nano giây(Cái này là ví dụ thôi nhé). Tóm lại là, có cách xác định chi phí của các thao tác cơ bản. Và trong hầu hết các trường hợp, ta sẽ chỉ coi rằng đó là một hằng số.

Điểm thú vị hơn ở trong khái niệm này là tần suất của việc chạy các thao tác. Ở đây ta sẽ xét đến một biến thể đơn giản của bài toán three-sum, bài toán one-sum. Bài toán được phát biểu như sau: Có bao nhiêu số có giá trị bằng 0?

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.

$i$ và $count$ phải được khai báo biến, và chúng được khởi tạo bằng 0.

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[]$

Số lần chạy phép ++ thì không cố định(tùy thuộc vào input).

Tương tự như bài toán one-sum và three-sum, chúng ta có bài toán two-sum: Có bao nhiêu 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 thì biến i và count cũng được khai báo biến và được khởi tạo bằng 0. Tuy nhiên, xuất hiện thêm biến $j$. Biến này được khỏi tạo và gán $n$ lần. 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, mỗi lần lệnh if chạy thì có hai lần truy nhập mảng, một lần so sánh bằng 0. 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 thì việc đi đếm các thao tác cơ bản sẽ trở nên khó khăn. Vậy,

Có cần thiết phải đếm tất cả các thao tác cơ bản? Cái này nó khá là giống với thống kê. Khi mà tập mẫu đủ tốt thì không cần phải tính toán đến toàn bộ khoảng dữ liệu cần nghiên cứu. Ở đây cũng thế, khi mà ước lượng thô là đủ tốt thì không cần phải tính toán đầy đủ toàn bộ các phép toán cơ bản. Dĩ nhiên là bạn vẫn có thể ngồi đếm tường tận số lần thực thi của từng thao tác, đặt trọng số, rồi cộng chúng lại. Nhưng thực tế thì người ta chỉ cần đếm thứ chạy chậm nhất(có chi phí cao nhất, hoặc được chạy nhiều lần nhất). Trong bài toàn two-sum, thì thao tác được thực thi nhiều nhất là thao tác 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, thời gian chạy cho $n$ nhỏ thì đằng nào cũng nhỏ.

Khi $n$ lớn thì 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 three-sum sấp xỉ với $\frac{n^{3}}{6}$

Tóm lại, về nguyên lý, Knuth nói rằng tồm tại các mô hình toán học chính xác. Trong thực tế, ta có thể tính ra những công thức rất phức tạp. Ta cũng có thể cần đến những kiến thức toán học cao cấp mà các nhà nghiên cứu lý thuyết sẽ rất quan tâm. Nhưng có lẽ ta không trông đợi tất cả mọi người phải biết. Cuối cùng thì tốt nhất là ta để dành những mô hình chính xác cho các chuyên gia. Còn lại, các mô hình xấp xỉ đã rất đáng giá. Và đối với tất cả các thuật toán, ta sẽ cố đạt được một mô hình xấp xỉ đủ dùng để mô tả thời gian chạy. Đôi khi ta sẽ dùng toán học để chứng minh, những lúc khác ta sẽ chỉ trích dẫn công trình nghiên cứu của một chuyên gia nào đó.

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

ToanNV

ToanNV

Developer, living in Tokyo, get married.

ToanNV © 2019
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora