10.5K 783 122

Đã đăng vào thg 9 3, 2021 7:59 SA 16 phút đọc

27.7K

Bài 11: Thuật toán và Phân tích thuật toán

I. Thuật toán và những tính chất của thuật toán

1. Khái niệm

Thuật toán - hay còn gọi là giải thuật - là khái niệm quan trọng nhất trong Tin học. Nó là nền tảng cho mọi khía cạnh của Tin học. Khái niệm về thuật toán đã tồn tại từ thời cổ đại, sớm nhất ở đế chế Babylonia với thuật toán chia vào năm 2500 TCN. Khái niệm về thuật toán có thể phát biểu như sau:

Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề.

Với sự phát triển chóng mặt của khoa học máy tính, các thuật toán cũng ngày càng phát triển về số lượng cũng như chất lượng. Trong phạm vi của lập trình thi đấu, chúng ta sẽ tập trung nghiên cứu chuyên sâu về các thuật toán từ dễ đến khó, phục vụ cho các kỳ thi về thuật toán như HSG Tin học, Tin học trẻ hay các kỳ thi thuật toán online. Toàn bộ các cài đặt sẽ được viết ở ngôn ngữ C++ vì như đã nói ở các chuyên đề lập trình cơ bản, C++ là một ngôn ngữ rất mạnh trong lập trình thi đấu.

2. Các đặc trưng của thuật toán

Mỗi thuật toán luôn luôn có đủ $5$ đặc trưng sau:

Có đầu vào (Input): Thuật toán nhận dữ liệu vào từ một tập nào đó.
Có đầu ra (Output): Từ dữ liệu đầu vào, thuật toán sẽ tính toán và đưa ra kết quả tương ứng với đầu vào đó.
Tính chính xác: Các bước của thuật toán được mô tả chính xác.
Tính hữu hạn: Thuật toán cần phải đưa ra được output sau một số hữu hạn các bước với mọi input.
Tính đơn trị: Các kết quả trung gian của từng bước thực hiện thuật toán được xác định một cách đơn trị và chỉ phụ thuộc và input và kết quả của các bước trước.
Tính tổng quát: Thuật toán có thể áp dụng để giải mọi bài toán có cùng dạng với bài toán đã giải.

Chẳng hạn, dưới đây là thuật toán tìm số ước của một số nguyên dương $N$ được viết trong một hàm int count_divisors(int N)

int count_divisors(int N)
{
    int divisors = 0;
    for (int i = 1; i <= N; ++i)
	if (N % i == 0)
	    ++divisors;

    return divisors;
}

II. Phân tích tính hiệu quả của thuật toán

1. Các tiêu chí đánh giá một thuật toán

Thông thường, khi giải một bài toán, chúng ta luôn luôn có xu hướng chọn cách giải "tốt" nhất. Nhưng thế nào là "tốt"? Trong toán học, một cách giải "tốt" có thể là cách giải ngắn gọn, xúc tích, hoặc trên tiêu chí sử dụng những kiến thức dễ hiểu. Còn đối với thuật toán trong Tin học thì dựa vào hai tiêu chuẩn sau:

Thuật toán đơn giản, dễ hiểu, dễ cài đặt.
Thuật toán hiệu quả: Dựa vào hai yếu tố là thời gian thực hiện thuật toán (còn gọi là độ phức tạp thời gian) và dung lượng bộ nhớ cần thiết để lưu trữ dữ liệu (còn gọi là độ phức tạp không gian). Tuy nhiên, trong bối cảnh hiện tại khi các máy tính có khả năng lưu trữ rất lớn thì yếu tố mà chúng ta cần quan tâm nhiều hơn là độ phức tạp thời gian.

2. Sự cần thiết của thuật toán hiệu quả

Công nghệ càng phát triển thì sẽ dẫn tới độ lớn dữ liệu cần tính toán ngày càng lớn, tất nhiên khả năng tính toán của máy tính cũng ngày càng phát triển. Nhưng không phải vì việc máy tính hiện đại mà chúng ta có thể bỏ qua tầm quan trọng của một thuật toán hiệu quả. Để làm rõ vấn đề này, tôi xin trích lại một ví dụ trong sách giáo khoa chuyên Tin quyển $1$ về thuật toán kiểm tra tính nguyên tố của một số.

bool is_prime(int N)
{
    if (N < 2) // Nếu N nhỏ hơn 2 thì chắc chắn không phải số nguyên tố.
        return false;

    // Nếu N có ước trong đoạn [2, N - 1] thì N không phải số nguyên tố.
    for (int i = 2; i < N; ++i)
        if (N % i == 0) 
            return false;

    return true;
}

Bên trên là cách cài đặt đơn giản nhất của giải thuật kiểm tra tính nguyên tố. Thuật toán này cần $N-2$ bước kiểm tra trong vòng lặp. Hãy giả sử cần kiểm tra một số có khoảng $25$ chữ số, và ta sở hữu một siêu máy tính có thể tính toán được một trăm nghìn tỉ ( $10^{14}$ ) phép tính trên giây, thì tổng thời gian cần để kiểm tra là:

\frac{10^{25}}{10^{14} \times 60 \times 60 \times 24 \times 365} \approx 3170 \text{ năm!}$$ Tuy nhiên, nếu tinh ý ta có thể nhận xét như sau: Một số $N$ có ước là $x \ (x \le \sqrt{N})$ thì chắc chắn nó cũng có ước là $\frac{N}{x} \ge \sqrt{N}$. Do đó, thay vì duyệt từ $2$ tới $N - 1$ thì ta chỉ cần duyệt từ $2$ tới $\sqrt{N}$ là có thể biết được $N$ có ước nào trong đoạn này hay không: ```cpp bool is_prime(int N) { if (N < 2) // Nếu N nhỏ hơn 2 thì chắc chắn không phải số nguyên tố. return false; // Nếu N có ước trong đoạn [2, N - 1] thì N không phải số nguyên tố. for (int i = 2; i * i <= N; ++i) if (N % i == 0) return false; return true; } ``` Theo phương pháp này, vẫn là một số nguyên có khoảng $25$ chữ số nhưng thời gian kiểm tra sẽ giảm xuống còn: $$\frac{\sqrt{10^{25}}}{10^{14}} \approx 0.03 \text{ giây!}

III. Phương pháp đánh giá độ phức tạp thuật toán

1. Phương pháp đánh giá bằng lý thuyết

Trong lập trình thi đấu, người ta sẽ đánh giá độ phức tạp thuật toán bằng phương pháp lý thuyết. Trong phương pháp này, ta quan tâm tới yêu tố kích thước của dữ liệu đầu vào, thông thường là một con số $n$ . Mối liên hệ giữa yếu tố này và số lượng các phép tính toán cũng như kích thước bộ nhớ lưu trữ để tìm ra được kết quả của bài toán gọi chung là độ phức tạp thuật toán (chứ không phải thời gian cụ thể như $1, 2$ hay $10$ giây). Ta sử dụng hai hàm số $T(n)$ và $S(n)$ để biểu diễn thời gian thực hiện của thuật toán và không gian lưu trữ của thuật toán với dữ liệu đầu vào kích thước là $n$ .

Độ lớn của hàm $T(n)$ được biểu diễn bằng một hàm $O\big(f(n)\big)$ với $T(n)$ và $f(n)$ là hai hàm số thực không âm. Nếu một thuật toán có thời gian thực hiện là $T(n) = O\big(f(n)\big)$ thì ta nói thuật toán đó có thời gian thực hiện cấp $f(n)$ . Nói một cách dễ hiểu, $T(n)$ sẽ biểu diễn số phép tính tối đa cần thực hiện trong thuật toán với một bộ dữ liệu đầu vào cấp $n,$ chẳng hạn trong bài toán kiểm tra tính nguyên tố của số $n,$ nếu $n$ là số nguyên tố thì thuật toán sẽ phải thực hiện nhiều lần thử nhất.

Còn độ lớn của hàm $S(n)$ cũng được biểu diễn bằng một hàm $O\big(g(n)\big)$ với $S(n)$ và $g(n)$ là hai hàm số thực không âm. Nếu một thuật toán tiêu tốn bộ nhớ $S(n) = O\big(g(n)\big)$ thì ta nói thuật toán đó có không gian lưu trữ cấp $g(n)$ . Một cách đơn giản hơn, $S(n)$ sẽ biểu diễn tổng dung lượng bộ nhớ cần sử dụng trong thuật toán với một bộ dữ liệu đầu vào cấp $n$ . Trong bài toán kiểm tra tính nguyên tố của số $n,$ mỗi biến khai báo ra đều đóng góp vào $S(n),$ vì chúng đều tiêu tốn bộ nhớ của chương trình.

2. Các quy tắc đánh giá độ phức tạp thời gian

Để đánh giá thời gian thực hiện thuật toán, ta xuất phát từ các lệnh đơn trong chương trình, rồi tới các câu lệnh có cấu trúc, các khối lệnh phức tạp hơn, sau đó hợp lại thành thời gian thực hiện cả chương trình. Cụ thể ta có các quy tắc:

Các lệnh đơn (lệnh khai báo, gán, nhập xuất dữ liệu, phép toán số học,...): Thời gian $O(1)$ .
Các khối lệnh: Giả sử một khối lệnh gồm các câu lệnh $S_1, S_2,..., S_m$ có thời gian thực hiện lần lượt là $\big(f_1(n)\big), O\big(f_2(n)\big),..., O\big(f_m(n)\big)$ thì thời gian thực hiện của cả khối lệnh là: $O\Big(\text{max}\big(f_1(n), f_2(n),...,f_m(n)\big)\Big)$ .
Câu lệnh rẽ nhánh: Ta có cú pháp lệnh rẽ nhánh là:
```
if ({Điều_kiện})
    {Câu_lệnh_1}
else 
    {Câu_lệnh_2}
```
Giả sử thời gian thực hiện của câu lệnh $1$ $1$ và câu lệnh $2$ $2$ lần lượt là $O\big(f_1(n)\big)$ $O (f_{1} (n))$ và $O\big(f_2(n)\big)$ $O (f_{2} (n))$ thì thời gian thực hiện lệnh rẽ nhánh là: $O\Big(\text{max}\big(f_1(n), f_2(n)\big)\Big)$ $O (max (f_{1} (n), f_{2} (n)))$ .
Câu lệnh lặp: Giả sử thời gian thực hiện phần thân của lệnh lặp là $O\big(f_1(n)\big)$ và số lần lặp tối đa của vòng lặp là $f_2(n)$ thì thời gian thực hiện của cả vòng lặp là $O\big(f_1(n).f_2(n)\big)$ . Điều này áp dụng cho tất cả các vòng lặp for, while và do...while.
Sau khi đánh giá được thời gian thực hiện của tất cả các câu lệnh trong chương trình, thời gian thực hiện của toàn bộ chương trình sẽ là thời gian thực hiện của câu lệnh có thời gian thực hiện lớn nhất. Ngoài ra, nếu như độ phức tạp tính toán là $O\big(c \times f(n)\big)$ với $c$ là một hằng số nhỏ, ta có thể bỏ qua $c$ và coi như thuật toán có độ phức tạp là $O\big(f(n)\big)$ - chẳng hạn như $O(3n), O(4n)$ có thể coi như $O(n)$ .

3. Các quy tắc đánh giá độ phức tạp không gian

Trước tiên, ta cùng xem lại bảng không gian lưu trữ tiêu tốn của các kiểu dữ liệu nguyên thủy trong C++:

Các kiểu dữ liệu đều có kích thước bộ nhớ ( $1$ byte, $2$ byte,...). Byte là một đơn vị đo dung lượng lưu trữ trên máy tính, bên dưới nó là bit ( $1$ byte $= 8$ bit) và bên trên nó có các đơn vị khác như Kilobyte (KB), Megabyte (MB), Gigabyte (GB), Terabyte (TB),...Các đơn vị này có một đặc điểm chung từ Byte trở lên:

$1$ Đơn vị sau $= 1024 \times \text{ }$ Đơn vị trước

Chẳng hạn như $1$ MB = $1024$ KB, $1$ TB = $1024$ MB,...

Độ phức tạp không gian của một thuật toán sẽ được tính toán thông qua hàm $O\big(g(n)\big)$ trước, rồi mới đổi ra giá trị dung lượng cụ thể. Nó là tổng của tất cả bộ nhớ sử dụng trong việc nhập dữ liệu đầu vào và bộ nhớ phụ sử dụng khi thực hiện thuật toán. Các quy tắc tính toán cơ bản như sau:

Các biến đơn khi khai báo (một hoặc nhiều biến): $O(1)$ .
Khai báo mảng một chiều kích thước $n$ : $O(n)$ .
Khai báo mảng nhiều chiều có kích thước các chiều lần lượt là $n_1, n_2, \dots, n_k$ : $O(n_1 \times n_2 \times \cdots \times n_k)$ .
Lời gọi đệ quy: Phụ thuộc vào số lượng lời gọi đệ quy lưu đồng thời trong phân vùng bộ nhớ call stack (sẽ học ở bài Hàm đệ quy).

Tổng bộ nhớ sử dụng trong toàn bộ chương trình sẽ hợp thành độ phức tạp không gian của chương trình là $O\big(g(n)\big)$ . Sau khi tính được $O\big(g(n)\big),$ ta sẽ quy đổi nó ra dung lượng bộ nhớ tương ứng với kiểu dữ liệu của input để tính ra được bộ nhớ sử dụng một cách tương đối chính xác.

4. Phân tích ví dụ

Ví dụ 1: Phân tích độ phức tạp thuật toán của đoạn chương trình sau

#include <iostream>

using namespace std;

int main()
{
    int n;  // (1)
    cin >> n; // (2)

    int s1 = 0; // (3)
    for (int i = 1; i <= n; ++i)  // (4)
	s1 += i;  // (5)

    int s2 = 0; // (6)
    for (int i = 1; i <= n; ++i) // (7)
	s2 += i * i; // (8)

    cout << s1 << endl << s2; // (9)
    
    return 0;
}

Thời gian thực hiện chương trình trên phụ thuộc vào số $n$ . Ta phân tích chi tiết:

Các lệnh $(1), (2), (3), (5), (6), (8), (9)$ đều có thời gian thực hiện là $O(1)$ .
Vòng for số $4$ có số lần lặp là $n$ và câu lệnh ở phần thân (là câu lệnh $(5)$ ) có thời gian thực hiện $O(1)$ . Vậy cả vòng lặp có thời gian thực hiện là $O(n)$ . Tương tự với vòng lặp số $(7)$ .

Vậy thời gian thực hiện của cả thuật toán là:

$\text{max}\big(O(1), O(n)\big) = O(n)$

Về độ phức tạp không gian, ta nhận thấy đoạn chương trình hoàn toàn sử dụng các biến đơn không hề phụ thuộc vào giá trị input $n$ :

Biến $sum$ : Chỉ có một biến nguyên được sử dụng, không phụ thuộc vào đầu vào $n,$ độ phức tạp không gian của biến này là $O(1)$ .
Các biến $i$ và $j$ : Vì chúng chỉ được sử dụng trong các vòng lặp và không lưu trữ thông tin nào sau khi vòng lặp kết thúc, không có đóng góp vào độ phức tạp không gian cuối cùng. Độ phức tạp không gian của các biến này cũng là $O(1)$ .
Biến $n$ : Đây là biến đại diện cho giá trị đầu vào của chương trình. Biến này chỉ lưu trữ một giá trị nguyên và không phụ thuộc vào kích thước của dữ liệu đầu vào. Do đó, độ phức tạp không gian của biến này cũng là $O(1)$ .

Vì vậy độ phức tạp bộ nhớ có thể coi là $O(1)$ .

Ví dụ 2: Phân tích độ phức tạp thuật toán của đoạn chương trình sau

#include <iostream>

using namespace std;

int main()
{
    int sum = 0; // (1)
    for (int i = 1; i <= N; ++i) // (2)
        for (int j = 1; j <= i; ++j) // (3)
            sum = sum + 1;  // (4)

    cout << sum;  // (5)
}

Đoạn chương trình trên có thời gian thực hiện phụ thuộc vào số $N$ . Phân tích chi tiết:

Câu lệnh $(1)$ và $(5)$ có thời gian thực hiện $O(1)$ .
Câu lệnh $(4)$ có thời gian thực hiện $O(1)$ .
Ứng với mỗi giá trị $i$ $i$ của câu lệnh lặp $(2),$ $(2),$ thì:
- Khi $i = 1,$ lệnh lặp $(3)$ thực hiện $1$ lần.
- Khi $i = 2,$ lệnh lặp $(2)$ thực hiện $2$ lần. $...$
- Khi $i = N,$ lệnh lặp $(2)$ thực hiện $N$ lần. Như vậy, lệnh lặp $(3)$ có số lần thực hiện là $\frac{N.(N + 1)}{2},$ từ đó suy ra cả lệnh lặp $(2)$ có thời gian thực hiện là $\approx O(N^2)$ .

$\Rightarrow$ Cả chương trình có thời gian thực hiện là $O(N^2)$ .

Độ phức tạp không gian cũng vẫn là $O(1),$ do đoạn chương trình chỉ sử dụng các biến đơn.

Ví dụ 3: Phân tích độ phức tạp thuật toán của đoạn chương trình sau:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1000;
int a[maxn + 1][maxn + 1];

int main()
{   
    int n;
    cin >> n;
    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> a[i][j];
        
    // Tính tổng đường chéo chính của ma trận.
    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += a[i][i];
        
    cout << sum;
    
    return 0;
}

Đoạn chương trình trên dùng để tính tổng các phần tử trên đường chéo chính của một ma trận vuông.

Về độ phức tạp thời gian, ta có thể thấy hai vòng lặp lồng nhau dùng để nhập ma trận là tốn nhiều thời gian thực thi nhất, vì vậy thời gian tổng quát của thuật toán là $O(n^2)$ .

Về độ phức tạp bộ nhớ, ta thấy đoạn chương trình khai báo một mảng hai chiều kích thước $maxn \times maxn,$ còn lại đều là các biến đơn. Như vậy độ phức tạp bộ nhớ tổng quát là $O(maxn^2) \approx O(10^6)$ .

5. Áp dụng vào bài toán

Bây giờ, ta cùng xem một ví dụ về đề bài trong các cuộc thi lập trình thi đấu:

Một đề bài trên trang web lập trình codeforces.com

Những đề bài như trên rất phổ biến ở các trang web lập trình online, và đôi khi là cả ở các đề thi HSG cấp quận (huyện), tỉnh (thành phố), quốc gia,...Nó cho chúng ta biết giới hạn thời gian và không gian của bài toán:

Giới hạn thời gian (Time limit per test): $2$ giây.
Giới hạn không gian (Memory limit per test): $256$ Megabytes.

Những ràng buộc này cho chúng ta biết, chương trình phải cho ra kết quả sau tối đa 2 giây, và bộ nhớ sử dụng không được vượt quá $256$ Megabytes. Để tính toán, trước hết ta sẽ tính độ phức tạp thời gian và không gian của thuật toán đã cài đặt, giả sử lần lượt là $O\big(f(n)\big)$ và $O\big(g(n)\big)$ . Sau đó, dựa vào một số kiến thức dưới đây để cải tiến thuật toán nếu cần:

Thời gian thực thi thuật toán sẽ $\le 2$ giây nếu như $f(n) \le 5 \times 10^8$ .
Không gian sử dụng sẽ bằng tích giữa $g(n)$ và kích thước của kiểu dữ liệu đầu vào. Chẳng hạn, $g(n) = 10^6$ và $n$ có kiểu dữ liệu long long, ta sẽ tính được không gian sử dụng là khoảng $8 \times 10^6$ bytes, tương đương với khoảng gần $8$ Megabytes - hoàn toàn đáp ứng được ràng buộc. Thông thường, giới hạn không gian cho phép trong các bài toán là khoảng $512$ Megabytes, vì vậy $g(n)$ nên $\le 10^8$ nếu $n$ là kiểu int, và khoảng $5 \times 10^7$ nếu $n$ là kiểu long long.

Sau khi tính toán được các yếu tố trên, các bạn sẽ tối ưu lại thuật toán để thỏa mãn được các ràng buộc.

IV. Tài liệu tham khảo