알고리즘을 분석한다는 것은, 얻은 결과가 맞는 것인지, 어느 정도의 시간을 소모하는지, 어느 정도 최적화가 되어 있는지의 3가지 여부를 확인하는 것으로 이루어진다. 어느 정도의 시간을 소모하는지는 Big-O 표기를 사용하며, 주로 최악의 경우와 평균 수행 시간을 분석하는 것으로 이루어진다. 시간 복잡도 외에도, 메모리와 같은 리소스의 사용량도 Big-O 표기를 이용하여 나타낼 수 있다.
최적화에 대한 분석은 어떻게 이루어지는가? 먼저, 어떤 문제를 해결하기 위해서, 주어진 문제가 필요한 최소한의 연산의 필요한지 파악할 필요가 있다. 즉, Big-O 표기가 '이것보다 더 복잡하거나 시간을 소모하지 않는다'라는 의미라면, 문제의 최적의 답을 얻는 과정은 '최소한 이것 이상의 연산을 필요로 한다'라는, 최소로 필요한 연산의 정도를 파악해야 한다는 것이다. 이 최소의 연산이 어느 정도인지 파악되었다면, 주어진 알고리즘과 비교해서 이 알고리즘이 얼마나 최적화 되어 있는지 비교가 가능하다.
즉, '이것보다 더 복잡하지 않다'라는 최악의 경우는 상한(upper bound)이라고 하며, '최소한 이것 이상의 연산이나 복잡도가 필요하다'의 경우를 하한(lower bound)이라고 한다. 알고리즘의 복잡도를 이야기할 때는 상한의 개념을 사용하지만, 문제의 복잡도의 경우에는 하한의 개념이 더 적절하다. 다시 말해, 문제는 일정 정도 이하로 더 간단해질 수 없다. Big-Ο 방식은 상한의 개념이며, 문제의 복잡도를 나타내는 Ω(오메가)는 하한의 개념이다.
Ο(n), Θ(n), Ω(n)은 모두 함수의 집합을 의미한다. Ο(n)은, n보다 같거나 더 작은 속도로 증가하는 함수의 집합을 이야기하며, Θ(n)은 같은 속도로 증가하는 함수의 집합을 의미한다. Ω(n)는, n보다 같거나 더 빠른 속도로 증가하는 함수의 집합을 의미한다.
최적화에 대한 분석은 어떻게 이루어지는가? 먼저, 어떤 문제를 해결하기 위해서, 주어진 문제가 필요한 최소한의 연산의 필요한지 파악할 필요가 있다. 즉, Big-O 표기가 '이것보다 더 복잡하거나 시간을 소모하지 않는다'라는 의미라면, 문제의 최적의 답을 얻는 과정은 '최소한 이것 이상의 연산을 필요로 한다'라는, 최소로 필요한 연산의 정도를 파악해야 한다는 것이다. 이 최소의 연산이 어느 정도인지 파악되었다면, 주어진 알고리즘과 비교해서 이 알고리즘이 얼마나 최적화 되어 있는지 비교가 가능하다.
즉, '이것보다 더 복잡하지 않다'라는 최악의 경우는 상한(upper bound)이라고 하며, '최소한 이것 이상의 연산이나 복잡도가 필요하다'의 경우를 하한(lower bound)이라고 한다. 알고리즘의 복잡도를 이야기할 때는 상한의 개념을 사용하지만, 문제의 복잡도의 경우에는 하한의 개념이 더 적절하다. 다시 말해, 문제는 일정 정도 이하로 더 간단해질 수 없다. Big-Ο 방식은 상한의 개념이며, 문제의 복잡도를 나타내는 Ω(오메가)는 하한의 개념이다.
Ο(n), Θ(n), Ω(n)은 모두 함수의 집합을 의미한다. Ο(n)은, n보다 같거나 더 작은 속도로 증가하는 함수의 집합을 이야기하며, Θ(n)은 같은 속도로 증가하는 함수의 집합을 의미한다. Ω(n)는, n보다 같거나 더 빠른 속도로 증가하는 함수의 집합을 의미한다.