복잡도

출처 : 나동빈 님 유튜브

ㅁ 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

ㅁ 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

ㅁ Big - O 표기법이란?

가장 빠르게 증가하는 항만을 고려한 시간복잡도 표기법

ex1) 연산 횟수가 4n^2 + 5n + 6 일 경우, 

O(N^3)과 같이 표기

 

ex2) 다음과 같은 경우, 

box = [1,2,3,4,5]

for i in box:
	for j in box:
    	cell = i * j
        print( cell )

O(N^2)와 같이 표기

 

ㅁ 시간제한이 1초인 문제를 만났을 때,

N의 범위가 500인 경우 : 시간 복잡도가 O(N^3) 

N의 범위가 2000인 경우 : 시간 복잡도가 O(N^2)

N의 범위가 100000인 경우 : 시간 복잡도가 O(NlogN)

N의 범위가 10,000,000인 경우 : 시간 복잡도가 O(N)