시간 복잡도와 공간 복잡도

알고리즘을 평가할 때 시간복잡도와 공간복잡도를 사용한다. 

시간 복잡도는 얼마나 오래 걸리는가, 공간 복잡도는 메모리를 얼마나 차지하는가를 평가한다.

 

두 지표 모두 데이터 크기 증가에 따른 효율성을 나타내기 위해 빅오 표기법을 사용한다.

 

---

시간 복잡도 (Time Complexity)

특정 크기의 입력을 기준으로 할 때 필요한 연산 횟수

 

실행 시간이 아니라 연산 횟수를 세는 이유는

• 모든 플랫폼에서 동일한 결과가 나오지 않는다.
• 실행 시간 측정을 위한 또다른 방법이 필요하다.

시간 복잡도는 3가지 경우로 나타낸다.

• 최선의 경우 (Best Case)
  • 빅 오메가 표기법 사용
  • 최선 시나리오로 최소한의 시간이 걸림
• 최악의 경우 (Worst Case)
  • 빅오 표기법 사용
  • 최악의 시나리오로 최대의 시간이 걸림
• 평균의 경우 (Average Case)
  • 빅세타 표기법 사용
  • 평균 시간을 나타냄

평균의 경우를 제일 많이 사용할 것 같지만!

=> 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 어려워지므로 최악의 경우로 성능을 파악한다.

 

빅오표기법 (Big-O notation)

1.  최악의 경우를 표현할 때 사용된다.
2. 상수항 같은 사소한 부분은 무시한다.
3. 가장 영향력이 큰 항 외의 다른 항은 무시한다.

 

상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수

왼쪽에서 오른쪽으로 갈수록 성능이 떨어진다.

 

 

 \(O\left ( 1 \right )\)  - 상수시간

• 입력 크기에 상관없이 일정한 연산을 수행한다.

def print_arr(arr):
	print(arr[0])

  배열의 크기가 1이든 1000이든 딱 한번만 실행된다.

 

 

\(O\left ( logN \right )\) - 로그시간

• 입력 크기(n)이 커질때 연산 횟수가 logN에 비례해서 증가한다.
• 실행을 반복할 때마다 알고리즘 탐색 범위를 1/2로 줄여나가는 이진 탐색이 대표적인 예시이다.

def example(n):
	i = 1
    while i < n:
    	print(i)
        i = i * 2

1부터 시작해 i 가 n보다 작을 때까지 두 배씩 증가하므로 실행횟수는 n에 대해 로그 시간 복잡도인 O(log n)이다.

 

 

 \(O\left ( n \right )\) -  선형시간

• 입력 크기(n)이 커질 때 연산 횟수가 n에 비례해서 증가한다.

def print_arr(arr):
	for item in arr:
		print(item)

 

 

\(O\left ( nlogN\right )\) - 선형 로그 시간

• 로그 시간으로 실행되는 알고리즘을 n번 반복하는 형태이다.
• 보통 데이터 세트를 작은 부분으로 나누고 이들을 독립적으로 처리하는 형태를 취한다.
• 병합 정렬과 같은 효율적인 정렬 알고리즘은 대부분 선형 로그 시간 복잡도를 따른다.

def test(lst):
	lst.sort()
    for item in lst:
    	print(item)

 

리스트 lst를 정렬한 후 모든 요소를 출력한다. sort() 함수는 O(N log n)의 시간 복잡도를 가지고, 각 요소를 출력하는데는 O(n) 시간이 걸린다. 전체 시간 복잡도는 O(N log n)이다.

 

 

\(O\left ( n^{2}\right )\) - 2차 시간

• 입력 크기(n)이 커질때 연산횟수가 제곱에 정비례해서 증가한다.
• 삽입 정렬이나 버블 정렬같은 정렬 알고리즘의 대부분 2차 시간 복잡도를 따른다.

numbers = [1,2,3,4,5]
for i in numbers:
	for j in numbers:
    	x = i * j
        print(x)

numbers 리스트에 들어있는 숫자를 서로 곱해 변수에 저장한 후 출력한다.

여기서 입력크기는 리스트의 크기이고 두 번 중첩된 for 문을 통해 곱셈과 출력을 n*n 번 반복한다.

 

 

그렇다면 반복문의 개수가 따라 시간 복잡도가 어떻게 증가할까?

• 반복문이 나열된다면
  • 반복문이 순차적으로 실행되므로 
  • 시간 복잡도는 O(N) + O(N) = O(N)이 된다.
• 중첩 반복문이라면
  • 내부 반복문이 외부 반복문의 실행 횟수만큼 반복되므로
  • 2중 중첩시 : O(N * N) = O(N^2),     3중 중첩시: O(N*N*N) = O(N^3)이 된다.

 

리스트 메소드의 시간 복잡도

리스트 메소드	시간 복잡도
append()	O(1)
insert()	O(n)
pop()	O(1)
remove()	O(n)
sort()	O(N log n )
delete()	O(n)
len()	O(1)
list[a:b] (슬라이싱)	O(n)

 

 

---

공간복잡도(Space Complexity)

알고리즘에서 사용하는 메모리의 양

• 공간 복잡도 또한 빅오표기법을 사용한다.
• 많은 데이터를 다루는 경우 공간 복잡도가 커지게 되면 프로그램이 메모리에 아예 올라가지 않아 실행할 수 없다.

 

공간복잡도 예제

#팩토리얼 1

def factorial(n):
	fac = 1
    for index in range ( 2, n+1 ):
    	fac = fac + index
    return fac

• n! 팩토리얼 예제
  • n! = 1 x  2 x 3 x ... n
•  n의 값에 상관없이 변수 n, fac, index 만 필요함
• 공간 복잡도 O(1)

 

# 팩토리얼 2

def factorial(n):
	if n > 1:
    	return n * factorial(n-1)
    else:
    	return 1

• 재귀함수를 사용했으므로 n에 따라 변수 n이 n개 만들어지게 됨
• 공간 복잡도는 O(n)

팩토리얼을 계산하는 코드인데 1번은 공간 복잡도가 O(1)이고, 2번은 공간 복잡도가 O(n)이다.

같은 기능을 하는 코드를 작성하더라도 어떤 함수를 사용하는지에 따라 효율적인 코드, 비효율적인 코드가 구분된다.