satelites   8달 전

안녕하세요.

위 문제의 시간복잡도를 계산해보니

O( (4x2^9) x 2(N - 2) ) 가 나왔습니다. [ N <=10 ]

이 경우 계수가 변수보다 훨씬 큰 데, 이때도 계수를 무시해야하나요?

djm03178   8달 전

시간 복잡도라는 것은 실제로 그 프로그램이 얼마나 오래 실행될 것이다를 나타내기보다는 수학적인 분석에 가깝기 때문에 정의에 맞게 사용해주는 편이 옳습니다. 수학적으로 점근 표기법에서는 계수가 얼마나 큰지가 전혀 중요하지 않기 때문에 그 계수를 무시하든, 써주든, 아니면 전혀 상관 없는 다른 크거나 작은 상수로 해주든 정의상 모두 같은 복잡도가 됩니다.

pichulia   8달 전

그래도 뭔가 찝찝하시다면...  구슬의 이동횟수를 나타내는 변수 K를 새로 정의해서 O(N2^K) 으로 표현할 수도 있습니다.

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