[algorithm] Big-O와 Little-O 표기법의 차이점
Big-O 표기법 O(n)과 Little-O 표기법 의 차이점은 무엇입니까 o(n)?
답변
f ∈ O (g)는 본질적으로
들면 적어도 하나의 상수의 선택의 (K) > 0 인 경우 상수 찾을 수 예는 부등식 0은 <= F (X) <= kg (x)는 모든 X의 보유> 그렇게.
O (g)는이 조건이 유지하는 모든 함수의 집합입니다.
f ∈ o (g)는 본질적으로
들면 각 상수의 선택의 (K) > 0 인 경우 상수 찾을 수 예는 부등식 0 <= F (X) <kg (X)이 모두 x의 보유> 그렇게.
다시 한 번, o (g)는 세트입니다.
Big-O에서는 부등식이 최소 x 이상으로 유지되는 특정 승수 k 를 찾으면 됩니다.
Little-o에서는 음수가 아니거나 0이 아닌 한 k를 작게 만들더라도 부등식이 유지되는 최소 x 가 있어야합니다 .
이 두 가지 모두 상한을 설명하지만, 다소 반 직관적으로 Little-o가 더 강력합니다. f ∈ o (g) 인 경우 f ∈ O (g) 인 경우보다 f g o (g) 인 경우 f와 g의 성장률 사이에 훨씬 더 큰 차이가 있습니다.
시차의 한 가지 예는 다음과 같습니다. f ∈ O (f)는 true이지만 f ∈ o (f)는 false입니다. 따라서 Big-O는 “f means O (g)는 f의 점근 성장이 g보다 빠르지 않다는 것을 의미한다”는 반면 “f ∈ o (g)는 f의 점근 성장이 g보다 엄격히 느리다는 것을 의미합니다. <=vs와 같습니다 <.
보다 구체적으로, g (x)의 값이 f (x)의 상수 배수 인 경우, f ∈ O (g)는 참입니다. 이것이 big-O 표기법으로 작업 할 때 상수를 삭제할 수있는 이유입니다.
그러나 f ∈ o (g)가 true가 되려면 g 에 x 의 더 큰 거듭 제곱 이 포함 되어야합니다. 따라서 x가 커질수록 f (x)와 g (x) 사이의 상대적 분리가 실제로 커져야합니다.
알고리즘을 참조하지 않고 순수 수학 예제를 사용하려면 :
다음은 Big-O에 해당하지만 little-o를 사용한 경우에는 해당되지 않습니다.
- x² ∈ O (x²)
- x² ∈ O (x² + x)
- x² ∈ O (200 * x²)
little-o의 경우 다음과 같습니다.
- x² ∈ o (x³)
- x² ∈ o (x!)
- ln (x) ∈ o (x)
f ∈ o (g) 인 경우 f ∈ O (g)를 의미합니다. 예를 들어, x² ∈ O (x³)는 x² ∈ O (가 x³), (다시 같은 O의 생각도 마찬가지입니다, 그래서 <=같은 및 O <)
답변
로 큰-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 사이의 진동이에 있어요. O(1)여전히 가지고 있기 때문에, 정상적인 한계를 가지고 있지에도 불구하고 a lim sup: 4.)
Big-O 표기법이 점근 비교로 변환되는 방식을 암기하는 것이 좋습니다. 비교는 기억하기 쉽지만 n O (1) = P 와 같은 것을 말할 수 없기 때문에 유연성이 떨어집니다 .
답변
개념적으로 무언가를 파악할 수 없을 때 X를 사용 하는 이유 에 대해 생각 하는 것이 X를 이해하는 데 도움이된다는 것을 알게되었습니다.
[알고있는 것들] 알고리즘을 분류하는 일반적인 방법은 런타임에 의한 것이며, 알고리즘의 복잡성을 크게 언급함으로써 어느 것이 “더 나은”기능을 가장 잘 예측할 수 있는지, 어느 것이 “가장 작은”기능인지 O에서! 실제 세계에서도 O (N)는 O (N²)보다 “더 낫다”.
O (N)에서 실행되는 알고리즘이 있다고 가정하겠습니다. 꽤 좋아요? 그러나 당신 (당신, 훌륭한 사람, 당신)은 O ( N ⁄ loglogloglogN ) 에서 실행되는 알고리즘을 생각해 봅시다 . 예! 더 빠릅니다! 그러나 논문을 쓸 때 어리석은 글을 거듭 쓰는 느낌이들 것입니다. 그래서 당신은 그것을 한 번 쓰고, “이 논문에서, 나는 이전에 시간 O (N)에서 계산 가능한 알고리즘 X가 실제로 o (n)에서 계산 가능한 것임을 증명했습니다.”
따라서 모든 사람들은 알고리즘이 더 빠르다는 것을 알고 있습니다. 이론적으로. 🙂
