배열을 생성할 때 시간복잡도

Question

알고리즘 문제에서 배열 생성과 관련해서 시간초과가 발생하여 질문을 드립니다.

배열을 생성하지 않고 정답으로 인정되는 경우는 다음과 같습니다.

N의 최대값은 500이고, go()라는 메서드에서 4방향으로 탐색을 하기 때문에 최종 시간복잡도는 1_000_000입니다.

for(int i = 0; i < N; i++) {
	for(int j = 0; j < N; j++) {
		go(i, j);
	}
}

하지만, 아래와 같이 배열을 생성할 경우 시간초과가 발생합니다.

for(int i = 0; i < N; i++) {
	for(int j = 0; j < N; j++) {
		visited = new boolean[N][N];
		go(i, j);
	}
}

결론적으로는 visited를 생성할 필요가 없었지만, 문제를 푸는 과정에서 불필요한 생성이 있었는데 그 과정에서 시간초과가 발생하였습니다.

배열을 하나 생성할 때에는 O(1)의 시간복잡도를 가질거라고 생각하였는데, 더 많은 시간복잡도를 필요로 하는거 같습니다.

혹시 배열을 생성할 때 시간복잡도를 어떻게 계산하는지 알 수 있을까요?

kiel · Accepted Answer

루프 안에서 visited 를 매번 생성하신건가요?

방문을 했는지 여부 플래그 용도로 만드신것 같은데 루프 밖에서 생성하시면 어떻게 되나요?

O(1) 은 이미 만들어진 배열에 인덱스로 접근할때 얘기고요, 생성할때 드는 비용은 비교가 안되게 큽니다.

대부분의 코드들이 가능하면 데이터를 새로 생성하는걸 피하려고 하는 이유가 있습니다.

사과맛오렌지 · Answer

애초에 배열을 만든다는 건 새로운 객체, 그것도 최소한 N*N바이트의 값을 가지는 메모리를 계속 할당받는다는 뜻이죠.

배열을 넣기 위한 메모리 chuck를 OS 커널로부터 받아오는 작업, 그 각각의 값을 false로 초기화하는 작업(O(n))뿐만 아니라, visited에 기 할당되었던 객체가 unreachable될 경우 해당 배열이 차지하는 메모리를 다시 reclaim하고, 경우에 따라 또 다시 OS에 반납하는 수많은 작업 하나하나가 엄청난 오버헤드가 됩니다.

시간복잡도만 볼 것이 아니라, 각각의 operation이 만드는 오버헤드도 주의 깊게 보셔야 합니다.

메이플비 · Answer

일단 시간복잡도와 런타임실행시간의 차이를 잘 모르시는것 같습니다.

시간복잡도는 이론적으로 알고리즘간의 효율성을 비교하기 위해 사용하는것이고, 런타임시 실행시간은 다른 다양한것에 의하여 결정지어집니다.

그리고 시간복잡도는 빅오노테이션을 사용하셔서 표기하시는게 중요합니다. 알고리즘간의 효율성 비교를 위한것이기 때문에 숫자로 적는것은 의미가 없습니다.

일반적으로 코딩테스트 사이트들의 경우 같은 시간복잡도라고 하더라도 구현한 방식에 따라서 발생할 런타임실행속도 차이가 있는점을 보완하기 위해서 시간제한에 어느정도 여유를 둡니다.

예를들자면 같은 O(n)을 가지는 방식이라면 오버헤드가 발생할만한 구현을 했다고 하더라도 둘 다 통과하게 하는게 코딩테스트의 취지에 맞으니까 그렇게 설정을 많이 해둡니다.

하지만 뭐 이게 완벽할 순 없다보니까, 코딩테스트에서 기대하는 시간복잡도보다 더 느린 알고리즘을 사용했어도 통과하기도 하고 그런 상황도 충분히 발생합니다.

지금 생각해보실 문제는, 배열의 생성이 오버헤드를 발생시켜 시간초과가 난 것인가에 대해서 보다는 애초에 지금 작성한 알고리즘이 문제 작성자가 기대하는 시간복잡도보다 더 높은것인지 아닌지를 먼저 생각해보셔야 합니다.

배열을 생성할 때 시간복잡도

3개의 답변

Q&A 목록