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

 

 

📌 퀴즈 개요

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

---

 

 

🧩 1. 개념 이해 문제

 

❓ 문제 1

Big-O 표기법에서 가장 효율적인 알고리즘 복잡도는?

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

 

❓ 문제 2

다음 코드의 시간복잡도는?

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

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

---

 

 

🧩 2. 실전 문제

 

❓ 문제 3

다음 코드에서 arr.sort()의 시간복잡도는?

arr = [3, 1, 4, 1, 5, 9]
arr.sort()

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

 

❓ 문제 4

다음 코드의 실행 시간복잡도는?

for i in range(n):
    if arr[i] == target:
        break

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

 

❓ 문제 5

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

1. 상수는 실행 시간에 영향을 주지 않기 때문이다.
2. 입력 크기가 커질수록 차이가 없어지기 때문이다.
3. 상수는 언어마다 다르게 동작하기 때문이다.
4. 코드 실행 시간이 항상 일정하기 때문이다.

---

 

 

 

 

 

 

 

 

🏆 정답 및 해설

✅ 문제 1 정답: 2)

• O(log n)은 이진 탐색과 같은 알고리즘에서 사용되며 매우 효율적입니다.

✅ 문제 2 정답: 3)

for i in range(n):
    for j in range(n):
        print(i, j)  # 총 n * n 실행되므로 O(n^2)

• 중첩 반복문이므로 O(n^2)입니다.

✅ 문제 3 정답: 2)

arr.sort()  # Timsort 알고리즘 사용 → O(n log n)

• Python의 sort()는 Timsort를 사용하며, 최적 시간복잡도는 O(n log n)입니다.

✅ 문제 4 정답: 2)

for i in range(n):
    if arr[i] == target:
        break  # 최악의 경우 n번 실행되므로 O(n)

• 최악의 경우 배열의 마지막까지 탐색해야 하므로 O(n)입니다.

✅ 문제 5 정답: 2)

• Big-O 표기법은 입력 크기가 매우 커졌을 때의 경향을 분석하므로, 상수 계수는 무시됩니다.

---