네. 당연히 O(n^2)니까 많이 잡아먹지요.

n = 32768에 대해서 테스트를 해 본 결과, 약 18.7초가 걸렸습니다.

정렬된 맵에서 i번째에 접근하려고 하는 경우, map 자체가 연속되게 저장하지 않기 때문에

Linked List처럼 순회를 하겠죠.

다른 방법을 생각해 보시는 게 좋을 듯 싶습니다.

18.7초라는 시간을 어떻게하면 구할 수 있나요?

최신 dev c++로 컴파일 하니까 실행 시간이 뜨더군요.

꼭 그게 아니더라도, 알고리즘 시작 부분과, 끝 부분에 time을 리턴하는 함수를 넣어두고

시작할 때 시간, 끝날 때 시간의 차이를 구하시면 됩니다. 시간 측정 함수는 구글링 하시면 많이 나와 있어요~~

아니면 프로파일링을 하시거나요. (용어가 맞나 모르겠지만..)

ps.

프로그램 내에서 변수 초기화 하고 그런 건 별로 안 들 겁니다. memset류로 큰 배열을 초기화 하면 시간이 들겠지만요.

입력받고, 계산하고 출력하는 거에서 시간을 거의 다 소모하니..