자바에서 N개짜리 배열 생성은 O(N)이 걸린다. (C++, C 도 마찬가지)

 

  혹시 C를 써봤다면, 자바에서는 배열 생성하면 모든 값이 초기화가 되어있는게 신기한 적이 있을 것이다. 배열을 만들어서 무언가 담고 싶을 때 C계열에서는 메모리 할당만 받고 끝나서 금방 끝나지만, 자바의 경우 배열을 만들고 초기화까지 해주는 아주 친-절한 언어이다. 

 

  그럼 단순히 int형 RxC 짜리 배열(int[][] arr = new int[R][C])을 만들 때 시간 복잡도가 어떻게 될까? 당연히 O(1)일 것 같지만, 자바에선 무려 O(RC)가 필요하다. 이하 10만x1만 짜리 배열 하나 만든건데 이것만 1초가 넘게 걸린다.

 

 

  그럼 이하 코드를 보자. 알고리즘을 풀 때 bfs를 여러번 돌릴 수 있다. 이 때, 사실 하나의 방문체크로 가능하지만(예를들어 하나의 큰 배열에서 빈 칸들의 구역을 나눌 때) 함수에서 계속해서 새로 만들어주는 식으로 짤 수도 있다. bfs 함수 내에서는 배열 생성 뿐 이므로 시간복잡도가 for문만 따져서 O(100) 일 것 같지만, 위에서 말했듯 배열 초기화 하는 만큼 시간 복잡도를 먹으므로 O(100 x r x c) 가 된다. 무려 1.6초나 걸렸다.

 

 

  방문 체크 배열이 하나로 충분하다면 아래처럼 코드를 짜면 된다. 아래의 경우 35ms가 걸린다.

 

---

 

참고로 C나 C++도 마찬가지다. 초기화 하지 않으면 4ms

 

{0}으로 초기화해주면 320ms (역시 c++.. 엄청나게 빠르다;;)

 

for문으로 초기화해주면 14초 (자바로 이거 돌렸으면 몇분 걸렸을듯)