메모리에 위치한 배열과 연산에 대한 Big-O value

배열에 대해 알아야 할 점을 간단히 정리해보자.

• 메모리에서 연속적으로 위치한다. 여기 저기 흩어져 있는 게 아니라, 한 배열의 요소들은 메모리 안에서 서로 인접해 있다. 메모리 안에 큰 블록이 생긴다고 생각할 수 있다. 배열의 길이가 한 번 정해지면 다시 수정할 수 없는 이유가 이 때문이다.
• 한 배열 안의 모든 요소들은 같은 크기를 갖고 있다. 이를테면 int 배열이면 4바이트씩 할당된다. 만약 primitive type이 아니라 object 배열이라면 어떨까? 배열의 원소가 object라면, 사실 그건 object 자체가 아니라 object reference다. 해당 object를 참조하고 있을 뿐이다. 그러니 어떤 object를 참조하든 상관없이 배열 안에서 항상 같은 크기를 갖고 있다.
  
• 바로 이러한 특성 때문에, 배열의 인덱스를 활용해서 각 요소의 주소값을 쉽게 계산할 수 있다. 만약 x(주소)에서 시작하는 배열이 있고 각 요소의 사이즈가 y라면, i번째 요소의 주소는 (x + i*y)와 같이 구할 수 있다. 따라서 우리가 어떤 요소의 인덱스를 알고 있다면, 그 요소를 반환하는 데 걸리는 시간은 모든 인덱스에 대해 동일하다. 몇 번째 요소이든, 다 똑같이 빠르게 접근할 수 있다. 배열에 요소의 개수가 몇 개이더라도 역시나 동일한데, 따라서 요소가 n개인 배열에서 특정 원소를 가져오는 연산의 시간 복잡도는 O(1)이다.
  이것이 가능한 이유는? 배열은 메모리 안에서 연속적으로 존재하고, 한 배열의 모든 요소들은 같은 크기를 갖고 있기 때문이다. 배열은 상당히 효율적인 자료구조다.

하지만, 원하는 인덱스를 모를 때는 어떨까?

public class Main {

  public static void main(String[] args) {
    int[] intArray = new int[7];

    intArray[0] = 20;
    intArray[1] = 35;
    intArray[2] = -15;
    intArray[3] = 7;
    intArray[4] = 55;
    intArray[5] = 1;
    intArray[6] = -22;

    int index = -1;
    for (int i = 0; i < intArray.length; i++) {
      if (intArray[i] == 7) {
        index = i;
        break;
      }
    }

    System.out.println("index = " + index);
  }
}

7이라는 값을 가진 요소가 몇 번째에 있는지 찾기 위해서, 0번째 요소부터 한칸씩 계속 이동한다. 찾을 때까지. 최악의 경우라면 n개의 요소에 대해 n번 탐색해야 할 것이다. 따라서 이 경우 시간 복잡도는 선형시간, O(n)이다. 

Operation	Time Complexity
Retrieve with index	O(1) ― Constant time
Retrieve without index	O(n) ― Linear time
Add an element to a full array	O(n)
Add an element to the end of an array (has space)	O(1)
Insert or update an element at a specific index	O(1)
Delete an element by setting it to null	O(1)
Delete an element by shifting elements	O(n)

즉 배열 연산에서 loop이 필요하다면 linear time일 것이고, loop이 필요 없다면 constant time일 것이다.