puleugo   8달 전

로직에는 큰 차이가 없는것 같은데, 1번이 시공간 복잡도가 훨씬 효율적입니다. 

리스트를 불러오지 않는게 시간과 공간 복잡도에 영향을 주는건가요?

아니면 제가 놓친 부분이 있는건가요?

puleugo   8달 전

지금 확인해보니 1번 코드는 python으로, 2번 코드는 pypy로 제출했네요.
pypy가 더 빠르기로 아는데, 케바케인건가용?

onart   8달 전

간단한 프로그램은 python3이 더 빠르게 측정되는 경향이 있네요.

* 시공간 복잡도는 이론의 얘기입니다. 따라서 로직이 큰 차이가 없는데 어떤 하나가 시공간 복잡도가 효율적이란 말은 잘못된 겁니다. 극단적으로 어떤 시간 공간 복잡도 모두 O(n) (혹은 Ω(n))인 알고리즘을 사용하는 프로그램이 10개의 입력을 받았을 때 16MB의 메모리를 사용하고 10000개의 입력을 받았을 때 16GB의 메모리를 사용한다고 가정하면, 평범한 램을 사용하는 경우 당연히 메모리 계층상 수행시간이 1000배보다 훨씬 더 걸릴 겁니다. 그런다고 시간 복잡도가 O(n)이 아니게 되는 건 아닙니다.

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