[Algorithm] 복잡도

 

 

 

알고리즘 복잡도

알고리즘이 얼마나 많은 리소스를 사용하는지 측정하는 방법

 

 

시간 복잡도

알고리즘이 문제를 해결하는데 얼마나 많은 시간이 필요한지를 측정

입력 크기에 따른 연산 횟수로 표현하며 이 연산 횟수가 증가하는 속도를 나타내는 것이 중요

 

 

공간 복잡도

알고리즘이 문제를 해결하는데 얼마나 많은 메모리가 필요한지를 측정

입력 데이터 외에 추가적으로 필요한 공간을 어떻게 만들어줄지

 

 

Big O notation

시간 및 공간 복잡도를 표현하기 위한 수학 표기법

O()는 최악의 경우(worst case scenario)에서 알고리즘의 성능을 의미, 입력크기가 n이라고 할 때 함수의 상한선(upper bound)를 제공

 

O(1)

상수 시간(constant time) : 입력 크기와 무관하게 항상 동일한 시간이 걸림

1

O(n)

선형 시간(linear time) : 입력 크기에 비례해서 처리시간 증가

100

O(n^2)

제곱 시간(quadratic time) : 입력 크기 제곱에 비례해서 처리시간 증가

10000

O(log n)

로그 시간(logarithmic time) : 로그함수같이 초기에 빠르게 감소하다가 점차 감소 속도가 줄어듦

10

O(n log n)

선형 로그 시간(linear logarithmic time) : 선형시간과 로그시간의 곱 만큼 처리시간 증가

1000

 

 

효율 좋은거 -> 나쁜거

x 데이터의양 // y time