[면접 준비] BigO 설명하기

학습 키워드: BigO, time complexity

 

2024-07-31 면접 카타 질문

BigO에 대해 설명해주세요:

 프로그래밍에서 BigO는 시간복잡도 및 공간복잡도를 나타내는 표기법입니다. 시간 복잡도는 코드가 실행되고 완료되기까지 걸리는 시간으로 입력 값의 길이나 크기에 따라 프로그램이 실행되는 시간이 얼만큼 변화하는지를 말합니다. 일반적으로 worst case scenario를 가정하여 작성하게 되는데, 예를 들어 2D 배열에서 원하는 값을 찾는 함수가 있을 때, 최악의 케이스에서 배열의 모든 index를 탐색하게 된다면 이 함수의 BigO는 O(n^2)으로 표기합니다. Binary Search Tree 처럼 worst case scenario가 주어진 input을 모두 탐색하지 않는 경우 O(log n) 으로 표기하며, n만큼 탐색하고 난 뒤부터 log n이 되는 O(n log n) 같은 케이스 또한 존재합니다. 공간복잡도를 표현할 때는 Input의 크기와 알고리즘을 처리하는데 쓰이는 추가 공간인 Auxiliary space로 나뉘며, 둘을 합쳐서 공간 복잡도라고 말합니다.

 

 BigO는 함수의 실행 시간이나 메모리 공간 사용량에 대해 일일이 설명하지 않고도 간단하고 이해하기 쉽게 표현할 수 있다는 장점으로 인해 알고리즘 성능 비교나 최적화를 진행할 때 유용하게 사용됩니다.

 

 

--