lucian0910   2년 전

아무리 찾아봐도 O(N^2) 이상으로 들어가는 부분이 없는 것 같은데 어느 부분에서 시간 초과가 나는지 알고 싶습니다 ㅠㅠ

djm03178   2년 전

sortArr에 할당되는 메모리의 총량, 그리고 그를 초기화하는 횟수가 O(N^2)입니다. right개를 할당하지 않고, right - left + 1개만 할당해서 풀어야 됩니다.

lucian0910   2년 전

전 단순히 for문이 1번만 쓰여서 n+1번 메모리 할당을 해서 괜찮을 줄 알았습니다. 단순히 2차원 배열 할당을 하면 무조건 O(n^2)이 뜨는 것인가요?

djm03178   2년 전

메모리 할당 자체는 O(n)번 일어납니다. 하지만 메모리 할당은 할당 크기가 클수록 오래 걸리는 작업입니다. 메모리가 할당될 때마다의 right 값을 모두 합하면 n^2에 비례하는 값이 나옵니다. 메모리 할당 뿐만 아니라, 10번째 줄의 루프가 도는 횟수만 세도 총합이 O(n^2)입니다.

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