algorithm - 표기법 - 알고리즘 시간복잡도 개념




빅 O와 리틀 O 표기법의 차이점 (2)

Big-O는 < ~와 같이 little-o입니다. Big-O는 포괄적 인 상한선이며 little-o는 엄격한 상한선입니다.

예를 들어, 함수 f(n) = 3n 은 다음과 같습니다.

  • O(n²) , o(n²)O(n)
  • O(lg n) , o(lg n) 또는 o(n)

마찬가지로 숫자 1 은 다음과 같습니다.

  • ≤ 2 , < 2 , ≤ 1
  • ≤ 0 , < 0 또는 < 1 아님

다음은 일반적인 아이디어를 보여주는 표입니다.

(참고 :이 테이블은 좋은 가이드이지만 제한 정의는 정상 한계 대신 상한 한도로 해야합니다. 예를 들어 3 + (n mod 2) 는 3에서 4 사이에서 영원히 진동합니다 3 + (n mod 2) O(1) 그것은 정상적인 제한이없는데도 불구하고 여전히 lim sup 가 있기 때문에 : 4.)

Big-O 표기법이 점근 적 비교로 변환되는 방법을 암기하는 것이 좋습니다. 비교는 기억하기 쉽지만 n O (1) = P와 같은 것을 말할 수 없으므로 유연성이 떨어집니다.

Big-O 표기 O(n)Little-O 표기 o(n) 의 차이점은 무엇입니까?


f ∈ O (g)는 본질적으로

적어도 하나 의 상수 k > 0 선택에 대해, 0 <= f (x) <= kg (x)가 모든 x> a에 대해 유지되는 상수 a를 찾을 수 있습니다.

O (g)는이 조건이 만족하는 모든 함수의 집합입니다.

f ∈ O (g)는 본질적으로

상수 k > 0의 모든 선택에 대해, 부등식 0 <= f (x) <kg (x)가 모든 x> a에 대해 유지되는 상수 a를 찾을 수 있습니다.

다시 한번, o (g)는 집합임을 주목하십시오.

Big-O에서는, 최소 x를 넘어서서 불평등이 성립하는 특정 승수 k 를 찾는 것만으로 충분합니다.

리틀 오 (Little-o)는 음수 또는 0이 아닌 한 k를 작게 만들지도 불평등이 유지되는 최소 x 가 있어야합니다.

이 두 가지 모두 상한을 설명하지만 다소 직관적으로는 그다지 강력하지는 않습니다. f ∈ O (g)보다 f ≥ o (g) 일 때 f와 g의 성장률 사이에 훨씬 큰 차이가있다.

불일치의 한 예가 다음과 같다. f ∈ O (f)는 참이지만 f ∈ o (f)는 거짓이다. 따라서 Big-O는 "f ∈ O (g)는 f의 점근 적 성장이 g의 속도보다 빠르다는 것을 의미한다"반면 "f ∈ o (g)는 f의 점근 적 성장이 g보다 엄격하게 느린 것을 의미한다". <=< 와 같습니다.

보다 구체적으로, g (x)의 값이 f (x)의 값의 상수 배이면, f∈O (g)는 참이다. 따라서 big-O 표기법으로 작업 할 때 상수를 삭제할 수 있습니다.

그러나 f ∈ O (g)가 참이 되려면 g의 공식에 더 높은 x의 을 포함해야하므로 f (x)와 g (x) 사이의 상대적인 분리는 실제로 x가 커질수록 커야합니다.

순전히 수학 예제를 사용하려면 (알고리즘을 참조하는 것이 아니라) :

다음은 Big-O에 해당하지만 little-o를 사용하는 경우에는 사실이 아닙니다.

  • x² ∈ O (x²)
  • x² ∈ O (x² + x)
  • x² ∈ O (200 * x²)

다음은 little-o에 해당합니다.

  • x² ∈ o (x3)
  • x² ∈ o (x!)
  • ln (x) ∈ o (x)

f ∈ O (g)이면 f ∈ O (g)임을 의미한다. 예를 들어 x² ∈ O (x3)이므로 x² ∈ O (x3), (다시 O는 <= 와 o를 < 로 생각한다)





little-o