PHÂN TÍCH MỘT SỐ THUẬT TOÁN


Thuật toán tìm Max
Thuật toán M: Tìm giá trị lớn nhất trong dãy x[1], x[2], …, x[N]
Begin
j:=1; m := x[1];
for i:=2 to N do
if x[i] > m then
m := x[i];
j := i;
end if
end do
End

Có thể chứng minh thuật toán M là đúng bằng nguyên lý qui nạp.
Nếu gọi ( là thời gian thực hiện một phép so sánh và ( là thời gian thực hiện một phép gán thì thời gian thực hiện thuật toán M là:
T= 2 ( + (N-1) ( + 2 AN (
Trong đó AN là số lần mà điều kiện x[i] > m được thỏa trong vòng lặp for. Nói cách khác AN số những i thỏa điều kiện sau đây:
x[i] = Max {x[k], 1 ( k ( i}
Có thể thấy rằng 0 ( AN ( N-1. Từ đó ta suy ra độ phức tạp (trung bình) của thuật toán M là O(ln(n)) vì dựa trên kỹ thuật tính toán dùng hàm sinh ta có thể chứng minh được rằng
mean(AN) = Hn – 1 = O( ln(n) )
và độ lệch là
( =


Chứng minh:

Ta tính giá trị trung bình của AN dựa trên 2 giả thiết sau:
dãy các x[i] đôi một khác nhau, và
mọi phép hoán vị đều có thể xảy ra với xác suất như nhau (là 1/N!).
Ký hiệu pNk là xác suất để AN = k.
Ta có:
pNk = (số hoán vị mà AN = k) / N!
Có thể kiểm tra được công thức sau đây (bài tập):
pNk =
.pN-1,k-1 +
.pN-1,k
Xét hàm sinh


Ta có thể kiểm tra thấy rằng:


Suy ra


Do đa thức
là hàm sinh của dãy {
,
} nên
Ave(
) =
.
Từ đó
Ave(
) =
= Hn-1.

Số nghịch thế của một phép hon vị
Định nghĩa:
Cho ( là một hoán vị của n phần tử 1, 2, …, n. Một nghịch thế
là một cặp (((i),((j)) thỏa
((i) > ((j) và i < j.
Với j = 1, 2, …, n đặt
bj = số các nghịch thế có thành phần thứ hai là j.
Bảng b1, b2, …, bn được gọi là bảng nghịch thế của hoán vị (.
Số các nghịch thế của ( là:
I(() =


Ví dụ: Giả sử một hoán vị ( viết dưới dạng dòng như sau
(((1) ((2) … ((n)) = (5 9 1 8 2 6 4 7 3)
( bảng nghịch thế là (2 3 6 4 0 2 2 1 0).

Định lý:
Có một tương ứng 1-1 giữa tập hợp các hoán vị n phần tử và
các bảng nghịch thế.

Tính chất:
Đặt
In(k) = số các hoán vị có k nghịch thế
và qui ước In(k) = 0 nếu k < 0 hay k >
.
Ta có các tính chất:
In(0) = 0
In(1) = n-1
In
= In(k)
In(k) = In-1(k) + In-1(k-1) + . . . + In-1(k-n+1)

Số nghịch thế trung bình:
Xét hàm sinh Gn(z) của phân bố xác suất
.
Do tính chất của In(k) ta có:
Gn(z) =
(1 + z + . . . + zn-1) Gn-1(z)
( Gn(z) =
Gn-1(z)
( Gn(z) =

và
hk(z) =
=
(1 + z + . . . + zk-1)
là hàm sinh của phân bố xác suất
nên có thể tính toán được
mean(hk) =

Var(hk) =

Suy ra:
Mean(Gn) =
=

Var(Gn) =
=


Tóm lại ta có định lý sau đây:

Định lý: Số nghịch thế trúng bình là
= O(n2) với độ lệch ( = O(
).

Sắp xếp bằng cách đếm
Xét bài toán sắp xếp