Thuật toán và độ phức tạp

Độ phực tạp thuật toán và tổ chức dữ liệu

Trần Đỗ Hùng

Trong Tin học, khi phân tích một bài toán người ta cũng tìm giả thiết và kết luận. Giả thiết

là những dữ liệu đưa vào máy tính xử lí kèm theo các điều kiện ràng buộc chúng (gọi là

input) và kết luận là những thông tin thu được sau xử lí (gọi là output). Bài toán trong Tin

học có thể hiểu là bất cứ công việc gì có thể giao cho máy tính thực hiện: vẽ một chữ, một

hình trên màn hình cũng là bài toán! …

Phương pháp giải bài toán có thể cài đặt thành chương trình máy tính (viết bằng ngôn ngữ

lập trình) gọi là thuật toán. Thuật toán được thể hiện là dãy các thao tác có thứ tự và hữu

hạn để sau khi thực hiện dãy thao tác này, từ input của bài toán sẽ nhận được output của

bài toán.

Một bài toán có thể được giải bằng một vài thuật toán khác nhau. Người ta cần lựa chọn

thuật toán thích hợp và do đó cần đánh giá thuật toán. Để đánh giá thuật toán người ta dựa

vào khái niệm độ phức tạp thuật toán. Độ phức tạp của thuật toán là đại lượng đánh giá

lượng thời gian và không gian bộ nhớ dành cho thực hiện thuật toán.

Từ ý nghĩa thực tiễn của các bài toán khác nhau, có khi người ta quan tâm tới thuật toán

đòi hỏi ít thời gian thực hiện, nhưng cũng có khi lại quan tâm nhiều hơn tới thuật toán cho

phép cài đặt dữ liệu chiếm ít không gian bộ nhớ.

Độ phức tạp về không gian bộ nhớ của thuật toán phụ thuộc phần lớn vào cấu trúc dữ liệu

được sử dụng khi cài đặt thuật toán.

Độ phức tạp về thời gian thực hiện (còn gọi là độ phức tạp tính toán) được đánh giá sơ bộ

dựa vào số lượng các thao tác cơ bản (gán, so sánh 2 số nguyên, cộng, nhân 2 số nguyên

…). Số lượng các thao tác này là một hàm số của kích cỡ dữ liệu input. Nếu kích cỡ dữ

liệu input là N thì thời gian thực hiện thuật toán là một hàm số của N. Với một thuật toán

trên các bộ dữ liệu input khác nhau (cùng kích cỡ N) có thể các hàm số này là khác nhau;

song điều quan tâm hơn cả là mức độ tăng của chúng như thế nào khi N tăng đáng kể.

Ví dụ: Xét thuật toán tìm giá trị lớn nhất trong dãy N số sau đây:

Input. Số nguyên dương N, dãy N số A1, A2, …, AN

Output max{A1, A2,…, AN}

Bước 1. max ← A1

Bước 2. for i ← 2 to N do

If max < Ai then max ← Ai

Bước 3. Hiện max

Trường hợp xấu nhất: dữ liệu vào là dãy sắp tăng, thì số thao tác cơ bản là f(N)=2N+1

Trường hợp tốt nhất: giá trị lớn nhất ở ngay đầu dãy, thì thao tác cơ bản là g(N)= N.

Khi N lớn đáng kể thì f(N) và g(N) coi như xấp xỉ nhau và xấp xỉ hàm bậc nhất của N. Vậy

trong trường hợp này ta kí hiệu độ phức tạp thời gian của thuật toán trên là O(N).

Người ta phân lớp các bài toán theo độ phức tạp thuật toán. Có thể liệt kê một số lớp sau

có độ phức tạp tăng dần:

- Độ phức tạp hằng O(1)

- Độ phức tạp lôgarit O(logN)

- Độ phức tạp tuyến tính O(N)