점근 범위와 실행 시간 사이의 관계?

Question

는 예를 들어 이진 검색을 가지고 있습니다, 시간을 실행하는 가장 좋은 경우는 먼저 비교를 얻을 것이다 때

key_to_find == (Imin으로 + IMAX)/2;

그리고 최상의 실행 시간은 O (1)로 표시됩니다. 나는 완전히 이해하지만 나를 혼란스럽게하는 이유는 O (1)이 사용되고 왜 Θ (1)이나 다른 표기법을 사용할 수 없는지입니다.

실행 시간 (가장 좋음, 평균 또는 최악의 경우)을 나타 내기 위해 어떤 표기법을 사용해야하는지 식별하는 방법.

Answer 1

O 표기법과 Θ 표기법은 최상의 경우, 평균 또는 최악의 경우와 관련이 없습니다. 함수의 점근 적 경계에 사용됩니다. 넌 작성할 수 47N의 LG N = O (N 엑스 N) 3N^2 + 4N = O (N^2)

그리고 O Θ 표기법 차이가있다. O는 "최대 (어떤 상수 계수를 사용함)"을 의미하고, Θ는 "같음 (일정한 계수를 사용함)"을 의미합니다 (예 : 47nln n = O (n^2)). 그러나 Θ (n^2)가 아닙니다.

최상의 케이스, 평균 케이스 또는 최악의 케이스를 표현하려면 보통 다음과 같이 명시 적으로 작성하십시오. "가장 좋은 케이스는 O (1) (또는 Θ (1))이며 평균 케이스는 O (lg n)입니다. 최악의 경우는 O (n)입니다. "

때때로 "실행 시간은 O (x)"입니다. 그러면 실행 시간은 x에 가장 비례합니다. "running time is Θ (x)"라고 말하면, 실행 시간은 항상 x에 비례 함을 의미합니다.

Answer 2

원하는 표기법을 사용할 수 있습니다. 빅 세타 (Big Theta)는 가장 정확하므로 알고있을 때마다 사용해야합니다. 부수적으로, O (1)은 복잡도 분석의 맥락에서 Θ (1)와 같습니다 (연산 수가 정수 인 경우, 즉 복잡도로 O (1/n)을 가질 수없는 경우).