ôn lại PTTKTT


Diễn đàn chia sẻ kiến thức, kinh nghiệm về IT và cuộc sống!
 
Trang ChínhGalleryTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
Top posters
Sakura (1124)
 
hotboy (705)
 
Già Làng (373)
 
con_ca_nho90 (289)
 
that_true (154)
 
theanhkkt (143)
 
phamay (137)
 
lovelonelyman (134)
 
o0ovioletstaro0o (128)
 
stevenhung (122)
 
Âm - Dương lịch
Clock
Logo
11TH02 Pro!
Liên kết
Tin tức 60s
Tin công nghệ
Thời sự 24h
Game Moblie

Share | 
 

 ôn lại PTTKTT

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
hotboy


avatar

Thú CƯng :
Nam Aries

Số bài viết : 705
Điểm : 1043
Được cảm ơn : 9
Ngày sinh : 21/03/1990
Tham gia ngày : 13/05/2010
Tuổi : 28
Đến từ : BDU

Bài gửiTiêu đề: ôn lại PTTKTT   14/7/2010, 20:57

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


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

[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) = aknk + ak-1nk-1 + .
. . + a1n + a0, với ak
0,




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

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

[You must be registered and logged in to see this image.] 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).


[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(nb).


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


[You must be registered and logged in to see this image.] độ
phức tạp giai thừa: O(n!).
Về Đầu Trang Go down
Xem lý lịch thành viên
 

ôn lại PTTKTT

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
IT World! :: HỌC TẬP :: Học Kỳ IV :: Phân Tích Thiết Kế Thuật Toán-