차수(Order)

  • 알고즘이 얼마나 복잡한지를 정량적으로 다루기 위한 개념
  • 항시 어떤 알고리즘이 좋다고 이야기할 수 없다.
  • 어떤 알고리즘이 효율적인지 척도가 필요하다.
  • 일반적으로 입력 크기 n이 매우 크다고 가정한다.

Ο(f(n)) - At most as fast as f

Ω(f(n)) - At least as fast as f

Θ(f(n)) - At the rate of f

Big-O 표기법

  • 정의 : 점근적 상한(Asymptotic Upper Bound)
    • 주어진 복잡도 함수 f(n)에 대해서 g(n)∈ O(f(n))이면 다음을 만족한다.
    • n ≥ N인 모든 정수 n에 대해서 g(n) ≤ c ×f(n)이 성립하는 실수 c > 0 와 음이 아닌 정수 N이 존재한다
  • g(n) ∈ O(f(n))
    • g(n)은 f(n)의 큰 O이다.
  • 어떤 함수 g(n)이 O(n^2)에 속한다는 말은
    • 함수 g(n)는 궁극에 가서는 (즉, 어떤 임의의 N값보다 큰 값에 대해서는 어떤 2차함수 cn^2보다는 작은 값을 가지게 된다는 것을 뜻한다
    • 다시 말해서, 그 함수 g(n)은 어떤 2차함수 cn^2보다는 궁극적으로 좋다고 말할 수 있다.
  • 어떤 알고리즘의 시간 복잡도가 O(f(n))이라면
    • 입력의 크기 n에 대해서 이 알고리즘의 수행시간은 아무리 느려고 cf(n) 보다는 빠르다.
  • n^2 + 10n ∈ O(n^2) (예제 1.9)
    1. n ≥ 10인 모든 정수 n에 대해서 n^2 + 10n ≤ 2n^2이 성립한다. 그러므로, c=2와 N=10을 선택하면 Big O 정의에 의해서 n^2 + 10n ∈ O(n^2)이라고 결론지을 수 있다.
    2. n≥1인 모든 정수 n에 대해서 n^2 + 10n ≤ n^2 + 10n^2 = 11n^2이 성힙한다. 그러므로, c =11와 N=1을 선택하면 Big O의 정의에 의해서 n^2 + 10n ∈ O(n^2)이라고 결론지을 수 있다.

💡 Big O를 보이는데 단 한가지 해답이 있는 것이 아님

Omega(Ω) 표기법

  • 정의 : 점근적 하한(Asymptotic Lower Bound)
    • 주어진 복잡도 함수 f(n)에 대해서 g(n) ∈ Ω(f(n))
  • 어떤 함수 g(n)이 Ω(n^2)에 속한다는 말은
    • 그 함수는 궁극에 가서는 (즉 어떤 임의의 N값보다 큰 값에 대해서는) 어떤 2차 함수 cn^2의 값보다는 큰 값을 가지게 된다는 것을 의미
  • 5n^2 ∈ Ω(n^2) (예제 1.12)

Theta(Θ) 표기법

  • 정의 : (Asymptotic Tight Bound)

Small o(o) 표기법

  • 정의 : 복잡도 함수 f(n)에 대해서 o(f(n))은 모든 양의 실수 c에 대해서 n ≥ N인 모든 n에 대해서 다음 부등식을 만족하는 음이 아닌 정수 N이 존재하는 모든 복잡도 함수 g(n)의 집합이다.

💡 g(n)≤c×f(n)차

차수의 특성

g(n) ∈ O(f(n)) iff f(n)∈Ω(g(n))

g(n) ∈ Θ(f(n)) iff f(n) ∈ Θ(g(n))