alpha_coder   5달 전

아래의 두 코드 모두 에라토스체 알고리즘을 통해 소수를 구하였는데, 하나는 시간초과가 나고 다른 하나는 시간초과가 나지 않는 이유를 잘 모르겠습니다. 제가 생각할 때, 시간초과가 나는 코드는 추가로 소수를 저장하기 위한 리스트를 생성했는데, 이 부분이 문제일까요? (소스코드 17번째 줄과 37번째 줄을 비교하면 소수만 확인하기 때문에 오히려 시간이 줄어들 줄 알았는데, 오히려 시간초과가 나서 당황스럽습니다. 조언 부탁드립니다.)

myyh1234   5달 전

prime_arr[1:]에서 배열을 복사하는 시간복잡도는 O(N)입니다.

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