[You must be registered and logged in to see this image.] 2.1 Khái
niệm độ phức tạp của thuật toán

Một chương trình máy
tính thường được cài đặt dựa trên một thuật toán để giải
bài toán hay vấn đề đặt ra. Một đòi hỏi đương nhiên là thuật
toán phải đúng. Tuy nhiên, ngay cả khi thuật toán đúng, chương trình
vẫn có thể là không sử dụng được đối với một số dữ liệu
nhập nào đó bởi vì thời gian cần thiết để chạy chương trình hay
vùng nhớ cần thiết để lưu trữ dữ liệu (như các biến trong
chương trình, các file lưu trữ, ...) quá lớn.

Thuật ngữ phân
tích thuật toán đề cập đến một quá trình tìm ra một
đánh giá về thời gian và không gian cần thiết để thực hiện
thuật toán. Ðộ phức tạp của thuật toán được thể hiện qua
khối lượng thời gian và không gian để thực hiện thuật toán.
Không gian ở đây được hiểu là các yêu cầu về bộ nhớ, thiết
bị lưu trữ, … của máy tính để thuật toán có thể làm việc
được. Việc xem xét độ phức tạp về không gian 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 trong
cài đặt thuật toán. Trong phần nầy chúng ta chỉ đề cập đến độ
phức tạp về thời gian của thuật toán.

Chúng ta cũng có thể
đạt được những thông tin rất hữu ích khi phân tích độ phức
tạp thời gian của thuật toán cơ sở của một chương trình máy tính.
Ðánh giá một cách chính xác thời gian thực hiện một chương trình
phụ thuộc vào rất nhiều yếu tố và là một công việc rất khó
khăn. Tuy nhiên các nhà toán học đã phân tích cho chúng ta hầu độ
phức tạp của hầu hết các thuật toán thường được sử dụng
như các thuật toán sắp xếp, các thuật toán tìm kiếm, các thuật
toán số học, v.v…

Ðộ phức tạp thời
gian của thuật toán thường được đánh giá dựa vào số lượng
thao tác được sử dụng trong thuật toán và số lượng thao tác
nầy phụ thuộc vào cở (size) của dữ liệu nhập. Ta còn gọi độ
phức tạp thời gian của thuật toán là độ phức tạp tính toán.
Các thao tác được sử dụng để đo độ phức tạp của thuật toán
có thể là phép so sánh 2 số nguyên, cộng 2 số nguyên, nhân 2 số
nguyên, chia 2 số nguyên, hay bất kỳ thao tác cơ bản nào khác. Như
thế ta có thể xem thời gian thực hiện thuật toán là một hàm phụ
thuộc vào dữ liệu nhập (thường là cở của dữ liệu nhập). Nếu
gọi cở dữ liệu nhập là n thì độ phức tạp có thể được xem
là một hàm theo n.

Chúng ta có thể đặt
ra câu hỏi về thời gian thực hiện thuật toán nhỏ nhất đối với
các dữ liệu nhập có cở n. Ta có thể nêu lên một số bài toán
có dữ liệu nhập có cở n như: sắp xếp dãy n số nguyên, tìm số
nhỏ nhất trong dãy n số nguyên, v.v.... Thời gian nhỏ nhất nầy
được gọi là thời gian thực hiện thuật toán trong trường hợp
tốt nhất đối với dữ liệu nhập có cở n. Tương tự ta cũng
thường đề cập đến thời gian thực hiện thuật toán lớn nhất
đối với các dữ liệu nhập có cở n, và gọi là thời gian
thực hiện thuật toán trong trường hợp xấu nhất đối với dữ
liệu nhập có cở n. Ngoài ra, đối với thuật toán có dữ liệu
nhập có cở n trong một tập hữu hạn nào đó, ta còn muốn tính ra thời
gian trung bình để thực hiện thuật toán.

Ví dụ 1: Thuật toán tìm giá trị lớn nhất trong
dãy gồm n số nguyên (xem ví dụ 1, mục I). Trong thuật toán nầy nếu ta
xem thời gian thực hiện thuật toán là số lần thực hiện phép so
sánh hay phép gán thì thời gian thực hiện thuật toán trong trường
hợp xấu nhất là:

t(n) = 1 + 2*(n-1) = 2n+1

và thời gian thực hiện thuật toán trong trường hợp
tốt nhất là:

T(n) = 1 + (n-1) = n.

[You must be registered and logged in to see this image.] 2.2 Ký
hiệu O

Việc tính toán độ
phức tạp (về thời gian hay về tính toán) của thuật toán sẽ giúp
ta có thể đánh giá và so sánh các thuật toán. Tuy nhiên có những
trường hợp mà 2 thuật toán khác nhau để giải quyết cùng một
bài toán có số lượng thao tác cơ bản là f(n) và g(n), với n là
cở dữ liệu nhập, rất khó so sánh đánh giá hơn kém theo sự so
sánh lớn bé thông thường. Hơn nữa trong hầu hết các thuật toán
như thuật toán sắp xếp, thuật toán tìm kiếm, … ta không thể tính
ra được số lượng thao tác f(n) theo n.

Thông thường ta ít
chú ý tới con số chính xác về thời gian thực hiện thuật toán
trong trường hợp xấu nhất và trong trường hợp tốt nhất. Ðiều
mà chúng ta thường quan tâm hơn khi đánh giá độ phức tạp thời
gian của thuật toán là mức độ tăng lên của thời gian thực hiện
thuật toán khi cở của dữ liệu nhập tăng lên. Chẳng hạn, một
thuật toán đang được xem xét nào đó có thời gian thực hiện
trong trường hợp xấu nhất và trong trường hợp tốt nhất lần
lượt là:

t(n) = 20n² + 5n + 1,

T(n) = n² + 10n + 1.

Như thế, nếu như n
rất lớn thì ta có thể xấp xỉ t(n) và T(n) với 20n² và n².
Có thể nói rằng t(n) và T(n) tăng giống như n² khi n tăng.
Ðể diễn đạt điều nầy, người ta định nghĩa và sử dụng ký
hiệu O được định nghĩa như dưới đây.


[You must be registered and logged in to see this image.] Ðịnh nghĩa: Cho 2 hàm thực f và g có miền xác
định trong tập số tự nhiên N. Ta viết:

f(n)
Î O(g(n))

và nói là f(n) có cấp cao nhất là g(n), hay f(n) thuộc
lớp O(g(n)), khi có một hằng số dương C sao cho:

| f(n)|
≤ C . | g(n) |,

với "hầu hết" n thuộc miền xác định của
các hàm f và g. Từ "hầu hết" ở đây ý nói là
"với mọi chỉ trừ một số hữu hạn", hay nói một cách
chính xác là

$ C > 0, $ k
Î N, " n
Î
N, n ≥ k
®
| f(n)|
≤ C
. | g(n) |

Ví dụ:

Với t(n) = 20n² + 5n + 1 và T(n) = n² + 10n + 1. Ta có
thể chứng minh được rằng nói t(n) và T(n) có cấp cao nhất là n²,
tức là t(n)
Î O(n²) và T(n)
Î O(n²).

Xét f(n) = log (n!). Ta có

n! = 1.2. . .n
≤ n.n. . .n ≤ nⁿ
Þ log(n!)
≤ log (nⁿ) = n.log(n)

Suy ra
log(n!)
Î O(n log n)

[You must be registered and logged in to see this image.] Ðịnh lý II.1: Nếu f(n) là một đa thức bậc k theo
n, tức là f(n) có dạng

f(n) = a_kn^k + a_k-1n^k-1 + .
. . + a₁n + a₀, với a_k≠
0,

thì ta có f(n) thuộc lớp O(n^k).

[You must be registered and logged in to see this image.] Ngoài
ra ta còn có các tính chất sau đây:

[You must be registered and logged in to see this image.] Giả
sử rằng f₁(n)
Î O(g₁(n)) và f₂(n)
Î O(g₂(n)). Khi ấy ta có

f₁(n) + f₂(n)
Î O (
max(g₁(n), g₂(n)) )

Hệ
quả là nếu f₁(n) và f₂(n) đều thuộc O(g(n)) thì ta
cũng có

f₁(n) + f₂(n)
Î
O(g(n))

[You must be registered and logged in to see this image.] Giả
sử rằng f₁(n)
Î O(g₁(n)) và f₂(n)
Î O(g₂(n)). Khi ấy ta có

f₁(n).f₂(n)
Î O ( g₁(n).g₂(n)
)

Ví dụ 2: Ðánh giá độ phức tạp (thời gian)
của thuật toán tìm kiếm tuyến tính (xem ví dụ 3 ở mục I)

Ðối với thuật toán nầy, trong trường hợp tốt
nhất (phần tử cần tìm nằm ngay tại vị trí đầu tiên của dãy)
thời gian thực hiện thuật toán là 1. Ta viết thời gian thực hiện
thuật toán trong trường hợp tốt nhất là: O(1).

Ta cũng có thể tính toán ra được thời gian thực
hiện thuật toán trong trường hợp xấu nhất và thời gian thực
hiện thuật toán trung bình đều là O(n).

[You must be registered and logged in to see this image.] 2.3 Một
số lớp độ phức tạp

Liên quan đến độ phức tạp của thuật toán ta có
một số thuật ngữ thường dùng trong sự phân lớp các độ phức
tạp của thuật toán được liệt kê dưới đây:

[You must be registered and logged in to see this image.] độ phức tạp hằng: O(1).


[You must be registered and logged in to see this image.] độ
phức tạp logarith: O(log n).


[You must be registered and logged in to see this image.] độ
phức tạp tuyến tính: O(n).


[You must be registered and logged in to see this image.] độ
phức tạp n log n: O(n log n).


[You must be registered and logged in to see this image.] độ
phức tạp đa thức: O(n^b).


[You must be registered and logged in to see this image.] độ
phức tạp mũ: O(bⁿ), trong đó b > 1.


[You must be registered and logged in to see this image.] độ
phức tạp giai thừa: O(n!).