[Algorithm] 시간 복잡도와 공간 복잡도

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다.

 

시간복잡도

문제를 해결하는 데 걸리는 시간과 입력의 함수 관계.

어떠한 알고리즘 로직이 얼마나 오랜 시간 걸리는지를 나타내는 데 쓰인다.

보통 빅오 표기법으로 나타낸다.

이는 효율적인 코드로 개선하는데 쓰이는 척도가 된다.

 

빅오 표기법

입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것.

가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤 것이다.

 

속도 비교

출처 : 면접을 위한 CS 전공지식 노트(2022)

O(1)과 O(n^2)는 입력 크기 n이 커질 수록 차이가 많이 나게 된다.

 

공간 복잡도

프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양.

정적 변수로 선언된 것 말고도 동적으로 공간을 계속해서 필요로 하는 경우도 포함된다.

 

자료 구조에서 시간 복잡도

출처 : 면접을 위한 CS 전공지식 노트(2022)

위 그림은 자료 구조에서 평균 시간 복잡도를 나타낸 것이다.

출처 : 면접을 위한 CS 전공지식 노트(2022)

위 그림은 자료 구조에서 최악의 경우 시간 복잡도를 나타낸 것이다.

 

참조

• 주홍철, 면접을 위한 CS 전공지식 노트, 길벗(2022)