abronia416   1년 전

제가 공부하는 알고리즘 코딩테스트 자바편 책에서 특정 문제의 시간복잡도 분석을 하는 부분의 워딩이 이해가 가질 않아 질문합니다!

문제의 시간 제한은 2초이고 입력받을 자연수 N의 범위가 1 <= N <= 10,000,000 입니다. 그래서 책에서는 이렇게 말합니다.

"우선 문제에 주어진 시간 제한은 2초입니다. 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀 있습니다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 합니다."

저는 이 워딩에서 의문점이 생겼습니다. n에 N의 최댓값인 10,000,000을 대입하여 nlogn을 계산하면 70,000,000이 나옵니다. 데이터 수가 10,000,000개일 때 연산은 약 70,000,000번을 한다는 의미인데... 1억번의 연산을 하면 1초 정도 걸린다고 생각하는 것이 일반적이므로 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 시간이 1초보다도 적게 나와서 거뜬하게 2초의 시간 제한을 만족시키는 것 아닌가요?

제가 시간 복잡도 계산에 대해서 잘못 생각하고 있는 것이 있다면 꼬집어주시면 감사하겠습니다.

siyamaki   1년 전

어떠한 코드를 작성하셨는지 모르겠지만 logN 연산에 필요한 각종 오버헤드가 있으니 1초에 1억번이 걸린 다는 것은 사실 알 수 없습니다. 단순한 사칙연산 및 대입은 빠를 수도 있겟지만 조금만 복잡한 알고리즘이 적용되기만 해도 추가적인 시간과 메모리가 필요합니다.

위에 말하신 내용은 그냥 어떠한 알고리즘을 사용해야 할 지 유추만 하는 용도로 사용하시면 될 것 같습니다.

보통 N이 1000만 이상이면 O(N)

10~100만대면 O(nlogn)

1만대면 O(NM)

1000대면 Brute-force 등 유추가 가능합니다

djm03178   1년 전

보통 프로그래밍에서 log는 밑을 2로 두는데, 이는 많은 경우 이 log가 전체 문제를 (대략적으로) 반으로 쪼개가며 해결하는 데에서 오기 때문입니다. 따라서 이를 기준으로 천만 로그 천만을 계산하면 대략 2.3억 정도가 나오게 됩니다.

하지만 그렇다고 해서 이러한 시간 복잡도가 항상 제한 시간을 초과하게 된다는 설명도 올바른 것은 아닙니다. 왜냐하면 시간 복잡도는 수행 시간 그 자체를 의미하는 것이 아니기 때문입니다. 2.3억 정도의 가벼운 연산은 경우에 따라서는 0.1초 내에도 실행이 가능하지만 무거운 연산이면 5초 내에도 실행이 되지 않을 수 있고, 이 차이를 결정하는 건 실제로 작성된 코드가 얼마나 무거운 연산들을 사용하고 있느냐이지 단순히 이론적으로 드러나는 시간 복잡도가 아니기 때문입니다.

마찬가지로 1초에 1억이라는 것도 아주 대략적이고 평균적인 수치일 뿐, 1억 번을 넘으면 무조건 1초를 넘고 1억 번이 안 되면 무조건 1초 내에 돈다는 뜻으로 받아들여서는 곤란합니다.

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