주니어 백엔드 개발자 인터뷰

# 시간복잡도와 공간복잡도

# 시간 복잡도란 무엇인가요?

시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킵니다. 어떠한 알고리즘의 로직이 '얼마나 오랜시간'이 걸리는지를 나타내는데 쓰이며 보통 빅오 표기법으로 나타냅니다.

# 빅오 표기법(Big-O Notation)이란 무엇인가요?

  • 최악의 경우를 생각하는 표기법입니다. (아무리 오래 걸려도 이 시간 안에는 끝날것이다.)

다른 표기법

최상의 경우 : 오메가 표기법(Big-Ω Notation)
평균의 경우 : 세타 표기법(Big-θ Notation)

  • 입력범위 n을 기준으로 로직이 몇번 반복되는 지 나타내는 것으로, 가장 오래걸리는 항의 상수인자를 제외한 값으로 나타냅니다.
  • O()로 표현합니다.
  • 예시 (시간복잡도 : O(n^))
for(int i=0; i<10; i++){
    for(int j=0; j<n; j++) {
        for(int k=0; k<n; k++){
            System.out.println("hello");  //10n^
        }    
    }
}

for(int i=0; i<n; i++){
    System.out.println("hi");  //n
}
  • 대표적인 Big-O의 복잡도를 나타내는 표
    빅오

# 시간 복잡도를 사용하는 이유는 무엇인가요?

시간 복잡도가 작을수록 프로그램이 실행되는데 걸리는 시간이 짧아집니다.
따라서, 효율적인 코드로 개선하는 데 사용하는 척도가 됩니다.

# 시간 복잡도를 줄이는 방법은 무엇이 있나요?

  • 반복문의 횟수를 줄입니다.
  • 자료구조와 알고리즘을 적절하게 이용합니다.

자료구조 시간복잡도 비교

자료구조

# 공간 복잡도란 무엇인가요?

공간 복잡도란 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말합니다.

  • 공간복잡도 예시
int a[n];   //O(n)
        
int b = 10; //O(1)
        
int self_recursion(int n)   //O(n)
{
    if(n > 1) return n * self_recursion(n - 1);
    else return 1;
}

# 공간 복잡도를 줄이는 방법은 무엇이 있나요?

배열의 크기, 동적할당이나 재귀호출의 정도가 공간 복잡도에 영향을 미칩니다.
따라서, 재귀함수를 자제하거나, 고정 공간보다는 가변 공간을 사용하면 공간 복잡도를 최소화 할 수 있습니다.

# 참고자료

출처: 주홍철.면접을 위한 CS 전공지식 노트.서울:길벗,2022.
출처: https://blog.chulgil.me/algorithm/

← 배열 (Array & ArrayList) →