Bài 25.5. Xác định độ phức tạp thời gian của hàm sau:
Bài Làm:
Gọi T(n) là thời gian thực hiện của chương trình. Thời gian chạy của thuật toán được phân tích như sau:
- Lệnh gán tại dòng 2 cần 1 đơn vị thời gian
- Vòng lặp for tại dòng 3, biến i chạy từ 1 đến n, nên vòng lặp có n bước lặp
- Với mỗi bước lặp trên, chương trình thực hiện:
-
Vòng lặp tại dòng 4, biến j chạy từ 1 đến i, nên vòng lặp thực hiện i bước lặp
-
Với mỗi bước lặp:
-
Chương trình thực hiện vòng lặp tại dòng 5, biến k chạy từ j đến j + i, vòng lặp có i + 1 bước lặp.
-
Với mỗi bước lặp chương trình thực hiện 1 lệnh gán tại dòng 6 cần 1 đơn vị thời gian
- Lệnh trả về tại dòng 7 cần 1 đơn vị thời gian
Tổng hợp lại, hàm trên có thời gian chạy là:
$T(n)=2+\sum_{i=1}^{n}\sum_{j=1}^{i}(i+1)=2+\sum_{i=1}^{n}(i^{2}+i)=2\sum_{i=1}^{n}(i^{2})+\sum_{i=1}^{n}(i)$
$T(n)=2+\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}=2+\frac{n^{3}+3n^{2}+2n}{3}$
Suy ra $T(n)=O(n^{3})$
