📚 상식 퀴즈 해설

Q. 알고리즘 복잡도의 "O(n)" 표기법은 무엇을 의미하나요?

빅오 표기법 O(n)은 선형 시간 복잡도(linear time complexity)를 의미합니다. 입력 데이터의 크기 n에 비례하여 실행 시간이 증가한다는 뜻입니다. 예를 들어 배열에서 최댓값을 찾으려면 모든 요소를 한 번씩 확인해야 하므로 O(n)입니다. 데이터가 2배가 되면 시간도 대략 2배가 됩니다. 빅오 표기법은 알고리즘의 효율성을 표현하는 수학적 표기법으로, 최악의 경우 성능을 나타냅니다. 주요 복잡도를 효율 순으로 정리하면 O(1) 상수 시간 > O(log n) 로그 시간 > O(n) 선형 시간 > O(n log n) > O(n²) 제곱 시간 > O(2ⁿ) 지수 시간입니다. 구글이 10억 개의 웹 페이지를 빠르게 검색할 수 있는 것도 O(n²)이 아닌 O(n log n) 이하의 효율적인 알고리즘을 사용하기 때문입니다.