[Lecture 7] 점근(asymptotic) 표기법/ Big-O 표기법

#Big-O 표기법

점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.

 

대표적으로 다음의 세 가지 표기법이 있다.

• 대문자 O 표기법
  • 알고리즘의 상한 및 상한은 필요한 시간의 가장 많은 양(최악의 경우 성능)으로 정의된다.
    빅 오 표기법은 점근적 상한을 설명하는 데 사용된다.
    
    수학적으로, 만약 f(n)가 알고리즘의 실행 시간을 설명한다면, f(n)는 O(g(n)이고, 양의 상수 C가 존재하고 n이 존재한다면, 모든 n >= n0에 대해 0 <= f(n) <= Cg(n)이다.
    n = 상한에 함수를 제공하는 데 사용된다.
    함수가 O(n)이면 자동으로 O(n^2)가 된다.
• 대문자 오메가(Ω) 표기법
  • 알고리즘의 하한과 하한은 필요한 최소 시간(가능한 가장 효율적인 방법, 즉 최선의 경우)으로 정의된다.
    O 표기법이 점근적 상한을 제공하는 것처럼, Ω 표기법은 점근적 하한을 제공한다.
    f(n)가 알고리즘의 실행 시간을 정의하도록 하자;
    모든 n > = n0에 대해 0 < = Cg(n) < = f(n)이 되도록 양의 상수 C와 (n0)가 존재한다면 f(n)는 Ω(g(n)이라고 한다
    n = 함수의 하한을 지정하는 데 사용됨
    함수가 Ω(n-제곱)이면 자동으로 Ω(n)이 된다.
• 대문자 세타(Θ) 표기법
  • 대문자 세타는 알고리즘이 취할 수 있는 가장 tight한 bound로 정의된다. 여기서 가장 tight한 bound는 알고리즘이 취할 수 있는 모든 최악의 경우 중 최고이다
    
    f(n)가 알고리즘의 실행 시간을 정의하도록 하자.
    f(n)가 O(g(n))이고 f(n)가 Ω(g(n))이면 f(n)는 Φ(g(n)라고 한다.
    
    수학적으로는,
    
    0 <= f(n) <= C1g(n) for n > = n0
    0 <= C2g(n) <= f(n) for n > = n0
    
    두 방정식을 합치면 다음과 같다:
    
    0 <= C2g(n) <= f(n) <= C1g(n) for n > = n0
    
    이 방정식은 단순히 양의 상수 C1과 C2가 존재한다는 것을 의미하며, 따라서 f(n)는 C2 g(n)와 C1 g(n) 사이에 끼어있다.
  • 그 외에
    • 소문자 o 표기법
    • 소문자 오메가(ω) 표기법 등등이 있다

이 중 압도적으로 많이 쓰이는 것이 대문자 O 표기법으로, 란다우 표기법이라고도 한다.

특히, 알고리즘의 복잡도를 나타내는 용어로는 "계산 복잡도 이론" 또는 "시간복잡도"로 대문자 O 표기법이 일반적으로 사용된다.

점근 표기법: Wikipedia / 나무위키

#Big-O Analysis

정의: f(n)와 g(n)가 n의 음이 아닌 함수라고 가정하자. 그런 다음 우리는 모든 n > N, f(n) ≤ Cg(n)에 대해 상수 C > 0과 N > 0이 있다면 f(n)가 O(g(n)라고 말한다.

 

Big-O는 n의 충분히 큰 값에 대해 함수의 성장률에 대한 상한을 나타낸다

 

위의 정의에 따르면, 함수 f가 함수 g의 big-O임을 증명하려면 부등식이 유지되는 특정 상수 C와 N을 찾아야 한다(부등식이 실제로 유지된다는 것을 보여준다)

#Big-O 예시

다음 함수를 한번 보자:

우리는 위 함수를 보고 다음을 짐작할 수 있다:

우리는 induction / 귀납법을 통해 쉽게 추측을 검증할 수 있었다: n = 2이면 T(2) = 20 미만인 17이므로 n = 2이면 추측이 유효하다. 일부 n ≤ 2, T(n) ≤ 5n2라고 가정하자. 그러면:

따라서, 수학적 귀납법에 의해, 모든 n ≥ 2에 대해 T(n) ≤ 5n2이다. 따라서, 정의에 따르면, T(n)는 O(n^2)이다.

 

위의 예시에서 "처음부터 어떻게 추측을 할 수 있을까?" 라고 생각이 들 수 있다. 다음 분석을 한번 보자

중간 단계는 괜찮아 보이는데, n ≤ n^2이면 n^2로 치환되기 때문에 적어도 5가 추가되므로 2를 빼면 더 큰 값이 된다

#성장률

이 Big-O 예시로 인해 우리는 무엇을 알 수 있을까? 입력 크기를 두 배로 늘리면 다음 함수가 어떻게 되는지 생각해 보자:

따라서 T(n)의 증가율에는 직관적인 한계가 있다. 알고리즘에 대한 입력 크기를 두 배로 늘리면 작업 수가 최대 4배까지 증가할 수 있다

#Big-O Theorems

다음의 모든 정리에 대해, f(n)가 n의 음이 아닌 함수이고 K가 임의의 양의 상수라고 가정하자.

 

• Theorem 1: K는 O(1)
• Theorem 2: 다항식은 O(n의 최대 거듭제곱을 포함하는 항)이다

• Theorem 3: K*f(n)는 O(f(n)이다. [즉, 상수 계수가 떨어질 수 있다, reflexivity]
  • g(n) = 7n^4 는 O(n^4)이다
• Theorem 4: 만약 f(n)가 O(g(n)이고 g(n)가 O(h(n))라면, f(n)는 O(h(n)이다. [transitivity]
  • f(n) = 7n^4 + 3n^2 + 5n + 100은 O(n^4)이다
• Theorem 5: 다음의 각 함수들은 후속 함수들의 Big-O이다:

• Theorem 6: 일반적으로, f(n)는 f(n)의 지배적인 항의 Big-O이며, 여기서 "지배적인"은 일반적으로 정리 5로부터 결정될 수 있다

Theorem 7: 임의의 기저 b에 대하여, logb(n)는 O(log(n))이다.

#Big-Omega / Big-Ω

Big-O 외에도, 우리는 함수의 성장에 대한 하한을 찾을 수 있다:

 

정의: f(n)와 g(n)가 n의 음이 아닌 함수라고 가정하자. 그런 다음 우리는 모든 n > N, f(n) ≥ Cg(n)에 대해 상수 C > 0과 N > 0이 존재한다면 f(n)는 Ω(g(n)이라고 말한다.

 

Big-Ω는 n의 충분히 큰 값에 대해 함수의 성장률에 대한 하한을 나타낸다.

#Big-O와 Big-Ω의 만남

위에 예제로 나온 함수를 다시 보자:

우리는 앞서 T(n)이 O(n^2)라는 결론을 내렸고, 실제로 T(n) <= 5n^2는 n > = 2이다.
T(n)가 Ω(n^2)임을 보여주는 것도 쉽다. 실제로 n > = 0이면 T(n) > = 2n^2이다.

 

아래 그래프를 한번 보자:
함수 T(n)는 n = 2 이상의 상한과 하한 사이에서 "안정적"이며, 상한과 하한은 모두 동일한 기본 함수 n^2에 의존한다

아래 그래프는 또 다른 Big-Ω를 나타내는 그래프이다

#Big-Theta / Big-Θ

마지막으로, 기본적으로 동일한 속도로 증가하는 두 가지 함수 있을 수 있다.

 

정의: f(n)와 g(n)가 n의 음이 아닌 함수라고 가정하자. 그렇다면 우리는 f(n)가 O(g(n))이고 f(n)가 Ω(g(n)이라면 f(n)가 Θ(g(n)이라고 말한다.

 

대안: f(n)와 g(n)가 n의 음이 아닌 함수라고 가정하자. 그러면 우리는 모든 n > N에 대해 C1g(n) ≤ f(n) ≤ C2g(n) ≤ C2g(n)인 상수 C1 > 0, C2 > 0이 존재한다면 f(n)는 θ(g(n)라고 말한다.

 

만약 f가 Θ(g)라면, 어느 시점부터 f는 g의 한 배수로 아래에 경계를 두고 g의 다른 배수로 위에 경계를 둔다(그리고 그 반대의 경우도 마찬가지이다. 그래서, 매우 기본적인 의미에서 f와 g는 같은 속도로 성장한다.

#Big-O와 Big-Ω의 만남

위에 예제로 나온 함수를 다시 보자:

T(n)는 O(n^2)이고 Ω(n^2)이다.

그렇기 때문에, T(n)는 n^2이 성장하는 것과 같은 방식으로 성장한다

 

아래 그래프는 또 다른 Big-Θ를 나타내는 그래프이다

#Order and Limits

함수의 순서를 결정하는 작업은 다음과 같은 결과로 상당히 단순화된다

정리7은 이 정리8을 사용해 쉽게 증명할 수 있다

마지막 항은 유한하고 양수이므로, logb(n)는 정리 8에 의해 Θ(log(n))이다.

 

Corollary: 위의 한계가 0이면 f(n)는 O(g(n))이고, 한계가 ∞이면 f(n)는 Ω(g(n))이다.

 

정리 8의 반대(converse)는 거짓이다. 그러나 다음을 증명할 수 있다

많은 Big-O 정리는 Big-Θ에 대한 진술로 강화될 수 있다.

 

정리 10: 만약 K > 0이 상수라면, K는 Θ(1)이다.

 

정리 11: 다항식은 Θ(n의 최대 거듭제곱)이다.

 

증명: 차수 k의 다항식을 가정하자. 그러면 다음이 있다

이제 함수가 음수가 아니라고 가정하기 때문에 ak > 0이다. 따라서 정리 8에 의해 다항식은 Θ(n^k)이다

 

정리 3, 6, 7은 비슷하게 확장될 수 있다.

 

정리 12: K*f(n)는 Θ(f(n)이다. [즉, 상수 계수를 없앨 수 있다.]

 

정리 13: 일반적으로, f(n)는 f(n)의 지배적인 항의 Big-Θ이며, 여기서 "지배적인"은 일반적으로 정리 5로부터 결정될 수 있다.

 

정리 14: 임의의 기저 b에 대하여, logb(n)는 Θ(log(n))이다

#Strict Comparisons 

편의상, 다음을 가정하자

 

f가 O(g)이지만 f가 Θ(g)가 아닌 경우에만 f는 엄격하게 O(g)이다

 

f가 Ω(g)이지만 f가 Θ(g)이 아닌 경우에만 f는 엄격하게 Ω(g)이다

 

예를 들어, n log n은 다음과 같은 이유로 정리 8과 그 결과에 의해 엄밀하게 O(n^2)이다:

Big-Θ는 동치 관계(Equivalence Relation)이다

 

정리 15: 만약 f(n)가 Θ(f(n))라면. [reflexivity]

정리 16: 만약 f(n)가 Θ(g(n))라면, g(n)는 Θ(f(n))이다. [symmetry]

정리 17: 만약 f(n)가 Θ(g(n))이고 g(n)가 Θ(h(n))라면, f(n)는 Θ(h(n)이다. [transitivity]

 

정리 15-17에 따르면, π는 양의 값 함수 집합에 대한 동치 관계이다. 동치 등급은 근본적으로 다른 성장률을 나타낸다. 복잡도 함수가 동일한 클래스에 속하는 알고리즘은 본질적으로 성능이 동일하다(실제에서는 중요하지 않은 상수 배수까지).

#알고리즘 분석에 응용

예시 1: 복잡도 함수를 갖는 알고리즘

이 있다. 이 함수는 정리 10에 의해 Θ(n^2)

 

예시 2: 복잡도 함수를 갖는 알고리즘

은 정의 5에 의해 O(n log(n)) 이다.

 

또한, 이 알고리즘은 다음과 같이 정리 8에 의해 Θ(n log(n))가 될 수 있다

대부분의 일반적인 복잡도 함수의 경우, 주어진 정리를 사용하여 big-O 및/또는 big-Θ 복잡도를 결정하는 것은 매우 쉽다

#선형 스토리지의 복잡성

N개 요소의 연속된 목록의 경우, 각 요소가 동일하게 검색 대상이 될 가능성이 있다고 가정하자

 

• 리스트가 임의로 정렬된 경우 평균 검색 비용은 Θ(N)이다
• 리스트를 정렬할 평균 검색 비용은 Θ(log N)이다. 
• 평균 랜덤 삽입 비용은 Θ(N)이다
• 꼬리 부분의 삽입은 Θ(1)이다

N개 요소의 연결된 목록의 경우, 각 요소가 동일하게 검색 대상이 될 가능성이 있다고 가정하면

 

목록 순서에 관계없이 평균 검색 비용은 Θ(N)이다
평균 임의 삽입 비용은 검색 시간을 제외하고 Θ(1)이다

#가장 일반적인 복잡성 클래스

정리 5는 다음과 같은 Big-Θ 동치 클래스의 대표들의 집합을 나열한다

대부분의 일반적인 알고리즘은 이러한 클래스 중 하나로 분류된다. 이 목록을 알면 올바른 알고리즘을 비교하고 선택하는 방법을 알 수 있다. 

#Graphical Comparison

#Lower-order Classes

n의 상당히 큰 값의 경우, 이러한 클래스만이 진정으로 실용적이며, n^2가 실용적인지는 논쟁의 여지가 있다

#정리 8의 증명

f와 g가 n의 음이 아닌 함수라고 가정하자, 또한 다음 식도 고려하자

그 다음, 한계의 정의로부터, 모든 ε  > 0에 대해 N > 0이 존재한다:

따라서 정의상 f는 Θ(g)이다