Trình bày cách tính độ phức tạp của một đoạn chương trình

Các bạn ôn thi tốt nghiệp có yêu cầu mình chỉ cho các bạn cách trình bày cách tính độ phức tạp của thuật toán. Hôm nay, mình sẽ chỉ cho các bạn cách trình bày mà mình hay sử dụng. Tất nhiên là có nhiều cách trình bày lắm. Nếu trình bày bằng văn xuôi thì khá dài dòng và đôi khi dùng từ ngữ lọng cọng nữa. Mình trình bày theo cách ít dùng văn và cách này xem như là các bạn đã hiểu rõ được các nguyên tắc tính độ phức tạp.

Ví dụ có đoạn mã lệnh như sau

Yêu cầu:
1. Tính độ phức tạp của h

{3}: O(1)
{2}: O(1) x n = O(n)
 Vậy độ phức tạp của hàm h là T(n) = O(n)

2. Tính độ phức tạp của t

{8}: O(n) // đã tính ở trên yêu cầu 1
{7}: n x O(n) = O(n^2)
{6}: n x O(n^2) = O(n^3)

Vậy, độ phức tạp của hàm t là T(n) = O(n^3)

3. Tính độ phức tạp của k

{8}: O(n) // đã tính ở trên yêu cầu 1
{7}: (n-i) x O(n) = O(n * (n-i))
{6}:

Share on Google Plus

About thanh