PHẦN III. Câu trả lời ngắn. Thí sinh trả lời từ câu 1 đến câu 3

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?

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

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

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

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

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

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

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).