빅 - 오 - 함수의 성장률은

Question

내가 더 약 큰-O을 알고 싶어 정보의 조각을 발견

'f(x)의 성장 속도가에 점근보다 작거나 같은 f(x) = O(g(x)) 경우 성장률이 g(x) '

이 시나리오에서 점근 적으로 의미하는 것은 무엇입니까? 또한 왜 Big-Theta가 우리가 사용하는 컴퓨터에 의존하지 않는지 이해하는데 어려움이 있습니까? 누구나이 두 가지 질문에 대해 더 자세한 정보를 제공 할 수 있습니까?

Answer 1

이 문맥에서 용어 "점근 적으로"는 "x가 무한대로 간다"를 의미합니다. 누군가가 "f (x)가 g (x)보다 완만하게 자라다"라고 말하면 매우 큰 x의 값에 대해 함수 g (x)가 함수 f (x)보다 빠르게 커질 것이라는 의미입니다. 이것은 f (x)가 ≥ 1이고 g (x)가 ≥ 인 경우 충분히 큰 x에 대해 g (x)의 값이 항상 함수 f (x)보다 커야 함을 의미합니다. 이 질문에 관해서는

:

또한

내가하지 빅 세타 우리가 사용하는 컴퓨터에 따라 않는 이유를 이해하는 어려움이 있습니까?

는 O, Θ 및 Ω 표기하지만 그것은 그들이 무엇을 의미하는지 실제로 아니라, 런타임을 설명하기 위해 CS에서 광범위하게 사용된다. 기술적으로,이 표기법은 실제로 함수의 의미와 관계없이 함수의 성장률을 계량화하는 데 사용됩니다. 예를 들어, 이산 수학에서 Stirling's approximation에 사용 된 big-O 표기법을 볼 수 있습니다. O (log n)은 "성장률이 O (log n) 인 일부 함수"를 의미합니다. CS에서, 알고리즘이 O (n)이라고 말하면, 실제로이 함수의 실행 시간을 설명하는 함수는 O (n)입니다. 좀 더 정확하게 말하면, "O (n)"이나 "알고리즘이 시간이 많이 걸린다 (O)"와 같은 표현을 볼 수 있습니다. big-O 표기법이 알고리즘의 런타임을 설명하는 데 사용됩니다. 알고리즘 그 자체보다 이 의미에서 "Θ 표기법이 컴퓨터에 의존하지 않는 이유는 무엇입니까?"라는 질문에 대한 한 가지 대답은 무엇입니까? "Θ 표기법은 기능의 성장 속도를 정량화하고 컴퓨터와 아무 관련이 없습니다." 또 다른 의미에서

, 특정 컴퓨터에 문제가되지 않는 이유는 Θ 표기법에 대한 점근 런타임하지 절대 런타임을 말하는 것입니다. 알고리즘에 런타임이 Θ (n) 인 경우 알고리즘의 런타임이 일부 선형 함수로 확장됨을 의미합니다. 입력의 크기와 같은 알고리즘의 런타임은 사실 100n + 137 또는 20,000,000n - 15와 같을 수 있습니다. 중요한 것은 모든 런 타임이 실행 시간이 아니라 실행 시간 자체가 길기 때문입니다. 다른 컴퓨터에서 동일한 코드를 실행하면 선택한 컴퓨터에 따라 실행하는 데 시간이 다소 걸릴 수 있지만 거의 선형 적으로 스케일에서 2 차 스케일링으로 변경되지 않습니다. 즉, 점심 시간이 일 때, 런타임은 동일하지만, 절대적으로은 런타임과 다를 수 있습니다.

희망이 도움이됩니다.