큰 Ө 표기법은 정확히 무엇을 의미합니까?

큰 Ө 표기법은 정확히 무엇을 의미합니까?

---

빅 O, 빅 오메가 및 빅 세타 표기법의 차이점에 대해 정말 혼란 스럽습니다.

big O가 상한이고 big Omega가 하한이라는 것을 이해하지만 big Ө (theta)는 정확히 무엇을 나타 냅니까?

나는 그것이 꽉 묶인 것을 의미한다고 읽었 지만 그 의미는 무엇입니까?

---

주어진 함수에서 알고리즘이 big-O 및 big-Omega임을 의미합니다.

이 경우 예를 들어 Ө(n), 다음 몇 가지 상수가 k같은 당신의,보다 큰 기능 (어떤 런타임) n*k충분히 큰에 대한 n, 그리고 몇몇 다른 상수 K함수가보다 작도록 n*K충분히 큰위한 n.

즉, 충분히 큰 n경우 두 개의 선형 함수 사이에 끼워집니다.

옵션 k < K과 n충분히 큰n*k < f(n) < n*K

---

먼저 큰 O, 큰 Theta 및 큰 오메가가 무엇인지 이해합시다. 그것들은 모두 기능 세트 입니다.

Big O는 상한 점 바운드를 제공하는 반면 Big Omega는 하한값을 제공합니다. 빅 세타 둘 다 제공합니다.

Ө(f(n))또한 모든 것이 O(f(n))있지만 다른 방법은 아닙니다. in 과 in에 모두
T(n)있다고합니다 . 세트의 용어로 는 IS 교차로 의 및Ө(f(n))O(f(n))Omega(f(n))
Ө(f(n))O(f(n))Omega(f(n))

예를 들어, 병합 정렬 최악의 경우는 둘 다 O(n*log(n))와 Omega(n*log(n))- 따라서도 Ө(n*log(n))하지만, 또한 O(n^2)이후, n^2그 이상의 점근 "더 큰"입니다. 그러나, 그것은 것입니다 하지 Ө(n^2) 알고리즘이 아니기 때문에 Omega(n^2).

좀 더 깊이있는 수학 설명

O(n)점근 적 상한입니다. 경우 T(n)이며 O(f(n)), 이것은 어느 의미에서 해당 n0상수가 C되도록 T(n) <= C * f(n). 한편, big-Omega는 ) C2와 같은 상수가 있다고 말합니다 T(n) >= C2 * f(n)).

혼동하지 마십시오!

최악, 최고 및 평균 사례 분석과 혼동하지 마십시오. 세 가지 (Omega, O, Theta) 표기법 모두 알고리즘의 최고, 최악 및 평균 사례 분석과 관련 이 없습니다 . 이들 각각은 각 분석에 적용될 수 있습니다.

우리는 일반적으로 ( 복합 정렬 예제와 같은) 복잡한 알고리즘을 분석하는 데 사용합니다 . "Algorithm A is O(f(n))" 라고 말할 때 , 실제로 의미하는 것은 "최악의 ^{1 가지} 경우 분석 에서 알고리즘의 복잡성 은 O(f(n))"-의미입니다.-함수의 "유사한"(또는 공식적으로 나쁘지 않은) 스케일 f(n)입니다.

알고리즘의 점근 적 경계를 신경 쓰는 이유는 무엇입니까?

글쎄, 거기에는 많은 이유가 있지만, 가장 중요한 이유는 다음과 같습니다.

1. 정확한 복잡도 함수 를 결정하는 것이 훨씬 어렵 기 때문에 이론적으로 충분히 유익한 big-O / big-theta 표기법을 "타협"합니다.
2. 정확한 op 수는 플랫폼에 따라 다릅니다 . 예를 들어 16 개의 숫자로 구성된 벡터 (목록)가있는 경우입니다. 얼마나 많은 작전이 필요할까요? 대답은 다음과 같습니다. 일부 CPU는 벡터 추가를 허용하지만 다른 CPU는 그렇지 않으므로 구현과 시스템에 따라 대답이 다르며 이는 바람직하지 않은 속성입니다. 그러나 big-O 표기법은 기계와 구현간에 훨씬 더 일정합니다.

이 문제를 설명하려면 다음 그래프를 살펴보십시오.

f(n) = 2*n보다 "나쁘다"는 것이 분명하다 f(n) = n. 그러나 그 차이는 다른 기능과 크게 다르지 않습니다. 우리는 f(n)=logn다른 기능들보다 빠르게 낮아지고 다른 기능들보다 f(n) = n^2빠르게 높아지고 있음을 알 수 있습니다.
따라서 위의 이유 때문에 상수 요소 (그래프 예제에서 2 *)를 "무시"하고 big-O 표기법 만 사용합니다.

위의 예에서, f(n)=n, f(n)=2*nin O(n)및 in 둘 다에있을 Omega(n)것입니다 Theta(n).
반면에-에 f(n)=logn있을 것입니다 O(n)(보다 낫습니다 f(n)=n) Omega(n).-에 있지 않을 것입니다 Theta(n).
비대칭 적 f(n)=n^2으로 Omega(n), 그러나, 안으로 들어갈 수 없으며 O(n), 따라서-또한 아니다 Theta(n).

---

¹ 항상 그런 것은 아니지만 일반적으로. 분석 클래스 (최악, 평균 및 최고)가 누락되면 실제로 최악의 경우를 의미 합니다.

---

Theta(n): A function f(n) belongs to Theta(g(n)), if there exists positive constants c1 and c2 such that f(n) can be sandwiched between c1(g(n)) and c2(g(n)). i.e it gives both upper and as well as lower bound.

Theta(g(n)) = { f(n) : there exists positive constants c1,c2 and n1 such that 0<=c1(g(n))<=f(n)<=c2(g(n)) for all n>=n1 }

when we say f(n)=c2(g(n)) or f(n)=c1(g(n)) it represents asymptotically tight bound.

O(n): It gives only upper bound (may or may not be tight)

O(g(n)) = { f(n) : there exists positive constants c and n1 such that 0<=f(n)<=cg(n) for all n>=n1}

ex: The bound 2*(n^2) = O(n^2) is asymptotically tight, whereas the bound 2*n = O(n^2) is not asymptotically tight.

o(n): It gives only upper bound (never a tight bound)

the notable difference between O(n) & o(n) is f(n) is less than cg(n) for all n>=n1 but not equal as in O(n).

ex: 2*n = o(n^2), but 2*(n^2) != o(n^2)

---

I hope this is what you may want to find in the classical CLRS(page 66):

---

Big Theta notation:

Nothing to mess up buddy!!

If we have a positive valued functions f(n) and g(n) takes a positive valued argument n then ϴ(g(n)) defined as {f(n):there exist constants c1,c2 and n1 for all n>=n1}

where c1 g(n)<=f(n)<=c2 g(n)

Let's take an example:

let f(n)=

g(n)=

c1=5 and c2=8 and n1=1

모든 표기법 중에서, ϴ 표기법은 함수의 성장률에 대한 최상의 직관을 제공합니다. 이는 상한과 하한을 각각 제공하는 big-oh 및 big-omega와 달리 빡빡한 경계를 제공하기 때문입니다.

ϴ은 g (n)이 f (n)에 가깝고, g (n)의 성장 속도는 가능한 f (n)의 성장 속도에 가깝다는 것을 알려줍니다.

참고 URL : https://stackoverflow.com/questions/10376740/what-exactly-does-big-%d3%a8-notation-represent