[CS지식] 복잡도

[면접을 위한 CS 전공지식 노트] 도서를 읽고 정리한 글 입니다.
티스토리에 정리했던 내용을 벨로그로 옮겼어요!
https://kkomyoung.tistory.com/2

1. 복잡도

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

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)로 나뉜다.

1-1. 점근 표기법

복잡도는 아래와 같은 점근 표기법으로 표기할 수 있다.

이 중 최악의 경우까지 고려하는 빅오 표기법이 가장 효율적이므로 많이 사용된다.

• Big-O(빅-오) 표기법 / O(N) : 알고리즘 최악의 실행시간 표기
• Big-Ω(빅-오메가) 표기법 / Ω(N) : 알고리즘 최상의 실행시간 표기
• Bid-θ(빅-세타) 표기법 / Θ(N) : 알고리즘 평균 싱행시간 표기

1-2. 빅오 표기법

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

빅오 표기법의 특징

시간복잡도에 미미한 영향을 주는 것들은 배제하고 표기된다.

• 상수항 무시 : O(N+7) → O(N)
• 계수 무시 : O(3N) → O(N)
• 최고차항만 표기 : O(N² + 2N + 1) → O(N²)

빅오 표기법의 종류

실행속도 (빠름 < 느림) : O(1) < O(log N) < O(N) < O(N log N) < O(N²) < O(2ⁿ)

2. 시간 복잡도

어떠한 알고리즘을 처리할 때 얼마나 오랜 시간이 걸리는지를 나타내기 위해 사용한다.

이때 시간은 절대적인 시간이 아닌, 알고리즘을 처리하기 위해 필요한 연산의 횟수를 기준으로 표시한다.

2-1. 예제

시간 복잡도 : O(1)

a = 2
b = 5
print(a+b)

# 입력값과 상관없이 한번 실행되어 O(1)이 된다.

시간 복잡도 : O(N)

array = [6,2,8,5,3]
sum = 0

for i in array:
	sum += i
for j in array:
	sum += j
    
print(sum)

# 입력값 n이 커지면 연산수도 같은 비율로 비례하여 증가한다.
# 병렬된 반복문이 2개이기 때문에 연산수는 2n이 되지만, 빅오 표기법에 의해 상수를 제외하고 O(n)이 된다.

시간복잡도 : O(N²)

array = [1,4,7,5,8]

for i in array:
	for j in array:
    	temp = i*j
        print(temp)
        
        
# 입력값 n이 증가함에 따라 연산수가 n의 제곱수의 비율로 증가한다.
# 반복문이 중첩되어 있는 경우 곱셈으로 계산하여 (n*n = n^2) O(n²)이 된다.

3. 공간 복잡도

알고리즘을 수행하기 위해 필요한 저장공간의 양을 말한다.

공간 복잡도 또한 빅오 표기법을 사용하여 표현한다.

3-1. 예제

시간 복잡도 : O(N)

array = [3, 2, 5, 6, 10 ...]
result = 0

for i in array:
	result += i
    
print(result)

"""
int형 리스트 array = 4byte * n
int형 변수 result = 4byte
for문의 int형 변수 i = 4byte
총 4n + 8의 메모리가 사용됐으며 빅오 표기법에 의하여 공간 복잡도는 O(N)이 된다.
"""