Ðộ Phức Tạp Của Chương Trình Có Gọi Chương Trình Con Không Đệ Qui

Ví dụ 1.3.

Giải thuật tính giá trị của ex theo công thức gần đúng:

ex = 1 + x/1! +x2/2! + …+ xn/n! với x và n cho trước EXP1();

{

scanf(x) ; S =1;

for (i=1;i<=n;i++)

{

p =1;

for(j=1;j<=i;j++) p=p*x/j; S = S +p;

Có thể bạn quan tâm!

Xem toàn bộ 205 trang tài liệu này.

}

Ta có thể coi phép toán tích cực ở đây là phép: p = p*x/j Ta thấy nó được thực hiện: 1 +2+…+ n = n(n+1)/2 lần

Vậy độ phức tạp tính toán của thuật toán này được đánh giá là T(n) = O(n2)

Thuật toán có thể được viết theo một cách khác: EXP2()

{

scanf(x); S =1;

P =1;

for (i=1;i<=n;i++)

{

p =p*x/i; S =S + p;

}

Bây giờ độ phức tạp tính toán lại là: T(n) = O(n). Vì phép gán p=p*x/i chỉ thực hiện n lần.

Ví dụ 1.4.

Thuật toán sắp xếp kiểu nổi bọt void Bubble(a)

{

for(i=1;i<=n-1; i++) for(j=n; j>=i+1; j--)

if (a[j-1]>a[j])

{

tg:= a[j-1];

a[j-1] := a[j]; a[j]:= tg;

}

Trong thuật toán ta coi phép so sánh (a[j-1]>a[j]) là phép toán tích cực. Phép

toán này nằm trong vòng lặp for(j=n; j>=i+1; j--) nên nó được thực hiện (n-i) lần. Vòng lặp for(j=n; j>=i+1; j--) nằm trong vòng lặp for(i=1;i<=n-1; i++) thực hiện

(n-1) lần. Do vậy số lần thực hiện phép toán tích cực (a[j-1]>a[j]) sẽ là:

n1

( n i ) n( n 1 )

i12

Nên độ phức tạp tính toán của thuật toán là O(n2).

Chú ý:

Ta biết rằng thời gian thực hiện thuật toán không phải chỉ phụ thuộc vào kích thước dữ liệu mà còn phụ thuộc vào tình trạng dữ liệu nhập nữa. Chẳng hạn, khi xếp tăng dần một dãy các số nguyên mà dãy các so nguyên đĩ đã có sẵn thứ tự tăng dần, hoặc ngược lại, hoặc ngẫu nhiên. Lúc đó khi phân tích thời gian thực hiện thuật toán ta sẽ phải xét tới: đối với mọi dữ liệu vào có kích thước n thì T(n) trong trường hợp tốt nhất, xấu nhất là như thế nào? T(n) trung bình? Việc xác định T(n) trung bình thường khó và phức tạp đòi hỏi những công cụ toán học đặc biệt, hơn nữa việc tính trung bình có thể có nhiều cách quan niệm khác nhau. Trong trường hợp T(n) khó xác định người ta thường đánh giá thuật toán qua giá trị xấu nhất của T(n)

VÝ dô 1.5.

timkiem(v)

/*Cho vectơ V có n phần tử, thuật toán này thực hiện tìm trong V một phần tử có giá trị bằng X cho trước. Nếu tìm thấy trả về chỉ số của phần tử đó, nếu không tìm thấy trả về giá trị 0*/

i =1;

while ((V[i] !=X)&& (i<= n)) i= i+1; if (i<=n) return(i);

else return(0);

Coi phép toán tích cực ở đây là phép so sánh V[i] với X. Có thể thấy số lần phép toán thực hiện phụ thuộc vào chỉ số i mà V[i] = X. Trường hợp thuận lợi nhất xảy ra khi X bằng V[1]: một lần thực hiện.

Trường hợp xấu nhất khi X bằng V[n] hoặc không tìm thấy: n lần thực hiện Vậy: Ttốt = O(1) và Txấu = O(n)

Thì ta xác định độ phức tạp tính toán của thuật toán là O(n)

* Qui tắc tổng quát để phân tích một chương trình:

Giả sử rằng, các lệnh gán không chứa các lời gọi hàm. Khi đó để đánh giá thời gian thực hiện một chương trình, ta có thể áp dụng một số quy tắc sau

1. Thời gian thực hiện các lệnh đơn: gán, đọc, viết là O(1)

2. Lệnh hợp thành (khối lệnh) : thời gian thực hiện lệnh hợp thành được xác định bởi luật tổng.

3. Lệnh if : Giả sử thời gian thực hiện các lệnh S1, S2 là O(f(n)) và O(g(n)) tương ứng. Khi đó thời gian thực hiện lệnh if là O(max (f(n), g(n)))

4. Lệnh witch: Lệnh này được đánh giá như lệnh if

5. Lệnh while : Giả sử thời gian thực hiện lệnh S (thân của while) là O(f(n)).

Giả sử g(n) là số tối đa các lần thực hiện lệnh S. Khi đó thời gian thực hiện lệnh while là O(f(n)g(n)).

6. Lệnh do ...while :Giả sử thời gian thực hiện khối lệnh trong thân do ... while là O(f(n)). Giả sử g(n) là số lần tối đa các lần thực hiện khối lệnh trong thân do ... while . Khi đó thời gian thực hiện lệnh do ... while là O(f(n)g(n)).

7. Lệnh for : Lệnh này được đánh giá tương tự như lệnh while.

1.5.3. Ðộ phức tạp của chương trình có gọi chương trình con không đệ qui

Nếu chúng ta có một chương trình với các chương trình con không đệ quy, để tính thời gian thực hiện của chương trình, trước hết chúng ta tính thời gian thực hiện của các chương trình con không gọi các chương trình con khác. Sau đó chúng ta tính thời gian thực hiện của các chương trình con chỉ gọi các chương trình con mà thời gian thực hiện của chúng đã được tính. Chúng ta tiếp tục quá trình đánh giá thời gian thực hiện của mỗi chương trình con sau khi thời gian thực hiện của tất cả các chương trình con mà nó gọi đã được đánh giá. Cuối cùng ta tính thời gian cho chương trình chính.

Giả sử ta có một hệ thống các chương trình gọi nhau theo sơ đồ sau:

Hình 1.2. Chương trình gọi chương trình con không đẹ quy

Chương trình A gọi hai chương trình con là B và C, chương trình B gọi hai chương trình con là B1 và B2, chương trình B1 gọi hai chương trình con là B11 và B12.

Ðể xác định độ phức tạp tính toán của A, ta thực hiện theo các bước sau:

1. Xác định độ phức tạp tính toán của C, B2, B11 và B12. Vì các chương trình con này không gọi chương trình con nào cả.

2. Xác định độ phức tạp tính toán của B1. Vì B1 gọi B11 và B12 mà độ phức tạp tính toán của B11 và B12 đã được tính ở bước 1.

3. Xác định độ phức tạp tính toán của B. Vì B gọi B1 và B2 mà độ phức tạp tính toán của B1 đã được tính ở bước 2 và độ phức tạp tính toán của B2 đã được tính ở bước 1.

4. Xác định độ phức tạp tính toán của A. Vì A gọi B và C mà độ phức tạp tính toán của B đã được tính ở bước 3 và độ phức tạp tính toán của C đã được tính ở bước 1.

Ví dụ 1.6.

Thuật toán sắp xếp nổi bọt.

Trước hết viết thủ tục Swap để thực hiện việc hoàn đổi hai phần tử cho nhau, sau đó trong thủ tục Bubble, khi cần sẽ gọi đến thủ tục Swap này.

void Swap (x, y)

{

temp = x; x = y;

y = temp;

}

void Bubble (a)

{

for(i=1;i<=n-1; i++) for(j=n; j>=i+1; j--)

if (a[j-1]>a[j])

Swap(a[j-1], a[j]);

}

Trong cách viết trên, hàm Bubble gọi hàm Swap, do đó để tính độ phức tạp tính toán của Bubble, trước hết ta cần tính độ phức tạp tính toán của Swap. Dễ thấy độ phức tạp tính toán của Swap là O(1) vì nó chỉ bao gồm 3 lệnh gán. Do vậy ta có thể coi phép toán tích cực là phép so sánh (a[j-1]>a[j]) và khi đó dễ thấy độ phức tạp tính toán của thuật toán là:

1.5.4. Phân tích các thuật toán đệ quy

Nhiều thuật toán dựa trên sự phân rã đệ qui một bài toán lớn thành các bài toán nhỏ, rồi dùng lời giải các bài toán nhỏ để giải bài toán ban đầu. Thời gian chạy của thuật toán như thế được xác định bởi kích thước và số lượng các bài toán con và giá phải trả của sự phân rã. Nên các thuật toán đệ qui có thời gian chạy phụ thuộc vào thời gian chạy cho các dữ liệu nhập có kích thước nhỏ hơn, điều này được diễn dịch thành một công thức toán học gọi là công thức truy hồi hay phương trình truy hồi, hệ thức truy hồi. Do đó, để tính độ phức tạp của thuật toán, ta thường phải giải các phương trình truy hồi.

Với các thuật toán có các lời gọi đệ quy, ta không thể áp dụng cách tính như vừa

trình bày trong mục 1.3.3 bởi vì một chương trình đệ quy sẽ gọi chính bản thân nó. Có thể thấy hình ảnh chương trình đệ quy A như sau:

Hình 1.3. Chương trình đệ quy A

Với các chương trình đệ quy, trước hết ta cần thành lập các phương trình truy hồi, sau đó giải phương trình truy hồi, nghiệm của phương trình truy hồi sẽ là thời gian thực hiện của chương trình đệ quy.

1) Thành lập phương trình truy hồi

Phương trình truy hồi là một phương trình biểu diễn mối liên hệ giữa T(n) và T(k), trong đó T(n) là thời gian thực hiện chương trình với kích thước dữ liệu nhập là n, T(k) thời gian thực hiện chương trình với kích thước dữ liệu nhập là k, với k <

n. Ðể thành lập được phương trình truy hồi, ta phải căn cứ vào chương trình đệ quy.

Thông thường một chương trình đệ quy để giải bài toán kích thước n, phải có ít nhất một trường hợp dừng ứng với một n cụ thể và lời gọi đệ quy để giải bài toán kích thước k (k<n).

Để thành lập phương trình truy hồi, ta gọi T(n) là thời gian để giải bài toán kích thước n, ta có T(k) là thời gian để giải bài toán kích thước k. Khi dừng, ta phải xem xét khi đó chương trình làm gì và tốn hết bao nhiêu thời gian, chẳng hạn thời gian này là c(n). Khi đệ quy chưa dừng thì phải xét xem có bao nhiêu lời gọi đệ quy với kích thước k ta sẽ có bấy nhiêu T(k). Ngoài ra ta còn phải xem xét đến thời gian để phân chia bài toán và tổng hợp các lời giải, chẳng hạn thời gian này là d(n).

Dạng tổng quát của một phương trình truy hồi sẽ là:

Trong đó C(n) là thời gian thực hiện chương trình ứng với trường hợp đệ quy dừng. F(T(k)) là một đa thức của các T(k), d(n) là thời gian để phân chia bài toán và tổng hợp các kết quả.

Chú ý:

Trong khi đánh giá độ phức tạp tính toán của thuật toán thì với T( 2 ) ta sẽ

n n n

hiểu 2 là 2  hoặc 2 

(Với x là một số thực thì:

x là số nguyên lớn nhất nhỏ hơn hoặc bằng x

x là số nguyên nhỏ nhất lớn hơn hoặc bằng x)

Ví dụ 1.7.

Xét hàm tính giai thừa viết bằng thuật toán đệ quy như sau: int Giai_thua(n)

{

if (n<=1) gt=1;

else gt=n* Giai_thua(n-1); return(gt);

}

Gọi T(n) là thời gian thực hiện việc tính n giai thừa, thì T(n-1) là thời gian thực hiện việc tính n-1 giai thừa. Trong trường hợp n <=1 thì chương trình chỉ thực hiện một lệnh gán gt=1, nên tốn O(1), do đó ta có T(1) = C1. Trong trường hợp n>1 chương trình phải gọi đệ quy Giai_thua(n-1), việc gọi đệ quy này tốn T(n-1), sau khi có kết quả của việc gọi đệ quy, chương trình phải nhân kết quả đó với n và gán cho gt. Thời gian để thực hiện phép nhân và phép gán là một hằng C2. Vậy ta có:

T(n) =

C1 nếu n 1

T(n-1)+C2 nếu n >1

Ðây là phương trình truy hồi để tính thời gian thực hiện của chương trình đệ quy Giai_thua.

2) Giải phương trình truy hồi

Một số phương pháp giải phương trình truy hồi:

* Phương pháp thay thế

Dùng đệ quy để thay thế bất kỳ T(m) với m < n vào phía phải của phương trình cho đến khi tất cả T(m) với m > 1 được thay thế bởi biểu thức của các T(1) hoặc T(0). Vì T(1) và T(0) luôn là hằng số nên chúng ta có công thức của T(n) chứa các số hạng chỉ liên quan đến n và các hằng số. Từ công thức đó ta suy ra T(n).

VÝ dô 1.8.

Hàm tính n! trong ví dụ 1.7. int Giai_thua(n)

{

if (n<=1) gt=1;

else

gt=n* Giai_thua(n-1); return(gt);

}

Ta đã có phương trình truy hồi để tính thời gian thực hiện của chương trình đệ quy Giai_thua là:

T(n) =

C1 nếu n 1

T(n-1)+C2 nếu n >1

- Với n  1, chỉ cần thực hiện lệnh gán gt = 1, do đó T(1) = O(1).

- Với n > 1. cần thực hiện lệnh gán gt= n*Giai_thua(n - 1).

Do đó thời gian T(n) là O(1) (để thực hiện phép nhân và phép gán) cộng với T(n-1) (để thực hiện lời gọi đệ qui Giai_thua(n – 1)). Tóm lại, ta có quan hệ sau:

T(1) = O(1)

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

Thay các O(1) bởi các hằng nào đó, ta nhận được quan hệ sau T(1) = C1

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

Để giải phương trình truy hồi, tìm T(n), chúng ta áp dụng phương pháp thế lặp. Ta có phương trình truy hồi

T(m) = C2 + T(m-1), với m > 1

Thay m lần lượt bởi 2, 3,..., n - 1, n, ta nhận được các quan hệ sau: T(2) = C2 + T(1)

T(3) = C2 + T(2)

.......

T(n -1) = C2 + T(n -2)

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

Bằng các phép thế liên tiếp, ta nhận được T(n) = (n - 1) C2 + T(1)

hay T(n) = (n - 1) C2 + C1, trong đó C1 và C2 là các hằng nào đó.