시간 복잡도, 공간 복잡도

빅오 표기법이란

코드를 분류하거나 비교할 수 있도록 하는 시스템

알고리즘 성능을 분석하기 위해 빅오 표기법 사용

 

빅오란

입력된 내용이 늘어날수록 알고리즘에 실행시간이 어떻게 변하는지 설명하는 공식적인 방법

입력의 크기와 실행시간의 관계

시간, 공간 복잡도에 대한 이해가 가능함(정확도 보단 전체적인 추세를 가늠함)

 

빅오의 특징

산수는 상수 시간 -> O(1) 

변수 배정(할당)은 상수 시간 -> O(1)

배열 엘리먼트를 인덱스로 접근하면 상수 시간 -> O(1)

객체를 키를 사용하여 접근하면 상수 시간 -> O(1)

루프는 루프의 길이(n) * 루프 안 연산 -> O(n)

중첩 루프라면 -> O(n^2)

 

빅오 표기

O(1) : 상수 시간

입력 크기(n)에 상관없이 일정한 연산을 수행

 

O(logn) : 로그 시간

입력 크기(n)가 커질수록 logn만큼 비례해서 연산을 수행(크기가 커질수록 크기가 작아짐)

 

O(n) : 선형 시간

입력 크기(n)가 커질수록 n에 비례해서 연산이 증가(일정하게 증가하는 모습)

 

O(n^2) : 2차 시간

입력 크기(n)가 커질수록 n^2 만큼 연산이 증가(크기가 커질수록 ^2만큼 매우 크게 증가)

 

O(2^n) : 지수 시간

입력 크기(n)가 커질수록 2^n만큼 연산이 증가(크기가 커질수록 2^n만큼 지수가 커지기 때문에 말도 안 되게 증가)

 

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

오른쪽으로 갈수록 시간 복잡도가 큰(수행 시간이 긴) 알고리즘

 

 

시간 복잡도

알고리즘의 수행 시간(연산)을 평가

ex) 입력 값이 커질수록 알고리즘 실행 시간이 달라짐

하드웨어, 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가함

 

시간 복잡도의 3가지 경우 => 최선의 경우 / 최악의 경우 / 평균적인 경우

알고리즘이 복잡할수록 최악의 경우로 알고리즘 성능을 파악함

 

연산 횟수가 다항식으로 표현될 경우, 최고차 항만 나타내고, 최고차 항의 계수를 제외시켜 나타냄

T(n) = n2 + 2n + 1 = O(n2) : 최고차 항만 나타냄.

T(n) = 2n = O(n) : 최고차 항의 계수는 제외함.

 

 

공간 복잡도

알고리즘 수행에 필요한 메모리 양을 평가

보조 공간 + 입력 공간

ex) 입력 값이 커질수록 알고리즘이 차지하는 공간(메모리)이 달라짐

 

보조 공간 : 입력을 제외하고, 알고리즘 자체가 필요로 하는 공간

 

boolean, number, undefined, null은 불변의 공간, 입력 크기에 상관없이 같은 메모리 사용 O(1)

문자는 O(n)의 공간을 필요

reference 타입 : 배열, 객체는 O(n)의 공간 필요