tjdgns9246   5달 전

음... 처음에는 입력받은 수의 맨 뒤 3자리부터 8진수로 변환해서 출력하는 소스를 짜다가

그냥 귀찮아서 10진법으로 변환 후에 atoi()를 쓸려고 했는데, 다른 웹 컴파일러에서 지원을 안해주더라구요.. ㅎㅎ

그래서 여기도 혹시나 지원이 안될까봐 10진수를 8진수로 출력하는 재귀함수로 만들었는데 시간초과가 뜹니다.

옛날부터 시간복잡도를 어떻게 계산하는지 방법을 잘 이해하지 못해서 여전히 시간초과를 신경쓰지 못하네요.

이 소스의 시간복잡도와 예상소요시간을 알 수 있을까요?



yukariko   5달 전

O (length^2)으로 보이네요.

길이제한이 100만이니 어림짐작으로 한 1000초쯤 걸릴것 같습니다.

tjdgns9246   5달 전

yukariko님 감사합니다.

근데 왜 O(length ^ 2)인지 알 수 있을까요?

for문에서의 length와 pow에서의 length 때문인가요?

for문에서는 length ~ 0까지, pow는 반대로 0 ~ length까지

이렇게 2중으로 돌리게 되면 결국 O(length) 아닌가요..?



yukariko   5달 전

그렇지는 않습니다.

반복을 length번 하는데,

각 반복안에1부터 length까지 또 반복을하게됩니다.

이런 경우 반복횟수는 length × (length / 2) 쯤되는데, 시간복잡도 표현으론 length^2가 되는것이죠.

tjdgns9246   5달 전

yukariko

아~ 그렇군요ㅎㅎㅎ 덕분에 시간복잡도를 조금 더 이해를 할 수 있게됬네요.

감사합니다. ^^

수고하세요!!

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