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à:
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) = 20n2 + 5n + 1,
T(n) = n2 + 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 20n2 và n2. Có thể nói rằng t(n) và T(n) tăng giống như n2 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.
Ðị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) = 20n2 + 5n + 1 và T(n) = n2 + 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à n2, tức là t(n) Î O(n2) và T(n) Î O(n2).
Xét f(n) = log (n!). Ta có
n! = 1.2. . .n ≤ n.n. . .n ≤ nn
Þ log(n!) ≤ log (nn) = n.log(n)
Suy ra
log(n!) Î O(n log n)
Ðị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
Giả sử rằng f1(n) Î O(g1(n)) và f2(n) Î O(g2(n)). Khi ấy ta có
f1(n) + f2(n) Î O ( max(g1(n), g2(n)) )
Hệ quả là nếu f1(n) và f2(n) đều thuộc O(g(n)) thì ta cũng có
f1(n) + f2(n) Î O(g(n))
Giả sử rằng f1(n) Î O(g1(n)) và f2(n) Î O(g2(n)). Khi ấy ta có
f1(n).f2(n) Î O ( g1(n).g2(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).
đọc k thế này mà tụi em hiểu dc thì.. tụi anh xin bái tụi e làm sư luôn rồi^_^ mấy cái này đọc thì khó nhưng tụi em cứ bắt thầy mỗi lần giài bài là phân tích độ phức tạp của cách giải đó, làm hoài tụi em sẽ hiểu. năm ngoái cô Phương có 1 cách khá là hay, ra đề xong là cho tụi anh làm, chỉ cần làm dc nhưng trường hợp đơn giản nhất, sau đó cô sẽ phân tích nhược điểm của thuật toán, phân tích độ phức tạp, và đưa ra thuật toán tốt hơn.(nhưng về sau cô bắt tụi anh tự xác định ĐPT k à )
ah thuật toán thì không ai kiểm tra nhưng nếu thuật toán tốt thì thời gian chạy sẽ nhanh và xử lý được dữ liệu lớn hơn!trong các cuộc thi tin học thì thời gian chạy và khả năng xử lý được dữ liệu lớn là tiêu chí để cho điểm đấy nhé.
Ðị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:
Ngoài ra ta còn có các tính chất sau đây:
Giả sử rằng f1(n) Î O(g1(n)) và f2(n) Î O(g2(n)). Khi ấy ta có
độ phức tạp hằng: O(1).
)
