[Python] 알고리즘 개념2 추가 퀴즈 - Big-O 표기법 심화

 

📌 퀴즈 개요

이 퀴즈는 "Big-O 표기법 심화" 개념을 더욱 깊이 이해하기 위한 추가 문제들로 구성되어 있습니다. 각 문제의 답을 선택하거나 직접 작성해보세요!

---

 

 

🧩 1. 개념 이해 문제

 

❓ 문제 1

Big-O 표기법에서 O(n log n) 시간복잡도를 가지는 알고리즘은?

1. 이진 탐색
2. 퀵 정렬
3. 선형 탐색
4. 버블 정렬

 

❓ 문제 2

Big-O 표기법에서 가장 효율적인 알고리즘은?

1. O(n)
2. O(n log n)
3. O(n^2)
4. O(1)

---

 

 

🧩 2. 실전 문제

 

❓ 문제 3

다음 코드에서 log_search(n) 함수의 시간복잡도는?

def log_search(n):
    while n > 1:
        n = n // 2

1. O(n)
2. O(n log n)
3. O(log n)
4. O(1)

 

❓ 문제 4

다음 코드의 시간복잡도를 올바르게 분석한 것은?

for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)

1. O(n)
2. O(n^3)
3. O(n log n)
4. O(2^n)

 

❓ 문제 5

Big-O 표기법에서 상수를 무시하는 이유는?

1. 상수는 실행 시간에 영향을 주지 않기 때문이다.
2. 입력 크기가 커질수록 상수의 영향이 작아지기 때문이다.
3. Big-O 표기법은 정확한 실행 시간을 측정하는 것이 목적이기 때문이다.
4. 컴퓨터 성능에 따라 상수 값이 달라지기 때문이다.

---

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🏆 정답 및 해설

✅ 문제 1 정답: 2)

• 퀵 정렬은 평균적으로 O(n log n)의 시간복잡도를 가집니다.

✅ 문제 2 정답: 4)

• O(1)은 입력 크기에 상관없이 항상 일정한 실행 시간을 가지므로 가장 효율적입니다.

✅ 문제 3 정답: 3)

while n > 1:
    n = n // 2  # 매 반복마다 n이 절반으로 줄어들므로 O(log n)

✅ 문제 4 정답: 2)

for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)  # 세 번의 반복문 중첩 → O(n^3)

✅ 문제 5 정답: 2)

• 입력 크기가 커질수록 상수의 영향이 작아지므로 무시합니다.

---