12+ Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 24: Đánh Giá Độ Phức Tạp Thời Gian Thuật Toán

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, tại sao chúng ta thường chỉ quan tâm đến số lượng các phép toán cơ bản (như gán, so sánh, cộng, trừ) thay vì thời gian thực thi chính xác trên một máy tính cụ thể?

• A. Thời gian thực thi chính xác quá khó để đo lường.
• B. Các phép toán cơ bản luôn mất cùng một lượng thời gian trên mọi máy tính.
• C. Chỉ có các phép toán cơ bản mới ảnh hưởng đến hiệu suất thuật toán.
• D. Số lượng phép toán cơ bản cung cấp ước lượng hiệu suất độc lập với phần cứng và môi trường thực thi.

Câu 2: Độ phức tạp thời gian O(n) mô tả mối quan hệ giữa thời gian thực thi và kích thước đầu vào n như thế nào?

• A. Thời gian thực thi không đổi khi n tăng.
• B. Thời gian thực thi tăng tỷ lệ thuận (tuyến tính) với n.
• C. Thời gian thực thi tăng theo hàm bình phương của n.
• D. Thời gian thực thi tăng theo hàm logarit của n.

Câu 3: Cho đoạn mã giả sau:

```
function process(arr, n):
sum = 0
for i from 0 to n-1:
sum = sum + arr[i]
return sum
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu, với n là kích thước của mảng `arr`?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n^2)

Câu 4: Cho đoạn mã giả sau:

```
function find_max(arr, n):
max_val = arr[0]
for i from 1 to n-1:
if arr[i] > max_val:
max_val = arr[i]
return max_val
```

Độ phức tạp thời gian của đoạn mã này trong trường hợp xấu nhất (worst-case) là bao nhiêu, với n là kích thước của mảng `arr`?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n log n)

Câu 5: Thuật toán tìm kiếm nhị phân trên một mảng đã được sắp xếp có độ phức tạp thời gian là O(log n). Điều này có nghĩa là gì?

• A. Thời gian tìm kiếm tăng gấp đôi khi kích thước mảng tăng gấp đôi.
• B. Thời gian tìm kiếm giảm đi một nửa khi kích thước mảng tăng gấp đôi.
• C. Thời gian tìm kiếm tăng theo bình phương của kích thước mảng.
• D. Thời gian tìm kiếm tăng rất chậm khi kích thước mảng tăng lên đáng kể.

Câu 6: Cho đoạn mã giả sau:

```
function print_pairs(arr, n):
for i from 0 to n-1:
for j from 0 to n-1:
print(arr[i], arr[j])
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu, với n là kích thước của mảng `arr`?

• A. O(n)
• B. O(n log n)
• C. O(log n)
• D. O(n^2)

Câu 7: Khi so sánh hai thuật toán A có độ phức tạp O(n) và thuật toán B có độ phức tạp O(n^2) để giải cùng một bài toán với kích thước đầu vào n rất lớn, thuật toán nào thường được ưu tiên hơn và vì sao?

• A. Thuật toán A (O(n)) vì thời gian thực thi tăng chậm hơn nhiều so với O(n^2) khi n lớn.
• B. Thuật toán B (O(n^2)) vì nó có thể xử lý dữ liệu lớn hơn.
• C. Cả hai thuật toán đều có hiệu quả như nhau với n lớn.
• D. Không thể xác định chỉ dựa vào độ phức tạp Big O.

Câu 8: Quy tắc cộng trong phân tích độ phức tạp thời gian được áp dụng khi nào?

• A. Khi các khối lệnh hoặc hàm được thực thi nối tiếp nhau.
• B. Khi có các vòng lặp lồng nhau.
• C. Khi các khối lệnh hoặc hàm được thực thi song song.
• D. Khi kích thước đầu vào được chia nhỏ.

Câu 9: Quy tắc nhân trong phân tích độ phức tạp thời gian được áp dụng khi nào?

• A. Khi các khối lệnh được thực thi nối tiếp nhau.
• B. Khi một khối lệnh (hoặc vòng lặp) được thực hiện bên trong một cấu trúc lặp khác.
• C. Khi thuật toán sử dụng phép nhân số học.
• D. Khi kết hợp độ phức tạp của hai thuật toán khác nhau.

Câu 10: Cho đoạn mã giả sau:

```
function example(n):
for i from 1 to 100:
print(i)
for j from 1 to n:
print(j)
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(1)
• B. O(100)
• C. O(n)
• D. O(100n)

Câu 11: Thuật toán nào sau đây thường có độ phức tạp thời gian tốt nhất (hiệu quả nhất) khi kích thước đầu vào n rất lớn?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n log n)

Câu 12: Độ phức tạp thời gian O(n^2) thường xuất hiện trong các thuật toán có cấu trúc như thế nào?

• A. Chỉ có các phép toán cơ bản.
• B. Một vòng lặp đơn chạy n lần.
• C. Hai vòng lặp lồng nhau, mỗi vòng lặp chạy khoảng n lần.
• D. Sử dụng đệ quy chia đôi.

Câu 13: Tại sao các hằng số và các thành phần bậc thấp thường bị bỏ qua trong ký hiệu Big O?

• A. Chúng không ảnh hưởng đến thời gian thực thi.
• B. Khi n rất lớn, thành phần bậc cao nhất chi phối sự tăng trưởng của hàm thời gian.
• C. Việc tính toán chúng rất phức tạp.
• D. Chúng chỉ quan trọng trong trường hợp tốt nhất.

Câu 14: Cho đoạn mã giả sau:

```
function example(arr, n):
if n <= 1: return // Chia mảng làm đôi mid = n / 2 left_half = arr[0...mid-1] right_half = arr[mid...n-1] // Gọi đệ quy trên hai nửa example(left_half, mid) example(right_half, n - mid) // Các thao tác kết hợp (ví dụ: trộn mảng đã sắp xếp) // ... (thực hiện trong thời gian O(n)) ``` Đây là cấu trúc của một thuật toán "chia để trị" điển hình (ví dụ: Merge Sort). Độ phức tạp thời gian của các thuật toán dạng này thường là bao nhiêu?

• A. O(n^2)
• B. O(n)
• C. O(log n)
• D. O(n log n)

Câu 15: Tại sao việc đánh giá độ phức tạp thời gian (và không gian) của thuật toán lại quan trọng trong việc phát triển phần mềm?

• A. Giúp dự đoán hiệu suất của chương trình với các bộ dữ liệu đầu vào lớn và so sánh hiệu quả giữa các thuật toán khác nhau.
• B. Chỉ cần thiết khi lập trình trên các hệ thống nhúng với bộ nhớ hạn chế.
• C. Là yêu cầu bắt buộc của mọi ngôn ngữ lập trình hiện đại.
• D. Chỉ giúp tìm ra lỗi logic trong mã nguồn.

Câu 16: Cho đoạn mã giả:

```
function example(n):
i = 1
while i < n: print(i) i = i * 2 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(log n)
• C. O(n^2)
• D. O(1)

Câu 17: Thuật toán nào dưới đây, khi triển khai một cách cơ bản, thường có độ phức tạp thời gian là O(n^2)?

• A. Sắp xếp chọn (Selection Sort)
• B. Tìm kiếm nhị phân (Binary Search)
• C. Sắp xếp trộn (Merge Sort)
• D. Sắp xếp nhanh (Quick Sort) - trung bình

Câu 18: Giả sử một thuật toán có độ phức tạp thời gian là T(n) = 5n^2 + 3n + 10. Khi sử dụng ký hiệu Big O để biểu diễn độ phức tạp, kết quả đúng là gì?

• A. O(n)
• B. O(5n^2)
• C. O(n^2 + n)
• D. O(n^2)

Câu 19: Trường hợp tốt nhất (best-case) của một thuật toán là gì?

• A. Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian ngắn nhất.
• B. Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian dài nhất.
• C. Bộ dữ liệu đầu vào trung bình.
• D. Trường hợp thuật toán không có lỗi.

Câu 20: Trường hợp xấu nhất (worst-case) của một thuật toán là gì?

• A. Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian ngắn nhất.
• B. Bộ dữ liệu đầu vào làm cho thuật toán thực thi với thời gian dài nhất.
• C. Bộ dữ liệu đầu vào trung bình.
• D. Trường hợp thuật toán hoạt động chính xác.

Câu 21: Cho đoạn mã giả:

```
function example(n):
sum = 0
for i from 1 to n:
sum = sum + i
j = 1
while j < n: print(j) j = j * 3 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(log n)
• B. O(n log n)
• C. O(n)
• D. O(n + log n)

Câu 22: Thuật toán tìm kiếm tuyến tính (Linear Search) trên một mảng có n phần tử có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n^2)

Câu 23: Độ phức tạp thời gian O(1) có nghĩa là gì?

• A. Thời gian thực thi không thay đổi khi kích thước đầu vào n thay đổi.
• B. Thời gian thực thi tăng tuyến tính với n.
• C. Thời gian thực thi là 1 đơn vị.
• D. Thuật toán rất nhanh.

Câu 24: Cho đoạn mã giả:

```
function example(n):
for i from 1 to n:
for j from 1 to i:
print(i, j)
```

Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

• A. O(n)
• B. O(n log n)
• C. O(log n)
• D. O(n^2)

Câu 25: Khi phân tích độ phức tạp thời gian của thuật toán, "kích thước đầu vào" (input size) n thường được định nghĩa là gì?

• A. Số dòng mã lệnh của chương trình.
• B. Một tham số đo lường quy mô của dữ liệu mà thuật toán xử lý (ví dụ: số phần tử, số bit).
• C. Thời gian chạy thực tế của chương trình.
• D. Số lượng biến được sử dụng trong thuật toán.

Câu 26: Giả sử bạn có hai thuật toán để giải quyết một bài toán: Thuật toán X có độ phức tạp O(n log n) và Thuật toán Y có độ phức tạp O(n^2). Với n = 1000, thuật toán nào có khả năng chạy nhanh hơn và tại sao?

• A. Thuật toán X (O(n log n)) vì n log n tăng chậm hơn nhiều so với n^2 khi n lớn.
• B. Thuật toán Y (O(n^2)) vì n^2 lớn hơn n log n.
• C. Cả hai thuật toán sẽ chạy với tốc độ tương đương nhau.
• D. Không thể xác định nếu không biết hằng số ẩn trong ký hiệu Big O.

Câu 27: Thuật toán sắp xếp nào dưới đây, khi triển khai hiệu quả, có độ phức tạp thời gian trung bình là O(n log n)?

• A. Sắp xếp chèn (Insertion Sort)
• B. Sắp xếp trộn (Merge Sort)
• C. Sắp xếp nổi bọt (Bubble Sort)
• D. Sắp xếp chọn (Selection Sort)

Câu 28: Nếu một thuật toán có độ phức tạp thời gian là O(2^n), điều gì sẽ xảy ra với thời gian thực thi khi kích thước đầu vào n tăng lên một lượng nhỏ (ví dụ: tăng thêm 1 hoặc 2)?

• A. Thời gian thực thi tăng tuyến tính.
• B. Thời gian thực thi tăng logarit.
• C. Thời gian thực thi tăng theo bình phương.
• D. Thời gian thực thi tăng theo cấp số nhân (rất nhanh).

Câu 29: Cho đoạn mã giả:

```
function example(arr, n):
if n <= 0: return 0 if n == 1: return arr[0] // Giả sử hàm sum_array_recursive(arr, n) tính tổng n phần tử // bằng cách gọi đệ quy trên n-1 phần tử và cộng thêm phần tử cuối. // Độ phức tạp của hàm này là O(n). return sum_array_recursive(arr, n) ``` Độ phức tạp thời gian của hàm `example` gọi `sum_array_recursive` như mô tả là bao nhiêu?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n^2)

Câu 30: Khi so sánh hiệu quả của hai thuật toán A (O(n log n)) và B (O(n^2)) cho một bài toán, có trường hợp nào mà thuật toán B có thể chạy nhanh hơn thuật toán A không?

• A. Không bao giờ, vì O(n log n) luôn tốt hơn O(n^2).
• B. Có thể, khi kích thước đầu vào n rất nhỏ, hằng số ẩn trong ký hiệu Big O có thể làm thay đổi kết quả so sánh.
• C. Có thể, nhưng chỉ trong trường hợp tốt nhất của thuật toán B.
• D. Chỉ khi thuật toán B được viết bằng ngôn ngữ lập trình nhanh hơn.

Câu 1: Khái niệm "độ phức tạp thời gian" của một thuật toán chủ yếu đo lường điều gì?

• A. Tổng dung lượng bộ nhớ mà thuật toán sử dụng.
• B. Số lượng dòng mã lệnh trong thuật toán.
• C. Số lượng phép toán cơ bản mà thuật toán thực hiện, phụ thuộc vào kích thước đầu vào.
• D. Thời gian chạy thực tế của thuật toán trên một máy tính cụ thể.

Câu 2: Tại sao khi đánh giá độ phức tạp thời gian bằng ký hiệu Big O (O), chúng ta thường chỉ quan tâm đến hạng tử có bậc cao nhất và bỏ qua các hệ số hằng?

• A. Vì khi kích thước đầu vào rất lớn, hạng tử có bậc cao nhất sẽ chi phối tốc độ tăng trưởng của hàm thời gian.
• B. Vì các hệ số hằng và hạng tử bậc thấp không ảnh hưởng đến thời gian chạy thực tế.
• C. Để làm cho việc tính toán độ phức tạp trở nên đơn giản hơn.
• D. Vì chúng ta chỉ quan tâm đến trường hợp xấu nhất của thuật toán.

Câu 3: Xét đoạn mã giả sau:
```
a = 10
b = 20
if n > 0:
for i from 1 to n:
c = a + b
```
Với `n` là kích thước đầu vào, độ phức tạp thời gian của đoạn mã này là gì?

• A. O(1)
• B. O(log n)
• C. O(n)
• D. O(n^2)

Câu 4: Xét đoạn mã giả sau:
```
sum = 0
for i from 1 to n:
for j from 1 to n:
sum = sum + 1
```
Với `n` là kích thước đầu vào, độ phức tạp thời gian của đoạn mã này là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^3)
• D. O(n^2)

Câu 5: Cho hai thuật toán A và B lần lượt có độ phức tạp thời gian là O(n log n) và O(n^2). Khi kích thước đầu vào `n` tăng lên rất lớn, thuật toán nào sẽ có hiệu suất (thời gian chạy) tốt hơn?

• A. Thuật toán A (O(n log n)) vì n log n tăng trưởng chậm hơn n^2.
• B. Thuật toán B (O(n^2)) vì n^2 là bậc cao hơn.
• C. Cả hai thuật toán có hiệu suất tương đương cho n lớn.
• D. Không thể xác định nếu không biết hệ số hằng của mỗi thuật toán.

Câu 6: Quy tắc cộng trong phân tích độ phức tạp thời gian được áp dụng khi nào?

• A. Khi có các vòng lặp lồng nhau.
• B. Khi các khối lệnh hoặc các phần của thuật toán được thực hiện một cách tuần tự.
• C. Khi một hàm gọi một hàm khác.
• D. Khi phân tích độ phức tạp không phụ thuộc vào kích thước đầu vào.

Câu 7: Quy tắc nhân trong phân tích độ phức tạp thời gian được áp dụng khi nào?

• A. Khi một khối lệnh được thực hiện lặp đi lặp lại bên trong một cấu trúc lặp (ví dụ: vòng lặp lồng nhau).
• B. Khi các khối lệnh được thực hiện tuần tự.
• C. Khi so sánh độ phức tạp của hai thuật toán khác nhau.
• D. Khi thuật toán sử dụng bộ nhớ phụ trợ.

Câu 8: Độ phức tạp thời gian O(1) có ý nghĩa gì?

• A. Thời gian chạy tăng tuyến tính với kích thước đầu vào n.
• B. Thời gian chạy tăng theo logarit của kích thước đầu vào n.
• C. Thời gian chạy tăng theo bình phương của kích thước đầu vào n.
• D. Thời gian chạy là hằng số, không phụ thuộc vào kích thước đầu vào n.

Câu 9: Thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

• A. O(n)
• B. O(log n)
• C. O(n^2)
• D. O(1)

Câu 10: Xét đoạn mã giả sau:
```
result = 0
for i from 1 to 100:
result = result + i
```
Độ phức tạp thời gian của đoạn mã này là gì?

• A. O(1)
• B. O(n)
• C. O(100)
• D. O(log n)

Câu 11: Khi phân tích độ phức tạp thời gian của một thuật toán, "trường hợp xấu nhất" (worst-case) thường được quan tâm nhất vì lý do gì?

• A. Vì nó dễ phân tích hơn trường hợp trung bình và tốt nhất.
• B. Vì nó xảy ra thường xuyên nhất trong thực tế.
• C. Vì nó cung cấp giới hạn trên về thời gian chạy, đảm bảo thuật toán không bao giờ vượt quá hiệu suất đó.
• D. Vì nó giúp so sánh thuật toán trên các bộ dữ liệu khác nhau.

Câu 12: Một thuật toán có độ phức tạp thời gian O(n log n). Điều này có nghĩa là gì về mối quan hệ giữa thời gian chạy và kích thước đầu vào n?

• A. Thời gian chạy tăng tuyến tính với n.
• B. Thời gian chạy tăng theo n nhân với logarit của n.
• C. Thời gian chạy tăng theo bình phương của n.
• D. Thời gian chạy là hằng số.

Câu 13: Xét đoạn mã giả sau:
```
for i from 1 to n:
j = 1
while j < n: print(i, j) j = j * 2 ``` Với `n` là kích thước đầu vào, độ phức tạp thời gian của đoạn mã này là gì?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(log n)

Câu 14: Thuật toán sắp xếp chọn (Selection Sort) có độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

• A. O(n)
• B. O(log n)
• C. O(n log n)
• D. O(n^2)

Câu 15: Cho một thuật toán có hàm thời gian T(n) = 5n³ + 20n² + 100. Độ phức tạp thời gian của thuật toán này theo ký hiệu Big O là gì?

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

Câu 16: Một thuật toán có độ phức tạp O(2^n). Điều này có ý nghĩa gì đối với việc sử dụng thuật toán này với kích thước đầu vào `n` lớn?

• A. Thuật toán rất hiệu quả và có thể xử lý dữ liệu lớn dễ dàng.
• B. Thời gian chạy tăng trưởng tuyến tính, nên phù hợp với mọi kích thước đầu vào.
• C. Thời gian chạy tăng trưởng rất nhanh (theo cấp số mũ), khiến thuật toán không khả thi cho các giá trị n lớn.
• D. Thuật toán có thời gian chạy hằng số, không phụ thuộc vào n.

Câu 17: Khi phân tích độ phức tạp của một cấu trúc điều kiện (if-else), độ phức tạp tổng thể thường được tính bằng cách nào?

• A. Bằng tổng độ phức tạp của nhánh if và nhánh else.
• B. Bằng độ phức tạp của nhánh có thời gian chạy lớn nhất (trong trường hợp xấu nhất).
• C. Bằng tích độ phức tạp của nhánh if và nhánh else.
• D. Bằng độ phức tạp của điều kiện (biểu thức logic) của if.

Câu 18: Xét đoạn mã giả sau:
```
func process_array(arr, n):
# Đoạn 1: Tìm phần tử nhỏ nhất (O(n))
min_val = arr[0]
for i from 1 to n-1:
if arr[i] < min_val: min_val = arr[i] # Đoạn 2: In ra 10 lần giá trị min_val (O(1)) for k from 1 to 10: print(min_val) ``` Độ phức tạp thời gian tổng thể của hàm `process_array` là gì?

• A. O(1)
• B. O(n^2)
• C. O(n)
• D. O(n log n)

Câu 19: Thứ tự tăng trưởng từ chậm nhất đến nhanh nhất của các độ phức tạp phổ biến là gì?

• A. O(n), O(log n), O(n^2), O(n log n)
• B. O(1), O(log n), O(n), O(n log n), O(n^2)
• C. O(n^2), O(n log n), O(n), O(log n), O(1)
• D. O(log n), O(1), O(n), O(n^2), O(n log n)

Câu 20: Giả sử một thuật toán có độ phức tạp thời gian là O(n^2). Nếu kích thước đầu vào `n` tăng gấp đôi, thì thời gian chạy của thuật toán sẽ tăng lên khoảng bao nhiêu lần (đối với n đủ lớn)?

• A. Gấp đôi (2 lần)
• B. Gấp ba (3 lần)
• C. Gấp log n lần
• D. Gấp bốn lần (4 lần)

Câu 21: Giả sử một thuật toán có độ phức tạp thời gian là O(log n). Nếu kích thước đầu vào `n` tăng gấp đôi, thì thời gian chạy của thuật toán sẽ tăng lên khoảng bao nhiêu (đối với n đủ lớn)?

• A. Tăng thêm một lượng hằng số.
• B. Tăng gấp đôi.
• C. Tăng theo log của log n.
• D. Không thay đổi.

Câu 22: Ký hiệu O lớn (Big O) dùng để chỉ điều gì khi phân tích độ phức tạp thời gian?

• A. Giới hạn trên (trường hợp xấu nhất) về tốc độ tăng trưởng thời gian chạy.
• B. Giới hạn dưới (trường hợp tốt nhất) về tốc độ tăng trưởng thời gian chạy.
• C. Thời gian chạy trung bình của thuật toán.
• D. Thời gian chạy chính xác của thuật toán.

Câu 23: Một chương trình thực hiện ba phần tuần tự: Phần 1 có độ phức tạp O(n), Phần 2 có độ phức tạp O(n²), và Phần 3 có độ phức tạp O(log n). Độ phức tạp thời gian tổng thể của chương trình là gì?

• A. O(n + n² + log n)
• B. O(n log n)
• C. O(n)
• D. O(n²)

Câu 24: Xét đoạn mã giả sau:
```
func process(n):
if n <= 1: return for i from 1 to 10: print(i) process(n/2) process(n/2) ``` Đoạn mã này mô tả cấu trúc gì và độ phức tạp thời gian của phần đệ quy (không xét vòng lặp cố định) thường rơi vào loại nào?

• A. Đệ quy, thường O(n log n) hoặc O(n) trong các trường hợp điển hình như chia để trị.
• B. Vòng lặp lồng nhau, thường O(n^2).
• C. Vòng lặp đơn, thường O(n).
• D. Cấu trúc hằng số, O(1).

Câu 25: Việc phân tích độ phức tạp thời gian của thuật toán giúp ích gì cho lập trình viên?

• A. Giúp tìm lỗi cú pháp trong mã nguồn.
• B. Giúp giảm thiểu việc sử dụng bộ nhớ.
• C. Giúp dự đoán thời gian chạy chính xác trên mọi máy tính.
• D. Giúp đánh giá hiệu suất của thuật toán khi xử lý dữ liệu lớn và so sánh các thuật toán khác nhau.

Câu 26: Xét đoạn mã giả sau:
```
func example(arr, n):
for i from 0 to n-1:
if arr[i] == target_value:
return True
return False
```
Đây là thuật toán tìm kiếm tuyến tính (Linear Search). Độ phức tạp thời gian trong trường hợp xấu nhất của nó là gì?

• A. O(log n)
• B. O(n)
• C. O(n log n)
• D. O(n^2)

Câu 27: Cho một thuật toán có độ phức tạp O(n^3). Nếu một máy tính có thể chạy thuật toán này với n=100 trong 1 giây, ước tính thời gian cần thiết để chạy thuật toán với n=200 trên cùng máy tính đó là bao nhiêu?

• A. 2 giây
• B. 4 giây
• C. 6 giây
• D. 8 giây

Câu 28: Khi so sánh hai thuật toán có độ phức tạp O(n) và O(n log n), điều gì đúng khi n rất lớn?

• A. Thuật toán O(n) sẽ chạy nhanh hơn thuật toán O(n log n).
• B. Thuật toán O(n log n) sẽ chạy nhanh hơn thuật toán O(n).
• C. Hai thuật toán có hiệu suất tương đương.
• D. Không thể so sánh vì cần biết hệ số hằng.

Câu 29: Xét đoạn mã giả sau:
```
func weird_loop(n):
count = 0
for i from 1 to n:
for j from i to n:
count = count + 1
```
Độ phức tạp thời gian của đoạn mã này là gì?

• A. O(n)
• B. O(n log n)
• C. O(n³)
• D. O(n²)

Câu 30: Mục tiêu chính của việc đánh giá độ phức tạp thời gian thuật toán là gì?

• A. Để so sánh hiệu quả và khả năng mở rộng của các thuật toán khác nhau khi xử lý dữ liệu lớn.
• B. Để xác định số lượng bộ nhớ cần thiết cho thuật toán.
• C. Để tìm ra thuật toán có ít dòng mã nhất.
• D. Để đảm bảo thuật toán không bao giờ gặp lỗi.

Câu 1: Tại sao việc đánh giá độ phức tạp thời gian của thuật toán lại quan trọng trong khoa học máy tính?

• A. Giúp xác định số dòng code trong chương trình.
• B. Chỉ cần thiết cho các thuật toán sắp xếp.
• C. Giúp tìm ra lỗi cú pháp trong code.
• D. Giúp dự đoán hiệu suất của thuật toán khi kích thước dữ liệu đầu vào tăng lên và so sánh hiệu quả giữa các thuật toán.

Câu 2: Khi phân tích độ phức tạp thời gian, chúng ta thường quan tâm đến trường hợp nào của dữ liệu đầu vào và tại sao?

• A. Trường hợp tốt nhất, vì nó thể hiện tốc độ nhanh nhất có thể.
• B. Trường hợp trung bình, vì nó phản ánh hiệu suất thực tế thường gặp.
• C. Trường hợp xấu nhất, vì nó đảm bảo thuật toán sẽ không bao giờ chạy chậm hơn mức ước lượng đó.
• D. Trường hợp tốt nhất và trung bình có ý nghĩa như nhau.

Câu 3: Ký hiệu Big O (O) được sử dụng để làm gì trong đánh giá độ phức tạp thời gian?

• A. Biểu thị thời gian chạy chính xác của thuật toán trên một máy cụ thể.
• B. Mô tả giới hạn trên về tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào rất lớn.
• C. Đếm chính xác tổng số phép toán cơ bản.
• D. Đo lường dung lượng bộ nhớ mà thuật toán sử dụng.

Câu 4: Một thuật toán có độ phức tạp thời gian O(1) nghĩa là gì?

• A. Thời gian thực hiện không đổi, không phụ thuộc vào kích thước đầu vào n.
• B. Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào n.
• C. Thời gian thực hiện tăng theo hàm logarit của n.
• D. Thời gian thực hiện tăng theo bình phương của n.

Câu 5: Cho đoạn mã Python sau:
```python
result = 0
for i in range(n):
result += i
```
Độ phức tạp thời gian của đoạn mã này là gì theo ký hiệu Big O, với n là kích thước đầu vào?

• A. O(1)
• B. O(n^2)
• C. O(n)
• D. O(log n)

Câu 6: Cho đoạn mã Python sau:
```python
result = 0
for i in range(n):
for j in range(n):
result += i * j
```
Độ phức tạp thời gian của đoạn mã này là gì theo ký hiệu Big O, với n là kích thước đầu vào?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(2^n)

Câu 7: Cho hai đoạn mã A và B. Đoạn A có độ phức tạp O(n), đoạn B có độ phức tạp O(n^2). Nếu thực hiện đoạn mã A rồi đến đoạn mã B, độ phức tạp thời gian tổng thể là gì theo ký hiệu Big O?

• A. O(n + n^2)
• B. O(n^2)
• C. O(n)
• D. O(n^3)

Câu 8: Một thuật toán tìm kiếm trên một mảng đã được sắp xếp bằng phương pháp chia đôi (tìm kiếm nhị phân) có độ phức tạp thời gian là gì?

• A. O(n)
• B. O(n^2)
• C. O(1)
• D. O(log n)

Câu 9: Sắp xếp các độ phức tạp thời gian sau theo thứ tự từ tốt nhất (nhanh nhất) đến tệ nhất (chậm nhất) khi n rất lớn: O(n^2), O(n), O(1), O(n log n).

• A. O(n^2), O(n log n), O(n), O(1)
• B. O(n), O(n^2), O(1), O(n log n)
• C. O(1), O(n), O(n log n), O(n^2)
• D. O(log n), O(n), O(n log n), O(n^2)

Câu 10: Một thuật toán xử lý tất cả các cặp phần tử trong một tập hợp n phần tử. Ví dụ: so sánh mọi cặp phần tử với nhau. Độ phức tạp thời gian phổ biến nhất cho hoạt động này là gì?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(log n)

Câu 11: Cho đoạn mã Python sau:
```python
def process_data(data):
n = len(data)
for i in range(n // 2):
print(data[i])
```
Độ phức tạp thời gian của hàm `process_data` là gì theo ký hiệu Big O, với n là kích thước danh sách `data`?

• A. O(n^2)
• B. O(log n)
• C. O(n)
• D. O(1)

Câu 12: Cho đoạn mã Python sau:
```python
def find_element(data, target):
for item in data:
if item == target:
return True
return False
```
Trong trường hợp xấu nhất, độ phức tạp thời gian của hàm `find_element` (tìm kiếm tuyến tính) là gì theo ký hiệu Big O, với n là kích thước danh sách `data`?

• A. O(n)
• B. O(log n)
• C. O(n^2)
• D. O(1)

Câu 13: Giả sử một thuật toán có thời gian chạy được mô tả bởi hàm T(n) = 5n^3 + 2n^2 + 100. Độ phức tạp thời gian của thuật toán này theo ký hiệu Big O là gì?

• A. O(n)
• B. O(n^2)
• C. O(1)
• D. O(n^3)

Câu 14: Khi so sánh thuật toán A có độ phức tạp O(n log n) và thuật toán B có độ phức tạp O(n^2), thuật toán nào hiệu quả hơn (chạy nhanh hơn) khi kích thước đầu vào n rất lớn?

• A. Thuật toán A (O(n log n))
• B. Thuật toán B (O(n^2))
• C. Cả hai thuật toán có hiệu quả tương đương.
• D. Không thể xác định nếu không biết giá trị cụ thể của n.

Câu 15: Cho đoạn mã Python sau:
```python
def example(n):
for i in range(100):
print(i)
for j in range(n):
print(j)
```
Độ phức tạp thời gian của hàm `example` là gì theo ký hiệu Big O, với n là kích thước đầu vào?

• A. O(100 + n)
• B. O(100n)
• C. O(n)
• D. O(1)

Câu 16: Cho đoạn mã Python sau:
```python
def another_example(n):
i = 1
while i < n: print(i) i *= 2 ``` Độ phức tạp thời gian của hàm `another_example` là gì theo ký hiệu Big O, với n là kích thước đầu vào?

• A. O(n)
• B. O(n^2)
• C. O(1)
• D. O(log n)

Câu 17: Khi phân tích độ phức tạp thời gian, tại sao chúng ta thường bỏ qua các hằng số và các số hạng bậc thấp trong hàm thời gian T(n)?

• A. Vì chúng không ảnh hưởng đến thời gian chạy thực tế.
• B. Vì chúng chỉ ảnh hưởng nhỏ khi kích thước đầu vào n rất lớn và ký hiệu Big O quan tâm đến tốc độ tăng trưởng tiệm cận.
• C. Vì chúng chỉ liên quan đến dung lượng bộ nhớ, không phải thời gian.
• D. Vì chúng làm cho việc tính toán trở nên phức tạp.

Câu 18: Thuật toán sắp xếp nổi bọt (Bubble Sort) đơn giản có độ phức tạp thời gian trong trường hợp xấu nhất là gì?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(log n)

Câu 19: Một bài toán yêu cầu duyệt qua tất cả các tập con có thể có của một tập hợp n phần tử. Độ phức tạp thời gian của thuật toán giải quyết bài toán này có khả năng là gì?

• A. O(2^n)
• B. O(n^2)
• C. O(n log n)
• D. O(n!)

Câu 20: Cho đoạn mã Python sau:
```python
def process_matrix(matrix, n):
for i in range(n):
for j in range(n):
# Thao tác O(1) trên matrix[i][j]
pass
for k in range(n):
# Thao tác O(1)
pass
```
Độ phức tạp thời gian của hàm `process_matrix` là gì theo ký hiệu Big O, với n là kích thước (số hàng/cột) của ma trận vuông?

• A. O(n)
• B. O(n + n^2)
• C. O(n^2)
• D. O(n^3)

Câu 21: Độ phức tạp thời gian O(n log n) thường xuất hiện trong các thuật toán nào?

• A. Tìm kiếm tuyến tính, tìm kiếm nhị phân.
• B. Các thuật toán sắp xếp hiệu quả như Sắp xếp trộn (Merge Sort), Sắp xếp nhanh (Quick Sort).
• C. Các phép toán cơ bản (cộng, trừ, nhân, chia).
• D. Duyệt qua tất cả các tập con của một tập hợp.

Câu 22: Nếu một thuật toán có độ phức tạp O(n) và chạy mất 1 giây cho n=1000, ước tính thời gian chạy cho n=2000 là bao nhiêu?

• A. Khoảng 2 giây.
• B. Khoảng 4 giây.
• C. Khoảng 0.5 giây.
• D. Không thể ước tính vì không biết hệ số hằng số.

Câu 23: Nếu một thuật toán có độ phức tạp O(n^2) và chạy mất 1 giây cho n=1000, ước tính thời gian chạy cho n=2000 là bao nhiêu?

• A. Khoảng 2 giây.
• B. Khoảng 4 giây.
• C. Khoảng 0.5 giây.
• D. Khoảng 8 giây.

Câu 24: Cho đoạn mã Python sau:
```python
def process_pairs(data):
n = len(data)
for i in range(n):
for j in range(i, n):
# Thao tác O(1) với data[i] và data[j]
pass
```
Độ phức tạp thời gian của hàm `process_pairs` là gì theo ký hiệu Big O, với n là kích thước danh sách `data`?

• A. O(n)
• B. O(n log n)
• C. O(n^2)
• D. O(log n)

Câu 25: Trong phân tích độ phức tạp, "kích thước đầu vào" (input size) của một thuật toán là gì?

• A. Một đại lượng đo lường quy mô của dữ liệu mà thuật toán xử lý (ví dụ: số phần tử trong danh sách).
• B. Số dòng code trong chương trình.
• C. Thời gian chạy thực tế của thuật toán.
• D. Lượng bộ nhớ mà thuật toán sử dụng.

Câu 26: Độ phức tạp thời gian O(n!) (n giai thừa) thuộc loại độ phức tạp nào và nó thường xuất hiện trong các bài toán gì?

• A. Đa thức, thường trong các bài toán tìm kiếm.
• B. Logarit, thường trong các bài toán chia để trị.
• C. Mũ, thường trong các bài toán duyệt tất cả tập con.
• D. Siêu đa thức, thường trong các bài toán liên quan đến hoán vị.

Câu 27: Khi nào thì độ phức tạp thời gian của một thuật toán được coi là chấp nhận được trong thực tế?

• A. Khi độ phức tạp là đa thức (ví dụ: O(n), O(n log n), O(n^2)) với bậc nhỏ.
• B. Chỉ khi độ phức tạp là O(1) hoặc O(log n).
• C. Khi độ phức tạp là mũ (ví dụ: O(2^n)).
• D. Chỉ khi thời gian chạy thực tế dưới 1 giây.

Câu 28: Cho đoạn mã Python sau:
```python
def strange_loop(n):
count = 0
for i in range(n):
for j in range(i):
count += 1
```
Độ phức tạp thời gian của hàm `strange_loop` là gì theo ký hiệu Big O, với n là kích thước đầu vào?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(log n)

Câu 29: Tại sao việc phân tích độ phức tạp thời gian thường tập trung vào trường hợp xấu nhất?

• A. Vì trường hợp xấu nhất dễ phân tích nhất.
• B. Vì trường hợp xấu nhất luôn xảy ra trong thực tế.
• C. Vì nó cung cấp giới hạn trên về thời gian chạy, đảm bảo thuật toán không bao giờ chạy chậm hơn mức đó.
• D. Vì nó thể hiện hiệu suất trung bình của thuật toán.

Câu 30: Cho một thuật toán thực hiện hai bước độc lập. Bước 1 có độ phức tạp O(log n), Bước 2 có độ phức tạp O(n). Độ phức tạp tổng thể của thuật toán là gì?

• A. O(log n)
• B. O(n)
• C. O(n log n)
• D. O(log n + n)

Câu 1: Khi đánh giá độ phức tạp thời gian của một thuật toán, chúng ta thường quan tâm đến yếu tố nào của đầu vào?

• A. Giá trị cụ thể của từng phần tử trong đầu vào.
• B. Kích thước của dữ liệu đầu vào (thường ký hiệu là n).
• C. Thời gian thực tế mà chương trình chạy trên một máy tính cụ thể.
• D. Ngôn ngữ lập trình được sử dụng để cài đặt thuật toán.

Câu 2: Độ phức tạp thời gian O(1) biểu thị điều gì về thời gian thực hiện của một thuật toán?

• A. Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào n.
• B. Thời gian thực hiện tăng theo logarit của kích thước đầu vào n.
• C. Thời gian thực hiện là hằng số, không phụ thuộc vào kích thước đầu vào n.
• D. Thời gian thực hiện tăng theo bình phương của kích thước đầu vào n.

Câu 3: Cho đoạn mã Python sau:
```python
def process_array(arr):
total = 0
for x in arr:
total += x
return total
```
Với `n` là kích thước của mảng `arr`, độ phức tạp thời gian của hàm `process_array` là gì?

• A. O(n)
• B. O(n^2)
• C. O(log n)
• D. O(1)

Câu 4: Cho đoạn mã Python sau:
```python
def find_pair(arr):
n = len(arr)
for i in range(n):
for j in range(n):
if arr[i] + arr[j] == 0:
return True
return False
```
Với `n` là kích thước của mảng `arr`, độ phức tạp thời gian của hàm `find_pair` là gì?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(log n)

Câu 5: Khi phân tích độ phức tạp thời gian bằng ký hiệu Big O, chúng ta thường bỏ qua các yếu tố nào?

• A. Chỉ số của vòng lặp.
• B. Tên biến.
• C. Số lượng tham số của hàm.
• D. Các hằng số nhân và các số hạng bậc thấp.

Câu 6: Một thuật toán có thời gian thực hiện được mô tả bởi hàm T(n) = 3n^2 + 5n + 100. Độ phức tạp thời gian theo ký hiệu Big O của thuật toán này là gì?

• A. O(n)
• B. O(log n)
• C. O(n^2)
• D. O(n^3)

Câu 7: Quy tắc cộng trong đánh giá độ phức tạp thời gian được áp dụng khi nào?

• A. Khi các khối lệnh hoặc hàm được thực hiện nối tiếp nhau.
• B. Khi có các vòng lặp lồng nhau.
• C. Khi một hàm gọi một hàm khác.
• D. Khi có các phép toán số học đơn giản.

Câu 8: Quy tắc nhân trong đánh giá độ phức tạp thời gian được áp dụng khi nào?

• A. Khi các khối lệnh hoặc hàm được thực hiện nối tiếp nhau.
• B. Khi một khối lệnh (có độ phức tạp T1) được thực hiện bên trong một vòng lặp hoặc khối lệnh khác (có độ phức tạp T2).
• C. Khi so sánh hai thuật toán khác nhau.
• D. Khi tính tổng thời gian thực hiện của tất cả các lệnh.

Câu 9: Cho đoạn mã Python sau:
```python
def example_func(n):
if n <= 1: return 1 else: print("Hello") return example_func(n-1) + example_func(n-2) ``` Độ phức tạp thời gian của hàm đệ quy này (ví dụ tính số Fibonacci cơ bản) là gì?

• A. O(n)
• B. O(n^2)
• C. O(log n)
• D. O(2^n)

Câu 10: Thuật toán Tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có độ phức tạp thời gian trung bình là gì?

• A. O(n)
• B. O(n^2)
• C. O(log n)
• D. O(1)

Câu 11: Độ phức tạp thời gian O(n log n) thường xuất hiện trong các loại thuật toán nào?

• A. Các thuật toán sắp xếp hiệu quả (ví dụ: Merge Sort, Quick Sort).
• B. Các thuật toán tìm kiếm tuyến tính.
• C. Các thuật toán có vòng lặp lồng nhau đơn giản.
• D. Các thuật toán có thời gian thực hiện không đổi.

Câu 12: Giả sử thuật toán A có độ phức tạp O(n) và thuật toán B có độ phức tạp O(n^2). Khi kích thước đầu vào n rất lớn, thuật toán nào sẽ có thời gian thực hiện tốt hơn?

• A. Thuật toán A (O(n)).
• B. Thuật toán B (O(n^2)).
• C. Thời gian thực hiện của cả hai thuật toán là như nhau.
• D. Không thể xác định nếu không biết hằng số.

Câu 13: Tại sao việc đánh giá độ phức tạp thời gian lại quan trọng trong lập trình, đặc biệt khi xử lý dữ liệu lớn?

• A. Giúp chương trình chạy nhanh hơn trên mọi máy tính.
• B. Giúp giảm dung lượng bộ nhớ mà chương trình sử dụng.
• C. Giúp xác định lỗi cú pháp trong mã nguồn.
• D. Giúp dự đoán hiệu suất của thuật toán khi kích thước đầu vào tăng lên và so sánh các thuật toán khác nhau.

Câu 14: Cho đoạn mã Python:
```python
def simple_ops(a, b):
c = a + b
d = c * 2
return d / 3
```
Độ phức tạp thời gian của hàm `simple_ops` là gì?

• A. O(n) (phụ thuộc vào giá trị của a, b)
• B. O(log n)
• C. O(n^2)
• D. O(1)

Câu 15: Khi nói về độ phức tạp thời gian của thuật toán, trường hợp "xấu nhất" (worst-case) có ý nghĩa gì?

• A. Thời gian thực hiện tối đa mà thuật toán có thể mất cho một đầu vào có kích thước n.
• B. Thời gian thực hiện trung bình cho một đầu vào có kích thước n.
• C. Thời gian thực hiện tối thiểu cho một đầu vào có kích thước n.
• D. Thời gian thực hiện khi thuật toán gặp lỗi.

Câu 16: Cho đoạn mã Python sau:
```python
def process_data(arr):
n = len(arr)
# Block 1
for i in range(n):
print(arr[i])
# Block 2
for i in range(n):
for j in range(n):
print(arr[i], arr[j])
```
Với `n` là kích thước mảng `arr`, độ phức tạp thời gian của hàm `process_data` là gì?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(n + n^2)

Câu 17: Một thuật toán có độ phức tạp O(log n) có nghĩa là gì?

• A. Thời gian thực hiện tăng chậm khi kích thước đầu vào n tăng, thường liên quan đến việc chia nhỏ bài toán.
• B. Thời gian thực hiện tăng rất nhanh khi kích thước đầu vào n tăng.
• C. Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào n.
• D. Thời gian thực hiện không đổi với mọi kích thước đầu vào.

Câu 18: Sắp xếp các độ phức tạp thời gian sau từ hiệu quả nhất đến kém hiệu quả nhất khi n rất lớn: O(n^2), O(log n), O(n), O(n log n).

• A. O(n^2), O(n log n), O(n), O(log n)
• B. O(n), O(log n), O(n^2), O(n log n)
• C. O(log n), O(n), O(n log n), O(n^2)
• D. O(log n), O(n log n), O(n), O(n^2)

Câu 19: Nếu một thuật toán có độ phức tạp O(n) mất 5 giây để xử lý đầu vào có kích thước n = 1000, thì ước tính nó sẽ mất bao lâu để xử lý đầu vào có kích thước n = 2000?

• A. Khoảng 10 giây.
• B. Khoảng 20 giây.
• C. Khoảng 5 giây.
• D. Khoảng 25 giây.

Câu 20: Nếu một thuật toán có độ phức tạp O(n^2) mất 2 giây để xử lý đầu vào có kích thước n = 100, thì ước tính nó sẽ mất bao lâu để xử lý đầu vào có kích thước n = 300?

• A. Khoảng 6 giây.
• B. Khoảng 18 giây.
• C. Khoảng 36 giây.
• D. Khoảng 18 giây (kích thước tăng 3 lần, thời gian tăng 3^2=9 lần, 2*9=18).

Câu 21: Cho đoạn mã Python sau:
```python
def mystery(n):
count = 0
i = 1
while i < n: count += 1 i *= 2 return count ``` Với `n` là số nguyên dương, độ phức tạp thời gian của hàm `mystery` là gì?

• A. O(n)
• B. O(log n)
• C. O(n^2)
• D. O(1)

Câu 22: Trong phân tích độ phức tạp thời gian, ký hiệu Ω (Omega lớn) biểu thị điều gì?

• A. Giới hạn trên chặt của thời gian thực hiện (worst-case).
• B. Giới hạn trung bình của thời gian thực hiện (average-case).
• C. Giới hạn dưới của thời gian thực hiện (best-case).
• D. Độ phức tạp chính xác.

Câu 23: Một thuật toán duyệt qua tất cả các cặp phần tử có thể có trong một danh sách n phần tử. Độ phức tạp thời gian điển hình của thuật toán này là gì?

• A. O(n)
• B. O(log n)
• C. O(n log n)
• D. O(n^2)

Câu 24: Tại sao các hằng số và các số hạng bậc thấp lại bị bỏ qua trong ký hiệu Big O khi n đủ lớn?

• A. Vì khi n rất lớn, sự đóng góp của các số hạng bậc cao hơn trở nên chi phối hoàn toàn.
• B. Vì chúng luôn bằng 0.
• C. Vì chúng chỉ ảnh hưởng đến độ phức tạp không gian, không phải thời gian.
• D. Vì chúng chỉ quan trọng đối với các đầu vào nhỏ.

Câu 25: Thuật toán sắp xếp nổi bọt (Bubble Sort) có độ phức tạp thời gian trong trường hợp xấu nhất là gì?

• A. O(n)
• B. O(n^2)
• C. O(n log n)
• D. O(log n)

Câu 26: Cho đoạn mã Python sau:
```python
def another_func(n):
total = 0
for i in range(100): # Vòng lặp chạy 100 lần cố định
total += i
for j in range(n):
total += j
return total
```
Với `n` là kích thước đầu vào, độ phức tạp thời gian của hàm `another_func` là gì?

• A. O(n)
• B. O(100 + n)
• C. O(100n)
• D. O(1)

Câu 27: Khi so sánh hai thuật toán A (O(n log n)) và B (O(n^2)), thuật toán nào sẽ trở nên vượt trội hơn khi kích thước dữ liệu n tăng lên đáng kể?

• A. Thuật toán A (O(n log n))
• B. Thuật toán B (O(n^2))
• C. Cả hai thuật toán có hiệu suất tương đương.
• D. Không thể xác định mà không biết giá trị cụ thể của n.

Câu 28: Trường hợp "tốt nhất" (best-case) của độ phức tạp thời gian của một thuật toán biểu thị điều gì?

• A. Thời gian thực hiện trung bình cho một đầu vào có kích thước n.
• B. Thời gian thực hiện tối đa mà thuật toán có thể mất cho một đầu vào có kích thước n.
• C. Thời gian thực hiện khi bộ nhớ đầy.
• D. Thời gian thực hiện tối thiểu mà thuật toán có thể mất cho một đầu vào có kích thước n.

Câu 29: Cho đoạn mã Python sau:
```python
def process_matrix(matrix):
rows = len(matrix)
cols = len(matrix[0]) # Giả sử ma trận không rỗng
for i in range(rows):
for j in range(cols):
print(matrix[i][j])
```
Với ma trận có kích thước `m` hàng và `n` cột, độ phức tạp thời gian của hàm `process_matrix` là gì?

• A. O(m)
• B. O(n)
• C. O(m * n)
• D. O(m + n)

Câu 30: Mục đích chính của việc sử dụng ký hiệu Big O là để làm gì?

• A. Tính toán chính xác số mili giây mà thuật toán sẽ chạy.
• B. Mô tả cách thời gian thực hiện của thuật toán thay đổi khi kích thước đầu vào tăng lên.
• C. So sánh hiệu quả của thuật toán trên các phần cứng máy tính khác nhau.
• D. Xác định ngôn ngữ lập trình tốt nhất để cài đặt thuật toán.