[big-o] Θ (n)과 O (n)의 차이점은 무엇입니까?

간단한 설명 :

알고리즘이 Θ (g (n))이면, n (입력 크기)이 클수록 알고리즘의 실행 시간이 g (n)에 비례한다는 것을 의미합니다.

알고리즘은 O (g (N))의 경우,은 알고리즘의 실행 시간은 N이 큰 것을 의미한다 얻는다 많아야 비례에 g (n)으로하여 출력한다.

일반적으로 사람들이 O (g (n))에 대해 이야기하더라도 실제로는 Θ (g (n))을 의미하지만 기술적으로는 차이가 있습니다.

보다 기술적으로 :

O (n)은 상한을 나타낸다. Θ (n)은 타이트 바운드를 의미합니다. Ω (n)은 하한을 나타냅니다.

f (x) = Θ (g (x)) iff f (x) = O (g (x)) 및 f (x) = Ω (g (x))

기본적으로 알고리즘이 O (n)이라고 말하면 O (n ² ), O (n ^1000000 ), O (2 ⁿ )이지만 … Θ (n) 알고리즘은 Θ (n ² ) 가 아닙니다 .

실제로, f (n) = Θ (g (n))은 n의 충분히 큰 값을 의미하므로 , c의 일부 값에 대해 f (n)은 c ₁ g (n) 및 c ₂ g (n) 내에 바인딩 될 수 있습니다. ₁ 및 C ₂ , 즉, F의 성장 속도는 점근 동일 g : g는 하한 수 및 및은 상부 (F)의 결합. 이것은 f가 g의 하한과 상한이 될 수 있음을 직접적으로 암시합니다. 따라서,

f (x) = Θ (g (x)) iff g (x) = Θ (f (x))

유사하게, f (n) = Θ (g (n))을 나타 내기 위해, g는 f의 상한 (즉, f (n) = O (g (n)))이고 f는 g (즉, f (n) = Ω (g (n)), 이것은 g (n) = O (f (n))과 정확히 같은 것입니다). 간결하게

f (x) = Θ (g (x)) iff f (x) = O (g (x)) 및 g (x) = O (f (x))

ω함수의 느슨한 상한 및 하한을 나타내는 적은 오메가와 작은 오메가 ( ) 표기법도 있습니다.

요약:

f(x) = O(g(x))(큰 OH)의 성장 속도가 수단 f(x)점근 적이며 이하 동일 의 성장률 g(x).

f(x) = Ω(g(x))(큰 오메가)의 성장 속도가 수단 f(x)점근이다 이상인 증가율g(x)

f(x) = o(g(x))(little-oh)는의 성장률 이 의 성장률 보다f(x) 무증상 임을 의미합니다 .g(x)

f(x) = ω(g(x))(리틀 오메가)의 성장 속도가 수단 f(x)점근 적이며 보다 증가율g(x)

f(x) = Θ(g(x))(세타)의 성장 속도가 수단 f(x)점근이다 동등 의 증가율g(x)

보다 자세한 논의 는 Wikipedia에 대한 정의를 읽 거나 Cormen et al.의 Introduction to Algorithms와 같은 고전적인 교과서를 참조하십시오.

답변

for(int i=0; i<n; i++){
    f(i);
}

for(int i=0; i<n; i++){
    if( f2(i) ) break;
    f(i);
}