스터디룸

읽기 전..

• 향후 상기한 제목으로 작성될 게시물은 모두 Geeks for Geeks Algorithms 페이지들을 번역 및 작성자의 해석대로 정리할 예정입니다.
• 정확한 이론 베이스는 당연히 없고 학습한 내용을 정리할 목적으로 가볍게 작성하였기 때문에 오개념이 있을 수 있으니 혹시 페이지를 방문하신 분들께서는 참고바랍니다.
• 개념을 바로잡기 위한 지적은 언제나 환영이니 부탁드립니다.

Asymptotic Notations(점근적 표기법)

점근적 분석으로 도출된 알고리즘의 복잡도를 표현하기 위해 Θ(세타), Ω(오메가), $O$(빅 오) 3가지 표기법이 있다.

1. Θ Notation

   

   Theta 표기법은 분석하고자 하는 함수를 상계과 하계로 종속시킨다. 위 그래프처럼 함수 $f(n)$을 분석한다고 가정해보자.

   Theta 표기를 가장 간단히 하는 방법은 가장 높은 차수의 변수만 남기고 모두 버린 뒤 해당 변수의 계수도 1로 바꾸면 된다. 이를 테면 $f(n)=3n^3+6n^2+6000$의 Theta 표기법은 $3n^3$이하 변수를 모두 탈락시킨 뒤 계수를 모두 버린 $n^3$이 되므로 완성된 Theta 표기법은 Θ($n^3$)​이다. 가장 높은 차수만을 남기는 이유는 Θ($n^3$)이 Θ($n^2$)보다 커지는 $n_0$지점이 반드시 존재하므로 Θ($n^2$)의 계수가 얼마나 크건 상관없이 누락해도 무방하기 때문이다.

   이를 정리하면 Θ$(g(n))$은 $n_0$이후의 모든 $n$에 대해 $0 \leq c_1\cdot g(n) \leq f(n) \leq c_2\cdot g(n)$를 만족시킬 수 있는 $c_1, c_2, n_0$이 존재하는 모든 함수 $f(n)$의 집합을 의미한다. 즉, $f(n)$이 Θ($g(n)$)에 속한다면 $n \geq n_0$을 만족하는 모든 $n$값에 대해 $f(n)$값은 항상 $c_1 \cdot g(n)$과 $c_2 \cdot g(n)$ 사이에 존재하기 때문에 Θ표기법은 주어진 알고리즘이 아무리 좋거나 나빠지더라도 비교하는 함수 범위 안에 있음을 의미한다.

   참고사항으로 위 정의에 따라 Theta 표기법 상 $n_0 \leq n$을 만족하는 모든 $n$에 대해 $f(n)$값은 반드시 $f(n_0)$보다 커야한다.

2. Big O Notation

   

   Big O 표기법은 알고리즘의 상계만을 다룬다. 예를 들어 Insertion 정렬의 경우 최상의 경우에 $n$만큼의 시간이 소요되고 최악의 경우 $n^2$만큼 소요되는데 이를 Big O 표기법으로 나타내면 $O(n^2)$이다. 그리고 Big O 표기법에 따라 최상의 경우($n$시간 소요)도 포함한다. 얼핏 Θ표기법과 차이점이 없어보이지만 Θ표기법은 최상의 경우[Θ($n$)]와 최악의 경우[Θ($n^2$)]를 따로 표기해야 한다.

   하계에 대해 고려할 필요가 없기 때문에 상계에 대한 정보만 가지고 있을 때 유용하게 사용할 수 있다. 그리고 많은 알고리즘들은 단순하게 상계에 대해 파악할 수 있기 때문에 일반적인 시간복잡도를 논할 땐 Big O 표기법을 사용한다.

   이를 정리하면 상수 $n_0$보다 큰 모든 수 $n$에 대해 $0 \leq f(n) \leq c \cdot g(n)$을 만족하는 양수의 값 $c$와 $n_0$가 존재하는 모든 함수 $f(n)$의 집합을 $O(g(n))$이라 표현할 수 있으므로 Big O 표기법은 주어진 알고리즘 $f(n)$이 아무리 나빠도 비교하는 함수 $c \cdot g(n)$보다는 같거나 좋음을 나타낸다.

3. Ω Notation

   Big O 표기법이 점근적 상계에 대한 정보만을 제공했다면 Ω표기법은 점근적 하계만을 다룬다. 그러나 점근적 하계는 최상의 케이스를 의미하므로 일반적으로 잘 쓰이지 않는다.

   

   Ω($g(n))$)은 상수 $n_0$보다 큰 모든 수 $n$에 대해 $0 \leq c \cdot g(n) \leq f(n)$을 만족하는 양수의 값 $c$와 $n_0$가 존재하는 모든 함수 $f(n)$의 집합을 의미하므로 Ω 표기법은 주어진 알고리즘 $f(n)$이 아무리 좋아도 비교하는 함수 $c \cdot g(n)$보다는 같거나 나쁨을 나타낸다.

   예를 들어, 위에서 기술하였듯이 Insertion Sort의 시간 복잡도는 최악의 경우 $n^2$이고 최상의 경우 $n$이므로 Ω 표기법으로 나타내면 Ω(n)이 된다. 하지만 우리는 알고리즘의 평균적인 상황이나 최악의 상황에서의 성능을 요구하기에 그닥 쓸모있는 정보를 제공하진 않는다.

알고리즘 문제를 해결하는 상황에선 보통 Big case를 주는 경우가 많기에 worst case를 고려하지 않으면 TLE(Time Limit Exceeded)문제가 발생한다. 그리고 input의 공간적 분포를 따졌을 때 대다수는 average case이므로 사용하고자 하는 알고리즘의 시간복잡도를 잘 따져봐야 한다.

반대로 Small case가 주어졌지만 수행시간도 극단적으로 짧게 제공된다면 asymptotic 관점에서는 느리지만 실제로는 더 빠른 알고리즘을 사용하는 융통성이 필요할지도 모르겠다. 주어진 input이 n_0보다 작다던지...

게시물 출처: Analysis of Algorithms | Set 3 (Asymptotic Notations)

읽기 전..

• 향후 상기한 제목으로 작성될 게시물은 모두 Geeks for Geeks Algorithms 페이지들을 번역 및 작성자의 해석대로 정리할 예정입니다.
• 정확한 이론 베이스는 당연히 없고 학습한 내용을 정리할 목적으로 가볍게 작성하였기 때문에 오개념이 있을 수 있으니 혹시 페이지를 방문하신 분들께서는 참고바랍니다.
• 개념을 바로잡기 위한 지적은 언제나 환영이니 부탁드립니다.

Algorithm Analysis? Performance?

흔히 알고리즘을 다룰 때 빠질 수 없는 개념은 '성능'이다. 성능이 보장되어 있어야 안정성, 보안 등 각종 이슈를 모두 해결할 수 있다. 알고리즘의 성능을 평가할 때는 단순히 '규모'에 대한 개념만 가지고 있으면 된다. 많은 양의 데이터를 정확하고 빠른 시간에 처리할 수 있는 알고리즘이 좋은 알고리즘이라고 생각하자.

단순하게 알고리즘 성능을 분석한다고 할 때 두 개의 알고리즘을 돌려서 적은 시간이 걸리는 알고리즘이 더 우수하다고 여겨진다. 그러나 적은 input부터 많은 input까지 고려하면 다음의 경우도 존재할 수 있다.

1. 일부 input에서는 1번이 우수하고 다른 input에서는 2번이 우수한 경우
2. 일부 input의 경우 어떤 기계에서는 1번이 우수하고, 다른 input의 경우 다른 기계에서는 2번이 우수한 경우

위 문제를 해결하기 위한 알고리즘 분석 개념 중 하나로 점근적 분석이 있다.

Asymptotic Analysis(점근적 분석)이란?

점근적 분석이란 알고리즘을 분석하기 위한 기법 중 하나로 input size대비 알고리즘이 처리하는 데 걸리는 시간(혹은 공간)에 대해 평가한다.

예를 들어, 빠른 머신에서 Linear Search를 수행할 때와 느린 머신에서 Binary Search를 수행할 때 일정 시점까지는 Linear Search가 빠르겠지만 input size가 점점 커질수록, 결국 Binary Search의 소요시간이 더 작아지는 시점이 온다.

• 뒤에 나오는 개념이지만 Linear Search의 시간복잡도는 n인 반면, Binary Search의 시간복잡도는 $\log n$이기 때문

그렇다고 점근적 분석이 정확한 알고리즘 성능을 제시하지는 않는다.

$1000nlog n$과 $2nlog n$은 일정범위에선 분명한 차이가 있지만 점근적 분석에 따르면 "$nlog n$"이므로 서로 동일한 성능을 가진다고 판단하는 문제가 있다.

게시물 출처: Analysis of Algorithms | Set 1 (Asymptotic Analysis)

Linear Search 알고리즘에 대해 분석하기

Linear Search 알고리즘을 적용할 때 3가지 케이스에 대해 분석하기로 한다.

def search(arr, n, x):
    for i in range(n):
        if arr[i]==x:
            return i
    return -1
#arr는 입력 list, n은 arr의 길이, x는 찾는 값

1. Worst Case

   서칭 알고리즘의 최악 케이스는 주어진 배열 내에 찾고자 하는 원소가 없어 모든 원소에 대해 탐색해야 하는 경우다. 특히, Linear Search의 경우 첫 번째 원소부터 하나씩 탐색하기 때문에 input size가 n이라면 최악의 경우의 시간복잡도는 Θ(n)이다.

2. Average Case

   일반적인 경우는 평균으로 해석하자고 가정하면 균일하게 분포된 모든 케이스에 대해 걸리는 탐색시간을 케이스의 수로 나누면 된다. 즉, 찾고자 하는 원소가 첫 번째에 위치한 경우부터 존재하지 않는 경우까지 모든 시간을 더한 뒤 경우의 수로 나눈 결과는 아래와 같다.
   $$
   \begin{align}
   Average\;Case\;Time &= \frac{\sum_{i=1}^{n+1}(\Theta(i))}{n+1}
   \\&=\frac{\Theta((n+1)\cdot(n+2)/2)}{n+1}
   \\&=\Theta(n)
   \end{align}
   $$

3. Best Case

   최상의 케이스는 찾고자 하는 원소가 첫 번째에 위치하여 한 번의 접근으로 탐색에 성공하는 경우로 시간 복잡도는 Θ(1)이다.

일반적으로 알고리즘을 분석할 땐 수행 시간의 상계(Upper bound)에 대한 정보를 제공할 수 있기에 가장 최악의 경우를 상정한다. 평균 케이스 분석은 모든 가능한 input에 대해 수학적으로 어떻게 분포되어 있는지 파악하고 있어야 하므로 잘 쓰이지 않는다.

다만 몇몇 알고리즘은 worst case와 best case 간의 소요시간이 동일한 경우가 있다. 예를 들어, Merge sort의 시간복잡도는 모든 케이스에 대해 Θ$(n\log n)$이다.

게시물 출처: Analysis of Algorithms | Set 2 (Worst, Average and Best Cases)