배가 및 추가 다른 asymptotioc 표기법

는

사람은 계산을 예를 수행하는 방법을 알고 않습니다 ?배가 및 추가 다른 asymptotioc 표기법

2011-10-11 Sławosz

안녕 Sławosz. 귀하의 질문은 매우 모호합니다. 당신은 무엇에 대해 더 구체적 일 수 있습니까? 2. 문제의 영역 (asymptotic 표기법은 일반적인 대수학 및 컴퓨터 과학에서 서로 다른 가정을 가지고 있습니다.) [math.SE] (http://math.stackexchange.com/)에 글을 쓰지 않았으므로 CS를 의미한다고 가정합니다.), 3. 당신이 수행하고자하는 방정식의 종류 (항상 그 나무 부분과? 원자의 유한 양 또는 O()의 무한 합이 허용 되는가? 등) 4. 우리가 실수를 말하는지 확인하십시오. 5. 결과 (O()? Omega()?)에 관심이 있습니까? –

다음은 [O (n) + O (n)이 혼란 스러울 수있는 방법]의 예입니다 (http://stackoverflow.com/questions/6687105/question-about-big-o-and-big-omega). O (n) + O (n) = O (n)을 유도 단계 O (n) + O (n) + ... = O) , **뭐가 잘못 되었 니**. 원인 (O (n))^n = O (n^n). 그래서 ** 매우 구체적인 **은 혼란을 피하기 위해 여기에 필요합니다. –

O는주는 상한;

Ω이 제공하는 하한 ;

Θ이주는 점근 적 바운드;

Wikipedia에는이를 설명하는 멋진 차트가 있습니다.

따라서 이러한 것들은 일반적으로 비교할 수 없습니다. 첫 번째 경우를 들어

O(n^2) + Θ(n) + Ω(n^3)

하자 최초의 O를 해결. 첫 번째 용어는 O(n^2)이고 두 번째 용어는 O(n)입니다. 이 두 가지를 바탕으로 지금까지 우리는 상한선을 위해 O(n^2)을 가지고 있습니다. 그러나 세 번째 용어는 상한에 대해 아무 것도 알려주지 않습니다! 그래서 우리는 실제로 O에 관해서 어떤 결론도 내릴 수 없습니다. 여기

점은 O 및 Θ 만 O 및 Ω에 대한 정보를 제공하며 Θ 당신에게 정보에 대한 Ω 만 제공한다는 것입니다. 이는 Θ(g(n))이 O(g(n))과 Ω(g(n))을 모두 포함하므로 O과 Ω 중 어느 하나가 적절한 분석으로 변경 될 수 있으므로 Θ을 변경할 수 있습니다. O도 Ω도 다른에 대해 아무것도 의미하기 때문에

그러나, 세 함께, 또는 단지 O 및 Ω, 당신은 우둔 떠난다.

출처

2011-10-11 22:26:28 PengOne

수 없습니다. a > 0과 b < 10을 알고 있다고 가정 해보십시오. 그렇다면 a+b에 대한 정보가 없습니다. 그것은 무엇이든 수 있습니다.

Big-O 및 Big-Omega는 기능에 대해 비슷하게 작동합니다.

출처

2011-10-11 22:49:22 tskuzzy

위의 대답은 일반적인 기능과 범위에는 맞지만 컴퓨터 과학에서는 일반적으로 긍정적 인 기능 만 고려합니다. 따라서 첫 번째 예에서 우리는 :

O(n^2) + Theta(n) + Omega(n^3) = Omega(1)+Theta(n)+Omega(n^3) = Omega(n^3)

이 기능은 모두 긍정적 인 것으로 가정합니다.즉, 모든 기능은 Omega(1)입니다.

출처

2011-10-12 19:50:45 tskuzzy

마찬가지로 문제에서 주어진 곱셈은 Omega (n^4)입니다. –

배가 및 추가 다른 asymptotioc 표기법

답변

관련 문제