차수

ChoRong0824·2022년 9월 21일
0

Algorithm

목록 보기
3/19

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)


(2)


(3)


Ω 표기법

(=빅O에 반대)

  • 정의 : 점근적 하한


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

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

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

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

예시

예시 2

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

profile
정진, "어제보다 더 나은 오늘이 되자"

0개의 댓글