면접을 위한 CS 전공지식 노트 - 시간 복잡도

책 '면접을 위한 CS 전공지식 노트'를 읽고 정리한 내용입니다.

빅오 표기법

• 시간 복잡도란 ‘문제를 해결하는 데 걸리는 시간과 입력의 함수 관계’를 가리킨다.
• 쉽게 말해 어떤 알고리즘이 ‘얼마나 오랜 시간’이 걸리는지를 나타내는데 쓰이는 것이다.
• 이 시간은 보통 빅오 표기법으로 나타낸다.
• 빅오 표기법이란 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타낸느 것이다.
• 아래 코드의 시간 복잡도를 빅오 표기법으로 나타내면 O(n2)이 된다.

for (int i = 0; i < 10; i++) {
		for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
						if (true) count << k << '\\n';
				}
		}
}

for (int i = 0; i < n; i++) {
		if (true) count << i << '\\n';
}

시간 복잡도의 존재 이유

• 효율적인 코드로 개선하는 데 쓰이는 척도가 된다.
• 예를 들어 O(n2)의 시간 복잡도를 가지고 9초가 걸린다고 했을 때 이를 O(n)의 시간 복잡도를 가지는 알고리즘으로 개선한다면 3초가 걸리게 된다.
• O(n2)보다는 O(n)이 O(n)보다는 O(1)을 지향해야 한다. (O(n2) → O(n) → O(1))

공간 복잡도

• 공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다.
• 정적 변수로 선언된 것 말고도 동적으로 재귀 함수로 인해 계속해서 필요로 할 경우도 포함된다.

자료 구조의 시간 복잡도

정렬의 시간 복잡도