10 Tin 2k11 - THPT Chuyên Lương Thế Vinh Đồng Nai Data Structures + Algorithms = Programming Tuesday, 18-01-22, 4:28 PM
Site menu
Statistics

Total online: 1
Guests: 1
Users: 0
Clock
Why Can't We Be Friends
Main » 2011 » August » 19 » ÐỘ PHỨC TẠP CỦA THUẬT TOÁN
4:06 PM
ÐỘ PHỨC TẠP CỦA THUẬT TOÁN

II. ÐỘ PHỨC TẠP CỦA THUẬT TOÁN

 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.

 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) = 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

f(n) = aknk + ak-1nk-1 + . . . + a1n + a0, với ak 0,

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

 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ó

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).

 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:

 độ phức tạp hằng: O(1).

 độ phức tạp logarith: O(log n).

 độ phức tạp tuyến tính: O(n).

 độ phức tạp n log n: O(n log n).

 độ phức tạp đa thức: O(nb).

 độ phức tạp mũ: O(bn), trong đó b > 1.

 độ phức tạp giai thừa: O(n!).

Views: 9256 | Added by: Angle_Bup | Rating: 3.0/1
Total comments: 15
0
12 comet   [Entry]
Độ phức tạp có thể dc tính 1 cách đơn giản thông qua các vòng lặp, đúng k thầy? biggrin

0
14 Angle_Bup   [Entry]
hyhy! thì em biết rồi đó! nếu không có vòng lặp thì độ phức tạp = const rồi còn gì! :P
khi gặp vòng lặp thì mới là "phức tạp"! ^^

0
10 siêu_trộm_1412_76   [Entry]
đọc vào ko hiểu chữ đuôi j hết lun.ko hieu wa thầy ui; angry cool wacko

0
11 comet   [Entry]
đọ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 à cry )

0
13 Angle_Bup   [Entry]
mấy em mới làm xong phần Pascal cơ bản thôi em ah!
^^ có mấy bài thầy phân tích sơ sơ cho thấy cách chạy rùi nhưng chưa nói đó là độ phức tạp thui!

0
8 binh   [Entry]
chong mat wa ua ma thi tin hoc có tính tg kt thuat toan ha thay e tuong viet chuog trinh thoy chu

0
9 Angle_Bup   [Entry]
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é.

0
6 Angle_Bup   [Entry]
mấy đứa đọc mà hiểu thì cho đi thi Olympic được rồi đấy! ^^ từ từ ngâm cứu thôi nghen!

0
5 nguyenchauthuan   [Entry]
Cái phần 1 em còn hiểu được đôi chút, nhưng sang phần 2 thì em thực sự không hiểu tí gì!

0
4 VoHuuTri   [Entry]
thầy ơi sao mấy cái kí hiệu nó hiện tùm lum hết zậy đọc ko hỉu j hết cry cry cry cry cry

0
3 binh   [Entry]
thay oi chung nao co tkb za sao t6 roi ma van ko co

0
7 Angle_Bup   [Entry]
thầy cũng đang chờ đây em!

0
2 punky   [Entry]
trùi sao đọc khó hỉu wa' zậy trời angry

0
1 kiepmeodoremon   [Entry]
Thầy ơi thứ 2 học văn hóa luôn phải k thầy, nếu có thì TKB thế nào ạ ?

0
15 Angle_Bup   [Entry]
uh học văn hóa luôn nhé!

Name *:
Email *:
Code *:
Login form
Chat Box
Search
Calendar
«  August 2011  »
SuMoTuWeThFrSa
 123456
78910111213
14151617181920
21222324252627
28293031
Entries archive
Site friends
  • VNOI
  • THPT Chuyên Lương Thế Vinh
  • Website builderuCoz!-->
    Copyright Hoàng Anh © 2022