자료구조

시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)

견오수 2023. 1. 31. 11:19
728x90

코딩테스트 문제를 풀 때 시간 복잡도를 계산하여 수행 시간을 짐작하여 문제를 해결한다.

대학교 때 자료구조 시간 때 배운 시간복잡도와 공간 복잡도를 복습하여 정리하였다.

 

1. 시간 복잡도(Time Complexity) 및 공간 복잡도(Space Complexity)  정의

 

복잡도는 알고즘의 성능을 나타내는 척도이다.

 

  • 시간 복잡도 : 알고리즘의 수행시간을 평가한다. 즉, 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다.
  • 공간 복잡도 : 알고리즘 수행에 필요한 메모리 양을 평가한다.  특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.

복잡도를 측정함으로써 시간 복잡도에서는 알고리즘을 의해 필요한 연산의 횟수를, 공간 복잡도에서는 메모리의 양을 계산할 수 있다. 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

 

 

2. 시간 복잡도(Time Complexity)

 

알고리즘의 수행 시간을 분석할 때 시간 복잡도를 사용한다. 

 

기본 연산의 예시는 다음과 같다.

  • 데이터 입출력 - copy, move
  • 산술 연산 - add, multiply 
  • 제어 연산 - if, while

 

3. 시간 복잡도 표기법

 

  • 빅 오메가 표기법   →  최선의 시나리오로(Best Case) 최소 이만한 시간이 걸린다.
  • 빅 세타 표기법  →  평균 시간(Average Case)을 나타낸다.
  • 빅 오 표기법 →   최악의 시나리오(Best Case)로 아무리 오래걸려도 이 시간보다 덜 걸린다.

시간 복잡도를 표현할 때는 최악의 경우로 알고리즘을 성능 평가한다.  →   빅오Big-O 표기법

 

 

4. 시간 복잡도 계산

 

  • 시간 복잡도는 일반적으로 빅오 표기법을 사용한다.
  • 연산 횟수가 다항식으로 포현될 경우, 최고차항의 계수를 제외시켜 나타낸다.

 

O(1) - 상수시간(Constant time)

 

  • O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
  • 입력값의 크기와 관계 없이, 즉시 출력 값을 얻어낼 수 있다.
function(num):
	print(num)

 

O(logN) - 로그시간(Logarithmic time)

 

  • 입력값이 커질 때 연산 횟수가 logN에 비례하여 증가하여 시간 복잡도는 O(logN)이다.
  • 예를 들어, up & down 게임은 숫자를 제시할 때마다 경우의 수가 절반씩 줄어들기 때문에 O(logN)이다.
for i in raneg(0,8,2):
	print(i)

 

O(n) - 선형시간(Linear time)

 

  • 입력값이 커질 때 연산 횟수가 n에 비례하여 증가해서 시간 복잡도는 O(n)이다.
  • 연산 횟수가 선형적으로 증가한다고 이해하면 된다.
for i in range(0, 8):
	print(i)

 

 

O(n^2) - 2차 시간(Linear time)

 

  • 입력값이 커질 때 연산 횟수가 n^2에 비례해서 증가하여 시간 복잡도는 O(n^2)이다.
  • 예를 들어, for문이 2번 중첩된  경우이다.

 

for i in range(0, 8):
	for j in range(0, 8):
		print(i)
		print(j)

 

O(2^n) - 지수 시간(Exponential time)

 

  • 입력값이 커질 때 연산 횟수가 2^n에 비례해서 증가하여 시간 복잡도는  O(2^n)이다.
  • 예를 들어 파보나치 수를 구하는 경우이다.
function(n):
 	if (n <= 1) 
 		return n;
  	return function(n-1) + function(n-2);

 

 

 

왼쪽으로 갈수록 시간 복잡도가 큰 알고리즘이다.

 

 

 

 

참고 

나동빈 - 이것이 코딩테스트다.
https://www.bigocheatsheet.com/
https://velog.io/@dvot007/%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84Big-O-%ED%91%9C%EA%B8%B0%EB%B2%95-%EA%B3%84%EC%82%B0
https://yoongrammer.tistory.com/79
728x90