Phân Tích Giải Thuật (môn sắp thi tốt nghiệp )

bài viết có sai chổ nào các bạn nhớ thông báo nhanh nha! để mình còn biết chổ sai của mình!

Cách Tính Thời Gian Chạy của Chương Trình không Đệ Qui.

Quy Tắc Cộng :

Trích dẫn :

P(1) : T1(n) = O( f(n) )
P(2) : T2(n) = O( g(n) )
Thời gian thực hiện của 2 chương trình nối tiếp nhau là :
T(n) = O(max( f(n), g(n) ))

Quy Tắc Nhân :

Trích dẫn :

P(1) : T1(n) = O( f(n) )
P(2) : T2(n) = O( g(n) )
Thời gian thực hiện của 2 chương trình lòng nhau là :
T(n) = O( f(n).g(n) )

Quy Tắc phân tích thời gian thực hiện

Trích dẫn :

Lệnh gán : O(1)
Lệnh đọc dữ liệu vào (read, scanf, ….) : O(1)
Lệnh viết (write, printf, …..) : O(1)
Lệnh kiểm tra điều kiện : O(1)

Chú Ý : Hằng số C có thể bỏ qua khi ta gặp các hàm : logn, n, nlogn, n2, n3, 2n, n!, n2

Thí Dụ 1 : hàm sắp xếp chọn.

Code:

void Select(){
   int i, j, k, temp ;
{1}            for( i = 0; i < n; i ++ ){
{2}               k = i ;
{3}               for( j = i+1 ; j < n ; j ++)
{4}                  if(a[j] < a[k])
                     k = j ;
{5}               temp = a[i] ;
{6}               a[i] = a[k] ;
{7}               a[k] = temp ;
   }
}

Các bạn chú ý : mình đang làm bằng ngôn ngữ C khác với pascal.

Ta thấy lệnh {1} lòng các lệnh {2}, {3} , {5}, {6}, {7}. Lệnh {3} lòng lệnh {4}
Lệnh {4} có độ phức tạp là O(1) vậy lúc này độ phức tạp của lệnh {3} và {4} chỉ phụ thuộc vào lệnh {3}.
Lệnh {3} tốn O(n-2) thời gian. do j xúât phát từ 1.
Các lệnh {2}, {5},{6},{7} đều tốn O(1) thời gian.
Các lệnh {2},{3}, {5},{6},{7}, là nối tiếp nhau.
Theo quy tắc cộng thì ta có O(max( O(1), O(n-2), O(1), O(1), O(1) ) = O(n-2)
Lệnh {1} tốn O(n-1) thời gian.
Do lệnh {1} lòng lệnh {2} nên ta có : T(n) = O( O(n-1). O(n-2) ) = O(n^2 – 3n + 2)
Vậy chương trình đã cho tốn T(n) = O(n^2 – 3n + 2) độ phức tạp.

Cách Tính Thời Gian Chạy của Chương Trình Đệ Qui

Trích dẫn :

B1. Lập phương trình đệ quy từ chương trình đã cho.
B2. Giải Phương trình đệ qui
a. Công thức có sẳn suy luận
b. Phương pháp truy hồi
B3. Nghiệm của phương tình đệ qui chính là thời gian thực hiện của chương trình đệ qui

Hướng dẫn cách lập phương trình Đệ Qui


Trích dẫn :

Gọi T(n) là thời gian giải bài tóan có kích thước n
 Gọi T(k) là thời gian giải bài tóan có kích thước K
 Gọi C(n) là thời gian đệ qui dừng.
 Gọi d(n) là thời gian phân chia bài tóan và tổng hợp các lời giải.

Thí Dụ 1 :
Tính hàm giai thừa và viết bằng giải thuật đệ qui.
Bài Làm :

Code:

double GiaiThua(unsigned int n){
      if( n < 2)
         return 1 ;
      return ( n*GiaiThua(n-1) )  ;
   }

Gọi T(n) là thời gian tính n giai thừa
Gọi T(n-1) là thời gian tính n-1 giai thừa
Gọi C(n) là thời gian đệ qui dừng ở đây là T(0) = T(1) = O(1) cụ thể là C1
Gọi d(n) là thời gian n*GiaiThua(n-1) cụ thể là C2

Vậy ta có

Trích dẫn :

T(n) = C1 nếu n = 0 , n = 1
T(n) = T(n-1) + C2 nếu n > 1

Hướng Dẫn giải phương trình đệ qui bằng phương pháp truy hồi

Thí dụ 1 :

Trích dẫn :

T(n) = C1 nếu n = 0
T(n) = T(n-1) + C2 nếu n > 0

Ta có :

T(n) = T(n-1) + C2
T(n) = (T(n-2) + C2 ) + C2 = T(n-2) + 2C2
T(n) = (T(n-3) + C2 ) + C2 = T(n-3) + 3C2
…….
T(n) = T(n-i) + iC2

Quá trình kết thúc khi i = n

T(n) = T(0) + nC2 = O(n)

Nhắc Lại :

Cấp Số Cộng :

Trích dẫn :

Sn = a1 + a2 + ... + an = n(a1 + an)/2
trong đó : an = a1 + (n-1)d (d = a2 - a1 : công sai)

Cấp số nhân :

Trích dẫn :

Sn = ar^0 + ar^1 + .... + ar^n = a(1-r^(n+1) ) / (1 - r )
hay là : Sn = ar^m + ... + ar^n = a( r^m - r^(n+1) ) / (1 - r )

cái này có thể thầy sẽ áp dụng cho giải hệ phương trình đệ qui.

Nhớ đóng góp theo nhiu nhiu nhe