[알고리즘] 알고리즘, 시간복잡도, 공간복잡도, 점근표기법

시간복잡도

입력값과 문제를 해결하는데 걸리는 시간과의 상관관계

중첩for문시 N^2의 수식을 가짐 따라서 중첩문이 생기면 시간이 기하급수적으로 늘어난다는것 참고

공간복잡도

입력값과 문제를 해결하는데 걸리는 공간과의 상관관계

Array 길이, 값을 넣어줄 각 변수들을 계산하여 카운트, 단 재할당하는 중복되는 변수의 공간은 카운트하지않는다.

->만약 공간복잡도가 그저 숫사상수로 29,30 이라면 공간복잡도 보단 시간복잡도로 비교하여 알고리즘의 효율성을 생각한다.따라서 시간복잡도를 더 신경써야한다.

보통 시간복잡도의 효율성을 비교할때 예를들어 3N+106 이라는 시간이 걸린다면 상수 106은 비교대상에서 제외하고 3N 부분만 계산한다 N에 따라 걸리는시간이 무한대로 커지기때문에 106은 비교대상에 넣지 않는것이다.

 

Ex) 52N+104 vs 3N+106 vs N^2

N의 길이	52N+104	3N+106	N^2
1	156	109	1
10	624	136	100
100	5304	406	10000
1000	52104	3106	1000000
10000	520104	30106	100000000

 

점근표기법

알고리즘 성능을 수학적으로 표현하는 방법. 알고리즘의 ‘효율성’을 평가하는 방법이다.

Asymptotic notation은 어떤 함수의 증가 양상을 다른함수와 비교로 표현하는 수론과 해석학의 방법이다.

점근이라하면 어떤 함수나 값이 다른 값에 무한히 다가가는 상태를 뜻한다.

위에서 이 함수는 N정도의 시간과 공간이 걸리겠구나 라고 분석했던것이 점근 표기법의 일종이다.

 

종류

빅오(Big-O)표기법- 최악의 성능이 나올때 어느정도의 연산량이 걸릴것인지 표기

빅오메가(Big-Ω)- 최선의 성능이 나올때 어느정도의 연산량이 걸릴것인지 표기

 

예를들어 빅오 표기법으로 표시하면 O(N), 빅 오메가 표기법으로 표시하면 Ω(1)의 시간 복잡도를 가진 알고리즘이다 라고 표현할수있다.

예를들어 배열에 대해서 해당 알고리즘의 시간복잡도가 N만큼 시간이 걸린다고 하더래도 배열의 위치에 따라 1번에 끝날수도 있고 맨뒤까지 계산하여 N만큼 걸릴수도 있게된다. 이처럼 알고리즘의 성능은 항상 같지 않고 달라질수있다. 

좋을때	1
안좋을때	N

즉, 위의 경우 빅오표기법으로 표시하면 O(N) ->최악,

오메가 표기법으로 표시하면 Ω(1)->최선 의 복잡도를 가진 알고리즘이다 라고 말할수있다.

결론

최선의 경우의 가능성은 적을뿐더러 우리는 항상 최악의 경우를 생각하여 빅오표기법으로 비교분석한다.