복잡도란

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

시간복잡도

• 특정한크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미
• 알고리즘을 위해 필요한 연산의 횟수
• 시간 복잡도를 표현할 때는 빅오(big-O)표기법을 사용

  • 간단하게 가장 빠르게 증가하는 항만을 고려하는 표기법

    빅오 표기법	명칭
    $O(1)$	상수 시간(Constant time)
    $O(logN)$	로그 시간
    $O(N)$	선형 시간
    $O(NlogN)$	로그 선형 시간
    $O(N^2)$	이차 시간
    $O(N^3)$	삼차 시간
    $O(2^n)$	지수 시간

array = [1,2,3,4,5] # 5개의 데이터(N = 5)
summary = 0 		# 합계를 저장할 변수

# 모든 데이터를 하나씩 확인하며 합계를 계산
for i in array :
	summary += i
    
# 결과를 출력
print(summary)

# 결과 
15

• 본 소스코드에서 가장 영향력이 큰 부분은 N에 비례하는연산을 수행하는 반복문 부분이므로 시간 복잡도를 $O(n)$이라고 표기

array = [1,2,3,4,5] # 5개의 데이터(N = 5)

for i in array :
	for j in array :
    	temp = i * j
        print(temp)

• 이 소스코드는 데이터의 개수가 N개일 때, $O(N^2)$의 시간 복잡도를 가진다.
  2중 반복문을 이용하여 각 원소에 대하여 다른 모든 원소에 대한 곱셈 결과를 매번 출력하고 있기 때문

• 모든 2중 반복문의 시간 복잡도가 $O(N^2)0$은 아님
  따라서 소스코드를 정확히 분석한 뒤에 시간 복잡도를 계산해야 한다.

  공간 복잡도

• 얼마나 많은 메모리ㅣ를 차지하는지를 의미

• 알고리즘을 위해 필요한 메모리의 양

• 빅오 표기법 이용

• 일반적으로 메모리 사용량 기준은 MB단위로 제시된다.

출처 : 이것이 코딩테스트다 with 파이썬