지수 함수의 큰 O 표기

Question

나는 1000n 또는 10n의 big-O가 O (n)과 동일한 것으로 나타 났지만 2^n과 3^n의 big-O는 다릅니다. O (2^n))와 O (3^n)을 얻지 못하면 왜이 경우 (2 또는 3)의 상수를 무시할 수 없는지, 그리고 이것을 정당화하는 수학적 증명이 있는지는 알지 못합니다.

Answer 1

임의로 큰 대입 3^n <= k * 2^n을 만족하는 상수 값 k이 없기 때문에 n. 따라서 f(n) = 3^n은 (은) O(2^n)의 멤버가 아닙니다.

http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations을 참조하십시오.

Answer 2

이벤트 원래 Asker에 대해서는 더 이상 사용하지 않을 수도 있지만
나는 더 쉬운 방법으로 접근 할 수 있다고 생각합니다.

O 표기법의

기본 defenition : F (g) IFF
그때는 그 F (g) = C를 보유하는 유리수의 C를 존재, O (N g())에있을 것 * g (N), N> = N0
(N0 인 사용자가 직접 선택할 수)

하는의는 O에서^n은 3이 적용 해보자 (2^n)이
3^N = 2^N * C
3^N = 2^N 개의 * (3^N/2^N)
3^N = 2^N 개의 * (3/2)^N
3^N = 2^N * 1.5^N

이는하는 바람직하지 않은 경우, C = 1.5^N 숫자지만 지수 함수는 독자적으로 나타납니다. O 3^N (2^N)에 대해 동일한 따라 한편

, 우리 넣기 2^N < = 3^N 개의 * (2/3)^N

이 당신이 0.75^n <에 대해 1을, 모든 c> 1을 취하면 0보다 큰 것을 의미한다는 것을 깨닫기 전까지는 갈등처럼 보일 수 있습니다.67^n n = 0

Answer 3

한계를 적용한 두 가지 복잡성, f (n) 및 g (n)을 campare하려면 lim_ {n -> \ inf} f (n)/g (n) 가능한 답변은 세 가지입니다.

1) lim_ {n -> \ inf} f (n)/g (n) = 0; f (n)/g (n)) f (n) ∈ O (g (n)) f (n) n) = +/- inf; f (n)/g (n)) f (n) ≥ f (n)) f (n) ≥ f (n) n) ∈ 실수; 이것은 f (n) ∈ O (g (n))와 g (n) ∈ O (f (n))를 의미한다.

lim_ {N -> \ INF} 2^N/3^N = lim_ {N -> \ INF} (2/3)^N = 0

그리고 demostrated, 우리는도 3 demostraded^n ∉ O (2^n)이고, 2/3임을 쉽게 알 수 있습니다. < 1 이것은 제한을 0으로 수렴하기위한 한계를 만듭니다. 그리고 나서 한계의 결과는 상수에 의존합니다. lim_ {n-> inf} a^0 = 0의 경우 0 < < 1 lim_ {n-> inf} a^n = inf 인 경우 a> 1; 더 나은 이해 점검을 위해

: 토마스 H 코만, 찰스 E 레이저 슨, 로날드 L. Rivest가와 클리포드 스타 인

으로 알고리즘 소개, 제 3 판 나는 그것을 도움이 희망 알고리즘의 교수 해요 당신. 조심해.