Complexity 복잡도 !

복잡도란 ?

복잡도는 알고리즘의 성능을 나타내는 척도

• 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지
• 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지

 

알고리즘을 위해 필요한 연산의 횟수는 시간 복잡도와 연관있으며

알고리즘을 위해 필요한 메모리의 양은 공강 복잡도와 연관있다 !

---

시간복잡도

알고리즘 문제에 명시된 시간제한과 연관되며 작성한 프로그램이

모든 입력을 받아 이를 처리하고 실행 결과를 출력하는데까지 걸리는 시간을 의미한다

 

시간복잡도 표현

빅오 표기법 (Big - O) 를 사용한다

가장 빠르게 증가하는 항만을 고려하는 표기법이다

 

아래 예제의 연산 횟수는 데이터의 개수 n 에 비례한다

소스 코드에서 가장 영향력이 큰 부분은 n 에 비례하는 반복문이므로 

따라서 시간 복잡도는 O(N) 이다

array = [3, 5, 1, 2, 4] # n = 5
summary = 0

# 모든 데이터를 하나씩 확인하며 합계 계산
for i in array:
	summary += i

print(summary)

시간복잡도 고수들의 방법 ..

문제의 조건을 확인하며 얼마나 효율적인 알고리즘을 작성해야하는지를 파악하기도 한다

시간 제한이 1초인 문제에 대해서

• N의 범위가 500 인 경우 : 시간복잡도가 O(N³)인
• N의 범위가 2,000 인 경우 : 시간복잡도가 O(N²)인
• N의 범위가 100,000 인 경우 : 시간복잡도가 O(NlogN)인
• N의 범위가 10,000,000 인 경우 : 시간잡도가 O(N)인

 

알고리즘을 설계하여 문제를 푼다고한다 !

---

공간복잡도

시간복잡도를 표기했던 것처럼 빅오 표기법을 사용한다

메모리 사용량 기준은 MB단위로 제시된다

 

코딩테스트의 대부분 문제는 리스트를 사용해서 풀어야한다

보통 메모리 사용량을  128 ~512MB 정도로 제한한다

일반적인 경우 데이터의 개수가 1,000만 단위가 넘어가지 않도록 설계한다

 

100만 개 이상의 데이터가 들어가는 리스트를 선언할 경우 잘못 설계한것이다 ..

---

참고

나동빈, 이것이 취업을 위한 코딩 테스트다 with 파이썬, 한빛미디어 (2021)