점근적 분석

Asymptotic Notations

Big-O

Big-O는 함수 증가율의 상한선(upper-bound)를 나타내는 수학적 표기이다. 이는 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용되며 가장 많이 사용되는 표기법이기도 하다. Big-O 표기법은 알고리즘의 효율성을 상한선 기준으로 표현한다 하였는데, 이 뜻은 알고리즘의 최악의 경우를 포함한 모든 경우를 고려한 값을 살펴볼 수 있다는 것이다.

Big-O Notation

Big-O는 수학적으로 \(f(n) = O(g(n))\)으로 표현하며 뜻은 다음과 같다.

• 알고리즘의 복잡도는 \(O(g(n))\)으로 표현하며, 충분히 큰 입력의 크기 n에 대해서 알고리즘의 시간 또는 공간복잡도가 \(g(n)\)의 최대만큼 빠르게 증가한다는 것을 의미한다.
• 즉, \(n_{0} > 0\)인 상수 \(n\)에 대해 상수인자 \(c\)가 존재하며, 이는 알고리즘의 복잡도가 \(c \cdot g(n)\)보다 작거나 같도록 한다.
• 즉, 이는 \(f(n)\)은 집합 \(O(g(n))\)에 속하는 것으로 이해할 수 있다.

\(f(n), g(n)\)의 뜻

• \(f(n)\)은 본인 알고리즘의 시간 효율성(running time)을 의미한다.
• \(g(n)\)은 복잡성의 일반적인 형태를 나타내는 함수이다.
• \(f(n)\)은 \(g(n)\)의 big-oh라고 읽으면 된다.

위 내용들을 설명한 것이 아래의 그래프이다.

표현식

\[O(g(n)) = \lbrace f(n) \space \vert \space \exists{c>0},\space n_{0}>0 \space \text{s.t.} \space \forall{n} \ge n_{0},\space f(n) \le c \cdot g(n) \rbrace \]

• \(O(g(n))\) = { \(f(n)\): there exist positive constants \(c\) and \(n0\) such that \(0 ≤ f(n) ≤ cg(n)\) for all \(n ≥ n0\) }
• 모든 \(n \ge n_{0}\)에 대해 양수\(c\)와 \(n_{0}\)이 존재하면 다음과 같은 \( f(n) \le c \cdot g(n) \)식을 \(f(n)\)이라고 할 수 있다.

예시

\(f(n)\)과 \(g(n)\)을 다음과 같이 정의한다.

• \( f(n) = n^2 + 2n + 3 \)
• \( g(n) = n^2 \)
• 그리고 충분히 큰 값인 상수 \(n\)과 \(c\)가 있다.
• \( f(n) \le c \cdot g(n) \)에 \(f(n)\)과 \(g(n)\)에 값을 대입하여 \( n^2 + 2n + 3 \le c \cdot n^2 \)으로 작성하며, 이를 만족하는 \(c\)값이 존재하기에 \(f(n)\)은 \(O(n^2)\)으로 나타낼 수 있다.
• \(n_{0}\)의 우측 모든 값에서 \(f(n)\)그래프 위에 \(c \cdot g(n)\)값들이 존재할 수 있도록 하는 \(c\)와 \(n_0\)가 존재한다고 해석한다.

---

\[\]

출처

https://www.programiz.com/dsa/asymptotic-notations
https://noahlogs.tistory.com/27
https://johngrib.github.io/wiki/big-O-notation/