Lời giải Giải SBT Tin học 11 KNTT Bài 24. Đánh giá độ phức tạp thời gian thuật toán có đáp án

Câu 1

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Đáp án đúng là: B. T2. T2 = thời gian chạy chương trình từ khi nhập xong dữ liệu input và tính xong dữ liệu output.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Đánh giá thời gian chạy của chương trình như sau: T(n) = n+2.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Đánh giá thời gian chạy của chương trình sau: T(n) = 2log2n + 2.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

Đánh giá thời gian chạy của chương trình sau, trong đó A là ma trận vuông bậc n.

T(n) = n2 + 2.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

T(n) = (3/2).n2 + (5/2)n + 1 trong trường hợp xấu nhất.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

T(n) = 2n2 – 3n + 2 trong trường hợp xấu nhất.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

T(n) = 2n2 – 2n + 1 trong trường hợp xấu nhất.

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

a) O(nlogn);

b) O(n3.logn);

c) O(5").

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý

a) Vì hiển nhiên n < n với n > 1 nên suy ra n = O(n).

b) Nếu như n2 = O(n) thì ta phải có n2 < C.n với n đủ lớn, nhưng từ bất đẳng thức này suy ra n < C. Mâu thuẫn. Vậy suy ra n = O(n).

Hướng dẫn chấm do TopStudy biên soạn, mang tính gợi ý