빅오나 세타, 오메가 표기법등등 이 f(n) = (표기법)(g(n)) 일때 f와 g의 상관관계를 표기하는 것이 맞나요?
예를 들어 (3/2)n^2 + (7/2)n - 4 = θ(n^2) 가 성립된다는 것은 알겠습니다
하지만 f(n)에 다른 표기법이 들어가 있을때,
예를 들어 왜 2(n^2) + θ(n) = θ(n^2) 가 true 인지 이해를 잘 못하겠습니다.
위의 예제가 왜 성립되는 지, 그리고
1) n^2 + O(nlog(n)) = θ(n^2)
2) Ω(n^3) + o(n^2) = Ω(n^3)
3) n + ω(log(n)) = θ(n)
4) θ(n) x θ(n^2) = θ(n^3)
가 각각 true인지 false인지, 그리고 각각 왜 그런지 인지 설명해주세요
제가 한 이해로는 예를 들어 n^2 + O(nlog(n)) = θ(n^2) 인 경우
세타 표기법은 이퀄 사인 왼쪽과 오른족이 n의 값이 달라도 항상 정비율로 늘러나거나 줄어드니까 (즉 오메가와 빅오를 포함)
n인 임의의 수 일때 왼쪽의 n^2 + O(nlog(n)) 은 항상 n^2 보다 크거나 같은 수 밖에 없으니까 false다 인데 제가 잘 이해하고 있는 건가요?
본인삭제금지
글쓰기