algorithm 예제 빅 O와 리틀 O 표기법의 차이점




알고리즘 시간복잡도 개념 (3)

나는 개념적으로 뭔가를 이해할 수 없을 때 X를 사용 하는 이유 에 대해 생각하는 것이 X를 이해하는 데 도움이된다는 것을 알게되었습니다. (당신이 시도하지 않았다고 말하면서, 나는 무대를 설정하고 있습니다.)

[당신이 알고있는 것들] 알고리즘을 분류하는 일반적인 방법은 런타임에 있습니다. 알고리즘의 큰 복잡성을 인용하면, "더 작은"함수를 가진 "더 나은"알고리즘을 꽤 잘 추정 할 수 있습니다 오! 실제 세계에서도 O (N)은 O (N²)보다 "더 우수"하며, 거대한 상수와 같은 어리석은 것들은 제외합니다.

O (N)에서 실행되는 알고리즘이 있다고 가정 해 보겠습니다. 아주 좋아, 응? 그러나 당신 (당신이 훌륭한 분인 당신)이 O ( N / loglogloglogN )에서 실행되는 알고리즘을 생각해 냈다고합시다 . 예! 그것의 더 빠름! 그러나 당신이 당신의 논문을 쓰고있을 때 당신은 바보 같은 말을 반복해서 쓰고 싶을 것입니다. 그래서 당신은 한번 쓰고, "이 글에서는 O (N)의 시간에 이전에 계산할 수있는 알고리즘 X가 실제로 o (n)에서 계산 가능하다는 것을 증명했다."라고 말할 수 있습니다.

따라서 모든 사람이 알고리즘이 더 빠름을 잘 알고 있습니다. 얼마나 많은 부분이 불분명 한 지 알지만 알고리즘은 더 빠릅니다. 이론적으로. :)

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를 < 로 생각한다)


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와 같은 것을 말할 수 없으므로 유연성이 떨어집니다.





little-o