시간복잡도 공부 중에 궁금한 것이 생겼습니다.

Question

시간복잡도 T(n) &#61; n² &#43; n &#43; 1 이 있을 때이를 빅오 표기법으로 표기하면 O(n²) 이라고 표기 하는데 여기 까지는 이해가 됐습니다근데 이에 대해 T(n) ≤ O(n²) 라고 하는데 이 부분이 이해가 안됩니다제 생각엔 빅오 표기법은 T(n)에 대하여 가장 영향이 큰 항만 고려 한 것이라 n² 만 남게 되고그럼 결국 n² &#43; n &#43; 1 ≤ n² 이렇게 되는데 저 부등호가 어떻게 성립이 되는거죠?이해 시켜주시면 감사하겠습니다

JethroHolic · Answer

점근분석 자체가 정확한 값이 아니라 흐름을 보기 위한 수단이므로 최고차항의 차수만을 사용합니다.n² &#43; n &#43; 1 이라는 형태를 점근분석하면 n^2의 값입니다.n² &#43; n &#43; 1 ≤ n² 를 T(n) ≤ O(n²) 의 형태가 아니라,F(n) &#61; n² &#43; n &#43; 1 이라는걸 점근 분석할 때는O(F(n)) ≤ O(n²) 처럼 생각하셔야합니다.

mirheeoj · Answer

주어진 부등호를 이해하는 방법에 대한 질문으로 생각이 되고요.T(n)은 전체 오퍼레이션의 숫자이고 O(n²)은 시간복잡도이며 양자의 관계는 후자가 해당 형태의 최대값이라고 생각하시면 됩니다.즉, 본문의 예에선 n² + n + 1 ≤ n² 이란 말을 하는 게 아니라, (n² + n + 1) ≤ (n²이 지켜지는 선에서 최대 오퍼레이션 수) 라는 거죠.또 한가지 예를 들어보면, 999999..999n² 도 여전히 'n²이 지켜지는 선에서 최대 오퍼레이션 수'보다는 작을겁니다. T(n) ≤ O(n²)은 이런 얘기예요.

시간복잡도 공부 중에 궁금한 것이 생겼습니다.

2개의 답변

기술 목록