이상학의 개발블로그

[학교-알고리즘] 점근적 표기법과 시간 복잡도 본문

교육/강의

[학교-알고리즘] 점근적 표기법과 시간 복잡도

학학이 2016. 4. 14. 16:12

 Order (차수)


선형 시간 알고리즘

선형 시간 입력( 1차, n 크기). ex) 순차검색


2차 시간 알고리즘

ex) 버블 정렬( n^2 )


 An inturitive introduction to "Order"

입력의 크기가 아주 클 때, 알고리즘의 복잡도는 최고차 항에 의해 결정된다.

최고차 항이 제일 중요하다.


점근적 표기법( Asymptotic Notation)

알고리즘을 만들고 해당 알고리즘이 잘 만들었는지 평가하는 성능분석은 매우 중요하다.

해당 알고리즘이 잘 만들어진 것인지 판단할수 있는 척도가 된다. 

그러나 만약 해당 알고리즘이 문제를 해결하는 절대적 시간을 기준으로 하면 문제가 발생하는데

만약, A 알고리즘은 슈퍼컴퓨터에서 B 알고리즘은 스마트폰에서 실행한 시간을 기준으로 A 알고리즘이 더 좋다고 평가할 수 있을까?

이럴때 사용하는 것이 점근적 표기법이다. 해당 알고리즘이 주어진 데이터 크기를 기준으로 수행시간 혹은 사용 공간이 얼마나 되는지 객관적 지표를 제시할 수 있다.

일반적으로 아래의 기호로 알고리즘의 성능을 표기한다.

빅 오(  ), 오메가( ), 세타(  ) 표기법에 대해 설명한다.


빅 오 (  )

점근적 상한선을 의미한다. (Asymptotic upper bound)

새로 만든 알고리즘이 아무리 나빠도 기존 비교하는 함수와 같거나 혹은 좋다는 뜻이다.

이 말을 잘 해석하면 왜 빅 오를 많이 쓰는지 알 수 있다. 알고리즘의 수행시간은 매 시간 그리고 하드웨어에 따라서 달라진다.

만약 알고리즘의 수행시간 중 어쩌다 나온 최고 빠른 시간을 기준으로 하고 '내가 만든 알고리즘이 90만큼 빨라(100점 만점)' 라고 하면

90점은 어쩌다 나온거지 대부분 60점, 70점에서 머물 것이다.

그래서 만약 '내가 만든 알고리즘은 아무리 나빠도 70점은 넘어 그 밑으로는 안나와' 라고 하면 

어떤 경우는 80점, 90점을 기대할 수 있을 것이며 또한 아무리 나쁜 경우라도 70점은 넘는다는 객관적 지표를 줄 수 있다. 

그래서 알고리즘 비교에 빅 오를 많이 쓴다.


오메가( )

점근적 하한선을 의미한다. (Asymptotic lower bound)

새로 만든 알고리즘이 아무리 빨라도 기존 비교하는 함수와 같거나 혹은 좋지 않다는 뜻이다.

위의 빅 오의 개념을 이해했다면 느낌이 올 것이다. 빅 오의 반대이다.


세타(  ) 

점근적 상한과 하한의 교집합을 의미한다. (Asymptotic tighter bound)

새로 만든 알고리즘이 아무리 나쁘거나 좋더라도 기존의 비교하는 함수의 범위 안에 존재한다는 뜻이다.


빅 오? 최악의 경우??

학교에서 빅 오에 대해서 배울 때 최악의 경우를 '빅 오'라고 하면서 시간 복잡도를 나타낼 때 많이 사용한다고 했다.

왜 최악의 경우를 사용할까? 뭔가 확 느낌이 오지 않았는데, 다른 강의를 들으면서 왜 최악의 경우를 사용하는지 알았다.

위에 썼지만 다시 말하면 ' 내 알고리즘은 아무리 느리게 결과가 나와도 70점은 할 수 있어' 이런 느낌이다.

학교 시험에서 맨날 60점 70점 맞는 친구가 한번 100점 맞았다고 그 친구의 실력이 100점이라고 판단 할 수는 없다.

그래도 이 친구는 60점 밑으로는 내려간 적이 없어 ' 아무리 못해도 60점은 받는 실력이구나' 라고는 판단할 수 있다.

이래서 빅 오를 사용하는 것 같다. 알고리즘은 절대적 시간으로 평가 할 수 없으니까. 왜? 하드웨어에 영향을 많이 받기 때문에!


Common Complexity Categories ( 시간 복잡도 순위)



Comments