차수

1.4 차수

• 알고리즘에서 포인트는 상수무시하며, 가장 큰 차수만 신경쓰면된다.

복잡도 함수의 증가율

O (큰 빅O)

(=상한값, 가장 나빳을 때)

O 표기법

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

• 그 함수는 궁극에 가서는 이차함수 cn^2 보다는 작은 값을 가지게 된다는 것을 뜨함. (그래프 상에서는 아래에 위치한다)
• 결론적으로, 그 함수 g(n)은 어떤 2차 함수 cn^2 보다는 궁극적으로 좋다 (기울기가 낮다)

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

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

(1)

Ω 표기법

(=빅O에 반대)

• 정의 : 점근적 하한

  

  
  

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

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

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

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

예시

예시 2

(오메가=가장 좋았을 때임으로)