Tổng hợp câu hỏi hay về big-O

Xin chào mọi người hôm nay mình sẽ mang đến cho mọi người những câu hỏi PT2 hay nhất và giải thích từ A-Z

1. Which is the big-O of the algorithm "BUBBLE SORT for sorting a Sequence of N element" in the WORST CASE?

• A. O(logN)
• B. O(N•logN)
• C. O(N)
• D. O(1)
• E. O(N^2)

Lời giải: Thuật toán sắp xếp nổi bọt là thuật toán 2 vòng lặp (n phần tử) lồng nhau nên WORST CASE là N^2 => E. O(N^2)

2. Which is the big-O of the algorithm "Finding the Maximum Element in a Sequence of N element"?

• A. O(logN)
• B. O(N•logN)
• C. O(N)
• D. O(1)
• E. O(N^2)

Lời giải: Tìm kiếm 1 phần tử trong mảng có thể phải chạy tối đa n vòng lặp để hoàn thành => C. O(N)

3. Which two of three following cases are important when evaluating the complexity of an algorithm? (Mutilchoice)

• A. Worst-case
• B. Best-case
• C. Average-case.

Lời giải: Độ phức tạp của thuật toán có liên quan có trường hợp tệ nhất và trường hợp trung bình. Best-case thường = 1 nên không ảnh hưởng tới độ phức tạp của thuật toán. Đáp án A,C

4. The big-O notation for f(x) = 4 logx + 2 is

• A. O(logx)
• B. O(x)
• C. O(1)

Lời giải: độ phức tạp của 4logx=>O(logx), 2=>O(1) mà O(logx)>O(1) nên chọn O(logx) => A

Câu 5

Lời giải