Câu 1: Độ phức tạp thời gian của thuật toán phản ánh đại lượng nào sau đây?

A. Tổng thời gian thực tế tính bằng giây đồng hồ mà CPU cần để chạy hết chương trình.

B. Dung lượng bộ nhớ RAM tối đa mà thuật toán chiếm dụng trong quá trình khởi chạy.

C. Số lượng các phép tính sơ cấp cần thực hiện tùy thuộc vào kích thước dữ liệu đầu vào n.

D. Tổng số dòng lệnh (lines of code) mà lập trình viên đã viết trong tệp mã nguồn.

Câu 2: Trong ký hiệu Big-O (O lớn), quy tắc nào sau đây là đúng khi xác định độ phức tạp của hàm T(n)?

A. Cộng tất cả các số mũ của biến n lại với nhau để ra kết quả ước lượng cuối cùng.

B. Chỉ giữ lại hạng tử có bậc cao nhất và bỏ qua các hệ số hằng số đi kèm.

C. Phải giữ nguyên hệ số đứng trước n để đảm bảo tính chính xác tuyệt đối của phép toán.

D. Nếu biểu thức có hàm logarit thì luôn bỏ qua hàm logarit và chỉ giữ lại hàm mũ.

Câu 3: Cho hàm thời gian thực hiện T(n) = 5n² + 100n + log(n). Độ phức tạp O lớn của thuật toán là:

A. O(n)

B. O(n²)

C. O(100n)

D. O(n² + n)

Câu 4: Một đoạn chương trình chỉ gồm các lệnh gán, phép tính cộng trừ đơn giản và không có vòng lặp hay gọi đệ quy. Độ phức tạp thời gian là:

A. O(n)

B. O(0)

C. O(∞)

D. O(1)

Câu 5: Đoạn mã Python for i in range(n): s = s + 1 có độ phức tạp là bao nhiêu?

A. O(1)

B. O(n)

C. O(n²)

D. O(log n)

Câu 6: Hai vòng lặp lồng nhau for i in range(n): for j in range(n): ... có độ phức tạp là:

A. O(n)

B. O(2n)

C. O(n²)

D. O(n log n)

Câu 7: Xét đoạn mã gồm hai vòng lặp nối tiếp nhau (không lồng nhau). Độ phức tạp của đoạn mã này là:

A. O(n²) vì code có sự xuất hiện của hai lệnh for riêng biệt.

B. O(n) vì quy tắc cộng O(n) + O(n) = O(2n) ≈ O(n).

C. O(1) vì các lệnh in ra màn hình thực thi rất nhanh.

D. O(nⁿ) vì hai biến i và j hoạt động độc lập với nhau.

Câu 8: Thuật toán tìm kiếm nhị phân (Binary Search) trên dãy đã sắp xếp có độ phức tạp thời gian là:

A. O(n)

B. O(n²)

C. O(log n)

D. O(1)

Câu 9: Đoạn mã i = 1; while i < n: i = i * 2 thực hiện công việc gì và có độ phức tạp bao nhiêu?

A. In các số từ 1 đến n, độ phức tạp O(n).

B. In các lũy thừa của 2, độ phức tạp O(log n).

C. In các số chẵn, độ phức tạp O(n/2).

D. Vòng lặp vô hạn, độ phức tạp không xác định.

Câu 10: Nếu kích thước dữ liệu đầu vào n tăng gấp đôi, thời gian chạy của thuật toán có độ phức tạp O(n²) sẽ tăng lên gấp bao nhiêu lần (về mặt lý thuyết)?

A. 2 lần.

B. 8 lần.

C. Không thay đổi.

D. 4 lần.

Câu 11: Hãy sắp xếp các độ phức tạp sau theo thứ tự tăng dần về thời gian thực hiện (hiệu quả giảm dần):

A. O(n) < O(1) < O(n²)

B. O(1) < O(log n) < O(n) < O(n²)

C. O(n²) < O(n) < O(log n) < O(1)

D. O(log n) < O(1) < O(n²) < O(n)

Câu 12: Đoạn mã for i in range(10000): print("Xin chào") (với n là đầu vào chương trình) có độ phức tạp là:

A. O(n)

B. O(n²)

C. O(1)

D. O(10000n)

Câu 13: Trong trường hợp xấu nhất, thuật toán tìm kiếm tuần tự (Linear Search) cần thực hiện bao nhiêu phép so sánh?

A. 1 lần.

B. log₂ n lần.

C. n/2 lần.

D. n lần.

Câu 14: Tại sao độ phức tạp O(log n) được đánh giá tốt hơn O(n) rất nhiều khi n lớn?

A. Vì hàm logarit luôn trả về kết quả là số âm nên thời gian chạy giảm đi.

B. Vì O(n) tốn bộ nhớ RAM của máy tính hơn O(log n).

C. Vì khi n tăng rất nhanh (ví dụ 1 tỷ), log n tăng rất chậm (chỉ khoảng 30).

D. Vì máy tính xử lý phép tính logarit nhanh hơn phép tính cộng.

Câu 15: Xét hàm tính tổng các phần tử của một danh sách A. Độ phức tạp của hàm này phụ thuộc vào điều gì?

A. Giá trị cụ thể của các phần tử nằm trong danh sách A.

B. Số lượng phần tử (độ dài) của danh sách A.

C. Tên của biến được dùng để lưu kết quả tổng.

D. Tốc độ gõ phím của người dùng khi nhập liệu.

Câu 16: Ba vòng lặp lồng nhau (vòng for k nằm trong j, vòng j nằm trong i) có độ phức tạp là:

A. O(n)

B. O(n²)

C. O(n³)

D. O(3n)

Câu 17: Một thuật toán có thời gian chạy là T(n) = n log n + n². Độ phức tạp Big-O là:

A. O(n)

B. O(n log n)

C. O(n²)

D. O(n² log n)

Câu 18: Khi phân tích độ phức tạp, thao tác “Truy cập một phần tử trong mảng qua chỉ số” (ví dụ A[5]) tốn chi phí là:

A. O(n) vì phải đếm từ đầu danh sách.

B. O(1) (Truy cập trực tiếp).

C. O(log n) vì bộ nhớ sắp xếp theo cấu trúc cây.

D. Phụ thuộc vào độ lớn giá trị của phần tử đó.

Câu 19: Giả sử máy tính thực hiện được 10⁸ phép tính/giây. Nếu thuật toán có độ phức tạp O(n²) và n = 100.000, thời gian chạy ước tính là:

A. Chạy xong ngay lập tức (dưới 1 giây).

B. Khoảng 10 giây.

C. Khoảng 100 giây (hơn 1 phút).

D. Khoảng 1 năm.

Câu 20: Đoạn mã while i < n: i = i + 2 có độ phức tạp bao nhiêu?

A. O(n2)

B. O(log n)

C. O(n)

D. O(1)

Câu 21: (Vận dụng cao) Xét đoạn mã có vòng lặp phụ thuộc nhau: vòng ngoài chạy n lần, vòng trong chạy từ 0 đến i. Độ phức tạp chính xác nhất là:

A. O(n) vì vòng lặp bên trong chạy ít hơn n lần.

B. O(n²) vì tổng số lần lặp là dãy số học ≈ n²/2.

C. O(n log n) vì cấu trúc tam giác.

D. O(1) vì đây là công thức toán học.

Câu 22: (Vận dụng cao) Đoạn mã while i * i < n: i += 1 có độ phức tạp là gì?

A. O(n)

B. O(log n)

C. O(√n)

D. O(n/2)

Câu 23: (Vận dụng cao) Cho bài toán tìm cặp số tổng bằng S. Cách 1 dùng 2 vòng lặp lồng nhau. Cách 2 dùng 2 con trỏ (đầu, cuối) co dần. Độ phức tạp lần lượt là:

A. O(n) và O(1).

B. O(n²) và O(n).

C. O(n²) và O(n²).

D. O(n log n) và O(log n).

Câu 24: (Vận dụng cao) Một chương trình đệ quy, mỗi lần gọi hàm lại sinh ra 2 nhánh gọi đệ quy con (giống cây nhị phân đầy đủ). Độ phức tạp là:

A. O(n)

B. O(n²)

C. O(2ⁿ)

D. O(log n)

Câu 25: (Vận dụng cao) Trong các cuộc thi lập trình, nếu giới hạn thời gian là 1 giây và n = 10⁶, bạn KHÔNG thể sử dụng thuật toán có độ phức tạp nào?

A. O(n)

B. O(n log n)

C. O(n²)

D. O(log n)