0
사실입니까?빅 O와 빅 오메가는 동일하지만 반대입니다.
f(n) = O(g(n)) === g(n) = Omega(f(n))
기본적으로 서로 상충되는 이유는 무엇입니까?
F가 F의 Big O에 있으면 G는 F의 Big Omega입니까?
그것은 정의를보고하는 데 도움이
A
답변
1
I를
F (N)는 O에서 N (g() 및 N 오메가 (g()) 두 경우를 제외하고 시타 (g (n)이) 없습니다.
희망 Big-O 표기법이 "최악의 경우"이고 Big Omega가 "가장 좋은 경우"라고 생각하는 가장 쉬운 방법은
물론 다른 표기법이 있습니다. 예를 들어, 은 일 수 있습니다. 다음 (멍청한) 선형 검색 알고리즘은 O (n)이지만 상태를 더 정확하게 표현하면 그것은 항상는 N에 정확히 비례 수 있습니다 :
public bool Contains(List<int> list, int number)
{
bool contains = false;
foreach (int num in list)
{
// Note that we always loop through the entire list, even if we find it
if (num == number)
contains = true;
}
return contains;
}
우리는 수,이 모두 O (N)와 오메가 (N)이라고 대안 상태입니다. 이 경우, Theta (n)의 표기법을 소개합니다.
평균 사례와 같은 다른 경우도 있습니다. 평균 사례는 종종 최상 또는 최악의 경우와 동일합니다. 예를 들어 잘 구현 된 선형 검색의 가장 좋은 경우는 O (1)입니다 (찾고있는 항목이 목록의 첫 번째 항목 인 경우). 그러나 최악의 경우는 O (n)입니다 (왜냐하면 전체 목록을 검색하여 해당 항목이 없음을 확인합니다. 목록에 항목이 포함되어 있으면 평균으로 항목을 찾기 위해 n/2 걸립니다 (평균적으로 항목을 찾기 위해 목록의 절반을 조사해야하기 때문에). 전통적으로, 우리는 "/ 2"부분을 버리고 평균 사례가 O (n)라고 말합니다.
은이 동일해야합니다. 바이너리 검색 트리 검색에 대한 "최상의"경우가 O (1)로 간주되어야하는지 (찾고있는 항목이 트리의 첫 번째 항목 일 수 있기 때문에) 또는 고려해야하는지 여부에 대한 몇 가지 논점을 보았습니다 O (log n) (왜냐하면 트리가 완벽하게 균형 잡힌 경우 이진 탐색을위한 "최적"의 경우이기 때문입니다). BST 삽입에 대한 설명은 here을 참조하십시오. 평균적인 경우는 분명히 O (log n)입니다. 최악의 경우는 O (n)입니다 (이진 탐색 트리가 완전히 인 경우이 균형을 이룬 경우). 우리가 가장 좋은 경우를 O (1), 평균적인 경우를 O (log n), 최악의 경우를 O (n)이라고하면 평균, 최악의 경우와 최선의 경우 모두 분명히 다르다.
3
: 당신은 O (N g())에서 F (N)를 만들 C와 K의 값을 찾을 수있는 경우에, 같은 값도 표시됩니다
f(n) is in O(g(n)) if and only if:
There are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.
g(n) is in Omega(f(n)) if and only if:
There are positive constants c and k, such that g(n) ≥ cf(n) ≥ 0 for all n ≥ k.
g (n)은 오메가 (f (n))가된다 (단지 부등식의 양변을 c로 나눔). 그것이 상호 교환 가능한 이유입니다. 도움!