ysh6108   10달 전

제가 적은 코드로 정답은 맞았으나 이해가 되지 않는 부분이 있어 질문합니다. 다른 블로그나 질문 게시판을 보니 a1*n + a0 <= c*n 일 때 경우만 고려해서 코드를 짜면 정답일 거라 적혀있었습니다. 그런데 저는 만약 a1이 0 일 경우에는 좀 다르다고 생각했습니다. O(g(n))은 "모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다"를 조건으로 한 "f(x)" 함수입니다. 따라서 a1이 0일 경우에는 f(x) =  a0 가 되니까 O(g(n)) = a0 이므로 g(n) = 1일 거라 판단했습니다. 그래서 a1이 0인 경우를 고려하지 않아도 되는 이유가 궁금합니다. 그리고 g(n)이 상수가 아니라면 그 이유도 궁금합니다. 시간 복잡도 유튜브 강의 보고온지 1시간 경과했습니다.. 양해부탁드립니다...

joe2357   10달 전

O(g(n))의 정의가 그렇다는 것이고, 이 문제는 f(n)이 O(n)을 만족하는지를 물어보고 있습니다.

이 문제에 한해서는 g(n) = n인거죠.

댓글을 작성하려면 로그인해야 합니다.