0. 대표적인 복잡도 카테고리

• 아래로 갈수록 성능이 최악이다.
• 그림에는 없지만 theta(n^n)의 성능이 가장 안 좋다.

---

1. Big O 빅오표기법

• 정의: 점근적 상한(Asymptotic Upper Bound)
  주어진 복잡도 함수 f(n)에 대해서 g(n)∈O(f(n))이면 다음을 만족한다.

  For a given complexity function f(n), O(f(n)) is the set of complexity
  functions g(n) for which there exists some positive real constant c and
  some nonnegative integer N such that, for all n ≤ N,

  g(n) ≤ c × f(n).

  어떤 양의 실수 c와 음이 아닌 정수 N이 존재할 때, 모든 n ≥ N에 대하여
  g(n) ≤ c × f(n) 이 성립한다.

g(n)은 f(n)의 큰 오(Big O)라고 읽는다.

어떤 함수 g(n)이 O(n^2)에 속한다는 말의 의미는

• 함수 g(n)이 궁극에 가서는(=임의의 N값보다 큰 값에 대해서는) 어떤 2차 함수 cn^2보다 작은 값을 가지게 된다는 것을 뜻한다.
• g(n)의 그래프는 어떤 2차 함수 cn^2보다 궁극적으로 좋다(=기울기가 낮다)고 할 수 있다.

어떤 알고리즘의 시간복잡도가 O(f(n))이라면

• 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 늦어도 f(n)은 된다. 다시 말해, f(n)보다 더 느릴 수는 없다.(= f(n)보다 빠르다. f(n)이 상한이다.)

---

2. Ω (Omega) 표기법

• 정의: 점근적 하한(Asymptotic Lower Bound)
  주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ Ω(f(n))이면 다음을 만족한다.

  For a given complexity function f(n), Ω(f(n)) is the set of complexity functions g(n) for which there exists some positive real constant c and some nonnegative integer N such that, for all n ≥ N,

  g(n) ≥ c × f(n)

  어떤 양의 실수 c, 음이 아닌 정수 N이 있을 때, 모든 n ≥ N에 대하여
  g(n) ≥ c × f(n)이 성립한다.

g(n)은 f(n)의 오메가라고 읽는다.

어떤 함수 g(n)이 Ω(n^2)에 속한다는 말의 의미는

• 함수 g(n)이 궁극에 가서는(=임의의 N값보다 큰 값에 대해서는) 어떤 2차 함수 cn^2보다 큰 값을 가지게 된다는 것을 뜻한다.
• g(n)의 그래프는 어떤 2차 함수 cn^2보다 궁극적으로 나쁘다(=기울기가 높다)고 할 수 있다.

어떤 알고리즘의 시간복잡도가 Ω(f(n))이라면

• 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 빨라도 f(n)이다. 다시 말해, f(n)보다 더 빠를 수는 없다.(= f(n)보다 느리다. f(n)이 하한이다.)

---

3. Θ (theta) 표기법

• 정의: Asymptotic Tight Bound

  For a given complexity function f(n),

  Θ(f(n)) = O(f(n)) ∩ Ω(f(n))

  This means that (f(n)) is the set of complexity functions g(n) for whichthere exists some positive real constant c and d and some nonnegativeinteger N such that, for all n ≥ N,

  c × f(n) ≤ g(n) ≤ d × f(n).

---

4. small o / little o 표기법

• 정의: 작은 o

  For a given complexity function f(n), o(f(n)) is the set of complexity functions g(n) satisfying the following: For every positive real constant c there exists a nonnegative integer N such that, for all n ≥ N,

  g(n) ≤ c × f(n).

  모든 양의 실수 c, 음이 아닌 정수 N이 있을 때, 모든 n ≥ N에 대하여
  g(n) ≤ c × f(n)이 성립한다.

• g(n) ∈ o(f(n))은 g(n)이 궁극적으로 f(n)보다 훨씬 좋다는 의미이다.

Big O와의 차이점

• Big o
  실수 c > 0 중에서 하나만 성립해도 된다.
• small o
  모든 실수 c > 0에 대하여 성립해야 한다.