백준 24313번 문제에서 g(n) = n인 이유를 잘 모르겠습니다ㅠ

Question

안녕하세요!간단한 문제이지만, 제가 수학적 지식이 거의 없어서 그런지...백준 24313번 문제에서 g(n)을 왜 n이라 보는 건지 잘 모르겠네요.즉, a1n &#43; a0 <&#61; c * g(n) 여기서 c * g(n)을 왜 c * n으로 보는 건지...검색해 보기에는 애매해서 GPT에게 물어보니 다음과 같은 답변이 돌아왔는데, 무슨 말인지 알듯 말듯 애매하네요ㅠ&#34;Big-O 표기법은 최고 차항만 취급하니 그런 거다.&#34;라는 느낌의 답변 같은데, 아직 잘 이해가 안 가네요...

도미다 · Answer

o(g(n)) 에자리에 o(n) 이니까 g(n)을 n으로 대입한거죠

Hide_D · Answer

'최고차항만 따지니까'가 이해하신게 맞고요.&#34;c * g(n) 인 상수 c가 존재한다.&#34; 라는 말은, 다시 말해 &#34;g(n)의 상수 배를 넘어서지 않는다&#34;는 말입니다.f(n)가 an &#43; b 라고 했을 때, O(f(n))은 O(n)라 하라고 했다는 이야기는,O(99999999f(n)) 역시 O(99999999n &#43; 99999999b)로, 상수 배인 것이니 O(n) 인 것이다. 라는 소리죠.

백준 24313번 문제에서 g(n) = n인 이유를 잘 모르겠습니다ㅠ

2개의 답변

Q&A 목록