어떠한 코드를 작성하셨는지 모르겠지만 logN 연산에 필요한 각종 오버헤드가 있으니 1초에 1억번이 걸린 다는 것은 사실 알 수 없습니다. 단순한 사칙연산 및 대입은 빠를 수도 있겟지만 조금만 복잡한 알고리즘이 적용되기만 해도 추가적인 시간과 메모리가 필요합니다.
위에 말하신 내용은 그냥 어떠한 알고리즘을 사용해야 할 지 유추만 하는 용도로 사용하시면 될 것 같습니다.
보통 N이 1000만 이상이면 O(N)
10~100만대면 O(nlogn)
1만대면 O(NM)
1000대면 Brute-force 등 유추가 가능합니다

abronia416 1년 전 2
제가 공부하는 알고리즘 코딩테스트 자바편 책에서 특정 문제의 시간복잡도 분석을 하는 부분의 워딩이 이해가 가질 않아 질문합니다!
문제의 시간 제한은 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초의 시간 제한을 만족시키는 것 아닌가요?
제가 시간 복잡도 계산에 대해서 잘못 생각하고 있는 것이 있다면 꼬집어주시면 감사하겠습니다.