Array.length 시간 복잡도 :: 마이구미

이번 글은 length에 대한 시간 복잡도를 알아보겠다.

제목을 어떻게 해야할지.. 참 고민했다.

무엇을 다룰 것인지는 소스를 통해 보면 확실히 이해할 것이다.

int[] array = new int[10];
// array.length -> 10

String s = "ABCD";
// s.length() -> 4

위와 같이 배열이나 문자열의 경우 크기(길이)를 가져올 수 있다.

가져온 크기를 통해 반복문의 루프 횟수를 정할 때 많이 이용한다.

// 1번
for(int i=0;i<array.length;i++) {
// ..
}

// 2번
int len = array.length;
for(int i=0;i<len;i++) {
    // ..
}

여러분은 1번과 2번의 경우 어떻게 사용하는가?

2번의 경우처럼 길이를 새로운 변수로 할당한 후 반복문을 사용하라고 많이 들어봤으리라 생각한다.

본인의 경우도 그렇게 사용하라고 많이 봐서 그렇게 사용하고 있었다.

그리고 대충 당연히 바로 접근하기 때문에 빠르기 때문이라고 생각했다.

오로지 속도 측면에서 빠르기 때문이라고 생각했다.

하지만 문득 다시 한번 생각해보았다.

결국 배열과 문자열의 경우에는 길이를 구하기 위해 계산이 필요한 것이 아닌, 단순히 length에 관련된 필드에 접근하기 때문에 시간복잡도가 O(1)이 나온다.

그렇다. 1번과 2번 모두 따지고보면 루프의 경우 시간복잡도가 O(n)이다.

위 그림에서 보다시피 시간의 차이가 없다고봐도 무방하다.

그렇다면 왜 2번의 경우를 쓰라고 하는 것일까?

바로 안전성이다.

반복문 안에서 길이가 변경될 수도 있기 때문에 예기치 않은 경우가 발생될 수 있다.

예를 들어 길이 4를 기준으로 루프를 돌릴껀데 반복문 안에서 길이가 3으로 변경된다면 의도치 않는 경우가 발생할 수 있기 때문이다.

// C++
strlen(s) // O(n)

strlen()의 경우에는 길이를 구하기 위한 계산에 의해 시간복잡도가 O(n)이다.

그렇다면 루프의 경우에는 O(n^2)이 된다.

이런 경우에는 2번의 경우로 해야 효율적이다.

성능에 문제가 없다면 변수 하나 추가되는 게 보기 싫을 수 있다.

이것 또한 개발자 특성에 따라 달라지겠지만....

에러를 예방하는 것은 좋은 습관이기에 안전한 코딩을 하는 것은 좋다고 본다.

Array length에 관한 시간 복잡도 숨겨진 비용 

http://stackoverflow.com/questions/17998386/time-complexity-or-hidden-cost-of-array-name-length-in-java