TÍnh độ phức tạp của chương trình sau, dẫn chứng cụ thể, thông số cụ thể, chứng minh đúng đắn:
sum = 0;
for (j = 0; j < n; j++)
for (k = 0; k < j * j; k++)
if (k % j == 0)
for (m = 0; m < k; m++)
sum++;
Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
$\text{Gửi bạn}$
Dòng 1: sum = 0; - Độ phức tạp O(1), chỉ một phép gán.
Dòng 2: for (j = 0; j < n; j++) - Vòng lặp chạy từ 0 đến n-1, n lần. Độ phức tạp O(n).
Dòng 3: for (k = 0; k < j * j; k++) - Vòng lặp lồng trong vòng lặp trước đó, chạy j^2 lần (với giá trị của j từ vòng lặp ngoại). Độ phức tạp là O(j^2).
Dòng 4: if (k % j == 0) - Kiểm tra điều kiện trong vòng lặp. Độ phức tạp O(1).
Dòng 5: for (m = 0; m < k; m++) - Vòng lặp chạy từ 0 đến k-1 (với giá trị của k từ vòng lặp trước). Độ phức tạp O(k).
Dòng 6: sum++; - Phép toán tăng giá trị của sum mỗi khi lặp. Độ phức tạp O(1).
Tổng cộng, độ phức tạp của chương trình là O(n * j^2 * k)
$\text{Chúc bạn học tốt}$
$\text{#hoangthuyc2}$
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin