Analysis of Algorithms(5) : Theory of Algorithms

Types of analyses

• 알고리즘을 분석하기 위해서는 크게 세 가지로 나눠서 보는 것 같습니다.
  • Best case : 처리하기 가장 좋은 형태의 input이 주어진 경우
  • Worst case : 처리하기 가장 어려운 형태의 input이 주어진 경우
  • Average case : random한 input이 주어지는 경우

 

Theory of algorithms

• 일반적으로는 주어진 문제를 해결하기 위한 최적의 알고리즘을 찾기 위해서, 우선 어려운 문제를 기준으로 접근해야 합니다.
  즉, 최악의 상황을 가정하고 이를 개선하는 방식으로 접근하는 것이죠.

 

Commonly-used notations in the theory of algorithms

• 일반적으로 우리에게 잘 알려진 것은 중간의 빅오 표기법이지만 세 개를 설명하고 있습니다.
  • Big Theta : 알고리즘을 구분하는데 사용되는 표기법입니다.
  • Big Oh : 상한선을 표현합니다. 즉 최악의 상황을 뜻합니다.
  • Big Omega : 하한선을 표현합니다. 반대로 최선의 상황을 뜻합니다.

 

Theory of algorithms: example 1

 

Commonly-used notations

• 정확한 의미에 따라 빅오 표기법은 '최적의 모델'을 뜻하는 것이 아닙니다.
  오히려 최악의 상황, 다른 말로는 아무리 안 좋아도 이것 이상 시간이 오래 걸리지는 않아라는 것을 뜻하죠.
• 그래서 이 수업에서는 최적의 알고리즘을 뜻할 수 있는 Tilde-notation을 사용합니다.

 

Quiz

• 빅오 표기법에 대해 기존에 알고 있던 대로라면 정답은 3번이 되었을 것입니다.
  (저는 보자마자 3번이네 하고 틀렸습니다 ㅎㅎ...)
• 하지만 빅오 표기법은 '상한선', 즉 최악의 경우를 나타내는 것 뿐이라서 위 모든 복잡도를 표함합니다.
  즉, n^3 이하의 시간 복잡도를 가지는 모든 알고리즘을 O(N^3)으로 표현해도 괜찮다는 것이죠 ㄷㄷ

 

 

출처: Coursera, Algorithms, Part 1, Princeton University