Xác định độ phức tạp và thời gian chạy

[Nguyen_Minh10 (Nguyen Minh)]

Nhờ mọi người cho mình xin đáp án 3 câu này ạ, mình có đọc tài liệu nhưng không hiểu. Cảm ơn mọi người.

Câu 1: Phép toán chạy nhiều nhất (dominant) trong đoạn mã dưới đây là:

int s = 0;
for (int i = 0; i<=n; i++)
    for (int j = 0; j<=n; j++)
s += a[i, j];

• A. s = 0
• B. i <= n
• C. j = 0
• D. sum += a[i, j]

Câu 2: Độ phức tạp của thuật toán ở câu 1 là:

• A. O(1)
• B. O(n)
• C. O(n²)
• D. O(n² / n)

Câu 3: Độ phức tạp của thuật toán tính e^x dưới đây là:

double Exp(int n, int x)
{
    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;
}

• A. O(n)
• B. O(nlog(n))
• C. O(n²)
• D. O(2n²)

[noz1995 (Trần Hoàn)]

Câu 1: Tất cả đều sai, đáp án đúng là j<=n nếu n ≥ 1

[Sherly1001]

Đâu cần làm quá lên vậy đại ca . Cơ mà đúng hơn phải là nếu n ≥ 0 cơ. Nhỏ hơn 0 thì chạy 1 lần int i = 0 và j <= n.

Nhưng mà đề trắc nghiệm (đại ca xem ảnh gốc ở lịch sử edit) chứ có phải tự luận đâu mà được chỉ ra cái sai, cứ an phận mà chọn đáp án đúng nhất, thi xong rồi báo cáo lại thôi.

[Nguyen_Minh10 (Nguyen Minh)]

Cảm ơn mọi người rất nhiều ạ