Đánh giá độ phức tạp của thuật toán (thuật giải)

Khi bạn lập trình bạn có từng suy nghĩ rằng tại sao lại có những chương trình chạy nhanh mà lại có những chương trình cùng chức năng đó lại chạy chậm và ngốn tài nguyên máy tính của bạn nhiều hơn. Bạn cố gắng tìm cách cài tiến các thuật giải của mình để chương trình chạy nhanh hơn, vậy nó nhanh đến cỡ nào. Bài viết này sẽ trang bị cho bạn một số kiến thức để đánh giá độ phức tạp thuật toán của bạn….

1. Tính hiệu quả của thuật giải:

Để giải quyết một vấn đề thường có nhiều cách. Để giải một bài toán, có thể có nhiều cách khác nhau. Cần phải lựa chọn cách “tốt nhất” theo một nghĩa nào đó.

Thế nào là một thuật giải “tốt”. Có thể nêu hai tiêu chuẩn sau:

– Đơn giản, dễ hiểu, dễ lập trình. (1)

– Cho lời giải nhanh, dùng ít tài nguyên máy tính. (2)

Thật không may là thường không thể đảm bảo đồng thời cả 2 tiêu chuẩn đó. Phải tùy theo trường hợp mà áp dụng tiêu chuẩn thứ nhất hay thứ 2.

– Nếu chỉ dùng thuật giải cho một vài lần thì tiêu chuẩn 1 quan trọng hơn tiêu chuẩn thứ 2.

– Trái lại, nếu đây là một bài toán rất phổ biến, thuật giải sẽ còn được dùng nhiều lần thì tiêu chuẩn 2 quan trọng hơn tiêu chuẩn 1.

Mục đích của việc nghiên cứu cấu trúc dữ liệu và giải thuật chính là để xây dựng các chương trình hiệu quả. Tiêu chuẩn 2 chính là tính hiệu quả của thuật giải. Một thuật giải được gọi là hiệu quả nếu nó tiết kiệm được không gian và thời gian. Tiết kiệm không gian là chiếm dụng ít bộ nhớ trong thời gian thực hiện. Tiết kiệm thời gian là chạy nhanh. Tiêu chuẩn thời gian thực hiện nhanh là quan trọng hàng đầu. Đánh giá độ phức tạp của thuật giải là đánh giá thời gian thực hiện nó. Bài toán không không phải là bài toán chưa có lời giải mà là bài toán mà việc giải nó mất một khoảng thời gian quá dài, đến mức không chấp nhận được.

2. Tại sao thuật giải cần phải có tính hiệu quả:

Máy tính ngày nay có tốc độ lên tới hàng trăm triệu phép tính trên một giây. Liệu việc cải tiến thuật giải để giảm bớt đi một số phép tính toán có ý nghĩa gì không?

Ví dụ sau đây cho thấy tầm quan trọng của một thuật giải hiệu quả. Xét bài toán tính định thức cấp n. Giả sử M = aij là ma trận vuông  n x m. Cần tính định thức det(M).

a. Thuật toán đệ quy:

–  Nếu n = 1 thí det(M) = a11 .

–   Trái lại, n > 1 sử dụng công thức khải triển theo định thức hàng để đưa về định thức cấp thấp hơn. (Ở đây chúng ta sẽ không đề cập đến cách tính toán như thế nào trong ví dụ này).

Giải thuật này sẽ cần đến  n.(n-1).(n-2)… 1 = n! phép tính nhân. Mà n! là một số rất lớn ngay khi cả n là không lớn lắm. Sẽ cần đến hàng triệu năm để tính một định thức cấp 100. Rõ ràng là không thể chấp nhận một thuật toán như thế.

b. Thuật toán sử dụng Gauss-Jordan:

–  Đưa ma trận về dạng đường chéo.

–  Tính định thức bằng tích các phần tử trên đường chéo.

Dùng thuật toán này tính định thức cấp n chỉ cần n3 phép tính. Chỉ cần không quá 1 giây để tính định thức cấp 100 trong.

–> Trong ví dụ trên, sự chênh lệch về số phép toán cần thực hiện của 2 thuật giải là rất lớn, nên lựa chọn là hiển nhiên. Tuy nhiên, ngay cả trong trường hợp việc cải tiến hiệu quả chỉ tiết kiệm được một số ít phép toán, nhưng thuật giải được sử dụng hàng triệu lần thì lợi ích mang lại cũng được nhân lên hàng triệu lần, con số đó không phải là nhỏ.

3. Đánh giá thời gian thực hiện thuật giải:

a. Tính độc lập:

Thế nào là một thuật giải nhanh. Có thể lập chương trình, chạy máy rồi bấm giờ. Tuy nhiên tốc độ thực hiện một chương trình phụ thuộc vào ngôn ngữ lập trình, chương trình dịch, hệ điều hành, phần cứng của máy… Mặt khác, phải lập trình mới đo được thời gian thực hiện của thuật giải.

Cần đánh giá thời thực hiện sao cho:

–  Không phụ thuộc máy, ngôn ngữ lập trình, chương trình biên dịch.

–  Không cần phải triển khai chương trình thực hiện thuật giải.

–  Chỉ dựa vào bản thân thuật giải.

Trong ví dụ ở phần 2, ta đã tính thời gian thực hiện thuật giải tính định thức bằng số phép tính cần tiến hành. Đây chính là cách làm đáp ứng nhu cầu trên.

b. Các phép toán sơ cấp:

Trước hết ta cần thống nhất những thao tác nào được coi là một phép tính.

Đây là khái niện phép toán sơ cấp. Các phép toán sơ cấp là những phép toán mà thời gian thực hiện nó đủ ngắn, hay nói đúng hơn là không vượt quá một hằng số nào đó. Các phép toán sau đây có thể coi là sơ cấp:

–  Các phép tính số học.

–  Các phép tính logic.

–  Các phép chuyển chỗ, gán…

c. Kích thước dữ liệu đầu vào:

Cho một thuật giải ta hoàn toàn ước lượng được tổng số các phép toán sơ cấp cần thiết để thực hiện thuật giải đó. Một điều hiển nhiên là tổng số phép toán sơ cấp để giải một bài toán phụ thuộc vào kích thước của bài toán. Dùng cùng một thuật toán, tính một định thức cấp 5 rõ ràng cần ít phép tính hơn định thức cấp 10. Tổng số mục dữ liệu đầu vào là đặc trưng cho kích thước của bài toán. Người ta thường dùng một số nguyên dương n để thể hiện kích thước này.

Như vậy, một thuật giải T áp dụng để giải bài toán có kích thước n sẽ cần một tổng số T(n) các phép toán sơ cấp. T(n) là một hàm của tham số n.

Hàm số T(n) là đặc trưng cho hiệu quả của thuật giải T.

4. Tính trạng dữ liệu đầu vào:

Không chỉ có số lượng dữ liệu đầu vào quyết định thời gian thực hiện giải thuật mà tình trạng dữ liệu cũng ảnh hưởng đến việc thuật giải thực hiện nhanh hay chậm.

Xét bài toán sắp xếp một dãy số. Rõ ràng là nếu dãy đã có sẵn thứ tự mong muốn hoặc gần thư thế thì công việc phải làm ít hơn trường hợp một dãy bất kỳ.

Hoặc bài toán tìm kiếm tuần tự trong một dãy số cho sẵn như tìm vị trí của phần tử k trong mảng a[0, 1, n-1] (nếu k tồn tại trong mảng a).

int SequentialSearch(int a[], int n, int k)
{
for(int i = 0; i < n; i++ )
{
if( k == a[i])
return i; // i la vi tri cua k trong mang a[]
}
return -1;
}

–  Trường hợp mới bắt đầu tìm kiếm gặp ngay phần từ k thì đây là trường hợp tốt nhất (best case) C(n) = 1.

–  Trường hợp tìm kiếm mà không có k trong mảng hay k nằm ở cuối mảng thì đây là trường hợp xấu nhất, phải duyệt qua tất cả các phần tử của mảng a[] (worst case). C(n) = n.

–  Trường hợp trung bình C(n)  = C(n)trung bình = 0, 5. p(n + 1) + n(1 – p).

** Tùy theo tình trạng dữ liệu đầu vào mà ta có các trường hợp:

–  Thuận lợi nhất C(n) là nhỏ nhất, ta ký hiệu là Cmin (best case).

–  Bất lợi nhất  C(n) là lớn nhất, ta ký hiệu là Cmax (worst case).

–  Ngẫu nhiên T(n) là trung bình, ta ký hiệu là Taver (average case).

–> Hợp lý nhất là dùng ước lượng thời gian thực hiện trung bình Taver để so sánh đánh giá thuật giải. Nếu tính thời gian thực hiện trung bình quá khó khăn, có theer đánh giá căn cứ vào trường hợp xấu nhất, tức là dùng Tmax. Thậm chí, nhiều bài toán thời gian thực đòi hỏi thời gian trả lời phải không vượt quá một giới hạn cho trước nào đó. Trong trường hợp này, chỉ có thể dùng ước lượng trong trường hợp xấu nhất, nghĩa là Tmax mà thôi.

5. Ký hiệu O (Big – O) và các vô cùng lớn:

a. Tốc độ tăng:

Giả sử để giải cùng một bài toán có hai giải thuật giải T1 , T2 với thời gian thực hiện tương ứng là:

T1(n) = C1(n),image

T2(n) = C2n2

Ở đây C1, C2 là các hằng số. Thế thì khi n đủ lớn chắc chắn T2(n) sẽ lớn hơn T1(n), dù rằng C1 Có lớn hơn C2 nhiều lần. Tôi nói đến điều này để chúng ta thấy rằng trong lĩnh vực các vô cùng lớn các hằng số không quan trọng. Độ lớn phụ thuộc chủ yếu vào tốc độ tăng của T(n) khi n tăng.

Ký hiệu O lớn được đặt ra nhằm mục đích loại bỏ các thành phần không quan trọng, làm rõ tốc độ tăng nói trên.

b. Ký hiệu O lớn (Big-O)

–  Định nghĩa: Giả sử  f(n), g(n) là 2 hàm số không âm, đồng biến theo n. Ta nói “f(n) là O lớn của  g(n)” và viết:    f(n) = O(g(n)).

khi và chỉ khi tồn tại hằng số C để f(n) <= C.g(n) kể từ n >= n0 nào đó.

Ta nói f(n) có cấp lớn không vượt quá g(n) (dễ hiểu là f(n) có tăng tới đâu đi nữa cũng không thể vượt quá  tốc độ tăng của g(n)).

Ví dụ:    f(n) = 2(n*n) + 3n + 5.

f(n ) <= 2(n*n) + 3(n*n) + 5(n*n) = 12(n*n)

với mọi n >= 1. Ta viết   f(n) = O(n2)

Viết T(n) = O(g(n)) nghĩa là tốc ọộ tăng của T(n) khi tiến đến vô cùng không vượt quá tốc độ tăng của g(n). Khi n lớn, g(n) cho ta hình dung được mức lớn của T(n).g(n) là “thước đo” độ lớn của T(n).

Các thuộc tính của big-O

image

c. Các đơn vị đo tốc độ tăng

Người ta thường cố gắng ước lượng g(n) sao cho sát với T(n) nhất và có dạng đơn giản nhất để dễ hình dung.

Bảng các vô cùng lớn thường dùng

image

Bảng trên cung cấp các “thước đo” thời gian thực hiện giải thuật giải hay dùng nhất và tên gọi thông thường của chúng.

Trong các đánh giá về thời gian thực hiện thuật giải, chủ yếu sẽ dùng các hàm logarit cơ số 2. Do đó, để đơn giản ta viết log n thay cho logarit cơ số 2 của n. Các logarit cơ số khác sẽ được chỉ rõ.

– T(n) = O(1): thời gian thực hiện giải thuật không quá một hằng số nào đó, không phụ thuộc vào n. Ta nói thuật giải có thời gian hằng số.

– T(n) = O(n): ta nói thuật giải có tốc độ tăng tuyến tính.

– T(n) = O(2n): ta nói thuật toán có độ tăng theo hàm mũ.

Bảng so sánh dưới đây giúp chúng ta dễ hình dung độ lớn của các mức thời gian thực hiện thuật giải nói trên:

Log n n n.log n n2 n3 2n
0 1 0 1 1 2
1 2 2 4 8 4
2 4 8 16 64 16
3 8 24 64 512 256
4 16 64 256 4096 65536
5 32 160 1024 32768 4,292,967,296

Rõ ràng là khi thời gian thực hiện thuật giải tăng với tốc độ hàm mũ thì độ lớn tăng rất nhanh. Những bài toán mà chưa tìm được thuật giải với thời gian dưới cấp hàm mũ, nghĩa là từ thời gian đa thức thức trở xuống, sẽ được xếp vào loại bài toán khó.

6. Big- Omega (Ω) và Big-Theta (Θ)

Tương tự như với bậc big-O, nếu như tìm được các hằng số C,k1,k2 đều dương và không phụ thuộc vào n, sao cho với n đủ lớn, các hàm R(n),f(n) và h(n) đều dương và

R(n)\geq C \cdot f(n)
k_1\cdot h(n) \leq R(n) \leq k_2\cdot h(n)

thì ta nói thuật toán có độ phức tạp cỡ lớn hơn Ω(n), và đúng bằng cỡ Θ(h(n)).

Như vậy nếu xét một cách chặt chẽ, kí hiệu Θ mới biểu thị độ phức tạp của thuật toán một cách chặt chẽ.

Do đó 2 ký hiệu thường được sử dụng trong đánh giá độ phức tạp của thuật toán là Big-O và Big Theta. Nhưng chúng ta thường sử dụng Big-O hơn.

7.  Cách xác định thời gian thực hiện một thuật giải:

a. Quy tắc tổng

Nếu     T1(n) = O(f(n)), T2(n) = O(g(n)),

thì       T1(n) + T2(n) = O( max {f(n), g(n)} );

Ví dụ:  Thuật giải gồm 2 thủ tục kế nhau  P = { P1, P2 }

P1 có thời gian là T1(n) = O(f(n)),

P2 có thời gian là T2(n) = O(g(n)),

Thời gian thực hiện P là T(n) = T1(n) + T2(n) = O ( max { f(n), g(n) }).

b. Tính thời gian thực hiện của các câu lệnh trong ngôn ngữ lập trình:

Dưới đây là thể hiện trình bày, ta quy ước gọi  f(n), fi(n) là thời gian thực hiện câu lệnh S, Si  tương ứng.

–  Câu lệnh đơn: các câu lệnh đơn như gán, đọc, viết, so sánh,… có thời gian thực hiện là O(1)

–  Lệnh ghép:   S = S1 = S2, …, = Sp;   tính thời gian thực hiện theo quy tắc tổng.

–  Lệnh rẽ nhánh:  if <điều kiện>  S1;  else S2;

tính thời gian thực hiện là  O( max { f1(n), f2(n) }).

–  Lệnh lựa chọn: case    tính thời gian tương tự như if.

–  Lệnh vòng lặp:  While< điều kiện> { S }  ;  tính thời gian thực hiện là  (số lần lặp) * f(n)

–  Vòng lặp  for tương tự như while.

Ví dụ:

Tính  ex

ex  = 1 + ( x/1!) + (x*x/2!) + (x*x*x/ 3!) + … + (xn /n!)

Thuật giải 1:

double SumDevideFactorial(int n)
{
double S = 1;
double p = 1;
for(int i = 1; i <= n; i++)
{
for(int j = 1;  j <= i;  j++)
{
p = p*x/ j;
S += p;
}
}
return S;
}
Vòng for bên trong có số phép toán bằng i.
Tổng số phép toán  T(n) = 1 + 2+ … + n = (n( n –1 ))/ 2 = O(n2)
Thuật Giải 2
Kế thừa, dùng kết quả của bước trước, tính số hạng sau qua số hạng trước.
x/n! = (x/n ) .  (xn-1/(n-1)!)
double SumDevideFactorial(int n)
{
double S = 1;
double p = 1;
for(int i = 1; i <= n; i++)
{
p = p*x/ i;
S += p;
}
return S;
}
Tổng số phép toán T(n) = O(n).
Như vậy giải thuật 2 tối ưu hơn giải thuật 1.
Advertisements

About thanhcuong1990

Handsome and talent!! ^^
This entry was posted in Data structure and Algorithms. Bookmark the permalink.

23 Responses to Đánh giá độ phức tạp của thuật toán (thuật giải)

  1. Phước Đại says:

    Cho mình hỏi: Tại sao nói độ phức tạp về thời gian là quan trọng nhất?

    • Nói về độ phức tạp của thuật toán thì độ phức tạp về thời gian là quan trọng nhất, bởi vì nếu một thuật toán cho ra một kết quả đúng nhưng thời gian thực hiện thuật toán cần một khoảng thời gian lớn đến nỗi không thể chấp nhận được (Ví dụ bài toán tháp Hà Nội nếu dùng đệ quy để tính toán thì với tốc độ máy tính hiện nay phải giải nó khoảng vài ngàn năm). Do đó yêu cầu thời gian được đưa ra đầu tiên. Thuật toán được gọi là hay thì phải có thời gian thực hiện ngắn và tiết kiệm tài nguyên máy tính. Sự hao phí tài nguyên máy tính liên quan đến phần cứng máy tính. Vì vậy mà những thuật toán đưa ra thường lấy thời gian để tính độ phức tạp hơn là tài nguyên (vì mỗi máy khác tài nguyên).
      (Ở đây nói đên thuật toán cho ra kết quả đúng).

  2. tlta. says:

    cái thuật giải 1 của Emu(x) phải đặt S+=p; ra ngoài vòng for trong cùng chứ anh.

  3. tlta. says:

    anh cho em hỏi cái nè.khó quá.em nghỉ nát đầu ko ra.
    nếu chương trình A chạy với thời gian tồi nhất là theta(N) còn chương trình B chạy với thời gian tồi nhất là theta(NlogN),hỏi chương trình A có chạy nhanh hơn B trên hầu hết các dữ liệu đầu vào ko.

    • Đối với những cách đánh giá thuật giải trên chỉ là mang tính ước lượng tương đương. Vì vậy, nếu chương trình A chạy với thời gian tồi nhất là theta(N) còn chương trình B chạy với thời gian tồi nhất là theta(NlogN) thì chưa chắc A chạy nhanh hơn B trong mọi dữ liệu đầu vào. Với dữ liệu đầu vào lớn và phức tạp thì có thể mọi chuyện sẽ thay đổi. 😀

  4. tlta. says:

    em cảm ơn anh nhiều.

  5. tomasino says:

    Anh cho em tài liệu trắc nghiệm môn Phân tích thiết kế thuật toán nha.
    Chỉ em cách nhanh nhất hay bí quyết (mẹo) gì đó tính độ phức tạp của thuật toán lun nha.

    • Chào bạn!
      Hiện mình không có tài liệu trắc nghiệm môn này. Còn để tính độ phức tạp của thuật toán nhanh thì bạn phải áp dụng cách tính mình nêu trên để giải quyết những thuật toán thông thường. Sau đó thuộc vô đánh lại là nhanh thôi.

      • tomasino says:

        Mấy bài thông thường thì cũng làm được những khổ nỗi thi thường cho khó chứ rất ít những câu đơn giản, nhất là tính độ phức tạp của giải thuật có vòng lặp, em còn chưa hiểu rõ cách tính, có câu tính được, câu ko. Mấy câu có vòng lặp while thường khó tính.
        Giúp em cách tính nó đi.
        Ak, anh có biết độ phức tạp của giải thuật đệ quy tìm dãy Fibonacci là = mấy ko?

  6. Quỳnh says:

    Có thể cho mình một ví dụ cụ thể hơn không?

  7. Nguyễn Văn Quyền says:

    anh ơi em đang học phương pháp số về bài phương pháp lặp đơn nhưng trong câu hỏi lại có câu đánh giá độ phức tạp của thuật toán vs lưu đồ thuật toán anh giúp em với

  8. Anh à , cảm ơn anh vì bài viết nhiều .. anh có thể cho thêm ví dụ đánh giá thời gian thực hiện
    đối với các phương pháp nhánh cận và quy hoạch động được không anh

  9. đạt says:

    anh có thể cho mấy ví dụ về tính độ phức tạp của thuật toán là logn và n*logn
    được không ạ

    • đạt says:

      và cho em hỏi cái chỗ anh :
      for(int i = 0; i < n; i++)
      {
      p = p*x/ i;
      S += p;
      }
      thì i =0 thì chia kiểu gì hả anh ???

      • Hoàng Khôi says:

        chạy 0 tới n-1 đó bạn, cũng tương đương là chạy từ 1 đến n.nên cũng là n lần.Độ phức tạp của thuật toán này là T(n) = O(n)

  10. Name says:

    tưởng thế lào, hóa ra copy paste

  11. Thanh says:

    ma trận vuông n x m là sao vậy bạn?

  12. thuc says:

    thuật toán nhập số n và mảng a, sau đó hiển thị ra độ chênh lệch nhỏ nhất của bên trái và bên phải.

  13. Vũ Anh Hào says:

    Cái này phức tạp nhể

  14. quang says:

    thuật toán thì viết sai… i=0 thì chia làm sao đc.. có mấy bạn cmt thắc mắc chổ đó thì ko trả lời

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s