[알고리즘] 복잡도란 무엇인가(시간복잡도, 공간복잡도, 빅오 표기법)

복잡도란

• 알고리즘의 성능을 나타내는 척도
• 크게 시간 복잡도, 공간 복잡도로 나눌 수 있다.

시간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다.
• 알고리즘을 위해 필요한 연산의 횟수
• 복잡도를 표현하기 위해 빅오 표기법을 사용한다.
• 최악의 경우에 대한 연산 횟수가 가장 중요하다.
• N의 범위에 따라 시간 복잡도를 계산하고 사용할 수 있는 알고리즘을 선택하는 방법도 있다.

빅오 표기법	표현
O(1)	상수
O(logN)	로그
O(N)	선형
O(NlogN)	로그 선형
O(N^2)	다항
O(2^n)	지수

 

 

공간 복잡도

• 특정한 크기의 입력에 대해 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다.
• 알고리즘을 위해 필요한 메모리의 양