Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 25: Thực Hành Xác Định Độ Phức Tạp Thời Gian Thuật Toán

Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 25: Thực Hành Xác Định Độ Phức Tạp Thời Gian Thuật Toán tổng hợp câu hỏi trắc nghiệm chứa đựng nhiều dạng bài tập, bài thi, cũng như các câu hỏi trắc nghiệm và bài kiểm tra, trong bộ Trắc Nghiệm Tin Học 11 – Kết Nối Tri Thức. Nội dung trắc nghiệm nhấn mạnh phần kiến thức nền tảng và chuyên môn sâu của học phần này. Mọi bộ đề trắc nghiệm đều cung cấp câu hỏi, đáp án cùng hướng dẫn giải cặn kẽ. Mời bạn thử sức làm bài nhằm ôn luyện và làm vững chắc kiến thức cũng như đánh giá năng lực bản thân!

Đề 01

Đề 02

Đề 03

Đề 04

Đề 05

Đề 06

Đề 07

Đề 08

Đề 09

Đề 10

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 01

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

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 quan tâm đến trường hợp xấu nhất (worst-case) thay vì trường hợp tốt nhất (best-case) hoặc trung bình (average-case)?

Vì trường hợp tốt nhất hiếm khi xảy ra trong thực tế.

Vì trường hợp trung bình quá khó để tính toán chính xác.

Vì trường hợp xấu nhất luôn là trường hợp nhanh nhất.

Vì trường hợp xấu nhất cho biết giới hạn trên về thời gian chạy, đảm bảo hiệu suất không bao giờ vượt quá mức đó.

Câu hỏi kiểm tra hiểu biết về ý nghĩa của việc phân tích trường hợp xấu nhất trong độ phức tạp thuật toán. Trường hợp xấu nhất đảm bảo rằng thuật toán sẽ không bao giờ mất thời gian nhiều hơn giới hạn đó, cung cấp một đảm bảo về hiệu suất tối đa.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 2: Cho đoạn mã giả sau:
```
sum = 0
for i from 1 to n:
sum = sum + i
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu Big O là gì?

O(1)

O(n)

O(n log n)

O(n^2)

Đoạn mã có một vòng lặp chạy từ 1 đến n. Số lần lặp tỷ lệ thuận với n. Do đó, độ phức tạp thời gian là O(n).

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 3: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to n:
print(i * j)
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu Big O là gì?

O(n)

O(n log n)

O(n^3)

O(n^2)

Đoạn mã có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n lần, và vòng lặp trong cũng chạy n lần cho mỗi lần lặp của vòng ngoài. Tổng số phép in (hoạt động cơ bản) là n * n = n^2. Do đó, độ phức tạp thời gian là O(n^2).

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 4: Thuật toán tìm kiếm nhị phân (Binary Search) 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 gì khi kích thước mảng (n) tăng lên?

Thời gian thực hiện tăng rất chậm khi kích thước mảng tăng.

Thời gian thực hiện tăng tuyến tính với kích thước mảng.

Thời gian thực hiện tăng nhanh chóng (bình phương) khi kích thước mảng tăng.

Thời gian thực hiện là hằng số, không phụ thuộc vào kích thước mảng.

Độ phức tạp O(log n) cho thấy thời gian thực hiện tăng rất chậm khi kích thước dữ liệu tăng lên. Logarit của n tăng chậm hơn nhiều so với n. Ví dụ, log₂ của 1024 là 10, trong khi n là 1024.

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 5: Xét thuật toán Linear Search (tìm kiếm tuần tự) trên một mảng có n phần tử. Trong trường hợp tốt nhất, phần tử cần tìm nằm ở đâu?

Ở vị trí đầu tiên của mảng.

Ở vị trí cuối cùng của mảng.

Ở vị trí chính giữa của mảng.

Phần tử không tồn tại trong mảng.

Trường hợp tốt nhất cho Linear Search là khi phần tử cần tìm được tìm thấy ngay lập tức. Điều này xảy ra khi nó là phần tử đầu tiên được kiểm tra, tức là nằm ở đầu mảng.

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 6: Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán Linear Search trên mảng có n phần tử là gì?

O(1)

O(log n)

O(n)

O(n^2)

Trường hợp xấu nhất cho Linear Search là khi phần tử cần tìm nằm ở cuối mảng hoặc không tồn tại trong mảng. Khi đó, thuật toán phải duyệt qua tất cả n phần tử. Số phép so sánh tỷ lệ thuận với n. Do đó, độ phức tạp là O(n).

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 7: Thuật toán sắp xếp Selection Sort (sắp xếp chọn) hoạt động bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của mảng và đưa nó về đúng vị trí. Độ phức tạp thời gian trong trường hợp xấu nhất của Selection Sort trên mảng n phần tử là gì?

O(n)

O(n log n)

O(log n)

O(n^2)

Selection Sort có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n-1 lần. Vòng lặp trong để tìm phần tử nhỏ nhất trong phần còn lại của mảng chạy khoảng n, n-1, ..., 1 lần. Tổng số phép so sánh và đổi chỗ tỷ lệ với n^2. Độ phức tạp trong mọi trường hợp (tốt nhất, xấu nhất, trung bình) đều là O(n^2).

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 8: Điều gì xảy ra với thời gian chạy của một thuật toán có độ phức tạp O(n^2) khi kích thước dữ liệu đầu vào (n) tăng gấp đôi?

Thời gian chạy tăng gấp đôi.

Thời gian chạy tăng gấp ba lần.

Thời gian chạy tăng gấp bốn lần.

Thời gian chạy không thay đổi đáng kể.

Nếu thời gian chạy là T(n) ≈ c * n^2, khi n tăng gấp đôi thành 2n, thời gian chạy mới là T(2n) ≈ c * (2n)^2 = c * 4n^2 = 4 * (c * n^2) = 4 * T(n). Thời gian chạy tăng gấp 4 lần.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 9: Cho đoạn mã giả sau:
```
count = 0
if condition:
for i from 1 to n:
count = count + 1
else:
count = 10
```
Với n rất lớn, độ phức tạp thời gian của đoạn mã này trong trường hợp xấu nhất là gì?

O(1)

O(n)

O(n^2)

O(log n)

Trong trường hợp xấu nhất, điều kiện 'if' đúng và vòng lặp 'for' chạy n lần. Số phép tính tỷ lệ thuận với n. Trường hợp 'else' chỉ tốn thời gian hằng số (O(1)). Khi n rất lớn, phần O(n) chi phối, do đó độ phức tạp là O(n).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 10: Thuật toán Bubble Sort (sắp xếp nổi bọt) có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2). Trường hợp tốt nhất của Bubble Sort xảy ra khi nào và độ phức tạp thời gian trong trường hợp đó là gì?

Khi mảng đã sắp xếp, O(n)

Khi mảng đã sắp xếp, O(1)

Khi mảng đảo ngược hoàn toàn, O(n)

Khi mảng đảo ngược hoàn toàn, O(n^2)

Trường hợp tốt nhất của Bubble Sort là khi mảng đã được sắp xếp. Bubble Sort có thể kiểm tra xem có bất kỳ cặp nào cần đổi chỗ trong một lần duyệt mảng hay không. Nếu không có đổi chỗ nào trong một lần duyệt đầy đủ, thuật toán sẽ dừng lại. Điều này chỉ mất một lần duyệt mảng, tương ứng với O(n) phép so sánh.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 11: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to 100:
print(i + j)
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu Big O là gì?

O(100)

O(n)

O(100n)

O(n^2)

Vòng lặp ngoài chạy n lần. Vòng lặp trong chạy 100 lần cố định cho mỗi lần lặp của vòng ngoài. Số phép in là n * 100. Vì 100 là hằng số, chúng ta bỏ qua nó trong ký hiệu Big O. Độ phức tạp là O(n).

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 12: Một thuật toán có độ phức tạp thời gian là O(n log n). Nếu với n = 1000, thuật toán chạy mất 1 giây, ước tính thời gian chạy khi n = 1000000 (1 triệu) là bao nhiêu? (Gợi ý: log₂1000 ≈ 10, log₂1000000 ≈ 20)

100 giây

1000 giây

Khoảng 2000 giây

Khoảng 1000000 giây

Thời gian chạy T(n) ≈ c * n log n. Ta có T(1000) ≈ c * 1000 * 10 = 10000c = 1 giây. Suy ra c = 1/10000 giây. Khi n = 1000000, T(1000000) ≈ c * 1000000 * 20 = 20000000c = 20000000 * (1/10000) = 2000 giây = 33.33 phút.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 13: Thuật toán nào trong các thuật toán sau có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2)?

Linear Search

Binary Search

Quick Sort (trường hợp trung bình)

Selection Sort

Selection Sort và Bubble Sort đều có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất (và cả trường hợp trung bình). Linear Search là O(n). Binary Search là O(log n).

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 14: 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) cho cùng một bài toán, điều gì có khả năng xảy ra nhất khi kích thước dữ liệu đầu vào (n) rất lớn?

Thuật toán A sẽ chạy nhanh hơn đáng kể so với thuật toán B.

Thuật toán B sẽ chạy nhanh hơn đáng kể so với thuật toán A.

Cả hai thuật toán sẽ có thời gian chạy tương đương.

Kết quả phụ thuộc vào các hằng số ẩn trong ký hiệu Big O.

Với n lớn, hàm n tăng chậm hơn nhiều so với hàm n^2. Do đó, thuật toán có độ phức tạp tuyến tính (O(n)) sẽ chạy nhanh hơn đáng kể so với thuật toán có độ phức tạp bình phương (O(n^2)).

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 15: Cho đoạn mã giả sau:
```
for i from 1 to n/2:
print(i)
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu Big O là gì?

O(n/2)

O(1)

O(n)

O(log n)

Vòng lặp chạy từ 1 đến n/2. Số lần lặp là n/2. Trong ký hiệu Big O, các hằng số và các số hạng bậc thấp được bỏ qua. n/2 tỷ lệ thuận với n. Do đó, độ phức tạp là O(n).

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 16: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from i to n:
print(i + j)
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu Big O là gì?

O(n)

O(n log n)

O(n^3)

O(n^2)

Vòng lặp ngoài chạy n lần (i từ 1 đến n). Vòng lặp trong chạy từ i đến n. Khi i=1, j chạy n lần. Khi i=2, j chạy n-1 lần. ... Khi i=n, j chạy 1 lần. Tổng số phép in là 1 + 2 + ... + n = n(n+1)/2. Đây là một đa thức bậc 2 theo n. Do đó, độ phức tạp là O(n^2).

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 17: Phát biểu nào sau đây là ĐÚNG về mối quan hệ giữa độ phức tạp thời gian O(n) và O(n^2)?

O(n^2) luôn hiệu quả hơn O(n).

O(n) hiệu quả hơn O(n^2) khi n đủ lớn.

Độ hiệu quả của chúng là như nhau.

O(n) chỉ hiệu quả hơn O(n^2) khi n rất nhỏ.

Với n đủ lớn, hàm n luôn tăng chậm hơn hàm n^2. Do đó, một thuật toán O(n) sẽ luôn hiệu quả hơn (chạy nhanh hơn) một thuật toán O(n^2) khi kích thước dữ liệu lớn.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 18: Khi phân tích một thuật toán, chúng ta thường bỏ qua các hằng số và các số hạng bậc thấp trong biểu thức thời gian chạy. Ví dụ, nếu thời gian chạy là 3n^2 + 5n + 10, tại sao chúng ta lại biểu diễn độ phức tạp là O(n^2)?

Vì hằng số và số hạng bậc thấp không ảnh hưởng đến thời gian chạy thực tế.

Vì việc tính toán chính xác thời gian chạy với tất cả các số hạng là quá phức tạp.

Vì khi n rất lớn, số hạng bậc cao nhất (n^2) là yếu tố chi phối đến sự tăng trưởng của thời gian chạy.

Vì ký hiệu Big O chỉ áp dụng cho các thuật toán có thời gian chạy là hàm đơn giản của n.

Ký hiệu Big O tập trung vào hành vi tiệm cận của thuật toán khi kích thước đầu vào (n) tiến tới vô cùng. Khi n rất lớn, số hạng có bậc cao nhất (n^2) sẽ chi phối giá trị của toàn bộ biểu thức, trong khi các hằng số (3, 10) và số hạng bậc thấp hơn (5n) trở nên không đáng kể so với n^2.

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 19: Một thuật toán thực hiện 1000 phép tính độc lập với kích thước đầu vào n. Độ phức tạp thời gian của thuật toán này là gì?

O(1)

O(1000)

O(n)

O(log n)

Nếu số phép tính là một hằng số (1000), không phụ thuộc vào kích thước đầu vào n, thì độ phức tạp thời gian là O(1) - độ phức tạp hằng số.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 20: Cho đoạn mã giả sau:
```
result = 0
for i from 1 to n:
for j from 1 to i:
result = result + 1
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu Big O là gì?

O(n)

O(n log n)

O(n^3)

O(n^2)

Vòng lặp ngoài chạy n lần (i từ 1 đến n). Vòng lặp trong chạy i lần. Tổng số lần cộng 'result' là 1 (khi i=1) + 2 (khi i=2) + ... + n (khi i=n) = n(n+1)/2. Đây là một đa thức bậc 2 theo n. Do đó, độ phức tạp là O(n^2).

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 21: Thuật toán nào sau đây thường được coi là hiệu quả nhất (có độ phức tạp thấp nhất) trong việc tìm kiếm một phần tử trong một mảng đã được sắp xếp?

Linear Search

Binary Search

Selection Sort (để tìm min/max)

Bubble Sort

Binary Search trên mảng đã sắp xếp có độ phức tạp O(log n), nhanh hơn đáng kể so với Linear Search (O(n)) khi n lớn.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 22: Một thuật toán có độ phức tạp O(log n). Điều này thường xuất hiện trong các thuật toán nào?

Thuật toán duyệt qua tất cả các cặp phần tử.

Thuật toán duyệt qua tất cả các phần tử một lần.

Thuật toán liên tục chia đôi phạm vi tìm kiếm/xử lý.

Thuật toán thực hiện một số lượng phép tính cố định.

Độ phức tạp O(log n) đặc trưng cho các thuật toán chia đôi phạm vi tìm kiếm hoặc xử lý dữ liệu trong mỗi bước, ví dụ như tìm kiếm nhị phân (Binary Search).

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 23: Giả sử một thuật toán sắp xếp có độ phức tạp O(n log n). Nếu với n = 1000, thuật toán chạy mất 1 giây. Ước tính thời gian chạy khi n = 2000 là bao nhiêu?

Khoảng 1.5 giây

Khoảng 2 giây

Khoảng 2.2 giây

Khoảng 4 giây

Thời gian chạy T(n) ≈ c * n log n. T(1000) ≈ c * 1000 * log(1000) = 1 giây. T(2000) ≈ c * 2000 * log(2000). log(2000) = log(2 * 1000) = log(2) + log(1000). Nếu dùng log₂: log₂1000 ≈ 10, log₂2000 ≈ 11. T(2000) / T(1000) ≈ (2000 * 11) / (1000 * 10) = 2 * 1.1 = 2.2. Thời gian chạy tăng khoảng 2.2 lần.

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 24: Cho đoạn mã giả sau:
```
count = 0
for i from 1 to n:
for j from 1 to i * i:
count = count + 1
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu Big O là gì?

O(n^2)

O(n log n)

O(n)

O(n^3)

Vòng lặp ngoài chạy n lần (i từ 1 đến n). Vòng lặp trong chạy i*i lần. Tổng số lần cộng 'count' là 1² (khi i=1) + 2² (khi i=2) + ... + n² (khi i=n). Tổng của các bình phương từ 1 đến n là n(n+1)(2n+1)/6, đây là một đa thức bậc 3 theo n. Do đó, độ phức tạp là O(n^3).

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 25: Tại sao việc xác định độ phức tạp thời gian của thuật toán lại quan trọng trong lập trình?

Để đá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.

Để biết chính xác thời gian chạy trên một máy tính cụ thể.

Để tìm ra lỗi (bug) trong chương trình.

Để biết số dòng mã trong thuật toán.

Việc xác định độ phức tạp giúp đánh giá hiệu suất của thuật toán khi kích thước dữ liệu lớn, cho phép so sánh và lựa chọn thuật toán phù hợp nhất cho bài toán, đặc biệt là với các bộ dữ liệu lớn.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 26: Cho đoạn mã giả sau:
```
function process(n):
if n <= 10: print("Small") else: for i from 1 to n: print("Large") ``` Độ phức tạp thời gian của hàm `process(n)` theo ký hiệu Big O là gì?

O(1)

O(n)

O(log n)

O(n^2)

Khi n nhỏ (<= 10), hàm chỉ thực hiện một phép in (O(1)). Khi n lớn hơn 10, hàm thực hiện một vòng lặp chạy n lần (O(n)). Khi n tiến tới vô cùng, nhánh 'else' với độ phức tạp O(n) sẽ chi phối. Do đó, độ phức tạp tổng thể là O(n).

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 27: Thuật toán Bubble Sort (sắp xếp nổi bọt) và Selection Sort (sắp xếp chọn) đều có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2). Tuy nhiên, trong thực tế, thuật toán nào thường có xu hướng chạy nhanh hơn một chút trên các bộ dữ liệu ngẫu nhiên và tại sao?

Bubble Sort, vì nó có thể dừng sớm nếu mảng đã được sắp xếp hoặc gần sắp xếp.

Selection Sort, vì nó chỉ thực hiện n-1 phép đổi chỗ.

Cả hai đều có thời gian chạy thực tế hoàn toàn giống nhau.

Độ phức tạp O(n^2) nghĩa là chúng luôn chạy chậm như nhau.

Mặc dù cả hai đều là O(n^2), Bubble Sort có thể dừng sớm trong trường hợp tốt hơn (O(n)) hoặc khi mảng gần được sắp xếp. Selection Sort luôn thực hiện cùng một số lượng phép so sánh và n-1 phép đổi chỗ, bất kể trạng thái ban đầu của mảng. Trong trường hợp trung bình trên dữ liệu ngẫu nhiên, số phép đổi chỗ của Bubble Sort có thể ít hơn, nhưng số phép so sánh vẫn là O(n^2). Tuy nhiên, câu hỏi hỏi về xu hướng chạy nhanh hơn một chút, và Bubble Sort có lợi thế dừng sớm trong các trường hợp không hoàn toàn xấu nhất, hoặc khi số phép đổi chỗ có chi phí cao hơn so với so sánh (tùy thuộc vào cài đặt và dữ liệu). Tuy nhiên, một phân tích kỹ hơn cho thấy số phép so sánh của Bubble Sort là O(n^2) ngay cả ở trường hợp trung bình, trong khi Selection Sort cũng là O(n^2) phép so sánh và O(n) phép đổi chỗ. Câu trả lời phụ thuộc vào chi phí tương đối của phép so sánh và đổi chỗ. Tuy nhiên, trong bối cảnh phổ thông, cả hai thường được coi là có hiệu suất tương đương ở bậc O(n^2). Xét trên khía cạnh dừng sớm, Bubble Sort có tiềm năng nhanh hơn ở một số trường hợp không phải là xấu nhất hoàn toàn.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 28: Cho đoạn mã giả sau:
```
function process_array(arr):
n = length(arr)
if n > 1000:
for i from 1 to n:
print(arr[i])
else:
for i from 1 to n:
for j from 1 to n:
print(arr[i] + arr[j])
```
Độ phức tạp thời gian của hàm `process_array(arr)` theo ký hiệu Big O là gì?

O(n^2)

O(n)

O(1000)

O(log n)

Khi n > 1000, hàm thực hiện vòng lặp đơn (O(n)). Khi n <= 1000, hàm thực hiện hai vòng lặp lồng nhau (O(n^2)). Ký hiệu Big O mô tả hành vi khi n *tiến tới vô cùng*. Trong trường hợp này, khi n đủ lớn để vượt qua ngưỡng 1000, thuật toán sẽ theo nhánh O(n). Do đó, độ phức tạp tiệm cận là O(n).

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 29: Giả sử bạn có một bộ dữ liệu rất lớn và cần thực hiện một thao tác có độ phức tạp thời gian là O(n^3). Điều này có ý nghĩa gì về tính khả thi của việc chạy thuật toán này trên bộ dữ liệu đó?

Thuật toán có thể sẽ mất một lượng thời gian rất lớn và không khả thi để chạy trên bộ dữ liệu lớn.

Thuật toán sẽ chạy rất nhanh vì n^3 là một hàm tăng trưởng chậm.

Thời gian chạy sẽ chỉ tăng tuyến tính với kích thước dữ liệu.

Độ phức tạp O(n^3) chỉ áp dụng cho các bài toán nhỏ.

Độ phức tạp O(n^3) tăng rất nhanh khi n tăng. Đối với bộ dữ liệu rất lớn, thời gian chạy sẽ trở nên không khả thi (quá lâu) trên hầu hết các hệ thống máy tính thông thường.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 01

Câu 30: Trong phân tích độ phức tạp, đâu là ký hiệu Big O thể hiện hiệu suất tốt nhất (nhanh nhất khi n lớn)?

O(log n)

O(n)

O(n log n)

O(n^2)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Khi n rất lớn, O(1) (thời gian hằng số) là tốt nhất, tiếp theo là O(log n), sau đó là O(n), O(n log n), O(n^2), O(n^3), v.v. O(log n) tăng chậm hơn O(n), O(n^2).

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 02

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

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

Lượng bộ nhớ mà thuật toán sử dụng.

Số lượng các phép tính cơ bản thực hiện theo kích thước dữ liệu đầu vào.

Tổng thời gian thực thi thực tế trên một máy tính cụ thể.

Mức độ dễ đọc và hiểu của mã nguồn thuật toán.

Độ phức tạp thời gian đo lường số lượng các phép tính cơ bản (như so sánh, gán, truy xuất) mà thuật toán thực hiện, thường được biểu diễn dưới dạng một hàm phụ thuộc vào kích thước dữ liệu đầu vào (n). Nó thể hiện tốc độ tăng trưởng thời gian chạy khi kích thước đầu vào tăng lên.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 2: Ký hiệu Big O (ví dụ: O(n), O(n^2), O(log n)) trong phân tích độ phức tạp thời gian biểu thị điều gì?

Giới hạn trên (tốc độ tăng trưởng tối đa) của thời gian chạy khi kích thước đầu vào lớn.

Thời gian chạy chính xác của thuật toán trên mọi bộ dữ liệu.

Thời gian chạy trung bình của thuật toán.

Giới hạn dưới (tốc độ tăng trưởng tối thiểu) của thời gian chạy.

Ký hiệu Big O biểu thị giới hạn trên (upper bound) của tốc độ tăng trưởng thời gian chạy của thuật toán trong trường hợp xấu nhất (worst-case), bỏ qua các hệ số và hằng số. Nó mô tả cách thời gian chạy tăng lên khi kích thước đầu vào (n) tiến tới vô cùng.

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 3: Xem xét đoạn mã giả sau:
```
function processArray(arr):
n = length(arr)
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?

O(1)

O(n)

O(n log n)

O(n^2)

Đoạn mã có một vòng lặp duy nhất chạy từ 0 đến n-1, thực hiện một số phép tính cơ bản (truy xuất phần tử mảng, cộng, gán) bên trong. Số lần lặp tỷ lệ thuận với kích thước mảng n. Do đó, độ phức tạp thời gian là O(n).

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 4: Xem xét đoạn mã giả sau:
```
function printPairs(arr):
n = length(arr)
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?

O(n)

O(log n)

O(n log n)

O(n^2)

Đoạn mã có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n lần, và với mỗi lần lặp của vòng lặp ngoài, vòng lặp trong cũng chạy n lần. Tổng số lần thực hiện phép in (hoặc các phép tính bên trong) là n * n = n^2. Do đó, độ phức tạp thời gian là O(n^2).

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 5: Xem xét đoạn mã giả sau:
```
function findMax(arr):
n = length(arr)
if n == 0:
return null
max_val = arr[0]
for i from 1 to n-1:
if arr[i] > max_val:
max_val = arr[i]
return max_val
```
Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán tìm giá trị lớn nhất này là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

Thuật toán duyệt qua mảng một lần duy nhất để tìm giá trị lớn nhất. Vòng lặp chạy n-1 lần. Số phép so sánh và gán tỷ lệ thuận với n. Do đó, độ phức tạp thời gian là O(n). Trường hợp xấu nhất xảy ra khi phần tử lớn nhất nằm ở cuối mảng, nhưng số phép tính vẫn tỷ lệ tuyến tính với n.

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 6: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp tốt nhất (best-case) là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

Trường hợp tốt nhất của tìm kiếm tuần tự là khi phần tử cần tìm nằm ngay ở vị trí đầu tiên của mảng. Thuật toán chỉ cần thực hiện một phép so sánh để tìm thấy và trả về kết quả. Số phép tính không phụ thuộc vào n, nên độ phức tạp là O(1).

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 7: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp xấu nhất (worst-case) là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

Trường hợp xấu nhất của tìm kiếm tuần tự là khi phần tử cần tìm nằm ở vị trí cuối cùng của mảng hoặc không có trong mảng. Thuật toán phải duyệt qua toàn bộ n phần tử để tìm kiếm. Số phép tính tỷ lệ thuận với n. Do đó, độ phức tạp thời gian là O(n).

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

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

O(n)

O(log n)

O(n log n)

O(n^2)

Thuật toán sắp xếp chọn có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n-1 lần. Vòng lặp trong (để tìm phần tử nhỏ nhất trong phần còn lại của mảng) chạy khoảng n, n-1, n-2,... lần. Tổng số phép so sánh và đổi chỗ tỷ lệ với n^2. Độ phức tạp luôn là O(n^2) bất kể trạng thái ban đầu của mảng.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 9: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp xấu nhất là bao nhiêu?

O(n)

O(log n)

O(n log n)

O(n^2)

Thuật toán sắp xếp nổi bọt trong trường hợp xấu nhất (mảng sắp xếp ngược) cũng có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n-1 lần, và vòng lặp trong (để so sánh và đổi chỗ các cặp phần tử kề nhau) chạy khoảng n, n-1, ... lần. Tổng số phép so sánh và đổi chỗ tỷ lệ với n^2. Độ phức tạp là O(n^2).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 10: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp tốt nhất (best-case) là bao nhiêu?

O(1)

O(n)

O(n log n)

O(n^2)

Trường hợp tốt nhất của Bubble Sort là khi mảng đã được sắp xếp. Thuật toán vẫn cần duyệt qua mảng ít nhất một lần để kiểm tra xem có cần đổi chỗ nào không. Nếu không có đổi chỗ nào trong lần duyệt đầu tiên, thuật toán có thể dừng lại. Do đó, chỉ cần một lần duyệt qua mảng, độ phức tạp là O(n).

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 11: Xem xét đoạn mã giả sau:
```
function example(n):
count = 0
for i from 1 to n:
for j from 1 to i:
count = count + 1
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n log n)

O(n^3)

O(n^2)

Vòng lặp ngoài chạy n lần. Vòng lặp trong chạy i lần, với i tăng từ 1 đến n. Tổng số lần thực hiện phép cộng là 1 + 2 + ... + n = n*(n+1)/2. Đây là một đa thức bậc 2 của n. Do đó, độ phức tạp là O(n^2).

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 12: Xem xét đoạn mã giả sau:
```
function process(n):
k = 1
while k < n: print(k) k = k * 2 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n^2)

O(log n)

O(1)

Biến k bắt đầu từ 1 và nhân đôi sau mỗi lần lặp (1, 2, 4, 8, ...). Vòng lặp dừng khi k đạt đến hoặc vượt quá n. Số lần lặp m thỏa mãn 2^m ≈ n, tức là m ≈ log₂(n). Do đó, độ phức tạp thời gian là O(log n).

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 13: 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 dữ liệu đầu vào n rất lớn, phát biểu nào sau đây là đúng nhất về hiệu suất của hai thuật toán?

Thuật toán A (O(n)) sẽ chạy nhanh hơn đáng kể so với thuật toán B (O(n^2)).

Thuật toán B (O(n^2)) sẽ chạy nhanh hơn đáng kể so với thuật toán A (O(n)).

Hai thuật toán sẽ có hiệu suất tương đương.

Không thể so sánh hiệu suất chỉ dựa vào ký hiệu Big O.

Với n lớn, hàm n tăng chậm hơn nhiều so với hàm n^2. Do đó, thuật toán có độ phức tạp O(n) sẽ thực hiện ít phép tính hơn đáng kể và chạy nhanh hơn thuật toán có độ phức tạp O(n^2).

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 14: Nếu một thuật toán có độ phức tạp thời gian O(n^3) và mất 1 giây để xử lý dữ liệu có kích thước n=100. Ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=200 là bao nhiêu?

2 giây

4 giây

8 giây

16 giây

Với độ phức tạp O(n^3), thời gian chạy tỷ lệ với n^3. Khi n tăng gấp đôi (từ 100 lên 200), thời gian chạy sẽ tăng (2n)^3 / n^3 = 8 lần. Nếu mất 1 giây cho n=100, sẽ mất khoảng 1 giây * 8 = 8 giây cho n=200.

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 15: Nếu một thuật toán có độ phức tạp thời gian O(n) và mất 1 giây để xử lý dữ liệu có kích thước n=1000. Ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=10000 là bao nhiêu?

1 giây

5 giây

50 giây

10 giây

Với độ phức tạp O(n), thời gian chạy tỷ lệ với n. Khi n tăng gấp 10 lần (từ 1000 lên 10000), thời gian chạy cũng sẽ tăng 10 lần. Nếu mất 1 giây cho n=1000, sẽ mất khoảng 1 giây * 10 = 10 giây cho n=10000.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 16: Trong phân tích độ phức tạp thời gian bằng ký hiệu Big O, khi biểu thức thời gian là một đa thức (ví dụ: 5n^2 + 3n + 10), ta chỉ giữ lại thành phần nào để xác định độ phức tạp?

Thành phần có hệ số lớn nhất.

Tất cả các thành phần và hệ số.

Thành phần có bậc (lũy thừa của n) cao nhất, bỏ qua hệ số.

Thành phần hằng số.

Trong ký hiệu Big O, ta quan tâm đến tốc độ tăng trưởng khi n rất lớn. Khi n lớn, thành phần có bậc cao nhất trong đa thức sẽ chi phối toàn bộ giá trị của biểu thức. Các hệ số và các thành phần bậc thấp hơn trở nên không đáng kể so với thành phần bậc cao nhất. Do đó, ta chỉ giữ lại thành phần có bậc cao nhất và bỏ qua hệ số.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

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

Chia đôi phạm vi tìm kiếm/xử lý (ví dụ: tìm kiếm nhị phân).

Duyệt qua tất cả các cặp phần tử trong mảng.

Duyệt qua từng phần tử một lần duy nhất.

Thực hiện một số lượng phép tính cố định, không phụ thuộc vào kích thước đầu vào.

Độ phức tạp O(log n) đặc trưng cho các thuật toán chia đôi phạm vi tìm kiếm hoặc xử lý trong mỗi bước, ví dụ như thuật toán tìm kiếm nhị phân (Binary Search) trên mảng đã sắp xếp, hoặc một số thuật toán liên quan đến cây nhị phân cân bằng.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

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

Thời gian chạy tăng tuyến tính theo n.

Thời gian chạy tăng theo logarit của n.

Thời gian chạy tăng theo bình phương của n.

Thời gian chạy là một hằng số, không phụ thuộc vào kích thước đầu vào n.

Độ phức tạp O(1) (hằng số) có nghĩa là thời gian thực hiện của thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào n. Số lượng phép tính luôn cố định, bất kể n lớn hay nhỏ (miễn là n hợp lệ).

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 19: Sắp xếp các độ phức tạp thời gian sau theo thứ tự tăng dần về tốc độ tăng trưởng khi n rất lớn: O(n^2), O(log n), O(n), O(1).

O(n^2), O(n), O(log n), O(1)

O(1), O(log n), O(n), O(n^2)

O(log n), O(1), O(n), O(n^2)

O(1), O(n), O(n^2), O(log n)

Khi n rất lớn, tốc độ tăng trưởng của các hàm là: Hằng số (O(1)) tăng chậm nhất, sau đó đến logarit (O(log n)), tuyến tính (O(n)), và cuối cùng là bình phương (O(n^2)) tăng nhanh nhất.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 20: Tại sao việc phân tích độ phức tạp thời gian lại quan trọng trong lập trình, đặc biệt với các bài toán lớn?

Chỉ để so sánh các ngôn ngữ lập trình khác nhau.

Để biết chính xác thời gian chạy trên máy tính của bạn.

Để dự đoán hiệu suất (thời gian chạy) của thuật toán khi kích thước dữ liệu đầu vào trở nên rất lớn.

Để tìm lỗi cú pháp trong mã nguồn.

Phân tích độ phức tạp giúp dự đoán hiệu suất của thuật toán khi dữ liệu đầu vào tăng lên. Đối với các bài toán lớn, sự khác biệt về độ phức tạp (ví dụ O(n) và O(n^2)) có thể dẫn đến sự khác biệt rất lớn về thời gian chạy, từ vài giây lên đến hàng giờ hoặc lâu hơn, làm cho thuật toán kém hiệu quả trở nên không khả thi.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 21: Một thuật toán bao gồm hai phần liên tiếp. Phần thứ nhất có độ phức tạp O(n^2), phần thứ hai có độ phức tạp O(n). Độ phức tạp thời gian tổng thể của thuật toán này là bao nhiêu?

O(n)

O(n + n^2)

O(n log n)

O(n^2)

Khi các phần của thuật toán được thực hiện tuần tự, độ phức tạp tổng thể là độ phức tạp của phần chiếm ưu thế nhất (phần có tốc độ tăng trưởng nhanh nhất). Giữa O(n^2) và O(n), O(n^2) tăng trưởng nhanh hơn. Do đó, độ phức tạp tổng thể là O(n^2).

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 22: Xem xét đoạn mã giả sau:
```
function anotherExample(n):
sum1 = 0
for i from 1 to n:
sum1 = sum1 + i
sum2 = 0
for j from 1 to n:
sum2 = sum2 + j*2
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n^2)

O(n)

O(log n)

O(1)

Đoạn mã có hai vòng lặp độc lập, mỗi vòng lặp chạy n lần. Vòng lặp thứ nhất có độ phức tạp O(n), vòng lặp thứ hai cũng có độ phức tạp O(n). Khi các phần được thực hiện tuần tự, độ phức tạp tổng là O(n) + O(n) = O(n).

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 23: Khi phân tích độ phức tạp thời gian của thuật toán sắp xếp chọn (Selection Sort), tại sao chúng ta thường nói độ phức tạp là O(n^2) cho cả trường hợp tốt nhất, trung bình và xấu nhất?

Số lượng phép so sánh và đổi chỗ luôn tỷ lệ với n^2, bất kể dữ liệu đầu vào.

Thuật toán có thể dừng sớm trong trường hợp tốt nhất.

Chỉ có trường hợp xấu nhất mới có độ phức tạp O(n^2).

Độ phức tạp trung bình là O(n log n).

Thuật toán sắp xếp chọn luôn thực hiện tìm kiếm phần tử nhỏ nhất trong phần mảng chưa sắp xếp và đổi chỗ nó về đúng vị trí. Số lần lặp và số phép so sánh/đổi chỗ trong các vòng lặp lồng nhau là cố định, không phụ thuộc vào trạng thái ban đầu của mảng. Do đó, số bước thực hiện luôn tỷ lệ với n^2.

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 24: Cho một đoạn mã có độ phức tạp thời gian là O(n). Nếu chạy đoạn mã này với n = 1000 mất 0.1 giây, ước tính thời gian chạy khi n = 5000 là bao nhiêu?

0.1 giây

0.25 giây

0.5 giây

1 giây

Với độ phức tạp O(n), thời gian chạy tỷ lệ tuyến tính với n. Khi n tăng từ 1000 lên 5000 (tăng gấp 5 lần), thời gian chạy cũng sẽ tăng gấp 5 lần. Thời gian ước tính là 0.1 giây * 5 = 0.5 giây.

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 25: Xem xét đoạn mã giả sau:
```
function trickyLoop(n):
count = 0
i = 1
while i <= n: count = count + 1 i = i * 3 ``` Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(log n)

O(n^2)

O(sqrt(n))

Biến i bắt đầu từ 1 và nhân 3 sau mỗi lần lặp (1, 3, 9, 27, ...). Vòng lặp dừng khi i đạt đến hoặc vượt quá n. Số lần lặp m thỏa mãn 3^m ≈ n, tức là m ≈ log₃(n). Trong ký hiệu Big O, cơ số của logarit không quan trọng (log_a(n) = log_b(n) * log_a(b), log_a(b) là hằng số). Do đó, độ phức tạp thời gian là O(log n).

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 26: Trong phân tích thuật toán, trường hợp 'trung bình' (average-case) của độ phức tạp thời gian mô tả điều gì?

Thời gian chạy nhanh nhất có thể.

Thời gian chạy chậm nhất có thể.

Thời gian chạy trên một bộ dữ liệu đầu vào 'điển hình' hoặc 'ngẫu nhiên'.

Thời gian chạy khi dữ liệu đã được sắp xếp.

Độ phức tạp trung bình mô tả hiệu suất của thuật toán trên một bộ dữ liệu đầu vào 'điển hình' hoặc 'ngẫu nhiên'. Nó thường là kết quả trung bình của độ phức tạp trên tất cả các bộ dữ liệu đầu vào có thể có với kích thước n, giả sử mỗi bộ dữ liệu có xác suất xuất hiện như nhau.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 27: Thuật toán nào trong số các thuật toán sắp xếp đơn giản sau đây có độ phức tạp thời gian tốt nhất trong trường hợp mảng đã được sắp xếp?

Bubble Sort

Selection Sort

Tất cả đều có O(n^2) trong trường hợp tốt nhất.

Không có thuật toán nào tốt hơn O(n log n) trong trường hợp tốt nhất.

Trong các thuật toán được liệt kê, Bubble Sort có thể dừng sớm nếu không có bất kỳ sự đổi chỗ nào trong một lần duyệt đầy đủ. Nếu mảng đã sắp xếp, nó chỉ cần một lần duyệt (O(n)) để kiểm tra và kết thúc. Selection Sort và các dạng đơn giản của Insertion Sort thường vẫn thực hiện O(n^2) hoặc gần O(n^2) phép tính ngay cả trên mảng đã sắp xếp.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 28: Xem xét đoạn mã giả sau:
```
function processMatrix(matrix):
rows = matrix.height
cols = matrix.width
sum = 0
for i from 0 to rows-1:
for j from 0 to cols-1:
sum = sum + matrix[i][j]
```
Nếu ma trận có kích thước m x n (rows = m, cols = n), độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(m + n)

O(max(m, n))

O(log(m*n))

O(m * n)

Đoạn mã có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy m lần (số hàng), vòng lặp trong chạy n lần (số cột). Tổng số lần thực hiện phép cộng là m * n. Độ phức tạp thời gian là O(m * n). Nếu ma trận vuông kích thước n x n, độ phức tạp là O(n^2). Câu hỏi không nói rõ m và n có quan hệ gì, nên biểu diễn chính xác nhất là O(m*n). Tuy nhiên, trong ngữ cảnh bài học thường xét trường hợp n là kích thước chung, nếu hiểu matrix là n x n thì là O(n^2), nếu hiểu là m x n thì là O(m*n). Dựa trên các phương án, O(m*n) hoặc O(n^2) (nếu m=n) là phù hợp nhất, các phương án khác không đúng.

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

Câu 29: Tại sao các hằng số và các thành phần bậc thấp hơn thường bị bỏ qua trong phân tích độ phức tạp Big O?

Vì chúng không đáng kể so với thành phần có bậc cao nhất khi n rất lớn.

Vì chúng chỉ ảnh hưởng đến trường hợp tốt nhất.

Vì chúng phụ thuộc vào tốc độ của máy tính cụ thể.

Vì chúng chỉ liên quan đến độ phức tạp không gian, không phải thời gian.

Ký hiệu Big O tập trung vào hành vi tiệm cận của thuật toán khi kích thước đầu vào (n) tiến tới vô cùng. Khi n rất lớn, thành phần có bậc cao nhất sẽ trở nên vượt trội so với các thành phần bậc thấp hơn và các hằng số. Việc bỏ qua chúng giúp đơn giản hóa phân tích mà vẫn giữ được thông tin quan trọng về tốc độ tăng trưởng chính của thuật toán.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 02

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

O(n)

O(log n)

O(n log n)

O(n^2)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Thuật toán tìm kiếm nhị phân hoạt động bằng cách liên tục chia đôi phạm vi tìm kiếm còn lại. Số lần chia đôi cần thiết để giảm phạm vi từ n xuống còn 1 là log₂(n). Do đó, số phép so sánh trong trường hợp xấu nhất (khi phần tử không có hoặc tìm thấy ở bước cuối cùng) tỷ lệ với log₂(n). Độ phức tạp là O(log n).

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 03

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, chúng ta thường quan tâm đến trường hợp nào nhất để đánh giá hiệu quả của nó với dữ liệu lớn?

Trường hợp tốt nhất (Best-case)

Trường hợp trung bình (Average-case)

Trường hợp xấu nhất (Worst-case)

Tất cả các trường hợp đều quan trọng như nhau

Trường hợp xấu nhất (worst-case) cho biết giới hạn trên về thời gian chạy của thuật toán, giúp chúng ta đảm bảo thuật toán sẽ không vượt quá một ngưỡng thời gian chấp nhận được ngay cả với dữ liệu khó nhất. Trường hợp tốt nhất (best-case) thường ít ý nghĩa thực tế vì hiếm khi xảy ra, còn trường hợp trung bình (average-case) khó phân tích và thường xấp xỉ trường hợp xấu nhất đối với nhiều thuật toán phổ biến.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 2: Cho đoạn mã giả sau:
```
sum = 0
for i from 1 to n:
sum = sum + i
```
Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là bao nhiêu?

O(1)

O(n)

O(n log n)

O(n^2)

Đoạn mã có một vòng lặp chạy từ 1 đến n. Số lần thực hiện các phép toán bên trong vòng lặp (phép gán, phép cộng) tỷ lệ thuận với giá trị của n. Do đó, độ phức tạp thời gian là O(n).

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 3: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Nếu phần tử cần tìm nằm ở vị trí cuối cùng của mảng, thì độ phức tạp thời gian của thuật toán trong trường hợp này là gì?

O(1)

O(log n)

O(n)

O(n^2)

Trong trường hợp xấu nhất (phần tử ở cuối mảng hoặc không có trong mảng), thuật toán tìm kiếm tuần tự phải duyệt qua toàn bộ n phần tử của mảng để thực hiện phép so sánh. Số phép so sánh tỷ lệ thuận với n, do đó độ phức tạp là O(n).

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 4: Thuật toán sắp xếp chọn (Selection Sort) hoạt động bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất trong phần chưa được sắp xếp của mảng và đưa nó về đúng vị trí. Tại sao thuật toán này có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất?

Thuật toán sử dụng hai vòng lặp lồng nhau, mỗi vòng lặp chạy gần n lần.

Thuật toán chỉ cần một vòng lặp duy nhất chạy n lần.

Thuật toán chia mảng thành hai nửa trong mỗi bước.

Số lượng hoán đổi luôn là hằng số.

Selection Sort có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n-1 lần. Vòng lặp trong (để tìm phần tử nhỏ nhất) chạy khoảng n lần (giảm dần từ n đến 1). Tổng số phép so sánh và hoán đổi xấp xỉ tỷ lệ với n*(n-1)/2, là một hàm bậc hai của n. Do đó, độ phức tạp là O(n^2).

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 5: Cho hai thuật toán: Thuật toán A có độ phức tạp O(n^2) và Thuật toán B có độ phức tạp O(n log n). Khi kích thước dữ liệu n rất lớn, nhận định nào sau đây là đúng về hiệu quả thời gian chạy của hai thuật toán?

Thuật toán A sẽ chạy nhanh hơn Thuật toán B.

Thuật toán B sẽ chạy nhanh hơn Thuật toán A.

Thời gian chạy của cả hai thuật toán là tương đương nhau.

Không thể so sánh hiệu quả chỉ dựa vào độ phức tạp O lớn.

Khi n rất lớn, hàm n log n tăng trưởng chậm hơn đáng kể so với hàm n^2. Do đó, thuật toán có độ phức tạp O(n log n) sẽ chạy nhanh hơn thuật toán có độ phức tạp O(n^2).

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 6: Độ phức tạp thời gian của thuật toán sắp xếp nổi bọt (Bubble Sort) trong trường hợp mảng đầu vào đã được sắp xếp hoàn toàn là gì?

O(n)

O(n log n)

O(n^2)

O(1)

Trong trường hợp tốt nhất (mảng đã sắp xếp), Bubble Sort có thể được tối ưu hóa bằng cách sử dụng một cờ (flag) để kiểm tra xem có bất kỳ cặp phần tử nào được hoán đổi trong một lần duyệt qua mảng hay không. Nếu không có hoán đổi nào xảy ra trong một lần duyệt, mảng đã được sắp xếp và thuật toán có thể dừng lại. Việc duyệt qua mảng một lần tốn O(n) thời gian.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 7: Cho đoạn mã giả sau:
```
count = 0
for i from 1 to n:
for j from 1 to n:
count = count + 1
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(log n)

O(n log n)

O(n^2)

Đoạn mã có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n lần, và với mỗi lần lặp của vòng lặp ngoài, vòng lặp trong cũng chạy n lần. Tổng số lần thực hiện phép cộng (và các phép toán liên quan) là n * n = n^2. Do đó, độ phức tạp thời gian là O(n^2).

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 8: Ký hiệu O lớn (Big O notation) mô tả khía cạnh nào của hiệu quả thuật toán?

Thời gian thực hiện chính xác tính bằng mili giây.

Tốc độ tăng trưởng của thời gian thực hiện khi kích thước đầu vào tăng lên.

Số lượng dòng mã trong thuật toán.

Lượng bộ nhớ RAM mà thuật toán sử dụng.

Ký hiệu O lớn mô tả tốc độ tăng trưởng của thời gian thực hiện (hoặc không gian bộ nhớ) của thuật toán khi kích thước đầu vào (n) tiến tới vô cùng. Nó bỏ qua các hằng số và các số hạng bậc thấp, chỉ tập trung vào số hạng chi phối sự tăng trưởng.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

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

Thời gian thực hiện tăng tuyến tính theo kích thước dữ liệu.

Thời gian thực hiện tăng theo hàm logarit của kích thước dữ liệu.

Thời gian thực hiện là không đổi, không phụ thuộc vào kích thước dữ liệu.

Thời gian thực hiện tăng theo bình phương của kích thước dữ liệu.

Độ phức tạp O(1) (hằng số) có nghĩa là thời gian thực hiện của thuật toán không phụ thuộc vào kích thước của dữ liệu đầu vào n. Số lượng phép toán thực hiện là cố định, bất kể n lớn hay nhỏ.

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 10: Giả sử thuật toán sắp xếp chọn (Selection Sort) mất 4 giây để sắp xếp một mảng có 2000 phần tử. Ước tính thời gian cần thiết để sắp xếp một mảng có 4000 phần tử bằng cùng thuật toán này là bao nhiêu?

8 giây

12 giây

10 giây

16 giây

Selection Sort có độ phức tạp O(n^2). Khi kích thước dữ liệu tăng từ n lên 2n (từ 2000 lên 4000), thời gian chạy sẽ tăng theo tỷ lệ (2n)^2 / n^2 = 4n^2 / n^2 = 4 lần. Do đó, thời gian ước tính sẽ là 4 giây * 4 = 16 giây.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 11: Cho đoạn mã giả sau:
```
result = 0
i = 1
while i < n: result = result + 1 i = i * 2 ``` Độ phức tạp thời gian của đoạn mã này theo ký hiệu O lớn là bao nhiêu?

O(n)

O(log n)

O(n log n)

O(n^2)

Trong vòng lặp `while`, biến `i` bắt đầu từ 1 và nhân đôi sau mỗi lần lặp (1, 2, 4, 8, ..., 2^k). Vòng lặp dừng khi `i` lớn hơn hoặc bằng `n`, tức là 2^k >= n. Số lần lặp k xấp xỉ log₂(n). Do đó, độ phức tạp thời gian là O(log n).

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 12: Khi so sánh thuật toán tìm kiếm tuần tự (Linear Search - O(n)) và thuật toán tìm kiếm nhị phân (Binary Search - O(log n)) trên một mảng đã sắp xếp, nhận định nào sau đây là đúng?

Tìm kiếm tuần tự luôn nhanh hơn tìm kiếm nhị phân.

Tìm kiếm nhị phân chỉ hiệu quả khi mảng chưa được sắp xếp.

Độ phức tạp của cả hai thuật toán là như nhau.

Tìm kiếm nhị phân hiệu quả hơn đáng kể so với tìm kiếm tuần tự khi n lớn (áp dụng cho mảng đã sắp xếp).

Tìm kiếm nhị phân (O(log n)) có tốc độ tăng trưởng thời gian chạy chậm hơn nhiều so với tìm kiếm tuần tự (O(n)) khi n lớn. Điều này có nghĩa là với mảng lớn, tìm kiếm nhị phân sẽ hiệu quả hơn đáng kể về mặt thời gian, miễn là mảng đã được sắp xếp.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 13: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from i to n:
// Thực hiện một phép toán cơ bản
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

Vòng lặp ngoài chạy từ i=1 đến n. Vòng lặp trong chạy từ j=i đến n. Số lần thực hiện phép toán bên trong là tổng của (n-1+1) + (n-2+1) + ... + (n-n+1) = n + (n-1) + ... + 1. Tổng này bằng n*(n+1)/2, là một hàm bậc hai của n. Do đó, độ phức tạp là O(n^2).

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 14: Tại sao các hằng số và các số hạng bậc thấp thường bị bỏ qua khi xác định độ phức tạp thời gian bằng ký hiệu O lớn?

Vì chúng không ảnh hưởng đáng kể đến tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào n rất lớn.

Vì chúng chỉ xuất hiện trong trường hợp tốt nhất của thuật toán.

Vì chúng chỉ liên quan đến không gian bộ nhớ, không phải thời gian.

Vì việc tính toán chúng là quá phức tạp.

Ký hiệu O lớn tập trung vào hành vi tiệm cận của thuật toán khi n tiến tới vô cùng. Đối với giá trị n rất lớn, số hạng có bậc cao nhất sẽ chi phối hoàn toàn tốc độ tăng trưởng của hàm thời gian, trong khi các hằng số và số hạng bậc thấp trở nên không đáng kể so với nó.

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 15: Một thuật toán xử lý dữ liệu mất 0.1 giây với n=1000. Nếu thuật toán này có độ phức tạp O(n), ước tính nó sẽ mất bao lâu để xử lý n=10000?

0.5 giây

10 giây

1 giây

0.01 giây

Với độ phức tạp O(n), thời gian chạy tỷ lệ thuận với n. Khi n tăng 10 lần (từ 1000 lên 10000), thời gian chạy cũng sẽ tăng khoảng 10 lần. Do đó, thời gian ước tính là 0.1 giây * 10 = 1 giây.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 16: Cho đoạn mã giả sau:
```
func(n):
if n <= 1: return 1 else: return func(n-1) + func(n-1) ``` (Đây là hàm tính số Fibonacci đệ quy không tối ưu). Độ phức tạp thời gian của hàm `func(n)` này là bao nhiêu?

O(n)

O(n^2)

O(n log n)

O(2^n)

Hàm này là một ví dụ cổ điển về đệ quy phân nhánh tạo ra nhiều lời gọi hàm trùng lặp. Số lượng lời gọi hàm tăng theo cấp số nhân với n. Cụ thể, độ phức tạp là O(2^n).

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 17: Thuật toán nào trong số các thuật toán sắp xếp sau đây thường có độ phức tạp thời gian là O(n^2) trong trường hợp xấu nhất?

Selection Sort

Merge Sort

Quick Sort

Binary Search (Đây là tìm kiếm, không phải sắp xếp)

Selection Sort và Bubble Sort đều là các thuật toán sắp xếp đơn giản với hai vòng lặp lồng nhau, dẫn đến độ phức tạp O(n^2) trong trường hợp xấu nhất (và cả trường hợp trung bình). Quick Sort và Merge Sort hiệu quả hơn với độ phức tạp trung bình là O(n log n).

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 18: Khi nói về độ phức tạp không gian (Space Complexity), O(n) nghĩa là gì?

Thời gian chạy tăng tuyến tính với n.

Lượng bộ nhớ phụ sử dụng tăng tuyến tính với n.

Thời gian chạy là hằng số.

Lượng bộ nhớ phụ sử dụng là hằng số.

Độ phức tạp không gian O(n) có nghĩa là lượng bộ nhớ phụ mà thuật toán sử dụng (ngoài không gian lưu trữ dữ liệu đầu vào) tỷ lệ thuận với kích thước đầu vào n. Tức là, nếu kích thước đầu vào tăng gấp đôi, lượng bộ nhớ phụ cũng tăng gấp đôi.

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 19: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to 100:
// Thực hiện một phép toán cơ bản
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n log n)

O(100n)

O(n^2)

Vòng lặp ngoài chạy n lần. Vòng lặp trong chạy 100 lần. Số lần thực hiện phép toán bên trong là n * 100. Vì 100 là một hằng số, chúng ta bỏ qua nó trong ký hiệu O lớn. Độ phức tạp thời gian là O(n).

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 20: Thuật toán nào sau đây là ví dụ điển hình của độ phức tạp thời gian O(1)?

Tìm kiếm một phần tử trong danh sách liên kết.

Sắp xếp một mảng bằng Bubble Sort.

Duyệt qua tất cả các phần tử của một mảng.

Truy cập một phần tử tại một chỉ số cho trước trong mảng.

Truy cập một phần tử tại một chỉ số cụ thể trong mảng (ví dụ: `array[5]`) là một thao tác có độ phức tạp O(1) vì thời gian thực hiện không phụ thuộc vào kích thước của mảng. Các thao tác khác như tìm kiếm, sắp xếp, thêm/xóa ở vị trí tùy ý thường có độ phức tạp cao hơn.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 21: Một thuật toán được mô tả là có độ phức tạp thời gian O(n^3). Nếu thuật toán này mất 1 giây để xử lý dữ liệu có kích thước n=100, thì ước tính nó sẽ mất bao lâu để xử lý dữ liệu có kích thước n=200?

8 giây

2 giây

4 giây

16 giây

Với độ phức tạp O(n^3), thời gian chạy tỷ lệ thuận với n^3. Khi n tăng gấp đôi (từ 100 lên 200), thời gian chạy sẽ tăng theo tỷ lệ (2n)^3 / n^3 = 8n^3 / n^3 = 8 lần. Do đó, thời gian ước tính là 1 giây * 8 = 8 giây.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 22: Điều gì xảy ra với hiệu quả của thuật toán sắp xếp nổi bọt (Bubble Sort - O(n^2)) khi kích thước dữ liệu đầu vào (n) tăng lên rất lớn?

Hiệu quả được cải thiện đáng kể.

Hiệu quả không thay đổi.

Hiệu quả giảm sút nhanh chóng.

Hiệu quả chỉ bị ảnh hưởng bởi các hằng số.

Với độ phức tạp O(n^2), thời gian chạy tăng theo bình phương của n. Điều này có nghĩa là khi n tăng lên rất lớn, thời gian chạy sẽ tăng lên rất nhanh chóng, làm cho thuật toán trở nên kém hiệu quả và không thực tế cho các tập dữ liệu lớn.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 23: Đâu là lợi ích chính của việc phân tích độ phức tạp thời gian của thuật toán?

Xác định thời gian chạy chính xác trên một máy tính cụ thể.

Dự đoán hiệu quả của thuật toán trên dữ liệu lớn và so sánh các thuật toán khác nhau.

Tìm lỗi cú pháp trong mã nguồn.

Giảm số lượng dòng mã của thuật toán.

Phân tích độ phức tạp giúp chúng ta hiểu được cách thời gian thực hiện (hoặc bộ nhớ) của thuật toán thay đổi khi kích thước dữ liệu đầu vào tăng lên. Điều này cho phép so sánh hiệu quả của các thuật toán khác nhau một cách độc lập với phần cứng cụ thể và dự đoán hiệu suất trên dữ liệu lớn.

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 24: Cho đoạn mã giả sau:
```
for i from 1 to n:
// Thực hiện một phép toán cơ bản
for j from 1 to m:
// Thực hiện một phép toán cơ bản
```
Với giả định n và m là hai kích thước đầu vào độc lập, độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n * m)

O(n^2)

O(max(n, m))

O(n + m)

Đoạn mã có hai vòng lặp tuần tự. Vòng lặp đầu tiên có độ phức tạp O(n). Vòng lặp thứ hai có độ phức tạp O(m). Tổng độ phức tạp là O(n + m).

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 25: Một thuật toán có độ phức tạp O(n log n). Nếu nó mất 0.5 giây để xử lý n=1000, ước tính thời gian xử lý cho n=20000 (tăng 20 lần) là bao nhiêu? (Gợi ý: log₂(1000) ≈ 10, log₂(20000) ≈ 14.3)

10 giây

14.3 giây

20 giây

5 giây

Thời gian chạy tỷ lệ với n log n. Tỷ lệ tăng thời gian khi n tăng từ 1000 lên 20000 là (20000 * log(20000)) / (1000 * log(1000)). Sử dụng log₂: (20000 * 14.3) / (1000 * 10) = (20 * 14.3) / 10 = 2 * 14.3 = 28.6 lần. Thời gian ước tính: 0.5 giây * 28.6 ≈ 14.3 giây.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 26: Đâu là yếu tố *không* được xem xét trực tiếp khi xác định độ phức tạp thời gian của thuật toán bằng ký hiệu O lớn?

Tốc độ xử lý của máy tính (GHz).

Kích thước dữ liệu đầu vào (n).

Số lượng vòng lặp lồng nhau.

Số lượng phép so sánh hoặc phép toán cơ bản tỷ lệ với n.

Tốc độ CPU cụ thể, ngôn ngữ lập trình được sử dụng, và chất lượng triển khai mã (ví dụ: hiệu quả của trình biên dịch) là các yếu tố ảnh hưởng đến thời gian chạy thực tế, nhưng chúng là các hằng số nhân hoặc cộng vào hàm thời gian và bị bỏ qua trong ký hiệu O lớn, vốn chỉ quan tâm đến tốc độ tăng trưởng theo n.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 27: Trong thuật toán sắp xếp chọn (Selection Sort), số lượng phép hoán đổi (swap) được thực hiện trong trường hợp xấu nhất là bao nhiêu?

O(n^2)

O(n)

O(log n)

O(1)

Selection Sort thực hiện chính xác n-1 lần hoán đổi, bất kể dữ liệu đầu vào như thế nào. Trong mỗi lần lặp của vòng lặp ngoài, nó tìm phần tử nhỏ nhất còn lại và hoán đổi nó vào vị trí đúng. Số lần tìm kiếm và so sánh là O(n^2), nhưng số lần hoán đổi chỉ là O(n).

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 28: Cho đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to i:
// Thực hiện một phép toán cơ bản
```
Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

Vòng lặp ngoài chạy từ i=1 đến n. Vòng lặp trong chạy từ j=1 đến i. Số lần thực hiện phép toán bên trong là tổng của 1 + 2 + 3 + ... + n. Tổng này bằng n*(n+1)/2, là một hàm bậc hai của n. Do đó, độ phức tạp là O(n^2).

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

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

Giảm thời gian thực hiện, đặc biệt khi xử lý dữ liệu lớn.

Làm cho mã nguồn dễ đọc và dễ hiểu hơn.

Giảm lượng bộ nhớ sử dụng bởi thuật toán.

Đảm bảo thuật toán luôn tìm ra đáp án chính xác.

Mục tiêu chính của việc tối ưu hóa thuật toán là làm cho nó chạy nhanh hơn, đặc biệt là với dữ liệu lớn. Điều này thường đạt được bằng cách giảm tốc độ tăng trưởng của thời gian chạy khi kích thước đầu vào tăng lên, tức là chuyển từ độ phức tạp bậc cao sang bậc thấp hơn (ví dụ: từ O(n^2) sang O(n log n) hoặc O(n)).

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 03

Câu 30: Giả sử bạn có một danh sách N tên học sinh cần sắp xếp theo thứ tự bảng chữ cái. Nếu N rất lớn (ví dụ: vài triệu), thuật toán nào sau đây có khả năng là lựa chọn tốt nhất về mặt hiệu quả thời gian?

Bubble Sort (O(n^2))

Selection Sort (O(n^2))

Linear Search (O(n))

Merge Sort (O(n log n))

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Đối với N rất lớn, cần sử dụng thuật toán sắp xếp có độ phức tạp hiệu quả như O(n log n). Bubble Sort và Selection Sort có độ phức tạp O(n^2), quá chậm cho dữ liệu lớn. Linear Search là thuật toán tìm kiếm, không phải sắp xếp. Merge Sort có độ phức tạp O(n log n) trong mọi trường hợp và là một lựa chọn hiệu quả cho dữ liệu lớn.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 04

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 1: Xét đoạn mã giả sau:
```
sum = 0
for i from 1 to n:
sum = sum + i
```
Đoạn mã này tính tổng các số từ 1 đến n. Độ phức tạp thời gian của đoạn mã này được biểu diễn bằng kí hiệu Big O nào?

O(1)

O(n)

O(n log n)

O(n^2)

Đoạn mã có một vòng lặp đơn chạy từ 1 đến n. Số lần thực hiện các phép tính bên trong vòng lặp (phép cộng, phép gán) tỉ lệ thuận với n. Do đó, độ phức tạp thời gian là O(n).

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 2: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Trong trường hợp xấu nhất, phần tử cần tìm không có trong mảng. Độ phức tạp thời gian trong trường hợp này là bao nhiêu?

O(1)

O(log n)

O(n)

O(n^2)

Trong trường hợp xấu nhất của tìm kiếm tuần tự, thuật toán phải kiểm tra từng phần tử trong mảng cho đến hết (hoặc tìm thấy ở vị trí cuối cùng). Số lần so sánh tỉ lệ thuận với kích thước mảng n. Do đó, độ phức tạp là O(n).

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 3: Một thuật toán có độ phức tạp thời gian là O(n^2). Nếu với đầu vào có kích thước n=1000, thuật toán chạy mất 1 giây, thì ước tính với đầu vào có kích thước n=2000, thuật toán sẽ chạy mất khoảng bao lâu?

0.5 giây

1 giây

2 giây

4 giây

Độ phức tạp O(n^2) nghĩa là thời gian chạy tỉ lệ với bình phương kích thước đầu vào. Khi n tăng gấp đôi (từ 1000 lên 2000), n^2 sẽ tăng gấp 2^2 = 4 lần. Do đó, thời gian chạy sẽ tăng khoảng 4 lần. Từ 1 giây lên khoảng 4 giây.

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 4: Thuật toán sắp xếp chọn (Selection Sort) trên một mảng có kích thước n. Độ phức tạp thời gian của thuật toán này là bao nhiêu trong trường hợp trung bình?

O(n)

O(n log n)

O(n^2)

O(log n)

Thuật toán sắp xếp chọn bao gồm hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n-1 lần, và vòng lặp trong tìm phần tử nhỏ nhất trong phần còn lại của mảng, chạy khoảng n, n-1, ..., 1 lần. Tổng số phép so sánh và hoán đổi xấp xỉ tỉ lệ với n*(n-1)/2, tức là O(n^2). Độ phức tạp của Selection Sort là O(n^2) cho mọi trường hợp (tốt nhất, trung bình, xấu nhất).

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 5: Xét đoạn mã giả sau:
```
count = 0
for i from 1 to n:
for j from 1 to n:
count = count + 1
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(n)

O(log n)

O(n log n)

O(n^2)

Đoạn mã có hai vòng lặp lồng nhau. Vòng lặp ngoài chạy n lần, và cho mỗi lần lặp của vòng ngoài, vòng lặp trong cũng chạy n lần. Tổng số lần thực hiện phép tính bên trong vòng lặp lồng nhau là n * n = n^2. Do đó, độ phức tạp là O(n^2).

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 6: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Trong trường hợp mảng đã được sắp xếp từ trước (trường hợp tốt nhất), độ phức tạp thời gian của thuật toán này là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(1)

Trong trường hợp tốt nhất (mảng đã sắp xếp), Bubble Sort có thể được tối ưu để dừng sớm nếu không có cặp nào được hoán đổi trong một lần duyệt toàn bộ mảng. Thuật toán vẫn cần duyệt qua mảng ít nhất một lần để kiểm tra điều này. Do đó, độ phức tạp trong trường hợp tốt nhất là O(n).

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 7: Khi phân tích độ phức tạp thời gian của thuật toán, kí hiệu Big O (O) thường được sử dụng để mô tả điều gì?

Thời gian thực hiện chính xác của thuật toán.

Độ phức tạp trong trường hợp tốt nhất.

Giới hạn dưới (lower bound) của tốc độ tăng trưởng thời gian.

Giới hạn trên (upper bound) của tốc độ tăng trưởng thời gian (thường là trường hợp xấu nhất).

Kí hiệu Big O mô tả giới hạn trên (upper bound) của tốc độ tăng trưởng thời gian thực hiện của thuật toán khi kích thước đầu vào n tiến tới vô cùng. Nó thường dùng để chỉ độ phức tạp trong trường hợp xấu nhất.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 8: Một thuật toán có độ phức tạp O(log n). Điều này có ý nghĩa gì về hiệu suất của thuật toán khi kích thước đầu vào n tăng lên rất lớn?

Thời gian chạy tăng tuyến tính với kích thước đầu vào.

Thời gian chạy tăng rất chậm khi kích thước đầu vào tăng.

Thời gian chạy tăng theo bình phương kích thước đầu vào.

Thời gian chạy là hằng số, không phụ thuộc vào kích thước đầu vào.

Độ phức tạp O(log n) biểu thị tốc độ tăng trưởng rất chậm so với n. Khi n tăng lên đáng kể, thời gian thực hiện của thuật toán chỉ tăng một lượng rất nhỏ. Đây là một trong những độ phức tạp hiệu quả nhất.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 9: Xét đoạn mã giả sau:
```
result = 0
for i from 1 to n:
for j from i to n:
result = result + 1
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

Vòng lặp ngoài chạy n lần. Vòng lặp trong chạy từ i đến n. Khi i=1, j chạy n lần. Khi i=2, j chạy n-1 lần. ... Khi i=n, j chạy 1 lần. Tổng số lần thực hiện phép tính là n + (n-1) + ... + 1 = n*(n+1)/2. Biểu thức này là một đa thức bậc 2 theo n. Do đó, độ phức tạp là O(n^2).

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

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

Thời gian chạy là hằng số, không phụ thuộc vào kích thước đầu vào.

Thời gian chạy tăng tuyến tính với kích thước đầu vào.

Thời gian chạy tăng theo logarit của kích thước đầu vào.

Đây là độ phức tạp kém hiệu quả nhất.

O(1) biểu thị độ phức tạp hằng số. Điều này có nghĩa là thời gian thực hiện của thuật toán không phụ thuộc vào kích thước của đầu vào (n). Ví dụ: truy cập một phần tử tại chỉ số cụ thể trong mảng.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 11: Thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có kích thước n. Độ phức tạp thời gian của thuật toán này là bao nhiêu?

O(n)

O(log n)

O(n^2)

O(n log n)

Tìm kiếm nhị phân hoạt động bằng cách liên tục chia đôi phạm vi tìm kiếm. Số lần chia đôi một phạm vi kích thước n cho đến khi còn 1 phần tử là log₂(n). Do đó, độ phức tạp thời gian là O(log n).

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 12: So sánh hai thuật toán A (độ phức tạp O(n)) và thuật toán B (độ phức tạp O(n^2)). Với kích thước đầu vào n đủ lớn, thuật toán nào sẽ có hiệu suất tốt hơn (chạy nhanh hơn)?

Thuật toán A

Thuật toán B

Hiệu suất như nhau

Không thể so sánh nếu không biết hằng số

Khi n đủ lớn, tốc độ tăng trưởng của n^2 nhanh hơn nhiều so với n. Do đó, thuật toán có độ phức tạp O(n) sẽ có thời gian chạy tăng chậm hơn và hiệu quả hơn so với thuật toán có độ phức tạp O(n^2).

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 13: Xét đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to 100:
// Thực hiện một phép tính O(1)
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(100)

O(n)

O(100n)

O(n^2)

Vòng lặp ngoài chạy n lần. Vòng lặp trong chạy 100 lần, một số hằng không phụ thuộc vào n. Tổng số lần thực hiện phép tính bên trong là n * 100. Vì 100 là hằng số, tốc độ tăng trưởng vẫn tỉ lệ tuyến tính với n. Do đó, độ phức tạp là O(n).

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 14: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Trong trường hợp xấu nhất (mảng sắp xếp ngược), độ phức tạp thời gian là bao nhiêu?

O(n)

O(log n)

O(n log n)

O(n^2)

Trong trường hợp xấu nhất của Bubble Sort, thuật toán cần thực hiện gần như tất cả các phép so sánh và hoán đổi có thể. Cấu trúc hai vòng lặp lồng nhau khiến số phép tính tỉ lệ với n^2. Do đó, độ phức tạp là O(n^2).

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 15: Khi phân tích độ phức tạp thời gian, tại sao chúng ta thường quan tâm đến trường hợp xấu nhất (worst-case) hơn là trường hợp tốt nhất (best-case)?

Trường hợp tốt nhất hiếm khi xảy ra.

Trường hợp tốt nhất thường có độ phức tạp O(1) nên không cần phân tích.

Trường hợp xấu nhất cung cấp giới hạn trên đáng tin cậy về hiệu suất.

Trường hợp trung bình khó xác định hơn.

Phân tích trường hợp xấu nhất giúp chúng ta biết được giới hạn trên về thời gian chạy của thuật toán, đảm bảo rằng thuật toán sẽ không vượt quá một ngưỡng thời gian nhất định ngay cả trong điều kiện bất lợi nhất. Điều này quan trọng cho việc đảm bảo hiệu suất đáng tin cậy của chương trình.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 16: Xét đoạn mã giả sau:
```
void process(int n) {
if (n <= 1) return; process(n/2); process(n/2); } ``` Đây là một hàm đệ quy. Độ phức tạp thời gian của hàm này là bao nhiêu?

O(log n)

O(n)

O(n log n)

O(2^n)

Mỗi lần gọi đệ quy, bài toán được chia thành hai bài toán con có kích thước bằng một nửa. Cây đệ quy có chiều sâu log₂(n). Tại mỗi cấp của cây, có 2^k nút (với k là độ sâu), và công việc thực hiện tại mỗi nút (ngoài lời gọi đệ quy) là hằng số (giả sử). Tuy nhiên, cấu trúc chia đôi và gọi lại hai lần cho kích thước n/2 dẫn đến một cây đệ quy mà tổng công việc tại mỗi cấp tăng lên. Đây là cấu trúc đệ quy thường thấy có độ phức tạp O(n). Ví dụ: duyệt cây nhị phân.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 17: Xét đoạn mã giả sau:
```
void do_something(int n) {
for i from 1 to n:
// Phép tính O(1)
for j from 1 to n:
// Phép tính O(1)
}
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(n^2)

O(n)

O(2n)

O(log n)

Đoạn mã có hai vòng lặp độc lập chạy tuần tự. Vòng lặp thứ nhất có độ phức tạp O(n). Vòng lặp thứ hai cũng có độ phức tạp O(n). Tổng độ phức tạp là O(n) + O(n). Trong kí hiệu Big O, ta chỉ giữ lại số hạng có bậc cao nhất. Ở đây cả hai đều là bậc 1, nên tổng là O(n).

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 18: Một thuật toán mất 5ms để xử lý dữ liệu có kích thước n=100. Nếu độ phức tạp của thuật toán là O(n log n), ước tính thời gian xử lý cho dữ liệu có kích thước n=10000 sẽ là bao nhiêu?

50 ms

500 ms

5 s

1 s

Thời gian chạy T(n) tỉ lệ với n log n, tức T(n) ≈ C * n log n. Với n₁=100, T(n₁)=5ms. Với n₂=10000, T(n₂)=?. Ta có T(n₂) / T(n₁) ≈ (n₂ log n₂) / (n₁ log n₁). log(100) = 2 (log cơ số 10, hoặc log cơ số 2 hay e cũng cho tỉ lệ tương tự). log(10000) = 4. T(10000) / 5ms ≈ (10000 * log(10000)) / (100 * log(100)) ≈ (10000 * 4) / (100 * 2) = 40000 / 200 = 200. T(10000) ≈ 5ms * 200 = 1000ms = 1 giây.

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 19: Trong phân tích độ phức tạp, 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?

Vì khi n rất lớn, số hạng bậc cao nhất chi phối tốc độ tăng trưởng.

Vì chúng không ảnh hưởng đến thời gian thực hiện thực tế.

Vì chúng chỉ quan trọng trong trường hợp tốt nhất.

Vì chúng làm cho việc tính toán phức tạp hơn.

Khi kích thước đầu vào n trở nên rất lớn, tốc độ tăng trưởng của các số hạng bậc cao sẽ chi phối hoàn toàn tốc độ tăng trưởng tổng thể của hàm thời gian. Các hằng số và số hạng bậc thấp trở nên không đáng kể so với số hạng bậc cao nhất. Kí hiệu Big O tập trung vào hành vi tiệm cận (asymptotic behavior) khi n → ∞.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 20: Xét đoạn mã giả sau:
```
for i from 1 to n:
for j from 1 to i*i:
// Phép tính O(1)
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(n)

O(n^2)

O(n^4)

O(n^3)

Vòng lặp ngoài chạy từ 1 đến n. Vòng lặp trong chạy từ 1 đến i*i. Tổng số lần thực hiện phép tính là ∑ (i*i) từ i=1 đến n. Tổng của i^2 từ 1 đến n là n(n+1)(2n+1)/6, là một đa thức bậc 3 theo n. Do đó, độ phức tạp là O(n^3).

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 21: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Trong trường hợp tốt nhất, phần tử cần tìm nằm ở vị trí đầu tiên. Độ phức tạp thời gian trong trường hợp này là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

Trong trường hợp tốt nhất, thuật toán tìm kiếm tuần tự chỉ cần thực hiện một phép so sánh để tìm thấy phần tử ngay ở vị trí đầu tiên. Số lượng phép tính là một hằng số, không phụ thuộc vào n. Do đó, độ phức tạp là O(1).

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 22: Một thuật toán có độ phức tạp O(n log n). Thuật toán này hiệu quả hơn thuật toán O(n^2) và kém hiệu quả hơn thuật toán O(n). Phát biểu này Đúng hay Sai?

Thứ tự tăng trưởng của các hàm là: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n). Do đó, O(n log n) hiệu quả hơn O(n^2) nhưng kém hiệu quả hơn O(n). Phát biểu này là Sai.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 23: Xét một đoạn mã thực hiện việc in tất cả các cặp phần tử khác nhau trong một mảng có kích thước n. Cấu trúc vòng lặp phổ biến để làm việc này là hai vòng lặp lồng nhau, mỗi vòng chạy từ 0 đến n-1, với điều kiện bỏ qua các cặp giống nhau hoặc đã xét. Độ phức tạp thời gian của đoạn mã này là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

Để in tất cả các cặp, ta thường dùng hai vòng lặp lồng nhau. Vòng ngoài chạy từ i=0 đến n-1. Vòng trong chạy từ j=i+1 đến n-1 để đảm bảo các cặp khác nhau và không lặp lại (ví dụ (a,b) và (b,a) nếu không có ràng buộc). Số lần thực hiện là tổng của (n-1), (n-2), ..., 1, tức là (n-1)n/2. Đây là đa thức bậc 2 theo n. Do đó, độ phức tạp là O(n^2).

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

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

Đánh giá hiệu quả của thuật toán khi kích thước đầu vào tăng lên.

Xác định thời gian chạy chính xác trên một máy tính cụ thể.

Tìm lỗi trong thuật toán.

Đảm bảo thuật toán luôn cho ra kết quả đúng.

Phân tích độ phức tạp giúp đánh giá hiệu quả của thuật toán, đặc biệt là khả năng mở rộng (scalability) khi kích thước đầu vào t??ng lên. Nó cho phép so sánh các thuật toán khác nhau để giải cùng một bài toán và lựa chọn thuật toán phù hợp nhất cho các yêu cầu về hiệu năng.

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 25: Xét đoạn mã giả sau:
```
void process_data(int n) {
for i from 1 to n:
// Phép tính O(1)
for j from 1 to n*n:
// Phép tính O(1)
}
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(n)

O(n^3)

O(n + n^2)

O(n^2)

Đoạn mã có hai vòng lặp độc lập. Vòng lặp thứ nhất chạy n lần (O(n)). Vòng lặp thứ hai chạy n*n lần (O(n^2)). Tổng độ phức tạp là O(n) + O(n^2). Khi n lớn, số hạng O(n^2) chi phối. Do đó, độ phức tạp tổng thể là O(n^2).

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 26: Thuật toán sắp xếp chèn (Insertion Sort) trên một mảng có kích thước n. Trong trường hợp xấu nhất (mảng sắp xếp ngược), độ phức tạp thời gian của thuật toán này là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(log n)

Trong Insertion Sort, ở mỗi bước, một phần tử được chèn vào vị trí đúng trong phần đã sắp xếp của mảng. Trong trường hợp xấu nhất (mảng sắp xếp ngược), mỗi phần tử mới được chèn đều phải so sánh và dịch chuyển qua tất cả các phần tử đã sắp xếp trước đó. Điều này dẫn đến số phép tính tỉ lệ với 1 + 2 + ... + (n-1) = n(n-1)/2, tức là O(n^2).

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 27: Xét đoạn mã giả sau:
```
void process_recursive(int n) {
if (n <= 0) return; // Phép tính O(1) process_recursive(n - 1); } ``` Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(log n)

O(n)

O(n^2)

O(2^n)

Hàm đệ quy này thực hiện một phép tính O(1) và sau đó gọi đệ quy chính nó với đầu vào n-1. Quá trình này lặp lại n lần cho đến khi n bằng 0. Số lần thực hiện phép tính O(1) tỉ lệ tuyến tính với n. Do đó, độ phức tạp là O(n).

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 28: Khi so sánh hai 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), điều gì xảy ra khi kích thước đầu vào n tăng từ nhỏ đến rất lớn?

Thuật toán A nhanh hơn B khi n đủ lớn.

Thuật toán B nhanh hơn A khi n đủ lớn.

Cả hai thuật toán có hiệu suất tương đương khi n rất lớn.

Không thể so sánh hiệu suất chỉ dựa vào độ phức tạp Big O.

Với n nhỏ, hằng số ẩn trong kí hiệu Big O có thể khiến thuật toán O(n^2) nhanh hơn hoặc bằng O(n log n). Tuy nhiên, khi n tăng lên rất lớn, tốc độ tăng trưởng n^2 sẽ nhanh hơn đáng kể so với n log n. Do đó, thuật toán O(n log n) sẽ nhanh hơn thuật toán O(n^2) khi n đủ lớn.

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 29: Xét đoạn mã giả sau:
```
for i from 1 to 100:
for j from 1 to n:
// Phép tính O(1)
```
Đoạn mã này có độ phức tạp thời gian là bao nhiêu?

O(100)

O(n)

O(100n)

O(n^2)

Vòng lặp ngoài chạy 100 lần (hằng số). Vòng lặp trong chạy n lần. Tổng số lần thực hiện phép tính bên trong là 100 * n. Tốc độ tăng trưởng tỉ lệ tuyến tính với n. Do đó, độ phức tạp là O(n).

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 04

Câu 30: Một thuật toán xử lý dữ liệu có kích thước n. Người ta đo được thời gian chạy T(n) và vẽ đồ thị T(n) theo n. Nếu đồ thị có dạng một đường thẳng đi qua gốc tọa độ (hoặc gần như vậy khi n lớn), thì độ phức tạp thời gian của thuật toán có khả năng là gì?

O(1)

O(log n)

O(n)

O(n^2)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Đồ thị thời gian chạy là đường thẳng tỉ lệ với n cho thấy thời gian chạy tăng tuyến tính với kích thước đầu vào. Điều này tương ứng với độ phức tạp thời gian O(n).

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 05

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 1: Cho đoạn mã giả sau:
```
function TinhTong(n):
tong = 0
for i from 1 to n:
tong = tong + i
return tong
```
Độ phức tạp thời gian của hàm `TinhTong(n)` theo ký hiệu O lớn là bao nhiêu?

O(1)

O(n)

O(n log n)

O(n^2)

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 2: Khi phân tích độ phức tạp thời gian của một thuật toán, ký hiệu O lớn (Big O notation) thường mô tả trường hợp nào?

Trường hợp tốt nhất (best case)

Trường hợp trung bình (average case)

Trường hợp xấu nhất (worst case)

Cả ba trường hợp trên

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 3: Cho đoạn mã giả sau:
```
function TimPhanTu(mang, gia_tri):
for i from 0 to length(mang) - 1:
if mang[i] == gia_tri:
return i
return -1
```
Nếu mảng `mang` có kích thước `n` và phần tử `gia_tri` nằm ở vị trí cuối cùng của mảng, độ phức tạp thời gian là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 4: Thuật toán tìm kiếm nhị phân (Binary Search) trên một mảng đã được sắp xếp có độ phức tạp thời gian trong trường hợp xấu nhất là O(log n). Điều này có ý nghĩa gì khi kích thước dữ liệu `n` tăng lên?

Thời gian thực hiện tăng tuyến tính với `n`.

Thời gian thực hiện tăng theo bình phương của `n`.

Thời gian thực hiện tăng rất nhanh khi `n` lớn.

Thời gian thực hiện tăng rất chậm so với sự tăng của `n`.

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 5: Cho đoạn mã giả sau:
```
function XuLyDuLieu(n):
for i from 1 to n:
for j from 1 to n:
print(i * j)
```
Độ phức tạp thời gian của hàm `XuLyDuLieu(n)` là bao nhiêu?

O(n)

O(n log n)

O(log n)

O(n^2)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 6: Nếu một thuật toán có độ phức tạp thời gian là O(n^2) và mất 1 giây để xử lý 1000 phần tử, ước tính thời gian cần thiết để xử lý 10000 phần tử là bao nhiêu?

10 giây

100 giây

1000 giây

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 7: 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à O(n^2). Điều này có nghĩa là gì về hiệu suất của thuật toán này với dữ liệu lớn?

Thời gian thực hiện tăng rất nhanh khi kích thước dữ liệu tăng, không phù hợp với tập dữ liệu rất lớn.

Thời gian thực hiện tăng chậm, phù hợp với mọi kích thước dữ liệu.

Thời gian thực hiện là hằng số, không phụ thuộc vào kích thước dữ liệu.

Thời gian thực hiện chỉ tăng tuyến tính với kích thước dữ liệu.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 8: Cho đoạn mã giả sau:
```
function HamKyBi(n):
i = 1
while i < n: print(i) i = i * 2 ``` Độ phức tạp thời gian của hàm `HamKyBi(n)` là bao nhiêu?

O(n)

O(n^2)

O(log n)

O(1)

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 9: Khi so sánh thuật toán tìm kiếm tuần tự (Linear Search) với tìm kiếm nhị phân (Binary Search) trên một mảng đã sắp xếp có kích thước `n`, nhận định nào sau đây là đúng về độ phức tạp thời gian trong trường hợp xấu nhất?

Tìm kiếm tuần tự (O(n)) chậm hơn tìm kiếm nhị phân (O(log n)) đáng kể khi `n` lớn.

Tìm kiếm tuần tự (O(n)) nhanh hơn tìm kiếm nhị phân (O(log n)) khi `n` lớn.

Hai thuật toán có độ phức tạp tương đương nhau khi `n` lớn.

Độ phức tạp của tìm kiếm nhị phân phụ thuộc vào việc mảng có chứa số nguyên hay không.

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 10: Một thuật toán thực hiện các bước sau:
1. Duyệt qua toàn bộ mảng kích thước `n` một lần để tìm giá trị lớn nhất (O(n)).
2. Thực hiện 10 phép tính số học cố định (không phụ thuộc vào `n`) (O(1)).
Độ phức tạp thời gian tổng thể của thuật toán này là bao nhiêu?

O(1)

O(n)

O(n + 10)

O(10n)

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 11: Cho đoạn mã giả sau:
```
function ProcessData(A, B):
n = length(A)
m = length(B)
for i from 0 to n-1:
for j from 0 to m-1:
print(A[i] + B[j])
```
Nếu `n` rất lớn và `m` rất lớn, độ phức tạp thời gian của hàm `ProcessData(A, B)` là bao nhiêu?

O(n + m)

O(max(n, m))

O(n)

O(n * m)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 12: Khi phân tích độ phức tạp của một thuật toán, hằng số và các hệ số bậc thấp thường bị bỏ qua trong ký hiệu O lớn. Ví dụ, O(2n^2 + 5n + 3) được rút gọn thành O(n^2). Tại sao lại làm như vậy?

Để tập trung vào tốc độ tăng trưởng của thời gian thực hiện khi kích thước đầu vào rất lớn.

Để làm cho việc tính toán đơn giản hơn.

Vì các hằng số và hệ số bậc thấp không ảnh hưởng đến thời gian thực hiện.

Vì chúng chỉ quan trọng trong trường hợp tốt nhất.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 13: 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 tốt nhất (mảng đã sắp xếp) là O(n). Tại sao lại như vậy?

Vì thuật toán chỉ cần một vòng lặp để kiểm tra.

Vì thuật toán có thể phát hiện mảng đã sắp xếp sau một lần duyệt đầy đủ mà không cần đổi chỗ nào.

Vì thuật toán chỉ thực hiện một phép so sánh.

Vì độ phức tạp O(n) là tối ưu cho mọi thuật toán sắp xếp.

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 14: Cho đoạn mã giả:
```
function Example(n):
count = 0
for i from 1 to n:
for j from 1 to i:
count = count + 1
return count
```
Độ phức tạp thời gian của hàm `Example(n)` là bao nhiêu?

O(n)

O(n log n)

O(log n)

O(n^2)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 15: Một thuật toán có độ phức tạp O(log n). Nếu với n = 1000, thuật toán chạy mất 10ms, thì ước tính với n = 1,000,000 (gấp 1000 lần), thuật toán sẽ chạy mất khoảng bao lâu? (Biết log2(1000) ≈ 10, log2(1000000) ≈ 20)

Khoảng 20ms

Khoảng 100ms

Khoảng 1000ms

Khoảng 10000ms

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 16: Thuật toán nào sau đây thường có độ phức tạp thời gian là O(1)?

Tìm kiếm một phần tử trong danh sách liên kết.

Sắp xếp một mảng bằng Bubble Sort.

Truy cập một phần tử tại vị trí bất kỳ trong mảng bằng chỉ số.

Duyệt qua tất cả các phần tử trong một danh sách.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 17: Khi phân tích một thuật toán đệ quy, độ phức tạp thời gian thường được biểu diễn bằng gì?

Hệ thức truy hồi (Recurrence Relation)

Công thức đóng (Closed Form)

Đồ thị hàm số

Ma trận kề

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 18: Cho đoạn mã giả sau:
```
function AnotherExample(n):
for i from 1 to n:
j = 1
while j <= n: print(i * j) j = j * 2 ``` Độ phức tạp thời gian của hàm `AnotherExample(n)` là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O((log n)^2)

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 19: Thuật toán nào sau đây có độ phức tạp thời gian điển hình là O(n log n)?

Tìm kiếm tuần tự (Linear Search)

Sắp xếp chọn (Selection Sort)

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp trộn (Merge Sort)

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 20: Giả sử bạn cần chọn một thuật toán để xử lý một tập dữ liệu có kích thước N rất lớn (ví dụ: N = 1 tỷ). Thuật toán nào có độ phức tạp thời gian *ít phù hợp nhất*?

O(N^2)

O(N log N)

O(N)

O(log N)

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 21: Cho đoạn mã giả sau:
```
function WeirdFunction(n):
if n <= 1: return 1 else: return WeirdFunction(n/2) + WeirdFunction(n/2) ``` Độ phức tạp thời gian của hàm đệ quy `WeirdFunction(n)` là bao nhiêu? (Giả sử phép chia `/` là phép chia nguyên)

O(log n)

O(n)

O(n log n)

O(n)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 22: Khái niệm nào sau đây mô tả tốc độ tăng trưởng của thời gian thực hiện thuật toán khi kích thước đầu vào tăng lên?

Độ chính xác của thuật toán

Độ đo bộ nhớ của thuật toán

Độ phức tạp thời gian của thuật toán

Tính đúng đắn của thuật toán

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 23: Cho đoạn mã giả sau:
```
function ProcessMatrix(matrix, n):
# matrix là ma trận vuông n x n
sum = 0
for i from 0 to n-1:
sum = sum + matrix[i][i] # Duyệt đường chéo chính
return sum
```
Độ phức tạp thời gian của hàm `ProcessMatrix(matrix, n)` là bao nhiêu?

O(n^2)

O(n)

O(1)

O(log n)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 24: Trong phân tích độ phức tạp, O(n) được gọi là độ phức tạp gì?

Tuyến tính (Linear)

Logarit (Logarithmic)

Hằng số (Constant)

Bình phương (Quadratic)

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 25: Tại sao việc xác định độ phức tạp thời gian của thuật toán lại quan trọng trong thực tế?

Chỉ để biết thuật toán có chạy được hay không.

Để biết chính xác thời gian chạy trên một máy tính cụ thể.

Để làm cho mã nguồn ngắn gọn hơn.

Để dự đoán hiệu suất của thuật toán với các tập dữ liệu lớn và so sánh hiệu quả giữa các thuật toán khác nhau.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 26: Cho đoạn mã giả sau:
```
function AnalyzeData(n):
total = 0
for i from 1 to 100:
total = total + i
for j from 1 to n:
total = total + j*2
return total
```
Độ phức tạp thời gian của hàm `AnalyzeData(n)` là bao nhiêu?

O(100)

O(n + 100)

O(n)

O(n^2)

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 27: Trong các độ phức tạp sau, độ phức tạp nào thể hiện hiệu suất tốt nhất (chạy nhanh nhất với `n` đủ lớn)?

O(log n)

O(n)

O(n log n)

O(n^2)

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 28: Khi một thuật toán chứa một vòng lặp `for` chạy từ 1 đến `n` và bên trong vòng lặp đó có một lời gọi hàm khác có độ phức tạp O(log n), thì độ phức tạp tổng thể của thuật toán là bao nhiêu?

O(log n)

O(n)

O(n^2)

O(n log n)

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 29: Cho đoạn mã giả:
```
function CompareArrays(A, B):
n = length(A)
m = length(B)
if n != m:
return False
for i from 0 to n-1:
if A[i] != B[i]:
return False
return True
```
Giả sử `n` và `m` có cùng độ lớn. Độ phức tạp thời gian của hàm `CompareArrays` trong trường hợp xấu nhất (hai mảng giống hệt nhau) là bao nhiêu?

O(1)

O(n)

O(n^2)

O(n log n)

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 05

Câu 30: Trong các yếu tố sau, yếu tố nào *không* ảnh hưởng trực tiếp đến độ phức tạp thời gian lý thuyết (Big O) của một thuật toán?

Kích thước của dữ liệu đầu vào (n).

Cấu trúc của các vòng lặp và lời gọi hàm.

Ngôn ngữ lập trình được sử dụng để cài đặt thuật toán.

Số lượng các phép toán cơ bản (so sánh, gán, tính toán) thực hiện trong trường hợp xấu nhất.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 06

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, ký hiệu Big O (ví dụ: O(n), O(n^2), O(log n)) chủ yếu mô tả điều gì?

Thời gian chạy chính xác của thuật toán trên một máy tính cụ thể.

Số dòng mã lệnh trong thuật toán.

Sự tăng trưởng của thời gian chạy khi kích thước dữ liệu đầu vào (n) tăng lên rất lớn.

Lượng bộ nhớ mà thuật toán sử dụng.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 2: Cho đoạn mã giả sau:
```
function ProcessArray(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 hàm `ProcessArray` là bao nhiêu?

O(1)

O(n)

O(n^2)

O(log n)

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 3: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Trong trường hợp xấu nhất, độ phức tạp thời gian của thuật toán này là bao nhiêu?

O(1)

O(n)

O(n^2)

O(n log n)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 4: Cho đoạn mã giả sau:
```
function AnalyzeData(data, n):
count = 0
for i from 0 to n-1:
for j from 0 to n-1:
if data[i] == data[j]:
count = count + 1
return count
```
Độ phức tạp thời gian của hàm `AnalyzeData` là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 5: Đối với các thuật toán sắp xếp đơn giản như Sắp xếp chọn (Selection Sort) hoặc Sắp xếp nổi bọt (Bubble Sort), độ phức tạp thời gian trong trường hợp xấu nhất và trung bình thường là bao nhiêu?

O(n)

O(log n)

O(n^2)

O(n log n)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

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

Thời gian thực hiện không phụ thuộc vào kích thước dữ liệu đầu vào n.

Thời gian thực hiện tăng tuyến tính theo kích thước dữ liệu đầu vào n.

Thời gian thực hiện tăng theo bình phương của kích thước dữ liệu đầu vào n.

Thời gian thực hiện tăng theo logarit của kích thước dữ liệu đầu vào n.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 7: 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ố hạng có bậc cao nhất và bỏ qua các hằng số cùng các số hạng bậc thấp hơn?

Vì các số hạng bậc thấp hơn không ảnh hưởng đến thời gian chạy.

Vì các hằng số luôn bằng 1 trong phân tích Big O.

Vì chúng ta chỉ quan tâm đến trường hợp tốt nhất của thuật toán.

Vì khi n đủ lớn, sự tăng trưởng của thời gian chạy chủ yếu được quyết định bởi số hạng có bậc cao nhất.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 8: Hai thuật toán A và B cùng giải quyết một vấn đề. Thuật toán A có độ phức tạp O(n^2), thuật toán B có độ phức tạp O(n log n). Khi kích thước dữ liệu đầu vào n rất lớn, thuật toán nào có xu hướng chạy nhanh hơn?

Thuật toán A.

Thuật toán B.

Cả hai thuật toán chạy với tốc độ tương đương.

Không thể xác định chỉ dựa vào độ phức tạp Big O.

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 9: Cho đoạn mã giả sau:
```
function Example(n):
i = 1
while i < n: print(i) i = i * 2 ``` Độ phức tạp thời gian của hàm `Example` là bao nhiêu?

O(n)

O(n^2)

O(1)

O(log n)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

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

O(n)

O(n^2)

O(1)

O(log n)

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 11: Cho đoạn mã giả sau:
```
function Combine(arr1, n1, arr2, n2):
// arr1 có kích thước n1, arr2 có kích thước n2
sum1 = 0
for i from 0 to n1-1:
sum1 = sum1 + arr1[i] // Vòng lặp 1

sum2 = 0
for j from 0 to n2-1:
sum2 = sum2 + arr2[j] // Vòng lặp 2

return sum1 + sum2
```
Giả sử n1 và n2 có cùng độ lớn, ký hiệu là n (n1 ≈ n2 ≈ n). Độ phức tạp thời gian của hàm `Combine` là bao nhiêu?

O(n^2)

O(n)

O(log n)

O(1)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 12: Tại sao việc xác định độ phức tạp thời gian của thuật toán lại quan trọng đối với lập trình viên?

Để biết thuật toán có sử dụng ngôn ngữ lập trình hiện đại hay không.

Để biết thuật toán có thể giải quyết được mọi bài toán hay không.

Để đá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.

Để kiểm tra xem thuật toán có bị lỗi cú pháp hay không.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 13: Cho đoạn mã giả sau:
```
function PrintPairs(arr, n):
for i from 0 to n-1:
for j from i to n-1:
print(arr[i], arr[j])
```
Độ phức tạp thời gian của hàm `PrintPairs` là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 14: Nếu một thuật toán có độ phức tạp O(n), và nó mất 100 mili giây để xử lý dữ liệu có kích thước n=1000. Ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=10000 là bao nhiêu?

100 mili giây

1000 mili giây (1 giây)

10000 mili giây (10 giây)

100000 mili giây (100 giây)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 15: Giả sử một thuật toán có độ phức tạp O(n^2). Nếu nó mất 1 giây để xử lý dữ liệu có kích thước n=1000. Ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=2000 là bao nhiêu?

1 giây

2 giây

3 giây

4 giây

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 16: Trong phân tích độ phức tạp, 'trường hợp tốt nhất' (best case) của một thuật toán là gì?

Tình huống dữ liệu đầu vào khiến thuật toán thực hiện số phép tính ít nhất.

Tình huống dữ liệu đầu vào khiến thuật toán thực hiện số phép tính nhiều nhất.

Thời gian chạy trung bình của thuật toán trên nhiều bộ dữ liệu khác nhau.

Thời gian chạy của thuật toán trên máy tính nhanh nhất.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 17: Cho đoạn mã giả sau:
```
function CheckConstant(arr, n):
if n > 0:
print(arr[0])
// Các thao tác khác không phụ thuộc vào n
result = 1 + 2
return result
```
Độ phức tạp thời gian của hàm `CheckConstant` là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 18: Đối với thuật toán tìm kiếm tuần tự (Linear Search) trên mảng kích thước n, trường hợp tốt nhất xảy ra khi nào và độ phức tạp thời gian trong trường hợp đó là bao nhiêu?

Phần tử cần tìm không có trong mảng, O(n).

Phần tử cần tìm ở vị trí cuối cùng, O(n).

Phần tử cần tìm ở vị trí đầu tiên, O(1).

Mảng đã được sắp xếp, O(log n).

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 19: Khi một thuật toán bao gồm nhiều phần có độ phức tạp khác nhau (ví dụ: một phần O(n) và một phần O(n^2) thực hiện nối tiếp nhau), độ phức tạp tổng thể của thuật toán được xác định bởi phần nào?

Phần có độ phức tạp thấp nhất.

Phần có độ phức tạp cao nhất.

Trung bình cộng độ phức tạp của các phần.

Tích độ phức tạp của các phần.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 20: Cho đoạn mã giả sau:
```
function ProcessMatrix(matrix, n):
// matrix là ma trận vuông n x n
total = 0
for i from 0 to n-1:
for j from 0 to n-1:
total = total + matrix[i][j]
return total
```
Độ phức tạp thời gian của hàm `ProcessMatrix` khi duyệt qua tất cả các phần tử của ma trận n x n là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 21: Thuật toán nào trong các lựa chọn sau đây thường có độ phức tạp thời gian tốt nhất (nhanh nhất) đối với các bộ dữ liệu lớn?

O(log n)

O(n)

O(n log n)

O(n^2)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 22: Cho đoạn mã giả sau:
```
function PartialSum(arr, n):
sum = 0
for i from 0 to min(n-1, 100):
sum = sum + arr[i]
return sum
```
Độ phức tạp thời gian của hàm `PartialSum` là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 23: Giả sử bạn có một thuật toán O(n log n). Nếu nó xử lý n=1000 phần tử trong 10ms, ước tính thời gian để xử lý n=10000 phần tử là bao nhiêu? (Lưu ý: log(1000) ≈ 10, log(10000) ≈ 13.3)

Khoảng 100 ms

Khoảng 133 ms

Khoảng 1000 ms

Khoảng 1330 ms (1.33 giây)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 24: Trong phân tích độ phức tạp, 'trường hợp xấu nhất' (worst case) của một thuật toán là gì?

Tình huống dữ liệu đầu vào khiến thuật toán thực hiện số phép tính ít nhất.

Tình huống dữ liệu đầu vào khiến thuật toán thực hiện số phép tính nhiều nhất.

Thời gian chạy trung bình của thuật toán trên nhiều bộ dữ liệu khác nhau.

Thời gian chạy của thuật toán trên máy tính chậm nhất.

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 25: Cho đoạn mã giả sau:
```
function ExampleNested(n):
count = 0
for i from 1 to n:
for j from 1 to n:
for k from 1 to n:
count = count + 1
return count
```
Độ phức tạp thời gian của hàm `ExampleNested` là bao nhiêu?

O(n)

O(n^2)

O(n log n)

O(n^3)

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 26: Khi so sánh hiệu suất của hai thuật toán có độ phức tạp O(n log n) và O(n^2), điều gì là đúng khi kích thước dữ liệu n tăng lên?

Thuật toán O(n log n) sẽ nhanh hơn đáng kể so với O(n^2).

Thuật toán O(n^2) sẽ nhanh hơn đáng kể so với O(n log n).

Hai thuật toán sẽ có hiệu suất tương đương.

Hiệu suất chỉ phụ thuộc vào hằng số ẩn trong ký hiệu Big O.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 27: Cho đoạn mã giả sau:
```
function ProcessEveryOther(arr, n):
sum = 0
for i from 0 to n-1 step 2:
sum = sum + arr[i]
return sum
```
Độ phức tạp thời gian của hàm `ProcessEveryOther` là bao nhiêu?

O(1)

O(n)

O(log n)

O(n^2)

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

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

Tìm kiếm tuần tự.

Các thao tác cơ bản trên mảng cố định.

Các thuật toán có ba vòng lặp lồng nhau.

Các thuật toán sắp xếp hiệu quả như Merge Sort (Sắp xếp trộn) hoặc Quick Sort (Sắp xếp nhanh).

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 29: Nếu một thuật toán có độ phức tạp O(n^3) và mất 8 giây để xử lý dữ liệu có kích thước n=100. Ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=200 là bao nhiêu?

64 giây

16 giây

32 giây

128 giây

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 06

Câu 30: Trong phân tích độ phức tạp thời gian, 'trường hợp trung bình' (average case) của một thuật toán là gì?

Tình huống dữ liệu đầu vào khiến thuật toán thực hiện số phép tính ít nhất.

Tình huống dữ liệu đầu vào khiến thuật toán thực hiện số phép tính nhiều nhất.

Thời gian chạy kỳ vọng của thuật toán trên tất cả các bộ dữ liệu đầu vào có thể xảy ra, tính trung bình.

Thời gian chạy của thuật toán khi n là số nguyên tố.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 07

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán sử dụng ký hiệu O lớn (Big O), điều gì là mục đích chính của việc bỏ qua các hằng số nhân và các số hạng bậc thấp hơn?

Giúp làm cho công thức tính toán đơn giản hơn.

Chúng chỉ ảnh hưởng đến thuật toán khi kích thước đầu vào nhỏ.

Chúng không bao giờ ảnh hưởng đến hiệu suất thực tế của thuật toán.

Tập trung vào tốc độ tăng trưởng của thời gian thực hiện khi kích thước đầu vào rất lớn.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

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

O(1)

O(log n)

O(n)

O(n^2)

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

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

O(n)

O(n log n)

O(n^3)

O(n^2)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

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

O(n)

O(n^2)

O(n log n)

O(n^3)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 5: Xét đoạn mã giả sau:
```
function example4(n):
if n <= 1: return print('Hello') example4(n / 2) ``` Giả sử phép chia `n/2` làm tròn xuống. Độ phức tạp thời gian của hàm đệ quy `example4(n)` dựa trên số lần gọi hàm đệ quy là gì?

O(log n)

O(n)

O(n log n)

O(n^2)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 6: Một thuật toán có độ phức tạp thời gian O(n log n). Nếu thuật toán này xử lý dữ liệu có kích thước n=1000 trong khoảng 0.1 giây, ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=10000 sẽ là bao nhiêu?

Khoảng 1 giây

Khoảng 10 giây

Khoảng 1.3 - 1.4 giây

Khoảng 0.5 giây

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 7: Thuật toán nào sau đây *thường* có độ phức tạp thời gian tốt nhất trong trường hợp xấu nhất để tìm kiếm một phần tử trong một mảng đã được sắp xếp?

Tìm kiếm tuần tự (Linear Search)

Tìm kiếm nhị phân (Binary Search)

Tìm kiếm nội suy (Interpolation Search)

Cả A và B đều có độ phức tạp như nhau

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 8: Thuật toán nào sau đây *thường* có độ phức tạp thời gian O(n^2) trong trường hợp xấu nhất để sắp xếp một mảng?

Sắp xếp Chọn (Selection Sort)

Sắp xếp Nhanh (Quick Sort)

Sắp xếp Trộn (Merge Sort)

Sắp xếp Vun đống (Heap Sort)

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 9: Xét đoạn mã giả sau:
```
function example5(n):
if n <= 0: return for i from 1 to n: print('Step') example5(n - 1) ``` Độ phức tạp thời gian của hàm đệ quy `example5(n)` dựa trên số lần in 'Step' là gì?

O(n)

O(log n)

O(n log n)

O(n^2)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 10: Thuật toán nào có độ phức tạp thời gian O(1)?

Truy cập một phần tử tại chỉ mục bất kỳ trong mảng.

Tìm kiếm một phần tử trong danh sách liên kết đơn.

Sắp xếp một danh sách.

Tìm kiếm phần tử lớn nhất trong mảng chưa sắp xếp.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 11: Khi so sánh 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), điều gì xảy ra khi kích thước đầu vào n trở nên rất lớn?

Thuật toán B sẽ luôn nhanh hơn thuật toán A.

Thời gian thực hiện của thuật toán B sẽ tăng nhanh hơn nhiều so với thuật toán A.

Cả hai thuật toán sẽ có thời gian thực hiện tương đương nhau.

Thuật toán A sẽ không thể xử lý được đầu vào lớn.

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 12: Xét đoạn mã giả sau:
```
function example6(n):
sum = 0
i = 1
while i < n: sum = sum + i i = i * 2 return sum ``` Độ phức tạp thời gian của hàm `example6(n)` là gì?

O(log n)

O(n)

O(n log n)

O(n^2)

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 13: Thuật toán sắp xếp nào sau đây có độ phức tạp thời gian O(n log n) trong trường hợp xấu nhất?

Sắp xếp Nổi bọt (Bubble Sort)

Sắp xếp Chèn (Insertion Sort)

Sắp xếp Trộn (Merge Sort)

Sắp xếp Chọn (Selection Sort)

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 14: Giả sử một thuật toán có độ phức tạp thời gian là O(n³). Nếu thuật toán này mất 1 giây để xử lý dữ liệu có kích thước n=100, ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n=200 là bao nhiêu?

2 giây

4 giây

6 giây

8 giây

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

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

Là kịch bản đầu vào khiến thuật toán thực hiện ít thao tác nhất.

Là kịch bản đầu vào khiến thuật toán thực hiện nhiều thao tác nhất.

Là kịch bản đầu vào ngẫu nhiên điển hình.

Là kịch bản chỉ xảy ra với đầu vào kích thước nhỏ.

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 16: Độ phức tạp thời gian của thuật toán Sắp xếp Nổi bọt (Bubble Sort) trong trường hợp mảng *đã được sắp xếp* là gì?

O(n^2)

O(n log n)

O(n)

O(1)

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 17: Xét đoạn mã giả sau:
```
function example7(n):
sum = 0
for i from 1 to n:
sum = sum + i
for j from 1 to n * n:
sum = sum + j
return sum
```
Độ phức tạp thời gian của hàm `example7(n)` là gì?

O(n)

O(n log n)

O(n + n^2)

O(n^2)

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 18: Tại sao độ phức tạp thời gian O(log n) được coi là rất hiệu quả, đặc biệt với đầu vào lớn?

Vì nó chỉ thực hiện một số thao tác cố định.

Vì số thao tác cần thiết tăng trưởng rất chậm khi kích thước đầu vào tăng.

Vì nó luôn nhanh hơn bất kỳ thuật toán nào khác.

Vì nó chỉ áp dụng cho các bài toán đơn giản.

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 19: Khi phân tích độ phức tạp thời gian, 'trường hợp xấu nhất' (Worst Case) thường được sử dụng nhất vì lý do nào sau đây?

Nó cung cấp giới hạn trên cho thời gian thực hiện, đảm bảo hiệu suất tối thiểu.

Nó là trường hợp dễ phân tích nhất.

Nó đại diện cho hiệu suất trung bình của thuật toán.

Đó là kịch bản đầu vào phổ biến nhất.

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 20: Xét đoạn mã giả sau:
```
function example8(A, n):
# A là một mảng kích thước n x n
sum = 0
for i from 0 to n-1:
for j from 0 to n-1:
sum = sum + A[i][j]
return sum
```
Độ phức tạp thời gian của hàm `example8(A, n)` là gì?

O(n)

O(n log n)

O(n^2)

O(n^3)

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 21: Sắp xếp các độ phức tạp thời gian sau theo thứ tự từ hiệu quả nhất đến kém hiệu quả nhất (tốc độ tăng trưởng chậm nhất đến nhanh nhất) khi n rất lớn: O(n^2), O(log n), O(n), O(1), O(n log n).

O(n^2), O(n log n), O(n), O(log n), O(1)

O(1), O(log n), O(n), O(n log n), O(n^2)

O(log n), O(1), O(n), O(n log n), O(n^2)

O(1), O(n), O(log n), O(n log n), O(n^2)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 22: Một thuật toán tìm kiếm tuần tự (Linear Search) trên mảng kích thước n có độ phức tạp thời gian O(n) trong trường hợp xấu nhất. Nếu mỗi phép so sánh mất 1 micro giây, và bạn có 1 giây (1,000,000 micro giây), kích thước mảng (n) lớn nhất mà thuật toán này có thể xử lý trong 1 giây trong trường hợp xấu nhất là bao nhiêu?

100

1000

100000

1000000

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 23: Một thuật toán sắp xếp (ví dụ: Selection Sort) có độ phức tạp thời gian O(n^2). Nếu mỗi phép so sánh/hoán đổi cơ bản mất 1 micro giây, và bạn có 1 giây (1,000,000 micro giây), ước tính kích thước mảng (n) lớn nhất mà thuật toán này có thể xử lý trong 1 giây là bao nhiêu?

100

316

1000

10000

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 24: Xét đoạn mã giả sau:
```
function example9(n):
count = 0
i = n
while i > 0:
count = count + 1
i = i / 2 # Giả sử phép chia làm tròn xuống
return count
```
Độ phức tạp thời gian của hàm `example9(n)` là gì?

O(log n)

O(n)

O(n log n)

O(n^2)

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 25: Độ 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?

Các thuật toán chỉ có một vòng lặp đơn giản.

Các thuật toán sử dụng kỹ thuật 'chia để trị' hiệu quả (ví dụ: Merge Sort).

Các thuật toán có hai vòng lặp lồng nhau.

Các thuật toán chỉ thực hiện một số bước cố định.

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 26: Xét đoạn mã giả sau:
```
function example10(n):
total = 0
for i from 1 to 100:
for j from 1 to n:
total = total + i * j
return total
```
Độ phức tạp thời gian của hàm `example10(n)` là gì?

O(1)

O(n)

O(n^2)

O(100n)

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 27: Tại sao việc phân tích độ phức tạp thời gian lại quan trọng trong khoa học máy tính?

Để biết thuật toán chạy bao nhiêu giây trên một máy tính cụ thể.

Để xác định số dòng mã trong thuật toán.

Để dự đoán 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.

Chỉ quan trọng đối với các thuật toán sắp xếp và tìm kiếm.

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 28: Xét đoạn mã giả sau:
```
function example11(n):
count = 0
i = 1
while i * i <= n: count = count + 1 i = i + 1 return count ``` Độ phức tạp thời gian của hàm `example11(n)` là gì?

O(log n)

O(n)

O(n log n)

O(√n)

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 29: Phát biểu nào sau đây là ĐÚNG khi nói về mối quan hệ giữa độ phức tạp thời gian và hiệu suất thực tế của thuật toán?

Độ phức tạp thời gian mô tả hành vi tiệm cận (khi n lớn) và là yếu tố chính quyết định hiệu suất cho đầu vào lớn, nhưng hằng số có thể quan trọng với đầu vào nhỏ.

Độ phức tạp thời gian hoàn toàn quyết định thời gian chạy thực tế trên mọi kích thước đầu vào.

Các thuật toán có cùng độ phức tạp thời gian luôn có hiệu suất thực tế giống hệt nhau.

Độ phức tạp thời gian chỉ hữu ích trong lý thuyết, không liên quan đến hiệu suất thực tế.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 07

Câu 30: Xét đoạn mã giả sau:
```
function example12(n):
count = 0
if n > 1000:
for i from 1 to n:
count = count + 1
else:
for i from 1 to 100:
count = count + 1
return count
```
Độ phức tạp thời gian của hàm `example12(n)` là gì?

O(1)

O(log n)

O(n)

O(n^2)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 08

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 1: Phân tích đoạn mã giả sau:
`function TongMang(A, n):`
` sum = 0`
` for i from 0 to n-1:`
` sum = sum + A[i]`
` return sum`
Độ phức tạp thời gian của hàm `TongMang` theo kích thước mảng `n` là gì?

O(1)

O(n)

O(n log n)

O(n^2)

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 2: Phân tích đoạn mã giả sau:
`function TimCapTongBangK(A, n, K):`
` for i from 0 to n-1:`
` for j from 0 to n-1:`
` if A[i] + A[j] == K:`
` return (i, j)`
` return (-1, -1)`
Độ phức tạp thời gian của hàm `TimCapTongBangK` trong trường hợp xấu nhất là gì?

O(n)

O(n log n)

O(n!)

O(n^2)

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 3: Phân tích đoạn mã giả sau:
`function DemSoLanChia2(n):`
` count = 0`
` while n > 1:`
` n = n / 2`
` count = count + 1`
` return count`
Độ phức tạp thời gian của hàm `DemSoLanChia2` là gì?

O(n)

O(n^2)

O(log n)

O(1)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 4: Thuật toán tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước `n`. Trong trường hợp xấu nhất, phần tử cần tìm nằm ở vị trí nào hoặc không có trong mảng? Điều này dẫn đến độ phức tạp thời gian là O(n).

Ở vị trí đầu tiên.

Ở vị trí cuối cùng hoặc không có trong mảng.

Ở vị trí chính giữa.

Ở bất kỳ vị trí nào với xác suất như nhau.

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 5: Thuật toán sắp xếp chọn (Selection Sort) trên một mảng kích thước `n` luôn có độ phức tạp thời gian O(n^2) ở cả trường hợp tốt nhất, xấu nhất và trung bình. Tại sao?

Vì thuật toán luôn phải duyệt qua phần còn lại của mảng để tìm phần tử nhỏ nhất trong mỗi bước của vòng lặp ngoài, bất kể mảng đã sắp xếp hay chưa.

Vì số lần đổi chỗ luôn là n-1.

Vì thuật toán sử dụng hai vòng lặp lồng nhau mà vòng lặp trong chỉ chạy khi mảng chưa sắp xếp.

Vì độ phức tạp chỉ phụ thuộc vào số lần so sánh, và số lần so sánh luôn là n^2.

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 6: Khi phân tích độ phức tạp thời gian của một thuật toán, chúng ta thường quan tâm đến bậc phức tạp cao nhất (ví dụ: trong O(n^2 + n), ta lấy O(n^2)). Điều này là bởi vì:

Các hằng số và các số hạng bậc thấp không bao giờ ảnh hưởng đến thời gian chạy.

Chúng ta chỉ quan tâm đến hiệu suất của thuật toán trên các bộ dữ liệu nhỏ.

Khi kích thước đầu vào `n` rất lớn, số hạng có bậc cao nhất sẽ chi phối tổng thời gian thực hiện.

Việc phân tích chi tiết tất cả các số hạng là quá phức tạp và không cần thiết.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

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

Gấp đôi (2 lần)

Gấp bốn lần (4 lần)

Gấp sáu lần (6 lần)

Gấp tám lần (8 lần)

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 8: Phân tích đoạn mã giả sau:
`function Xuly(A, n):`
` for i from 0 to n-1:`
` print A[i]`
` for j from 0 to n-1:`
` print A[j]`
Độ phức tạp thời gian của hàm `Xuly` là gì?

O(n^2)

O(n)

O(log n)

O(1)

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 9: Phân tích đoạn mã giả sau:
`function Magic(n):`
` if n <= 1: return`
` for i from 1 to 10:`
` print i`
` Magic(n/2)`
Độ phức tạp thời gian của hàm `Magic` là gì?

O(n)

O(n log n)

O(log n)

O(1)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 10: Thuật toán sắp xếp nổi bọt (Bubble Sort) trên một mảng kích thước `n`. Trong trường hợp tốt nhất (mảng đã được sắp xếp), độ phức tạp thời gian là O(n). Tại sao?

Vì thuật toán có thể sử dụng một cờ (flag) để kiểm tra xem có sự đổi chỗ nào xảy ra trong một lần duyệt hay không. Nếu không có đổi chỗ, mảng đã sắp xếp và thuật toán dừng lại sau một lần duyệt toàn bộ mảng (O(n)).

Vì vòng lặp trong chỉ chạy một lần.

Vì số lần so sánh trong trường hợp tốt nhất là n/2.

Vì thuật toán chỉ cần thực hiện các phép so sánh chứ không cần đổi chỗ.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 11: Phân tích đoạn mã giả sau:
`function TinhToanPhucTap(n):`
` for i from 0 to n-1:`
` for j from 0 to i-1:`
` print (i, j)`
Độ phức tạp thời gian của hàm `TinhToanPhucTap` là gì?

O(n)

O(n log n)

O(log n)

O(n^2)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 12: Giả sử thuật toán A có độ phức tạp O(n^2) và thuật toán B có độ phức tạp O(n log n). Đối với các bộ dữ liệu có kích thước `n` rất lớn, thuật toán nào thường được ưu tiên sử dụng và tại sao?

Thuật toán A, vì O(n^2) cho biết hiệu suất ổn định hơn.

Thuật toán B, vì O(n log n) tăng chậm hơn nhiều so với O(n^2) khi n lớn.

Thuật toán A, vì n^2 luôn lớn hơn n log n.

Thuật toán B, vì log n luôn nhỏ hơn n.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 13: Phân tích đoạn mã giả sau:
`function ProcessData(arr, n):`
` for i from 0 to n-1:`
` print arr[i]`
` if n > 100:`
` for j from 0 to 99:`
` print arr[j]`
Độ phức tạp thời gian của hàm `ProcessData` là gì?

O(n)

O(n + 100)

O(100)

O(n^2)

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 14: Trong phân tích độ phức tạp thời gian tiệm cận (Asymptotic Time Complexity), ký hiệu O lớn (Big O) thường biểu diễn điều gì?

Thời gian thực hiện chính xác của thuật toán.

Giới hạn dưới của thời gian thực hiện trong trường hợp tốt nhất.

Thời gian thực hiện trung bình của thuật toán.

Giới hạn trên của thời gian thực hiện trong trường hợp xấu nhất.

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 15: Phân tích đoạn mã giả sau:
`function CountPairs(A, n):`
` count = 0`
` for i from 0 to n-2:`
` for j from i+1 to n-1:`
` count = count + 1`
` return count`
Độ phức tạp thời gian của hàm `CountPairs` là gì?

O(n)

O(n log n)

O(n!)

O(n^2)

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 16: Khi so sánh 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), phát biểu nào sau đây là đúng về hiệu suất của chúng khi `n` đủ lớn?

Thuật toán A luôn chạy nhanh hơn thuật toán B.

Thuật toán B luôn chạy nhanh hơn thuật toán A.

Thuật toán A sẽ chạy nhanh hơn thuật toán B một cách đáng kể.

Không thể so sánh vì thiếu thông tin về hằng số.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

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

Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào.

Thời gian thực hiện là không đổi, không phụ thuộc vào kích thước đầu vào.

Thời gian thực hiện tăng theo hàm logarit của kích thước đầu vào.

Thuật toán không bao giờ dừng lại.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 18: Phân tích đoạn mã giả sau:
`function Example(n):`
` for i from 1 to n:`
` print i`
` for j from 1 to 100:`
` print j`
Độ phức tạp thời gian của hàm `Example` là gì?

O(n)

O(100)

O(n + 100)

O(n^2)

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 19: Phân tích đoạn mã giả sau:
`function AnotherExample(n):`
` i = 1`
` while i < n:`
` print i`
` i = i * 2`
Độ phức tạp thời gian của hàm `AnotherExample` là gì?

O(n)

O(n^2)

O(log n)

O(1)

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 20: Trong thuật toán sắp xếp nổi bọt (Bubble Sort), trường hợp nào được coi là trường hợp xấu nhất về thời gian thực hiện?

Mảng đã được sắp xếp tăng dần.

Mảng được sắp xếp ngược (giảm dần).

Tất cả các phần tử trong mảng đều giống nhau.

Mảng rỗng.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 21: Phân tích đoạn mã giả sau:
`function Calculate(n):`
` result = 0`
` for i from 0 to n*n - 1:`
` result = result + i`
` return result`
Độ phức tạp thời gian của hàm `Calculate` là gì?

O(n)

O(n log n)

O(n^3)

O(n^2)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

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

Tìm kiếm nhị phân (Binary Search) trên mảng đã sắp xếp.

Tìm kiếm tuần tự (Linear Search).

Sắp xếp chọn (Selection Sort).

Duyệt qua tất cả các cặp phần tử trong mảng.

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 23: Phân tích đoạn mã giả sau:
`function YetAnotherExample(n):`
` sum = 0`
` for i from 0 to n-1:`
` for j from 0 to 9:`
` sum = sum + i * j`
` return sum`
Độ phức tạp thời gian của hàm `YetAnotherExample` là gì?

O(n)

O(10n)

O(n^2)

O(10)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 24: Phân tích đoạn mã giả sau:
`function ComplexFunction(n):`
` for i from 0 to n-1:`
` print i`
` for j from 0 to n-1:`
` for k from 0 to n-1:`
` print (j, k)`
Độ phức tạp thời gian của hàm `ComplexFunction` là gì?

O(n)

O(n^2)

O(n + n^2)

O(n^3)

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 25: Giả sử bạn có hai hàm: `HamA(n)` có độ phức tạp O(n) và `HamB(m)` có độ phức tạp O(m^2). Nếu bạn gọi `HamA(n)` rồi sau đó gọi `HamB(n)` (với m=n), độ phức tạp tổng thể sẽ là gì?

O(n)

O(n log n)

O(n^2)

O(n^3)

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 26: Ý nghĩa của việc phân tích độ phức tạp thời gian của thuật toán là gì?

Ước lượng 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.

Đo thời gian thực hiện chính xác của thuật toán trên một máy tính cụ thể.

Xác định số dòng mã trong thuật toán.

Chỉ ra thuật toán có chạy đúng hay không.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 27: Phân tích đoạn mã giả sau:
`function DoSomething(n):`
` i = n`
` while i > 0:`
` print i`
` i = i - 1`
` for j from 1 to 5:`
` print j`
Độ phức tạp thời gian của hàm `DoSomething` là gì?

O(1)

O(n)

O(n + 5)

O(n^2)

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 28: Phân tích đoạn mã giả sau:
`function AnalyzeMe(n):`
` for i from 0 to n-1:`
` for j from 0 to 1000:`
` print (i, j)`
Độ phức tạp thời gian của hàm `AnalyzeMe` là gì?

O(n)

O(1000n)

O(n^2)

O(1000)

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 29: Tại sao việc hiểu độ phức tạp thời gian lại quan trọng khi thiết kế thuật toán?

Để biết thuật toán sẽ chạy chính xác bao nhiêu giây.

Để chứng minh thuật toán là đúng.

Để dự đoán hiệu suất của thuật toán với các bộ dữ liệu lớn và so sánh các thuật toán khác nhau.

Để biết thuật toán sử dụng bao nhiêu bộ nhớ.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 08

Câu 30: Phân tích đoạn mã giả sau:
`function MysteryLoop(n):`
` i = 0`
` while i < n:`
` print i`
` i = i + 3`
Độ phức tạp thời gian của hàm `MysteryLoop` là gì?

O(1)

O(n)

O(n/3)

O(log n)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 09

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán bằng ký hiệu O lớn (Big O), chúng ta quan tâm chủ yếu đến yếu tố nào khi kích thước đầu vào (n) rất lớn?

Các hằng số nhân

Các số hạng bậc thấp

Thời gian thực thi trên một máy tính cụ thể

Tốc độ tăng trưởng của số phép toán cơ bản theo n

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 2: Xét đoạn mã giả sau:
```
function Example(n):
sum = 0
for i from 1 to n:
sum = sum + i
return sum
```
Độ phức tạp thời gian của hàm `Example(n)` là gì?

O(1)

O(log n)

O(n)

O(n^2)

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

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

O(n)

O(n log n)

O(log n)

O(n^2)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 4: Thuật toán tìm kiếm tuần tự (Linear Search) trong một mảng gồm n phần tử có độ phức tạp thời gian trong trường hợp xấu nhất là O(n). Trường hợp xấu nhất này xảy ra khi nào?

Phần tử cần tìm là phần tử đầu tiên của mảng.

Phần tử cần tìm là phần tử cuối cùng của mảng hoặc không có trong mảng.

Mảng đã được sắp xếp theo thứ tự tăng dần.

Mảng có kích thước nhỏ hơn 100 phần tử.

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 5: Một thuật toán có độ phức tạp thời gian là O(n^2). Nếu với đầu vào có kích thước n = 100, thuật toán chạy mất khoảng 10 mili giây. Ước tính thời gian chạy của thuật toán này với đầu vào có kích thước n = 1000 là bao nhiêu?

100 mili giây

1 giây

1000 mili giây (1 giây)

10 giây

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

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

Tìm kiếm nhị phân (Binary Search) trên mảng đã sắp xếp.

Tìm kiếm tuần tự (Linear Search) trên mảng bất kỳ.

Sắp xếp chọn (Selection Sort).

Duyệt qua tất cả các cặp phần tử trong mảng.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 7: 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 log n). Khi kích thước đầu vào n rất lớn, thuật toán nào thường hiệu quả hơn (chạy nhanh hơn)?

Thuật toán A.

Thuật toán B.

Cả hai thuật toán có hiệu quả như nhau.

Không thể so sánh nếu không biết các hằng số.

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 8: Xét đoạn mã giả sau:
```
function AnotherExample(n):
for i from 1 to n:
// Các thao tác có độ phức tạp O(1)
for j from 1 to n*n:
// Các thao tác có độ phức tạp O(1)
```
Độ phức tạp thời gian tổng thể của hàm `AnotherExample(n)` là gì?

O(n)

O(n log n)

O(n + n^2)

O(n^2)

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 9: Thuật toán sắp xếp chọn (Selection Sort) hoạt động bằng cách lặp đi lặp lại việc tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần chưa được sắp xếp của mảng và hoán đổi nó với phần tử ở vị trí đầu tiên của phần chưa được sắp xếp đó. Thao tác nào trong Selection Sort đóng góp chính vào độ phức tạp O(n^2) của nó?

Thao tác hoán đổi (swap) hai phần tử.

Thao tác tìm phần tử nhỏ nhất (hoặc lớn nhất) trong phần mảng còn lại.

Việc khởi tạo các biến đếm.

Thao tác truy cập một phần tử theo chỉ số.

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

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

Thời gian thực hiện tăng tuyến tính theo kích thước đầu vào n.

Thời gian thực hiện tăng theo hàm logarit của kích thước đầu vào n.

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.

Thời gian thực hiện tăng theo bình phương của kích thước đầu vào n.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 11: Xét đoạn mã giả:
```
function Power(base, exp):
if exp == 0:
return 1
else:
return base * Power(base, exp - 1)
```
Độ phức tạp thời gian của hàm đệ quy `Power(base, exp)` theo `exp` là gì?

O(1)

O(log exp)

O(exp)

O(base * exp)

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 12: 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 tốt nhất (khi mảng đã sắp xếp) là gì?

O(1)

O(n)

O(n log n)

O(n^2)

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 13: Khi so sánh O(n) và O(n^2), tại sao O(n^2) lại kém hiệu quả hơn đáng kể so với O(n) khi n lớn?

Vì hàm n^2 tăng nhanh hơn rất nhiều so với hàm n khi n tăng.

Vì thuật toán O(n^2) luôn có nhiều dòng mã hơn.

Vì thuật toán O(n) sử dụng ít bộ nhớ hơn.

Vì O(n^2) chỉ dùng cho các bài toán khó hơn.

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 14: Xét đoạn mã giả sau:
```
function ProcessArray(arr, n):
max_val = arr[0]
for i from 1 to n-1:
if arr[i] > max_val:
max_val = arr[i]
// Một số thao tác khác không phụ thuộc vào n
return max_val
```
Độ phức tạp thời gian của hàm `ProcessArray(arr, n)` là gì?

O(1)

O(log n)

O(n)

O(n^2)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 15: Một thuật toán cần thực hiện N phép toán cơ bản để xử lý đầu vào có kích thước n. Nếu N = 5n^3 + 2n^2 + 100. Khi sử dụng ký hiệu O lớn, độ phức tạp thời gian của thuật toán này là gì?

O(n)

O(n^2)

O(5n^3)

O(n^3)

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 16: Đối với thuật toán tìm kiếm tuần tự (Linear Search), độ phức tạp thời gian trong trường hợp tốt nhất là O(1). Trường hợp tốt nhất này xảy ra khi nào?

Phần tử cần tìm là phần tử đầu tiên của mảng.

Phần tử cần tìm là phần tử cuối cùng của mảng.

Phần tử cần tìm nằm ở giữa mảng.

Mảng có kích thước rất lớn.

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 17: Tại sao khi phân tích độ phức tạp bằng ký hiệu O lớn, chúng ta thường bỏ qua các hằng số nhân?

Vì hằng số luôn bằng 1.

Vì khi n đủ lớn, tốc độ tăng trưởng của hàm được quyết định bởi số hạng bậc cao nhất, không phải hằng số.

Vì hằng số phụ thuộc vào ngôn ngữ lập trình.

Vì hằng số chỉ ảnh hưởng đến bộ nhớ sử dụng.

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 18: Sắp xếp các độ phức tạp thời gian sau theo thứ tự tăng dần về tốc độ tăng trưởng (từ chậm nhất đến nhanh nhất): O(n), O(log n), O(n^2), O(1).

O(n^2), O(n), O(log n), O(1)

O(n), O(log n), O(n^2), O(1)

O(1), O(log n), O(n), O(n^2)

O(log n), O(1), O(n), O(n^2)

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 19: Xét đoạn mã giả sau:
```
function ExampleLoop(n):
i = 1
while i < n: // Các thao tác có độ phức tạp O(1) i = i * 2 ``` Độ phức tạp thời gian của hàm `ExampleLoop(n)` là gì?

O(n)

O(log n)

O(n^2)

O(1)

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 20: Nếu một thuật toán có độ phức tạp O(n log n) chạy mất 1 giây với n = 1000. Ước tính thời gian chạy của thuật toán này với n = 1000000?

Khoảng 100 giây.

Khoảng 1000 giây.

Khoảng 3000 giây.

Khoảng 2000 giây. (n log n: 1000 log 1000 ~ 1000 * 10 = 10000. 1000000 log 1000000 ~ 1000000 * 20 = 20000000. Tỉ lệ thời gian ~ (20M / 10k) = 2000 lần. 1 giây * 2000 = 2000 giây).

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 21: 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à O(n^2). Trường hợp xấu nhất này xảy ra khi nào?

Mảng đã được sắp xếp theo thứ tự tăng dần.

Mảng đã được sắp xếp theo thứ tự giảm dần.

Mảng đã được sắp xếp ngược lại với thứ tự mong muốn (ví dụ: muốn tăng dần nhưng mảng đang giảm dần).

Mảng chứa các phần tử giống nhau.

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 22: Xét đoạn mã giả sau:
```
function ExampleConditional(n):
if n > 1000:
for i from 1 to n*n:
// O(1) operations
else:
for i from 1 to n:
// O(1) operations
```
Độ phức tạp thời gian của hàm `ExampleConditional(n)` là gì?

O(n)

O(n log n)

O(1)

O(n^2)

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 23: Trong phân tích độ phức tạp, tại sao chúng ta thường quan tâm đến trường hợp xấu nhất (worst-case) của thuật toán?

Để đảm bảo rằng thuật toán vẫn có thể hoàn thành trong một khoảng thời gian chấp nhận được ngay cả trong điều kiện khó khăn nhất.

Vì trường hợp xấu nhất là trường hợp dễ phân tích nhất.

Vì trường hợp xấu nhất là trường hợp xảy ra thường xuyên nhất.

Vì trường hợp xấu nhất cung cấp kết quả nhanh nhất.

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 24: Xét đoạn mã giả sau:
```
function ComplexFunction(n):
for i from 1 to n:
// O(1) operations
for j from 1 to n:
for k from 1 to n:
// O(1) operations
```
Độ phức tạp thời gian của hàm `ComplexFunction(n)` là gì?

O(n)

O(n^2)

O(n + n^3)

O(n^3)

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 25: 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 tốt nhất là gì?

O(n)

O(log n)

O(n log n)

O(n^2)

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 26: Giả sử bạn có hai thuật toán để giải cùng một bài toán. Thuật toán A có độ phức tạp O(n^2) và thuật toán B có độ phức tạp O(n log n). Với đầu vào kích thước N = 10^6, thuật toán nào có khả năng hoàn thành trong thời gian hợp lý (ví dụ: vài giây đến vài phút) trên máy tính hiện đại?

Thuật toán A (O(n^2))

Thuật toán B (O(n log n))

Cả hai đều quá chậm.

Cả hai đều đủ nhanh.

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 27: Xét đoạn mã giả sau:
```
function AnalyzeData(n):
if n < 10: // O(1) operations else: for i from 1 to n: for j from 1 to 100: // O(1) operations ``` Độ phức tạp thời gian của hàm `AnalyzeData(n)` là gì?

O(1)

O(100n)

O(n)

O(n^2)

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 28: Thuật toán sắp xếp nào trong các lựa chọn dưới đây *không* có độ phức tạp thời gian trường hợp xấu nhất là O(n^2)?

Sắp xếp trộn (Merge Sort)

Sắp xếp nổi bọt (Bubble Sort)

Sắp xếp chọn (Selection Sort)

Sắp xếp chèn (Insertion Sort)

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 29: Nếu một thuật toán cần thực hiện số phép toán là T(n) = n * (n - 1) / 2. Khi biểu diễn bằng ký hiệu O lớn, độ phức tạp thời gian của thuật toán này là gì?

O(n)

O(n^2)

O(n log n)

O(1)

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 09

Câu 30: Độ phức tạp thời gian O(n!) (giai thừa) và O(2^n) (hàm mũ) được coi là rất kém hiệu quả. Chúng thường xuất hiện trong các bài toán có tính chất gì?

Các bài toán tìm kiếm đơn giản.

Các bài toán sắp xếp hiệu quả.

Các bài toán duyệt toàn bộ không gian trạng thái hoặc tổ hợp (ví dụ: Bài toán người du lịch, tìm tất cả hoán vị).

Các bài toán xử lý dữ liệu lớn trên cơ sở dữ liệu.

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Bạn đã sẵn sàng chưa? 45 phút làm bài bắt đầu!!!

Bạn đã hết giờ làm bài! Xem kết quả các câu hỏi đã làm nhé!!!

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán - Đề 10

1 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 1: Khi phân tích độ phức tạp thời gian của một thuật toán, ký hiệu O lớn (Big O notation) thường được sử dụng để mô tả điều gì?

Thời gian thực hiện chính xác của thuật toán trên một máy tính cụ thể.

Số bước thực hiện trung bình của thuật toán.

Giới hạn trên của tốc độ tăng trưởng thời gian thực hiện khi kích thước dữ liệu đầu vào tăng lên.

Bộ nhớ sử dụng bởi thuật toán.

2 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 2: Xét đoạn mã giả sau:
```
function process(n):
sum = 0
for i from 1 to n:
sum = sum + i
return sum
```
Độ phức tạp thời gian của hàm `process(n)` là bao nhiêu?

O(1)

O(n)

O(n^2)

O(log n)

3 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 3: Xét đoạn mã giả sau:
```
function analyze(n):
count = 0
for i from 1 to n:
for j from 1 to n:
count = count + 1
return count
```
Độ phức tạp thời gian của hàm `analyze(n)` là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(2^n)

4 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 4: Xét đoạn mã giả sau:
```
function calculate(n):
result = 0
for i from 1 to n:
for j from i to n:
result = result + 1
return result
```
Độ phức tạp thời gian của hàm `calculate(n)` là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

5 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 5: Một thuật toán tìm kiếm trong một mảng đã được sắp xếp bằng cách liên tục chia đôi phạm vi tìm kiếm. Độ phức tạp thời gian trong trường hợp xấu nhất của thuật toán này là gì?

O(1)

O(n)

O(n^2)

O(log n)

6 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 6: 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à O(n^2). Điều này có nghĩa là gì khi kích thước mảng đầu vào (n) tăng gấp đôi?

Thời gian thực hiện sẽ tăng khoảng 4 lần.

Thời gian thực hiện sẽ tăng gấp đôi.

Thời gian thực hiện sẽ tăng khoảng log(2) lần.

Thời gian thực hiện sẽ không thay đổi.

7 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 7: Thuật toán Tìm kiếm tuần tự (Linear Search) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp tốt nhất của thuật toán này là gì?

O(1)

O(n)

O(n log n)

O(n^2)

8 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 8: Thuật toán Sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp tốt nhất (khi mảng đã được sắp xếp) là gì?

O(1)

O(n)

O(n log n)

O(n^2)

9 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 9: Thuật toán Sắp xếp nổi bọt (Bubble Sort) trên một mảng có kích thước n. Độ phức tạp thời gian trong trường hợp xấu nhất là gì?

O(1)

O(n)

O(n log n)

O(n^2)

10 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 10: Trong phân tích độ phức tạp thời gian O lớn, chúng ta thường bỏ qua các hằng số nhân và các số hạng bậc thấp. Ví dụ, một thuật toán có số bước là 3n^2 + 2n + 5 sẽ được biểu diễn là O(n^2). Tại sao lại làm như vậy?

Để làm cho việc tính toán đơn giản hơn.

Vì các hằng số và số hạng bậc thấp không ảnh hưởng đến thời gian thực hiện.

Vì chúng ta quan tâm đến tốc độ tăng trưởng của thời gian thực hiện khi n rất lớn, khi đó các số hạng bậc cao chi phối.

Vì các hằng số và số hạng bậc thấp phụ thuộc vào ngôn ngữ lập trình.

11 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 11: Một thuật toán có độ phức tạp O(n log n). Nếu thuật toán này mất 0.5 giây để xử lý dữ liệu có kích thước n = 1000, ước tính thời gian cần thiết để xử lý dữ liệu có kích thước n = 2000?

Khoảng 0.75 giây

Khoảng 1.1 giây

Khoảng 2.0 giây

Khoảng 2.5 giây

12 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

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

Thời gian thực hiện không phụ thuộc vào kích thước dữ liệu đầu vào.

Thời gian thực hiện tăng tuyến tính với kích thước dữ liệu đầu vào.

Thời gian thực hiện tăng theo logarit của kích thước dữ liệu đầu vào.

Thời gian thực hiện tăng theo bình phương của kích thước dữ liệu đầu vào.

13 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 13: Trong các độ phức tạp thời gian sau, độ phức tạp nào là hiệu quả nhất (tốt nhất) khi kích thước dữ liệu đầu vào n rất lớn?

O(n)

O(n log n)

O(n^2)

O(log n)

14 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 14: Xét đoạn mã giả sau:
```
function doSomething(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 hàm `doSomething(n)` là bao nhiêu?

O(1)

O(n)

O(100 + n)

O(100n)

15 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 15: Xét đoạn mã giả sau:
```
function processData(arr):
n = arr.length
if n <= 1: return mid = n / 2 processData(arr[0...mid-1]) processData(arr[mid...n-1]) // some O(n) operation here to combine results ``` Đoạn mã này mô tả cấu trúc của một thuật toán 'chia để trị' (Divide and Conquer). Nếu bước kết hợp tốn O(n), độ phức tạp thời gian tổng thể của thuật toán này có thể là bao nhiêu?

O(n)

O(n^2)

O(n log n)

O(log n)

16 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 16: 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), thuật toán nào sẽ có hiệu suất tốt hơn khi xử lý lượng dữ liệu lớn?

Thuật toán A

Thuật toán B

Cả hai có hiệu suất như nhau

Không thể xác định chỉ dựa vào độ phức tạp O lớn

17 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 17: Một thuật toán mất 10 giây để hoàn thành với dữ liệu đầu vào có kích thước n = 1000. Nếu độ phức tạp của thuật toán là O(n^3), ước tính thời gian cần thiết để hoàn thành với dữ liệu đầu vào có kích thước n = 2000?

20 giây

40 giây

80 giây

Không đủ thông tin để ước tính chính xác

18 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 18: Xét đoạn mã giả sau:
```
function complexFunc(n):
sum1 = 0
for i from 1 to n:
sum1 = sum1 + i

sum2 = 0
for j from 1 to n:
for k from 1 to n:
sum2 = sum2 + j*k

return sum1 + sum2
```
Độ phức tạp thời gian của hàm `complexFunc(n)` là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(n^3)

19 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 19: Thuật toán nào trong số các thuật toán sắp xếp cơ bản sau đây có độ phức tạp thời gian trong trường hợp xấu nhất là O(n^2)?

Tìm kiếm nhị phân (Binary Search) - *Lưu ý: Đây là tìm kiếm, không phải sắp xếp*

Sắp xếp trộn (Merge Sort)

Sắp xếp nhanh (Quick Sort) - *Trường hợp trung bình là O(n log n), nhưng xấu nhất là O(n^2)*

Sắp xếp chèn (Insertion Sort)

20 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 20: Tại sao độ phức tạp thời gian trong trường hợp xấu nhất (worst-case) lại quan trọng khi đánh giá một thuật toán?

Vì đó là trường hợp phổ biến nhất xảy ra.

Vì nó cung cấp một giới hạn trên đảm bảo về hiệu suất của thuật toán, bất kể dữ liệu đầu vào là gì.

Vì nó dễ tính toán nhất.

Vì nó cho biết hiệu suất tốt nhất có thể đạt được.

21 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 21: Xét đoạn mã giả sau:
```
function processArray(arr):
n = arr.length
if n == 0:
return 0
if n == 1:
return arr[0]

sum = 0
for x in arr:
sum = sum + x
return sum
```
Độ phức tạp thời gian của hàm `processArray(arr)` là bao nhiêu?

O(1)

O(n)

O(n log n)

O(n^2)

22 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 22: Một thuật toán có độ phức tạp O(log n). Nếu nó mất 0.1 giây cho n = 1024, ước tính thời gian cho n = 4096?

Khoảng 0.12 giây

Khoảng 0.2 giây

Khoảng 0.4 giây

Khoảng 0.8 giây

23 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 23: Xét đoạn mã giả sau:
```
function find_pair(arr, target):
n = arr.length
for i from 0 to n-2:
for j from i+1 to n-1:
if arr[i] + arr[j] == target:
return true
return false
```
Độ phức tạp thời gian của hàm `find_pair(arr, target)` là bao nhiêu?

O(n)

O(n log n)

O(n^2)

O(log n)

24 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 24: Khi so sánh O(n log n) và O(n^2), thuật toán có độ phức tạp O(n log n) thường được ưa chuộng hơn cho các bài toán sắp xếp trên tập dữ liệu lớn. Điều này là do:

n log n luôn nhỏ hơn n^2.

Tốc độ tăng trưởng của n log n chậm hơn đáng kể so với n^2 khi n lớn.

Các thuật toán O(n log n) dễ cài đặt hơn.

Các thuật toán O(n log n) sử dụng ít bộ nhớ hơn.

25 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 25: Xét đoạn mã giả sau:
```
function mystery(n):
i = 1
while i < n: print(i) i = i * 2 ``` Độ phức tạp thời gian của hàm `mystery(n)` là bao nhiêu?

O(n)

O(n^2)

O(sqrt(n))

O(log n)

26 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 26: Nếu một thuật toán có độ phức tạp O(n), và mất 5 giây để xử lý 100.000 phần tử, thì ước tính thời gian cần thiết để xử lý 500.000 phần tử là bao nhiêu?

10 giây

15 giây

25 giây

50 giây

27 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 27: Xét đoạn mã giả sau:
```
function anotherFunc(n):
for i from 1 to n:
// Một phép tính O(1) ở đây

for j from 1 to n:
for k from 1 to 10:
// Một phép tính O(1) ở đây
```
Độ phức tạp thời gian của hàm `anotherFunc(n)` là bao nhiêu?

O(1)

O(n)

O(n log n)

O(n^2)

28 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 28: Độ phức tạp thời gian trung bình (average-case) của một thuật toán là gì?

Thời gian thực hiện trung bình trên tất cả các bộ dữ liệu đầu vào có cùng kích thước.

Thời gian thực hiện tốt nhất có thể đạt được.

Thời gian thực hiện lâu nhất có thể xảy ra.

Độ phức tạp chỉ áp dụng cho các thuật toán ngẫu nhiên.

29 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 29: Tại sao thuật toán Tìm kiếm nhị phân (Binary Search) yêu cầu mảng đầu vào phải được sắp xếp?

Để giảm độ phức tạp thời gian xuống O(log n).

Để đảm bảo phần tử cần tìm luôn tồn tại trong mảng.

Vì thuật toán dựa vào việc so sánh phần tử cần tìm với phần tử ở giữa và loại bỏ một nửa mảng dựa trên thứ tự.

Để sử dụng ít bộ nhớ hơn.

30 / 30

Category: Trắc nghiệm Tin học 11 Kết nối tri thức Bài 25: Thực hành xác định độ phức tạp thời gian thuật toán

Tags: Bộ đề 10

Câu 30: Xét đoạn mã giả sau:
```
function processNested(n):
count = 0
for i from 1 to n:
for j from 1 to i:
for k from 1 to 5:
count = count + 1
return count
```
Độ phức tạp thời gian của hàm `processNested(n)` là bao nhiêu?

O(n)

O(n^2)

O(5n^2)

O(n^3)

Xem kết quả

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Nhận kết quả

Xảy ra lỗi

Bước 1: Vào google.com rồi gõ từ khóa:
Copy nhanh thanh-tim-kiem

Bước 2: Trong kết quả tìm kiếm Google, hãy tìm website giống hình bên dưới

Nếu trang 1 không có hãy tìm ở trang 2, 3, 4... nhé trang-google

Bước 3:

Cuộn xuống cuối bài viết rồi bấm vào nút GIỐNG HÌNH DƯỚI và chờ 1 lát để lấy mã:

luot-xem

Nếu tìm không thấy mã bạn có thể Đổi nhiệm vụ để lấy mã khác.

Đề trắc nghiệm liên quan:

Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 14: Sql – Ngôn Ngữ Truy Vấn Có Cấu Trúc
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 20: Thực Hành Bài Toán Tìm Kiếm
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 20: Thực Hành Tạo Lập Các Bảng Có Khóa Ngoài
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 26: Công Cụ Chỉnh Màu Sắc Và Công Cụ Chọn
Đề Trắc Nghiệm Tin Học 11 (Kết Nối Tri Thức) Bài 31: Thực Hành Tạo Phim Hoạt Hình

Đề 01

Đề 02

Đề 03

Đề 04

Đề 05

Đề 06

Đề 07

Đề 08

Đề 09

Đề 10

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quảbạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Đề trắc nghiệm liên quan:

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha

Bạn ơi!!! Để xem được kết quả
bạn vui lòng làm nhiệm vụ nhỏ xíu này nha