Bài liên quan:
- Cách trình bày mô tả một thuật toán chia để trị
- 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ài tập chuyên đề chia để trị cơ bản
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 13. Tính độ phức tạp của k
{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)
{8}: O(n) // đã tính ở trên yêu cầu 1
{7}: (n-i) x O(n) = O(n * (n-i))
{6}:
