알고리즘 분석 - 성장 질문 순서

Question

나는 "큰 오", "큰 오메가"및 "큰 세타"의 성장 순서를 연구하고 있습니다. 나는이의 작은 기호를 입력 할 수 없기 때문에 다음과 같이 내가 그들을 나타내는 것

ORDER = I n을 말할 것이다 예를 들어 = 큰 오메가
OMEGA
THETA = 큰 세타

오 큰 = ORDER (n^2)는 함수 n이 n^2 (n은 빠른 n^2만큼 커짐)의 순서임을 의미합니다.

확인 대부분의 경우 나는 이러한 이해 :

것입니다 N (N + 1) 대 N^2

I : 여기에 좋아

n = ORDER(n^2)    //n grows at most as fast as n^2 
n^2 = OMEGA(n)    //n^2 grows atleast as fast as n 
8n^2 + 1000 = THETA(n^2) //same order of growth 

나를 혼란 예제를 제공 n (n + 1) = n^2 + n임을 깨달으십시오; 나는 그것이 n^2와 같은 성장 순서를 가지고 있다고 말할 것입니다;

N (N + 1) = ORDER 그러므로 나는

이

N (N + 1) = THETA는 (N^2) 내 질문에

하지만, 또한 말을 올바른 것 말할 것 (n^2)

이 부분이 혼란 스럽습니다. 감사.

은 너희들을 감사!

그냥 내가 제대로 이해하고 있는지 확인하기 위해 다음에 모두 해당 :

N^2 + N = ORDER (2000N^2)
N^2 + N = THETA (2000N^2)
N^2 + N = OMEGA (2000N^2)

2000N^2 = ORDER (N^2 + N)
2000N^2 = THETA (N^2 + N)
2000N이^2 = OMEGA (N^2 + n)

그래서 f = THETA (g)이면 f = ORDER (g)이고 f = Ω (g)도 참이다.

Answer 1

Moron is correct 등이 그 중 가장 쉬운 방법입니다.

하지만 O (g (n)을) 에 이해 = F (N)에 대한 정의로 돌아 : 포지티브 M 및 존재 N0 예컨대, 모든 N> N0, F (n)의 <위한 = Mg (n)이다.

M = 2라고 가정합니다. 모든 n> n0, n^2 + n에 대해 038이라는 값을 찾을 수 있습니까? < = M (n^2)?

(서로 관련하여 커지는 방식을 이해하려면 펜과 종이의 두 가지 기능을 모두 그려보십시오.)

는

Answer 2

예, n (n + 1) = 주문 (n^2)이 맞습니다.

f = Theta (g) 인 경우 f = Order (g) 및 g = Order (f)가 ​​모두 참입니다.

Answer 3

당신은이 기호의 의미의 쉽고 직관적 인 이해를 얻을이 간단한 테이블을 사용할 수 있습니다

F (N)와 N g()는 두 가지 기능 또한 다음

Growth Rate 
if f(n) = Θ(g(n)) then  growth rate of f(n) = growth rate of g(n) 

if f(n) = O(g(n)) then  growth rate of f(n) ≤ growth rate of g(n) 

if f(n) = Ω(g(n)) then  growth rate of f(n) ≥ growth rate of g(n) 

if f(n) = o(g(n)) then  growth rate of f(n) < growth rate of g(n) 

if f(n) = ω(g(n)) then  growth rate of f(n) > growth rate of g(n) 

는 경우 순서는 항상 가장 높은 순서의 관점에서 작성됩니다. 즉, 순서가 O (n^2 + n + 1)이면 n^2가 가장 높은 순서이므로 O (n^2)로 작성합니다. O (자본 O) 또는 Ο (자본 미크론), Ω (자본 오메가), 및 Θ (자본 세타) :