15 câu Trắc nghiệm Tin học 11 Cánh diều Định hướng KHMT Bài 5: Đánh giá thuật toán có đáp án

Độ phức tạp thời gian của thuật toán được xác định bởi yếu tố nào?

Độ phức tạp thời gian tuyến tính được ký hiệu là gì?

Phép toán nào được coi là phép toán sơ cấp?

Thuật toán nào sau đây có độ phức tạp thời gian hằng số?

Khi ước lượng độ phức tạp thời gian của thuật toán, quy tắc nào được áp dụng?

Trong trường hợp nào thuật toán có thể có độ phức tạp thời gian tuyến tính?

Phép toán nào không được coi là sơ cấp?

Cách nào được coi là ước lượng làm giả thêm?

Khi nào độ phức tạp thời gian của thuật toán là O(n^2)?

Đặc điểm nào sau đây không thuộc về độ phức tạp thời gian hằng số?

Thuật toán nào sau đây có độ phức tạp thời gian hằng số?

a) Tính tổng dãy số bằng cách cộng dồn từng số.

b) Tính tổng dãy số bằng công thức tính tổng cấp số cộng S=

c) Tìm kiếm một phần tử trong danh sách đã sắp xếp bằng cách sử dụng thuật toán tìm kiếm nhị phân.

d) Sắp xếp một dãy số bằng thuật toán sắp xếp nổi bọt (bubble sort).

Cách nào dưới đây có độ phức tạp thời gian tuyến tính?

a) Tìm số lớn nhất trong dãy số bằng cách so sánh từng cặp.

b) Tính giai thừa của một số nguyên n bằng đệ quy.

c) Sắp xếp một dãy số bằng thuật toán Quick Sort.

d) Tìm kiếm một số trong dãy số không sắp xếp bằng cách lặp qua từng phần tử.

Tại sao cần phải ước lượng độ phức tạp thời gian của một thuật toán?

Thế nào là độ phức tạp thời gian hằng số?

Độ phức tạp thời gian tuyến tính có ý nghĩa gì trong việc đánh giá thuật toán?